IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Quad-edge structure implémentation


Sujet :

Algorithmes et structures de données

  1. #1
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut 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 ?

  2. #2
    Membre éprouvé
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Points : 1 060
    Points
    1 060
    Par défaut
    Bonjour,

    Citation Envoyé par FlashLogic Voir le message
    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)?

  3. #3
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    Ah oui excellent lien merci !

  4. #4
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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 ?

  5. #5
    Membre éprouvé
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Points : 1 060
    Points
    1 060
    Par défaut
    Citation Envoyé par FlashLogic Voir le message
    "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 Voir le message
    "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 Voir le message
    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).

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par FlashLogic Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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.

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par FlashLogic Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Membre éprouvé
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Points : 1 060
    Points
    1 060
    Par défaut
    Citation Envoyé par FlashLogic Voir le message
    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 )

  10. #10
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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.

  11. #11
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    Note: la triangulation itérative contrainte n'est pas si compliqué que cela:

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

  12. #12
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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:



    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 ?
    Images attachées Images attachées  

  13. #13
    Membre éprouvé
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Points : 1 060
    Points
    1 060
    Par défaut
    Citation Envoyé par FlashLogic Voir le message
    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)

  14. #14
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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:



    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.
    Images attachées Images attachées  

  15. #15
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    Hum en fait il y a une primitive bien plus simple

    Images attachées Images attachées  

  16. #16
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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.

  17. #17
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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.

  18. #18
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Octobre 2010
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : Octobre 2010
    Messages : 90
    Points : 230
    Points
    230
    Par défaut
    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

    Quelques videos de démos:

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

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

  19. #19
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    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,
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

Discussions similaires

  1. Déclaration et implémentation tableau structuré avec mail outlook
    Par C'estPasMoi dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 22/05/2014, 12h47
  2. Implémentation en java de structures de données
    Par wafiwafi dans le forum Général Java
    Réponses: 15
    Dernier message: 05/04/2011, 16h42
  3. [Forth] Implémentation des structures dynamiques
    Par <Zer0> dans le forum Autres langages
    Réponses: 14
    Dernier message: 29/01/2009, 00h01
  4. Réponses: 2
    Dernier message: 08/11/2007, 12h13
  5. Réponses: 7
    Dernier message: 08/12/2005, 10h26

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo