Rendering Line Drawings From 3D Models

Tom is a systems programmer for an entertainment graphics company. He can be contacted at [email protected].

Bézier Curves

The imitation of reality has been the supreme goal of computer graphics. There's just one problem: When was the last time you could make sense of reality? When driving, I can miss seeing a stop sign that hides behind a tree, struggle to keep my car inside fading lane lines, or fail to notice a patrol car behind me. Reality, in other words, is a mess -- contrast between adjacent items can be poor, outlines indefinite, and colors distracting. In short, photorealistic rendering suffers from these problems to the degree that it imitates reality.

For immediate visual communication, however, a simple line drawing may be all that is needed. A black line drawing on a white background can be clear and definite, as well as cheap to print. It can emphasize important details and drop extraneous clutter. Nonphotorealistic graphics make an immediate impression on the viewer.

Luckily, there are techniques for extracting precise edge-and-shape information from less-than-precise 3D models so that you can generate clear and discernible pen-and-ink-like drawings. In this article, I'll examine three of these algorithms:

• Using difference operators on the Z buffer.

• For parametric surfaces, drawing isoparametric lines.

• Using normals and dot products to detect where the surface curves away from the viewer, and also drawing boundaries.

To illustrate these techniques, I'll use the room scene in Figure 1, which includes a desk, globe, chair, and levitating Bézier surface. The example program, called "room" (available electronically; see "Resource Center," page 5) is about 900 lines of C++ and based on OpenGL. Although a class hierarchy makes sense here, it isn't as helpful in describing algorithms. Even the vector container from the Standard Template Library becomes annoying for arrays of fixed length; I have to declare both a standard array and the vector object, then fill in the vector with the old array. Unless I'm doing sorts and other heavier algorithms provided by the STL, this doesn't return much. The program is built from four modules, each in its own .cpp file and represented by an include file: room.cpp (main) and room.h, world.cpp and world.h, roomutil.cpp and roomutil.h, and Bezier.cpp and Bezier.h.

I've made use of the OpenGL graphics library because it takes care of the modeling and n issues, and provides access to a Z buffer. I developed "room" under Linux 2.2 with Mesa (by Brian Paul), but room should run under Windows. My GUI is GLUT because, although limited when compared with major GUIs, GLUT makes the code more portable. You may need to acquire GLUT over the Web for your system, but OpenGL seems to be included in Windows 95, and may be included with other operating systems.

Difference Operators on the Z Buffer

One technique for making line drawings from 3D models is to apply difference operators to the Z buffer. While each pixel in the framebuffer is the value of the red, green, and blue colors given the object color and the light falling on it, the value of each pixel in the Z buffer is the distance from the viewer's eye to the model in OpenGL's internal coordinates between 0 and 1. Displayed, the Z buffer is brighter for more distant points and darker for closer ones. Figure 2, a view of the room via the Z buffer, shows that the more distant objects are brighter because they have higher Z or depth values, and higher values are displayed as bright in the frame buffer.

In the continuous domain, rates of change in functions are found with derivatives. For derivatives of scalar fields, there are the general operators -- (del, a derivative) and -- ² (the laplacian, a second-order derivative). When applied to a graphic image in one color, a del operator tends to make a derivative image that has higher values where there were rapid changes between light and dark -- where you might want outlines. From a Z buffer image, this tends to draw silhouette lines at edges of objects against the background because there is a big change in depth from the object to the background. This change from an object to the background is called a "discontinuity," even though this term applies in math only to continuous functions and not an array of discrete points.

A first-order Sobel operator tends to draw lines at simple changes in value. From a Z buffer, Sobel operators draw silhouettes around objects, because it detects the change in value from the object's edge to the background. Unlike the laplacian, Sobel requires two matrices, one of which finds changes horizontally and the other vertically. The matrices are:

Listing One, from the module room.cpp in the function sobel_diff(), uses these matrices (sobela and sobelb, respectively). Figure 3 is output from Listing One. Advanced work has addressed issues with these operators, such as doubling narrow lines and occasionally drawing lines on the middle of a model's surface because its slope (relative to the viewer) is very fast, and therefore found by difference operators.

