News for hackers. Stuff that matters.
Re:John Carmack on shadow volumes (2000) by kazinator on Tuesday December 02, 2014 @10:40AM (#8687613)
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!)

Re:John Carmack on shadow volumes (2000) by JoeAltmaier on Tuesday December 02, 2014 @10:42AM (#8687628)
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?

Re:John Carmack on shadow volumes (2000) by kazinator on Tuesday December 02, 2014 @12:23PM (#8688304)
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.

Re:John Carmack on shadow volumes (2000) by moogleii on Tuesday December 02, 2014 @11:09AM (#8687772)
Alas, if only you had been there 14 years ago to create that cleaner, yet performant solution.
Re:John Carmack on shadow volumes (2000) by kazinator on Tuesday December 02, 2014 @12:17PM (#8688245)
I know! I somehow lost interest in hacking on computer graphics about 20 years ago though.