True3D

by Jeff Krueger and Aaron Fontaine

This is a modified version of the original written description of our project. It does not include all of the original figures, but there are some nice screen shots of the program in action.


I. Problem Definition

Using an array of three-dimensional (x, y and z coordinate) points and an array describing how to connect these points, create a wireframe figure or world. Draw a two-dimensional representation in perspective and allow the user to navigate around to view it at different angles. The navigation features should include move forward, backward, up, down, left, right, and strafe left and right.


II. Solution

The solution is called True3D and was derived from a combined effort between Aaron Fontaine and myself. There are three main parts to True3D. First is the MacOS shell, which handles events and interaction with the MacOS. Second is the main 3D routines which handle the calculations necessary to rotate, translate, and draw matrices. The third part is the data structures we used, which were designed and revised to be as flexible as possible.

The MacOS shell is composed a small collection of routines which handle user interaction with True3D. Some housekeeping tasks are also performed, such as activating and updating the main window. Keypresses that affect the movement of the object displayed are sent to the main 3D routines to be processed. I designed and implemented the code for the MacOS shell.

The main 3D routines deal with the 3D data. These routines include one to change the view based on user interaction, one to perform translation matrix multiplication to calculate the result of the user’s movement, and one to display the result on the screen. The algorithms used in these routines were primarily designed by Aaron Fontaine, while both of us implemented them.

There are seven data structures used. These structures were carefully designed by both of us to allow the most flexible data set possible. Here is a brief description of each:

The structures of main interest are Matrix and LineData. True3D uses three Matrix structures: the original matrix defining the object’s vertices, a rotation matrix, and a result matrix. The result matrix is calculated based on the data in the PlayerInfo structure by translating the source and performing matrix multiplication with the rotation matrix. The LineTable structure is used when drawing the object on the screen. True3D simply connects the vertices to form the object.

The code for True3D is split into two header files and five source files. The first header file, Prototypes.h, contains the function prototypes required in C. The second header file, True3D.h, contains the structure declarations and constants. It is not necessary to provide a separate description of each function or the members of the data structures because the description is included in the source listing itself. Each member of a structure has a comment, and each function has a comment block describing what its input and output are, specifically what it does, and who designed and implemented it. The code itself is extremely well-commented and can be easily followed. The functions in the following pseudocode are in the same order as the program listing.


III. The Math Behind True3D

I have included three drawings Aaron made which explain the math behind True3D. These drawings are located at the back of the dossier.

Figure 1

This shows the formulas used to rotate the source matrix. The general formula for the rotation matrix we used is the result of solving the equations, and is shown and the bottom of the page. The implementation of the rotation matrix can be seen in the CalcResultMatrix routine.

Figure 2

This shows how we calculate the distance from the player’s viewpoint to the projection screen, known as “a”. It is calculated in Load3D based on the view angle constant, kViewAngle. The value is stored in the DrawInfo structure and used in UpdateMainWindow when calculating the 2D coordinates of a vertex.

Figure 3

This shows how we use “a” to calculate the 2D coordinates of a vertex. The two resulting formulas for NewX and NewY are implemented in the UpdateMainWindow routine.


IV. Testing and Robustness

I have included four figures illustrating the capabilities of True3D and two showing how the data for the objects is entered. These figures are located at the back of the dossier.

Figure 4

A drawing by Aaron Fontaine, showing the process of determining the vertices for a dodecahedron. The vertices are then stored in a resource. MacOS uses resources to keep dynamically-sized data. A resource editor called Resorcerer is was used to enter the Matrix and the LineTable in. True3D can simply load this data already in the correct format.

Figure 5

This is a screen shot of Resorcerer editing the vMap (Matrix) resource. A template was created that has the same format as the Matrix structure, and Resorcerer took care of the rest.

Figure 6

This is a screen shot of Resorcerer editing the lMap (LineTable) resource. A template was created that has the same format as the LineTable structure, and Resorcerer took care of the rest.

Figure 7

The dodecahedron actually shown on the screen.

Figure 8

A box with a pyramid on top. This demonstrates True3D’s color capabilities.

Figure 9

This shows True3D’s ability to display an object at virtually any angle or position.

Note: The resource fork of True3D can contain multiple vMap (Matrix) and lMap (LineTable) resources. By changing the ID number of the constant kObjectID and recompiling the program, a different object can be loaded and displayed. In this case, the dodecahedron is 128, the box/pyramid is 129, and Seirpinski’s triangle is 130.


V. Conclusion

True3D is a solid start to a 3D game. It’s strengths include the ability to display any object or array of objects that can be made up of straight lines, such as a 3D “world”. Custom colors can be defined in a ‘pltt’ (palette) resource and are specified by index number in the LineTable.

True3D has one major weakness. It assumes a 1:1 ratio between the units used to describe the object in the matrix and pixels on the screen. This can cause problems when the numbers become very large due to the player’s position and angle. When calculating the result, the coordinates that exceed the variable’s limit “roll over” and are displayed with no degree of accuracy.

I spent a lot of time rewriting the essential calculation routines of True3D to optimize the speed at which they run. Unfortunately, some inefficiencies exist in the way True3D handles its data. If all the data, including the globals, was contained in one large chunk, execution speed would likely improve because the data in the level 2 cache on the PowerPC processor would not be flushed and reloaded as it is when the data is scattered.

Due to limitations on time, Aaron and I were not able to design an impressive world. However, I feel that the capabilities of True3D were clearly demonstrated.

This summer, Aaron and I would like to continue to enhance True3D to support hidden surface removal, collision detection, and texture mapping. These features would greatly enhance the appearance and flexibility of the objects True3D can display.


Updated January 19, 2000.

E-mail: jkrueger@cs.wisc.edu