形体的表示及其数据结构课件.ppt-淘文阁

资源描述

《形体的表示及其数据结构课件.ppt》由会员分享，可在线阅读，更多相关《形体的表示及其数据结构课件.ppt（81页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、关于形体的表示及其数据结构第1页，此课件共81页哦第一节第一节二维形体的表示二维形体的表示二维图形的边界表示二维图形的边界表示折线法和带树法折线法和带树法折线法就是用多段线段形成的折线去折线法就是用多段线段形成的折线去逼近曲线逼近曲线折线表示曲线应该解决的关键问题是折线表示曲线应该解决的关键问题是:如何恰当地确定曲线上一系列点如何恰当地确定曲线上一系列点,使之在使之在某些判定准则下达到最优。某些判定准则下达到最优。第2页，此课件共81页哦带树法带树法带树是一棵二叉树带树是一棵二叉树,树的每个结点对应树的每个结点对应一个矩形带段一个矩形带段,这样每个结点可由八个字这样每个结点可由八个

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

3、Pn 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这这两两组组点点分分别别做做与与步步1

4、 1中中相相同同的的构构造造矩矩形形带带段段及及对对应应结结点点的的操操作作,产生的两个结点产生的两个结点,分别是根的左右子结点。分别是根的左右子结点。3.3.反复执行上述操作反复执行上述操作,直到所产生结点的直到所产生结点的w=ww=wl l+w wr r w w0 0。这样的结点是叶结点。这样的结点是叶结点。第5页，此课件共81页哦设表示曲线有设表示曲线有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页，此

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

6、点就认为是被显示了子结点都被显示的结点就认为是被显示了,按按此看法此看法,显示带树表示的曲线就是显示带树的显示带树表示的曲线就是显示带树的结点。结点。第7页，此课件共81页哦带树表示的曲线求交带树表示的曲线求交两两个个矩矩形形带带段段S S1 1和和S S2 2的的位位置置关关系系有有如如下下三种三种:(1)(1)不相交。不相交。(2)(2)良良性性相相交交,即即S S1 1的的与与起起点点至至终终点点连连线线平平行行的的两两条条边边都都与与S S2 2相相交交,S,S2 2的的与与起起点点至至终终点点连连线线平行的两条边也都与平行的两条边也都与S S1 1相交。相交。(3)(3)可能性相

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

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

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

10、封闭的,与用象素阵列来表示图与用象素阵列来表示图形的方法比较空间需求也算是节省的。形的方法比较空间需求也算是节省的。第11页，此课件共81页哦平面图形的四叉树表示方法平面图形的四叉树表示方法假定一个平面假定一个平面图图形是形是黑白黑白的二的二值图值图形形,即即组组成成图图形象素形象素阵阵列的列的仅仅有黑色象素有黑色象素值值1,1,白白色象素色象素值值0,0,设设表表现图现图形的象素形的象素阵阵列由列由2 2n n22n n个象素个象素组组成。成。表示表示该图该图形的四叉形的四叉树结树结构可以如下形成构可以如下形成:图图形形显显然包括然包括2 2n n22n n的正方形中，的正方形中，这这个正

11、方个正方形是四叉形是四叉树树的根的根结结点。点。若若图图形整个地占据形整个地占据这这个正方形个正方形,则图则图形形就用就用该该正方形表示正方形表示,否否则则将将该该正方形均分正方形均分为为四四个小正方形，每个小正方形个小正方形，每个小正方形边长为边长为原正方形原正方形边长边长的一半的一半.它它们们是根是根结结点的四个子点的四个子结结点点,可可编编号号为为0,1,2,30,1,2,3。第12页，此课件共81页哦再考再考查查每个小正方形每个小正方形,若整个被若整个被图图形占形占据据,则标记则标记相相应结应结点点为为1,1,可称可称为为黑黑结结点点。若。若整个与整个与图图形不相交形不相交,则标记则

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

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

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

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

