Bonjour à tous,

Je suis actuellement confronté à un problème de taille...
Comme le sujet de mon post l'indique, je dois programmer un octree dans le cadre de mon stage afin d'optimiser mon code.

La théorie de l'octree est simple et je pense l'avoir bien comprise, par contre au niveau de l'implémentation il y a un hic.

Pour la construction de l'octree, on parle de subdiviser la boite englobante en 8 fils. Chaque fils étant ensuite re-subdivisé en 8 fils et ainsi de suite tant que les conditions d'arrêt de la récursivité ne sont pas remplies.

Jusque là tout va bien.

A la fin de chaque subdivision, il est question de répartir les faces (ou points) dans les fils correspondants.
Et c'est là que la bât blesse.

D'après les sources que j'ai pu voir, les techniques de répartition des faces dans les octants (ou fils) sont basés sur le test d'appartenance des points aux octant.
En gros, pour savoir si la face est dans le fils, on regarde si au moins un de ces points est dedans.

Le problème c'est qu'avec cette méthode, il est possible d'avoir des "trous". Imaginez un très grand triangle qui doit être inclut dans plusieurs octants, on n'inclura la face que dans les octants aux extrémités de la face (ou à ses sommets).

Ainsi si un octant se trouve sur un segment de la face mais ne contient aucun de ses points, cette technique n'inclura pas (et à tort) la face en question.

Question implémentation, tout a été codé et testé. Le résultat confirme cette crainte car le résultat produit une image à "trous".
Pour compenser j'ai améliorer ce test d'appartenance en effectuant un test d'intersection non pas avec les points mais avec les segments de la face sur les octants.
L'image résultat n'est plus "trouée" mais prend beaucoup plus de temps que le rendu classique sans octree !

Alors voici ma question : Comment répartir les faces dans les octants de manière rapide et efficace dans une implémentation d'octree ??

A tous ceux qui pourront m'apporter une aide quelle qu'elle soit, Merci !

L'idée est donc d'avoir une liste de triangle par noeud.
Et le probleme que tu as, c'est que tu veux mettre cette cette liste uniquement aux feuilles.

Non : si un triangle traverses plusieurs cubes finaux, alors tu ne le mettra pas dans une feuille, tu le mettras dans le noeud du dessus (donc dans un cube plus grand), et tu remontes ce triangle jusqu'a ce que ses 3 points soient dans un seul cube
Et la, tu es sur de ne pas avoir de "trous" comme tu dis.

Cas extreme : un triangle qui fait tout le monde de longueur (un sol plat par exemple) sera placé dans le noeuf racine de l'octree.

Ensuite, quand tu vas pour lire la liste des triangles maximale qu'il y a dans un petit cube, tu lis la liste de la feuille, mais aussi des noeuds parents : jusqu'a la racine.

En espérant avoir pu t'aider

Salut Fvirtman merci pour ton aide,

En fait dans mon implémentation, j'ai bien une liste de triangle par nœud, fils y compris (puisque ça reste un noeud).

La méthode que tu me décris, est celle du parcours en "bottom-up" alors que je parcours l'arbre en partant de la racine (top-down) pour finir aux feuilles.
Les 2 méthodes de parcours étant différentes, l'arbre octal est-il construit différemment ?

A noter que je construis également mon octree en top-down cad en partant de la boite englobante de la scène.

Ton idée de mettre les triangles dans le dernier noeud dans lequel il "loge entier" est très juste, d'ailleurs c'est actuellement le cas dans mon code. J'ai simplement ajouté dans chaque noeud qui scinde un triangle, le triangle en question (donc présence volontaire de doublons).

Je suis sur le sujet depuis quelques jours maintenant, il doit y avoir un truc que j'ai pas saisi quelque part...

PS:j'ai visité ton site perso et tes projets sont super et nombreux . La démo sur la stéréoscopie à l'air géniale, dommage qu'il n'y ait pas l'exécutable à dispo.

Arf, j'avais oublié le lien sur ma page pour la stéréoscopie ! Je viens de corriger ce probleme

Hum, apres, les doublons dans les octrees, je ne suis pas bien pour, mais cet avis est bien sur discutable !
Je ne pense pas que aies de différence en fonction de l'ordre de construction, dans la mesure ou de toute façon, ordre ou non, un triangle sera au meme endroit.

Merci à Fvirtman qui m'avait donné la réponse à mon problème mais que je n'ai compris que plus tard

Je colle la réponse que j'ai posté sur un autre forum afin de pouvoir switcher l'état de mon post à "Résolu" !

Pour ceux que ça pourrait aider :
Je cherchais à pointer mes faces uniquement aux feuilles.
Donc pour les faces à cheval (cf face bleue sur le schéma), je devais me débrouiller pour les répartir correctement dans plusieurs fils.

Ce qui pour être rigoureusement juste doit être fait avec un test d'intersection entre la face et la boite englobante des 8 fils. Mais c'est beaucoup trop long.

Il faut donc, comme l'as très bien expliqué TanEk, ne stocker le triangle bleu que dans le noeud parent et pas dans ces 4 enfants du schéma.
C'est pourquoi répartir le triangle bleu par ses points ne permet de ne stocker que dans 3 fils.
Le fils manquant fait apparaît des trous dans l'image correspondant au bout de triangle vert sur l'image.

Grâce à cela, il ne doit y avoir aucun doublon dans l'arbre octal autant horizontalement (pour un même niveau de profondeur donnée) que verticalement (pour toute profondeur).

Vous me retirez une grosse épine du pied,

Merci beaucoup pour vos réponses éclairées, je vous tiendrais au courant des résultats obtenus et quelques images si j'en ai le droit

tout a fait, dans ton exemple, le triangle bleu ne sera typiquement pas dans les feuilles, mais dans le parent qui englobe tes 4 carrés (8 cubes en 3D)

(3D octree, 2D quadtree, c'est pareil)