计算机图形学算法基础作业.doc

《计算机图形学算法基础作业.doc》由会员分享，可在线阅读，更多相关《计算机图形学算法基础作业.doc（86页珍藏版）》请在三一办公上搜索。

1、计算机图形学算法基础作业姓名： LH 学院： 理学院 专业： 计算数学 时间： 2010-12-31 目录1 直线段生成算法综述11.1 生成直线的DDA方法11.1.1 DDA算法基本原理11.1.2 DDA算法实现步骤11.1.3 DDA算法程序（或伪程序）描述21.1.4 DDA算法流程图21.2 生成直线的Bresenham算法31.2.1 Bresenham算法基本原理31.2.2 Bresenham算法实现步骤51.2.3 Bresenham算法程序（或伪程序）描述51.2.4 Bresenham算法流程图51.3 中点画线算法21.3.1 中点画线算法基本原理21.3.2 中点画

2、线算法实现步骤31.3.3 中点画线算法程序（或伪程序）描述31.3.4 中点画线算法流程图31.4 生成直线算法的进一步改进51.5 各种直线生成算法的优缺点对比分析61.6 直线生成算法的发展趋势72 椭圆的Bresenham生成算法72.1 椭圆曲率分析72.2 椭圆方程分析72.3 椭圆生成算法92.3.1 算法实现过程92.3.2 算法流程图102.3.3 算法程序描述113 直线段裁剪算法综述113.1 Sutherland-Cohen裁剪算法113.1.1 Sutherland-Cohen算法基本原理113.1.2 Sutherland-Cohen算法实现步骤113.1.3 算法

3、程序（或伪程序）描述123.1.4 算法流程图123.2 中点分割裁剪算法123.2.1 中点分割算法基本原理与实现步骤123.2.2 算法程序（或伪程序）描述133.2.3 算法流程图133.3 梁友栋Barskey算法143.3.1 梁友栋Barskey算法基本原理与实现步骤143.3.2 算法程序（或伪程序）描述153.3.3 算法流程图153.4 快速算法153.5 其余一些改进的直线裁剪算法163.6 各种直线裁剪算法的优缺点对比分析163.7 直线裁剪算法的发展趋势164 图形求交技术164.1 求交点算法164.1.1 线与线的交点的求法174.2.2 线与面的交点的求法184.

4、2 求交线算法194.3 包含判定算法214.4 重叠判定算法264.5 凸包计算265 自由曲线曲面造型技术285.1 Bezier曲线和曲面285.1.1 Bezier曲线285.1.2 Bezier曲面315.2 B样条曲线与曲面325.2.1 B样条的递推定义和性质325.2.2 B样条曲线345.2.5 B样条曲面365.3 NURBS曲线与曲面375.3.1 NURBS曲线375.3.2 非均匀有理B样条（NURBS）曲面395.4 Coons 曲面405.4.1 基本概念405.4.2 双线性Coons曲面415.4.3 双三次Coons曲面426 CAGD中有关曲线曲面、拼接技

5、术446.1 基本原理446.2 Bezier曲线的的拼接条件446.3 Bezier曲面的的拼接条件467 图形变换技术487.1 二维图形几何变换497.1.1 平移(Translation)497.1.2 旋转(Rotation)497.1.3 变比(scaling)507.2 三维图形几何变换517.2.1 平移517.2.2 旋转517.2.3 变比547.3 参数图形几何变换547.3.1 圆锥曲线的几何变换547.3.2 参数曲线、曲面的几何变换557.4 投影变换587.4.1 平行投影(parallel projection)587.4.2 透视投影(perspective

6、projection)608 图形消隐算法618.1 扫描线Z-buffer算法618.2 区域子分割算法618.3 光线投射算法628.4 平面公式法628.5 径向预排序法638.6 径向排序法638.7 隔离平面法638.8 深度排序法638.9 光线跟踪法638.10 Z缓冲区法648.11 极值检测法648.12 深度分类方法648.13 八叉树方法659 图形学若干基本算法的实现研究65参考文献68附录68图形学算法基础作业1 直线段生成算法综述1.1 生成直线的DDA方法1.1.1 DDA算法基本原理DDA是数字微分分析式（Digital Differential Analyze