16、一层中的类推可形成多层结构。其中，每一层中的部分，我们把它有称为几何元素。部分，我们把它有称为几何元素。第18页，此课件共81页哦点点它它是是0 0维维几几何何元元素素，有有端端点点、交交点点、切切点、孤立点等形式。点、孤立点等形式。曲曲线线、曲曲面面的的应应用用中中会会涉涉及及到到三三种种类类型型的点：的点：型值点型值点相应曲线、曲面必然经过的点。相应曲线、曲面必然经过的点。控控制制点点相相应应曲曲线线、曲曲面面不不一一定定经经过过的的点点，仅仅用于确定位置和形状。用于确定位置和形状。插插值值点点在在型型值值点点之之间间插插入入的的一一系系列列点点，用用于于提高曲线曲面的输出精度。提

17、高曲线曲面的输出精度。第19页，此课件共81页哦不同的空间中点的表示方式不同的空间中点的表示方式一维空间中用一元组一维空间中用一元组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)表示；表示；点是几何造型中的最基本的元素，曲线、点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述。曲面和其它形体都可以用有序的点集描述。用计算机存储、管理、输出形体的实质用计算机存储、管理、输出形体的实质就是

18、对点集及其连接关系的处理。就是对点集及其连接关系的处理。第20页，此课件共81页哦边边边边是是一一维维几几何何元元素素，是是两两个个邻邻面面（正正则则形形体体）或或多多个个邻邻面面（非非正正则则形形体体）的的交交界界。边边分分直直线线边边和和曲曲线线边边。直直线线边边由由起起点点和和终终点点两两端端点点确确定定；曲曲线线边边由由一一系系列列型型值值点点或或控控制制点点表表示示，也可以用显示、隐式方程描述。也可以用显示、隐式方程描述。环环环是有序有向边（直线段或曲线段）组环是有序有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻成的面的封闭边界。环中的边不能相交，相邻两条边共

19、享一个端点。环有内外之分，确定面两条边共享一个端点。环有内外之分，确定面的最大外边界的环称之为的最大外边界的环称之为外环外环，通常其边按，通常其边按逆逆时针方向时针方向排序。而把确定面中内孔或凸台边界排序。而把确定面中内孔或凸台边界的环称之为的环称之为内环内环，其边相应外环排序方向相反，其边相应外环排序方向相反，通常按通常按顺时针顺时针方向排序。方向排序。第21页，此课件共81页哦面面面面是是二二维维元元素素，是是形形体体上上一一个个有有限限、非非零零的的区区域域，它它由由一一个个外外环环和和若若干干个个内内环环所所界界定定。面面有有方方向向性性，一一般般用用其其外外法法向向量量作作为为该该

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

21、、悬边的形体是非正则形体。悬面、悬边的形体是非正则形体。第22页，此课件共81页哦体素体素体体素素是是可可以以用用有有限限个个尺尺寸寸参参数数定定位位和和定定型型的体，常有下面三种定义形式。的体，常有下面三种定义形式。一组单元实体一组单元实体长方体、圆柱体、圆锥体、球体。长方体、圆柱体、圆锥体、球体。扫扫描描体体由由参参数数定定义义的的一一条条（一一组组）截截面面轮轮廓廓线线沿沿一一条条（一一组组）空空间间参参数数曲曲线线作作扫扫描描运运动动而而产生的形体。产生的形体。用代数半空间定义的形体用代数半空间定义的形体，在此半空间中点集，在此半空间中点集可定义可定义(x,y,z)|f(x,y,

22、z)0(x,y,z)|f(x,y,z)0此处的此处的f f应是不应是不可约的多项式。可约的多项式。形体的层次结构形体的层次结构点点边边环环面面外壳外壳形体。形体。第23页，此课件共81页哦在几何造型中最基本的几何元素是在几何造型中最基本的几何元素是点（点（V V）、边）、边(E)(E)、面、面(F),(F),这三种元素一这三种元素一共有九种连接关系共有九种连接关系第24页，此课件共81页哦线框、表面及实体表示线框、表面及实体表示常用的多面体表示法是三表表示法，即采常用的多面体表示法是三表表示法，即采用三个表用三个表:顶点表顶点表,用来存放多面体各顶点的用来存放多面体各顶点的坐标坐标;边

