流形三角网格的表面重采样及其应用

论文摘要

随着三维数据获取技术的提高,三维模型已经在诸如电影娱乐、科学可视化和制造业等许多领域得到广泛应用。在计算机图形学和几何建模等领域,越来越多的模型都使用三角网格表示,三角网格的质量对算法的效率和稳定性都有很大影响。通过三维扫描仪获取的点云数据或通过其他几何算法（如布尔运算）获得的模型尽管包含了物体的细节,但其模型表达方式不能达到最优。因此如何对原始模型进行表面重采样和优化使其满足不同应用的需求有着重要的研究意义。本文以现有的二维采样算法为基础,从两方面深入研究了流形三角网格表面的各向同性（Isotropic）采样算法:一是基于全局参数化,将现有二维采样应用到三维网格采样中,但是本文算法将改善现有算法中的一些局限性,这类算法效率较高,对复杂度较低的模型比较适用;二是为了解决复杂模型的表面采样问题,本文将二维Poisson-Disk采样算法扩展到三维网格表面上,从而在表面上直接采样得到具有各向同性的采样点集,然后在所得采样点集上应用松弛法可以进一步优化采样点的分布。本文不仅将这个采样算法应用到了高质量的重新网格化中,还探索了各向同性采样点集的其他应用。本文的主要创新点可以归结如下:（一）在二维重要性采样算法的基础上提出了一个基于全局参数化的网格表面顶点采样及重新网格化算法。算法在几何扭曲度的引导下搜索一条切线将模型表面切分成一片与圆盘同胚的表面,然后将其全局参数化到二维单位圆中。与其他全局参数化方法相比,该方法不但有效改善了参数化的扭曲度,而且减少了模型在被切分成多个子面片时带来的缝合困难。算法中所采用的二维重要性采样算法可以在实数空间进行任意精度的采样。对采样点进行平面三角化及连通度优化后再映射回三维空间可以实现网格表面的重采样与重新网格化,得到具有自适应性的高度规则网格。（二）提出了一个直接在流形网格表面进行的Poisson-Disk均匀采样算法。本文以测地距离为流形网格表面的距离测度,将二维快速均匀Poisson-Disk采样算法扩展到流形网格表面,实现了三维表面的均匀Poisson-Disk采样。在此过程中,本文基于快速MMP算法实现了一个自动提取测地等值线的算法,使得采样点在三维表面上的排斥区边界和可用边界可以通过二次曲线精确而连续地表示。实验表明,本文提出的均匀Poisson-Disk采样算法能在高亏格的复杂流形网格表面生成具有各向同性的均匀采样点分布。另外,本文通过分析得出了算法在均匀采样情况下采样点密度与Poisson-Disk半径间的关系。（三）在均匀采样算法的基础上,给出了在任意自定义采样密度下的Poisson-Disk自适应采样算法。为了实现流形网格表面的自适应采样,本文根据网格顶点的采样密度给出网格表面任意一点排斥区半径的定义。在此定义下,本文发现了在流形网格表面进行自适应采样时的可用边界的表达式。这个表达式表明,自适应采样时的可用边界由一系列二次曲线弧段组成。根据这个表达式,本文设计了对应的等值线提取算法,从而实现了在任意自定义采样密度下的Poisson-Disk自适应采样。（四）将本文提出的三维网格表面重采样算法应用于高质量的网格优化,并给出了一个完整的重新网格化算法框架。该算法框架以表面重采样点为初始分布,在构造采样点之间的连通关系之后采用Lloyd松弛对采样点的分布进行进一步的优化。由于初始采样点已具有各向同性,只需通过较少次松弛可使所得的顶点分布满足精确的各向同性,不仅克服了松弛法费时的缺陷且提高了新网格的质量。对重新网格化后网格角度的分析表明,以本文所提出采样算法为基础的重新网格化算法与前人算法相比,在三角形形状方面能获得更好的质量,并且能很好地保持原始网格的特征。（五）提出了一个光滑渐进的多层次网格表面重采样算法。在固定原有层次的采样点的情况下,通过逐步提高采样点的密度或者减小采样时排斥区半径的大小,可以继续往模型表面插入新的采样点,该算法不仅能保证所得到的细化后的采样点依然具有各向同性分布,而且能保证较粗层次的顶点全部出现在细化后的层次中,从而实现光滑渐进的多层次采样点集。最后,本文给出了各向同性的采样点在物体分布和纹理映射方面的应用。由于本文所提出的重采样算法能保证每个采样点都具有一个“排斥区”,这不仅能使得物体在三维表面上呈均匀分布还能保证物体之间不发生重叠。模型表面上的各向同性采样点还为三维表面的纹理映射提供了一个基函数,本文利用这个性质实现了三维模型表面的基纹理的均匀分布,并取得了理想的实验结果。

论文目录

