关键词: 点到网格距离查询, 近似算法, 动态规划, Delaunay 三角化, 广义Voronoi图

Abstract: Nearest distance query from a point to a mesh surface is a fundamental operation in computer graphics,with broad applications in collision detection,physical simulation,and surface registration.However,traditional acceleration structures based on spatial partitioning(e.g.,KD-tree,octree) or bounding volume hierarchies(BVH) often suffer from performance degradation due to their inability to effectively prune redundant branches,particularly when query points are distant from the model surface.Recently,the dynamic programming-based nearest neighbor search algorithm(DP-NNS),built upon incremental Delaunay construction,has demonstrated remarkable advantages in point cloud nearest neighbor queries.Nevertheless,its query table construction relies on Voronoi cell adjacency relationships between points,and the generalized Voronoi diagram of triangle meshes is computationally intractable in practice,preventing DP-NNS from being directly extended to point-to-mesh distance queries.To address this issue,this paper proposes an approximate point-to-mesh distance query algorithm built upon the DP-NNS framework.A triangle mesh consists of three types of geometric primitives:vertices,edges,and faces.Corresponding proxy points are assigned to approximate its generalized Voronoi cells.Vertices are directly inserted as proxy points,while edges and faces are adaptively sampled based on a unified density parameter.The adjacency relationships among all three primitive types are thereby unified into Delaunay adjacency relationships between proxy points,extending the DP-NNS framework to the geometric primitive level and enabling the construction of a primitive-level query table.During querying,tailored distance computation strategies are applied to each primitive type,with bounding sphere-based pruning employed for faces to avoid unnecessary exact distance computations.Experiments on multiple standard datasets demonstrate that the proposed method achieves a query speedup of 2 to 10 times over FCPW,Embree and Libigl,with particularly pronounced advantages when query points are distant from the model surface,while maintaining competitive approximation accuracy.

Key words: Point-to-mesh distance query, Approximation algorithm, Dynamic programming, Delaunay triangulation, Generalized Voronoi diagram