Идентифицировать развернутые сетки УФ области

Question

Предположат, у нас есть 3D-сетку с текстурными координатами для каждой вершины, так что если я сделать это разворачивало я получаю что-то вроде этого (игнорировать красный квадрат):

Теперь я 'm пытается найти правильный алгоритм, чтобы однозначно идентифицировать те области, используя вершинные UVs и сохраняя атрибут с этим уникальным значением id. Идея заключается в том, чтобы использовать это значение в качестве индекса для таблицы цветов и получить что-то вроде этого (ручная работы):

Я попытался перебору каждой вершины и найти «несвязанные» треугольники сравнивающих текстур COORDS, но порядок индексов сетки кажется не связанным с тем, как размещены УФ-объекты, или я не применяю правильную формулу. Я не сомневаюсь, как хранить и передавать это значение в шейдер или что-то еще, сомнение в том, как знать «регион», к которому принадлежит вершина, или, в конечном счете, пиксель.

Спасибо.

ОБНОВЛЕНИЕ: Данные, используемые для отображения сетки, представляют собой список вершин (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; 
}; 

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

Результатом является другими к каждому три индекса, это означает, что к ++ вызываются для каждого нового треугольника, так что я что-то в алгоритме отсутствует: 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 

UPDATE 3

Для получения дополнительной информации, есть только один УФ коорд для каждой вершины.

Отчисления/Правила до сих пор:

• вершина может быть в большей, чем одно лицо (часть из более чем одного треугольника).
• вершина будет n раз в массиве vertexToFace, как только на лицо оно принадлежит.
• первая вершина в массиве vertexToFace будет произвольной иметь regionId = 0.
• вершина относится к области, если она разделяет одни и те же координаты x и y или одну и ту же грань другой вершины в этом регионе.

Если я правильно понял, это правильная информация для реализации нерекурсивного обхода графика.Мне нужно повторить и сохранить как подключенную, так и несвязанную вершину, все связанные вершины будут частью текущей области, все не будут проверены снова с уже подключенными, первая итерация хранит первые треугольные вершины, вторая - все вершины треугольники, которые «касаются» первого треугольника, продолжаются до тех пор, пока итерация не даст никакой новой связанной вершины (оптимизация здесь, если мы проверяем только список вершин, добавленных в последнюю итерацию), никакая добавленная новая вершина означает, что пришло время увеличить областьId и снова начните с первой несвязанной вершины.

Я попытаюсь реализовать поиск по этому проекту.

Answer 1

Хорошо, следуя ранее упомянутые точки и благодаря Csaba Bá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::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++; 
} 

Если визуализировать RegionID генерируется с таблицей цветов я получить желаемый результат (обратите внимание, что цвет изменяется только в 0,1 на каждый канал, но вот 10 различных цветов):

Конечно алгоритм может быть оптимизирован, но он выполняет в течение разумного времени и использовании памяти, так что, пока это о к.

Answer 2

Теперь я пытаюсь найти правильный алгоритм, позволяющий однозначно идентифицировать те регионы, используя вершинные UVs, и сохранять атрибут с этим уникальным значением id.

Создание графа

Сделать идентификаторы для вершин и граней (пронумеровать их). Но убедитесь, что одни и те же вершины получают одинаковые id-s, сравнивают их по UV или положению.

Создать вектор: std::vector<int> vertexToFace;

vertexToFace[i]==j означает, что я й вершина находится на грани у.

Затем две вершины являются соседями, если они находятся на одной грани.

Затем создайте std::vector<std::forward_list<int> > graph; Сохраните вершины в качестве векторного указателя и добавьте соседей. (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), но его легко реализовать. Сложнее, но быстрее требуется другой вектор: std::vector<std::array<int,3>> faceToVertex;, таким образом, из i-й вершины вы можете получить доступ к своим соседям в постоянное время. В любом случае, мы построили график, в котором мы ищем connected components, что легко с depth-first search.

Реализация связных компонент алгоритма

Для реализации этого, вы должны сделать еще один вектор: 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); 
} 

Тогда мы сделали с этой задачей, но это еще не самое быстрое решение.

Faster алгоритм

Чтобы получить еще быстрее, мы должны избавиться от рекурсии и нам не нужны графики впоследствии использовать std::forward_list<int> для стека. Вставьте первую вершину в стек. Затем поместите одну вершину, установите ее компоненту в k. Нажмите все его соседи в стек, а затем удалите соседей. Другими словами, добавьте список соседей в стек (очень быстрая операция). Повторяйте, пока стек не будет пустым.

Таким образом, мы не будем делать бесконечный цикл, потому что, если мы вернемся к одной и той же вершине, у него не будет соседей, и мы уже посетили их. Поэтому нет необходимости в посещенном векторе. Мы можем установить элемент вектора компонентов несколько раз, но всегда к одному и тому же значению, поэтому зачем его проверять?

Однако, если у нас нет посещенного вектора, то сложнее найти другую вершину, которую мы не посетили. Хотя мы могли бы искать некоторую вершину на графике, у которой все еще есть соседи, есть лучшее решение.

Создать std::set<int> notvisited(); Для тех пунктов, которые еще не были просмотрены. Сначала он должен содержать все вершинные идентификаторы, а затем каждый раз, когда мы устанавливаем идентификатор компонента, мы пытаемся удалить вершину из набора notvisited. Мы повторяем получение вершины из набора и запускаем алгоритм fill_from() до тех пор, пока набор не станет пустым, в то же время у нас есть все идентификаторы компонентов.

UPDATE: обновленная информация о сохранении сетки.

Если у вас нет равных элементов в «списке вершин» (почему бы вам), то индекс вершины является его положением в массиве. Таким образом, id-s для вершин выполняется.

Ид-s для треугольников или лица, в «списке индексов», позвольте мне назвать этот массив int listOfIndices[];, для J-го лица, вершины, соединенные с ней listOfIndices[3*j + 0], listOfIndices[3*j + 1] и listOfIndices[3*j + 2]. Чтобы сделать первый вектор, вам необходимо сделать следующее:

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 каждый раз).