Bézier曲线的细分技术毕业论文(34页).doc

《Bézier曲线的细分技术毕业论文(34页).doc》由会员分享，可在线阅读，更多相关《Bézier曲线的细分技术毕业论文(34页).doc（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-Bzier曲线的细分技术毕业论文-第 27 页本科毕业设计（2013届）题 目Bzier曲线的细分技术学 院计算机学院专 业计算机科学与技术班 级09052314学 号09051412学生姓名郭佳远指导教师余正生完成日期2013年6月诚 信 承 诺我谨在此承诺：本人所写的毕业论文Bzier曲线的细分技术均系本人独立完成，没有抄袭行为，凡涉及其他作者的观点和材料，均作了注释，若有不实，后果由本人承担。 承诺人（签名）： 年 月 日摘 要 本毕业设计主要设计Bzier曲线的细分技术。Bzier曲线在曲线曲面工程设计中是一种比较常用的曲线，它在线面造型及线面重构中发挥着重要作用。Bzier 曲线的

2、显著特性是“刚性”有余，“柔性”不足。为了增加曲线的“柔性”，往往采用升阶的方法，通过增加新控制顶点来加强对曲线修改的灵活性。但是如果一旦移动新生成的控制顶点，曲线次数也随之增加，有时在对曲线进行修改时，不希望改编曲线的整体次数，此时就需要对曲线进行细分。我们希望从一个控制多边形出发，按照我们事先选取的细分规则，在给定的控制多边形中插入新的顶点，再连接这些新的顶点得到新的控制多边形，所得到的新的控制多边形是初始控制多边形的加细。不断的重复上述过程，随着细分的不断进行，控制多边形就被逐渐加细，其极限状态为一条曲线，称为递归细分曲线 。在完成毕业设计的过程中，我们首先在理论上对我们的问题进行数学分

3、析与证明，然后对解决问题的算法进行实现，并在文中通过样例来支持本毕业设计研究结论的有效性。关键词：计算机辅助几何设计； Bzier曲线；deCasteljau算法； 细分曲线ABSTRACT The main aim of this thesis is to devise Bzier curves subdivision techniques. Bzier curve is a relatively common curve in the engineering design of curves and surfaces, It plays an important role at onlin

4、e face shape and line and plane reconstruction. The Bzier curves notable features is the rigid more than flexible. In order to increase the flexible of the curve, we often adopt the method of Ascending Order, By adding new control points to enhance the flexibility of the curve changes. But if mobile

5、 newly generated control vertices, the curve frequency and also increases, sometimes to modify the curve, we do not want the overall frequency and adaptation curve, then we need to curve refinements. We hope that the departure from a control polygon, Selected in advance in accordance with our rules

6、segments, insert a new vertex in the given control polygon, and then connect these new vertices to the new control polygon obtained new control polygon is the refinement of the initial control polygon. Constantly repeat the process, as the breakdown of the ongoing control polygon gradually increase

7、the fine, the ultimate status of a curve, known as recursive subdivision curve. During our working process, we firstly proved our algorithm mathematically, then implemented our algorithm by programs, and supported our method with some real samples.Key words：Computer aided geometric design; Bzier cur

8、ves; deCasteljau algorithm; subdivision curve目录1 引言11.1 课题的背景和研究意义11.2 论文的研究内容及主要工作21.3 论文的结构32 预备知识42.1 Bernstein 多项式42.2 Bzier曲线42.3 实际问题描述53 Bzier曲线的细分73.1 细分曲线的构造思想和发展史73.2 Bzier曲线的细分算法93.3 实例分析124 开发环境配置与调试164.1 OpenGl简介164.2 VS2010上OpenGl开发环境的配置174.3 OpenGl的逻辑组织结构195 程序设计与算法实现235.1 主要算法235.2 使

9、用C+语言实现该算法246 程序调试与维护296.1 程序操作297 结论32致谢33参考文献341 引言1.1 课题的背景和研究意义 随着计算机技术的发展和普及，计算机辅助设计与制造技术（CAD（Computer Aided Design）/CAM（Computer Aided Manufacture）得到了迅猛的发展，他们推动了许多领域的设计革命，CAD/CAM技术的发展和应用水平已经成为衡量一个国家现代化水平的重要标志之一。而计算机辅助几何设计（Computer Aided Geometry Design，简称CADG）是CAD/CAM的理论基础和关键技术，一旦CAGD中有一种新的几何造

