c++ - 识别展开的网格 UV 区域

Question

假设我们有一个 3D 网格，每个顶点都有纹理坐标，所以如果我渲染它展开，我会得到这样的东西(忽略红色方 block ):

现在我正在尝试找到合适的算法来使用顶点 UV 唯一标识这些区域并存储具有此唯一 ID 值的属性。这个想法是使用这个值作为颜色表的索引并得到这样的东西(手工制作):

我尝试迭代每个顶点并找到比较纹理坐标的“未连接”三角形，但网格索引顺序似乎与 UV 的放置方式无关，或者我没有应用正确的公式。我对如何存储这个值并将其传递给着色器或其他任何东西没有疑问，问题是如何知道顶点所属的“区域”，或者最终，像素。

谢谢。

更新:用于渲染网格的数据是顶点列表 (GL_VERTEX_BUFFER) 加上索引列表 (GL_ELEMENT_ARRAY)。网格被渲染为 GL_TRIANGLES，每个顶点都是这样的结构:

struct Vertex
{
    float x, y, z;
    float nx, ny, nz;
    float tcx, tcy;
    float regionId; //the attribute I want to fill
};

struct MPUVRegionVertex
{
    float x, y;
    int faceId, regionId;
};

更新 2:我创建了一个新的 MPUVRegionVertex 顶点数组，每个索引都有一个元素(不是每个唯一顶点)。在@CsabaBálint 回复之后，我得到了这段代码:

MPUVRegionVertex* uvVertexData = new MPUVRegionVertex[indexCount];

for(int ic = 0; ic < indexCount / 3; ic++)
{
    for(int vc = 0; vc < 3; vc++)
    {
        uvVertexData[3*ic+vc].x = vertexData[indexData[3*ic+vc]].tcx;
        uvVertexData[3*ic+vc].y = vertexData[indexData[3*ic+vc]].tcy;
        uvVertexData[3*ic+vc].faceId = ic;
    }
}

std::vector<std::forward_list<int> > graph(indexCount);

for(int t1=0;t1 < indexCount; ++t1)
{
    for(int t2 = t1 + 1; t2 < indexCount; ++t2)
    {
        if (uvVertexData[t1].faceId == uvVertexData[t2].faceId)
        {
            graph[t1].push_front(t2);
            graph[t2].push_front(t1);
        }
    }
}

std::forward_list<int> stack;
std::vector<int> component(indexCount);
std::set<int> notvisited;

for(int nv = 0; nv < indexCount; nv++)
{
    notvisited.insert(nv);
}


int k = 0;
while(notvisited.size() > 0)
{
    stack.push_front(*notvisited.begin());
    notvisited.erase(notvisited.begin());

    while(!stack.empty())
    {
        //SOMETHING WRONG HERE
        int temp = stack.front();
        notvisited.erase(temp);
        stack.pop_front();
        component[temp] = k;
        stack.merge(graph[temp]);
        graph[temp].clear();
    }
    k++;
}

结果是每三个索引都有一个不同的 k，这意味着为每个新三角形调用 k++，所以我在算法中遗漏了一些东西 :S。

component[0]=0
component[1]=0
component[2]=0
component[3]=1
component[4]=1
component[5]=1
component[6]=2
component[7]=2
component[8]=2
component[9]=3
...
component[1778]=592
component[1779]=593
component[1780]=593
component[1781]=593

关于网格的一些信息:

Size of shape[0].indices: 1782
shape[0].positions: 1242
shape[0].texcoords: 828
shape[0].normals: 1242

更新 3

有关更多信息，每个顶点只有一个 UV 坐标。

到目前为止的扣除/规则:

• 一个顶点可以在一个以上的面上(多个三角形的一部分)。
• 一个顶点将在 vertexToFace 数组中出现 n 次，它所属的每个面一次。
• vertexToFace 数组中的第一个顶点将任意具有 regionId = 0。
• 如果一个顶点与该区域中的另一个顶点共享相同的 x 和 y 坐标或相同的面，则该顶点属于该区域。

如果我没看错的话，这是实现非递归图遍历的正确信息。我需要迭代并保存连接和未连接的顶点，所有连接的顶点都将成为当前区域的一部分，所有不连接的顶点都将再次检查已连接的顶点，第一次迭代存储第一个三角形顶点，第二次存储所有顶点“接触”第一个三角形的三角形，继续直到迭代没有给出新的连接顶点(如果我们只检查上次迭代中添加的顶点列表，则此处优化)，没有添加新顶点意味着是时候增加 regionId 和从第一个未连接的顶点重新开始。

我将尝试按照该设计实现搜索。

