Generar polígono de sección transversal 2D a partir de malla 3D

Question

Estoy escribiendo un juego que utiliza modelos 3D para dibujar una escena (proyección ortográfica descendente), pero un motor de física 2D para calcular la respuesta a colisiones, etc. Tengo un pocos recursos 3D para los que me gustaría poder generar automáticamente un hitbox "rebanando" la malla 3D con el plano XY y creando un polígono a partir de los bordes resultantes.

Google me está fallando en esto (y tampoco mucho material útil en SO). Sugerencias?

Las mallas con las que estoy tratando serán versiones simplificadas de los modelos mostrados, que están conectados, cerrados, no convexos y no tienen género.

Answer 1

Dado que sus mallas no son convexas, la sección transversal resultante puede desconectarse, por lo que en realidad consta de múltiples polígonos. Esto significa que se debe verificar cada triángulo, por lo que necesitará al menos O (n) operaciones para n triángulos.

Aquí hay una manera de hacerlo:

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 

Esto ejecutará en O (n) para n triángulos, siempre que sus triángulos tienen punteros a sus tres vecinos, y que T apoya el traslado constante de tiempo (por ejemplo, un conjunto de hash).

Como con todos los algoritmos geométricos, el diablo está en los detalles. Piense con cuidado en los casos en que el vértice de un triángulo está exactamente en el plano, por ejemplo.

Answer 2

Puede hacer esto con un poco de geometría al encontrar todos los polígonos que se cruzan con el plano y luego encontrar el segmento exacto de la intersección. estos segmentos son las líneas del polígono 2D que estás buscando.