10、型出现，往往就能很快地应用到CAD/CAM系统中。早期是由数学放样和外形设计的实际需要，作为样条函数及函数逼近论等在飞机、汽车、船舶制造中的实际应用而发展起来的。现在，它已与许多学科有了紧密联系，成为一门新兴的交叉学科和边缘学科。CAGD主要研究在计算机图像系统的环境下对曲面信息的表示、逼近、分析和综合。现在，越来越多的科研人员从事这方面的研究，并取得了瞩目的成果。其应用的范围已从最初的飞机、汽车以及船舶制造业发展到建筑设计、生物工程、医疗卫生事业、航天材料、电子工程、服装设计、多媒体技术、动画制作等各个技术领域。随着计算机图形显示对于真实性、实时性和交互性的日益增强，图形工业和制造工业迈向一

11、体化、信息化和网络化步伐的日益加快，CAGD得到了飞速的发展。它经历了从离散到连续，再从连续到离散的发展过程。但是，当细分（Subdivision）技术出现以后，这种造型方法得到了很大的改进，人们可以直接从离散到离散，减少了过去的建立连续函数的那个环节。细分算法的由来最早可以追溯到1956年de Rahm.G提出的割角（Cutting Corner）思想。其思想是通过对折线角点进行切割生成光滑曲线。1974年，Chaikin提出了类似的生成曲线的细分方法。1978年，Catmull和Clark提出了著名的Catmull-Clark细分模式，标志着细分方法正式成为曲面建模的手段。80年代末到90

12、年代初期，出现了许多著名的细分方法，如1987年Dyn提出四点法曲线插值模式及六点法曲线插值模式，1991年Dyn又提出Binary细分模式，稳定细分模式Cavaretta 1991，Loop模式Loop 1987，蝶形模式Dyn 1990等。在细分曲线造型方面，引入均差细分、生成多项式、生成函数等概念描述细分过程，关于细分模式的收敛性、连续性分析已有了系统的研究成果。90年代中期至今是细分技术的发展期。这一阶段出现了一些新的细分方法，也有一些方法是对老方法进行改进。在细分曲线造型方面，蔡志杰对非均匀有序控制顶点时的四点法及变参数四点法的收敛性和连续性进行了分析；骆岩林研究了生成曲线的有理稳定

13、细分方法；丁友东提出了非线性四点插值细分法；金建荣提出了非均匀四点插值细分法，生成的曲线达到G连续。2002年，Hassan提出了Ternary四点插值细分法，生成了曲线达到G连续。近些年提出的细分模式还有：Ivrissimtzis等Ivrissimtzis 2004的模式；PetersPeters 2003的4-3模式；JenaJena 2002基于三角样条的细分算法；2001年李桂清提出了细分等。1.2 论文的研究内容及主要工作我们希望从一个控制多边形出发，按照我们事先选取的细分规则，在给定的控制多边形中插入新的顶点，再连接这些新的顶点得到新的控制多边形，所得到的新的控制多边形是初始控制多

14、边形的加细。不断的重复上述过程，随着细分的不断进行，控制多边形就被逐渐加细，其极限状态为一条曲线，称为递归细分曲线 。在完成毕业设计的过程中，我们首先在理论上对我们的问题进行数学分析与证明，然后对解决问题的算法进行实现，并在文中通过样例来支持本毕业设计研究结论的有效性。首先，我们要掌握掌握Bzier曲线的定义式，和控制点的选择，熟悉Bzier曲线的性质。然后，对Bzier曲线的De Casteljau定义进行数学推导，证明由n+1个控制顶点定义的n次Bzier曲线可以被定义为由前后n个控制顶点决定的两个n-1次Bzier曲线和线性组合起来。考虑到实际设计的应用需求，我们将Bzier曲线的形式进

