计算机图形学

摘 要1第1章 绪论21.1 研究背景21.1.1 样条曲线的发展历程与研究前沿21.1.2 样条曲线的应用31.2 主要工作3第2章 曲线基础52.1 曲线的参数表示52.2 插值与逼近62.2.1 插值62.2.1 逼近62.3 连续性72.3.1 函数的可微性72.3.2 几何连续性72.4 样条描述82.5 三次样条9摘 要计算机图形学是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。它的重要性体现在人们越来越强烈地需要和谐的人机交互环境：图形用户界面已经成为一个软件的重要组成部分，可视化已经成为信息领域的一个重要发展趋势。样条曲线发展迅速。在基于PC系统的Photoshop、3D Max、AutoCAD、Maya等建模工具中，“样条曲线”以“基本图形对象”的存在形式，实现平面绘图、立体绘图基本功能，是“三维动画”的重要组成元素；样条曲线也是几何造型技术的重要内容。“Bezier和B样条曲线”在样条曲线的发展史中举足轻重，诸多其他曲线都是由它们发展而来的。本文主要的工作是系统的研究和整理Bezier曲线曲面的算法、性质、作用以及样条曲线的其他相关基础知识，并基于VC+6.0对曲线进行绘制。结合在VC+6.0上实现的Bezier曲线，对其性质进行直观的分析和比较。最后点明样条曲线是自由曲面的基础。关键词：计算机图形学 样条曲线 Bezier曲线。ABSTRACTComputer graphics a scientific that use mathematical algorithms makes two-dimensional or three-dimensional graphics into the grid in the form of a computer monitor . Simply put, The main content of computer graphics is to study how to represent,calculate,and display graphics in the computer, the importance of it was reflected in the growing strong need for a harmonious human-computer interaction environment: Graphical user interface has become an important part of the software, Visualization has become an important development trend of information fields.Spline curve is developing rapidly. Among PC-based system,Photoshop, 3D Max, AutoCAD, Maya and other modeling tools, spline curve have basic function of dimensional drawings and three-dimensional drawing for its “basic graphic object form, spline curve is a vital component of three-dimensional animation, it is also an important content of geometric modeling techniques. Bezier and B-spline curve is important in the development of spline curve, many other curves are evolved based on them. This paper has a comprehensive, systematic and deep research on Bezier curve algorithm.and other basic knowledge. And based on VC + +6.0 draw the curve. Combined with Bezier curves on VC + +6.0 achieve, intuitive analysis and comparison of their properties. Finally highlighted spline is the foundation of freedom surfaces.Key words：ComputerGraphics spline curve Bezier curves.第1章 绪论1.1 研究背景1.1.1 样条曲线的发展历程与研究前沿1964年，美国麻省理工学院（MIT）的孔斯（Coons）用封闭曲线的4条边界定义一张曲面。同年，舍恩伯格（Schoenberg）提出了参数样条曲线、曲面的形式。1971年，法国雷诺（Renault）汽车公司的贝济埃（Bezier）发表了一种用控制多边形定义曲线和曲面的方法。1972年,德布尔(de Boor)给出了B样条的标准计算方法。1974年，美国通用汽车公司的戈登（Gorden）和里森费尔德（Riesenfeld）将B样条理论用于形状描述，提出了B样条曲线和曲面。1975年，美国锡拉丘兹（Syracuse）大学的佛斯普里尔（Versprill）提出了有理B样条曲线。20世纪80年代后期，皮格尔（Piegl）和蒂勒（Tiller）将有理B样条曲线发展成非均匀有理B样条（Nonuniform Rational B-Spline，NURBS）曲线。NURBS曲线已成为当前自由曲线和曲面描述的最广为流行的技术，目前国际标准化协会（ISO）已将NURBS曲线方法作为定义工业产品几何形状的唯一数学方法。04样条曲线的研究领域涉及诸多内容，主要有各阶次样条曲线的不同扩展（比如NUAHBs、C-Bezier曲线、C-B样条曲线、H-Bezier曲线等）、结点插入算法的研究及应用、光顺的新方法研究、求值、升阶降阶方法的研究、造型与形状调整的研究以及实时插补技术的研究等几个方向。1.1.2 样条曲线的应用曲线曲面造型是计算机辅助几何设计和计算机图形学的一项重要内容，也是CAD/CAM系统的最关键的部分之一，其应用除了航空、造船、汽车这三大制造业外，还涉及医疗诊断、生物工程等设计领域。当前，CAD/CAM中曲线曲面造型的主流方法为Bezier曲线曲面和NURBS方法。针对工程曲线曲面造型中这两种方法存在的缺陷，07我们可以对已有的样条函数进行调整或修改，通过改变调和函数的形式，对样条曲线进行传递扩展，从而达到调整和改变曲线形状的目的。生成的新样条曲线不仅具备基础样条函数的性质，还具有自身的优点。例如，对二次均匀B样条基函数进行扩展，构造出三次和四次带局部参数 的调和函数，推广后得到了n次的调和函数，它们具有二次均匀B样条基函数的性质，且用它们生成的分段多项式曲线具有与分段二次均匀B样条曲线相同的结构和几何性质；又如，用一种混合基（代数多项式和三角函数的线性组合）代替三次多项式曲线方程中的幂基，并相应地修改基函数而形成的用曲线曲面方程所表示的曲线曲面，这就是一种新颖的曲线曲面造型方法C曲线曲面理论。07大多数物体的曲线曲面部分，都可以使用灵活的B样条曲线进行拟合。在基于PC系统的3D Max、AutoCAD、Maya等建模工具中，“样条曲线”以“基本图形对象”的存在形式，实现平面绘图、立体绘图基本功能，是“三维动画”的重要组成元素。1.2 主要工作本文主要的工作是系统的研究和整理Bezier和B样条曲线的算法、性质、作用以及样条曲线的其他相关基础知识，并基于VC+6.0对这两种样条曲线进行实现和性质比较。论文思路大致如下：首先讨论Bezier曲线。Bezier曲线在本质上是由调和函数根据控制点插值生成的，其运算量较大。de Casteljau算法的效率则要高得多。Bernstein调和函数在0，1上都是“活动”的，使得Bezier曲线不能作局部修改；且调和函数的次数与控制点的个数相关，使得高阶次Bezier曲线计算较为复杂，并且由于对数字取整也给结果带来误差；采用在点集中插入一些点“拼接”虽然可以满足多段Bezier曲线的光滑连接条件，但不方便。然后是寻找到能灵活控制曲线形状且计算量不大等更好性质的调和函数。为了获得足够的灵活性，可以试着把几个低次多项式分段“连接”起来。这样在不同的t分段区间上用不同多项式定义的曲线称为分段多项式。对曲线形状更自如地控制，并能够指定对哪些控制点插值，把讨论过的所有设计方法都封装进去，组成单个算法。用n次B样条基函数替换Bernstein基函数，便获得B(basis)样条曲线。接着是对B样条曲线进行研究。主要研究均匀B样条曲线的算法，并介绍非均匀B样条曲线和开放B样条曲线。Bezier曲线是B样条曲线的特例，B样条多项式的阶数增加1，每个B样条调和函数就支持扩展一个区间，同时降低了一些局部控制能力。当m到达边界n+1时，就得到了Bezier曲线，这时的局部控制能力为最小。Bezier曲线和B样条曲线之间可以进行相互转换。最后点明样条曲线是自由曲面的基础。另外，结合在VC+6.0上实现的Bezier和B样条曲线，对其性质进行直观的分析和比较。第2章 曲线基础2.1 曲线的参数表示曲线的表示可以分为参数表示和非参数表示两种，其中非参数表示又可分为显式表示和隐式表示两种。对于一个平面曲线，显式表示一般形式是y=f(x)。在此方程中，一个x值与一个y值对应，所以显式方程不能表示封闭或多值曲线，例如，不能用显式方程表示一个圆。如果一个平面曲线方程，表示成f(x,y)=0的形式，则称之为隐式表示。隐式表示的优点是易于判断函数f(x,y)是否大于、小于或等于零，也就易于判断点是落在所表示曲线上或曲线的哪一侧。非参数方程的缺点是：与坐标轴相关；会出现斜率为无穷大的情形（如垂线）；对于非平面曲线，难以用常数系数的非参数化函数表示；不便于计算机编程。由于参数表示的曲线具有几何不变性等优点，计算机图形学中通常用参数形式描述曲线。在几何造型系统中，曲线方程通常表示成参数的形式，即曲线上任一点的坐标均表示成给定参数的函数。假定用t表示参数，平面曲线上任一点P可表示为 (2.1)空间曲线上任一三维点P可表示为 (2.2)最简单的参数曲线是直线段，端点为、的直线段参数方程可表示为 (2.3)圆在计算机图形学中应用十分广泛，其在第一象限内的单位圆弧的非参数显式表示为其参数形式可表示为 (2.4)在曲线的表示上，参数方程比显式、隐式方程有更多的优越性，主要表现在一下几点。l 可以满足几何不变性的要求。l 有更大的自由度来控制曲线的形状。l 对非参数方程表示的曲线进行变换，必须对曲线上的每个型值点进行几何变换；而对参数表示的曲线可对其参数方程直接进行几何变换。l 便于处理斜率为无穷大的情形，不会因此而中断计算。l 参数方程中，代数、几何相关和无关的变量是完全分离的，而且对变量个数不限，从而便于用户把低维空间中曲线扩展到高维空间去。这种变量分离的特点使人们可以用数学公式处理几何分量。l 规格化的参数变量，使其相应的几何分量是有界的，而不必用另外的参数去定义边界。l 易于用向量和矩阵表示几何分量，简化了计算。2.2 插值与逼近2.2.1 插值给定一组有序的数据点(i=0,1,2,n)，构造一条曲线顺序通过这些数据点，称为对这些数据点进行插值，所构造的曲线称为插值曲线。(1) 线性插值假设给定函数f(x)在两个不同点和的值，用一个线形函数，近似代替f(x)，称为f(x)的线性插值函数。其中线性函数的系数是a，b，通过条件：可表示为： (2.5)(2) 抛物线插值抛物线插值又称为二次插值。设已知f(x)在3个互异点，的函数值为，要求构造一个函数：，使在结点处与在处的值相等。由此可构造的线性方程组，求得a，b，c，即构造了的插值函数。02图2-1 曲线的插值2.2.1 逼近当型值点较多时，构造插值函数通过所有型值点是相当困难的。而测量所得的数据点本身比较粗糙，使得构造精确的插值函数也是没有意义的。这时通常选择一个次数较低的函数，构造一条曲线使之在某种意义下最接近给定的数据点，称为对这些数据点进行逼近，所构造的曲线为逼近曲线。插值和逼近则统称为拟合。逼近的方法最常用的是最小二乘法，假设给定一组数据点，要求构造一个逼近函数。令是m次多项式，即逼近的程度可以通过各点偏差的平方和来度量。最小二乘问题就是要求出各系数，使偏差的平方和最小，即求解式(5.6)所示函数的极值问题： (2.6)如要取到极值，则 (2.7)这里只有m+1个系数是未知量，可通过求解m+1个方程得出。将系数带入多项式函数即可得到所求的逼近函数。图2-2 曲线的逼近022.3 连续性设计一条复杂曲线时，常常通过多段曲线组合而成，这需要解决曲线段之间如何实现光滑连接的问题。曲线间连接的光滑度的度量有以下两种。2.3.1 函数的可微性把组合参数曲线构造成在连接处具有直到n阶连续，即n阶连续可微，这类光滑度称之为或n阶参数连续性。2.3.2 几何连续性组合曲线在连接处满足不同于的某一组约束条件，称为具有n阶几何连续性，简记为。曲线光滑度的这两种度量方法并不矛盾，连续包含在连续之中。对于曲线P(t)和Q(t)，参数。若要求在接合处达到连续或连续，即两曲线在结合处位置连续，有 (2.8)若要求在结合处达到连续，就是说两条曲线在结合处在满足连续的条件下，并有公共的切线向量： (2.9)当时，连续就称为连续。若要求在结合处达到连续，就是说两条曲线在结合处在满足连续的条件下，并有公共的曲率：(2.10)将式(2.9)及式(2.10)合并整理，得(2.11)这个关系为(2.12)为任意函数。当时，连续就称为连续。2.4 样条描述样条（Spline）一词来源于工程绘图人员为了将一些指定点连接成一条光顺曲线所使用的工具，即富有弹性的细木条或薄钢条。最初，样条曲线都是借助于物理样条得到的，放样员把富有弹性的细木条（或有机玻璃条），用压铁固定在曲线应该通过的给定型值点处，样条做自然弯曲所绘制出来的曲线就是样条曲线。样条曲线不仅通过各有序型值点，并且在各型值点处的一阶和二阶导数连续，也即该曲线具有连续的、曲率变化均匀的特点。在计算机图形学中，样条曲线是指由多项式曲线段连接而成的曲线，在每段边界处满足特定的连续性条件。通常用式(2.9)来描述n次样条参数多项式曲线： (2.13)将式(2.9)写成矩阵乘积的形式，得 (2.14)其中C为(n+1)3阶的系数矩阵，T为n+1个幂形式的基函数组成的向量。022.5 三次样条多项式是一种基本的数学研究对象，在计算机图形学中经常使用多项式，这时因为多项式定义简介，并且计算起来效率很高。虽然Sederberg已经证明了对给定的多项式函数x(t)和y(t)，总能找到其隐式形式，但是一般来说，只有对一次或二次的隐式形式才总能找到其参数方程形式。用一次和二次多项式参数化的曲线很容易理解。当使用更高次的多项式时，情况就要复杂得多。三次多项式为曲线设计提供了一条功能强大的途径。但是这些方法不是从隐式形式出发寻找其参数化形式，而是从设计者选定的一组“控制点”出发，应用某个特定的算法生成曲线上的点，如果满意就接受这条曲线而不去管它的隐式形式。与单纯采用数学手段相比，这种方法在许多方面都是一种更自然的曲线设计方法。01三次多项式在灵活性和计算速度之间提供了一个合理的这种方案。与更高次的多项式相比，三次样条只需要较少的计算与存储且较稳定；与低次的多项式相比，三次样条又具有更多的灵活性，事实上，大多数形状表示与设计都是采用三次多项式来实现的。给定n+1个点，可得到通过每个点的分段三次多项式曲线：(2.15)方程组中12个系数唯一地确定了一条3次参数曲线的位置与形状。将式(2.11)写成向量式，得(2.16)其中a，b，c，d是代数系数向量，p(t)是三次参数曲线上任一点的位置向量。描述参数曲线的条件有端点位置向量、端点切线向量及曲率等。对三次参数曲线，可用其端点向量和端点切线向量描述，将简记为，则由式(2.13)可得 (2.17)将这些系数代回到原曲线方程,则曲线方程可表示为 (2.18)这时三次参数曲线为三次Hermite样条曲线，即 (2.19) (2.20)其中，是Hermite矩阵，它是边界约束矩阵的逆阵，通常为为常数。是Hermite几何向量。式（2.17）为三次Hermite样条曲线的方程：(2.21)在上式中只要给定，就可以求出p(t)。对于不同的初始条件是不同的，但T和都是相同的，将T称为Hermite基函数（也可以称为混合函数或调和函数）。其表达式为 (2.22)则Hermite基函数的各分量可写为(2.23)利用基函数表达的三次Hermite样条曲线的方程为 (2.24)其中和专门控制端点的函数值对曲线的影响，而同端点的导数值无关；和则专门控制端点的一阶导数值对曲线形状的影响，而同端点的函数值无关。或者说，和控制左端点的影响，和控制右端点的影响。三次Hermite样条曲线特点是可以局部调整，因为每个曲线段仅依赖于端点约束。基于Hermite样条的变化形式为Cardinal样条和Kochanek-Bartels样条。Hermite曲线具有几何不变性。02