Raytracing (orienté temps-réel)

• Raytracing en général
  • Notation
  • Intersection d'une sphère et d'un rayon
  • Intersection d'un plan et d'un rayon
  • Intersection d'un triangle/polygone et d'un rayon
  • Réflexions
• Raytracing temps-réel
  • Lancés de rayons primaires
  • Elimination rapide de sphères
  • Toujours plus loin

Notation :

. est le produit scalaire
* est la multiplication d'un vecteur par un réel

Intersection d'une sphère et d'un rayon lumineux

Soit un rayon passant par O(ox,oy,oz), de direction le vecteur unitaire
D(dx,dy,dz)

Soit une sphère de centre (a,b,c) et de rayon r


Nous recherchons l'intersection I(x,y,z)
Il existe 2 méthodes :

Méthode par équations :

Nous avons le système :
	(x-a)^2 + (y-b)^2 + (z-c)^2 = r^2
	x=ox + t*dx
	y=oy + t*dy
	z=oz + t*dz
	avec le vecteur D(dx,dy,dz) de norme 1
Soit :
	(ox+t*dx - a)^2 + (oy+t*dy - b)^2 + (oz+t*dz - c)^2 = r^2
	t^2(dx^2+dy^2+dz^2) + t*2( dx(ox-a)+dy(oy-b)+dz(oz-c) ) + (ox-a)^2+(oy-b)^2+(oz-c)^2-r^2 = 0
D'oû
	A*t^2 + B*t + C=0
Avec :
	A = dx^2+dy^2+dz^2=1 car norme de D=1
	B = 2( dx(ox-a)+dy(oy-b)+dz(oz-c) )
	C = (ox-a)^2+(oy-b)^2+(oz-c)^2-r^2
	det = B^2-4AC = B^2-4C
Si det>=0 alors il y a une/deux intersection(s)
	sqdet = sqrt(det)
	t1 = (-b-sqdet)/2
	t2 = (-b+sqdet)/2
	si t1<0 alors t1=t2
	si t2<0 alors t2=t1
	t = min(t1,t2)
	P(x,y,z) = O(ox,oy,oz) + t*D(dx,dy,dz)

Méthode géométrique :

	 ->
	|D | = 1
	    ->   ->
	OK = D . OC
	CK^2 = OC^2-OK^2
Si 0<CK^2<=r^2 alors il y a intersection
	->  ->
	OI = D*(ok-sqrt(r^2 - CK^2))

Intersection d'un plan et d'un rayon lumineux

Soit un rayon passant par O(ox,oy,oz), de direction le vecteur unitaire D(dx,dy,dz), et le triangle ABC. N est la normale unitaire du triangle.

-> -> OO' = OA . N -> -> OI = OO'/acos( (OO' . D)/OO' ) -> -> OI = OI * D

Intersection d'un triangle/polygone et d'un rayon lumineux

Soit O la caméra, D la direction du rayon de norme 1, et ABC un triangle.

Avec la méthode précédente, on trouve l'intersection I entre le rayon et le plan (ABC).
On veut maintenant vérifier si l'intersection est à l'intérieur du triangle.

Méthode 1

Pour cela on précalcule A', B', C' les bases des hauteurs du triangles, et G le barycentre.

L'intersection est dans le triangle si : -> -> A'I . A'G >= 0 -> -> et B'I . B'G >= 0 -> -> et C'I . C'G >= 0

Méthode 2

Cette méthode fonctionne avec n'importe quel polygone et risque d'être plus rapide que la méthode précédente dans le cas de triangles.
Soient A(1),...,A(n) les différents points du polygones.

Pour tous les triangles I,A(i),A(i+1), calculons l'aire algébrique de chaque triangle :

-> -> -> Aire*2 = N . ( IA(i) * IA(i+1) ) -> -> -> Aire*2 = N . vecteur_constant Si toutes les aires sont de même signe, l'intersection est dans le polygone.

Réflexion en un point P, de normale N vecteur unitaire

La nouvelle direction est :
-> ->      ->  ->   ->
R = D - 2 ( D . N) * D
Il ne reste plus qu'a tracer un nouveau rayon depuis P de direction R

Lancés de rayons primaires - depuis la caméra :

Calculez un buffer de poly_id : pour chaque pixel, indiquez quel polygone/primitive est affiché(e) et quelle couleur est extraite de la texture - en calculant un sbuffer par exemple. Puis lancez un rayon sur le bon polygone seulement pour chaque pixel.

Ou alors, utilisez un quadtree.

1---2---1---2---1---2---1
|.......|.......|.......|
|.......|.......|.......|
|.......|.......|.......|
2...2...2...2...2...2...2
|.......|.......|.......|
|.......|.......|.......|
|.......|.......|.......|
1---2---1---2---1---2---1

• Lancez les rayons "1"
• Si quatre rayons "1" touchent le même objets, interpolez entre eux (soit la couleur, soit la normale en recalculant la couleur).
• Sinon subdivisez en quatre le quadrilataire, et lancez les rayons "2" nécessaires
• Et ainsi de suite...

Elimination rapide de sphères

Pour les rayons primaires:

Calculez une cullbox 2D (un carré englobant la sphère à l'écran:
C'est juste un produit de Thales, x2d = focale*X/Z et y2d = focale*Y/Z. avec -1.0<= x2d ou y2d <= +1.0.
Changez de repère pour avoir des coordonnées en pixels et votre cullbox est prête.

Puis vérifiez avant de lancer un rayon sur une sphère si le pixel actuel est dans la cullbox de la sphère.

Pour les rayons secondaires et les rayons primaires passant la cullbox:

 ->
|D| = 1
     ->   ->
OK = D  . OC
CK^2 = OC*OC-OK*OK

Et toujours plus :

Utilisez une structure comme les arbres BSP (sous leur forme générique, ou de grille - octree, grille avec poids...), l'encapsulation de plusieurs objets proches dans des sphères... pour accélérer la détection de l'objet touché