三角形网格上曲面重构研究

摘要

随着计算机应用技术和计算机图形学技术的不断发展，使用细节丰富的多边形网格来描述数字几何模型越来越普遍。和传统算法向比，利用多边形网格描述与处理数字模型的算法灵活多样，具有计算效率高，便于绘制等优点，使其在计算机辅助几何设计(CAGD)，计算机游戏、动画、电影、数字模拟，以及计算机科学可视化等领域得到广泛地应用。但是利用多边形模型简洁，高效地描述数字几何模型还面临一系列问题。首先，由于直接产生的多边形模型往往存在洞、自交、重叠、复边、法向不一致、非流体等问题，阻碍了该技术除绘制以外领域的广泛应用;其次，多边形模型往往含有过多细节，大量退化元素等问题，不仅影响占用的存储空间，而且影响算法稳定性、复杂性，以及计算精确度。与多边形模型相比，隐式曲面模型不存在前面提到的问题，所以如何利用隐式曲面来处理多边形模型越来越受到人们的广泛关注，成为数字几何处理研究的热点和重点问题之一。近年来，使用隐式曲面模型逼近或者插值多边形模型的研究取得了一系列重要成果，但依然存在大量需要解决的问题，例如，如何保证隐式曲面模型和被逼近的多边形模型之间的误差在给定的范围内;如何使构造的隐式曲面模型表示形式简洁，并且存储高效;如何在满足误差的前提下，快速地将多边形模型转变成满足要求的隐式曲面模型;以及如何快速绘制隐式曲面模型等。
　　基于前面提到的问题，本文在，1）高效鲁棒的多边形——隐式曲面构造方法;2）隐式曲面的快速采样方法;3）基于误差构造简化曲面模型，三方面做了针对性的研究工作，具体内容和成果如下:
　　1、高效鲁棒的多边形——隐式曲面构造方法
　　基于加权多边形——隐式曲面误差项，提出了一种鲁棒的多层次单位隐式曲面划分算法。新算法能够使构造的隐式曲面在满足误差的条件下，高效稳定地逼近原多边形网格。利用提出的能够正确区分多边形内部顶点和网格顶点的加权多边形——隐式曲面误差项，新算法构造的局部隐式曲面（一般隐式二次曲面）不仅具有局部多边形模型所建议的形状，而且多边形顶点和局部隐式曲面之间的误差更小。另外，将多边形网格模型的对偶模型和加权多边形——隐式曲面误差项应用到传统的多层次单位隐式曲面划分算法中，提出一个稳定，高效的隐式曲面重构算法。同传统的多层次单位隐式曲面划分算法向比，在同样的逼近误差下，新算法更稳定，并且产生的隐式曲面模型含有更少的核函数。
　　2、隐式曲面的快速采样方法
　　提出了一种新的隐式曲面快速采样方法。首先提出了一种新的采样点互斥能量目标函数，基于该目标函数，通过一种混合优化方法来求解采样点的分布。第1步为采样点的局部优化，通过对采样点移动速度的控制参数调整，避免了大量Hessian矩阵的求逆操作，使得采样点能够根据互斥半径快速覆盖整个隐式曲面，得到初始采样点集;第2步为采样点的全局优化，采用L-BFGS方法对所有采样点进行优化，得到最终的高质量采样结果。通过实验表明，新方法的采样速度大大提高，并能够获得较好的隐式曲面采样点分布。并且基于该方法的均匀分布或者依据曲率的自适应分布采样结果，能够生成简洁并且高质量的多边形模型。
　　3、基于误差构造简化曲面模型
　　提出了一种新的隐式曲面构造方法，构造的隐式曲面由每个三角形上构造的曲面片组成，且能够插值或者逼近原始的多边形网格。每个三角形上的曲面片由顶点处构造的隐式二次曲面加权产生，并且为了使构造的曲面模型含有的曲面片数尽可能少，我们把三角形网格简化算法引入到曲面重构过程中。算法输入一个三角形网格和一个拟合误差，依据顶点到构造的曲面模型之间的距离是不是满足给定的误差迭代地删除网格顶点，直至算法收敛。既然该算法是基于曲面重构和顶点删除的，那么我们可以精确地控制删除的顶点和构造的曲面模型之间的误差，并且大量的试验结果显示，该算法产生的曲面模型能够较好地逼近原始模型。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 研究现状

1．3 本文主要工作和创新点

1．4 各章节安排

第2章 相关基础

2．1 引言

2．2 曲面重构的相关算法

2．2．1 低次代数曲面拟合

2．2．2 Metaball曲面重构

2．3 粒子采样

2．3．1 W-H算法概述

2．3．2 鲁棒的采样系统

2．3．3 快速采样系统

2．3．4 粒子系统的应用

2．4 小结

第3章 三角形网格上鲁棒的多层次单位隐式曲面划分算法

3．1 引言

3．2 算法概述

3．2．1 MPU的计算方法

3．3 加权PIEM

3．4 基于对偶图的MPU

3．5 实验结果

3．5．1 同多边形隐式曲面误差项的比较

3．5．2 不同数据集上的MPU算法比较

3．5．3 和IAPS比较

3．6 小结

第4章 基于混合优化的快速隐式曲面采样方法

4．1 引言

4．2 基于粒子系统的隐式曲面采样方法

4．3 混合优化的隐式曲面采样方法

4．3．1 新能量函数

4．3．2 采样点局部快速调整

4．3．3 基于L-BFGS的采样点全局优化

4．4 实验结果比较

4．5 小结

第5章 使用较少曲面片的网格上曲面重构

5．1 引言

5．2 算法概述

5．3 加权曲面构造

5．3．1 顶点处曲面的构造

5．3．2 平滑区域的拟合

5．3．3 角点和sharp-feature处二次曲面的构造

5．3．4 顶点处隐式曲面参数化

5．3．5 三角形上的曲面构造

5．4 三角形简化

5．5 实验结果

5．5．1 保持特征的网格重构

5．5．2 和前期算法的比较

5．5．3 算法性能比较

5．6 小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

攻读学位期间发表的学术论文目录

攻读学位期间参与科研项目情况

外文论文