第6章 形体的表示及其数据结构

1、第六章第六章 形体的表示及其数据结构形体的表示及其数据结构 与空间任意形体有关的信息可以分为与空间任意形体有关的信息可以分为图形信息图形信息和和非图形信息非图形信息两类。图形信息指两类。图形信息指构成它们的点、线、面的位置构成它们的点、线、面的位置, ,相互关系及相互关系及大小等大小等; ;非图形信息指形体的颜色、亮度、非图形信息指形体的颜色、亮度、质量、体积等一些性质。质量、体积等一些性质。 形体的图形信息又可以分为形体的图形信息又可以分为几何信息几何信息和和拓扑信息拓扑信息两类。几何信息指形体在空间两类。几何信息指形体在空间的位置和大小的位置和大小, ,拓扑信息指组成形体各部分拓扑信息指组

2、成形体各部分的数目及相互间的连接关系。的数目及相互间的连接关系。 第一节第一节 二维形体的表示二维形体的表示 二维图形的边界表示二维图形的边界表示 折线法和带树法折线法和带树法 折线法就是用多段线段形成的折线去折线法就是用多段线段形成的折线去逼近曲线逼近曲线 折线表示曲线应该解决的关键问题是折线表示曲线应该解决的关键问题是: :如何恰当地确定曲线上一系列点如何恰当地确定曲线上一系列点, ,使之在使之在某些判定准则下达到最优。某些判定准则下达到最优。 带树法带树法 带树是一棵二叉树带树是一棵二叉树, ,树的每个结点对树的每个结点对应一个矩形带段应一个矩形带段, ,这样每个结点可由八个这样每个结点

3、可由八个字段组成字段组成, ,前六个字段描述矩形带段前六个字段描述矩形带段, ,后二后二个是指向两个子结点的指针个是指向两个子结点的指针, , 即矩形带段即矩形带段的起点是的起点是(x(xb b,y,yb b),),终点是终点是(x(xe e,y,ye e) )。相对从。相对从起点到终点的连线起点到终点的连线, ,矩形有两边与之平行矩形有两边与之平行, ,两边与之垂直两边与之垂直, ,平行两边与之距离分别为平行两边与之距离分别为w wl l和和w wr r。 设要表示的曲线是由经过适当选取已确设要表示的曲线是由经过适当选取已确定的一组离散点定的一组离散点P P0 0,P,P1 1, ,P,Pn

4、 n序列给出序列给出, ,则生则生成表示曲线的分辨率为成表示曲线的分辨率为w w0 0的带树的算法的带树的算法, ,可简可简略描述如下略描述如下: :1. 1. 找出由起点找出由起点P P0 0, ,终点终点P Pn n确定的矩形带段确定的矩形带段, ,其其中包含中包含P P0 0至至P Pn n的全部点的全部点, ,构造此矩形带段的对构造此矩形带段的对应结点并令为根。应结点并令为根。2. 2. 找出找出P P0 0至至P Pn n之间距离连线之间距离连线P P0 0P Pn n为最远的点为最远的点P Pk k, ,然后对然后对P P0 0至至P Pk k和和P Pk k至至P Pn n这两组

5、点分别做与步这两组点分别做与步1 1中相同的构造矩形带段及对应结点的操作中相同的构造矩形带段及对应结点的操作, ,产生的两个结点产生的两个结点, ,分别是根的左右子结点。分别是根的左右子结点。3. 3. 反复执行上述操作反复执行上述操作, ,直到所产生结点的直到所产生结点的w=ww=wl l+ +w wr r w w0 0。这样的结点是叶结点。这样的结点是叶结点。 设表示曲线有设表示曲线有5 5个点个点(3,7)(9,12),(15,4),(18,5),(20,7) ,(3,7)(9,12),(15,4),(18,5),(20,7) ,取分辨取分辨率率w w0 0=1,=1,则上述算法构造的带

6、树则上述算法构造的带树 以不同的分辨率显示用带树表示的曲线以不同的分辨率显示用带树表示的曲线 设给出允许的分辨率为设给出允许的分辨率为w*, ,表示曲线的表示曲线的带树的分辨率为带树的分辨率为w w0 0, ,并设并设w w0 0w*,则显示算法可则显示算法可简略描述如下简略描述如下: : 从根结点开始从根结点开始, ,若当前正考查结点的若当前正考查结点的W=wW=wl l+w+wr r w*,则显示该结点对应的矩形带段则显示该结点对应的矩形带段; ;若不然若不然, ,即即W W w*则转去分别考查该结点的左则转去分别考查该结点的左右两个子结点右两个子结点, ,对子结点做同样的处理。左对子结点

7、做同样的处理。左右子结点都被显示的结点就认为是被显示了右子结点都被显示的结点就认为是被显示了, ,按此看法按此看法, ,显示带树表示的曲线就是显示带显示带树表示的曲线就是显示带树的结点。树的结点。 带树表示的曲线求交带树表示的曲线求交 两个矩形带段两个矩形带段S S1 1和和S S2 2的位置关系有如下的位置关系有如下三种三种: :(1) (1) 不相交。不相交。(2) (2) 良性相交良性相交, ,即即S S1 1的与起点至终点连线平行的与起点至终点连线平行的两条边都与的两条边都与S S2 2相交相交,S,S2 2的与起点至终点连的与起点至终点连线平行的两条边也都与线平行的两条边也都与S S

