March 10, 2008
Like many programmers, my first exposure to ray tracing was on my venerable Commodore Amiga. It's an iconic system demo every Amiga user has seen at some point: behold the robot juggling silver spheres!
Thus begins the article in the May/June 1987 AmigaWorld in which Eric Graham explains how the Juggler was created. The program ("with full Intuition interface") promised at the end of the article was Sculpt 3D for the Amiga, released in the fall of 1987. Byte by Byte sold Amiga and then Macintosh and Windows variants of Sculpt for more than a decade.
Eric rendered the frames in a raytracer he wrote called ssg, a Sculpt precursor. The rendered images were encoded in the Amiga's HAM display mode and then assembled into a single data file using a lossless delta compression scheme similar to the method that would later be adopted as the standard in the Amiga's ANIM file format.
Eric and his wife Cathryn actively promoted raytracing on the Amiga. Cathryn wrote the Amiga Sculpt 3D user manual and compiled an electronic newsletter distributed on a series of disks. Raytracing 1.0, the earliest of these, contains both ssg and the static geometry of the juggler object, along with the Juggler image data and the player program.
Juggler was an astounding demo in its time. I personally remember staring at it for several minutes through the front window of a local Amiga dealer, wondering how it "worked." Many people were inspired by Juggler, and by the Amiga animations that followed, to pursue a career in 3D graphics. Nothing like it could have run on any other stock personal computer in 1986.
In fact, Eric recalled recently, the Commodore legal department initially "thought it was a hoax, and that I'd done the animation on a mainframe." He sent them his renderer so that they could generate and compile the frames themselves.
The juggler may seem primitive by today's standards. Maybe it is. I've been subjected to forum signature images with more frames of animation. But it was revelatory back in 1986. The Amiga brought 3D raytracing graphics to the masses for the first time. Ray tracing is extremely computation intensive, but hyper-realistic. It's essentially calculating the result of every individual ray of light in a scene.
Given the explosion of computing power in the 22 years since Juggler was released, you might think all 3D graphics would be rendered via ray tracing by now. To a certain extent, that is true; many computer animated films are rendered through ray tracing techniques, such as Pixar's PhotoRealistic RenderMan.
Pixar has done some incredible work on 3D rendering, but it's not exactly what I'd call real time. Courtesy of Chris Anderson, here's a little Pixar quiz:
On 1995 computer hardware, the average frame of Toy Story took two hours to render. A decade later on 2005 hardware, how long did it take the average frame of Cars to render?
- 30 minutes
- 1 hour
- 2 hours
- 15 hours
Answer: D. The average Cars frame took 15 hours, despite a 300x overall increase in compute power. The artists have an essentially infinite appetite for detail and realism, and Pixar's resources have grown over the decade so it can afford to allocate more computers to the task, allowing each to run longer to achieve the artist's and animator's ambitions for the scenes.
Surprisingly, Cars was the first Pixar movie to be rendered with the slower, more accurate ray tracing techniques; previous movies used mostly scanline rendering. There's an excellent presentation from Pixar's Per Christensen (ppt) describing the differences in some detail, if you're curious. And if you want to experiment with ray tracing yourself, there's always POV-Ray, which produces some impressive results as well.
Movies, of course, don't have to be rendered in real time. But even with the freedom to take as much time as necessary per frame, ray tracing is often too expensive. Imagine the difficulty, then, of shoehorning ray tracing into real time 3D engines. Modern GPUs are impressive pieces of silicon, but they cheat mightily when it comes to rendering a 3D scene. They have to, otherwise they'd never be able to generate the 30 or 60 frames per second necessary to provide the illusion of an interactive world.
Of course, this doesn't stop people from trying. The most impressive real time ray tracing attempt I've seen is from Daniel Pohl and his OpenRT real-time ray tracing project. Daniel has done some fascinating proof of concept work with Quake 3 and Quake 4.
But performance remains a problem, even on the latest and greatest hardware:
So why don't we see raytracing right now in games? The problem is still performance. Rendering all these effects through the CPU is not as fast as using special purpose hardware like current graphic cards for the rasterization algorithm. But the evolution of CPUs is fast. Q3RT speed has increased by more than a factor of 4 since 2004. Intel's new quad core is out and the efficiency using the same CPU clock rate is about 30% higher.
One big advantage of raytracing is that it is perfect for parallelization. As explained in the introduction, a ray is shot through the 3D scene for every pixel. If you render an image with 640x480 pixels, you have about 300,000 rays. Each of them can be calculated independently of the others. This means the image could be split up into four parts and every core of a quad-core CPU can calculate the color values of the image without waiting on any of the other cores for intermediate results. Therefore the scaling of performance with the number of cores in Quake 4: Ray traced with OpenRT on Intel's quad-core CPU is great. The following benchmarks were taken at a resolution of 256x256 pixels on the Quake 4 map "Over the Edge (Q4DM7)".
|4 cores||16.9 fps||3.84x scaling|
|2 cores||8.6 fps||1.96x scaling|
|1 core||4.4 fps||1x scaling|
It's difficult to find much software that scales beyond two cores. So the emergence of a many-core future is a boon to ray tracing algorithms, which scale nearly perfectly.
The dimensions of the original juggler are 320 x 200. That's roughly the same number of pixels as the 256 x 256 Quake 4 benchmark presented above. It's possible we could render the ray traced Amiga juggler today in real time at close to 30 fps-- but barely. Despite many hyperbolic marketing claims of "rendering Toy Story in real time", real time ray tracing remains something of a holy grail in practice-- considering Toy Story was rendered at 1536 x 922. Who knows what we'll be able to render in the next 20 years?
Posted by Jeff Atwood
Great article! I remember an Apple keynote a while back where steve showed Pixar's Luxo Jr rendering in "real time" as he swung the camera around.
I'd love to be able to watch an animated movie and choose ANY angle in real time. I have no idea why that fascinates me, but it does.
Very intersting post. Its nice to see there is some use to these quadcore CPU's if anyone writes the code for it (which I imagine will be done)
raytracing "quake" is one thing, raytracing "juggler" is much simpler (simple scene, containing raytracing-friendly spheres and checkered plane).
i'm sure it can be done in realtime on a regular modern computer nowadays!
omg you did this post for me didn't you...
Been a POV-Ray user for years, I even made my own renderfarm, now I'm searching about unbiased raytracers: forward raytracers, tracing rays from the light, slow as hell (let's say slow as backwards raytracers were many years ago) but impressively realistic results. I was browsing Luxrender website when I noticed this post on the RSS feed...
By the way, why on does the "POV-Ray, which [produces some impressive results] as well" link point to the IMDB entry on Cars movie?? I'm pretty sure Cars didn't involve POV-Ray...
In 2000 I wrote a realtime raytracer that could render a scene similar to the Amiga juggler in 320x240 at 30fps on a PII-450 using various scene optimisation techniques, so I'm not sure how true that last paragraph is...
While the Pixar Photorealistic Renderer (prman) is the industry benchmark in rendering it has ray tracing as an add on. Blue Sky Studios (http://blueskystudios.com/) has been doing ray tracing for over 20 years. The people that started Blue Sky got their start at MAGI/Synthavision and worked on TRON.
Blue Sky has ray traced all of their movies, shorts, and commercials for many years. They have a little more on the renderer here: http://blueskystudios.com/content/process-tools.php. They even won the 1998 Oscar for Best Animated Short for Bunny (http://blueskystudios.com/content/shorts-bunny.php) where the only thing not rendered with radiosity was Bunny and the moth. All environments were radiostiy renders.
Nicolas, thanks for this link! Very cool real time raytracing demo:
- default window size (which is 320 x 240)
- default settings
(eg, do not change anything after launching the executable)
I get ~90fps on a 3.0 GHz Intel Core 2 duo.
"Egg" under the Demo menu is by far the slowest at around 11 fps.
[It's essentially calculating the result of every individual ray of light in a scene.]
Well, that's not exactly true. Your diagram shows it more accurately, i.e. it's casting a ray from the "eye" or "camera" point for every pixel that makes up the viewport. The goal for each pixel is to calculate its colour, plain and simple. The more complex the scene and the more complex the effects desired, the more colour calculations to perform. If an individual ray intersects any "object", then a vector is calculated from the point of intersection to *every light source* in the scene (in your diagram this second vector is called the "shadow ray"). The angle between the original ray and this vector provides the basis for a number of different colour accumulation calculations. When the second vector intersects yet another object rather than reaching the light source directly, it can result in yet more calculations, if you so choose (e.g. reflection). Otherwise, you simply do not add any colour from that light source. This *can* get more complex if you want soft shadows with proper penumbra, etc, but for the basic case you simply "do not add colour".
The diagram itself has somewhat of an incorrect depiction in that it shows the vector "passing through" the object to still hit the light source, but fails to explain that the result is simply "do not add colour". It would be more accurate to at least explain that the original ray had to interesect with something, in this case a plane. Otherwise, the colour added would simply be the background colour. Then, as the "shadow ray" intersects with the sphere, the light cannot reach that point on the plane and hence you do not add any new colour to that point.
For any programmers out there, it is actually quite easy to write your own ray-tracer in any language you choose. The old stand-by book "Computer Graphics in C" has a pretty good description of what's involved. And as was stated, the result of a ray-traced scene has nothing to do with your graphics hardware, it's all CPU crunching (unless you're bold enough to try and hijack the GPU to do some crunching for you).
I don't see much point in moving exclusively to ray-tracing, considering how nice results you can get with rasterization + shaders. If anything, a hybrid approach (like Pixar's renderman...) is the best solution, imho.
Nvidia is obviously going to be biased :), but this article is good nevertheless: http://www.pcper.com/article.php?aid=530
The quiz made me grin. I've worked for years with a 3D artist who was doing 3D CG decades ago using custom software written for NASA and running on VAXen. Since he was doing TV work his frames were all 720x486x24, and in 1980 they took about 20-30 minutes each to render on the VAX and custom accelerator.
Over the years he moved to Softimage on Irix, then on PCs, then added a render farm that grew to 60+ processors, using both scanline and Mental Ray renderers. In 2007 he finished a large project with frames that took... 20-30 minutes each to complete. He has some sort of internal yardstick when designing that keeps him in that range no matter what resources he has at his disposal.
f0dder great link. If that is NVIDIA's voice of the status quo with traditional 3D hardware rendering, here's Intel's response:
Ray Tracing and Gaming - 1 Year Later (Jan 2008)
It does seem the hybrid rendering approaches work best, and that's what Pixar's RenderMan does. I'm really surprised they never got into ray tracing until Cars, though. Do check out that presentation I linked, it's outstanding.
Actually, it's the other way around: the nvidia interview is the response to intel's article :) (check dates) - intel obviously wants to push raytracing since they're mainly CPU people, and considering their experiments with 80+ core CPUs, they want something that can take advantage of it; most computer science is notoriously hard to parallelize, raytracing is almost the exception to the rule...
I'm actually surprised if Pixar did Cars fully-raytraced, considering how nice results their hybrid Renderman has done in the past - and, I assume, how much less CPU time it has taken.
No! Please don't perpetuate this myth! Raytracing is NOT the holy grail.
For a reasoned argument, check out this article by Deano Calver. He worked at Ninja Theory on Heavenly Sword.
- anti-aliasing is hard
- moving scenes are VERY expensive
- it is almost fully procedural, so the artist has near zero stylistic control over the final look of a shot
Synchronicity! I was just listening to this podcast on POV Ray this morning: http://www.twit.tv/floss24
There's some good history in there as well as discussion about the performance issues associated with ray tracing techniques.
If you haven't seen it, Jon Harrop has some comparisons of a ray tracer in various language.
Ocaml for the win!
And the JoCaml extension to Ocaml provides distributed program and "free" n-core scalability.
So I'm pretty sure we're closing in on "solved problem". :)
You mentioned that you're surprised that Pixar never got into raytracing before Cars. Actually, Pixar has had a few shots as early as Bug's Life that used ray-tracing.
They used a separately implemented renderman compliant system called BMRT, http://en.wikipedia.org/wiki/Blue_Moon_Rendering_Tools that would serve rays to their PRman implementation. They hired on Larry Gritz, the grad student who wrote BMRT, to their PRman routine. He has since left, and worked on Gelato, NVidia's film-quality hardware accelerated rendering system.
An interesting story I heard at siggraph - I believe PRman 11 was the first version to support raytracing internally. Before it was available, Weta was working on the second film in the LotR trilogy, which features Gollum prominently. His eyes are so large that without proper refraction of his iris through the lens, his eyes are noticeably unnatural and flat. Because they couldn't easily use raytracing to get proper refraction, they created a displacement shader that computed where rays would hit if refraction were properly taking place, and deformed the iris and pupil so that PRman's simple scan rendering would produce the proper result.
AA is only as hard ray tracing more. To AA using raytracing you just send more rays per pixel. It costs a lot, but so does raytracing currently. Once we get real time raytracing just wait a few more years for AA real time raytracing. AA is a non-issue.
They claim moving scenes don't work with raytracing due to the amount of work required to get the scene into the required structure, but this is a non-issue. Just toss another core or two to update the structure in parallel. Simple.
I don't know you understanding of raytracing, but you can pretty much toss any 3D model that exists now into an appropriate raytracer...I don't see how artist would not be able to affect the scene.
The another of that article goes on to talk about how GI doesn't look good. Double U Tee F! GI scenes are the far more realistic/pretty CG I scenes I have ever seen/created.
Raytracing IS the holy grail of rendering. (Of course we currently use mostly backwards raytracing, forward raytracing is the holy grail of raytracing.)
The above page notes that playable frame rates were only achieved using a virtual CPU of 36GHz (cluster of 20x AMD AthlonXP 1800+). Even if we assume that improvements in desktop CPU power and parallelism over the past few years have reduced the requirement to a 30GHz CPU, one would still need 5x 3GHz dual-core CPUs to make ray tracing practical on a standard PC. (And that's not even taking anti-aliasing into account.)
Given that the processor industry seems to have hit a ceiling at 3GHz, I'm betting it will be a while before we see games that use ray tracing renderers with acceptable performance. Even with the might of Intel behind ray tracing, rasterization-based rendering has been around for more than a decade and the major player (nVidia and ATI) have become very good at what they do. Ray tracing has lot of catching up to do if it's going to compete with (never mind supersede) rasterization.
I'm certain that ray tracing is the future of computer graphics, but I'm equally sure it will be a number of years before it becomes a viable solution to rasterization.
I agree with some of the other comments. Ray-tracing is NOT the ultimate holy grail of rendering. It's just one of many techniques developed over time, and although it has some nice intrinsic properties, it also has disadvantages. Hybrid schemes will always produce better results than pure ray-tracing.
Ray-tracing would be all you'd need IF modelling the environment could be done at essentially molecular level AND you could ray-trace at photonic resolution instead of screen resolution. The latter is ultimately a matter of computational resources, but the former is incredibly hard, if not impossible.
Hybrid rendering schemes employ algorithms such as radiosity to model the micro-structure of surfaces without having to do this explicitly, bump by bump.
Ah Jeff, you that's a topic I am so interested in. I am still waiting for the day when the companies stop creating another "graphics feature" that is just another of those cheats to make the graphics look more realistic, instead of investing their time and money into something for the future, i.e. real-time raytracing. Imagine future video cards with multiple GPUs that are solely made for real-time raytracing, still highly specialized, but you won't need like 10 new features every year. It will make a much better scaling of performance with price, too.
And last but not least, possibly one day we won't need dedicated GPUs, but rather a part of your 1024 (or how many we will have by then) CPU cores then gets assigned the task of raytracing, and the video card is not much more than a high speed output port.
That might seem unrealistic? I suppose what we have as standard hardware nowadays would have been thought unrealistic back in that 1987.
Raytracing will become THE killer-app in video graphics as soon as multi-core-ization has hit a certain level, i.e. number of cores, and the first programs and probably video games using them for RT will pop up. Especially concerning video gaming, the two bottlenecks are speed of hard disk access, which will multiply with improvement of flash memory and it replacing mechanical magnetic hard drives, and the second bottleneck, video data processing speed, will at that point DIRECTLY SCALE with progress in CPU development.
As somebody said earlier in this blog, PRman (Photorealistic RenderMan, the one developed by Pixar) is a RAYES renderer with embedded some raytracing capabilities.
The way RAYES work is dicing (splitting) the geometry into micro-triangles (well nu-patches to be exact) and shade each triangle vertex with user defined shaders. Resulting color, opacity and extra output channels are "stored" in the mesh points. The final image is obtained by rasterization of the diced mesh by interpolation of the colors at the mesh vertex.. a similar approach done in the old Gouraud shading (do you remember that?), the difference is that micro-triangles are very thin, usually about the size of a single pixel, so there is no lack of details. Shading points can be also moved before the shader is executed (to do displacement) or after to do motionblur.
The exectution of shaders is done in parallel on many shading points at the same time (many shading points of the same primitive define a shading-grid). This is done to split the cost of the shader interpreter across many points (SIMD execution). Data like geometry and surface properties changes gradually between adjacent points (coherent access of data), this makes possible a number of optimizations and tricks, like computing the derivatives of any arbitrary variables in the shader.
Raytracing done in PRman is very complex. First of all geometry divided into micro-triangles is too heavy, you can easily end up having many dozens millions of triangles in a scene. The scene is never handle as a whole thing, image is rendered in buckets, what is outside the bucket is clipped. Therefore implicit geometry like NURBS subdivision surfaces, blobby, etc geometry must be splitted again and again to compute the ray intersection and thrown away. There are a number of optimization systems, like the multiresolution geometry cache based on ray differentials, but none of this is very effective. Ray intersection remains very slow if compared to other products.
A second major problem is the shading execution. SIMD execution is impossible at ray hit, because of the nature or raytracing, rays can hit everywhere. Each object can have a different shader assigned, therefore each ray hit triggers a single shading point execution with the entire cost of the shader interpreter spent on it.
There are also a large number of problems that affect scalability of PRman raytracing on multi threading.
For these reasons PRman is probably the most terrible raytracing capable renderer ever made (I have to deal with it every day for at least 10 hours a day)... but almost none of the other render engine on the market can handle displacement and motionblur well enough to deliver a film quality imagery. Those two are some of the most important features needed to make a CG image look real and integrated with a live-action plate... This is probably the reason why PRman is still the product of choice of many VFX/animation houses.
"In fact, Eric recalled recently, the Commodore legal department initially "thought it was a hoax, and that I'd done the animation on a mainframe." He sent them his renderer so that they could generate and compile the frames themselves."
That just about sums up Commodore management's view of the Amiga. They had absolutely no idea how brilliant the machine the Amiga engineers had made was. IBM and Apple were genuinely scared when the Amiga (with it's amazing custom chips and pre-emptive multitasking OS) came out in 1985, but could rest easy once they saw Commodore's pathetic attempts at marketing the thing.
I was really into graphics at one point, and wrote a pretty fast raytracer with some pretty interesting features in under 24 hours while I was in school.
A few points:
The classical raytracing algorithm is O(log n) (albeit a very big O(log n)), while rasterization is O(n). This means that eventually (for complex enough scenes) raytracing may actually be faster than rasterization. This can already be shown for simple (eye-rays only) raytracing.
There is significant friction between the elegance of the raytracing algorithm and modern computing architectures. Raytracing relies heavily upon recursion, which modern CPUs don't like very much from a low-level perspective. Recursion is elegant, but recursive data structures often lead to cache thrashing, which leads to lots of low-level optimizations. Some of these are as clever as storing all the nodes of your KD-tree contiguously in memory, and some of them are as hackish and evil as using the lower 2 bits of a floating point number to store extra data.
There is fascinating research going on in the field of raytracing hardware (see http://graphics.cs.uni-sb.de/SaarCOR/). Honestly, the only reason we have awesome 3D rasterization nowadays is because of dedicated hardware. Modern CPUs still can't rasterize a modern scene at playable framerates with decent resolution, even with lots of low-level tweaking. Raytracing hardware shows some SERIOUS potential. If I remember correctly, you can match a high-end dual-core Pentium's performance with an FPGA running at around 100 megahertz (don't quote me on that though). Now, think of what could be possible with a dedicated ray-tracing card with specs equivalent to a modern high-end graphics card :D
Is it common to use multiple light sources in ray tracing? How does ray-trace rendering scale with the number of light sources?
It is worth noting that real time ray tracing is *not* near perfect scaling on real world hardware because it tends to jump around in memory a lot on complex scenes.
The resulting cache misses make it scale up to the limit of the memory subsystem. (By choosing to parallelize rays close to each other you mitigate this but as you get more cores the probability of local rendering steps taking similar paths is much reduced).
With classical ray tracing, the number of light rays you have to test at each intersection is in general linearly proportional to the number of light sources in the scene. Simple ray tracers will test every light source at each intersection in order to determine which lights the point of intersection is illuminated by. If you have area light sources and want better shadows (with soft edges, etc) you need to fire multiple rays at each light source for each intersection.
Of course, there are always clever ways to reduce the number of tests you have to make, but conceptually that's what you have to do.
For anyone interested in building a ray tracer while still learning and understanding the theory behind it, I would recommend the book "Realistic Ray Tracing" by Shirley and Morely. It's very hands-on, but it also presents things from a theoretical perspective.
if you have a raytracer it doersn't necessarily means you have to shoot rays for everything. If in a scanline renderer you are using shadow maps techniques to cast shadows from each light, so you can do with a raytracer.. You can use exactly the same shadows maps to do shadows. You can even cast rays from the lights to build a small shadow map on the flight, blur it and use it to generate cheap soft shadows. You can use mixed techniques like computing a shadow map, then cast a single ray from the shading point back to the light (or vice-versa) to find the shadow caster distance and blur the shadow map depending on the distance, to create inexpensive but high quality soft shadows.
People have to stop thinking that every cool rendering trick owns to scanline/rasterization domain, while raytrace is a "pure solution" where only rays are casted to do everything. In general a raytracing capable renderer delivers higher quality images because it can use all the known techniques and tricks plus one, the raytracing! And not because it's a pure raytracer and then it's cheating less than a scanliner.
For the truth seek, the movie cars was 24 frames per second as every other movie, 30 fps is just the US/Japanese NTSC TV standard.
And yes it would take hundred of years to render an entire movie on a single computer.
I worked on Happy Feet two years ago as lighting TD. The average frame was taking around 25-30 hours to render, of course it wasn't a 30 hour single frame rendering, but many less complex images to be combined together to make the final image.
In your equation consider also the number of times the average shot have to be re-rendered, because of animation changes, surfacing changes, light changes.. the average number of takes in happy feet was 12 times per shot, but not every time everything was re-renderer, only the layers affected by the changes.
We had a rendefarm of 3600 CPUS all Xeons 3.2GHz. It took about 1 year to render the entire movie. Of course we were working like crazy in the meanwhile, to feed the renderfarm with new animation, textures and lighting setups.
For us working in the non-realtime section of computer graphics, realtime is just a myth. For as far as I can remember, 12 years are gone and rendering times became slower and slower. Demand for high quality/high complexity is growing more than what hardware is getting faster, therefore we need more machines, larger farms, more memory. Those days a 8 cores with 16 GB of ram sounds like the minimum we need to do a decent job.
Raytracing easily produces excellent results for the relatively few things in the world which are highly relective or refractive. For everything else, theres rasterisation, which is nearly always faster and often more flexible.
Raytracing is a non-issue: graphics programmers are pragmatic, and will use whatever gets them the best bang-for-buck. So far, rasterisation has won hands down.
I was more referring to classical raytracing, not a hybrid approach. There are advantages to having a "pure" approach.
Actually tracing the light rays still yields the best shadows. The very point of using raytracing instead of rasterization is that raytracing generates images of better quality than rasterization when solving certain problems (namely shadows, reflection, and refraction).
Furthermore, whatever method you use to calculate shading will still scale linearly relative to the number of light sources. It might be a "smaller" linearly, but it will still be linear.
I actually worked at Commodore in the very early 90's... While not an electrical engineer, I did have wonderful discussions with them about how they made the Amiga do all those amazing things.
Before that, I wrote ray-tracers all through college... everyone loved the eye-candy. Now my day job is creating tools to build near real-time plots and graphs for monitoring.
With all my tendencies towards visualization, you'd think I'd agree that ray-tracing is the future of computer graphics. But I doubt it.
I'd so much rather see better physical models for animation and innovative/immersive controls for human/computer interaction. Perhaps these aren't really computer graphics exactly, but they closely relate. Spend the cycles here and nobody will notice whether it's raytraced or not.
Considering the 15-hours-per-frame statistic, doing the math yields that an hour's worth of the movie would take about 148 years to render (if rendered one frame at a time on one machine). One must wonder just how many machines they used, and what wonderous horsepower they must have had in order to render the entire movie in a practical timeframe.
Raytracing WILL eventually displace rasterization, but it won't happen tomorrow. Most of the objections given to raytracing by other commenters are moot - antialiasing, for example, is generally viewed as a STRENGTH of raytracing in terms of ease of implementation and cost relative to the complexity of the scene. The issue of dynamically updating acceleration structures for ray tracing will be solved; there are already data structures, such as bounding interval hierarchies, that can be updated quickly and yet deliver most of the performance of traditional acceleration structures like kd-trees. Raytracing is also inherently able to take advantage of precalculated global illumination data (such as photon maps) in a way that rasterization is not; dynamic global illumination is a hard problem, but it's hard for both ray tracing and rasterization, and the solution is likely to involve ray tracing. Photon maps are calculated using "forwards" ray tracing - that is, with the rays originating from the light source - and so once realtime raytracing is possible, it's only a matter of time until photon mapping or a similar algorithm can be performed in realtime as well.
All that's really holding us back is having a large number of cores to work with and a great deal of memory bandwidth; it'll take a while before we reach the point at which realtime raytracing makes MORE sense than rasterization, but it's not so far off as some seem to think, and the time complexity of raytracing as compared with rasterization make the switchover a mathematical certainty as scenes get more complex.
Splendid. Excellent post, realy helpful. Thank you!
The nice thing about POVRay is that you can download the source code and see what it is doing. Great for learning about coding for raytracing.
LOL. I wrote a ray-tracing app in VB.NET before I even knew what ray tracing was. At univ in 3rd semester calculus, we learned a lot about 3d math (vectors, surfaces, etc...) and it just dawned on me that I could write a program that rendered 3d objects by plotting a line eminating from a "camera point" for every pixel on the screen, then test for an intersection between that line and every object in the scene. Later, I wrote my own texture mapping algorithm as well (easy, since all surfaces I had were defined using parametric equations). The lighting equations came from a physics lecture. My friends were impressed that I could write something so awesome.
It wasn't until a year later when I took a computer graphics course that I realized the algorithm I'd "invented" already had a name.
People seem to group all kinds of new rendering techniques under the rasterization label. I don't feel that raytracing in itself is a goal to strive for. Raytracing is a small part of the rendering calculation - visibility calculation. Just as the z-buffer rasterization method is. One is pixel order rendering, the other object order. In terms of efficency rasterization beats raytracing hands down for calculating correspondence between pixels as locations on objects. Because *all* 3D graphics is about making images that *look* correct, a good developer would use rasterization everywhere where it is feasible. Where rasterization falls down is reflection and refraction off of curved surfaces (like car fenders), and people are actually surprisingly bad at judging defects in such cases. There will certainly be more raytracing than now, there already is simple raytracing for surface details in recent games, but rasterization is not going anywhere soon. A hybrid approach is much more likely - rasterization for most cases, ray tracing when rasterization doesn't work or is too difficult.
"No! Please don't perpetuate this myth! Raytracing is NOT the holy grail.
For a reasoned argument, check out this article by Deano Calver. He worked at Ninja Theory on Heavenly Sword.
- anti-aliasing is hard
- moving scenes are VERY expensive
- it is almost fully procedural, so the artist has near zero stylistic control over the final look of a shot
Read the linked article. I have a few problems with it.
1. "Exponentially" is used to mean "multiplied". I know, it's common slang to say something which is twice as good (or even 1.5x as good) is "exponentially better", but when you're discussing the arcane aspects of different visual modeling approaches you should use precise language. Antialiasing requires "exponentially more" rays? No, it requires up to an order of magnitude more, which number does not keep increasing exponentially. In practice, it requires at least 4x, and could use 10x. Dealing with "soft" light sources doesn't require "exponentially more" rays, it requires a large multiplier more (on the lighting traces).
2. While he seems convinced that he's talking in general terms about ray tracing, he is using compromises being made *today* to make ray tracing *today* more efficient and saying that this means that ray tracing (which definitely describes the compromise-free variety as well as the pragmatic variety) is not really "the holy grail". I'm sorry, but every "problem" with compromises made from the ideal of ray tracing is countered by several endemic to rasterization. As a bit of a lay person here, when I hear "real time ray tracing is the holy grail", I read that as something we are striving for, not a description of something which has been achieved. Perhaps he is reacting to some marketing type who has proclaimed their implementation of real-time ray tracing to be "the holy grail", but that isn't clear in his writeup. Ray tracing as an approach is condemned universally.
3. Somewhat along the same lines as above, it is a completely different question to ask, "which approach will yield good enough results with acceptable performance?" Perhaps rasterization could improve to the point where it is "as good as" compute-intensive ray tracing. Perhaps "the right" compromises could likewise be made to ray tracing to improve its performance while not hitting the failings he cites. The question of which tool is right for the job at hand is quite different from which is most likely to produce the most lifelike results in a "pure" implementation on infinite future hardware, etc.
Realtime raytracing is old news for the demoscene. It's been done for many years, almost exclusively on the CPU only (without any additional GPU power).
Some more old and new real time raytracing demos:
"Chrome" was a 4KB intro that did realtime and precalculated raytracing back in 1995 on a 100MHz Pentium. It was not the first to do raytracing.
"Federation Against Nature" has specialized in raytracing, and have done some demos between 2000 and 2003.
The Realstorm Global Illumination Benchmark is a real time raytracer that also adds many other nice effects, and is from 2006.
Heaven Seven from 2000 has already been mentioned.
However it seems the demoscene has moved away from the idea for now for the same reasons that other people mention:
1) You get more "bang for buck" with rastering, especially with 3D HW.
For anything other than shiny quadratic solids, raytracing is terribly expensive and inefficient.
2) More creative control with rastering.
The classical raytracing algorithm is O(log n) (albeit a very
big O(log n)), while rasterization is O(n). This means that
eventually (for complex enough scenes) raytracing may actually
be faster than rasterization. This can already be shown for
simple (eye-rays only) raytracing.
I'm not sure if this is what you mean, but many people on the web are arguing the performance for large scene point by assuming that Scanline renderers render everything, using the painters' algorithms.
It isn't true.
As we know, renderers of all types, including real-time, cull the scene and use space partitioning techniques.
In fact performance is the reason why we use Render Man and not a ray tracer. It deals extremely well with extremely large scenes. Ray tracing requires often to have the entire scene in memory, for hit- testing, and requires tessellating all objects. The essence of PRMan, as mentioned above, is the minimal amount of work and memory required for scenes of any size.
Pure scanline rendering can't do real complex reflections and refractions, that's when we turn on ray tracing, and we only do so for these pixels.
When you've got proper ray tracing, with good anti-aliasing, you must then have Depth-Of-Field and motion blur.
So YES, the processing power grows exponentially in production.
Ray tracing is terrible at these, but it's practically free with PRMan. That's why we use it.
What a wonderful collection of gems? I had no idea this history existed. Thank you for sharing this with me. Thank you to Jeff and all commentators. Thank you, all ray tracers!
I had the juggler on my Amiga 2000 too in the late '80s. I bought a book about 3D computer graphics on the Amiga (in German...) and I've been interested in ray tracing ever since.
Great article. I really enjoyed reading it and following the links from the comments.
I'm an Amigan from way back and fondly remember my Amiga500 and like others here was amazed by the Juggler.
Guys, get up to date..
www.pouet.net/prod.php?which=32194 is beautiful real-time raytracing on the GPU WITH music all crammed into 4 kb.
Pyrolistical: if you have a millions-of-triangles model only taking up 1% of screen space, you're not going to render all those triangles even with a scanline renderer - you'll be using LOD and rendering a less complex model.
Which you'd also do when raytracing, I bet... even if it's only 1% of the fired rays that have a chance to hit the model, you'd still need to hit-test those rays against those millions of polys unless you use LOD?
Check out Winamp's AVS (Advanced Visualisation Studio) we have been real time raytracing with that /in software/ using a /scripting language/ since 2000.
Its a very wasteful way to render, but is actually /more/ efficient if you have enough limitations on your resources and some suitable way to read a texture using texture coordinates (Dynamic Movement in avs, bitmap loaders on other platforms).
I never said we did a good job of it though... its just the only efficient way to texture a 3d object using AVS. Although the last preset I released doing this used bump and specular mapping on a procedurally generated corridor in very low res...
Easy peasy... :P
Raytracing triangles is silly, you can use a fast rasterisation method then reverse engineer the rays if you need them for lighting effects etc... I'd imagine any modern implementation would do that. As the comment above suggests doing bounds testing on millions of triangles is a complete waste of CPU time and when we have hardware to render millions of triangles a second... it makes sense to use it.
This is why the juggler there is made of spheres, spheres are cheaper to raytrace than triangles (unless you do as suggested above) and you can combine them all efficiently with clever use of min and max on the raytrace parameter.
Just to add as well..
A lot of idiot comments here...
The complexity estimated mentioned above are crap, especially given that the meaning of n is not mentioned.
Depth of field and motion blur are not hard to implement on top of raytracing if you use a depth buffer and the classic "3 or 4 frames at a time" motion blur method. If your company is struggling with this, point them my way, I'd love to work for them.
As mentioned in some smarter posts above the idea of differentiation between ray-tracing and scanline methods is one born of ignorance. All modern ray-tracers and scanline renderers use methods from each others field... if they don't then they lose efficiency and/or prettyness.
Oh and a quick note, parallax mapping implementations are normally doing raytracing... so real time raytracing... nothing big, new or clever.
I still find it amazing it took 38 hours to render a single frame for the Transformers film.
Depth of field and motion blur are not hard to implement on top of
raytracing if you use a depth buffer and the classic "3 or 4 frames
at a time" motion blur method. If your company is struggling
with this, point them my way, I'd love to work for them.
DOF and motion blur are trivial to _implement_ with Ray Tracing, they are just prohibitive to use, and make the cost grow exponentially. That's the problem that REYES was designed to address, and what I was replying to.
Mental Image has been struggling with DOF and Motion blur performance and quality for more than 20 years.
These are the main reasons why film studios choose RenderMan instead of Mental Ray. Others that use Ray Tracing for rendering use 2D motion blur or 2D depth of field in post. Not casting other rays.
And what has Mental Ray been working on these last 10 years? The scanline mode of their ray tracer. They're in the business of making ray tracing for production.
The people who don't understand the current state of the technology argue the virtues of ray tracing based on 1980s ray tracing, and also 1980s quality expectation.
Let's say you have a super complex model with billions of triangles,
if the entire thing only filled up 1% of the screen, you are
still going to render all the triangles using scanline.
But with a raytracer, you'll only render the visible surface of
the triangle, which is only be a hand full of triangles.
The performance difference would be huge, even on todays hardware.
and yet, PRMan or a modern scanline renderers (Like Mental Ray in scanline mode) the same scenes that a ray tracers does, faster.
You're probably thinking of old A-buffer renders that don't do any BSP or anything else. It's ok, but no one uses that. In any case, this debates crops about about the domain of games and the CPU vs GPU rasterizer.
In games, a huge city is partitioned. Whether it would use the GPU or being ray traced, not the entire scene would be drawn.
Then, the GPU scales much better compared to hit testing every ray, even if it does redundant over-drawing. It's better to draw too much than to do a lot of work to avoid drawing a triangle, it parallelizes better right now and in the forseable future.
You take a look at the John Carmark article linked above.
I think that the holey grail for rendering isn't raytracing. It's physically correct renderers like Maxwell Render.
When you compare the difference in the output between a raytracer and a physically correct renderer, the results are an order of magnitude more realistic. Problem is that they are as slow today as a raytracer was 20 years ago :(
Yes all scanline renderers cull as much as it can, but it mostly culls the stuff not in view. This can make a huge difference.
Let's say you have a super complex model with billions of triangles, if the entire thing only filled up 1% of the screen, you are still going to render all the triangles using scanline.
But with a raytracer, you'll only render the visible surface of the triangle, which is only be a hand full of triangles. The performance difference would be huge, even on todays hardware.
The trade-off is, with scanline you can render the triangles serially, (low memory cost), but with a ray tracer you pretty much need it all in memory to do hit detection fast.
DOF and motion blur are trivial to _implement_ with Ray Tracing, they are just prohibitive to use, and make the cost grow exponentially. That's the problem that REYES was designed to address, and what I was replying to.
You misdunderstood. Its not significantly expensive. In big O terms its just a linear term on the end (dependent on the resolution). They do not make the cost grow exponentially unless you implement them badly. Whats wrong with distance dependent convolution based on the depth buffer contents for DOF? Rendering consecutive frames and blurring them together for motion blur?
Motion blur adds a multiplicative constant and DOF adds and additive one. The multiplicative one is annoying, but still neither actually affects the growth of the run time or the asymptotic run time...
Where can I sign up for a job at one of these companies struggling with these "problems"?
Hello all, very interesting discussion, please accept my humble post with a link to my website The Amusement Machine http://theamusementmachine.net which has some videos and screenshots of realtime raytracing on graphics hardware. One of the videos does contain normal hardware accelerated rasterization mixed with raytracing. All in real time.... I do apologize for no demo or exe but, I promise it will be up soon.
It's quite funny to read all the comments about raytracing vs. rasterising. You probably should'n pay to much attention on what the big players say.
Intel want to sell their (future) CPUs so they are hyping it.
Nvidea wants to sell their GPUs, so they are biased against it.
And John Carmark? He has enough knowledge and deep enough pockets to get all the nice visuals out of an GPU, so it doesn't really matter to him.
And at the moment it's the choice between using rasterising with an API or even complete engine, or writing a raytracer from scratch and probably ignoring those nice graphics cards most gamers spent much more money on, than on their CPUs. Anyone who needs to sell a (non exotic) game the next few years would be pretty silly to use raytracing.
But we are almost at the point where a raytraced game is feasible. On Highend hardware it may already be.
It won't look nearly as nice as those rasterised AAA Titles like Crysis and such, probably more like something from 10 years ago. But... if you want shadows, reflections, refractions or even combinations of that, with a raytracer you define the material, drop the object into the scene, and it works.
With a rasteriser, getting even one of those effects right in a scene, can give you a real headache.
If you can pay a dozend top coders and artists, it probably doesn't matter, but for a small, independent group on a budget, raytracing may become interesing very soon (2-3 years?).
And raytracing will scale better than rasterising for the future.
-rasterising doesn't scale nearly as good as raytracing over multiple processors.
-non local effects like shadows and reflektions and some kind of GI will become more and more important. Rasterising is local by desing. Only one triangele is accessed at a time. Raytracing will be more efficent for those effects, because you have access to the whole scene at any time, and always exactly know what you need to access.
-as triangles get smaller and smaller, rasterisers loose more and more of one reason for their efficency: Projecting a triangle onto the screen, and then drawing lots of pixels very fast.
-Yes, you can (and have to) divide scenes for rasterisers. But you can not divide it as fine grained as in raytracing, because then you would loose another reason for it's efficency: Just throwing lots and lots of triangles at the screen, without any complicated checks and computations. So what, you ask? I'm pretty sure, the more complexe the scenes and effects, the more you will see the difference of only accessing what you really need to.
-memory access in a good designed raytracer is actually very good. You get into trouble if you have for example lots of non planar, reflecting surfaces. But doing something like that with rasterising is much worse.
And please don't always assume the most naive aproach for implementing something for a raytracer.
Adaptive antialiasing only has a fraction of the cost of a naive implementation. Soft shadows can be sped up in a similar way.
And if nothing else helps, you can still use those hacks and tricks you have to use on a rasteriser.
And remember: you mostly compare software raytracers from hobby coders with little to no artistic skills to rasterisers running on highly evolved, dedicated hardware, showing the work of the industries finest artists.
Combining a raytracer and a rasteriser in an interaktive environment, like a game, makes little sense to me. If the raytracer isn't fast enough to render those secondary effects fullscreen, you can't allow the player to step close to an object that uses that effect. And if the raytracer is fast enough, your better off with raytracing only, because the worst case speed difference will be minimal, and it doesn't really matter if you have 100 or 1000 fps in the best case. And getting a rasteriser and a raytracer to work nicly together is something for another big headache.
GI is just something on top of rasterising or raytracing. But most GI algorithms will work much better with raytracing than with rasterising, and may even use the same resources (procedures/hardware) for tracing rays and intersecting geometry, as the raytracing part.
So to me it's pretty clear, raytracing is the future. It's probably just not as close as Intel wants us to believe.
If an individual ray intersects any "object", then a vector is calculated from the point of intersection to *every light source* in the scene (in your diagram this second vector is called the "shadow ray"). The angle between the original ray and this vector provides the basis for a number of different colour accumulation calculations.
Still not sure if this is for real or not:
especially the comment:
"The first quoted Daniel Pohl's work in which he was about to modify Quake IV to work with the Intel ray-tracing engine. Just using an 8-core Intel processor, Daniel was able to achieve almost 100 fps at the resolution of 1024x1024."
Great post Jeff. I still have my Amiga 2000. I attended AmigaWorld in DC too. Totally got me hooked on CG.
I still use my amiga 2000 - mostly for music composition - but I still play with ray tracing from time to time.
What a great retrospective! Those were the days. Geeks, not users, ruled.
The idea of being able to construct and visualize a virtual mathematical
reality captured all our imaginations back in Amiga days. I remember one of my favorites was the first Caligari Truespace renderer for the Amiga. It's now in its 7th incarnation for Windows at http://www.caligari.com although there's lots more competition out there now.
Pixar found that the REYES algorithm that they traditionally used was falling short in Cars. All that chrome, shiny metal and reflective glass meant that Reyes could not pick up on the multitude of reflections and refractions present. Hence, they started considering Ray Tracing for Cars which is why the time frame shot up. However, remember that for each minute of rendering time, it takes nearly 4 months to render a 90 minute movie at 30 frames per second, so 10 hours on average is a bit much. Some shots may have taken that long, but not all of them.
Also, they started work on some ray trace speed ups using adaptive sampling and multi-resolution geometry. You can read the paper on it at http://graphics.pixar.com/ (there are a number of very cool papers there).
Still love the Amiga and all its Ray Tracing glory.
Re : Deano Calver's article :
Aliasing could be solved by using an adapative technique (give rays a size, determine where each 'corner' of the ray hits, and if needed shoot additional rays). This also helps with refraction where a ray is skewed, each corner might hit a surface some distance apart, and thus require additional rays.
Moving scenes can fairly easily be solved by splitting geometry into static and non-static. Static geometry (walls and so on) has all the partitions pre-defined while the moving items (characters, vehicles) have moving bounding volumes that are tested per ray. The swaying grass problem can be solved by combining these two methods into a static partitioned volume defined based on the size of the moving geometry plus the maximum moving distance.
AFAIK Ray tracing is not a global illumination technique. Once you determine the point at pixel X,Y, you calculate the light off the number of light sources depending on colour, distance and angle the same as other rasterization techniques. Ray tracing gives you the basic facilities to create a better lighting model (i.e. shadow handling, ambient occlusion, and even radiosity) but it is not truly part of the algorithm.
However, he is correct that each solution requires more rays being fired off. When you consider that most solutions to visual problems with scanline techniques involve cheating in some way i.e. adding lights to simulate global illumination, pixel shaders for refraction and reflection maps, the answer in ray tracing will still always be based on firing more rays.
By the time we have enough processors on a single machine to make real time ray tracing a possiblity such hardware will allow far better results in other scanline methods.
Though you guys might find this QA on Raytracing and it's current place in game technology with John Carmack interesting.
Seems he doesn't think it's all that either, but I'll let you have a butchers.