计算机图形学教程（第5版 微课版）课件 第5、6章 图形变换与裁剪、实体几何造型基础

第五章

图形变换与裁剪计算机学院苏小红二维图形的显示流程计算机学院苏小红5.1窗口视图变换

1.窗口和视图区用户坐标系（worldcoordinatesystem，简称WC）设备坐标系（devicecoordinatesystem，简称DC）窗口区（window）视图区（viewport）计算机学院苏小红2.窗口到视图区的变换窗口区与视图区间的映射关系：窗口区中的任一点(xw,yw)

与视图区中的任一点(xv,yv)存在如下对应关系：（5-1）（5-2）XwOwWxlWxrYwWybWyt窗口(xw,yw)YuXuOuVxlVxrVybVyt视图区(xv,yv)窗口与视图区的对应关系计算机学院苏小红

（5-3）（5-4）由式（5-1）和式（5-2）可分别解得：令有（5-5）

（5-6）

计算机学院苏小红5.2二维图形几何变换5.2.1二维图形几何变换的原理二维图形由点或直线段组成直线段可由其端点坐标定义二维图形的几何变换：对点或对直线段端点的变换计算机学院苏小红1.平移变换（translation）平行于x轴的方向上的移动量平行于y轴的方向上的移动量

5.2.2几种典型的二维图形几何变换xy平移变换（5-7）（5-8）计算机学院苏小红平行于x轴的方向上的缩放量平行于y轴的方向上的缩放量2.比例变换（scale）指相对于原点的比例变换

yx相对于原点的比例变换相对于重心的比例变换yx重心（5-10）（5-9）计算机学院苏小红比例变换的性质当时，变换前的图形与变换后的图形相似当时，图形将放大，并远离坐标原点当时，图形将缩小，并靠近坐标原点当时，图形将发生畸变计算机学院苏小红3.旋转变换（rotation）

点P绕原点逆时针转θ度角（设逆时针旋转方向为正方向）（5-11）（5-12）将式（5-11）代入式（5-12）得：（5-13）（5-14）yx旋转变换计算机学院苏小红5.2.3齐次坐标（homogeneouscoordinates）技术

1.齐次坐标技术的引入平移、比例和旋转等变换的组合变换处理形式不统一，将很难把它们级联在一起。

2.变换具有统一表示形式的优点便于变换合成便于硬件实现3.齐次坐标技术的基本思想

把一个n维空间中的几何问题转换到n+1维空间中解决。计算机学院苏小红4.齐次坐标表示齐次坐标表示不是唯一的

有n个分量的向量有n+1个分量的向量哑元或标量因子规格化的齐次坐标计算机学院苏小红5.基本几何变换的齐次坐标表示

平移变换

比例变换旋转变换：6.无穷远点或无穷远区域的齐次坐标表示

时，齐次坐标表示一个n维的无穷远点逆时针为正

计算机学院苏小红5.2.3常用的二维几何变换

1.对称变换（symmetry）（反射变换或镜像变换）（1）相对于y轴对称（2）相对于x轴对称oyx对称变换（1）yxo对称变换（2）计算机学院苏小红（3）相对于原点对称（即中心对称）（4）相对于直线y=x对称oxy对称变换（3）xyoy=x对称变换（4）计算机学院苏小红（5）相对于直线y=-x对称xyoy=-x对称变换（5）计算机学院苏小红2.错切变换（shear）（1）沿x轴方向关于y轴错切将图形上关于y轴的平行线沿x方向推成θ角的倾斜线，而保持y坐标不变。△x

错切变换（1）yx计算机学院苏小红（2）沿y轴方向关于x轴错切将图形上关于x轴的平行线沿y方向推成Ψ角的倾斜线，而保持x坐标不变。

错切变换（2）yx△y计算机学院苏小红问题：如何实现复杂变换？变换分解变换合成5.3.3二维组合变换计算机学院苏小红1.相对于任意点（x0,y0）的比例变换对任意点比例变换的步骤：（1）平移变换（2）相对于原点的比例变换（3）平移变换

