Discussion :

[epsilon68]

bonjour,

Savez-vous comment construire une hierarchie de sphere pour organiser un ensemble de triangle?
Les octrees je connais bien mais je prefererais des spheres plutot que des cubes pour simplifier les intersections (dans mon cas beaucoup d'intersections)

Merci beaucoup d'avance pour votre aide.

a+

[epsilon68]

Est-ce que le fait de partir sur un octree puis de prendre la sphere englobante de chaque cube est satisfaisant ?

[bafman]

a priori, pour une BSH, je partirait plutot dans le sens inverse du quad tree :
pour chaque triangle : tu créer sa sphere englobante, et ensuite, tu créer des groupe de sphere proches et tu continue comme ca jusqu'à n'avoir plus qu'une sphere.

[epsilon68]

comment crée-t-on une sphere englobante (optimale) des autres spheres proches (le plus proche possible donc) ?

[bafman]

si tu groupe les sphere 2 à 2, ca se fait facilement. par 3 aussi, il suffit, a priori, de prendre le centre de gravité du triangle comme centre de la sphere. Pour regroupé par plus, j'ai pas d'idée direct comme ca

[epsilon68]

Creer une sphere de plusieurs autres spheres n'est pas vraiment un probleme en soi, mais de trouver les spheres les plus proches pour creer une sphere englobante est une autre pair de manche...

Comment il faut faire ?

[bafman]

je ne sais pas trop. A priori, je partirait sur un algo en plusieurs passes qui prend une sphère, recherche ses plus proche voisin, les "regroupe", et les enlèvent du groupe de sphere à grouper, et on recommence... bon en même temps, c'est tout naze comme algo, car c'est hyper lent et ça risque de générer des sphere non groupable car trop éloignés...

[epsilon68]

oui tu as raison c'est completement naze

il faut partir sur un octree et recalculer le sphere des points des triangles se trouvant dans le cube, puis descendre dans la hierarchie.
attention le cube de depart est un cube sur la sphere optimale de tous les vertex du model.

J'hesitais mais maintenant c'est mûr pour moi.
Je vais d'ailleurs l'implementer tres bientot.

[epsilon68]

Quelqu'un aurait-il deja testé? aurait une meilleure solution? des critiques?

[PRomu@ld]

Quel est le contexte d'application ? Pourquoi vouloir utiliser des sphères pour ta hiérarchie et pas des boîtes (et donc un BVH classique) ou alors un kd-tree ?

[epsilon68]

des spheres c'est pour "attaquer" mon model sur n'importe quel coté, comme faire un lancer de rayon de n'importe ou... typiquement les AABox sont vraiment long a tester dans ce cas la.

je ne connais pas les kd-tree mais je suis ouvert, tu as des suggestions?

[PRomu@ld]

En fait, il ne faut pas voir les intersections directes objet/rayon mais scène rayon. Même si ton approche sphère semble correcte pour les objets pris tous seuls mais dans une scène, ça n'est pas forcément le mieux.

En plus, une AABB pas trop efficace par rapport à une sphère, c'est pas toujours vrai (ou alors ton test d'intersection est peu efficace.

Le KD-tree, c'est une des structures accélératrices la plus optimale pour du lancer de rayon. C'est un peu long à construire (plus long qu'un BVH ou qu'un BIH), quoique des progrès significatifs ont été fait, mais c'est surtout très rapide à parcourir.

La structure d'un KD-tree, c'est très simple, c'est un arbre BSP aligné aux axes.

[epsilon68]

la je structure mon model, mais apres effectivement il y a bien un scene graph...
la je peux changer et prendre les AABox, de toute facon le nombre d'objets est tout petit par rapport au nombre de faces...

les spheres donnent en outre l'avantage de ne pas etre recalculées quand on transforme le model.

par contre comment veux-tu faire une intersection avec une AABox efficace?
aussi efficace que la sphere? moi je n'ai pas trouvé.

tu penses que les KD-trees sont le mieux? t'aurais un lien interessant (a tout hasard) ?

EDIT: J'ai oublié d'ajouter que je ne fais pas que du lancer de rayon mais de trouver aussi les collisions avec sphere/cone/cylindre avec les triangles, ses aretes et ses sommets...

[Camel LowFilter]

les arbres de sphères je crois que c'est surtout utile pour ranger les polygones d'un model animé avec des bones, mais comme c'est plus lent à parcourir que les structures statiques on s'en sert localement mais pas sur toute une map à moins de vouloir faire une petite map organique
sa construction se base entierement sur l'arbre de bones et leurs enveloppes, elle peut etre complexe et peut requérir un editeur pour la guider manuellement

si les animations sont juste locales il vaut mieux utiliser une structure generale statique (octree, kd tree...) et ajouter des arbres de sphere ou autres là où ça bouge

[epsilon68]

je voulais faire les spheres pour etre super rapide en intersection de rayon et de collision des triangles avec des spheres/cones/cylindres.

Tu me dis que ca va etre super lent ? qu'il n'y a rien de pire?
mais pourquoi donc? les spheres sont ce qu'il y a de plus rapide a tester justement....

[PRomu@ld]

http://cag.csail.mit.edu/~amy/papers/box-jgt.pdf

[epsilon68]

en fait je l'avais deja implementé mais je n'avais pas trouvé de speed-up...
je reessaierai a l'occasion... je compte implementer les spheres mais aussi les AAbox, je pourrais comparer la vitesse. Octree vs Spheres ...
on va voir.

Comment calculeriez-vous la sphere englobante optimale sur un ensemble de points ?

a+

[PRomu@ld]

Optimale je sais pas mais approximative comme ceci :

Tu prends les deux points les plus éloignés, ça te fait un double rayon initial, ensuite tu prends les points un par un et tu vérifies s'ils sont dans ta sphère. Si ça n'est pas le cas, tu mets à jour le rayon et le centre.

Tu peux trouver le code dans un Graphic Gem (je n'ai plus le tome en tête).

[epsilon68]

c'est aussi l'algo que j'avais en tete. mais la sphere est approximative (il dit 7% d'erreurs). Je me demandais si d'autres avaient implementé une sphere englobate parfaite et rapide à calculer ...

peut-etre je demande le "mieux" alors que j'ai déjà le "bien"
et comme tout le monde sait, c'est que le mieux est l'ennemi du bien.... :-)

[PRomu@ld]

Tout comme les AABB, l'obtention de quelque chose d'optimal est relativement compliqué et peut-être pas forcément utile.

Souviens toi que ça doit être une structure accélératrice, d'un objet factice pour accélérer les calculs. Rien ne t'obliges à avoir quelque chose d'optimal. Pour 7% d'erreurs, je pense que c'est suffisant.