8、1 1相交。相交。(3) (3) 可能性相交可能性相交, ,这时不是良性相交这时不是良性相交, ,但也不但也不是不相交。是不相交。 设表示要求交两曲线的带树己构造得足够设表示要求交两曲线的带树己构造得足够精确精确, ,即在树叶一层即在树叶一层, ,来自不同带树的矩形带来自不同带树的矩形带段或是不相交或是良性相交段或是不相交或是良性相交, ,而没有可能性相而没有可能性相交出现。交出现。 两树两树T1T1和和T2T2表示的两条曲线是否相交的算表示的两条曲线是否相交的算法法, ,可以简略叙述如下可以简略叙述如下: : 若若T T1 1和和T T2 2对应的矩形带段互不相交对应的矩形带段互不相交, ,

9、那么那么它们代表的曲线不相交它们代表的曲线不相交; ; 若若T T1 1和和T T2 2对应的矩形带段良性相交对应的矩形带段良性相交, ,那么那么它们代表的曲线相交它们代表的曲线相交; ; 若若T T1 1和和T T2 2对应的矩形带段可能性相交对应的矩形带段可能性相交, ,且且T T1 1的面积大于或等的面积大于或等T T2 2的面积的面积, ,那么分别执行那么分别执行T T2 2与与T T1 1的左右两个儿子结点的相交性检查。的左右两个儿子结点的相交性检查。 若若T T1 1的面积小于的面积小于T T2 2的面积的面积, ,则把它们位则把它们位置对换一下再如上进行两个检查。若两个置对换一下

10、再如上进行两个检查。若两个检查的结果都是不相交检查的结果都是不相交, ,则认为所表示曲则认为所表示曲线不相交线不相交; ;若两个检查中有一个是良性相若两个检查中有一个是良性相交交, ,则认为所表示曲线相交则认为所表示曲线相交; ;若不是上述两若不是上述两情形情形, ,即出现可能性相交即出现可能性相交, ,则对可能性相交则对可能性相交的两个矩形带段中面积较大者的两个矩形带段中面积较大者, ,取其对应取其对应结点的两个子结点结点的两个子结点, ,如此进行可直到树叶如此进行可直到树叶那一层。那一层。 实践表明用带树方法表示曲线对提高实践表明用带树方法表示曲线对提高计算效率是有帮助的。另外两个带树对计

11、算效率是有帮助的。另外两个带树对并、并、交等运算是封闭的交等运算是封闭的, ,与用象素阵列来表示与用象素阵列来表示图形的方法比较空间需求也算是节省的。图形的方法比较空间需求也算是节省的。 平面图形的四叉树表示方法平面图形的四叉树表示方法 假定一个平面图形是假定一个平面图形是黑白黑白的二值图形的二值图形, ,即组成图形象素阵列的仅有黑色象素值即组成图形象素阵列的仅有黑色象素值1,1,白白色象素值色象素值0,0,设表现图形的象素阵列由设表现图形的象素阵列由2 2n n2 2n n个象素组成。个象素组成。 表示该图形的四叉树结构可以如下形成表示该图形的四叉树结构可以如下形成: :图形显然包括图形显然

12、包括2 2n n2 2n n的正方形中，这个正方的正方形中，这个正方形是四叉树的根结点。形是四叉树的根结点。 若图形整个地占据这个正方形若图形整个地占据这个正方形, ,则图形则图形就用该正方形表示就用该正方形表示, ,否则将该正方形均分为否则将该正方形均分为四个小正方形，每个小正方形边长为原正方四个小正方形，每个小正方形边长为原正方形边长的一半形边长的一半. .它们是根结点的四个子结点它们是根结点的四个子结点, ,可编号为可编号为0,1,2,30,1,2,3。 再考查每个小正方形再考查每个小正方形, ,若整个被图若整个被图形占据形占据, ,则标记相应结点为则标记相应结点为1,1,可称为可称为黑

13、黑结点结点。若整个与图形不相交。若整个与图形不相交, ,则标记相则标记相应结点为应结点为0 0，可称为，可称为白结点白结点。 若不是上述两情形，即与图形部分若不是上述两情形，即与图形部分相交，则称相应结点是相交，则称相应结点是灰结点灰结点并将其一并将其一分为四。当再分生成小正方形边长达到分为四。当再分生成小正方形边长达到一个一个象素单位象素单位时，再分终止，此时一般时，再分终止，此时一般应将仍是灰结点的改为黑结点，如此形应将仍是灰结点的改为黑结点，如此形成了平面图形的四叉树表示成了平面图形的四叉树表示 四叉树的存储结构，即四叉树的存储结构，即规则方式、线规则方式、线性方式和一对四方式性方式和一

14、对四方式，相应的四叉树也就，相应的四叉树也就称为规则四叉树、线性四叉树和一对四式称为规则四叉树、线性四叉树和一对四式四叉树。四叉树。 规则四叉树是用五个字段的记录来表规则四叉树是用五个字段的记录来表示树中的每个结点，其中一个用来描述结示树中的每个结点，其中一个用来描述结点的特性，即是灰、黑、白三类结点中的点的特性，即是灰、黑、白三类结点中的哪一种。其余四个用于存放指向四个子结哪一种。其余四个用于存放指向四个子结点的指针。点的指针。 线性四叉树以某一预先确定的次序遍线性四叉树以某一预先确定的次序遍历四叉树形成一个线性表结构历四叉树形成一个线性表结构 。 RAabcdBCDefghRAabcdBC

