CS 798 Assignment 3
Lesley Northam

1 System Requirements

The following libraries and tools were used in the implementation of this assignment (and are thus required for running the binary file):
  • GTKmm 2.0 - GTK 2.0 C++ Wrappers
  • GtkGLextmm 1.0 - OpenGL Drawing Area Widget for GTK (C++ Wrapper)
  • image.hpp - PNG Image Input/Output library from CS488
  • algebra.hpp - Points, Vectors and Matrices library from CS488
  • trimesh2 - Library for reading, storing, rendering, etc. meshes from Princeton
  • OpenGL 1.3
  • C++

2 User Interface

The user interface for this program (called contour), is a window and can be opened from the shell or from Konqueror (or file browser of users choice). No arguments are required or expected to the binary file, all parameters can be specified by the user during runtime. The interface:

Open Mesh: Allow the user to open a mesh. Only trimesh2 supported files are supported. OBJ files are suggested.

Open Texture: Allow the user to open a texture file. File is assumed to be PNG format and 64x64 pixels in size.

Save Image: Allow the user to save the rendering area as an image. File format is assumed to be PNG.

Reset: Reset the models position and orientation.

Basic Options: Options for viewing the model, only BG functions with Contours and Shading.

Show Edges: Display mesh edges (in blue). Initially off.

Toggle Lighting: Turn lighting on or off. Initially lighting is on.

Toggle Shiny: Turn specular highlights on or off. Initially shiny is on.

Toggle BG: Switch between white and black background. Initially BG is black.

Toggle Surface: Draw the mesh surface. Initially on.

Crease Options: Options for rendering creases. Scroll box controls crease angle. Any two faces whose angle is greater than or equal to the angle in the box will have a crease edge between them.

Toggle Creases: Turn crease rendering on or off. Initially off.

Toggle Holes: Turn hole edge (edges with only one bordering face) rendering on or off. Initially off.

Toggle Contours: Turn contour rendering on or off. Initially off.

Toggle ID Image: Display ID image used in edge visibility detection. Initially off.

Polygon Edge Offset: Set polygon offset, used to push mesh backwards for contour detection.

Edge Visibility Error %: When scan converting edges, maximum percent of "bad" pixels permitted.

Toggle Bresenham: Turn Breseham scan conversion algorithm on or off. If off, a secondary exploration algorithm is used. Initially on.

Select Line Width: Set the width of the line.

Toggle Lines: Switch between rendering contours/creases/holes with triangle-strips and GL_LINES. Initially renders with triangle strips.

Toggle Shading: Turn cartoon shading on or off. Initiall off.

The user interface does not perform any error checking, and may behave erratically if the guidelines laid out above are not followed strictly. Specifically, note that all images (saved or loaded) must be PNG format. Texture files MUST be 64x64 pixels in size. Meshes must be trimesh2 compatible.

The OpenGL rendering area is interactive. Moving the mouse with the left button pressed results in rotations. Moving the mouse with the middle button pressed results in translations. Moving the mouse with the right button pressed results in scaling. This functionality was ported from "mesh_view.cpp" in trimesh2 to work in a GTK interface.

The window should not be resized.

3 Hole Edges

A hole edge is any edge such that it belongs to only one triangular face. Hole edges are pre-computed when the mesh is initially opened. To find a hole edge, each triangular face is tested and if any edge is missing a neighbour, it is added to a list of hole edges. Finding hole edges can illustrate the connectivity of a mesh.

4 Crease Edges

A crease edge is any edge such that the angle between the two neighbouring faces is greater than some specified threshold angle. Crease edges are computed in advance, whenever the threshold angle is changed. The trimesh2 library does not store face normals, so they are computed when the mesh is loaded and stored within the program. The face normal is computed as the average of the vertex normals.

5 Contour Edges

A contour edge is any edge such that L dot N = 0 (where L is the light vector and N the normal). Contour edge detection is implemented as in Hertzmann's "Introduction to 3D Non-Photorealistic Rendering: Silhouettes and Outlines". First the vertex signs are computed, then for any triangle where the vertex signs are not identical edge points are interpolated down the edges of opposing vertex signs.

6 Visibility

Each edge is drawn on a black screen in an ID colour. The ID colours are unique, and are chosen by cycling through green and blue values. Then, the mesh is drawn overtop (using the specified polygon offset) in black.

The starting point of each edge is converted to screen coordinates (Pscreen = Proj * Model * P). A 3x3 area around each starting point is read from the frame buffer and examined. If the ID colour of the starting point is found, its location is recorded and scan conversion will take place. If the ID colour is not found, then the edge is considered not visible and is thus discarded.

On the left, the ID image. On the right, basic contours.

Scan conversion is done in one of two ways, method one being Bresenhams algorithm and method two being a variation on Bresenhams algorithm. First, a new block of pixels is read from the frame buffer (Note: we only read what we need from the frame buffer), the block represents a box confining the edge.

Bresenham's Algorithm

Bresenhams algorithm is followed (as per wikipedia). The starting point is not guarenteed to be a valid "hit" point, so for each computed point the 8 surrounding pixels are tested and the matching one is selected (provided it is not the previous point). To control the amount of "bad" pixels we allow (given that we may not be starting from a "hit" point, and our slope might be slightly off due to screen conversion), we compare the number of "misses" to the number of "hits" we expect, if the percent is less than the max allowed error the line is drawn. Otherwise it is not.

