¿Cómo puedo realizar un triángulo dentro de la prueba en mallas poligonales?

10

ingrese la descripción de la imagen aquí Tengo 3 vértices (V1, V2, V3)seleccionados al azar en una malla triangular regular. Para estos 3 vértices, he calculado la distancia geodésica y el camino (usando Dijkstra) entre ellos y he formado una superficie en forma de triángulo como en la figura anterior.

Ahora, tengo los vértices que se encuentran en cada ruta y puedo calcular distancias geodésicas desde un vértice dado.

Lo que quiero hacer es obtener los vértices o triángulos que se encuentran en un área triangular. ¿Cómo puedo hacer esto?

mesh triangulation mkocabas
fuente
2
Suponiendo que ese enfoque barcéntrico haga lo que creo que haría, sería bastante lento con conjuntos grandes. Imagine un conjunto de 9 millones de vértices con solo 9 vértices en el conjunto deseado. ¿Por qué iterar todo el conjunto cuando v1, v2 y v3 le brindan toda la información que necesita? La respuesta de relleno de inundación sería la solución flexible más rápida. Aunque no es flexible, si puede asumir que tiene líneas como las que tiene ahora en la geometría, entonces la línea de exploración sería el enfoque más rápido.
Andrew Wilson
Tienes toda la razón sobre los problemas de rendimiento. Me gustaría utilizar este enfoque en mallas grandes, por lo que lo que estoy buscando es un método eficiente. En realidad, no estoy familiarizado con los algoritmos de llenado por inundación ni de escaneo, los echaré un vistazo. Gracias.
mkocabas
3
Un relleno de inundación con un gráfico comenzaría en un nodo, visitaría cada nodo vecino si se cumple la condición límite y no se visita, márquelo como visitado y repita (recursión). Alteración: marque cada nodo en la ruta como visitado y comience desde un nodo dentro del conjunto. Luego, simplemente use el control de visitas como condición de límite.
Andrew Wilson
Gracias por la explicación detallada. Considero que el llenado por inundación es algo más razonable, pero quiero implementar tanto el llenado por inundación como la línea de escaneo, y luego comparar el rendimiento.
mkocabas

Respuestas:

4

Existe un método alternativo que se basa en el llenado de inundaciones. Primero organice sus datos de borde en un bucle donde los bordes están formando un bucle en sentido antihorario. Luego comience en un punto arbitrario en el bucle y elija los bordes que unen ese punto. Use el borde del límite de salida y crúcelo con el otro borde de salida, si apunta en la dirección de la cara normal, entonces se debe incluir un borde, si no lo descarta. Desde este borde, continúe hasta llegar a un borde límite, en cuyo punto termina el relleno. Continúe en un vértice de borde límite aún por visitar.

joojaa
fuente
No estoy familiarizado con el algoritmo de llenado de inundaciones. Tu explicación me parece un poco complicada. ¿Podría por favor proporcionar una referencia decente para mirar? Gracias.
mkocabas
Obtuve la solución leyendo algunos. Gracias.
mkocabas
3

Ya he comentado sobre el uso del relleno de inundación y cómo sería mejor ya que es más flexible, pero otra posible solución es scanline. (Digo posible porque hace muchos supuestos sobre su geometría, pero para el conjunto particular que se muestra y muchos similares funcionaría).

Para su ejemplo con 3 puntos: Encuentre el vértice de intersección del segmento v1, v2 y la línea en la que se encuentra v3. (El vértice en la esquina superior izquierda de v2) Llamaremos a este vértice v4.

For every vertex pair a,b down v1,v4 and v1,v3 
    For every vertex from a to b
        Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
    For every vertex from a to b
        Mark as in the set

ingrese la descripción de la imagen aquí

Se llama scanline porque (en la imagen de arriba) vas por las líneas rojas y verdes simultáneamente y luego las líneas rojas y azules simultáneamente escanean las líneas a medida que avanzas.

Esta solución sería muy rápida si hay un patrón de índice, que suele ser el caso. De lo contrario, se necesitaría un cálculo para determinar qué vértice vecino se encuentra en la línea.

Lo curioso es el scanline, las pruebas barcéntricas (en el cuadro delimitador de triángulos) y el relleno de inundación son todas formas de dibujar triángulos en renderizado 3D.

Andrew Wilson
fuente
2

Creo que puede calcular algunas coordenadas barcéntricas unidas a la superficie para cada punto de la superficie y luego usarlas para verificar el interior o el exterior del triángulo.

No tengo un algoritmo exacto a mano, pero encontré el siguiente documento que parece manejar exactamente este tipo de coordenadas.

Coordenadas baricéntricas en superficies

Dragonseel
fuente
Gracias por la respuesta y el documento de referencia. Intentaré implementar el método propuesto.
mkocabas