ngons: Are they really that evil?

Playing around with polygons and trying to code them, I've seen a variety problems that can occur working with polygonal geometry. More than once I've hit a snag in my program and I scratch my head and think, "How do the big guys handle that?" Then I crack open Maya, build the same topology and see it break there as well. What I've come to find is different modeling applications handle polygons in different ways--some are deficiencies and some are just design choices.

Problem with Tris and Quads
A polygon as most people know requires at least three points. This of course makes a triangle. A triangle is an ideal planar figure as the three points--assuming they all don't lie on the same line--form a plane. No matter where you move the points, they will always form a plane. Interpolating attributes between the points is easy. Triangles are simple to rasterize, ray trace, and are pretty much universal across modeling applications.

In geometry a polygon (pronounced /ˈpɒlɪɡɒn/) is traditionally a plane figure that is bounded by a closed path or circuit, composed of a finite sequence of straight line segments (i.e., by a closed polygonal chain). -http://en.wikipedia.org/wiki/Polygon

Stepping up to four points already begins to create problems with modeling applications. This is because unlike a triangle, not all four points have to lie on the same plane. The modeler can be restrictive to the user requiring all points to lie on the same plane (making it extremely difficult for an artist), or it can make certain assumptions about how to render a non-planar quad. Sometimes this may or may not be what the artist wants. There's not really a set definition of how to manipulate/render a non-planar polygon.

Take a look at the examples below. In the first two images, the user grabs two vertices at opposite ends of the cube and pulls down forming what looks like a roof. For many people, this maybe what they expect as the program--Blender in this case--just treats the quad as two triangles with the long edge going across the two unselected vertices. This may seem perfectly acceptable, but look at the second example. Now we grab the other two vertices and pull down. One might look at the first example and now assume that it will also form the house, but instead it forms some kind of double-steeple with a rain gutter in between.

Pulling down to opposite vertices

Pulling down the other two vertices



What's going on? Well, Blender just knows it has to render this quad face, so it looks at the first vertex on the face and says, "Okay, let's render these as triangles since rendering non-planar quads doesn't make sense and a planar quad is just two triangles anyway." So it looks at the next two vertices around the face--the one that was pulled down and the opposite unselected vertex and says, "That's three" and renders a nice roof. If you pull the other two vertices down like in the second example, Blender starts rendering at the same vertex as before, but goes up to the unselected vertex, and then back down to the other selected vertex forming that steeple/trench.

Here's the question. Which one is correct? If you pick one and assume that's what the program should always do, you've restricted the artist to never being able to make that other shape easily. You may think Blender's not very smart not knowing how to render non-planar polygons, but that wouldn't be fair. There's no rule. If some program makes a certain decision about how to render that, it's just how they want to deal with it. It doesn't make their solution correct, or Blender's solution incorrect.

You may be thinking, "Hrmm, I bet I could write an algorithm that changes around the order of the rendering to guess what the artist wants...". It's been done. If you go into Maya and try doing this example, you can actually get the model to "pop" in between these two examples as Maya tries to figure out by some threshold what you're trying to do. Is Maya right and Blender wrong? Like I said there's no rule for handling non-planar polygons. If you really want to bend a quad into a two triangles with guaranteed results, just make the two triangles before you bend them (as shown below). Now there's no ambiguity at all. The computer doesn't have to make any decisions about bending anything. You're just moving the points on the triangle, and it knows how to do that no questions asked.

Not only do quads introduce problems like these when they're non-planar, but happens when the quad is not convex? In the example below, I have pulled a vertex over to so the resulting polygon is concave. If I grabbed a different vertex, the renderer might have done what you expencted rendering two nice triangles inside the quad. But because I grabbed that vertex, the renderer made a triangle where it shouldn't have and you see visual tearing, where one triangle is sitting on top of another.

Here you might say, "Well, if the Blender programmers made their modeler smarter, they could just look at that quad, see that it's concave, and render it with the correct triangles". That's certainly a valid point, but that takes processor time to figure out. Assuming the polygon is planar, which as I already stated is iffy, the algorithm has to look at the quad and see how to best divide it up without going outside the polygon. Maya does this and it may seem like a great idea, but that's processing power that could be doing other things like rendering larger meshes. Which would you prefer?

