Fix wind order

[Igors]

Добрый день

Дан контейнер полигонов (для простоты тр-ков).

Код

C++ (Qt)
struct CTria {
 int m_index[3];
 ...
};
 

Тр-к хранит индексы вертексов на которые он ссылается, напр (0, 1, 2)

Требуется проверить образуют ли тр-ки корректную поверхность(и) и изменить порядок индексов если это не так. Пример для 2 смежных тр-ков

(0, 1, 2) и (3, 2, 1) - поверхность корректна, если в первом тр-ке ребро 1-2, то в смежном должно быть наоборот 2-1

(0, 1, 2) и (3, 1, 2) - а здесь НЕкорректна, будут неприятности при рисовании тем же OpenGL

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

Спасибо

[ssoft]

Сначала необходимо проверить, что треугольники (полигоны) образуют поверхность, вернее поверхности без включения одинаковых ребер.
Для этого необходимо проверить вхождение каждого ребра не более чем в 2-а треугольника. Если ребро входит более 2-х раз - исходные данные не корректные.

Далее начиная с первого треугольника:

• Если для текущего треугольника имеется хоть одно запомненное ребро, то помечаем треугольник +, если все имеющиеся ребра с обратным порядком вершин, или -, если все имеющиеся ребра прямой порядок вершин. Если порядок вершин разный - петля Мебиуса. Если нет ни одного ребра помечаем треугольник +.
• Для + запоминаем ребра с имеющимся порядком вершин, для - с обратным.

+ и - и есть порядок обхода.

Всё.

[__Heaven__]

Я подобное делал путём описания вершин.
То есть при появлении у меня треугольника N я в вершину добавлял запись, что она участвует в формировании N.

В цикле проверки треугольников я беру 0 вершину треугольника и запрашиваю у неё список формируемых ею треугольников. Среди тех ищу сопрягающиеся с текущим треугольником.

[Igors]

Сначала необходимо проверить, что треугольники (полигоны) образуют поверхность, вернее поверхности без включения одинаковых ребер.
Для этого необходимо проверить вхождение каждого ребра не более чем в 2-а треугольника. Если ребро входит более 2-х раз - исходные данные не корректные.

Да, так называемый "non-manifold" (mesh). Ну придется считать 3-е и др входящие ребра открытыми (а шо делать?)

Далее начиная с первого треугольника:

• Если для текущего треугольника имеется хоть одно запомненное ребро, то помечаем треугольник +, если все имеющиеся ребра с обратным порядком вершин, или -, если все имеющиеся ребра прямой порядок вершин. Если порядок вершин разный - петля Мебиуса. Если нет ни одного ребра помечаем треугольник +.
• Для + запоминаем ребра с имеющимся порядком вершин, для - с обратным.

+ и - и есть порядок обхода.

Всё.

Ничего не понял. Для тр-ка всегда имеются 3 ребра, на то он и тр-к. Можно капитальнее? Ребра строим или как? Если да, то какая это структура? Спасибо

В цикле проверки треугольников я беру 0 вершину треугольника и запрашиваю у неё список формируемых ею треугольников. Среди тех ищу сопрягающиеся с текущим треугольником.

Ну хорошо, от вертекса получили список тр-ков в которые он входит. Довольно хлопотно, ну ладно, а дальше-то что?

[__Heaven__]

а дальше-то что?

Проходим по списку треугольников и ищем смежные. далее выполняете свою проверку.

[ssoft]

Существует глобальный массив треугольников, которому можно сопоставить глобальные массивы ребер и вершин. Здесь нас интересуют ребра.
По мере обхода треугольников, заполняем вспомогательный глобальный массив ребер. Могу предложить хранение глобального массива ребер, например, в виде QHash< QPair<int, int>, Edge >.
Это наиболее универсальный способ, но может быть и более оптимальный (например, Edge[N][N] будет эффективнее, но затраты по памяти больше; или можно разреженную матрицу взять и т.п.).

Структура struct Edge{ int m_counter; ... }; включает счетчик вхождений в треугольники.

typedef QHash< QPair<int, int>, Edge > Edges;

рассмотрим i-й треугольник, пусть l, m, n - вершины

- пытаемся найти ребро (l,m) в глобальном массиве данных по ключу QPair<int, int>( l,m ) или QPair<int, int>( m, l )
- пытаемся найти ребро (m,n) в глобальном массиве данных по ключу QPair<int, int>( m,n ) или QPair<int, int>( n,m )
- пытаемся найти ребро (n,l) в глобальном массиве данных по ключу QPair<int, int>( n,l ) или QPair<int, int>( l,n )

