从网格中查找起点的最近点

我想做一些类似于raycast的事情。 使用光线投射,您可以设置原点和命运,并检查光线与某些物体碰撞的位置,但仅与一条线相交。 我想要做的是给出一个具有xyz坐标的原点,检查它在网格中碰撞的最近点。 所以如果我有一个0, 0, 0 ,宽度为2的框,并且我的原点是0, 0.5, 0algorithm/函数应该返回它碰撞的最近点是0,1,0。 我希望我很清楚。

我正在使用Ogre3D和子弹物理。 我也可以使用OpenGL。

谢谢。

你想用GJK 。 一般algorithmfind两个(凸)网格之间的最近点,但是当然你的“网格”中的一个可以是空间中的单个点。

请注意,因为它只适用于凸形状,所以需要将网格划分为凸块(如果它不是凸的),以便应用algorithm。 find每个块的最近点,然后保持最接近的结果。

该algorithm通过评估几何图元并通过find“下一个最接近的”邻接图元来优化所考虑的图元。 你从一个点开始在每个网格上,将其展开成一条线,然后展开成一个三角形,然后是一个四面体,“行走”相邻的四面体(或者更简单的形状),直到到达最靠近另一个形状的点/线/三角形。

形象化比散文的一两段更容易解释。 查看周慧敏的概述或Molly Rocketvideo教程 。 该技术相当容易从2D延伸到3D。

通过在网格表面(三角形,四边形 )的所有图元迭代并find最接近于P的图元,可以在网格上find最靠近点P的点。 如果你的网格是由三角形组成的, 这个问题有指向几种距离计算方法的指针,特别是“源自一个点到一个三角形(3D)的距离” 。 否则,你可以看看例如 盒子的距离 。

一旦你知道哪一个是最接近的基元,你可以find最近的点。 距离计算可能已经提供了信息(如果您使用了geometrictools.com的源代码)。 有时最接近的点是网格的一个顶点,有时候是在一个边缘,有时候它位于三角形的中间。

这将是algorithm:

 best_primitive = null best_dist = infinity for each primitive in mesh: new_dist = distance(P, primitive) if new_dist < best_dist: best_dist = new_dist best_primitive = primitive best_point = closest_point(P, best_primitive) 

这个方法是O(n)。