A second-order operator such as a laplacian tend to show turnarounds (inflections). From a Z buffer image, a laplacian tends to draw lines at the cornered intersections of walls and other surfaces. The laplacian operator is simply:

The purpose of "-1" is to subtract neighboring pixel values from the value at the center of the operator's matrix, which is scaled to be in units of the same magnitude. Listing Two is from room.cpp's laplace_diff() function. The laplacian operator is centered over a pixel in the Z buffer. In Figure 4, this is centered over the part of the Z buffer that has the values:

All you do is multiply corresponding values and add:

then add the products:

-.2-.3-.2-.2+2.4-.2-.2-.3-.2=.6.

You do this for each pixel. (I skipped the border pixels to avoid the if statements required to detect the borders and fill in the missing values, such as the center value, which would register no difference with the missing pixels -- appropriate behavior for this operator). Listing Two does this.

The outer loops of i and j scan the entire image width and height. The inner loops move through the 3×3 operator. Clearly, this could be optimized by replacing the two inner loops on io and jo with a single statement; see Listing Three. Figure 5 is the result of this operator.

Isoparametric Lines

Isoparametric lines are those in which one parameter is held constant while another changes. This presumes that your model's surface is defined parametrically in the first place. The Bézier surface in this example has two parameters (u and v in the code). When you select "isoparametric" from the menu, the Bézier surface is drawn as a collection of lines with a u constant for each sweep of the surface by a changing v. The lines suggest the curvature of the surface, and also bunch up where the surface is narrower. This may help define the surface, but there are algorithms for dropping out lines as they become crowded. Without hidden line removal, this algorithm is incomplete, but it serves as an illustration. Although OpenGL supports Bézier surfaces, I built mine from scratch to have direct access to the way it is drawn and to illustrate the techniques used.

The code to draw the Bézier surface as lines (see Listing Four, from bezier.cpp) is combined with the code that draws it as quadrilateral patches. All this does is draw sets of connected line segments as you change the u parameter. The result is a set of curves that follows and suggests the surface. Figure 6 is the result of this approach.

Finding Silhouette Edges from Vector Operations

The final technique I'll present here for making line drawings from 3D models involves finding silhouettes from vector operations on the normals to the surface of the model. I'll use the Bézier surface for this example as well, since finding its silhouette where it bends behind is more interesting than finding the boundaries of boxes.

Finding this silhouette is easy for boundaries. I know where the boundaries of my Bézier surface are -- at the boundaries of my matrix of vertices. All I need to do is to draw lines along the vertices at the edges of my matrix of vertices. It's trickier to find the silhouette of where I made the surface curve behind. To do that, I use the normals (the vectors at right angles to the quad patches), and the vector from the viewer's eye to the normals.

For each test vertex:

1. Find the normal to the test patch and those neighboring patches that share an edge.

2. Find the vector from the viewer's eye to the patch.

3. Find the dot product of the view vector and the normal for each of the patches.

4. Compare the resulting dot products. If there is a change of sign in the dot product from the test patch to its neighbor, then one is bent behind the other; draw the edge between the two patches. Figure 7 shows the relationships between these various vectors.

The code is in bezier() and is the "else" to "if (isoparm)" on the assumption that you are using either isoparametric lines or silhouettes. Some code for finding silhouettes is in bezier() and Listing Five (from the bezier() function in the module bezier.cpp). The code has to check that the parametric indices that march along the surface still have at least one more vertex to go, because it will compare dot products for this surface and the next one. I don't need to compare dot products for the last surface because it is a boundary and will get a line for that reason. Figure 8 shows the results of finding the silhouette of the Bézier surface. I have neglected hidden-line removal for this algorithm as well, and the small end of the surface can be seen.

References

Angel, Edward. Interactive Computer Graphics: A Top-down Approach with OpenGL. Addison-Wesley, 1997.

Janzen, Thomas. 10 Papers on Non-Photorealistic Rendering. http://world.std .com/~tej/, 1998.

Lansdown, John and Simon Schofield. "Expressive Rendering: A Review of Nonphotorealistic Techniques." IEEE Computer Graphics and Applications. May 1995.

Paul, Brian([email protected]). Mesa 3.0. ftp://iris.ssec. wisc.edu/pub/Mesa/.

