Implementing a Demo-style 3D Renderer in Haskell

Michael Chen

May 1, 2001

1 Introduction

Demo programs were popular in the late 1980’s and early 1990’s to show off one’s ability to push rather limited hardware (286’s and 386’s) to achieve visual and audio effects. In this project, I attempted to write an extremely rudimentary 3D “engine” in Haskell.

Since I had a really bad encounter with the last programming assignment regarding FRP, I decided that it would be easier to have a non-interactive 3D engine, but allow input to specify rotations of the object along the x, y, and z axes.

2 Quick 3D Math

The obviously for this 3D renderer, various operations needed to be implemented. First, there needs to be a mathematical means of rotating an object. Second, there needs to be a way of translating the object from 3D space to 2D space.

2.1 Rotations

Rotating the Object is made a lot simpler by using matrix math with a few special matrices. Essentially, all essential three dimensional transformations can be described by using 4x4 matrices. However for the scope of this project, I wasn’t interested in computing 3D translations, so 3x3 matrices work fine.

In order to do these rotations, treat the coordinate to be transformed as a vector of length 3, and simply multiply the vector by the appropriate transformation matrix to obtain a vector that represents the rotated coordinate.

2.1.1 Rotations around X axis

[ \begin{matrix}1 & 0 & 0 \\ 0 & cos(θ) & sin(θ) \\ 0 & −sin(θ) & cos(θ) \end{matrix} ]

2.1.2 Rotations around Y axis

[ \begin{matrix}cos(θ) & 0 & −sin(θ) \\ 0 & 1 & 0 \\ sin(θ) & 0 & cos(θ) \end{matrix} ]

2.1.3 Rotations around Z axis

[ \begin{matrix}cos(θ) & sin(θ) & 0 \\ −siz(θ) & cos(θ) & 0 \\ 0 & 0 & 1 \end{matrix} ]

2.2 Translating to a 2D Coordinate System

Once a three dimensional point (x, y, z) can be manipulated and transformed, it needs to be plotted to the screen. To do this, a simple formula is used to transform the coordinates to something that can be plotted.

To derive a two dimensional point, simply divide all of the components of the three dimensional point by it’s z coordinate.

\frac{(x, y, z)}{z} = (\frac{x}{z}, \frac{y}{z} , 1)

In essence, what this transformation does is project the three dimensional point onto the plane z = 1. To change the project plane (and thus mess with the perspective), simply multiply all of the coordinates with n where z = n is the new projection plane.

3 Drawing a simple object

Objects for this system are treated as lists of Triangles. First, any user defined transformations are applied to the triangles that make up the object. Then, the triangles are sorted based on their average Z coordinate in descending order.

This is done so that when drawing triangles, the further triangles are drawn first and thus will be covered up by triangles nearer to the “observer.” This is often called the back-to-front or painter’s algorithm. The only reason this algorithm was chosen was its simplicity. In certain situations, such as objects with intersecting polygons, this algorithm will result in incorrect behavior.

Once the triangles are sorted, they are “flattened” by applying the 3D to 2D transformation. Once the transformation is complete, all of the triangles are drawn to the screen using the Haskell graphics library polygon primitive.

4 Faking Animation

Simple animations (functions main 8 - 14) were hacked by forcing the drawing engine to accept a stream of x-axis, y-axis, and z-axis rotations. For each, member of the stream, the system would render the frame, render a large black rectangle to blank the screen, and then continue on to the next element in the stream.

Surprisingly animation is quite fast^{1} and in most instances it actually seems pretty good. Unfortunately, since the Haskell graphics library lacks any means of waiting for the screen refresh, the animation suffers from excessive flickering.

5 Conclusion

Implementing a semi-working 3D system in Haskell turned out to be pretty difficult, and surprisingly enough, although Haskell is interpreted, the performance of a flat-shaded rendered appears to be good enough that real-time performance might be achievable, especially in scenes with a number of low triangles. If more time were available, it would have been interesting to couple this 3D system with FRP for some animated behavior.

Simple texture mapping was attempted, but it turned out to be difficult given the time frame for the project. Since the Unix version of the Haskell Graphics library seems to lack a bitmap loader, texture mapping was dropped.

References

[1] Ilkka Pelkonen. 3DICA 3D Programming Tutorial, version 2.22b. Web Document available at http://www.3dica.org.

[2] J. D. Foley, A. van Dam, S. K. Feiner and J. F. Hughs. Computer Graphics. 2nd Ed. Boston: Addison-Wesley, 1996. pp 201-284.

1On an 800 MHz machine.