No standards across programs
Not only does the designers have to decide and implement these rules, but what happens when the model leaves the program? Bending a quad may give you what you want in the modeler, but there's no guarantee the program where you're sending that quad handles it the exact same way. Take a ray tracer, for instance. I've never seen an ray intersection that handles a generic four-sided polygon. It will usually divide it up into triangles as would a rasterizer. There's no "correct" way to do handle non-planar polygons or concave polygons, so when you decide you want to model that way, you might get bitten later on. Some programs might handle these issues better than others, but they are just making an arbitrary decision.

N-gons are evil
I have shown that just by moving from a triangle to a quad opens up a whole set of problems--one little extra vertex now allows an artist to create non-planar, concave polygons. "Yuck!", I hope you are saying to yourself. What about ngons? ngons are typically what people call polygons with five or more sides. They have all the same problems as quads, except with infinitely more bad situations. For someone whose never used ngons, he/she may ask, "Well, why don't see just stay far away from ngons to avoid the problems?". This is yet another design decision. Here are a somes reasons why ngons should or should not be included in a modeler.

ngons are good

• "clean" topology - when working with a polygons that are going to be planar anyway, ngons don't display a bunch of edges across it, which makes the model look a little cleaner
• nice cuts - some tools create n-sided polygons. Although they may create poor geometry, they can be extremely convenient
• power to the artist - allowing ngons in modelers gives the artist a chance to work more efficiently even though it may screw him/her up later. Plus, once they're ready to export, they can always clean the mesh up afterwards (some artists prefer this workflow)

An image I stole from the Blender forums. The extrude-vertex tool creates two visible ngons I've marked with a red dot. These ngons are very "clean" in the sense that they are planar, convex, and thus will break down to triangles without any funky results

Two images I stole from blender3darchitect.com. The artist has replaced the distracting quads over the arches with a simple concave ngon. It is debatable whether it is more pleasing to the eye--the former to me looks like keystones. The artist will probably have to clean that up somehow (like triangulating it) before exporting the model

ngons are bad

• no standards - there are no guarantees that ngons will import/export as expected. I have read that Cinema 4D, for example, supports ngons, but triangulates ngons on import
• subdivision - working in realtime subdivion is very popular now a days, but how do you subdivide an ngon? Most algorithms require very strict rules for mesh topology like the popular Catmull-Clark subdivision, that requires all quads. People have implemented/published additions to these algorithms to make them more robust, but it's up to the designer to pick which one is best for them
• tool support - ngons require more complex data structures than quads or triangles meaning tools that work with the polygon have to be smarter--some tools just break or don't handle ngons
• processing power - nothing is for free and at some point the program has to decide how to render the ngons to the screen. If it's a concave polygon, the program has to divide it into triangles that are contained in the original polygon. Would the artist rather be spending this processing power on something else?

What's the conclusion?
I can't take sides with how important or useful ngons are. I've heard several times that once an artist models with ngons, it's hard to go without them. I'm not sure if that's a good thing or not. ngons seem to make things easier at certain stages of modeling, while they often need to be cleaned up later in the pipeline. Working with just triangles and quads can be extremely difficult in many situations, but several powerful tools like loop cut and loop select only work because of the special nature of quad loops, which is why some artists try to keep the model as quads as long as possible.

Below is a screenshot from CGSociety, which has a wiki comparing the various modeling programs. It's apparent that nearly every application now supports ngons. zBrush is excused since I'm sure it has insane data structures to handle what only zBrush can handle, and Blender supposedly has ngon support on the way, so regardless of whether an artist needs it or should use it, support for them is/will be pretty much standard.

Table of modeling applications that provide ngon support taken from CGSociety's wiki

Next-Gen 3D Rendering Technology: Voxel Ray Casting

Tom's Hardware recently did a follow up to their ray tracing article specifically on Voxel Ray Casting. I thought it was a good review of the technology and did a good job presenting the pros and cons associated with it.

One of the most critical bottlenecks in any rendering technique is managing coherency. The scene in a typical game may contain gigabytes of geometry and textures and it is important most of the time isn't wasted pulling the data in and out of the cache.

