计算机图形学各种算法的作业（偏于理论）

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

姓名：学院：专业：时间：

LH 理学院 计算数学 2010-12-31

LH的计算机图形学作业

目录

1 直线段生成算法综述 ................................................................... 1

1.1 生成直线的DDA方法 ........................................................ 1

1.1.1 DDA算法基本原理 ....................................................... 1 1.1.2 DDA算法实现步骤 ....................................................... 1 1.1.3 DDA算法程序（或伪程序）描述 .................................. 2 1.1.4 DDA算法流程图 .......................................................... 2

1.2 生成直线的Bresenham算法 ............................................. 3

1.2.1 Bresenham算法基本原理 ............................................ 3 1.2.2 Bresenham算法实现步骤 ............................................ 5 1.2.3 Bresenham算法程序（或伪程序）描述 ........................ 5 1.2.4 Bresenham算法流程图 ................................................ 5

1.3 中点画线算法 .................................................................... 2

1.3.1 中点画线算法基本原理 ............................................... 2 1.3.2 中点画线算法实现步骤 ............................................... 3 1.3.3 中点画线算法程序（或伪程序）描述 ........................... 3 1.3.4 中点画线算法流程图 .................................................. 3

1.4 生成直线算法的进一步改进 ............................................. 5 1.5 各种直线生成算法的优缺点对比分析 .............................. 6 1.6 直线生成算法的发展趋势 ................................................. 7 2 椭圆的Bresenham生成算法 ................................................... 7

I

LH的计算机图形学作业

2.1 椭圆曲率分析 .................................................................... 7 2.2 椭圆方程分析 .................................................................... 7 2.3 椭圆生成算法 .................................................................... 9

2.3.1 算法实现过程 ............................................................. 9 2.3.2 算法流程图 .............................................................. 10 2.3.3 算法程序描述 ............................................................ 11

3 直线段裁剪算法综述 ........................................................... 11

3.1 Sutherland-Cohen裁剪算法 ........................................... 11

3.1.1 Sutherland-Cohen算法基本原理................................ 11 3.1.2 Sutherland-Cohen算法实现步骤................................ 11 3.1.3 算法程序（或伪程序）描述 ...................................... 12 3.1.4 算法流程图 .............................................................. 12

3.2 中点分割裁剪算法 .......................................................... 12

3.2.1 中点分割算法基本原理与实现步骤 ............................ 12 3.2.2 算法程序（或伪程序）描述 ...................................... 13 3.2.3 算法流程图 .............................................................. 13

3.3 梁友栋－Barskey算法 .................................................... 14

3.3.1 梁友栋－Barskey算法基本原理与实现步骤 ............... 14 3.3.2 算法程序（或伪程序）描述 ...................................... 15 3.3.3 算法流程图 .............................................................. 15

3.4 快速算法 ......................................................................... 15 3.5 其余一些改进的直线裁剪算法 ....................................... 16

II

LH的计算机图形学作业

3.6 各种直线裁剪算法的优缺点对比分析 ............................ 16 3.7 直线裁剪算法的发展趋势 ............................................... 16 4 图形求交技术 ...................................................................... 16

4.1 求交点算法 ...................................................................... 16

4.1.1 线与线的交点的求法 ................................................ 17 4.2.2 线与面的交点的求法 ................................................ 18

4.2 求交线算法 ...................................................................... 19 4.3 包含判定算法 .................................................................. 21 4.4 重叠判定算法 .................................................................. 26 4.5 凸包计算 ......................................................................... 26 5 自由曲线曲面造型技术 ........................................................ 28

5.1 Bezier曲线和曲面 ......................................................... 28

5.1.1 Bezier曲线 ............................................................. 28 5.1.2 Bezier曲面 ............................................................. 31

5.2 B样条曲线与曲面 ........................................................... 32

5.2.1 B样条的递推定义和性质 .......................................... 32 5.2.2 B样条曲线 ............................................................... 34 5.2.5 B样条曲面 ............................................................... 36

5.3 NURBS曲线与曲面 ........................................................... 37

5.3.1 NURBS曲线 ............................................................... 37 5.3.2 非均匀有理B样条（NURBS）曲面 .............................. 39

5.4 Coons 曲面 ...................................................................... 40

III

LH的计算机图形学作业

5.4.1 基本概念 .................................................................. 40 5.4.2 双线性Coons曲面 .................................................... 41 5.4.3 双三次Coons曲面 .................................................... 42

6 CAGD中有关曲线曲面Cn、Gn拼接技术 ................................. 44

6.1 基本原理 ......................................................................... 44 6.2 Bezier曲线的C0、G0、C、G、C、112的.......... 44 G2拼接条件

6.3 Bezier曲面的C0、G0的、C、G11拼接条件 ...................... 46 7 图形变换技术 ...................................................................... 48

7.1 二维图形几何变换 .......................................................... 49

7.1.1 平移(Translation) .................................................. 49 7.1.2 旋转(Rotation) ....................................................... 49 7.1.3 变比(scaling) ......................................................... 50

7.2 三维图形几何变换 .......................................................... 51

7.2.1 平移 ........................................................................ 51 7.2.2 旋转 ........................................................................ 51 7.2.3 变比 ........................................................................ 54

7.3 参数图形几何变换 .......................................................... 54

