Introduction

For this project, I implemented a small OpenGL program in Windows that does the following basic tasks:

1. Reads in a surface described by a set of Bezier patches.
2. Generates a set of polygons describing that surface (using uniform subdivision), displayable in points-only mode, wire-frame, or fully shaded.
3. Sets the vertex colors to show the max, min, Gauss, or mean curvature  using a color scheme described below.
4.  Can generate line textures to show the normal, tangent direction, or principle curvature directions at each point on the surface.

In addition, it can also do the following more interesting things, all of which are explained in detail in later sections:

1. Draw a flat two dimensional outline around  the surface using geometric methods.
2. Draw a flat two dimensional outline around  the surface using OpenGL stencil buffer techniques.
3. Perform real-time non-photorealistic rendering of the surface as a 'sketch' using geometric and probabilistic techniques.

This document will present my results in three sections.  First I will demonstrate basic functionality as specified in the assignment file.  Next, I will show and explain the extra features implemented in my program, along with what I learned from each.   I will then close with a few comments about the assignment in general, followed by references.

Required Features

Immediately upon execution, the program reads in a file containing a set of points describing Bezier patches.  These patches make up a surface to display, created using uniform subdivision at a resolution determined at compile time.  The surface can be displayed in points-only, wire-frame, or fully shaded mode via keyboard commands.  The below images show the mesh resulting from "teapot.bez", with lighting provided by two infinite lights.

Figure 1. The teapot Bezier surface with normal shading.	Figure 2. The teapot Bezier surface, wire-frame only.	Figure 3. The teapot Bezier surface, vertices only.

Keyboard switches allow changing of the vertex color scheme to show different curvature values at each point.  These curvatures were calculated using methods discussed in class.  The following figures show color maps for maximum curvature, minimum curvature, Gaussian curvature, and mean curvature.  The map from colors to rough curvature values is displayed to the left of each row, with values ranging from large negative numbers through zero to large positive numbers.

	Figure 4. Gaussian curvature values at each vertex,  mapped onto the teapot surface.	Figure 5. Gaussian curvature values at each vertex,  mapped onto the teapot surface, different  perspective.
	Figure 6. Mean curvature values at each vertex,  mapped onto the teapot surface.	Figure 7. Mean curvature values at each vertex,  mapped onto the teapot surface, different  perspective.
	Figure 8. Maximum curvature values at each vertex,  mapped onto the teapot surface.	Figure 9. Maximum curvature values at each vertex,  mapped onto the teapot surface, different  perspective.
	Figure 10. Minimum curvature values at each vertex,  mapped onto the teapot surface.	Figure 11. Minimum curvature values at each vertex,  mapped onto the teapot surface, different  perspective.

In addition to coloring vertices according to various types of curvature, line textures showing  the normal, tangent direction, or principle curvature directions at each point on the surface can be applied via keyboard commands.  The following figures show the normal direction, u and v tangent directions, and principle curvature directions at each point.

Figure 12. The normals at each vertex of the teapot surface.	Figure 13. The partial derivatives in u and v at each vertex of the teapot surface.	Figure 14. The directions of principal curvature at each vertex of the teapot surface.  The green lines are the directions of maximum curvature, the pink the minimum.

Additional Features

Outline Generation

Two dimensional outlines of the surface can be rendered and applied using two different methods.  The first algorithm uses vectors describing the camera view and the surface normals.

The first step of my algorithm calculates a vector between the camera and the object is calculated and normalizes it.  This vector is then dotted with the normal at each point in the mesh, which was pre-computed and stored at startup.  When the dot product of the normal of a vertex and the camera vector is within a small margin of error of 0 (the error  margin is necessary because even with fine meshes the results will have major holes otherwise), the vertex is added into a linked list of similar vertices.  A linked list is used because it will make sorting quicker later, as points on the outline of the surface will likely not be in order.

Next, the linked list of vertices is 'distance' sorted, meaning that each vertex is moved  next to the vertex closest to it, via the distance function, within the list.  This is an easy way to order the vertices for drawing lines, but it is obvious that it will only work reliably at high resolutions.

Finally, the vertices are connected with lines and the outline appears.  Figures 15 and 16 give an example of this technique in action.