No graphics article/post would be complete without at least one comment in the discussion section referencing the Matrix and how it's so close to becoming a reality. I guess that's optimistic considering we can't even predict the weather or have self-driving cars. I did see a few other comments, which I thought deserved a bit more follow up.

kikireeki 10/21/2009 7:28 PM
What happened to Normal Mapping?

Normal mapping is used when one wants to render limited geometry but apply a variety of normals the the otherwise flat surface giving the illusion of detail. The point of this is to use really high amounts of geometry to do the job. Normal mapping can't fix jagged silhouettes, for instance. Each corner of a voxel has a stored normal value, and since these voxels will be less than a pixel when evaluated, the interpolated normal between these eight points is satisfactory.

spiketheaardvark 10/21/2009 8:43 PM
I wish the article discussed how such a system would handle transparent objects and refracted light sources, such as an image of a glass of water.

It doesn't. Big disappointment, I guess. If it could, it would be sparse-voxel ray tracing, wouldn't it? The idea of ray casting is you only fire rays from the camera directly into the scene. No secondary rays. A big reason ray tracing is so slow is when secondary rays are fired to other parts of the scene for things like transparency, reflection, and shadows, you have to go get that geometry to intersect against and shade (including fetching the associated textures). This is really difficult when rays are shooting off at random directions requiring everything to be paged in just to render a metallic sphere. If you have multiple reflections around the scene, there's going to be a lot of paging going on. Don't fire off enough rays for something like color bleeding and you get something like this:

Ray casting like rasterization is very coherent. With rasterization the applicaition streams in geometry piece by piece and hopefully only has to do it one time. With ray casting, part of the octree that fits in a given area of the screen can be paged in, ray casted, and paged out of memory. If you want to add secondary effects, many secondary rays leave the paged in part of the octree and need the geometry for that part of the scene brought it. And another secondary ray from the next pixel might shoot into a different part of the scene requiring another geometry fetch. That's why voxelized octrees won't get us any closer to ray-tracing-style secondary effects. It's just to give us more geometry. It's just to give us more geometry! IT'S JUST TO GIVE US MORE GEOMETRY! I'm happy enough with that. Even if it is only static geometry.

Here's Jon Olick's demo video from Siggraph 2008. If you're wondering what those funky blocks are, those are the individual blocks of the octree paged in and out of memory.


Adroid 10/22/2009 1:32 AM
Great Article. Its an interesting point that about 10 years ago the whole market went to polygons instead of voxels. Who knows where we would be if the industry went that direction. Nowadays processors are becoming more and more capable of such a feat.

I think the sweet spot is finding a mix of both... Maximizing both processor and GPU use in games. Its a heck of alot of programming, but thats why they get paid the big bucks to make games we love right?

If the whole industry went this way 10 years ago we'd be playing a lot more beautiful chess games and fewer 1st-person shooters. I was at the conference when Jon Olick was presenting. Of course, someone had to ask the question, "How do you handle animations and rebuild your octree?". He simply replied that they're not out to solve a problem ray tracing researchers have been investigating for years. This only works on static geometry. This only works for static geometry! THIS ONLY WORKS FOR STATIC GEOMETRY! To get these voxels, they model in polygons, then sample them into voxels. To do this in a game with animations, they'd have to animate the character in polygons, voxelize, and render again to get all the data back. And from what Jon Olick has mentioned, voxelizing is too slow for real time and has to be precomputed.

The idea certainly is to find the sweet spot. Rasterize animated geometry and ray cast static geometry. Developers can still model and rig everything with polygons and the engine can voxelize anything declared static. Voxelized objects lose the ability to deform, but are rendered faster. They can use the same surface shaders and even the same shadow maps, too. It can be completely transparent to the developer using the engine besides choosing what's static and what's dynamic. If the guys excitedly pushing this say it's not going to completely replace rasterization, they have no reason to lie, right? I personally still think the GPU is still best suited for rendering as most games now like Crysis are CPU-limited already doing other things like AI, physics, etc.

Here's the full pdf of Jon Olick's slides. They're pretty complex and don't have many shiny pictures, but it was a great presentation. The best part of all this is the technology is available now on current hardware and will get more prominent as more and more developers become proficient in it.

