P2M: A Fast Solver for Querying Distance from Point to Mesh Surface

P2M: A Fast Solver for Querying Distance from Point to Mesh Surface算法总流程筛选拦截凸多面体R-tree实现图解方法评价性能优缺点

读论文。

论文内容：使用KDT，构建拦截表放入R-tree的筛选方法进行预处理，加速查询过程。

算法总流程

预处理部分：

$V$ 的KD-Tree与Voronoi图。
$E,F$ 计算拦截器，填到拦截表中，并计算外边框。
$V$ ，将能够拦截器的元素（的外边框）插入R-tree中。

$O(N_VM_{E+F})$ $N_V$ $M_{E+F}$ 为边与面的数量。

查询部分：

$p$ $v$ 。
$v$ 能够拦截的元素，更新距离最小值。

常数很小。

筛选

通过KDT来找到最近的顶点后，需要找到最近的网格面，我们可以通过预处理一些筛选加快这个过程。

拦截

$q$ ：

$v_1$ $e_1,e_2,e_3$ 。
$v_2$ $e_1,e_3$ 。

差别在于边Voronoi图的顶点完全在点Voronoi边的一侧。于是可以看成对边的一个筛选？

$v$ $e$ $\text{Cell}(v;\mathcal V_V)\cap \text{Cell}(e;\mathcal V_E)\neq \emptyset$ $v$ $e$ 的拦截器，然后可以列出上面的拦截表。

以上是二维情况，推广到三维情况，有：

$\text{Cell}(v;\mathcal V_V) \cap \text{Space}^\bot(e) \sub \text{Bisect}^v(v,l_e)$ $v$ $e$ 。

$\text{Space}^\bot(s)$ $s$ $\text{Bisect}$ $l_e$ $e$ 所在直线。

凸多面体

三维空间中还有面元的存在，直接使用上面的定义会比较难以表示。

$\text{Cell}(v;\mathcal V_V) \cap \text{Space}^\bot(f)$ $\text{Bisect}^v(v,\pi_f)$ 是凸的抛物面，如果判断在内部，可以直接判断顶点就可以了。

$\text{ConvexPoly}(v,e)=\text{Cell}(v;\mathcal V_V)\cap \text{Space}^\bot(e)$ $k$ $\{x_i\}_{i=1}^k$ $\text{ConvexPoly}(v,e) \sub \text{Bisect}^v(v,l_e)$ $x_i\in \text{Bisect}^v(v,l_e)$ $||x_i-v||\leq \text{Dist}(x_i,l_e)$ $\text{Dist}(x,l)$ $x$ $l$ 的距离。

这样定义就很好实现，也方便推广到面的情况：

$\text{ConvexPoly}(v,f)=\text{Cell}(v;\mathcal V_V)\cap \text{Space}^\bot(f)$ $k$ $\{x_i\}_{i=1}^k$ $||x_i-v||\leq \text{Dist}(x_i,\pi_f)$ $v$ $f$ $\text{Dist}(x,\pi)$ $x$ $\pi$ 的距离。

R-tree

通过上面方法可以计算出拦截表，但是直接对拦截表进行遍历太低效了。

$v$ $e$ $f$ $\text{ConvexPoly}(v,e) \cap \text{Bisect}^e(v,l_e) \neq \emptyset$ $\text{Bisect}$ $\text{Region}(v,e)$ $\text{Region}$ ，然后对于一个点建立R-tree。

实现

使用泛洪算法：

图解

个人感觉这篇论文的图很帅。

Fig.3

$\mathcal V_V$ 。
$\mathcal{V}_{V,E,F}$ ，对应关系：黄色-顶点、蓝色-边、红色-面。

Fig.4

$\text{Cell}$ $\text{Cell}$ $\text{Cell}$ 的形状取决于相邻的平面。

Fig.5

$\text{Bisect}^v(v,l_e),\text{Bisect}^e(v,l_e);\text{Bisect}^v(v,\pi_f),\text{Bisect}^f(v,\pi_f)$ 。

Fig.6

$e$ $l_e$ $e$ $\text{Space}^\bot(e)$ $\text{Cell}(v;\mathcal V_V)$ $\text{Cell}(v;\mathcal V_V) \cap \text{Space}^\bot(e)$ $\text{Bisect}^v(v,l_e)$ $\text{Bisect}$ 。