15、Defgh。其中。其中R R表示根，字表示根，字母右上角加母右上角加表示是灰结点。表示是灰结点。 一对四式四叉树的存储结构一对四式四叉树的存储结构 每个结每个结点有五个字段，其中四个字段用来描述该点有五个字段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点存结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的指针。放指向子结点记录存放处的指针。四个子四个子结点对应的记录是依次连续存放的。结点对应的记录是依次连续存放的。 为节省存贮空间为节省存贮空间, ,有两个途径可以采取。有两个途径可以采取。一个是增加计算量；另一个途径是在记录中一个是增加计算量；另一个途径是在记录中再增加一

16、个字节再增加一个字节, ,一分为四一分为四, ,每个子结点对应每个子结点对应2 2位位, ,表示它的子结点在指针指向区域中的偏移。表示它的子结点在指针指向区域中的偏移。 第二节第二节 三维几何模型三维几何模型 几何元素几何元素 形体的模型主要指的就是包含图形信形体的模型主要指的就是包含图形信息所形成的模型。息所形成的模型。 形体本身的构造有一定的层次性，低形体本身的构造有一定的层次性，低层部分组合构成上一层部分，而上一层部层部分组合构成上一层部分，而上一层部分组合又可以构成更高一层的部分，依此分组合又可以构成更高一层的部分，依此类推可形成多层结构。其中，每一层中的类推可形成多层结构。其中，每一

17、层中的部分，我们把它有称为几何元素。部分，我们把它有称为几何元素。 点点 它是它是0 0维几何元素，有端点、交点、切维几何元素，有端点、交点、切点、孤立点等形式。点、孤立点等形式。 曲线、曲面的应用中会涉及到三种类型曲线、曲面的应用中会涉及到三种类型的点：的点：型值点型值点 相应曲线、曲面必然经过的点。相应曲线、曲面必然经过的点。控制点控制点 相应曲线、曲面不一定经过的点，仅相应曲线、曲面不一定经过的点，仅用于确定位置和形状。用于确定位置和形状。插值点插值点 在型值点之间插入的一系列点，用于在型值点之间插入的一系列点，用于提高曲线曲面的输出精度。提高曲线曲面的输出精度。 不同的空间中点的表示方

18、式不同的空间中点的表示方式 一维空间中用一元组一维空间中用一元组tt表示；表示； 二维空间中用二元组二维空间中用二元组x,yx,y或或x(t),y(t)x(t),y(t)表示；表示； 三维空间中用三元组三维空间中用三元组x,y,zx,y,z或或x(t),y(t),z(t)x(t),y(t),z(t)表示；表示； 点是几何造型中的最基本的元素，曲线、点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述。曲面和其它形体都可以用有序的点集描述。 用计算机存储、管理、输出形体的实质用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。就是对点集及其连接关系的处理。 边边

19、边是一维几何元素，是两个邻面（正则形边是一维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界。边体）或多个邻面（非正则形体）的交界。边分分直线边直线边和和曲线边曲线边。直线边由起点和终点两。直线边由起点和终点两端点确定；曲线边由一系列型值点或控制点端点确定；曲线边由一系列型值点或控制点表示，也可以用显示、隐式方程描述。表示，也可以用显示、隐式方程描述。环环 环是有序有向边（直线段或曲线段）组环是有序有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点。环有内外之分，确邻两条边共享一个端点。环有内外之分，确定面的

20、最大外边界的环称之为定面的最大外边界的环称之为外环外环，通常其，通常其边按边按逆时针方向逆时针方向排序。而把确定面中内孔或排序。而把确定面中内孔或凸台边界的环称之为凸台边界的环称之为内环内环，其边相应外环排，其边相应外环排序方向相反，通常按序方向相反，通常按顺时针顺时针方向排序。方向排序。面面 面是二维元素，是形体上一个有限、非零面是二维元素，是形体上一个有限、非零的区域，它由的区域，它由一个外环和若干个内环所界定一个外环和若干个内环所界定。面有方向性，一般用其外法向量作为该面的面有方向性，一般用其外法向量作为该面的正向。若一个面的外法向量向外，此面为正；正向。若一个面的外法向量向外，此面为正

21、；否则，为反向面。否则，为反向面。体体 体是三维几何元素，由封闭表面围成的体是三维几何元素，由封闭表面围成的空间，它是欧氏空间空间，它是欧氏空间R R3 3中非空、有界的封闭子中非空、有界的封闭子集，其边界是有限面的并集。在实际应用中，集，其边界是有限面的并集。在实际应用中，要求形体是正则形体，即形体上任意一点的要求形体是正则形体，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭足够小的邻域在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。圆。不满足上述要求的形体称为非正则形体。存在悬面、悬边的形体是非正则形体。存在悬面、悬边的形体是非正则形体。 体素体素 体素是可以用

22、有限个尺寸参数定位和定型体素是可以用有限个尺寸参数定位和定型的体，常有下面三种定义形式。的体，常有下面三种定义形式。一组单元实体一组单元实体 长方体、圆柱体、圆锥体、球体。长方体、圆柱体、圆锥体、球体。扫描体扫描体 由参数定义的一条（一组）截面轮廓由参数定义的一条（一组）截面轮廓线沿一条（一组）空间参数曲线作扫描运动线沿一条（一组）空间参数曲线作扫描运动而产生的形体。而产生的形体。用代数半空间定义的形体用代数半空间定义的形体，在此半空间中点集，在此半空间中点集可定义可定义(x,y,z)|f(x,y,z) 0(x,y,z)|f(x,y,z) 0此处的此处的f f应是应是不可约的多项式。不可约的多

