  Most of the existing point-to-mesh distance query solvers, such as Proximity
Query Package (PQP), Embree and Fast Closest Point Query (FCPW), are based on
bounding volume hierarchy (BVH). The hierarchical organizational structure
enables one to eliminate the vast majority of triangles that do not help find
the closest point. In this paper, we develop a totally different algorithmic
paradigm, named P2M, to speed up point-to-mesh distance queries. Our original
intention is to precompute a KD tree (KDT) of mesh vertices to approximately
encode the geometry of a mesh surface containing vertices, edges and faces.
However, it is very likely that the closest primitive to the query point is an
edge e (resp., a face f), but the KDT reports a mesh vertex \u{psion} instead.
We call \u{psion} an interceptor of e (resp., f). The main contribution of this
paper is to invent a simple yet effective interception inspection rule and an
efficient flooding interception inspection algorithm for quickly finding out
all the interception pairs. Once the KDT and the interception table are
precomputed, the query stage proceeds by first searching the KDT and then
looking up the interception table to retrieve the closest geometric primitive.
Statistics show that our query algorithm runs many times faster than the
state-of-the-art solvers.

Graphics