Answer 1

Now I'm trying to find the proper algorithm to uniquely identify those regions using the vertex UVs and storing an attribute with this unique id value.

创建图表

为顶点和面创建 id(给它们编号)。但要确保相同的顶点获得相同的 id-s，通过 UV 或位置进行比较。

创建一个 vector :std::vector<int> vertexToFace;

vertexToFace[i]==j表示第 i 个顶点在 j 面上。

如果两个顶点在同一个面上，则它们是相邻的。

然后创建一个 std::vector<std::forward_list<int> > graph;将顶点存储为 vector 索引，并添加邻居。 (O(n^2) 复杂度)

为此，您必须取第 i 个顶点，并且对于每个 j，您必须检查它们是否在同一面上。稍微优化的版本:

for(int i=0; i<n; ++i) for(int j=i+1; j <n ++j)
if (vertexToFace[i] == vertexToFace[j])
{
    graph[i].push_front(j);
    graph[j].push_front(i);
}

这是 O(n^2)，但很容易实现。一个更难但更快的需要另一个 vector :std::vector<std::array<int,3>> faceToVertex; ，这样，从第 i 个顶点你可以在常数时间内访问它的邻居。无论哪种方式，我们都建立了一个图表，我们正在寻找 connected components。 , 这很容易 depth-first search .

实现连通分量算法

要实现这一点，您必须创建另一个 vector :std::vector<bool> visited(n,false); , 和另一个 std::vector<int> component(n) .您的问题的解决方案将在最后一个中。

算法简单，从顶点0开始，设visited[0] = true;和 component[0]=0; .然后对每个未访问的邻居做完全相同的事情，所以对于邻居 i(forward_list 的某个元素)if (!visited[i]) component[i] = 0; ，然后做同样的事情。当组件的所有元素都被访问时它停止。因此，您必须寻找一个未访问的元素，然后再次执行上述操作，但要知道您正在执行组件 1，依此类推。示例:

int l, k=0;
while(l!=n)
{
    l=0;
    while(visited[l]) l++;
    fill_from(graph, visited, component, l, k);
    ++k;
}

我想你明白了，所以:(伪代码)

void fill_from(graph, visited, component, l, k)
{
    if(visited[l]) return;
    component[l] = k;
    for(auto &i : graph[l])
            fill_from(graph,visited,component,i,k);
}

然后我们完成了任务，但这还不是最快的解决方案。

更快的算法

为了更快，我们必须摆脱递归，之后我们不需要图表，使用 std::forward_list<int>用于堆栈。将第一个顶点插入堆栈。然后弹出一个顶点，将其组件设置为 k。将 所有邻居 插入堆栈，然后删除邻居。换句话说，将邻居列表附加到堆栈(非常快的操作)。重复直到栈不为空。

这样我们就不会无限循环，因为如果我们回到同一个顶点，它就没有邻居，而且我们已经访问过它们。因此不需要访问 vector 。我们可以多次设置分量 vector 元素，但总是设置相同的值，所以为什么要检查它？

但是，如果我们没有访问过的 vector ，那么就很难找到我们没有访问过的另一个顶点。虽然我们可以在图中寻找一些仍然有邻居的顶点，但有更好的解决方案。

创建 std::set<int> notvisited();对于那些还没有访问过的点。起初它应该包含所有顶点 ID，然后每次我们设置组件 ID 时，我们都会尝试从 notvisited 中删除一个顶点。放。我们重复从集合中获取一个顶点并运行 fill_from() 算法直到集合变空，同时，我们拥有所有组件 id-s。

更新:使用有关如何存储网格的更新信息。

如果您在“顶点列表”中没有相等的元素(为什么会这样)，那么顶点的索引就是它在数组中的位置。这样，顶点的 id-s 就完成了。

三角形或面的 id-s 在“索引列表”中，让我将此数组命名为 int listOfIndices[]; ，对于第j个面，与其相连的顶点为listOfIndices[3*j + 0] , listOfIndices[3*j + 1]和 listOfIndices[3*j + 2] .要制作第一个 vector ，您必须执行以下操作:

std::vector<int> vertexToFace(num_of_verteces); //previously n
for(int j = 0; j < num_of_faces; ++j)
{
    vertexToFace[listOfIndices[3*j + 0]]=j;
    vertexToFace[listOfIndices[3*j + 1]]=j;
    vertexToFace[listOfIndices[3*j + 2]]=j;
}

(建立逆关系的算法)；请注意，在这种情况下，您甚至不需要不同的 faceToVertex数组，因为你已经有了它(listOfIndices)，你只需要用不同的方式索引它(每次除以 3)。