+ Répondre à la discussion Actualité déjà publiée
  1. #1
    Membre averti

    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2011
    Messages
    82
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : mars 2011
    Messages : 82
    Points : 395
    Points
    395

    Par défaut Octree et code de Morton

    Bonjour,

    Voici un tutoriel pour apprendre les octrees et le code de Morton.

    Les octrees (arbres octaires) sont des structures de données utilisées dans les applications 3D pour accélérer une série d'opérations dans l'espace, comme la recherche des voisins d'un point ou la détection de collisions.

    Une primitive pour bon nombre de ces applications est la recherche dichotomique. Elle peut être accélérée en employant une représentation particulière des coordonnées, le code de Morton. Il peut également servir pour itérer rapidement sur les éléments de l'arbre.


    Voilà un tutoriel avec pas mal de bit bashing , quelques jolies images et un petit code source.

    N'hésitez pas à me laisser des retours.



    Tous les meilleurs cours et tutoriels pour apprendre la programmation des jeux
    Mes tutoriels avancés sur la triangulation par filet à surface et sur les octree - N'hésitez pas à consulter les tutoriels et FAQ 2D/3D/jeux.

  2. #2
    Membre expert
    Inscrit en
    mars 2005
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : mars 2005
    Messages : 1 036
    Points : 3 058
    Points
    3 058

    Par défaut

    Merci pour cet article vraiment très clair et bien écrit.

  3. #3
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut Merci

    Bonjour et merci pour ce travaille d'une très grande qualité.
    Je suis en cours d'implémentation de cet octree en java et ça marche super bien.
    J'arrive à construire des octrees contenant 1 million d'objets en 700 ms en moyenne !
    J'avoue ne pas avoir tout compris sur les opérations manipulant directement les bits.
    J'aurai encore quelques questions, est-ce possible de vous contacter par mail ?
    encore merci !

  4. #4
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2008
    Messages
    22 338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

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

    Informations forums :
    Inscription : mai 2008
    Messages : 22 338
    Points : 153 128
    Points
    153 128
    Billets dans le blog
    8

    Par défaut

    Autant poser vos questions sur le forum afin que :
    • plusieurs personnes puissent vous répondre (et ainsi, avoir plusieurs formulations des explications (ça peut toujours aider)) ;
    • plusieurs personnes puissent avoir les détails et non pas que vous.
    Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi

    Ma page sur DVP
    Mon Portfolio

    Qui connaît l'erreur, connaît la solution.

  5. #5
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Tout à fait vous avez entièrement raison, veuillez pardonner mon erreur

  6. #6
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2008
    Messages
    22 338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

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

    Informations forums :
    Inscription : mai 2008
    Messages : 22 338
    Points : 153 128
    Points
    153 128
    Billets dans le blog
    8

    Par défaut

    Du coup, quelles sont les questions ?
    Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi

    Ma page sur DVP
    Mon Portfolio

    Qui connaît l'erreur, connaît la solution.

  7. #7
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Comment retrouver le code de morton d'un cube en connaissant son index (son numéro d'enfant 0 à 7) et son exposant ?
    je pense que c'est possible puisqu'on fait déjà l'inverse :
    index = (mortonCode >> 3*exposant) & 7
    Merci

  8. #8
    Membre averti

    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2011
    Messages
    82
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : mars 2011
    Messages : 82
    Points : 395
    Points
    395

    Par défaut

    Bonjour,

    Je suis content que cet article vous soit utile.
    Vous pouvez posez vos question, ici, ça peut être utile pour tout le monde.

    Effectivement je n'ai pas présenté explicitement l'opération inverse, la voici:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    mortonCode = (index << 3*exposant) | (indexPere << 3*exposantPere) | (indexGrandpere << 3*exposantGrandpere)...
    Une petite boucle suffit à le calculer, sachant que exposantPere = exposant+1
    Mes tutoriels avancés sur la triangulation par filet à surface et sur les octree - N'hésitez pas à consulter les tutoriels et FAQ 2D/3D/jeux.

  9. #9
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Cool merci !
    je ne pensais pas avoir besoin de remonter jusqu'au root.
    Oui votre article m'est très enrichissant.

    Au passage pouvez-vous m'expliquer en base 10 ce que fait :
    index = (mortonCode >> 3*exposant) & 7
    je crois comprendre que mortonCode >> 3 * exposant revient à faire une division euclidienne du code de morton par 2^(3*exposant)
    que veut dire & 7 ? (et logique avec 111 ? mais pourquoi ?)
    (J'avoue il faut que je m'intéresse de plus près aux opération sur les bits)

  10. #10
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Afin de retrouver le code de morton, j'ai implémenté selon vos préconisations ceci :

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    public long getMorton(){
        Node node = this;
        long morton = 0;
        while(!node.isRoot()){
            morton |= node.index << 3 * node.exponent;
            node = node.parent;
        }
        return morton;
    }

    Ca marche impec, cependant je suis frustré de ne rien comprendre à morton |= node.index << 3 * node.exponent;morton |= node.index * 2^(3 * node.exponent); ? pourquoi un ou logique avec la précédente valeur ?

  11. #11
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Autre question :
    comment retrouver les 8 cubes entourant un cube précis dans le plan x,y et ce à n'importe quelle profondeur de l'arbre (exposant)?
    "soit nous cherchons les cubes voisins à un cube, il y en a alors 26 ;" <- mais comment ? je m'arrache les cheveux....
    merci !

  12. #12
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Un solution qui marche :
    pour un noeud A, retrouver ses coo cartésiennes à partir de son morton,
    - recalculer le morton pour les coo cartésienne pour x,y et z avec pour chacun x-1, x, x + taille du cube A (soit 26 variations de A, car chaque cube à les mêmes coordonnées que son premier enfant)
    - pour chacun des 26 morton parcourir l'octree pour retrouver les 26 autres cubes de la même taille que A (au même exposant)

    optimisation possible, repartir du parent commun le plus prôche au 27 cubes et non de la racine

    ce code me permet de "streamer" l'affichage de mon octree en fonction du déplacement de la caméra, je n'affiche que le cube pointé par la caméra + ses 26 voisins.
    J'arrive comme ça à gérer un objet de 512 de côté sur 8 de haut à 60 fps (limité par la syncro verticale) (Octree de 134 217 728 cases avec au max 2 097 152 cubes)
    satisfaisant pour le moment mais je pense que l'on peut aller encore plus loin.

  13. #13
    Membre averti

    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2011
    Messages
    82
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : mars 2011
    Messages : 82
    Points : 395
    Points
    395

    Par défaut

    Désolé d'avoir tardé a répondre.

    Finalement tu te débrouille très bien tout seul .

    Le |= est comme un += dans ce cas car il n'y a jamais de retenu dans l'addition.

    L'histoire des 8 cubes au lieu des 26 est utile pour extraire les voisin d'un cube et les mettre dans le même octree.
    Les 27 cubes (3*3*3 cubes entourant un cube) possèdent 8 pères. On peut alors mettre ces 8 pères dans le même cube pour obtenir un nouvel octree autours du cube. C'est une manière d'extraire une partie de l'octree tout en gardant une structure d'octree.
    Mes tutoriels avancés sur la triangulation par filet à surface et sur les octree - N'hésitez pas à consulter les tutoriels et FAQ 2D/3D/jeux.

  14. #14
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    février 2013
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : février 2013
    Messages : 1
    Points : 1
    Points
    1

    Par défaut "petite erreur de frappe"

    Bonjour
    Merci beaucoup PierroVsf pour ce travail.
    Il me semble qu'il y'a une petite erreur de frappe dans le code "octree.h" ( ligne 101).
    Dans la dernière ligne du premier constructeur de la class Traceur:
    scale=1./scale

    Si c'est possible de poster le code source de l'animation.
    Merci par avance.

  15. #15
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Bonjour,
    Après un mois de développement d'un jeu perso en 3d isométrique (voxel sous forme de sprite 2d de cube), je me rends compte aujourd'hui que cet octree ne répond pas complètement à mon besoin .
    Du à la nature du code de morton, ou Z order curve (j'aurai du m'y intéresser plus tôt...) je me retrouve avec des problèmes d'affichage car mes sprites ne sont pas affichés dans le bon ordre.
    Tout se passe bien si ils ont des coordonnées entières, mais sur du décimal (position d'un item qui bouge comme le joueur) j'ai du recouvrement lié au parcour en Z.
    J'aime beaucoup cette structure élégante et performante en octree, mais il faut que j'arrive à la parcourir de façon efficace avec un ordre topologique (d'abord les sprites les plus éloignés de la caméra puis les plus proches.)
    https://en.wikipedia.org/wiki/Topological_sorting
    Est ce quelqu'un à une idée pour faire ça avec mon octree en morton code, ou faut-il que je refasse un octree différent (non basé sur le morton code) ou alors est-ce que l'octree est à oublier au profit d'une autre structure (certainement encore un graphe) ?

    merci

  16. #16
    Membre averti

    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2011
    Messages
    82
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : mars 2011
    Messages : 82
    Points : 395
    Points
    395

    Par défaut

    Bonjour,

    J'ai fait la petite correction nécessaire dans le code source.
    En fait j'ai mis la dernière version de mon octree que j'utilise maintenant, il n'y a pas grand chose de changé. Mais je suis sûr qu'il marche .

    Côté code source de l'animation, j'ai fait moi même ce gif avec libreoffice draw donc aucun code derrière, ensuite le code source qui pourrait t'interresser serai peut être celui qui a permis de générer cette image, c'est un code en C un peu imbuvable que j'ai fait il y a longtemps:
    http://pierre-benet.developpez.com/t...B91B58EEC8.png
    Il y a d'ailleurs une sorte de z buffer réalisée via l'octree, qui permet d'afficher proprement des cube en transparence, mais je m'étais heurté au même problème lorsque les cube dépassent un peu de leur feuille, mais je ne l'avais pas résolu.

    Pour voir l'octree en action, je préfère que tu aille voir dans cet article:
    http://pierre-benet.developpez.com/t...-contour-dual/
    qui utilise les octree présentés ici de manière efficace pour faire de la triangulation en temps réel.
    Mes tutoriels avancés sur la triangulation par filet à surface et sur les octree - N'hésitez pas à consulter les tutoriels et FAQ 2D/3D/jeux.

  17. #17
    Membre à l'essai
    Profil pro
    Inscrit en
    septembre 2005
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2005
    Messages : 14
    Points : 14
    Points
    14

    Par défaut

    Pardon, mais cette réponse fait suite à mon problème d'ordre d'affichage ?

Discussions similaires

  1. De la rapidité du code
    Par jfloviou dans le forum Contribuez
    Réponses: 233
    Dernier message: 29/05/2009, 02h17
  2. Explorateur de code C
    Par Zero dans le forum C
    Réponses: 14
    Dernier message: 06/06/2002, 09h41
  3. OmniORB : code sous Windows et Linux
    Par debug dans le forum CORBA
    Réponses: 2
    Dernier message: 30/04/2002, 17h45

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