Semester Project, Spring 2004, Graphics 2:
Robert Bader
email: rbader AT stevens DOT edu
Non-Photorealistic Rendering
Final Project Page

Description,Background/Motivation, Sources:
All in my proposal, which is here


Algorithms:
There were several algorithms that I learned about and implemented:
Cool to Warm shading:
This is a very simple algorithm described in the Gooch paper which is based off of normal lighting calculations. The difference is that instead of using a transition from black to the material color as the normal goes from facing away from the light source to facing towards the light source, it goes from a "cool" to a "warm" color, that allows for the viewer to easily identify changes in shape. This is accomplished using the same method as Gouraud shading. The dot product of the vector from the light source to the vertex and the vertex normal is used to determine the color by interpolating between the cool and warm colors.

Cell or Cartoon Shading:
This algorithm is designed to give a 3-D object a 2-D look. This is accomplished by having only a few different levels of color available for shading. These colors are put into a 1-D texture map, and using the dot product of the light vector and the normal vector, a texture coordinate is determined for each vertex. The texture map must be used, because if the color was interpolated between two vertices it wouldnt achieve the "hard line" that is associated with cartoon shading.

Pencil Shading:
This algorithm makes a 3-D object appear to be a pencil shading (sortof). This is accomplished in many steps. The first step is to create a texture map for each "level" of shading. A level of shading is the density of pencil marks, ranging from high density (dark shade) to low density (light shade). I did this by dividing the texture space up according to the number of lines I wanted, and then drawing a line across each section, with some up and down randomness. in this picture, the black lines represent the division of the texture into sections, and the blue lines are the lines that get drawn(with as much randomness as i could provide in paint):

One of these is created for each level needed to be drawn. Then the faces of the model must be sorted into bins for each level. If a polygon's vertices dont all lie in the same level, then the polygon must be subdivided into smaller polygons. This is done by walking along the vertices, and when two vertices are not in the same level, interpolation is used to find an intermediate vertex. Visually, sortof like this:

Once all the bins are filled with their appropriate polygons, then to generate texture coordinates, each vertex is multiplied by the projection matrix generated by openGL, which gives screen coordinates. Using the screen coordinates as the texture coordinates, each polygon is drawn. The problem that occurs with this method (as described in the paper Stylized Rendering...) is the "shower door" effect, wherein models appear to be moving through the texture. I found the solution to this is to generate several textures per level (empirical evidence suggests 5 is appropriate), and each frame, randomly pick from the textures that were not used in the previous frame, using a new texture for each level. The only problem with this method, is that it requires a great deal more memory to store all these textures, but I think the results are much better for any sort of animated movement.

Silhouette Detection:
Silhouette detection is achieved by checking for 3 types of edges that should be part of the silhouette. The first type of edge is an edge that is on a border, and is only connected to one face. the second type of edge is an edge that is between two faces where the dot product of their normals is beyond some threshold. The third type of edge is one which has one face that faces towards the viewer, and one that faces away from the viewer:

The first two types of edges are determined in pre-processing, however the third type of edge is view dependant, and so it must be determined for every frame. This is done by finding the dot products between the view vector (to one of the edges vertices) and each of the face normals. The dot products are multiplied together, and if the result is less than or equal to zero, the edge is the third type of sillhouette edge.

Implementation:
The program is basically a model viewer. The user can move around the model, and change its colors, and what shading algorithm it uses.
The current build is here (i usually update this if i make any changes to the executable...but I make no guarantees about the documentation)
note: when it starts up, there is a lot of loading/calculating that must be done, so please be patient

Controls:
a rotate around the center of the model to the left
d rotate around the center of the model to the right
s move away from the object
w move towards the object
q move "up"
r move "down"
x toggle faces on/off
z toggle shower door effect on/off
c stylized shading(experimental, currently does not work right at all)
spacebar exit

the sub window allows the user to control the various shading types and colors:
The "High" Color is the color that is used for when the vertex is in the completely in the light, and the "Low" Color is the color use when the vertex is completely in the dark.
A new file can be loaded by clicking on the filename, and typing in a new one. Then click "Open". Ive been told that there is a bug that causes the loading to work wrong if a file it was looking for was not found. This can be rectified by restarting the program.
Moving the shading slider to the left starts pencil shading.
Moving the slider to the right starts cell shading, and the number represents the number of levels used from the texture. The texture seen along the bottom is the texture that is being used. When in cell shading mode, clicking on the different parts of the texture lets the user change the color in the texture. It uses the first n+1 texels of the texture, starting at the left. I find it looks best using levels 2-4, if the values are raised.
Changing the crease bar changes the threshold at which an edge will be considered a crease.

Results:
all of these results were obtained on my computer, athlon xp 2700+, 1 gb ram, radeon 9700, using the bunny model
Silhouette Detection:
This ran at an average of about 112 frames per second, when faces were not being drawn.



Cool to Warm Shading:
This ran at an average of about 88 frames per second.



Cartoon Shading:
This ran at an average of about 80 frames per second.





Pencil Shading:
This ran at an average of about 24 frames per second.




Executable:
The current build is here
Source Code:
The code is here
The main file needed is npr.cpp