23、项式。形体的层次结构形体的层次结构 点点边边环环面面外壳外壳形体。形体。 在几何造型中最基本的几何元素是在几何造型中最基本的几何元素是点（点（V V）、边）、边(E)(E)、面、面(F),(F),这三种元素一这三种元素一共有九种连接关系共有九种连接关系 线框、表面及实体表示线框、表面及实体表示 常用的多面体表示法是三表表示法，即采常用的多面体表示法是三表表示法，即采用三个表用三个表: :顶点表顶点表, ,用来存放多面体各顶点的用来存放多面体各顶点的坐标坐标; ;边表边表, ,指出哪两个顶点之间有多面体的指出哪两个顶点之间有多面体的边；边；面表面表，指出哪些边围成了多面体的表面。，指出哪些边围成

24、了多面体的表面。 任意多面体容易得到它的三表表示任意多面体容易得到它的三表表示, ,但任但任意三张表却不一定表示了一个真实的多面体。意三张表却不一定表示了一个真实的多面体。这里必须满足的条件至少有以下几项这里必须满足的条件至少有以下几项: :顶点表顶点表中的每个顶点至少是中的每个顶点至少是三边三边的端点的端点; ;边表中的每边表中的每条边是条边是两个多边形两个多边形面的公共边；每个多边形面的公共边；每个多边形面是封闭的等等。面是封闭的等等。 x xy yz z1 10 00 01 11 10 00 01 10 00 00 00 01 10 01 11 11 11 10 01 11 10 00

25、01 11 12 22 23 33 34 44 41 15 56 66 67 77 78 88 85 51 15 52 26 63 37 74 48 81 110105 59 92 211116 610103 312127 711114 49 98 812125 56 67 78 83 32 21 14 4顶点表顶点表面表面表边表边表 空间正二空间正二十面体十面体V V2020, , 的三表表示。的三表表示。 引人一个引人一个正数正数0,0,它它满足二次方满足二次方程程2 2-1=0,1=0,因此因此=1/2(1+ )=1/2(1+ )1.6180341.618034。 5 5XYZ编号编号x

26、yz编号编号xyz110123-101213-001-12431-10-1 014-0-13201-2110330-1221-0340-1-边编边编号号 边编边编号号 1 11 11 1 ，131316162121，32322 21 21 2 ，141417172222，33333 32 12 1 ，232318182222，34344 42 22 2 ，242419192323，31315 53 13 1 ，333320202323，32326 63 23 2 ，343421212424，33337 71 11 1 ，212122222424，34348 81 11 1 ，222223233

27、131，1111边 编边 编号号 边 编边 编号号 9 91 21 2 ，232324243131，121210101 21 2 ，242425253232，131311111 31 3 ，212126263232，141412121 31 3 ，222227273333，111113131 41 4 ，232328283333，121214141 41 4 ，242429293434，131315152 12 1 ，313130303434，1414面编号面编号 面编号面编号 1 17 7，2323，151511112525，6 6，29292 28 8，1717，272712123030，

28、6 6，26263 31111，1616，252513131111，1 1，7 74 42929，2828，121214148 8，1 1，12125 59 9，1919，242415159 9，2 2，13136 62828，2121，101016161414，2 2，10107 72626，2020，131317171919，3 3，15158 81414，2222，303018181616，3 3，20209 92727，5 5，232319191717，4 4，212110102424，5 5，282820202222，4 4，1818 三维实体表示方法三维实体表示方法 从用户角度来看

29、，形体以特征表示和从用户角度来看，形体以特征表示和构造的实体几何表示比较适宜；从计算机对构造的实体几何表示比较适宜；从计算机对形体的存储管理和操作运算角度看，以边界形体的存储管理和操作运算角度看，以边界表示最为实用。表示最为实用。 1 1 构造的实体几何法构造的实体几何法 构造的实体几何构造的实体几何(CSG:Constructive (CSG:Constructive Solid Geometry)Solid Geometry)法是指任意复杂的形体都法是指任意复杂的形体都可以用简单形体可以用简单形体( (体素体素) )的组合来表示。的组合来表示。 形体的形体的CSGCSG表示可看成是一棵有序

30、的二表示可看成是一棵有序的二叉树，称为叉树，称为CSGCSG树。其终端结点或是体素，树。其终端结点或是体素，如长方体、圆锥等；或是刚体运动的变换参如长方体、圆锥等；或是刚体运动的变换参数，如平移参数数，如平移参数T Tx x等；非终端结点或是正则等；非终端结点或是正则的集合运算，一般有交、并、差运算；的集合运算，一般有交、并、差运算；或是刚体的几何变换，如平移、旋转等。或是刚体的几何变换，如平移、旋转等。 采用采用BNFBNF范式可定义范式可定义CSGCSG树若下：树若下： :=:=| CSG CSG树是无二义性的，但不是唯一的，其定树是无二义性的，但不是唯一的，其定义域取决于所用体素以及所允

