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

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Octrees optimisés grâce au code de Morton
Un tutoriel de Pierre Bénet

Le , par PierroVsf
16 commentaires

18PARTAGES

13  0 
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

Une erreur dans cette actualité ? Signalez-nous-la !

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

Code java : Sélectionner tout 
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 ?
0  0 
fleporcq
Avatar de fleporcq
Membre à l'essai https://www.developpez.com
Le 19/08/2017 à 23:39
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 !
0  0 
Commenter Signaler un problème