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

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

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

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