Создайте двумерный многоугольник из 3D-сетки

Question

Я пишу игру, которая использует 3D-модели для рисования сцены (сверху-вниз орфографической проекции), но 2D-физический движок для расчета реакции на столкновений и т. Д. У меня есть несколько 3D-активов, для которых я хотел бы иметь возможность автоматически генерировать hitbox путем «срезания» 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 (п) для п треугольников, при условии, что ваши треугольники имеют указатели на свои трех сосед, и что T поддерживает постоянная время абсорбции (например, хэш-набор).

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

Answer 2

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