opengl - 如何对点云的边界进行分割？

Question

我有一个顶点云。我想仅使用云中的顶点在顶点云周围镶嵌一个“壳”，以便壳大致符合顶点云的形状。

有没有简单的方法可以做到这一点？我想我可以对点云进行球形参数化，然后“行走”最外面的顶点来分割云，但我不确定这是否可行。

我认为添加顶点是可以接受的，但是“壳”的总体形状应该与顶点云的形状相匹配。

Answer 1

我有一个适用于 2D 情况的算法。虽然很棘手，但可以将其推广到 3D 空间。基本思想是从最小表面(2D 中的三角形或 3D 中的四面体)开始，并在遍历点数组时分割每条边(面)。

2D 算法(python。完整源代码/演示此处: http://pastebin.com/jmwUt3ES )

编辑:这个演示看起来很有趣:http://pastebin.com/K0WpMyA3

def surface(pts):
center = pt_center(pts)
tx = -center[0]
ty = -center[1]
pts = translate_pts(pts, (tx, ty))
# tricky part: initialization
# initialize edges such that you have a triangle with the origin inside of it
# in 3D, this will be a tetrahedron.
ptA, ptB, ptC = get_center_triangle(pts)
print ptA, ptB, ptC
# tracking edges we've already included (triangles in 3D)
edges = [(ptA, ptB), (ptB, ptC), (ptC, ptA)]
# loop over all other points
pts.remove(ptA)
pts.remove(ptB)
pts.remove(ptC)
for pt in pts:
    ptA = (0,0)
    ptB = (0,0)
    # find the edge that this point will be splitting
    for (ptA, ptB) in edges:
        if crossz(ptA, pt) > 0 and crossz(pt, ptB) > 0:
            break
    edges.remove((ptA, ptB))
    edges.append((ptA, pt))
    edges.append((pt, ptB))
# translate everything back
edges = [((ptA[0] - tx, ptA[1] - ty), (ptB[0] - tx, ptB[1] - ty)) for (ptA, ptB) in edges]
return edges

结果:

推广到 3D

• 不是边缘，而是三角形。
• 初始化是围绕原点的四面体
• 找到分割面需要投影一个三角形，并检查 pt 是否在该三角形的内部
• 分割涉及添加 3 个新面，而 2D 则涉及 2 个新边
• 需要小心面部方向(在我的二维代码中，我可以轻松保证 A->B 为 CCW 方向)

根据点云的大小和速度要求，您可能需要更聪明地了解数据结构，以便更快地添加/删除。