7.3.1 圆锥曲线的几何变换 ................................................ 54 7.3.2 参数曲线、曲面的几何变换 ...................................... 55

7.4 投影变换 ......................................................................... 58

7.4.1 平行投影(parallel projection) .............................. 58 7.4.2 透视投影(perspective projection) ......................... 60

IV

LH的计算机图形学作业

8 图形消隐算法 ...................................................................... 61

8.1 扫描线Z-buffer算法 ..................................................... 61 8.2 区域子分割算法 .............................................................. 61 8.3 光线投射算法 .................................................................. 62 8.4 平面公式法 ...................................................................... 62 8.5 径向预排序法 .................................................................. 63 8.6 径向排序法 ...................................................................... 63 8.7 隔离平面法 ...................................................................... 63 8.8 深度排序法 ...................................................................... 63 8.9 光线跟踪法 ...................................................................... 63 8.10 Z缓冲区法 ..................................................................... 64 8.11 极值检测法 .................................................................... 64 8.12 深度分类方法 ................................................................ 64 8.13 八叉树方法 .................................................................... 65 9 图形学若干基本算法的实现研究 .......................................... 65 参考文献 ................................................................................ 68 附录 ....................................................................................... 68

V

LH计算机图形学作业：共九道题

图形学算法基础作业

1 直线段生成算法综述

1.1 生成直线的DDA方法 1.1.1 DDA算法基本原理

DDA是数字微分分析式（Digital Differential Analyzer）的缩写。设直线之起点为（x1,y1），终点为（x2,y2），则斜率k为：

k=y2-y1dy =x2-x1dx直线中的每一点坐标都可以由前一点坐标变化一个增量?Dx,Dy?而得到，即表示为递归式：

xi?1?xi?Dxyi?1?yi?Dy并有关系：Dy ? m ? Dx

递归式的初值为直线的起点（x1,y1），这样，就可以用加法来生成一条直线。

1.1.2 DDA算法实现步骤

具体方法是：

按照直线从（x1,y1）到（x2,y2）的方向不同，分为8个象限（见图1.1）。对于方向在第1a象限内的直线而言，Dx?1，Dy?m。对于方向在第1b象限内的直线而言，取值Dy?1，Dx?1/m。各象限中直线生成时Dx, Dy的取值列在表1-1之中。

图1.1 直线方向的8个象限图

1

LH计算机图形学作业：共九道题

表1-1 各象限中直线生成时Dx, Dy的取值列

象限 1a 1b 2a 2b 3a 3b 4a 4b dx?dyT F T F T F T F ? Dx 1 1/m -1 -1/m -1 -1/m 1 1/m Dy m 1 m 1 -m -1 -m -1 研究表中的数据，可以发现两个规律：

Dy=1 1、当dx?dy时Dx=1, Dy=m；否则：Dx=1/m，2、Dx, Dy的符号与dx, dy的符号相同。这两条规律可以导致程序的简化。由上述方法写成的程序如附录1所示。其中steps变量的设置，以及Dx=dx/steps; Dy=dy/steps等语句，正是利用了上述两条规律，使得程序变得简练。

使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。 1.1.3 DDA算法程序（或伪程序）描述

具体程序见附录1。 1.1.4 DDA算法流程图

（略） 1.2 中点画线算法

1.2.1 中点画线算法基本原理

假定直线斜率k在0?1之间，当前象素点为(xp,yp)，则下一个象素点有两种可选择点P1(xp?1,yp)或P2(xp?1,yp?1)。若P1与P2的中点(xp?1,yp?0.5)称为M，Q为理想直线与x?xp?1垂线的交点。当M

2

LH计算机图形学作业：共九道题

在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。这就是中点画线法的基本原理。 1.2.2 中点画线算法实现步骤

下面讨论中点画线法的实现。过点(x0,y0)、(x1,y1)的直线段L的方程式为F(x,y)?ax?by?c?0，其中a?y0?y1,b?x0?x1，

c?x0y1?x1y0，要判断中点M在Q点的上方还是下方，只要把M