31、许的几何变换义域取决于所用体素以及所允许的几何变换和正则集合运算算子。和正则集合运算算子。 CSGCSG表示的优点：表示的优点： 数据结构比较简单，数据量比较小，内部数数据结构比较简单，数据量比较小，内部数据的管理比较容易；据的管理比较容易；每个每个CSGCSG表示都和一个实际的有效形体所对应；表示都和一个实际的有效形体所对应；CSGCSG表示可方便地转换成表示可方便地转换成BrepBrep表示，从而可支持表示，从而可支持广泛的应用；广泛的应用； 比较容易修改比较容易修改CSGCSG表示形体的形状。表示形体的形状。CSGCSG表示的缺点：表示的缺点：产生和修改形体的操作种类有限，基于集合运算产

32、生和修改形体的操作种类有限，基于集合运算对形体的局部操作不易实现；对形体的局部操作不易实现； 由于形体的边界几何元素由于形体的边界几何元素( (点、边、面点、边、面) )是隐含是隐含地表示在地表示在CSGCSG中，故显示与绘制中，故显示与绘制CSGCSG表示的形体表示的形体需要较长的时间。需要较长的时间。并2 2 特征表示特征表示 特征表示是从应用层来定义形体，因而可特征表示是从应用层来定义形体，因而可以较好地表达设计者的意图，为制造和检验以较好地表达设计者的意图，为制造和检验产品和形体提供技术依据和管理信息。从功产品和形体提供技术依据和管理信息。从功能上看可分为形状、精度、材料和技术特征。能

33、上看可分为形状、精度、材料和技术特征。 形状特征：体素、孔、槽、键等形状特征：体素、孔、槽、键等 精度特征：形位公差、表面粗糙度等；精度特征：形位公差、表面粗糙度等； 材料特征：材料硬度、热处理方法等；材料特征：材料硬度、热处理方法等； 技术特征：形体的性能参数和特征等。技术特征：形体的性能参数和特征等。 形状特征单元是一个有形的几何实体，是一形状特征单元是一个有形的几何实体，是一组可加工表面的集合。如采用长、宽、高三组可加工表面的集合。如采用长、宽、高三尺寸表示的长方体；采用底面半径及高度表尺寸表示的长方体；采用底面半径及高度表示的圆柱体均是可选用的形状特征单元。示的圆柱体均是可选用的形状特

34、征单元。 形状特征单元的形状特征单元的BNFBNF范式可定义如下：范式可定义如下： ：=|; ：= =长方体长方体| |圆柱体圆柱体| |球体球体| |圆锥体圆锥体| |棱棱锥体锥体| |棱柱体棱柱体| |棱台体棱台体| |圆环体圆环体| |楔形体楔形体| |圆角圆角体体| |； ：= =并并| |交交| |差差| |放；放； ：= =外圆角外圆角| |内圆角内圆角| |倒倒角。角。 3 3 边界表示边界表示 边界表示详细记录了构成形体的所有几何边界表示详细记录了构成形体的所有几何元素的几何信息及其相互连接关系元素的几何信息及其相互连接关系拓扑关系，拓扑关系，便于直接存取构成形体的各个面、面的

35、边界以便于直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。为基础的各种几何运算和操作。 形体的边界表示就是用面、环、边、点来形体的边界表示就是用面、环、边、点来定义形体的位置和形状。例如，一个长方体由定义形体的位置和形状。例如，一个长方体由六个面围成，对应有六个环，每个环由四条边六个面围成，对应有六个环，每个环由四条边界定义，每条边又由两个端点定义。而圆柱体界定义，每条边又由两个端点定义。而圆柱体则由上顶面、下底面和圆柱面所围成，对应有则由上顶面、下底面和圆柱面所围成，对应有上顶面圆环、下底面圆环。

36、上顶面圆环、下底面圆环。 BrepBrep表示的优点是：表示的优点是： 表示形体的点、边、面等几何元素是显式表表示形体的点、边、面等几何元素是显式表示的，使得绘制示的，使得绘制BrepBrep表示形体的速度较快，表示形体的速度较快，而且比较容易确定几何元素间的连接关系；而且比较容易确定几何元素间的连接关系； 对形体的对形体的BrepBrep表示可有多种操作和运算。表示可有多种操作和运算。BrepBrep表示的缺点是：表示的缺点是： 数据结构复杂，需要大量的存储空间，维护数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂；内部数据结构的程序比较复杂； 修改形体的操作比较难以实现；修

37、改形体的操作比较难以实现； BrepBrep表示并不一定对应一个有效形体，即需表示并不一定对应一个有效形体，即需要有专门的程序来保证要有专门的程序来保证BrepBrep表示形体的有效表示形体的有效性、正则性等。性、正则性等。 八叉树八叉树 假设要表示的形体假设要表示的形体V V可以放在一个充分可以放在一个充分大的正立方体大的正立方体C C内内,C,C的边长为的边长为2 2n n, ,形体形体V C ,V C ,它的八又树表示可以递归定义为它的八又树表示可以递归定义为: : 八叉树每个结点与八叉树每个结点与C C的一个子立方体对的一个子立方体对应，树根就和应，树根就和C C本身对应。如果本身对应

38、。如果V=C,V=C,那么那么V V八八叉树仅有树根。如果叉树仅有树根。如果VC,VC,则将则将C C均分为八个均分为八个子立方体子立方体, ,每个子立方体对应根结点的一个子每个子立方体对应根结点的一个子结点。只要某个子立方体不是完全空白或完结点。只要某个子立方体不是完全空白或完全被全被V V所占据所占据, ,它就要被八等分它就要被八等分, ,从而它对应的从而它对应的结点也有了八个子结点。这样的递归判断及结点也有了八个子结点。这样的递归判断及可能分割一直进行可能分割一直进行, ,直到结点对应的立方体或直到结点对应的立方体或完全空白完全空白, ,或完全被占据或完全被占据, ,或其大小已是预先或其

