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

资源描述

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

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

2、,这样每个结点可由八个字这样每个结点可由八个字段组成段组成,前六个字段描述矩形带段前六个字段描述矩形带段,后二个后二个是指向两个子结点的指针是指向两个子结点的指针,即矩形带段的即矩形带段的起点是起点是(x(xb b,y,yb b),),终点是终点是(x(xe e,y,ye e)。相对从起。相对从起点到终点的连线点到终点的连线,矩形有两边与之平行矩形有两边与之平行,两两边与之垂直边与之垂直,平行两边与之距离分别为平行两边与之距离分别为w wl l和和w wr r。第三张，PPT共八十一页，创作于2022年6月第四张，PPT共八十一页，创作于2022年6月设设要要表表示示的的曲曲线线是是由由经经

3、过过适适当当选选取取已已确确定定的的一一组组离离散散点点P P0 0,P,P1 1,P,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

4、0至至P Pk k和和P Pk k至至P Pn n这这两两组组点点分分别别做做与与步步1 1中中相相同同的的构构造造矩矩形形带带段段及及对对应应结结点点的的操操作作,产生的两个结点产生的两个结点,分别是根的左右子结点。分别是根的左右子结点。3.3.反复执行上述操作反复执行上述操作,直到所产生结点的直到所产生结点的w=ww=wl l+w wr r w w0 0。这样的结点是叶结点。这样的结点是叶结点。第五张，PPT共八十一页，创作于2022年6月设表示曲线有设表示曲线有5 5个点个点(3,7)(9,12),(15,4),(18,5),(20,7),(3,7)(9,12),(15,4),(18,

5、5),(20,7),取分辨率取分辨率w w0 0=1,=1,则上述算法构造的带树则上述算法构造的带树第六张，PPT共八十一页，创作于2022年6月以不同的分辨率显示用带树表示的曲线以不同的分辨率显示用带树表示的曲线设给出允许的分辨率为设给出允许的分辨率为w*,表示曲线的表示曲线的带树的分辨率为带树的分辨率为w w0 0,并设并设w w0 0w*,则显示算法可则显示算法可简略描述如下简略描述如下:从根结点开始从根结点开始,若当前正考查结点的若当前正考查结点的W=wW=wl l+w+wr r w*,则显示该结点对应的矩形带段则显示该结点对应的矩形带段;若不然若不然,即即W W w*则转去分别考

6、查该结点的左则转去分别考查该结点的左右两个子结点右两个子结点,对子结点做同样的处理。左右对子结点做同样的处理。左右子结点都被显示的结点就认为是被显示了子结点都被显示的结点就认为是被显示了,按按此看法此看法,显示带树表示的曲线就是显示带树的显示带树表示的曲线就是显示带树的结点。结点。第七张，PPT共八十一页，创作于2022年6月带树表示的曲线求交带树表示的曲线求交两两个个矩矩形形带带段段S S1 1和和S S2 2的的位位置置关关系系有有如如下下三种三种:(1)(1)不相交。不相交。(2)(2)良良性性相相交交,即即S S1 1的的与与起起点点至至终终点点连连线线平平行行的的两两条条边边都都

7、与与S S2 2相相交交,S,S2 2的的与与起起点点至至终终点点连连线线平行的两条边也都与平行的两条边也都与S S1 1相交。相交。(3)(3)可能性相交可能性相交,这时不是良性相交这时不是良性相交,但也不但也不是不相交。是不相交。第八张，PPT共八十一页，创作于2022年6月第九张，PPT共八十一页，创作于2022年6月设设表表示示要要求求交交两两曲曲线线的的带带树树己己构构造造得得足足够够精精确确,即即在在树树叶叶一一层层,来来自自不不同同带带树树的的矩矩形形带带段段或或是是不不相相交交或或是是良良性性相相交交,而而没没有有可可能能性性相相交出现。交出现。两两树树T1T1和和T2T2表

8、表示示的的两两条条曲曲线线是是否否相相交交的的算算法法,可以简略叙述如下可以简略叙述如下:若若T T1 1和和T T2 2对对应应的的矩矩形形带带段段互互不不相相交交,那那么么它们代表的曲线不相交它们代表的曲线不相交;若若T T1 1和和T T2 2对应的矩形带段良性相交对应的矩形带段良性相交,那么那么它们代表的曲线相交它们代表的曲线相交;若若T T1 1和和T T2 2对应的矩形带段可能性相交对应的矩形带段可能性相交,且且T T1 1的面积大于或等的面积大于或等T T2 2的面积的面积,那么分别执行那么分别执行T T2 2与与T T1 1的左右两个儿子结点的相交性检查。的左右两个儿子结点的相

9、交性检查。第十张，PPT共八十一页，创作于2022年6月若若T T1 1的面积小于的面积小于T T2 2的面积的面积,则把它们位则把它们位置对换一下再如上进行两个检查。若两个置对换一下再如上进行两个检查。若两个检查的结果都是不相交检查的结果都是不相交,则认为所表示曲线则认为所表示曲线不相交不相交;若两个检查中有一个是良性相交若两个检查中有一个是良性相交,则认为所表示曲线相交则认为所表示曲线相交;若不是上述两情形若不是上述两情形,即出现可能性相交即出现可能性相交,则对可能性相交的两个则对可能性相交的两个矩形带段中面积较大者矩形带段中面积较大者,取其对应结点的两取其对应结点的两个子结点个子结点,

10、如此进行可直到树叶那一层。如此进行可直到树叶那一层。实践表明用带树方法表示曲线对提高实践表明用带树方法表示曲线对提高计算效率是有帮助的。另外两个带树对计算效率是有帮助的。另外两个带树对并、并、交等运算是封闭的交等运算是封闭的,与用象素阵列来表示图与用象素阵列来表示图形的方法比较空间需求也算是节省的。形的方法比较空间需求也算是节省的。第十一张，PPT共八十一页，创作于2022年6月平面图形的四叉树表示方法平面图形的四叉树表示方法假定一个平面假定一个平面图图形是形是黑白黑白的二的二值图值图形形,即即组组成成图图形象素形象素阵阵列的列的仅仅有黑色象素有黑色象素值值1,1,白白色象素色象素值值0,0

11、,设设表表现图现图形的象素形的象素阵阵列由列由2 2n n22n n个象素个象素组组成。成。表示表示该图该图形的四叉形的四叉树结树结构可以如下形成构可以如下形成:图图形形显显然包括然包括2 2n n22n n的正方形中，的正方形中，这这个正方个正方形是四叉形是四叉树树的根的根结结点。点。若若图图形整个地占据形整个地占据这这个正方形个正方形,则图则图形形就用就用该该正方形表示正方形表示,否否则则将将该该正方形均分正方形均分为为四四个小正方形，每个小正方形个小正方形，每个小正方形边长为边长为原正方形原正方形边长边长的一半的一半.它它们们是根是根结结点的四个子点的四个子结结点点,可可编编号号为为0,

12、1,2,30,1,2,3。第十二张，PPT共八十一页，创作于2022年6月再考再考查查每个小正方形每个小正方形,若整个被若整个被图图形占形占据据,则标记则标记相相应结应结点点为为1,1,可称可称为为黑黑结结点点。若。若整个与整个与图图形不相交形不相交,则标记则标记相相应结应结点点为为0 0，可称可称为为白白结结点点。若不是上述两情形，即与若不是上述两情形，即与图图形部分相交，形部分相交，则则称相称相应结应结点是点是灰灰结结点点并将其一分并将其一分为为四。四。当再分生成小正方形当再分生成小正方形边长边长达到一个达到一个象素象素单单位位时时，再分，再分终终止，此止，此时时一般一般应应将仍是灰将仍

13、是灰结结点的改点的改为为黑黑结结点，如此形成了平面点，如此形成了平面图图形的四叉形的四叉树树表示表示第十三张，PPT共八十一页，创作于2022年6月第十四张，PPT共八十一页，创作于2022年6月四叉树的存储结构，即四叉树的存储结构，即规则方式、线规则方式、线性方式和一对四方式性方式和一对四方式，相应的四叉树也就，相应的四叉树也就称为规则四叉树、线性四叉树和一对四式称为规则四叉树、线性四叉树和一对四式四叉树。四叉树。规则四叉树是用五个字段的记录来表规则四叉树是用五个字段的记录来表示树中的每个结点，其中一个用来描述结示树中的每个结点，其中一个用来描述结点的特性，即是灰、黑、白三类结点中的点的

14、特性，即是灰、黑、白三类结点中的哪一种。其余四个用于存放指向四个子结哪一种。其余四个用于存放指向四个子结点的指针。点的指针。线性四叉树以某一预先确定的次序遍线性四叉树以某一预先确定的次序遍历四叉树形成一个线性表结构历四叉树形成一个线性表结构。RAabcdBCDefghRAabcdBCDefgh。其中。其中R R表示根，字表示根，字母右上角加母右上角加表示是灰结点。表示是灰结点。第十五张，PPT共八十一页，创作于2022年6月一对四式四叉树的存储结构一对四式四叉树的存储结构每个结每个结点有五个字段，其中四个字段用来描述该点有五个字段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点

15、存结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的指针。放指向子结点记录存放处的指针。四个子四个子结点对应的记录是依次连续存放的。结点对应的记录是依次连续存放的。第十六张，PPT共八十一页，创作于2022年6月为节省存贮空间为节省存贮空间,有两个途径可以采取。一个有两个途径可以采取。一个是增加计算量；另一个途径是在记录中再增加一个是增加计算量；另一个途径是在记录中再增加一个字节字节,一分为四一分为四,每个子结点对应每个子结点对应2 2位位,表示它的子表示它的子结点在指针指向区域中的偏移。结点在指针指向区域中的偏移。第十七张，PPT共八十一页，创作于2022年6月第二节第二节三维

16、几何模型三维几何模型几何元素几何元素形体的模型主要指的就是包含图形信形体的模型主要指的就是包含图形信息所形成的模型。息所形成的模型。形体本身的构造有一定的层次性，低形体本身的构造有一定的层次性，低层部分组合构成上一层部分，而上一层部层部分组合构成上一层部分，而上一层部分组合又可以构成更高一层的部分，依此分组合又可以构成更高一层的部分，依此类推可形成多层结构。其中，每一层中的类推可形成多层结构。其中，每一层中的部分，我们把它有称为几何元素。部分，我们把它有称为几何元素。第十八张，PPT共八十一页，创作于2022年6月点点它它是是0 0维维几几何何元元素素，有有端端点点、交交点点、切切点、孤

17、立点等形式。点、孤立点等形式。曲曲线线、曲曲面面的的应应用用中中会会涉涉及及到到三三种种类类型型的点：的点：型值点型值点相应曲线、曲面必然经过的点。相应曲线、曲面必然经过的点。控控制制点点相相应应曲曲线线、曲曲面面不不一一定定经经过过的的点点，仅仅用于确定位置和形状。用于确定位置和形状。插插值值点点在在型型值值点点之之间间插插入入的的一一系系列列点点，用用于于提高曲线曲面的输出精度。提高曲线曲面的输出精度。第十九张，PPT共八十一页，创作于2022年6月不同的空间中点的表示方式不同的空间中点的表示方式一维空间中用一元组一维空间中用一元组tt表示；表示；二维空间中用二元组二维空间中用二

18、元组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)表示；表示；点是几何造型中的最基本的元素，曲线、点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述。曲面和其它形体都可以用有序的点集描述。用计算机存储、管理、输出形体的实质用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。就是对点集及其连接关系的处理。第二十张，PPT共八十一页，创作于2022年6月边边边边是是一一维维几几何何元元素素，是是两两个个邻邻面面（正正则则形形体体）

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

