Ray tracing for massively multiplayer online role-playing game (MMORPG)?

I have been playing various video games lately with an eye to which would benefit most from ray tracing in the near term. I tried World of Warcraft a couple of days ago (and so did my daughter so I fear I am out $20 a month for the rest of my life). I speculate that such a MMORPG is perfect for ray tracing now due to 1) it's current emphasis on geometry, and 2) the need to support low-end hardware.

I'd like to get my hands on a dataset from one of these MMORPG games. If anybody has a legitimate copy or is in one of the MMORPG companies and would like to help me find out if this is feasible on current medium-end CPUs, let me know.

Hybrid algorithms

Some movies are made with a "hybrid" algorithm where rasterization is used for the visibility pass and ray tracing is used for some or all of the shading. This raises two questions:

1. Why is this done rather than using just one algorithm?
2. Would this technique be good for games?

First question 1: the reason it makes sense to use both is that rasterization is fantastic at dealing with procedural images. It is the basic Reyes look that is still going strong after almost 25 years: for each patch, dice in micropolygons while applying displacements. If you do a billion micropolygons, no problem as they are never stored. The frame buffer is where the action is. Now suppose you want to do ambient occlusion; the best way to do that is ray tracing. But ray tracing on procedural geometry is slow. Using Pharr et al's caching technique is probably the best known method. But an alternative is just not to apply the displacements and use less geometry as PDI did for the Shrek 2 movie (see their siggraph paper for details). That idea goes back to at least Cohen's 85 paper where detailed geometry is illuminated by a coarse model.

Now question 2: would this be good for games. Nobody knows. I will give two arguments, one for, and one against. The reason this will happen is again procedural geometry. But there will not be so much that it wont fit in core. Still doing it with rasterization will help locality and something like a DX10 geometry shader can be used, and efficient use of caches is where the action is and will continue to be. Now an argument against: Whitted-style ray tracing has good locality and thus such complexity is not needed. Once games use ray tracing they may as well use it for visibility for software simplicity. My bet is on the latter, but I sure wouldn't give odds. If graphics teaches us anything, it is that predicting the future is difficult!

Probabilistic reflection/refraction

In the response to the previous post, Thomas said he would choose probabilistically. If you are sending many rays per pixel I definitely agree this is the way to go. I believe that approach was first suggested in Kajiya's 86 path tracing paper.

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

Note that the weighting is implicit; if you trace reflected_ray a fraction ks of the time, that is just like tracing it every time and weighting it by ks. And as Thomas said, the best images come when you use Fresnel equations.

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.

Two recent views on ray tracing vs rasterization

One from Jeffrey Howard at Intel

and

one from Dean Calver

Ray Tracing Shading Language

Steve Parker and friends at Utah have developed a ray tracing shading language (RTSL) described in this pdf file. I am very excited about this work for entirely selfish reasons. I like ray tracing partially because of the elegant code. Now add ray packets and SSE and voila-- it makes DirectX code look lovely in comparison. The initial results are that ray packets and SSE can be relegated to a compiler with little or no loss of performance. and the code is pretty sweet looking. I have been looking over the shoulder of this project writing some RTSL code and it really seems to work as well as reported in the paper. A surprise to me is that it is much nicer to write than C++ for me because you avoid the blasted C++ header files.

Grid creation paper

Here is a pdf file of a new paper by Thiago Ize, Steve Parker, and myself. It will appear in Ulm at RT07 It does some theory on how to build grids within grids. It is a follow-on to the classic Jevans and Wyvill paper. Its main practical result is that for a two level grid of small triangles, use N**(1/5) subdivisions in each dimension, and then in occupied cells use M**(1/3) where M is the number of primitives in that cell. For single ray code this seems to work quite well. There is also some analysis for long-skinny triangles (like you might get subdividing a cylinder) which says grids are bad at such scenes. That being said, BVH with AABB and k-d are probably even worse!