23、表边表,指出哪两个顶点之间有多面体的指出哪两个顶点之间有多面体的边；边；面表面表，指出哪些边围成了多面体的表面。，指出哪些边围成了多面体的表面。任意多面体容易得到它的三表表示任意多面体容易得到它的三表表示,但任但任意三张表却不一定表示了一个真实的多面体。意三张表却不一定表示了一个真实的多面体。这里必须满足的条件至少有以下几项这里必须满足的条件至少有以下几项:顶点表顶点表中的每个顶点至少是中的每个顶点至少是三边三边的端点的端点;边表中的每边表中的每条边是条边是两个多边形两个多边形面的公共边；每个多边形面的公共边；每个多边形面是封闭的等等。面是封闭的等等。第25页，此课件共81页哦第26页，此课件

24、共81页哦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 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顶点表顶点表面表面表边表边表第27页，此课件共81页哦空间正二十空间正二十面体面体V V2020,的三的三表表示。表表示。引人

25、一个引人一个正数正数0,0,它它满满足二次方足二次方程程2 2-1=0,1=0,因此因此=1/2(1+=1/2(1+)1.618034)1.618034。XYZ第28页，此课件共81页哦编号编号xyz编号编号xyz110123-101213-001-12431-10-1 014-0-13201-2110330-1221-0340-1-第29页，此课件共81页哦边边编编号号边边编编号号1 11111，131316162121，32322 21212，141417172222，33333 32121，232318182222，34344 42222，242419192323，31315 531

26、31，333320202323，32326 63232，343421212424，33337 71111，212122222424，34348 81111，222223233131，1111边边编编号号边边编编号号9 91212，232324243131，121210101212，242425253232，131311111313，212126263232，141412121313，222227273333，111113131414，232328283333，121214141414，242429293434，131315152121，313130303434，1414第30页，此课件共8

27、1页哦面编号面编号面编号面编号1 17 7，2323，151511112525，6 6，29292 28 8，1717，272712123030，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，2323191

28、91717，4 4，212110102424，5 5，282820202222，4 4，1818第31页，此课件共81页哦第32页，此课件共81页哦三维实体表示方法三维实体表示方法从用户角度来看，形体以特征表示和构从用户角度来看，形体以特征表示和构造的实体几何表示比较适宜；从计算机对形造的实体几何表示比较适宜；从计算机对形体的存储管理和操作运算角度看，以边界表体的存储管理和操作运算角度看，以边界表示最为实用。示最为实用。1 1 构造的实体几何法构造的实体几何法构造的构造的实实体几何体几何(CSG:Constructive(CSG:Constructive Solid Geometry)So

29、lid Geometry)法是指任意复法是指任意复杂杂的形体都的形体都可以用可以用简单简单形体形体(体素体素)的的组组合来表示。合来表示。形体的形体的CSGCSG表示可看成是一棵有序的二表示可看成是一棵有序的二叉叉树树，称，称为为CSGCSG树树。其。其终终端端结结点或是体素，点或是体素，如如长长方体、方体、圆锥圆锥等；或是等；或是刚刚体运体运动动的的变换变换参参数，如平移参数数，如平移参数T Tx x等；非等；非终终端端结结点或是正点或是正则则的集合运算，一般有交、并、差运算；的集合运算，一般有交、并、差运算；第33页，此课件共81页哦或是刚体的几何变换，如平移、旋转等。或是刚体的几何变换，

30、如平移、旋转等。采用采用BNFBNF范式可定义范式可定义CSGCSG树若下：树若下：:=:=|CSGCSG树树是是无无二二义义性性的的，但但不不是是唯唯一一的的，其其定定义义域域取取决决于于所所用用体体素素以以及及所所允允许许的的几几何何变变换换和正则集合运算算子。和正则集合运算算子。CSGCSG表示的优点：表示的优点：数数据据结结构构比比较较简简单单，数数据据量量比比较较小小，内内部部数数据的管理比较容易；据的管理比较容易；第34页，此课件共81页哦每个每个CSGCSG表示都和一个实际的有效形体所对应；表示都和一个实际的有效形体所对应；CSGCSG表表示示可可方方便便地地转转换换成成Brep

