Rahul P. Sathe, Advanced Visual Computing, Intel Corp
DirectX 11 has introduced hardware tessellation in order to enable high geometric detail without increasing memory usage or memory bandwidth demands. Higher-order surface patches with displacements are of prime interest to game developers, and we would like to render them as efficiently as possible. For example, we would like to cull subdivision surface patches (instead of the resulting triangles) that will not affect the final image. Culling a given patch avoids higher-order surface evaluation of domain points in that patch as well as processing of the triangles generated for the patch. The nature of higher-order surface patches coupled with displacements and animation make the process of culling them non-trivial, since the exact geometric bounds are not known until well after the opportunity to cull a given patch. In this chapter, we will present an algorithm that evaluates conservative bounding boxes for displaced approximate Catmull-Clark subdivision surface patches at run time, allowing us to perform view frustum culling on the patches. With this method, we achieve performance improvement with minimal overhead.
Before describing our culling strategy, we must review the fundamentals of Catmull-Clark subdivision surfaces, displacement mapping, and the methods that are currently in use to approximate Catmull-Clark subdivision surfaces on DirectX 11.
Catmull-Clark subdivision surfaces have become an increasingly popular modeling primitive and have been extensively used in offline rendering [DeRose98]. In general, subdivision surfaces can be described as recursive refinement of a polygonal mesh. Starting with a coarse polygonal mesh M0, one can introduce new vertices along the edges and faces and update the connectivity to get a mesh M1, and repeat this process to get meshes M2, M3, and so on. In the limit, this process approaches a smooth surface S. This smooth surface S is called the subdivision limit surface, and the original mesh M0 is often referred to as the control mesh.
The control mesh consists of vertices connected to each other to form edges and faces. The number of other vertices that a given vertex is connected to directly by shared edges is called the valence of a vertex. In the realm of Catmull-Clark subdivision surfaces, a vertex is called a regular or ordinary vertex if it has a valence of four. If the valences of all of the vertices of a given quad are four, then that quad is called an ordinary quad or an ordinary patch. The faces that have at least one vertex that is not valence four are called extraordinary faces (or patches).
Recently, Loop and Schaefer introduced a hardware-friendly method of rendering Approximate Catmull Clark (ACC) subdivision surfaces, which maps very naturally to the DirectX 11 pipeline [Loop08]. At its core, the ACC scheme maps each quadrilateral from the original control mesh to a bi-cubic Bezier patch. Loop and Schaefer show that, for ordinary patches, the bi-cubic Bezier corresponds exactly to the Catmull-Clark limit surface. Extraordinary patches do not correspond exactly to the limit surface, but Loop and Schaefer decouple the patch description for position attributes and normal attributes in order to reduce the visual impact of the resulting discontinuities. To do this, for extraordinary patches, ACC generates separate normal and bi-tangent patches in order to impose GN continuity at patch boundaries. The word “approximate” in ACC has its roots in the fact that these extraordinary patches are GN continuous, and this GN continuity only guarantees the same direction of partial derivatives but not the magnitudes across the patch boundaries. The ACC scheme describes the normals and bi-tangents using additional Bezier patches, which results in a continuous normal field even across edges of extraordinary patches.
Although it is very empowering to be able to generate smooth surfaces from polygonal meshes procedurally, such smooth surfaces are rarely encountered in real life and lack realism without additional high-frequency geometric detail. This is where displacement maps come into the picture. Displacement maps are simply textures that can be used to store geometric perturbations from a smooth surface. Although normal maps and displacement maps have the similar effect of adding high-frequency detail, the difference is notable around the silhouettes of objects. A normal mapped object’s silhouette lacks geometric detail because only per-pixel normals are perturbed and not the underlying geometry, as illustrated in Figure 1.4.1. To add this high-frequency detail, displacement maps can be applied to subdivision surfaces.
DirectX 11 has introduced three new stages to the graphics pipeline to enable dynamic on chip tessellation, as shown in Figure 1.4.4. The two new programmable pipeline stages are the hull shader and the domain shader. Between these two programmable stages lies a new fixed function stage, the tessellator. Fortunately for us, ACC and Direct3D 11 were designed with each other in mind, and there is a natural mapping of the ACC algorithm onto the Direct3D 11 pipeline.
As illustrated in Figure 1.4.1, the new hull shader stage follows the traditional vertex shader. In a typical implementation of ACC on Direct3D 11, the vertex shader is responsible for performing animation of the control mesh vertices. In the hull shader, each quadrilateral’s four vertices and its one-ring neighborhood are gathered from the output of the vertex shader. These vertices are used to define the control points of a bi-cubic Bezier patch. This basis conversion process that generates the Bezier patch control points is SIMD friendly, and every output control point can be calculated independently of others. In order to exploit this opportunity for parallelism, this control point phase of the hull shader is invoked once per control point. In the case of ACC, the basis conversion process depends on the topology of the incoming patch, but the output control points are always a 4×4 Bezier control mesh. Please refer to the sample code on the CD.
In addition to the computation of the Bezier control points, the hull shader can optionally calculate edge tessellation factors in order to manage level of detail. One can assign arbitrary tessellation factors to the edges of a patch (within some constraints, defined by the DirectX 11 tessellator specifications). Because the hull shader is programmable, one can choose any metric to calculate edge tessellation factors. Typical metrics may include screen space projection, proximity to silhouette, luminosity reaching the patch, and so on. The calculation of each edge tessellation factor is typically independent of the others, and hence the edge tessellation factors can also be computed in parallel in a separate phase of the hull shader called the fork phase. The final stage of hull shader is called the join phase (or patch constant phase) and is a phase in which the shader can efficiently compute data that is constant for the entire patch. This stage is of most interest to us in this chapter.
The tessellator accepts edge LODs of a patch and other tessellator-specific states that control how it generates domain locations and connectivity. Some of these states include patch topology (quad, tri, or isoline), inside reduction function (how to calculate inner tessellation factor(s) using outer tessellation factors), one-axis versus two-axis reduction (whether to reduce only one inner tessellation factor or two—once per each domain axis), and scale (how much to scale inner LOD). The tessellator feeds domain values to the domain shader and connectivity information to the rest of the pipeline via the geometry shader.
In the case of quadrilateral patch rendering, the domain shader is invoked at domain values (u,v) determined by the tessellator. (In the case of triangular patches, the barycentric coordinates (u,v,w); w = 1 – u – v are used.) Naturally, the domain shader has access to output control points from the hull shader. Typically, the domain shader evaluates a higher-order surface at these domain locations using the control points provided by the hull shader as the basis. After evaluating the surface, the domain shader can perform arbitrary operations on the surface position, such as displacing the geometry using a displacement map.
In ACC, we evaluate position using bi-cubic polynomials for a given (u,v). Our domain shader interpolates texture coordinates (s,t) from the four vertices using bilinear interpolation to generate the texture coordinates for the given (u,v). We also optionally sample a displacement map at these interpolated texture coordinates. As mentioned earlier, normal calculation is different for ordinary and extraordinary patches. For ordinary patches, we just calculate d/du and d/dv of the position and take the cross-product. For extraordinary patches, we evaluate tangent and bi-tangent patches separately and take their cross-product.
The mapping of ACC to the DirectX 11 pipeline that we have described allows us to render smooth surfaces with adaptive tessellation and displacement mapping, resulting in a compelling visual quality improvement while maintaining a modest memory footprint. At the end of the day, however, we are still rendering triangles, and the remaining stages of the graphics pipeline are largely unchanged, including the hardware stages that perform triangle setup and culling. This means that we perform vertex shading, domain shading, tessellation, and hull shading of all patches submitted to the graphics pipeline, including those patches that are completely outside of the view frustum. Clearly, this provides an opportunity for optimization. The main contribution of this chapter is a method for frustum culling patches early in the pipeline in order to avoid unnecessary computations. Of course, we must account for mesh animation and displacement, both of which deform a given patch in a way that complicates culling. An elegant generalized solution to surface patch culling has been proposed by Hasselgren et al. that generates culling shaders, looking at domain shaders using Taylor Arithmetic [Hasselgren09]. This article proposes a simplified version of ideas discussed in their work to cull the approximate Catmull-Clark patches against view frustum.
We perform a pre-processing step on a given control mesh and displacement map in order to find the maximum displacement for each patch. Please note, although the positions are evaluated as bi-cubic polynomials using the new basis, the texture coordinates for those points are the result of bilinear interpolation of texture coordinates of the corners. This is due to the fact that the local (per-patch) uv-parameterization used to describe the Catmull-Clark surface and the global uv-parameterization done while creating the displacement map are linearly dependent on each other. Figure 1.4.3 shows one such patch. This linear dependence means that straight lines u = 0, v = 0, u = 1, and v = 1 in the patch parameterization are also straight lines in the global parameterization. Due to this linear relationship, we know the exact area in the displacement map from which the displacements will be sampled in the domain shader for that patch. The maximum displacement in the given patch can be found by calculating the maximum displacement in the region confined by patch boundaries in the displacement map. Even if the displacement map stores vector-valued displacements, the mapping is still linear, so we can still find the magnitude of the maximum displacement for a given patch. Based on this, we can create a buffer for the entire mesh that stores this maximum displacement per patch.
Figure 1.4.3. Mapping between global (s-t) and local (u-v) parameterization is linear. The figure on the left shows (u,v) parameterization that is used for patch evaluation. The figure on the right shows the global parameterization (s,t) that was used while unwrapping original mesh. Bold lines correspond to u=0, v=0, u=1, and v=1 lines in the figure on the left.
At run time, the patch vertices of the control mesh go through the vertex shader, which animates the control mesh. The hull shader then operates on each quad patch, performing the basis transformation to Bezier control points. One convenient property of Bezier patches is that they always stay within the convex hull of the control mesh defining the patch. Using the maximum displacement computed previously, we can move the convex hull planes of a given patch outward by the maximum displacement, resulting in conservative bounds suitable for culling a given patch. Although moving the convex hull planes out by the max displacement may give tighter bounds compared to an axis-aligned bounding box (AABB) for the control mesh, calculating the corner points can be tricky because it requires calculation of plane intersections. It is simpler and more efficient to compute an AABB of the control mesh and offset the AABB planes by the maximum displacement.
In Figure 1.4.5, we show a 2D representation of this process for illustration. Dotted black lines represent the basis-converted Bezier control mesh. The actual Bezier curve is shown in bold black, displacements along the curve normal (scalar valued displacements) are shown in solid gray, and the maximum displacement for this curve segment is denoted as d. An AABB for the Bezier curve is shown in dashed lines (the inner bounding box), and the conservative AABB that takes displacements into account is shown in dashed and dotted lines (the outer bounding box).
Figure 1.4.4. The DirectX11 pipeline. Normally, triangles get culled after primitive assembly, just before rasterization. The proposed scheme culls the patches in the hull shader, and all the associated triangles from that patch get culled as a result, freeing up compute resources.
Figure 1.4.5. Conservative AABB for a displaced Bezier curve. The Bezier curve is shown in bold black, the control mesh in dotted lines, and displacements in solid gray lines. AABB for the Bezier curve without displacements is shown in dashed lines (inner bounding box), and conservative AABB for the displaced Bezier curve is shown in dashed and dotted lines (outer bounding box).
As you can see, the corners of inner and outer enclosures are more than d distance apart, so we are being more conservative than we need to be for the ease and speed of computation.
At this point, we have a conservative patch AABB that takes displacements into account. If the AABB for a patch is outside the view frustum, we know that the entire patch is outside the view frustum and can be safely culled. If we make the view frustum’s plane equations available as shader constants, then our shader can test the AABB using in-out tests for view frustum. Alternatively, one can transform the AABB into normalized device coordinates (NDC), and the in-out tests can be done in NDC space. In-out tests in NDC space are easier than world space tests because they involve comparing only with +1 or –1. If the AABB is outside the view frustum, we set the edge LODs for that patch to be negative, which indicates to the graphics hardware that the patch should be culled. We perform the culling test during the join phase (a.k.a. patch constant phase) of the hull shader because this operation only needs to be performed once per patch.
For each culled patch, we eliminate unnecessary tessellator and domain shader work for that patch. All patches, whether or not they’re culled, take on the additional computational burden of computing the conservative AABB and testing against the view frustum. When most of the character is visible on the screen (for example, Figure 1.4.9 (a)), culling overhead is at its worst. Figure 1.4.6 shows that, even in this case, culling overhead is minimal and is seen only at very low levels of tessellation. At LOD=3, the gains due to culling a very small number of patches (around the character’s feet) start offsetting the cycles spent on culling tests.
Figure 1.4.6. Culling overhead is the worst when nothing gets culled. Culling overhead is minimal except at very low levels of tessellation. “NO CULL” indicates the fps measured when no culling code was running. “CULL Overhead” shows the fps measured when culling code was running in the patch constant phase of shaders.
When about half of the patches in our test model are outside of the view frustum (see Figure 1.4.9 (b)), the overhead of the AABB computations is offset by the gains from culling the offscreen patches. The gains from culling patches are more noticeable at higher levels of tessellation. This is shown graphically in Figures 1.4.7 and 1.4.8. Figure 1.4.7 shows how fps changes with the edge tessellation factor (edge LOD) when about half of the patches are culled. As you can see, at moderate levels of tessellation, we strike the balance between benefits of the proposed algorithm at increased level of detail. Figure 1.4.8 shows the same data as percentage speed-up.
Figure 1.4.7. Culling benefits go up with the level of tessellation, except at the super-high levels of tessellation where culling patches doesn’t help. At moderate levels of tessellation, we get benefits of the proposed algorithm and still see high geometric details.
Figure 1.4.8. Culling benefits shown as percentage increase in fps against edge LODs (edge tessellation factor).
Figure 1.4.9. Screenshots showing our algorithm in action. We saw about 8.9 fps for the view on the left and 15.1 fps for the view on the right on the ATI Radeon 5870. Increase in the frame rate was due to view frustum culling patches.
We performed all our tests on the ATI Radeon 5870 card, with 1 GB GDDR. The benefits of this algorithm increase with domain shader complexity and tessellation level, whereas the per-patch overhead of the culling tests remains constant. It is easy to imagine an application strategy that first tests an object’s bounding box against the frustum to determine whether patch culling should be performed at all for a given object, thus avoiding the culling overhead for objects that are known to be mostly onscreen.
We have presented a method for culling Catmull-Clark patches against the view frustum using the DirectX 11 pipeline. Applications will benefit the most from this algorithm at moderate to high levels of tessellation. In the future, we would like to extend this technique to account for occluded and back-facing patches with displacements.