Alternate Algorithm

Starting with the confirmed hit point, the neighbouring pixels in the direction the line travels (start->end) are observed and the current pixel is set to this new point. For example, if the line moves from left to right, the current "hit" is the center of the 3x3 grid. The pixels to test for the "new" pixel are illustrated in the image below and correspond to the red arrows.

The algorithm continues until either: cannot find anymore points or the amount of allowable misses (percent error) has been exceeded. A new point is generated with the last valid point, and the edge is drawn from the first hit to the last hit. This means, that only the visible portion of the edge is drawn.

Edge Collisions

It can be difficult to determine if two edges cross in screen space using Bresenhams algorithm. If one edge has a point that lies directly on top of a point on another edge, it is easy to say that the "colour on top" is the edge on top. However, edge points may not coincide even if the lines do cross. For example, observe the following image:

Note that the red and blue lines overlap, however they do not share any points. Thus, it is difficult to detect that the two edges cross! And, since they share no points, it is not possible to tell which edge is on top. Issues like these could be resolved by using a ray-tracing method. Drawing a ray between our surface point and camera, if anything is intersected along that line, the point is not drawn, otherwise it is. This computation however, can be very expensive -- especially for meshes as there can be thousands or even millions of triangular faces.

7 Edge Rendering

Edges can be rendered in one of two ways. First (the default mode), rendering is done using a triangle strip capped at each end with a circle. Second, rendering is done using GL_LINES.

Width of a line for triangular strip rendering is done as shown in the diagram below. Where, N is the normal, A is the start point, B is the end point, a-d are the computed triangle vertices and w is the line width.

Capping circles are drawn at points A and B, with radius w/2.

On the left, the drawn with capped triangle strips and on the right, drawn with GL_LINES.

8 Shading

For an extension, I chose to implement the 2D cel-shading approach taken from "X-Toon: An Extended Toon Shader" (Barla et al). Texture coordinates are computed by: x-value is the cosine of the angle between light vector and normal, and y-value is the distance from the camera. Note that maximum distance is 200 units from camera (distance is capped if it exceeds this value, ideally this max distance would be a parameter). These coordinates are computed per-frame. The mesh is then rendered.

On the left, model close to camera. On the right, model further from camera.

9 Performance

Machine Specifications

The machine used is "SilverRaven2" and it has the following specs:
  • AMD Athlon XP 2800+ (circa February 2003)
  • 512mb OCZ Dual Channel DDR400 RAM (circa April 2003)
  • Western Digital 80gb IDE HD with 8mb cache (circa April 2003)
  • ATI Radeon All-in-Wonder 8500DV (AGP4x, 64mb, circa September 2001)
  • KUbuntu Fiesty Fawn
  • Kernel = 2.6.20-16-generic
  • glxinfo output glxinfo.txt
A comparison of my video card against the best one in the undergraduate graphics lab is given here: Card Comparison . Note that the memory bandwidth of my card is over five times slower than that of the lab machine's card.

Frames Per Second

Frames per second are estimated by determining the number of frames randered between mouse button down and mouse button up (corresponds to motion or re-draws) divided by the amount of time elapsed between button down and up states (computed by using the time function).

For the cow model (5804 triangles) without contours, an estimated average of 50fps is observed. For the Zero model (12303 trianges) without contours, an estimated average of 35fps is observed.

For the cow model with contours, an average of 4-5fps is observed. For the Zero model, an average of 1.67-2.25fps is observed (this model has contours and holes, and a significantly larger number of edges due to the model complexity).

When it comes to reading pixels from the frame buffer, I noted that reading the whole buffer (512x512x2(G,B)) takes longer than one second. (In fact, it takes about 2-3 seconds (occasionally more) on my machine). Thus, I chose not to read the entire buffer. I chose to do multiple, small reads -- but ONLY exactly what we need. For each edge, a minimum of 16 pixels are read. If any edge is not found in that block, then no further pixels are read for that edge. A larger block encompassing the entire edge is only read if that edge was found in the test block. I observed that this method of reading from the buffer is faster than reading the entire buffer for each frame.


  • All glReads are done on NxN blocks where N is a power of two (even if non-power of two reads are desired, reading non-power of two values does not work for my system). For any machine capabe of reading non-power of two blocks, the code could be easily modified to improve performance.

10 Result Images

In no particular order, here are some images that were rendered using the contour program.
And as a point of interest, you can "fake" contours to some degree using textures and cel-shading. Below are three examples of faking contours with such a texture.


  • "Introduction to 3D Non-Photorealistic Rendering: Silhouettes and Outlines", Aaron Hertzmann
  • "WYSIWYG NPR: Drawing Strokes Directly on 3D Models", Kalnins, Markosian, Meier, Kowalski, Lee, Davidson, Webb, Hughes, Finkelstein
  • "Artistic Silhouettes: A Hybrid Approach", Northrup, Markosian
  • "Real-Time Nonphotorealistic Rendering", Markosian, Kowalski, Trychin, Dourdev, Goldstein, Hughes
  • "X-Toon: An extended toon shader", Barla, Thollot, Markosian
  • Turbo Squid,, Free 3D Models