Step into Interactive Ray Tracing

I overheard someone commenting recently that ray tracing was the next logical step in interactive rendering. Although this is surely a popular idea, he continued that switching to a ray tracer soon before secondary effects (like reflections and refractions) were practical would be worthwhile. His argument was that since ray tracers can use the same graphical "hacks" like environment maps and shadow maps to match rasterization, when more performance comes down the road the developers could just swap out a given hack with the physically-accurate equivalent. Why not, right? Well, that's a tough pill to swallow.

Games are bottlenecking
The fact of the matter is that interactive rendering--especially in games--is a very performance-intensive medium. As opposed to most applications like a word processor or database, every AAA game title is developed to suck every last drop of performance out of the CPU and GPU. If the developers are only getting 50% CPU/GPU utilitization, they naturally would tweak the game to get more visual quality out of the system. This is natural considering most game players aren't multi-tasking between applicationss while running these programs and can dedicate the hardware to that one game.

This is the problem with transitioning to ray tracing. To move to ray tracing while providing the same quality effects adds more work to an already bottle-necked system. Ray tracing interactive scenes is inherently slower for the same perceptive quality. Optics, BRDFs, and light-transport-related topics have been researched for hundreds of years. Today's ray tracing researchers are focused on speed. Problems include rebuilding dynamic acceleration structures, corralling rays into coherent packets, and getting all the operations to march in lock step on these SIMD-plentiful architectures. It's all about performance. The only time games will implement ray tracing is when they can do the same important effects as efficiently as rasterization. Using rasterization techniques in ray tracers is still slower then rasterization: one still has to build acceleration structures, one still has to do crazy optimizations, and one still has to deal the incoherent texture and geometry accesses inherent in ray tracing. So why on Earth would any developer opt for a ray tracer with half the performance for the same graphics just so fifty years down the road, it's easier to add secondary effects? Blah.

Rasterization's Bang for the Buck
I've stated this before, but many production companies still use rasterization because they care about visual quality. Pixar and Dreamworks, for example, still rasterize the scene first before adding any secondary effects. After all these years these companies are still using basic shadow maps to shade direct illumination. And it's their business to make pretty pictures! The only people saying ray-traced games can do soft shadows interactively are ray tracing researchers and marketers. I could write a rasterizer to do physically-accurate shadows, but it wouldn't be interactive either. That's why I don't brag about it.

With the current growth of processing power, I am guessing that sometime in my life I will see ray tracing become the normal rendering technique in interactive computer graphics, but I doubt it will be in the next thirty years. Rasterization will only fall behind the second it fails to keep improving.

Five-Years Difference
Rasterization is moving at an incredible rate. In a separate article, I compared a screenshot of two games only five years apart: Battlefield 1942 released in 2002, and Crysis released only five years later. This is what ray tracing is competing with. A rapid, cut-throat industry where GPUs are getting more and more powerful and developers are creating more and more dazzling hacks. Years from now when a ray tracer can produce images comparable Crysis, we'll be looking back wondering how we ever tolerated such mediocre graphics.




What's coming down the pipeline?
Interactive rasterization certainly hasn't stopped moving and will continue to provide a lot of one-sided competition for ray tracers in games.

Here are some things coming down the pipeline that we can look forward to that will continue to choke up interactive ray tracers:

• Highly-tesselated subdivision surfaces
  
• Movie-quality anti-aliasing
  
• Realistic hair
  
• Interactive deforming
  

Shortest Ray Tracer In the World (not really)

I saw Andrew Kensler's newest back-of-a-business-card ray tracer. It's some pretty short and simple code to render his initials in reflective spheres. I'm not sure he could find the way to shorten the code even more, without losing any kind of coherence.

This took 2 minutes on my workstation


And here's the code (butchered by my browser)

#include    // card > aek.ppm

#include 

#include 

