《第6章 形体的表示及其数据结构.ppt》由会员分享，可在线阅读，更多相关《第6章 形体的表示及其数据结构.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Computer Graphics03.03.20231第第6章章形体的表示及其数据结构形体的表示及其数据结构第一节第一节二维形体的表示二维形体的表示第二节第二节三维几何模型三维几何模型第三节第三节分形分形Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.20232第第6 6章章 形体的表示及其数据结构形体的表示及其数据结构 与空间任意形体有关的信息可以分为与空间任意形体有关的信息可以分为1.1.图
2、形信息图形信息:点、线、面的位置点、线、面的位置,相互关系及大小等相互关系及大小等2.2.非图形信息非图形信息:颜色、亮度、质量、体积。颜色、亮度、质量、体积。图形信息包括图形信息包括1.1.几何信息：几何信息：形体在空间的位置和大小形体在空间的位置和大小2.2.拓扑信息：拓扑信息：组成形体各部分的数目及相互间的连接关系。组成形体各部分的数目及相互间的连接关系。形体的表示方法通常可分为两类：形体的表示方法通常可分为两类：1.1.边界表示边界表示：用边界将形体分为内部和外部。例如曲线曲面：用边界将形体分为内部和外部。例如曲线曲面2.2.空间分区表示空间分区表示：描述形体的内部性质：描述形体的内部
3、性质,将包含形体的空间区将包含形体的空间区域划分为一组小的非重叠的连续实体。（四叉树和八叉树）域划分为一组小的非重叠的连续实体。（四叉树和八叉树）Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.20233第第6章章形体的表示及其数据结形体的表示及其数据结构构一一.二维图形的边界表示二维图形的边界表示a.折线法折线法就是用多段线段形成的折线去逼近曲线，折就是用多段线段形成的折线去逼近曲线，折线表示曲
4、线应该解决的关键问题是线表示曲线应该解决的关键问题是:如何恰当地确定如何恰当地确定曲线上一系列点曲线上一系列点,使之在使之在某些判定准则下某些判定准则下达到达到最优最优。设已经用某种方法取得了曲线上足够多的点设已经用某种方法取得了曲线上足够多的点,使连接使连接那些点的折线可以很好地表达该曲线。那些点的折线可以很好地表达该曲线。问题是问题是:怎样在其中选择怎样在其中选择尽可能少尽可能少的点的点,使选出的点仍使选出的点仍能较好地表达原曲线。具体地说能较好地表达原曲线。具体地说,使选出的点满足以使选出的点满足以下二条准则下二条准则:Computer GraphicsComputer Graphics
5、College of Computer Science and TechnologyCollege of Computer Science and Technology03.03.20234(1)共线性共线性设设Pj和和Pk是选出的两点是选出的两点,则在则在Pj到到Pk之间所有点到直线之间所有点到直线PjPk的垂直距离的垂直距离,应小于某个预先给定的限制阈值应小于某个预先给定的限制阈值0,这里这里00,是是一个可以由应用问题需要而确定的一个可以由应用问题需要而确定的很小的正数很小的正数。若不小于。若不小于0,应应寻找距离为最大之点并考虑是否可以在该点将这一段寻找距离为最大之点并考虑是否可以在该
6、点将这一段分裂分裂为两为两段。段。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.20235(2)合并性合并性设选出的连续三点是设选出的连续三点是Pi,Pj,Pk,则向量则向量PiPj与与PjPk的夹角的夹角的绝对值的绝对值,应大于某个预先给定的限制阈值应大于某个预先给定的限制阈值0。,若小于若小于0,则则Pj不不应选取而应考虑是否能将应选取而应考虑是否能将Pi至至Pj和和Pj至至Pk两段合并。两
7、段合并。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.20236设设 有有 曲曲 线线 上上 n+1个个 点点 的的 坐坐 标标 序序 列列,各各 点点 依依 次次 编编 号号 为为0,1,2,n;为为使使删删去去各各点点距距留留下下前前后后二二点点所所形形成成直直线线的的距距离离不不很很大大而而预预先先给给定定的的阈阈值值0;为为使使选选出出连连续续三三点点所所成成向向量量夹夹角角不不很很小小
8、而而预预先先给给定定的的阈阈值值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.暂
9、暂定定j前前后后两两线线方方向向L2点点j到到k的的方方向向,若若i=j则则L1L2,到到6;否否则则继继续续。L2是是暂暂定定找找到到从从j向向后后的的新新线线方方向向,L1是前次找到原有线方向。是前次找到原有线方向。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202374.向向量量夹夹角角检检查查检检查查Pi,Pj,Pk三三点点形形成成二二向向量量L1和和L2的的夹夹角角的的绝绝对对值值,
10、若若可可以以通通过过即即应应发发生生合合并并,做做ji然然后后返返2,否否则则继继续续。本本步步检检查查通通过过即即点点j不不能能选选取取,而要检查原而要检查原i到到k的直线。的直线。5.找找到到一一个个选选取取点点ij,L1点点j到到k的的方方向向,输输出出点点编号编号j,ss+1。6.准准备备下下次次jk,kk+k0,若若kn则则kn,若若jn-1则则返返2,否则继续。否则继续。7.最后取点最后取点输出点编号输出点编号n,算法结束。算法结束。Computer GraphicsComputer GraphicsCollege of Computer Science and Technolog
11、yCollege of Computer Science and Technology03.03.20238P0P1P2P3P4P5P6i0,j0,kk0(3)PjPk即即P0P3,若通过；若通过；jk,kk+k0,PjPk即即P3P6Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.20239b.带树法带树法带树是一棵二叉树带树是一棵二叉树,树的每个结点对应一树的每个结点对应一个矩形带段个矩形带段
12、,这样每个结点可由八个字段这样每个结点可由八个字段组成组成,前六个字段描述矩形带段前六个字段描述矩形带段,后二个是后二个是指向两个子结点的指针指向两个子结点的指针,即矩形带段的起即矩形带段的起点是点是(xb,yb),终点是终点是(xe,ye)。相对从起点到。相对从起点到终点的连线终点的连线,矩形有两边与之平行矩形有两边与之平行,两边与两边与之垂直之垂直,平行两边与之距离分别为平行两边与之距离分别为wl和和wr。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Comput
13、er Science and Technology03.03.202310Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202311设设要要表表示示的的曲曲线线是是由由经经过过适适当当选选取取已已确确定定的的一一组组离离散散点点P0,P1,Pn序序列列给给出出,则则生生成成表表示示曲曲线线的的分分辨辨率率为为w0的的带带树树的的算算法法,可可简简略略描描述述如下如下:1.找找出出由由起起点点P0
14、,终终点点Pn确确定定的的矩矩形形带带段段,其其中中包包含含P0至至Pn的的全全部部点点,构构造造此此矩矩形形带带段段的的对对应应结点并令为根。结点并令为根。2.找找出出P0至至Pn之之间间距距离离连连线线P0Pn为为最最远远的的点点Pk,然然后后对对P0至至Pk和和Pk至至Pn这这两两组组点点分分别别做做与与步步1中中相相同同的的构构造造矩矩形形带带段段及及对对应应结结点点的的操操作作,产产生的两个结点生的两个结点,分别是根的左右子结点。分别是根的左右子结点。3.反复执行上述操作反复执行上述操作,直到所产生结点的直到所产生结点的w=wl+w wr rw0。这样的结点是叶结点。这样的结点是叶结
15、点。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202312设表示曲线有设表示曲线有5个点个点(3,7)(9,12),(15,4),(18,5),(20,7),取分辨率取分辨率w0=1,则上述算法构造的带树则上述算法构造的带树Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege o
16、f Computer Science and Technology03.03.202313带树法解决曲线的问题：带树法解决曲线的问题：以不同的分辨率显示用带树表示的曲线以不同的分辨率显示用带树表示的曲线设给出允许的分辨率为设给出允许的分辨率为w*,表示曲线的带树的表示曲线的带树的分辨率为分辨率为w0,并设并设w0w*,则显示算法可简略描则显示算法可简略描述如下述如下:从根结点开始从根结点开始,若当前正考查结点的若当前正考查结点的W=wl+wrw*,则显示该结点对应的矩形带段则显示该结点对应的矩形带段;若不然若不然,即即Ww*则转去分别考查该结点的左右两个则转去分别考查该结点的左右两个子结点子结
17、点,对子结点做同样的处理。左右子结点对子结点做同样的处理。左右子结点都被显示的结点就认为是被显示了都被显示的结点就认为是被显示了,按此看法按此看法,显示带树表示的曲线就是显示带树的结点。显示带树表示的曲线就是显示带树的结点。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202314利用带树求曲线相交利用带树求曲线相交两个矩形带段两个矩形带段S1和和S2的位置关系有如下三种的位置关系有如下三种:(
18、1)不相交。不相交。(2)良良性性相相交交,即即S1的的与与起起点点至至终终点点连连线线平平行行的的两两条条边边都都与与S2相相交交,S2的的与与起起点点至至终终点点连连线线平行的两条边也都与平行的两条边也都与S1相交。相交。(3)可能性相交可能性相交,这时不是良性相交这时不是良性相交,但也不但也不是不相交。是不相交。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202315Computer G
19、raphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202316设设表表示示要要求求交交两两曲曲线线的的带带树树己己构构造造得得足足够够精精确确,即即在在树树叶叶一一层层,来来自自不不同同带带树树的的矩矩形形带带段段或或是是不相交或是良性相交不相交或是良性相交,而没有可能性相交出现。而没有可能性相交出现。两两树树T1和和T2表表示示的的两两条条曲曲线线是是否否相相交交的的算算法法,可可以简略叙述如下以简略叙述如下:算法：
20、算法：1.若若T1和和T2对对应应的的矩矩形形带带段段互互不不相相交交,那那么么它它们们代表的曲线不相交代表的曲线不相交;2.若若T1和和T2对应的矩形带段对应的矩形带段良性相交良性相交,那么它们那么它们代表的曲线相交代表的曲线相交;3.若若T1和和T2对应的矩形带段对应的矩形带段可能性相交可能性相交,且且T1的的面积大于或等面积大于或等T2的面积的面积,那么分别执行那么分别执行T2与与T1的左右两个儿子结点的相交性检查。的左右两个儿子结点的相交性检查。Computer GraphicsComputer GraphicsCollege of Computer Science and Techn
21、ologyCollege of Computer Science and Technology03.03.2023174.若若T1的面积小于的面积小于T2的面积的面积,则把它们位置对则把它们位置对换一下再如上进行两个检查。换一下再如上进行两个检查。4.1.若两个检查的结果都是不相交若两个检查的结果都是不相交,则认为所则认为所表示曲线不相交表示曲线不相交;4.2.若两个检查中有一个是良性相交若两个检查中有一个是良性相交,则认为则认为所表示曲线相交所表示曲线相交;4.3.若不是上述两情形若不是上述两情形,即出现可能性相交即出现可能性相交,则则对可能性相交的两个矩形带段中面积较大对可能性相交的两个矩
22、形带段中面积较大者者,取其对应结点的两个子结点取其对应结点的两个子结点,如此进行可如此进行可直到树叶那一层。直到树叶那一层。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202318如何确定一点是否在一封闭曲线内如何确定一点是否在一封闭曲线内从该点引射线与区域边界相交的次数为从该点引射线与区域边界相交的次数为奇奇数，点在区域内，否则点在区域外。数，点在区域内，否则点在区域外。判别两曲线相交：一条
23、射线（宽度为判别两曲线相交：一条射线（宽度为0的带的带树，与表示曲线的带树求交，交点的个数树，与表示曲线的带树求交，交点的个数即为带树良性相交次数。即为带树良性相交次数。实践表明用带树方法表示曲线对提高计算实践表明用带树方法表示曲线对提高计算效率是有帮助的。另外两个带树对效率是有帮助的。另外两个带树对并、交并、交等运算是封闭的等运算是封闭的,与用象素阵列来表示图形与用象素阵列来表示图形的方法比较空间需求也算是节省的。的方法比较空间需求也算是节省的。Computer GraphicsComputer GraphicsCollege of Computer Science and Technolo
24、gyCollege of Computer Science and Technology03.03.202319二二.平面图形的平面图形的四叉树四叉树表示方法表示方法（表示（表示实区域实区域，不，不是边界）是边界）假定一个平面假定一个平面图图形是形是黑白黑白的二的二值图值图形形,即即组组成成图图形象形象素素阵阵列的列的仅仅有黑色象素有黑色象素值值1,白色象素白色象素值值0,设设表表现图现图形的象素形的象素阵阵列由列由2n2n个象素个象素组组成。成。表示表示该图该图形的四叉形的四叉树结树结构可以如下形成构可以如下形成:图图形形显显然然包括包括2n2n的正方形中，的正方形中，这这个正方形是四叉个正
25、方形是四叉树树的根的根结结点。点。若若图图形整个地占据形整个地占据这这个正方形个正方形,则图则图形就用形就用该该正方形正方形表示表示,否否则则将将该该正方形均分正方形均分为为四个小正方形，每个小四个小正方形，每个小正方形正方形边长为边长为原正方形原正方形边长边长的一半的一半.它它们们是根是根结结点的点的四个子四个子结结点点,可可编编号号为为0,1,2,3。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.
26、03.202320 再考再考查查每个小正方形每个小正方形,若整个被若整个被图图形占据形占据,则标记则标记相相应结应结点点为为1,1,可称可称为为黑黑结结点点。若整个与。若整个与图图形不相交形不相交,则标记则标记相相应结应结点点为为0 0，可称，可称为为白白结结点点。若不是上述两情形，即与若不是上述两情形，即与图图形部分形部分相交，相交，则则称相称相应结应结点是点是灰灰结结点点并将其一并将其一分分为为四。当再分生成小正方形四。当再分生成小正方形边长边长达到达到一个一个象素象素单单位位时时，再分，再分终终止，此止，此时时一般一般应应将仍是灰将仍是灰结结点的改点的改为为黑黑结结点，如此形点，如此形成
27、了平面成了平面图图形的四叉形的四叉树树表示表示 Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202321Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202322TreeCreatetree4(
28、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=Cr
29、eatetree4(V,C4,n-1);elsereturnNULL;Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202323四叉树的存储方式：即四叉树的存储方式：即规则方式、线性方式和一对四方规则方式、线性方式和一对四方式式1.规则四叉树规则四叉树用五个字段的记录来表示树中的每个结点用五个字段的记录来表示树中的每个结点一个用来描述结点的特性，即是灰、黑、白三类结点一个用来描述结点的特性，即是
30、灰、黑、白三类结点中的一种。其余四个用于存放指向四个子结点的指针。中的一种。其余四个用于存放指向四个子结点的指针。缺点缺点：大量的存储空间被指针占用，存储空间利用率：大量的存储空间被指针占用，存储空间利用率差差2.线性四叉树线性四叉树以某一预先确定的次序遍历四叉树形成一个以某一预先确定的次序遍历四叉树形成一个线性表结线性表结构构。RAabcdBCDefgh。其中。其中R表示根，字母右上角加表示根，字母右上角加表示是灰结点。表示是灰结点。优点：节省存储空间空间优点：节省存储空间空间缺点：灵活性差缺点：灵活性差Computer GraphicsComputer GraphicsCollege of
31、 Computer Science and TechnologyCollege of Computer Science and Technology03.03.2023243.一对四式四叉树一对四式四叉树一对四式四叉树的存储结构一对四式四叉树的存储结构每个结点有五个字每个结点有五个字段，其中四个字段用来描述该结点的四个子结点段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的状态，另一个结点存放指向子结点记录存放处的指针。的指针。四个子结点对应的记录是依次连续存放四个子结点对应的记录是依次连续存放的。的。Computer GraphicsComputer Gr
32、aphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202325改进改进的一对四式四叉树的一对四式四叉树(为节省存贮空间为节省存贮空间)：a.增加计算量（紧凑的一对四式四叉树）增加计算量（紧凑的一对四式四叉树）存取相应节点时，先检查其父节点，看在它之前存取相应节点时，先检查其父节点，看在它之前有几个叶节点有几个叶节点b.一个记录增加一个字节一个记录增加一个字节该字节一分为四该字节一分为四,每个子结点对应每个子结点对应2位位,表示它的子表示它的子结点在指针指
33、向区域中的偏移。结点在指针指向区域中的偏移。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202326四叉树优点：四叉树优点：(与象素阵列表示与象素阵列表示)节省存储空间节省存储空间可以用不同精度来表示可以用不同精度来表示与设备无关，便于移植与设备无关，便于移植Computer GraphicsComputer GraphicsCollege of Computer Science and Te
34、chnologyCollege of Computer Science and Technology03.03.202327第第6章章形体的表示及其数据结形体的表示及其数据结构构一一.几何元素几何元素形体的模型主要指的就是包含图形信息所形体的模型主要指的就是包含图形信息所形成的模型。形成的模型。形体本身的构造有一定的层次性，低层部形体本身的构造有一定的层次性，低层部分组合构成上一层部分，而上一层部分组分组合构成上一层部分，而上一层部分组合又可以构成更高一层的部分，依此类推合又可以构成更高一层的部分，依此类推可形成多层结构。其中，每一层中的部分，可形成多层结构。其中，每一层中的部分，我们把它有称
35、为几何元素。我们把它有称为几何元素。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202328(1)点点点点是是0维维几几何何元元素素，有有端端点点、交交点点、切切点点、孤立点等形式。孤立点等形式。曲曲线线、曲曲面面的的应应用用中中会会涉涉及及到到三三种种类类型型的的点：点：型值点型值点相应曲线、曲面必然经过的点。相应曲线、曲面必然经过的点。控控制制点点相相应应曲曲线线、曲曲面面不不一一定定经经
36、过过的的点点，仅用于确定位置和形状。仅用于确定位置和形状。插插值值点点在在型型值值点点之之间间插插入入的的一一系系列列点点，用用于提高曲线曲面的输出精度。于提高曲线曲面的输出精度。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202329不同的空间中点的表示方式不同的空间中点的表示方式(1)一维空间中用一元组一维空间中用一元组t表示；表示；(2)二维空间中用二元组二维空间中用二元组x,y或或x(
37、t),y(t)表示；表示；(3)三维空间中用三元组三维空间中用三元组x,y,z或或x(t),y(t),z(t)表示；表示；点是几何造型中的最基本的元素，曲线、曲点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述。面和其它形体都可以用有序的点集描述。用计算机存储、管理、输出形体的实质就是用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。对点集及其连接关系的处理。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Scien
38、ce and Technology03.03.202330(2)边边边边是是一一维维几几何何元元素素，是是两两个个邻邻面面（正正则则形形体体）或或多多个个邻邻面面（非非正正则则形形体体）的的交交界界。边边分分直直线线边边和和曲曲线线边边。直直线线边边由由起起点点和和终终点点两两端端点点确确定定；曲曲线线边边由由一一系系列列型型值值点点或或控控制制点点表表示示，也也可可以以用显示、隐式方程描述。用显示、隐式方程描述。(3)环环环是有序有向边（直线段或曲线段）组成的面环是有序有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻两条边的封闭边界。环中的边不能相交，相邻两条边共享一个端点
39、。环有内外之分，确定面的最大共享一个端点。环有内外之分，确定面的最大外边界的环称之为外边界的环称之为外环外环，通常其边按，通常其边按逆时针方逆时针方向向排序。而把确定面中内孔或凸台边界的环称排序。而把确定面中内孔或凸台边界的环称之为之为内环内环，其边相应外环排序方向相反，通常，其边相应外环排序方向相反，通常按按顺时针方向顺时针方向排序。排序。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.2023
40、31(4)面面面面是是二二维维几几何何元元素素，是是形形体体上上一一个个有有限限、非非零零的的区区域域，它它由由一一个个外外环环和和若若干干个个内内环环所所界界定定。面面有有方方向向性性，一一般般用用其其外外法法向向量量作作为为该该面面的的正正向向。若若一一个个面面的的外外法法向向量量向向外外，此此面面为为正正；否否则，为反向面。则，为反向面。(5)体体体是体是三维几何元素三维几何元素，由封闭表面围成的空间，由封闭表面围成的空间，它是欧氏空间它是欧氏空间R3中非空、有界的封闭子集，其中非空、有界的封闭子集，其边界是有限面的并集。在实际应用中，要求形边界是有限面的并集。在实际应用中，要求形体是体
41、是正则形体正则形体，即形体上任意一点的足够小的，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。不满足邻域在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。存在悬面、上述要求的形体称为非正则形体。存在悬面、悬边的形体是非正则形体。悬边的形体是非正则形体。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202332正则形体：即形体上任意一点的足够小的邻域正则形体：即形体上
42、任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。不满足上述在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。存在悬面、悬边要求的形体称为非正则形体。存在悬面、悬边的形体是的形体是非正则形体非正则形体。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202333(6)体素体素体体素素是是可可以以用用有有限限个个尺尺寸寸参参数数定定位位和和定定型型的的体体，常有下面三种定义形式。常
43、有下面三种定义形式。一一组组单单元元实实体体长长方方体体、圆圆柱柱体体、圆圆锥锥体体、球球体。体。扫扫描描体体由由参参数数定定义义的的一一条条（一一组组）截截面面轮轮廓廓线线沿沿一一条条（一一组组）空空间间参参数数曲曲线线作作扫扫描描运运动动而而产生的形体。产生的形体。用代数半空间定义的形体用代数半空间定义的形体，在此半空间中点集，在此半空间中点集可定义可定义(x,y,z)|f(x,y,z)0此处的此处的f应是不可约的应是不可约的多项式。多项式。形体的层次结构形体的层次结构点点边边环环面面外壳外壳形体。形体。Computer GraphicsComputer GraphicsCollege o
44、f Computer Science and TechnologyCollege of Computer Science and Technology03.03.202334在几何造型中最基本的几何元素是点在几何造型中最基本的几何元素是点(V)、边、边(E)、面、面(F),这三种元素一共有九这三种元素一共有九种连接关系种连接关系Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202335二二.线框
45、、表面及实体表示（多面体的表示）线框、表面及实体表示（多面体的表示）常用的多面体表示法是常用的多面体表示法是三表表示法三表表示法，即采用三个表，即采用三个表:顶点表顶点表:顶点坐标顶点坐标,用来存放多面体各顶点的坐标用来存放多面体各顶点的坐标;边表边表:两个顶点编号表达一条边两个顶点编号表达一条边,指出哪两个顶点之间有多面体指出哪两个顶点之间有多面体的边的边面表：面表：边的编号表示面边的编号表示面,指出哪些边围成了多面体的表面指出哪些边围成了多面体的表面线框模型：点表，边表线框模型：点表，边表表面模型：点表，边表，面表表面模型：点表，边表，面表实体模型：点表，边表，面表位置确定实体模型：点表，
46、边表，面表位置确定形体确定形体确定三表确定三表确定给出三表给出三表不一定表示一个真实形体不一定表示一个真实形体(正则形体：正则形体：V-E+F=2)满足条件满足条件1.顶点表中的每个顶点至少是顶点表中的每个顶点至少是三边三边的端点的端点;2.边表中的每条边是边表中的每条边是两个多边形两个多边形面的公共边；面的公共边；3.每个多边形面是封闭的等等。每个多边形面是封闭的等等。Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Techn
47、ology03.03.202336Computer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202337xyz100110010000101111011001122334415667788515263748110592116103127114981256783214顶点表顶点表面表面表边表边表Computer GraphicsComputer GraphicsCollege of Computer Scie
48、nce and TechnologyCollege of Computer Science and Technology03.03.202338空间正二十空间正二十面体面体V20,的三的三表表示。表表示。引入一个正引入一个正数数0,它满它满足二次方程足二次方程2-1=0,因因此此=1/2(1+)1.618034。XYZComputer GraphicsComputer GraphicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202339编号编号xyz110
49、112-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,14Computer GraphicsComputer Grap
50、hicsCollege of Computer Science and TechnologyCollege of Computer Science and Technology03.03.202340面编号面编号面编号面编号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，18Computer Graphi