Of prisms and imprisonment

My esteemed Cordelia,

A thousand apologies for my extended incommunicado period. I was suddenly kidnapped and held as a hostage by bank robbers in Bahrain. There, through the grace of Providence, I was able to befriend a llama and ultimately effect my escape. Luckily this eventuality had been anticipated in my Gantt chart, so I am yet on track. Onward!

You will recall in my last Missive a description of a box with shaders applied to the sides and top. In three dimensions, the natural extension is a triangular prism: One triangular top face, and three rectangular sides. In this formulation, a mesh would be built up from intersecting triangular prisms, the top face of each corresponding to a triangle in the polygonal surface. The intersection of the prisms, however, is suboptimal, inasmuch as it can lead to overdraw and complicates the mesh structure.

Luckily, no intersection is necessary, because the "boxes" need not be prisms! Instead, they form arbitrary nonpyramidal triangular frusta, or trapezoids in the two-dimensional case. Each one has its top face as a face in the polygonal surface, as before, and the bottom face is a constant distance away, but the other three rectangular faces need not be orthogonal to the top face. Instead, these faces are simply chosen to avoid intersection with neighboring polygons, most easily by placing each one in the equiangular plane between the two faces which it connects. The result is a set of nonintersecting (but fully incident) frusta, each one defined by a top face, a depth, and three planes. A ray which is incident on a frustum, then, will find an intersection with the virtual surface no further than the point at which the ray exits the frustum by the top face or one of the three side faces. This point along the ray is easily determined with standard ray-plane intersection formulæ (provided, of course, that no ray is truncated by intersection from outside the frustum, as would be the case if the ray entered through the side of the frustum).

Implementation of the algorithm proceeds tolerably well. Switching from NVidia's FX Composer to a more low-level XNA housing has manifestly improved the ease with which I can test and debug problems which occur. A fascinating byproduct of the representation of frusta is that the same shader works equally well for sides as well as the top. All that is necessary is to define three-dimensional texture coordinates, such that the precondition that all points incident on the frustum have w=0 is relaxed.

With warm regards from Eswar the llama,

Ben