en abscisse le nombre de sphères et le temps en millisecondes en
ordonnées.
et pour 90x90 sphères, le calcul dure ~35s, en parallèle sur un
processeur 8 coeurs, ca commence à faire long !
comment pourrait-on gagner du
temps ? le programme fait essentiellement des calculs
d'intersection rayon / sphère... peut on éviter de calculer
certaines intersections ?
quand on regarde les images, il est assez simple de se rendre
compte que calculer les intersections avec toutes les sphères à
gauche pour les pixels de la partie droite de l'image ne doit
pas servir à grand chose... et que ne pas calculer ces
intersections ne changera pas l'image. de la même manière, pour
les pixels à gauche de l'image, il ne sert sans doute pas à
grand chose de calculer les intersections avec les sphères de
droite...
l'idée est de grouper les objets, les sphères dans ce cas, et de
ne calculer les intersections avec les objets du groupe que si
le rayon passe dans la région ou se trouve le groupe... sinon ce
n'est pas la peine, on connait deja le résultat de
l'intersection, le rayon ne touche pas les objets...
groupes d'objets et englobant
comment grouper les objets ?
on peut tout simplement les trier sur l'axe x et construire 2
groupes, un par moitiée.
par exemple :
#include
<algorithm>
stuct Sphere
{
Point c; //
centre de la sphere
float r; //
rayon
Color color;
};
std::vector<Sphere> objects;
{
// ajouter des spheres
objects.push_back({ Point(0, 0, -5), 2,
White() });
...
}
// trier les
les centres des spheres sur l'axe x
std::sort(objects.begin(), objects.end(),
[]( const Sphere& sphere, const Sphere& autre )
{
return sphere.c.x < autre.c.x;
}
);
// couper en
2
unsigned m=
objects.size() / 2;
// groupe 1 :
les objets se trouvent dans [0 .. m)
// groupe 2 :
les objets se trouvent dans [m .. size)
ce n'est pas très compliqué à faire, il suffit d'utiliser le tri
de la librairie standard et de définir une fonction de
comparaison pour trier les sphères. vous pouvez regarder
d'autres exemples sur
cpp.reference.
maintenant que l'on a groupé les sphères, comment savoir que le
rayon ne passe pas dans la région de l'espace occupée par les
objets d'un groupe ? et on ne veut surtout pas tester toutes les
sphères ! on va utiliser un nouvel objet, une boite alignée sur
les axes, pour représenter la région occupée par le groupe. si
un rayon ne touche pas la boite, on sait qu'il ne touchera pas
les objets du groupe ! cet objet s'appelle l'
englobant du groupe, tous
les objets (du groupe) se trouvent à l'intérieur.
on peut représenter la boite avec ses extremités sur chaque axe
: minimum et maximum sur l'axe x, idem pour y et z. il ne reste
plus qu'à construire ces coordonnées à partir d'un ensemble de
sphères et à calculer son intersection avec un rayon.
struct BBox
{
Point pmin, pmax;
BBox( ) : pmin(), pmax()
{}
BBox( const Sphere&
sphere ) :
pmin( sphere.c.x - sphere.r, sphere.c.y - sphere.r,
sphere.c.z - sphere.r ),
pmax( sphere.c.x + sphere.r, sphere.c.y + sphere.r,
sphere.c.z + sphere.r )
{}
};
comment construire la boite
englobante d'une sphère ? sur l'axe x, le point de la
sphère le plus à gauche a pour coordonnée : centre.x - rayon, le
plus à droite centre.x + rayon, idem pour y et z.
comment construire l'englobant
de plusieurs sphères ? il suffit de parcourir toutes
les sphères et de garder sur chaque axe la plus petite et la
plus grande valeur.
le plus simple est d'agrandir l'englobant du groupe pour
contenir l'englobant de chaque sphère.
void BBox::grow( const
BBox& autre )
{
pmin= min(pmin, autre.pmin);
pmax= max(pmax, autre.pmax);
}
BBox box= Box(spheres[0]);
for(unsigned i= 1; i < spheres.size();
i++)
box.grow(
Box(spheres[i]) );
intersection englobant / rayon,
les explications se trouvent dans la
doc
en ligne, dans la partie cube et cube aligné sur les axes.
au final, l'englobant ressemble à ça :
struct BBox
{
Point pmin, pmax;
BBox( ) : pmin(), pmax()
{}
BBox( const Sphere& sphere ) :
pmin( sphere.c.x
- sphere.r, sphere.c.y - sphere.r, sphere.c.z - sphere.r ),
pmax( sphere.c.x
+ sphere.r, sphere.c.y + sphere.r, sphere.c.z + sphere.r )
{}
void grow( const
BBox& autre )
{
pmin= min(pmin, autre.pmin);
pmax= max(pmax, autre.pmax);
}
bool intersect( const
Point& o, const Vector& d, const float tmax ) const
{
Point rmin= pmin;
Point rmax= pmax;
if(d.x < 0) std::swap(rmin.x, rmax.x);
if(d.y < 0) std::swap(rmin.y, rmax.y);
if(d.z < 0) std::swap(rmin.z, rmax.z);
Vector invd= { 1 / d.x, 1 / d.y, 1 / d.z };
Vector dmin= (rmin - o) * invd;
Vector dmax= (rmax - o) * invd;
float rtmin= std::max(dmin.z, std::max(dmin.y,
std::max(dmin.x, float(0))));
float rtmax= std::min(dmax.z, std::min(dmax.y,
std::min(dmax.x, tmax)));
return (rtmin <= rtmax);
}
};
une fois que l'on a trié les sphères, il ne reste plus qu'à
construire l'englobant de chaque moitiée de l'ensemble de
sphères :
// couper en 2
unsigned m= objects.size() / 2;
// groupe 1 : les objets se trouvent dans [0 .. m)
BBox groupe1= Box( spheres[0] );
for(unsigned i= 1; i < m; i++)
groupe1.grow(
Box(spheres[i]) );
// groupe 2 : les objets se
trouvent dans [m .. size)
BBox groupe2= Box( spheres[m] );
for(unsigned i= m +1; i < spheres.size(); i++)
groupe2.grow( Box(spheres[i]) );
et voila, la préparation de la scène est terminée !!
on peut maintenant calculer l'image : à chaque fois que l'on
veut calculer l'intersection des objets avec un rayon, on
commence par tester l'intersection avec l'englobant d'un groupe
puis avec les sphères associées, si nécessaire :
Hit plus_proche;
if(groupe1.intersect(o, d, plus_proche.t))
{
for(unsigned i= 0; i
< m; i++)
if(Hit h= spheres[i].intersect(o, d, plus_proche.t))
plus_proche= h;
}
if(groupe2.intersect(o, d, plus_proche.t))
{
for(unsigned i= m; i < spheres.size();
i++)
if(Hit h=
spheres[i].intersect(o, d, plus_proche.t))
plus_proche= h;
}
return plus_proche;
et ça marche ? ie est-ce que ça permet de gagner du temps sans
produire de défaut dans l'image ?
oui !!
re-voila la courbe de temps de calcul pour comparer :
on peut trier les centres des sphères sur chaque axe et on
constate que le resultat est plus ou moins interressant,
trier sur l'axe z semble le plus rapide sur cette scène...
pourquoi ?
voila à quoi ressemblent les groupes : les sphères changent de couleur
en fonction de leur groupe. chaque groupe est representé par une plaque
sur le sol de la même couleur que les sphères.
en triant sur l'axe X, pas de surprise :
les englobants et les sphères sont bien séparées / groupées. il y a
quand même un petit défaut, ie la petite sphère bleue sur le groupe
jaune, au milieu. les englobants se superposent, pour les rayons qui
passent dans cette zone, il faudra tester les sphères des 2 groupes, ie
toutes les sphères... en dehors de cette zone les groupes sont bien
séparés et les rayons ne testent que les sphères d'un seul groupe. ce
qui permet d'aller 2 fois plus vite, ie on ne teste que la moitiée des
sphères...
voila les groupes pour l'axe Y :
aye ! les 2 groupes sont vraiment superposés, on teste presque toutes
les sphères. les grouper de cette manière ne sert pas à grand chose.
et sur Z :
c'est aussi bien que les groupes pour l'axe X.
maintenant que l'on a coupé en 2 et que les calculs sont au
moins 2 fois plus rapides... on a forcément envie de tester
avec plus de groupes...
si on coupe en 4 sur chaque
axe, est ce que c'est toujours mieux que couper en 2 ?
ah ? faire 4 groupes n'est pas toujours mieux que 2... par
exemple 4 groupes en triant sur l'axe y est moins rapide que
2 groupes sur l'axe z... et le meilleur résultat est de
faire 4 groupes en triant sur l'axe x.
voila les groupes en image : sur l'axe X
les groupes sont bien séparés, et c'est rapide.
par contre pour l'axe Y, c'est moche :
les groupes sont superposés et c'est aussi lent qu'avec 2 groupes...
bilan : utiliser
tout le temps le même axe n'a pas l'air d'être la meilleure
solution et le résultat n'est pas toujours interressant. et
dans une scène différente, il faudra certainement découper
différemment.
au lieu de trier toujours sur le même axe, on pourrait peut
être changer d'axe ? par exemple, on peut faire 2 groupes en
triant sur l'axe x, puis trier chaque moitiée sur l'axe y et
éventuellement encore trier et répartir les objets sur l'axe
z.
comment écrire ce tri
bizarre ?
c'est récursif non ? on trie sur x, on obtient 2 moitiées,
on trie chaque moitiée sur y, on obtient 4 groupes, et enfin
on trie chaque groupe sur z pour arriver à 8 groupes.
on va écrire une fonction récursive avec un axe en
paramètre, et le nombre de découpes à faire, et quelle
partie du tableau d'objets trier :
std::vector<Group>
groups;
void build( const unsigned depth, const unsigned axis,
const unsigned begin, const unsigned end )
{
// creer un groupe s'il ne reste plus
qu'un objet ou qu'il n'y a plus de tri à faire
if(depth == 0 || end
- begin <= 1)
{
// construire la boite du groupe d'objets
BBox box=
BBox(objects[begin]);
for(unsigned k= begin+1; k < end; k++)
box.insert( BBox(objects[k]) );
// conserver les
parametres du groupe
groups.push_back({ box, begin, end });
}
else
{
// sinon trier les centres des sphères sur un axe
std::sort(objects.data() + begin, objects.data() + end,
[axis]( const Sphere& sphere, const Sphere&
autre )
{
// trier sur l'axe x, y ou z
return sphere.c(axis) <
autre.c(axis);
}
);
// couper en 2
unsigned m= (begin
+ end) / 2;
// et recommencer
sur chaque moitie en changeant d'axe. les objets se
trouvent entre begin et m
build(depth -1, (axis + 1) % 3, begin, m);
// idem pour la
2ieme moitiee, les objets se trouvent entre m et end
build(depth -1, (axis + 1) % 3, m, end);
}
}
pour construire les groupes, il
ne reste plus qu'à utiliser la fonction avec le nombre de
découpes à faire (3 pour trier et répartir les objets sur
l'axe x puis y et z) :
build( /* nombre de
découpes */ 3, /* axe */ 0, 0, objects.size() );
on a aussi besoin de se rappeler quels objets sont associés
à chaque groupe en plus de sa boite englobante. on peut
utiliser une structure pour stocker ces informations :
struct Group
{
BBox box;
unsigned begin;
unsigned end;
};
pour calculer les intersections avec un rayon, il suffit de
calculer l'intersection avec la boite de chaque groupe et avec
les objets du groupe en cas d'intersection :
Hit intersect( const
Point& o, const Vector& d )
{
Hit hit;
for(unsigned i= 0; i
< groups.size(); i++)
{
// si le rayon touche la boite englobante du groupe, il
faudra tester les objets du groupe...
if(groups[i].box.intersect(o, d, hit.t))
{
for(int k= groups[i].begin; k < groups[i].end; k++)
if(Hit h= objects[k].intersect(o, d, hit.t))
// garde l'intersection la plus proche
hit= h;
}
}
return hit;
}
et ca donne quoi ?
couper 3 fois récursivement pour construire 8 groupes est
interressant ! et si on continue ? si on coupe 6 fois
récursivement pour créer 64 groupes ? c'est nettement plus
rapide pour beaucoup d'objets, mais plus lent pour moins de 1000 ou 2000 sphères à peu près...
voila les groupes :
pourquoi ? lorsqu'il y a peu de sphères et que l'on crée
beaucoup de groupes, on peut très bien se retrouver à
créer des groupes ne contenant qu'une seule sphère. tester
l'intersection de la boite englobante du groupe +
l'intersection d'une seule sphère est forcément plus long que de
ne tester que la sphère... on peut modifier la création
des groupes pour vérifier qu'ils contiennent suffisamment
de sphères pour rendre l'intersection du groupe toujours
plus rapide. par exemple avec minimum 16 sphères par
groupe :
pour les curieux :
au lieu d'imposer l'axe à utiliser pour trier les sous
ensembles d'objets, on peut aussi choisir l'axe le
plus long / étiré de l'englobant... les groupes construits sont encore mieux séparés.
exemple avec plus de sphères : 6 tris sur les axes x, y et z suivis de nouveau de x, y et z pour obtenir 64 groupes :
il y a pas mal de superpositions...
on choisissant de trier et répartir sur l'axe de l'englobant le plus
étiré, les groupes sont assez différents et, surtout, se superposent
beaucoup moins :
bilan !
et voila, avec quelques lignes de code de plus, et
quelques expériences, on vient de passer de 35s de calcul
pour >8000 sphères à 1.4s !! pas mal, non ?
mais on peut faire encore mieux, en construisant des arbres au
lieu de construire un ensemble de groupes, ce qui permet de
passer moins de temps à calculer les intersections avec les englobants
des groupes :
les explications sont dans la doc en ligne, cf
le
lancer de rayon, ça rame ? ou pas ?
on peut se demander s'il est vraiment nécessaire de faire plus
compliqué. en pratique, c'est tout simplement en fonction du
nombre d'objets dans la scène. en général, on utilise des
triangles pour décrire des scènes que l'on modélise avec
blender
ou un autre logiciel de sculpture 3d. et il faut beaucoup de
triangles pour décrire une "vraie" scène, plusieurs millions ou
dizaines de millions !! les arbres deviennent nécessaires dans
ce cas. c'est encore un "bête" problème d'algorithmes et de
complexité.
voila par exemple une scène de test pour un tp de M2 : 36
millions de triangles, éclairés par un ciel, et sans matières.
sans structure accélératrice de bonne qualité, on ne pourrait
pas calculer cette image en quelques secondes :