typedef int i;typedef float f;struct v{

f x,y,z;v operator+(v r){return v(x+r.x

,y+r.y,z+r.z);}v operator*(f r){return

v(x*r,y*r,z*r);}f operator%(v r){return

x*r.x+y*r.y+z*r.z;}v(){}v operator^(v r

){return v(y*r.z-z*r.y,z*r.x-x*r.z,x*r.

y-y*r.x);}v(f a,f b,f c){x=a;y=b;z=c;}v

operator!(){return*this*(1/sqrt(*this%*

this));}};i G[]={247570,280596,280600,

249748,18578,18577,231184,16,16};f R(){

return(f)rand()/RAND_MAX;}i T(v o,v d,f

&t,v&n){t=1e9;i m=0;f p=-o.z/d.z;if(.01

for(i j=9;j--;)if(G[j]&1<,0,-j-4);f b=p%d,c=p%p-1,q=b*b-c;if(q>0

){f s=-b-sqrt(q);if(s.01)t=s,n=!(

p+d*t),m=2;}}return m;}v S(v o,v d){f t

;v n;i m=T(o,d,t,n);if(!m)return v(.7,

.6,1)*pow(1-d.z,4);v h=o+d*t,l=!(v(9+R(

),9+R(),16)+h*-1),r=d+n*(n%d*-2);f b=l%

n;if(b<0||T(h,l,t,n))b=0;f p=pow(l%r*(b

>0),99);if(m&1){h=h*.2;return((i)(ceil(

h.x)+ceil(h.y))&1?v(3,1,1):v(3,3,3))*(b

*.2+.1);}return v(p,p,p)+S(h,r)*.5;}i

main(){printf("P6 512 512 255 ");v g=!v

(-6,-16,0),a=!(v(0,0,1)^g)*.002,b=!(g^a

)*.002,c=(a+b)*-256+g;for(i y=512;y--;)

for(i x=512;x--;){v p(13,13,13);for(i r

=64;r--;){v t=a*(R()-.5)*99+b*(R()-.5)*

99;p=S(v(17,16,8)+t,!(t*-1+(a*(R()+x)+b

*(y+R())+c)*16))*3.5+p;}printf("%c%c%c"

,(i)p.x,(i)p.y,(i)p.z);}}

I'm still waiting for his back-of-a-napkin photon mapper.

Scala Review: Quite Refreshing

Since my first programming course in college, I've been told to use the right programming tool for the job. This was back in the day where perl was the ideal CGI and scripting language. I think even without python, perl was still the wrong tool for the job.

Regardless, I have used java many times for testing any idea floating around in my head. It had the relative speed of C++ and came with many more libraries than C++ making it a lot easier to perform some arbitrary task like load an image without having to find a special C++ library like libpng.

It's hard being number 2
Java sure has its faults. It certainly isn't the sexy language it was ten years ago, but it sometimes gets flak it really doesn't deserve. It is always criticized for being slower than C++, while no one mentions it being faster than most other languages. I guess it's hard being the number 2 in performance.

Java is a relatively simple language in the sense that it's pretty easy to understand what the code is doing. C++ trivia questions abound that make you ask yourself, "Why?! Why?! Why?! That must be a compiler bug!" until you see it in a C++ specification. Java dropped function passing, pointers, multiple inheritance, operating overloading, and a lot of other features to create a language one might call dumbed down.

This, in my opinion, is one of Java's main complaints. It's a simple language. Usually when someone will start listing examples, it's them lamenting that Java can't do it their way like designing classes with multiple inheritance--sure, it means you have to rethink your problem, or you may have to type a bit more for a given problem, but I think deep down the person just wants to be different.

Scala building off of Java's success
For many tasks, Java is everything I need it to be

1. The built-in packaging is much better than many other languages. Those who refer to it as "jar hell" are just bitter C++ developers
   
2. It is a relatively fast language. Java is usually not at the top on many language performance benchmarks, but it often comes as a close second.
   
3. Java comes with some great libraries. Some have gone as far as to criticize Java for having too many libraries, but these are just bitter C++ developers. It's not like one library is obscuring another by popularity. If I need java networking, an image library isn't going to throw me off the trail to find it
   
4. It has tons of examples. I can't even count how many times I want to do some mundane task and a google takes me to an EXACT example in the java almanac
   

Now, as much as I like Java, it will never displace all the other tools in my toolbox. It's just a really handy tool I'm glad to have there. Yet despite all the bonuses of Java as a language, there were always some features I didn't need or know I wanted, but when I found Scala, it literally opened my eyes. Well, maybe not literally...

