计算机图形学算法基础作业
姓名：学院：专业：时间：
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