Quad-edge structure implémentation

Bonjour.

J'implémente pour la première fois une structure type quad-edge. C'est pour de l'intelligence artificielle. Je vise une implémentation respectant l'interface conventionnelle (Next, Rot...), tout en étant efficace (recherche des adjacences en temps constant) et souple (ajout/suppression de vertex, flip edge...).

Je n'ai jamais eu une implémentation des quad-edge sous les yeux. Je me pose donc des questions sur la nature des données stockées.

J'ai en tête d'implémenter 2 graphes A et B (duaux). Chaque sommet d'un graphe aura des références vers ses voisins directs en ordre CCW. Chaque sommet d'un graphe aura des références vers les sommets du polygone correspondant dans l'autre graphe, toujours en CCW.

Voilà, il semble que par dessus ça je peux implémenter efficacement l'interface quad-edge. Mais est-ce la façon "conventionnelle" de procéder ?

Bonjour,

Citation:

---

Envoyé par FlashLogic

Voilà, il semble que par dessus ça je peux implémenter efficacement l'interface quad-edge. Mais est-ce la façon "conventionnelle" de procéder ?

---

Ça me parait étrange de faire pointer un vertex vers des faces. Il n'est pas plus judicieux de faire pointer un edge vers une face?

Peut-être peux tu t'inspirer des structures présentes dans CGAL (Halfedge Data Structures) et JTS (com.vividsolutions.jts.triangulate.quadedge.QuadEdge)?

Ah oui excellent lien merci !

Un lien intéressant où ils expliquent une implémentation possible:

http://www.cs.cmu.edu/afs/andrew/scs.../quadedge.html

Apparemment ils ne stockent qu'un fragment des données, le reste se déduisant logiquement:

"Internally, our implementation stores only four essential pieces of information with each edge (origin vertex, left face, Onext, and quadedge index) and the rest of the adjacency operators (Dest, Right, Lnext, Rprev, Dnext, ...) are derived using Sym and Rot."

Je note aussi la phrase suivante:

"Duals are also extremely useful for Voronoi diagrams and Delaunay triangulation, but that's another course (computational geometry)."

Je me demande donc si pour de l'IA, le mieux est de considérer une structure de graphes duaux ou une structure quad-edge. Sachant que les 2 sont apparemment équivalentes... peut-être devrais-essayer d'implémenter une structure polyvalente ?

Citation:

---

Envoyé par FlashLogic

"Internally, our implementation stores only four essential pieces of information with each edge (origin vertex, left face, Onext, and quadedge index) and the rest of the adjacency operators (Dest, Right, Lnext, Rprev, Dnext, ...) are derived using Sym and Rot."

---

Oui, une partie des opérateurs peut être calculé. Si tu as uniquement le vertex source et le edge opposé, tu calcules le vertex target comme étant la source du edge opposé.

Citation:

---

Envoyé par FlashLogic

"Duals are also extremely useful for Voronoi diagrams and Delaunay triangulation, but that's another course (computational geometry)."

---

Ton dual peut être implicite non?

Citation:

---

Envoyé par FlashLogic

Je me demande donc si pour de l'IA, le mieux est de considérer une structure de graphes duaux ou une structure quad-edge. Sachant que les 2 sont apparemment équivalentes... peut-être devrais-essayer d'implémenter une structure polyvalente ?

---

Tout dépend de ce que tu veux faire en IA avec cette structure. Après, chercher une structure générique me semble voué à l'échec (c'est un peu comme chercher à faire une classe Arbre qui réponde de manière optimale à tous les besoins).

Citation:

---

Envoyé par FlashLogic

Je me demande donc si pour de l'IA, le mieux est de considérer une structure de graphes duaux ou une structure quad-edge. Sachant que les 2 sont apparemment équivalentes... peut-être devrais-essayer d'implémenter une structure polyvalente ?

---

La structure QuadEdge est un moyen "assez simple" à la fois pour naviguer dans un graphe dual et pour modifier ce graphe dual. Cette structure n'est optimale pour aucun des deux cas pris indépendamment, mais elle offre un bon compromis.

