math - Algoritmo de esquema 2D para malla 3D proyectada

geometry projection (6)

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

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 girada arbitrariamente en un plano arbitrario.

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

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

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

la proyección de cada borde que pertenece a una sola cara es parte del contorno 2D,
para otros bordes, determine el vector normal de sus caras adyacentes
Calcule los productos de puntos de esas normales con la normal del plano de proyección.
la proyección de este borde pertenece al contorno 2D si todos los signos de los productos de puntos no son iguales (lo que significa que una cara apunta hacia el plano de proyección mientras que al menos otra no lo hace, lo que identifica el borde como parte de la imagen). 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 interiores y exteriores, 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 ordenar 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 un búfer de profundidad computado con una matriz de proyección ortogonal para representar la geometría desde el punto de vista del plano de proyección y realizar algunas pruebas de z para determinar qué bordes son visibles desde el plano. Si necesita precisión, deberá realizar una intersección de rayos / triángulos para determinar la visibilidad.

La técnica de formas alfa mencionada en esta pregunta maneja un conjunto general de puntos donde las conexiones de vértices no se conocen:

¿Existe un algoritmo eficiente para generar un casco cóncavo 2D?

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

Un algoritmo de fuerza bruta puede ser factible, especialmente si se utilizan estructuras de clasificación espacial. Por ejemplo, para cada faceta:

Proyecto faceta sobre el plano.
Compruebe si la faceta proyectada está completamente encerrada por la geometría existente, en caso afirmativo: hecho (no es necesario expandir la silueta proyectada)
Si los puntos caen fuera de la geometría existente, haga intersecciones triángulo-triángulo para determinar qué partes caen afuera, construya un n-gon arbitrario (posiblemente cóncavo) para llenar el espacio faltante, luego corte el n-gon en triángulos

Otra idea, dependiendo de la fidelidad que requiera, es simplemente disparar un grupo de rayos normales desde su plano de proyección a su geometría original. Crea un 2d hit / miss y úsalo para determinar tus extensiones.

Solo para agregar: ¡Una forma muy intuitiva de encontrar bordes en una proyección es la eliminación de caras! Cualquier borde entre una cara seleccionada y no seleccionada debe ser un contorno. Si desea ocultar los bordes interiores, simplemente use el z-buffer. La selección de la cara posterior es simplemente el orden de vértice posterior a la proyección y es muy económico de calcular.

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

Toma todos los bordes de tus triángulos 2D y agrúpalos. Si dos bordes comparten ambos puntos finales, están en el mismo grupo. Todos los grupos, con un solo borde, forman parte del shell.

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

Comience con el punto más a la derecha (el punto con la mayor coordenada x)
Consigue todos los bordes de este punto.
Siga el borde con el ángulo más pequeño hacia el eje x positivo, y también agréguelo al conjunto de soluciones
Desde el punto alcanzado, siga y agregue el borde con el ángulo más pequeño al borde del que vino.
Repite hasta llegar al punto original.