Stereo graphics; mesh plots and hidden line removal. (part 2) John D. Fowler Jr..

Last month's discussion on creating lifelike images with plausible depth will be extended in this installment to include plotting of mathematical functions of two variables with removal of hidden lines. I hope you still have the viewer described in the first part of this series. You will need it to capture the sense of depth inherent in the stereo images shown on these pages. Most of the definitions and concepts introduced in the first part will also apply here.

The plots which accompany this article are two-dimensional projections of three-dimensional graphs of functions of two variables. A function of two variables may be written as:

y=f(x,z).

The dependent variable y is uniquely determined by some mathematical combination of terms involving the independent variables x and z. For each value of x and z, the functional relationship returns a single value of y, the value of the function. Some examples of two-variable functions will be given later in this article.

The presence of a three-variable (y,x, and z) relationship creates a serendipitous corresponding with the three dimensions of our real world. If we let pairs of values for x and z represent points on a flat surface, the functional values of y can represent the height above the plane over the points (x,z). If we take regularly-spaced values of x and z in order to form a square grid on the flat surface, the corresponding values of y will form a set of points above or below this grid. Connecting neighboring values of y along lines of equal x and equal z gives us a net-like graphic approximation of the function. Such a graph is called a mesh plot.

A mesh plot of a pyramid-like function is shown in Figure 1. The figure is a projection onto the page of an object (the three-dimensional graph of the function), plotted from a particular viewing point. If it were plotted from directly above (or below) and with a large enough viewer-to-object distance to prevent perspective distortion, the square mesh projection onto the X-Z plane would be apparent.

One source of confusion in viewing plots of this type is the presence of line segments which, had this been a real solid, would be hidden from the viewer. Removal of the these hidden lines renders the object more readily recognizable and, in the case of mimicking real objects in stereo, enhances the illusion. Figure 1, but with hidden lines removed. Hidden Line Removal

Removal of hidden lines (or surfaces for solid objects) has occupied the attention of workers in the field of computer graphics for almost as long as computers have been drawing figures. Specific methods have been discovered which work efficiently for particular types of plots, but will not function properly for others. Several methods will be outlined here.

Direct coding. Given a particular object with a specific orientation and viewer position, the programmer can handcode the program to plot only those lines which will be visible. This can be done by calculating the end points of visible line segments prior to writing the program. This method, of course, is very specific and useless for displaying objects in more general situations.

Plotting from the front using a memory map. This takes a lot of memory but allows a more general solution to plotting multiple objects with hidden lines removed. The amount of memory needed depends on the display resolution. One bit is required for each picture element (pixel) of the display. For a 1K display (210 x 210 bits) 220 bits or 128K bytes of memory must be dedicated to plotting. There exist today personal computers with this much memory, and they will be commonplace in the near future.

The procedure is as follows. Clear (zero) the memory map. Assign a bit in the map to each point on the display. Start at the front of the nearest object to be plotted and calculate, point by point, the display elements to be plotted. Check the map, and if the bit corresponding to a given point contains a zero, set the bit to 1 and plot the point. If the bit already contains a 1, the point is hidden and should not be plotted. After the nearest object has been plotted, continue with the second-nearest object, and so on.

Overlapping objects, for which parts object 1 are both closer and further away than object 2, can be tricky.

Plotting from the front and maintaining a perimeter list. For certain types of objects, remembering every visible point is unnecessary, thus allowing the use of considerably less memory. This class of objects consists of those for which any thin vertical slice through the object is filled from a single bottom perimeter point to a single top point. Objects with holes or non-vertical projections do not qualify. Mesh plots are acceptable, as long as they are not rotated with respect to the horizon. For our purposes, this means that the mesh plots can not be rotated about the Z axis.

The procedure for plotting these objects is to start from the front and work back, always keeping a record in memory of the perimeter of the portion of the object which has already been drawn. Each point under consideration for plotting must be compared to the current perimeter. If it lies outside the perimeter, then the perimeter is extended to include the point, and it is plotted. If the point lies insides the perimeter, it is hidden and not plotted. The perimeter can be kept in two vector variables of dimension XRES, which is the number of resolvable points along a horizontal line on the display. One vector can contain the top half of the perimeter, and the other vector the bottom half.

This is the procedure which we shall use in our program for generating mesh plots. Notice the intimate connection between the variable dimensions and magnitudes and the display resolution. Since XRES and YRES will be a few thousand at the most, we can use 2-byte integers for most of the variables in our program. This will yield a substantial saving in memory. Other features

Some of the features of the program, in addition to hidden line removal, include:

* Arbitrary rotation of the function from 0 to 360 degrees about the Y axis, followed by arbitrary rotation about the X axis.

* Arbitrary viewer position (x,y,z) and plotting resolutions (XRES,YRES).

* Color coding of the function in the Y-direction according to the value of the function (See Figures 2, 3, 5, and 6).