39、大小已是预先规定的体素大小规定的体素大小. . 这时对它与这时对它与V V之交作一定的之交作一定的“舍舍入入”, ,使体素或认为是空白使体素或认为是空白, ,或认为是或认为是被被V V占据的。这里所谓的体素占据的。这里所谓的体素, ,就是指就是指被分割后得到的小立方体。被分割后得到的小立方体。 通常称对应立方体被形体通常称对应立方体被形体V V完全占完全占据的结点为据的结点为黑结点黑结点, ,完全不占据的为完全不占据的为白白结点结点, ,部分被占据的为部分被占据的为灰结点灰结点。 存贮结构存贮结构, , 有常规的、线性的、有常规的、线性的、一对八式的八叉树等等。一对八式的八叉树等等。 八叉树方

40、法的主要优点在于八叉树方法的主要优点在于, ,可以非常方可以非常方便地实现形体的便地实现形体的集合运算集合运算 。 八叉树表示的三维形体的几何变换八叉树表示的三维形体的几何变换 比例变换比例变换 旋转变换旋转变换 相对通过原点的一条任意方向相对通过原点的一条任意方向的直线做旋转任意角度的旋转变换。的直线做旋转任意角度的旋转变换。 构成原形体的构成原形体的直立直立的正立方体经绕原点任的正立方体经绕原点任意轴线旋转任意角度后意轴线旋转任意角度后, , 一般都成为一般都成为斜置斜置的。的。为了使变换后形体的八叉树仍对应一系列直立为了使变换后形体的八叉树仍对应一系列直立的正立方体的正立方体, ,必须对

41、被斜置立方体部分占据体必须对被斜置立方体部分占据体素做出选择素做出选择, ,即或认为是占据即或认为是占据, ,为黑结点为黑结点, ,或认或认为不占据为不占据, ,为白结点为白结点, ,这就必然带来一定的误差。这就必然带来一定的误差。而且执行多次变换后而且执行多次变换后, ,误差积累会大到产生严误差积累会大到产生严重的错误。重的错误。 第一项措施是保持一个原始的八叉树做为参考第一项措施是保持一个原始的八叉树做为参考的源树。设指定了一次变换的源树。设指定了一次变换R R1 1, ,接着又要做变换接着又要做变换R R2 2, ,可以计算出可以计算出复合变换复合变换R=RR=R1 1R R2 2, ,

42、然后对原始的八然后对原始的八叉树做一次变换。这样来避免误差的积累。叉树做一次变换。这样来避免误差的积累。 第二项措施是为了尽量减少第二项措施是为了尽量减少 舍入舍入 误差误差, ,可以可以规定一个当前正要重建的八叉树规定一个当前正要重建的八叉树, ,如果它的最底如果它的最底层叶结点对应的体素是部分地为显示对象所占层叶结点对应的体素是部分地为显示对象所占据，那么当且仅当这个体素的中心位于某个黑据，那么当且仅当这个体素的中心位于某个黑变换后立方体内时变换后立方体内时, ,这个体素才被规定为黑这个体素才被规定为黑, ,否否则就规定为白。这样规定使得一般不会产生原则就规定为白。这样规定使得一般不会产生

43、原来不存在的孔洞，而不这样规定来不存在的孔洞，而不这样规定, ,例如简单地规例如简单地规定部分被占据的体素都为白定部分被占据的体素都为白, ,则可能在做则可能在做45450 0左右左右旋转时原来黑立方体变换为部分占据若干体素旋转时原来黑立方体变换为部分占据若干体素而被指定为白而被指定为白, ,在变换后形体中间出现断裂。在变换后形体中间出现断裂。 设己采取了上述两项措施设己采取了上述两项措施, ,已知形体变换已知形体变换前的八叉树表示前的八叉树表示T T1 1, ,己计算出己计算出 要做的复合变换要做的复合变换R,R,要确定变换后形体的要确定变换后形体的八叉树表示八叉树表示T T2 2, ,可以

44、写出如下的算法框架：可以写出如下的算法框架：1. 1. 遍历形体原来的八叉树遍历形体原来的八叉树T T1 1, ,对遇到的每个黑对遇到的每个黑结点结点, ,做下述步做下述步2 2。2. 2. 对遇到黑结点对应的正立方体做相应变换对遇到黑结点对应的正立方体做相应变换, ,得它新的一般来说是斜置的新位置。若这位得它新的一般来说是斜置的新位置。若这位置已超出定义八叉树的充分大正立方体置已超出定义八叉树的充分大正立方体C C之外之外, ,报告出错报告出错; ;否则执行下述的步否则执行下述的步3 3。3. 3. 从要计算求出的目标树从要计算求出的目标树T T2 2的根开始的根开始, ,检查检查2 2中确

45、定的处于新位置立方体与中确定的处于新位置立方体与T T2 2中结点对应中结点对应的直立的正立方体是否相交的直立的正立方体是否相交, ,分以下三种情况分以下三种情况进行处理进行处理: : (1) 1) 不相交不相交, ,说明正考查直立正立方体未被占说明正考查直立正立方体未被占据据, ,可保持为白结点可保持为白结点, ,不做处理。不做处理。(2) (2) 直立的正立方体整个被占据直立的正立方体整个被占据, ,即它在变换即它在变换后后 斜置斜置 立方体内立方体内, ,置对应结点为黑结点。置对应结点为黑结点。(3) (3) 在上述两条均不成立时在上述两条均不成立时, ,生成当前结点生成当前结点的八个子