15、行描述，在为造型设计带来方便的同时，统一描述了整张造型曲面的数学形式，便于数学证明的同时也为程序语言表达提供了方便。在具体的实现过程中，我们先编程实现Bzier曲线，并在低次曲线情形产生一些示例。然后编程实现Bzier曲线的细分技术，并能产生直观的可视化效果图。本毕业设计能够显著简化Bzier曲线的设计过程，为现实生产设计带来了方便。1.3 论文的结构全文一共7章，按照整个对Bzier曲线和Bzier曲线细分技术研究过程来安排章节间的逻辑结构。第1章是前言部分，主要介绍课题的背景和研究意义，并介绍了研究过程中需要完成的主要工作。第2章介绍了参数曲线与参数曲面的简单预备知识，为之后的证明引入必要

16、的基本的定理与结论。第3章是本文的核心章节，Bzier曲线细分技术的生成算法，并给出了本算法的若干实例以支持本算法的正确性。 第4章主要介绍了OpenGl开发环境的插件开发与其他功能对本文算法的支持。第5章介绍了Bzier曲线细分技术生成算法以及该算法在OpenGl开发环境下的具体实现过程和详细代码。第6章给出了对本项目的后续开发与维护进行了介绍。第7章为全文的总结。2 预备知识2.1 Bernstein 多项式 定义：设f是0,1上的函数，,约定=1.称0,1上的多项式函数为f的第n个Bernstein 多项式。应当将视为一个映射，它把0,1上的函数映射为0,1上的多项式函数。称为第n个Be

17、rnstein算子。2.2 Bzier曲线2.2.1 Bzier曲线的定义或定义在任意区间a,b，即表示n次Bzier曲线，（i=1,2,.,n）表示控制点，其中表示k次Bernstein基函数，k为控制多边形的顶点的序号， ，且2.2.1 Bzier曲线的性质性质 1 Bzier曲线的递推关系：性质 2 端点性质： （1） Bzier曲线以为起点，以为终点； （2） Bzier曲线与首末边相切，即性质 3 对称性：将Bzier曲线多边形顺序取反，定义同一条曲线，仅曲线方向取反。即性质 4 凸包性质： 一个点集的凸包被定义为由该点集的元素形成的所有的凸组合的集合。可以这样来想象确定平面上点集的

18、凸包：在点集的每一个元素位置上打上钉子，然后用一根封闭的橡皮绳套在所有钉子的外面，橡皮绳因弹性自然收缩形成封闭的多边形区域，略去钉子与橡皮绳的粗面，这个包括边界在内的多边形区域就是该点集的凸包。对于空间分布的点，则可想象一封闭的橡皮膜包住这些点，任其弹性收缩所形成的的空间区域即为其凸包。Bzier曲线的凸包性质是指Bzier曲线恒为于它的控制顶点的凸包内，这一性质确定了Bzier曲线的所在范围，使得设计人员预先就心中有数。它还被用于分割求交：如果用Bzier形式表示的两相交元素的控制顶点的凸包不相交，则可定义它们不相交。性质 5 几何不变性：Bzier曲线的形状仅与控制多边形的各顶点有关，与坐

19、标系 的选取无关性质 6 变差减少性质：任意一平面与Bzier曲线的交点数不会超过它与控制多边形的交点数，但包含等个控制多边形的平面除外。这一性质导致如下的凸性定理：如定义平面Bzier曲线的控制多边形是凸的（指连接首末顶点构成的封闭多边形为凸的，相重边情况除外），则所定义的平面Bzier曲线也是凸的性质 7 Bzier曲线的导矢： n次Bzier曲线的首末端点的k阶导矢分别为（kN）：其中高阶向前差分矢量由低阶向前差分矢量递推地定义为：2.3 实际问题描述Bzier曲线就是这样的一条曲线，它是依据四个位置任意的点坐标绘制出的一条光滑曲线。在历史上，研究Bzier曲线的人最初是按照已知曲线参数

