摘要
针对现有基于体素结构的点到三角网距离算法中存在的可能因未找到最近三角形所在体素而导致计算结果错误,以及较远点距离计算速度慢的问题,对其进行改进,提出准确快捷的基于体素结构的距离算法.首先将每个三角形进行点采样并求出采样点所在体素,得到三角网的体素化结果;对于每个待计算点,通过邻接体素与点距离变化规律寻找三角网包围盒内与该点距离小于某半径值的所有体素,逐渐扩大该半径值直至找到非空体素为止;以找到的体素中最近三角形到该点的距离作为初始距离,再令该半径值等于初始距离与一个适当微小量之和,即可找到与该点最近的三角形,得到准确的距离.实例测试结果表明,文中算法在一般情况下运算速度较快,与现有算法相比,较远点到三角网距离的计算时间明显缩短.
To solve the problems of the existing point-to-triangle-mesh distance computation algorithm which runs slow or gets a wrong answer in some cases,an improved algorithm based on voxel structure was proposed.This algorithm first computes the voxelized mesh by sampling all triangles and computing the voxels of sample points of each triangle; Then the algorithm searches all voxels which are away from the given point less than a given value within the bounding box of the mesh by considering the distance variation of adjoin voxels,expands the given value gradually until at least one non-empty voxel is found,gets the original distance by computing the distance between the given point and the nearest triangle within the triangles which are found,and expands the given value to the original distance adding an appropriate small number.The nearest triangle will be found and the accurate distance will be calculated.Experimental results show that this algorithm has a good performance.The time consumption of distance computation between a triangle mesh and a distant point can be reduced compared with the existing algorithm.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2014年第3期348-355,共8页
Journal of Computer-Aided Design & Computer Graphics
关键词
三角网
距离算法
体素结构
体素化
triangle mesh
distance computation algorithm
voxel structure
voxelization