计算机图形学若干基本算法的实现研究

论文摘要

本文所研究的计算机图形学若干基本算法,包括:裁剪算法、多边形布尔运算、曲线边多边形分割算法、曲线边多边形面积算法、高维空间距离算法和主成分回归分析法(PCR),具体工作如下:平面多边形的各种分解表示方法在计算机几何造型领域中有着广泛的应用,根据基于三角形的多边形表示方法,通过研究构造的多种算法和它的一些应用,在原有工作的基础上,对算法进行了扩展,针对在构造有曲线边多边形分层表示时可能会出现不合理情形,对曲线边进行分割,提出了一些可以利用的分割算法,包括对圆锥曲线边求分割点和切点的算法,对三次Bezier曲线边求可能的自交点的算法,对三次Bezier曲线边求不同形式分割点和切点的算法。复杂几何形状面积的计算,属于计算几何方面的问题。在实际应用中,不但经常需要计算一般多边形的面积,而且有时还需要计算有曲线边多边形的面积。为简便和考虑实用需要,可以假定曲线边是圆锥曲线边或三次Bezier曲线边。本文对圆锥曲线边和三次Bezier曲线边两种曲线边多边形的面积算法分别进行讨论。由对象多个特征组成的特征向量,可以自然地看作是高维数据空间中的一点。许多实际问题涉及到高维数据点。在高维空间中点的超球范围查找问题是:已知一个高维数据点集,输入一个点和半径数值,询问所确定超球范围内包含有给出点集中哪些点。考查了用计算街区和棋盘距离的线性组合来代替计算欧氏距离的方法,这个方法由于减少了乘法计算而明显的可以提高效率。还有,本文结合贝叶斯网络提出一种新的回归树学习算法─BRT(Bayesian Regression Tree)。在BRT多元回归模型中,需要有变量选择的功能,利用主成分回归分析法(PCR),在通过正交旋转变换来消除原始数据中的相关性或冗余度的基础上,根据方差贡献率选择特征属性,实现高维属性空间向低维属性空间的映射。

论文目录

• 内容提要
• 第一章 引言
• 1.1 计算机图形学的发展和应用
• 1.2 计算几何的产生和发展
• 1.3 图形学基础算法的国内外研究状况
• 1.3.1 裁剪算法
• 1.3.2 多边形的布尔运算
• 1.3.3 复杂多边形面积计算
• 1.3.4 高维空间中点距离计算
• 1.3.5 贝叶斯网络中的回归分析方法
• 1.4 本文的主要工作
• 1.5 本文的组织
• 第二章 图形学中的几个基本算法
• 2.1 多边形的方向性、简单性和包含性
• 2.1.1 基本概念
• 2.1.2 简单性
• 2.1.3 多边形方向
• 2.1.4 包含测试
• 2.2 基于三角形的多边形分层表示及其应用
• 2.2.1 一般多边形的布尔表示
• 2.2.2 L-REP 的构造和实现
• 2.2.3 基于图形矩阵的算法
• 2.2.4 基于图形矩阵算法的改进
• 2.2.5 射线扫描算法
• 2.2.6 应用
• 2.2.7 小结
• 2.3 曲线边多边形的包含测试
• 2.3.1 基本概念
• 2.3.2 曲线片包含测试
• 2.3.3 圆锥曲线片的包含性
• 2.3.4 Bezier 曲线片的包含性
• 2.3.5 曲线边多边形的包含测试
• 2.3.6 小结
• 2.4 平面多边形的布尔表示
• 2.4.1 基本定义
• 2.4.2 多边形表示
• 2.4.3 小结
• 2.5 普通平面多边形的布尔运算
• 2.5.1 简单链
• 2.5.2 交集运算的形式与简化
• 2.5.3 多边形交集算法
• 2.5.4 并集算法
• 2.5.5 差集算法
• 2.5.6 有效性分析和结论
• 2.5.7 小结
• 第三章 可用于构造有曲线边多边形合理分层表示的分割算法.
• 3.1 引言
• 3.2 对圆锥曲线边的分割
• 3.3 三次BEZIER 曲线的自交点
• 3.4 对三次BEZIER 曲线边的分割
• 3.5 举例
• 3.6 小结
• 第四章 平面扩展简单多边形的面积计算
• 4.1 引言
• 4.2 扩展多边形的相关定义
• 4.3 圆锥曲线边弓形面积的算法
• 4.3.1 化简圆锥曲线方程
• 4.3.2 椭圆弓形面积的求法
• 4.3.3 双曲线弓形面积的求法
• 4.3.4 抛物线弓形面积的求法
• 4.3.5 Bezier 曲线边弓形面积的求法
• 4.4 多边形面积的求法
• 4.5 小结
• 第五章 高维空间中欧氏距离的计算
• 5.1 用计算街区和棋盘距离的线性组合代替计算欧氏距离
• 5.1.1 用计算α（L1 + L∞）代替计算L2
• 5.1.2 用计算αL1 +βL∞代替计算L2
• 5.2. 算法
• 5.3. 实验结果及讨论
• 第六章 贝叶斯回归分析方法
• 6.1 回归分析与相关分析
• 6.2 回归—时间序列模型
• 6.2.1 模型形式
• 6.2.2 鲍克斯—詹金斯（B-J）方法
• 6.3 贝叶斯回归分析方法
• 6.3.1 MCMC 算法
• 6.3.2 线性回归模型和贝叶斯回归方法
• 6.4 回归的正交旋转设计
• 6.5 贝叶斯回归树模型
• 6.5.1 贝叶斯回归树构造
• 6.5.2 实验及分析
• 6.6 本章小结
• 第七章 总结与展望
• 7.1 本文的主要贡献
• 7.2 进一步研究的方向
• 参考文献
• 攻读博士学位期间取得的科研成果及发表论文情况
• 摘要
• Abstract
• 致谢