20、方程来确定四个点的思路设计出这种矢量曲线绘制法。Bzier曲线的有趣之处更在于它的“皮筋应”，也就是说，随着点有规律地移动，曲线将产生皮筋伸引一样的变换，带来视觉上的冲击。1962年，法国数学家Pierre Bzier第一个研究了这种矢量绘制曲线的方法，并给出了详细的计算公式，因此按照这样的公式绘制出来的曲线就用他的姓氏来命名是为贝塞尔曲线。“贝赛尔”工具在photoshop中叫“钢笔工具”；在CorelDraw中翻译成“贝赛尔工具”；而在Fireworks中叫“画笔”。它是用来“画线”造型的一种专业工具。当然还有很多工具也可以完成画线的工作，例如大家常用的photoshop里的直线、喷枪、画

21、笔工具，Fireworks里的直线、铅笔和笔刷工具，CorelDraw里的自由笔，手绘工具等等。用“贝塞尔”工具无论是画直线或是曲线，都非常简单，随手可得。其操作特点是通过用鼠标在面板上放置各个锚点，根据锚点的路径和描绘的先后顺序，产生直线或者是曲线的效果。我们都知道路径由一个或多个直线段或曲线段组成。锚点标记路径段的端点。在曲线段上，每个选中的锚点显示一条或两条方向线，方向线以方向点结束。方向线和方向点的位置确定曲线段的大小和形状。移动这些元素将改变路径中曲线的形状，可以看下图。路径可以是闭合的，没有起点或终点（如圆圈），也可以是开放的，有明显的端点（如波浪线）。1关于“贝塞尔”工具，有两个

22、重要的概念需要了解，那就是“平滑点”和“角点”。“平滑点”是指临近的那条线段是平滑曲线，它位于线段中央。平滑曲线由称为平滑点的锚点连接，当移动平滑点的一条方向线时，将同时调整该点两侧的曲线段。“角点”是指它临近的那条线段至少一边是直的，尖锐的曲线路径由角点连接，当移动角点的一条方向线时，只调整与方向线同侧的曲线段。在CAD/CAM中，常采用Bzier曲线曲面，这样便于理解曲线/曲面。但采用Bzier形式的曲线曲面不能精确的表示二次曲线和二次曲面，如球体和圆。将多项式改为有理形式，不仅能精确表示二次曲线和二次曲面，且增加了设计的自由度。重复的进行两点线性插值，可以构造Bzier 曲线。重复的进行

23、两点有理插值，可以构造有理Bzier 曲线。 与控制顶点类似，有理Bzier曲线上的点可映射为Bzier曲线上的点或对应的控制多边形上的点。在透视投影使用理形式与非有理形式产生相同投影时，有理Bzier曲线曲面和有理B样条曲线曲面继承了Bzier曲线曲面和B样条曲线曲面的简单、优美的特性。这种形式，数学上的分析及几何特性的掌握了解都比其他4D空间(wx、wy、wz、w)方法和单纯的3D空间有理形式要简单和容易。 现在，有理曲线曲面不仅仅用于表示和构造二次曲线曲面。对有理曲线曲面的权因子该如何选取往往不很清楚，而且有理形式的计算比非有理形式复杂，但是，由于其构造特性，现在人们已经开始考虑有理Bz

24、ier和有理B样条曲线曲面的应用。 3 Bzier曲线的细分3.1 细分曲线的构造思想和发展史 细分方法容易产生性能良好的曲线曲面，近些年己成为计算机辅助几何设计及计算机图形学领域内一项重要的研究课题。其构造思想是从一个控制多边形或初始控制网格出发，按照事先选取的细分规则(一般是加权平均)，在给定的初始控制多边形或控制网格中插入新顶点(这些新顶点是初始控制多边形或控制网格上某几个顶点的加权平均)，再连接这些新顶点得到新控制多边形或控制网格，所得新控制多边形或控制网格是初始控制多边形或控制网格的加细。不断重复上述过程，随着细分的不断进行，控制多边形或控制网格就被逐渐加细，其极限状态为一条曲线或一

25、张曲面，称为递归细分曲线或递归细分曲面。其实质是一类从序列到序列的迭代算法。 细分算法的由来最早可以追溯到1956年de Rahm.G提出的割角(CuttingCorner)思想。其思想是通过对折线角点进行切割生成光滑。1974年，Chaikin提出了类似的生成曲线的细分方法。1978年，Catmull和Clarkt提出了著名的Catmull-Clark细分模式，标志着细分方法正式成为曲面建模的手段。此时，Doo和Sabin采用离散Fourier变换的方法，对Catmull-Clark模式的收敛性进行了分析，开创了细分模式收敛性矩阵特征分析的先河。 纵观细分发展历史大致可以分成如下三个阶段:

