Создать 2D многоугольник поперечного сечения из 3D сетки

Question

Я пишу игру, в которой для рисования сцены используются 3D-модели (ортогональная проекция сверху вниз), но физический движок 2D для вычисления реакции на столкновения и т. Д. У меня есть несколько 3D-ресурсов, для которых я хотел бы иметь возможность автоматически генерировать хитбокс, "разрезая" трехмерную сетку с плоскостью XY и создавая многоугольник из результирующих ребер.

Google подводит меня к этому (и не так много полезного материала по SO). Предложения?

Сетки, с которыми я имею дело, будут упрощенными версиями отображаемых моделей, которые связаны, замкнуты, не выпуклы и имеют нулевой род.

Answer 1

Поскольку ваши сетки не являются выпуклыми, результирующее поперечное сечение может быть отсоединено, поэтому фактически состоит из нескольких полигонов. Это означает, что каждый треугольник должен быть проверен, поэтому вам понадобится как минимум O(n) операций для 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 поддерживает постоянные удаления (например, хэш-набор).

Как и во всех геометрических алгоритмах, дьявол кроется в деталях. Тщательно продумайте, например, случаи, когда вершина треугольника находится точно на плоскости.

Answer 2

Вы можете сделать это с помощью abit геометрии, найдя все многоугольники, которые пересекаются с плоскостью, а затем найдя точный отрезок пересечения. Эти сегменты - линии искомого 2D-многоугольника.