31、Brep表表示示，从从而而可可支支持持广泛的应用；广泛的应用；比较容易修改比较容易修改CSGCSG表示形体的形状。表示形体的形状。CSGCSG表示的缺点：表示的缺点：产产生生和和修修改改形形体体的的操操作作种种类类有有限限，基基于于集集合合运运算算对形体的局部操作不易实现；对形体的局部操作不易实现；由于形体的边界几何元素由于形体的边界几何元素(点、边、面点、边、面)是隐含是隐含地表示在地表示在CSGCSG中，故显示与绘制中，故显示与绘制CSGCSG表示的形体表示的形体需要较长的时间。需要较长的时间。第35页，此课件共81页哦并第36页，此课件共81页哦2 2 特征表示特征表示特特征征表表示示

32、是是从从应应用用层层来来定定义义形形体体，因因而而可可以以较较好好地地表表达达设设计计者者的的意意图图，为为制制造造和和检检验验产产品品和和形形体体提提供供技技术术依依据据和和管管理理信信息息。从从功功能能上看可分为形状、精度、材料和技术特征。上看可分为形状、精度、材料和技术特征。形状特征：体素、孔、槽、键等形状特征：体素、孔、槽、键等精度特征：形位公差、表面粗糙度等；精度特征：形位公差、表面粗糙度等；材料特征：材料硬度、热处理方法等；材料特征：材料硬度、热处理方法等；技术特征：形体的性能参数和特征等。技术特征：形体的性能参数和特征等。形状特征单元是一个有形的几何实体，是一形状特征单元是一个

34、此课件共81页哦3 3 边界表示边界表示边界表示详细记录了构成形体的所有几何边界表示详细记录了构成形体的所有几何元素的几何信息及其相互连接关系元素的几何信息及其相互连接关系拓扑关系，拓扑关系，便于直接存取构成形体的各个面、面的边界以便于直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。为基础的各种几何运算和操作。形体的边界表示就是用面、环、边、点来形体的边界表示就是用面、环、边、点来定义形体的位置和形状。例如，一个长方体由定义形体的位置和形状。例如，一个长方体由六个面围成，对应有六个环，每个环由四条

35、边六个面围成，对应有六个环，每个环由四条边界定义，每条边又由两个端点定义。而圆柱体界定义，每条边又由两个端点定义。而圆柱体则由上顶面、下底面和圆柱面所围成，对应有则由上顶面、下底面和圆柱面所围成，对应有上顶面圆环、下底面圆环。上顶面圆环、下底面圆环。第40页，此课件共81页哦BrepBrep表示的优点是：表示的优点是：表表示示形形体体的的点点、边边、面面等等几几何何元元素素是是显显式式表表示示的的，使使得得绘绘制制BrepBrep表表示示形形体体的的速速度度较较快快，而且比较容易确定几何元素间的连接关系；而且比较容易确定几何元素间的连接关系；对形体的对形体的BrepBrep表示可有多种操作和运

36、算。表示可有多种操作和运算。BrepBrep表示的缺点是：表示的缺点是：数数据据结结构构复复杂杂，需需要要大大量量的的存存储储空空间间，维维护护内部数据结构的程序比较复杂；内部数据结构的程序比较复杂；修改形体的操作比较难以实现；修改形体的操作比较难以实现；BrepBrep表示并不一定对应一个有效形体，即需表示并不一定对应一个有效形体，即需要有专门的程序来保证要有专门的程序来保证BrepBrep表示形体的有效表示形体的有效性、正则性等。性、正则性等。第41页，此课件共81页哦八叉树八叉树假设要表示的形体假设要表示的形体V V可以放在一个充分大可以放在一个充分大的正立方体的正立方体C C内内,C

37、,C的边长为的边长为2 2n n,形体形体V C,V C,它它的八又树表示可以递归定义为的八又树表示可以递归定义为:八叉树每个结点与八叉树每个结点与C C的一个子立方体对应，的一个子立方体对应，树根就和树根就和C C本身对应。如果本身对应。如果V=C,V=C,那么那么V V八叉树八叉树仅有树根。如果仅有树根。如果VC,VC,则将则将C C均分为八个子立均分为八个子立方体方体,每个子立方体对应根结点的一个子结点。每个子立方体对应根结点的一个子结点。只要某个子立方体不是完全空白或完全被只要某个子立方体不是完全空白或完全被V V所所占据占据,它就要被八等分它就要被八等分,从而它对应的结点也从而它对应