46、结点的八个子结点, ,对八个子结点对应的八个直对八个子结点对应的八个直立子立方体立子立方体, ,依次再递归执行步依次再递归执行步3 3。如果最。如果最终这八个结点被标上同样特性终这八个结点被标上同样特性, ,比方为黑结比方为黑结点点, ,则应再删掉这八个子结点而把它们的共则应再删掉这八个子结点而把它们的共同父结点置为黑。同父结点置为黑。 算法中算法中, ,主要工作是检查某个直立的正主要工作是检查某个直立的正立方体与一个斜置的正立方体是否相交立方体与一个斜置的正立方体是否相交, ,。对所有黑结点对应正立方体处理相同对所有黑结点对应正立方体处理相同, ,使得使得操作可以并行进行。操作可以并行进行。

47、线性八叉树线性八叉树 在对立方体做八等分时在对立方体做八等分时, ,按一致的方式按一致的方式, , 对分出的子立方体进行编号。若再分共进对分出的子立方体进行编号。若再分共进行行n n层，则每个结点可以用层，则每个结点可以用n n位的八进制数位的八进制数的数串的数串来表示来表示, ,数串从左至右数串从左至右, ,第一位对应第一位对应第一次划分，第二位对应第二位划分，依第一次划分，第二位对应第二位划分，依此类推。据此整个八叉树就可以根据对其此类推。据此整个八叉树就可以根据对其做深度第一遍历而依次列出的黑结点的编做深度第一遍历而依次列出的黑结点的编号序列来表示号序列来表示 。 前图所示三维形体前图所

48、示三维形体, ,其线性八叉树表示是其线性八叉树表示是: : 0 x,10,12,13,14,2x,4x,6x,7x 0 x,10,12,13,14,2x,4x,6x,7x 求并运算求并运算 C C1 1UCUC2 2 两棵线性八叉树两棵线性八叉树: :C C1 1=122,123,301,302,303,305,307=122,123,301,302,303,305,307C C2 2=12x,300,302,304,306=12x,300,302,304,306 将将C C2 2的各结点依次插入到的各结点依次插入到C C1 1的适当位置的适当位置, ,使使插入后编号渐增这一性质保持不变。当插

49、入后编号渐增这一性质保持不变。当C C2 2中结中结点可以点可以包含包含C C1 1中若干结点时中若干结点时, ,则则取而代之取而代之。另。另外外, ,如果插入后可以进行结点如果插入后可以进行结点 压缩压缩,也应该也应该立即进行立即进行: :C C1 1UCUC2 2=12x,300,301,302,303,304,305,306,307 =12x,300,301,302,303,304,305,306,307 =12x,30 x =12x,30 x 八叉树表示形体的显示八叉树表示形体的显示 当观察位置是当观察位置是x x1 10,y0,y1 10,z00时时, ,最可最可能被遮挡看不见的是编

50、号能被遮挡看不见的是编号2 2的子立方体的子立方体, ,全全部依次排出可以是部依次排出可以是26034715 26034715 z zl l0,y0,y1 10,x00 优先级优先级2603471526034715。前图表示形体的线性前图表示形体的线性八叉树八叉树0 x,10,12,13,14,0 x,10,12,13,14,2x,4x,6x,7x 2x,4x,6x,7x 按结点应显示次序排按结点应显示次序排出的序列就是出的序列就是: :2x,6x,Ox,4x,7x,12,2x,6x,Ox,4x,7x,12,10,13,14 10,13,14 z z1 1 y y1 1 x x1 1 优先级优

51、先级000000735612407356124000000371256043712560400000517430625174306200000153074261530742600000000002603471526034715000000000000421653704216537第三节第三节 分形分形 分形的概念分形的概念 三分康托三分康托(Cantor)(Cantor)集集 设设E E0 0是闭区间是闭区间0,1,0,1,即即E E0 0是满足是满足0 0 x1的实数的实数x x组成的点集组成的点集;E;E1 1是是E E0 0去掉中间去掉中间1/31/3之后的点集之后的点集, ,即即E E

52、1 1是两个闭区间是两个闭区间00，1/31/3和和1/31/3，2/3;E2/3;E2 2是分是分别去掉别去掉E E1 1中两个区间的中间中两个区间的中间1/31/3之后的点集之后的点集, ,即即E E2 2已经是四个闭区间。此过程要继续进行已经是四个闭区间。此过程要继续进行,E,Ek k是是2 2k k个长度为个长度为1/31/3k k的闭区间组成的点集。三分康托集的闭区间组成的点集。三分康托集F F是属于所有的是属于所有的E Ek k的点组成的集的点组成的集, ,即即 。 F F可以看成是集序列可以看成是集序列E Ek k当当k k趋于无穷时的极限。趋于无穷时的极限。只能画出只能画出k

53、k取定时的某个取定时的某个E Ek k。当。当k k充分大时充分大时,E,Ek k是是对对F F的很好的近似的表现的很好的近似的表现 0 0k kk kE EF F 三分康托集是区间三分康托集是区间0,10,1中的可以展成以中的可以展成以3 3为为底的幕级数的下面形式的数组成的底的幕级数的下面形式的数组成的: :a a1 13 3-1-1+a+a2 23 3-2-2+a+a3 33 3-3-3 其中其中a ai i的取值限制为的取值限制为0 0或或2,2,不取不取1 1。为看清。为看清这一事实这一事实, ,注意从注意从E E0 0得到得到E E1 1时时, ,去掉的是去掉的是a ai i=1=

