John Carmack has an ability to iterate and do throwaway experiments on complex code like almost no one else I can think of. I write complex code sometimes, but when I do I rarely want to just start over with a new approach again and again like he does.
It's awesome that when he lets us peek behind the curtain to see his process.
"Focused, hard work is the real key to success. Keep your eyes on the goal, and just keep taking the next step towards completing it. If you aren't sure which way to do something, do it both ways and see which works better." --John Carmack
"Putting creativity on a pedestal can also be an excuse for laziness. There is a lot of cultural belief that creativity comes from inspiration, and can't be rushed. Not true. Inspiration is just your subconscious putting things
together, and that can be made into an active process with a little introspection. Focused, hard work is the real key to success. Keep your eyes on the goal, and
just keep taking the next step towards completing it. If you aren't sure which way to do something, do it both ways and see which works better." - John Carmack
JC is technically brilliant but in other aspects of intelligence has been questionable. This interesting quote is a classic example of a Yogi Berraism. Claiming you can rush creativity, you just need to have the time to rewrite your complex code 2 or 3 times.
His claim is that doing a ton of really hard work repeatedly is still a lot faster and more reliable than waiting under the apple tree for a flash of inspiration.
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.
I would contend being under the apple tree is how it's done. Even for JC. Easy for him to say the contrary, when his business was always largely handled by others as a byproduct of him also being at the right-place at the right-time. This is why he's known to shut the door and hide. He didn't have to be a busy-body handling the day to day operations of id Software. It's the reason he was able to sit thinking about 2-3 shadow volume techniques, and the time to implement and test them all.
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.
Maybe on details, but we disagree that you can rush creativity or genius. His trial-and-error method got him shadow volume years after a separate pair of engineers discovered it. This is why most great discoveries are done in research environments with teams.
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.
Are there other indications this is the hard truth? It could turn out to be just one genius' creative process, where others do "idle under the apple tree". I believe Feynman's results about quantum theory did stem from idling and meddling with some non-interesting work, before the revelation dawned on him.
I've read about this too and it makes a lot of sense to me. I've been using Julia through LightTable and Juno, which makes these types of iterations and experimentation WAY easier and faster.
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.
Without having played Mario Galaxy myself, judging from screenshots it seems the game is using shadow maps[1] or just static geometry for fake shadows[2].
It looks quite fake. Most objects in the scene are not participating in casting shadows, and the shadows cast by the characters don't seem to be forged from their true silhouette.
This is pretty interesting to read, but does anyone have any good links that describe what shadow volumes are and why this solution was clever at the time? Is it still clever, or has some new method taken its place?
Caveat: I'm not a rendering engineer (though I do work in game development), so my knowledge might be a bit out of date or imperfect.
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 volumes have a number of disadvantages. You have to create geometry for every shadow casting object and for every light source for which it casts a shadow, this is a lot of geometry and a lot of CPU overhead, so you generally used them for static lights and only shadowed moving objects that crossed the light cone. These days CPU doesn't matter as much, but back in 2000 it was a big deal. It was hard to solve the problem in a general way, and you ended up asking your modelers to tag which objects could be shadow casters, which could be shadow receivers, and which lights corresponded to the shadows.
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.)
Another reason stencil shadows are difficult in a production environment is that any model that casts a shadow needs to be watertight (i.e. a manifold). Models need to have to full geometry for things like hair, thin fins, and grass.
Shadow mapping[1] has pretty much taken over at this point. This is mainly because of the high overdraw when rendering shadow volumes. You can also filter shadow maps to get soft shadows. This is not really possible with shadow volumes.
Raytraced shadows are starting to become feasible.
Let's not forget that he was not the first to come up with this technique. From wikipedia [1]:
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.
From my memory the only games which ended up using shadow volumes were Doom 3 and games based on the Doom 3 engine. Shadow maps always seemed like the way forward to me. That is purely based on my own "what looks better" scale. Given that most techniques in 3D programming are hacks to make things look better, I was surprised to see Carmack go down the shadow volumes path. It felt like he'd chosen it based on having nicer code versus an overall nicer looking game.
This is all my opinion of course.
I find shadow volumes tend to look better, at least cleaner anyway. Shadow mapping if not properly done can look glitchy and aliased. One surprisingly bad offender was Skyrim.
I recall seeing both shadow mapping and volumes in Far Cry. Mapping was generally used outdoors in daylight (parallel casted light), and volumes for point lights. F.E.A.R. used volumes extensively also.
Are there actual production games using ray traced shadows? For non realtime rendering the advantages are soft shadows through lots of rays, rendering in one pass, and no geometry based artifacts. To do them in games though you have to trace against some sort of geometry and that geometry has to be sorted every frame. Simple proxy geo and dynamic bvhs are feasible I'm sure, but it seems to me to be a solution in search of a problem for the time being since all geo to be traced must stay in memory (and for transparency, the opacity textures as well). Now filtering cone sampling of volumes like the Unreal engine is a different story.
There is nothing new about the idea that to determine whether a point is inside a shape (2D or 3D), you can extend a ray from that point to infinity and then count the transitions across object boundaries. If the count is odd, the point is inside, otherwise it is outside.
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!)
In/out works for shapes in geometry with continuous boundaries. But digital shapes are defined by vertices. If your ray intersects a vertex right as it inflects back (tangent to a corner) a 'crossing' gets counted yet nothing was crossed?
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?
For a convex polygon, you can determine whether a point is inside or outside by giving each edge an consistent orientation around the path. Then check where the point lies w.r.t. that orientation: is it to the left of the line or to the right? If the polygon is counter-clockwise, say, and the point is to the left of every edge-line, then the point is inside. This extends to 3D convex polyhedra, where you have a consistent orientation of each face. If a point is in the negative half-space of each face, then it is inside.
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.
And for what shadow volumes are: It is basically an imaginary volume that encloses the shadowed area on your world. For example a sphere produces a cone shaped shadow volume behind it when a point light hits it. In computer graphics you can use this geometry to render shadows on object.
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
And this follows on insightfully from the discussion on "slow" programmers. In most cases in the "business" world someone like Carmack would have been reamed for re-implementing code that already worked, or for taking valuable time away from the next project.
That would only happen if someone was like him and was being micro-managed by a manager who wasn't familiar with him yet. John Carmack is crazy productive, the vast majority of Quake (and predecessors) was written by him. Anyone with a head on his shoulders watching over him for very long would see him outperforming possibly the entire team and trust his judgement.
It's awesome that when he lets us peek behind the curtain to see his process.