20、针方向排序。而把确定面中内孔或凸台边界排序。而把确定面中内孔或凸台边界的环称之为的环称之为内环内环，其边相应外环排序方向相反，其边相应外环排序方向相反，通常按通常按顺时针顺时针方向排序。方向排序。第二十一张，PPT共八十一页，创作于2022年6月面面面面是是二二维维元元素素，是是形形体体上上一一个个有有限限、非非零零的的区区域域，它它由由一一个个外外环环和和若若干干个个内内环环所所界界定定。面面有有方方向向性性，一一般般用用其其外外法法向向量量作作为为该该面面的的正正向向。若若一一个个面面的的外外法法向向量量向向外外，此此面面为为正正；否否则，为反向面。则，为反向面。体体体是三维几何元素，

21、由封闭表面围成的体是三维几何元素，由封闭表面围成的空间，它是欧氏空间空间，它是欧氏空间R R3 3中非空、有界的封闭子中非空、有界的封闭子集，其边界是有限面的并集。在实际应用中，集，其边界是有限面的并集。在实际应用中，要求形体是正则形体，即形体上任意一点的足要求形体是正则形体，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。够小的邻域在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。存在不满足上述要求的形体称为非正则形体。存在悬面、悬边的形体是非正则形体。悬面、悬边的形体是非正则形体。第二十二张，PPT共八十一页，创作于2022年6月体素体素体体素素是是可可以以用

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

