Discussion :

[_Minh_]

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 !

[raptor70]

Personnellement, je travaillerais directement avec les bounding box pour sélectionné l'octant dans lequel doit être inclus dans ton object, je ne descendrais pas au niveau de la face. Mais tu peux évidement utiliser des bounding box.

Par contre, je ne comprends pas pourquoi tu fais des tests d'intersections, ce n'est pas très utile. Par contre, une face à cheval sur deux octant nécessite un choix : soit dans un octant, soit dans l'autre .. (par exemple, on peut prioritiser les X positifs, on peut choisir quels octants contient le plus de vertex, ... ). Tes choix doivent permettrent de séparer TOUTES tes faces, tu ne dois pas en supprimer.

[_Minh_]

Hello raptor70,

Pour précision, je ne travail qu'avec un seul objet constitué d'un maillage unique (non composé de sous-objets).
Donc, la boite englobante de celui-ci est la racine de mon octree.

Concrètement, si je veux utiliser des bounding box ça sera forcément au niveau des faces puisqu'il n'y a pas de niveau intermédiaire !

En ce qui concerne, la gestion des faces à cheval, le cas est traité et j'inclus la face dans tous les octants correspondants.

J'ai pu voir que certains testent la boite englobante du triangle avec les octants, je vais voir si cela règle mon problème...

[zenux]

Bonjour,

Par contre, une face à cheval sur deux octant nécessite un choix : soit dans un octant, soit dans l'autre .. (par exemple, on peut prioritiser les X positifs, on peut choisir quels octants contient le plus de vertex, ... ). Tes choix doivent permettrent de séparer TOUTES tes faces, tu ne dois pas en supprimer.

Dangereux comme solution, non ?
Imagine qu'une face se trouve à 60% dans l'octant 1 et à 40% dans l'octant 2. Tu va donc mettre la face dans l'octant 1.
Si dans le champ de vision, il n'y a que l'octant 2 de visible, le triangle ne sera pas affiché alors qu'il devrais l'être !

[TanEk]

Il n'y a pas une histoire de mettre certains triangles dans les feuilles mais plutôt dans les noeuds intermédiaires ou plutôt particulièrement dans le noeud le plus bas dans l'arbre qu'est l'octree englobant l'objet ?

[raptor70]

Bonjour,



Dangereux comme solution, non ?
Imagine qu'une face se trouve à 60% dans l'octant 1 et à 40% dans l'octant 2. Tu va donc mettre la face dans l'octant 1.
Si dans le champ de vision, il n'y a que l'octant 2 de visible, le triangle ne sera pas affiché alors qu'il devrais l'être !

C'est vrai ... donc tu peux très bien imaginer l'intégrer dans les deux octants .... on étant sur que chaque face n'est dessinées qu'une seule fois ( système de flag ou de pointeur dans les octants)

[_Minh_]

Bonjour,



Dangereux comme solution, non ?
Imagine qu'une face se trouve à 60% dans l'octant 1 et à 40% dans l'octant 2. Tu va donc mettre la face dans l'octant 1.
Si dans le champ de vision, il n'y a que l'octant 2 de visible, le triangle ne sera pas affiché alors qu'il devrais l'être !

En effet, c'est pour cette raison que j'inclus la face en question dans chaque octant qu'elle (la face) intersecte.
En partant du principe que mieux vaut trop que pas assez !

Pour ceux qui auraient déjà programmé un octree, comment avez-vous réparti les faces dans les octants ?
Puisque c'est visiblement là mon problème

[TanEk]

Et pour ma remarque ? Ell est passé à la trappe ?

[_Minh_]

Oups, désolé je lis parfois (trop) vite

Si je comprends bien ta remarque, tu proposes de mettre les faces à cheval dans le noeud parent le plus haut (en partant des feuilles) dans lequel la face logerait entière.
Ouch l'idée est simple mais la phrase est lourde...

Et c'est le cas dans mon implémentation, le noeud parent possèderais la face entière ainsi que chacun de ses fils qui l'intersècterait.

