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

The Solution

My esteemed Cordelia,

I must apologise. When I came to the close of my last Missive, I must have left you in a frightful state. To appeal to your fancy with stories of the wonders of parallax mapping, only to cruelly cut down the technique with diagrams of despair...! it strains morality. But fear not, Cordelia: I have a solution to the problems of parallax mapping. I will first solve a problem that you may not yet have thought of (although it is intimately related to the problem already discussed): That of a ray entering below the polygonal surface.

Let us return to the issue of the polygonal versus the virtual surface. Until now, I have treated them as two separate entities, linked by large-scale shape but unconnected otherwise. But this is not so! Pray examine, Cordelia, the other feature present in the first picture of that last posting: to wit, the brown line. If the polygonal surface places a maximum on the height of the virtual surface (normal to that polygon), then the brown line may be thought of as a minimum. These are two of the extents of the area in which the entire virtual surface must fall. In the two-dimensional case here, we need define two more: the left and right. Behold:


What, you may ask, does this gain us? Well, in this ideal case, nothing. But now consider this less auspicious viewing ray.


In this case, the viewing ray has no intersection whatsoever with the polygonal surface. How, then, is it to be rendered? The fragment program is never invoked!

And indeed, with classical parallax mapping it would not be. But in this picture I have also given the answer: The side itself is rasterized, and invokes the fragment program. Not the same fragment program as for the top face, for you may be certain, Cordelia, that it would be quite confused by its unexpected orientation and produce all manner of outlandish results. But some small modifications can easily correct this problem and lead to the correct generation of texture indices, ray marching, &c.

Nota bene: the sides, like the top, will benefit from backface culling. After all, a ray entering the box I have defined here will only produce a first intersection with the inside of one of the sides if it originates inside the box itself (a situation I do not here address) or through the bottom. But if the parent object is polyhedral and closed, no such ray can arise save one which originates in the cavity of the parent object, which is again a situation I do not here address. In the common case, therefore, the only possible explanation for a backface collision with either the top or the sides is that polygons have been rendered in a suboptimal manner, and that a later polygon will overdraw this one. Better, then, not to render this first erroneous polygon at all.

With condolences on the mishap that recently befell your livery,

Ben

Some specifics

My esteemed Cordelia,

Parallax mapping, in its essentials, may be quite simply described. One considers two surfaces: the polygonal surface described by the actual triangles sent to the renderer, and a virtual surface at some depth below the polygonal surface. This virtual surface may be of much higher resolution, as it is described by a texture rather than by geometry and thus fine details are a matter of texture memory rather than vertex transformation and triangle rasterization. It is this surface which is portrayed in the rendering.

But how, you may ask? How is this gallant Feat accomplished?

Why, by means of ray-tracing, Cordelia! When it comes time to render a Fragment of a triangle thus blessed with an underlying virtual surface, a complicated set of steps begins. The details of these machinations are the subject for another letter, but the geometrickal meaning is clear. Pray examine, Cordelia, the drawing below.




In this drawing, the green line represents the polygonal surface, and the black line the virtual surface. (Note that the green line is utterly flat-- this is the first murmur of the weakness of this Technique!) The yellow line represents a view ray which, under normal circumstances, would intersect the surface at the blue point and produce the image of a flat plane. Instead, the fragment program searches forwards in the bump map, in order to find not an intersection with the polygon surface, but one with the virtual surface. In this case, this is found at the red point. The program then renders the fragment as though it were at the red point, giving the illusion of depth where none exists.

I say "illusion", Cordelia, for such it is! In the published descriptions of Parallax mapping (see N. Tatarchuk's "Practical Dynamic Parallax Occlusion Mapping", &c.) a dreadful deception has been perpetrated upon the good people of Graphics! Virtually all examples in such publications show the technique applied only to large, flat planes, and then only to bump maps which tile seamlessly. Why? Because this technique fails in precisely the point where the surface bends. Witness the revised example below:

Here, the surface bends, avoiding any intersection with the viewing ray whatsoever. One would imagine the ray, therefore, to extend into blessed Oblivion, and produce no color or depth. Not so! Because the lookup is performed in texture space, rather than object space, the test proceeds as follows:


You see? It is as though a bend never occurred. The fragment shader has no way of discarding a fragment due to lack of intersection, because in the simplified geometry of parallax mapping, there will always be an intersection. Hence the only silhouette of a parallax mapped object is that of its accursed polygonal surface. This, then, is the weakness of the otherwise miraculous Parallax Mapping.

With hopes of a happy Feast of St. Agnes,

Ben

Introduction

My esteemed Cordelia,

Wondrous news! I have undertaken the design and construction of a new Technique for improved "parallax mapping" on the "graphical processing unit"! This Technique, if I may be so bold, promises to increase the realism with which parallax mapping displays curved objects obliquely, and at a relatively low cost in calculation. By making clever use of fins which point into the object, rather than out, it will be possible to clearly display the silhouettes of objects with the complexity their bump maps promise, rather than as mundane polylines. I need only finalise the details of the mathematics, and then implement the Technique. More to follow!

Hoping the dropsy does not take poor Thaddeus,

Ben