C++ Vector 比计算几何中的 Vector 修改了两次

Question

我正在尝试解决以下问题。我有 2 个类似球体的多面体，如下图所示，我试图找到每个模型的三角形，这些三角形要么在另一个模型内，要么与它相交。为了实现这一点，我开发了一种几何算法，我从模型的每个顶点开始一条射线，并检查它与另一个模型相交的次数。如果数字是奇数，则顶点在另一个模型内部，如果数字是偶数，则在外部。

当我试图区分完全在另一个模型内部的三角形和相交的三角形时，出现了问题。为此，我使用以下逻辑：

对于另一个模型内部的每个顶点，我检查同一模型的所有三角形并尝试找到该顶点所属的三角形。
当我找到这样的三角形时，我将计数器向量中的相同索引加1。
最后我想检查每个三角形与另一个模型的顶点数。有3就是内三角，有1-2就是相交三角，有0就是外三角

问题是以下代码似乎模拟了该过程，使计数器值达到 6。这不应该发生，因为每个三角形只能有 3 个顶点。

图像格式为 ti 的 counter[ti] 值。

如果有人能为我指出问题所在，我将不胜感激！另外，欢迎任何改进我的代码的想法。提前谢谢你。

    //create a vector to keep how many vertices are inside the other model for each triangle
    std::vector<int> counter(triangles.size());
    for (unsigned i = 0; i < counter.size(); i++){
        counter[i] = 0;
    }

    //check for every vertex of the model whether it is inside the other model
    for (unsigned vi = 0; vi < vertices.size(); vi++)
    {   

        Vec3d &ver = vertices[vi];
        vec myVec(ver.x, ver.y, ver.z);
        Ray myRay(myVec, myVec.Normalized());
        int interCount = 0;
        for (unsigned ti = 0; ti < triangles2.size(); ti++){
            vec v1, v2, v3;
            v1.x = triangles2[ti].v1().x; v1.y = triangles2[ti].v1().y; v1.z = triangles2[ti].v1().z;
            v2.x = triangles2[ti].v2().x; v2.y = triangles2[ti].v2().y; v2.z = triangles2[ti].v2().z;
            v3.x = triangles2[ti].v3().x; v3.y = triangles2[ti].v3().y; v3.z = triangles2[ti].v3().z;
            math::Triangle tri(v1,v2,v3);
            if (myRay.Intersects(tri)){
                interCount++;
            }
        }
        //if it is inside, find the triangles that have this vertex
        //and add 1 to the respective index in the counter
        if (interCount%2!=0){
            for (int ti = 0; ti < triangles.size(); ti++){
                bool isOnTri = false;
                vvr::Triangle &tri = triangles[ti];
                if ((tri.v1().x == ver.x && tri.v1().y == ver.y && tri.v1().z == ver.z) && isOnTri == false){
                    isOnTri = true;
                }
                else if ((tri.v2().x == ver.x && tri.v2().y == ver.y && tri.v2().z == ver.z) && isOnTri == false){
                    isOnTri = true;
                }
                else if ((tri.v3().x == ver.x && tri.v3().y == ver.y && tri.v3().z == ver.z) && isOnTri == false){
                    isOnTri = true;
                }
                if (isOnTri){
                    counter[ti] ++;
                }
                isOnTri = false;
            }
        }
    }

    //put the triangles in the proper struct
    cout << "\n";
    for (int ti = 0; ti < triangles.size(); ti++){
        cout << counter[ti] << " for " << ti << " ";
        vvr::Triangle &tri = triangles[ti];
        vvr::Triangle3D m_tri(tri.v1().x, tri.v1().y, tri.v1().z,
            tri.v2().x, tri.v2().y, tri.v2().z,
            tri.v3().x, tri.v3().y, tri.v3().z, Colour::blue);
        m_tri.setSolidRender(true);
        if (counter[ti]==5 || counter[ti] == 6){
            m_tris_inner.push_back(m_tri);
        }
        else if (counter[ti]>0 && counter[ti]<5){
            m_tris_intersect.push_back(m_tri);
        }
        else if (counter[ti]==0){
            m_tris_outer.push_back(m_tri);
        }
    }

Answer 1

如评论中所述，您的计数器值大于 3 的一个可能原因是顶点列表中存在重复的顶点，因此当它们都被处理时计数将得到更新。由于当任何顶点等于其任何顶点与对象相交时，三角形的计数器会增加，如果每个顶点有 2 个具有相同坐标的副本，则计数器将增加 6 次。

发生这种情况的一种可能方式是，如果您通过从二十面体开始并使用中点细分递归细分其三角形来生成模型，而不共享相邻三角形的中点顶点。

解决此问题的方法是在生成顶点时检查重复项，然后再将新顶点添加到列表中，但是您可以对代码进行一些优化，这将使它变得无关紧要。

首先，您可以在开始外循环之前通过计算 triangles2 中所有顶点的边界框来优化相交测试。您可以通过遍历所有顶点并找到最小和最大 x y 和 z 来完成此操作。然后当你测试 vertices 中的每个顶点时，首先检查它的 x y z 值是否在 triangles2 的边界框给定的范围内，如果不在则它不可能相交，你可以跳过这个循环：

for (unsigned ti = 0; ti < triangles2.size(); ti++)

或者，您可以计算边界球体并进行点对球体测试。也可以根据对象的近球形几何形状进行一些特殊情况测试 - 所有部分相交的三角形都将位于一个平面上。然而，边界框是一种很好的通用优化，适用于大多数任意形状。如果您计算两个对象的边界框，那么您可以测试它们是否在函数的最开始重叠，如果不重叠，您会立即知道顶点的 none 相交。

您可以进行的第二个更改是将 3 个索引存储到 triangles 内的 vertices 数组中，而不是存储顶点的 3 个副本。找到每个相交顶点后，不要遍历所有三角形，而是将 interCount 存储到一个数组中，每个顶点有一个条目。完成对所有顶点的迭代后，然后在单独的循环中迭代三角形：

for (int ti = 0; ti < triangles.size(); ti++)

并利用每个三角形存储的3个顶点索引，查找interCount中对应的3个值，统计有多少奇数。如果它为 0，则三角形完全位于另一个对象之外。如果它是 3 那么它完全在里面。如果它是 1 或 2，则它与表面部分相交。

这样做会更快，因为您不必为每个顶点检查每个三角形的每个顶点，而且您也不必担心计算超过 3 个顶点，因为您只有 3 个指数。

C++ Vector 比计算几何中的 Vector 修改了两次

C++ Vector is modified twice than it should in Computational Geometry

c++

algorithm

computational-geometry