Adding some nice features
It's hard to summarize from a global perspective why I enjoy Scala, so here are a few small features that stood out to me.

• Scala compiles to java byte code, so it has access to all java libraries ever written. Java code can even use compiled scala code
  
• In many tests I've seen, it is comparatively fast to java
  
• Scala allows function passing, but in a better way than python. An entire function block can be written inside a function call, which is a lot more powerful than python's lambda
  
• Fun match ability, which many refer to as a switch statement on steroids. I recently learned it is an easy way to do type checking
  
• Syntax-supported singleton objects, lazy evaluation of members, ...
  
• The package system syntax is more flexible than java, where multiple public classes can be in the same file. I believe even several classes from different packages can be stored in the same file
  
• Tuples! I never appreciated tuples until I started working in python. Going back to java and having to write a separate class just to return two or three values is incredibly frustrating. Java wants them; Scala has them
  
• Scala is strongly-typed. Some people may loathe this, but I actually prefer it. When writing difficult code, I have never met a developer whose bottleneck is having to decide what type a variable should be. It's writing code the compiler can heavily optimize, which is easier in a strongly-typed language and shows a lot of the problems at compile time instead of run time
  

A note on syntax
One of the Scala complaints I feel I must address is the syntax. Some people would have preferred Scala to have a C-like syntax like so many other popular languages. Now I myself also look at a language and sometimes cringe at the lack of curly-brace-separated blocks or not passing functions with parenthesis, but Scala is actually very simple to get used to. Here are a few little differences that come to my head.

object SingletonThing {
   def display(name:String) { 
      println("I'm ready to work")
      println("Thank you for calling me, " + name)
   }
}

Here's a singleton object. It's very similar to the static methods one would put inside a class in java. To make a singleton, just use the object keyword instead of class. Also functions begin with the keyword def. I was adamantly resistant to this syntax for about ten minutes. Also, parameter strings reverse the C++ order of types and variables. I actually prefer this order now.

class GiveMeAFunction(someNumber:int) {
   println("This is part of the GiveMeAFunction constructor")
   val anotherNumber = someNumber + 5

   def doSomethingWithTheNumbers(someFunctionYouGiveMe:(int,int) => Unit) {
      someFunctionYouGiveMe(someNumber, anotherNumber)
   }
}

This example gives a few more insights into scala basics. First, scala classes are declared with a default constructor parameter string and its constructor code trickles into the body. It is possible to have secondary constructors, but I haven't needed them yet.

Second, you'll notice the val keyword with member declared. The two main ways to store a reference is with val meaning that that value will remain constant, and var meaning it is a variable. Using val supposedly allows the compiler to make certain optimizations, but it is more useful as a quick way to not accidentally mess up the value you have stored in it. This syntax is somewhere in between C++ and python. You can declare a value as variable or constant like C++, yet you don't have to manually retype the type similar to python. I consider Scala's implementation superior to python's as once you declare a variable, it will remain that type where python will let you put whatever you want into it at any time. This has been a headache for me when coding in python and I'll accidentally put a function into a variable instead the function's return value, which it won't complain about until somewhere later in execution.

And lastly is the function passing. I created a method which takes a function someFunctionYouGiveMe, which has to take two integers as parameters with Unit (means void) return type. I can then call that function or save it off to be used later. I have grown to love this syntax.

Other than that, there are only minor differences to Java. if statements must be on the same line as their code if one doesn't used a code block. Semi-colons aren't needed unless you really want to put two commands on the same line. Also, importing is a little more robust than Java.

Scala is what Java should have been
I encourage any person who enjoys Java or wants a little experience to toy around in Scala. It's a functional/object-oriented hybrid that has been a really fun transition from Java.

A question I might be asked is if Scala is really so cool, why would I ever use Java again? Well, the only reason I use Java now is to take advantage of Netbean's GUI-building forms. Other than that, I will probably use Scala for everything else. Some may consider Scala a fad, but I think with it's added features and friendly play with the Java language, it will be around as long as the JVM will be.

Ray Tracing Simpler than Rasterizing?

In one short word... depends.

