Overview

Figure 2: A set of points with normals partitions space into cells (one is shaded) which can be traversed in order by a ray. This observation holds in 3D as well. An analogous partition can be added within each cell.

The inspiration for our method comes from the REYES rendering architecture [3]. That simple architecture has worked well for almost two decades, and relies on three simplifying assumptions related to displacements:

• displacements are bounded in distance,
• base surfaces know how to subdivide themselves,
• subdividing the displaced base surfaces into a net of simple sub-pixel patches provides sufficient accuracy.

We borrow these assumptions directly. By assuming that a finely subdivided model provides sufficient accuracy, we can use micropolygon normals directly, so no derivative properties of the displacement need be known. We also add the assumption that the displacements are along the direction of the interpolated normal. Although this is more restrictive than the displacement mapping found in the REYES architecture, it is the type of displacement mapping found in Maya[1]. For the intersection method, first imagine a base surface being ``carved up'' with a set of vertices and normals (Figure 2). Within each partition we could displace a triangle whose vertices lie along projected normal vectors from the base surface. If one considers a given triangle under all possible displacements, it sweeps out a 3D region in space. For reasonably well-behaved surfaces, adjacent triangles have adjacent regions. The shape of the boundaries between these regions depends on how the normal vectors of base geometry behave. If one imagines all the regions swept out by all triangles, each triangle forming a ``column'' in space, the possibility of a traversal algorithm presents itself. If the base geometry is a plane then all displacements are perpendicular to the plane and the traversal algorithm would be similar to that usually used for ray intersections with height fields [9], except that the traversed cells would have triangular rather than rectangular cross-sections. We would like to choose a base geometry that is general enough to be geometrically expressive, but restrictive enough that such a traversal algorithm is feasible.

Because they are so often used in practice, three obvious choices are NURBS surfaces, subdivision surfaces, and implicit surfaces such as metaballs. Since all three of these primitive types are quite different from each other, it is desirable to find a common representation that they could all be converted into. The only obvious choice for this common representation is a triangulated mesh, to which it is straightforward to convert for NURBS and subdivision surfaces, and at least feasible for implicit surfaces [14]. For this reason we choose triangles as our base geometry. To ensure that the displaced surface is continuous, we use shared vertex normals and displace along normals computed via barycentric interpolation (i.e., Phong normal interpolation [13]). Although more general displacements are useful [10], we leverage this restriction on the direction of displacement to create a simpler algorithm than would be possible otherwise.

Figure 3: A simple displacement by function $h$ in the normal direction creates a new curve in 2D.

We strengthen the restriction of a bound on the displacement to limit the range of possible displacements so that any resulting displaced surface is unable to intersect itself. Each point in the valid region corresponds to exactly one position and displacement value on the base triangle. This restriction means that each region has only one set of neighbors, another requirement for a simple traversal algorithm. It also means that the first intersection found will be the closest intersection to the ray origin.

Figure 4: Icosahedron with displacement pushing each point to a sphere, $N=1,4,100$.

Our displacement framework assumes there is a point ${\bf p}$ on an underlying surface which is displaced in the direction of the normal vector $\mbox{${\bf n}$}$$($$\mbox{${\bf p}$}$$)$ by a displacement function $h($$\mbox{${\bf p}$}$$)$ (Figure 3). For a triangle with points $\mbox{${\bf p}$}$$_0,$$\mbox{${\bf p}$}$$_1,$$\mbox{${\bf p}$}$$_2$ and corresponding normals $\mbox{${\bf n}$}$$_0,$$\mbox{${\bf n}$}$$_1,$$\mbox{${\bf n}$}$$_2$ the bilinearly interpolated points and normals $\mbox{${\bf p}$}$ and $\mbox{${\bf n}$}$ are:

$$\mbox{${\bf p}$} = \alpha \mbox{${\bf p}$} _0 + \beta \mbox{${\bf p}$} _1 + \gamma \mbox{${\bf p}$} _2,$$

$$\mbox{${\bf n}$} = \alpha \mbox{${\bf n}$} _0 + \beta \mbox{${\bf n}$} _1 + \gamma \mbox{${\bf n}$} _2,$$

where $(\alpha,\beta,\gamma)$ are the barycentric coordinates on the triangle, so $\alpha+\beta+\gamma=1$. Our displaced surface $\mbox{${\bf p}$}$$_d$ is thus:

   $$\mbox{${\bf p}$}$$$$_d = \alpha$$$$\mbox{${\bf p}$}$$$$_0 + \beta$$   $$\mbox{${\bf p}$}$$$$_1 + \gamma$$$$\mbox{${\bf p}$}$$$$_2 + h(\alpha$$$$\mbox{${\bf p}$}$$$$_0 + \beta$$   $$\mbox{${\bf p}$}$$$$_1 + \gamma$$$$\mbox{${\bf p}$}$$$$_2) \left(\alpha\mbox{${\bf n}$}_0 + \beta \mbox{${\bf n}$}_1 + \gamma\mbox{${\bf n}$}_2 \right)$$