Elle a effectivement tout son intérêt dans l'implémentation des algos de triangulation, car on y alterne les étapes de navigation (find) et de modification (make/slice) aussi bien sur les faces que les edges.

Je veux savoir implémenter de A à Z un pathfinding sur structure planaire polygonale. Notamment la méthode décrite dans la thèse de Douglas Jon Demyen:

http://citeseerx.ist.psu.edu/viewdoc...0.1.1.130.4581

Donc passer par la triangulation itérative de Delauney sous contrainte.

Je vais prendre le temps qu"il faut et je compte passer par une bonne compréhension des bases, donc de la structure de données.

Je vais implémenter les algos sur les 2 structures (Quad-edge et graphe/dual) pour les comparer. Même si je ne me fais pas d'illusion, le quad-edge sortira vraisemblablement vainqueur, mais ça me permettra de bien comprendre les différences.

Citation:

---

Envoyé par FlashLogic

Je vais implémenter les algos sur les 2 structures (Quad-edge et graphe/dual) pour les comparer. Même si je ne me fais pas d'illusion, le quad-edge sortira vraisemblablement vainqueur, mais ça me permettra de bien comprendre les différences.

---

L'utilisation des fonctions du quadedge (rot/sym, slice/makenew) n'est pas vraiment intuitive. Mais rien n'empêche d'utiliser le quadedge comme structure de données bas niveau, et de créer au dessus une sur-couche pour manipuler des sommets, des arcs et des faces. ;)

Citation:

---

Envoyé par FlashLogic

Je veux savoir implémenter de A à Z un pathfinding sur structure planaire polygonale.

---

Pour tes comparaisons, j'ai du mal à voir sur quoi tu vas te baser : La triangulation et le calcul du graphe dual de voisinage de surface peuvent-être vu comme des étapes de préparation (loading...)

Après, le calcul de chemin sera utilisé une foultitude de fois :
- Trouver le triangle de départ et d'arrivé
- Calculer un plus court chemin dans le graphe de voisinage des surfaces
- En déduire le chemin résultant

Du coup, j'aurais presque tendance à dire : Il faut privilégier les temps d'accès sur le graphe de voisinage des surfaces (notamment les arcs sortant, i.e. la récupération des faces adjacentes) et la recherche géométrique d'un triangle (indexe spatial type QuadTree ou Rtree sur les boites des triangles). Que la triangulation soit lente : Qu'importe, elle n'est appelée qu'une fois.

En d'autres termes, avant de comparer, demande toi si tu veux :
- Un algorithme performant pour une triangulation et un plus court chemin
- Un algorithme performant pour une triangulation et 1000 plus court chemin

PS :
- Bon courage pour la triangulation de Delaunay contrainte!
- Le conseil de pseudocode est précieux (les fonctions d'un QuadEdgeBuilder qui assurent la création d'un arc et de son opposé s'il n'existe pas, d'une face à partir d'une liste d'arc, etc. sont grandement pratiques ;))

Je vais déjà comparer la confort de manipulation, car comme dit plus haut, quad-edge n'est pas vraiment intuitif.

Je vais avoir besoin aussi d'une triangulation rapide (ajout/suppression d'arête contrainte) car j'espère pouvoir mettre à jour rapidement la triangulation. Au final du final j'aimerai "plaquer" et mettre à jour un navmesh sur un monde Box2D, et prendre en compte aussi bien les objets statiques que dynamiques.

Note: la triangulation itérative contrainte n'est pas si compliqué que cela:

http://citeseerx.ist.psu.edu/viewdoc...10.1.1.14.6477

J'ai commencé une implémentation des graphes duaux (stockage des données, primitive rectangle, méthodes polygon-subdiv et flip-edge). Ca marche bien et c'est élégant ; par contre les méthodes sont longues à implémenter et le manque de l'objet edge se fait sentir. Rajouter une class Edge alourdirait encore d'un cran l'implémentation des méthodes... Je verrai plus tard si je continue cette librairie.

