CG2014-07-三维对象的表示

计算机图形学河南大学计算机与信息工程学院2014年2月计算机图形学2第七章三维对象的表示7.1三维对象表示方法概述7.2多边形表面7.3二次曲面7.4样条曲线概述7.5Hermite样条曲线7.6Bézier曲线和曲面7.7B样条曲线和曲面7.8空间分区表示方法7.9非规则对象表示方法计算机图形学37.1三维对象表示方法概述7.1.1三维图形的基本问题7.1.2数据模型7.1.3过程模型计算机图形学41.在二维屏幕上如何显示三维物体？显示器屏幕、绘图纸等是二维的显示对象是三维的解决方法----投影三维显示设备正在研制中2.如何表示三维物体？二维形体的表示----直线段,折线,曲线段,多边形区域三维形体的表示----空间直线段、折线、曲线段、多边形、曲面片计算机图形学5三维对象表示方法线框模型线框模型：将形体表示成一组轮廓线的集合。一般地，画出了形体的棱线与轮廓线就能唯一地表示出来。如图，八个顶点可以定义一个长方体，但还不足以识别它，如果定义了棱线，则无论如何放置长方体都能唯一地表示了。对于多面体由于其轮廓线和棱线通常是一致的，所以多面体的线模型更便于识别，且简单。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4计算机图形学6计算机图形学7计算机图形学8计算机图形学9线框模型用三维线框模型表示三维形体常具有二义性

由于不存在面的信息，三维线框容易构造出无效形体由于不能表示出曲面的轮廓线，所以不能正确表示曲面信息无法进行图形的线面消隐。生成复杂形体时，线框模型要求输入大量的数据，加重用户的输入负担。难以保证数据的统一性和有效性。两种看法（伞尖远离视点或指向视点）旋转时出现不同效果计算机图形学10计算机图形学11八叉树模型及八叉树编码示意图八叉树Vonkochsnowflake计算机图形学127.2

多边形表面多边形表面分为两组进行组织几何表：顶点坐标和用来标识多边形表面空间方向的参数点表、边表、面表属性表：指明物体透明度及表面反射度的参数和纹理特征计算机图形学13多边形表面顶点表序号点坐标1x1,y1,z12x2,y2,z23x3,y3,z34x4,y4,z45x5,y5,z5边表序号顶点号1v1,v22v2,v33v3,v14v3,v45v4,v56v5,v1多边形面表序号边序号1E1,E2,E32E3,E4,E5,E6E1E2E4E5S1v2v1v3v4v5E3E6S2计算机图形学14PolygonSurfaces多边形网格图形系统一般使用多边形网格对3D物体进行建模计算机图形学15计算机图形学16(a)线框图物体的多边形表示实例野鸭模型的多边形表示，有6656个面片，3474个顶点。(b)原始法向着色图(c)平均法向着色图计算机图形学17多边形表面模型多边形网格：三维形体的边界通常用多边形网格（polygonmesh）的拼接来模拟。球面椭球面环面超二次曲面二次曲面和超二次曲面

不能表达复杂的曲线和曲面。例如飞机或汽车的流线表面…..使用样条表示7.3二次曲面

