Wednesday, October 17, 2007

Ray tree pruning

A time honored way to speed up your glass is to do "ray tree pruning" and you should do it if you aren't already. The way Whitted originally implemented his paper was like this:

color trace(ray r, depth d)
color c
if (r hits scene at point p)
c = direct_light(p)
if (depth < maxdepth)
c += ks*trace(reflected_ray) + kt*trace(refracted_ray)
else
c = background(r)
return c

If you hit glass that will be two branches per recursion level. The first efficiency improvement would be to only send the rays if ks and kt are non-zero. But that would not help you for glass. Instead, you need to kill whole paths down the recursion tree once they are sufficiently attenuated. For example, if kt=0.05, then after 3 transmissions the coefficient is (0.05)^3 and can be ignored. To implement this, you need to change the call to include an attenuation argument:

color trace(ray r, depth d, float atten)

and add

if (depth < maxdepth)
if (atten*ks.max_component() < maxatten)
c += ks*trace(refected_ray, atten*ks.max_component())
if (atten*kt.max_component() < maxatten)
c += kt*trace(refracted_ray, atten*kt.max_component())

You will be amazed at how much faster a scene like Whitted's glass ball is.

5 comments:

Unknown said...

If you're clipping based on attenuation, then why even bother with the depth limit on the recursion?

In my ray tracer, I've replaced the depth limit with an attenuation term rather than adding one. Works as long as you don't have a fluorescent material that "amplifies" the light.

Peter Shirley said...

Hi Adrian.

In real physics I agree, but in a program I think you should plan for a ray to sneak inside an object or to get some floating point error that allows it to internally reflect until your stack overflows. If the viewer chose a viewpoint inside a glass ball I think this would even happen for some viewpoints without a bug! Of course, if you always added some exponential attenuation that might accomplish the same thing as max depth.

Another reason for max_depth-- good for approximate fast renderings.

Unknown said...

the way i'd do glass is to first compute the fresnel coefficients for reflection and refraction, and probabilistically do one based on that.

Michael said...

Using just a single attenuation value is probably not the best way to do this. Imagine a fully red glass (color 1,0,0) in front of a blue glass (color 0,0,1). Always using the max component won´t kill the ray at all while using the max component of the product of the colors will kill the ray instantly.

Unknown said...

Yes, this one's a big win. I believe it was first mentioned in:

A Testbed for Realistic Image Synthesis, R. A. Hall, D. P. Greenberg, IEEE Computer Graphics & Applications, 3(), November 1983, pp. 10-20.

(Or it was in Hall's thesis.)

Eric