计算机图形学课程设计_毕业论文（设计）.doc

计算机图形学算法基础作业 姓名： LH 学院： 理学院 专业： 计算数学 时间： 2010-12-31 目录 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 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 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 5.4.1 基本概念 40 5.4.2 双线性Coons曲面 41 5.4.3 双三次Coons曲面 42 6 CAGD中有关曲线曲面、拼接技术 44 6.1 基本原理 44 6.2 Bezier曲线的的拼接条件 44 6.3 Bezier曲面的的拼接条件 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 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 图形学算法基础作业