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

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

Google терпит неудачу на этом (и не очень полезный материал на SO тоже). Предложения?

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

Ответ 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 поддерживает удаление посто нного времени (например, хэш-набор).

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

Ответ 2

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