第7章 几何造型技术

1、形体表示模型n在实体模型的表示中，基本上可以分为分解表示、构造表示和边界表示三大类。n1、分解表示将形体按某种规则分解为小的更易于描述的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都能够直接描述为止。分解表示-空间位置枚举表示n形体空间细分为小的均匀的立方体单元。n用三维数组CIJK表示物体，数组中的元素与单位小立方体一一对应n当CIJK = 1时，表示对应的小立方体被物体占据n当CIJK = 0时，表示对应的小立方体没有被物体占据分解表示-空间位置枚举表示n优点n简单，可以表示任何物体n容易实现物体间的交、并、差集合运算n容易计算物体的整体性质，如体积等n缺点n占用大量的存

2、储空间，如1024*1024*1024 = 1G bitsn物体的边界面没有显式的解析表达式，不适于图形显示n对物体进行几何变换困难，如非90度的旋转变换n是物体的非精确表示分解表示-八叉树表示n八叉树表示n对空间位置枚举表示的空间分割方法作了改进：均匀分割 自适应分割n八叉树建立过程八叉树的根节点对应整个物体空间八叉树的根节点对应整个物体空间如果它完全被物体占据，将该节点标记为如果它完全被物体占据，将该节点标记为F(Full)，算法结束；算法结束；如果它内部没有物体，将该节点标记为如果它内部没有物体，将该节点标记为E(Empty)，算法结束；算法结束；如果它被物体部分占据，将该节点标记为如果

3、它被物体部分占据，将该节点标记为P(Partial)，并将它分割成并将它分割成8个子立方体，对每一个子立方体进行个子立方体，对每一个子立方体进行同样的处理同样的处理分解表示-八叉树表示n8叉树的表示应用三维形体的分解，它对一个外接立方体的形体进行前后、左右、上下等部分8个小立方体，如果小立方体单元为满或为空，表示该立方体完全在形体中或完全不在形体中，则其停止分解；对部分形体占有的小立方体需进一步分解为8个子立方体，直至所有小立方体单元要么全部满，要么全部空，或已分解到规定的分解精度为止。236720131375具有子孙的节点具有子孙的节点(P)(P)空节点空节点(E)(E)实节点实节点(F)(

4、F)分解表示-八叉树表示n优点n可以表示任何物体，且形体表示的数据结构简单n简化了形体的集合运算。只需同时遍历参加集合运算的两形体相应的八叉树，无需进行复杂的求交运算。n简化了隐藏线（或面）的消除，因为在八叉树表示中，形体上各元素已按空间位置排成了一定的顺序。n分析算法适合于并行处理。n缺点n没有边界信息，不适于图形显示n对物体进行几何变换困难n是物体的非精确表示n占用大量存储。实际上，八叉树表示是以存储空间换取算法的效率分解表示-线性八叉树表示线性八叉树：用一可变长度的一维数组来存储一棵八叉树。数组中仅存储八叉树的性质为FULL的终端结点。并用一个八进制数表示该结点在八叉树中的位置。编码方式

5、为：Q1Q2Qm,其中Q1表示该结点所属的一级父结点的编号（0-7），以此类推。例右图为：1X,30X,31X,323X,33X236720131375具有子孙的节点具有子孙的节点(P)(P)空节点空节点(E)(E)实节点实节点(F)(F)分解表示-单元分解表示n单元分解表示n对空间位置枚举表示的空间分割方法作了改进：单一体素 多种体素n三种空间分割方法的比较n空间位置枚举表示-同样大小立方体粘合在一起表示物体n八叉树表示-不同大小的立方体粘合在一起表示物体n单元分解表示-多种体素粘合在一起表示物体分解表示-单元分解表示n优点n表示简单n容易实现几何变换n基本体素可以按需选择，表示范围较广n可

6、以精确表示物体n缺点n物体的表示不唯一n物体的有效性难以保证构造表示n推移表示n构造实体几何表示（CSG）n特征表示构造表示-推移表示n将物体A沿着轨迹P推移得到物体B，称B为sweep体n平移sweep-将一个二维区域沿着一个矢量方向推移构造表示-推移表示n旋转sweep-将一个二维区域绕旋转轴旋转一周n 三维形体也能在空间通过扫描变换生成新的形体：如左图，一个圆柱体按指定方向在长方体上运动生成新的形体，这个过程犹如长方体与运动者的圆柱体不断的作差运算操作。有时经过扫描变换所生成的形体可能会出现维数不一致问题。构造表示-推移表示扫描线方向扫描线方向U U构造表示-推移表示n广义sweepn任

7、意物体沿着任意轨迹推移n推移过程中物体可以变形构造表示-推移表示n优点n表示简单、直观n适合做图形输入手段n缺点n作几何变换困难n对几何运算不封闭n用扫描变换产生的形体可能出现维数不一致的问题。n扫描方法不能直接获取形体的边界信息，表示形体的覆盖域非常有限。构造表示-构造实体几何表示(CSG).通过对体素定义运算而得到新的形体的一种表示方法。体素可以是立方体、圆柱、圆锥等，也可以是半空间，其运算为变换或正则集合运算并、交、差。CSG表示可以看成是一棵有序的二叉树。n其终端节点或是体素、或是形体变换参数。n非终端结点或是正则的集合运算，或是变换（平移和/或旋转）操作，这种运算或变换只对其紧接着的

