McGill University
Computer Science Dept.

TechnicalQuake

A Project for COMP-767 - Non-Photorealistic Rendering

Michael Batchelder and Kacper Wysocki
Winter 2005

Rebuilding edge information

Things such as drawing silhouettes and creases, and fancy shading algorithms are difficult to do on a polygon unless you know the neighbouring polygons that share edges with the current polygon. Unfortunately, Quake stores all its model frames as "polygon soups", that is, series of independent triangle strips and triangle fans which again consist of independent vertices. So the very first thing we set about doing was somehow rebuilding some of the direly needed neighbouring edge information.

Our approach consists of creating a three-level hash: We keep a table of models previously seen. For each model, we maintain a table of animation frames encountered. For each frame, we store a 3D-hash of edges, each of which contains normals for polygons that share that edge. This is illustrated below.

Three level 3D hash diagram
The first time a frame is drawn, when an edge is encountered, it is looked up in the hash. If the vertex pair has been seen before, we add the current surface normal to the existing edge. Otherwise, we add the edge, and the surface normal of the current surface, to the hash table, and proceed to the next triangle.

Coming up with and implementing this structure in Quake was not completely trivial, and so we had anticipated that this sort of preprocessing would make the rendering unbarably slow. However, we were pleasantly surprised once the table creation was implemented, because this preprocessing took hardly no time at all. Although the process had a measurable impact on framerates, the difference is still not noticable to the human eye, as this table shows in frames per second.

Time Demo Demo1Demo2Demo3
Default 222219217
Sketch 146148135
A.I. Toon 979788
TechnicalQuake 868778
TechnicalQuake - No Edges 10410495
The results were obtained in 800x600 window mode NPRQuake, on a Pentium 4 2.66GHz with 512MB RAM and a GeForce4 Ti 420, running gentoo GNU/Linux.

Gooch Shading

Once we had the edge table, we felt ready to proceed to the rendering part. We implemented Gooch shading on the models, which linearly interpolates between a cool (receding) and warm (advancing) color based on the light direction and the surface normals, according to the equation:

I=((1+l.n)/2)*kcool + (1-(1+l.n)/2)*kwarm
This reserves high and low luminance ranges for silhouettes and creases, thereby increasing shape comprehension.

cool-to-warm
This image illustrates the cool-to-warm tonal transition that keeps luminance constant.

transition
Here we can clearly see that depth and shape cues are conveyed nicely from the shading.

cool-to-warmer
The shape cues are retained in different lighting conditions.

Splashback

Splashback is an adaptation of the cool-to-warm Gooch shading that simulates the more dramatic effects sometimes used by artists. The effect is acheived when the reflected light from the left of the object produces a back-splash of light opposite the direct lighting source. We acheive this effect simply by adding the following multiplier to the Gooch shading color equation:

(alpha*abs(cos(theta))+(1-alpha))^p

splasH! Back!
whip lash back splash
We see that the model shading appears more dramatic than in the earlier examples.

Silhouettes and creases - nice try

Silhouettes and creases are where we had the most problems. We had hoped that the Quake "polygon soup" would match up at the vertices, at least most of the time. We were disappointed by discovering that not only did the models consist of polygons that did not match up at edge boundries, and therefore had unexpected discontinuities that were invisible under normal rendering, but that the models sometimes had double-faced polygons, edges that were part of more than two polygons, and degenerate triangles.

Nevertheless, we implemented a silhouette and crease finder algorithm based on our preprocessing information, and the algorithm described in the Gooch et al Interactive Technical Illustration paper. The results are not amazing, because the neighbouring information is inaccurate due to the above mentioned issues, and also because quake does not correctly give us the eye position, rendering the same edges as silhouettes regardless of viewing direction.

crap silhouettes and edges
Silhouettes(black) and creases(white) are drawn in random places because eye position remains constant across large chunks of the map.

silsncreasesrbad
How a good idea can go wrong.

shading+silsandcreases
A combination of the broken silhouette/crease drawing and the shading.

quake models suck
The red lines are lines that only have one normal associated with them, which means that they are not really connected to the rest of the model.
The elbow's connected to the, oh wait...

Mike heart backpacks


Project References:

[1] Bruce Gooch, Peter-Pike J. Sloan, Amy Gooch, Peter Shirley and Richard Riesenfeld. Interactive Technical Illustration. Symp on Interactive 3D Graphics, 1999

[2] Ramesh Raskar. Hardware Support for Non-photorealistic Rendering. In Graphics Hardware, 2001

[3] Amy Gooch and Bruce Gooch and Peter Shirley and Elaine Cohen. A Non-photorealistic Lighting Model for Automatic Technical Illustration. ACM Siggraph '98 Conference Proceedings, 1998

[4] Alex Mohr, Erik Bakke, Andrew Gardner, Christopher Hennman, and Steve Dutcher. NPRQuake. At http://www.cs.wisc.edu/graphics/Gallery/NPRQuake/whoWeAre.html

[5] ID Software. Quake 1 Source Code. At http://www.idsoftware.com/business/techdownloads/

[6] Adrian Ilie. COMP 238 Final Project: Non-Photorealistic Rendering Techniques for a Game Engine. At http://www.cs.unc.edu/~adyilie/comp238/Final/Final.htm

[7] Adam Lake, Carl Marshall, Mark Harris, and Marc Blackstein. Stylized rendering techniques for scalable real-time 3d animation. Proceedings of NPAR 2000, 13--20


COMP-767 - Advanced Topics in Graphics: Non-Photorealistic Rendering