Нахождения Лики сетка Подчасть

Question

Описание:

У меня есть сетка и ее вся вершинное лицо информации (индексы вершин, положение вершин, индексы лица и т.д.), и я хочу сделать суб-часть этого сетка. Например, если у меня есть ручная сетка, я хочу только отобразить один из пальцев.

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

Вопрос:

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

Дополнительная информация:

class Vertex 
{ 
    Vertex(float _x, float _y, float _z) 
    { 
     x = _x; y = _y; z = _z; 
    } 
    float x, y, z; // Positions 
}; 

class Face 
{ 
    Face(int _v1, int _v2, int _v3) 
    { 
     vertIndex1 = _v1; vertIndex2 = _v2; vertIndex3 = _v3; 
    } 
    int vertIndex1, vertIndex2, vertIndex3; // Vertex indices 
}; 

Пример использования для триангулированной квадратной сетки:

некоторый вектор, такой как std::vector<Vertex> verts и std::vector<Face> faces. У меня есть Vertex v1 (0,0,0), v2 (1,0,0), v3 (0,1,0) и v4 (1,1,0). Таким образом, соответствующие объекты Face являются f1 (0, 1, 2) и f2 (0, 3, 4), где 0, 1, 2 и 4 являются индексами Vertex объектов в векторе verts. Как вы можете видеть, вершина может быть в разных Face с.

Теперь, скажем, у меня есть рука сетки, где verts.size() является 6000 и faces.size() 12000. Однако, вместо всей руки сетки, я хочу сделать только мизинец и у меня есть только набор вершинных индексов мизинца такого как (345, 369, 541, ...).

Итак, я знаю, какие вершины мне нужно использовать, я знаю всю информацию о лицах, и я хочу найти индексы лица только для этих заданных вершин.

Answer 1

Если простой алгоритм O (m + n) -time, O (n) -пространства, описанный в комментарии, является слишком медленным, вы можете сделать множество вещей, но я предлагаю следующий простой трюк, будет быстро находить все соответствующие грани всякий раз, когда (а) ширина или высота или глубина ограничивающей рамки, содержащая все вершинные части, является «маленькой», и (б) большинство лиц не являются «слишком широкими»:

Предкоммутировать 6 списков граней, 2 для каждого измерения (x, y, z): один из них сортируется путем увеличения минимальной координаты вершины в этой размерности, а другой сортируется путем увеличения максимальной координаты вершин в этом направлении. Из данного списка вершин подчасти, найдите минимальное и максимальное положение в каждом из трех измерений (так что 6 чисел, mx, my, mz, Mx, My, Mz). Двоичный поиск в списке лиц, отсортированных по минимальной вершине x координаты для mx, а затем снова для Mx, что дает позиции в списке i и j соответственно. Нам нужно только проверить поверхности в диапазоне i ... j, так как каждая другая грань по определению имеет по крайней мере одну вершину с координатой x вне диапазона mx .. Mx (если ее минимальная координата x равна < mx, он имеет по крайней мере 1 вершину вне диапазона, если ее минимальная вершина x равна> Mx, то все 3 вершины находятся за пределами диапазона). Помните j-i и делайте аналогично для остальных 5 отсортированных списков, отслеживая один с наименьшим значением j-i. Наконец, проверьте все грани в этом наименьшем возможном списке «трудный путь».