26、第一阶段：1980年前后，提出并初步发展时期。1974年，Chaikin用割角法产生曲线，把离散细分的概念引入到图形学界。1978年，Catmull和Clark, Doo和Sabin分别将双三次和双二次B样条推广到任意拓扑结构的网格上。Catmull-Clark细分模式和Doo-Sabin关于奇异点处行为的分析理论标志着细分方法正式成为曲线曲面造型的一种手段。由于Catmull-Clark细分法能用较少的控制顶点迅速生成具有任意形状的光滑曲面(除奇异点处为C1连续外，曲面处处为C2连续)，此方法很快在造型和动画领域付诸应用，从此离散细分曲面造型得到广泛的研究。 第二阶段：80年代末到90年代初

27、的形成时期。这一阶段出现了许多著名的细分方法，如1987年D”提出四点法曲线插值模式及六点法曲线插值模式，1991年Dyn又提出Binary细分模式，稳定细分模式Cavaretta 1991 , Loop模式Loop 1987，蝶形模式Dyn 1990等。在此期间，也有一些方法是对旧方法进行改进Nasri 1987,1991; Halstead 1993; Hoppe 1994; Zorin 1996. Loop模式是一种基于三角网格的细分算法，其实质是四次三方向箱样条在任意拓扑三角网格上的推广。在细分曲线造型方面，引入均差细分、生成多项式、生成函数等概念描述细分过程，关于细分模式的收敛性、连

28、续性分析己有了系统的研究成果。在细分曲面造型方面，引入了细分矩阵描述细分过程，引入离散Fourie:方法、矩阵特征根法、矩阵逼近论等方法多种细分曲面进行特征分析及收敛性连续性分析。 第三阶段：90年代中期至今为发展时期。这一阶段出现了一些新的细分方法，也有一些方法是对老方法进行改进。在细分曲线造型方面，蔡志杰对非均匀有序控制顶点时的四点法及变参数四点法的收敛性和连续性进行了分析;骆岩林研究了生成曲线的有理稳定细分方法;丁友东提出了非线性四点插值细分法;金建荣提出了非均匀四点插值细分法，生成的曲线达到G1连续。2002年，Hassan提出了Ternary四点插值细分法，生成的曲线达到G2连续。在

29、曲面造型方面，Peters和Rief提出Mid-edge细分模式；Sederberg等在任意拓扑网格上引入非均匀节点区间的概念，推广得到非均匀细分曲面；DeRose将细分曲面造型方法用于人物动画的设计；Velho和Zorin提出了4-8细分法，其实质是C4连续的四方向样条在任意网格拓扑结构上的推广，在正常点是C4连续的，在奇异点是创连续的;Kobbelt先提出了适合四边形网格的插值算法，后来又提出了细分模式；Nasrin提出了使细分曲面插值预先指定的二次样条曲线的算法；Levin设计了细分规则用于网格曲线插值的联合细分模式；Habbib提出了基于顶点和边插入的曲线网插值方法；Biermann提

30、出了边界法向插值方法等等。Ying和Zorin提出一种可以用于构造非流形曲面的细分方法。近些年提出的细分模式还有：Ivrissimtzis等Ivrissimtzis 2004的模式；PetersPeters 2003的4-3模式;Hassan等Hassan 2002的ternary四点插值细分;JenaJena 2002)基于三角样条的细分算法;2004年李桂清提出了细分等。 纵观细分发展的历程可以看出，细分的发展是从最初的曲线到张量积曲面，再到任意拓扑结构网格的曲面;从单一的四边形网格或三角形网格到混合网格;从样条推广到石，拒细分;从最初单一的细分到可以产生局部特征的造型曲面。可见，细分是向