当（x0,y0）为图形重心的坐标时，这种变换实现的是相对于重心的比例变换。计算机学院苏小红令任意点比例变换示意图平移平移比例则有计算机学院苏小红2.绕任意点（x0,y0）的旋转变换绕任意点旋转变换的步骤：（1）平移变换（2）对图形绕原点进行旋转变换（3）平移变换

θ(x2,y2)(x3,y3)(x0,y0)θOxy(x1,y1)(x4,y4)相对于任意点(x0,y0)的旋转变换计算机学院苏小红任意点旋转变换示意图平移平移旋转令则有计算机学院苏小红变换的结果与变换的顺序有关（矩阵乘法不可交换）变换的固定坐标系模式相对于同一个固定坐标系先调用的变换先执行，后调用的变换后执行计算机学院苏小红三维几何变换（1/7）三维齐次坐标(x,y,z)点对应的齐次坐标为标准齐次坐标(x,y,z,1)右手坐标系

xyz计算机学院苏小红三维几何变换（2/7）平移变换

放缩变换计算机学院苏小红三维几何变换（3/7）旋转变换:右手螺旋方向为正绕x轴yxyzz’y’zoox轴指向纸外绕轴旋转角计算机学院苏小红三维几何变换（4/7）绕z轴绕y轴计算机学院苏小红三维几何变换（5/7）对称变换关于坐标平面xy的对称变换计算机学院苏小红三维几何变换错切变换zyxzyxzyxzyxzyxzyx三维错切变换沿z含x错切沿z含y错切沿y含x错切沿y含z错切沿x含y错切

沿x含z错切计算机学院苏小红三维几何变换（7/7）三维变换的一般形式哈尔滨工业大学计算机学院苏小红32第五章

图形变换与裁剪

投影变换计算机学院苏小红33基本内容1三维图形的基本问题平面几何投影平行投影透视投影34三维图形的基本问题（1/5）显示器屏幕、绘图纸等是二维的显示对象是三维的解决方法----投影三维显示设备正在研制中1.在二维屏幕上如何显示三维物体？35三维图形的基本问题（2/5）2.如何表示三维物体？二维形体的表示----直线段,折线,曲线段,多边形区域二维形体的输入----简单（图形显示设备与形体的维数一致）三维形体的表示----空间直线段、折线、曲线段、多边形、曲面片三维形体的输入、运算、有效性保证----困难解决方法----各种用于形体表示的理论、模型、方法36三维图形的基本问题（3/5）3.如何反映遮挡关系？物体之间或物体的不同部分之间存在相互遮挡关系遮挡关系是空间位置关系的重要组成部分解决方法----消除隐藏面与隐藏线37三维图形的基本问题（4/5）何谓真实感图形？逼真的示意的人们观察现实世界产生的真实感来源于空间位置关系----近大远小的透视关系和遮挡关系光线传播引起的物体表面颜色的自然分布解决方法建立光照明模型开发真实感图形绘制方法4.如何产生真实感图形38三维图形的基本问题（5/5）三维图形的基本研究内容投影三维形体的表示消除隐藏面与隐藏线建立光照明模型、研究真实感图形绘制方法39照像机模型与投影

如何投影?生活中的类比--如何拍摄景物？拍摄过程选景取景--裁剪对焦—参考点按快门--成像移动方式移动景物移动照相机两个坐标系平面几何投影（1/17）40投影—照相机模型选定投影类型

设置投影参数–拍摄方向、距离等三维裁剪

–取景投影和显示

–成像简单的三维图形显示流程图二平面几何投影（2/17）41平面几何投影及其分类

投影将n维的点变换成小于n维的点

将3维的点变换成小于3维的点投影中心(COP:CenterofProjection)视觉系统—观察点、视点电影放映机—光源投影面不经过投影中心平面--照相机底片曲面—球幕电影,视网膜平面几何投影（3/17）42平面几何投影（4/17）投影线从投影中心向物体上各点发出的射线

直线—光线曲线—喷绘平面几何投影

投影面是平面投影线为直线投影变换投影过程投影的数学表示43平面几何投影（5/17）投影分类投影中心与投影平面之间的距离为无限

投影中心与投影平面之间的距离为有限