I would definitely agree that someone can sit down and bust out a simple ray tracer. When I was learning python, I hacked a 500-line script to render a simple scene. It has shadows, reflective materials, and a couple of primitives that would have to be discretized into triangles to render with a rasterizer. The only real library I used was an image library to actually put the image into a window.

1. For handling reflections, I just reflect the ray direction off the surface and send it out again
   
2. When shading something, I fire a ray towards the light source and if I hit something before I get there, I shadow the surface
   
3. I added a procedural checker material with only a few lines of code based on the surface position
   

In my opinion, it's some pretty simple code to implement these rather significant features. If I wanted to add more complicated features like shade trees, it would have been a relatively simple addition. Not only was this script straight forward, but I implemented it right off the top of my head. I don't have the best of memory, so I'd like to reinforce these concepts are quite intuitive to remember.

Simple python ray tracer featuring procedural shading, Lambertian and reflective materials, and simple shadows

(source code)

Same work with a rasterizer
Now, let's imagine that I had to write the same kind of functionality in a simple scanline rasterizer.

1. the procedural geometry is out--both the plane and the sphere have to be broken up into triangles, which isn't complicated, but surely not as elegant as some vector algebra
   
2. I would need to implement or find a matrix library to handle all my projections, and since I don't have the projection matrix memorized, I'd need to go get a reference of that
   
3. I would also need to implement the actual scanline algorithm to sweep through these polygons and implement a simple depth map
   
4. For shadows, I'd need to render a shadow map making sure the objects casting the shadows are in the light frustum
   
5. For reflections, I'd have to render an environment map, which would involve texture lookups and alignments, etc.
   
6. The procedural checker material would probably be the easiest thing to implement, but I would have to interpolate the vertex attributes to the different pixels
   

I certainly can't elegantly fit all that in under 500 lines of code. It's pretty evident that implementing a few basic visual effects is obviously much simpler with ray tracing.

Where is Rasterization Simpler?
Ray tracing models light transport in a very physically-realistic manner. It handles pretty much any "effect" rasterization can do, but it comes at a big cost--mostly performance. Most ray tracing research currently is all about making the algorithm faster, which requires some very complex code to be written.

First, ray tracing pretty much requires the entire the scene including textures to fit into local memory. For example, if you fire a ray into the scene above and it hits the ball, that ball needs to know about the plane below it and the ball to the left of it to do a reflection. That's simple enough in this case, but what happens if your scene is five gigabytes and you have four gigabytes of RAM? You have to go through the incredibly slow process of getting that primitive from the hard drive and load it into memory. That's a ridiculously slow. And the very next ray may require another hard drive swap if it hits something not in memory.

One easy solution is to break your scene up into manageable layers and composite them, but then you have to start keeping track of what layer needs what. Like if you have a lake reflecting the far off mountains, both need to be in the same layer.

What's with these acceleration structures?
And what of these acceleration structures? Ray tracing is often touted as being able to push more geometry than rasterization as an acceleration structure typically allows the ray to prune large groups of primitives and avoid costly intersections. That's certainly nice if you happen to have one, but where do these structures come from? You build it yourself! And if you happen to be playing a game that requires any kind of deforming animation (almost any 3D game now a days), you have to rebuild these structures every frame.

Despite the research in this field, it's still expensive to maintain them as the scene changes. State of the Art in Ray Tracing Animated Scenes discusses some of the more recent techniques to speed up this process, but as Dr. Wald says, "There's no silver bullet.". You have to pick which acceleration structure to use in a given situation, and then you have to efficiently implement them.

With a rasterizer, you have to linearly go through your entire list of geometry. But if we're animating and deforming that geometry anyway, that's fine. With a ray tracer, animation means having to rebuild your acceleration structures. Why does ray tracing make animation so complicated when it should be so simple?

Ray Tracing Incoherency
Ray tracing is inherently incoherent in many ways. Firing a ray (or rays) through every pixel makes it difficult to know what object the renderer will want in the cache. For example, if one pixel hits a blade of grass, that geometry needs to be loaded into the cache. If the very next pixel is another piece of geometry, that blade may need to be swapped out again. For visibility rays you can optimize this a little bit, but with secondary rays (the entire purpose of ray tracing) these rays are going all over the place. Many elaborate schemes have been developed to attack this problem, but it's a difficult property that comes with ray tracing and won't be solved any time soon.

