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

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

#0

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

9 янв. 2019, 13:01

#1

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

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

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

9 янв. 2019, 23:27

#2

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

10 янв. 2019, 0:21

#3

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 для выпуклого полигона тривиальный.

+ Картинки

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

#4

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

11 янв. 2019, 0:30 (Правка: 0:34)

#5

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

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

#6

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

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

#7

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

11 янв. 2019, 12:03

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