Войти
ПрограммированиеФорумОбщее

Оптимизация меша после булевых операций

#0
13:01, 9 янв. 2019

Сделал булевские операции над CSG. Всё работает быстро и без глюков, но реализация через BSP дает слишком много полигонов в полученном меше. Искал материалы по оптимизации меша после булевых операций, но ничего не нашел. Помогите кто чем может.


#1
23:27, 9 янв. 2019

Я не делал CSG, но делал резку выпуклых мешей плоскостями.

Если меш хранится в виде треугольников, то
1) их труднее резать (в одной грани может быть много треугольников, каждый из которых может не разрезаться или резаться на треугольник плюс ещё два треугольника);
2) лишние треугольники размножаются с бешеной скоростью;
3) потом надо оптимизировать избыточный меш. Не то чтобы это сложно, но очень муторно и постоянно всплывают погрешности вычислений. Регулярно где-то остаётся лишний треугольник или наоборот щель.

Если меш хранится в виде полигонов, то
1) резать понятнее (одна грань ― один многоугольник, либо он режется на два таких же, либо грань не режется вообще),
2) вычисления сильно проще и их сильно меньше,
3) многоугольники не размножаются вообще, лишних появиться в принципе не может,
4) ничего не надо оптимизировать, а при необходимости преобразовать к треугольному мешу элементарно.

#2
0:21, 10 янв. 2019

Берутся 2 меша и из их полигонов строятся 2 bsp дерева - какраз резка плоскостями.
Если исходный меш сложнее кубика, то он уже даже на этапе построения дерева сам себя плоскостями изрежет порядочно.
Один полигон может быть разбит плоскостью на 2, потом следующей плоскостью половинка еще на 2 и так далее.
вот либа с примером работы
Это как я  понимаю стандартная реализация булевских операций через bsp деревья  - просто, быстро, но очень много лишнего на выходе. Без последующей оптимизации результата никак - но ни одной статьи или документа с описанием алгоритмов я не нашел.

#3
(Правка: 11 янв. 2019, 0:13) 23:22, 10 янв. 2019

0. Объединить совпадающие вершины, если такие получились.

1. Сгруппировать все треугольники по граням. В каждой группе смежные треугольники, принадлежащие одной плоскости.

2. Дальше для каждой группы-грани, в которую попало больше одного треугольника, выделить внешние рёбра. Внешние принадлежат только одному треугольнику. Внутренние принадлежат двум.

3. Выделенные рёбра отсортировать в замкнутую цепочку: A->B, B->C, C->D, D->A. UPD: Пасьянс должен сложиться. Если не сложился или попалось ребро X->X, искать ошибку на предыдущих шагах.

4. Слить вместе смежные рёбра, лежащие на одной прямой. UPD: Это потенциальный источник ошибок, когда, например, у одной грани четыре коротких ребра подряд слились в одно длинное прямое, а у смежной с ней те же четыре ребра из-за погрешности и другого порядка вычислений слились не в одно, а в два. Чтобы такого никогда не происходило, надо усложнять или вообще менять алгоритм.

5. Полученный полигон заново триангулировать.

PS
Если в получившейся сетке есть вершины, принадлежащие только двум треугольникам, или рёрба, принадлежащие только одному, значит из-за погрешности вычислений что-то недооптимизировалось или переоптимизировалось. Скорее всего в п.0 и п.4, в п.1 тоже может.

PPS
От моего случая со строго выпуклыми мешами только два отличия:

― В пункте 3 я мог не выстраивать рёбра в цепочку, а взять среднюю точку и отсортировать все вершины вокруг неё по часовой стрелке (ну или против).
― Пункт 5 для выпуклого полигона тривиальный.

+ Картинки
#4
(Правка: 0:34) 0:30, 11 янв. 2019

Ну да, опытным путем примерно к тому же алгоритму и пришел. Только при выстраивании внешних граней в замкнутую цепочку может быть такой вариантИзображение, где непонятно какая грань следующая и походу еще придется анализировать углы между гранями.
Да и с полигонами с отверстиями заморочки - получится 2 цепочки: внешняя и внутренняя и определять кто из них кто, прежде чем скормить функции триангуляции.
Ну а в случае строго выпуклых полигонов все довольно тривиально.

#5
(Правка: 1:33) 1:32, 11 янв. 2019

alexzzzz
> Слить вместе смежные рёбра, лежащие на одной прямой. UPD: Это потенциальный источник ошибок
Чтобы не было проблем с плавающим питухом, надо не "лежащие на одной прямой", а "принадлежащие одному ребру исходного меша". В общем, использовать точные дискретные топологические признаки вместо приблизительных.

#6
(Правка: 8:49) 8:43, 11 янв. 2019

MaRC
А зачем постфактум что-то анализировать? Почему при рассечении плоскостью грани для новой вершины не сохранять информацию, что она результат рассечения ребра, образованного вершинами X Y?
upd. Сейчас только прочитал пост выше от смайла. Насколько я понял, он именно это и советует.

#7
12:03, 11 янв. 2019

}:+()___ [Smile]
MrShoor
Очень ценное замечание - я до этого хранил только информацию в новых полигонах, какому они принадлежали полигону до рассечения. А можно и нужно в процессе сечения сохранять доп информацию и о гранях с вершинами. Это и количество расчётов уменьшит и от многих проблем избавит.

ПрограммированиеФорумОбщее