Erstellen von Dreiecksnachbarschaftsdaten

Wie genau kann man bei einer Liste von Dreiecksindizes diese in eine Liste von Indizes mit Adjazenz für einen Geometrie-Shader konvertieren?

Beachten Sie, dass wir hier ausschließlich über Indizes sprechen - Scheitelpunkte sind vorhanden, aber wir werden uns ausschließlich auf Indizes konzentrieren, da wir sie verwenden können, um doppelte Scheitelpunkte abzugleichen, ohne auf Gleitkomma-Vergleiche und Epsilons eingehen zu müssen - das hat diese Arbeit schon erledigt.

Ich weiß, dass für jedes gegebene Dreieck in der Liste die Indizes {0, 1}, {1, 2} und {2, 0} (oder {n, n + 1}, {n + 1, n + 2}, { n + 2, n}, wenn Sie es vorziehen) davon bilden seine Kanten; Die Indexliste ist wohlgeformt und berücksichtigt die Wicklungsreihenfolge korrekt.

Ich weiß, dass wir für jede gegebene Kante die gesamte Liste nach einem anderen Dreieck durchsuchen können, das zwei dieser Indizes verwendet, und der dritte Index dieses Dreiecks ist derjenige, der zum Vervollständigen des benachbarten Dreiecks für diese Kante verwendet wird.

Ich weiß, dass in der Adjazenzliste jedes ursprüngliche Dreieck durch 6 Indizes dargestellt wird, die ursprünglichen Indizes gehen in die Slots 0, 2, 4; Die neuen Indizes zum Vervollständigen der Nachbarschaft befinden sich in den Slots 1, 3, 5. Der zu vervollständigende Index für die Kante {0, 1} geht in den Slot 1, der Index zum Vervollständigen für die Kante {1, 2} in den Slot 3, den Index Zum Vervollständigen für Kante {2, 1} wird in Steckplatz 5 verschoben.

Was habe ich versucht?

Ich habe versucht, es brutal zu erzwingen, und ja, das wird funktionieren, aber ich bin auf der Suche nach einem eleganteren Ansatz.

Ich habe Eric Lengyels Kantenlistenersteller ausprobiert, aber (1) er scheint die ursprüngliche Dreiecksreihenfolge nicht zu respektieren, (2) er scheint die Wicklungsreihenfolge nicht zu respektieren, (3) es ist so klar wie Schlamm, wohin er gehen soll Als nächstes, nachdem Sie die Kantenliste erstellt haben und (4) ich den Verdacht habe, dass Beispielcode so offensichtliche Fehler wie "triangleIndex" oder "faceIndex" aufweist - hat der Autor den Code überhaupt kompiliert, egal, um ihn auszuführen es überprüfen?

Also - irgendwelche Vorschläge oder Hinweise von hier an?

Ich würde versuchen, eine Hash-Tabelle dafür zu verwenden (zum Beispiel, std::unordered_mapwenn Sie in C ++ sind). Erstellen Sie eine Hash-Tabelle, die von einer halben Kante (in der Reihenfolge als Indexpaar ausgedrückt) dem dritten Index des Dreiecks zugeordnet wird, zu dem die halbe Kante gehört.

Dies kann durch einfaches Durchlaufen der Dreiecksliste und Hinzufügen der drei Halbkanten jedes Dreiecks zur Hash-Tabelle erstellt werden. Wenn Ihre anfängliche Indexliste ein Paar benachbarter Dreiecke (0, 1, 2, 2, 1, 3) hätte, würden Sie eine Hash-Tabelle erhalten, die Folgendes enthält:

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

Beachten Sie, dass die Kanten (1, 2) und (2, 1) beide in der Tabelle erscheinen, die die beiden Seiten der Kante darstellen und auf den dritten Scheitelpunkt jedes der beiden Dreiecke zeigen.

Um die Adjazenzdaten zu erstellen, müssen Sie lediglich die Dreiecksliste erneut durchlaufen und die Kanten jedes Dreiecks mit der entgegengesetzten Wicklung abfragen. Wenn Sie also das Dreieck (0, 1, 2) verarbeiten, fragen Sie die Kanten (1, 0), (2, 1) und (0, 2) ab. Dies findet den entgegengesetzten Scheitelpunkt jeder Kante, falls vorhanden.

Schauen Sie sich die Datenstruktur mit der halben Kante an .

Die Idee ist ungefähr, dass Sie eine Liste von halben Kanten speichern , z. B. die Hälfte einer bestimmten Kante, die an einer bestimmten Fläche angebracht ist. Diese Struktur speichert dann auch Informationen über die entsprechende Halbkante für die angrenzende Fläche.

Die Datenstruktur macht Abfragen zu Konnektivität, Nachbarschaft usw. sehr effizient. Es gibt Algorithmen, um die Daten effizient zu generieren, jedoch nicht unbedingt "Spiellaufzeit" effizient (wahrscheinlich möchten Sie dies offline in Ihrer Asset-Pipeline tun).

Siehe auch diese Blog-Beiträge . Ich glaube, die Struktur und die Algorithmen befinden sich auch in der Echtzeit-Kollisionserkennung, aber ich erinnere mich nicht sicher und habe keine Kopie im Büro.