(Real-time oriented) Raytracing



. is the dot product
* is the multiplication of a vector with a real

Raytracing in general

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 :

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.

ray sphere
	->     ->  ->   ->
	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.

ray tri 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 :

ray tri
	        ->     ->      ->
	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

Real-Time Raytracing

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:

For the bigger quads, I use this size: 16x16. That means I cast a "1" ray every 16 columns and every 16 rows.

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
If CK^2 <= radius*radius, the ray hits the sphere.

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.

Main page

email : Sly