y并判断它的符号即可。为此，我们构造判别式: 代入F(x,，

d?F(M)?F(xp?1,yp?0.5)?a(xp?1)?b(yp?0.5)?c

当d?0时，M在L(Q点)下方，取P2为下一个象素； 当d?0时，M在L(Q点)上方，取P1为下一个象素； 当d?0时，选P1或P2均可，约定取P1为下一个象素。

注意到d是xp,yp的线性函数，可采用增量计算，提高运算效率。 若当前象素处于d?0情况，则取正右方象素P1(xp?1,yp),要判下一个象素位置，应计算d1?F(xp?2,yp?0.5)?a(xp?2)?b(yp?0.5)?c?d?a，增量为a。

若d?0时，则取右上方象素P2(xp?1,yp?1)。要判断再下一象

?素，则要计算d2?F(px增量为

2p,?y1?.5p)?a(?xp2?)b?(y?，1?.5?)cda?b。画线从

0(x0,y0)开始，

d的初值

d0?F(0?x1?,y?。 00.5)，因?FF(x(0x,y0),?0y，)所以ad0?0a?.0.5b5b0? 由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法程序。 1.2.3 中点画线算法程序（或伪程序）描述

具体程序见附录2 1.2.4 中点画线算法流程图 （略）

1.3 生成直线的Bresenham算法 1.3.1 Bresenham算法基本原理

本算法由Bresenham在1965年提出。设直线从起点（x1, y1）到终点。直线可表示为方程y=kx+b。其中 （x2, y2） 3

LH计算机图形学作业：共九道题

b=y1?k?x1

k=y2-y1dy=

x2-x1dx我们讨论先将直线方向限于1a象限（图1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即 xi?1=xi+1。而y的相应增加应当小于1。为了光栅化，yi+1只可能选择如图1.2两种位置之一。

图1.2 yi+1的位置选择

图1.2中 yi+1的位置选择yi-1=yi 或者 yi+1=yi+1

选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算式为：

y=m?xi+1?+b d1=y-yi d2=yi+1-y (1.2.1)(1.2.2)

(1.2.3)0则yi+1=yi+1，否则yi+1=yi。因此算法的关键在于简便如果d1-d2>，

2符号。将式（1.2.1）地求出d1-d的、（1.2.2）、（1.2.3）代入d1-d2，

得

d1-d2=2y-2yi-1=2dy(xi+1)-2yi+2b-1 dx用dx乘等式两边，并以Pi=dx?d1-d2?代入上述等式，得

Pi=2xidy-2yidx+2dy+dx?2b-1? (1.2.4)

d1-d2是我们用以判断符号的误差。由于在1a象限，dx总大于0，所以

Pi仍旧可以用作判断符号的误差。Pi?1为：

Pi+1=Pi+2dy-2dx?yi+1-yi? (1.2.5)

i得到：误差的初值P1，可将x1, y1，和b代入式（2.1.4）中的xi, y而

4

LH计算机图形学作业：共九道题

P1=2dy-dx

1.3.2 Bresenham算法实现步骤

综述上面1.3.1的推导，第1a象限内的直线Bresenham算法思想如下：

1、画点(x1, y2); dx?x2?x1; dy? y2?；y1计算误差初值P1=2dy-dx; i=1； 2、求直线的下一点位置：

xi+1=xi+1；

if Pi>0 则yi+1=yi+1； 否则yi+1=yi； 3、画点（xi+1, yi-1）； 4、求下一个误差Pi+1；

if Pi>0 则Pi+1=Pi+2dy-2dx; 否则Pi+1=Pi+2dy；

5、i=i+1; if i

由上述算法思想编制的程序见附录3。这个程序适用于所有8个方向的直线（图1.1）的生成。程序用色彩C画出一条端点为（x1, y1）和的直线。其中变量的含义是：P是误差；const1和const2，是（x2, y2）误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断dx>d为y分支，并分别将2a,3a象限的直线和3b,4b象限的直线变换到1a,4a和2b,1b方向去，以求得程序处理的简洁。

1.3.4 Bresenham算法流程图

（略）

1.4 生成直线算法的进一步改进

除过前面所讲到的3种基本直线生成算法外，还有一些其它的方法，由于过多，这里仅列举几种如下：

（1）二步法。虽然Bresenham直线生成算法是一效率很高的算法，但是人们仍在寻找更有校的算法。1987年又有人提出了一种二步法。

5

LH计算机图形学作业：共九道题

即每循环一次不是绘制一个像素，而是绘制两个像素，这样无疑可把生成直线的速度提高一倍。

（2）改进的Bresenham算法。对于对于传统的直线生成算法，人们往往把注意力集中在算法本身，却忽略了算法之外的一些有用信息:画线之前，从起点坐标和终点坐标，我们就可以获知该线段的斜率，由此可进一步得出在主轴方向连续走l个步长，在副轴方向才走一个坐标单位，这就是本算法提高Bresenham算法执行效率的一个方面。提高算法效率的第二个方面是利用线段本身的对称性，则新算法所产生的起点一侧的半条线段与用Bresenham算法产生的相同。至于终点一侧的半条线段，可以看成以终点为起点线段的生成。

算法实现：

特殊地，对于水平线(?y?0)，垂直线(?x?0)和对角线(x?y)，它们都可直接装人帧缓冲器，而无需进行画线算法处理。

从以上的描述可以实现优于Bresenham的直线生成算法。其中待生成直线的已知数据为:(x1,y1)为线段起点的横、纵坐标；(x2,y2)为线段终点的横、纵坐标。

算法的输人数据为: (x1,y1)，(x2,y2)。

（3）基于类最佳逼近的散步直线生成算法。一种新的直线逼近方法—类最佳逼近,基于这种逼近方法,斜率k??0,0.5直线和斜率为1?k?的的直线具有某种互补性质。利用该性质,设计出一种新的三步直线方法,该算法揭示了直线计算的互补性,理论简单,精度达到最好。这种算法改善了Bresenham算法和双步算法的计算效率。该算法对于硬件实现将更有益处。

除此之外直线生成算法还有对称扫描四步增量画线算法、基于Bresenham的高效直线生成集成算法、基于Bresenham算法的四步画直线算法、基于直线特性的直线生成集成算法、基于自适应步长的直线生成算法、基于等分像素点的直线生成算法、6步直线生成算法、基于对角线行程的直线生成算法等等。

1.5 各种直线生成算法的优缺点对比分析

DDA算法的优点是：绘制实数直线效果好，误差小；缺点是：实现较复杂，不利于硬件实现。因为该算法涉及到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y四舍五入后取整。

6

LH计算机图形学作业：共九道题

中点画线算法优点是：只有整数运算，不含乘除法；可用硬件实现。 Bresenham算法的优点是：

1、不必计算直线之斜率，因此不做除法； 2、不用浮点数，只用整数；

3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。 4、Bresenham算法速度很快，并适于用硬件实现。 1.6 直线生成算法的发展趋势

（略）

2 椭圆的Bresenham生成算法

2.1 椭圆曲率分析

nt椭圆r??acost,bsi?（

方向的短半轴长度，且

a为沿x轴方向的长半轴长度，b为沿y轴

22223/2a?b），曲率为kr?ab/(asint?bcost)，在

第一象限t??0,?/2?，将kr对t求导数，有dkr/dt?0，即曲率为减函数，

)即t?0）处的曲率在点(a,0（

kr(t?0)?a/b2；在点(0,b)（即t??/2）处的

曲率

22kr(t??/2?b/aa/aa。半径为的圆的曲率为，半径为b的圆的曲)率为

b/b2，两圆的曲率关系为b/b2?a/a2(a?b)，则两圆的曲率在椭

22)(0,b)的曲率之间，圆上点(a,0与四者的关系为：a/b?1/b?1/a?b/a。

2.2 椭圆方程分析

根据椭圆及圆的曲率分析，椭圆弧分别由半径为

a和b的圆弧逼近

生成。为了更准确的由圆弧生成椭圆弧，在椭圆弧上确定一点P0，将椭圆弧分成曲率较小和曲率较大的两段，椭圆方程为：

F?x,y??b2x2?a2y2?a2b2?0。

其中度，且

a为沿x轴方向的长半轴长度，b为沿y轴方向的短半轴长

a?b?0。由于椭圆的对称性，这里只要讨论第一象限椭圆弧

7

LH计算机图形学作业：共九道题

的生成。将椭圆弧分为上下两部分，以弧上曲率为-1的点（即法向量两个分量相等的点）作为分界。该椭圆上一点(x,y)处的法向量为：

N(x,y)??F?Fi?j?2b2xi?2a2yj ?x?y结合椭圆方程可计算出分界点P0的坐标为：

(a2/a2?b2,b2/a2?b2)。

以P0点为分界点，将第一象限的圆弧分成曲率较大和较小的两段弧。如图2.1所示，

y?[b2/a2?b2,b]椭圆弧，与半径为a的圆在点的

22222T1(0a,到)T2(a/a?b,ab/a?b)的圆弧上对应。在椭圆弧上任取一

点Q1，过Q1作垂直线与圆交于P1点，连接圆心与P1点，与Y轴的夹角为

θ。则

椭圆的参数方程可表示为：

'??x?asinθ,?' ??y?bcosθ.圆的参数方程可表示为：

?x?asinθ, ?y?acosθ.?对于同一θ，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：

'??x?x,?' y?(b/a)y.??

图2.1 圆弧与椭圆弧对应点之一 图2.2 圆弧与椭圆弧对应点之一

8

LH计算机图形学作业：共九道题

如图2.2所示，半径为

22222b的圆上，从点T3(a/ab?b,b/a?b)到

T4(b,0)的圆弧与椭圆上y?(0,b2/a2?b2的)椭圆弧对应，在椭圆弧上任

取一点Q2，过Q2作垂直线与圆交于P2点，连接圆心与P2点，与Y轴的夹角为

θ。则

椭圆的参数方程可表示为：

'??x?asinθ,?' y?bcosθ.??圆的参数方程可表示为：

?x?bsinθ, ?y?bcosθ.?对于同一θ，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：

'??x?(a/b)x,?' y?y.??2.3 椭圆生成算法

当圆弧上的点从(a,0)沿着图2.1、图2.2的对应关系方向变化到

(b,0)时，椭圆弧上相对应的点也从该方向变化到(a,0)。

2.3.1 算法实现过程

1、计算分界点P0(x0,y) 0。

2、用Bresenham算法生成两段圆弧C1、C2。C1半径为a，

x?[0,a2/a2?b2]；C2半径为b，y?[0,b2/a2?b2]。

3、将圆弧C1进行比例变换：例系数为

x方向的比例系数为

1，

y方向的比

b/a；将圆弧C2进行比例变换：x方向的比例系数为a/b，

1。

y方向的比例系数为

9

LH计算机图形学作业：共九道题

4、如图2.3，已知椭圆上在第一象限的点三个象限与

Q(x,y)，则椭圆上另外

Q(x,y,(?x,y)?,，(x因此只点)对称的点分别为(?x,y)?要画出在第一象限的图形，即可得到整个椭圆的图形。

图2.3 椭圆对称性

2.3.2 算法流程图

椭圆的Bresenham算法流程图如下：

开始 计算分界点P0?x0,y0? 椭圆上点Y的坐标大于y0 Y 用Bresenham算法计算圆弧Tx,Ty N ??用Bresenham算法计算圆弧Tx,Ty ??计算对应圆弧上的点 Y 椭圆上点的Y坐标大于0 N 结束

图2.4 椭圆的Bresenham算法流程图

10

LH计算机图形学作业：共九道题

2.3.3 算法程序描述

具体程序实现见附录5。

3 直线段裁剪算法综述

裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。

直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。 3.1 Sutherland-Cohen裁剪算法 3.1.1 Sutherland-Cohen算法基本原理

Sutherland–Cohen算法分成两步。第一步是判断直线段是否完全在窗口内，若在则该线段称为完全可见的；或可显然的决定线段完全在窗口的外边，称为完全不可见；对不能判断完全可见或完全不可见的线段则要进行第二步处理。这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，把其中一段显然完全不可见的线段抛弃，对余下的部分再作第一步判断，重复上述过程，直到直线段最后余下的部分可以用第一步的判断得出肯定结论为止。 3.1.2 Sutherland-Cohen算法实现步骤

基本思想：对于每条线段p1p2分为三种情况处理分为三种情况处理:

（1）若p1p2完全在窗口内，则显示该线段p1p2，简称“取”之。 （2）若p1p2明显在窗口外，则丢弃该线段，简称“弃”之。 （3）若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 为快速判断，采用如下编码方法：

每个区域赋予4位编码（如图3.1所示）：

CtCbCrCl

其中：

?1Ct???0y?ymaxother?1Cb???0y?ymin other 11

LH计算机图形学作业：共九道题

?1Cr???0x?xmaxother?1Cl???0x?xminother

yT yB 1001 1000 0001 0101 0000 0100 1010 0010 0110 xL xR

x

图3.1 区域编码 图3.2 线段不能用编码确定

若p1p2完全在窗口内code1=0,且code2=0,则“取” 若p1p2明显在窗口外code1&code2≠0，则“弃”

在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

计算线段p1?x1,y1?p2?x2,y2?与窗口边界的交点

if(LEFT&code !=0)

{ x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} else if(RIGHT&code !=0)

{ x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} else if(BOTTOM&code !=0)

{ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);} else if(TOP & code !=0)

{ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);} 3.1.3 算法程序（或伪程序）描述