A rasterizer is inherently coherent. When you load a gigabyte-sized model into RAM and bring its gigabyte of textures, you render the entire scene, you're working with that one model until you need the next one. When doing a texture lookup, there's a really good chance that chunk of texture is still in your cache since the pixel before probably used an adjacent texture lookup. And when this model is completely rendered, you can throw it away and move onto the next one and let the depth buffer take care of the overlaps. Doesn't the depth buffer rock?

Both are Complex
In general, there's nothing really simple about production-quality ray tracing. It basically trades "graphics hacks" for system optimization hacks. David Luebke said in Siggraph 2008, "Rasterization is fast, but needs cleverness to support complex visual effects. Ray tracing supports complex visual effects, but needs cleverness to be fast". Every scene is bottlenecked by time and trying to get ray tracing working in that time isn't always "simple".

nVidia's Interactive Ray Tracing with CUDA presentation

Rasterization: King of Anti-Aliasing?

With the ongoing marketing of interactive ray tracing, I have continued to evaluate why rasterization will continue to be the dominant rendering method in games for quite some time. Ray tracing is considered by many as the end-all-be-all in computer graphics and some people seem to simply turn their brain off when it comes time to discuss its disadvantages. While conversing with an old colleague on that note, I realized I've never met a rasterization fanatic that insists everything has to be rasterized. Wouldn't it make more since to use them in areas they excelled in? As you read the next part, keep telling yourself rasterization still dominates the movie industry for good reasons and why those same principles apply in games.

Rasterization: King (or Queen) of Anti-Aliasing
It's pretty much undisputed (to sane individuals) that rasterization trumps ray tracing in terms of anti-aliasing. When Pixar's REYES renderer was being developed, one of their primary goals was providing high-quality anti-aliasing. This is one of rasterization's biggest advantages and one of the principal reasons off-line renderers still use rasterization for visibility rays. This has to do with the basic difference between ray tracers and rasterizes. With a ray tracer, one ray is fired per pixel and an intersection is computed for that ray. With anti-aliasing, more rays are fired into the scene per pixel. Thus if you want n samples, you fire n rays and do n intersections. These intersections are in 3D and are relatively expensive to compute. Rasterization, on the other hand, does a lot of work to get a primitive onto the screen. Once it's there, however, it can be sampled efficiently in 2D. So, rasterizers project geometry into 2D, and we'd like to sample in 2D since we're making a 2D image anyways. How convenient.

Once the primitive is on the screen, rasterizers can crank out the samples


Imagine a pixel on screen as you see above and one desires to perform nine samples instead of one to provide a more alias-free image. With ray tracing, each sample is an expensive intersection test. With rasterization, the renderer simply has to decide, "Does this sample lie inside the primitive or outside?" Hrmm, which one seems simpler? That that may seem trite since a computer is doing all the work, but it's the difference between solving a complex 3D intersection or a 2D region test. With ray tracing, firing n-times more rays is n-times slower. With rasterization, the brunt of the work is getting it on the screen. Once it's projected into 2D, samples are dirt cheap.

Who cares about anti-aliasing?
The topic of anti-aliasing certainly isn't sexy. It doesn't require secondary rays, funky texture maps, or any complex data structure. It's usually just more work. But it's one thing we haven't seen really pushed on GPUs--more settled on. A modern video card can do 16x full screen anti-aliasing and certainly could do much more.

Look at the image below. There's nothing really complicated in this scene. Certainly nothing that would require a ray tracer--mirrored reflections, simple smoke, some large textures, and a lot of little details. For all I know this image could have been ray traced--probably considering every modeler comes with some kind of ray tracer--but it screams for a rasterizer. You'll see games soon turning this stuff out in real time.



Anti-aliasing in games
With production studios sometimes requiring more than 64x samples per pixel, it's no wonder why companies are still rasterizing away. With current graphics cards easily performing 8x sampling per pixel while ray tracers chug away on beastly machines to compete, it would take very little for GPUs to flex their anti-aliasing muscle with even more samples. Anti-aliasing right now is pretty good and it's only getting better. Movie quality anti-aliasing in a game? Woo hoo!