D0I:10.13374/j.issn1001-053x.1983.02.036 北京钢铁学院学报 1983年第2期 发展中的计算几何 工程图学教研室陈仁宽 一、前 言 计算几何是研究空间形状，结构在计算机内表达和构形的科学，它是随着计算机辅助设 计和辅助制造系统的发展，随着分析航空和卫星照片的需要，逐渐形成的一个计算机科学和 数学相结合的新分枝。它涉及诸如计算机辅助几何设计（简称CAGD)和模式识别(pattern.- recognition)等许多领域。 计算几何的出现，首先是由于目前的计算机的存储是一维的，对信息是进行“串行加 工”的，而所要表达的对象是二维或三维的。这就出现维度不匹配的问题。其次经典的几何 学虽然结构严谨、表达简洁，但不适于用计算机来实现。因此有必要发展计算几何来导出计 算机擅长的算法。 计算几何在六十年代里尚处于实验室研究阶段，十七年代后，在理论和，实践上都取得 了不少进展。在大量工作基础上，1974年在UTAH大学召开了第一届国际CAGD会议，标 志着它的发展进入了一个新的阶段。 由于篇幅的关系，本文仅其主要内容：曲线和曲面的表达，三维体素的几何造型和几何 算法作扼要的介绍。 二、曲线和曲面 在CAGD中用到的曲线有二次曲线、参数样条曲线、Bezier曲线和B样条曲线等。在 表示的方式上经常使用〔0,1)区间上的矢值函数。例如连结点P(0)和P(1)的直线段。表 示为 a(t)=(1-t)(0)+t户(1) t∈〔0,1) 下文对二次曲线和参数样条曲线从略，仅介绍Bèzier曲线和B样条曲线以窥一班。 1.Bezier曲线 它是以给定的型值点定义一多边形，然后按下面的表达式产生一条曲线来光滑的逼近这 个多边形。 n a()=∑i,Bw() t∈(0,1) i=0 其中Bw,i(t)=()t(1-t)N-称为Bernstein基函数。 由上式可知， 169
北 京 钢 铁 学 院 学 报 年第 期 发 展 中 的 计 算 几 何 工 程 图学教研 室 陈仁 宽 一 、 前 口 计 算几 何是 研究 空 间形状 ， 结 构在计 算机内表达和 构形的 科学 ， 它是随 着计 算机辅助设 计和 辅助制造系统 的发展 ， 随着分析航空和 卫 星照片的 需要 ， 逐渐形成的一个计 算机科学和 数学 相 结 合的 新 分枝 。 它涉及诸 如计 算机辅助几何设计 简称 和 模式 识别 一 。 。 ‘ 等许多领域 。 计 算几何的 出现 ， 首先是 由于 目前 的计算 机的 存储是 一 维的 ， 对信息是 进行 “ 串行加 工 ” 的 ， 而所要表 达 的对 象是二 维 或三维 的 。 这 就出现维度不 匹配的 问题 。 其次经典的 几何 学虽然结 构严 谨 、 表 达 简洁 ， 但不适 于 用计 算机来实现 。 因此有必 要发展计 算几何来导出计 算机植长 的 算法 。 计算几何在六 十年代里尚处于实验室 研究阶段 ， 十七 年代后 ， 在理论和 ， 实践上都取 得 了不 少进展 。 在大量工 作基础 上 ， 年在 大学 召开 了第一届 国际 会议 ， 标 志 着它的 发展 进入 了一个新的阶段 。 由于篇幅 的关系 ， 本文仅其主 要 内容 曲线和 曲面的表达 ， 三 维体素的 几 何造型 和 几 何 算法作扼 要的介绍 。 二 、 曲线和 曲面 在 中用 到的 曲线有二次 曲线 、 参数样条 曲线 、 “ 曲线和 样条 曲线等 。 在 表示 的 方式 上经 常使 用 〔 ， 〕 区 间 上的 矢值 函数 。 例如连 结点 和 的直线段 。 表 示为 二 如 一 下文对二次 曲线和 参数样条曲线 从 略 ， 仅介绍 己 曲线和 色 曲线 〔 〔 ， 〕 样条曲线 以窥一班 。 它是 以 给定 的型值 点定义 一 多边形 ， 然后 按下面的表达 式 产生 一条曲线来光滑的逼 近这 个多边形 。 二 一 ， ‘ 〔 ， 艺 〕 其 中 ， ‘ 梦 ‘ 一 、 一 ‘ 称为 泣 基 函数 由 上式可 知 ， DOI ：10．13374／j ．issn1001－053x．1983．02．036
d(0)=p,d1)=户 曲线段通过起点和终点，且切于首、未两条边。当t≤1时，BN,(t)相当于给每个点P, 加权，所有点下：的权之和三B,:()=1。这意味着曲线段所有的点一定落在多边形顶点 的凸包之内。因此，.这种曲线具有变差减小的性质(varition diminishing).,见图1。 P 图1 当N=2时，曲线所表示的就是由三点定义的抛物线 (t)=(1-)2P。+2t(1-t)p,+t2市： 2.B样条曲线 如同把多项式插值推广到分段多项式插值一样，我们可以把Bezier曲线推广到B样条曲 线，仍用一系列形成多边形的顶点来定义B样条曲线。不过 这里不用Bernstein基函数而用B样条基函数。 N a()= pBw,《t) i=1 这里BM,,(t)用选推过程来定义则为 1 当t:≤t≤ti+:时 其它则 图2 M=2 BM,:()=,t-t,·BM-,(t) tit-1ti +tMt.BM-1+1(t)M>1 ti+M-ti+1 B样条基函数有局部支集性质，也就是仅在有限的区间 上它的函数值为正且≤1，其它地方就都为零。这是它比其 它曲线好的地方。由于局部支集性质，它产生的曲线有下列 性质： (1)扰动定义曲线的多边形上一个顶点，仅在这个顶点 的附近，曲线有局部扰动，如图2。 (2)凸包性质：B样条曲线上任何一节(span)都是 由M个相邻的顶点来确定的，由于权函数BM,1(t)是非负 的且总和为1，因此这一节曲线段必位于这些顶点形成的凸 包之内。如图3当M取不同的值，曲线应为在相应的凸包集 合内。因此，B样条曲线比同样的多边形定义的Bezier曲 线更逼近多边形。 图3 170
曲线段通 过起点和 终点 ， 且 切 于 首 、 加权 ， 所有点 的 凸包之 内 。 卜 ‘ 的 权 之和 名 ’ 连一 。 ， ， 末 两条边 。 当 《 时 ， ， ‘ 相 当于 给每 个点 ‘ ‘ 。 这意味着曲线段所有的点一定落在多边形顶 点 因此 ， 这 种 曲线具有变差 减小的性 质 ， 见 图 。 图 当 时 ， 曲线所表 示的 就是 由三 点定义的抛物线 样条曲线 叫卜 卜 甲全 一 一 “ 如同把多项 式插值推广 到分段 多项式插值 一样 ， 我们可 以 把 ‘ 曲线推广到 样 条 曲 线小 用一系列形 成多边形 的 顶 点来 定义 “ 样条 曲线 。 不 过 尸心 这里不用 基 函数而用 样条 基 函 数 。 耳 一一了 ， 岌 · 艺式 · ， ， 这 里 ， ‘ ， ‘ ， 用选 推过程 来定义则为 当 ‘ 《 《 ‘ 十 时 其 它则 ‘ 一 一 气 ’ ” 一 ‘ ， ‘ ’ 户碧于兰 一 ‘ 亡 · 一 一 ‘ ， 时 样条基 函数有局 部支集性质 ， 也就 是仅在有限的 区间 上它的 函数值 为正且《 ， 其 它地 方就都为零 。 这是 它 比其 它 曲线好的 地方 。 由于局部 支集性 质 ， 它产生的 曲线有下列 性 质 扰 动定义 曲线 的 多边形 上一个顶 点 ， 仅 在这个顶 点 的 附近 ， 曲线有局部扰 动 ， 如图 。 凸包性 质 样条 曲 线 上 任何 一 节 都是 由 个相 邻的顶 点来 确定的 ， 由于权 函数 ， 是非 负 的且总和 为 ， 因此 这一节 曲线段必 位于 这些顶 点形成的 凸 包 之 内 。 如图 当 取不 同的值 ， 曲线应 为在相应 的 凸包集 合 内 。 因此 ， 样 条 曲线 比 同样 的 多边形 定义 的 “ 曲 线 更逼 近 多边形 。
(3)B样条曲线也具有变差减小的性质。因此特殊情况，当M个相继顶点是共线时，由 于这M个点可以确定曲线上的一节，且根据变差减小性质，其对应的节是一条直线段。 3.Bèzier曲面片 这种曲面可以看作由一个多边形网格通过Bèzier算子逼近得出。它只在四个角点处是 插值的。其余点就不再通过网格的顶点。其表达式为： s)=∑市()1-0()加1-)- i=0j=0 这种曲面已用于汽车车身设计。详细内容可参阅文献(3)。 4.B样条曲面片 为了改进Bezier曲面片的装配，可采用同样的方法引出B样条曲面片。 MN S(t,)=∑∑市BL,(t)B,1u) i=0j=0 以上BL,,(t)和BM,,(u)分别为参变量t和u的B样条基函数。可参阅文献〔4)。 5.Coo ns曲面片 这里仅介绍双三次曲面，根据C0os的表达式能够构造出满足任何高阶边界条件的曲 面。然而在实际应用中，无法提供那么多的信息，因此还是用双三次曲面。采用C0os的 符号，其表达式为： uw=〔F。F1GgG)000100m01w1/F。 101110w11w 00u 01u 00uw 01uw Go 10u 11u 10uw 11G1 以上四阶方阵中全部元素都是曲面角点上的信息，记为B。其左上角的二阶子阵是角点 位置矢量，右下角的二阶子阵是角点的扭矢，其余两个子阵是角点沿两个方向的切矢。F, F1,G,G1是三次混合函数。 (F。F:G。G1)=〔1uu2u)M :1000 M= 001 0 -33-2-1 2-211 并有 F。 F =M' Go w2 G1 w3 令 u=〔1uu2u3) W=(1 ww2 w3) 则曲面片方程可表达为： uw=UMBMW 171
样 条 曲线也具有 变差减小的性 质 。 因此 特殊 情况 ， 当 个相 继顶 点是共线 时 ， 由 于这 个点可 以 确定 曲线 上的 一节 ， 且根据 变差减 小性 质 ， 其对应 的节是一 条直 线 段 。 已 曲面 片 这 种 曲面可 以 看作 由一个多边形 网 格通 过 仑 算子逼近得出 。 它只 在 四 个角点处是 插值 的 。 其余点就不 再通 过网 格的顶 点 。 其表达 式 为 ， · 卜 乏 乏， ‘ ， 瞥 ‘ 卜 一 梦 一 卜 · 一 二 这种 曲面 巳用于 汽车车身设计 。 详细 内容可 参阅文献 。 样条曲面 片 为 了改 进 色 曲面片的装配 ， 可 采 用 同样 的 方法 引出 样条曲面片 。 ， 乏 乏节 ‘ ， ， ‘ 卜 ， ， ， 以 上 ， ‘ 和 ， ， 分别为参 变量 和 的 样 条基 函数 。 可 参阅文献 〔 。 曲 面 片 这 里仅 介绍双三 次曲面 ， 根 据 。 。 的表 达 式能够构造出满足任何高阶边 界条件的 曲 面 。 然而 在实际应 用 中 ， 无法 提供 那 么多的信息 ， 因此 还是 用双三 次 曲面 。 采 用 。 。 的 符号 ， 其表达 式 为 。 ， 。 〕 。 ， 。 ， 。 。 ， 以 上四 阶方 阵 中全部元素都是 曲面 角点 上的信 息 ， 记为 。 其左 上角的二 阶子阵是角点 位置 矢量 ， 右 下角的 二阶子 阵是角点的扭 矢 ， 其余两个子阵是 角点沿两 个 方 向的 切矢 。 。 ， 是三 次混 合 函数 。 。 二 。 〕 〔 吕 〕 ’ 一 一 一 一 … … 几﹄ 令 〔 名 吕 〕 则 曲面片方程可表 达 为 ’
三、三维体素的几何造型(VolumeModelling) 为了解决一维的计算机存贮和现实世界的不匹配，人们探素构成对应于三维形状信息的 机内存贮，然后进行形状处理的途径。这就发展成为三维体素几何造型的研究。从1968年以 来，这个领城一直十分话跃。目前最有影响的是下列三个几何造型系统：1罗彻斯特大学的 PADL2)北海道大学的TIPS3)剑桥大学的BUILD。几何造型的发展促进了机械零 件的机辅设计。日本的TIPS系统就是为话应试行型和对话型机辅设计而研制的。 几何造型从采用的数学方法来说基本可以分为两类。BUILD系统为一类，用数据结构 建立各几何元素之间的拓扑关系，棱边也在机内有明确的定义。另一类为以PADL和TIPS 系统为代表，采用半空间和布尔运算为其基本的元素和方法，棱边在机内没有明确令义，但 能通过运算确定。 1.BUILD系统 它的雏型是由剑桥大学I,C.Braid在1973年的论文中提出来的。他定义了六种体素如 图5。两种拼合的算法：(1)合并(Merge)即两个体素共面相连接；(2)相交。 几何元素的数式描述仍用解析的方式。如直线表示为 〔x,y,z,1)=〔1-t,t) 平面表示为 A (x,y,z,1) B =0 C D 它的数据结构采用表结构，定义各几何元素和它们之间的拓扑关系。因此，如图4的立 体可以先对体素六面体进行缩放、旋转等变换，然后进行合并运算。合并算法实际上是求重 合面各棱边的交点，插入顶点表，构造新的边界等更新数据结构的过程。 11-21+9-×1-2×1+2 图4 图5 图6 BUILD系统的数据结构，后来采用了B.G.Baumgart的翼边结构，另又定义了逻辑非 (Negation)、平扫(Sweeping)、旋转(Swing)、扭挠(Tweaking)等运算，以便 形成零件中孔洞、车削加工和拔模斜度等结构。 BUILD的另一重要内容为系统自动检验通过运算形成的模型是否合理。采用的数学方 172
三 、 三 维体素的几 何造 型 为 了解决一维的计 算机存贮和 现实世 界的不 匹配 ， 人们探索构成 对应 于三 维形状信息的 机 内存贮 ， 然后 进行形状 处理的途径 。 这就 发展成为三 维体素几何造型 的 研究 。 从 年以 来 ， 这个领域一直十分 活跃 。 目前最有影 响的 是下列三 个几何造型 系统 罗彻斯 特大学 的 北海道 大学的 剑桥 大学 的 。 几何造型 的发展促进 了机械零 件的机辅设计 。 日本的 系统就是为话应 试 行型 和 对话型 机辅设计 而研制的 。 几何造型 从采 用的数学方法来说基 本可 以分为两类 。 系统为一类 ， 用数据结 构 建立 各几何元素之 间的拓扑关系 ， 棱 边也在机 内有 明确的定义 。 另一类为以 和 系统为代表 ， 采 用半空 间和布尔运 算为其 基本的元素和方法 ， 棱边在机内没有明 确令义 ， 但 能通 过运 算确定 。 系统 它的雏型 是 由剑桥 大学 在 年的 论文 中 提 出来 的 。 他定义 了六种 体素如 图 。 两种拼合的 算法 合 并 即两个体素共面 相连接 相 交 。 几何元素的数式描述仍 用解析的 方式 。 如直线表示为 〔 · ， ， · ， 〕 〔 一 ， 〕「 一 〕 平面表示为 ︸ 一 、、‘几 ‘ 】 ， ， 一 它的数据结构采 用表 结 构 ， 定义 各几何元 素和 它们 之 间的拓扑关系 。 因此 ， 如图 的 立 体可 以先对体素六 面体进行缩放 、 旋转等变换 ， 然后进行 合并运 算 。 合并算法 实际 上是求重 合面 各棱 边的交点 ， 插入顶 点表 ， 构造新 的边 界等更新数据结 构的过程 。 司 ’ 旬 矽 回 印 嘟 一 又 一 又 图 图 图 系统的 数据结构 ， 后来采 用 了 的翼边结 构 ， 另又定义 了逻辑非 、 平 扫 、 旋转 、 扭挠 等运 算 ， 以便 形成零件 中孔洞 、 车削加工 和 拔模斜度等结 构 。 的 另一重 要 内容为系统 自动检验通 过运算形成的模型 是 否合理 。 采 用的 数学方
法是图论里的欧拉公式 V-E+F=2 这里V为顶点数，E为边数，F为表面数。当物体复杂时则用下列公式 V-E+F=2S-2H+R 这里S为体素的个数，H为孔的个数，R为环的个数。 如图6，注意：计算时圆孔看作具有8个顶点，12条边，4个表面的形体，即沿A, B,C,D四点等分。这里圆孔和表面的交线称为环。 2.TIPS系统 它是目前应用上最完善的一个系统。它的基本元素是半空间。基木想法是立体是片段 (segmcnt)的和集，而片段又是半空间E的交集。也即 n S=EnE21..nE=0 E i=1 m 而立体 P=S,US2…USm=US, j=1 m =U n {.n,E} j=1i=1 现在几何造型正在向塑造更复杂的物体进行探索。大致说来有两种做法：一种做法是用 雕塑曲面(Sculpture surface)代替平面和柱面，曲面由多边形网格经过磨光而形成，且 用B样条代替边。另一种做法是先用多面体粗糙的表示一个物体，求出其应有的交线，然后 再磨光这个多面体结构。 四、几何算法 几何造型系统的发展促进了对几何算法进行更多的探索。有效的几何分类和检索方法具 有极为重要的地位。 隐藏线消除问题是计算机图学中经常遇到的问题。它可以抽象的描述为在三维空间里 给定几个多边形，以一给定的点来看，判断画出来的图那些部分可见，那些部分不可见。 Sutherlend等在1973年比较了十种隐藏面的算法后，指出这个问题实质上是一个在三维空 间里进行分类的问题。在理论上最坏情况要运算O(nlogn)次。 另外相交问题也是计算几何重要问题。确定几个几何对象是否相变，如果相交，交在什 么地方，如果不交，何处相距最近。很多几何造型系统是由比较每个而和每条边来确定的。 这种算法要O(n2)次。1979年Boyse提出采用试探法来加速这种判断。 空间检索里的经典问题是：在平面上给定一个点集{P,}和另一不属于{P,}的点Q,找 一点P,∈{P,}离点Q最近。Knuth称它为邮局问题，并指出在平面上n个点的这个问题的 最佳解为O()次。如果在这个问题中点集{P:}是固定的，而Q取许多不同的值，为了提高 效率，则要引出一个称之为Voronoil网格(Voronoi tesselation)的结构。 在Voronoil网格里，每个点在一个凸多边形内，称为Voronoi多边形。这个多边形区域 内的点与该点的距离要比P:集里其他点小。如图7，图中虚线所画的是对偶网格称为Delau一 ney三角网。给定一个Voronoi网格则最邻近的检索问题变为确定点Q在那个多边形里的问 173
法 是图论里 的 欧拉公式 一 这里 为顶 点数 ， 为边数 ， 为表 面数 。 当物体复杂时则用下列公式 一 一 这里 为体素的个数 ， 为孔的个数 ， 为环 的 个数 。 如图 ， 注意 计 算时圆孔看 作具有 个顶 点 ， 条边 ， 个表 而 的 形体 ， 即 沿 ， ， 四 点等分 。 这 里 圆孔和 表面 的 交线称 为环 。 系统 它是 目前应 用 上最完善的 一 个系统 。 它的 基 本元素 是半空间 。 从 木想法 是 立体是片段 的和 集 ， 而片段又是半空 间 的交集 。 也 即 而立体 一 一 ， ，… … 。 ， 门 … … 一， 产了、 勺土 一 现在 几何造型 正 在 向塑造更复杂的物体进行探 索 。 大致 说来有两种 做法 一种 做法 是 用 雄塑 曲面 。 代替平 面和 柱面 ， 曲面 由多边形 网 格经 过磨光而形成 ， 且 用 样条代替边 。 另一种做法 是先 用 多面 体粗糙 的表示 一 个物 体 ， 求出其应 有的 交线 ， 然后 再磨光这个多面 体结构 。 四 、 几 何 算 法 几何造型 系统的发展促进 了对几何算法进 行更多的 探 索 。 有效的 几何分 类和检索方法具 有极为重要的 地位 。 隐戴线 消除问题 是计 算机图学 中经 常遇 到的 问题 。 它可 以 抽象的 描 述 为 在三 维 空 间里 给定 几个多边形 ， 以 一 给定的 点来 看 ， 判 断 画 出来 的 图 那 些部 分可 见 ， 那些部分 不可 见 。 等在 年 比较 了十种 隐藏面 的 算法 后 ， 指出这 个 问题 实 质 上是 一个在三维 空 间里进行 分 类的 问题 。 在理论 上最坏情 况要 运 算 次 。 另外相 交问题 也是计 算几何重 要 问题 。 确定几个几何 对象是 否相 变 ， 如果 相交 ， 交 在什 么地方 ， 如果不 交 ， 何 处相 距最近 。 很 多几何造型 系统是 由 比较每 个而 和 每条边来 确定的 。 这种算法 要 次 。 年 提出采 用试探法 来 加 速这种判 断 。 空间检索里 的 经典问题 是 在平面 上给定一个点集 王 ‘ 和 另一不 属 于 笼 ‘ 的 点 ， 找 一点 ，〔 ‘ 卜离点 最近 。 称 它为邮局 问题 ， 并指出在平面 上 个点的这个问题 的 最佳解为 次 。 如果在这 个问题 中点集 ‘ 是 固定的 ， 而 取 许 多不 同的值 ， 为 了提高 效率 ， 则 要 引出一 个称 之为 网格 的结 构 。 在 网 格 里 ， 每 个点在一 个 凸 多边形 内 ， 称为 多边形 。 这 个多边形 区域 内的 点与该 点的 距 离要 比 ‘ 集 里 其他 点小 。 如 图 ， 图 中虚线所 画 的 是 对孟偶 网 格称 为 一 三 角网 。 给定一 个 。 。 网格则最邻 近的 检 索 问题 变为确定 点 在那个多边形 里 的问
题了。 用数学形式描述点P:的Voronois多边形为 V=jQ;H(PP) 这里H(P:,P,)为以P,到P,的垂直平分线为界的包括P点的半平面。Voronoi网格 是由几个V:多边形组成。由这个定义直接形成算法其效率是很低的，要O(n21og)次， 在1978年出现Green-Sibson算法和Shamos算法比由定义直接形成的算法要好。 图7 近年来我国也开展了CAGD和计算几何的研究。在曲线而面领域提出了正负法等绘图 的数学方法，在样条函数，双圆弧拟合等方面的研究也取得了成果。几何造型方面也有个别 单位正在进行探素性的工作，也取得一定成果。可以期望随着我国四个现代化事业的发展， 这门学科的研究也会在我国活跃地开展起来的。 参考文献 (1)A.R.Foinest,Computational Gcometry Achievements and Problems (1974) (2)A.R.Forrest.Recent Work on Geometric Algorith ms.(1978) (3)P.Bezier.Mathemstical and Practical Possibities of UNISURF (1974) (4)W.J.Gordon and R.F.Riesenefeld.B-Spline Curves and Surfaces. (1974) (5)B.A.Barsky and D.P.Greenberg.Determining a Set ob B-spline Control Vertices to Generate an Interpolating Surface (1980) (6)Okino,N.,Kakazn,Y.and Kubo.H.TIPS-1:Technicae In bor mation Processing System for Computer-Aided,Design,Drawing and Manufac- -turing. (7)Shamos.M,I.Computa Sional Geo metry(1974) 174
题 了 。 用数学形式描述 点 ‘ 的 多边形 为 ‘ 母 ‘ ‘ ， ，， 这 里 ‘ ， ， 为 以 ‘ 到 ，的 垂直平 分线为界的包 括 ‘ 点的半平面 。 网格 是由几个 ‘ 多边形 组成 。 由这个定义 直接形 成 算法 其效 率是很低 的 ， 要 次 ， 在 年出现 一 算法和 算法 比由定义 直 接形 成的 算法 要好 。 图 近年来我 国也开 展 了 和计 算几何 的 研究 。 在 曲线而 而领域提出 了正 负法 等绘 图 的数学 方法 ， 在样条 函数 ， 双 圆弧 拟合 等方面的 研究也取 得 了成果 。 几何造型 方面 也有个别 单位正 在进 行探 索性 的工 作 ， 也取 得一定成果 。 可 以 期望 随着我 国四 个现代化事业 的发展 ， 这 门学科的 研究也 会在我 国 活跃 地开 展起来 的 。 今 考 文 献 一〕 ， 〔 〕 〔 〕 色 〕 一 ， 〔 〕 一 〕 ， ， ， 一 一 ， ， 一 一 〔 〕