Je me pose la question de savoir si la boite englobante de la scène doit être cubique.

(Quelques heures après) Il semblerait que oui, la boite doit être cubique car les résultats sont meilleurs. Or la mienne ne l'était pas mais juste parallélépipédique.
C'est donc un premier élément de réponse, mais ce n'est pas encore parfait.
Je continue de chercher...

[TanEk]

Hum je ne crois pas que tu aies compris ce que je disais par là. En gros le triangle qui est dans plusieurs feuilles va être stocké dans le père commun à toutes ces feuilles. Mais il ne sera pas du tout stocké dans les feuilles. Les feuilles ne sauront pas que le triangle existe...

En gros au lieu que tes objets soient pointés uniquement par les feuilles, ils sont pointés par les feuilles ou les noeuds intermédiaires mais pas les deux en même temps.

Ainsi si tu fais un affichage utilisant ce type d'octree tu vas :

tester la racine de l'octree représentant la scène. S'il est dans le frustum alors t'affiches les objets pointés par la racine (en l'occurence peut-être ton triangle qui prend de la place), ensuite on va voir les fils, on teste l'intersection avec frustum, si oui alors afficher les objets pointés, puis on va voir les fils des fils, etc.

[_Minh_]

Hum je ne crois pas que tu aies compris ce que je disais par là. En gros le triangle qui est dans plusieurs feuilles va être stocké dans le père commun à toutes ces feuilles. Mais il ne sera pas du tout stocké dans les feuilles. Les feuilles ne sauront pas que le triangle existe...

En gros au lieu que tes objets soient pointés uniquement par les feuilles, ils sont pointés par les feuilles ou les noeuds intermédiaires mais pas les deux en même temps.

Ainsi si tu fais un affichage utilisant ce type d'octree tu vas :

tester la racine de l'octree représentant la scène. S'il est dans le frustum alors t'affiches les objets pointés par la racine (en l'occurence peut-être ton triangle qui prend de la place), ensuite on va voir les fils, on teste l'intersection avec frustum, si oui alors afficher les objets pointés, puis on va voir les fils des fils, etc.

C'est en exposant ta solution à mon tuteur que j'ai compris le fond du problème ! C'est vrai que c'est dur à décrire par des posts mais merci d'avoir pris le temps !

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

[TanEk]

Toujours un plaisir d'aider autrui . Et je ne suis pas contre quelques images :p. Bonne continuation.

[zenux]

Il n'y a pas une histoire de mettre certains triangles dans les feuilles mais plutôt dans les noeuds intermédiaires ou plutôt particulièrement dans le noeud le plus bas dans l'arbre qu'est l'octree englobant l'objet ?

Dangereux (niveau performance), aussi, il me semble...
Imagine qu'une face se trouve au milieu de 2 octants de niveau 2 (le niveau 1 étant l'octant mère), cette face devra être ajouté à l'octant mère.
Cette face sera donc TOUJOURS affiché vu que l'octant mère est toujours visible (ou presque).

Pour l'instant, je n'ai rien trouvé de mieux que de mettre les faces/objets aux feuilles et d'utiliser un flag pour ne pas les afficher plusieurs fois.
Regarde du côté des loose octree, ça permet peut-être de résoudre ce problème....

[HanLee]

Dangereux (niveau performance), aussi, il me semble...
Imagine qu'une face se trouve au milieu de 2 octants de niveau 2 (le niveau 1 étant l'octant mère), cette face devra être ajouté à l'octant mère.
Cette face sera donc TOUJOURS affiché vu que l'octant mère est toujours visible (ou presque).

Pour l'instant, je n'ai rien trouvé de mieux que de mettre les faces/objets aux feuilles et d'utiliser un flag pour ne pas les afficher plusieurs fois.
Regarde du côté des loose octree, ça permet peut-être de résoudre ce problème....