8、子结点（子形体）起作用。构造表示-构造实体几何表示(CSG)构造表示-构造实体几何表示(CSG)nCSG树是无二义性的，但不是唯一的.CSG表示的优点：n数据结构比较简单，数据量比较小，内部数据的管理比较容易；n物体的有效性自动得到保证；nCSG方法表示的形体的形状，比较容易修改。构造表示-构造实体几何表示(CSG)CSG表示的缺点：n对形体的表示受体素的种类和对体素操作的种类的限制，也就是说，CSG方法表示形体的覆盖域有较大的局限性。n对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角；n由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长

9、的时间。n表示不唯一 构造表示-特征表示n用一组特征参数表示一组类似的物体n特征包括形状特征、材料特征等n适用于工业上标准件的表示构造表示的特点n构造表示的特点：n构造表示通常具有不便于直接获取形体几何元素的信息、覆盖域有限等缺点，n但是，便于用户输入形体，在CAD/CAM系统中，通常作为辅助表示方法。边界表示n边界表示（BR表示或BRep表示）n按照体面环边点的层次，详细记录了构成形体的所有几何元素的几何信息及其相互连接的拓扑关系。n边界表示的一个重要特点是在该表示法中，描述形体的信息包括几何信息（Geometry）和拓扑信息（Topology）两个方面。n拓扑信息描述形体上的顶点、边、面的

10、连接关系，拓扑信息形成物体边界表示的“骨架”。n形体的几何信息犹如附着在“骨架”上的肌肉。边界表示n边界模型表达形体的基本拓扑实体包括：n1. 顶点n2. 边。边有方向，它由起始顶点和终止顶点来界定。边的形状（Curve）由边的几何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描述，也可用显式、隐式或参数方程来描述。边界表示n3. 环。环（Loop）是有序、有向边（Edge）组成的封闭边界。环有方向、内外之分，外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。n4.面。面（Face）由一个外环和若干个内环（可以没有内环）来表示，内环完全在外环之内。n若一个面的外法矢向外，

11、称为正向面；反之，称为反向面。边界表示n面的形状可以是平面或曲面。平面可用平面方程来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程（隐式、显式或参数形式）来描述。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进行。n5.体。体（Body）是面的并集。边界表示n边界表示模型是一种采用描述形体表面的方法来描述的几何表示模型。一个形体一般可以通过其边界拆成一些有界的“面”或“小片”的子集来表示，而每一个面又可以通过其边界的边和顶点来表示。若面的表示无二义性，则其边界表示模型也无二义性，但通常不一定只有唯一的表示。U图3.2

12、.10 边界表示边界表示的数据结构n边界表示法的数据结构有四种方法：以面为基础、以顶点为基础、以边为基础和翼边结构；n以面为基础的数据结构以面为基础的数据结构n以面为基础，按照体、面、顶点坐标的树结构层次组织元素数据；如n面 顶点坐标nF1 (X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4)nF2 (X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5) n.n其中顶点按照外观顺时针顺序；边界表示的数据结构n2 2以顶点为基础的数据结构以顶点为基础的数据结构n以顶点/坐标和面/顶点序列两张关系表表示，如：n顶点 坐标 面 顶点序列nV1 X1Y1Z1 F1 V1V2V3V4n.n3.

13、3.以边为基础的数据结构以边为基础的数据结构n以边/顶点，顶点/坐标，面/边三张关系表表示；边界表示模型n四棱椎边界表示的例子如右，由4个面组成，且这种表示可以看作是含有体、面、边、顶点为节点的有向图n四棱椎边界表示也可以基于边界的三角形分解，即把形体的边界拆成一些互不重叠的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱四棱柱面节点面节点边节点边节点顶点坐标顶点坐标f1f2f3.e1e2e3e4.v1v2v3.(x1,y1,z1)组合组合结构结构坐标坐标信息信息.6.3 实体构造技术实体构造技术n由简单的物体来构成复杂的物体由简单的物体来构成复杂的物体n扫描表示扫描表示

14、n结构实体几何法结构实体几何法扫描表示扫描表示n思想：思想： 通过平移、旋转及其他对称变换来构通过平移、旋转及其他对称变换来构造三维对象造三维对象 通过指定一个二维形状以及在空间区通过指定一个二维形状以及在空间区域内移动该形状的扫描来描述该三维域内移动该形状的扫描来描述该三维物体物体zoyxAn平移扫描 二维图形A沿Z轴平移n旋转扫描 二维图形A绕Z轴旋转zByxA结构实体几何法结构实体几何法n思想思想 通过对两个指定三维通过对两个指定三维对象进行并、交或差对象进行并、交或差等集合操作产生一个等集合操作产生一个新的三维对象新的三维对象 结构实体几何法结构实体几何法物体物体A和和B差差并并交交差