31、着一个造型能力更强，使用更方便，更加经济有效的方向发展的。细分方法的特点：1. 曲线曲面的生成显示速度快：符合计算机从离散到离散的造型特点。2. 数值稳定性(Numerical stability):凸线性组合的细分方法是一个迭代过程，有很好的数值计算稳定性。3. 模型简单(Model simplicity)：细分方法的数学模型仅涉及初始数据网格和细分规则，而细分规则往往简单明了，易于实现，效率也高。4. 可升级性(Scalability)：细分算法具有多分辨的性质，特别适合于层次细节技术。5. 适用于任意的拓扑网格(Arbitrary topology meshes):细分曲面可以定义在任意

32、的拓扑网格上，三角形网格或者四边形网格或者两者的混合网格均可。6. 表示的一致性(Uniformity of representation):这里的一致性是指细分法把曲面片与多面体的表示统一起来，使得造型系统有了统一处理曲面和多面体表示的手段。细分模式的分类：从不同角度可以对细分模式进行分类1. 按极限曲线曲面是否过初始控制顶点，细分模式可以分为插值细分模式C（Interpolatory subdivision schemes )&逼近细分模式(Approximating subdivision schemes ) 。2. 按控制点列的改进规则的特点，细分模式可分为顶点插入细分模式&割角细分模

33、式。3. 按不同层细分规则的特点，细分模式可分为稳定细分模式(Stationary schemes )&非稳定细分模式(Non-stationary schemes )。不同细分层次采用相同细分规则的细分模式称为稳定细分模式，否则成为非稳定细分模式。经典的细分模式大多为稳定细分模式。4. 按同一层细分规则的特点，细分模式可分为均匀细分模式(Uniform schemes )&非均匀细分模式(Non-uniform schemes )。每一层细分中网格的不同部分采用相同细分规则的细分模式称为均匀细分模式，否则称为非均匀细分模式。5. 按初始控制网格的类型，细分曲面模式可分为基于三角形网格的细分模

34、式&基于四边形网格的细分模式。6. 根据拓扑分裂类型分类，一个是面分裂(face split)，另一个是点分裂(vertex split)。第一种方式的细分方法称为基本型(prime)，即组成网格的每一个面被分裂为四个，旧点拓扑位置保持不变，自每条网格边上插入一个新点，对四边形网格，每一个网格面中也要插入一个新点。第二种方式的细分方法称为对偶型(dual)，对应于每个旧点，有多个新点产生，每个点对应一个与这个旧点相邻的网格面;对应于每一条网格边，生成一个新面;旧的网格面保持不变。3.2 Bzier曲线的细分算法 1962年法国雷诺汽车公司的工程师Bzier构造出一种独创的参数多项式曲线，这种曲

35、线采用一组独特的多项式基函数，使得它具有许多优良的性质。1963年法国雪铁龙公司的de Casteljau提出了Bzier曲线的分割，Stark和常庚哲分别给予证明。本节主要研究基于de Casteljau算法的Bzier曲线细分。Bzier曲线的De Casteljau定义：一般的，由n+1个控制顶点定义的n次Bzier曲线可以被定义为由前后n个控制顶点决定的两个n-1次Bzier曲线和线性组合， 即 事实上，由Bzier的递推关系有：因此，就得到了Bzier 曲线的De Casteljau 的递推定义如下：其中中间的控制顶点为K表示递推级数，递推一次，控制顶点减少一个。控制顶点都与t有关。

36、当t从0到1变化，第k级递推的每个中间顶点都各扫描出一条由原始顶点 定义的k次中间Bzier曲线。这k+1个原始顶点进行k级递推后，就生成了由中间顶点给出的一条k次中间Bzier曲线。 Bzier曲线的细分：给定参数t0，1，由De Casteljau 算法求得曲线上一点P（t），该点把曲线分为两个曲线段，即：显然，第一条曲线相应的蚕丝范围为0，r，第二条曲线相应的参数范围为r，1，细分就是要求出定义这两个子曲线段的点。N次Bzier 曲线细分一次后，其控制顶点增加到2n+1，顺次连接这些控制顶点得到新的控制多边形，随着细分的不断进行，控制多边形就逐渐逼近原Bzier曲线。这里主要集中于左边细