过程clip描述了这一算法。其中用一个集合(top,bottom,right,left)来表示端点的编码。具体程序见附录6。 3.1.4 算法流程图

（略）

3.2 中点分割裁剪算法

3.2.1 中点分割算法基本原理与实现步骤

与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，

12

LH计算机图形学作业：共九道题

并把线段与窗口的关系分为三种情况：完全可见、完全不可见和线段与窗口有交。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。

求线段与窗口的交点如下：

设要裁剪的线段是P0P1。中点分割算法可分成两个过程平行进行，即从P0出发找出离P0最近的可见点（图3.3中的A点），和从P1出发找出离P1最近的可见点（图3.3中的B点）。这两个最近可见点的连线就是原线段的可见部分。

从P0出发找出最近可见点的办法是先求P0P1的中点Pm，若P0Pm不能定为显然不可见，则取P0Pm代替P0P1，否则取PmP1代替P0P1，再对新的P0P1求中点Pm。重复上述过程，直到P1Pm长度小于给定的小数?为止。

图3.4是求P0的最近可见点P的算法框图。求P1的最近可见点的算法框图是一样的，只要把P0和P1交换即可。

在显示时?可取成一个像素的宽度，对分辨率为2N?2N的显示器来说，上面讲的二分的过程最多只要做N次。由于计算机过程只要做加法和除2，所以特别适合用硬件来实现。