44平面几何投影（6/17）透视投影平行投影45平面几何投影（7/17）平行投影

投影中心与投影平面之间的距离为无限是透视投影的极限状态投影方向投影平面46平面几何投影（8/17）正投影与斜投影正平行投影斜平行投影47平面几何投影（9/17）三视图：正视图、侧视图和俯视图

yzx主视图俯视图侧视图图3一个直角棱台的三视图48解决：投影平面不垂直于任何一个坐标轴——正轴测投影

yxz图5正轴测投影平面的定义投影方程：平面几何投影（10/17）49120°120°120°(a)正等轴测yzx投影平面三个单位向量将投影成三个长度相等的平面向量，即三根坐标轴有相同的变形系数正方体的正等轴测投影

平面几何投影（11/17）50正方体的正轴测投影(c)正三轴测yzx投影平面(b)正二轴测投影平面yzx平面几何投影（12/17）51透视投影投影中心与投影平面之间的距离为有限参数：投影方向，距离例子：室内白炽灯的投影，视觉系统特点：产生近大远小的视觉效果，由它产生的图形深度感强，看起来更加真实。平面几何投影（13/17）52

透视投影投影方程yxz投影中心dx’y’P’Pyxz投影平面一点透视平面几何投影（14/17）53灭点的个数?灭点：不平行于投影平面的平行线，经过透视投影之后相交于一点，称为灭点.yxzz轴灭点图7正方体的一点透视及其灭点空间平行线可认为是相交于无穷远点，灭点可以看成是无穷远点经透视投影后得到的点灭点的位置?无穷远点灭点平面几何投影（15/17）54一点透视两点透视三点透视主灭点:平行于坐标轴的平行线产生的灭点。一点透视两点透视三点透视主灭点的个数由什么决定?平面几何投影（16/17）55平面几何投影（17/17）56第五章图形变换与裁剪（三）

5.5二维线段裁剪苏小红计算机科学与技术学院哈尔滨工业大学575.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法2多边形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

581.直线段裁剪(1/18)裁剪（clipping）的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交裁剪与覆盖的区别591.直线段裁剪(2/18)裁剪窗口矩形、圆形、一般多边形被裁剪对象线段、多边形、曲线、字符设计裁剪算法的核心问题效率高，速度快601.直线段裁剪(3/18)把直线当作点的集合，逐点裁剪点(x,y)在窗口内的充分必要条件是：

问题：极其费时，精度不高。611.直线段裁剪(4/18)把直线当作一个整体来裁剪矩形裁剪窗口：

[xmin，xmax]

[ymin，ymax]待裁剪线段：前提：任何平面线段在凸多边形窗口进行裁剪后，落在窗口内的线段不会多于1条。621.直线段裁剪(5/18)待裁剪线段和窗口的关系完全落在窗口内,完全落在窗口外,部分在内，部分在外.635.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法64直接求交算法直线与窗口边都写成参数形式，求参数值。1.直线段裁剪(6/18)655.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法66Cohen-Sutherland算法1.直线段裁剪(7/18)为提高效率，该算法强调：快速判断情形(1)(2)；减少情形(3)的求交次数和求交所需的计算量。待裁剪线段和窗口的关系完全落在窗口内,完全落在窗口外,部分在内，部分在外.67Cohen-Sutherland算法算法步骤：判别线段两端点是否都落在窗口内，如果是，则线段完全可见，转至第4步；判别线段是否为显然不可见，如果是，则裁剪结束，转至第4步；求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第1步处理，结束裁剪过程是递归的。1.直线段裁剪(8/18)68关键问题：如何快速判别完全可见和完全不可见线段？解决方法——编码：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；Cohen-Sutherland

算法1.直线段裁剪(9/18)11100000011100000011100000011100000069端点编码：定义为它所在区域的编码快速判断“完全不可见”

线段两端点编码的逻辑“与”运算结果非零

，则完全不可见。Cohen-Sutherland算法1.直线段裁剪(10/18)所以也称为编码裁剪算法70逐个端点判断其编码ClCtCrCb中各位是否为“1”，若是，则需求交。最坏情形：线段求交四次。对于那些部分可见又部分不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交？Cohen-Sutherland算法1.直线段裁剪(11/18)71