37、分。相应左边细分曲线，对于Bernstein基函数有一个重要的代数恒等式： （3-1） 令 （3-2） 由式（3-1）：点由式（3-2）根据De Casteljau 算法（如图3-1所示）求得，在这里细分参数r相当于细分掩模。图 3-1 Bzier曲线的De Casteljau 算法根据矩阵乘法点可写成： 其中，为n+1阶细分矩阵。即： 细分矩阵是一个下三角矩阵，且每一行全部元素相加和为1，细分矩乘以Bzier曲线控制顶点便得到多项式曲线的控制顶点。随着细分过程的不断进行，新的控制多边形就收敛于相应的Bzier曲线。3.3 实例分析 递归细分是用来指到分裂一个单一的Bzier曲线分为两个细分曲

38、线的过程中的术语。递归细分是重要的几个原因，但最重要的是，也许是为近似的Bzier曲线由直线段。一被划分为足够多细分的曲线可近似为直线段没有太多的错误。当我们讨论在本节的后半部，这样可以帮助渲染和其他应用程序，如相交测试。假设我们都给出了Bzier的曲线q(u)与控制点。这是一个三次曲线，如果我们让曲线然后，q1和q2是三次曲线。我们限制q1和q2区间0，1。显然，0U1，q1（u）是描绘出曲线q（u）上半部分的曲线，即q（u）0U1/2。同样，q2（u）是下半部分q（u）。下面的定理给出了一个简单的方式来表达q1和q2作为Bzier曲线。让q1(u),q2(u)在q（u）上，然后根据De C

39、asteljau 算法在q（u）的控制多边形上生成r0，r1，r2，s0，s1，t0等点，那么我们可以看见两个新的三次Bzier曲线生成，p0，r0，s0，t0为q1（u）的控制点，然后t0，s1，r2，p3为q2（u）的控制点如图3-2所示。 图3-2 通过计算生成的新的细分点有几个重要的递归细分的应用。首先，最突出的应用程序是为渲染Bzier的一系列直线段曲线，这往往是必要的，因为通常使用图形硬件直线段作为原语。为此，我们需要一种方法，打破一个Bzier曲线直到每个小细分曲线足够接近细分曲线是一条直线，使呈现为直线的细分曲线线条给人足够的结果。要进行这种细分，我们需要有一个标准“足够接近一

40、条直线。”一般来说，这个标准应该不只是取决于上也呈现上下文在曲线的曲率。例如，当渲染一个矩形像素阵列，有可能是没有需要细分的曲线是那么直之间的曲线的直线近似的距离小于单个像素。这里有一种方法使该标准，“足够接近的直线”。精确：第一，基于浏览器和像素分辨率的距离曲线图形渲染的情况下，计算出一个值0，因此，任何渲染差异绝对值小于将是微不足道的。据推测，这将对应于一些的像素尺寸的几分之一。然后递归细分曲线成细分曲线，停止每当曲线的直线近似的误差小于。一种快速肮脏的测试使用停止条件是要检查的中点的位置曲线，即，停止条件是在大多数情况下，这种情况可以非常快速地进行检查：在三次Bzier曲线方面q（0.5

41、）可以得出t0=快速计算表明停止条件快速计算表明停止条件只是成为只是成为：这种“快速和肮脏的”测试可以偶尔失败，因为它是基于只有中点曲线Bzier。一个更可靠的测试将检查是否在中间控制点，P1和p2，躺下约线段P0P3。第二个重要的应用递归细分包括结合凸船体测试，如图3-3所示，以确定区域不在的Bzier曲线。我们有兴趣在确定当射线（半线）相交的表面，我们将看到，这是特别重要的是要有有效的方法决定何时行确实不相交的表面。作为另一个例子，假设我们是大场景的渲染在任何给定的时间，只有一小部分是可见的。为了快速渲染场景，它是必要的能够迅速决定哪些对象是凭借不可见的，例如，作为外的视锥。将基于以下为非

