3

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

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

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

4

4 回答 4

2

我有一个适用于二维情况的算法。这很棘手，但可以将其推广到 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

结果：

2D 演示结果

泛化到 3D

  • 你有三角形而不是边缘。
  • 初始化是围绕原点的四面体
  • 找到分裂面涉及投影一个三角形，并检查 pt 是否在该三角形的内部
  • 拆分涉及添加 3 个新面，而 2D 是 2 个新边
  • 需要注意面部的方向（在我的 2D 代码中，我很容易保证 A->B 是 CCW 方向）

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

于 2013-10-24T14:38:11.090 回答
0

我会考虑一个“度量”函数 f(x, y, z)，它返回 3D 空间中任意点的标量值。应该以考虑给定点 (x, y, z) 是在云的“内部”还是“外部”的方式构建此函数。例如，这可以是从 (x, y, z) 到云中每个点的平均向量的长度，也可以是 (x, y, z) 某个附近范围内的多个云点。功能的选择会影响最终的结果。

有了这个 f(x, y, z)，您就可以使用行进立方体算法来执行细分，基本上为某个值构造 f(x, y, z) 的等值面。

于 2013-10-24T14:38:24.783 回答
0

3D 凸包（3d 表面 z = f(x, y) 的凸包算法）。

然后对于每个最大面上的点，搜索云上最近的点，并重新对该面进行三角测量以包含该点。

重复直到它“足够接近”，基于与每个剩余面的最近云点的最大距离，或最大剩余面的大小（长度/面积？）

于 2013-10-24T16:33:53.483 回答
0

您应该尝试3d Delaunay Triangulation。这将镶嵌点云，同时确保三网格仅具有来自点云的顶点。CGAL 有两种对点云进行三角剖分的实现 - delaunay和regular。常规版本使用此处描述的想法对点进行三角测量。

如果你使用 C++，你可以使用他们的实现。如果没有，您仍然可以查看他们的代码来自己实现它（虽然它非常复杂）。

于 2013-10-24T20:49:17.757 回答