如果允许两个找最近点的过程平行进行，这样的话可使裁剪速度加快，增加算法效率。

图3.3 中点分割算法

3.2.2 算法程序（或伪程序）描述

具体程序见附录7。 3.2.3 算法流程图

中点分割算法框图如图3.4。

13

LH计算机图形学作业：共九道题

P0可见否? 否 是 P?P0 exit 是 显然不可P0P1否 原线完全不可Pm?(P0?P1)/2是 P1?Pm??否 P0?Pm exit P0Pm显然不可见? 是 否 P0?PmP1?Pm

图3.4 中点分割算法框图

3.3 梁友栋－Barskey算法

3.3.1 梁友栋－Barskey算法基本原理与实现步骤

设要裁剪的线段是P0P1，Pi的坐标是?xi,yi?,i?0,1。P0P1和窗口边界交于A、B、C、D四点，见图3.5。算法基本思想是从A，B和P0三点中找出最靠近P1的点，图3.5中要找的点是P0，从C，D和P1三点中找出最靠近P0的点，图3.5中要找的点是C点。那么P0C就是P0P1上的可见部分。

y D y

P1 C P0y

B A xL xR x

图3.5 P0C是可见部分

14

LH计算机图形学作业：共九道题

具体计算时要把P0P1写成参数方程

?x?x0??x?t ??y?y0??y?t其中?x?xy?。y把窗口边界的四条边分成两类，一类称1?x0,?y?10为始边，另一类称为终边。

参数化形式写出裁剪条件:

XL?x1?u??x?XRYB?y1?u??y?YT可以统一表示为形式：upk?qk

p1???xp3???yq1?x1?XLq1?y1?YBp2??xp4??yq2?XR?x1q4?YT?y1

当pk?0且qk?0，则线段完全在边界外，qk?0，则该线段平行于裁剪边界并且在窗口内；

当pk?0的情况下：当pk?0,线段从裁剪边界延长线的外部延伸到内部；当pk?0,线段从裁剪边界延长线的内部延伸到外部。