23、体的层次结构点点边边环环面面外壳外壳形体。形体。第二十三张，PPT共八十一页，创作于2022年6月在几何造型中最基本的几何元素是在几何造型中最基本的几何元素是点（点（V V）、边）、边(E)(E)、面、面(F),(F),这三种元素一这三种元素一共有九种连接关系共有九种连接关系第二十四张，PPT共八十一页，创作于2022年6月线框、表面及实体表示线框、表面及实体表示常用的多面体表示法是三表表示法，即采常用的多面体表示法是三表表示法，即采用三个表用三个表:顶点表顶点表,用来存放多面体各顶点的用来存放多面体各顶点的坐标坐标;边表边表,指出哪两个顶点之间有多面体的指出哪两个顶点之间有多面体的边

24、；边；面表面表，指出哪些边围成了多面体的表面。，指出哪些边围成了多面体的表面。任意多面体容易得到它的三表表示任意多面体容易得到它的三表表示,但任但任意三张表却不一定表示了一个真实的多面体。意三张表却不一定表示了一个真实的多面体。这里必须满足的条件至少有以下几项这里必须满足的条件至少有以下几项:顶点表顶点表中的每个顶点至少是中的每个顶点至少是三边三边的端点的端点;边表中的每边表中的每条边是条边是两个多边形两个多边形面的公共边；每个多边形面的公共边；每个多边形面是封闭的等等。面是封闭的等等。第二十五张，PPT共八十一页，创作于2022年6月第二十六张，PPT共八十一页，创作于2022年6月x xy

