Color computing and 3-D graphics still going strong and growing
BYTE ran the first installment in a series of how-to articles
on how to accomplish 3-D programming. Fifteen years later, 3-D is increasingly appearing in mainstream computing through games, business applications, and the Internet. We also reviewed Tandy's Color Computer.
In
March 1981
Franklin Crow from Ohio State University provided Part 1 of our 3-D graphics how-to. So enjoy...especially if you're not content to let your software do all the work! The Tandy review follows this article as a sidebar.
Three-Dimensional Computer Graphics, Part 1
by Franklin Crow
The proces
s of generating computer representations of three-dimensional structures has been pretty thoroughly worked out over the past fifteen years. Several books on computer graphics describe the necessary steps and commercial graphic software has been available for some time. Recently, three-dimensional graphic software has been made available even to those using microcomputers for personal or recreational purposes.
The software necessary for producing representations of simple shapes is not terribly complicated. In this article, I will try to lay out a few fundamental algorithms that can form the core of a three-dimensional graphics package. However, in order to make sense of these algorithms, considerable explanation will be necessary.
To generate an image of a three-dimensional shape, we have to have a computer-readable representation of the shape. (I will describe a couple of ways to represent shapes.) Then the data for the shape must be transformed to conform to the view of the shape that would be see
n from a given point. The data must then be further transformed to fit the shape to the limits of a display surface (video display or plotter). Finally, those parts of the shape that are hidden from view, either because they exceed the limits of the display or because they are hidden by other parts of the shape, must be eliminated.
Getting the Data
The first decision to be made when generating three-dimensional data for input to a graphics system is which coordinate system to use. A right-handed Cartesian system is most often used. Standing at the origin of such a system, the
x
axis would go to the right, the
y
axis straight ahead, and the
z
axis straight up. If we think in terms of a small area of the earth,
x
would measure longitude (east positive, west negative),
y
latitude, and
z
altitude.
Points in this space can be defined as a trio of numbers giving
x
,
y
, and
z
coordinates. A three-dimensiona
l drawing of an object can then be considered a set of lines connecting points in space. An object can be described by listing all its points in the order in which we would draw them. We can then draw the object by "following the dots."
However, we rarely see drawings that are made without ever lifting pencil from paper, so we should add an indicator wherever we move to a point without drawing a line. Thus one format for describing objects consists of a list of sets of numbers. Each set contains three numbers describing a position in space and a command to draw a line to that position or just move to that position without drawing a line, a total of three numbers and a character. An example of this format can be seen in
figure 1a
, with the associated data given in
table 1a
. The Pascal procedures given in
listing 1
read and display objects defined in this format.
This format is fine if we just want to make drawings of objects that appear to be c
onstructed of straight pieces of wire. To represent a solid object, we have to define a surface enclosing the object and therefore need another format. Surfaces are most easily represented if we define them as sets of faces, or polygons.
To define objects made of polygons, we must list the polygons individually. This can be done by listing the coordinates of each vertex (point) of the polygon in clockwise order (as seen from outside the object) around the periphery of the polygon. It is important that all polygons be described consistently since the clockwise order is useful for calculations determining which side of a polygon is facing the viewer.
A solid object is customarily defined as a group of adjoining polygons. Since neighboring polygons share vertices along common borders, objects can be more compactly defined by first listing all the vertices belonging to the object and then listing polygons by the numbers of the vertices they use. An example of this sort of format is seen in
figure lb
, with data in
table lb
. The procedures in
listing 2
read and display objects as a set of polygons.
Now that we know how to read and display objects, where do we get the data describing the objects? The simplest way is to dream it up. After all, much of the joy of computer graphics lies in creating imaginary worlds. Take a piece of graph paper and draw front and side views of an object you'd like to represent. Then measure the vertices of the object by counting squares from some point of origin on the paper. The front view will give you the
x
and
z
coordinates, and the side view will give you the
y
coordinate (
see figure 2
).
People who are involved in creating three-dimensional graphics generally build software to aid in designing objects. For example, a program to generate surfaces of revolution is relatively easy to write. Then shapes such as wine glasses and vases are easy to make. A surface of revol
ution can be defined by a sequence of points following a path up one side of the surface. The points then sweep out a surface by rotating about a central axis. Surfaces of revolution are widely used in computer imagery.
More advanced techniques make use of high-speed interactive graphics terminals (costing $20,000 to $150,000) in conjunction with elaborate software to define and modify shapes. See the papers by Crow and Parent (listed among the suggested readings
at the end of this article) for examples of this approach to data gathering.
Defining a View of Some Objects
Once data describing an object is available, it is time to figure out how to look at it. In the real world, when we look at an object, what we see is determined by our viewpoint and the position of the object. How can we emulate this in an imaginary world?
We want the choice of viewing an object from any viewpoint. Therefore we must have an algorithm that will move the vertices of the object to the prope
r position, given a particular viewpoint. The input to this algorithm consists of two points in space: the position from which we are looking and the position at which we are looking. I will refer to these as the
eyepoint
and the
center of interest
, respectively.
In order to understand how such an algorithm works, we need to know more about how to move objects about in an imaginary world. So far I have defined an object within its own space or frame of reference. Now we would like to arrange a number of objects in a scene, each in a different position and orientation.
Changing the position of an object is relatively simple. Using the longitude, latitude, altitude model of space, we can move an object east by simply adding some positive number to the
x
coordinates of all its vertices. To move an object north, we add some positive number to all its
y
coordinates. To move an object up or down, we change all its
z
coordinates. This process is called
trans
lation
.
Similarly, to change the size of an object we multiply all its coordinates by the same number. This is called
scaling
. To make an object twice as large in every dimension, we multiply all coordinates of every vertex by two. Thus, changing the position or size of an object is relatively straightforward. Rotating an object or combining successive operations, however, requires more sophisticated techniques.
Objects can be moved about quite elegantly using techniques provided by matrix algebra. We devise a sort of template that is filled in to provide the operation desired. Filled templates, called
transformation matrices
, can then be combined to provide complicated operations.
A template, or
matrix
, consists of sixteen positions (four rows by four columns). Numbers loaded into a matrix are combined with vertex coordinates to yield updated coordinates by matrix multiplication. The first column of the matrix affects only the
x
coordinate and therefore
contains all the numbers that define the updated
x
coordinate. The second column treats the
y
coordinate similarly, and the third column handles the
z
coordinate. The fourth column is for completeness, to make things more elegant. It also allows us to pull some fancy tricks such as finding the inverse of a transformation. I won't use the fourth column in this article, however.
A vertex is "transformed" by the matrix as follows: To get the new
x
coordinate, the old
x
coordinate is multiplied by the top number in the first column, then added to the product of the old
y
coordinate and the second number in the first column. The sum is then added to the product of the old
z
coordinate and the third number in the first column. Finally, the whole thing is added to the bottom number in the first column. The new
y
coordinate can be obtained by combining the second column and the old vertex coordinates in the same way. Similarly, the new
z
coordinate is produced using the third column. The Pascal procedure in
listing 3
transforms a vertex.
Under the rules stated above, the bottom row of the matrix holds numbers that translate the object. A number at the bottom of the first column is added to all
x
coordinates to move an object east or west. Similarly, numbers at the bottom of the second and third columns affect the
y
and
z
coordinates. To scale objects, we enter the scaling factor along the top-left-to-bottom-right diagonal of the matrix. The top-left number in the matrix is multiplied by the old
x
coordinate to yield the new
x
coordinate. Similarly, the second number in the second column multiplies the
y
coordinate and the third number in the third column multiplies the
z
coordinate.
Rather than trying to explain rotations in the limited space here, I will simply illustrate how to fill in the matrix. Trying a few examples by hand should convince
you that rotations work. Simple rotations are those that rotate an object about one of the axes of our space. For instance, to rotate an object about the
z
axis by an angle A, use the following matrix:
cos(A) sin(A) 0 0
-sin(A) cos(A) 0 0
0 0 1 0
0 0 0 1
Note that this matrix leaves the
z
coordinate unchanged, which is what we would expect from a rotation about the
z
axis. Furthermore, a rotation through a zero angle leaves everything unchanged since the cosine of zero is 1 and the sine of zero is 0.
I always use the convention that a positive rotation occurs in a counterclockwise direction looking in the negative direction along the axis about which you are rotating. This means that if the thumb of your right hand is pointed in the same direction as that axis, your fingers will curl in the direction of positive rotation. Keeping
track of such things requires a
strong sense for visualizing space. When in doubt, I sketch things with pencil and paper.
To rotate about the
x
axis, use the following matrix:
1 0 0 0
0 cos(A) sin(A) 0
0 -sin(A) cos(A) 0
0 0 0 1
To rotate about the
y
axis, use the following matrix:
cos(A) 0 -sin(A) 0
0 1 0 0
sin(A) 0 cos(A) 0
0 0 0 1
Combining these fundamental rotations results in even more interesting rotations.
Note that all transformations occur relative to the origin of the given space. Thus, to rotate or scale an object without changing its position, we must first be sure that it is centered on the origin. Therefore, a rotation or scaling "in place" (ie: without changing position) requires a translation to center on the origin, followed by rotation or scaling, then a second translation ba
ck to the original position.
Once all the objects in a scene have been transformed to the desired positions and orientations, a view from a given eyepoint in the direction of the object of interest is simulated by an additional transformation that places the object in the desired position and orientation. This simulation can be achieved by combining a few rotation matrices.
In the first step, we move everything so that the eyepoint lies at the origin of the space and the center of interest lies on the
y
axis, or due north. To do this, we translate the eyepoint to the origin and apply the same matrix to all the other data. The translation matrix is as follows:
1 0 0 0
0 1 0 0
0 0 1 0
-Eye.X -Eye.Y -Eye.Z 1
where Eye.X, Eye.Y, and Eye.Z are the
x
,
y
, and
z
coordinates of the eyepoint.
A rotation about the
z
axis can now be used to move
the center of interest in a northerly direction. In particular, we move the center of interest into the plane defined by the
y
and
z
axes. The angle of rotation is found by passing the center of interest through the eyepoint translation matrix defined above and then applying the following formulas:
cos(A) = C1.Y/ sqrt((C1.X)2 + (C1.Y)2)
sin(A) = C1.X/ sqrt((C1.X)2 + (C1.Y)2)
where A is the angle of rotation and C1.X and C1.Y are the
x
and
y
coordinates of the translated center of interest, respectively (
see figure 3
).
The process of moving the center of interest onto the
y
axis is completed by rotating the object about the
x
axis, using the following formulas:
cos(A) = C2.Y/ sqrt((C2.Y)2 + (C2.Z)2)
sin(A) = -C2.Z/ sqrt((C2.Y)2 + (C2.Z)2)
where C2.Y and C2.Z are, respectively, the
y
and
z
coordinates of the
translated and rotated center of interest (
see figure 4
).
Because all this is done with the intention of displaying the resulting coordinates on a flat surface, one more transformation is called for. It is useful to think about the display surface (video display, plotter, etc) as a space in which the
x
axis measures width, the
y
axis height, and the
z
axis depth. We can place our transformed coordinates into this space by interchanging the
y
and
z
axes, using the following matrix:
1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
Given coordinates for an eyepoint and a center of interest, we can use the matrix multiply procedure to combine the above operations into a single orientation for displaying a view of the scene. The procedure in
listing 4
builds such a matrix. We refer to the resulting arrangement of a scene as the
eyespace
.
Clipping
Once all the data in the scene is transformed to the eyespace, we must decide how much of the scene fits on the display. The display can be thought of as a window into an imaginary world. Things such as the size of the window and our distance from it determine what can and cannot be seen: We can use the edges of the window and the origin of the space (ie: the eyepoint) to define planes that clip parts of polygons not visible through the window (
see figure 5
).
The clipping window defines the
field of vision
in much the same way that the film gate and lens in a camera limit the field captured by the film. The window can be defined as a polygon corresponding to the boundaries of the display as we expect to view it. For example, if we are in the habit of looking at a 12-inch video display from a distance of 16 inches or so, the clipping window should be a rectangle about 6 inches high and 8 inches across, located 16 inches from the eyepoint.
The first
step of the clipping process is to define the planes to be clipped against. Planes can be defined by four numbers, the coefficients of an equation of the following form:
A * x
+
B * y
+
C * z
+ D = 0
We can simplify this equation somewhat since all the planes we are interested in pass through the origin. For all planes passing through the origin, the fourth coefficient,
D
, equals zero.
Our window can then be characterized by a sequence of sets of three numbers, each set describing one plane.
Listing 5
produces the coefficients of the plane equations needed for clipping. Input is assumed to be a polygon. Each clipping plane is determined by three points: the eyepoint and the two endpoints of an edge from the input polygon. This assumes that polygon vertices are taken clockwise as seen from the eyepoint and that a "lefthanded" (width, height, depth) eyespace is used.
Once we have the clipping-plane coefficients, th
ey can be applied to all the vertices of a polygon to find out which lie inside and which lie outside the field of view. The clipping coefficients are applied to a vertex using the following formula in Pascal style:
Distance : = Vtx.X * Clp.X + Vtx.Y * Clp.Y + Vtx.Z * Clp.Z
This operation (known as a vector
dot product
) yields a distance measure that tells us how far inside or outside the viewable area the vertices lie. Negative numbers indicate that a vertex lies outside, positive numbers that a vertex lies inside. If distances for all clipping planes applied to all vertices of a polygon are positive, it is completely visible. If distances for all vertices and any of the clipping planes are negative, the polygon is entirely outside the window and thus not visible (assuming the clipping window is convex). If some distances are positive and some are negative, we may have to cut the polygon into inside and outside portions.
The procedure in
listing 6
takes a polygon and clips it by a set of plane coefficients stored in a second polygon array. Each plane is tested in turn against each polygon vertex. Vertices lying inside (on the positive side of) a plane are copied to a temporary polygon array. Where two adjacent vertices are found to lie on opposite sides of a plane (ie: D1 X D2
<
0.0, meaning the signs of the distances are different), the intersection point of the clipping plane and the edge connecting the two vertices is copied to the temporary array. When all the vertices of the polygon have been clipped against one plane, the temporary array is copied back into the input array and clipped against the next plane. This process eliminates parts of polygons lying outside an unbounded pyramid emanating from the eyepoint and delimited by the window polygon.
Displaying
Any polygon found to lie within the field of vision must be displayed. An additional transform is necessary to take the coordinates of the eyespace to the coordinate
s used by the display device, the "screen space." Furthermore, a division is necessary to achieve the appearance of
perspective (ie: objects in the distance should be smaller). This transform can take the form of a scaling matrix as follows:
Scale.X : = DotsAcross * WinDist/WinWidth
Scale.Y : = DotsDown * (4/3) * WinDist/WinWidth
The matrix is then:
Scale.X 0 0 0
0 Scale.Y 0 0
0 0 1 0
Middl.X Middl.Y 0 1
In the above transform, DotsAcross is the number of dots across the display, DotsDown the number of lines on the display from top to bottom, WinDist the distance to the window in eyespace, WinWidth the width of the window, and Middl.X and Middl.Y are the
x
and
y
coordinates of the middle of the display (in screen space, usually DotsAcross /2 and DotsDown/2). The factor (4/3) takes into account that the standard video display is 4
/3 as wide as it is high (the
aspect ratio
). It is assumed that the window has the same proportions as the display.
Nonrectangular windows require a more careful calculation. If the maximum width of the window is less than 4/3 times the maximum height, another number must be substituted for the window width in the above calculations. That number should be the maximum of the window width and 4/3 times the window height. Of course, if we use a display with a different aspect ratio, the width of the display divided by its height should replace the 4/3.
The procedure in
listing 7
divides the
x
and
y
coordinates of each vertex by its
z
coordinate to achieve the perspective effect, then applies the transformation to display coordinates directly, rather than using a matrix transformation.
This completes the process of computing an image of objects with all data shown, as though the objects were made of pieces of straight wire. Next, we look at ho
w to achieve the appearance of solid objects capable of hiding each other.
Hidden Faces
There are two methods that allow solid objects to hide parts of themselves or other objects. The first uses the plane equation of each polygon to determine whether or not it lies on the far side of its object. If it does, the polygon is clearly hidden by closer parts of the object. The second uses a clipping procedure similar to the one described earlier to remove parts of faces that are hidden by closer faces.
In everything that follows, polygons are assumed to be convex. Restricting things in this way simplifies the task considerably at a very small increase in the cost of preparing object descriptions.
Earlier in the article, I stressed the importance of taking the vertices of all polygons in a consistent order, usually clockwise as seen from outside the object. Many objects are closed surfaces, meaning that the inside of the object can be seen only by passing through the surface. In
fact, if we choose to do so, we can construct all objects as closed surfaces for display purposes.
In any event, if a polygon appears on the screen with its vertices in counterclockwise order, we must be seeing it from the inside. If we are looking at a closed surface from the inside, some other part of the surface must lie between us and the polygon in question. Therefore, when making pictures of solid objects made of closed surfaces, we can immediately reject any polygons appearing in counterclockwise order.
Earlier we used planes for clipping by evaluating the positive or negative distance from a point to the plane. Similarly, when the eyepoint lies on the positive side of the plane of a polygon, the vertices of that polygon appear in clockwise order. When on the negative side, they appear in counterclockwise order. Some of the procedures developed earlier can be used to determine whether or not a polygon "faces the eyepoint."
Three of the vertices of the polygon define a plane. Here we can
use the procedure developed earlier for finding a plane defined by two window vertices and the eyepoint. Use the three points to define two lines. If the two lines are treated as direction vectors (subtract one endpoint from the other), the two vectors can be passed to the procedure, which then returns coefficients for a plane parallel to the polygon and passing through the origin. These coefficients, when used in a dot product with one vertex of the polygon, yield a number that tells us on which side of the polygon the eye lies. The
function in listing 8
does the job.
If a closed convex surface is being displayed by itself, the above process is adequate to produce the image with only visible faces shown. However, if the surface is not convex, or there is more than one object involved, further procedures are necessary.
Those polygons surviving the clipping procedure and the "eye-facing" test can be sorted by their distance from the eyepoint. We base the sort on the average of the
z
coordinates of each polygon in turn. If all polygons are roughly the same size, no two polygons intersect each other, and no two polygons lie close to each other in nearly parallel planes, the sort order will allow us to eliminate hidden parts of polygons. Most scenes involving separated, reasonably simple objects will conform to the above conditions.
Since the polygons must be transformed, clipped, and tested for "eye-facing" one by one, it makes sense to use an insertion sort to order the polygons displayed. A list of polygons to be displayed is built by inserting each new polygon description (number of vertices and position in vertex array) in the already sorted list of previous polygons. A binary search can be used to reduce the search time for finding the insertion point. The
procedure in listing 9
, implements a binary insertion sort. Note that polygon vertices are stored in an array in contiguous groups. The
z
coordinate of the first element of the group is us
ed to hold the average
z
coordinate of the polygon for subsequent tests.
Sorting is a major part of nearly all hidden-line and hidden-surface algorithms. For a thorough discussion of sorting and other aspects of hidden-surface algorithms, see the paper by Sutherland and others listed in the suggested readings. Also see the third volume of Donald E Knuth's
The Art of Computer Programming
for a thorough treatment of sorting in general.
Once the polygons are sorted, we can apply a clipping algorithm in a reversed sense. We will remove any parts of polygons lying inside a closer polygon as seen on the display (
see listing 10
). Starting with the closest polygon and working outward, each polygon will be clipped by all its predecessors. Remember, keeping things simple will require that polygons be convex. (Nonconvex polygons can always be broken into a set of convex ones.)
In order to use a polygon for clipping, its edges must be converted to clipping planes. Ther
efore, once any part of a polygon is determined to be visible, the entire polygon is subsequently converted to plane coefficients using the same procedure used earlier to convert the window description for clipping.
Since each polygon edge, once clipped, can be displayed without further treatment, it is easiest to clip each edge individually. This process is not as straightforward as it may seem. A polygon may clip an edge into two parts, each of which must then be subsequently clipped by the remaining polygons. Of course, any of the later polygons may further divide one of the edge fragments. This sort of situation is best handled using recursion. Therefore, the procedure given in listing 10 recursively clips a polygon by all closer polygons and flags visible polygons for use in subsequent clipping. Hidden polygons obviously need not be used to clip more distant polygons.
Conclusion
The preceding procedures provide essentially everything needed to display three-dimensional line
drawings representing solid objects modeled by polygons. An effort has been made to make the procedures concise. This has been done at the expense of efficiency and sometimes, perhaps, even at the expense of clarity. I have assumed the availability of a display of some kind that can be used to draw lines. Most systems capable of full graphics provide software for generating lines.
In the interests of completeness, Part 2 will present a complete program incorporating the procedures described above. I have been able to use it, somewhat crudely, with a semigraphic terminal (Zenith H-19) and the UCSD Pascal system (
see photo 2
) and, more satisfyingly, with a 500-line raster display and a Pascal interpreter running under the UNIX operating system (see
photo 1
,
photo 3
, and
photo 4
).
If you have a serious interest in three-dimensional graphics, a full understanding of what has been presented here is heartily recommended. In a
ddition, you should consult the suggested readings listed below for more material. Many people have spent time on the problems discussed in this article and have published useful articles describing other ways to produce computer-generated three-dimensional images.
In addition to line drawing images, much computer graphics is now displayed using the features offered by raster displays. Quite realistic imagery is possible, offering a vast array of possibilities well beyond those described here. There is much work to be done in this area yet, so if you are interested, go to it!
Acknowledgments
Mary Lieb handled text-editing and formatting chores. Some of the software development and all the higher-resolution computer-generated images were done on equipment supplied in part by the National Science Foundation (equipment grant # MCS 80-06322) and in part by the Ohio State University.
Suggested Reading
Newman, W and R Sproull
,
Principles of Interactive Computer Graphics
Rogers, D F and J A Adams
,
An Introduction to Computer Graphics
Gilol, W K
,
Interactive Computer Graphics
, Prentice-Hall, 1978. An introductory textbook with a somewhat different approach than that of the two books above.
Knuth, D E
,
The Art of Computer Programming: Volume 3, Sorting and Searching
, Addison Wesley, 1973. A treasure trove of algorithms and analyses of algorithms--a very important book.
Sutherland, I E, et al
,
"A Characterization of Ten Hidden-Surface Algorithms,"
ACM Com
puting Surveys, March 1974. A very informative explanation of the extant hidden-surface algorithms of the time. Computing Surveys is available in most technical libraries.
Crow, F C
,
"A System for the Design of Three-Dimensional Objects,"
Proceedings of the ACM National Conference, 1977 A system for designing three-dimensional shapes involving simple curved surfaces, available from the Association for Computing Machinery, 1133 Avenue of the Americas, New York NY 10036.
Parent, R
,
"Three-Dimensional Object Synthesis,"
Proceedings of SIGGRAPH '76, 1976. A more comprehensive system for building three-dimensional objects. See also the proceedings of the annual SIGGRAPH conferences for the last five years or so, which contain papers describing most of the interesting work done in recent years-the best way to keep up with what's going on. Available from the Association for Computing Machinery, listed above.
Data for an object defined as a set of lines (table 1a) and for an
object defined as a set of polygons (table 1b). In table 1a, the "m"
and "d" in the first column mean "move to" or draw to" the point
with
x
,
y
, and
z
coordinates as given in the next three columns,
respectively.
In table 1b, the firstline gives the number of points (10) and
polygons (7) in the shape. The next 10 lines give the point
number (1 thru 10) and the
x
,
y
, and
z
coordinates of the point.
The last seven rows describe the seven polygons: the first number
gives the number of points making up that polygon, and the rest of
the numbers on that line give the point numbers (as described by
the point description lines) that make up the polygon. Both tables
1a and 1b describe the shape shown in figure 1b.
1a
M 1.0 -1.0 -1.0
d -1.0 -1.0 -1.0
d -1.0 -1.0
.00
d -.00 -1.0 1.0
d 1.0 -1.0 1.0
d 1.0 1.0 1.0
d 1.0 1.0 -1.0
d 1.0 -1.0 -1.0
d 1.0 -1.0 1.0
M -1.0 -1.0 .00
d -1.0 -.00 1.0
d -1.0 1.0 1.0
d -1.0 1.0 -1.0
d -1.0 -1.0 -1.0
M -1.0 -.00 1.0
d -.00 -1.0 1.0
M -1.0 1.0 -1.0
d 1.0 1.0 -1.0
M 1.0 1.0 1.0
d -1.0 1.0 1.0
1b
10 7 (NumPts NumPolys)
1 1.0 -1.0 -1.0
2 -1.0 -1.0 -1.0
3 -1.0 -1.0 .00
4 -.00 -1.0 1.0
5 1.
0 -1.0 1.0
6 -1.0 -.00 1.0
7 -1.0 1.0 -1.0
8 1.0 1.0 -1.0
9 1.0 1.0 1.0
10 -1.0 1.0 1.0
5 1 2 3 4 5
4 8 1 5 9
4 7 8 9 10
5 2 7 10 6 3
4 8 7 2 1
5 5 4 6 10 9
3 3 6 4
Pascal procedure to read data describing a three-
dimensional object and display it as a collection
of straight lines.
type Point = record X,Y,Z : real; Draw : boolean; end;
var Points : array [1..Maxpts] of Point;
I, NumPts : integer;
procedure ReadObject( FileName : string);
var I, NumPts : integer;
Cmd : char ;
begin
reset(ObjFile,FileName); (* open input file *)
readln( 0bjFile , NumPts); (* get number of points *)
for I:=l to NumPts d
o
with Points[I] do
begin
readln(ObjFile,Cmd,X,Y,Z);
if cmd = 'd' then Draw := true else Draw := false
end;
close( ObjFile);
end;
procedure DrawObject;
var TmpPt : Point;
begin
Start; (* initialize display *)
for I:=1 to NumPts do
begin
Transform(Points[I], TmpPt); (* transform to display *)
with TmpPt[I] do
if Draw then Drawto(X,Y); (* draw to next pt *)
else Moveto(X,Y); (* move to next pt *)
end;
Finish; (* close-out display *)
end;
Procedure to display a three-dimensional object with surfaces defined
as polygons.
type Point = record X,Y,Z : real end;
Polygon = record Start,Polyvtces : integer end;
var Points : array [1..MaxPts] of Point;
Polygons
: array [1..Maxpols] of Polygon,
Vertices : array [11..MaxVtces] of integer;
NumPts,NumVtces,I,J : integer;
procedure ReadObject( FileName : string );
begin
reset(ObjFile,FileName); (* open input file *)
readln(ObjFile,NumPts,NumPolys);
for I:=1 to NumPts do (* read in points *)
with Points[l] do
readln(ObjFile,J,X,Y,Z);
NumVtces :=0; (* initialize size of vertex array *)
for I:=1 to NumPolys do (* read in polygon descriptions *)
with Polygons[I] do
begin
Start := NumVtces; (* start point in vertex array *)
read(ObjFile,Polyvtces); (* number of vertices *)
for J:=1 to Polyvtces do (* read vertex pointers *)
read( ObjFile,Vertices(NumVtces+J]);
readln (* go to next line of input *)
NumVtces := NumVtces + PolyVtce
s;
end;
end (* ReadObject *)
procedure DisplayObject;
var TmpPt : Point;
begin
for I:=1 to NumPolys do
with Polygons[I] do
begin
Transform(Points[Vertices[Start+PolyVtces]],TmpPt);
with TmpPt do Moveto(X,Y);
for J:=1 to PolyVtces do
begin
Transform(Points[Vertices[Start+J]],TmpPt);
with TmpPt do Drawto(X,Y);
end;
end;
end; (* Displayobject *)
This procedure will transform the vertices of a polygon using a
four-by-four matrix.
var Mt : array [1..4,1..4] of real;
procedure Transform( Pt : Point; var Newpt : Point );
begin
NewPt.X := Pt.X*Mt[1,1] + Pt.Y*Mt[1,2] + Pt.Z*Mt[1,3] + Mt[1,4];
NewPt.Y := Pt.X*Mt[2,l] + Pt.Y*Mt[2,2] + Pt.Z*Mt[2,3] + Mt
[2,4];
NewPt.Z := Pt.Z*Mt[3,l] + Pt.Y*Mt[3,2) + Pt.Z*Mt[3,3] + Mt[3,4];
end;
Distance and viewing angle transforms are determined by this
procedure, which uilds a transformation matrix based on the
relationship between the coordinates of the eyepoint and those of the
center of interest.
procedure GetEyespace( EyePt,CntrInt : Point );
var Mtx : Matrix;
C1,C2 : Point;
Hypotenuse,CosA,SinA : real;
procedure Ident( var Mtx : Matrix ); (* initialize matrix *)
var I,J : counter;
begin
for I:=1 to 4 do
for J:=1 to 4 do
if I = J then Mtx[I,J] :=1.0 else Mtx[I,J] :=0.0;
end; (* Ident *)
procedure MatrixMult( Mt1,Mt2 : Matrix; var Result : Matrix );
var I,J,K : counter;
begin
for I:=1 to 4 do
for J:=1 to 4 do
begin
Result[I,J] := 0.0;
for K:=1 to 4 do
R
esult[I,J] := Result[I,J] + Mt1[K,J]*Mt2[I,K];
end;
end; (* MatrixMult *)
procedure Transform( Pt : Point; Mtx : Matrix; var NewPt : Point );
begin
NewPt.X := Pt.X*Mtx[1,1] + Pt.Y*Mtx[1,2] + Pt.Z*Mtx[l,3] + Mtx[l,4];
Newpt.Y := Pt.X*Mtx[2,1] + Pt.Y*Mtx[2,2] + Pt.Z*Mtx[2,3] + Mtx[2,4];
Newpt.Z := Pt.X*Mtx[3,l) + Pt.Y*Mtx[3,2) + Pt.Z*Mtx[3,3] + Mtx[3,4];
end; (* Transform *)
begin (* Eyespace Procedure body *)
Ident(EyeSpace);
with EyePt do (* load eyepoint translation *)
begin Eyespace[1,4]:=-X; Eyespace[2,4]:=-Y; Eyespace[3,4]:=-Z; end;
Transform( CntrInt,EyeSpace,C1 ); (* translate ctr. of interest *)
Ident(Mtx); (* load rotation about Z axis *)
with C1 do Hypotenuse := sqrt( X*X + Y*Y );
if Hypotenuse 0.0 then
begin
CosA := C1.Y / Hypotenuse; SinA := C2.X / Hypotenuse;
Mtx[1,1] := CosA;
Mtx[2,1] := SinA;
Mtx[1,2] := -SinA; Mtx[2,2] := CosA;
MatrixMult( Eyespace , Mtx, Eyespace );
end:
Transform( CntrInt,Eyespace,C2 ); (* rotate ctr. of interest *)
Ident(Mtx); (* load rotation about Z axis *)
with C2 do Hypotenuse := sqrt( Y*Y + Z*Z );
if Hypotenuse 0.0 then
begin
CosA := C2.Y I Hypotenuse; SinA := -C2.Z I Hypotenuse;
Mtx[2,2] := CosA; Mtx[3,2] := SinA;
Mtx[2,3) := CosA; Mtx[3,3] := CosA;
MatrixMult( Eyespace,Mtx,Eyespace );
end;
Ident( Mtx ); (* load switch between Y and Z axes *)
Mtx[2,2] := 0.0; Mtx[3,3] := 0.0;
Mtx[2,3] := 1.0; Mtx[3,2] := 1.0;
MatrixMult( Eyespace , Mtx, EyeSpace );
end; (* GetEyespace *)
The field of vision for a three-dimensional display is bounded by
"clipping planes," the coefficients of which are calculated in
this
procedure.
type OnePoly = array [1..MaxSides] of Point;
procedure GetPlanes( var Poly : OnePoly; NumPts : integer );
var I,LstI : integer;
TmpPoly : OnePoly;
begin (* get plane equation coefficients for polygon edges *)
LstI : = NumPts; (* leading vertex of the edge *)
for I:=1 to NumPts do
begin
with Poly[I] do
begin (* vector cross-product using edge endpoints *)
TmpPoly[I].X := Y * Poly[LstI].Z - Z * Poly[LstI).Y;
TmpPoly[I].Y := Z * Poly[LstI].X - X * Poly[LstI].Z;
TmpPoly[I].Z := X * Poly[LstI].Y - Y * Poly[LstI].X;
end;
LstI := I;
end; (* for Loop *)
for I:=1 to NumPts do (* copy back to input polygon *)
with TmpPoly[I] do
begin Poly[I].X := X, Poly[I].Y := Y, Poly[I].Z := Z; end;
end; (* Getplanes *)
Procedure to determine if any vertices of a polygon lie outside
previously defined clipping planes; if this is so, the polygon
is modified accordingly.
var Window : OnePoly (* clipping window *)
WindowSize : integer; (* number of edges in clip window *)
function DotProd( Pt1,Pt2 : Point ) : real;
begin (* vector dot-product *)
DotProd := Pt1.X * Pt2.X + Pt1.Y * Pt2.Y + Pt1.Z * Pt2.Z;
end; (* DotProd *)
procedure ClipIn(var Poly : OnePoly; var NumPts : counter);
var I,J,LstJ,TmpPts : counter;
D1,D2,A : real;
TmpPoly : OnePoly;
begin
for I:=1 to WindowSize do (* for each window edge *)
if NumPts 0 then
begin
D1 := DotProd( Poly[NumPts],Window[I] );
LstJ := NumPts;
TmpPts := 0;
for J:=1 to NumPts do (* f
or each polygon edge *)
begin
if D1 0.0 then (* is leading vertex inside? *)
begin
TmpPts := TmpPts + 1;
with TmpPoly[TmpPoints] do
begin (* copy leading vertex *)
X:=Poly[LstJ].X; Y:=Poly[LstJ].Y; Z:=Poly[LstJ].Z;
end;
end; (* if leading vertex inside *)
D2 := DotProd( Poly[J],Window[I] );
if D1 * D2 0.0 then (* does edge straddle window? *)
begin
A := D1 / (D1 - D2);
TmpPts := TmpPts + 1;
with TmpPoly[TmpPts] do
begin
X := A * Poly[J].X + (1.0 - A) * Poly[LstJ].X;
Y := A * Poly[J].Y + (1.0 - A) * Poly[LstJ].Y;
Z := A * Poly[J].Z + (1.0 - A) * Poly[Ls
tJ].Z;
end;
end;
LstJ := J;
D1 := D2;
end; (* NumPts loop *)
for J:=1 to TmpPts do (* copy polygon back to input *)
with TmpPoly[J] do
begin Poly[J].X:=X; Poly[J].Y:=Y; Poly[J].Z:=Z; end;
NumPts := TmpPts;
end; (* WindowSize loop *)
end; (* ClipIn *)
This procedure achieves a perspective effect by dividing the
x
and
y
coordinates of each vertex by the z coordinate.
procedure MakeDisplayable( var Pt : Point );
begin
Pt.X := Scale.X * Pt.X / Pt.Z + Middl.X;
Pt.Y := Scale.Y * Pt.Y I Pt.z + Middl.Y;
end;
This Pascal function determines whether or not a
polygon will be hidden by another par
t of the same
surface in a three-dimensional display.
function FacesEye( Poly : OnePoly ) : boolean;
var TmpPt : Point;
TmpPoly : OnePoly;
begin
with Poly[2] do (* make copy of second Vertex *)
begin TmpPt.X:=X; TmpPt.Y:=Y; TmpPt.Z:=Z; end;
(* directed vector from second to *)
(* first vertex *)
TmpPoly[1].X := Poly[1].X - Poly[2].X;
TmpPoly[1].Y := Poly[1].Y - Poly[2].Y;
TmpPoly[1].Z := Poly[1].Z - Poly[2].Z;
(* directed vector from second to *)
(* third vertex *)
TmpPoly[2].X := Poly[3].X - Poly[2].X;
TmpPoly[2].Y := Poly[3].Y - Poly[2].Y;
TmpPoly[2].Z := Poly[3].Z - Poly[2].Z;
GetPlanes( TmpPoly,2 ); (* get plane coefficients *)
if Dotprod( TmpPt,TmpPoly[1] ) = 0.0
then FacesEye := false
else FacesEye := true;
end; (* FacesEye *)
Based on the average value of their z coordinates,
polygons are sorted by their distance from the eyepoint in this
binary insertion sort procedure.
var OutVtces : array (1..MaxVtces] of Point;
OutPolys : array [1..MaxPolys] of Polygon;
NumDisplay,NumVtxOut : integer; (* # polygons, # vertices *)
procedure InsertSort( Poly : OnePoly ; NumPts : integer );
var I,J,K : integer;
AvDepth : real;
begin (* binary-insertion sort on average *)
(* depth *)
AvDepth := 0.0;
for I:=1 to NumPts do
with Poly[I] do (* store vertices and find average *)
(* depth *)
begin
OutVtces[NumVtxOut + I + 1].x := X;
OutVtces[NumVtxOut + I + 1].
Y := Y;
OutVtces[NumVtxOut + I + 1].z := Z;
AvDepth := AvDepth + Z; (* sum depths *)
end;
AvDepth := AvDepth / NumPts; (* divide for average *)
OutVtces(NumVtxOut + 1].Z := AvDepth; (* store for later *)
J := 0; (* initialize for insertion search *)
I := (NumDisplay +1) div 2;
K := NumDisplay;
while (J I) do (* binary search for insertion point *)
if AvDepth OutVtces[OutPolys[I].Start] .Z
then begin K := I; I := ( I + J ) div 2; end
else begin J := I; I := ( I + K + 1 ) div 2; end
for J:=NumDisplay downto I+1 do (* found it, now insert *)
begin (* sove everything above insertion *)
(* point up one*)
OutPolys[J + 1].Start := OutPolys[J].Start;
OutPolys[J + 1].NumVtX := OutPolys[J].NumVtx;
end;
OutPolys[I + 1].Start := NumVtxOut +
1; (* store new entry *)
Outpolys[I + 1].NumVtx := NumPts;
NumVtxOut : = NumVtxOut + NumPts + 1; (* vertex count *)
NumDisplay := NumDisplay + 1; (* polygons stored *)
end; (* InsertSort *)
Once sorted, polygons are checked to determine if a
polygon closer to the eyepoint hides all or part of
one that is farther away.
procedure Clipout( Poly : OnePoly; var NumPts : integer; Place : integer );
var I,LstI,NumDrawn : integer;
Pt1,Pt2 : Point;
Drawn : boolean;
procedure clipAfter( Index : integer; Pt1,Pt2 : Point );
var I,J : integer;
D1,D2,A : real;
Out : boolean;
Pt3 : Point;
begin (* recursively check polygons for *)
(* overlap with input edge *)
if Index Place (* is polygon closer than edge in*)
(* sorted list? *)
then with OutPolys[Index] do
begin
I := Start + NumVtx; (* pick up last edge first *)
Out := false;
repeat (* for each polygon edge *)
D1 := DotProd( Pt1,OutVtces[I] ); (* distance to first point *)
D2 := DotProd( Pt2,OutVtces[I] ); (* distance to 2nd point *)
if ( D1 = 0.0 ) and ( D2 = 0.0 )
then begin (* both points visible *)
Out := true;
ClipAfter( Index + I,Pt1,Pt2 ); (* try next one *)
end
else if D1 * D2 0.0
then begin (* one point visible *)
A := D1 / (D1 - D2); (* get clipped point *)
Pt3.x := A * Pt2.x + ( 1.0 - A ) * Pt1.X;
Pt3.Y := A * Pt2.Y + ( 1.0 - A ) * Pt1.Y;
Pt3.Z := A * Pt2.Z + ( 1.0 - A ) * Pt1.Z;
if D1 0.0
then begin (* Pt1 visible, try next one *)
ClipAfter( Index+1,Pt1,Pt3 );
with Pt3 do (* go on with hidden part *)
begin Pt1.X:=X; Pt1.Y:=Y; Pt2.Z:=Z; end;
end
else begin (* Pt2 visible, try next one *)
ClipAfter( Index + 1,Pt3,Pt2 );
with Pt3 do (* go on with hidden part *)
begin Pt2.X:=; Pt2.Y:=Y; Pt2.Z:=Z; end;
end;
end; (* one point visible *)
I := I - 1; (* count down for next edge *)
until Out or ( I = Start ); (* all visible or edges exhausted *)
end
else begin (* reached end of list of closer
(* polygons, display *)
M
akeDisplayable( pt1 ); Make Displayable( Pt2 );
Moveto( Pt1.X,Pt1.Y ); Drawto( Pt2.X,Pt2.Y );
Drawn := true; (* mark as displayed *)
end;
end; (* ClipAfter *)
(* ClipOut procedure body *)
begin (* clip each poly edge by all closer *)
(* polys, draw what's left *)
NumDrawn := 0;
Lst1 := NumPts do
for I:=1 to NumPts do
begin (* get endpoints for edge *)
with Poly[LstI] do begin Pt1.X := X; Pt1.Y := Y; Pt1.Z := Z; end;
with Poly[I] do begin Pt2.X := X; Pt2.Y := V; Pt2.Z := Z; end;
Drawn := false;
ClipAfter( 1,Pt1.Pt2 ); (* clip to closer polys, then display *)
if Drawn then NumDrawn := NumDrawn + 1;
LstI := I;
end; (* for loop *0
if NumDrawn = 0 then NumPts :0; (* mark as hidden if nothing drawn *)
end;
(* ClipOut *)
illustration_link (71 Kbytes)
Three-dimensional object displayed as a set of straight lines defined by 10 points (figure 1a) and a set of polygons defined by using the same points (figure 1b). See table 1 for associated data.
illustration_link (119 Kbytes)
Vertices for objects to be displayed in three dimensions may be measured from front and side views laid out on ordinary graph paper.
illustration_link (68 Kbytes)
Graphical representation of calculating the rotational angle about the
z
axis in computing the eyespace matrix.
illustration_link (20 Kbytes)
Graphical representation of calculating a rotation about the
x
axis.
illustration_link (68 Kbytes)
Representation of how a viewing window "clips" portions of polygons lying outside the pyramid defined by the window and the eyepoint.
illustration_link (97 Kbytes)
Another opportunity grabbed to revisit one of the spectacular Robert Tinney artworks which used to grace the cover of BYTE.
screen_link (17 Kbytes)
High-resolution display of solid three-dimensional objects defined as sets of polygons.
screen_link (38 Kbytes)
Low-resolution display of the same objects as in photo 1.
screen_link (113 Kbytes)
Removal of hidden surfaces can be clearly observed in this display on a custom graphics display unit connected to a Digital Equipment VAX 11/780.
screen_link (107 Kbytes)
Transformation of a scene due to a change in the location of the eyepoint as well as transformation of the objects within the scene. Compare with photo 3.
15 Years Ago in BYTE
