基于粒子采样的隐式曲面多边形化

摘要

曲面重构属于逆向工程技术，首先采集数据，对数据去除误差、噪声，修补空洞，然后根据获得的点云数据对曲面进行重构，而隐式曲面重构是曲面重构中的一种。由于隐式曲面容易判断点的内外、容易与直线求得交点，以及容易对其实现布尔操作等特性，成为计算机图形学研究的热点，但是同时也存在难以绘制的特点。
　　 隐式曲面的多边形化是指用多边形网格来逼近隐式曲面，从而达到绘制该隐式曲面的目的。基于粒子采样的隐式曲面多边形化，是指首先通过粒子系统获取曲面的稳定采样点，然后依据一定的算法将采样点连接成三角网格。采样点质量的好坏关系到三角网格的质量，三角网格连接的健壮性、光滑性影响到曲面表达的好坏。
　　 本文针对基于粒子采样的隐式曲面多边形化，存在误差不容易控制，参数难以调整等问题，提出了曲率约束下的隐式曲面的粒子采样，在粒子不和曲面交互的前提下进行。首先选取一个种子粒子，根据种子粒子的位置的不断更新来初始化固定数目的粒子。粒子之间具有相互的排斥力，由静电力函数定义，粒子依合力减小的方向运动，逐渐趋向平衡位置。提出了将移动后的粒子重新投影到曲面上的立方体的旋转投影法，依据二分迭代求根法来计算交点。粒子逐步迭代更新，直至达到平衡状态，这样就获得了初步的采样结果。然后，添加曲率对粒子作用力的影响，粒子在初步的平衡状态下再次更新位置直到获得最终的采样点集。随曲率指导的采样点相比均匀采样点可以更好的表达曲面，二分迭代求根法使得粒子反投影时的误差可以控制。采样方法只需调整立方体的边长、排斥半径的初值、判断是否达到均衡状态的阈值、误差精度四个参数，该方法也适用于三角网格模型。最后用实例说明了方法的有效性。
　　 本文还研究了基于采样点集的多边形化方法。首先获得采样点的Voronoi图，根据Voronoi顶点求取采样点的极点，将采样点集和极点合并，对此数据场进行Delaunay三角剖分，对剖分的四面体抽取crust图，即得到采样点集的三角网格。实验证明三角网格光顺性、健壮性良好，并不需要进一步的细分，有效的实现了对隐式曲面的表达。最后用实例展示了剖分形成的三角网格。

目录

声明

摘要

第一章 绪论

1．1 课题背景及研究意义

1．2 国内外研究现状

1．2．1 光线跟踪(Ray tracing)算法

1．2．2 Marching Cubes隐式曲面多边形化

1．2．3 基于粒子采样的隐式曲面多边形化

1．3 本文的主要内容和组织结构

第二章 隐式曲面和粒子系统

2．1 隐式曲面的属性

2．1．1 隐式曲面容易判断点的内外

2．1．2 隐式曲面求交点的容易

2．1．3 隐式曲面的布尔操作

2．1．4 隐式曲面的法向量、切平面、曲率

2．2 元球造型

2．3 三角面片数据

2．3．1 数据格式

2．3．2 数据的邻域与法向量

2．4 粒子系统

2．4．1 粒子系统的产生

2．4．2 粒子系统的基本理论

2．4．3 粒子系统的模型

2．4．4 粒子系统的分类

2．5 本章小结

第三章 曲率约束的隐式曲面粒子采样

3．1 Witkin方法

3．1．1 粒子和曲面之间的约束

3．1．2 目标函数的最优化

3．1．3 粒子

3．1．4 控制点

3．1．5 自适应采样

3．2 曲率约束的隐式曲面的粒子采样

3．2．1 排斥半径和静电力函数

3．2．2 粒子的法向反投影和旋转反投影方法

3．2．3 奇异点的处理

3．2．4 粒子采样步骤

3．2．5 曲率采样

3．2．6 三角网格的粒子采样

3．3 实验结果与分析

3．3．1 常见曲面的粒子采样

3．3．2 Blobby曲面

3．3．3 bunny模型

3．3．4 实验结果分析

3．4 本章小结

第四章 隐式曲面多边形化

4．1 隐式曲面多边形化的意义

4．2 BPA算法和壳空间剖分的三角化

4．2．1 BPA算法

4．2．2 壳空间剖分的三角化

4．3 Crust算法

4．3．1 Crust算法介绍

4．3．2 基于数据的crust算法流程

4．3．3 实验结果与分析

4．4 本章小结

第五章 总结与展望

5．1 全文总结

5．2 下一步的工作

参考文献

致谢

附录