如何确定一个三角网格是凹面的还是非凹面的？

Question

给定一个三维三角网格，如何确定它是凸的还是凹的？是否有一种算法可以检查这个问题？如果有，定义一个容差范围以忽略小的凹陷将会很有用。

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

- danijar

---

这里有一个类似的问题。第二个评论应该会对你有所帮助。http://gamedev.stackexchange.com/questions/53142/decomposing-a-concave-mesh-into-a-set-of-convex-meshes - Devolus

可能是重复的问题：如何确定一个多边形是复杂/凸/非凸的？ - Peter Wood

嗯，对于这样的多边形，应该很容易确定其是否为凹多边形。检查每个角是否有大于180度的角度即可。如果大于180度，则为凹多边形；如果小于180度，则为凸多边形。然而，对于3D网格来说，这几乎是不可能的。 - SinisterMJ

@PeterWood 正如Anton Roth所指出的那样，我的问题与您提到的重复问题之间存在很大的区别。 - danijar

3D网格没有区别。只需确保每个面规范化向量指向网格的外部（使用逆时针点放置）。 - dfens

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

- sbabbi

---

说实话，我不确定这个。 - sbabbi

谢谢sbabbi，看起来很不错。是的，我的网格有内部和外部，否则它们根本不能是凸面体。但我还没有理解p * n + d = 0。难道一个平面不是由(x - p) * n = 0定义的吗？d是向量还是标量？你所说的p = triangle plane是指p是原点向量吗？顺便说一下，容差在你的算法中并不是必需的，因为允许非凹多边形网格包含共线顶点。但在我的情况下，拥有容差范围很好。 - danijar

@danijar。已经编辑了答案并进行了一些澄清。由于浮点数近似，当您测试构成平面本身的顶点时，无法确定h是否完全为零，因此需要非零公差。 - sbabbi

谢谢澄清，但是飞机不应该是 X * N - d = 0 吗？而不是加号？我理解浮点数精度的问题。 - danijar

@danijar 是的，我也修复了那个问题。 - sbabbi

Answer 2

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

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

- SinisterMJ

---

我看了你的编辑。假设我知道所有其他三角形的角度是高于还是低于180度，那么这如何导致凸多边形或凹多边形的分类？ - danijar

如果物体内部的角度小于180度，则它是凸形的。 - SinisterMJ