计算机图形学18样条的历史很早的绘图员利用“ducks”和有柔性的木条（样条）来绘制曲线木质的样条具有二阶连续并且通过所有的控制点ADuck(weight)Duckstraceoutcurve7.4样条曲线概述计算机图形学19样条：通过一组指定点集而生成平滑曲线的柔性带样条曲线在计算机图形学中的含义由多项式曲线段连接而成的曲线在每段的边界处满足特定的连续性条件样条曲面使用两组正交样条曲线进行描述样条计算机图形学20样条在图形学中的应用设计曲线、曲面汽车车身设计、飞机和航天飞机表面的设计、船体设计以及家庭应用。曲线的产生给定一组离散的坐标点，将数据集拟合成指定的曲线函数根据曲线函数得到曲线的图形计算机图形学21曲线的类型插值样条曲线：选取的多项式使得曲线通过每个控制点逼近样条曲线：选取的多项式不一定使曲线通过每个控制点计算机图形学22给定一组有序的数据点Pi，i=0,1,…,n，构造一条曲线顺序通过这些数据点，称为对这些数据点进行插值，所构造的曲线称为插值曲线。线性插值：假设给定函数f(x)在两个不同点x1和x2的值，用一个线形函数：y=ax+b，近似代替，称为的线性插值函数。抛物线插值:已知在三个互异点的函数值为，要求构造一个函数使抛物线在结点处与在处的值相等。插值计算机图形学23xyo1y2y)(xfy=)(xyj=1x2xxyo1y2y)(xfy=)(xyj=1x2x3x3y(a)(b)

线性插值和抛物插值计算机图形学24逼近：构造一条曲线使之在某种意义下最接近给定的数据点(但未必通过这些点)，所构造的曲线称为逼近曲线。在计算数学中，逼近通常指用一些性质较好的函数近似表示一些性质不好的函数。逼近计算机图形学25

曲线的逼近求给定型值点之间曲线上的点称为曲线的插值。将连接有一定次序控制点的直线序列称为控制多边形或特征多边形。计算机图形学26

曲线的逼近凸壳凸壳的定义Convexhull

包含一组控制点的凸多边形边界凸壳的作用提供了曲线或曲面与包围控制点的区域之间的偏差的测量以凸壳为界的样条保证了多项式沿控制点的平滑前进计算机图形学27凸壳计算机图形学28光顺(Firing)指曲线的拐点不能太多。对平面曲线而言，相对光顺的条件是：a.具有二阶几何连续性(G2)；b.不存在多余拐点和奇异点；c.曲率变化较小。光顺计算机图形学29假定参数曲线段pi以参数形式进行描述：参数连续性几何连续性参数连续性与几何连续性计算机图形学301.参数连续性0阶参数连续性记作C0连续性，是指曲线的几何位置连接，即计算机图形学311阶参数连续性记作C1连续性，指代表两个相邻曲线段的方程在相交点处有相同的一阶导数：计算机图形学322阶参数连续性，记作C2连续性，指两个相邻曲线段的方程在相交点处具有相同的一阶和二阶导数。

计算机图形学332.几何连续性0阶几何连续性，记作G0连续性，与0阶参数连续性的定义相同，满足：1阶几何连续性，记作G1连续性，指一阶导数在相邻段的交点处成比例;2阶几何连续性，记作G2连续性，指相邻曲线段在交点处其一阶和二阶导数均成比例。计算机图形学34参数连续性条件两个相邻曲线段在相交处的参数导数相等零阶连续(C0连续)：简单地表示曲线连接一阶连续(C1连续)：说明代表两个相邻曲线的方程在相交点处有相同的一阶导数（切线）二阶连续(C2连续)：两个曲线段在交点处有相同的一阶和二阶导数，交点处的切向量变化率相等参数连续性条件计算机图形学35曲线分段构造时参数连续性条件零阶连续一阶连续二阶连续F(u)f(u)F(1)=f(0)F'(1)=f'(0)F''(1)=f''(0)计算机图形学36几何连续性条件两个相邻曲线段在相交处的参数导数成比例零阶连续（G0连续）：与0阶参数连续性相同，即两个曲线必在公共点处有相同的坐标一阶连续（G1连续）：表示一阶导数在两个相邻曲线的交点处成比例二阶连续（G2连续）：表示两个曲线段在相交处的一阶和二阶导数均成比例几何连续性条件计算机图形学377.6Bezier曲线7.6.1Bezier曲线的定义Bezier曲线的例子计算机图形学38定义：其中，Pi构成该Bezier曲线的特征多边形Bernstein基函数具有如下形式：注意：当k=0，t=0时，tk=1，k!=1。

计算机图形学397.6.2Betnstein基函数的性质

（1）正性

（2）端点性质

计算机图形学40（3）权性

由二项式定理可知：计算机图形学41（4）对称性

因为

计算机图形学42(5）递推性。

即高一次的Bernstein基函数可由两个低一次的Bernstein调和函数线性组合而成。因为，计算机图形学43（6）导函数

（7）最大值。在处达到最大值。计算机图形学44（8）升阶公式

计算机图形学45（9）积分计算机图形学461．一次Bezier曲线(n=1)

计算机图形学472．二次Bezier曲线(n=2)

计算机图形学483．三次Bezier曲线(n=3)

计算机图形学49

三次Bezier曲线四个Bezier基函数0tB0,3(t)B3,3(t)B1,3(t)B2,3(t)计算机图形学50计算机图形学517.6.2Bezier曲线的性质1．端点

计算机图形学522．一阶导数

计算机图形学53计算机图形学54

三次Bezier曲线段在起始点和终止点处的一阶导数为：计算机图形学553．二阶导数

三次Bezier曲线段在起始点和终止点处的二阶导数为：计算机图形学56当t=0时，当t=1时，上式表明：2阶导矢只与相邻的3个顶点有关，事实上，r阶导矢只与（r+1）个相邻点有关，与更远点无关。将、及、代入曲率公式，可以得到Bezier曲线在端点的曲率分别为：计算机图形学57（4）对称性。由控制顶点构造出的新Bezier曲线，与原Bezier曲线形状相同，走向相反。因为：这个性质说明Bezier曲线在起点处有什么几何性质，在终点处也有相同的性质。计算机图形学58计算机图形学59（5）凸包性由于，且，这一结果说明当t在[0，1]区间变化时，对某一个t值，P(t)是特征多边形各顶点的加权平均，权因子依次是。在几何图形上，意味着Bezier曲线P(t)在中各点是控制点Pi的凸线性组合，即曲线落在Pi构成的凸包之中，如下图所示。Bezier曲线的凸包性凸包计算机图形学60（6）几何不变性。这是指某些几何特性不随坐标变换而变化的特性。Bezier曲线位置与形状与其特征多边形顶点的位置有关，它不依赖坐标系的选择。计算机图形学61（7）变差缩减性。若Bezier曲线的特征多边形是一个平面图形，则平面内任意直线与C(t)的交点个数不多于该直线与其特征多边形的交点个数，这一性质叫变差缩减性质。此性质反映了Bezier曲线比其特征多边形的波动还小，也就是说Bezier曲线比特征多边形的折线更光顺。计算机图形学62（8）仿射不变性对于任意的仿射变换A：即在仿射变换下，的形式不变。计算机图形学637.6.5Bezier曲线的生成1．绘图一段Bezier曲线①利用定义式Bezier曲线的绘制，可以利用其定义式，对参数t选取足够多的值，计算曲线上的一些点，然后用折线连接来近似画出实际的曲线。随着选取点增多，折线和曲线可以任意接近。计算机图形学64假设给定的四个型值点是P0=(1，1)，Pl=(2，3)，P2=(4，3)，P3=(3，1)，则计算结果见下表。计算机图形学65t(1-t)33t(1-t)23t2(1-t)t3P(t)01000(1,1)0.150.6140.3250.05740.0034(1.5058,1.765)0.350.2750.4440.2390.043(2.248,2.376)0.50.1250.3750.3750.125(2.75,2.5)0.650.0430.2390.4440.275(3.122,2.36)0.850.00340.05740.3250.614(3.248,1.75)10001(3,1)计算机图形学66计算机图形学67②利用曲线性质（几何作图法和分裂法）几何作图法(deCasteljau算法)0P1P2P11P10P20PBezier曲线上的点

抛物线三切线定理计算机图形学68)3/1(30PP=011/3

几何作图法求Bezier曲线

上一点（n=3，t=1/3）0P1P2P3P10P11P12P20P21P计算机图形学697.6.6Bezier曲面基于Bezier曲线的讨论，我们可以方便地可以给出Bezier曲面的定义和性质，Bezier曲线的一些算法也可以很容易扩展到Bezier曲面的情况。计算机图形学701．Bezier曲面定义：BENi,m(u)与BENj,n(v)是Bernstein基函数：

依次用线段连接点列中相邻两点所形成的空间网格，称之为特征网格。计算机图形学71计算机图形学722．Bezier曲面的拼接0阶连续性只要求相连接的曲面片具有公共的边界曲线。1阶连续性则要求在边界曲线上的任何一点，两个曲面片跨越边界的切线矢量应该共线，而且两切线矢量的长度之比为常数。计算机图形学73如右图所示，设两张m×n次Bezier曲面片

分别由控制顶点和定义。),(vuP),(vuQ)0,0(P)1,0(P)0,1(Q)1,1(Q)0,0()0,1(QP=)1,0()1,1(QP=uvBezier曲面片的拼接计算机图形学74

Bezier曲面片的拼接边界线P0,0Q3,0P3,3(Q0,3)P0,3Q3,3P3,1(Q0,1)P3,0(Q0,0)P3,2(Q0,2)计算机图形学757.7B样条曲线Bezier曲线和曲面的不足：Bezier曲线或曲面不能作局部修改；Bezier曲线或曲面的拼接比较复杂计算机图形学767.7.1B样条曲线B样条曲线（构造具有局部性的调和函数）给定n+1个控制点P0，P1，…，Pn，它们所确定的k阶B样条曲线是：

其中Ni，k(u)递归定义如下：

计算机图形学77

这里u0，u1，…，un+k，是一个非递减的序列，称为节点，(u0，u1，…，un+k)称为节点向量。定义中可能出现，这时约定为0。

计算机图形学78均匀二次（三阶）B样条曲线

取n=3，m=3，则n+m=6，不妨设节点矢量为：T=(0,1,2,3,4,5,6)：计算机图形学79计算机图形学80基函数由递推转换到直接定义可以把不同段的时间进行移动例如：t在[2，3]设置为t=t-2；依次改为t=t-1；t=t注意顺序颠倒。即t=t-2变为F0,3。以下相同处理。计算机图形学81计算机图形学82tBk,3(t)214351

四段二次(三阶)均匀B样条基函数N0,3(t)N1,3(t)N2,3(t)N3,3(t)计算机图形学837.7.2B样条曲线的性质1．局部支柱性

B样条的基函数是一个分段函数，其重要特征是在参数变化范围内，每个基函数在tk到tk+m的子区间内函数值不为零，在其余区间内均为零，通常也将该特征称为局部支柱性。计算机图形学84

B样条曲线的局部支柱性P0P1P2P3P″4P5P6P7P4P′4计算机图形学852．B样条的凸组合性质

B样条的凸组合性和B样条基函数的数值均大于或等于0保证了B样条曲线的凸包性，即B样条曲线必处在控制多边形所形成的凸包之内。

计算机图形学86B样条曲线与Bezier曲线的凸包性比较B样条曲线Bezier曲线Bezier曲线B样条曲线m=3m=4m=5(a)B样条曲线和Bezier曲线的凸包比较(b)B样条曲线和Bezier曲线的比较B样条凸包Bezier凸包B样条凸包B样条凸包Bezier凸包Bezier凸包计算机图形学877.7.5B样条曲面定义：控制顶点、控制网格（特征网格）、B样条基函数。B样条曲面具有与B样条曲线相同的局部支柱性、凸包性、连续性、几何变换不变性等性质。计算机图形学88

有理样条曲线曲面：NURBSB样条曲线包括其特例的Bezier曲线都不能精确表示出抛物线外的二次曲线，B样条曲面包括其特例的Bezier曲面都不能精确表示出抛物面外的二次曲面，而只能给出近似表示。提出NURBS方法，即非均匀有理B样条方法主要是为了找到与描述自由型曲线曲面的B样条方法既相统一、又能精确表示二次曲线弧与二次曲面的数学方法。计算机图形学89NURBS曲线的定义NURBS曲线是由分段有理B样条多项式基函数定义的计算机图形学90Ri,k(t)具有k阶B样条基函数类似的性质：局部支承性：Ri,k(t)=0，t

[ti,ti+k]权性：可微性：如果分母不为零，在节点区间内是无限次连续可微的，在节点处(k-1-r)次连续可导，r是该节点的重复度。若

i=0，则Ri,k(t)=0；若

i=+

，则Ri,k(t)=1；计算机图形学91NURBS曲线与B样条曲线具有类似的几何性质：局部性质。变差减小性质。凸包性。在仿射与透射变换下的不变性。在曲线定义域内有与有理基函数同样的可微性。计算机图形学92如果某个权因子为零，那么相应控制顶点对曲线没有影响。若，则当时，Bezier曲线和非有理B样条曲线是NURBS曲线的特殊情况计算机图形学93计算机图形学94NURBS曲线曲面的定义NURBS曲面可由下面的有理参数多项式函数表示：计算机图形学95NURBS曲线曲面的性质NURBS曲面可由下面的有理参数多项式函数表示：计算机图形学96NURBS曲线曲面的特点既为自由型曲线曲面也为初等曲线曲面的精确表示与设计提供了一个公共的数学形式，因此，一个统一的数据库就能够存储这两类形状信息。为了修改曲线曲面的形状，既可以借助调整控制顶点，又可以利用权因子，因而具有较大的灵活性。计算稳定且速度快。计算机图形学97NURBS曲线曲面的特点NURBS有明确的几何解释，使得它对良好的几何知识尤其是画法几何知识的设计人员特别有用。NURBS具有强有力的几何配套计算工具，包括节点插入与删除、节点细分、升阶、节点分割等，能用于设计、分析与处理等各个环节。NURBS具有几何和透视投影变换不变性。计算机图形学98NURBS曲线曲面的特点NURBS是非有理B样条形式以及有理与非有理Bezier形式的合适的推广。需要额外的存储以定义传统的曲线曲面。权因子的不合适应用可能导致很坏的参数化，甚至毁掉随后的曲面结构。某些技术用传统形式比用NURBS工作得更好。例如，曲面与曲面求交时，NURBS方法特别难于处理刚好接触的情况。某些基本算法，例如求反曲线曲面上的点的参数值，存在数值不稳定问题。7.8空间分区表示由简单的物体来构成复杂的物体扫描表示结构实体几何法7.8.2八叉树计算机图形学99扫描表示思想：通过平移、旋转及其他对称变换来构造三维对象通过指定一个二维形状以及在空间区域内移动该形状的扫描来描述该三维物体计算机图形学100zoyxA平移扫描二维图形A沿Z轴平移计算机图形学101旋转扫描二维图形A绕Z轴旋转zByxA计算机图形学102结构实体几何法思想通过对两个指定三维对象进行并、交或差等集合操作产生一个新的三维对象

计算机图形学103结构实体几何法物体A和B差并交差计算机图形学1047.8.2八叉树分层树形结构，称为八叉树。思想利用实体的空间相关性优点减少了三维物体的存储需求提供了存储有关物体内部信息的方便表示计算机图形学105四叉树二维平面三维空间八叉树计算机图形学106四叉树四叉树数据结构思想同质象限10231023计算机图形学107用于二维平面的分解对二维区域递归地等分4个小正方形，这个分解过程可表示为一棵树，除叶节点，其每个节点都有四个分支，分别表示4个小正方形若小正方形是同质的，则不必再分解；若小正方形是非同质的，则需将它再一分为四分解是递归的。四叉树计算机图形学108四叉树例3120312001230132计算机图形学109四叉树31245613251924182021222371112891014151617具有子孙的节点空节点实节点24513910781112314152021161722231819242516计算机图形学110计算机图形学111四叉树二维图的四叉树表示三维形体的分解对三维空间进行前后、左右、上下等分为8个小立方体，小立方体单元均质，则停止分解；小立方体单元非均质，需进一步分解为8个子立方体直至所有小立方体单元均质，或已分解到规定的分解精度为止。八叉树计算机图形学112八叉树236720131375具有子孙的节点空节点实节点计算机图形学113计算机图形学114BSP树二叉空间分割（BinarySpacePartitioning，BSP）树方法是一种类似于八叉树的空间分割方法，它每次将一实体用任一位置和任一方向的平面分为二部分（不同于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割）。7.9非规则对象表示方法

7.9.1分形Fractal欧氏几何法&分形几何法分形基本特征分形生成过程分形分类分形维数概念计算机图形学115Euclidean-GeometryMethods--useequationstodescribeobjectswhichhavesmoothsurfacesandregularshapes.Fractal-GeometryMethods--useprocedurestomodelnaturalobjectswhichhaveirregularorfragmentedfeatures.

欧氏几何法&分形几何法计算机图形学116infinitedetailateverypoint每点具有无限细节self-similaritybetweentheobjectpartsandtheoverallfeatures对象整体和局部之间的自相似性利用一个过程来描述分形物体，该过程为产生物体局部细节指定了重复操作

distantCloserCloseryet分形基本特征计算机图形学117计算机图形学118分形几何(fractalgeometry)分形(Fractal)的主要特征：自相似性质：分形物体的任何一个部分都和物体整体具有某种程度的相似无限小细节性质：当无限地放大分形物体时，物体总是表现有细节，而不是像欧氏空间的物体一样最终会表现出光滑性维数非整数计算机图形学119分形举例：Koch雪花曲线Koch雪花曲线中间曲线的每一个线段