ben tu te fais une structure d´abres ( ou en classes si tu preferes)
Imagines que tu stockes tes triangles dans une classe Triangle, tu fais :
struct Noeud
{
list<Triangle*> L;
struct Noeud* fils[8];
int minx,miny,minz,maxx,maxy,maxz;
};
puis tu fais une fonction récursive qui remplit l´arbre :
a la base, tu as une grande liste de triangles ( une soupe de triangle) Gliste
tu en as calculé la boite englobante ( minx,miny,minz) ; ( maxx,maxy,maxz)
Tu procedes au 1er noeud avec Glist : tous tes triangles sont dedans.
tu fais 8 appels récursifs dans ta fonction :
sur :
( minx,miny,minz) ; ( (maxx-minx)/2,(maxy-miny)/2,(maxy-miny)/2)
( (maxx-minx)/2,miny,minz) ; ( maxx,(maxy-miny)/2,(maxy-miny)/2)
etc ! ! tu dcoupes le cube en 8 en fait ! !
A la sortie, tu as dans chaque noeud peu de triangles dans leur liste L, et la boite englobante de la zone ( ton monde est découpé en gros cubes, dans lesquels il y a des cubes plus petits)
Les triangles qui sont absolument dans un petit cube de feuille sont dans la liste des feuilles ; si un triangle chevauche 2 box, il est dans la integralement dans la box de sa mere, ou de sa grand mere, etc, et donc il est stocké dans la liste en question ( celle d´un noeud au milieu de l´arbre)
Tu vois comment mettre en place ta structure ? ?
Ensuite, comment faire marcher cela ?
tu te fais une fonction qui détermine si une box est dans ton champs de vision ou non ( partiellement ou entierement, on s´en fiche)
Quand tu vas pour dessiner, tu te base sur l´octree : tu vas donc faire 8 tests ( pour les 8 box de base) ( donc rien du tout)
Avec de la chance, tu en élimines déja qq unes que tu ne vois pas --> en 1 test, tu as donc éliminé les milliers de triangles qu´il y avait dedans ! ! tu n´auras pas a les tester.
pour ceux que tu vois, c´est simple, tu explores le fils qui à son tour a 8 fils, 8 cubes plus petits, que tu pourras voir ou ne pas voir !
Et tu continues récursivement : et a chaque fois tu affiches uniquement les triangles des listes.
donc au lieu de tester 1000000 triangles, tu testes juste quelques box, et tu affiches les triangles dedans, tres beau a la sortie normalement.
Un gain de temps monstrueux.
Voila, j´espere que j´ai réussi a te faire comprendre le principe, apres, a toi d´implémenter tes structures !
