基于空间分割的多线程距离场生成算法

摘要

计算空间内任意一点到一个给定的任意多面体的最小有符号距离在许多工程领域都有应用。近年来，在计算机图形学、计算机仿真等相关领域，用距离场表示目标图形对象得到了广泛的应用。例如碰撞检测、估计提取、纹理映射、三维物体变形等。我们常说的距离场实际上是一个标量场，它表示三维空间内任意一点到一个给定的三维物体表面的最小距离值。在计算机图形学中，通常使用的是有符号的距离场，用符号表示该点的位置是在物体内部还是在物体外部。大多数情况下，距离场场值为正时表示该点位于三维物体外部；距离场场值为负时表示该点位于三维物体内部；距离场场值为零时表示该点位于三维物体表面。
　　本文描述了三种关于三维物体的有向距离场生成算法，分别为蛮力计算距离场生成算法，基于空间分割的单线程距离场生成算法以及基于空间分割多线程距离场生成算法。详细介绍了距离场生成过程中有关STL模型文件的导入与处理，空间分割的思想，距离场的存储以及距离场符号的判断。比较三种算法的计算结果，可以看出基于空间分割的多线程距离场生成算法相对于另两种算法不但节省了大量的存储空间，同时在距离场生成速度上有较大的提高，特别是对于复杂的模型。

目录

封面

中文摘要

英文摘要

目录

第一章 绪论

1.1 选题的意义及研究背景

1.2 国内外相关研究动态

1.3 本文主要研究内容

1.4 本文的组织结构

第二章 距离场生成的相关理论

2.1 欧式距离

2.2 常用的三维建模方法

第三章 距离场生成的相关计算

3.1三维物体的表示

3.2常用的计算点到三角形的最小距离的方法

3.3 空间内一点到三角形的最小距离算法实现

3.4 距离符号的计算

3.5 距离场的存储与表示

第四章 本文距离场生成算法的实现

4.1 STL模型文件简介及导入处理

4.2 距离场蛮力计算

4.3 空间分割思想

4.4 基于空间分割思想的距离场计算

4.5 距离场符号判断

4.6 基于空间分割的单线程和多线程距离场生成算法

4.7 算法实验效果图

4.8距离场的应用

第五章 总结与展望

参考文献

攻读学位期间的研究成果

致谢

声明