对于每条直线，可以计算出参数u1和u2，它们定义了在裁剪矩形内的线段部分，u1的值由线段从外到内遇到的矩形边界所决定?p?0?。对这些边界计算rk?qk/pk。u1取0和各个rk值之中的最大值。u2的值由线段从内到外遇到的矩形边界所决定?p?0?。对这些边界计算rk?qk/pk。u2取1和各个rk值之中的最小值。如果u1?u2，则线段完全落在裁剪窗口之外，被舍弃。否则裁剪线段由参数u的两个值u1，u2计算出来。 3.3.2 算法程序（或伪程序）描述

具体程序见附录8。 3.3.3 算法流程图

（略） 3.4 快速算法

在实际绘图时，常出现大部分线段是可见的，或大部分线段为显然不可见。因而用最少的操作去判断被裁剪的线段是否属于这两种情况则可以提高裁剪的效率。此外，尽量减少比较和四则运算，也是提高效率的重要措施。这样会使程序长一点，但由于效率高，在软件包中值得采用。用这样的算法确定一根显然不可见线段平均只要做3.6次比较，确

15

LH计算机图形学作业：共九道题

定一根完全可见线段要用8次比较，而用Sutherland-Cohen算法做同样工作则分别要做11次和10次比较。快速算法在最快的情况下要和四条边求交点，这要用10次加减法、5次乘除法和13次比较。采用Sutherland-Cohen算法要做16次加减法、8次乘除法和35次比较。此外后者还要多次调用过程合作集合运算，这些都使它比快速算法效率低。

3.5 其余一些改进的直线裁剪算法

除过前面所讲到的4种基本直线裁剪算法外，还有一些其它的裁剪方法，由于过多，这里仅列举几种如下：

（1）具有最少算术运算量的二维线裁剪算法。见文献：王骏，梁友栋，彭群生，具有最少算术运算量的二维线裁剪，《计算机学报》，1991年第7期。

（2）一个有效的多边形窗口的线裁剪算法。见文献：刘勇奎等，一个有效的多边形窗口的线裁剪，《计算机学报》，1999年第11期。

（3）一种基于几何变换的高效的线裁剪新算法。见文献：汪乱，吴锐迅，蔡士杰。一种基于几何变换的高效的线裁剪新算法。《软件学报》，1998，9(10): 728一733。

（4）任意多边形窗口的线裁剪算法。见文献：孙岩，唐棣:任意多边形窗口的线裁剪，《2000年图形学会议专刊))。 3.6 各种直线裁剪算法的优缺点对比分析

Sutherland-Cohen直线裁剪算法要计算直线段与窗口边界的交点，这不可避免地要进行大量的乘除运算，必会降低程序的执行效率。而中点分割裁剪算法却只需用到加法和除2运算，而除2运算在计算机中可以简单地用右移一位来实现，从而提高算法的效率。所以特别适合硬件实现，同时也适合于并行计算。 3.7 直线裁剪算法的发展趋势

（略）

4 图形求交技术

4.1 求交点算法

求交点可以分两种情况：求线与线的交点以及求线与面的交点。

16

LH计算机图形学作业：共九道题

4.1.1 线与线的交点的求法

1、直线段与直线段的交点

假设二条直线的端点分别为P1则，P，2Q，1，Q2它们可以用向量形式表示为：

P?t?=A+Bt Q?s?=C+Ds (0?t?1)(0?s?1)

其中，A?P1，B?P2?P1，C?Q1，D?Q2?Q1。 构造方程

A+Bt=C+Ds (4.1.1)

对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s,t，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解（ti, si）是有效解时，可用二个线段方程之一计算交点坐标，例如P?ti?=A+Bti。

我们还可以根据向量的基本性质，直接计算s与t：对（4.1.1）两边构造点积得

?A+Bt）=（C X D）（?C+Ds）?C X D?（由于CXD同时垂直于C和D，等式右边为零。故有

t??(C?D)?A

(C?D)?B类似地有

s??(A?B)?C

(A?B)?D完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。

2、直线段与二次曲线的交点

不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。 假设曲线方程为 f?x?,y， =0直线段方程为 则在交点处有

?x, y?=?x1+tdx, y1+tdy?,

f?x1+tdx, y1+tdy?=0。

at2?bt?c?0

当曲线为二次曲线时，上述方程可写为

17

LH计算机图形学作业：共九道题

用二次方程求根公式即可解出t值。 3、圆锥曲线与圆锥曲线的交点

圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次NURBS曲线）。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。 4.2.2 线与面的交点的求法

1、直线段与平面的交点（如图4.1）

图4.1 线段与平面求交

考虑直线段与无界平面的求交问题。把平面上的点表示为

P?u,w?=A+uB+wC，直线段上的点表示为Q?t?=D+tE，二者的交点记为

R。假设线段不平行于平面，则它们交于R=P?u,w?=Q?t?，即

A+uB+wC=D+tE

C等式两边点乘（B X ），得

（B X C）（?A+uB+wC）（=B X C）（?D+tE）

C垂直于B，又垂直于C，故有 由于B X 既

（B X C）?A=（B X C）（?D+tE）

可解出

t?

(B?C)?A?(B?C)?D

(B?C)?E类似求得

18

LH计算机图形学作业：共九道题

u?(C?E)?D?(C?E)?A

