Python中点云到网格的距离

Question

我有一个大的3D点云和一个由三角形元素组成的网格。我需要计算每个点到网格的最小距离，如本文所述（https://www.geometrictools.com/Documentation/DistancePoint3Triangle3.pdf）。然而，由于大量的点和元素，暴力方法是不可行的。据我所知，将元素和数据点存储在树结构（例如八叉树）中将大大加快计算速度。是否有一个Python库允许我非常高效地进行计算，即使是对于大量的点和元素 非常感谢

Answer 1

La Lune De Idees提供的答案是一个非常好的起点。多亏了这个答案，我才能够通过使用numpy和scipy将代码速度提高30倍

给定

vertice_points作为M x 3 numpy数组的网格

及

point_cloud一个点云作为nx 3 numpy数组，用于计算到的距离

我提出了以下完整的（我工作时）示例：

# make efficient search tree
tree = cKDTree(vertice_points)

# get indices of closest three points to use as vetice to calculate distance to
d, idx_of_point_in_mesh = tree.query(point_cloud, 3)

# anchor point to span a plane from
anchor_points = vertice_points[idx_of_point_in_mesh[:,0],:]

# use next two nearest points to span a plane with two vectors
# from anchor point
plane_points = vertice_points[idx_of_point_in_mesh[:,1:],:]
plane_vecs = np.array(plane_points)
plane_vecs[:,0,:] -= anchor_points
plane_vecs[:,1,:] -= anchor_points

# calculate normal vectors of the planes
normals = np.cross(plane_vecs[:,0,:], plane_vecs[:,1,:], axis=1)

# distance from each point to its anchor point for spanning a plane
PQ = anchor_points - point_cloud
# distance is dot product between normal and PQ vector
# since normals and PQ are arrays of vectors 
# use einsum to calc dot product along first dimension
dists = np.einsum('ij,ij->i', PQ, normals)

注意：上述代码假设网格中三个最近点跨越的垂直度也是到该点的最近垂直度，这是一个合理的假设，前提是网格相对平坦，且点靠近网格中心，且与网格延伸距离不远。这就是我的用例的情况

Answer 2

您可以使用scipy.spatial.cKDTree。 使用KD树，您可以在大约O（N*log（M）*k）的情况下解决问题，其中N是点云中的点数，M是网格中的顶点数，k是一个顶点的“相邻”三角形的平均数

1. 在网格顶点上构建KD树：

tr = cKDTree(Mesh_vertexs)

1. 构建哈希表vertex -> list of "adjoining" triangles
2. 学习找出点和三角形之间的距离（如果你不能） 那么该算法的伪码是非常简单的：

for point in point_cloud:
    d,idx_of_point_in_mesh = tree.query(point)
    for triangle in Mesh_Triangles_near_vertex[idx_of_point_in_mesh]:
        d = min(d, distance(triangle,point))
    min_distance[point] = d

为了估计性能，对于网格中的10^6个顶点，一个查询tree.query (point)在我的笔记本电脑上进行27.5 µs ± 235 ns。 对于10^6个点的云，时间将是27.5 µs * 10 ^ 6 = 27sec+计算每个点的距离（三角形，点）的成本