c++ - 如何判断三角形网格是否凹？

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

Answer 2

对于您描述的简单多边形，您可以检查每个顶点的每个内角，并检查该角度是否低于 180 度。如果是这样，它就不可能是凹的。如果单个顶点超过 180°，则它是凹的。

编辑：对于 3D 网格，同样的想法也适用，但是您必须在每个顶点处测试每个三角形彼此之间的角度是高于还是低于 180°