[ Home ] [ Up ] [ Rendering Hair ] [ Displacement Mapping ] [ Visibility Maps ] [ Motion Blur ] [ Ray Tracing ] [ Programming ]

Introduction

As computers grow faster and faster, displacement mapping is quickly becoming a preferred alternative to the more efficient but physically inaccurate technique of bump mapping. I am close to completing a project in optimizing the displacement mapping functionality of R&H's renderer.

Renderers based on the REYES architecture subdivide all geometry into micropolygons. This is of great advantage when it comes to displacement mapping, since no further subdivision is needed. However, our renderer is scanline-based, so it deals most efficiently with larger triangles. This is why it is essential to restrict the subdivision to only those those triangles that actually require it in order to adequately portray the displacement map.

Click on thumbnails for full-size image.

Implementation

Given a triangle mesh that is sufficiently subdivided to convey the desired displacement map, the displacement itself is easily accomplished: We translate each vertex along its normal by a distance that is derived from the displacement map at the vertex's texture coordinates. If a vertex has more than one normal, as is the case along a crease or corner, it can be displaced by some combination of these normals (or not at all). A more general implementation would allow each vertex to be displaced along an arbitrary vector; however, the vertex normal is what is typically used. 

While vertex displacement itself is easy, there are two basic challenges in preparing a triangle for displacement with a given map:

We tackle these as follows.

Determining Triangle Subdivision

We allow a user-defined tolerance to govern the overall level of triangle subdivision. In addition to this, we weigh two other factors in deciding whether to subdivide a particular triangle: the size of the triangle, and the maximum amount of variation that occurs in the displacement over the triangle. In our implementation, we equate the triangle's size with its area and we equate the map variation with the absolute value of its second derivative.

Conveniently, the area is a byproduct of computing the triangle's normal (which is needed to compute the vertex normals). The map's second derivative is less obvious. We are looking for a scalar value that indicates the greatest absolute rate of change of gradient. For each pixel, we consider the 8 neighboring pixels as shown below:

To calculate the absolute derivative of the gradient, we treat the grid of nine pixels as a height field. Conceptually, we construct a fan 8 triangles originating from the center pixel to each of the outer ones. Our measure of the second derivative is based on the greatest angle between the normals of any two of these triangles. Much of the intermediate math, involving cross products, vector normalization, and dot products, can be simplified down to a formula that gets applied at each pixel.

In this way, we construct a new single-channel map containing the maximum gradient derivative at each pixel. Then we scan convert each triangle in texture space, checking whether any interior pixel exceeds a pre-computed threshold, which is just the product of the user-specified tolerance and the triangle's area.

The following are two examples of maps, their gradient derivatives, and the resulting subdividied and displaced geometry:

Maps and corresponding absolute gradient derivatives.

Original and displaced meshes.

Subdividing A Triangle

We choose a simple subdivision scheme that replaces a triangle with four subtriangles. Each edge is split at its midpont and the resulting vertices, after minor adjustment, are retriangulated as shown below:

Basic triangle subdivision rule.

This scheme appears easy, but there are a few complications. First, we must keep track of shared edges, so that these are not split twice. This is done by identifying each edge with the ordered pair of its vertex identfiers, and using the sign of the edge index to denote direction. The edges are stored in a hash table, so that an edge can be quickly located given the pair of vertex id's that it spans.

Repairing the Mesh After Subdivision

Unless all the triangles are subdivided equally, some will end up containing an edge that is split (this happens when a triangle is split but one of its neighbors isn't). Such a triangle needs to be fixed in order to eliminate T-junctions, cases where a single edge spans the same line as two or more other edges. (T-junctions are generally to be avoided in rendering, but particularly so with displacement mapping, as they cause cracks in the displaced mesh.) Although subdividing this triangle repeatedly would fix the T-junctions, this would propagate the problem through the rest of the mesh, forcing all the triangles to be subdivided equally. Instead, we must subdivide the problem triangle in a way that does not further split any of its edges.

To do so, we first consider whether all of the edges have been split. If so, we just subdivide the triangle into 4 subtriangles and recursively apply the same process. If not, at least one edge is not split. We then form a zigzag triangulation along the two other edges, until we've reached the second-last vertex of one of the edges. At this point, we form a fan of triangles from this vertext to the remaining vertices of the other edge.

This is how we repair a post-subdivision triangle with split edges.

Preserving Curvature

Another challenge is to preserve the implicit curvature of the original mesh in the subdivided one. If we added new vertices at the exact midpoints of the edges being split, we would end up with a perfectly planar mesh of subtriangles. While this may be the desired look for a faceted surface, it is not representative of a smooth, curved surface. To accommodate the latter, we adjust the position of the new vertex created by splitting an edge that divides triangles belonging to the same smoothing group.

There are many ways to derive the position of the midpoint vertex so as to preserve curvature. Subdivision schemes such as Loop's scheme or the Butterfly scheme would guarantee a smooth and consistent surface. However, these schemes are somewhat expensive because they require access to neighboring edges. Our solution is to base the position of the midpoint vertex on just the positions and normals of the endpoint vertices. To accomplish this, we first construct tangent vectors at the endpoints, which are orthogonal to the normals. This is trivial in the 2-D case, but with three dimensions, we have an extra degree of freedom to play with. So we constrain the tangents to be in the direction of the difference vector between the endpoints, and orthogonal to the normals. With the tangents so defined, we can now construct a hermite interpolant passing through the endpoints. By evaluating the interpolant at the midpoint, we derive the position of the new vertex. For the normal, we simply use the average of the endpoint normals.

We construct a hermite interpolant to determine the position of the midpoint.

This approach works well provided that the normals at the endpoints are not too far apart, which is a reasonable requirement for displacement mapping, since the base mesh should aready be subdivided finely enough for rendering without displacement mapping. Thus, the midpoint vertices added by subdivision will be very close to the linear midpoint between the edges.

Future Work

One problem we need to address is that the varying sizes of the triangles in the final displaced mesh tend to produce artifacts in the shading. This occurs because our rendering pipeline does not store vertex normals in the geometry, but rather computes them by adding together the geometric normals of the triangles that contain them. Since the area of each triangle affects the weighting of its contribution to a vertex normal, having triangles of different sizes sharing a vertex (e.g. sliver triangles alongside thicker ones) can result in inconsistent shading. I believe the best solution will be to explicitly store the post-displacement vertex normals in the model, rather than deriving them from the triangle normals of the post-subdivided mesh.

Another area that could use improvement is our subdivision vertex placement, used to preserve mesh curvature. Although the hermite interpolation we discussed yields reasonable surfaces for base meshes that contain only slight curvature,  we could lift that restriction and produce even smoother subdivided meshes by adopting a more advanced subdivision algorithm such as Loop's scheme, or the modified butterfly scheme. This would require keeping track of neighboring geometry in the mesh, which could significantly increase the time and memory needed for subdivision. However, since subdivision time is generally very small relative to rendering time, this would likely be a reasonable price to pay for the ability to use displacement mapping on coarser meshes.