Hardware Determined Edge Features

Presented at NPAR 2004.

Morgan McGuire, Williams College
John F. Hughes, Brown University

Paper (PDF, revised 13-Mar-2004)
Paper (PDF, proceedings version)
Presentation (PPT)

This work was performed at Brown University


Algorithms that detect silhouettes, creases, and other edge based features often perform per-edge and per-face mesh computations using global adjacency information. These are unsuitable for hardware-pipeline implementation, where programmability is at the vertex and pixel level and only local information is available. Card and Mitchell and Gooch have suggested that adjacency information could be packed into a vertex data structure; we describe the details of converting global/per-edge computations into local/per-vertex computations on a related .edge mesh.. Using this trick, we describe a feature-edge detection algorithm that runs entirely in hardware, and show how to use it to create thick screen-space contours with end-caps that join adjacent thick line segments. The end-cap technique favors speed over quality and produces artifacts for some meshes.

We present two parameterizations for mapping stroke textures onto these thick lines.a tessellation-independent screen space method that is better suited to still images, and an object space method better suited to animation. As additional applications, we show how to create fins for fur rendering and how to extrude contours in world-space to create the sides of a shadow volume directly on the GPU.

The edge mesh is about nine times larger than the original mesh when stored at 16-bit precision and is constructed through a linear time pre-processing step. As long as topology remains fixed, the edge mesh can be animated as if it were a vertex mesh.



NVIDIA has now shipped NV40 and NV47 hardware ("GeForce 6 and 7"). These cards have the ability to perform a texture lookup in the vertex stage. As mentioned at the end of the paper, this allows the edge mesh to store vertex and normal indices instead of 3D vectors, leading to a 6x reduction in the size of our data structure. The (at the time of this writing, 2006) soon-to-be-released DirectX 10 graphics cards take this one step further with a programmable geometry processor.

Marc ten Bosch has an extension to our technique called Partial Silhouette Detection that helps maintain coherence under animation with very attractive results.

Joern Loviscach's Stylized Haloed Outlines on the GPU adds more line styles for sketchy strokes and halos for conveying occlusion.

In the paper, we mention that artists have long used Raskar's 1999 Image Precision Silhouette Edges method, which they apparently discovered independently. Ramesh tells us that he is often asked about this, and suggested we provide an example so it can be cited in the future. Here are three: Conor O'Kane's "Honey" model (2000, http://www.planetquake.com/polycount/info/quake3/honey/honey.shtml) uses a 1D texture for 2-tone shading (ala Gooch) and an inverted, black, enlarged version of the mesh to provide cartoon outlines. Seth Galbraith wrote the Cartoon Outline Generator tool (2001, http://www.planetquake.com/gg/tutorial/toon/) to automate the process of producing the second mesh. The Anim8or site offers the following artist submitted tutorial (date unknown): http://www.anim8or.com/tutorials/from_users/toon_notes/toon_rendering_hints.jpg. Note that Quake 3's realistic rendering engine itself is not modified by these techniques and these models work with any Quake 3 renderer; the changes are purely to the geometry of a model and are performed in a modelling tool.

Ramesh Raskar has also pointed out to us that his 1999 method can handle thick silhouettes, and that the 2001 paper shows examples of textured strokes. Figure 12 in his 2001 paper shows a thickened stroke exhibiting stroke-cracks; this is where the thick-stroke-cracks problem is first described, as we mentioned in the text.


There are three errors in the proceedings version of the paper because we submitted the wrong draft:

  • Footnote 10 should not be present
  • The labels for Figure 7 are overprinted on the following page
  • The final paragraph of Appendix B is truncated
These are corrected in the PDF on this page. There is an additional error in both PDFs that is not corrected: on page 7, the sentence "A mostly vertical edge is one where" should then read "|s1y - s0y| > |s1x - s0x|", i.e., the first "0x" subscript should have been a "0y" (thanks to Dwight House for pointing this out!)


 author = {Morgan McGuire and John F. Hughes},
 title = {Hardware-determined feature edges},
 booktitle = {Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering},
 year = {2004},
 isbn = {1-58113-887-3},
 pages = {35--47},
 location = {Annecy, France},
 doi = {http://doi.acm.org/10.1145/987657.987663},
 url = {http://graphics.cs.williams.edu/papers/EdgesNPAR04/index.html},
 publisher = {ACM Press},