第九章 基本造型方法

第九章基本造型方法9.1概述9.2结构实体几何模型（CSG）9.3分解模型9.4边界模型9.5非传统造型技术9.1概述设计对象所含的信息可以分为两个部分：非视觉信息和视觉信息。图9.1对象的信息

计算机内对形状信息的描述方法简称为造型（Modeling）的技术。造形技术主要由形状表达和形状操作两个部分组成。1形状表达的任务是将形状的结构用数据结构模拟出来。这种描述形状的数据结构称为模型（Model）。2形状操作的任务是实现对模型的生成、修改、综合、分析、计算、显示等等操作，以便完成设计过程中的各种造型任务。

1．实体造型技术（SolidModeling）

2．曲面造型技术（SurfaceModeling）

3．非几何形体的造型技术

造型技术是CAD的核心技术之一。目前常用的造型技术有：

结构模型又称结构实体几何（ConstructiveSolidGeometry）模型，简称CSG。CSG含有一组简单的几何实体类型，如立方体、球、圆柱、圆锥等。它们称为基元实体类型（PrimitiveSolidType）。CSG还含有一组施加于基元实体类型上的操作，这些操作包括：几何变换、集合运算以及剖割、局部修改等其他造型操作。这是用二叉树的形式记录一个零件的所有组成体素拼合运算的过程，可以简称为体素拼合树。

9.2结构实体几何模型(CSG)

Wrench+/\cube3+/\+cube2/\cylinder1cube1图9.2体素拼合实例

表9.1CSG节点数据结构OP_Code操作码transformprimitive坐标变换基本体素left_Subtreeright_Subtree左子树右子树OP_Code01234

基本体素

求并

求差

求交

装配

CSG的发展历史体素拼合操作

要求：参与运算的体素必须是正规集。运算必须封闭，即运算产生的结果依然是正规集。正规化处理

图9.3AB产生的非正规点集

对参与运算的元素进行分类

图9.4曲线段X相对于二维域S的分类

图9.5按照正规分类原则，XonS=NULL体素拼合操作 设S是体素A和B的正规运算结果，则拼合算法等价于从已知的(XinA,XonA,XoutA)和(XinB,XonB,XoutB)求(XinS,XonS,XoutS)，或可以写做：SMC(X,A<op>B)=combine(SMC(X,A),SMC(X,B),<op>)表9.2点对于拼合体A∩B的分类

当集合运算的结果有二义性时，利用邻域进行测试

图9.6利用邻域判断点的分类性质

对于A与B的交集SN(P,S)=N(P,A)∩N(P,B)三、八叉树的变换操作对一棵八叉树的平移、旋转、比例等等变换可以通过对该树的point数组中所含的坐标的变换而完成，树中其余结点的位置可以通过这些参数而推算出来。

四、计算分析操作五、图形显示计算分析操作包括实体的体积、重心、面积等性质的计算。由于八叉树表达的严格有序性，这些操作的实现得到方便。树上的算法往往是通过递归完成的。

图形显示包括剪载、消隐、真实感显示等操作。其中有些算法，如消隐等，可利用八叉树的空间有序性，以从远到近地遍历树的方法实现。而另一些算法，如线框图的轮廓线的提取，则比较麻烦。

CSG应用分治(divide-and-conquer)算法

图9.7适用分治算法的CSG树节点组织

procedureClassLine3D(L,S)ifSisaprimitivethenClassLine3DWrtPrim(L,S)elseCombineLine3D(ClassLine3D(L,Left_S),ClassLine3D(L,Right_S),Op_S)9.3分解模型

八叉树表达2.八叉树的操作3.线性八叉树

9.3.1八叉树表达八叉树概念图9.8正方体及其八个子正方体

(a)一个实体

(b)所对应的八叉树表示

图9.9实体及其八叉树表示

八叉树的数据结构

typedefstructoctreetype{classtype/*Black,White,Grey*/class；intdepth；/*深度控制值*/structoctreetype*octree[8]；}octreetype；struct{pointtypepoint[8]；/*存放正方形八个顶点之座标*/octreetype*rootptr；}roothead；octreetype*octreeptr；octreetypeoctree；

