Developpez.com - Rubrique 2D-3D-Jeux

Le Club des Développeurs et IT Pro

Octrees optimisés grâce au code de Morton

Un tutoriel de Pierre Bénet

Le 2016-02-26 22:55:33, par PierroVsf, Membre éclairé
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
  Discussion forum
16 commentaires
  • LittleWhite
    Responsable 2D/3D/Jeux
    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.
    le 14/08/2017 à 11:37
  • Matt_Houston
    Expert confirmé
    Merci pour cet article vraiment très clair et bien écrit.
    le 27/02/2016 à 7:26
  • PierroVsf
    Membre éclairé
    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 : 
    mortonCode = (index << 3*exposant) | (indexPere << 3*exposantPere) | (indexGrandpere << 3*exposantGrandpere)...
    Une petite boucle suffit à le calculer, sachant que exposantPere = exposant+1
    le 16/08/2017 à 10:24
  • fleporcq
    Membre à l'essai
    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 !
    le 14/08/2017 à 11:27
  • fleporcq
    Membre à l'essai
    Tout à fait vous avez entièrement raison, veuillez pardonner mon erreur
    le 14/08/2017 à 22:01
  • LittleWhite
    Responsable 2D/3D/Jeux
    Du coup, quelles sont les questions ?
    le 15/08/2017 à 9:31
  • fleporcq
    Membre à l'essai
    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
    le 16/08/2017 à 0:20
  • fleporcq
    Membre à l'essai
    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)
    le 16/08/2017 à 17:57
  • fleporcq
    Membre à l'essai
    Afin de retrouver le code de morton, j'ai implémenté selon vos préconisations ceci :

    Code java : 
    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 ?
    le 16/08/2017 à 20:46
  • fleporcq
    Membre à l'essai
    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 !
    le 19/08/2017 à 23:39
  Poster une réponse