| |||||||||||||||||||||||||||
|
1 System RequirementsThe following libraries and tools were used in the implementation of this assignment (and are thus required for running the binary file):
2 User InterfaceThe 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:
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 EdgesA 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 EdgesA 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 EdgesA 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 VisibilityEach 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.
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 AlgorithmBresenhams 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 AlgorithmStarting 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 CollisionsIt 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 RenderingEdges 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.
8 ShadingFor 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.
9 PerformanceMachine SpecificationsThe machine used is "SilverRaven2" and it has the following specs:
Frames Per SecondFrames 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. NOTES:
10 Result ImagesIn no particular order, here are some images that were rendered using the contour program.
References
|
