Pete Shirley's Graphics Blog

2011 updates

2011-11-24T06:02:00.000-08:00

This post is an update on various things. First, as many have heard judging from my emails, I had a serious car accident about 5 weeks ago. I am back at work at NVIDIA and am 98% recovered. Lessons: drive carefully and have a car with side air bags :) Also, for those of you in the car market, here is a great site for crash ratings.

Happily, Peter-Pike Sloan just joined me as an office mate at NVIDIA! Feel free to suggest here what problems you think we should work on :) You can note his new affiliation at google scholar, which has a new cool way to fix attributions etc (so please join and update your data): new google scholar. This is part of a trend in NVIDIA hiring the smartest Finns in graphics with Kari Pulli leading our vision and computational photography efforts now!

Peter-Pike and his student Brad Loos have a new paper linked here. I think this is likely to become one of the most influential rendering papers ever, but even if I turn out to be wrong, it's worth a read.

While I was on medical leave I wrote a short post-apocalypse novel for my daughter. It was a lot of fun and I made it a Kindle book (you can read that on anything with a free reader). It's aimed at 12 year olds, but feel free to read it. Here is a link to ebook The Book of Max. Note it is $2.99 and I don't want to make any money off graphics people so email me if you want me to send you a gift chit for it.

New I3D paper posted

2011-02-24T09:27:00.000-08:00

I just posted a recent i3d paper:

paper page

The basic idea on this paper is to take a stochastic sampled set of samples from a stochastic rasterizer or a ray tracer and use a signal dependent blur. The take-away is: you can do a sweep algorithm because front effects back more than vice-versa.

Improved code for concentric map

2011-01-18T09:27:00.000-08:00

If you need to warp points on a square to a disk, many people use Ken Chiu's and my code from jgt:

