Все кто работал с конструктивной сплошной геометрией (CSG), создавал свой воксельный движок или использовал готовые модели, сталкивался с проблемой оптимизации треугольников. Число и расположение треугольников у моделей может быть не оптимальным. Конечно, если дизайнер нарисовал для вас лично модель, его можно попросить её исправить. Но как быть, если модель процедурная, и дизайнер не может исправлять каждую процедурную деталь?

Нам придется делать это автоматически.

Для примера, возьмем одну деталь, из процедурного генератора стадий созданного на Javascript:

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

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

Решение с виду было простым, но мне, это лишь казалось. В результате целый месяц ушел на реализацию.

Так как же оно работает? Разберемся с этапами: объединяем все треугольники по группам в зависимости от текстуры и текстурной сетки. Мы получим группы где у нас содержатся треугольники только с одной текстурой и текстурной сеткой у которой при удалении вершин не изменится общая картина.

После этого мы преобразуем наши треугольники в полигоны и производим удаление лишних вершин. Как только мы это выполним, мы уже получим качественную модель. Но это только начало пути.

Преобразовать полигоны в треугольники задача не самая простая, обратный путь сложнее. Преобразовать можно при помощи готовых библиотек, но тут нас ждет одно большое разочарование. Готовые библиотеки такие как earcut, libtess и несколько других, умудряются так криво расположить треугольники, что даже в редакторе сложно исправить дефекты.

После десятка зарисовок на листке бумаге, мною было принято решение использовать Триангуляцию Делоне (созданная еще в 1934 году советским математиком Борисом Николаевичем Делоне), но всё далеко не так просто. Триангуляцию Делоне в чистом виде применить не получится. Хоть количество и расположение треугольников будет всегда оптимальным:

В теории всё хорошо, а в реальности у нас сразу же возникает проблема, треугольники идут не в тех местах:

Красным обозначено ожидаемое разбиение относительно нашей структуры. Но нас ждал сюрприз в этом месте, треугольники шли пересекая конечную структуру. Для этого пришлось модернизировать метод, задача свелась к перестраиванию треугольников которые пересекают наше ребро. После преобразований получился следующий результат:

Теперь треугольники в нужной последовательности, с оптимальным заполнением полигона. На этом можно было остановиться.

Но это далеко не всё, так как реализация Javascript в браузерах не самая быстрая. А расчеты физики на CPU через Javascript слишком чувствительны к числу треугольников, было применено дополнительное преобразование:

На изображении показана начальная деталь и она же после преобразований, из полигона мы получили 6 треугольников, отлично расположенных, а после конечного преобразования их уже 4, что и требовалось. Конечно, это изменит модель и в ней будут заметны микро трещины, но так же такое преобразование позволяет дополнительно сократить модель еще на 5-10%.

А вот и конечный результат, после всех преобразований, теперь наша модель выглядит так:

Оригинальная модель содержала 4148 треугольников, после преобразования в полигоны и с удалением лишних вершин: 1174 треугольника, с применением последней оптимизации мы получили 994 треугольника.

Итог: мы сократили модель с 4148 треугольников до 994.

Это отличный результат, теперь наша модель занимает меньше памяти, она быстрее отображается на видеокарте и для работы физического движка созданного на Javascript уже не так накладно обрабатывать такое число треугольников.