[In this Intel-sponsored feature, part of the Gamasutra Visual Computing microsite, Intel senior graphics software engineer Joshua Doss delves practically into techniques for edge detection, crucial for many approaches to non-photorealistic rendering.]

Edge detection techniques are fundamental to non-photorealistic rendering algorithms. Two of the fundamental algorithms used in non-photorealistic rendering algorithms are silhouette edge detection and crease edge detection. The silhouette edge is the part of a model where the front facing triangle borders a back facing triangle. A crease edge is found where the angle between two front facing triangles is beyond a certain application-defined threshold.

In the past decade, many different techniques have been used to detect and draw these edges. Each method has its strengths, as well as room for improvement, but none of them provides an accurate representation of edges detected and created entirely on the GPU.

This article discusses a GPU-based implementation of edge detection and inking using the geometry shader model available in DirectX 10 capable hardware and provides a walk-through of the geometry shader implementation and the additional capabilities it provides.

This model of a spring has a simple Gooch shading applied, along with the edge detection techniques in this paper.

Existing Work

Edge-based inking (see Marshall in References) uses a preprocessing step to build a unique edge list for the model being evaluated on the CPU. Each triangle is decomposed into edges, which are then stored in a hash table. The table can be compacted by discarding all edges that are not unique.

Each edge contains information about the vertices on the edge, as well as a flag entry. This flag entry identifies the edge as being a silhouette, crease, or other type of edge and is initially set to an arbitrary value and updated at runtime. The face normals must also be computed for each triangle and stored in the edge list in this preprocessing step.

The runtime portion of this technique begins with updating the face normals (if using an animated model). Computation of the view vector takes place in this step, and the edges are tested using the view vector (V) and the face normal (N1 and N2). This process will determine if they are silhouette edges by testing to see if the sign of the cosine of the angles between the face normals and view vector differ:

[N1XV] X [N2XV) lesser than or equal to 0.

A silhouette edge is an edge shared by a front and back facing polygon.

After the silhouette edges are found with this technique, the edge flags are updated to label the edge as a silhouette edge. The next step is to detect crease edges by testing to see if the cosine of the angle between two adjacent triangles joined by the edge being tested is above a certain threshold. If an edge is detected as a crease edge, the edge flag is set to indicate this, testing with the equation:

|N1XN2| lesser than or equal to cos?

To determine whether to draw or ink an edge, iterate over the edge list and render only the edges with the silhouette and/or crease edge flag set to true. The render state should be set up so that the line thickness is of a higher value than the default; so the edge is visible and of a visually appealing width.

This method requires a graphics API that allows line thickness to be set explicitly for visually appealing results. Unfortunately, it creates a challenge for game developers since Direct3D does not allow for the line thickness to be explicitly set by the application.

To get around this, a different technique was offered for Direct3D: programmable vertex shader inking. Shader inking is possible with both the Direct3D and OpenGL APIs and is dependent only on having a programmable vertex shader. The dot product of the vertex normal and the view vector are used to index into a one-dimensional texture, which then gives a varying thickness line around the model's silhouette edge.

This technique is fast, as it runs entirely on the graphics card (see Marshall in References), and it offers some stylization of the lines as the polygons on the edge show varying thickness along the silhouettes, depending on the polygon's angle with respect to the view vector.

Unfortunately, using shader inking has at least three drawbacks. For one, it uses only the vertex normal. Second, it can miss certain silhouette edges. And third, the varying edge thickness is very difficult to control.