(Real-time oriented) Raytracing

• Raytracing in general
  • Notation
  • Sphere - ray intersection
  • Plane - ray intersection
  • Triangle/Polygon - ray intersection
  • Reflexions
• Real-Time Raytracing
  • First ray hits
  • Quick sphere skiping
  • Going further

Notation

Intersection between a sphere and a light ray

A ray is a point : O(ox,oy,oz) and a direction : unit vector D(dx,dy,dz)
A sphere is : center (a,b,c) and radium r

We are looking for the intersection point : I(x,y,z) There are 2 ways :

• Equation way :

  
  We have :
  	(x-a)^2 + (y-b)^2 + (z-c)^2 = r^2
  	x=ox + t*dx
  	y=oy + t*dy
  	z=oz + t*dz
  Which mean :
  	(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
  So
  	A*t^2 + B*t + C=0
  With :
  	A = dx^2+dy^2+dz^2=1 car D norm=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
  If det>=0 then there is 1/2 intersection(s)
  	sqdet = sqrt(det)
  	t1 = (-b-sqdet)/2
  	t2 = (-b+sqdet)/2
  	if t1<0 then t1=t2
  	if t2<0 then t2=t1
  	t = min(t1,t2)
  	P(x,y,z) = O(ox,oy,oz) + t*D(dx,dy,dz)
  

• Geometric way :

  
  	 ->
  	|D | = 1
  	    ->   ->
  	OK = D . OC
  	CK^2 = OC^2-OK^2
  If 0<CK^2<=r^2 then there is an intersection
  	->  ->
  	OI = D*(ok-sqrt(r^2 - CK^2))
  
  

Intersection between a plane and a light ray

A ray is a point : O(ox,oy,oz), and a direction : unit vector D(dx,dy,dz) ABC is a triangle and N is its unit normal.

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

Intersection between a triangle/polygon and a light ray

A ray is a point : O(ox,oy,oz), and a direction : unit vector D(dx,dy,dz). ABC is a triangle

With the previous method, we find I the intersection of the ray and of the plane (ABC). We'll now check if I is inside the triangle ABC.

Method 1

For this we need to precompute A',B',C' the base of the "height" line of the triangle (see figure), and G the barycenter of the triangle.

The intersection is inside the triangle if : -> -> A'I . A'G >= 0 -> -> and B'I . B'G >= 0 -> -> and C'I . C'G >= 0

Method 2

This method will work for any polygon, and can even be faster than the previous method in the case of triangles.
Let A(1),...,A(n) be the vertices of the polygon.

For every triangle I,A(i),A(i+1) we'll check if its algebric area is positive :

-> -> -> Area*2 = N . ( IA(i) * IA(i+1) ) -> -> -> Area*2 = N . const_vector If every area have the same sign, I is inside the polygon.

Reflexion at point P, which normal is the unit vector N

The new direction is :
R = D - 2(D.N)*D
Just trace a new ray from P with direction R, and add its color

Primary rays - from camera

Compute an poly_id buffer : for each pixel, find which polygon/primitive is displayed and get its color from the texture - using for example sbuffer . Then trace a ray only on the proper polygon for each pixel.

Or use a quadtree:

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

• Cast the "1" rays.
• If four "1" rays touch the same object, interpolate between them (either the color, or the position+normal and recompute the color).
• Else split the quad in four quads, and cast the required "2" rays. If a quad gets too small (ie: 4x4), raytrace all rays inside.
• And so on, split again and again when required.

Quick sphere elimination

First generation rays:

Compute a 2D cullbox (2D square around the sphere on the screen):
That does just require a Thales product, x2d = focal*X/Z and y2d = focal*Y/Z. with -1.0<= x2d or y2d <= +1.0. Do alter x2d and y2d so that they are between 0 and the width or heigh of the screen.

Then check if a pixel is inside the sphere's cullbox before casting a ray to it.

For accepted first rays and other rays:

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

Further on :

Use a BSP tree (in the classic way, in the grid forms - octree, weighted grids...), put sphere around near objects to find quickly which group of objects are not hit by the ray.