由基本实体产生复杂几何实体的集合运算过程可以 用二叉树来描述。 这棵二叉树就称为CSG树。 实际的集 合运算过程不仅包含参加运算的基本实体，还包含进入 拼合运算的过程中实体的空间位置。 CSG树的根节点表 示的是最终的运算结果。
第10章 计算机图形学的几何造型技术 例如图10.3所示的实体， 可以用长方体和圆柱体 两种基本实体进行拼合获得:
立存在的低维部分，如二维的面、一维的线或零维的点。 这也就是通常所说的孤点、悬边或面。
CSG模型通过将简单的基本实体进行集合的并、交、
差运算产生复杂的几何实体。 在直接的集合运算过程中， 并不能保证所得结果的正则性。 为保证CSG模型结果的正 则性，需要对直接的集合运算结果进行正则化处理。
第10章 计算机图形学的几何造型技术 正则多面体的顶点、边、环、面之间满足一定的 条件： 如两点成一边，首尾相连的若干边组成环，环
的曲线，相同参数对应的两点之间形成对应。 其次是
每组对应点之间的过渡关系的建立。 比较简单直观的 是让所有对应点沿两点之间的连线进行过渡，所有连
线都与基准线具有同一个参数。 对应基准线的每一个
参数的所有点构成一条相应的过渡线。 在基准线不是 一点时， 令先前产生的两剖面线之间的过渡线的起点
平移到基准线上的相应位置。
实体= (长方体+ 粗圆柱体)-细圆柱体(10.1.1)
第10章 计算机图形学的几何造型技术
(－) (＋)
图10.3 基本三维几何实体数据结构
第10章 计算机图形学的几何造型技术 2. 实体的正则性及欧拉运算 前面我们已经提到了实体的正则性。 其本质的含义就
是说我们要处理的三维实体是真正的三维几何体，不包括独
第10章 计算机图形学的几何造型技术
第10章 计算机图形学的几何造型技术
10.1 三维欧氏几何实体造型方法 10.2 分形几何方法
习题
第10章 计算机图形学的几何造型技术
10.1 三维欧氏几何实体造型方法
10.1.1 基本三维欧氏几何实体描述 通常情况下， 三维实体是由封闭表面围成的有限 的三维空间，一个基本的三维几何实体由点、线、面 构成。这里以最简单的长方体为例来说明。如图10.1所 示，如果这个长方体中间有圆柱形空洞，则相应物体
空间与两个圆柱半空间的交，并且要注意两个圆柱半 空间的不同： 一个是内侧，另一个是外侧。
第10章 计算机图形学的几何造型技术
图10.4 几何实体半空间表示法
第10章 计算机图形学的几何造型技术 10.1.4 三维欧氏几何实体的面表示法 1. 扫描曲面的产生
一种比较常用的操作性面表示法称为扫描或扫成 (sweeping)法。 它用来表示在移动某个指定的几何 对象的过程中经过的三维空间区域产生的几何实体。 移动的方式包括平移、旋转及其它对称变换等。 在移 动的过程中，移动的几何对象大多为二维几何体部分 或全部边界线，其形状可以变化，也可以不变化。由 于这类实体的几何形状通常被其边界曲面所指定，因 此我们主要关心其作为扫描面的边界曲面的形状，而 较少提到三维扫描几何实体。
可界定出面，面包围成体等等。 其中的点、边、面在
几何上要协调一致，在拓扑关系上也要满足一定的要 求，其中一个重要的结果就是欧拉公式:
V(顶点数)-E(边数)+F(面数)-R(环数)+2H(通孔数)2S(3D实体数)=0 (10.1.2) 其中: 通孔表示没有上、下底面的洞，不包括凹陷 的坑; 3D实体表示相互不连通的3D几何实体。
翼边数据结构通过边指明了如上所述的所有相关
信息，可帮助我们方便快速地查找构成体的各几何元 素之间的连接关系。 当然，这种方法的存储内容有重
复，要求存储的信息比较大。
第10章 计算机图形学的几何造型技术 2. 数据的对称结构 翼边数据结构是以边为中心表示实体的方法。 用
对称数据结构表示实体时，点、边、面处于对称的地
终渐变成终止剖面线时扫描产生曲面。这个过程中要 做的是建立起始和终止两条剖面线上点的对应关系。
第10章 计算机图形学的几何造型技术
Q( )
P(u)
图10.5 一条剖面线沿一条基准线
第10章 计算机图形学的几何造型技术
P1(u) Q( )
P0(u)
图10.6 两条剖面线沿一条基准线
第10章 计算机图形学的几何造型技术 为简化问题，先考虑基准线为一个点的特殊情 形。 一般认为这两条剖面曲线都是参数空间［0, 1］上
位： 由某个边出发，可明确指出边所在的面和构成边 的点； 同时，由某个点出发，可明确指出边所在的所
有边和所有面； 由某个面出发，也可明确指出组成面
的所有边和所有点。
第10章 计算机图形学的几何造型技术 10.1.3 三维欧氏几何实体的体表示法 1. CSG树构造法
CSG即Constructive Solid Geometry（构造实体几何） 的缩写。 这个方法的思路是将简单的基本实体通过集合 的并、交、差运算产生复杂的几何实体。 常用的基本几 何实体有长方体、球体、圆柱体、圆锥体、圆台、三维 环等，甚至还有更复杂的自定义实体。
第10章 计算机图形学的几何造型技术 图10.7可解释成给定一条剖面线和两条基准线，让剖 面线的两端分别沿两条基准线的起点同步移动到基准线的 终点时扫描产生曲面。 抛开剖面线和两条基准线的实际含 义，交换两者的名称，则这里曲面的生成与图10.6中给定 两条不同的剖面线和一条基准线生成曲面的方式相同。 给 定两条剖面线和两条基准线生成曲面可以用孔斯曲面的方 法。 扫描面生成曲面的方式由于操作简单、直观， 因而易 于在交互设计中应用。 给定剖面线和基准线后生成曲面的 数学表达式都不难依据其生成方式求得，详细的细节推导 留做习题。
第10章 计算机图形学的几何造型技术 (3) mev(v1，v2，e， f1，f2): 在已知顶点v1和v2之间 生成一条新边e， 由此产生f1的邻面f2。 如分裂了一
个顶点， 则产生一条环形边， 把面分成两个区域。 其
逆操作为kev(v1，v2，e，f1，f2)。 (4) kekr(v1，v2，e): 删除v1和v2之间的边e， 生成内
第10章 计算机图形学的几何造型技术
Q0( ) P(u) Q1( )
图10.7 一条剖面线沿两条基准线
第10章 计算机图形学的几何造型技术
图10.8 常见曲面的扫描产生
第10章 计算机图形学的几何造型技术 需要说明的是，剖面线和基准线都可以是闭曲线。 如图10.8所示，常见的旋转面就是基准线为闭曲线圆弧的扫 描面。 圆柱面就是剖面线为闭曲线圆弧的扫描面。 圆环曲 面就是剖面线和基准线都为闭曲线圆弧的扫描面。 2. 曲面求交 前面的曲面的造型技术在实际应用中常需要把单个的曲 面拼合起来， 以构成设计所需要的复杂外形。 另外，三维 实体的并、交、差也需要确定相关集合的边界面的交叉部分。 所有这些都涉及到不同曲面的相交和分割问题。 可以说曲面求交是曲面及实体造型操作中最基本的算法 之一，使用得最频繁。 因此要求曲面求交必须准确、可靠、 迅速， 并且保留相交曲面的已知拓扑关系， 以便获得正确 的实体造型结果。
第10章 计算机图形学的几何造型技术 通过面指定的半空间即是我们所需要的基本几何 体。 一个三维实体可以用若干个面所指定的实半空间
的交来表示。 例如如图10.4所示， 一个长方体可以看
成是由六个侧平面指定的六个半空间的交； 一个圆柱 体可以看个空心圆柱体则是由两个平面定义的半
第10章 计算机图形学的几何造型技术 边是物体上两个相邻面的交界线段， 通常一条边 只能为两个面所共有。 边有从起点指向终点的方向，
除首尾相连的封闭边外，不能自交。
顶点是边的端点， 不能出现在边的内部， 也不能 孤立存在于物体的内部。 复杂的三维几何实体可以由简单的基本几何实体 组合构成。 下面介绍结合计算机的要求，用点、线、 面、体表示复杂的三维实体的各种方法。
第10章 计算机图形学的几何造型技术
体：三维实体
壳：成组的面，体的边界
面：平面或曲面
环：成组的边，面的边界
线：直线或曲线边
点：顶点
图10.2 基本三维几何实体的构成要素
第10章 计算机图形学的几何造型技术 图10.1中的边的顶点信息只存储一次，有一个惟一 的标识号。 但它被左右邻面的环表引用两次: 一次正 向，一次反向。 可以在环的边表结构中设一标识位， 说明每一条边在环的统一走向中与边的原始定义方向 一致还是相反。
(1) mvfs(v, f): 输入一个点， 构造一个拓扑球， 也就是建
立一个实体骨架， 形成边界模型的初始状态。 这时只有一个 顶点和一张没有边界的(球) 面。 其逆操作为kvfs(v, f)。
(2) mev(v1, v2, e): 输入一个顶点v2， 与已有的顶点v
1连成一条新边e。 其逆操作是kev(v1，v2，e)。
第10章 计算机图形学的几何造型技术 10.1.2 由三维欧氏几何实体表示的数据结构 1. 数据的翼边结构 正规形体模型的翼边数据结构表示的实体的分层 几何实体结构如图10.2所示。 翼边结构由Baumgart等 提出，它以边为中心，清楚说明多面体模型中点、线、 面之间的拓扑关系。图10.1表示从外面观察多面体的一 条边Ei 时，可以见到边Ei 的前后两个顶点Vi0 和Vi1 ，左 右两个邻面Fi0 和Fi1 ，以及上下左右四条邻边: 左顺时 针边Eil0 、左逆时针边Eil1 、右顺时针边Eir0 和右逆时针 边Eir1。
可按图10.2所示结构层次的几何对象进行描述。
第10章 计算机图形学的几何造型技术
E il 1
Vi0 Fi0
E il 0
Eir1
Ei vi1 Eir0
Fi1
图10.1 基本三维几何实体的数据结构
第10章 计算机图形学的几何造型技术 图10.2中各名词术语的意义可进一步明确如下： 壳是由具有某种一致方向的一组面的集合构成的， 它形 成封闭的单一连通空间并构成实体的边界。 面是有界、不自交的连通表面， 带有方向性，由一个外 环和若干内环作边界。 面可以无内环， 但一定有外环。 一 张面只能从属于一个壳。 环是面的封闭边界， 由有向边按一定顺序组成。 环不 能自交，即环的各条组成边除了公共端点外不能再有其它交 点。 环有内外之分， 确定面中内孔或凸台周界的环是内环， 具有顺时针走向； 确定面的最大外边界的环是外环， 具有 逆时针走向。 基于这一定义， 在面上沿任一条边的正向前 进， 物体内部总保持在左侧、外部总保持在右侧。