John Carmack on shadow volumes (2000)
fabiensanglard.net
fabiensanglard.net
It's awesome that when he lets us peek behind the curtain to see his process.
The flash-of-inspiration mode of creativity has been dramatized so much that most of the population assumes that's just how it's done. It also seems way easier than hard work, so people want it to be true when they try to be creative. Simultaneously, it seems way less attainable than plain old hard work (the requirements seem to be mostly circumstance), so people also want it to be true when they are not trying to be creative ("My great idea just hasn't come to me yet!").
JC is reminding us of the hard truth: the reality behind the stories is that creativity is the prize of determination, not serendipity.
If that's not the 'apple tree' of software development, I don't know what is.
I'd bet my life that if you have no time to sit and think, just a busy-body answering phone calls, emails, you're not coming up ideas. At one point JC did sit and think, hard. Then he implemented hard.
Through the whole process he had isolation, so he really was 'under the apple tree'. Irregardless if his process involved building prototypes of his various ideas.
He in my view, failed to see that he just filled his 'apple tree' time with tinkering. Some people plant a garden while thinking about code, or focus intently. I'm not sure there's much difference between methods, it depends on the field and person.
The most complex fields, involving what I'd consider true genius cannot be tested. It's just too general of a statement, and only relevant to him or a portion of the population.
But this is Carmack as I've always seen him. Technically brilliant, missing the big picture (his games were in some cases restricted simply to show off a technical feature eg. the Doom 3 flashlight), and fairly narrow minded.
Inspiration can sometimes show you which path to take, but in the absence of inspiration, simply brute forcing will keep you moving forward as well.
Especially helpful is the ability to use GLFW, OpenGL, GTK, and Gadfly to visualize what is going on.
Stencil buffer shadows were very popular in the mid 2000s because of their performance and relative simplicity in implementation. Their main drawback is that there is no easy way to get a soft penumbra around shadow edges. You can spot them in many games from the last generation because of their universal hard edges -- an area is either in shadow or not. See: Mario Galaxy, etc.
[1] http://screens.latestscreens.com/wii/screenshots/supermariog...
[2] http://images9.gry-online.pl/galeria/galeria_duze3/169624250...
It's very clever, and leads to pixel-perfect shadows. the other main technique used to do real time shadows, shadow mapping, writes them to a buffer, so if you have a larger buffer you get better shadows, and with a smaller buffer you get worse, more aliased shadows (there are techniques to make this harder to notice, though).
Shadow volumes is also typically slower, and puts (more) restrictions on your geometry than shadow mapping, so my experience is that most engines use shadow mapping.
Though, I think I remember one of the rendering engineers saying that shadow volumes is much easier to implement for small engines, and that he's disappointed it isn't more widely used, but I might just be thinking of some other less robust method of stencil-buffer shadowing.
Searching shadow mapping and shadow volumes in Google looks like it leads to good links if you're interested in learning more.
Shadow maps are faster and compounding shadows is much easier. What you do is render the subset of the scene that you want casting shadows from the point of view of each light source that you want casting shadows, and then render the entire scene once for each light, using the shadow map to kill fragments that aren't illuminated. Back in the late 90's and 2000, you could potentially have one, maybe two shadow maps. The downside is resolution, but you can play tricks with the projection matrix to bias the pixellation artifacts into more distant areas.
Pre-computed shadow volumes were awesome for static lights, where you didn't have to pay the geometry compute overhead every frame, and shadow maps were awesome for things like flashlights and moving lights, since they allowed moving the shadow compute complexity to the GPU. When the Riva TNT2 came out, and you could multi-texture, shadow map performance doubled.
Lighting is hard! If you have 2 shadow-map shadow casters, and one shadow volume, you're rendering the scene at least 5 times and the shadow volume twice, using the geometry processor to kill front or back sides from the point of view (can't pre-compute this).
(I've been working on this stuff since the 90's. SGI was doing this stuff years before games, but it just wasn't well known because nobody could afford those damn things, it took cheap 3D commodity hardware to make this work really fun, well, minus the whole thing about it sucking to work in the games industry.)
Raytraced shadows are starting to become feasible.
William Bilodeau and Michael Songy discovered this technique in October 1998, and presented the technique at Creativity, a Creative Labs developer's conference, in 1999.[2] Sim Dietrich presented this technique at both GDC in March 1999, and at Creativity in late 1999.[3][4] A few months later, William Bilodeau and Michael Songy filed a US patent application for the technique the same year, US 6384822 , entitled "Method for rendering shadows using a shadow volume and a stencil buffer" issued in 2002. John Carmack of id Software independently discovered the algorithm in 2000 during the development of Doom 3.[5] Since he advertised the technique to the larger public, it is often referred to as Carmack's Reverse.
Math was excluded, as was computer code as a specific usage of mathematical logic.
But slowly patents on computer code made its way into patents, initially as code controlling mechanical or chemical processes.
Looks like some sort of volumetric ray marching approach acceleratred by a signed distance field. Does anyone know what it is?
Also small nitpick: you don't filter the shadow map, but the resulting shadow response.
Secondly, this ray can be extended in any direction; it doesn't matter.
In the shadow volume rendering algorithm, they were originally casting that ray from the visible point on an object (corresponding to a pixel) back toward the eye. Carmack realized that you can cast it away from the eye. But that ray can obviously go in any direction. The eye has nothing to do with whether the point is in a shadow. Of course the algorithm breaks sometimes if the ray is cast toward the eye, and stops at the eye, since it hasn't gone to infinity. So if the eye is in shadow, then the ray has failed to emerge from that shadow, and count that.
I suspect that a much cleaner solution would be to cast the ray toward the light source! Then we only have to consider the silhouette polygons/surfaces, basically: the light-source-side "caps" of the shadow volume. We don't even need the shadow volume as such; we don't need the sides (because they are parallel to any ray we cast toward the light source) and we don't need any caps on it on the opposite side, away from the light source.
The down side, however, is that casting rays not in the eye direction means considering objects that are not in the visible scene. Your database of objects for the frame has to include anything that can potentially be between the light source and the visible point. The beauty of the shadow volumes algorithm is that it can work with viewport-clipped data. (And that is why you want to cast that shadow volume intersecting ray away from the eye: because stuff behind the eye is clippped!)
Another way to do this is to count the area from a point (sum of dot products of consecutive shape vertices). If its positive - inside. If its negative - outside?
These approaches require traversing the whole shape though, whereas the ray-intersecting approach works with clipped pieces (that are not necessarily even connected to form a complete shape). You don't even know which pieces belong to which volumes, necessarily.
Imagine a ray coming out from your eye, if that ray first hits a shadow volume and then an object then that point of that object is inside shadow. If ray never hits the volume or passes through volume
Crazy. Slow is smooth, smooth is fast.