Search code examples
c++openglshadervertexuv-mapping

Identify unwrapped mesh UV regions

suppose we have a 3D mesh with texture coords for each vertex, so if I render it unwrapped I get something like this (ignore the red square):

enter image description here

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. The idea is to use this value as an index for a color table and get something like this (hand made):

enter image description here

I tried iterating each vertex and finding "unconnected" triangles comparing texture coords, but the mesh indices order seems unrelated to how UVs are placed or i'm not applying the correct formula. I have no doubts about how to store and pass this value to a shader or whatever, the doubt is how to know the "region" to which the vertex belongs, or ultimately, the pixel.

Thanks.

UPDATE: The data used to render the mesh is a list of vertices (GL_VERTEX_BUFFER) plus a list of indices (GL_ELEMENT_ARRAY). The mesh is rendered as GL_TRIANGLES, and each vertex is a struct like this:

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;
};

UPDATE 2: I created a new vertex array of MPUVRegionVertex, with an element for each index (not per unique vertex). Following @CsabaBálint response I ended up with this code:

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++;
}

The result is a different k every three indexes, this means that k++ is called for each new triangle, so I'm missing something in the algorithm :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

Some information about the mesh:

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

UPDATE 3

For more information, there is only one UV coord for each vertex.

Deductions / Rules up to now:

  • a vertex can be in most than one face (part of more than one triangle).
  • a vertex will be n times in the vertexToFace array, once per face it belongs.
  • first vertex in the vertexToFace array will arbitrary have regionId = 0.
  • a vertex belongs to a region if it shares the same x and y coords or the same face of another vertex in that region.

If I understood well, this is the correct information to implement the non-recursive graph traversal. I need to iterate and save both connected and unconnected vertex, all connected vertex will be part of the current region, all not will be checked again with the already connected, the first iteration stores the first triangle vertexes, the second one stores all vertexes of triangles that are "touching" the first triangle, continue until an iteration gives no new connected vertex (optimization here if we check only with the list of vertex added in the last iteration), no new vertex added means it's time to increment the regionId and start again with the first unconnected vertex.

I will try to implement the search following that design.

Solution

  • Ok, following the previously mentioned points and thanks to Csaba Bálint for the initial hints, I found a solution:

    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::set<int> notAssigned;

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

std::forward_list<int> addedInLastIterationElements;
int currentRegion = 0;

//while there are not assigned vertex 
while (notAssigned.size() > 0)
{
    //the first not assigned element simulate that was "added" to the current region in the last check
    addedInLastIterationElements.push_front(*notAssigned.begin());

    //this first has the new current region as it's regionId
    uvVertexData[*notAssigned.begin()].regionId = currentRegion;

    //and becomes assigned
    notAssigned.erase(notAssigned.begin());

    do
    {
        //will store the elements added in the next iteration
        std::forward_list<int> newRegionElements;

        //iterate not assigned elements
        for(int currentElement : notAssigned)
        {
            //iterate elements added to the current region in the last iteration
            for(int currentRegionElement : addedInLastIterationElements)
            {
                //compare if this vertex belongs to the same region of some of the recently added
                if((uvVertexData[currentElement].x == uvVertexData[currentRegionElement].x && 
                    uvVertexData[currentElement].y == uvVertexData[currentRegionElement].y) ||
                   (uvVertexData[currentElement].faceId == uvVertexData[currentRegionElement].faceId))
                {
                    //store as an element added this iteration
                    newRegionElements.push_front(currentElement);

                    //store the current region
                    uvVertexData[currentElement].regionId = currentRegion;
                }
            }
        }

        //remove new elements from the notAssigned list
        for(int assigned : newRegionElements)
        {
            notAssigned.erase(assigned);
        }

        //replace the elements added the previous iteration for the last iteration
        addedInLastIterationElements = newRegionElements;

        //prepare for new elements
        newRegionElements.clear();
    }
    //if there is no match in the last iteration, means all remaining vertex belongs to another region
    while(!addedInLastIterationElements.empty());

    //next region
    currentRegion++;
}

    If a render the regionId generated with a table of colors I get the desired result (note that colors varies only in 0.1 per channel, but here are 10 different colors):

    enter image description here

    Sure the algorithm can be optimized but it performs in a reasonable time and memory usage, so, for now it's ok.