Coding — creating 3D graphics on the ZX Spectrum

Tagan News #07

Coding

In connection with the expansion :) I’ve decided to add a section to the newspaper devoted to programming. I didn’t have time to write something specifically for it, so I’m using an article written at the request of Alexander Shushkov (Alex Xor) for a book about programming on the Spectrum. And if you find this article interesting, I’ll tell you one more thing: the book is planned to contain a large number of articles on all sorts of topics. So it’s in your interests, too, to support the compiler in this difficult work. Well, I’ve done my good deed—advertised it :) So, let’s begin.

How to Make 3D

C) Vitamin/CAIG/2001

With the development of hardware, programs that work with 3D graphics have become widespread in recent years. These include games, editors, and demos. You can find examples on practically any platform, and the Spectrum is no exception. If you’ve seen the Iris demo by Flash inc, you’ll surely remember the part where various 3D objects spin on screen. We’ll try to make something similar. Of course, this engine is much simpler: it has no lighting, meaning the color of a face remains constant in any position; it cannot cast shadows. But it will do just fine for understanding the basics of this kind of programming.

To begin with, let’s work out what we need in order to draw a 3D object.

1) Define the object itself. Since ours will be a solid object, not a vector one, we need to specify the coordinates of all its vertices, then a list of all its faces, indicating which vertices belong to each face.

2) Define the necessary operations (translation, rotation, scaling) for the object. We’ll only rotate it, so you can figure out the other, fairly simple operations on your own.

3) Develop all the necessary functions and procedures, both for calculations and for working directly with graphics.

Let’s consider each point in order.

1) Object format. This engine uses the following way of storing an object: first comes the number of vertices, then the number of faces. Next come groups of three numbers, corresponding to the coordinates of each vertex. The number of these groups is equal to the number of vertices. After that comes the list of faces. Each face is described by 4 numbers: the indices of the vertices belonging to that face, and its “color,” i.e. the number of the fill texture. This format is the simplest both to define and to implement in a program.

2) Since the only operation applied to our object is rotation, let’s describe how a single vertex is rotated. The coordinate axes are oriented as follows: the Ox axis points toward us, the Oy axis points right, and the Oz axis points down. This arrangement is not essential; it was chosen more for code efficiency than for any other reason. To rotate around the Ox axis, use the following formula:

x'=x
y'=y*cos(rx)-z*sin(rx)
z'=z*cos(rx)+y*sin(rx)

Rotation around the Oy axis:

x''=x'*cos(ry)+z*sin(ry)
y''=y'
z''=z'*cos(ry)-x*sin(ry)

Around the Oz axis:

x'''=x''*cos(rz)-y''*sin(rz)
y'''=y''*cos(rz)+x''*sin(rz)
z'''=z''

Coding

Actually, these calculations are performed by multiplying a matrix containing the coordinate values by rotation matrices for each axis. This is how scaling and translation effects are produced. But we have replaced the rather labor-intensive matrix multiplication operation with the operations described above.

So, we have obtained new coordinates for all the vertices of the given object (in a separate buffer, of course). What do we do next? Draw it on the screen!

3) The basis of all graphics routines for creating three-dimensional (and not only three-dimensional) images, whatever platform they are implemented on, is a routine that draws a triangle from three pairs of coordinates. There are several ways to implement this. The simplest is to draw the triangle and then fill it with the selected texture. But believe me: the labor involved in this method, not to mention the considerable complexity of the supporting routines (line drawing, texture filling), will negate all our efforts to make things faster. Another method is more suitable: triangle scan conversion.

The idea is as follows. Suppose we have a triangle defined by three pairs of screen coordinates. Using this data, along with the fill color, we must draw the triangle. First, let’s note some features of this shape. A triangle is bounded by three line segments, each of which can be represented by the equation of a straight line: y = k*x + b, where y is the current ordinate, k is the tangent of the line’s angle of inclination, x is the current abscissa, and b is the coefficient defining the line’s offset from the origin. For our line segment, this expression becomes: x = x0 + (x1-x0)*(y-y0)/(y1-y0), where (x0,y0) and (x1,y1) are the starting and ending points, respectively. In other words, we obtain the abscissa from the current ordinate. The following algorithm gradually takes shape:

  • Sort all vertices in ascending order of ordinate; the abscissa values do not matter here.
  • Split the triangle into two parts—up to the middle point and after it (vertically).
  • Calculate the abscissa increment for each side: dx = (x1-x0)/(y1-y0), since the ordinate increases by 1 as we proceed row by row from the first vertex to the last.
  • At each step, calculate the new abscissas of the points where the scanline intersects the sides of the triangle, then draw a horizontal line between these two points.
  • When the ordinate moves into the second half of the triangle, recalculate one of the increment coefficients.
  • Continue until we reach the bottom vertex of the triangle.

Note 1: In general, to calculate the abscissa of the next point, you can use Bresenham’s line algorithm.

Note 2: You also need to watch out for cases where the vertices have the same ordinate; otherwise, we risk getting stuck in a loop and drawing something completely different.

For complete happiness, we also need to determine the type of each face at any given moment—front-facing or back-facing. This is calculated using the normal vector. If it points toward us, the face should be drawn; if not, it should not. The vector is calculated like this:

| i  j  k|
|x1 y1 z1| = i*(y1*z2-z1*y2)-j*(x1*z1-z1*x2)+k*(x1*y2-y1*x2)
|x2 y2 z2|

where i, j, k are unit vectors along the three axes, and x1, y1, z1 are the components of the first vector, x2, y2, z2 those of the second. These vectors share a common vertex and are arranged clockwise relative to each other.

For example, you can take vectors AB and AC, or BC and BA, or CA and CB. In this case, the normal vector points toward us. To determine whether a face is visible, we only need to calculate one coordinate of the vector—in our case, X = y1z1 - z1y2. If it is less than zero, we will not draw that face.

As for this particular implementation: fixed-point arithmetic is used, with the high byte as the integer part and the low byte as the fractional part in units of 1/256. The triangle is also drawn in a somewhat unusual way: the top part from the top, the bottom part from the bottom. Maybe that’s faster this way; I don’t know. All the other notes are in the program text. And here’s what you can (and should) get in the…

Share your thoughts about the article