Saul Mooallem holds a B.S.E.E. from MIT and a masters in Applied Analysis and Computer Science from the University of Waterloo, Ontario. During his 25-year career in the computer industry, he has developed telecommunications applications and computer systems software, and has worked for both vendor and user organizations. You can contact him at 6 Rossmore Terrace, Livingston, NJ 07039.
Within the exciting realm of graphics are techniques to depict illumination and shading, to create realistic images of landscapes or plant life using fractals, and to process images. [See, for example, our on-going series on image processing. — ed.] One of the foundations of three-dimensional graphics, however, is solid modeling. Solid modeling employs primitives — basic solid objects such as cubes, spheres, cylinders, cones and toruses — to model extremely complex objects.
My curiosity about 3-D graphics led me to write a program that creates and displays solid objects. This article explains how to model cubes, spheres, cylinders and cones using polygons. It also describes how to resize, rotate and move these objects, and presents two different methods of displaying them.
Graphics Concepts And Terminology
A collection of objects that is displayed is called a scene. Each object in a scene is constructed from multiple facets represented by polygons in 3-D space. Each facet within the object has an equal number of sides and vertexes. For example, a cube is made of six four-sided facets. Since you cannot represent a cone's curved surface precisely using polygons, you must approximate it using a number of triangles that share a common vertex and a bottom facet with as many sides as the number of triangular facets. To construct objects, you use a coordinate system called world coordinates. As in the real world, each vertex has x, y, and z coordinates. The scaling system can employ centimeters, feet, or any other units you choose.
Building Object Definitions
A scene typically contains many instances of objects, each with its own position, size, orientation, and color. Before you create a particular object, you should construct the basic definition of that type of object. The definition is a prototype from which you build objects. All definitions in this program are centered at world x, y, z coordinates (0, 0, 0), are one unit high and wide, and are aligned on the y axis. For example, the program would represent a sphere as a globe with its north and south poles at 0.5 and -0.5 on the y axis, respectively. Similarly, the definition of a cone has its pointed end at 0.5 and its circular, flat end centered at -0.5 on the y axis. To construct an instance of an object, you perform transformations on its definition. There are three types of transformations: scaling (changing the object's size), rotation, and translation (moving the object to a new location). In addition, you can assign a color to each object. If you want a big green cone turned right side up, you simply rotate the definition 180 degrees, use a large scaling factor, move the object wherever you want, and assign it the color green.To display an object on the picture plane (your screen), you must map its vertexes from world coordinates to device coordinates (pixel positions). This mapping is called projection, since the appearance of the resulting image in the picture plane depends on the relative positions of the viewer's eye and the solid model. Mapping is like placing a slide projector at a certain point on the z axis and then selecting a lens (wide-angle or telephoto) and a viewpoint. To display a solid image, you must also perform backface removal, which hides from view any facets that face away from, and therefore should not be visible to, the viewer.
The program displays objects in either of two forms: wireframe or rendered. As the term implies, a wireframe display shows only the outline of each facet, but a rendered image shows each facet as a colored surface. In its simplest form, rendering uses solid colors. To create a more realistic image, you place "light" sources at certain points and shade each facet according to the intensity of the "light" striking it. Since Borland Turbo C++ supports only 16 colors on a VGA display, I used a technique called dithering to approximate various intensities in each of the 16 colors. Dithering entails using programmer-defined patterns to color the interior of a facet. Other, more complex rendering techniques are more photorealistic. Such methods even map textures to surfaces or assign properties such as translucency or reflectivity. Unfortunately, many of these techniques involve ray tracing and typically require the processing power of a graphics workstation. Creating a single image can easily take several minutes.
Figure 1 shows the hierarchy of all functions in the program and includes a description of each.
Data Structures
Since most graphics applications allow the user to create and modify objects on the fly, my program allocates all data structures dynamically. I've also provided global variables for many options and values to facilitate adding an interactive user interface. Definitions and objects have their own descriptors, defined as structures in the header solid.h. Facets and vertexes also have their own descriptors. Descriptors can point to other descriptors, and the scene is represented as a linked list of object descriptors. Figure 2 illustrates the descriptors' structures and the relationships among them.A realistic visual representation of a sphere requires hundreds of vertices and facets. To minimize both memory and processor usage, all transformations operate only on the x, y, and z coordinates of the object's vertexes. Because the facet descriptors simply tell which vertexes belong to each facet, they are never modified by transformations. For example, since all instances of cubes have the same six facets, I conserve memory by maintaining facet descriptors only in the definition descriptor.
How The Program Operates
The function define_solid constructs the definitions of all four primitive objects as special cases of a general definition. Think of a sphere as a globe marked with lines of longitude and latitude. The basic idea is to make multiple sweeps around the globe, top to bottom, starting each sweep at the same longitude and moving counterclockwise as viewed from above the sphere. On each sweep, the descriptors for all the facets are constructed first, and then those for the vertices along the bottom edge of the sweep. define_solid constructs triangular facets in the polar regions (the first and last sweeps) and rectangular ones elsewhere.A cone, on the other hand, requires only a single sweep (the north polar one). As a special case, a cone also needs a facet in the x-z plane for its flat, circular end. Next, a cylinder needs a non-polar sweep to construct the rounded wall from rectangular facets, as well as two additional facets (another special case) for the top and bottom. A cube is just a cylinder with four rectangular facets per sweep. Incidentally, defining a pyramid as a special case of a cone is equivalent to defining the cube as a special case of the cylinder. When constructing facet descriptors, the algorithm I used to determine whether a facet is visible requires that the facet's vertexes appear in counterclockwise order, as seen from the exterior of the object.
The function make_object, constructs an instance of an object. The function first checks whether the definition for the specified type of object exists. If not, make_object builds the definition by calling define_solid. Then it constructs the object descriptor, copies the vertex descriptors from the definition to the object descriptor, and initializes the scaling, rotation, translation, and color values. Thereafter, you can set any of these values directly in main.
After make_object has generated all the objects, show_scene takes over. First it calls transform_object once for each object in the scene. This function scales, rotates and translates each vertex and determines whether each facet is visible. transform_object also calls display_facet to do a trial projection of each vertex in order to identify how much of the image will be projected onto the screen. (This is like positioning your camera for a group portrait. The image should be as large as possible without cutting anyone out.) Finally, show_scene calls display_facet to draw each facet on the screen.
To perform scaling on a vertex, transform_object simply multiplies each vertex coordinate by the corresponding scale factor. Rotation requires some geometry formulas that I won't describe here (see the listings or references). To translate an object, transform_object merely adds the x, y, and z translation values to each vertex's x, y, and z coordinates, respectively. You must perform rotation before translation, otherwise the object will be revolved about the origin of the coordinate system rather than rotated about the center of the object itself.
After performing these three transformations, transform_object calls display_facet with the argument display_opt set to FALSE. Instead of drawing the facet, display_facet projects the facet onto the picture plane to determine the field of view. By maintaining the minimum and maximum x and y values of all projected vertices, you can maximize the image size on the screen. The global variable border even allows you to vary the size of the border around the image. display_facet also determines whether the facet is visible. Because vertex indexes appear in a certain order, if the facet faces away from the viewer, the angle between the normal vector (the vector perpendicular to the facet) and a vector from the origin has a negative cosine. This technique of identifying invisible facets is called backface removal.
Backface removal, which treats each facet independently, differs from visible surface determination, a complex and computation-intensive process. Visible surface determination sorts all the polygons in the scene and then performs several tests to see whether any two intersect. Unlike backface removal, it can correctly display two intersecting solid objects.
The second time display_facet is called for a facet, the argument display_opt is set to TRUE, causing display_facet to call draw_polygon, which performs the projection and actually draws a polygon. The global variable render_opt tells whether to use a wireframe or a rendered representation. In a wireframe representation, the global variable display_hidden tells whether an invisible facet should be displayed at all and, if so, whether it should be shown in a different color or with broken lines. Backfacing facets are always skipped if rendering is selected.
Rendering a visible facet takes three steps: drawing the outline of the facet in a unique color (white) to provide a boundary for filling; shading the interior of the facet; and redrawing the outline with a broken line that matches the interior fill pattern. The function render_facet computes the light intensity on the facet, selects a corresponding fill pattern, and fills the interior of the polygon. The illumination depends on the dot product of the unit vector perpendicular to the facet and the unit vector from the light source to any point on the facet. I've used a single light source in my program and take into account only the angle of illumination, not the distance from the light source to the facet. render_facet selects from 12 fill patterns ranging in density from zero to 100 percent. To shade a facet's interior, I calculate a seed point by averaging the x and y coordinates of the projected vertices. One limitation of my program is that relatively small facets on the screen cause the fill to "leak out" of the polygon. One solution would be to avoid filling facets smaller than some predetermined size.
In addition to the complexities of geometry formulas and vector arithmetic, the most challenging aspects of writing this program were keeping track of all the pointers and vertex indexes, and debugging the program. To aid my debugging efforts, I finally wrote a couple of functions that print the facet and vertex descriptor information.
Possible Enhancements
Since all the graphics routines I use have counterparts in other libraries, porting this program to other compilers or environments shouldn't be difficult. The only functions that call graphics functions are main, display_facet, render_facet and draw_polygon. You could take many different directions to enhance this fundamental program: a user interface; multiple light sources; additional types of solids; visible surface determination; animation (for instance, a spinning cube); or multiple viewports with mouse control (as in 3-D computer-aided design applications). I've even thought of using fractals to turn each facet into many smaller ones, creating the appearance of a bumpy surface.
References
Foley, James D.; van Dam, Andries; Feiner, Steven K.; and Hughes, John F. 1990. Computer Graphics, Principles and Practice, 2nd edition. Addison-Wesley. Reading, MA.Adams, Lee. 1986. High-Performance CAD Graphics in C. Windcrest Books. Blue Ridge Summit, PA.
Listing 1: soldfs.c
Listing 2: soldis.c
Listing 3: soldrp.c
Listing 4: solid.c
Listing 5: solid.h
Listing 6: solmko.c
Listing 7: solqui.c
Listing 8: solrdr.c
Listing 9: solsho.c
Listing 10: solvec.c
Listing 11: solxfo.c