目录
1 成果展示 4
2 整体架构 5
3 测试情况 7
3.1 安全性与可靠性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 易用性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 可维护性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 算法介绍 7
4.1 本部分均是结合自己对算法的理解完成的 . . . . . . . . . . . . . . . . 7
4.2 DDA算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2.1 简明的理解 . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2.2 更细致的角度 . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.3 Bresenham算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.3.1 快速理解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
∗
谢谢老师和助教哥的审查.
4.3.2 从更细致的出发 . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4 中点画线算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.5 Cohen Sutherland线段裁剪算法 . . . . . . . . . . . . . . . . . . . . . 15
4.5.1 主要思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.6 Liang-Barsky裁剪算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.6.1 算法思想: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.6.2 值得思考的问题: . . . . . . . . . . . . . . . . . . . . . . . . 17
4.6.3 更细致的来 . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.7 旋转与缩放 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.8 曲线生成: B
´
ezier曲线 . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.9 de Casteljau算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.10 B样条曲线 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.10.1 B样条基函数的性质 . . . . . . . . . . . . . . . . . . . . . . 24
4.10.2 B样条曲线函数的性质 . . . . . . . . . . . . . . . . . . . . . 24
4.10.3 B样条曲线类型划分 . . . . . . . . . . . . . . . . . . . . . . 24
4.11 圆绘制: 中点Bresenham 圆生成算法 . . . . . . . . . . . . . . . . . . . 25
4.12 圆绘制: 八分法圆生成算法 . . . . . . . . . . . . . . . . . . . . . . . . 26
4.13 椭圆绘制: 中点Bresenham 椭圆生成算法 . . . . . . . . . . . . . . . . 26
4.14 填充图元生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.14.1 扫描填充图元生成 . . . . . . . . . . . . . . . . . . . . . . . 28
4.14.2 X-扫描线算法 . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.14.3 改进的扫描线多边形填充算法 . . . . . . . . . . . . . . . . 31
4.14.4 区域填充图元生成 . . . . . . . . . . . . . . . . . . . . . . . 32
4.15 变换部分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.15.1 平移 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.15.2 旋转 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.15.3 二维观察变换 . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.15.4 三维观察概念 . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.16 图形学基本概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 加分项 36
5.1 线段反走样实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1.1 附加: 线画图元的反走样概念 . . . . . . . . . . . . . . . . . 38
5.2 优化Bezier曲线生成算法的计算与性能测试 . . . . . . . . . . . . . . . 39
5.2.1 数学上优化Bezier曲线生成算法 . . . . . . . . . . . . . . . 39
5.2.2 性能测试 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3 函数插值(数值分析)学习 . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3.1 函数插值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3.2 三次Hermite插值 . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3.3 三次样条插值 . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.4 光线追踪学习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.5 Sutherland-Hodgeman多边形裁剪 . . . . . . . . . . . . . . . . . . . . 42
5.6 Weiler-Atherton多边形裁剪算法深入学习 . . . . . . . . . . . . . . . . 44
5.6.1 算法思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.6.2 具体算法过程 . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.6.3 对比: 裁剪的Sutherland-Hodgman算法 . . . . . . . . . . . 46
6 附录 47
6.1 11月进度报告概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.1.1 11月实现了啥 . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.1.2 代码方面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.1.3 报告方面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.1.4 12月计划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.2 10月进度报告概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.2.1 10月进度报告实现细节 . . . . . . . . . . . . . . . . . . . . 48
6.2.2 10月进度展示 . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.2.3 10月进度遇到的困难和挑战 . . . . . . . . . . . . . . . . . . 50
6.2.4 11月计划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.3 个人总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7 参考文献 51
1. 成果展示
图形学 绘制系统CG_Canvas_171840708是南京大学计算机图形学的课程实验与大
作业, 它集成了各种图形的绘制: 线(DDA和Bresenham), 圆和椭圆(中点生成), 多边形, 矩
形, 三角形, 五角星, Bezier和B样条曲线, 还提供各种操作例如裁剪, 取色, 填充, 缩放等,
另有3D效果展示. 整个系统不仅对开发人员我深入 学习图形学起到了很好的帮助, 还给使
用者带来了很形象的图形展示体验, 可以应用到生活的各个方面.
图 1. 运行界面展示
(谢谢助教哥!!!)
详细使用过程以及动动动图图图展示请看 系统使用说明书
2. 整体架构
项目使用MainWindow(继承自QMainWindow类)作为控制面板主体, 内嵌提供给用
户画布的任意多个重写的QGLWidget, 所有图形设置了一个管理类CanvasAdmin, CanvasAdmin将
对接所有基本图元的绘制以及操纵, 为了更好地进行代码复用, 在CanvasAdmin调用图元
操纵函数需要经过一个基类接口, 通过这个基类接口可以动态绑定各种图元上的操作. 具
体类间关系如下:
