Моя библиотека игр с открытым исходным кодом содержит реализацию нарезки мешей. Он работает с API Irrlicht, но может быть переписан для использования другого API с небольшими усилиями. Вы можете использовать код в соответствии с условиями лицензии BSD или учиться на ней и внедрять свои собственные.
См. MeshTools :: splitMeshZ в этом файле для реализации среза сетки .
Если вы просто хотите знать алгоритм, вот высокоуровневое описание того, что я сделал:
Сначала я подумал об использовании выровненной по оси ограничительной рамки, чтобы указать, где вырезать сетку. Это было проблематично, поскольку в нем было много особых случаев. Например, край, который пересекает угол коробки, может быть разбит на три части, а не только на две.
Использование плоскости, чтобы разрезать сетку только на левую сетку и правую сетку, уменьшает количество особых случаев, потому что ребро находится либо на одной стороне плоскости, либо на другой, или оно пересекает плоскость и поэтому рубится ровно на две части.
Любая желаемая конфигурация разрезов может быть сделана простым разрезанием один раз, взятием одну из полученных сеток и разрезанием ее снова в другом месте и т. Д. В частности, в случае, который вы описываете в этом разделе, круг может быть вырезан из сферы, отрезав одну половину сферы, сместив плоскость на небольшую величину и обрезав другую половину, оставив только тонкую полосу. (Вы не можете сократить сетку до буквально никакой глубины с помощью кода, который я написал, но вы можете сократить сетку до того, что вы установили в качестве порога равенства с плавающей точкой. Я думаю, что я произвольно выбрал 0,001 в своем коде.)
Используя подобную логику, любой желаемый угол плоскости резания может быть достигнут с использованием фиксированной плоскости; вам просто нужно преобразовать сетку, чтобы повернуть ее относительно фиксированной плоскости резки, а затем преобразовать результат обратно. (Для моей игры мне потребовались только разрезы, перпендикулярные плоскости XY, поэтому для простоты я позволяю установить только значение Z разреза и предположить, что разрез находится в этом месте Z.)
Хорошо, теперь, когда мы упростили задачу, алгоритм не так уж и плох:
Исходное условие: у вас есть плоскость резания. У вас есть набор исходных треугольников. У вас есть два набора назначения из полигонов (не треугольников; квадраты могут быть получены путем разрезания треугольника). Два набора назначения называются Левый и Правый.
Процесс: итерация по трем точкам треугольника. Подсчитайте количество точек, которые меньше, чем плоскость резания. Я буду называть те, которые меньше, чем плоскость резки слева, и те, которые больше, чем плоскость резки справа. Есть только несколько случаев:
- Все точки треугольника находятся слева: поместите треугольник в набор слева
- Все точки справа: поместите треугольник в правильное множество
- Одна точка слева, другие справа: если вы разрежете треугольник по двум краям, и вы держите одну из точек, вы в конечном итоге удерживаете меньший треугольник. Поместите треугольник в левое множество, составленное из левой точки, и двух точек, где ребра пересекают плоскость. Поместите квад в Правильный набор (см. Следующий случай).
Две точки слева, одна точка справа. Если вы держите край треугольника и обрезаете его по двум другим краям, у вас остается трапеция. Поместите четырехугольник в левую сетку, состоящую из двух точек в вашей руке, плюс две точки, которые пересекают разрез. Поместите треугольник в правильный набор (зеркальное отображение случая выше).
Когда закончите, превратите четырехугольники в треугольники, добавив ссылку на самую короткую часть.
Вот и все. Это основной алгоритм. Фактический код обрабатывает еще несколько случаев, например, что, если ребро точно равно разрезу, что, если треугольник точно по краю, не добавлять вырожденные многоугольники (например, точку без тела) и т. Д.
Разное. вопросы (все рассмотрено в связанном коде):
Не переусердствуйте в математике для LERP'а в месте, где край пересекает плоскость резания.Для этого не требуется полная линейная интерполяция, на самом деле это всего лишь Highschool Algebra II: повышение по пробегу, умноженное на соотношение
. Выгодно кэшировать сгенерированные (с LERP) точкитак, чтобы треугольники, которые совместно использовали вершины в неразрезанной сетке, имели общие новые вершины в разрезанной сетке.
Если вы собираетесь сохранить совместное использование вершин и используете буферы индекса треугольника,Вы, к сожалению, еще не знаете индекс, когда вы впервые генерируете фигуры для вставки в наборы Left и Right.Я использую класс "ВозможноВертекс" для представления номера индекса будущего треугольника.
Если вы собираетесь отображать сетку, порядок намотки имеет значение.Тщательное размышление о том, как вы его кодируете, может гарантировать, что получающиеся полигоны будут использовать тот же порядок намотки, что и треугольники, из которых они получены.Это становится особенно сложно при триангуляции четырехугольников.Я не могу вспомнить детали, но все это обрабатывается в связанном коде.
Для моей игры я хотел сделать плоскую ленту, соединяющую две разрезанные сетки.Вот почему splitMeshZ дает 3 сетки, а не только две.Вы можете использовать среднюю сетку или просто игнорировать ее.