Création de données d'adjacence de triangle

9

Étant donné une liste d'indices triangulaires, comment procéder exactement pour convertir cela en une liste d'indices avec adjacence pour un shader de géométrie?

Notez que nous parlons strictement d' indices ici - les sommets sont présents, mais nous allons nous concentrer uniquement sur les indices, car nous pouvons les utiliser pour faire correspondre les sommets en double sans avoir à entrer dans des comparaisons à virgule flottante et des epsilons - ce travail a déjà été fait.

Je sais que pour tout triangle donné de la liste, les indices {0, 1}, {1, 2} et {2, 0} (ou {n, n + 1}, {n + 1, n + 2}, { n + 2, n} si vous préférez) en forme ses bords; la liste d'index est bien formée et respecte correctement l'ordre de bobinage.

Je sais que pour tout bord donné, nous pouvons rechercher dans la liste entière un autre triangle qui utilise deux de ces indices, et le troisième indice de ce triangle est celui à utiliser pour compléter le triangle adjacent pour ce bord.

Je sais que dans la liste d'adjacence, chaque triangle d'origine est représenté par 6 indices, les indices d'origine vont dans les emplacements 0, 2, 4; les nouveaux indices pour compléter la contiguïté vont dans les emplacements 1, 3, 5. L'index à compléter pour le bord {0, 1} va dans l'emplacement 1, l'index à compléter pour le bord {1, 2} va dans l'emplacement 3, l'index à compléter pour le bord {2, 1} va dans l'emplacement 5.

Qu'est-ce que j'ai essayé?

J'ai essayé de le forcer brutalement, et oui, cela fonctionnera, mais je suis après une approche plus élégante.

J'ai essayé le générateur de liste de bord d'Eric Lengyel, mais (1) il ne semble pas respecter l'ordre des triangles d'origine, (2) il ne semble pas respecter l'ordre d'enroulement, (3) c'est aussi clair que la boue où aller ensuite après avoir construit la liste des bords, et (4) j'ai un soupçon d'exemple de code qui a des erreurs flagrantes évidentes comme "triangleIndex" contre "faceIndex" - l'auteur a-t-il même compilé le code, sans parler de l'exécuter le vérifier?

Alors - des suggestions ou des conseils à partir d'ici?

algorithm 3d-meshes Maximus Minimus
la source
Jimmy, j'ai édité les trucs sur les volumes d'ombre et changé le titre, car cela ne semblait pas pertinent et était potentiellement déroutant - la question est en fait juste de construire des données d'adjacence, même si votre but ultime est de les utiliser pour les volumes d'ombre.
Nathan Reed

Réponses:

11

J'essaierais d'utiliser une table de hachage pour cela (par exemple, std::unordered_mapsi vous êtes en C ++). Créez une table de hachage qui mappe à partir d'un demi-bord (exprimé comme une paire d'indices, dans l'ordre) vers le troisième index du triangle auquel le demi-bord appartient.

Cela peut être construit en itérant simplement sur la liste des triangles et en ajoutant les trois demi-bords de chaque triangle à la table de hachage. Si votre liste d'index initiale avait une paire de triangles adjacents (0, 1, 2, 2, 1, 3), vous vous retrouveriez avec une table de hachage contenant:

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

Notez que les arêtes (1, 2) et (2, 1) apparaissent toutes les deux dans le tableau, représentant les deux côtés de l'arête et pointant vers le troisième sommet de chacun des deux triangles.

Ensuite, pour construire les données d'adjacence, tout ce que vous avez à faire est de parcourir à nouveau la liste des triangles et d'interroger les bords de chaque triangle avec l'enroulement opposé. Ainsi, lors du traitement du triangle (0, 1, 2), vous interrogez les bords (1, 0), (2, 1) et (0, 2). Cela trouvera le sommet opposé de chaque arête, s'il existe.

Nathan Reed
la source
1
Cool, la recherche de bords avec l' ordre opposé était un élément clé des informations manquantes; travaille un champion; +1 et accepté.
Maximus Minimus
2

Regardez la structure de données à demi-bord .

L'idée est que vous stockez une liste de demi-bords , par exemple la moitié d'un bord particulier attaché à une face particulière. Cette structure stocke ensuite également des informations sur le demi-bord correspondant pour la face adjacente.

La structure de données rend les requêtes sur la connectivité, la contiguïté, etc. très efficaces. Il existe des algorithmes pour générer efficacement les données, mais pas nécessairement "l'exécution du jeu" efficacement (vous voudrez probablement le faire hors ligne dans votre pipeline d'actifs).

Voir également ces articles de blog . Je crois que la structure et les algorithmes sont également en détection de collision en temps réel, mais je ne m'en souviens pas avec certitude et je n'ai pas de copie au bureau.

Sean Middleditch
la source
-1, désolé, mais cela n'a donné aucune information que je n'avais pas déjà, et était orienté autour de l'utilisation sur le CPU plutôt que de construire une liste avec adjacence pour une utilisation dans un GS.
Maximus Minimus