如何确定三角形网格是否凹陷？

Question

给定一个三维三角形网格,我怎样才能知道它是凸面还是凹面？有算法检查吗？如果是这样,定义公差范围以忽略小凹陷将是有用的.

^{图片来源:http://www.rustycode.com/tutorials/convex.html}

Answer 1

凸多面体可以被定义为有限数量的半空间的交集。这些半空间实际上是定义面的半空间。

编辑：假设您的网格实际上定义了一个多面体（即有一个“内部”和一个“外部”）

你可以做这样的事情（伪代码）：

for each triangle
    p = triangle plane
    n = normal of p (pointing outside)
    d = distance from the origin of p
    //Note: '*' is the dot product.
    //so that X*N + d = 0 is the plane equation
    //if you write a plane equation like (X-P)*n = 0 (where P is any point which lays in the plane), then d = -P*n (it's a scalar).

    for each vertex v in the mesh
         h = v*N + d
         if (h > Tolerance) return NOT CONVEX
         //Notice that when v is a vertex of the triangle from which n and d come from,
         //h is always zero, so the tolerance is required (or you can avoid testing those vertices)
    end
end
return CONVEX