25、 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顶点表顶点表面表面表边表边表第二十七张，PPT共八十一页，创作于2022年6月空间正二空间正二十面体十面体V V2020,的三表表示。的三表表示

26、。引人一个引人一个正数正数0,0,它它满满足二次方程足二次方程2 2-1=0,-1=0,因此因此=1/2(1+=1/2(1+)1.618034)1.618034。XYZ第二十八张，PPT共八十一页，创作于2022年6月编号编号xyz编号编号xyz110123-101213-001-12431-10-1 014-0-13201-2110330-1221-0340-1-第二十九张，PPT共八十一页，创作于2022年6月边边编编号号边边编编号号1 11111，131316162121，32322 21212，141417172222，33333 32121，232318182222，34344

27、42222，242419192323，31315 53131，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

28、，313130303434，1414第三十张，PPT共八十一页，创作于2022年6月面编号面编号面编号面编号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，3

29、03018181616，3 3，20209 92727，5 5，232319191717，4 4，212110102424，5 5，282820202222，4 4，1818第三十一张，PPT共八十一页，创作于2022年6月第三十二张，PPT共八十一页，创作于2022年6月三维实体表示方法三维实体表示方法从用户角度来看，形体以特征表示和构从用户角度来看，形体以特征表示和构造的实体几何表示比较适宜；从计算机对形造的实体几何表示比较适宜；从计算机对形体的存储管理和操作运算角度看，以边界表体的存储管理和操作运算角度看，以边界表示最为实用。示最为实用。1 1 构造的实体几何法构造的实体几何法构造的

30、构造的实实体几何体几何(CSG:Constructive(CSG:Constructive Solid Geometry)Solid Geometry)法是指任意复法是指任意复杂杂的形体都的形体都可以用可以用简单简单形体形体(体素体素)的的组组合来表示。合来表示。形体的形体的CSGCSG表示可看成是一棵有序的二表示可看成是一棵有序的二叉叉树树，称，称为为CSGCSG树树。其。其终终端端结结点或是体素，点或是体素，如如长长方体、方体、圆锥圆锥等；或是等；或是刚刚体运体运动动的的变换变换参参数，如平移参数数，如平移参数T Tx x等；非等；非终终端端结结点或是正点或是正则则的集合运算，一般有交、并

