Construir datos de adyacencia de triángulos

Dada una lista de índices de triángulos, ¿cómo exactamente se puede convertir eso en una lista de índices con adyacencia para un sombreador de geometría?

Tenga en cuenta que aquí estamos hablando estrictamente de índices : los vértices están presentes, pero nos vamos a centrar únicamente en los índices, porque podemos usarlos para unir vértices duplicados sin tener que entrar en comparaciones de punto flotante y épsilones, ese trabajo tiene Ya ha sido hecho.

Sé que para cualquier triángulo dado en la lista, los índices {0, 1}, {1, 2} y {2, 0} (o {n, n + 1}, {n + 1, n + 2}, { n + 2, n} si lo prefieres) de él forman sus bordes; la lista de índice está bien formada y respeta el orden de bobinado correctamente.

Sé que para cualquier borde dado, podemos buscar en la lista completa otro triángulo que use dos de esos índices, y el tercer índice de ese triángulo es el que se debe usar para completar el triángulo adyacente para ese borde.

Sé que en la lista de adyacencia cada triángulo original está representado por 6 índices, los índices originales van en las ranuras 0, 2, 4; los nuevos índices para completar la adyacencia van a las ranuras 1, 3, 5. El índice a completar para el borde {0, 1} va a la ranura 1, el índice a completar para el borde {1, 2} va a la ranura 3, el índice completar para el borde {2, 1} entra en la ranura 5.

Que he probado

He intentado forzarlo, y sí, eso funcionará, pero busco un enfoque más elegante.

He probado el generador de listas de borde de Eric Lengyel, pero (1) no parece respetar el orden del triángulo original, (2) no parece respetar el orden de bobinado, (3) es tan claro como el barro a dónde ir después de que hayas creado la lista de bordes, y (4) tengo una sospecha de código de muestra que tiene errores evidentes tan obvios como "triangleIndex" versus "faceIndex" - el autor incluso compiló el código, no importa ejecutarlo verificarlo?

Entonces, ¿alguna sugerencia o sugerencia de aquí en adelante?

Intentaría usar una tabla hash para esto (por ejemplo, std::unordered_mapsi está en C ++). Construya una tabla hash que se asigne desde un medio borde (expresado como un par de índices, en orden) hasta el tercer índice del triángulo al que pertenece el medio borde.

Esto se puede construir simplemente iterando sobre la lista de triángulos y agregando los tres medios bordes de cada triángulo a la tabla hash. Si su lista de índice inicial tuviera un par de triángulos adyacentes (0, 1, 2, 2, 1, 3), terminaría con una tabla hash que contiene:

(0, 1) -> 2
(1, 2) -> 0
(2, 0) -> 1
(2, 1) -> 3
(1, 3) -> 2
(3, 2) -> 1

Tenga en cuenta que los bordes (1, 2) y (2, 1) aparecen en la tabla, representan los dos lados del borde y apuntan al tercer vértice de cada uno de los dos triángulos.

Luego, para construir los datos de adyacencia, todo lo que tiene que hacer es iterar sobre la lista de triángulos nuevamente y consultar los bordes de cada triángulo con el devanado opuesto. Entonces, al procesar el triángulo (0, 1, 2), consultaría los bordes (1, 0), (2, 1) y (0, 2). Esto encontrará el vértice opuesto de cada borde, si existe.

Mire la estructura de datos de medio borde .

La idea más o menos es que almacene una lista de medios bordes , por ejemplo, la mitad de un borde particular adjunto a una cara particular. Esta estructura también almacena información sobre el medio borde correspondiente para la cara contigua.

La estructura de datos hace que las consultas sobre conectividad, adyacencia, etc. sean muy eficientes. Hay algoritmos para generar los datos de manera eficiente, aunque no necesariamente el "tiempo de ejecución del juego" de manera eficiente (probablemente querrá hacerlo sin conexión en su canal de activos).

Vea también estas publicaciones de blog . Creo que la estructura y los algoritmos también se encuentran en la detección de colisiones en tiempo real, pero no recuerdo con certeza y no tengo una copia en la oficina.