Figure 15. Geometrically created outline of the  teapot surface.  Note the discontinuities where no points were registered as being on the outline.	Figure 16. Another example of a geometrically created outline of the teapot surface.  The drawbacks of this method are even more noticeable here.

Note that even with a fine mesh, this method does not give extremely good results.  In addition, it was difficult to 'tune' the margin of error such that all points on the outline were chosen correctly without extra vertices being added.  As an example, the edge along the spout of the teapot in figure 16 shows what happens to the outline when there is no point close enough on the edge of the viewable surface to be picked up as part of the outline.  The spout curves more quickly than the edge of the teapot, making resolution more important there.  Finally, because of the extra sorting done to make up for the default vertex ordering, the algorithm doesn't give very good frame rates.

The other method implemented to trace the outline of an object made use of OpenGL's stencil buffers.  The algorithm is simple.  First, the surface mesh is rendered into the stencil buffer.  Next, the mesh is rendered again to the screen, only this time in thick wire-frame.  OpenGL then compares each rendered wire-frame pixel with what is in the stencil buffer, and replaces it with the contents of the stencil buffer where applicable.  The result is a thick outline around the object which is much cleaner and cheaper than the first outline method.  The idea for this came from reading various OpenGL help pages, along with  [1]--although this paper doesn't quite use the same technique described here.  Figures 17 and 18 give some examples of this method in action.

Figure 17. Outline created with stencil buffers.	Figure 18. Another example of stencil buffers in action.

Sketch Rendering

The other extra feature implemented in my program is an option to render the surface using a sketch-like rendering effect.  The idea for this came from [2] along with lecture materials, and there are also some great examples in books in the engineering library. 

 The algorithm I created to do this kind of rendering works as follows:

1. First, for each point in the mesh, vectors are calculated to each light source and the camera. 
2. These vectors are then dotted with the normal at the point.  Only points with positive dot products with at least one light and the camera are considered for eventual sketch line placement.  This makes the 'sketch' seem more sketch-like, since most artists do not draw both sides of an object or pure black.
3. The weighted average of all light contributions is then calculated and stored.  The weights are customizable, allowing for different lighting effects.  This value is the 'light contribution' to whether or not this point has lines drawn at it.
4. Next, the min and max curvatures at the vertex are averaged, and the 'curvature contribution' is stored.
5. A weighted average is then calculated with the light contribution and curvature contribution.  In the above pictures the light contribution was weighted slightly more than curvature.
6. Next, a uniformly distributed random number between 0 and 1 with mean 0.5 is generated and saved.  The random number is compared with the weighted average to decide whether or not to draw any line at all.  This means that vertices with high curvature and less light are much more likely to be drawn.  Distributions other than uniform were tried, but uniform seemed to give the best results. 
7. If a line is to be drawn, the random number is then used to decide whether or not a curve will be drawn in the maximum curvature direction or the minimum.  There is equal chance of either, a parameter which can really change the look of the sketch when experimented with.
8. Finally, a line is rendered to the screen at the vertex.  The length of the line is also randomized slightly.

Figures 19-23 present comparisons of normal shading verses renders by the sketch algorithm for the teapot surface.

Figures 19-23.  Comparison images between normal shading and 'sketch' rendering.

Because most of the complex values, such as curvature, are pre-calculated and stored on load, 'sketch rendering' ends up being quick even on high-resolution meshes.  Also, its highly customizable; tweaking the parameters can give some very interesting effects.

Conclusion

I really enjoyed this project.  It was fun to create all of this from scratch, learn the math, and then implement interesting extensions to what was presented in class.  The part that took me the longest was trying to figure out what all the different types of curvature actually 'meant,' as this was the first time I had seen these terms.  My only regret is that I couldn't spend more time tweaking my methods and adding more features.  I look forward to getting started on my semester project soon.

References

[1] J. Rossignac and M. van Emmerik. Hidden Contours on a Framebuffer. In Proceedings of the 7th Workshop on Computer Graphics Hardware, Eurographics, September 1992.

[2] Winkenbach, G. and Salesin, D. H. Rendering Parametric Surfaces in Pen and Ink. Computer Graphics Proceedings, SIGGRAPH 1996.

(also various OpenGL web pages)