31、、差运算；的集合运算，一般有交、并、差运算；第三十三张，PPT共八十一页，创作于2022年6月或是刚体的几何变换，如平移、旋转等。或是刚体的几何变换，如平移、旋转等。采用采用BNFBNF范式可定义范式可定义CSGCSG树若下：树若下：:=:=|CSGCSG树树是是无无二二义义性性的的，但但不不是是唯唯一一的的，其其定定义义域域取取决决于于所所用用体体素素以以及及所所允允许许的的几几何何变变换换和正则集合运算算子。和正则集合运算算子。CSGCSG表示的优点：表示的优点：数数据据结结构构比比较较简简单单，数数据据量量比比较较小小，内内部部数数据的管理比较容易；据的管理比较容易；第三十四张，PPT共

32、八十一页，创作于2022年6月每个每个CSGCSG表示都和一个实际的有效形体所对应；表示都和一个实际的有效形体所对应；CSGCSG表表示示可可方方便便地地转转换换成成BrepBrep表表示示，从从而而可可支支持持广泛的应用；广泛的应用；比较容易修改比较容易修改CSGCSG表示形体的形状。表示形体的形状。CSGCSG表示的缺点：表示的缺点：产产生生和和修修改改形形体体的的操操作作种种类类有有限限，基基于于集集合合运运算算对形体的局部操作不易实现；对形体的局部操作不易实现；由于形体的边界几何元素由于形体的边界几何元素(点、边、面点、边、面)是隐含是隐含地表示在地表示在CSGCSG中，故显示与绘制中

33、，故显示与绘制CSGCSG表示的形体表示的形体需要较长的时间。需要较长的时间。第三十五张，PPT共八十一页，创作于2022年6月并第三十六张，PPT共八十一页，创作于2022年6月2 2 特征表示特征表示特特征征表表示示是是从从应应用用层层来来定定义义形形体体，因因而而可可以以较较好好地地表表达达设设计计者者的的意意图图，为为制制造造和和检检验验产产品品和和形形体体提提供供技技术术依依据据和和管管理理信信息息。从从功功能能上看可分为形状、精度、材料和技术特征。上看可分为形状、精度、材料和技术特征。形状特征：体素、孔、槽、键等形状特征：体素、孔、槽、键等精度特征：形位公差、表面粗糙度等；精度

34、特征：形位公差、表面粗糙度等；材料特征：材料硬度、热处理方法等；材料特征：材料硬度、热处理方法等；技术特征：形体的性能参数和特征等。技术特征：形体的性能参数和特征等。形状特征单元是一个有形的几何实体，是一形状特征单元是一个有形的几何实体，是一组可加工表面的集合。如采用长、宽、高三组可加工表面的集合。如采用长、宽、高三尺寸表示的长方体；采用底面半径及高度表尺寸表示的长方体；采用底面半径及高度表示的圆柱体均是可选用的形状特征单元。示的圆柱体均是可选用的形状特征单元。第三十七张，PPT共八十一页，创作于2022年6月形状特征单元的形状特征单元的BNFBNF范式可定义如下：范式可定义如下：=|;：=长

36、、边、点及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。为基础的各种几何运算和操作。形体的边界表示就是用面、环、边、点来形体的边界表示就是用面、环、边、点来定义形体的位置和形状。例如，一个长方体由定义形体的位置和形状。例如，一个长方体由六个面围成，对应有六个环，每个环由四条边六个面围成，对应有六个环，每个环由四条边界定义，每条边又由两个端点定义。而圆柱体界定义，每条边又由两个端点定义。而圆柱体则由上顶面、下底面和圆柱面所围成，对应有则由上顶面、下底面和圆柱面所围成，对应有上顶面圆环、下底面圆环。上顶面圆环、下底面圆环。第四十张，PPT共八十一页，创作于2022年6月Brep

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

38、对应一个有效形体，即需表示并不一定对应一个有效形体，即需要有专门的程序来保证要有专门的程序来保证BrepBrep表示形体的有效表示形体的有效性、正则性等。性、正则性等。第四十一张，PPT共八十一页，创作于2022年6月八叉树八叉树假设要表示的形体假设要表示的形体V V可以放在一个充分大可以放在一个充分大的正立方体的正立方体C C内内,C,C的边长为的边长为2 2n n,形体形体V C,V C,它它的八又树表示可以递归定义为的八又树表示可以递归定义为:八叉树每个结点与八叉树每个结点与C C的一个子立方体对应，的一个子立方体对应，树根就和树根就和C C本身对应。如果本身对应。如果V=C,V=C,

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

