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

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.Generar polígono de sección transversal 2D a partir de malla 3D

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.

Fuente

2010-05-09 nornagon

Considerando su descripción, ¿podría también ser aceptable proyectar la malla 3D en un plano 2D? La parte de proyección es fácil y reduce la pregunta a "crear un polígono a partir de un grupo de triángulos superpuestos", que puede ser más fácil de resolver, especialmente si su proyección es convexa. – Thomas

Quizás nos puedas decir más sobre tu malla. ¿Es convexo? ¿Está conectado? ¿Está cerrado? ¿Tiene cero género? ¿Cómo se representa en la memoria? – Thomas

Las mallas no son convexas, pero se conectarán y cerrarán, y no tendrán género. – nornagon

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.

Fuente

2010-05-09 11:46:09 Thomas

Gracias, ahora solo necesito pensar un poco acerca de cómo determinar qué triángulo es vecino qué otro triángulo en qué borde ... – nornagon

Es por eso que le pregunté cómo se representa su malla en la memoria. Podría preprocesar la malla, unir los bordes si comparten dos vértices. – Thomas

También puede recorrer todos los triángulos primero, generar los segmentos de línea y mantener los punteros en los triángulos originales. Luego, recorra todos los segmentos de línea y conéctelos. Eso le ahorrará la fase de preprocesamiento, pero podría ser más lento si lo hace muchas veces. – Thomas

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.

Fuente

2010-05-09 11:40:24 shoosh

¿Cómo ordeno los segmentos? – nornagon

segmentos que son adyacentes se originan a partir de dos triángulos que comparten el mismo borde. – shoosh

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

Respuesta

Cuestiones relacionadas