Ben, si l'octant mère est visible, c'est normal de l'afficher cette face, vu qu'elle est de dimension équivalente à l'octant visible non ?

-------

Et si tu la mets dans les feuilles uniquement, c'est quoi le critère de subdivision de ton octree, si ce n'est pas la taille des éléments englobés ?

Si tu as divisé ton octree au niveau n, c'est à dire 8^n feuilles (car tu as dit que tu ne référençais qu'au niveau de la feuille).
Si une face ne rentre que dans l'octant racine (en terme de dimensions), alors, il y a aura k.8^n feuilles qui référencent cette face, avec un k de l'ordre de 1/3 par exemple.

Donc, k.8^n tests pour ne pas redessiner cette face plusieurs fois, je trouve ça énorme.



J'espère juste avoir mal compris ce que tu préconises.

[zenux]

Donc, k.8^n tests pour ne pas redessiner cette face plusieurs fois, je trouve ça énorme.

Oui tu as raison, ça fait beaucoup......mais dans le type de jeux vidéo que je suis entrain de développer ça n'arrive jamais. Prend un jeu comme Crysis, Doom3, Far cry, il n'y a aucun objet qui rempli tout l'octant mère.
Il y a sûrement des situations où cette technique n'est pas du tout la meilleure.

Ben, si l'octant mère est visible, c'est normal de l'afficher cette face, vu qu'elle est de dimension équivalente à l'octant visible non ?

Tu as du mal comprendre...
Imagine un octant mère de 1024*1024*1024 et un objet défini par une bounding box de 2*2*2 qui se trouve au milieu de l'octant mère. Avec la technique de TanEk, tu commence à la feuille et tu remonte à l'octant parent tant qu'il y a intersection. Dès qu'il n'y a plus intersection, tu ajoutes l'objet dans l'octant. Si tu fait ça, ton objet de 2*2*2 va se trouver dans l'octant mère.
Et dire que l'objet de 2*2*2 est toujours visible quand l'octant mère est visible est totalement faux....

Ou alors je n'ai pas compris la solution de TanEK.

[TanEk]

Si si tu as très bien compris mais c'est la structure de l'octree qui limite. Il existe d'autres structures plus complexes et qui permettent d'éviter ce problème propre à l'octree qui sont les Kd-tree & co (que je ne connais pas du tout).