9.3.2八叉树的操作八叉树的操作主要有八叉树的生成，集合运算，变换操作，分析计算和图形显示。

一、八叉树的生成程序make-tree调用两个子程序classify和setson,两个子程序的功能如下：1.classtypeclassify(primitive,tree)；该子程序比较实体基元primitive和以tree为根的八叉树的相交关系，返回black,white和grey等三个值之一。2.setson(tree)；该子程序使得tree结点产生8个儿子。make-tree(primitive,tree,depth)primitivetype*primitive；octreetype*tree；intdepth；

classtypeb；inti；b=classify(primitive,tree)；switch(b){casewhite：tree->class=white；break；caseblack：tree->class=black；break；default：if(depth==0)tree->class=black；else{tree->class=grey；setson(tree)；for(i=0；i<8；i++)make-tree(primitive,tree->octree[i],depth-1)；}/*defaultend.*/}/*switchend.*/}程序9.1实体转换为八叉树算法

二、八叉树的集合运算

八叉树的集合运算，是指对两棵八叉树进行并、交、差的运算而产生一棵新的八叉树。

考虑两棵八叉树求交的操作，算法思想如下：设n1、n2是求交的两棵八叉树中相同位置的对应结点，n3是求交后新树中的对应结点。则求交规则为：1．如果n1,n2同为叶结点，则有：2.如果n1是叶结点，n2不是，则有：3.如果n1,n2同为非叶结点，则n1,n2,n3同时分解至儿子层再进行求交。

9.3.3线性八叉树八叉树的缺陷两种改进方法： 1.黑叶结点法

2.括号叶结点法

一、黑叶结点法黑叶结点法只列出树中黑色结点。方法是将八叉树中所有结点按层次和次序编号。编号的数字位长代表深度、数字大小代表次序，如图9.10所示。

图9.10八叉树结点的编号

二、括号叶结点法

括号叶结点法用括号表示层次，按从左到右的次序列出所有的叶结点，并按照黑、白分类。例如，对图9.9所示的八叉树，可以表示为下列线性表：（（WWWBWWWW）BWWW（WBWBWWWW）WW）这张表虽然长了一些，但每个元素只有3种变化，即只占2bit的存储空间，因此也大压缩了存储空间。

9.4边界模型边界表示法(B-rep)也称为边界模型(BoundaryModel)。3种物体类型——小面(一个小面可以有几条边界曲线，只要它们定义一个连通的物体)、边和顶点，以及和它们有联系的几何信息共同构成了边界表示的基本元素。除了小面、边和顶点坐标等几何信息外，边界表示还必须表示这些小面、边和顶点的相互联系。通常将实体的所有几何信息称做“几何”，而将它们内部的连接信息称做“拓扑”。

图9.11边界表示的对象实例

翼边结构

图9.12图9.11的翼边结构的一个例子

图9.13完整的翼边结构

9.5非传统造型技术分形造型2.粒子系统9.5.1分形造型欧氏几何的主要描述工具是直线、平滑的曲线、平面及边界整齐的平滑曲面，这些工具在描述一些抽象图形或人造物体的形态时是非常有力的，但对于一些复杂的自然景象形态就显得无能为力了，诸如山、树、草、火、云、波浪等。这是由于从欧氏几何来看，它们是极端无规则的。为了解决复杂图形生成问题，分形(Fractal)造型应运而生。

基本概念

HelgeVonKoch

的雪花图形

Mandelbrot的一个海岸线例子

分数维

D=(logN)/log(1/S)分形造型对模型的基本要求⒈能逼真地“再现”自然景象。所谓逼真是指从视觉效果上逼真，“再现”即不要求完全一致。⒉模型不依赖于观察距离。即距离远时可给出大致轮廓和一般细节，距离近时能给出更丰富细节。⒊模型说明应尽量简单，模型应具有数据放大能力。⒋模型应便于交互地修改。⒌图形生成的效率要高。