非流形表面转化算法的研究

论文摘要

实际建模过程中，我们经常会遇到非流形的多边形表面。首先，某些底层建模操作不可避免地会产生非流形表面；其次，由于非流形表面比流形表面具有更复杂的拓扑关系和更强的描述性，用户主观地需要产生一些非流形表面。相反，大量现有的图形学算法只能应用于流形表面，包括简化，压缩和细分算法。因此，为了使产生的非流形表面安全地应用这些算法，又能满足建模者视觉上的需求，我们提出了将产生的非流形表面转化为一个几何外观上与之相似的流形表面。描述网格的数据结构有很多，但最常用的一些基于边的数据结构并不能正确地描述某些非流形表面。因此，基于一种以面为基础的网格数据结构DLFL，提出了扩展的DLFL数据结构。它不仅继承了原结构所包含的丰富的拓扑信息，而且能描述所有的能显示出来的非流形表面。最后，基于该数据结构，我们提出了一种新的非流形点搜索算法，可达到线性时间复杂度。大量现有非流形边的修补算法可能会再产生新的非流形边，因此，我们提出了一种改进的切割-缝合操作。它不仅能在任何情况下进行有效的切割，而且可以避免缝合后会再产生新的非流形边。我们重新研究了非流形点的修补算法。针对现有研究仅能产生一种拓扑上分离的流形描述，利用InsertEdge操作将原非流形点在拓扑上转化为一个管道，从而可以得到一种拓扑上连通的流形描述。最后，基于经典的图形旋转系统理论，对该操作的封闭性进行了证明。通过Doo-Sabin算法对修改后的表面进行细分，证明表面已经转化为流形描述。

论文目录

• 摘要
• Abstract
• 第一章 前言
• 1.1 课题背景
• 1.2 技术背景
• 1.2.1 实体及正则集
• 1.2.2 二维流形
• 1.2.3 多边形表面
• 1.3 目前的研究现状
• 1.4 研究的课题内容和意义
• 1.5 论文组织结构
• 第二章 数据结构及搜索算法研究
• 2.1 边界表示的数据结构
• 2.2 DLFL 数据结构及其扩展
• 2.3 搜索算法的研究
• 2.4 实验结果
• 2.5 本章小结
• 第三章 非流形边修补算法的研究
• 3.1 现有的研究及缺陷
• 3.2 切割操作（Cutting）
• 3.3 缝合操作（Stitching）
• 3.3.1 沿着相同边界进行缝合（Same boundary）
• 3.3.2 沿着不同边界进行缝合（Different boundary）
• 3.4 实验结果
• 3.5 本章小结
• 第四章 非流形点修补算法的研究
• 4.1 现有的研究及缺陷
• 4.2 新的非流形点修补算法
• 4.3 InsertEdge 操作的封闭性证明及时间复杂度分析
• 4.3.1 图形旋转系统理论
• 4.3.2 InsertEdge 操作的封闭性证明及时间复杂度分析
• 4.4 复杂非流形点的分析
• 4.5 实验结果
• 4.6 本章小结
• 第五章 总结和展望
• 5.1 文章总结
• 5.2 进一步研究方向
• 参考文献
• 致谢
• 攻读硕士学位期间的研究成果