Mais en tout cas mon approche semble la plus correcte et ne peut être optimisée (en tout cas de ce que j'en sais, je ne me considère pas comme un expert des octree ), sinon ce sont des solutions "non correctes" comme choisir une feuille au hasard et qui font que l'objet peut être caché alors qu'il devrait être visible ou alors mettre l'objet dans plusieurs feuilles mais cela complique inutilement les tests et est rarement favorable.

En effet cela peut arriver qu'un objet soit dans le noeud mère mais c'est très rare et s'il existe il est en général tout seul donc ce n'est pas très grave au vu des centaines d'objets faisant la scène.

[HanLee]

zenux : mais quelle que soit la méthode, le fait qu'un octant soit visible ne garantit pas que ses objets seront visibles.

L'important c'est que la réciproque soit respectée : un objet visible -> l'octant à qui il appartient est visible.

Après, les loose-octrees permettent justement d'éviter le cas de figure dont tu viens de parler, quand un petit objet se trouve au bord.

Si si tu as très bien compris mais c'est la structure de l'octree qui limite. Il existe d'autres structures plus complexes et qui permettent d'éviter ce problème propre à l'octree qui sont les Kd-tree & co (que je ne connais pas du tout).

Mais en tout cas mon approche semble la plus correcte et ne peut être optimisée (en tout cas de ce que j'en sais, je ne me considère pas comme un expert des octree ), sinon ce sont des solutions "non correctes" comme choisir une feuille au hasard et qui font que l'objet peut être caché alors qu'il devrait être visible ou alors mettre l'objet dans plusieurs feuilles mais cela complique inutilement les tests et est rarement favorable.

En effet cela peut arriver qu'un objet soit dans le noeud mère mais c'est très rare et s'il existe il est en général tout seul donc ce n'est pas très grave au vu des centaines d'objets faisant la scène.

Bah, en tout cas ça montre juste que l'octree n'est pas une structure adaptée à ça, vu tous les cas particulier qu'il faut prendre en compte.
C'est bien adapté aux terrains quand ils sont réguliers par exemple, mais bon...

Le BVH se comporte mieux mais, c'est plus dur de trouver une bonne heuristique pour sa construction.

[zenux]

zenux : mais quelle que soit la méthode, le fait qu'un octant soit visible ne garantit pas que ses objets seront visibles.

L'important c'est que la réciproque soit respectée : un objet visible -> l'octant à qui il appartient est visible.

Oui mais niveau performance, ça peux devenir horrible....imagine que mon objet au centre de l'octant mère de 2*2*2 soit en fait un personnage dans un véhicule : tu va te retrouver avec plus de 10 000 faces affichées en permanence (ou du moins quand l'octant mère est visible).
Ca me semble largement plus performant de le mettre dans quelques feuilles.
Si mon objet de 2*2*2 se trouve dans 8 feuilles, je vais devoir faire 8 "if"....c'est quand même plus performant que d'afficher 10 000 faces en permanence, non ?

[TanEk]

Je ne suis quand même pas fan de ton astuce... Là ce n'est qu'une question de feeling. Je préfère changer de structure et en prendre une plus adaptée que faire un hack comme tu le proposes pour gérer certains cas défavorables (qui ne sont que des exceptions). Car ton hack entraîne une lourdeur dans le code qui entraîne des soucis de maintenance, de compréhension du code (imagine un gars qui a déjà fais des octree utilise ton octree et croit à juste titre qu'un objet n'est pointé qu'une fois dans l'octree). Enfin bref, question de feeling comme je disais .

C'est comme si tu décidais de faire un hack pour le quick sort parce que si la liste est déjà triée alors les performances vont être désastreuses. C'est au programmeur à faire en sorte de ne pas appliquer le quick sort sur une liste déjà triée. Sinon s'il ne peut pas savoir si elle est déjà triée, il applique l'autre algorithme, le stable_sort.

Là c'est pareil, quand tu fais la map, tu fais en sorte de ne pas mettre les objets à des endroits qui vont faire qu'ils seront dans le noeud root de l'octree. Et pour les objets dynamiques, comme leur nom l'indique, ils sont dynamiques donc même s'ils arrivent à un moment à l'endroit qui pose problème, et bien ils n'y resteront pas longtemps.

Et puis 10000 triangles c'est que dalle pour une carte graphique .

[HanLee]

Oui mais niveau performance, ça peux devenir horrible....imagine que mon objet au centre de l'octant mère de 2*2*2 soit en fait un personnage dans un véhicule : tu va te retrouver avec plus de 10 000 faces affichées en permanence (ou du moins quand l'octant mère est visible).
Ca me semble largement plus performant de le mettre dans quelques feuilles.
Si mon objet de 2*2*2 se trouve dans 8 feuilles, je vais devoir faire 8 "if"....c'est quand même plus performant que d'afficher 10 000 faces en permanence, non ?

Oui, non mais de toute façon, ni moi ni toi avons la meilleure solution quel que soit le cas de figure.

Nos approches sont duales :
- la mienne est adaptée pour des gros objet
- la tienne est adaptée pour des petits objets.

Et encore, ça dépend des données, on raisonnait tous les deux avec le pire des cas, et ici, c'est absolument pas rigoureux vu la distribution très large des différentes données possibles et des cas de figure à prendre en compte.

--------

TanEk, pour le quick sort, on applique en général une heuristique pour le pivot.
Le stable_sort c'est particulier, c'est quand on ne veut pas que 2 valeurs équivalentes au sens de l'opérateur de comparaison (attention, j'ai pas dit "égales", il y a nuance, sinon ça n'aurait aucun intérêt) soient échangées.