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

第第6 6章章 形体的表示及其数形体的表示及其数据结构据结构Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology第六章第六章 形体的表示及其数据结构形体的表示及其数据结构 与空间任意形体有关的信息可以分为与空间任意形体有关的信息可以分为1.1.图形信息图形信息:点、线、面的位置点、线、面的位置,相互关系及大小等相互关系及大小等2.2.非图形信息非图形信息:颜色、亮度、质量、体积。颜色、亮度、质量、体积。图形信息包括图形信息包括1.1.几何信息：几何信息：形体在空间的位置和大小形体在空间的位置和大小2.2.拓扑信息：拓扑信息：组成形体各部分的数目及相互间的连接关系。组成形体各部分的数目及相互间的连接关系。形体的表示方法通常可分为两类：形体的表示方法通常可分为两类：1.1.边界表示边界表示：用边界将形体分为内部和外部。例如曲线曲面：用边界将形体分为内部和外部。例如曲线曲面2.2.空间分区表示空间分区表示：描述形体的内部性质：描述形体的内部性质,将包含形体的空间区将包含形体的空间区域划分为一组小的非重叠的连续实体。（四叉树和八叉树）域划分为一组小的非重叠的连续实体。（四叉树和八叉树）4/12/20242Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology第一节第一节二维形体的表示二维形体的表示一一.二维图形的边界表示二维图形的边界表示a.折线法折线法就是用多段线段形成的折线去逼近曲线，折就是用多段线段形成的折线去逼近曲线，折线表示曲线应该解决的关键问题是线表示曲线应该解决的关键问题是:如何恰当地确定如何恰当地确定曲线上一系列点曲线上一系列点,使之在使之在某些判定准则下某些判定准则下达到达到最优最优。设已经用某种方法取得了曲线上足够多的点设已经用某种方法取得了曲线上足够多的点,使连接使连接那些点的折线可以很好地表达该曲线。那些点的折线可以很好地表达该曲线。问题是问题是:怎样在其中选择怎样在其中选择尽可能少尽可能少的点的点,使选出的点仍使选出的点仍能较好地表达原曲线。具体地说能较好地表达原曲线。具体地说,使选出的点满足以使选出的点满足以下二条准则下二条准则:4/12/20243Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology(1)共线性共线性设设Pj和和Pk是选出的两点是选出的两点,则在则在Pj到到Pk之间所有点到直线之间所有点到直线PjPk的垂直距离的垂直距离,应小于某个预先给定的限制阈值应小于某个预先给定的限制阈值0,这里这里00,是是一个可以由应用问题需要而确定的一个可以由应用问题需要而确定的很小的正数很小的正数。若不小于。若不小于0,应应寻找距离为最大之点并考虑是否可以在该点将这一段寻找距离为最大之点并考虑是否可以在该点将这一段分裂分裂为两为两段。段。4/12/20244Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology(2)合并性合并性设选出的连续三点是设选出的连续三点是Pi,Pj,Pk,则向量则向量PiPj与与PjPk的夹角的夹角的绝对值的绝对值,应大于某个预先给定的限制阈值应大于某个预先给定的限制阈值0。,若小于若小于0,则则Pj不不应选取而应考虑是否能将应选取而应考虑是否能将Pi至至Pj和和Pj至至Pk两段合并。两段合并。4/12/20245Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology设设 有有 曲曲 线线 上上 n+1个个 点点 的的 坐坐 标标 序序 列列,各各 点点 依依 次次 编编 号号 为为0,1,2,n;为为使使删删去去各各点点距距留留下下前前后后二二点点所所形形成成直直线线的的距距离离不不很很大大而而预预先先给给定定的的阈阈值值0;为为使使选选出出连连续续三三点点所所成成向向量量夹夹角角不不很很小小而而预预先先给给定定的的阈阈值值0;参参数数k0表表示示每每次次向向前前检查检查k0个点。个点。1.初初始始化化i0,j0,kk0,输输出出点点编编号号0,s1。i记记最最近近己己选选之之点点,初初始始起起点点0为为必必选选,j记记待待检检查查之之点点,算算法法中中保保持持ij,待检查线是点待检查线是点j到到k的直线。的直线。2.共共线线性性检检查查检检查查点点j到到k间间各各点点共共线线性性。若若不不能能通通过过,距距离离直直线线PjPk最最远远的的点点是是m,则则km返返回回本本步步开开头头。否否则则继续。继续。本步必能通过本步必能通过,因最坏在因最坏在k=j+1时能通过。时能通过。3.暂暂定定j前前后后两两线线方方向向L2点点j到到k的的方方向向,若若i=j则则L1L2,到到6;否否则则继继续续。L2是是暂暂定定找找到到从从j向向后后的的新新线线方方向向,L1是前次找到原有线方向。是前次找到原有线方向。4/12/20246Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology4.向向量量夹夹角角检检查查检检查查Pi,Pj,Pk三三点点形形成成二二向向量量L1和和L2的的夹夹角角的的绝绝对对值值,若若可可以以通通过过即即应应发发生生合合并并,做做ji然然后后返返2,否否则则继继续续。本本步步检检查查通通过过即即点点j不不能能选选取取,而要检查原而要检查原i到到k的直线。的直线。5.找找到到一一个个选选取取点点ij,L1点点j到到k的的方方向向,输输出出点点编号编号j,ss+1。6.准准备备下下次次jk,kk+k0,若若kn则则kn,若若jn-1则则返返2,否则继续。否则继续。7.最后取点输出点编号最后取点输出点编号n,算法结束。算法结束。4/12/20247Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and TechnologyP0P1P2P3P4P5P6i0,j0,kk0(3)PjPk即即P0P3,若通过；若通过；jk,kk+k0,PjPk即即P3P64/12/20248Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technologyb.带树法带树法带树是一棵二叉树带树是一棵二叉树,树的每个结点对应一树的每个结点对应一个矩形带段个矩形带段,这样每个结点可由八个字段这样每个结点可由八个字段组成组成,前六个字段描述矩形带段前六个字段描述矩形带段,后二个是后二个是指向两个子结点的指针指向两个子结点的指针,即矩形带段的起即矩形带段的起点是点是(xb,yb),终点是终点是(xe,ye)。相对从起点到。相对从起点到终点的连线终点的连线,矩形有两边与之平行矩形有两边与之平行,两边与两边与之垂直之垂直,平行两边与之距离分别为平行两边与之距离分别为wl和和wr。4/12/20249Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology4/12/202410Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology设设要要表表示示的的曲曲线线是是由由经经过过适适当当选选取取已已确确定定的的一一组组离离散散点点P0,P1,Pn序序列列给给出出,则则生生成成表表示示曲曲线线的的分分辨辨率率为为w0的的带带树树的的算算法法,可可简简略略描描述述如下如下:1.找找出出由由起起点点P0,终终点点Pn确确定定的的矩矩形形带带段段,其其中中包包含含P0至至Pn的的全全部部点点,构构造造此此矩矩形形带带段段的的对对应应结点并令为根。结点并令为根。2.找找出出P0至至Pn之之间间距距离离连连线线P0Pn为为最最远远的的点点Pk,然然后后对对P0至至Pk和和Pk至至Pn这这两两组组点点分分别别做做与与步步1中中相相同同的的构构造造矩矩形形带带段段及及对对应应结结点点的的操操作作,产产生的两个结点生的两个结点,分别是根的左右子结点。分别是根的左右子结点。3.反复执行上述操作反复执行上述操作,直到所产生结点的直到所产生结点的w=wl+w wr rw0。这样的结点是叶结点。这样的结点是叶结点。4/12/202411Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology设表示曲线有设表示曲线有5个点个点(3,7)(9,12),(15,4),(18,5),(20,7),取分辨率取分辨率w0=1,则上述算法构造的带树则上述算法构造的带树4/12/202412Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology带树法解决曲线的问题：带树法解决曲线的问题：以不同的分辨率显示用带树表示的曲线以不同的分辨率显示用带树表示的曲线设给出允许的分辨率为设给出允许的分辨率为w*,表示曲线的带树的表示曲线的带树的分辨率为分辨率为w0,并设并设w0w*,则显示算法可简略描则显示算法可简略描述如下述如下:从根结点开始从根结点开始,若当前正考查结点的若当前正考查结点的W=wl+wrw*,则显示该结点对应的矩形带段则显示该结点对应的矩形带段;若不然若不然,即即Ww*则转去分别考查该结点的左右两个则转去分别考查该结点的左右两个子结点子结点,对子结点做同样的处理。左右子结点对子结点做同样的处理。左右子结点都被显示的结点就认为是被显示了都被显示的结点就认为是被显示了,按此看法按此看法,显示带树表示的曲线就是显示带树的结点。显示带树表示的曲线就是显示带树的结点。4/12/202413Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology利用带树求曲线相交利用带树求曲线相交两个矩形带段两个矩形带段S1和和S2的位置关系有如下三种的位置关系有如下三种:(1)不相交。不相交。(2)良良性性相相交交,即即S1的的与与起起点点至至终终点点连连线线平平行行的的两两条条边边都都与与S2相相交交,S2的的与与起起点点至至终终点点连连线线平行的两条边也都与平行的两条边也都与S1相交。相交。(3)可能性相交可能性相交,这时不是良性相交这时不是良性相交,但也不但也不是不相交。是不相交。4/12/202414Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology4/12/202415Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology设设表表示示要要求求交交两两曲曲线线的的带带树树己己构构造造得得足足够够精精确确,即即在在树树叶叶一一层层,来来自自不不同同带带树树的的矩矩形形带带段段或或是是不相交或是良性相交不相交或是良性相交,而没有可能性相交出现。而没有可能性相交出现。两两树树T1和和T2表表示示的的两两条条曲曲线线是是否否相相交交的的算算法法,可可以简略叙述如下以简略叙述如下:算法：算法：1.若若T1和和T2对对应应的的矩矩形形带带段段互互不不相相交交,那那么么它它们们代表的曲线不相交代表的曲线不相交;2.若若T1和和T2对应的矩形带段对应的矩形带段良性相交良性相交,那么它们那么它们代表的曲线相交代表的曲线相交;3.若若T1和和T2对应的矩形带段对应的矩形带段可能性相交可能性相交,且且T1的的面积大于或等面积大于或等T2的面积的面积,那么分别执行那么分别执行T2与与T1的左右两个儿子结点的相交性检查。的左右两个儿子结点的相交性检查。4/12/202416Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology4.若若T1的面积小于的面积小于T2的面积的面积,则把它们位置对则把它们位置对换一下再如上进行两个检查。换一下再如上进行两个检查。4.1.若两个检查的结果都是不相交若两个检查的结果都是不相交,则认为所则认为所表示曲线不相交表示曲线不相交;4.2.若两个检查中有一个是良性相交若两个检查中有一个是良性相交,则认为则认为所表示曲线相交所表示曲线相交;4.3.若不是上述两情形若不是上述两情形,即出现可能性相交即出现可能性相交,则则对可能性相交的两个矩形带段中面积较大对可能性相交的两个矩形带段中面积较大者者,取其对应结点的两个子结点取其对应结点的两个子结点,如此进行可如此进行可直到树叶那一层。直到树叶那一层。4/12/202417Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology如何确定一点是否在一封闭曲线内如何确定一点是否在一封闭曲线内从该点引射线与区域边界相交的次数为从该点引射线与区域边界相交的次数为奇奇数，点在区域内，否则点在区域外。数，点在区域内，否则点在区域外。判别两曲线相交：一条射线（宽度为判别两曲线相交：一条射线（宽度为0的带的带树，与表示曲线的带树求交，交点的个数树，与表示曲线的带树求交，交点的个数即为带树良性相交次数。即为带树良性相交次数。实践表明用带树方法表示曲线对提高计算实践表明用带树方法表示曲线对提高计算效率是有帮助的。另外两个带树对效率是有帮助的。另外两个带树对并、交并、交等运算是封闭的等运算是封闭的,与用象素阵列来表示图形与用象素阵列来表示图形的方法比较空间需求也算是节省的。的方法比较空间需求也算是节省的。4/12/202418Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology二二.平面图形的平面图形的四叉树四叉树表示方法表示方法（表示（表示实区域实区域，不，不是边界）是边界）假定一个平面假定一个平面图形是形是黑白黑白的二的二值图形形,即即组成成图形象形象素素阵列的列的仅有黑色象素有黑色象素值1,白色象素白色象素值0,设表表现图形的象素形的象素阵列由列由2n2n个象素个象素组成。成。表示表示该图形的四叉形的四叉树结构可以如下形成构可以如下形成:图形形显然然包括包括2n2n的正方形中，的正方形中，这个正方形是四叉个正方形是四叉树的根的根结点。点。若若图形整个地占据形整个地占据这个正方形个正方形,则图形就用形就用该正方形正方形表示表示,否否则将将该正方形均分正方形均分为四个小正方形，每个小四个小正方形，每个小正方形正方形边长为原正方形原正方形边长的一半的一半.它它们是根是根结点的点的四个子四个子结点点,可可编号号为0,1,2,3。4/12/202419Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology 再考再考查每个小正方形每个小正方形,若整个被若整个被图形占据形占据,则标记相相应结点点为1,1,可称可称为黑黑结点点。若整个与。若整个与图形不相交形不相交,则标记相相应结点点为0 0，可称，可称为白白结点点。若不是上述两情形，即与若不是上述两情形，即与图形部分形部分相交，相交，则称相称相应结点是点是灰灰结点点并将其一并将其一分分为四。当再分生成小正方形四。当再分生成小正方形边长达到达到一个一个象素象素单位位时，再分，再分终止，此止，此时一般一般应将仍是灰将仍是灰结点的改点的改为黑黑结点，如此形点，如此形成了平面成了平面图形的四叉形的四叉树表示表示 4/12/202420Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology4/12/202421Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and TechnologyTreeCreatetree4(V,C,n)/V是形体，是形体，C是正方形，是正方形，n表示正方形边长对应的层次表示正方形边长对应的层次if(intersect(V,C,n)=C)new(P);构造构造P;return(P);elseif(intersect(V,C,n)!=NULL)if(n=1)new(P);构造构造P;return(P);elsenew(P);构造构造P;return(P);C1=C.0;C2=C.1;C3=C.2;C4=C.3;P-F1=Createtree4(V,C1,n-1);P-F2=Createtree4(V,C2,n-1);P-F3=Createtree4(V,C3,n-1);P-F4=Createtree4(V,C4,n-1);elsereturnNULL;4/12/202422Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology四叉树的存储方式：即四叉树的存储方式：即规则方式、线性方式和一对四方规则方式、线性方式和一对四方式式1.规则四叉树规则四叉树用五个字段的记录来表示树中的每个结点用五个字段的记录来表示树中的每个结点一个用来描述结点的特性，即是灰、黑、白三类结点一个用来描述结点的特性，即是灰、黑、白三类结点中的一种。其余四个用于存放指向四个子结点的指针。中的一种。其余四个用于存放指向四个子结点的指针。缺点缺点：大量的存储空间被指针占用，存储空间利用率：大量的存储空间被指针占用，存储空间利用率差差2.线性四叉树线性四叉树以某一预先确定的次序遍历四叉树形成一个以某一预先确定的次序遍历四叉树形成一个线性表结线性表结构构。RAabcdBCDefgh。其中。其中R表示根，字母右上角加表示根，字母右上角加表表示是灰结点。示是灰结点。优点：节省存储空间空间优点：节省存储空间空间缺点：灵活性差缺点：灵活性差4/12/202423Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology3.一对四式四叉树一对四式四叉树一对四式四叉树的存储结构一对四式四叉树的存储结构每个结点有五个字每个结点有五个字段，其中四个字段用来描述该结点的四个子结点段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的状态，另一个结点存放指向子结点记录存放处的指针。的指针。四个子结点对应的记录是依次连续存放四个子结点对应的记录是依次连续存放的。的。4/12/202424Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology改进改进的一对四式四叉树的一对四式四叉树(为节省存贮空间为节省存贮空间)：a.增加计算量（紧凑的一对四式四叉树）增加计算量（紧凑的一对四式四叉树）存取相应节点时，先检查其父节点，看在它之前存取相应节点时，先检查其父节点，看在它之前有几个叶节点有几个叶节点b.一个记录增加一个字节一个记录增加一个字节该字节一分为四该字节一分为四,每个子结点对应每个子结点对应2位位,表示它的子表示它的子结点在指针指向区域中的偏移。结点在指针指向区域中的偏移。4/12/202425Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology四叉树优点：四叉树优点：(与象素阵列表示与象素阵列表示)节省存储空间节省存储空间可以用不同精度来表示可以用不同精度来表示与设备无关，便于移植与设备无关，便于移植4/12/202426Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology第二节第二节三维几何模型三维几何模型一一.几何元素几何元素形体的模型主要指的就是包含图形信息所形体的模型主要指的就是包含图形信息所形成的模型。形成的模型。形体本身的构造有一定的层次性，低层部形体本身的构造有一定的层次性，低层部分组合构成上一层部分，而上一层部分组分组合构成上一层部分，而上一层部分组合又可以构成更高一层的部分，依此类推合又可以构成更高一层的部分，依此类推可形成多层结构。其中，每一层中的部分，可形成多层结构。其中，每一层中的部分，我们把它有称为几何元素。我们把它有称为几何元素。4/12/202427Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology(1)点点点点是是0维维几几何何元元素素，有有端端点点、交交点点、切切点点、孤立点等形式。孤立点等形式。曲曲线线、曲曲面面的的应应用用中中会会涉涉及及到到三三种种类类型型的的点：点：型值点型值点相应曲线、曲面必然经过的点。相应曲线、曲面必然经过的点。控控制制点点相相应应曲曲线线、曲曲面面不不一一定定经经过过的的点点，仅用于确定位置和形状。仅用于确定位置和形状。插插值值点点在在型型值值点点之之间间插插入入的的一一系系列列点点，用用于提高曲线曲面的输出精度。于提高曲线曲面的输出精度。4/12/202428Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology不同的空间中点的表示方式不同的空间中点的表示方式(1)一维空间中用一元组一维空间中用一元组t表示；表示；(2)二维空间中用二元组二维空间中用二元组x,y或或x(t),y(t)表示；表示；(3)三维空间中用三元组三维空间中用三元组x,y,z或或x(t),y(t),z(t)表示；表示；点是几何造型中的最基本的元素，曲线、曲点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述。面和其它形体都可以用有序的点集描述。用计算机存储、管理、输出形体的实质就是用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。对点集及其连接关系的处理。4/12/202429Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology(2)边边边边是是一一维维几几何何元元素素，是是两两个个邻邻面面（正正则则形形体体）或或多多个个邻邻面面（非非正正则则形形体体）的的交交界界。边边分分直直线线边边和和曲曲线线边边。直直线线边边由由起起点点和和终终点点两两端端点点确确定定；曲曲线线边边由由一一系系列列型型值值点点或或控控制制点点表表示示，也也可可以以用显示、隐式方程描述。用显示、隐式方程描述。(3)环环环是有序有向边（直线段或曲线段）组成的面环是有序有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻两条边的封闭边界。环中的边不能相交，相邻两条边共享一个端点。环有内外之分，确定面的最大共享一个端点。环有内外之分，确定面的最大外边界的环称之为外边界的环称之为外环外环，通常其边按，通常其边按逆时针方逆时针方向向排序。而把确定面中内孔或凸台边界的环称排序。而把确定面中内孔或凸台边界的环称之为之为内环内环，其边相应外环排序方向相反，通常，其边相应外环排序方向相反，通常按按顺时针方向顺时针方向排序。排序。4/12/202430Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology(4)面面面面是是二二维维几几何何元元素素，是是形形体体上上一一个个有有限限、非非零零的的区区域域，它它由由一一个个外外环环和和若若干干个个内内环环所所界界定定。面面有有方方向向性性，一一般般用用其其外外法法向向量量作作为为该该面面的的正正向向。若若一一个个面面的的外外法法向向量量向向外外，此此面面为为正正；否否则，为反向面。则，为反向面。(5)体体体是体是三维几何元素三维几何元素，由封闭表面围成的空间，由封闭表面围成的空间，它是欧氏空间它是欧氏空间R3中非空、有界的封闭子集，其中非空、有界的封闭子集，其边界是有限面的并集。在实际应用中，要求形边界是有限面的并集。在实际应用中，要求形体是体是正则形体正则形体，即形体上任意一点的足够小的，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。不满足邻域在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。存在悬面、上述要求的形体称为非正则形体。存在悬面、悬边的形体是非正则形体。悬边的形体是非正则形体。4/12/202431Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology正则形体：即形体上任意一点的足够小的邻域正则形体：即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。不满足上述在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。存在悬面、悬边要求的形体称为非正则形体。存在悬面、悬边的形体是的形体是非正则形体非正则形体。4/12/202432Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology(6)体素体素体体素素是是可可以以用用有有限限个个尺尺寸寸参参数数定定位位和和定定型型的的体体，常有下面三种定义形式。常有下面三种定义形式。一一组组单单元元实实体体长长方方体体、圆圆柱柱体体、圆圆锥锥体体、球球体。体。扫扫描描体体由由参参数数定定义义的的一一条条（一一组组）截截面面轮轮廓廓线线沿沿一一条条（一一组组）空空间间参参数数曲曲线线作作扫扫描描运运动动而而产生的形体。产生的形体。用代数半空间定义的形体用代数半空间定义的形体，在此半空间中点集，在此半空间中点集可定义可定义(x,y,z)|f(x,y,z)0此处的此处的f应是不可约的应是不可约的多项式。多项式。形体的层次结构形体的层次结构点点边边环环面面外壳外壳形体。形体。4/12/202433Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology在几何造型中最基本的几何元素是点在几何造型中最基本的几何元素是点(V)、边、边(E)、面、面(F),这三种元素一共有九这三种元素一共有九种连接关系种连接关系4/12/202434Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology二二.线框、表面及实体表示（多面体的表示）线框、表面及实体表示（多面体的表示）常用的多面体表示法是常用的多面体表示法是三表表示法三表表示法，即采用三个表，即采用三个表:顶点表顶点表:顶点坐标顶点坐标,用来存放多面体各顶点的坐标用来存放多面体各顶点的坐标;边表边表:两个顶点编号表达一条边两个顶点编号表达一条边,指出哪两个顶点之间有多面体指出哪两个顶点之间有多面体的边的边面表：面表：边的编号表示面边的编号表示面,指出哪些边围成了多面体的表面指出哪些边围成了多面体的表面线框模型：点表，边表线框模型：点表，边表表面模型：点表，边表，面表表面模型：点表，边表，面表实体模型：点表，边表，面表位置确定实体模型：点表，边表，面表位置确定形体确定形体确定三表确定三表确定给出三表给出三表不一定表示一个真实形体不一定表示一个真实形体(正则形体：正则形体：V-E+F=2)满足条件满足条件1.顶点表中的每个顶点至少是顶点表中的每个顶点至少是三边三边的端点的端点;2.边表中的每条边是边表中的每条边是两个多边形两个多边形面的公共边；面的公共边；3.每个多边形面是封闭的等等。每个多边形面是封闭的等等。4/12/202435Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology4/12/202436Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technologyxyz100110010000101111011001122334415667788515263748110592116103127114981256783214顶点表顶点表面表面表边表边表4/12/202437Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology空间正二十空间正二十面体面体V20,的三的三表表示。表表示。引入一个正引入一个正数数0,它满它满足二次方程足二次方程2-1=0,因因此此=1/2(1+)1.618034。XYZ4/12/202438Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology编号编号xyz110112-01130-114-0-12110221-023-1024-1-031013201-330-1340-1-边编号边编号边编号边编号111,131621,33212,141722,32321,231822,34422,241923,31531,332023,32632,342124,33711,212224,34811,222331,11912,232431,121012,242532,131113,212632,141213,222733,111314,232833,121414,242934,131521,313034,144/12/202439Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology面编号面编号面编号面编号17，23，151125，6，2928，17，271230，6，26311，16，251311，1，7429，28，12148，1，1259，19，24159，2，13628，21，101614，2，10726，20，131719，3，15814，22，301816，3，20927，5，231917，4，211024，5，282022，4，184/12/202440Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology4/12/202441Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology三三.三维实体表示方法三维实体表示方法从用户角度来看，形体以特征表示和构造的实体从用户角度来看，形体以特征表示和构造的实体几何表示比较适宜；从计算机对形体的存储管理几何表示比较适宜；从计算机对形体的存储管理和操作运算角度看，以边界表示最为实用。和操作运算角度看，以边界表示最为实用。1.构造的实体几何法构造的实体几何法构造的构造的实体几何体几何(CSG:ConstructiveSolidGeometry)法是指任意复法是指任意复杂的形体都可以用的形体都可以用简单形形体体(体素体素)的的组合来表示。合来表示。形体的形体的CSG表示可看成是一棵表示可看成是一棵有序的二叉有序的二叉树，称，称为CSG树。其。其终端端结点或是体素，如点或是体素，如长方体、方体、圆锥等；或是等；或是刚体运体运动的的变换参数，如平移参数参数，如平移参数Tx等；非等；非终端端结点或是正点或是正则的集合运算，一般有交、的集合运算，一般有交、并、差运算；并、差运算；或是刚体的几何变换，如平移、旋或是刚体的几何变换，如平移、旋转等。转等。4/12/202442Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology采用采用BNF范式可定义范式可定义CSG树若下：树若下：:=|CSG树树是是无无二二义义性性的的，但但不不是是唯唯一一的的，其其定定义义域域取取决决于于所所用用体体素素以以及及所所允允许许的的几几何何变变换换和正则集合运算算子。和正则集合运算算子。4/12/202443Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and TechnologyCSG表示的优点：表示的优点：数据结构比较简单，数据量比较小，内部数据的管理比较容易；数据结构比较简单，数据量比较小，内部数据的管理比较容易；每个每个CSG表示都和一个实际的有效形体所对应；表示都和一个实际的有效形体所对应；CSG表示可方便地转换成表示可方便地转换成Brep表示，从而可支持广泛的应用；表示，从而可支持广泛的应用；比较容易修改比较容易修改CSG表示形体的形状。表示形体的形状。CSG表示的缺点：表示的缺点：产产生生和和修修改改形形体体的的操操作作种种类类有有限限，基基于于集集合合运运算算对对形形体体的的局局部部操作不易实现；操作不易实现；由于形体的边界几何元素由于形体的边界几何元素(点、边、面点、边、面)是隐含地表示在是隐含地表示在CSG中，中，故显示与绘制故显示与绘制CSG表示的形体需要较长的时间。表示的形体需要较长的时间。4/12/202444Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology2特征表示特征表示特特征征表表示示是是从从应应用用层层来来定定义义形形体体，因因而而可可以以较较好好地地表表达达设设计计者者的的意意图图，为为制制造造和和检检验验产产品品和和形形体体提提供供技技术术依依据据和和管管理理信信息息。从从功功能能上看可分为形状、精度、材料和技术特征。上看可分为形状、精度、材料和技术特征。形状特征：体素、孔、槽、键等形状特征：体素、孔、槽、键等精度特征：形位公差、表面粗糙度等；精度特征：形位公差、表面粗糙度等；材料特征：材料硬度、热处理方法等；材料特征：材料硬度、热处理方法等；技术特征：形体的性能参数和特征等。技术特征：形体的性能参数和特征等。形状特征单元是一个有形的几何实体，是一形状特征单元是一个有形的几何实体，是一组可加工表面的集合。如采用长、宽、高三组可加工表面的集合。如采用长、宽、高三尺寸表示的长方体；采用底面半径及高度表尺寸表示的长方体；采用底面半径及高度表示的圆柱体均是可选用的形状特征单元。示的圆柱体均是可选用的形状特征单元。4/12/202445Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology形状特征单元的形状特征单元的BNF范式可定义如下：范式可定义如下：:=|;:=长长方方体体|圆圆柱柱体体|球球体体|圆圆锥锥体体|棱棱锥锥体体|棱柱体棱柱体|棱台体棱台体|圆环体圆环体|楔形体楔形体|圆角体圆角体|；:=并并|交交|差差|放；放；:=外圆角外圆角|内圆角内圆角|倒角。倒角。4/12/202446Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology3边界表示边界表示边界表示详细记录了构成形体的所有几何元素边界表示详细记录了构成形体的所有几何元素的几何信息及其相互连接关系的几何信息及其相互连接关系拓扑关系，便拓扑关系，便于直接存取构成形体的各个面、面的边界以及于直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点为各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。基础的各种几何运算和操作。形体的边界表示就是用形体的边界表示就是用面、环、边、点来定义面、环、边、点来定义形体的位置和形状形体的位置和形状。例如，一个长方体由六个。例如，一个长方体由六个面围成，对应有六个环，每个环由四条边界定面围成，对应有六个环，每个环由四条边界定义，每条边又由两个端点定义。而圆柱体则由义，每条边又由两个端点定义。而圆柱体则由上顶面、下底面和圆柱面所围成，对应有上顶上顶面、下底面和圆柱面所围成，对应有上顶面圆环、下底面圆环。面圆环、下底面圆环。4/12/202447Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and TechnologyBrep表示的优点是：表示的优点是：表表示示形形体体的的点点、边边、面面等等几几何何元元素素是是显显式式表表示示的的，使使得得绘绘制制Brep表表示示形形体体的的速速度度较较快快，而且比较容易确定几何元素间的连接关系；而且比较容易确定几何元素间的连接关系；对形体的对形体的Brep表示可有多种操作和运算。表示可有多种操作和运算。Brep表示的缺点是：表示的缺点是：数数据据结结构构复复杂杂，需需要要大大量量的的存存储储空空间间，维维护护内部数据结构的程序比较复杂；内部数据结构的程序比较复杂；修改形体的操作比较难以实现；修改形体的操作比较难以实现；Brep表示并不一定对应一个有效形体，即需表示并不一定对应一个有效形体，即需要有专门的程序来保证要有专门的程序来保证Brep表示形体的有效表示形体的有效性、正则性等。性、正则性等。4/12/202448Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology四四.八叉树八叉树假设要表示的形体假设要表示的形体V可以放在一个充分大的可以放在一个充分大的正立方体正立方体C内内,C的边长为的边长为2n,形体形体VC,它的八它的八又树表示可以递归定义为又树表示可以递归定义为:八叉树每个结点与八叉树每个结点与C的一个子立方体对应，的一个子立方体对应，树根就和树根就和C本身对应。如果本身对应。如果V=C,那么那么V八叉树八叉树仅有仅有树根树根。如果。如果VC,则将则将C均分为八个子立均分为八个子立方体方体,每个子立方体对应根结点的一个子结点。每个子立方体对应根结点的一个子结点。只要某个子立方体不是完全空白或完全被只要某个子立方体不是完全空白或完全被V所占据所占据,它就要被八等分它就要被八等分,从而它对应的结点也从而它对应的结点也有了八个子结点。这样的递归判断及可能分有了八个子结点。这样的递归判断及可能分割一直进行割一直进行,直到结点对应的立方体或完全空直到结点对应的立方体或完全空白白,或完全被占据或完全被占据,或其大小已是预先规定的体或其大小已是预先规定的体素大小素大小.4/12/202449Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology这时对它与这时对它与V之交作一定的之交作一定的“舍入舍入”,使体素或认使体素或认为是空白为是空白,或认为是被或认为是被V占据的。这里所谓的体占据的。这里所谓的体素素,就是指被分割后得到的小立方体。就是指被分割后得到的小立方体。通常称对应立方体被形体通常称对应立方体被形体V完全占据的结点为完全占据的结点为黑黑结点结点,完全不占据的为完全不占据的为白结点白结点,部分被占据的为部分被占据的为灰灰结点结点。存贮结构存贮结构,有常规的、线性的、一对八式的八叉有常规的、线性的、一对八式的八叉树等等。树等等。优点：优点：1.占用存储空间少占用存储空间少2.便于形体的交并差的集合运算便于形体的交并差的集合运算3.可以显式不同精度的实体，消隐便于实现可以显式不同精度的实体，消隐便于实现4/12/202450Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology八叉树表示的三维形体的几何变换八叉树表示的三维形体的几何变换1.比例变换比例变换2.旋转变换旋转变换相对通过原点的一条任意方向的直相对通过原点的一条任意方向的直线做旋转任意角度的旋转变换。线做旋转任意角度的旋转变换。构成原形体的构成原形体的直立直立的正立方体经绕原点任意轴的正立方体经绕原点任意轴线旋转任意角度后线旋转任意角度后,一般都成为一般都成为斜置斜置的。为了的。为了使变换后形体的八叉树仍对应一系列直立的正使变换后形体的八叉树仍对应一系列直立的正立方体立方体,必须对被斜置立方体部分占据体素做出必须对被斜置立方体部分占据体素做出选择选择,即或认为是占据即或认为是占据,为黑结点为黑结点,或认为不占据或认为不占据,为白结点为白结点,这就必然带来一定的误差。而且执行这就必然带来一定的误差。而且执行多次变换后多次变换后,误差积累会大到产生严重的错误。误差积累会大到产生严重的错误。4/12/202451Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology多次变换误差会积累，解决方法多次变换误差会积累，解决方法第第一一项项措措施施是是保保持持一一个个原原始始的的八八叉叉树树做做为为参参考考的的源源树树。设设指指定定了了一一次次变变换换R1,接接着着又又要要做做变变换换R2,可可以以计计算算出出复复合合变变换换R=R1R2,然然后后对对原原始始的的八八叉叉树树做做一一次次变变换换。这样来这样来避免误差的积累避免误差