Генерируйте 2D полигон поперечного сечения от 3D сетки
Я пишу игру, которая использует 3D модели для рисования сцены (нисходящая ортогональная проекция), но 2D механизм физики для вычисления ответа на коллизии, и т.д. У меня есть несколько 3D активов, для которых я хотел бы смочь автоматически генерировать hitbox путем 'разрезания' 3D сетки с плоскостью X-Y и создания полигона из результирующих краев.
Google приводит меня к сбою на этом (и не много полезного материала по ТАК любому). Предложения?
Сетки, с которыми я имею дело, будут упрощенными версиями отображенных моделей, которые соединены, закрыты, невыпуклы и иметь нулевой род.
2 ответа
Поскольку ваши сетки не являются выпуклыми, полученное сечение может быть несвязным, то есть фактически состоять из нескольких многоугольников. Это означает, что каждый треугольник должен быть проверен, поэтому для n треугольников вам потребуется как минимум O(n) операций.
Вот один из способов сделать это:
T <- the set of all triangles
P <- {}
while T is not empty:
t <- some element from T
remove t from T
if t intersects the plane:
l <- the line segment that is the intersection between t and the plane
p <- [l]
s <- l.start
while l.end is not s:
t <- the triangle neighbouring t on the edge that generated l.end
remove t from T
l <- the line segment that is the intersection between t and the plane
append l to p
add p to P
Это будет выполняться за O(n) времени для n треугольников, при условии, что ваши треугольники имеют указатели на три своих соседа, и что T поддерживает удаление в постоянном времени (например, хэш-набор).
Как и во всех геометрических алгоритмах, дьявол кроется в деталях. Подумайте внимательно о случаях, когда вершина треугольника находится точно в плоскости, например.
Вы можете сделать это с помощью геометрии, найдя все многоугольники, которые пересекаются с плоскостью, а затем найти точный сегмент пересечения. эти сегменты являются линиями двумерного многоугольника, который вы ищете.