Как накапливать края трехмерной треугольной сетки? Алгоритм для подсчета ребер сетки в c c ++?
Я хочу накапливать края треугольной модели / сетки. Например, треугольный куб имеет 18 ребер.
Это выглядит так просто и легко, но буквально это слишком сложно.
У меня есть вся смежная информация о треугольнике. Например, у меня есть смежные вершины и треугольники, и я знаю, какие треугольники имеют общее ребро, но проблема в том, как извлечь это общее ребро между двумя треугольниками.
Одна вещь, которая должна быть учтена, это то, что не должно быть повторяющегося индекса точки / вершины ребра.
Первое, как посчитать общее количество ребер. Помните, что куб имеет 18 ребер.
Я много пробовал, но сейчас сдался. 🙂
любая идея?
,
Обновление 1:
Хорошо, у меня есть треугольник T [i] (индекс v1, индекс v2, индекс v3), который имеет три ребра v1v2, v2v3, v3v1.
и у меня есть соседские треугольники всех ребер.
T[i].index_of_sharedTri1_with_edge_v1v2,
T[i].index_of_sharedTri2_with_edge_v2v3,
T[i].index_of_sharedTri3_with_edge_v3v1;
Теперь какой цикл мне нужно сделать, чтобы извлечь уникальный край? Какую информацию мне нужно сравнить? Нужно ли сравнивать реберные вершины, общий индекс tri или что? Я пытался разными способами, но это так сложно.
Обновление 2:
GLTris *e = new GLTris[nb_Tris*3];
int n = getTotalEdges_Sorted(indices, nb_Tris, e);
cout<<n<<endl;
int ne = RemoveDublicatesFromAnSortedEdgeArray(e, n);
for(int i=0; i<ne; i++)
e[i].Cout();
Я пробовал это, и это прекрасно работает, но мне нужно выяснить, будет ли это работать на всех типах сеток и это эффективный способ?
Решение
Если у вас есть количество треугольников и информация о смежности для каждого, тогда число ребер просто:
3 * num_triangles — num_shared_edges
Где num_shared_edges может быть накоплено путем итерации по каждому треугольнику и суммирования количества смежных треугольников. Затем разделите на два, так как вы посчитали их все дважды (очевидно, предполагается, что у вас не более двух треугольников на ребро)
Если вы хотите создать список уникальных ребер, вам необходимо отслеживать их, предпочтительно в какой-то легко индексируемой структуре, например карте.
Процедура примерно такова:
- Определите ребро как два индекса (i1, i2). Закажите эти индексы так, чтобы i1 < i2. Теперь общие ребра гарантированно совпадают.
- Создайте некоторую структуру списка, которая может содержать эти края. Вы должны быть в состоянии быстро найти существующее ребро по его индексам, поэтому вам нужна структура с возможностью поиска, например, какое-то дерево. Если бы вы использовали c ++, я бы предложил использовать карту с парой i1, i2 в качестве ключа.
- Переберите все треугольники, добавив 3 ребра для каждого. Не добавляйте ребро, если оно уже существует.
Это все, что нужно сделать.
Другие решения
Если поверхность проста и закрыта, чем Эйлерова характеристика количество ребер E = F + V - 2, Куб в вашем примере имеет V=8, F=12,
Я выучил простой трюк.
Сначала вы определяете структуру, которая представляет собой неупорядоченную пару индексов вершин (например, struct{int i,j} это гарантирует, что i<j).
Затем создайте std::set<UnorderedPair>,
Наконец, каждый раз, когда вы сталкиваетесь с ребром, просто вставьте его в этот набор. В конце, количество элементов в этом наборе даст вам количество уникальных ребер.