42、交叉或不可见的测试事实：为Bzier曲线定义控制点Pi，点Q（U），0U1，所有的谎言在控制点的凸包。这是一个后果的事实上的点Bzier曲线作为控制点的加权平均计算。图 3-3 凸包的Bzier曲线的控制点在迅速缩小递归细分的过程。要说明凸包测试递归细分相结合的原则，考虑第一实施例的两维模拟。这些原则的延伸三维问题很简单。假定我们有一个Bzier曲线 Q（u）一条线或射线L和要决定是否线相交的Bzier的曲线，如果是这样的，发现发生此交汇。一种基于递归细分工作如下：首先通过比较Q3由于控制点的凸包线L曲线完全在于它的控制点的凸包，如果L不相交的凸船体，则L不相交Bzier的曲线：在这种情况下，

43、该算法可返回错误表示没有交集发生。如果L不相交的凸包，则算法进行递归细分，划分Bzier的曲线分为两半，Q1和Q2。然后，该算法递归地调用其自身，以确定是否线相交的细分曲线之一。然而，前执行的递归细分和递归调用，算法检查是否的Bzier曲线足够接近的直线，如果是这样，该算法仅仅执行支票是否直线L的Bzier曲线近似直线相交。因此，交汇或非交叉返回作为答案。对于使用递归细分测试非交叉或不可见的算法表现良好，这是必要的凸壳迅速下降，在每一个连续的大小细分。在此过程中的一个图3-4中示出，其中显示了凸船体两个细分曲线的Q1和Q2通过递归细分。其实，收缩更迅速的凸壳细分曲线的进行比图是显而易见的：的凸

44、包的“长度”，“宽度”的凸包的平方减小。这一事实可以证明的的事实，Bezier曲线有初等微积分，刚刚从连续的二阶导数。 图 3-4凸船体两个细分曲线的Q1和Q24 开发环境配置与调试4.1 OpenGl简介OpenGL（全写Open Graphics Library）是个定义了一个跨编程语言、跨平台的编程接口的规格，它用于三维图象（二维的亦可）。OpenGL是个专业的图形程序接口，是一个功能强大，调用方便的底层图形库。 OpenGL 是行业领域中最为广泛接纳的 2D/3D 图形 API, 其自诞生至今已催生了各种计算机平台及设备上的数千优秀应用程序。OpenGL 是独立于视窗操作系统或其它操作

45、系统的，亦是网络透明的。在包含CAD2、内容创作、能源、娱乐、游戏开发、制造业、制药业及虚拟现实等行业领域中，OpenGL 帮助程序员实现在 PC、工作站、超级计算机等硬件设备上的高性能、极具冲击力的高视觉表现力图形处理软件的开发。 OpenGL的前身是SGI公司为其图形工作站开发的IRIS GL。IRIS GL是一个工业标准的3D图形软件接口，功能虽然强大但是移植性不好，于是SGI公司便在IRIS GL的基础上开发了OpenGL。OpenGL的英文全称是“Open Graphics Library”，顾名思义，OpenGL便是“开放的图形程序接口”。虽然DirectX在家用市场全面领先，但在

46、专业高端绘图领域，OpenGL是不能被取代的主角。 OpenGL是个与硬件无关的软件接口，可以在不同的平台如Windows 95、Windows NT、Unix、Linux、MacOS、OS/2之间进行移植。因此，支持OpenGL的软件具有很好的移植性，可以获得非常广泛的应用。由于OpenGL是图形的底层图形库，没有提供几何实体图元，不能直接用以描述场景。但是，通过一些转换程序，可以很方便地将AutoCAD2、3DS/3DSMAX3等3D图形设计软件制作的DXF和3DS模型文件转换成OpenGL的顶点数组。在OpenGL的基础上还有Open Inventor、Cosmo3D、Optimizer等多种高级图形库，适应不同应用。其中，Open Inventor应用最为广泛。该软件是基于OpenGL面向对象的工具包，提供创建交互式3D图形应用程序的对象和方法，提供了预定义的对象和用于交互的事件处理模块，创建和编辑3D场景的高级应用程序单元，有打印对象和用其它图形格式交换数据的能力。OpenGL是一个开放的三维图形软件包，它独立于窗口系统和操作系统，以它为基础开发的应用程序可以十分方便地在各种平台间移植；OpenGL可以与Visual C+紧密接口，便于实现机械