-- если ребер в глобальном массиве нет, запоминаем, что данный треугольник имеет прямой порядок вершин.
-- если есть хотя бы одно ребро в глобальном массиве, то - порядок прямой, если все ребра найдены вторым способом; порядок обратный, если все ребра найдены первым способом; неоднозначность (петля), если ребра найдены разным способом.

- вносим информацию о ребрах в глобальный массив (увеличиваем счетчик использования ребер в анализе)
-- если найденный порядок обхода прямой, увеличиваем счетчик первым способом (для  (l,m), (m,n), (n,l)), если обратный то вторым (для (m,l), (n,m), (l,n)).
-- если нужно, включаем в структуру Edge дополнительную информацию (например, номера вершин, номера треугольников и т.п.)
-- если счетчик превысил 2, то ребро принадлежит более, чем двум треугольникам, следовательно фигура образует не анализируемый случай поверхности.

Да, так называемый "non-manifold" (mesh). Ну придется считать 3-е и др входящие ребра открытыми (а шо делать?)

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

[Igors]

Могу предложить хранение глобального массива ребер, например, в виде QHash< QPair<int, int>, Edge >.

Не согласен, такая организация данных мне кажется легковесной/несолидной

-- если ребер в глобальном массиве нет, запоминаем, что данный треугольник имеет прямой порядок вершин.
-- если есть хотя бы одно ребро в глобальном массиве, то - порядок прямой, если все ребра найдены вторым способом; порядок обратный, если все ребра найдены первым способом; неоднозначность (петля), если ребра найдены разным способом.

Рассмотрим последний случай. Допустим нашли тр-к у которого одно ребро нормальное, а другое "кривое". И что, почему мы делаем вывод что это петля? Это может быть "устранимый"(корректируемый) дефект. Значит надо менять порядок обхода тр-ка, сразу или маркировать "-" чтобы потом всех таких исправить сразу. Но тр-к имеет соседей которые уже рассмотрены и с которыми у него все Ок - значит их тоже надо менять. А те своих и.т.д.   

См аттач (петля Мебиуса как она строится). Здесь мы зациклимся с заменой. Но стоит удалить любой полигон - и все, дефект уже устранимый.

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

Давайтк крысу (rat mesh) оставим на десерт 

[ssoft]

Могу предложить хранение глобального массива ребер, например, в виде QHash< QPair<int, int>, Edge >.

Не согласен, такая организация данных мне кажется легковесной/несолидной

ИМХО, если, структура решает необходимую задачу с требуемой производительностью, то она вполне применима. Но "хозяин - барин". 

Рассмотрим последний случай. Допустим нашли тр-к у которого одно ребро нормальное, а другое "кривое". И что, почему мы делаем вывод что это петля? Это может быть "устранимый"(корректируемый) дефект. Значит надо менять порядок обхода тр-ка, сразу или маркировать "-" чтобы потом всех таких исправить сразу. Но тр-к имеет соседей которые уже рассмотрены и с которыми у него все Ок - значит их тоже надо менять. А те своих и.т.д.   

Здесь требуется небольшая коррекция алгоритма - нужно организовать порядок обхода треугольников, начиная с соседей.

* Для этого нужно сначала сформировать глобальный массив ребер.
* Затем - цикл по всем треугольникам
** задаем/определяем порядок обхода вершин треугольника (1)
** если треугольникам просматривали
*** если порядок обхода не изменился, то переходим к следующей
*** иначе реагируем на некорректную структуру (сообщаем об ошибке, или исправляем, или удаляем треугольник, или др.)
** цикл по всем ребрам треугольника
*** определяем смежный треугольник для данного и переходим к (1)

Здесь получается рекурсия, от которой можно и избавиться.

[Igors]

*** иначе реагируем на некорректную структуру (сообщаем об ошибке, или исправляем, или удаляем треугольник, или др.)

Народная примета: много "или" почти всегда отмазка  Задача была исправить (если возможно), а не сообщать и не удалять. И если исправляем то неясно как Вы избегаете зацикливания

В общих чертах сделал так

- строю ребра (полигоны знают свои ребра). Одно ребро шарится 1 или 2 полигонами. Для крысы ребро не уникально (возможно 2 и более ребер с одной парой вертексов)

- строю "islands" присваивая каждому полигону ID того island в который он входит. Заодно собираю индексы всех "конфликтных" ребер.

- используя конфликтные ребра для каждого island получаю контейнер ID тех островов с которыми он конфликтует

- "сливаю" все islands начиная от большего, маркируя их +/-. Ну и финальная инверсия для тех кто оказался на инверсном острове

Не то чтобы "длинно", но простотой не блещет. Думал может перемудрил - ну вроде нет. Спасибо за обсуждение