54、1的的数数, ,从从E E1 1得得E E2 2时时, ,去掉的是去掉的是a a2 2=1=1的数的数, ,并以此类推。并以此类推。 三分康托集具有的一些值得注意的特征三分康托集具有的一些值得注意的特征, ,这些特征对许多其它的分形也是大体上适合的。这些特征对许多其它的分形也是大体上适合的。(1) F(1) F是自相似的。是自相似的。E E1 1的两个区间的两个区间00，1/31/3，1/31/3，2/32/3的每一个的每一个, ,其内部其内部F F的部分与的部分与F F整体整体相似相似, ,相似比为相似比为1/31/3。(2) F(2) F具有具有“精细结构精细结构”，即它包含有任意小比，即

55、它包含有任意小比例的细节。例的细节。 (3) F(3) F的实际定义是简单的和明确的。的实际定义是简单的和明确的。 (4) (4) 传统的几何学很难描述传统的几何学很难描述F F的性质的性质, ,因为因为F F不是不是满足某些简单条件的点的轨迹满足某些简单条件的点的轨迹, ,也不是任何简也不是任何简单的方程的解的集合。单的方程的解的集合。(5) F(5) F的局部几何性质也很难描述的局部几何性质也很难描述, ,在它的每点附在它的每点附近都有大量被各种不同间隔分开的其它点。近都有大量被各种不同间隔分开的其它点。 (6) (6) 按传统几何学中的长度概念按传统几何学中的长度概念,F,F的长度为的长

56、度为零。就是说零。就是说, ,尽管从不可数集合这点上说尽管从不可数集合这点上说F F是一是一个相当大的集个相当大的集, ,但它却没有长度但它却没有长度, ,或者说长度不或者说长度不能对能对F F的形状或大小提供有意义的描述。的形状或大小提供有意义的描述。von Kochvon Koch曲线曲线 称集合称集合F F是分形是分形, ,即认为它具有下面典型即认为它具有下面典型的性质的性质: : (1)(1) F F具有精细的结构，即有任意小比例的具有精细的结构，即有任意小比例的细节。细节。 (2) F(2) F是如此的不规则以至它的整体和局是如此的不规则以至它的整体和局部都不能用传统的几何语言来描述

57、。部都不能用传统的几何语言来描述。(3) F(3) F具有某种自相似的形式具有某种自相似的形式, ,可能是近似可能是近似的或是统计的。的或是统计的。(4) (4) 一般地一般地,F,F的的 分形维数分形维数 大于它的拓扑维大于它的拓扑维数。数。 (5) (5) 在大多数令人感兴趣的情形下在大多数令人感兴趣的情形下,F,F以以非常简单的方法定义非常简单的方法定义, ,可能由迭代产生。可能由迭代产生。 考虑一个简单的几何图形考虑一个简单的几何图形, ,取一个边长为取一个边长为1 1的正方形的正方形, ,若每边扩大若每边扩大2 2倍倍, ,则正方形面积放大则正方形面积放大4 4倍倍, ,其数学表达式

58、为其数学表达式为2 22 2=4,=4,这是这是2 2维图形。对维图形。对3 3维图形维图形, ,如考虑边长为如考虑边长为1 1的立方体的立方体, ,令每边长放令每边长放大大2 2倍倍, ,则立方体体积扩大则立方体体积扩大8 8倍倍, ,其数学表达式其数学表达式为为2 23 3=8=8。 类似地类似地, ,对一个对一个DfDf维的几何对象维的几何对象, ,若每边长若每边长扩大扩大L L倍倍, ,则这个几何对象相应地放大则这个几何对象相应地放大K K倍倍, ,归归纳前述结果纳前述结果,D,Df f,L,K,L,K三者间的关系式应为三者间的关系式应为: :L LDfDf=K =K 解出解出D Df

59、 f, ,有有: :D Df f=lnK/lnL=lnK/lnL 这里这里D Df f不必是整数。这就是不必是整数。这就是HausdorffHausdorff引人的维引人的维数概念数概念, ,可以称为可以称为HausdorffHausdorff维数。维数。 假定有一个单位正方形假定有一个单位正方形, ,把它每边三等把它每边三等分得九个小的正方形分得九个小的正方形, ,九个小正方形面积总九个小正方形面积总和是原单位正方形面积和是原单位正方形面积, ,即即9 9(1/3)(1/3)2 2=1=1。现。现在我们把在我们把D Df f维的几何对象等分为维的几何对象等分为N N个小的几个小的几何图形何图

60、形, ,则每个小图形每维缩小为原来的则每个小图形每维缩小为原来的r r倍倍, ,而而N N个小图形的总和应有个小图形的总和应有N Nr rDfDf=1=1。 这时解出这时解出 , ,有有: : 容易看出式容易看出式(1)(1)和和(2)(2)本质上是相同的本质上是相同的, ,即这样即这样引入的也是引入的也是HausdorffHausdorff维数维数 ln(1/r)ln(1/r)lnNlnND DF FF FD D von Koch von Koch曲线曲线, ,每次分为每次分为4 4个小图形个小图形, ,每每个小图形缩小个小图形缩小1/31/3倍倍, ,故其故其HausdorffHausdo