gray

gray

About Gray

Gray (Greiners Raytracer) is a hobby/research project of mine. It is a program that simulates light to produce computer generated images. The technique used is called ray tracing, where a large number of rays are cast against mathematical 3D models to simulate the interaction between light and materials. The result is beautiful computer generated images, like the ones we are used to see in special effects in movies.

Epsilon

ProgrammingPosted by Søren Greiner Wed, February 24, 2010 13:26:46
A reoccurring problem in ray tracing is unwanted self-intersections when a ray bounces off a surface. Take for instance a mirror defined as a plane. When a ray is cast towards the mirror a hit point is computed on the mirror surface. But when we use floating point numbers, the exact point cannot always be represented as a floating point number. The computed hit-point may therefore lie on either side of the mirror offset by a small error. This causes problems when computing a reflected ray. If the hit point ends on the back side of the mirror, the reflected ray may hit the same mirror again instead of tracing away from the mirror.

The quick fix is to move the hit-point a small amount along the normal vector (in the incident direction) of the surface. This is what I usually do:

vOffsetHit = vHit + vNormal*0.00001

But why 0.00001? Originally I chose this number because it was larger than typical errors. This fixed some of the artifacts in my images where small holes appeared in my geometry.

However this number only works if the scene geometry has a magnitude around 1 or so. What if the scene geometry is very large? Perhaps the mirror is placed at coordinate 100000,100000,100000. In this case an offset of 0.00001 is too small. Due to limited precision in floating point numbers (~7 significant decimal digits) 100000+0.00001 gives the number 100000, where 100000.00001 was expected.

The solution is to compute a scaled epsilon value that guarantees that x + epsilon > x. I wrote a function called Epsilon that does exactly this. This is how it is defined:

// Difference between 1.0f and the minimum float greater than 1.0f
#define FLOAT_EPSILON 1.19209289550781e-007

float Epsilon(float x, float scale)
{
float f = FLOAT_EPSILON*scale;
return fabs(x)*f;
}

x is the number to compute epsilon from. scale is used to scale epsilon and must be > 1.

This is how it can be used:

vHit.x = some number
vOffsetHit.x = vHit.x + Epsilon(vHit.x, 10)

Now we have a guarantee that vOffsetHit.x is larger than vHit.x with an amount at least 10 times larger than the smallest epsilon.

Simple really...

I have implemented a small unit test program that tests this function and it seems to be working well:

Epsilon.cpp



Fill in only if you are not real





The following XHTML tags are allowed: <b>, <br/>, <em>, <i>, <strong>, <u>. CSS styles and Javascript are not permitted.