• 摘要
• abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 三维模型的获取与表示
• 1.2.1 三维模型数据的获取
• 1.2.2 三维模型的表示方式
• 1.3 数字几何处理研究内容
• 1.4 问题的提出
• 1.5 本文研究内容及成果
• 1.6 论文组织结构
• 第二章 研究综述
• 2.1 采样算法研究综述
• 2.1.1 二维平面采样算法
• 2.1.2 三维表面采样算法研究现状
• 2.1.2.1 基于Voronoi/Delaunay几何的贪心法表面重采样
• 2.1.2.2 基于松弛算法的表面重采样
• 2.1.2.3 三维表面采样算法小结
• 2.2 三角网格表面的参数化研究综述
• 2.2.1 非封闭表面的平面参数化
• 2.2.1.1 基于凸组合的重心坐标法
• 2.2.1.2 基于能量最优化的离散保角映射
• 2.2.2 闭合三角网格的参数化
• 2.3 重新网格化研究综述
• 2.3.1 结构规则化的重新网格化
• 2.3.2 高质量的重新网格化
• 2.3.2.1 基于二维参数化的高质量重新网格化
• 2.3.2.2 基于表面重采样的高质量重新网格化
• 2.4 离散网格表面测地线的计算方法概述
• 2.5 本章小结
• 第三章 基于二维全局参数化的表面采样与重新网格化
• 3.1 算法概述
• 3.2 任意亏格闭合三角网格的切割与全局参数化
• 3.2.1 扭曲度量
• 3.2.2 网格切割与圆形域参数化
• 3.2.2.1 寻找初始切割线
• 3.2.2.2 模型切割线的边界参数化
• 3.3 具有蓝噪声性质的多层次重要性采样
• 3.4 自适应的重新网格化和优化算法
• 3.4.1 控制图的定义
• 3.4.2 重新网格化与优化
• 3.5 实验结果
• 3.6 本章小结
• 第四章 流形三角网格表面的Poisson-Disk均匀采样
• 4.1 流形三角网格表面采样算法
• 4.1.1 二维快速Poisson-Disk采样算法
• 4.1.2 流形三角网格表面Poisson-Disk均匀采样算法概述
• 4.2 流形三角网格表面精确等值线的提取
• 4.2.1 相关工作
• 4.2.2 流形三角网格上的测地线计算
• 4.2.2.1 测地线的基础知识
• 4.2.2.2 快速测地线计算算法
• 4.2.3 精确等值线的提取
• 4.2.3.1 窗口推广的结束条件
• 4.2.3.2 圆形等值线的提取
• 4.2.4 实验结果
• 4.3 可用边界的更新
• 4.3.1 可用边界合并算法
• 4.3.2 具有自然边界的局部参数化方法
• 4.4 采样流程
• 4.4.1 采样密度控制
• 4.4.2 采样点的随机生成及结束条件
• 4.5 实验结果与分析
• 4.5.1 采样点的各向同性分析
• 4.5.2 ρ值的确定
• 4.5.3 网格表面均匀重采样
• 4.5.4 算法稳定性与效率讨论
• 4.6 本章小结
• 第五章 流形三角网格表面的Poisson-Disk自适应采样
• 5.1 流形三角网格表面的自适应采样
• 5.2 自适应Poisson-Disk采样的可用边界
• 5.2.1 可用边界的表达式
• 5.2.2 可用边界的参数表示形式
• 5.3 流形三角网格表面上的可用边界提取
• 5.4 自适应Poisson-Disk采样的可用边界的更新
• 5.5 实验结果与分析
• 5.5.1 自适应采样中的采样密度调整
• 5.5.1.1 网格表面的采样密度定义
• 5.5.1.2 顶点排斥半径的定义和调整
• 5.5.2 实验结果
• 5.6 本章小结
• 第六章 基于流形网格表面重采样的高质量重新网格化
• 6.1 采样点连接关系的恢复
• 6.1.1 采样点的插入
• 6.1.2 网格原始顶点的移除
• 6.1.3 1-邻域网格参数化
• 6.2 采样点分布的优化
• 6.2.1 CVT的基本概念和属性
• 6.2.2 基于CVT的网格优化
• 6.3 网格顶点连通度优化
• 6.4 网格采样和优化过程中的特征保持
• 6.4.1 曲面特征分类
• 6.4.2 网格表面的特征检测算法
• 6.4.3 特征采样与特征保持
• 6.5 实验结果与分析
• 6.5.1 实验结果
• 6.5.2 实际应用
• 6.5.3 实验数据统计
• 6.5.4 与其他方法比较
• 6.6 本章小结
• 第七章 网格表面重采样的其他应用
• 7.1 光滑渐进的多细节层次的网格表示
• 7.2 模型表面的物体分布与模型近似
• 7.3 模型表面的纹理映射
• 7.4 本章小结
• 第八章 结论与展望
• 8.1 本文工作总结
• 8.2 未来工作展望
• 参考文献
• 附录A 二次曲线的参数表示形式
• A.1 椭圆方程的参数表示形式
• A.2 双曲线的参数表示形式
• A.3 抛物线的参数表示形式
• 个人简历、在学期间的研究成果
• 致谢