7、r）的缩写。设直线之起点为，终点为，则斜率为：直线中的每一点坐标都可以由前一点坐标变化一个增量而得到，即表示为递归式：并有关系：递归式的初值为直线的起点，这样，就可以用加法来生成一条直线。1.1.2 DDA算法实现步骤具体方法是：按照直线从到的方向不同，分为8个象限（见图1.1）。对于方向在第1a象限内的直线而言，。对于方向在第1b象限内的直线而言，取值。各象限中直线生成时的取值列在表1-1之中。图1.1 直线方向的8个象限图表1-1 各象限中直线生成时的取值列象限1a1b2a2b3a3b4a4bTFTFTFTF11/m-1-1/m-1-1/m11/mm1m1-m-1-m-1研究表中的数据，可

8、以发现两个规律：1、当时；否则：2、的符号与的符号相同。这两条规律可以导致程序的简化。由上述方法写成的程序如附录1所示。其中steps变量的设置，以及等语句，正是利用了上述两条规律，使得程序变得简练。使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。1.1.3 DDA算法程序（或伪程序）描述具体程序见附录1。1.1.4 DDA算法流程图（略）1.2 中点画线算法1.2.1 中点画线算法基本原理假定直线斜率在之间，当前象素点为，则下一个象素点有两种可选择点或。若与的中点称为M，Q为理想直线与垂线的交点。当M在Q的下方时，则取应为下一个象素

9、点；当M在Q的上方时，则取为下一个象素点。这就是中点画线法的基本原理。1.2.2 中点画线算法实现步骤下面讨论中点画线法的实现。过点、的直线段L的方程式为，其中，要判断中点M在Q点的上方还是下方，只要把M代入，并判断它的符号即可。为此，我们构造判别式:当时，M在L(Q点)下方，取为下一个象素；当时，M在L(Q点)上方，取为下一个象素；当时，选或均可，约定取为下一个象素。注意到是的线性函数，可采用增量计算，提高运算效率。若当前象素处于情况，则取正右方象素,要判下一个象素位置，应计算，增量为a。 若时，则取右上方象素。要判断再下一象素，则要计算，增量为。画线从开始，的初值，因，所以。 由于我们使用

10、的只是的符号，而且的增量都是整数，只是初始值包含小数。因此，我们可以用代替来摆脱小数，写出仅包含整数运算的算法程序。1.2.3 中点画线算法程序（或伪程序）描述具体程序见附录21.2.4 中点画线算法流程图 （略）1.3 生成直线的Bresenham算法1.3.1 Bresenham算法基本原理本算法由Bresenham在1965年提出。设直线从起点到终点。直线可表示为方程。其中我们讨论先将直线方向限于1a象限（图1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即 。而y的相应增加应当小于1。为了光栅化，只可能选择如图1.2两种位置之一。图1.2 的位置选择图1.2中 的位置选择

11、或者 选择的原则是看精确值与及的距离d1及d2的大小而定。计算式为：如果，则，否则。因此算法的关键在于简便地求出的符号。将式（1.2.1）、（1.2.2）、（1.2.3）代入，得用乘等式两边，并以代入上述等式，得是我们用以判断符号的误差。由于在1a象限，总大于0，所以仍旧可以用作判断符号的误差。为：误差的初值P1，可将x1, y1，和b代入式（2.1.4）中的而得到：1.3.2 Bresenham算法实现步骤综述上面1.3.1的推导，第1a象限内的直线Bresenham算法思想如下：1、画点(x1, y2); 计算误差初值P1=2dy-dx; i=1；2、求直线的下一点位置：xi+1=xi+1

12、；if Pi0 则yi+1=yi+1；否则yi+1=yi；3、画点（xi+1, yi-1）；4、求下一个误差Pi+1；if Pi0 则Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1; if is.r) 两个面无交；else 所求交线是圆。其圆半，半径，圆所在平面法向量为c=s.c-d * p. w;r=sqr t(s.r2-d2);w=p.w;一个平面与一个圆柱面可以无交、交于一条直线（切线）、二条直线、一个椭圆或一个圆，可以用两个面的定义参数求出它们的相对位置关系和相对角度关系，进而判断其交属于何种情况，并求出交线的定义参数。平面与圆锥的交线也可类似求出。3、平面

