《形体的表示及其数据结构.ppt》由会员分享，可在线阅读，更多相关《形体的表示及其数据结构.ppt（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章第六章 形体的表示及其数据结构形体的表示及其数据结构 与空间任意形体有关的信息可以分为与空间任意形体有关的信息可以分为图形信息图形信息和和非图形信息非图形信息两类。图形信息指两类。图形信息指构成它们的点、线、面的位置构成它们的点、线、面的位置,相互关系及相互关系及大小等大小等;非图形信息指形体的颜色、亮度、非图形信息指形体的颜色、亮度、质量、体积等一些性质。质量、体积等一些性质。形体的图形信息又可以分为形体的图形信息又可以分为几何信息几何信息和和拓扑信息拓扑信息两类。几何信息指形体在空间两类。几何信息指形体在空间的位置和大小的位置和大小,拓扑信息指组成形体各部分拓扑信息指组成形体各部分的
2、数目及相互间的连接关系。的数目及相互间的连接关系。第一节第一节 二维形体的表示二维形体的表示 二维图形的边界表示二维图形的边界表示 折线法和带树法折线法和带树法 折线法就是用多段线段形成的折线去折线法就是用多段线段形成的折线去逼近曲线逼近曲线 折线表示曲线应该解决的关键问题是折线表示曲线应该解决的关键问题是:如何恰当地确定曲线上一系列点如何恰当地确定曲线上一系列点,使之在使之在某些判定准则下达到最优。某些判定准则下达到最优。设已经用某种方法取得了曲线上足够设已经用某种方法取得了曲线上足够多的点多的点,使连接那些点的折线可以很好地表使连接那些点的折线可以很好地表达该曲线。问题是达该曲线。问题是:
3、怎样在其中选择怎样在其中选择尽可能尽可能少少的点的点,使选出的点仍能较好地表达原曲线。使选出的点仍能较好地表达原曲线。具体地说具体地说,使选出的点满足以下二条准则使选出的点满足以下二条准则:(1)(1)共线性共线性 设设P Pj j和和P Pk k是选出的两点是选出的两点,则在则在P Pj j到到P Pk k之间所有点到直线之间所有点到直线P Pj jP Pk k的垂直距离的垂直距离,应小于某个预先给定的限制阈值应小于某个预先给定的限制阈值0 0,这里这里0 000,是一个可以由应用问题需要而确定是一个可以由应用问题需要而确定的的很小的正数很小的正数。若不小于。若不小于0 0,应寻找距离应寻找
4、距离为最大之点并考虑是否可以在该点将这一为最大之点并考虑是否可以在该点将这一段段分裂分裂为两段。为两段。(2)(2)设选出的连续三点是设选出的连续三点是P Pi i,P,Pj j,P,Pk k,则向量则向量P Pi iP Pj j与与P Pj jP Pk k的夹角的夹角的绝对值的绝对值,应大于某个应大于某个预先给定的限制阈值预先给定的限制阈值0 0。,若小于若小于0 0,则则P Pj j不应选取而应考虑是否能将不应选取而应考虑是否能将P Pi i至至P Pj j和和P Pj j至至P Pk k两段合并。两段合并。设设有有曲曲线线上上n+1n+1个个点点的的坐坐标标序序列列,各各点点依依次次编编
5、号号为为0,1,2,n;0,1,2,n;为为使使删删去去各各点点距距留留下下前前后后二二点点所所形形成成直直线线的的距距离离不不很很大大而而预预先先给给定定的的阈阈值值0 0;为为使使选选出出连连续续三三点点所所成成向向量量夹夹角角不不很很小小而而预预先先给给定定的的阈阈值值0 0;参参数数k k0 0表表示示每每次次向向前前检检查查k k0 0个点。个点。1.1.初初始始化化 i0,j0,kki0,j0,kk0 0,输输出出点点编编号号0,s10,s1。ii记记最最近近己己选选之之点点,初初始始起起点点0 0为为必必选选,j,j记记待待检检查查之之点点,算算法法中中保保持持ij,ij,待待检
6、检查查线是点线是点j j到到k k的直线。的直线。2.2.共共线线性性检检查查检检查查点点j j到到k k间间各各点点共共线线性性。若若不不能能通通过过,距距离离直直线线P Pj jP Pk k最最远远的的点点是是m,m,则则kmkm返返回回本本步步开开头头。否否则则继继续续。本本步步必必能能通通过过,因最坏在因最坏在k=j+1k=j+1时能通过。时能通过。3.3.暂暂定定j j前前后后两两线线方方向向L2L2点点j j到到k k的的方方向向,若若i=ji=j则则L1L2,L1L2,到到6;6;否否则则继继续续。L2L2是是暂暂定定找找到到从从j j向向后后的的新新线线方方向向,L1,L1是是
7、前前次次找找到到原原有有线线方向。方向。4.4.向向量量夹夹角角检检查查检检查查P Pi i,P,Pj j,P,Pk k三三点点形形成成二二向向量量L1L1和和L2L2的的夹夹角角的的绝绝对对值值,若若可可以以通通过过即即应应发发生生合合并并,做做jiji然然后后返返2,2,否否则则继继续续。本本步步检检查查通通过过即即点点j j不不能能选选取取,而而要要检查原检查原i i到到k k的直线。的直线。5.5.找找到到一一个个选选取取点点ij,L1ij,L1点点j j到到k k的的方向方向,输出点编号输出点编号j,ss+1j,ss+1。6.6.准准 备备 下下 次次 jk,kk+kjk,kk+k0
8、 0,若若 knkn则则kn,kn,若若jn-1jn-1则返则返2,2,否则继续。否则继续。7.7.最后取点输出点编号最后取点输出点编号n,n,算法结束。算法结束。P0P1P2P3P4P5P6i0,j0,kki0,j0,kk0 0(3)PjPk即即P0P3,若通过；若通过；j j k,k k+kk,k k+k0,0,PjPk即即P3P6带树法带树法 带树是一棵二叉树带树是一棵二叉树,树的每个结点对应树的每个结点对应一个矩形带段一个矩形带段,这样每个结点可由八个字这样每个结点可由八个字段组成段组成,前六个字段描述矩形带段前六个字段描述矩形带段,后二个后二个是指向两个子结点的指针是指向两个子结点的
9、指针,即矩形带段的即矩形带段的起点是起点是(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 n序序列列给给出出,则则生生成成表表示示曲曲线线的的分分辨辨率率为为w w0 0的的带带树树的的算算法法,可可简简略略描述如下描述如下:1.1.找找出出由由起
10、起点点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 1中中相相同同的的构构造造矩矩形形带带段段及及对对应应结结点点的的操操作作,产生的两个结点产生的两个结点,分别是根的左右子结点。分别是根的左右子结点。3.3.反复
11、执行上述操作反复执行上述操作,直到所产生结点的直到所产生结点的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,则上述算法构造的带树则上述算法构造的带树 以不同的分辨率显示用带树表示的曲线以不同的分辨率显示用带树表示的曲线 设给出允许的分辨率为设给出允许的分辨率为w*,表示曲线的表示曲线的带树的分辨率为带树的分辨率为w w0 0,并设并设w w0 0
12、w*,则显示算法可则显示算法可简略描述如下简略描述如下:从根结点开始从根结点开始,若当前正考查结点的若当前正考查结点的W=wW=wl l+w+wr r w*,则显示该结点对应的矩形带段则显示该结点对应的矩形带段;若不然若不然,即即W W w*则转去分别考查该结点的左则转去分别考查该结点的左右两个子结点右两个子结点,对子结点做同样的处理。左右对子结点做同样的处理。左右子结点都被显示的结点就认为是被显示了子结点都被显示的结点就认为是被显示了,按按此看法此看法,显示带树表示的曲线就是显示带树的显示带树表示的曲线就是显示带树的结点。结点。带树表示的曲线求交带树表示的曲线求交 两两个个矩矩形形带带段段S
13、 S1 1和和S S2 2的的位位置置关关系系有有如如下下三种三种:(1)(1)不相交。不相交。(2)(2)良良性性相相交交,即即S S1 1的的与与起起点点至至终终点点连连线线平平行行的的两两条条边边都都与与S S2 2相相交交,S,S2 2的的与与起起点点至至终终点点连连线平行的两条边也都与线平行的两条边也都与S S1 1相交。相交。(3)(3)可能性相交可能性相交,这时不是良性相交这时不是良性相交,但也不但也不是不相交。是不相交。设设表表示示要要求求交交两两曲曲线线的的带带树树己己构构造造得得足足够够精精确确,即即在在树树叶叶一一层层,来来自自不不同同带带树树的的矩矩形形带带段段或或是是
14、不不相相交交或或是是良良性性相相交交,而而没没有有可可能能性性相相交出现。交出现。两两树树T1T1和和T2T2表表示示的的两两条条曲曲线线是是否否相相交交的的算算法法,可以简略叙述如下可以简略叙述如下:若若T T1 1和和T T2 2对对应应的的矩矩形形带带段段互互不不相相交交,那那么么它们代表的曲线不相交它们代表的曲线不相交;若若T T1 1和和T T2 2对应的矩形带段良性相交对应的矩形带段良性相交,那么那么它们代表的曲线相交它们代表的曲线相交;若若T T1 1和和T T2 2对应的矩形带段可能性相交对应的矩形带段可能性相交,且且T T1 1的面积大于或等的面积大于或等T T2 2的面积的
15、面积,那么分别执行那么分别执行T T2 2与与T T1 1的左右两个儿子结点的相交性检查。的左右两个儿子结点的相交性检查。若若T T1 1的面积小于的面积小于T T2 2的面积的面积,则把它们位则把它们位置对换一下再如上进行两个检查。若两个置对换一下再如上进行两个检查。若两个检查的结果都是不相交检查的结果都是不相交,则认为所表示曲线则认为所表示曲线不相交不相交;若两个检查中有一个是良性相交若两个检查中有一个是良性相交,则认为所表示曲线相交则认为所表示曲线相交;若不是上述两情形若不是上述两情形,即出现可能性相交即出现可能性相交,则对可能性相交的两个则对可能性相交的两个矩形带段中面积较大者矩形带段
16、中面积较大者,取其对应结点的两取其对应结点的两个子结点个子结点,如此进行可直到树叶那一层。如此进行可直到树叶那一层。实践表明用带树方法表示曲线对提高实践表明用带树方法表示曲线对提高计算效率是有帮助的。另外两个带树对计算效率是有帮助的。另外两个带树对并、并、交等运算是封闭的交等运算是封闭的,与用象素阵列来表示图与用象素阵列来表示图形的方法比较空间需求也算是节省的。形的方法比较空间需求也算是节省的。平面图形的四叉树表示方法平面图形的四叉树表示方法 假定一个平面假定一个平面图图形是形是黑白黑白的二的二值图值图形形,即即组组成成图图形象素形象素阵阵列的列的仅仅有黑色象素有黑色象素值值1,1,白色白色象
17、素象素值值0,0,设设表表现图现图形的象素形的象素阵阵列由列由2 2n n22n n个个象素象素组组成。成。表示表示该图该图形的四叉形的四叉树结树结构可以如下形成构可以如下形成:图图形形显显然包括然包括2 2n n22n n的正方形中，的正方形中，这这个正方个正方形是四叉形是四叉树树的根的根结结点。点。若若图图形整个地占据形整个地占据这这个正方形个正方形,则图则图形就形就用用该该正方形表示正方形表示,否否则则将将该该正方形均分正方形均分为为四个四个小正方形，每个小正方形小正方形，每个小正方形边长为边长为原正方形原正方形边边长长的一半的一半.它它们们是根是根结结点的四个子点的四个子结结点点,可可
18、编编号号为为0,1,2,30,1,2,3。再考再考查查每个小正方形每个小正方形,若整个被若整个被图图形占据形占据,则标记则标记相相应结应结点点为为1,1,可称可称为为黑黑结结点点。若整个与。若整个与图图形不相交形不相交,则标记则标记相相应结应结点点为为0 0，可称，可称为为白白结结点点。若不是上述两情形，即与若不是上述两情形，即与图图形部分形部分相交，相交，则则称相称相应结应结点是点是灰灰结结点点并将其一并将其一分分为为四。当再分生成小正方形四。当再分生成小正方形边长边长达到达到一个一个象素象素单单位位时时，再分，再分终终止，此止，此时时一般一般应应将仍是灰将仍是灰结结点的改点的改为为黑黑结结
19、点，如此形点，如此形成了平面成了平面图图形的四叉形的四叉树树表示表示 四叉树的存储结构，即四叉树的存储结构，即规则方式、线规则方式、线性方式和一对四方式性方式和一对四方式，相应的四叉树也就，相应的四叉树也就称为规则四叉树、线性四叉树和一对四式称为规则四叉树、线性四叉树和一对四式四叉树。四叉树。规则四叉树是用五个字段的记录来表规则四叉树是用五个字段的记录来表示树中的每个结点，其中一个用来描述结示树中的每个结点，其中一个用来描述结点的特性，即是灰、黑、白三类结点中的点的特性，即是灰、黑、白三类结点中的哪一种。其余四个用于存放指向四个子结哪一种。其余四个用于存放指向四个子结点的指针。点的指针。线性四
20、叉树以某一预先确定的次序遍线性四叉树以某一预先确定的次序遍历四叉树形成一个线性表结构历四叉树形成一个线性表结构 。RAabcdBCDefgh RAabcdBCDefgh。其中。其中R R表示根，字表示根，字母右上角加母右上角加表示是灰结点。表示是灰结点。一对四式四叉树的存储结构一对四式四叉树的存储结构 每个结每个结点有五个字段，其中四个字段用来描述该点有五个字段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点存结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的指针。放指向子结点记录存放处的指针。四个子四个子结点对应的记录是依次连续存放的。结点对应的记录是依次连续存放的。为节
21、省存贮空间为节省存贮空间,有两个途径可以采取。有两个途径可以采取。一个是增加计算量；另一个途径是在记录中一个是增加计算量；另一个途径是在记录中再增加一个字节再增加一个字节,一分为四一分为四,每个子结点对应每个子结点对应2 2位位,表示它的子结点在指针指向区域中的偏移。表示它的子结点在指针指向区域中的偏移。第二节第二节 三维几何模型三维几何模型 几何元素几何元素 形体的模型主要指的就是包含图形信形体的模型主要指的就是包含图形信息所形成的模型。息所形成的模型。形体本身的构造有一定的层次性，低形体本身的构造有一定的层次性，低层部分组合构成上一层部分，而上一层部层部分组合构成上一层部分，而上一层部分组
22、合又可以构成更高一层的部分，依此分组合又可以构成更高一层的部分，依此类推可形成多层结构。其中，每一层中的类推可形成多层结构。其中，每一层中的部分，我们把它有称为几何元素。部分，我们把它有称为几何元素。点点 它它是是0 0维维几几何何元元素素，有有端端点点、交交点点、切切点、孤立点等形式。点、孤立点等形式。曲曲线线、曲曲面面的的应应用用中中会会涉涉及及到到三三种种类类型型的点：的点：型值点型值点 相应曲线、曲面必然经过的点。相应曲线、曲面必然经过的点。控控制制点点 相相应应曲曲线线、曲曲面面不不一一定定经经过过的的点点，仅仅用于确定位置和形状。用于确定位置和形状。插插值值点点 在在型型值值点点之
23、之间间插插入入的的一一系系列列点点，用用于于提高曲线曲面的输出精度。提高曲线曲面的输出精度。不同的空间中点的表示方式不同的空间中点的表示方式 一维空间中用一元组一维空间中用一元组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)表示；表示；点是几何造型中的最基本的元素，曲线、点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述。曲面和其它形体都可以用有序的点集描述。用计算机存储、管理、输出形体的
24、实质用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。就是对点集及其连接关系的处理。边边:边边是是一一维维几几何何元元素素，是是两两个个邻邻面面（正正则则形形体体）或或多多个个邻邻面面（非非正正则则形形体体）的的交交界界。边边分分直直线线边边和和曲曲线线边边。直直线线边边由由起起点点和和终终点点两两端端点点确确定定；曲曲线线边边由由一一系系列列型型值值点点或或控控制制点点表表示示，也可以用显示、隐式方程描述。也可以用显示、隐式方程描述。环环:环是有序有向边（直线段或曲线段）组环是有序有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻成的面的封闭边界。环中的边不能相
25、交，相邻两条边共享一个端点。环有内外之分，确定面两条边共享一个端点。环有内外之分，确定面的最大外边界的环称之为的最大外边界的环称之为外环外环，通常其边按，通常其边按逆逆时针方向时针方向排序。而把确定面中内孔或凸台边界排序。而把确定面中内孔或凸台边界的环称之为的环称之为内环内环，其边相应外环排序方向相反，其边相应外环排序方向相反，通常按通常按顺时针顺时针方向排序。方向排序。面面:面面是是二二维维元元素素，是是形形体体上上一一个个有有限限、非非零零的的区区域域，它它由由一一个个外外环环和和若若干干个个内内环环所所界界定定。面面有有方方向向性性，一一般般用用其其外外法法向向量量作作为为该该面面的的正
26、正向向。若若一一个个面面的的外外法法向向量量向向外外，此此面面为为正正；否否则，为反向面。则，为反向面。体体:体是三维几何元素，由封闭表面围成的体是三维几何元素，由封闭表面围成的空间，它是欧氏空间空间，它是欧氏空间R R3 3中非空、有界的封闭子中非空、有界的封闭子集，其边界是有限面的并集。在实际应用中，集，其边界是有限面的并集。在实际应用中，要求形体是正则形体，即形体上任意一点的足要求形体是正则形体，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。够小的邻域在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。存在不满足上述要求的形体称为非正则形体。存在悬面、悬边的形
27、体是非正则形体。悬面、悬边的形体是非正则形体。体素体素:体体素素是是可可以以用用有有限限个个尺尺寸寸参参数数定定位位和和定定型型的体，常有下面三种定义形式。的体，常有下面三种定义形式。一组单元实体一组单元实体 长方体、圆柱体、圆锥体、球体。长方体、圆柱体、圆锥体、球体。扫扫描描体体 由由参参数数定定义义的的一一条条（一一组组）截截面面轮轮廓廓线线沿沿一一条条（一一组组）空空间间参参数数曲曲线线作作扫扫描描运运动动而而产生的形体。产生的形体。用代数半空间定义的形体用代数半空间定义的形体，在此半空间中点集，在此半空间中点集可定义可定义(x,y,z)|f(x,y,z)0(x,y,z)|f(x,y,z
28、)0此处的此处的f f应是不应是不可约的多项式。可约的多项式。形体的层次结构形体的层次结构 点点边边环环面面外壳外壳形体。形体。在几何造型中最基本的几何元素是在几何造型中最基本的几何元素是点（点（V V）、边）、边(E)(E)、面、面(F),(F),这三种元素一这三种元素一共有九种连接关系共有九种连接关系 线框、表面及实体表示线框、表面及实体表示 常用的多面体表示法是三表表示法，即采常用的多面体表示法是三表表示法，即采用三个表用三个表:顶点表顶点表,用来存放多面体各顶点的用来存放多面体各顶点的坐标坐标;边表边表,指出哪两个顶点之间有多面体的指出哪两个顶点之间有多面体的边；边；面表面表，指出哪些
29、边围成了多面体的表面。，指出哪些边围成了多面体的表面。任意多面体容易得到它的三表表示任意多面体容易得到它的三表表示,但任但任意三张表却不一定表示了一个真实的多面体。意三张表却不一定表示了一个真实的多面体。这里必须满足的条件至少有以下几项这里必须满足的条件至少有以下几项:顶点表顶点表中的每个顶点至少是中的每个顶点至少是三边三边的端点的端点;边表中的每边表中的每条边是条边是两个多边形两个多边形面的公共边；每个多边形面的公共边；每个多边形面是封闭的等等。面是封闭的等等。x xy yz z1 10 00 01 11 10 00 01 10 00 00 00 01 10 01 11 11 11 10 0
30、1 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顶点表顶点表面表面表边表边表 空间正二空间正二十面体十面体V V2020,的三表表示。的三表表示。引人一个引人一个正数正数0,0,它它满满足二次方足二次方程程2 2-1=0,1=0,因此因此=1/2(1+=1/2(1+)1.618034)1.618034。XYZ编号编号
31、xyz编号编号xyz110123-101213-001-12431-10-1 014-0-13201-2110330-1221-0340-1-边边 编编号号边边 编编号号1 11111，131316162121，32322 21212，141417172222，33333 32121，232318182222，34344 42222，242419192323，31315 53131，333320202323，32326 63232，343421212424，33337 71111，212122222424，34348 81111，222223233131，1111边边 编编号号边边 编编号号9
32、 91212，232324243131，121210101212，242425253232，131311111313，212126263232，141412121313，222227273333，111113131414，232328283333，121214141414，242429293434，131315152121，313130303434，1414面编号面编号面编号面编号1 17 7，2323，151511112525，6 6，29292 28 8，1717，272712123030，6 6，26263 31111，1616，252513131111，1 1，7 74 42929，2
33、828，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三维实体表示方法三维实体表示方法 从用户角度来看，形体以特征表示和从用户角度来看，形体以特征表示和构造的实体几何表示比较适宜；从计算机对构造的实体几何
34、表示比较适宜；从计算机对形体的存储管理和操作运算角度看，以边界形体的存储管理和操作运算角度看，以边界表示最为实用。表示最为实用。1 1 构造的实体几何法构造的实体几何法 构造的构造的实实体几何体几何(CSG:Constructive(CSG:Constructive Solid Geometry)Solid Geometry)法是指任意复法是指任意复杂杂的形体都的形体都可以用可以用简单简单形体形体(体素体素)的的组组合来表示。合来表示。形体的形体的CSGCSG表示可看成是一棵有序的二表示可看成是一棵有序的二叉叉树树，称，称为为CSGCSG树树。其。其终终端端结结点或是体素，点或是体素，如如长长
35、方体、方体、圆锥圆锥等；或是等；或是刚刚体运体运动动的的变换变换参参数，如平移参数数，如平移参数T Tx x等；非等；非终终端端结结点或是正点或是正则则的集合运算，一般有交、并、差运算；的集合运算，一般有交、并、差运算；或是刚体的几何变换，如平移、旋转等。或是刚体的几何变换，如平移、旋转等。采用采用BNFBNF范式可定义范式可定义CSGCSG树若下：树若下：:=:=|CSGCSG树树是是无无二二义义性性的的，但但不不是是唯唯一一的的，其其定定义义域域取取决决于于所所用用体体素素以以及及所所允允许许的的几几何何变变换换和正则集合运算算子。和正则集合运算算子。CSG CSG表示的优点：表示的优点：
36、数数据据结结构构比比较较简简单单，数数据据量量比比较较小小，内内部部数数据的管理比较容易；据的管理比较容易；每个每个CSGCSG表示都和一个实际的有效形体所对应；表示都和一个实际的有效形体所对应；CSGCSG表表示示可可方方便便地地转转换换成成BrepBrep表表示示，从从而而可可支支持持广泛的应用；广泛的应用；比较容易修改比较容易修改CSGCSG表示形体的形状。表示形体的形状。CSGCSG表示的缺点：表示的缺点：产产生生和和修修改改形形体体的的操操作作种种类类有有限限，基基于于集集合合运运算算对形体的局部操作不易实现；对形体的局部操作不易实现；由于形体的边界几何元素由于形体的边界几何元素(点
37、、边、面点、边、面)是隐含是隐含地表示在地表示在CSGCSG中，故显示与绘制中，故显示与绘制CSGCSG表示的形体表示的形体需要较长的时间。需要较长的时间。2 2 特征表示特征表示 特特征征表表示示是是从从应应用用层层来来定定义义形形体体，因因而而可可以以较较好好地地表表达达设设计计者者的的意意图图，为为制制造造和和检检验验产产品品和和形形体体提提供供技技术术依依据据和和管管理理信信息息。从从功功能能上看可分为形状、精度、材料和技术特征。上看可分为形状、精度、材料和技术特征。形状特征：体素、孔、槽、键等形状特征：体素、孔、槽、键等 精度特征：形位公差、表面粗糙度等；精度特征：形位公差、表面粗糙
38、度等；材料特征：材料硬度、热处理方法等；材料特征：材料硬度、热处理方法等；技术特征：形体的性能参数和特征等。技术特征：形体的性能参数和特征等。形状特征单元是一个有形的几何实体，是一形状特征单元是一个有形的几何实体，是一组可加工表面的集合。如采用长、宽、高三组可加工表面的集合。如采用长、宽、高三尺寸表示的长方体；采用底面半径及高度表尺寸表示的长方体；采用底面半径及高度表示的圆柱体均是可选用的形状特征单元。示的圆柱体均是可选用的形状特征单元。形状特征单元的形状特征单元的BNFBNF范式可定义如下：范式可定义如下：=|;：=长长方方体体|圆圆柱柱体体|球球体体|圆圆锥锥体体|棱棱锥锥体体|棱棱柱柱体
39、体|棱棱台台体体|圆圆环环体体|楔楔形形体体|圆圆角角体体|；：=并并|交交|差差|放；放；：=外圆角外圆角|内圆角内圆角|倒倒角。角。3 3 边界表示边界表示 边界表示详细记录了构成形体的所有几何边界表示详细记录了构成形体的所有几何元素的几何信息及其相互连接关系元素的几何信息及其相互连接关系拓扑关系，拓扑关系，便于直接存取构成形体的各个面、面的边界以便于直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。为基础的各种几何运算和操作。形体的边界表示就是用面、环、边、点来形体的边界表示就是用面、环、边、点
40、来定义形体的位置和形状。例如，一个长方体由定义形体的位置和形状。例如，一个长方体由六个面围成，对应有六个环，每个环由四条边六个面围成，对应有六个环，每个环由四条边界定义，每条边又由两个端点定义。而圆柱体界定义，每条边又由两个端点定义。而圆柱体则由上顶面、下底面和圆柱面所围成，对应有则由上顶面、下底面和圆柱面所围成，对应有上顶面圆环、下底面圆环。上顶面圆环、下底面圆环。BrepBrep表示的优点是：表示的优点是：表表示示形形体体的的点点、边边、面面等等几几何何元元素素是是显显式式表表示示的的，使使得得绘绘制制BrepBrep表表示示形形体体的的速速度度较较快快，而且比较容易确定几何元素间的连接关
41、系；而且比较容易确定几何元素间的连接关系；对形体的对形体的BrepBrep表示可有多种操作和运算。表示可有多种操作和运算。BrepBrep表示的缺点是：表示的缺点是：数数据据结结构构复复杂杂，需需要要大大量量的的存存储储空空间间，维维护护内部数据结构的程序比较复杂；内部数据结构的程序比较复杂；修改形体的操作比较难以实现；修改形体的操作比较难以实现；Brep Brep表示并不一定对应一个有效形体，即需表示并不一定对应一个有效形体，即需要有专门的程序来保证要有专门的程序来保证BrepBrep表示形体的有效表示形体的有效性、正则性等。性、正则性等。八叉树八叉树 假设要表示的形体假设要表示的形体V V
42、可以放在一个充分大可以放在一个充分大的正立方体的正立方体C C内内,C,C的边长为的边长为2 2n n,形体形体V C,V C,它它的八又树表示可以递归定义为的八又树表示可以递归定义为:八叉树每个结点与八叉树每个结点与C C的一个子立方体对应，的一个子立方体对应，树根就和树根就和C C本身对应。如果本身对应。如果V=C,V=C,那么那么V V八叉树八叉树仅有树根。如果仅有树根。如果VC,VC,则将则将C C均分为八个子立均分为八个子立方体方体,每个子立方体对应根结点的一个子结点。每个子立方体对应根结点的一个子结点。只要某个子立方体不是完全空白或完全被只要某个子立方体不是完全空白或完全被V V所
43、所占据占据,它就要被八等分它就要被八等分,从而它对应的结点也从而它对应的结点也有了八个子结点。这样的递归判断及可能分有了八个子结点。这样的递归判断及可能分割一直进行割一直进行,直到结点对应的立方体或完全空直到结点对应的立方体或完全空白白,或完全被占据或完全被占据,或其大小已是预先规定的或其大小已是预先规定的体素大小体素大小.这时对它与这时对它与V V之交作一定的之交作一定的“舍入舍入”,”,使体素或认为是空白使体素或认为是空白,或认为是被或认为是被V V占据的。这里所谓的体素占据的。这里所谓的体素,就是指被分就是指被分割后得到的小立方体。割后得到的小立方体。通常称对应立方体被形体通常称对应立方
44、体被形体V V完全占完全占据的结点为据的结点为黑结点黑结点,完全不占据的为完全不占据的为白白结点结点,部分被占据的为部分被占据的为灰结点灰结点。存贮结构存贮结构,有常规的、线性的、有常规的、线性的、一对八式的八叉树等等。一对八式的八叉树等等。八叉树方法的主要优点在于八叉树方法的主要优点在于,可以非常方可以非常方便地实现形体的便地实现形体的集合运算集合运算 。八叉树表示的三维形体的几何变换八叉树表示的三维形体的几何变换 比例变换比例变换 旋转变换旋转变换 相对通过原点的一条任意方向相对通过原点的一条任意方向的直线做旋转任意角度的旋转变换。的直线做旋转任意角度的旋转变换。构成原形体的构成原形体的直
45、立直立的正立方体经绕原点任的正立方体经绕原点任意轴线旋转任意角度后意轴线旋转任意角度后,一般都成为一般都成为斜置斜置的。的。为了使变换后形体的八叉树仍对应一系列直立为了使变换后形体的八叉树仍对应一系列直立的正立方体的正立方体,必须对被斜置立方体部分占据体必须对被斜置立方体部分占据体素做出选择素做出选择,即或认为是占据即或认为是占据,为黑结点为黑结点,或认或认为不占据为不占据,为白结点为白结点,这就必然带来一定的误差。这就必然带来一定的误差。而且执行多次变换后而且执行多次变换后,误差积累会大到产生严误差积累会大到产生严重的错误。重的错误。第第一一项项措措施施是是保保持持一一个个原原始始的的八八叉
46、叉树树做做为为参参考考的的源源树树。设设指指定定了了一一次次变变换换R R1 1,接接着着又又要要做做变变换换R R2 2,可可以以计计算算出出复复合合变变换换R=RR=R1 1RR2 2,然然后后对对原原始始的的八叉树做一次变换。这样来避免误差的积累。八叉树做一次变换。这样来避免误差的积累。第二项措施是为了尽量减少第二项措施是为了尽量减少 舍入舍入 误差误差,可以可以规定一个当前正要重建的八叉树规定一个当前正要重建的八叉树,如果它的最底如果它的最底层叶结点对应的体素是部分地为显示对象所占据，层叶结点对应的体素是部分地为显示对象所占据，那么当且仅当这个体素的中心位于某个黑变换后那么当且仅当这个
47、体素的中心位于某个黑变换后立方体内时立方体内时,这个体素才被规定为黑这个体素才被规定为黑,否则就规定否则就规定为白。这样规定使得一般不会产生原来不存在的为白。这样规定使得一般不会产生原来不存在的孔洞，而不这样规定孔洞，而不这样规定,例如简单地规定部分被占例如简单地规定部分被占据的体素都为白据的体素都为白,则可能在做则可能在做45450 0左右旋转时原来左右旋转时原来黑立方体变换为部分占据若干体素而被指定为白黑立方体变换为部分占据若干体素而被指定为白,在变换后形体中间出现断裂。在变换后形体中间出现断裂。设己采取了上述两项措施设己采取了上述两项措施,已知形体变换已知形体变换前的八叉树表示前的八叉树
48、表示T T1 1,己计算出己计算出 要要做做的的复复合合变变换换R,R,要要确确定定变变换换后后形形体体的的八叉树表示八叉树表示T T2 2,可以写出如下的算法框架：可以写出如下的算法框架：1.1.遍遍历历形形体体原原来来的的八八叉叉树树T T1 1,对对遇遇到到的的每每个个黑黑结点结点,做下述步做下述步2 2。2.2.对对遇遇到到黑黑结结点点对对应应的的正正立立方方体体做做相相应应变变换换,得得它它新新的的一一般般来来说说是是斜斜置置的的新新位位置置。若若这这位位置置已已超超出出定定义义八八叉叉树树的的充充分分大大正正立立方方体体C C之之外外,报告出错报告出错;否则执行下述的步否则执行下述
49、的步3 3。3.3.从要计算求出的目标树从要计算求出的目标树T T2 2的根开始的根开始,检查检查2 2中确定的处于新位置立方体与中确定的处于新位置立方体与T T2 2中结点对应中结点对应的直立的正立方体是否相交的直立的正立方体是否相交,分以下三种情况分以下三种情况进行处理进行处理:(1)1)不不相相交交,说说明明正正考考查查直直立立正正立立方方体体未未被被占占据据,可保持为白结点可保持为白结点,不做处理。不做处理。(2)(2)直直立立的的正正立立方方体体整整个个被被占占据据,即即它它在在变变换换后后 斜置斜置 立方体内立方体内,置对应结点为黑结点。置对应结点为黑结点。(3)(3)在在上上述述
50、两两条条均均不不成成立立时时,生生成成当当前前结结点点的的八八个个子子结结点点,对对八八个个子子结结点点对对应应的的八八个个直直立立子子立立方方体体,依依次次再再递递归归执执行行步步3 3。如如果果最最终终这这八八个个结结点点被被标标上上同同样样特特性性,比比方方为为黑黑结结点点,则则应应再再删删掉掉这这八八个个子子结结点点而而把把它它们们的的共共同同父父结结点点置为黑。置为黑。算法中算法中,主要工作是检查某个直立的正立主要工作是检查某个直立的正立方体与一个斜置的正立方体是否相交。对所方体与一个斜置的正立方体是否相交。对所有黑结点对应正立方体处理相同有黑结点对应正立方体处理相同,使得操作可使得