A Postscript package for rendering shadows on non-convex polyhedra

Source file: shadow.inc

Rendering non-convex objects is a complicated operation, even more so when shadows are taken into account.  The reason for this is that the object will often cast a shadow on parts of itself.  E.g. the sides of a box will cast a shadow on its interior, and one side of a torus will cast a shadow on another.  As we will explain, such a task is very computationally intensive, due to the multiplicative processes necessary.

Background

Some assumptions must first be made.  By convention, we will be dealing with objects represented as arrays of faces, each faces in turn consisting an array of vertices (each of which is an array of 3-dimensional coordinates) as well as the normal vector for each face; such as those examples provided in Chapter 14 of the text.  Also, all faces must be convex: any representation of an object containing non-convex faces must have those faces split up into adjoining convex faces.

Shadow rendering theory

Given a 3D object, we first determine which faces are " visible" to both the eye and to the light source, this is done by evaluating the project of the normal vector both toward the eye and toward the light source.  These are the faces which will cast a visible shadow on other parts of the object, as opposed to faces which are cast a shadow not visible to the eye or faces which simply do not face the light-source.  Thus by pruning the total number of faces to account for, we will be reducing the computational steps needed to render the object.  It will quickly become clear why this is desirable. 

To render the object, we make the use of Binary Space Trees (BSPs) as referred to in Chapter 14 of the text.  First the object is used to build the binary tree, then the tree traversal routine is called, passing in as an argument a rendering function that will be applied to each face.  We have designed this rendering function to be modular: it calls two separate user-definable sub-functions: one for rendering the surface of each face, another for rendering the shadow cast on each face.  Before the shadow rendering routine can be called, however, the shadows that fall on a particular face have to be calculated.

To calculate the shadows falling on a target face, we first need to calculate the plane of the target face, let's call this the target plane.  This is a simple matter of using the vertices of the plane and the normal function, since a vector orthogonal to the vertices will also be orthogonal to the plane. It is only necessary to perform this calculation once per target plane.

Next we project a face of the object from the coordinates of the light-source onto the target plane, which becomes the cast shadow.  The computations required for this operation are provided in Chapter 12 of the text.  Given points P (the project origin), Q (the point to be projected) and the formula f(x,y,z) = Ax + By + Cz + D = 0 of the target plane, the projected point R on the target plane is given by applying the following linear transformation to Q:

This transformation is performed on each vertex of the face to be projected.  Note that, ideally, a BSP algorithm should be used here too...this particular application commonly referred to as a Shadow Volume BSP (SVBSP).  The position of each face to be projected must be with that of the light source relative to the target plane.  If the light source and face to be projected are on the same side of the target plane, then a shadow will be cast.  If they are on opposite sides, then no shadow will be cast.  If the face spans the target-plane, then the face must be split into two portions and only the face on the same side of the target plane as the light-source will have its shadow cast.  However due to time constraints we have not implemented the algorithm to deal with a face that spans the target-plane.

Once a shadow has been cast on the target-plane, we must clip the image to the borders of the target face.  We take two vertices of the target plane and a third point not on the same plane (easily obtained by summing one vertex with the normal vector). This guarantees a plane that will intersect our target plane at one of its sides. If our face is a convex polygon, then the mean value of the vertices is some point in the interior of the face.  Evaluating f(x,y,z) at this mean point yields a value which must be less than zero -- as the Hodgman-Sutherland clipping algorithm removes the segment of a polygon where f(x,y,z) is greater than zero.  Thus if f(x,y,z) at the mean point is greater than zero, we change the signs of A, B, C, D to correct this.  We may then clip the cast shadow.  The following diagram gives an idea of what we have just explained, with PQRS being the vertices of the target face.

The process is repeated for each edge of the target-face in round-robin fashion.  Once we have obtained our clipped shadow (which may be clipped to nothing), it is then rendered with the user-specified shadow-rendering routine.  This is then repeated for all faces which will cast a shadow on a particular target-face.

Because we must project all the faces of the object onto every other face (even if we truncate the list of faces by visibility criteria) in order to project a shadow, it becomes clear that rendering the shadows cast becomes a very computationally intensive process.  In fact, this is an O(n²) complex operation...improved only marginally by the use of BSPs or any other data structure.

Using the package

Unfortunately our implementation of this algorithm is not robustly reliable, there are some kinks to be worked out.  However, it is very simple to use.

First define your object according to the previously mentioned convention, i.e. an array of faces, each faces an array of vertices and the normal vector.  Then define two routines which must be named surface-render and shadow-render, these are called by the predefined routine overall-render which is supplied to the BSP traverse routine.

The code snippet that then renders the image will resemble the following:

/b object /polygon-interp bsp-tree def

/E get-eye cim3d transform3d def
/light [5 2 4 0] normalized cim3d transform3d def

b /overall-render traverse

Examples

Due to the very intensive computation involved, the code seems to choke on objects with a large number of faces.  So the examples provided here have only a small number of faces in total.  However both are non-convex, and demonstrate the work in principle.

(source)

(source)

References:

http://www.cs.ucsb.edu/~cs180/notes/shadow.pdf