网格建模的基本方法

ANYANG INSTITUTE OF TECHNOLOGY本科毕业论文网格建模的基本方法Basic Methods of Mesh Modeling系（院）名称：计算机科学与信息工程学院专业名 称：2012届计算机科学与技术学生姓名：学生 学号： 200803010031指导教师姓名：指导教师职称：进师毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文，是我个人在指导教师的指导 下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的 地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为 获得安阳工学院及其它教育机构的学位或学历而使用过的材料。对本研究提 供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了 谢意。作者签名：日期：指导教师签名：日期：使用授权说明本人完全了解安阳工学院关于收集、保存、使用毕业设计（论文）的规 定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有 权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为 目的前提下，学校可以公布论文的部分或全部内容。作者签名：日 期：网格建模的基本方法摘要：随着计算机图形学应用技术的不断进步，网格建模技术得到了快速的发展。网格 建模已经成为计算机图形学和CAD研究领域的一个热门课题。实现网格建模有多种方法，而细分作为一种网格建模基本方法，在计算机图形学的许 多领域中都已得到广泛应用。所谓细分就是从初始控制网格开始，按照某种规则，递 归地产生新点并逐渐加密控制网格，随着细分的不断进行，控制网格逐渐被磨光， 最终生成由离散点插值或逼近的光滑曲线或曲面。在本文中，首先对网格建模的三种常见方法做简单介绍，然后利用“细分曲面”方法来实现网格建模，该方法运用分裂与平均的细分方法实现曲线或曲面的细分。在 Visual Studio 2010开发环境下通过使用C+调用OpenGL图形库，实现了曲线细分的显示 和交互，达到了较好的效果。关键词：网格建模；细分曲面；分裂与平均；细分曲线；OpenGLBasic Methods of Mesh ModelingAbstract: With the development of computer graphics technology, mesh modeling technology has been developed rapidly, therefore, mesh modeling into the computer graphics and CAD has been a hot research subject.Realizing the grid modeling has many kinds of methods, and subdivision as a grid modeling method, has been widely used in many fields of computer graphics. The initial control mesh subdivision is from the start, according to certain rules, recursively to generate new point and gradually encryption control grid, with the subdivision of the ongoing, control grid being polished, eventually generating discrete point interpolation or approximation of smooth curves or surfaces.In this paper, firstly to the grid modeling of three kinds of common methods do a brief introduction, and then using a method in which subdivision to realize grid modeling, this method is the use of splitting and average subdivision method realizing curve or surface subdivision. In the Visual Studio 2010 development environment through the use of C+ calling OpenGL graphics library, realize the subdivision curves display and interaction, has achieved the good effect.Key words: Mesh modeling; Subdivision surface; Split and average; Subdivision curve; OpenGL弓I言1第1章绪论21.1网格建模研究背景21.2网格建模方法2拉伸形体2旋转曲面3细分曲面41.3课题研究目标错误!未定义书签。第2章细分曲面52.1细分曲面的研究现状5细分曲面的发展概况5细分曲面的最新进展62.2细分曲面的基本概念62.3 Chaikin 算法92.4细分方法的分类102.5细分方法特点112.6细分应用的理论基础12细分矩阵12细分矩阵的特征值和特征向量13细分算法的收敛性13细分曲面连续性142.7几种典型细分算法152.7.1 Catmull-Clark 细分规则152.7.2 Loop细分规则162.7.3 Doo-Sabin 细分规则172.8本章小结18第3章曲线的细分193.1贝塞尔曲线概述19贝塞尔曲线描述19贝塞尔曲线的性质193.1.3 Bezier 细分20细分实现步骤223.2细分曲线实现22交互功能22分裂与平均23设计结果24第4章曲面的细分264.1箱样条26分裂与平均26箱样条曲面的细分过程26三方向线性箱样条274.2细分曲面28结论29致谢30参考文献31引言计算机技术的飞速发展和计算机性价比的提高，为计算机图形学的发展奠定了坚实的 基础。随着计算机图形学及相关技术的发展，3D网格模型正在成为继声音、图像和视频 之后的另一种重要的多媒体数据类型。由于三维网格模型具有绘制速度快、描述手段灵活 等特点，因而成为了一种标准的三维造型工具。实现网格建模常见的方法有：拉伸、旋转 以及细分。在本文中，主要介绍网格建模的一般方法：细分。细分作为一种网格建模方法，在计算机图形学的许多领域都已经获得了广泛的应用。 其构造思想是从一个初始控制多边形或初始控制网格出发，按照事先选取的细分规则（一 般是加权平均），在给定的初始控制多边形或网格中插入新顶点（这些顶点是初始控制多 边形或控制网格上某几个顶点的加权平均），再连接这些新顶点得到新控制多边形或控制 网格，所得新控制多边形或控制网格是初始控制多边形或控制网格的加细。不断重复上述 过程，随着细分的不断进行，控制多边形或控制网格就被逐渐加细，其极限状态为一条曲 线或一张曲面。与其他一些常见的建模方法相比，如样条、隐式曲面等，细分曲面作为从给定规则通 过网格细分产生离散曲线曲面的方法更易于在计算机上表示。从飞机、轮船、汽车到家电、 服装、日用品，甚至高山、白云、江河；从静态模拟到动态仿真，细分均以其简洁的表示、 处理任意拓扑的能力大有后来居上之势。本文主要研究的内容方向是网格建模的一般方法“细分曲面”的实现。在此，首先对 细分曲面的发展状况以及相关理论做简单介绍，最终目的是通过编程实现曲线和曲面的细 分。第1章绪论1.1网格建模研究背景随着计算机硬件和计算机图形学及其相关技术的发展，计算机图形的建模技术也得到 了迅猛发展。科学计算可视化、计算机动画和虚拟现实等技术在工程应用中得到了广泛的 使用，这些技术的实现都离不开对真实物体的三维建模。多边形建模技术（也称为网格建模）作为一种常见的建模方法，是最早采用的一种建 模方式，也是大多数建模软件默认的一种建模类型，它的思想很简单，就是用小平面来模 拟曲面，从而制作出各种形状的三维物体。相对于曲面建模，例如NURBS，一般是先利用多项式函数生成光滑的几何面片，然 后添加边界约束条件拼接不同的面片，最终形成整体光滑的几何模型。由于添加的边界约 束条件最后导致求解大型的线性方程组，因此利用多项式函数进行几何建模难于描述结构 复杂的真实三维几何物体。从而，多边形建模的优势便体现了出来。多边形建模只需要较 少的计算量，建模效率也就大大提高了；我们知道多边形建模的基础在于点、线和多边形， 可构建出任意的拓扑形状，建模更灵活。它从早期主要用于游戏，到现在已被广泛应用于建筑（例如室内设计、环境艺术设计）、 医用图像、文物保护、电影制作等领域。例如在电影终结者中大量使用了 3D Morphing 技术；De Rose等人制作的电影短片Geris Game中大量使用了三维网格的细分技术。 在此短片中的一个场景是一个名叫Geri的老头，在公园里自己对自己下象棋，千方百计 想取胜的诙谐故事。动画中的人物表情和动作被刻画的惟妙惟肖，使观众得到真正的视觉 美的享受。这正充分展现了三维网格建模技术的艺术表现力。因此，我们可以看出网格建 模技术是有着很广泛的应用前景，所以也吸引了很多学者对网格建模方法进行了大量的研 究和开发。1.2网格建模方法网格建模有很多种方法，比较常见的有拉伸形体、旋转曲面和细分曲面。拉伸形体拉伸是通过把2D图形在空间中进行一系列的拉伸步骤而生成网格的一种方法。例如 将一个平面多边形沿着一条直线拉伸得到一个棱柱，如图1-1所示，其中图1-1（a）为一个初始多边形，图1-1 (b)为初始多边形经过拉伸构成的一个棱柱。在这里拉伸仅仅是 把底面多边形平移到一个新位置从而达到的顶面多边形。然而我们可以对这种方法进行扩 展来生成更加广泛的形体，比如可通过对底面多边形进行放大或缩小甚至旋转生成顶面多 边形。图1-2所示的是把一个正方形拉伸3次得到的管状体，每一次拉伸操作的方向、放缩和扭曲程度都不相同。(b)初始多边形经拉伸形成的棱柱图1-1构造棱柱的网格表示图1-2管状体旋转曲面旋转曲面就是把轮廓曲线绕着一条轴进行旋转得到的曲面。曲线绕着轴旋转从而在不 同位置形成的曲线称为经线。完全旋转一周会生成一个封闭的环，称为曲面的纬线。如图 1-3所示的就是一个旋转曲面的例子，通过一个圆环旋转生成的一个环面。细分曲面对于一些网格，初始是比较粗糙的几何模型，对一些应用而言因缺少细节而不能满足 需求。比如一些地形模型如果面片数量不足，就不能遮盖个别的表面，因而也不容易区别 光滑波动的山丘(从远处望去)和山脉上陡峭的山峰(从飞机上近距离观察)，这样的话 就不能使人满意，那么就需要对网格模型做些细分处理，以达到光滑曲面的效果。其实细 分过程很简单，对于网格模型中的一个三角形面片，一个增加面片的简单方法描述如下: 两两连接的三条边的中点，使得一个三角形生成四个三角形。有一个面片生成四个面片， 称为“单层改进”。显然这个过程直接继续下去可得到更多层次的改进。这样我们会清晰 地看到一个具体的模型。细分曲面建模方法可以改进简单的和有组织结构的网格模型。利用这种方法对网格进 行优化，可以生成新的面片，从而使网格模型在渲染时显得更加光滑。细分网格面片得到 新的面片是一个极有前景的方法，并且作为一个课题仍在被研究中。1.3课题研究目标在本文中，主要对网格建模的一般方法“细分曲面”进行分析。（1）首先要对细分曲面的研究现状进行分析，即细分曲面的发展概况以及最新进展。（2）对细分曲面的相关概念、细分方法的分类与特点以及基本理论作简要介绍。（3）最终目的是通过细分算法实现曲线曲面的细分。图1-3环面第2章细分曲面2.1细分曲面的研究现状细分曲面的发展概况细分方法的出现可以追溯到1956年，Gde Rham通过对折线角点进行切割来生成离散形 式光滑曲线，即所谓的“切角算法”。真正把细分概念引入到图形学，是在1974年的CAGD 国际会议上，Chaikin提出的一种快速生成曲线的细分方法，这正是该“切角算法”思想的 具体实现。1978年，Catmull和。永提出了基于四边形的Catmull-Clark细分算法，将此曲面 视为双三次均匀B样条曲面在任意拓扑结构下的推广，使得细分方法正式成为曲面造型的 一种手段。与此同时，Doo和Sabin采用离散Fourier变换的方法分析了Catmull-Clark模式的 收敛性。此后Ball和Storry就C atmull-Clark模式奇异点处收敛性问题做了大量有益的探索， 并证明了曲面在奇异点处的切平面连续条件。1987年，Loop在其硕士论文首次提出了一种 基于箱样条细分算法三角网格的Loop细分方法。1990年Dyn、Levin和Gregory则提出了一 种四点插值的曲线细分法，该方法后来衍生出了著名的蝶形细分方法(Butterfly Subdivision Scheme)，该曲面插值初始控制网格的所有顶点以及细分过程中所产生的新点，但是这种 细分方法要求初始网格是正则的三角网格才能保证极限细分曲面是。连续的。以上四种基 本的细分方法是细分方法发展早期阶段的重要研究成果，在实际应用中，仍发挥着重要作 用。1995年，Reif解决了细分曲面在奇异点处的连续性的问题，给出了 C1连续的充分条件， 为细分规则收敛性的研究提供了有力的理论工具，成为细分曲面分析理论研究的转折点。 此后，细分方法有了更迅猛的发展。在1996年Zorin等人提出了改进的Butterfly算法，可以 在任意网格上生成C1的细分曲面。基于变分的细分方法是由Kobbelt提出的，细分网格不再 是由静态的规则决定，而是通过使某些能量函数最小化来生成新网格。1998年，Qin和 Mandal等将动态模型引入到Catmull-Clark曲面中。后来他们又将这种方法推广到了 Butterfly曲面。2000年，Kobbelt提出了一种新的用于三角形网格细分的&细分方法，其拓 扑分裂规则不再是一分为四，而是一分为三。除奇异点外，细分极限曲面达到C 2连续，在 奇异点处C1连续。2001年，Ying和Zorin提出了一种可以用于构造非流形曲面的细分方法。 MacCracken和Joy将Catmull-Clark细分方法推广用于体网格(volume mesh)的细分。在这一时 期，细分方法得到了更广泛的应用，并取得了大量成果。细分曲面的最新进展如上所述，国外的学者在该领域无论是理论还是应用方面都已经进行了较广泛的研 究，美国的Utah大学、New York大学、德国的Karlsruhe大学等各个大学包括美国的Pixar公 司都是这方面的先行者，他们对细分方法的发展和应用起到了关键性的作用，使得如今的 细分方法在许多领域都有重要应用，如三维动画造型、医学图像重建、工程曲面造型等。国内细分曲面研究方面总体来说起步比较晚，但近几年，随着国外细分曲面技术关注 度的提升，国内对这方面的研究也有所升温，关于这方面的研究文献也呈现逐年递增的趋 势。目前国内对细分曲面的研究主要集中在少数几所高校，其研究方向主要集中在基本算 法、工程和图形学领域。其中浙江大学的郑建民、张宏鑫、张积文等人分别提出了非均匀 递归细分方法、半静态细分方法、基于C-B样条的Catmull-Clark细分方法；清华大学的秦开 怀等人对非均匀细分曲面连续性、细分曲面NC刀具并行轨迹计算等进行了研究；南京航空 航天大学王占东等人主要就基于稀疏数据的细分曲面拟合方法进行了研究；山东理工大学 的徐家川对细分曲面技术在汽车车身造型在图形学中应用的研究；西安交通大学的王小 椿、吴维勇等人研究了 Catmull-Clark细分曲面与NURBS的相互转化。虽然国内研究仍然处 在理论研究阶段，尚未形成完善的体系，应用也存在较多的不足，特别是细分曲面造型技 术在工程。人。系统中的应用。但只要我们对细分曲面不断地潜心研究，就会促进细分曲面 应用领域的发展。2.2细分曲面的基本概念细分曲面的基本思想是由初始网格按照一定的细分算法插入新点反复迭代得到光滑 的极限曲面。细分主要分为两个步骤：拓扑分裂和几何平均。拓扑分裂是指通过增加新的 顶点产生新的网格拓扑，有面分裂和顶点分裂两种典型形式。几何平均是指每细分一次就 计算所有顶点的位置，与拓扑分裂同步进行。因此，细分的关键技术是如何制定合理的细 分规则以得到连续的光滑极限曲面。要了解细分曲面的本质牵涉到很多基本概念，因此， 下面介绍主要的相关概念。（1）拓扑（Topology）一词来源于希腊，拓扑学是现代数学中重要的分支学科，它 研究几何形体在连续形变之下保持不变的性质。（2）由顶点、边和面构成的整个或部分多面体表面称为网格（Mesh）。如果所有网 格面均为三角形，称其为三角网格（Triangular Mesh）；如果所有网格面均为四边形，称 其为四边形网格(Quadrilateral Mesh)；如果网格面中包含有不同类型的多边形面，则称 为任意多边形网格(Arbitrarily Polygonal Mesh)。(3) 如果网格的某一条边只属于一个面，称这条边为边界边(Boundary Edge)；如 果一个顶点处在边界边上则称此顶点为边界点(Boundary Vertex)；至少包含一条边界边 的面称为边界面(Boundary Face)。非边界的顶点、边和面分别称为内部顶点(Internal Vertex)、内部边(Internal Edge)和内部面(Internal Face)。含有边界边的网格称为开网 格(Open Mesh)，否则称之为闭网格(Close Mesh)。(4) 对于网格中的任意一个顶点 匕，与其直接相连的边的数量称为顶点 匕的价 (Valence)，记为N。对于三角网格M，如果匕为内部顶点且价不等于6或匕为边界顶点且价不等于4，则称V为奇异顶点(Extraordinary Vertex)，否则称为正则顶点(RegulariVertex)。对于四边形网格M，如果V为内部顶点且价不等于4或V为边界顶点且价不等于3，则称V为奇异顶点；否则称为正则顶点。不存在奇异顶点的网格称为正则网格 i(Regular Mesh)或称为规则网格。(5) 细分方法有两种典型的拓扑分裂(Splitting)方法：基于顶点的拓扑分裂规则称 为对偶分裂算子(Dual Splitting Operator)；基于面的拓扑分裂规则称为基本分裂算子(Primal Splitting Operator)o基于顶点的拓扑分裂，是在原网格顶点拓扑分裂后，生成一个新的多边形面。对于价 为N的内部顶点V ,将顶点V分裂出N 1个顶点，并依次连成一个N边多边形，此N边 形称为新网格的顶点面(V-面)。对于内部边E(匕,七)，一定有两个相邻面(记为F1和F2)， 假设V、V分裂的与F和F相对应的顶点分别为V、V、V、V，那么连接ij12i1i2j1j2V、V、V和V形成的四边形面称为边面(E-面)。原网格M中的多边形面F上的每个 i1i2jj2顶点都分裂出一个新顶点与之对应，把这些分裂出来的新顶点依原来的顺序相连，就生成 一个与面F边数相同的面，该面称为面面(F-面)，如图2-1所示，其中图2-1(a)为初 始控制网格，图2-1(b)为细分后的控制网格。V面面F面(a)初始控制网格(b)细分后的控制网格图2-1基于顶点的拓扑分裂示意图基于面的拓扑分裂是在原网格的边和面上插入一定数量的新顶点，然后对每个面进行 拓扑剖分，从而得到新网格。新插入的点称为奇顶点，原网格的顶点称为偶顶点。而新插 入的顶点中，边上插入的点为边顶点(E-顶点)，面上插入的点为面顶点(F-顶点)，原来 的顶点为点顶点(V-顶点)。针对三角网格和四边形网格，常用的分裂有以下几种：Q1-4三角形分裂：在三角形的每条边上插入一个E-顶点，然后两两相连。Q1-Y 2三角形分裂：在每条边上等份地插入丫-1个E-顶点，在每个面上插入相应的 (Y-1)(Y-2)个F-顶点，把网格的每个三角形分成Y 2个三角形。1-4即为1- 2的特例(y=2, 2如图2-2所示，其中图2-2 (a)为初始三角网格，图2-2 (b)为经过1-4分裂生成的网格。Q1-4四边形分裂：在四边形的每条边插入一个E-顶点，每个面中心插入一个F-顶 点，如图2-3所示，其中图2-3 (a)为初始四边形网格，图2-3 (b)为一次1-4分裂后的 网格，图2-3 (c)为两次1-4分裂后的网格。图2-2三角网格分裂情况(a)初始网格(b) 一次1-4分裂(c)两次1-4分裂图2-3四边形网格分裂情况(6) 从网格M 0开始，依次采用某种拓扑分裂规则和几何平均规则对其进行细化，从而得到一系列网格M0,M1 Mk .。网格序列的极限limMk称为细分曲面(Subdivision k sSurface)o M。称为细分曲面的控制网格(Control)。拓扑分裂规则(Topological SplittingRules)和几何平均规则(Geometric Averaging Rules)的集合称为细分方法(SubdivisionScheme)o2.3 Chaiki n 算法细分曲面的基本思想源于Chaikin算法，该算法通过不断的割角可以从一个多边形生图 2-4 Chaikin 算法Chaikin细分过程体现了所有细分算法的两个基本步骤：（1）拓扑分裂：通过增加新的顶点产生新的网格拓扑。Chaikin细分的拓扑规则如图 2-4所示，通常被称为“割角”（Corner Cutting）o在每一个旧顶点匕两边插入新的顶点 V和V，并连接这两个顶点产生新边而去除原顶点所在的角。（2）几何平均：每细分一次，重新计算所有顶点的位置o Chaikin细分的几何规则如 方程组（2-1）所示，就是新顶点是原顶点邻接点位置的线性平均。为清晰简便起见，方程组 （2-1）通常由图2-5所示的细分模板所代替，其中图2-5（a）为细分一次的模板，图2-5（b） 为细分两次的模板。V =1V + 3 V（2-1）i 4 i-14 i3的顶nn 8 8 4 n J点，按公式P =来计算；当顶点Valence=3时，可以取P = n 8nn 16(1)内部E顶点:对于每条内部边的端点为V ,V ,设共享此边的三角形面为(v ,V ,V ) 01012和(v0, V1, V 3),则相应的E顶点定义为那么此内部边相对应的E顶点为：31V = 8(v + v ) + 8(v + v )。(2) 内部V顶点：若内部顶点v的边邻点为v ,v v，其中n = V，则相应的V01n-11 E顶点为：y = （1-np ）1。妄1 V。Vnn ii=0（3）边界E顶点：边界边（v ,v ）上的E顶点的定义为：v = L（v + V ）。01E 20113（4）边界V顶点：边界边（v ,v,V ）上的V顶点的定义为：v = -（v + V ） + -V。o 1v 8。142.7.3 Doo-Sabin 细分规则该算法从概念与原理上在几种细分算法中最简单，它是一种点分裂细分的细分策略， 仅使用一个权图就可以定义该策略（对边界需要应用特殊的规则，实际上边界处的极限曲 线是一个二次样条曲线）。Doo-Sabin算法实际上是从Chaikin快速生成算法的思想推广而 来的一种生成光滑曲面的方法，生成的曲面可达到5连续，图2-8为Doo-Sabin细分模板。细分模板：（a）与顶点对应的F顶点（b）边界F-顶点（实心圆）（c）顶点标号示意图图2-8 Doo-Sabin细分规则设有一个n边面，其顶点依次为v ,vv ，v所在的位置与图2-8（a）的权值y的01n-1 ii位置相对应，每个顶点Vi都分裂出一个顶点V；，这些新分裂出的顶点会形成一个新的n 边面，如图2-8（c）所示。根据细分模板可得到：V=尸y V。0i ii=0图中系数y,的计算方法有两种方案:（1）Doo-Sabin 方案：15y = + ，0 4 4n1r 2沅 Yn-1y i F3+2cos I vji=-,2,（2）Catmull-Clark 方案:=1+L02 4n丫 L n-3 + 土 广 土 ，T22.8本章小结通过对本章的介绍，我们对细分曲面有了一定的了解。细分曲面不仅具有简单高效、 局部性、连续性、仿射不变性等特点，还具有自身的一些特性：任意拓扑性，一致表示性， 多分辨率分析。所以近年来在很多领域都有广泛的应用，如计算机动画、游戏、其特性多 分辨率的应用、工程中的应用、CAD之类的绘图软件中的应用等。细分曲面作为一种崭新的技术，其理论还在不断的完善中，新的细分方法也会不断涌 现的。因此细分曲面大有后来居上的创新之势。第3章曲线的细分3.1贝塞尔曲线概述贝塞尔曲线描述1962年，法国雷诺汽车公司的工程师Pierre Bezier运用贝塞尔曲线来为汽车的主体进 行设计。贝塞尔曲线最初是由Paul de Casteljau于1959年运用de Casteljau算法开发，以 稳定数值的方法求出贝塞尔曲线。在空间给定n+1个点P , P , P，称下列参数曲线为n次Bezier曲线。 01nP c)=* (，) Pk ,(。 t 1) 尸、(3-1)土 )(一 “-k , S n贝赛尔曲线就是多项式曲线。一条Bezier曲线P(t)的控制点就是Bezier曲线相对于 Bernstein 基函数 Bn(t),Bn(t) Bn(t)的系数，其中函数 Bn(t),Bn(t) Bn(t)称为 Bernstein 基 01n01n函数，也称为拼接函数(blending function)，因为这些函数把离散的控制点P , P , P拼 01n 接称为一条光滑曲线。 贝塞尔曲线的性质(1) 仿射不变性：Bezier曲线只与其控制点有关，坐标原点的位置以及坐标轴的方 向对Bezier曲线的位置和形状都没有影响。(2) 凸包性质：当t=0时，P(0) = P0，决定曲线的起点，当t=1时，P=Pn，故Pn 决定曲线的终点，Bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。Bezier 曲线P(t)在P点与边PP相切，在P点与边P P相切。Bezier曲线P(t)位于其控制顶点00 1nn-1 nP , P , P的凸包之内。01n(3) 变差减缩性质：称曲线具有变差减缩性质，是指其振荡次数不会超过其控制多 边形的振荡次数，即如果平面上任意直线(或三维空间的任意平面)与曲线的交点数小于 或等于该直线(或平面)与控制多边形的交点数。如图3-1所示，变差减缩与非变差减缩 的对比情况，其中图3-1 (a)为变差减缩性质的示意图，直线L与曲线的交点数等于该 直线与控制多边形的交点数，图3-1(b)为非变差减缩性质的示意图，直线L与曲线的 交点数大于该直线与控制多边形的交点数。图3-1变差减缩与非变差减缩对比(4) 首末控制点插值性质：Bezier曲线一般不插值所有控制点，但Bezier曲线总插值首末控制点。如果P(t)表示在区间a,b上控制点P , P , P的Bezier曲线，那么 01nP(a) = P，P(b) = P。因此P(t)开始于第一个控制点P，结束于最后一个控制点P。0n0n 3.1.3 Bezier 细分把Bezier曲线剖分为两条或更多条Bezier曲线，而且它们表示相同的曲线，这一过 程称为Bezier细分。在Bezier细分算法中的基本问题是：给定一组控制点P0, P , P，它们定义了区间a,b上的一条Bezier曲线，求出控制点Q0, Q、 Q.和R。，气, 七，它们定义这条 Bezier曲线在区间a,c和c,b上所对应的曲线段。虽然de Casteljau算法本来是用于计算一 条Bezier曲线上点的位置，但它也可以解决上述的问题。在此，我们引入了 de Casteljau 细分算法。令P(t)是区间a,b上一条Bezier曲线，控制点是P , P , P。为了在t=c处剖分曲 01n线，我们执行在t二c时相应于P(t)的de Casteljau算法。那么出现在de Casteljau算法示意 图中左边界上的点Q, Q、 Qn就是曲线从t=a到t=c的片段对应的控制点，而出现在 de Casteljau算法示意图右边界上的点R, RR.就是曲线从t=c到t=b的片段对应的控制点，如图3-2所示，控制点为P , P , P , P的三次Bezier曲线的de Casteljau细分算法。图3-2三次Bezier曲线的de Casteljau细分算法当c是参数区间a,b的中点，即c =色时，有bC = - = -_a，所以在de Casteljau 2 b - a 2 b - a-细分算法中所有边上的标识在计算时的值都是2。因此，对于中点细分，de Casteljau细图3-3 Bezier曲线的de Casteljau细分算法在这里可以给出控制点Q, Q 1,Q和R0, R 1, R的显式表达式，这些控制点对给定的n次Bezier曲线进行了细分，而且它们是用Bezier曲线的初始控制点P0, P1,P 表示的。所以根据de Casteljau算法，可以得到公式（3-2）：。0= P0Rn= P(3-2)J R = PZ-12R = Pn2 + 211 + Pn-22图3-4给出了控制点为P。，P , P , P的三次Bezier曲线的P （t）的de Casteljau细分算法的几何解释。图3-4 de Casteljau细分算法的几何解释当细分Bezier曲线时，我们发现新的控制多边形比初始控制多边形距离曲线更近。如果持续递归细分每个Bezier曲线段，那么在极限时，这些控制多边形会收敛到一条光 滑曲线。细分实现步骤（1）确定初始控制顶点，并连线；（2）使用算法开始细分；（3）若对细分的曲线效果不满意，继续细分，直到满意为止。3.2细分曲线实现交互功能确定初始控制点，相邻点连线。用鼠标绘制，注册鼠标事件void myMouse（int button,int state,int x,inty），鼠标事件发生时，通过系统调用注册的鼠标函数，并向其提供这些参数值。 button 值可能是 GLUT_LEFT_BUTTON 、 GLUT_MIDDLE_BUTTON 和 GLUT_RIGHT_BUTTON中的一个；而 state的值可能是 GLUT_DOWN和GLUT_UP中的一 个；x和y的值指明事件发生时鼠标的位置。其实，事件处理器本身并不引起屏幕的重新绘 制事件，在此，鼠标处理器需要调用glutPostRedisplay()。鼠标绘制点，并连线实现的具体代码如下：void myMouse(int button, int state, int x, int y)(if(button= GLUT_LEFT_BUTTON & state=GLUT_DOWN)Point3 tmp(x,HEIGHT-y,0); 鼠标左键画点CPs.push_back(tmp);drawPoint(tmp);if(button= GLUT_RIGHT_BUTTON & state=GLUT_DOWN)glClear(GL_COLOR_BUFFER_BIT);drawControlPolyLines(CPs); 鼠标右键连线glFlush();glutPostRedisplay();初始多边形绘制成功后，系统调用注册的键盘函数void keyBoardEvents(unsigned char key,int x,int y)，按键d” 执行细分。分裂与平均对初始的控制多边形进行一次分裂和三次平均的一次细分，生成样条曲线。一个控制 点分裂为一对点，然后相邻点进行平均，每进行一次细分，相当于对相邻点平均三次。为 区别不同细分层次的生成的曲线，就在颜色上做了不同的设置。具体代码实现如下：vector& subDivide(vector& cps)为区别不同细分层次的生成的曲线做了颜色的不同设置static unsigned char red = 255;static unsigned char green = 0;static unsigned char blue = 0;red = (red + rand()%255)%255;green = (green + rand()%255)%255;blue = (blue + rand()%255)%255;每一次细分，相当于每个点分裂一次，相邻点平均三次vector splitCPs = split(cps);vector averCPs = average(splitCPs);vector averCPs1 = average(averCPs);vector averCP