Saito, Takafumi and Tokiichiro Takahashi. "Comprehensible Rendering of 3-D Shapes." ACM Computer Graphics: Proceedings of SIGGRAPH, 1990.

Williamson, Richard E. and Hale F. Trotter. Multivariable Mathematics: Linear Algebra, Calculus, Differential Equations. Prentice-Hall, 1979.x

SGI OpenGL resources: http://www.sgi .com/Technology/openGL/, http://www .digital.com:80/pub/doc/opengl/, http:// www.sgi.com/Technology/openGL/glspec/glspec.html.

Woo, Mason, Jackie Neider, and Tom Davis. OpenGL Programming Guide, Second Edition. Addison-Wesley Developers Press, 1997.

Kempf, Renate and Chris Frazier, editors. OpenGl Reference Manual, Second Edition. Addison-Wesley Developers Press, 1997.

DDJ

Listing One

for (i = 1; i < (gw - 1); ++i) {
  for (j = 1; j < (gh - 1); ++j) {
    suma = 0.0; sumb = 0;
    for (io = -1; io <= 1; ++io) {
      for (jo = -1; jo <= 1; ++jo) {
        suma  += sobelaM[io+1][jo+1] * pixels[i + io][j + jo];
        sumb += sobelbM[io+1][jo+1] * pixels[i + io][j + jo];
      }
    }
    diffpixels[i][j] = (fabs(suma) + fabs(sumb)) / 8.0;
  }
}

Back to Article

Listing Two

for (i = 1; i < (gw - 1); ++i) {
  for (j = 1; j < (gh - 1); ++j) {
    sumo = 0.0;
    for (io = -1; io <= 1; ++io)
      for (jo = -1; jo <= 1; ++jo)
        sumo  += laplaceline[io+1][jo+1] * pixels[i + io][j + jo];
    diffpixels[i][j] = sumo / 3;
  }
}

Back to Article

Listing Three

sumo += (-pixels[i-1][j-1] - pixels[i-1][j] - pixels[i-1][j+1] 
      - pixels[i][j-1] + 8*pixels[i][j] - pixels[i][j+1] 
      - pixels[i+1][j-1] - pixels[i+1][j] - pixels[i+1][j+1])/8;

Back to Article

Listing Four

glBegin(GL_LINES);
 ...
for (u_ctr = 0; u_ctr < PARM_STEP_QTY; ++u_ctr) {
  for (v_ctr = 0; v_ctr < PARM_STEP_QTY; ++v_ctr) {
    if (isoparm) {
      if (!(u_ctr % 4) || (u_ctr == (PARM_STEP_QTY - 1))) {
        glVertex3dv(vertices[u_ctr][v_ctr]);
        glVertex3dv(vertices[u_ctr][v_ctr + 1]);
      }
    }else {
      ... // draw either silhouettes or patches
    }
  }
}
glEnd();
 ...

Back to Article

Listing Five

void Bezier(Bezier_type points, const dbl_vec_type LookAtEye)...
for (u = 0; u <= PARM_STEP_QTY; ++u) {
  for (v = 0; v <= PARM_STEP_QTY; ++v) { ...
  cross(vert[u][v + 1], vert[u][v], vert[u + 1][v], n);
  if (silhouette) {
    ... // draw borders on edge vert
    if ((v + 2) <= PARM_STEP_QTY) { // for inner patches
      cross(vert[u][v + 2], vert[u][v + 1], vert[u + 1][v + 1], n2);
      eyevect[0..2] = vert[u][v + 1][0..2] - Eye[0..2];
      if (oppositesigns(dot(eyevect, n), dot(eyevect, n2))) { 
        glVertex3dv(vert[u][v+1]);
        glVertex3dv(vert[u + 1][v + 1]);
      }
    }
    if ((u + 2) <= PARM_STEP_QTY) {
      //... similar code along changing u counter
    }
  }else {
   //  draw normal patches.
    ...

Back to Article

Listing Six

for (k = 0; k < DIM_QTY; ++k) {
  for (i = 0; i < DIM_QTY; ++i) {
    for (j = 0; j < DIM_QTY; ++j)
      p[k] += bu[i] * bv[j] * p_control[i][j][k];
  }
}

Back to Article