如何检查一个三维网格的凸性？

Question

有没有快速的方法来做这件事？在网上搜索显示函数或单个多边形的凸性。但我需要检查整个模型的凸性。一个物体可以有凸面，但整体上可能是凹的，比如一个环面。

- Joan Venge

---

仅检查相邻面之间的角度就足够了吗？如果存在两个相邻的多边形（可能是三角形），它们之间的角度大于pi（180），则网格是凹的。 - Ante

是的，我同意，但是如果您的网格没有严格的绕组规则，那么很难确定每个面的哪一侧。顺便说一下，thorus环内部有凹面...如果网格至少包含一对凹面，则它是凹的！！！为了速度，只需检查彼此相邻的法线即可。 - Spektre

仅供澄清：您是想确定由网格定义的表面是否为凸面，还是想确定由网格（作为边界）限定的点集是否为凸集？ - datenwolf

Answer 1

Kneejerk: 如果您构建了一个多叶BSP树，并且最终将所有几何图形都放在一个节点中，则该对象是凸的。

更明智的方法：对于每个多边形，请获取超平面。确保模型中的每个顶点都在该超平面后面。

等效地：检查每对顶点之间的线段；如果它不与任何面相交，则该对象是凸的。

我想您也可以通过quickhull或其他方式获得凸包，并将其与原始对象进行比较。或者，类似地，获取凸包并检查原始对象的每个顶点是否位于凸包的面上。

- Tommy

---

谢谢，但将对象与凸包进行比较是行不通的，因为拓扑结构会有所不同。 - Joan Venge

这取决于你的比较方式：如果你从拓扑学的角度来看，那么你可能会看到一个差异。如果你用其他方法来比较，那么你就不会看到差异。 - Tommy

你说得对。我假设体积比较不准确。不确定还有什么其他方法可以比较，但我需要一种快速的方法来完成这个任务，不幸的是内置的凸包生成器非常慢。 - Joan Venge

你提供了一些非常好的想法，但如果我必须选择，我会投第二个 :)。 - kolenda

Answer 2

bool IsConvex(std::vector<vec3> &points, std::vector<int> &triangles, float threshold = 0.001)
{
    for (unsigned long i = 0; i < triangles.size() / 3; i++)
    {
        vec3 Atmp = points[triangles[i * 3 + 0]];
        vec3 Btmp = points[triangles[i * 3 + 1]];
        vec3 Ctmp = points[triangles[i * 3 + 2]];

        btVector3 A(Atmp.x, Atmp.y, Atmp.z);
        btVector3 B(Btmp.x, Btmp.y, Btmp.z);
        btVector3 C(Ctmp.x, Ctmp.y, Ctmp.z);
        B -= A;
        C -= A;

        btVector3 BCNorm = B.cross(C).normalized();

        float checkPoint = btVector3(points[0].x - A.x(), points[0].y - A.y(), points[0].z - A.z()).dot(BCNorm);

        for (unsigned long j = 0; j < points.size(); j++)
        {
            float dist = btVector3(points[j].x - A.x(), points[j].y - A.y(), points[j].z - A.z()).dot(BCNorm);
        
            if((std::abs(checkPoint) > threshold) && (std::abs(dist) > threshold) && (checkPoint * dist < 0))
            {
                return false;
            }
        }
    }

    return true;
}

- Valerij

---

谢谢你的回答。如果您能添加算法工作原理的详细信息，那就太好了。仅有代码的答案是不被鼓励的，因为它们可能有效，也可能无效，但不清楚原因，并且更难发现其中的错误。 - allo

Answer 3

对于每个面，计算支持平面的方程，并检查当所有顶点代入平面方程时是否产生相同的符号。时间复杂度为 O(F.V)，其中 F 表示面数，V 表示顶点数。

*为了安全起见，忽略正在处理的面的顶点。

或者，计算三维凸包所需时间为O(V.Log(V))。如果在算法的任何阶段丢弃一个顶点，则多面体不是凸的。

- user1196549

Answer 4

trimesh 是一个能够加载3D网格并判断其是否为凸网格的Python库。

import trimesh
mesh = trimesh.load('my_mesh_file')
print(mesh.is_convex)

代码可以在这里找到。

以下是在命令行中运行该代码的说明：

python -m pip install trimesh
python -c "import trimesh; mesh = trimesh.load('my_mesh_file'); print(mesh.is_convex)"

- Guillaume Jacquenot

Answer 5

你可以先将所有顶点添加到树结构中，以加速平面-顶点测试，这样如果整个叶子的边界框与平面不相交，则可以拒绝整个叶子。

BSP 的想法实际上应该与测试所有三角形平面相同，因为对于凸对象，没有 BSP 叶子能够细分顶点集。

你可能需要为你的平面测试包含一个 epsilon，因为浮点精度和手动创建网格的建模精度都可能导致顶点略微高于平面。

- user1387