Почему линия волос создавала вырожденные треугольники: разбор Monster Forge

Материал подготовлен ИИ-агентом от имени Mr Q. Минимальный численный пример проверен выполнением Python; описание исправления и проверок сверено с исходниками Monster Forge.

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

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

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

Для небольшого примера возьмём треугольник A=(0,0), B=(1,1), C=(2,-1) и оставим область y >= 0. На ребре A→B сохраняется A. На B→C сохраняется B и находится пересечение D=(1.5,0). На C→A пересечение совпадает с A.

Результирующий список точек: [A, B, D, A].

В коде геометрические точки объединяются по ключу из округлённых координат. Совпавшие A получают один индекс в общей таблице вершин. Но сам список индексов полигона после такого объединения остаётся таким: [0, 1, 2, 0].

Триангуляция веером создаёт две грани: (0,1,2) и (0,2,0). Вторая ссылается на одну вершину дважды и имеет нулевую площадь. Уникальность общей таблицы вершин и корректность границы отдельного полигона — разные свойства.

В проверенном примере площади граней до исправления составляют [0.75, 0.0]. После удаления повторного индекса остаётся одна грань с площадью 0.75. Для этого воспроизведения достаточно стандартной библиотеки Python.

В функции scalp_shell последовательность уже объединённых индексов очищается от повторов с сохранением порядка:

ids = list(dict.fromkeys(index(p) for p in polygon))

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

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

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

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

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

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

Исправление: https://github.com/QoobIY/monster-forge/blob/main/monsterforge/constructor_surface_fit.py

Регрессионные проверки: https://github.com/QoobIY/monster-forge/blob/main/tests/creature_workshop/test_constructor_hair_fit.py

Полный исполняемый пример и английская версия разбора: https://dev.to/qoobiy/when-clipping-a-triangle-creates-a-zero-area-face-a-monster-forge-case-study-3ndk

Monster Forge — открытый low-poly конструктор персонажей с Python-бэкендом и браузерным интерфейсом. Код и объявленные встроенные исходные ресурсы доступны под Apache-2.0. Некоторые позиционные референсы созданы с помощью ИИ; обычная сборка работает по сохранённым рецептам геометрии.

Проект и инструкции запуска: https://github.com/QoobIY/monster-forge

Автор проекта: Mr Q. Публичный контакт: https://github.com/QoobIY