/* seedx, seedy is point on [0,1]^2. x, y is point on radius 1 disk */
void to_unit_disk( double seedx, double seedy, double *x, double *y )
{

double phi, r;

double a = 2*seedx - 1; >/* (a,b) is now on [-1,1]^2 */
double b = 2*seedy - 1;

if (a > -b) { /* region 1 or 2 */
if (a > b) { /* region 1, also |a| > |b| */
r = a;
phi = (M_PI/4 ) * (b/a);
}
else { /* region 2, also |b| > |a| */
phi = (M_PI/4) * (2 - (a/b));
}
}
else { /* region 3 or 4 */
if (a < b) /* region 3, also |a| >= |b|, a != 0
r = -a;
phi = (M_PI/4) * (4 + (b/a));
}
else { /* region 4, |b| >= |a|, but a==0 and b==0 could occur.
r = -b;
if (b != 0)
phi = (M_PI/4) * (6 - (a/b));
else
phi = 0;
}
}

*x = r * cos(phi);
*y = r * sin(phi);

}

Dave Cline recently sent me a neat trick that uses negative radii and I think is correct. Let me know if you try it. (cut and pasted from his mail)

Vector2 ToUnitDisk(Vector2 O) {
float phi,r;
float a = 2*O.x - 1;
float b = 2*O.y - 1;
if (a*a> b*b) { // use squares instead of absolute values
r = a;
phi = (PI/4)*(b/a);
} else {
r = b;
phi = (PI/4)*(a/b) + (PI/2);
}
return Vector2( r*cos(phi), r*sin(phi) );
}

Annual post

2010-12-31T16:44:00.000-08:00

I am barely getting a post in for 2010. This is my stake in the ground that this blog is the lamest one in the world that is technically still active. I welcome competition.

Onto a post. I think in 2010 we have reached a quiet revolution: we can do tens of millions of rays per second quite easily, which means we can get 16 rays per pixel in a second, even with global illumination. This means we can do progressive preview "well enough". If I were to do an MS thesis today, it would be on a UI for such systems.

A question for the future is whether batch rendering system architecture will start being determined by what is good preview, rather than preview trying to match batch.

Ambient occlusion

2009-12-22T10:51:00.000-08:00

I am doing some reading on ambient occlusion and I would appreciate pointers to recent papers. Here is a TR from Morgan M. on using the analytic form factor equation which is cool. Please reply for other things I should read!

Shadow artifact

2009-12-03T12:32:00.000-08:00

Here is a photo in my living room of a real shadow from windows. The multiple panes give a nasty "artifact". With artificial lighting these are even more common.

Ray tracing BOF at SIGGRAPH

2009-07-31T20:56:00.000-07:00

On Tuesday from 5-6pm in the Sheraton we'll have some ray tracing demos from academics and industry. We should be able to stay in the room after for more demos and talking. Should be an informal affair. Hope to see you there!

A neat trick for ray collisions in nonuniform media

2009-05-15T12:52:00.000-07:00

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

2009-04-08T15:05:00.000-07:00

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

2009-03-31T10:03:00.000-07:00

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

2009-03-25T09:53:00.000-07:00

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

2008-10-09T13:50:00.000-07:00

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

2008-05-23T18:57:00.000-07:00

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)?

2008-01-24T16:14:00.000-08:00

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

2007-11-05T05:40:00.000-08:00

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:

Why is this done rather than using just one algorithm?
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

2007-10-21T05:50:00.000-07:00

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

2007-10-17T06:33:00.000-07:00

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

2007-10-14T20:34:00.000-07:00

One from Jeffrey Howard at Intel

and

one from Dean Calver

Ray Tracing Shading Language

2007-08-24T15:19:00.000-07:00

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

2007-08-13T20:45:00.000-07:00

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!

Results of new poll in

2007-08-10T06:06:00.000-07:00

This poll was better designed but still had one big flaw-- should have had more years-- people clumped in 2011.

For those readers that have not done a ray tracer I recommend Suffern's new book. He covers a ton of details that are not in other books. I saw a copy at SIGGRAPH and it lives up to the potential shown by all those chapters he's let me use in classes over the years.

New poll

2007-08-03T09:06:00.000-07:00

Well people are clearly divided on the last poll. But as pointed out it was ambiguous so here's a new poll that is more straightforward.

2007-07-30T06:28:00.001-07:00

Bram's comments on the last article got me thinking about halftones. This is probably obvious to most people but it was news to me. Without good color profiles and calibrated monitors, you of course can't get predictable appearance. Things like sRGB will help the first but 99% of monitors are not calibrated. But with halftoning you can (assuming LCDs are well behaved about half tone patterns-- CRTs sure are not) get predictable greyscales. For example here are two images with a 25% and a 50% greyscale. (and RE the last article, not which is more of a middle grey). It just doesn't matter what your gamma is (assuming your black point is dark!) to predict what these greys are.

This basic idea is often used for gamma estimation-- the best example is Greg Ward's great gamma image.

Gamma and textures.

2007-07-29T09:35:00.000-07:00

Gamma correction issues are always a pain. A review: given 256 grey levels, it makes sense to make them perceptually uniform. Thus a 20% grey intensity (one fifth the physical intensity of white) should be around 127 as it is perceptually half way between black and white. But what happens when you want to use it as a texture map in a physically based renderer? You need to "de-gamma" the image. If you are using somebody else's renderer, should you do that as a preprocess or might they do it? For my own purposes in that situation I have made three textures of the grey squares in the macbeth color checker chart. The grey square in position 3 from the left (i.e., the third darkest) should look mid-grey in your final render. The 1.0 image has 0.19*255 in that square so it is not gamma corrected (i.e. the byte values are linear in intensity). Of course to make this all more complicated, a renderer might or might not do something different if there is something in the texture's color profile or not.

New poll online

2007-07-21T18:47:00.000-07:00

Here is a poll to narrow down what the non-random sample of people who look at this blog think. I am most interested in the percentage that say never (I am guessing 40%) but also interested in the distribution of the other answers.

Plucker coords considered harmful

2007-07-14T06:52:00.000-07:00

Christer Ericson has a terrific article on why scaler triple products are usually preferable to plucker coords here. I couldn't agree more. Christer has a book on collision detection I have been meaning to order for sometime and his blog content encourages me.

Ratatouille

2007-07-01T06:55:00.000-07:00

I saw Ratatouille with the family this weekend. It is the first CG movie that we all really liked a lot. Brad Bird is really on fire-- I think I liked this movie better than the Iron Giant which was terrific. One thing I especially liked was the lack of big-name actors who are not voice actors. Watch the Toy Story movies and the watch some old Disney (e.g. Jungle Book) and you will see just how much using screen actors for voice talent hurts animated movies. Spongebob and the Simpsons would be awful if they used Tom Hanks and John Travolta. I hope Ratatouille makes a zillion dollars and will show that the director and studio is enough to bring in the crowds.

In addition to being a terrific movie, the rendering passed some threshold for me. Previous CG movies have always looked flat to me, with Shrek 2/3 being better due to their use of indirect bounces I assume. But Ratatouille had even more depth. It is the best looking CG movie I have seen by a long shot. As much depth as live action I think. I have no idea what is different, but I have to suspect global illumination given my prejudices. If it was done with hand-placed fill lights, then the artists must be on performance-enhancing drugs! If anybody knows please reply.

Top utility papers of all time

2007-06-02T19:57:00.000-07:00

This is heavily biased toward rendering, but here are what I consider the most useful papers at present. Many great papers have of course been obviated by improvements so this list is far from a "best paper" list. These are papers worth reading now.

Recursively generated B-spline surfaces on arbitrary topological meshes, Catmull and Clark, 1978. No sign of fading away!

An improved illumination model for shaded display Whitted, 1980. Beware the 1/r^2 mistake but otherwise about as perfect a paper as there is!

Distributed Ray Tracing Cook, 1984. There are some sampling details you can find elsewhere, but all the basic ideas are here.

Ray Casting for Modeling Solids, Roth, 1982. A sweet CSG algorithm.

An Image Synthesizer, Perlin 1985. See his later paper and his webpage for more info on noise.

(more coming later-- suggestions welcome)

My top utility papers

2007-05-28T09:15:00.000-07:00

Some of the papers I have worked on have been influential (e.g., Maciel's I3D one) but most of these are superceded by improvements in subsequent papers, or are mainly of theoretical interest. Here is my current list of the most useful papers that are also easy to implement. I will include Mike Stark's b-spline paper as soon as I find an online copy. Note I will not post a list of papers that were a dumb idea! And also for you new people in the field, take note that half of these were rejected the first time, so never assume the reviewers know what they are talking about (or that they don't! Just read reviews with a scientist's skepticism).

A Ray Tracing Framework for Global Illumination, GI 91. This paper repeats much of Arvo and Kirk's metahierarchy work which unfortunately I wasn't aware of at the time, but also spells out how to manage the various abstract classes in a distribution ray tracer. It also includes a better way to sample the disk, later spelled out in a jgt paper. Most of this stuff is now standard practice, but good if you are new to the field.

Direct Lighting Calculation by Monte Carlo Integration EGRW 91. This paper lays out what to do when you have
more than one light. The follow-on TOG 96 article has some more details, but except for the light grid I think most of them are not worth the added complexity. I do think there has been little subsequent progress on the "thousands of lights" problem which is a shame, but the Cornell folks have recently been doing lots of interesting work on it.

A Practitioners’ Assessment of Light Reflection Models . Pacific Graphics 97. Section 5.1 is especially useful. If you have a bump or displacement map, you really only need a BRDF for the subsurface part, and this one is as simple as they get.

The irradiance volume, CG&A 97. I think that like ambient occlusion this technique has tons of problems but in practice is "good enough".

A Non-Photorealistic Lighting Model For Automatic Technical Illustration, SIG 02. Section 4.2 has all you need to know. Simple hack, seems to work.

Interactive Ray Tracing for Isosurface Rendering, Viz 98. This just plain works. Steve Parker's group still uses the same technique and it shows no signs of losing its utility as it scales so well.

An Anisotropic Phong BRDF Model, JGT 00. This works surprisingly well in practice. It is no good for cloth though-- I would love to see a similar model for cloth.

A Spatial Post-Processing Algorithm for Images of Night Scenes, JGT 02. This still needs to be extended to animation.

Photographic Tone Reproduction for Computer Graphics, SIGGRAPH 02. The first simple model works well on almost all images I have seen. Erik Reinhard et al.'s book is definitely worth picking up for putting this model in context.

An efficient and robust ray-box intersection algorithm. There is also source code at the JGT site. This paper made me hate IEEE FP because of negative and positive zero.

Optimizing Ray-Triangle Intersection via Automated Search, RT06. This is really just Moller-Trumbore 2. I was shocked that the automated search actually worked, and unsurprised the subsequent hand tuning did too.

Image Synthesis Using Adjoint Photons. Graphics Interface 06. This paper is how I now think about path tracing, and it maps directly into some pretty sweet code. The author list is long but Boulos and Morley are really the two principle guys behind it. It takes advantage of the same properties of light as the dual photography paper. Jared Johnson, Solomon Boulos, Austin Robison and I have extended this to linearly polarized light which we will write up soon. I am hoping that a clean extension to fluorescence is also possible.

Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies, ACM TOG 07. I have been advocating the BVH for years-- maybe I am just too lazy to really learn k-d trees. But the real advantage of BVH in my opinion is dynamic scenes. Note that the presentation of the packet-culling is a bit weak. For more details see this tech report.

Meta-h index rankings

2007-05-01T15:15:00.000-07:00

A couple of us have been trying to make a more objective (note that does not mean more accurate!) ranking of CS research departments. We're using the google scholar data combined with the h-index. Still lots of mistakes I am sure. Interesting that Greenberg and Hanrahan are in a dead heat for the highest rating in graphics. Not worth drawing too much conclusion from, but the data is interesting. I'd like to add more universities and research groups, so feel free to send me updates and suggestions.

The data is here

tor@brown siggraph page

2007-04-21T08:40:00.000-07:00

Tim Rowley is once again making his very useful siggraph preview page. I am especially intrigued by the first paper in the list: Solid Texture Synthesis from 2D Exemplars.

Rainbows in clouds

2007-03-23T08:34:00.000-07:00

When the sun is behind you and you look at some rainstorms, you see a rainbow. Since the droplets in a cloud are (I assume) spherical, why don't we see rainbows in clouds? My hypothesis is that they are there, but they are superimposed on a bright cloud where secondary scattering dominates, so the rainbow is just washed out by contrast. Recently I was on a flight around noon and could see below me the shadow of my plane and when the clouds became thin enough that primary scattering probably dominates, there was a perfect circular rainbow with the dark terrain below it. So why no rainbows from thin clouds when the viewer is not on a plane? My guess is the sky behind it is bright. But I am unsure. Another possibility is that what I saw was not a rainbow. But the ring's angular radius looked about right...

Getting to Ulm from the US

2007-03-23T06:10:00.000-07:00

For those interested in attending RT07 (see previous post), I found that going through Frankfurt was really easy-- the airport has a train station that will take you straight to downtown Ulm. If you do that, be aware that train has a reserved seating system (like an airplane or Amtrak). Hope to see you there!

IRT 07

2007-03-19T12:36:00.000-07:00

The interactive ray tracing symposium will be in Ulm, Germany this year:

IRT 07 site

SCHEDULE
JUNE 14, 2007 SUBMISSION DEADLINE
JULY 12, 2007 REVIEWS DUE
JULY 19, 2007 AUTHOR NOTIFICATION
AUGUST 2, 2007 CAMERA-READY COPY
SEPTEMBER 10-12, 2007 SYMPOSIUM IN ULM

Bounding Volume Hierarchy

2007-03-15T04:41:00.000-07:00

If I were trapped on a desert island with only one data structure allowed I would bring my trusty BVH. I have been liking the BVH for some time in spite of all the k-d tree advocates (see the SIGGRAPH 05 notes for a discussion before ray packets were integrated) despite them being "slow". One reason is simplicity-- dividing on objects leads to cleaner implementations than dividing space, and leads to O(N) bounded memory use. My basic software rule is KISS rules! . Another reason is they handle many dynamic models well as has been shown by the collision detection community. It turns out they can also be fast.

Solomon Boulos and Ingo Wald have done a bunch of nice work to packetize a BVH (a ray packet is a set of rays that are traced together). The first optimization (and a huge one) is to descend the BVH as soon as any of the rays hit a box. Maintaining a "first not dead ray" index makes this more efficient. Another optimization is to use interval arithmetic to test a whole packet against a box for a conservative trivial reject. See Solomon's tech report for details (it is really simple even though it sounds fancy, and has a nice mapping to C++ code). Note that both of these optimizations are algorithmic and are mostly orthogonal to SSE optimizations (the descend if one hits optimization makes SSE less helpful).

Finally, the BVH traversal has a low penalty for false positives on boxes, so conservative boxes like you get for moving objects, and well as the lower intrinsic coherency of secondary packets, are not so bad for the BVH.

An important disclaimer: I have previously (in the early 90s) been an advocate of k-d, and later the grid. So maybe this is just the end of the first cycle in my opinion!

It does help if you use the surface-area heuristic to build (that was what it was first invented for in fact-- the BVH). Nobody has ever justified to my satisfaction why the SAH greedy algorithm works so well.

New ray packet paper

2007-03-14T17:15:00.000-07:00

Solomon Boulos and friends have shown that ray packets may work for secondary rays. Check out the first paper here. As much as I hate the software engineering implications that arise with ray packets, I do like that they can make things faster.

Environment map formats

2007-03-10T05:02:00.000-08:00

As there are no "natural" mappings between the sphere of directions and the square, so there is no standard way to parametrize your environment map. In the Original paper by Blinn and Newell, a cylindrical map was used. There are many such cylindrical maps out there and have been used for map projection . For software renderers these are more intuitive than cube maps or the Disk on square paramerterization. In a physically based renderer, you would like to importance sample the environment map. This is easiest if each texel in the map subtends the same solid angle as every other texel. There is one cylindrical map that does this for a given rectangle. A well-known version of this projection is the Peters Projection.

Here's an example projection. The rectangle has parameters [0.1]^2. Let's take u to the angle phi (longitude): u = phi/(2*pi) = atan2(y,x)/(2*pi) assuming your direction (x,y,z) is a unit vector and z is "up". Now we have v = f(z). The simplest such mapping is v = (z+1)/2. Is there area distortion there? What is the area of a given pixel in the texture map. How about the differential area? Let's say that we have a differential square du*dv in the texture map. The area on the sphere of that will be sin(theta) * dtheta(v) * dphi(u).

dphi(u) = 2*pi*du = constant so we can ignore it.

Since z = cos(theta), the other mapping is
(cos(theta) + 1)/2 = v
so differentiating both sides:
-sin(theta)*dtheta/2 = dv

As the differential area is proportional to sign theta, each pixel does have the same solid angle. So this most simple mapping is also a good one! I am not sure why anybody uses any other in a software renderer.

Bye-bye z-buffer?

2007-02-17T06:27:00.000-08:00

The main advantage of the z-buffer in my opinion is that you can stream geometry through it so companies like Pixar can make images of HUGE models. However, in an interactive setting you don't want to do that, so games use pretty small polygon sets that can fit in main memory. The image quality in games will be better once ray tracing is interactive. When will that be?

Intel has just demonstrated a 80 core teraflop chip that looks ideal for ray tracing. According to recent tests, full ray tracing is about 20 times slower than it needs to be on a 2GHz dual-core opteron 870. If Intel's numbers are realistic (we'll have to wait to see what the meory implications are) then the slightly smaller Larabee system will be plenty fast enough for good ray tracing on a single chip.

What does this mean? I predict it means the z-buffer will soon exist only in software renderers at studios, so if you are an undergraduate don't bother learning OpenGL unless you need to use it in a project or job soon. I doubt OpenGL will die entirely due to lagacy issues, but it is not something to learn unless you have to. I speak as a person that spent much of my early years writing FORTRAN code!

Left and right-handed coordinate systems

2007-02-17T06:14:00.000-08:00

We have hit that time in my class again where we set up viewing frames. I continue to shun left-handed from my software, but do see why they are popular.

Let's suppose when looking "into" the screen, you want the y axis to point up and the x axis to point to the right. If you have a right-handed system, then the z axis will come out from the screen. Negative z will go into the screen. If you implement a z-buffer system you will initialize it with z = -infinity. In a ray tracer, the viewing rays will have a negative z component. It does seem "nicer" to have positive z go into the screen. But at what cost?

We can have the y axis point down as is done in many device coordinate systems. That seems worse to me than having z point out from the screen.

We can have a left-handed system. This is equivalent to adding one reflection matrix to your system. Whether that is worth it is a matter of taste. To me it is not, as it confuses me more than the negative-z problem. My brain-washing from many courses 20 years ago and geometric software in the intervening years is all in favor of right-handed systems, while the "which way is z" issue has a lot less congitive cement for me, so I choose to live with negative z going into the screen. Interestingly, the perspective matrix doesn't change either way!

Pixar's Monte Carlo Patent done?

2007-02-09T06:38:00.000-08:00

Pixar patented Monte Carlo for graphics back in the mind-1980s, and for reasons I don't know the patent wasn't issued (#4897806) until Jan 1990. That is in the transitional phase of patent law as I understand it, so it expired 17 years after being issued-- i.e., last month. So is Monte Carlo now fair game in the US? I would think so, but there are also patents 5025400 and 5239624 that last until 2009 and 2011 respectively. They seem to my eye to not really claim anything new that was not in the original patent or the fabulous 1984 SIGGRAPH paper. Anyone have any more informed wisdom on this?

And a not-so-new paper

2007-01-30T05:23:00.000-08:00

The architecture of our rendering system is described in a gi 06 paper. Morley and Boulos should get co-first authors for this paper and deserve the bulk of the credit for the system. I consider this paper a turning point in my thinking about realistic rendering. The reason is that it addresses media as a first class citizen of rendering in a practical way. The system doesn't really know the difference between media and surfaces, and overlapping media are not a problem. So you can add an atmosphere, and then a cloud, and neither the atmosphere nor the cloud need be aware of each other. Brute force is not an insult-- just ask quicksort!

New paper

2007-01-30T05:14:00.000-08:00

I'll indicate new papers we do on this blog with a short post.

My student Margarita Bratkova just completed a paper on her work on panoramic maps. A tech report version is here.

Intro Graphics Course

2007-01-22T10:00:00.000-08:00

For the first time in several years I am teaching Intro Graphics. I am basing this course on the Reyes pipeline as described in the superb paper. Here is my course web page. If you would like to follow along and do the assignments let me know and I'll link to your page. Each week there will be one assignment that will take 1-4 hours or so.

Gamma correction

2006-12-15T05:57:00.000-08:00

Most graphics monitors have a "gamma" that gives a rough approximation to their non-linearity. For example, if we use an internal color space where all of R, G, B are stored as 0 to 1 values, then the physical spectra coming from the red part of the pixel would be:

output_red( lambda ) = max_output_red(lambda) * pow( R, gamma )

where gamma is typically a number around 2.0. Suppose gamma is 2.0. If we want to display a red that is 1/4 the maximum, the R would would store in a file to send to the display would be 0.5.

Note that all of this is not to make up for some "defect" in the monitor. When you use 8-bit per channel color representations, there are only 256 gray levels available. If you space these out so they LOOK evenly spaced to a human observer, that makes a perceptually uniform set of 256 grays and banding is minimized. But since human intensity perception is non-linear (think of the "middle gray" photographer's card which is physically about 1/5 the rreflectance of white paper), this means the monitor must be as well.

Opponent process color space

2006-11-27T10:06:00.000-08:00

For many applications, opponent process color works better than RGB or other common graphics spaces. Opponent color encodes a greyscale channel along with two color channels that range red to green and blue to yellow. A simplified version is:

V = (R+G+B)/3
RG = R-G
BY = B - (R+G)/2

Note that the second two channels run -1 to 1.

Moore's Law and Ray Budget

2006-11-23T06:35:00.000-08:00

Moore's Law states the number of transistors on a chip will rise exponentially, and this has happened fairly steadily. A variation relates to performance, which for CPUs has doubled every two years or so. Another variation is that CPU performance per dollar has doubled every 18 months or so. In practice, the cost law implies you can buy more and better CPUs as time goes on. Finally, screen resolution has been on its own curve that doubles the number of pixels every 10 years or so.

What does this mean for rendering? About 27 years ago Turner Whitted ray traced a 640x480 image at about 1 ray per pixel. For the same money budget we can get about 18 doubling of performance, but we have 3 doublings or so in the number of pixels. So now we should be able to do 2.5 million pixels, each with 2^15 = 32k rays.

A caveat is that we want to use more objects. Fortunately, performance in practice is related to the log of the number of objects.

What does this all mean? The rendering community should raise its intuition for how many rays per pixel we can use in practice. In academics, where it is good to think 5-10 years out, we should be looking at another 6 doublings or so, and a million rays per pixel should then be reasonable.

Another way to compute ray budget is to assume 30Hz interactive ray tracing will become practical at 1 ray per pixel. For an 8 hour batch run using the same infrastructure, you can send 30*60*60*8 = 864k samples per pixel.

Bottom line: batch rendering algorithms should assume a million samples per pixel or so are available, and this should make new algorithmic possibilities practical.

Outer product

2006-11-20T13:08:00.000-08:00

Given two three vectors the "inner" product is:

...........|X|
[x y z]|Y| = [xX + yY + zZ]
...........|Z|

Which we use all the time (dot product). There is
also an outer product:

|x|.................|xX xY xZ|
|y|[X Y Z] = |yX yY yZ|
|z|.................|zX zY zZ|

I'm not sure this is useful for anything in graphics, or even what this thing is operationally.

More on bilinear patch intersection

2006-11-20T06:19:00.000-08:00

Because ray - BL patch involve solving a quadratic, I am concerned there will be "cracking" issues where rays sneak between adjacent patches. A cure for that would be to do four "ordered edge" tests on the ray and the patch edges. More information on such tests in in Andrew Kensler's and my recent triangle intersection paper. Note that Pluecker coordinates are not needed-- the easier to comprehend (for me) triple product test will do the job.

Ray tracing bilinear patches

2006-11-17T19:31:00.000-08:00

I'm going to try to reimplement the displacement map method I did with Brian Smits and Mike Stark a few years ago. A key part of that method is intersecting bilinear patches. Given a ray o+tv and a patch with vertices p00, p01, p11, and p10 we have

o + tv = (1-u)(1-v)p00 + u(1-v)p10 + (1-u)v p01 + uv p11

This is three equations (x, y, and z) and three unknowns (t, u, v). The way Brian and I solved this was to eliminate t by using 2 of the equations and then solve the uv system directly. A similar approach is used in Shaun Ramsey et al.'s jgt paper. This has always been unsatisfactory to me because it chooses an arbitrary ordering of the dimensions. Perhaps a numeric solution would be more robust?

Another possibility is to use Kajiya's old trick. Consider the ray as the intersection of two planes

(p - p0) dot N0 = 0
(p - p1) dot N1 = 0

If you substitute
p = (1-u)(1-v)p00 + u(1-v)p10 + (1-u)v p01 + uv p11

into both the plane equations above then you get two equations in uv of the form:
Auv + Bu + Cv + D = 0 (1)
auv + bu + cv + d = 0 (2)

If you solve one of those for u and then plug it into the other, you get a quadratic in v. That leaves four possibilities of what to do first:

solve (1) for u
solve (1) for v
solve (2) for u
solve (2) for v

There is also a degree of freedom for which planes to use. In any case seems more stable than the three equations, 2 unknowns method above.

Image formats for realistic rendering

2006-11-17T02:47:00.000-08:00

It is remarkable to me that there is no accepted standard for high dynamic range images that is based on CIE standards. Such a format should support XYZ and scotopic luminance V. A big dump with four floats per pixel would work fine, although of course more compressed formats are certainly straightforward. If anyone is aware of such a format that programs such as photoshop can read out of the box, please let me know.

How long before interactive ray tracing is on the desktop?

2006-11-13T09:58:00.000-08:00

Solomon Boulos and friends in our group at Utah have their ray tracer going about 1 frame per second on one core of a 2GHz Opteron 870 with one ray per pixel at a million pixels. This is with full shadows and reflections so is slower than a lot of the numbers you see in the literature. For NTSC resolution (640x480) that would be more like 3-4 frames per second. So we'd need about 8 of those cores for fluid motion. So we are right on the threshold for such low resolutions. If Intel comes through with its 60 core chip, and ray tracing maps to it, then HDTV resolution and some multisampling should be straightforward. The Cell is also a possibility as shown by Carsten Benthin and his collaborators in their recent papers. We could get ray tracing even sooner if an ASIC is built. I don't see why a game box based on ray tracing would not be feasible now.