40、十二张，PPT共八十一页，创作于2022年6月这时对它与这时对它与V V之交作一定的之交作一定的“舍入舍入”,使体素或认为是空白使体素或认为是空白,或认为是被或认为是被V V占占据的。这里所谓的体素据的。这里所谓的体素,就是指被分割后就是指被分割后得到的小立方体。得到的小立方体。通常称对应立方体被形体通常称对应立方体被形体V V完全占据完全占据的结点为的结点为黑结点黑结点,完全不占据的为完全不占据的为白结点白结点,部分被占据的为部分被占据的为灰结点灰结点。存贮结构存贮结构,有常规的、线性的、一有常规的、线性的、一对八式的八叉树等等。对八式的八叉树等等。第四十三张，PPT共八十一页，创作于20

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

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

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

44、产生原来不存在的孔洞，而不这样规定孔洞，而不这样规定,例如简单地规定部分被占例如简单地规定部分被占据的体素都为白据的体素都为白,则可能在做则可能在做45450 0左右旋转时原来左右旋转时原来黑立方体变换为部分占据若干体素而被指定为白黑立方体变换为部分占据若干体素而被指定为白,在变换后形体中间出现断裂。在变换后形体中间出现断裂。第四十五张，PPT共八十一页，创作于2022年6月第四十六张，PPT共八十一页，创作于2022年6月第四十七张，PPT共八十一页，创作于2022年6月设己采取了上述两项措施设己采取了上述两项措施,已知形体变换已知形体变换前的八叉树表示前的八叉树表示T T1 1,己计算出

45、己计算出要要做做的的复复合合变变换换R,R,要要确确定定变变换换后后形形体体的的八叉树表示八叉树表示T T2 2,可以写出如下的算法框架：可以写出如下的算法框架：1.1.遍遍历历形形体体原原来来的的八八叉叉树树T T1 1,对对遇遇到到的的每每个个黑黑结点结点,做下述步做下述步2 2。2.2.对对遇遇到到黑黑结结点点对对应应的的正正立立方方体体做做相相应应变变换换,得得它它新新的的一一般般来来说说是是斜斜置置的的新新位位置置。若若这这位位置置已已超超出出定定义义八八叉叉树树的的充充分分大大正正立立方方体体C C之之外外,报告出错报告出错;否则执行下述的步否则执行下述的步3 3。3.3.从要计

46、算求出的目标树从要计算求出的目标树T T2 2的根开始的根开始,检查检查2 2中确定的处于新位置立方体与中确定的处于新位置立方体与T T2 2中结点对应中结点对应的直立的正立方体是否相交的直立的正立方体是否相交,分以下三种情况分以下三种情况进行处理进行处理:第四十八张，PPT共八十一页，创作于2022年6月(1)1)不不相相交交,说说明明正正考考查查直直立立正正立立方方体体未未被被占占据据,可保持为白结点可保持为白结点,不做处理。不做处理。(2)(2)直直立立的的正正立立方方体体整整个个被被占占据据,即即它它在在变变换换后后斜置斜置立方体内立方体内,置对应结点为黑结点。置对应结点为黑结点。

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

48、处理相同,使得使得操作可以并行进行。操作可以并行进行。第四十九张，PPT共八十一页，创作于2022年6月线性八叉树线性八叉树在对立方体做八等分时在对立方体做八等分时,按一致的方式按一致的方式,对分出的子立方体进行编号。若再分共进对分出的子立方体进行编号。若再分共进行行n n层，则每个结点可以用层，则每个结点可以用n n位的八进制数位的八进制数的数串的数串来表示来表示,数串从左至右数串从左至右,第一位对应第一位对应第一次划分，第二位对应第二位划分，依第一次划分，第二位对应第二位划分，依此类推。据此整个八叉树就可以根据对其此类推。据此整个八叉树就可以根据对其做深度第一遍历而依次列出的黑结点的编做

49、深度第一遍历而依次列出的黑结点的编号序列来表示号序列来表示。前前图图所所示示三三维维形形体体,其其线线性性八八叉叉树树表表示示是是:0 x,10,12,13,14,2x,4x,6x,7x 0 x,10,12,13,14,2x,4x,6x,7x 第五十张，PPT共八十一页，创作于2022年6月求并运算求并运算 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

50、 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 第五十一张，PPT共八十一页，创作于2022年6月八

展开阅读全文