1In three dimensions, we would like the same control over abstraction as in two dimensions, but there are several additional requirements. We'll focus on animated and interactive applications, since if we only care about still images, we can just use the techniques Doug described. For animation, we need temporal, or frame-to-frame coherence between consecutive frames. For interactive applications, we need both temporal coherence and good performance. A desirable, though not strictly necessary, quality is flexibility in the types of lines that the method can handle. 23Line density is one of the most important cues for abstraction in line drawings. In the image shown, the central building is obviously emphasized while the surrounding buildings are not, and the only variation between the two is the line density. However, the basic pipeline described previously hasno natural control over screen space line density - lines are drawn wherever the extraction and visibility algorithm determine they should be.The simplest way to deal with inordinate line density is to nip it in the bud by creating an abstraction of the model itself, such as by smoothing. The lines are then extracted from this smooth model, and rendered as normal. 45So, how do you make an abstraction of a model? One way is to create a specialized method tailored to a specific type of model, such as bushy trees. In this example, we represent each leaf with a disk, and vary the radius of these disks to control the level of abstraction. This method has the nice effect of not only controlling density, but also varying the shape of the lines themselves.6More generally, we can create a set of simplified meshes using some low-pass filtering method. We then interpolate between these meshes at runtime, giving precidence to the smooth mesh in areas where low density are desired, and the detail mesh for areas of high density. The major issue is that this method is restricted to smooth models that can be effectively filtered without losing their character.If you have shapes that cannot be filtered easily, such as these buildings, or worse, have a set of lines built in to the model itself (such as the lines on the building in the foreground), then its difficult to use a model based strategy. 7A stroke based strategy can be more general because it doesn't depend on changing the model. The density control happens in image space, after the lines are extracted and turned into 2D strokes. The source of the lines is not important, be it extracted silhouettes and suggestive contours or manually added decorative line, because they all get turned into 2D strokes. 89The simplest way to control line density in image space is to keep track of the density as each new stroke is drawn. The density function is usually defined as a smoothed version of the drawing in progress. When the density reaches a user-specificied threshold, the remaining strokes in that area are dropped. The strokes must be ordered somehow by importance, as a random ordering will cause undesired results such as in the middle image. Ordering the strokes by an importance metric can improve the results by making sure the more important strokes (here, the strokes that lie along large depth discontinuties) get drawn first.There are a number of tricks that can be performed in the image domain. One is to simulate indication by drawing strokes more densly around the edges of the object. This effect can be achieved by first drawing the entire scene and blurring it to get a smooth version. The smooth version is then run through an edge detector, which produces an image with smooth dark areas around the edges of the shape. This image can then be used as a target density image to locally control the stroke density across the image. Unfortunately, dropping strokes at an arbitrary threshold generally leads to terrible temporal coherence. Superior results can be achieved by smoothly merging strokes instead of dropping them.10Techniques to merge dense strokes are generally called stroke simplification techniques. The general idea is to identify a set of similar, nearby strokes, merge them into a cluster, and then replace the cluster with a single representative stroke. The subtly arises from the problem of choosing a representative stroke. Sometimes long, curly strokes (such as the stroke near the lion's shoulder) need to be broken into a series of strokes.11A naive algorithm for clustering strokes is at least O(n^2), since every stroke needs to be compared to every other stroke to find the closest matches. Shesh 2008 proposes to use an advanced datastructure called a 1+epsilon deformable spanner, which is essentially a graph structure that allows finding all pairs of nearest points in roughly linear time for reasonable graphs. Shesh demonstrates the system at interactive framerates with good temporal coherence. However, the implementation of the system is somewhat complex due to the use of the spanner structure.1213The final line density control scheme that I will mention is the priority buffer, which is inspired by the item buffer Adam mentioned before. The priority buffer test has several important benefits. It has temporal coherence suitable for animation. It is stroke based so it handles all types of lines, with the caveat that the priority ordering must be well defined. It is also fast and relatively easy to implement, especially if you are already using an item buffer to compute line visibility.14The priority buffer is a second offscreen buffer, where lines are ordered by a priority value rather than depth. We locally vary the width of the lines so that the lines are thin where line density should be high, and wide where line density should be low. The effect is that in areas of low density, wide, high priority lines cover low priority lines and obscure them. We vary the final weight of each line according to its visibility in the priority buffer. So for example, the lines on the left here are thin, corresponding to high density in the final rendering, and the lines on the right are wide, corresponding to low density.15The item buffer and priority buffers are similar, but they are necessarily separate. Of course, the ordering of the lines is by depth in the item buffer and by priority in the priority buffer. Somewhat more subtly, however, lines in the item buffer should be as thin as possible while avoiding rasterization errors. If lines are drawn wide in the item buffer, the visibility