38、的结点也有了八个子结点。这样的递归判断及可能分有了八个子结点。这样的递归判断及可能分割一直进行割一直进行,直到结点对应的立方体或完全空直到结点对应的立方体或完全空白白,或完全被占据或完全被占据,或其大小已是预先规定的或其大小已是预先规定的体素大小体素大小.第42页，此课件共81页哦这时对它与这时对它与V V之交作一定的之交作一定的“舍入舍入”,使体素或认为是空白使体素或认为是空白,或认为是被或认为是被V V占据的。占据的。这里所谓的体素这里所谓的体素,就是指被分割后得到的小就是指被分割后得到的小立方体。立方体。通常称对应立方体被形体通常称对应立方体被形体V V完全占据完全占据的结点为的结点为

39、黑结点黑结点,完全不占据的为完全不占据的为白结点白结点,部分被占据的为部分被占据的为灰结点灰结点。存贮结构存贮结构,有常规的、线性的、一有常规的、线性的、一对八式的八叉树等等。对八式的八叉树等等。第43页，此课件共81页哦八叉树方法的主要优点在于八叉树方法的主要优点在于,可以非常方可以非常方便地实现形体的便地实现形体的集合运算集合运算。八叉树表示的三维形体的几何变换八叉树表示的三维形体的几何变换比例变换比例变换旋转变换旋转变换相对通过原点的一条任意方向相对通过原点的一条任意方向的直线做旋转任意角度的旋转变换。的直线做旋转任意角度的旋转变换。构成原形体的构成原形体的直立直立的正立方体经

40、绕原点任的正立方体经绕原点任意轴线旋转任意角度后意轴线旋转任意角度后,一般都成为一般都成为斜置斜置的。的。为了使变换后形体的八叉树仍对应一系列直立为了使变换后形体的八叉树仍对应一系列直立的正立方体的正立方体,必须对被斜置立方体部分占据体必须对被斜置立方体部分占据体素做出选择素做出选择,即或认为是占据即或认为是占据,为黑结点为黑结点,或认或认为不占据为不占据,为白结点为白结点,这就必然带来一定的误差。这就必然带来一定的误差。而且执行多次变换后而且执行多次变换后,误差积累会大到产生严误差积累会大到产生严重的错误。重的错误。第44页，此课件共81页哦第第一一项项措措施施是是保保持持一一个个原原始始

41、的的八八叉叉树树做做为为参参考考的的源源树树。设设指指定定了了一一次次变变换换R R1 1,接接着着又又要要做做变变换换R R2 2,可可以以计计算算出出复复合合变变换换R=RR=R1 1RR2 2,然然后后对对原原始始的的八叉树做一次变换。这样来避免误差的积累。八叉树做一次变换。这样来避免误差的积累。第二项措施是为了尽量减少第二项措施是为了尽量减少舍入舍入误差误差,可以可以规定一个当前正要重建的八叉树规定一个当前正要重建的八叉树,如果它的最底如果它的最底层叶结点对应的体素是部分地为显示对象所占据，层叶结点对应的体素是部分地为显示对象所占据，那么当且仅当这个体素的中心位于某个黑变换后那么当

42、且仅当这个体素的中心位于某个黑变换后立方体内时立方体内时,这个体素才被规定为黑这个体素才被规定为黑,否则就规定否则就规定为白。这样规定使得一般不会产生原来不存在的为白。这样规定使得一般不会产生原来不存在的孔洞，而不这样规定孔洞，而不这样规定,例如简单地规定部分被占例如简单地规定部分被占据的体素都为白据的体素都为白,则可能在做则可能在做45450 0左右旋转时原来左右旋转时原来黑立方体变换为部分占据若干体素而被指定为白黑立方体变换为部分占据若干体素而被指定为白,在变换后形体中间出现断裂。在变换后形体中间出现断裂。第45页，此课件共81页哦第46页，此课件共81页哦第47页，此课件共81页哦设己

