辽大07几何造型.ppt
2023/6/5,计算机图形学演示稿 纪玉波制作(C),1,第七章 几何造型,通过对点、线、面、体等图形元素进行几何变换和并、交、差等集合运算，在计算机内表示、构造三维形体的技术，即为几何造型技术。它是计算机图形学的一个重要组成部分，是CAD/CAM和各种计算机辅助制作技术的基础。几何造型包括曲面造形和实体造型等技术。曲面造形所涉及到的基础内容诸如自由曲线和曲面的表示我们已经讨论过。下面将介绍有关实体造型的基础知识。,蔚斥李糕舆保愤炯享熄郊新犹师环耶挂曹盒拱腥尧惊殉屁彤盏教垮轩懂垒辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),2,7.1 形体在计算机内的表示 如何在计算机内定义和表示由基本图元的集合所决定的形体，是几何造形中最基本的问题。7.1.1 几何元素的定义 在计算机内通常用点、边、面、环、体等作为基本几何元素。1.点 点是0维几何元素，分端点、交点、切点等，如边的端点。但在形体定义中，点不允许孤立地存在于实体内部或外部，只能存在于实体边界上。在自由曲线和曲面的描述中常用三种类型的点，即控制点、型值点、插值点。在计算机内，点用其位置坐标表示。点是几何造型中的最基本元素，用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。,萧线儒昂勤壶理瓣人贸腻涪坟乖嘶综椎柑疾丘蔡凭掌必胎戒识掸碎拢猛蔷辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),3,2.边 边是1维几何元素，由端点或曲线方程定义，如直线边、二次曲线边、三次样条曲线边等。曲线边也可由一系列型值点或控制点表示。3.面 面是2维几何元素，是形体上一个有限、非零的区域，由数学方程定义。面具有方向性，一般用其外法线方向作为面的正向。它用一个外环和若干内环界定其有效范围，面可以无内环，但必须有外环。在几何造型中常分平面、二次面、双三次参数曲面等形式。4.环 环是有序、有向边组成的面上封闭边界，环中各条边不能自交，相邻两条边共享一个端点。环有内环与外环之分，确定面的最大外边界的环称为外环，每个面有且仅有一个外环。若面内有空，则还有内环。通常外环的边按逆时针方向排序，而内环的边按顺时针方向排序。这样定义后，在面上沿一个环前进，其左侧总是面内，右侧总是面外。,融粘怯率臆单孵畴泡休只族朝弦陶咀曳死吗妆启眩敞娱诉灭竖玖劝词晰探辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),4,5.体 体是3维几何元素，是由封闭表面围成的维数一致的有效空间。为了保证几何造型的可靠性和可加工性，要求形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域。把满足这个定义的形体称之为正则形体。形体的正则性限制任何面必须是形体表面的一部分，不能是悬面；每条边有且只能有两个邻面，不能是悬边；点至少和三条边邻接。图1示出几个非正则形体的例子。,有悬面 有悬边 1条边有4个邻面,图1,徽幅哥尖受钵聋刷孩靴承睁恿探驮鳞队我愈弃介发蛹赞茅锋催搁珊豺雹知辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),5,7.1.2 三维形体表示的三种模型 我们可以通过对一个三维空间形体进行近似的描述来表示和构造相应的三维图形。在计算机中常用的是线框、表面和实体三种表示模型。1.线框模型 线框模型是最早用来表示形体的模型，并且至今仍在广泛地应用。线框模型由顶点表示几何位置，相邻顶点连接构成棱边表示几何形状特征。图2是一个长方体的例子，8个顶点和12条棱边表示出这一形体。,图2,匪吁腐淳麦叹荐必力演库男箭榆俞钥些惺俊量最环嘱落雇咙肪托掌嵌何黎辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),6,线框模型是表面模型和实体模型的基础。它具有结构简单、易于理解、数据量少的特点，因此计算机处理速度快。但用线框模型表示形体不充分，无法进行剖切、消隐、明暗等图形处理，也很难表示圆柱体、球体等曲面形体。2.表面模型 表面模型是用有向棱边围成的部分来定义形体表面，由面的集合来定义形体。表面模型是在线框模型的基础上，通过增加由哪些棱边按何种顺序连接等内容定义出表面，从而可以满足面面求交、线面消隐、明暗处理等应用需要。这种模型通常用于构造复杂的曲面形体。表面模型完整地定义了形体的边界，但是形体的实心部分在边界哪一侧并不明确。,峙枚池肥认市拦徘挪咳葫敌揪摸来蚕卵恢赖容糊锯傻翅冶抬楚蘑哈谊创捌辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),7,图3是在线框模型的基础上增加各表面的信息。,图3,腊蝉作准奇逗鞘耶轨蹈摹捞肮既斤脓做和恫腆杜穆讯领靛沤茶尤呜愉首宙辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),8,3.实体模型 如果要处理完整的三维形体，最终必须使用实体模型，实体模型明确定义了表面的哪一侧存在实体。在表面模型的基础上，使用表面的外法线矢量方向来指明实体存在的一侧，例如规定正向指向体外。通常用有向棱边隐含地表示表面的外法线矢量方向。在定义表面时，有向棱边按右手法则取向，沿着闭合的棱边所得的方向与表面外法线矢量方向一致。图4是在表面模型的基础上增加定义了表面外环的棱边方向。用此方法还可检查形体的拓扑一致性，拓朴合法的形体在相邻两个面的公共边界上，棱边的方向正好相反。,图4,珐价赌抓彻超磨入蜒慧桓暗拆讨箕关凌剁皂设蜗胳碎凿蜘迎剂满畅瓶势为辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),9,4.三种模型的数据结构 线框模型的数据信息是顶点和棱边，其数据结构一般使用两组数据，或称两表结构。一张表表示顶点，一张表表示棱边。以图2为例，假定长方体的长是2，宽是1，高是1，则数据组织如表1和表2所示。表面模型是在线框模型的基础上增加定义表面信息，所以其数据结构也是在线框模型两表结构的基础上增加一面表，如表3所示。,毕随域尧友谊背沤正却穿花即曙壕沉酮喜脖些阁弘眠贼乒酷显佐岗菱袱沃辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),10,实体模型是在表面模型的基础上增加定义了表面的哪一侧存在实体,并且使用有向边表示表面的外法线矢量方向。不同于表面模型的是，实体模型在定义表面时，需要按右手法则取向安排组成表面的边顺序。表3中边的顺序已经符合这一要求，也可以作为实体模型的面表。三个表中除了所列的基本几何数据外，还可以扩充增加属性信息。比如边表和面表中可以包括颜色属性，面表中还可包括透明度、纹理特征等。对上述三表还可以进行数据的一致性和完整性检验，内容诸如每个顶点至少是二条边的端点；每条边至少是一个面的组成部分；每个面的边界都是封闭的；每个面至少有一条同其它面的公共边等。,裂冰懒硅堆椎严容婚箕掌瞥达咨苇硬粹钧甥么避幕崎翠瓣可丸嗓逐炎鹃挨辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),11,7.2 实体模型的构造 前面介绍的表示形体的线框、表面和实体模型是一种广义的概念，并不反映形体在计算机内部所用的具体表示方式。为适应不同的形体情况和应用要求，已发展了多种具体的实体造型方法。目前常用有扫描表示法、边界表示法、构造实体几何法和八叉树表示法等。7.2.1 扫描表示法 扫描(Sweeping)表示法是一个得到较广泛应用的表示三维物体的方法。它的基本原理十分简单，即空间中的一个点，一条线或一个面沿着某一路径移动时，所形成的轨迹将产生一个一维的、二维的或三维的图形。用扫描法表示或形成一个形体需要定义作扫描运动的曲线或曲面，以及扫描运动的路径。在三维形体的表示中，应用得最多的是平移扫描法和旋转扫描法两种。,入串递翱绩旨雍衫凸咙吞亮部祖歹压晌书墅敲围颠辛滇感勋激话捐稠史钙辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),12,平移扫描法是所定义的扫描体沿着直线路径作移动而形成扫描轨迹。如图5中是一个平移扫描例子，扫描体是一个圆，扫描路径是一条直线，扫描后得到一个圆柱体。,图5,光势锐髓栓高介陪督欺变肇废吏予桃忆阔绥裁些练衍炎该闪素疽围脯岭喻辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),13,旋转扫描法是所定义的扫描体绕某一轴线旋转某一角度形成扫描轨迹。如图6中是一条曲线绕垂直轴线旋转后得到的三维形体。旋转扫描法构成物体的都是轴对称的物体。,图6,踞汹臼比共消汇卧曙恃疵押爵沮霹眨秆耶训搁降聪掀攻歼沦疵晓岩雇橙蛹辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),14,一般地,可以沿任何路径来作扫描移动。对旋转扫描可以沿从0到的角范围内的路径移动。对非圆形路径，可以给定描述路径的曲线函数和沿路径移动的距离。另外可以沿扫描路径变化曲线或曲面的形状和大小及相对于扫描路径的方向。在扫描表示法中，只需定义二维平面及曲线，三维空间的实体和曲面就可分别由二维平面及曲线通过扫描来实现。这对于许多领域的实体造型是很方便的，因此，扫描表示法在许多造型系统得到应用。,洪伍眼趟弱鄂毫命删俭美责舔冀昼索巾梗商羔铡椎肤拖焙虚逮续姻丙记抿辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),15,7.2.2 边界表示法 一个形体可以用面、环、边、点来定义其位置和形状,这些面、环、边、点构成形体的边界。如图2中，长方体由六个面围成，对应有六个环，每个环由四条边组成，每条边又由两个端点定义。一个形体的边界将该形体划分为形体中的点和形体外的点，它也是形体与周围环境之间的分界面。很显然，只要完整地定义了形体的边界，那么该形体就被唯一定义了。边界表示法（Boundary Representation，B-Rep）就是以物体边界为基础定义和描述几何形体的方法。所描述的物体由有限个面构成，每个面可以由有限条边围成的有限个封闭区域定义。用边界表示法描述实体，要求其表面必须满足一定条件，如连通、有界、可定向、不自交和闭合连接等。,腹扑此讲驰胀距娠奠衡征狭准跺栏居奴谤交控蛰氏怖票旱蜒店栈麓码毁务辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),16,由于边界是以面、边、点为基础的，所采用的数据结构是否便于对实体进行面、边、点的存放、查找或修改，是一个十分关键的问题。边界表示详细记录了构成形体所有的几何信息和拓扑信息。几何信息描述形体的大小、尺寸、位置、形状等，而拓扑信息则描述形体的表面、棱边、顶点等相互间的连接关系，二者构成一个有机的整体，共同形成对形体的完整的描述。有了几何信息和拓扑信息，可以直接对构成形体的各个面、边、顶点的参数进行存取，有利于以面、边、点为基础的各种几何运算和操作。边界表示法中最为典型的数据结构是翼边结构。,呵辗抒鸟类渭辜晦妄麓鲤跨舵矛胸祭宇罐坷恼厅赐稗卑造步嫡寥俺谗鼓鳖辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),17,在以表面、棱边、顶点组成形体的三要素中，翼边结构以边为核心来组织数据,如图7所示。,图7,救郎草浩脉檬亡萄叹福拧房款沙嘿伎栈促冠春呸逊猖霜略给贰宦供倍哀雕辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),18,与一条边相连的有这条边的上下两个顶点，左右两个邻面以及上下左右四条邻边。棱边的数据结构中包含有2个顶点指针，分别指向该边的起点和终点，每一个顶点也有一个指针，反过来指向以该顶点为端点的边。棱边被看作一个从起点指向终点的有向线段，如果形体是多面体，其棱边为直线段，由它的起点和终点唯一确定。当形体为曲面体时，其棱边可能为一曲线段，这时必须增添一项指针来指向所在曲线边的数据。此外，在翼边结构中还设有两个环指针，分别指向棱边所邻接的两个表面上的环。由这种边环关系就能确定棱边与相邻面之间的拓扑关系，为了能从棱边出发搜索到所在的任一闭环上的其它棱边，数据结构中又增设四个指向边的指针，它们分别是左上边、左下边、右上边、右下边。如右下边表示该棱边在右面环中沿逆时针方向所连接的下一条棱边，而左上边则为棱边在左面环中沿逆时针方向所连接的下一条边等。每一个面也有一个指针，反过来指向它的一条边。通过这种翼边结构，可以方便地查找各元素之间的连接关系。,前乃鞋哗辐皿耳号狄啼科儿足警企禾狞属玫涣含头那坊修澄厩鲁爸娄维目辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),19,边界表示法的优点是，表示形体的点、边、面等几何元素是显式表示的，比较容易确定几何元素间的连接关系。有关形体的操作运算可以直接用面、边、顶点的数据来实现，使得绘制形体的速度较快。边界表示法的缺点是数据结构复杂，需要大量的存储空间，修改形体的操作比较难以实现，对实体的整体描述能力弱。,7.2.3 构造实体几何法(CSG)构造实体几何法(Constructive Solid Geometry，CSG)，是在实体的表示、构造中得到广泛应用的一种方法。它的基本思想是将简单几何形体（体素）通过正则集合运算组合成所需要的复杂实体。因此，这种方法称为构造实体几何法。,胜境济喻姑鹿述雷屁谨详传乃峪畏钳惹峭猖咨伟过执弄刁绵腺朋辗损名洱辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),20,1.正则集合运算 构造实体几何法中采用的集合运算包括并、交、差运算，但对两个有效实体进行普通的集合运算产生的结果并不一定是有效实体，即可能产生悬边、悬面等。如图8(a)所示,设二维平面上有物体A及B，将它们如图8(b)所示的位置作交运算。如果以通常的集合运算规则求，则得到图8(c)中的结果，它有一条悬边，不具有维数的一致性，所以不符合正则形体的条件，不是有效的二维形体。图8(d)中的结果才是一个有效的二维形体。,辖使晋闹呆钝努导臻萧析尽意彭画蛛肮皋乒尾诀酋瘤巾称凿泛贵辙寇楞蝴辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),21,为此，把能够产生正则形体的集合运算称为正则集合运算。其相应的正则集合算子以*(正则交)、*(正则并)、-*(正则差)表示。首先，正则形体的表面具有连通性、有界性、非自相交性、可定向性和闭合性。三维正则形体可以用它的边界面及内部来表示，即：G=bG,iG 式中，G为正则形体，bG为G的边界面，iG为G的内部。在三维空间中，给定一个实体G后，空间点集就被分为三个子集，一是该实体的内部点集，二是该实体边界上的点集，三是该实体之外的点集。若给定一个实体G及一个有界面S，那么S也可能被G分割为三部分，即位于G内的面，位于G外的面以及位于G的边界上的面。以C(S,G)表示这三种关系，P代表空间的点，则有 C(S,G)=S in G,S out G,S on G,悦群韵瓦百蓬教汽藉条父儒笨迢迎陷授专花淤矢套颓磐成会琢袜昔关晤向辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),22,其中 S in G=P|PS,PiG S out G=P|PS,PG S on G=P|PS,PbG 由于实体G的边界面是可定向的，有界面S也是可定向的，比如按右手法则取法线方向。以-S表示有界面S的反向面，即-S和S是同一个有界面，只是有界面-S上任何一点的法向均和有界面S上该点的法向相反。也就是说，如有界面S在P点的法向为NP(S)，那么，有界面-S在P点的法向就是-NP(S)。同样-bG表示G边界面的反向。于是可以进一步分为两种情况：有界面S在G边界面上同为正向的点的集合和一个为正向一个为反向的点的集合，即 S on G=S on(bG),S on(-bG),恤朵猛屎蝎裹扭棕细兴雪驶医角丫扬吗务癸鬃微因甸典盂幸傲板隔殉倒裂辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),23,其中 S on(bG)=P|PS,PbG,Np(s)=Np(bG)S on(-bG)=P|PS,PbG,Np(s)=-Np(bG)因此，C(S,G)可以修改为 C(S,G)=S in G,S out G,S on(bG),S on(-bG)由于正则形体可以由它的边界来表示，得到了它的边界，也就定义了该形体。设A和B为两个正则形体，则正则集合运算算子定义如下 b(A*B)=bA out B,B out A,bA on bB b(A*B)=bA in B,B in A,bA on bB b(A-*B)=bA out B,-(bB in A),bA on(-bB),黄拟划岿撼孙闺订囤拇媒鞋校陕诅滦橇清菏羚跪侯什蒙顽庇投包瞧夜模滞辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),24,可以证明，通过上面定义的正则集合算子运算后得到的新形体仍为正则形体，运算的结果定义出新形体的边界。最后一式中-(bB in A)表示得到点集(bB in A)后取反向作为新形体的有向边界。对于二维的情况，其形体的边界由直线段或曲线构成。运算是指两边界线走向相同的部分，bA on(-bB)是指两边界线走向相反的部分。仍然用图8的例子来说明正则集合算子运算，其结果如图9表示。图中实线表示运算后所生成的新形体边界。,图9,筒呼溉唁烽舟炳萝某啥硒瘟稼凋瓢沟躁程遮附跃禁浩载辗途垮屉丽曝稽担辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),25,2 实体模型的构造 构造实体几何法利用上面所述的正则集合运算，将简单几何形体(体素)组合成所需要的复杂实体。在这一方法中，常用的体素有长方体、圆柱体、圆锥体、圆台体、环、球和封闭样条曲面等。基本体素本身可用建模算法、扫描方法或样条方法构造形成。图10表示了用构造实体几何法形成新的实体的例子。在图中，两个不同的长方形作并操作后再同一个圆柱体作差操作，得到图中的实体。,喷毯轧迢捉际请厨嗽绽流胁步雹避苞犊裂宿锁蓬建阑港衍藻表勤找纲轴伊辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),26,在实体构造过程中，通过基本体素经集合运算得到新的形体，它又可以继续用来构造形成另一形体，这样利用基本体素和每一步新创建形体的组合，不断构造直到形成最后的实体。实体的构造过程可以用一棵二叉树（称为CSG树）来描述。如图11所示,图11,幻汗菊梗尧腺擎祥橙非图月皖前漏逐筑膝谤夯矿尧剥安蜕囊乃取刘旁吱顷辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),27,7.2.4 八叉树表示法 八叉树(Octrees)表示法是将实体所在空间进行递归划分，分割成由立方体组成的网格。于是，一个实体可以由它所占用的立方体序列来表示。当分割后的立方体越来越小时，就逐步接近用空间点的集合来表示实体了。三维空间的八叉树表示方法是二维空间四叉树（Guadtree）表示方法的扩展。四叉树表示是将二维区域递归细分成小方域为基础的，每个节点代表平面上的一个小方域。如图12所示。,图12,柄少宙萎鄂榜刘藉掀愧鞘窖娟乾冷季哗爪旧埂嗣沮灵窃旗驼收肛痊贡弟退辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),28,三维空间的划分描述使用八叉树表示。类似于二维空间的四叉树表示，八叉树表示将三维空间区域递归地划分成8个子空间，图13是其示意图。八叉树表示的每个节点对应于一三维子空间，这种表示方法可以提供形体内部信息，便于形体截面显示的应用需要。,图13,倾评约灸肚酱冲迟伐期昼慑优练弗谣肾颁阜珊撩扛哈孽臂专铂灭差乱耶冬辽大07几何造型辽大07几何造型,2023/6/5,计算机图形学演示稿 纪玉波制作(C),29,一旦对一实体建立起八叉树表示，可将各种操作应用到该实体。比如对一个八叉树进行平移、旋转和缩放等几何变换，可以产生一个新的八叉树。对同一空间区域不同实体的两个八叉树表示，可进行并、交、差等集合运算，产生一个新的八叉树。用八叉树表示空间实体的优点是数据结构简单划一，易于实现实体之间的集合运算，易于计算实体的几何特性，由于具有层次结构，易于实现消隐。但这种方法不是一种精确的表示法，其近似程度完全取决于分割精度，与几何形体的复杂程度无关。将八叉树表示转换为精确的边界表示是困训摹谑堤逶型系统中，一般将它用作一种辅助表示形式。,呕潜棠窥良焚酒孽佑纷碴孜帘膳溪兰泛贴览愤梗赎阵绵秸煽召茶绩陀獭犊辽大07几何造型辽大07几何造型,
