788 Spring '01 Final Project

Jon Woodring

Real Time Non-Photorealistic Rendering Techniques, sketch and cartoon shading

Much of our graphics rendering has been dedicated to producing images that try to meet the criteria that they look as much as real life as possible within performance constraints. Non-photorealistic rendering is more concerned about producing images that fit a stylistic constraint, not necessarily to exactly model real-life imagery. Stylistic examples usually fit into artistic categories, such as pen and ink sketches, charcoal, watercolor, etc.; though there may be other stylistic requirements, outside of the art domain.

Traditionally, non-photorealistic techniques have been applied in the image space domain, in the way of convolution filters. Look to Photoshop or the GIMP for many examples of these. These filters are usually written in software without any hardware acceleration, and depending on the size of the convolution kernel footprint, can subsample the image plane many times, making NPR techniques a slow proposition.

Can we utilize common consumer hardware graphics acceleration to achieve some of out non-photorealistic techniques? The answer is yes, and in the following paragraphs, it will be presented several techniques used in a real time pen and ink sketcher and cartoon shader. The material that was derived from the papers is not the only non-photorealistic techniques presented, and where appropriate, differences in the implemented system and the papers will be mentioned.

To do pen and ink/pencil sketches, we turn the shading of the model into a selection of a "tonal art map". A tonal art map is a series of hatched images that depict how an artist would shade an area. If an area is dark, a dark hatched image is selected, if it is light, a light hatched image is selected. The tonal art maps will ultimately become texture maps that the hardware uses to shade our triangles.

For continuity across textures, so that we don't see seams at wrapping and across tone boundries, a lighter tonal art map is a subset of stokes in a darker tonal art map, additionally a tonal art map is torodial. So, a stroke going from light to dark texture will be seen as continuous, but not in the reverse direction, from dark to light. To achieve this property, we blend textures across faces, by choosing a tonal art map at each vertex. Still, there will be tone discontinuity from face to face, because tone decision is a binary decision. To solve this final problem, we linearly interpolate the texture at each vertex, by blending between the ceiling and floor tonal art maps at each vertex.

In the paper, it is mentioned using multitexturing or a multipass algorithm. This implementation does a 7 pass algorithm in the following steps:

Turn on smooth shading, set depth test to less than or equal to, no hardware lighting
Turn off blending, turn on writing to the z-buffer
Render the mesh in black
Turn on blending, turn off writing to the z-buffer
For each face, for each vertex:

Calculate the light at the current considered vertex
Determine texture coordinates for each vertex, based on projection
Find the ceiling and floor tonal art map
Linearly interpolate the ceiling contribution and select that texture
Render the triangle, smooth shading across the face (no contribution of texture at other 2 vertices)
Linearly interpolate the floor contribution and select that texture
Render the triangle, smooth shading across the face (no contribution of texture at other 2 vertices)

The paper also uses curvature aligned textures and mipmaps, where in a mipmap the strokes are a subset of a closer texture. This implementation uses a planar projection texture coordinates, dynamically scaled based on distance squared from the image plane. In both cases, it makes it so that the strokes are always the same size and distance apart. While the former indicates stroke with curvature aligned textures, just for simplicity, this implementation does no such thing, but the strokes do appear always in the same place on the image plane.

The second type of shading used is cartoon shading. In cartoon shading, there is a discontiuity of tone from light to dark in the same material. To implement this, we set up a two pixel texture map for each material, where one pixel defines light material and the other pixel defines the dark material. At each vertex, we do the lighting calculation, which is the texture coordinates in our 1D 2 pixel texture map. The hardware then linearly interpolates texture coordinates, and if crossing the zone from light to dark, will automatically render the tone discontiuity as texture coordinates pass the .5 barrier.

Here is presented the algorithm used in cartoon shading implmentation:

Turn on flat shading, z-depth test, no hardware lighting
For each face

Select the 2 pixel texture based material (in the implementation there was only 1 material, grey)
Do lighting calculation at each vertex and set texture coordinates
Render a face

Finally, in both shading techniques, silhouette edges are rendered. Silhouette edges help define boundry and detail that can sometimes get obscured or lost in these two shading techniques. Additionally, is very common in these stylistic techniques for boundries and details to be drawn. A silhouette edge is defined to be an edge between a front facing polygon and a backfacing polygon. So, to draw silhouette edges, we just have to identify edges as such, and render them as needed.

This implementation finds silhouette edges in a brute force manner. It just does a linear walk through all possible edges collected in a preprocessing step. A smarter algorithm could be applied to find silhouette edges, or cull away edges not in the viewing frustrum. Currently no culling is done. Additionally, the paper mentions scaling line width depending on depth from the image plane, while for simplicity, this implementation has uniform line width.

In a preprocessing step, build a list of possible silhouette edges, plus collect all the boundry edges
After rendering the mesh, set z-depth to less than or equal
Set color to black, and line width
For each possible silhouette edge, determine if it is a silhouette edge, if so render it
For all boundry edges, render it

The implementation was created in C++ with OpenGL, developed with a 760MHz Celeron, 256MB, Win98, and GeForce accelerator. No timing information was taken, but fps are estimated to be over 15Hz (possibly over 30Hz) for a 3100 triangle mesh, with full range of motion in the model and the light, in pen and ink sketching. Cartoon shading refresh rate was far beyond that.

Future research consideration I am currently looking into is seeing if it is possible to extend strokes beyond the boundry of the mesh, and see if there are any such NPR techniques that can be hardware accelerated in this manner.

References:

Lake, Marshall, Harris, Blackstein. Stylized Rendering Techniques For Scalable Real-Time 3D Animation. NPAR 2000.

Praun, Hoppe, Webb, Finkelstein. Real-Time Hatching. To appear in SIG2001.

Goblet, sketch shading