15、差8.5 八叉树八叉树n分层树形结构，称为八叉树。分层树形结构，称为八叉树。n思想思想 利用实体的空间相关性利用实体的空间相关性n优点优点n减少了三维物体的存储需求减少了三维物体的存储需求n提供了存储有关物体内部信息的方便表示提供了存储有关物体内部信息的方便表示四叉树四叉树二维平面二维平面三维空间三维空间八叉树八叉树四叉树四叉树n四叉树四叉树n数据结构数据结构n思想思想 n同质象限同质象限10231023n用于用于二维平面二维平面的分解的分解n对二维区域对二维区域递归地等分递归地等分4个小正方形，这个分解过个小正方形，这个分解过程可表示为一棵树，除叶节点，其每个节点都有四程可表示为一棵树，除叶

16、节点，其每个节点都有四个分支，分别表示个分支，分别表示4个小正方形个小正方形n若小正方形是同质的，则不必再分解；若小正方形是同质的，则不必再分解；n若小正方形是非同质的，则需将它再一分为四若小正方形是非同质的，则需将它再一分为四n分解是递归的。分解是递归的。四叉树四叉树四叉树四叉树n例3120312001230132四叉树四叉树312456132519241820212223711 12891014151617具有子孙的节点具有子孙的节点空节点空节点实节点实节点245139 107811 12314 15 20 21 16 17 22 23 18 19 24 2516n三维形体的分解三维形体的

17、分解n对三维空间进行前后、左右、上下等分为对三维空间进行前后、左右、上下等分为8个小个小立方体，立方体，n小立方体单元均质，则停止分解；小立方体单元均质，则停止分解；n小立方体单元非均质，需进一步分解为小立方体单元非均质，需进一步分解为8个子立个子立方体方体n直至所有小立方体单元均质，或已分解到规定直至所有小立方体单元均质，或已分解到规定的分解精度为止。的分解精度为止。八叉树八叉树八叉树八叉树236720131375具有子孙的节点具有子孙的节点空节点空节点实节点实节点8.6 分形分形Fractaln欧氏几何法欧氏几何法&分形几何法分形几何法n分形基本特征分形基本特征n分形生成过程分形生

18、成过程n分形分类分形分类n分形维数概念分形维数概念nEuclidean - Geometry Methods - use equations to describe objects which have smooth surfaces and regular shapes.nFractal - Geometry Methods - use procedures to model natural objects which have irregular or fragmented features.欧氏几何法欧氏几何法&分形几何法分形几何法ninfinite detail at ever

19、y point每点具有无限细节每点具有无限细节nself-similarity between the object parts and the overall features对象整体和局部之间对象整体和局部之间的自相似性的自相似性n利用一个过程来描述分形物体，利用一个过程来描述分形物体，该过程为产生物体局部细节指该过程为产生物体局部细节指定了重复操作定了重复操作distantCloserCloser yet分形基本特征分形基本特征nIdea 分形图形的生成过程是重复使用指定的变换函数作分形图形的生成过程是重复使用指定的变换函数作用于空间区域中的点的过程用于空间区域中的点的过程 Initia

20、l point P0, transformation function FP1 = F(P0), P2 = F(P1), P3 = F(P2) nExamples (P399)分形生成过程分形生成过程Von koch snowflake树形生成元及对应曲线树形生成元及对应曲线树形生成元及对应曲线树形生成元及对应曲线分形分类分形分类n类型类型n自相似自相似分形：组成部分是整个物体的收缩形式分形：组成部分是整个物体的收缩形式n自仿射自仿射分形：组成部分为不同坐标方向上的不分形：组成部分为不同坐标方向上的不同缩放因子形成。同缩放因子形成。n不变分形不变分形集：由非线性变换形成。集：由非线性变换形成。

21、n自平方分形自平方分形n自逆分形：由自逆过程形成。自逆分形：由自逆过程形成。nSelf-similar Fractal自相似分形自相似分形 自相似分形的组成部分是整个物体的收缩形式。从自相似分形的组成部分是整个物体的收缩形式。从初始形状开始，对整个物体应用缩放参数初始形状开始，对整个物体应用缩放参数s来构造来构造物体的子部件。物体的子部件。nTypesnDeterministic self-similar 确定自相似分形确定自相似分形nStatistically self-similar 统计自相似分形统计自相似分形n用于模拟树木、灌木和其他植物用于模拟树木、灌木和其他植物(彩页彩页12)分形分类分形分类nSelf-affine Fractal 自仿射分形自仿射分形 自仿射分形的组成部分由不同坐标方向上的不同缩自仿射分形的组成部分由不同坐标方向上的不同缩放参数放参数sx、sy、sz形成形成nTypesnDeterministic self-affine fractals确定自仿确定自仿射分形射分形nStatistically self-affine fractals统计自仿射统计自仿射分形分形n用于模拟岩层、水和云等自然