A neat trick for ray collisions in nonuniform media

Mattias Rabb showed me a really neat trick a few years ago that this post will share. He found it in a paper I had never seen by Coleman in 1967. Kudos to Mattias for not only finding this paper, but managing to find this trick in it (I would not have understood it had he not told me what was there). It gives a way to compute an unbiased random hitpoint for a light particle and a nonuniform density.

Recall that for a uniform density volume this can be done analytically. Given a canonical random number X (e.g., a call to drand48()), and a medium with interaction coefficient s (the probability of a collision in a small distance d is sd), we have distance = -log(1-X)/s (see Dutre et al., p 241 for a derivation of this classic result).

In a photon tracing program we would use this as follows:

X = drand48()
d = -log(1-X)/s
newposition = rayorigin + d*raydirection // assumes unit length direction
scatter or absorb

No suppose s(x,y,z) is a function of position like a call to noise or whatever. Usually we would resort to ray maching with small steps that assume s is locally constant. This is a pain in the same family as ray epsilons. But the Coleman paper has a lovely trick when s(x,y,z) is always less than a known smax. Pretend the medium is all constant smax, take a step as above, and sometimes reject the result:

d = 0
while (1) {
X = drand48()
d += -log(1-X)/smax
Y = drand48()
newposition = rayorigin + d*raydirection
if (s(newposition)/smax > Y) break
}

This takes a bunch of random steps and is unbaised (I would love to see a clean proof of this-- I don't follow Coleman's). I think it saved us something like 5X in our adjoint photon tracer.

EGSR 2009

The deadline for my favorite conference is coming up:
http://iiia.udg.edu/EGSR2009/
From Salt Lake to Barcelona is less then $900 (and I didn't look hard-- maybe much cheaper) so this looks like a feasible year to go!

HPG 2009

The new HPG 2009 conference should be an excellent place to submit papers now:

http://www.highperformancegraphics.org/

Deadline in about a month.

Andrew Kensler's new ray tracer

The latest in a long and distinguished line of short ray tracers. This time with blur!

http://www.cs.utah.edu/~aek/code/card.cpp


Clearly Andrew needs to start doing some demoscene.

PS-- I am about to head of to EPGPV and EG. Hope to see some of you over a beer and pretzel in Munich!

Double-sided dielectrics for ray tracing

No, neither I nor this blog is dead yet.

Sometimes ray tracing models will take a thin dielectric (like a car windshield) and represent it with one surface. If we assume this dielectric surface is locally planer, then the direction of the ray will not be changed by the double refraction, but it will be offset. This is shown in the image above. Our challenge is to calculate the vector o in the figure. The new origin of the ray will just be hit_point+o.

The thickness t is provided by the model, possibly with a texture. First let's find a unit vector parallel to o by subtracting off the portion of v in the direction of n:

a = -normalize(v - dot(v,n)n)

Now we need to find the distance that is the length of o, which is q-w. We can see that

q = t tan(Theta).

Similarly,

w = t tan(Theta')

Snell's law tells us that

sin(Theta) = ref_Idx sin(Theta').

Assuming v is a unit vector we also have

cos(Theta) = -dot(v,n)

That allows us (with a bunch of sqrts) to get all the sines and cosines we need above.

New pastures

It has been months since my last blog post. My excuse is that I have left my professor job at the University of Utah and joined NVIDIA. I’ll still be based in Utah and will be an Adjunct Prof at the U. Many people have been surprised that I have left a job-for-life that I enjoy, and that I have gone to a GPU company. Given that I went to school at age 5 and have never left, and that I have have been a ray tracing guy for the last 20 years, I can understand their surprise. This post is to explain why I’ve made this move. Historically, graphics people have self-selected into interactive and batch programmers based largely on whether responsiveness or visual quality was more important to them, and I’ve been squarely in the latter category. However, recent GPU graphics has gotten close to the line where I find the visual quality compelling, and I believe it will soon be possible to cross that line. I think the place to help cross that line is in industry given how close this line is, and given the need for development in the context of compelling geometric models.

As for NVIDIA, the main question I asked myself to help make the decision was expressed in my last blog post; are hybrid methods a natural architecture for interactive graphics? After much contemplation, I have concluded the answer is yes. For complex geometry rasterization and hi-res screens has many advantages over ray tracing for viewing “rays”, and the solution already works. It is yet to be shown that ray tracing can be similarly efficient for such sampling rates, and I am skeptical that a magic bullet will be found to change that. I also believe that most lighting effects missing from current games do not need such high geometric complexity give the success of PDI’s renderer which uses lower LODs for illumination. That being said, is NVIDIA hardware flexible enough to support interesting hybrid algorithms? Well, I took the job :) While I cannot yet say if and when NVIDIA is going to use ray tracing, I am confident that we will use whatever is best for getting great interactive graphics, and if ray tracing is part of that solution we will make it fast. NVIDIA is supportive of me continuing this blog so I hope to get back on track with posts soon.

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.