Construindo dados de adjacência do triângulo

Dada uma lista de índices de triângulo, como exatamente se converte isso em uma lista de índices com adjacência para um sombreador de geometria?

Observe que estamos falando estritamente de índices aqui - os vértices estão presentes, mas vamos nos concentrar apenas nos índices, porque podemos usá-los para combinar vértices duplicados sem ter que entrar em comparações de ponto flutuante e epsilons - que o trabalho tem já foi feito.

Eu sei que, para qualquer triângulo da lista, os índices {0, 1}, {1, 2} e {2, 0} (ou {n, n + 1}, {n + 1, n + 2}, { n + 2, n} se você preferir) dele formar suas arestas; a lista de índices está bem formada e respeita a ordem dos enrolamentos corretamente.

Eu sei que, para qualquer aresta, podemos procurar na lista inteira outro triângulo que use dois desses índices, e o terceiro índice desse triângulo é o usado para completar o triângulo adjacente para essa aresta.

Eu sei que na lista de adjacências, cada triângulo original é representado por 6 índices, os índices originais vão para os slots 0, 2, 4; os novos índices para concluir a adjacência entram nos slots 1, 3, 5. O índice a ser preenchido para a borda {0, 1} entra no slot 1, o índice a ser preenchido na borda {1, 2} entra no slot 3, o índice para concluir a borda {2, 1} entra no slot 5.

O que eu tentei?

Eu tentei forçar brutalmente, e sim, isso funcionará, mas estou buscando uma abordagem mais elegante.

Eu tentei o construtor de listas de arestas de Eric Lengyel, mas (1) ele não parece respeitar a ordem do triângulo original, (2) não parece respeitar a ordem do enrolamento, (3) é tão claro quanto a lama para onde ir a seguir, depois de criar a lista de arestas, e (4) suspeitei de um código de exemplo que tenha erros óbvios como "triangleIndex" versus "faceIndex" - o autor até compilou o código, não importa executá-lo para verificar isso?

Então - alguma sugestão ou sugestão daqui em diante?

Eu tentaria usar uma tabela de hash para isso (por exemplo, std::unordered_mapse você estiver em C ++). Crie uma tabela de hash que mapeie de uma meia borda (expressa como um par de índices, em ordem) até o terceiro índice do triângulo ao qual a meia borda pertence.

Para criar isso, basta iterar sobre a lista de triângulos e adicionar três meias-arestas de cada triângulo à tabela de hash. Se sua lista de índice inicial tivesse um par de triângulos adjacentes (0, 1, 2, 2, 1, 3), você terminaria com uma tabela de hash contendo:

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

Observe que as arestas (1, 2) e (2, 1) aparecem na tabela, representando os dois lados da aresta e apontando para o terceiro vértice de cada um dos dois triângulos.

Em seguida, para criar os dados de adjacência, basta iterar a lista de triângulos novamente e consultar as arestas de cada triângulo com o enrolamento oposto. Portanto, ao processar o triângulo (0, 1, 2), você consultaria as arestas (1, 0), (2, 1) e (0, 2). Isso encontrará o vértice oposto de cada aresta, se existir.

Veja a estrutura de dados de meia borda .

A idéia é que você armazene uma lista de meias arestas , por exemplo, a metade de uma aresta específica anexada a uma face específica. Essa estrutura também armazena informações sobre a meia aresta correspondente para a face adjacente.

A estrutura de dados faz consultas sobre conectividade, adjacência e muito mais. Existem algoritmos para gerar os dados com eficiência, embora não necessariamente com "tempo de execução do jogo" eficientemente (você provavelmente desejará fazer isso offline no seu pipeline de ativos).

Veja também essas postagens no blog . Acredito que a estrutura e os algoritmos também estejam na detecção de colisão em tempo real, mas não me lembro com certeza e não tenho uma cópia no escritório.