6.2.3.1 : Que sont les octree et les quadtree ?
Les octree permettent de trier des objets dans un espace à 3 dimensions (on parle de quadtree à 2 dimensions).
Un octree décrit généralement un espace sous la forme d'un cube, ou d'un parallélépipède rectangle.
La construction d'un octree repose sur des rêgles simples :
- Un octree peut être vide
- Un octree ne peut pas contenir plus d'un objet à trier à la fois
- Lorsque l'on doit ajouter un objet à trier dans un octree déjà plein, on le coupe en 8 ($2\times2\times2$ ), ou 4 dans le cas d'un quadtree, puis on replace les deux objets dans leurs sous-octree ou sous-quadtree respectif.
Figure 15 : Illustration du remplissage d'un quadtree.
Figure 16 : Illustration de l'utilisation des octree.
- mettre à jour la masse de la cellule en fonction des particules qu'elle contient
- mettre à jour le centre de gravité de la cellule en fonction des particules qu'elle contient