Là où j'ai des questions, c'est que j'ai aussi commencé une implémentation du quad-edge. J'ai pris les conventions suivantes:

http://www.developpez.net/forums/att...1&d=1383216136

J'ai 4 classes Vertex, Edge, Face et Mesh.

Ma classe Edge stocke explicitement par référence:
- originVertex
- oppositeEdge
- nextLeftEdge
- leftFace

et déduit le reste à la demande:
- destinationVertex = oppositeEdge.originVertex
- prevLeftEdge = nextLeftEdge.nextLeftEdge
- nextRightEdge = oppositeEdge.nextLeftEdge.nextLeftEdge.oppositeEdge
- prevRightEdge = oppositeEdge.nextLeftEdge.oppositeEdge
- rotLeftEdge = nextLeftEdge.nextLeftEdge.oppositeEdge
- rotRightEdge = oppositeEdge.nextLeftEdge
- rightFace = oppositeEdge.leftFace

Jusqu'ici tout va bien. Le problème arrive quand je veux modéliser ma 1ère primitive, soit un petit graphe planaire sous forme de rectangle:

TL...TR
+---+
|..../|
|.../.|
|../..|
|./...|
|/....|
+---+
BL...BR

Le système n'est alors pas fiable car certains edges (ceux du périmètre) n'ont pas 2 polygons, et ça fragilise tout l'édifice (je me retrouve à mettre des références null un peu partout). Logiquement parlant, le système n'est pas clos par application des opérateurs et je n'aime pas ça.

C'est quoi alors la meilleure approche ?

Citation:

---

Envoyé par FlashLogic

C'est quoi alors la meilleure approche ?

---

J'aime bien la notion d'infinite face dans CGAL.

EDIT : Il est de toute façon intéressant d'indexer les edge de la frontière pour la triangulation incrémentale (si un vertex n'est pas dans un triangle, tu vas parcourir le contour pour voir à droite de quels edge il se trouve)

Je n'aime pas trop le concept de face infinie.

Après avoir retourné le problème dans tous les sens, je vais plutôt me considérer sur une sphère, Du coup ma primitive ressemblera à ça:

http://www.developpez.net/forums/att...1&d=1383282338

J'ai mis en rouge la zone utile de travail.

Les gros avantages c'est que ça me permet de sauver ma convention de polygon à 3 edges et d'avoir un système complètement clos par application des opérateurs. Au final ainsi je reste sur une classe Edge qui ne stocke que 4 données.

Hum en fait il y a une primitive bien plus simple :mrgreen:

http://www.developpez.net/forums/att...1&d=1383291018

L'implémentation est en bonne voie :)

Vous pouvez faire joujou avec un proto sur mon blog:

http://totologic.blogspot.com/2013/1...-delaunay.html

J'ai définitivement enterré l'implémentation sous forme de graphe dual pour me concentrer sur la structure quad-edge qui malgré son aspect déroutant à première vue, se révèle en fait plutôt aisée à manipuler.

Vu le manque de ressource sur le net sur ce sujet, j'ai écrit un premier article sur l'implémentation concrète des quad-edge:

http://totologic.blogspot.com/2013/1...explained.html

D'autres suivront.

Finalement, quad-edge, triangulation dynamique de delaunay constrainte, pathfinding.... j'ai obtenu d'excellents résultats que je ne peux m'empêcher de vous faire partager :lol:

Quelques videos de démos:

https://www.youtube.com/watch?v=PYaur2VJ2MY

https://www.youtube.com/watch?v=L6kXx5lUT9g

Ce big déterrage de post o.O" je m'en excuse d'avance.

J'ai lu l'article de FlashLogic, je l'ai à peu près compris, mais je me demandais une chose : la structure QuadEdge est-elle tellement plus performante que la structure HalfEdge ? J'implémente moi même en ce moment une structure HalfEdge, optimisée de telle sorte qu'il n'y ait (presque !) aucune redondance d'information, et surtout, un accès constant aux triangles adjacents. C'est, en somme, ce que fait une structure QuadEdge. Alors, QuadEdge ou HalfEdge ?

Cordialement,