Comic Rendering

For several reasons the comic renderer was the first one to be implemented. One of these reasons being that I had the best idea of how to go about it. I found a little program on www.darwin3d.com/gamedev.htm called Loony (written by Jeff Lander), which pretty much did exactly what I imagined a cartoon-renderer should do, so I ran it and thought about how I could implement something similar. The following is a description of my initial ideas and the progressive refinement of the implementation.

Basic Comic Style

Even though it is probably difficult to decide what comic-style actually means, I look at my own drawing (Figure 1) and identified the following:


Figure 1 - A quick Cartoon Sketch

Obviously this drawing style is by no means standardized, but the produced effect can easily be recognised as a cartoon style.

Implementation Consideration

As it is done on paper this technique requires two basic passes: One for the outlines and one for the shading. To implement this technique in software the following considerations are important:

Outlining

The existing 3D models available under CoRgi are based on triangular primitives (as are many other 3D descriptions). Since the outline of objects seems to be more important than the interior, it seemed reasonable to work with Edge-information rather than triangles. Obtaining the edge-information from a triangle description is discussed a little later. In the course of this discussion we will make the following assumptions about edges:

To obtain the outline of an object we consider only those edges that fulfil the following condition: With respect to the normals of adjacent triangles, one has to face the viewer, while the other one has to point away from the viewer. This condition is explained in Figure 2.


Figure 2 -Side-view of a typical scene (Lines represent
 triangles, while numbers mark edges. Normals are marked with arrows)

It should be noted that only the viewing direction but no positions are taken into account at this point. A normal is facing towards the viewer if the dotproduct between the normal-vector and the view-direction-vector is negative. If the dotproduct is positive, the normal is facing away from the viewer. Since the outline-condition states that one normal has to face the viewer, while the other one has to point away from the viewer, this the product of the dotproducts has to be negative. This is clearly the case for edges {4,5,6,7,8}. It is not well defined for edges {1,11} because the triangle represented by the line [1..11] has a normal perpendicular to the viewvector, making the combined dotproduct zero, thus flushing out a reasonable result (in fact the direction of the other normal becomes irrelevant). A possible solution would be to include these edges by default.

From the direction of the viewer the silhouette of the object in Figure 2 is actually only defined by the edges 6 and 1 and/or 11, but as stated above the edges {4,5,7,8} will also be marked as outline-edges. This is not necessarily undesired as these other edges usually represent some relevant geometric detail of the object.

As we can see in Figure 3 this method already produces reasonable results. Figure 3a shows half the triangles comprising the wireframe of a rocket-object. It is easily conceivable that drawing also the front-facing triangles would obscure the scene even more. Figure 3b shows in thick lines all those edges for which the outline-condition holds. Additionally some lines were drawn somewhat thinner wherever the outline-condition was not met, but the angle between adjacent triangles was greater than a certain threshold value, thus giving hints about harder edges.

Considering that the actual rendering of objects is one of the most expensive operations in the graphics pipeline, we can see how the elimination of undesired edges can improve on the drawing performance (Figure 3c). 


Figure 3 -a) Normal wire-frame (acutally showing only backfacing triangles)
b) Only edges for which outline-condition holds (thick) and "special" edges (thin) are drawn
c) a comparison of figures a) and b)

The next problem arises because of edges like {7,8,11} which fulfil the outline-condition but should be hidden because they are located at the back of the object. Possible solutions are any kind of hidden line removal (HLR). The one we use here is the readily available z-Buffer and to draw front-facing triangles to eliminate edges at the back of the object. This is not actually a great inconvenience, because we want to shade the object anyway.

Shading

The shading the object is a function of the light-direction and the normals of triangles comprising the object. Several functions exist to take various measures such as angle between normal and light-vector, distance to light-source, wave-length of light and others into consideration to produce a realistic lighting-effect. For our comic-renderer realism is not the highest objective. Instead we want to give basic clues about shape and orientation of the object with as little effort as possible.

To this effect we first used the dotproduct of the light-direction-vector and the normal of each triangle to determine a color value for that triangle. A look-up table was created to map the possible dotproduct-values into a table containing 32 shading values. The content of this table determined how many different shades were available and how they related to the value of the dotproduct. The result was that depicted in Figure 4a. As can be seen the visual effect is very blocky and produces flickering when animated due to the fact that whole triangles change color when the light-direction changes relative to the object. Even for objects with a high triangle-count this effect is disturbingly noticeable.

Our current (visually more pleasing) approach uses the same table-look-up, but performs the dotproduct-calculation at each vertex instead of each triangle and then makes use of the smooth shading capability of OpenGL to interpolate the shade-values on the triangles. The result can be seen in Figure 4b. Another problem is that even though the main body of the rocket is now smoothly shaded (even under animation) the feet of the rocket display unrealistic shading due to the interpolation on flat surfaces with little geometric detail. This is a compromise that we are willing to make. Possible solutions are to take the edge-information into consideration to identify regions of relatively flat regions and color these in uniformly.


Figure 4 -a) Triangle Shading. b) Interpolated Vertex-Shading with early outline-technique
c) Interpolated Vertex-Shading with accelerated outline-technique

Outlining revisited

Even though the produced effects are an acceptable comic-style, they showed to be relatively slow in practice (especially when using objects of high detail). The solution to this we found in the implementation of Lander's code. He produces an outline without the knowledge of any edge-information with the clever use of specific OpenGL-commands. The Polygon-mode is set to draw wire-frame-style triangles instead of filled triangles. Then the back-facing triangles are drawn with a thick line-style (resulting in Figure 3a). In the Shading-phase the front-faces are drawn to hide everything but the outline of edges fulfilling the outline-condition automatically. Since no edge-information has to be generated for this approach and no testing is necessary when drawing, this method can be fully accelerated by existing hardware. The only disadvantage is that the thinner lines in Figure 4b cannot be reproduced by this method - another compromise we are willing to make (for the sake of fast rendering).

 

Generating Edge-Information from Triangle information

Even though it is not used in our final implementation of the comic-renderer we'd like to discuss quickly the approach we took to obtaining the edge-information necessary for our first outlining approach. In Pseudo Code, the method looks like this:

for each Triangle T(V1,V2,V3)
    E1 = V1<->V2
    E2 = V3<->V2
    E3 = V1<->V3
    found = false
    for all Edges Ei
        for each Edge E in Templist
            if Ei = E then
                Add T as second adjacent Triangle of E
                Add Edge E to Edgelist
                remove E from Templist
               
found = true
                break
            endif
        endfor
        if not found then
            Add Ei to Templist with T as first adjacent Triangle
        endif
    endfor
endfor

where:

By using a Templist, we minimise the edge-comparisons necessary. If we assume that every edge can only have two adjacent triangles, then an edge can be discarded for comparisons once it has found its second adjacent triangle. For the rocket object above this means that instead of an every increasing edgelist (without using a templist) resulting in about 150 edges having to be compared at maximum, we are faced with only 32 comparisons at maximum. These numbers are obviously dependent on the structure of the Trianglelist and the object under consideration, but show what a great improvement can be achieved even for small objects.