Discussion :

[f56bre]

Bonjour,

Je suis en train d'implémenter un système de raytracing et pour cela je souhaite utiliser les bounding box. Cette technique semble bien adapté car étant "centrée sur l'objet" mais quelque chose me chagrine. Au départ de mon algo, je lance mon rayon mais y a t'il un moyen de m'orienter directement vers les bounding box susceptibles d'être dans la trajectoire au lieu de toutes les tester (et si possible tomber rapidement sur la plus proche...)? Exite t'il une technique pour cela? Faut-il coupler un système de partitionnement du style octree pour trier le gros de la scène?

merci

[bafman]

tu a la réponse, il faut utiliser un système de partitionnement genre octree, BVH et autre kd Tree selon le cas d'utilisation

[f56bre]

Merci pour cette réponse mais la question sous-entendait "si oui comment?"
Je veux dire, dans quelle mesure bounding box et octree sont liés? Jusque qu'elle précision les octree interviennent ils? Auriez-vous des docs là dessus?

merci

[shenron666]

je n'ai pas de doc en tête mais avec un peu de recherches tu peux en trouver facilement

pour te faire un petit résumé boundingbox vs octree (ou autre quadtree, kdtree ect)
- la boundingbox délimite grossièrement un objet et donc la place qu'il occupe dans le monde virtuel
- le machin tree subdivise le monde virtuel en zones de manière à simplifier / accélérer les tests de collision / visibilité (inutile d'afficher un objet hors du champ de la caméra)

edit : voici une petite applet java démontrant des algorithmes de subdivision

[f56bre]

Merci pour ta réponse shenron666 mais en fait mon problème n'est pas d'implémenter l'une ou l'autre des solutions mais de savoir s'il est intéressant de les coupler (octree pour dégrossir en fonction de la position dans la scène et bounding box pour le reste) et si oui comment?

[IrmatDen]

Oui, il faut les coupler. Comment ? Tu peux avoir ta scène composée de plusieurs objets ayant leur BB (ou autre type de volume, les boîtes ne sont pas les seuls); tu décomposes ta scène dans l'arbre que tu as choisi selon les BV des objets la composant.
Ensuite, tu peux encore avoir des sous-arbres et sous-BV pour chaque objet s'il est assez complexe pour en justifier le coût.

[f56bre]

Donc en suivant ton raisonnement, IrmatDen, je descend dans mon octree jusqu'à ce que je tombe sur noeud contenant un ou plusieurs volumes englobants pour le(s)quel(s) je fais un test d'intersection avec mon rayon. Maintenant pour ce qui est du parcours dans l'objet (pour atteindre mes faces, mes sommet ou juste un sous-ensemble de l'objet) ne me suffirait-il pas de tester les points moyens des volumes englobants les plus proches de mon rayon?

[IrmatDen]

Si tu vérifies les volumes à proximité du rayon (et non pas le noeud dans lequel il entre), ça ne t'indique pas contre quelle(s) primitive(s) tester tes intersections; tu te retrouves à définir un volume pendant que tu traces, et ce pour chaque rayon qui entre dans l'objet (un peu comme s'il n'y avait pas de volumes englobant, ou pas assez)... enfin, si je comprends bien ta question

[f56bre]

Oula j'avoue que là je ne te suis pas trop. Mon soucis est de savoir quand je passe la main aux volumes englobants une fois que j'ai précisé ma position dans l'espace à l'aide des octree.
J'ai donc bien mes volumes qui existent déjà autour de mes objets et mon but est de faire en sorte de tester tout de suite les bons (ceux qui sont susceptible de croiser mon rayon) d'où l'utilisation des octrees. Ce que je proposais est de prendre comme critère de choix pour l'arrêt du parcours de l'octree non pas une précision fixe mais plutôt le nombre de volumes contenus.
Exemple : Un noeud de mon octree contient 4 volumes, en poursuivant dans un des fils de ce noeud (en fonction du chemin de mon rayon bien sûr) je tombe sur un noeud contenant un seul volume donc hop, je passe la mains au test d'intersection rayon/volume englobant. Qu'en dis-tu?

[IrmatDen]

J'avais donc mal compris ^^

Ce que je proposais est de prendre comme critère de choix pour l'arrêt du parcours de l'octree non pas une précision fixe mais plutôt le nombre de volumes contenus.

Oui, ça te permettra d'éviter d'obtenir trop de zones vides (et donc trop de tests d'intersections inutiles).