Real-Time 3D with Python Part II: Surfaces and Perspective

In the introduction I explained the idea: Using Python to program old skool demo style real-time vector graphics. In Part I I set up a simple 3D wireframe object, rotated it, and drew it on the screen. This part is about adding surfaces to that wireframe, and how to use perspective so that more distant objects appear smaller on screen, and objects in general look more natural.

The program code for all parts can be downloaded from github. Note that the full code is not found below - to run this, use github code.

Defining surfaces

A cube object has eight nodes and six surfaces. For the program to reasonably handle a surface, it has to be flat - all its nodes must lay on a single plane. Then it is possible to define if the surface is visible or not and to draw it using a single polygon. To tell the program what those surfaces are, I define a new class:

class VectorObjectSurface:

    """
    Surfaces for a VectorObject.
    
    @author: kalle
    """
    def __init__(self):
        self.idnum = 0
        # properties set when defining the object
        self.nodes = []
        self.color = (0,0,0)
        self.edgeWidth = 0
        # the following are calculated during program execution
        self.zpos = 0.0

    def setZPos(self, zpos):
        self.zpos = zpos

Then, for the VectorObject class I add a list to hold these, and code to set one surface up and add it to the list:

    def addSurfaces(self, idnum, color, edgeWidth, node_list):
        # add a Surface, defining its properties
        surface = VectorObjectSurface()
        surface.idnum = idnum
        surface.color = color
        surface.edgeWidth = edgeWidth
        surface.nodes = node_list
        self.surfaces.append(surface)

The surfaces can then be set up after the nodes have been defined (see previous part). The colour of the surface is here defined as white for the first two, light grey for the next two, and dark grey for the last two:

    node_list = [0, 3, 2, 1] # node_list defines the four nodes forming a cube surface, in clockwise order
    vobj.addSurfaces(0, (255,255,255), 0, node_list)
    node_list = [4, 5, 6, 7]
    vobj.addSurfaces(1, (255,255,255), 0, node_list)
    node_list = [0, 1, 5, 4]
    vobj.addSurfaces(2, (150,150,150), 0, node_list)
    node_list = [3, 7, 6, 2]
    vobj.addSurfaces(3, (150,150,150), 0, node_list)
    node_list = [0, 4, 7, 3]
    vobj.addSurfaces(4, (80,80,80), 0, node_list)
    node_list = [1, 2, 6, 5]
    vobj.addSurfaces(5, (80,80,80), 0, node_list)

Note that the order of the nodes is always clockwise (looking at the object from outside). Why? We will need to figure out if the surface is visible to the viewer, and unless (in later parts) specifically defined to show also its back side, only the front side will be drawn. When defining the nodes in clockwise order, we also which side is front and which one is back.

Obviously, the nodes have to be in correct order going around the edges of the surface, not crossing it. The last node will automatically be connected back to the first one, so for example node_list = [0, 3, 2, 1] defines a polygon with edges [0, 3], [3, 2], [2, 1], and [1, 0].

A couple of other things we need to add to the VectorObject class.

    def updateSurfaceZPos(self):
        # calculate average Z position for each surface using rotatedNodes
        for surface in self.surfaces:
            zpos = sum([self.rotatedNodes[node, 2] for node in surface.nodes]) / len(surface.nodes) 
            surface.setZPos(zpos)
        
    def sortSurfacesByZPos(self):
        # sorts surfaces by Z position so that the most distant comes first in list
        self.surfaces.sort(key=lambda VectorObjectSurface: VectorObjectSurface.zpos, reverse=True)

When the object has been rotated, I want to draw the most distant surfaces first and the ones closer after them, so that if they overlap the closer surfaces will be shown over the more distant ones and not the other way around. (For a simple cube this is not a problem, but the object could be more complex.)

First I update the average distance from viewer (Z coordinate) for every surface in updateSurfaceZPos. It simply sums up the rotated Z coordinate of each of the surface's nodes and the divides the sum by the number of nodes. Then, having that stored for all surfaces, I can sort the list of surfaces by it.

Then, before drawing the object in display (see previous part), I can use these to make sure I am drawing the surface in correct order.

        # draw the actual objects
        for VectorObj in self.VectorObjs:
            # first sort object surfaces so that the most distant is first.
            VectorObj.updateSurfaceZPos()
            VectorObj.sortSurfacesByZPos()
            # then draw surface by surface. 
            for surface in VectorObj.surfaces:
                # build a list of transNodes for this surface
                node_list = ([VectorObj.transNodes[node][:2] for node in surface.nodes])
                pygame.draw.aalines(self.screen, surface.color, True, node_list)       
                pygame.draw.polygon(self.screen, surface.color, node_list, surface.edgeWidth)       

Note that unlike in the previous part, I am not drawing any circles to mark the nodes, and the aalines here is actually not required, it simply makes the filled polygon have anti-aliased edges. All surfaces are drawn, even if we know at least three of them (this being a cube) will be pointing away from the viewer on the back side, but at this stage we are still missing the code to determine which ones. (A simple solution would be to not draw the three most distant ones - but that only works for a cube-like object.)

Have some perspective, please

How about adding that perspective to the transformation from 3D to 2D? It is really simple. To make more distant objects appear smaller, I simply use the distance as a divisor. For scaling I have defined (in VectorViewer) self.zScale = width * 0.7. This can be tweaked to easily show objects bigger or smaller. Then, redefining the transform method:

    def transform(self, zScale, midScreen):
        """ 
         Flatten from 3D to 2D and add screen center.
        """
        # apply perspective using Z coordinates and add midScreen to center on screen to get to transNodes.
        # for normal objects, some of the transNodes will not be required, but possibly figuring out which are and processing them
        #   individually could take more time than this.
        self.transNodes = (self.rotatedNodes[:, 0:2] * zScale) / (self.rotatedNodes[:, 2:3]) + midScreen

As you can see (comparing to Part I), the only change here is to use the zScale as a scaling multiplier and the Z coordinate of rotatedNodes as a divisor. Hey, Presto! We have perspective.

This is where we are at this stage:

Need for Speed

On the Amiga (or more generally the MC68000 chip), division was a terribly expensive operation, taking about 13 milliseconds each. Avoiding division was thus very important, but with e.g. scaling above it is also very necessary. A common trick used here was to replace a DIVS instruction with a MULS and a SWAP,  using a precalculated table - in quite a similar manner as for the sine and cosine operators described in the previous part. In effect, in the beginning of the program, we can store in memory a table of $10000/x for all x we need as divisor (remember, integers only), and then replace all divide operations with 1) fetching the correct precalculated number from the table, 2) multiplying the dividend with it, and 3) swapping the halves of the result (taking the higher 16 bits to the lower 16 bits, in effect dividing it with $10000).

Despite the added complexity, this could save perhaps 40+ % of the CPU time needed - a MULS takes less than half the cycles a DIVS requires, while accessing the table and swapping the are relatively quick. Using tricks like this was based on detailed diagrams of instruction timings, and of course the full control of the CPU that Assembly language provides.

Next: Part III: Visibility and Shading.