Algoritmo de contorno 2D para malla 3D proyectada

Question

Dado: una malla 3D definida con un conjunto de vértices y triángulos que forman la malla con estos puntos.

Problema: Encuentre el contorno 2d de la malla proyectada arbitrariamente girada en un plano arbitrario.

La proyección es fácil. El desafío radica en encontrar el "casco" de los bordes proyectados del triángulo en el plano. Necesito ayuda con la entrada/punteros en la investigación de este algoritmo. Para simplificar, podemos suponer que los bordes 3D se proyectan directamente hacia abajo en el plano xy.

Answer 1

• de inicio con el punto más a la derecha (el punto con la mayor coordenada x)
• obtener todos los bordes de este punto
• Siga el filo con el ángulo más pequeño hasta el eje x positivo, y también añadir que a la solución prevista
• desde el punto alcanzado, seguir y añadir el filo con el ángulo más pequeño hasta el borde viniste
• Repita hasta que llegue al punto original

Answer 2

La técnica formas alfa mencionados en esta pregunta se ocupa de un conjunto general de los puntos en los que no se conocen las conexiones de vértices:

Is there an efficient algorithm to generate a 2D concave hull?

Sin embargo, puesto que ya conoce la información "cara", que puede ser preservado a través la proyección, probablemente no sea el mejor enfoque.

Un algoritmo de fuerza bruta podría ser factible, especialmente si se usan estructuras de clasificación espacial. por ejemplo, para cada faceta:

1. faceta del proyecto sobre el plano
2. Comprobar si faceta proyectada está completamente encerrado en la geometría existente, en caso afirmativo: hecho (sin necesidad de ampliar la silueta proyectada)
3. Si los puntos están fuera la geometría existente, hacer intersecciones triángulo-triángulo para determinar qué porciones caen fuera, construir un arbitrario n-gon (posiblemente cóncava) para llenar el espacio encuentra, entonces picar el n-gon en a triángulos

Otra idea, dependiendo de la fidelidad que requiera, solo tiene que disparar montón de rayos normales desde su plano de proyección a su geometría original. Crea un 2d hit/miss y usa eso para determinar tus extensiones.

Answer 3

¿Es simplemente una cuestión de proyectar los puntos xyz en puntos x'Y 'en el plano arbitrario y luego simplemente hacer un casco convexo en esas coordenadas?

Answer 4

Solo veo respuestas para soluciones convexas, así que aquí está el mío para no convexo. (Fue un poco confuso cuál era la intención.)

Tome todos los bordes de sus triángulos 2D y agrúpelos. Si dos bordes comparten ambos puntos finales, están en el mismo grupo. Todos los grupos, con solo un borde, son entonces parte del caparazón.

Finalmente puede combinar los bordes de la carcasa en un anillo, uniéndolos entre sí.

Answer 5

El contorno 2D de la proyección de malla es un subconjunto de la proyección de sus bordes.

Usando esta observación, se puede determinar el contorno 2D usando el siguiente método:

• la proyección de cada borde perteneciente a una sola cara es parte del contorno 2D,
• para otros bordes, determinar el vector normal de sus caras adyacentes
• calcula los productos puntos de esas normales con la normalidad del plano de proyección
• la proyección de este borde pertenece al esquema 2D si todos los signos de los productos dot no son iguales (lo que significa, una cara apunta hacia el plano de proyección, mientras que al menos otra no, que identifica el borde como parte del contorno).

Tenga en cuenta que este método informará todos los bordes que son ortogonales al plano de proyección, incluso aquellos que no son visibles desde el punto de vista del plano de proyección. Por ejemplo, con un toro, encontrará los contornos interior y exterior, incluso cuando el toro se gira de tal manera que su orificio interior no sea visible desde el punto de vista del plano de proyección. Para determinar qué bordes son visibles, necesitará algún tipo de prueba de visibilidad. Si el uso previsto es para la visualización del usuario, puede usar una memoria intermedia de profundidad calculada con una matriz de proyección ortogonal para representar la geometría desde el punto de vista del plano de proyección y hacer algunas pruebas z para determinar qué bordes son visibles desde el plano. Si necesita precisión, necesitará realizar una intersección de rayos/triángulos para determinar la visibilidad.

Answer 6

Solo para añadir: ¡Una manera muy intuitiva de encontrar los bordes en una proyección es la eliminación de caras! Cualquier borde entre una cara seleccionada y no eliminada debe ser un contorno. Si desea ocultar los bordes interiores, simplemente use el z-buffer. El sacrificio de caras traseras es simplemente el orden de los vértices de proyección y muy barato de calcular.