(C?E)?B(B?E)?D?(B?E)?A

(B?E)?C??如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见4.2节。

2、圆锥曲线与平面的交点

圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。

3、圆锥曲线与二次曲面的交点

圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲

面的隐式方程，得到参数的四次方程，用求根公式求解。 4.2 求交线算法

求交线显然是指求面与面的交线，下面讨论几种常见的情况。 1、平面与平面的交线

在CAD中一般使用平面上有界区域。先考虑最简单的情形。两个平面区域分别由P?u,w定如果它们不共面而且不分 Q?s,t, u?, ?w, ?s, 义t 。0, 1?,?离，则必交于一直线段。这条直线必落在P?u,w?-Q?s,t?=0所定义的无限直线上。注意这是个含有四个未知数，三个方程式的方程组，只要分别与八条边界线方程：u=0, u=1, w=0, w=1, s=0, s=1, t=0, t=1联立，即可求出线段的两个端点的参数。在上述方程组中，只要找到两组解，就可以不再对剩余其它方程组求解。找到的两组解就是所求的交线段端点参数。

当两个一般的多边形（即既可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。我们可以把两个多边形分别记为A和B，用如下的算法求出它们的交线：

（1）把A的所有边与B求交，求出所有有效交点； （2）把B的所有边与A求交，求出所有有效交点； （3）把所有交点先按y，再按x的大小进行排序；

（4）把每对交点的中点与A和B进行包含性检测，若该中点即在A中又在B中，则该对交点定义了一条交线段。

2、平面与二次曲面的交线

求平面与二次曲面的交线有两种方法：代数法和几何法。

19

LH计算机图形学作业：共九道题

C(t)??PiBi,n(t)??Pn?iBi,n(t)??Pn?iBn?i,n(1?t)??PBii,n(1?t),**i=0i=0i=0i=0nnnnt?[0,1]

这个性质说明Bezier曲线在起点处有什么几何性质，在终点处也有相同的性质。

（3）凸包性 由于

?Bi=0ni,n(t?)且1,0?Bi,n(t)?1(0?t?1,i=0,1,?,n)，这一结果说明当

t?[0,1]变化时，对某个t值，P(t是)特征多边形各项定点Pi的加权平均，)t?[0,1]中权因子依次是Bi,n。在几何图形上，意味着Bezier曲线P(t在

各点是控制点Pi的凸线性组合，即曲线落在Pi构成的凸包之中，如图5.2所示。

图5.2 Bezier曲线凸包性

（4）几何不变性。

这是指某些几何特性不随坐标变换而变化的特性。Bezier曲线的位置与形状与其特征多边形顶点Pi(i=0,1,?,n)的位置有关，它不依赖坐标系的选择，即有：

?PBii,n(t)??PBii,n(i=0i=0nnu?a) （参变量u是t的置换） b?a（5）变差缩减性。

若Bezier曲线的特征多边形P0P1?Pn是一个平面图形，则平面内任意直线与P(t)的交点个数不多于该直线与其特征多边形的交点个数，这一性质叫变差缩减性质。此性质反映了Bezier曲线比其特征多边形的波动小，也就是说Bezier曲线比特征多边形的折线更光顺。

（6）仿射不变性

对于任意的仿射变换A：

?n?nA([P(t)])?A??PBii,n(t)???A[Pi]Bi,n(t)

?i=0?i=0即在仿射变换下，P(t)的形式不变。

30

LH计算机图形学作业：共九道题

5.1.2 Bezier曲面

基于Bezier曲线的讨论，我们可以方便地可以给出Bezier曲面的

定义和性质，Bezier曲线的一些算法也可以很容易扩展到Bezier曲面的情况。

1.定义

设Pij?i=0,1,?,m,j=0,1,?,n?为(n+1)?(m+1)个空间点列，则m?n次张量积形式的Bezier曲线为：

mnP(u,v)=??PijBi,m(u)Bj,n(v),i=1j=1u,v?[0,1]

ii其中Bi,m(u)=Cmu?(1m-iu)j,nj,B(v)jn=?Cvv)是(1Bernstein基函数，

依次用线段连接点列Pij?i=0,1,?,m,j=0,1,?,n?中相邻的两点所形成的空间网络，称之为特征网格。Bezier曲面的矩阵表示式是：

?P00?P?10?P(u,v)=?B(u),B(u),?,B(u)1,nm,n?0,n?????Pn0在一般实际应用中，m,n不大于4。 2．性质

P01P11?Pn1????P0m??B0,m(v)??B(v)?P1m???0,m? ????????Pnm??Bn,m(v)?除变差减小性质外，Bezier曲线的其它性质可推广到Bezier曲面： （1）Bezier曲面特征网格的四个角点正好是Bezier曲面的四个角点，即P(0,0)0 (1,1)=P=0P,P(1,m00)=P,P(00,n,1)=P。mP（2）Bezier曲面特征网格最外一圈顶点定义Bezier曲面的四条边界；Bezier曲面边界的跨界切矢只与定义该边界的顶点及相邻一排顶点有关，且

P00P10P01、P0nP1nP0n?1、PmnPm,n?1Pm?1,n和Pm0Pm?1,0Pm,1（图

5.3

打上斜线的三角形）；其跨界二阶导矢只与定义该边界的顶点及相邻两排顶点有关。

（3）几何不变性。 （4）对称性。 （5）凸包性。

31

LH计算机图形学作业：共九道题

图5.3 双三次Bezier曲面及边界信息

5.2 B样条曲线与曲面

以Bernstein基函数构造的Bezier曲线或曲面有许多优越性，但有两点不足：其一是Bezier曲线或曲面不能作局部修改；其二是Bezier曲线或曲面的拼接比较复杂。1972 年，Gordon、Riesenfeld等人提出了B样条方法，在保留Bezier方法全部优点的同时，克服了Bezier方法的弱点。

5.2.1 B样条的递推定义和性质

1．定义

与Bezier曲线得定义方法类似，B样条曲线方程定义为：

P(t)=?PiNi,k(t)

i=1n 其中，Pi(i=0,1,?,n)是控制多边形的顶点，Ni,k(t)(i=0?,1,称,为n)k阶(k?1次)B样条基函数，其中每一个称为B样条，它是一个称为节点矢

t?1t???nt+所量，即非递减的参数t序列T:0k决定的k阶分段多项式，

也即k阶（k?1次)多项式样条。

