法是图论里的欧拉公式 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法 是图论里 的 欧拉公式 一 这里 为顶 点数 ， 为边数 ， 为表 面数 。 当物体复杂时则用下列公式 一 一 这里 为体素的个数 ， 为孔的个数 ， 为环 的 个数 。 如图 ， 注意 计 算时圆孔看 作具有 个顶 点 ， 条边 ， 个表 而 的 形体 ， 即 沿 ， ， 四 点等分 。 这 里 圆孔和 表面 的 交线称 为环 。 系统 它是 目前应 用 上最完善的 一 个系统 。 它的 基 本元素 是半空间 。 从 木想法 是 立体是片段 的和 集 ， 而片段又是半空 间 的交集 。 也 即 而立体 一 一 ， ，… … 。 ， 门 … … 一， 产了、 勺土 一 现在 几何造型 正 在 向塑造更复杂的物体进行探 索 。 大致 说来有两种 做法 一种 做法 是 用 雄塑 曲面 。 代替平 面和 柱面 ， 曲面 由多边形 网 格经 过磨光而形成 ， 且 用 样条代替边 。 另一种做法 是先 用 多面 体粗糙 的表示 一 个物 体 ， 求出其应 有的 交线 ， 然后 再磨光这个多面 体结构 。 四 、 几 何 算 法 几何造型 系统的发展促进 了对几何算法进 行更多的 探 索 。 有效的 几何分 类和检索方法具 有极为重要的 地位 。 隐戴线 消除问题 是计 算机图学 中经 常遇 到的 问题 。 它可 以 抽象的 描 述 为 在三 维 空 间里 给定 几个多边形 ， 以 一 给定的 点来 看 ， 判 断 画 出来 的 图 那 些部 分可 见 ， 那些部分 不可 见 。 等在 年 比较 了十种 隐藏面 的 算法 后 ， 指出这 个 问题 实 质 上是 一个在三维 空 间里进行 分 类的 问题 。 在理论 上最坏情 况要 运 算 次 。 另外相 交问题 也是计 算几何重 要 问题 。 确定几个几何 对象是 否相 变 ， 如果 相交 ， 交 在什 么地方 ， 如果不 交 ， 何 处相 距最近 。 很 多几何造型 系统是 由 比较每 个而 和 每条边来 确定的 。 这种算法 要 次 。 年 提出采 用试探法 来 加 速这种判 断 。 空间检索里 的 经典问题 是 在平面 上给定一个点集 王 ‘ 和 另一不 属 于 笼 ‘ 的 点 ， 找 一点 ，〔 ‘ 卜离点 最近 。 称 它为邮局 问题 ， 并指出在平面 上 个点的这个问题 的 最佳解为 次 。 如果在这 个问题 中点集 ‘ 是 固定的 ， 而 取 许 多不 同的值 ， 为 了提高 效率 ， 则 要 引出一 个称 之为 网格 的结 构 。 在 网 格 里 ， 每 个点在一 个 凸 多边形 内 ， 称为 多边形 。 这 个多边形 区域 内的 点与该 点的 距 离要 比 ‘ 集 里 其他 点小 。 如 图 ， 图 中虚线所 画 的 是 对孟偶 网 格称 为 一 三 角网 。 给定一 个 。 。 网格则最邻 近的 检 索 问题 变为确定 点 在那个多边形 里 的问