1）特点：用编码方法可快速判断线段-——

完全可见或完全不可见。

2）特别适用两种场合：大窗口场合；窗口特别小的场合（如：光标拾取图形时，光标看作小的裁剪窗口）1.直线段裁剪(12/18)Cohen-Sutherland算法725.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法

中点分割裁剪算法梁友栋-Barsky算法73中点分割法基本思想：利用对分搜索思想搜索交点从P1点出发找出距P1最近的可见点从P2点出发找出距P2最近的可见点不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止取中点Pm=(P1+P2)/2。P2P1从P1点出发找距P1最近的可见点PmP1用P1Pm代替P1P2P2P2用PmP2代替P1P2PmP11.直线段裁剪(13/18)741.直线段裁剪(13/18)优点：算法原理和编码裁剪是一致的，不同之处在于用移位运算代替求交计算适合硬件实现中点分割法755.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法

梁友栋-Barsky算法76Liang-Barsky裁剪算法

P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分1.直线段裁剪(14/18)基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段77Liang-Barsky裁剪算法

直线L与区域的交：1.直线段裁剪(15/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口

78存在可见线段的充要条件即不为空集。1.直线段裁剪(16/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口。

79Liang-Barsky裁剪算法

1.直线段裁剪(17/18)向x轴投影，得到可见线段端点的x坐标变化范围

左端点x坐标右端点x坐标RS,AB,TU三条线段的交集的端点坐标等价于求三条线段的左端点的最大值，右端点的最小值

y坐标可由将x坐标代入直线方程计算得到P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分URTS80Liang-Barsky裁剪算法AB有可见部分的充要条件也可表示为1.直线段裁剪(18/18)P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分URTS815.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法2多边形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

822.多边形裁剪（Ploygonclipping）-1/3错觉：多边形裁剪是直线段裁剪的组合？新的问题：图1因丢失顶点信息而去法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它8312123(a)(b)(c)AB裁剪后的多边形顶点形成的几种情况分裂为几个多边形2.多边形裁剪-2/384关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列常用算法

Sutherland_Hodgman算法

Weiler-Atherton算法

2.多边形裁剪-3/385Sutherland-Hodgman算法-1/4分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：左边的结果是右边的开始。亦称逐边裁剪算法86Sutherland-Hodgman算法-2/4内侧空间与外侧空间多边形的边与半空间的关系

线段与当前裁剪边的位置关系可见一侧窗口(a)输出Pi+1当前裁剪边Pi+1Pi可见一侧窗口(a)无输出当前裁剪边Pi+1Pi可见一侧窗口(a)输出I当前裁剪边Pi+1Pi可见一侧窗口(a)输出I和Pi+1当前裁剪边Pi+1PiII87Sutherland-Hodgman算法-3/4裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。几点说明：裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口88Sutherland-Hodgman算法-4/4

存在的问题逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？

逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几个多边形沿边框产生多余的线段？图6逐边裁剪法对凹多边形裁剪时可能出现的问题321876954103217654108932174108956原图对左边裁对顶边裁32174108956对右边裁对底边裁Demo89Weiler-Atherton算法-1/7裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为SP裁剪多边形：裁剪窗口，记为CP90约定：SP与CP均用它们顶点的环形链表定义外边界取顺时针方向内边界取逆时针方向使得沿多边形的边走动，其右边为多边形的内部。Weiler-Atherton算法-2/7C2C1C3C4C8C7C5C6I1I8I2I3I4I5I6I791SP和CP把二维平面分成两部分。内裁剪：SP∩CP外裁剪：SP-CPWeiler-Atherton算法-3/7裁剪结果区域的边界由两部分构成：SP的部分边界CP的部分边界且在交点处，边界发生交替即由SP边界转至CP边界或由CP边界转至SP边界

92Weiler-Atherton算法-4/7如果SP与CP有交点，则交点成对出现，它们被分为如下两类：进点：SP边界由此进入CP

如，I1,I3,I5,I7,I9,I11出点：SP边界由此离开CP

如，I0,I2,I4,I6,I8,I10

93Weiler-Atherton算法-5/7由任一个进点出发，沿SP的边，跟踪检测其与CP的交点（前交点），并判断该交点是进点还是出点。若是进点：则沿SP边所示方向收集顶点序列。若是出点：则从此点开始，检测CP的边所示方向收集顶点序列。如此交替沿两个多边形的边行进。直至回到跟踪的起始点为止。94Weiler-Atherton算法-6/7C2C1C3C4S1S2S3S4S5S6I1I2I3I4I5I6I7I8裁剪多边形CP主多边形SP算法裁剪后所生成的多边形为I1I2I3S3I4I5I6I7S6I8I1主多边形表裁剪多边形表S1S2I1S3S4S5S6I2I3I4I5I6I7I8C1C2I3I4C4I8I1I2I5C3I5I6S1I7C1开始结束95Weiler-Atherton算法-7/7C2C1C3C4C8C7C5C6S2S1S3S4S8S7S5S6I1I8I2I3I4I5I6I7主多边形表裁剪多边形表S1S2I1I4S4S6I5I2I3S3S1S5S7I6S8I7I8S5C1C2C3C4I4I5I1I8C1C5C5C6I2I3I6C7C8I7算法裁剪后所生成的多边形为I1I2I7I8I1和I3I4I5I6I3

裁剪多边形CP主多边形SP开始开始结束结束苏小红哈尔滨工业大学计算机科学与技术学院第6章实体几何造型基础实体造型（SolidModeling）几何造型技术第一代：手工绘制工程图第二代：二维计算机绘图第三代：三维线架系统第四代：曲面造型第五代：实体造型哈尔滨工业大学计算机学院苏小红97三维实体的表示（1/7）模型分类哈尔滨工业大学计算机学院苏小红98完全以数据描述规则形体的建模方法边界表示分解表示构造表示以过程和控制参数描述不规则形体的建模方法随机插值模型迭代函数系统L系统粒子系统动力系统三维实体的表示（2/7）过程模型哈尔滨工业大学计算机学院苏小红99包括----随机插值模型、迭代函数系统、L系统、粒子系统、复变函数迭代等以一个过程和相应的控制参数描述例如用一些控制参数和一个生成规则描述的植物以一个数据文件和一段代码的形式存在三维实体的表示（3/7）数据模型哈尔滨工业大学计算机学院苏小红100完全以数据描述例如用以8个顶点表示的立方体以中心点和半径表示的球以数据文件的形式存在包括----边界表示、分解表示、构造表示等三维实体的表示（6/7）线框模型哈尔滨工业大学计算机学院苏小红101相邻顶点连接构成棱边表示几何形状特征形体表示成一组轮廓线的集合，只需建立三维线段表数据结构简单、处理速度快所构成的图形含义不确切，与形体之间不存在一一对应关系，有二义性不能计算面积、体积等物理量，不便进行光照或消隐处理，不适合真实感显示和数控加工----物体的骨架图6-8用线框模型表示的有二义性的物体可以有三种不同的理解，从三个方向中的一个方向打一个方孔

三维实体的表示（7/7）表面模型哈尔滨工业大学计算机学院苏小红102----物体的皮肤用有向棱边围成的部分来定义形体表面，由面的集合来定义形体形体与其表面一一对应，避免了二义性能够满足真实感显示和数控加工等需求能够计算面积，表达物体的表面形状，只有面的信息，形体信息不完整进行剖切操作时，内部为空洞，无法计算和分析物体的整体性质（如体积、重心等），限制了在工程分析方面的应用在面模型上打孔，内部为“空洞”三维实体的表示（7/7）实体模型哈尔滨工业大学计算机学院苏小红103----”有血有肉”的物体模型主要是明确定义了表面的哪一侧存在实体，在表面模型的基础上，使用表面的外法线矢量方向来指明实体存在的一侧，例如规定正向指向体外。通常用有向棱边隐含地表示表面的外法线矢量方向在定义表面时，有向棱边按右手法则取向，沿着闭合的棱边所得的方向与表面外法线矢量方向一致。用此方法还可检查形体的拓扑一致性，拓朴合法的形体在相邻两个面的公共边界上，棱边的方向正好相反。包含描述实体所需的较多信息，如几何信息、拓扑信息，表示完整而无歧义。实现所有的CAD/CAM任务，保证CAD/CAM的自动化三种表示模型的功能比较哈尔滨工业大学计算机学院苏小红104多面体模型（1/10）每个多边形的数据被存储在多边形数据表中多边形数据表可分两组：几何表包括物体的几何数据（如顶点坐标等）和用来标识多边形表面空间取向的参数（如表面外法线方向）属性表包括物体透明度、表面反射系数以及纹理特征参数 哈尔滨工业大学计算机学院苏小红105多面体模型（2/10）通常以层次结构存储哈尔滨工业大学计算机学院苏小红106图6-1绘制多面体所需的层次数据结构信息表面表0表面表1…多边形表0多边形表1…V0,Nv0V1,Nv1V2,Nv2V3,Nv3…Np0Np1…表面表数组多边形表面数组顶点数组多边形法向量数组Nv3Nv0Nv1Nv2V3V0V1V2Np0(b)多边形信息(a)层次数据结构信息在Phong明暗处理算法中用到在背面剔除中用到多面体模型（3/10）缺点：相邻多边形的共享边在上述数据结构中没有得到显式表达，这使得同一条边在绘制过程中可能被处理两次。哈尔滨工业大学计算机学院苏小红107多面体模型（4/10）基于边的表示边数组的每个元素包含4个指针，分别指向对应边的两个顶点和它邻接的两个多边形法向量哈尔滨工业大学计算机学院苏小红108图6-2基于边的绘制方法所需的数据结构信息(a)多边形信息边数组顶点数组法向量数组V0,Nv0V1,Nv1V2,Nv2V3,Nv3…1,2,2,00,1,1,03,0,1,02,3,2,03,1,2,1…NULLNp1Np2…V0Nv3Nv0Nv1Nv2V3V1V2Np1Np2E1E0E2E3E4(b)基于边的数据结构信息多面体模型（8/10）多面体模型的优点数据结构相对简单集合运算、明暗图的生成和显示速度快缺点：虽然多面体可以任意精度逼近任意复杂的曲面物体，但它毕竟是曲面物体的一种近似逼近表示，存在误差

哈尔滨工业大学计算机学院苏小红109图6-5曲面物体的多面体近似逼近表示过程曲面物体曲面逼近多边形多边形顶点曲面模型（1/10）曲面造型研究在计算机内如何描述一张曲面，如何对曲面的形状进行控制与显示可以由数学函数来定义包括二次曲面、超二次曲面、隐函数曲面等也可以由用户输入一系列离散的数据点来确定的参数曲面（第4章）如Coons曲面、B样条曲面、NURBS曲面等哈尔滨工业大学计算机学院苏小红110哈尔滨工业大学计算机学院苏小红111四面体网格模型表示方法将包含实体的空间分割成四面体单元的集合特点可以以边界面片为四面体的一个面，模型精度高能够构建复杂形体的网格模型在复杂对象的科学计算和工程分析中具有重要的应用四面体网格模型数据结构复杂，实现复杂空间域边界一致的四面体剖分是近年来的研究热点。

描述实体的信息GeometryTopology哈尔滨工业大学计算机学院苏小红112描述形体的几何元素（顶点、边、面）之间的连接关系，形成物体边界表示的“骨架”描述形体的几何元素性质和度量关系，如位置、大小、方向、尺寸、形状等信息犹如附着在“骨架”上的肌肉按照：体－面－环－边－点的层次记录信息

实体的定义（1/14）表示形体的基本几何元素：顶点（Vertex）边（Edge）面（Face）环（Loop）体（Body）哈尔滨工业大学计算机学院苏小红113零维几何元素。在齐次坐标系下，n维空间中的点用n+1维向量来表示。

一维几何元素。对正则形体，边是两邻面的交集，对非正则形体，边有可能是多个邻面的交集。边的形状可以是直线，也可以是曲线。二维几何元素。可以无内环，但必须有一个且只有一个外环。面有方向性，一般用其外法线方向作为该面的正向。面的形状可以是平面，也可以是曲面

二维几何元素。有序、有向边（直线段或曲线段）组成的面的封闭边界。外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。三维几何元素。由封闭表面围成的空间，其边界是有限面的并集。实体的定义（2/14）几何造型就是通过对点、线、面、体等几何元素经平移、放缩、旋转等几何变换和并、交、差等集合运算产生实际的或想象的物体模型哈尔滨工业大学计算机学院苏小红114实体几何造型（SolidModeling）研究三维几何实体在计算机中的完整信息表示的模型和方法的技术实体的定义（3/14）如何保证实体的有效性呢？一个无效的实体当然也不具备可加工性要保证实体的有效性和可加工性，形体必须是正则的那么什么是正则形体呢？哈尔滨工业大学计算机学院苏小红115实体的定义（3/14）二维流形（2-manifold）美国H.B.Voelcker和A.A.G.Requicha等为描述正则形体引入的概念指这样一些面，其上任意一点都存在一个充分小的邻域，该邻域与平面上的封闭圆盘是同构的，即在该邻域与圆盘之间存在连续的一一映射正则形体？对于任一形体，它是三维欧氏空间R3中非空、有界的封闭子集，且其边界是二维流形（即该形体是连通的）否则称为非正则形体哈尔滨工业大学计算机学院苏小红116实体的定义（3/14）如何得到一个正则形体？将三维形体点集分成内部点集和边界点集两部分先找出形体的内部点集然后形成形体内部点集的闭包哈尔滨工业大学计算机学院苏小红117图6-9正则形体的形成过程示意图(a)形体的开集(b)图(a)开集的闭包(c)图(a)形体的内部点集(d)图(c)内部点集的闭包实体的定义（3/14）正则形体的性质？（1）刚性不变形的实体，不能随实体的位置和方向而发生形状变化（2）维数的一致性三维空间中的实体的各部分均应是三维的哈尔滨工业大学计算机学院苏小红118实体的定义（8/14）

几何元素

正则形体

非正则形体

面

是形体表面的一部分不允许存在悬面

可以是形体表面的一部分，也可以是形体内的一部分，也可以与形体相分离。

边

只有两个邻面不允许存在悬边

可以有多个邻面、一个邻面或没有邻面。

点

至少和三个面（或三条边）邻接不允许存在孤立点

可以与多个面（或边）邻接，也可以是聚集体、聚集面、聚集边或孤立点。哈尔滨工业大学计算机学院苏小红119实体的定义（4/14）正则形体的性质？（3）有限性一个实体必须占据有限的三维空间（4）边界的确定性根据实体的边界能区分出实体的内部和外部（5）封闭性经过一系列刚体运动和任意次序的集合运算之后，实体仍保持其同等的有效性哈尔滨工业大学计算机学院苏小红120实体的定义（4/14）正则形体的表面的性质（1）连通性位于实体表面上的任意两个点都可用实体表面上的一条路经连接起来（2）有界性实体在有限空间内是可定义的，即实体表面可将空间分成互不连通的两个区域，其中一个区域是有界的。哈尔滨工业大学计算机学院苏小红121实体的定义（4/14）正则形体的表面的性质（3）非自交性实体的表面不能自交克莱茵瓶（KleinBottle）就是一个自交且不可定向的封闭曲面（4）可定向性表面的两侧可明确地定义出属于实体的内侧还是外侧莫比乌斯带（MobiusBand）则是一个单边不可定向的例子哈尔滨工业大学计算机学院苏小红122实体的定义（4/14）确定多面体表面是否具有可定向性的方法Mobius提出将实体的每个表面的边环定义一个一致的方向（例如逆时针方向），这样，每条边会得到两个指示方向的箭头，当且仅当每条边在每个方向都具有一个箭头时，该实体表面就是可定向的。哈尔滨工业大学计算机学院苏小红123欧拉公式与欧拉运算欧拉特征设表面s由一个平面模型给出，且v,e,f分别表示其顶点、边和小面的个数，那么v-e+f是一个常数，它与s划分形成平面模型的方式无关。该常数称为Euler特征。哈尔滨工业大学计算机学院苏小红124v=8,e=13,f=7v-e+f=2欧拉公式欧拉公式与欧拉运算欧拉物体满足欧拉公式的物体欧拉运算增加或者删除面、边和顶点以生成新的欧拉物体的过程哈尔滨工业大学计算机学院苏小红125欧拉公式只是检查实体有效性的一个必要条件，而不是充分条件实体的正则集合运算为什么在正则实体造型中，不使用普通的并、交、差等集合运算，而要使用正则集合运算呢？普通的集合运算会产生悬边、悬面等低于三维的形体哈尔滨工业大学计算机学院苏小红126正则集合运算保证集合运算的结果仍是一个正则形体实体的正则集合运算如何实现正则集合运算？方法1：先按照普通集合运算再删去不符合正则形体定义的部分：悬边、悬面等方法2：定义正则集合算子，直接计算得到哈尔滨工业大学计算机学院苏小红127正则集合运算任何物体都可用三维欧氏空间中点的集合来表示，但三维欧氏空间中任意点的集合却不一定对应于一个有效的物体设有三维空间中的一个点集A，那么称为A的正则点集。如果A满足那么称A为正则点集。其中，r表示正则化算子，b、i分别表示取闭包运算和取内点运算。哈尔滨工业大学计算机学院苏小红128正则集合运算正则集合运算定义如下：正则并正则交正则差哈尔滨工业大学计算机学院苏小红129正则集合运算以正则交集合运算为例符合正则形体定义的实体，是三维空间中的点的正则点集，可以用它的边界点集和内部点集来表示，即写成A为符合正则形体定义的实体bA代表A的边界点集iA代表A的内部点集哈尔滨工业大学计算机学院苏小红130正则集合运算普通集合交运算确定两个相交物体的重叠边界中的有效部分确定图中粗实线所示边界中的有效部分哈尔滨工业大学计算机学院苏小红131图6-17正则交运算的候选部分(a)

(b)(d)ABABAB12AB(c)正则集合运算确定两个相交物体的重叠边界中的有效部分确定图中粗实线所示边界中的有效部分如果对物体的边界采用一致的方向约定，那么，在两个相交物体的重叠边界上，如果某点处的切矢同向，则重叠边界线段就是的有效边界，否则，就是无效的边界哈尔滨工业大学计算机学院苏小红132图6-17正则交运算的候选部分(a)

(b)(d)ABABAB12AB(c)正则集合运算哈尔滨工业大学计算机学院苏小红133数据模型——边界表示BoundaryRepresentation，也称BR表示或BRep表示最成熟、无二义性当前CAD/CAM系统中的最主要的表示方法物体的边界与物体一一对应实体的边界是表面的并集表面的边界是边的并集哈尔滨工业大学计算机学院苏小红134数据模型——边界表示多面体表示的实体的表面、棱边、顶点之间的连接关系有9种类型至少需要选择其中的2种才能表示一个实体的完整的拓扑信息哈尔滨工业大学计算机学院苏小红135图6-20表面、棱边、顶点之间的拓扑关系ffffff→{f}feeeef→{e}fvvvvf→{v}effe→{f}eeeeee→{e}evve→{v}vfffv→{f}veeev→{e}vvvvv→{v}采用较少的关系类型进行组合来表示一个实体，所需的存储空间小，但对数据的查找时间长反之，所需的存储空间大，但对数据的查找时间短数据模型——边界表示比较著名的有半边数据结构、翼边数据结构、辐射边数据结构等翼边数据结构最早是由美国斯坦福大学B.G.Baumgart等人于1972年提出以边为核心来组织数据的一种数据结构用指针记录每一边的两个邻面（即左外环和右外环）、两个顶点、两侧各自相邻的两个邻边（即左上边、左下边、右上边和右下边）用这一数据结构表示多面体模型是完备的，但它不能表示带有精确曲面边界的实体哈尔滨工业大学计算机学院苏小红136图6-21翼边数据结构左上边右上边左下边右下边左外环右外环eP2P1数据模型——边界