B样条有多种等价定义，在理论上较多地采用截尾幂函数的差商定义。我们只介绍作为标准算法的de Boor-Cox递推定义，又称为de Boor-Cox公式。约定0/0=0。

32

LH计算机图形学作业：共九道题

?1,Ni,1(t)=??0,Ni,k(t)?ti?x?ti?1,其它.

t?tit?tNi,k?1(t)?i+kNi?1,k?1(t)ti+k?1?titi+k?ti?1该递推公式表明：欲确定第i个k阶B样条Ni,k(t，)需要用到

ti,?t?i1,,i共t+k,?1个节点，称区间[ti,ti+k]为Ni,k(t)的支承区间。曲线方程

中，n+1个控制顶点Pi(i=0,1,?,n)，要用到n+1个k阶B样条Ni,k(t。)它们支撑区间的并集定义了这一组B样条基的节点矢量T?[t0,t1,?,tn+k]。

2．B样条曲线类型的划分

曲线按其首末端点是否重合，区分为闭曲线和开曲线。闭曲线又区分为周期和非周期两种情形，周期闭曲线与非周期闭曲线的区别是：前者在首末端点是C2连续的，而后者一般是C0连续的。非周期闭曲线可以认为是开曲线的特例，按开曲线处理。

B样条曲线按其节点矢量中节点的分布情况，可划分为四种类型。假定控制多边形的顶点为Pi(i=0?为,1,，,n)k阶（k?1次)，则节点矢量是 T?[t0,t1,?,tn+k]。 （1）均匀B样条曲线

节点矢量中节点为沿参数轴均匀或等距分布，所有节点区间长度这样的节点矢量定义了均匀的B样条?i?ti?1?ti?常数?0(i=0,1,?,n+k?1)，基。图5.4是均匀B样条曲线实例。

图5.4 三次均匀的B样条曲线

（2）准均匀的B样条曲线

与均匀B样条曲线的差别在于两端节点具有重复度k，这样的节点矢量定义了准均匀的B样条基。

均匀B样条曲线在曲线定义域内各节点区间上具有用局部参数表示的统一的表达式，使得计算与处理简单方便。但用它定义的均匀B样条曲线没有保留Bezier曲线端点的几何性质，即样条曲线的首末端点不再是控制多边形的首末端点。采用准均匀的B样条曲线就是为了解决这个问题，使曲线在端点的行为有较好的控制，如图5.5所示。

33

LH计算机图形学作业：共九道题

图5.5 准均匀三次B样条曲线

（3）分段Bezier曲线

节点矢量中两端节点具有重复度k，所有内节点重复度为k-1，这样的节点矢量定义了分段的Bernstein基。

B样条曲线用分段Bezier曲线表示后，各曲线段就具有了相对的独立性，移动曲线段内的一个控制顶点只影响该曲线段的形状，对其它曲线段的形状没有影响。并且Bezier曲线一整套简单有效的算法都可以原封不动地采用。其它三种类型的B样条曲线可通过插入节点的方法转换成分段Bezier曲线类型，缺点是增加了定义曲线的数据，控制顶点数及节点数都将增加。分段Bezier曲线实例如图5.6所示。

图5.6 三次分段Bezier曲线

（4）非均匀B样条曲线

在这种类型里，任意分布的节点矢量T?[t1,?,tn+k]，只要在数学上成立（节点序列非递减，两端节点重复度?k，内节点重复度?k?1）都可选取。这样的节点矢量定义了非均匀B样条基。 5.2.2 B样条曲线

1．局部性

由于B样条的局部性，k阶B样条曲线上的参数为t?[it,it]一点+1的

P(t)至多与k个控制顶点Pj(j=i?k+1,?,i)有关，与其它控制顶点无关；移

动该曲线的第i个控制顶点Pi至多影响到定义在区间(ti,ti+k)上那部分曲线的形状，对曲线的其余部分不发生影响。

2．连续性

P(t)在r重节点ti(k??i处整条曲线P(t)的连n)的连续阶不低于k?1?r。

续阶不低于k?1?rmax，其中rmax表示位于区间(tk?1,tn?1)内的节点的最大重

34

本文来源：https://www.bwwdw.com/article/wpg3.html