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