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

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

是否有捷径可寻？我想我可以对点云进行球形参数化，然后“走”最外面的顶点来分割云，但我不确定这会起作用。

我想添加顶点是可以接受的，但是“ shell ”的一般形状应该与顶点云的形状相匹配。

最佳答案

我有一个适用于 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

而不是边，你有三角形。

初始化是围绕原点

的四面体

寻找 split 面涉及投影一个三角形，并检查 pt 是否在该三角形的内部

split 涉及添加 3 个新面，而 2D 是 2 个新边

需要注意面部的方向(在我的 2D 代码中，我很容易保证 A->B 是逆时针方向)

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

关于opengl - 如何分割点云的边界？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19567091/