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 :mrgreen: , quelques jolies images et un petit code source.

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



:fleche: Tous les meilleurs cours et tutoriels pour apprendre la programmation des jeux

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

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 !

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.

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

Du coup, quelles sont les questions ?

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

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

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)

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

Code:

---

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 ?

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 !

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.

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.

Bonjour
Merci beaucoup PierroVsf pour ce travail.:bravo:
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.

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 :calim2:.
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

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.

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