13、与参数曲面的交线 最简单的方法是把参数曲面的表示代入平面方程得到用参数曲面的参数s、t表示的交线方程另一种方法是用平移和旋转变换对平面进行坐标变换，使平面成为新坐标系下的平面。再用相同的变换应用于参数曲面方程得到参数曲面在新坐标系下的方程由此得交线在新坐标系下的方程为。4.3 包含判定算法在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此下面主要讨论关于点的包含判定算法。判断点与线段的包含关系，也就是判

14、断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：1、直线段；2、圆锥曲线段（主要是圆弧）；3、参数曲线（主要是Bezier，B样条与NURBS曲线）。点与面的包含判定也类似地分为三种情况。下面分别讨论。1、点与直线段的包含判定假设点坐标为，直线段端点为，则点P到线段的距离的平方为 当时，认为点在线段（或其延长线）上，这时还需进一步判断点是否落在直线段的有效区间内。只要对坐标分量进行比较，假设线段两端点的x分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点），那么当与反号时，点P在线段的有效区间内。2、点与圆锥曲线段的包含判定以圆弧为例，假设点的坐标为，圆弧的中心为，

15、半径为，起始角，终止角。这些角度都是相对于局部坐标系x轴而言。圆弧所在平面为 先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。给定中心为，半径为，起始角，终止角的圆弧，对平面上一点，判断P是否在圆弧上，可分二步进行。第一步判断P是否在圆心为，半径为的圆的圆周上，即下式是否成立： 第二步判断P是否在有效的圆弧段内。3、点与参数曲线的包含判定设点坐标为，参数曲线为。点也参数曲线的求交计算包括三个步骤：（1）计算参数值，使到的距离最小；（2）判断是否在有效参数区间内（通常为）；（3）判断与的距离是否小于 。若（2），（3）步的判断均为“是”，则点在曲线

16、上；否则点不在曲线上。第一步应计算，使得最小，即最小根据微积分知识，在该处即用数值方法解出值，再代入曲线参数方程可求出曲线上对应点的坐标。第（2）、（3）步的处理比较简单，不再详述。4、点与平面区域的包含判定设点坐标为，平面方程为。则点到平面的距离为 若 ，则认为点在平面上，否则认为点不在平面上。在造型系统中，通常使用平面上的有界区域作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点落在该区域内，则认为点与该面相交，否则不相交。下面以平面区域多边形为例，介绍有关算法。判断平面上一个点是否包含在同平面的一个多边形内，有许多种算法，这里仅介绍常用的三种：叉积判断

17、法、夹角之和检验法以及交点计数检验法。（1）叉积判断法假设判断点为。多边形顶点按顺序排列为。如图4.2所示。令。那么，在多边形内的充要条件是叉积的符号相同。叉积判断法仅适用于凸多边形。当多边形为凹时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用后面介绍的两种方法。图4.2 叉积判断法（2）夹角之和检验法假设某平面上有点和多边形，如图4.3所示。将点分别与相连，构成向量。假设角 。如果，则点在多边形之外，如图4.3(a)所示。如果，则点在多边形之内，如图4.3(b)所示。可通过下列公式计算：令, ，则，所以且的符号即代表角度的方向。图4.3 夹角之和检验法在多边形边数不太多（44）的

18、情况下，可以采用下列近似公式计算。其中为常数。当时，可判在多边形内。当时，可判在多边形外。证明略。（3）交点计数检验法当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。具体做法是，从判断点作一射线至无穷远：求射线与多边形边的交点个数。若个数为奇数，则点在多边形内，否则，点在多边形外。如图4.4所示，射线a, c分别与多边形交于二点和四点，为偶数，故判断点A，C在多边形外。而射线b, d与多边形交三点和一点，为奇数，所以B，D在多边形内。当射线穿过多边形顶点时，必须特殊对待。如图2.5.4所示，射线f过顶点，若将交点计数为2，则会错误地判断F在多边形外。但是，若规定射线过顶点时，计数为1，则又会错误地判断点E在多边形内。正确的方法是，若共享顶点的两边在射线的同一侧，则交点计数加2，否则加1。按这种方法，E点计为2，所以在多边形外；F点计数为，所以在多边形内。图4.4 交点计数法5、点与二次曲面/参数曲面的包含判定假设点坐标为，二次曲面方程为，则当 时，认为点在该二次曲面上，在造型系统中，通常使用裁剪的二次曲面。在这种情况下，还要判断点是否在有效范围内。裁剪的二次曲面通常用有理Bezier或有理B样条的参数空间上的闭合曲线来定义曲面的有效范围，故要把点所