* Using a different color for the bottom side of the mesh (Figures 4 and 5).

* Drawing single frames or stereo pairs.

The program is shown in Listing 1. The function to be plotted, which is written in the form: P=f(K,L) goes in the subroutine starting at Line 4000. The subroutine always terminates by scaling the function as follows: P=P*YRES/(3TX*FR), followed by a RETURN statement. The function is usually written so that the origin occurs where K and L both equal D/2. D is the number of lines along one side of the mesh.

Color coding the height of the function is accomplished by assigning maximum values for given colors (pens) to the vector V1. This is done in lines 40 through 60 and used in lines 3080 through 3110. The program as listed provides for 12 colors. This number can be altered by changing lines 20, 40, and 3080.

Variables FR and TX serve the purpose of scaling the plot so that it will fit properly on the display. In particular, TX is intended to be the maximum of the absolute value of the function over the plotting range, but it can also be used as a vertical scaling factor by setting it larger or smaller. The program assumes that the display coordinate (0,0) defines the lower left corner of the display. The variables Q and W then define, respectively, the horizontal and vertical displacements necessary to move the origin to the center of the display.

Since the program must always draw from the front, some calculations are required to set loop indices based on the viewing angles PH and TH. Lines 160 through 230 set the indices properly so that plotting will always begin at the nearest corner of the mesh. Sines and cosines of the angles are calculated in lines 260 and 270.

The perimeter vectors H (for high side) and L (for low side) are initialized in line 290. These two vectors test the visibility of a point in the following ways: For any point (M,N) on the display, if N is greater than H(M) or if N is less than L(M), the point is visible; otherwise, it is hidden. If the point is visible, the perimeter must be altered by setting either H(M) (if above) or L(M) (if below) to N. Note that the variable M must be an integer, since it is used as a subscript in the perimeter vectors.

The main part of the program begins at line 200. There are five subroutines which perform the functions discussed below. The subroutine at line 2000 calculates the display coordinates (M,N) for mesh points. For a more detailed description of this subroutine, see Part 1 of this series in the January 1983 issue of Creative Computing.

The subroutine at line 3000 does the vertical color coding of the function, using ten variables as input: the starting point of the line (MOLD, NOLD); the end point (M,N); the first visible point (M1,N1); the last visible point (M2,N2); and the starting and ending values of the functions, PL and P. The subroutine Calculates pen-changing points and calls the plotting subroutine.

The subroutine at line 4000 defines the function P(K,L).

You will have to write your own plotting subroutine, since it will be specific to your system. This will be easy to do, however. The reference CALL DRAW (A,B,C,D) appears in the listing at lines 670, 770, 1170, and 3200. You must replace these lines with calls to a subroutine which draws a straight line from the point (A,B) to the point (C,D) using the color specified by the variable PN.

In drawing the mesh, the program distinguishes between two types of lines, almost-horizontal and almost-vertical (called h and v below). These directions are referenced to the horizontal and vertical axes of the display. A line which lies in a direction closer to the horizontal than the vertical axis is an H-line.

The subroutine from line 850 to line 1230 calculates the mesh points and determines the visibility of v-line segments connecting the current h-line to the next. Visible segments are plotted. Display coordinates (M,N) for the next h-line are saved in the vectors ML and NL. If a point is not visible, the vector component of ML for that point is set to its negative. This information will be used in the next part of the program.

The portion of the program from lines 300 through 830 handles the h-line segments. If both the last and current components of ML are negative, then the entire line segment is assumed to be hiden. Otherwise, the loop in lines 490 through 710 is executed to test for visible portions of the h-line segment.

When stereo images are drawn, the image intended for the left eye is drawn on the left side of the frame.

The functions which were used in drawing the figures are listed in Table 1. These should give you some good ideas in making up your own. The parameters for the function of Figure 6 were selected with the RND (random) function, so you might say that the computer did the whole thing. For further ideas on functions to plot, consult Melvin L. Prueitt's Computer Graphics (Dover Books, 1975).

The decision as to whether the bottom side of the mesh or the top side is being plotted, is made in lines 640, 740, and 1140. The pen color number, PN, equals 2 if plotting is on the underside; otherwise, PN equals 3.

Lines 650, 750, and 1150 will switch PN to 1 whenever the line number being plotted is exactly divisible by D. This is what colors the border of the mesh with the color corresponding to a PN of 1. To use color number 1 on, for instance, every fifth line, change D to 5 in lines 650, 750, and 1150.

If PN is greater than the number specified in line 660, 760, or 1160, the color-coding subroutine at line 3000 will be called. To color-code the whole mesh, set this number to zero. To color-code just the top side, the number should be 2, as in the listing. If the number is set to 3 or more, no color-coding of the vertical direction will occur.

The foregoing offers a very incomplete sketch of how the program works. The best way to learn about it is to use it. Observe what happens as the picture is being drawn. Try to change it. Make up some functions of your own. Most of all, I hope you have fun.