43、采取了上述两项措施设己采取了上述两项措施,已知形体变换已知形体变换前的八叉树表示前的八叉树表示T T1 1,己计算出己计算出要要做做的的复复合合变变换换R,R,要要确确定定变变换换后后形形体体的的八叉树表示八叉树表示T T2 2,可以写出如下的算法框架：可以写出如下的算法框架：1.1.遍遍历历形形体体原原来来的的八八叉叉树树T T1 1,对对遇遇到到的的每每个个黑黑结点结点,做下述步做下述步2 2。2.2.对对遇遇到到黑黑结结点点对对应应的的正正立立方方体体做做相相应应变变换换,得得它它新新的的一一般般来来说说是是斜斜置置的的新新位位置置。若若这这位位置置已已超超出出定定义义八八叉叉树树的的

44、充充分分大大正正立立方方体体C C之之外外,报告出错报告出错;否则执行下述的步否则执行下述的步3 3。3.3.从要计算求出的目标树从要计算求出的目标树T T2 2的根开始的根开始,检查检查2 2中确定的处于新位置立方体与中确定的处于新位置立方体与T T2 2中结点对应中结点对应的直立的正立方体是否相交的直立的正立方体是否相交,分以下三种情况分以下三种情况进行处理进行处理:第48页，此课件共81页哦(1)1)不不相相交交,说说明明正正考考查查直直立立正正立立方方体体未未被被占占据据,可保持为白结点可保持为白结点,不做处理。不做处理。(2)(2)直直立立的的正正立立方方体体整整个个被被占占据据,即

45、即它它在在变变换换后后斜置斜置立方体内立方体内,置对应结点为黑结点。置对应结点为黑结点。(3)(3)在在上上述述两两条条均均不不成成立立时时,生生成成当当前前结结点点的的八八个个子子结结点点,对对八八个个子子结结点点对对应应的的八八个个直直立立子子立立方方体体,依依次次再再递递归归执执行行步步3 3。如如果果最最终终这这八八个个结结点点被被标标上上同同样样特特性性,比比方方为为黑黑结结点点,则则应应再再删删掉掉这这八八个个子子结结点点而而把把它它们们的的共共同父结点置为黑。同父结点置为黑。算法中算法中,主要工作是检查某个直立的正主要工作是检查某个直立的正立方体与一个斜置的正立方体是否相交立

46、方体与一个斜置的正立方体是否相交,。对所有黑结点对应正立方体处理相同对所有黑结点对应正立方体处理相同,使得使得操作可以并行进行。操作可以并行进行。第49页，此课件共81页哦线性八叉树线性八叉树在对立方体做八等分时在对立方体做八等分时,按一致的方式按一致的方式,对分出的子立方体进行编号。若再分共进对分出的子立方体进行编号。若再分共进行行n n层，则每个结点可以用层，则每个结点可以用n n位的八进制数位的八进制数的数串的数串来表示来表示,数串从左至右数串从左至右,第一位对应第一位对应第一次划分，第二位对应第二位划分，依第一次划分，第二位对应第二位划分，依此类推。据此整个八叉树就可以根据对其此类推

47、。据此整个八叉树就可以根据对其做深度第一遍历而依次列出的黑结点的编做深度第一遍历而依次列出的黑结点的编号序列来表示号序列来表示。前前图图所所示示三三维维形形体体,其其线线性性八八叉叉树树表表示示是是:0 x,10,12,13,14,2x,4x,6x,7x 0 x,10,12,13,14,2x,4x,6x,7x 第50页，此课件共81页哦求并运算求并运算 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

48、,300,302,304,306 将将C C2 2的的各各结结点点依依次次插插入入到到C C1 1的的适适当当位位置置,使使插插入入后后编编号号渐渐增增这这一一性性质质保保持持不不变变。当当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 第51

49、页，此课件共81页哦八叉树表示形体的显示八叉树表示形体的显示当观察位置是当观察位置是x x1 10,y0,y1 10,z00时时,最可最可能被遮挡看不见的是编号能被遮挡看不见的是编号2 2的子立方体的子立方体,全全部依次排出可以是部依次排出可以是26034715 26034715 第52页，此课件共81页哦 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 按结点应显示次序排按结点应显示次序排出的

50、序列就是出的序列就是: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 优先级优先级000000735612407356124000000371256043712560400000517430625174306200000153074261530742600000000002603471526034715000000000000421653704216537第53页，此课件共81页哦第三节第三节分形分形分形的概念分形的概念三分康托三分康托(Cantor)(Cantor)集集设设E E0

展开阅读全文