Sound Vision Demo in Python

In July 1992, the Amiga demo group Reflect released Sound Vision at the first Assembly demo competition. Having programmed a large part of the demo, which was, at the time, quite awesome (if I may say so), I wondered if I could do the same on PC with Python and pygame. The demo consists of a number of independent parts with real-time calculated graphics, so I chose just one to get to grips with the programming environment (I have no previous experience on Python). Of course, I picked the most complex part - the 3D Vector World with light sourcing. You can read about this in a previous series of blogs. Next, I did the Fractal Landscapes part - again, read more here. Then I embarked on coding the rest of the parts, and indeed, now having some practice, they were finished quite a bit quicker than the ones already mentioned.

All the code and graphics and music files can be downloaded from github. The video captures below are from the Python version at 1280x720 @60Hz.

Programming vs. Programming

Programming demos on 1992 Amiga hardware (actually released 1985) using Assembly language was quite different from using today's rather hardware-agnostic Python & pygame setup. At the time, the first thing we demo programmers usually did was to take over from the operating system and use the memory normally dedicated to OS routines for our own purposes. This was possible because all hardware setups were the same (maybe someone had more RAM but that's about it) and no drivers etc. were needed. Even if, back then, the Motorola MC68000 running at ~7.1 Mhz was great, and all you had to do was fill a screen with a resolution of 352 x 286 pixels and a maximum of 32 colors, there were quite a few obstacles to cross before getting to real time 3D graphics. Consider these:

• There was no floating point support - integers only. And even with 32 bit registers, you could only perform multiplication on 16 bit integers (0 to 65,535, or -32,768 to 32,767 if signed). Any division result had to fit into that as well. 3D rotations employ a lot of multiplication and division, how do you avoid overflow and losing precision?
• There were no mathematical functions available at all, apart from instructions for addition, subtraction, multiplication and division. For 3D rotations sine and cosine are essential and used a lot. The sine of any number is, by definition, between -1 and +1 - but all you have are integers anyway! How do you get the sine and cosine, perform the operations, and most importantly: how do you do it fast enough? And how do you ever get a square root if you need one? I discuss this a bit more here.
• And of course, things like CPU cache (today's computers have more of that than the Amiga had total RAM), multiprocessing and multithreading were only in our dreams. Basically, any number to be used in, say, multiplication had to be first fetched from RAM to one of the eight data registers in the CPU.
• The standard setup was only 512 kB of RAM, which is about 0.006 % of today's standard 8 GB.

For the Python project, I had a number of goals on how it should work. First, it should run in a window and in full screen mode - so using "Amiga style" bitplane graphics modes was probably not a good idea. Second, it should run in any resolution selected (you can set this at the end of SoundVision.py). Third, it should be "standard Python" not requiring any Cython-type supersets or any other such additions.

Sound Vision

The demo consists of a number of independent parts just like the original. The SoundVision.py program simply imports these parts as modules and runs them one after another. In addition it handles setting up the screen and music. The parts are shortly described here.

It must also be said that I only did part of the original Amiga programming, and credits for the additional code, the music and the still pictures are given in The Stars and End Credits parts.

Stripy Plane Vectors (Title texts)

The stripy plane vectors are created in a very similar manner as they were realized in the original Amiga demo. There are two planar (2D) vector objects - the letter and the stripes - and they are combined on top of each other to create the striped letter. On the Amiga, this was easy to do with two separate bitplanes; on a regular PC screen, the stripes were "subtracted" from the letter using pygame's blit command. Note the nice copperbars imitation in the background! 

Metamorphing Title Text

This was an invention - or, rather, an addition to an existing Shadebobs routine - that was able to shift from one 1-color image to another gradually, using a 32-color palette. In essence it stored all the 31 images, adding them on top of each other so that the highest number color was used when all images overlapped, and the other colors in a similar way based on the number of images overlapping. The invention was merely to also subtract the oldest image, so that instead of continuously adding images, you would only have 31 in use at any one time.

Moving and/or rotating the images slightly combined to this creates the effect. Changing from one text to another is a matter of simply defining the letters so that each letter coordinate can be interpolated to the coordinate of the new letter. I improved on the original by using a 256 color palette.

The Stars

The movable 3D stars were easy, the race was about the number of them. I think I got up to something like 650 movable 3D stars with true perspective in two bitplanes on the Amiga. Movable here means they can go sideways and up or down, but not rotate around any axis. Adding some bitplanes for the credits meant using some precious cycles for having more colors, so in the demo there are maybe 630 stars or so.

In Python, using NumPy here is quite efficient. The number of stars is 1 % of window resolution, so for a Full HD screen you get 20,760 stars. In addition, the closest ones are plotted in 2, 3 or 4 pixel size - but still, if you watch the video above, you need to enlarge it to actually see them. For plotting the stars, it would be way too slow to use a loop and setting each pixel separately. Instead, I am using pygame's surfarray, which can be operated as if it were a standard NumPy array. This way all the stars can be plotted simultaneously! I have also improved on the original code so that moving the stars works better (albeit not perfectly) and they can also be rotated around the Z-axis (the axis from viewer to distance).

Side Effect Cube

On the Amiga, this was programmed by my friend and colleague Overlander. The aim is to have a number of 3D objects; a star field, a rotating 2D star, and a 3D cube, and then project these on the sides of another, bigger 3D cube. The projection can be done in two ways: 1) rotate the "side objects", project them to a stationary big cube's sides, and the rotate the big cube including these; or 2) rotate all objects separately, and use interpolation to add the smaller objects to the big cube. The latter is faster, if perhaps slightly less accurate. I am not sure which method Overlander used, but I used the latter here.

Shadow Bobs

This effect, probably better known as Shadebobs, was something of a filler as there was really nothing new to it. It was needed, because the next part, the Globe, relied heavily on the processor to rotate a (back then) huge 3D object and that could not be achieved real time with a decent frame rate. However, shadebobs was very light on the processor and heavy on the Blitter coprocessor instead; so when the Blitter was busy creating shadebobs, the CPU was used for precalculating the Globe.

I improved the original by moving to a 256 color palette (from 32 on the Amiga). You could actually easily use even more colors, but 256 is convenient when using a NumPy array with data type uint8 (unsigned 8-bit integer), as when adding to color 255 it drops back to 0 automatically and no additional code is needed to check for that limit. Again I am using pygame's surfarray to do this and able to process hundreds of bobs per frame.

The Globe

On the Amiga, the 300 frames (pictures) in 240x240 pixels and EHB (extra half-brite, six bitplanes) would have used 12MB RAM. Of course, four bitplanes (the blue ball) are stationary, but still there was not nearly enough RAM to store the pictures, even with extra RAM as pictures needed to reside in the so-called Chip RAM. Instead, during the Shadow Bobs part, the globe was rotated and the necessary Blitter data was stored. Even this required a 512kB memory extension (so 1MB RAM in total). Then, using the precomputed Blitter data, the object was drawn fresh for each frame. Amiga's EHB mode allowed for a sixth bitplane to be used, but it had no color registers - it simply halved the color brightness. This is how I was able to show Finland separately. The blue ball in the background was an image created in a ray tracing program.

With Python I create the blue ball first. It is actually a one-color blue ball - but then I also create a shaded gray ball, which is then used to create the shading or "light source" effect using pygame's multiplicative blit operation. No precalculations are needed, the 3D land masses are rotated and drawn real time. There's also a small routine to convert a Mercator projection world map to 3D globe Cartesian coordinates. The bit that needed quite a lot of work is how to define the edges of a continent when parts of it are on the back side. On the Amiga this was actually easier!

The World

This was really the part that took the most time and effort. There's a lot happening; there's a 3D city the viewer can fly through, there are moving objects like a car, the light source is moving and the buildings are shaded accordingly, and cast shadows. Nothing is precalculated, at least in the sense that you could fly another route or give control of the flight to the viewer. On the Amiga the rotation of the city is 2D only for two reasons: 1) it would have been slower in 3D and 2) the blue "ground" is created using the Copper coprocessor, and going 3D would have meant not using this effect at all. While all the other parts run in "full frame rate" i.e. 50 frames per second (PAL Amigas had a fixed 50Hz refresh rate), this part is so complex it, at times, runs at something like 13-15 frames per second - a bit jerky, that is. I still like it, though.

The Python implementation was my first Python project - read more about it here - and now I would probably make some changes to this. In the Amiga Assembly code it was important to avoid unnecessary calculations, but it seems using Python to (for example) figure out which rotations are not required is often slower than rotating everything using a single NumPy operation. Anyway, I improved on the original by keeping the code fully 3D, so there's some Z-axis rotation as well. Also, the data on which the city, movement etc. are based, are now in a separate xml file. 

The Milky Way

This is a variation of the Metamorphing Title Text - there's a rather simple planar vector object, which is rotated, and the last 31 (on the Amiga) or 127 (Python) images are added on top of each other to form the final image. Here, instead of using a surfarray, I was able to use some clever additive and subtracting blits to generate the final true color image, due to the limited palette.

Box in a Box in a Box...

There are eight boxes rotating inside each other, within a frame. On the Amiga, I needed the frame to make the area updated smaller than full screen - otherwise it would not have worked at 50 fps in five bitplanes. Even if there are only eight boxes with three different color sides showing each, i.e. 24 colors, the opacity of each box must be taken into account as well. The solution, in bitplane graphics, was simple (if I recall correctly): the area covered by each box was drawn using three bitplanes (that is, using eight colors - one for each box), to give each box its color. Then, each box had two sides drawn in bitplane number four and two in bitplane number five, so that they added bits 01, 10 and 11 to the total color, separating the sides. This was rather efficient as drawing filled polygons on the Amiga was achieved by drawing the vertical lines (one pixel per horizontal line), and then invoking a Blitter fill operation. The fill operation worked in an XOR fashion so that it always switched on/off when it encountered a new pixel on a single horizontal line. Thus, I could draw all the edges of the boxes, and use just one fill operation to achieve the result, where the color always changes if the outer box edge crosses the box's surface.

With Python, I could have used a surfarray again, but instead there's rather simply just an alpha value in use. The biggest box is drawn directly on the screen, but the next ones are copied so that about one third of the existing image remains and about two thirds (the alpha value) come from the new, smaller box, creating the effect of seeing through the outer boxes. There are some limitations on how this works, and I had to kind of "work backwards" from the colors I needed to define the colors to be actually used, as they blend with the previously drawn boxes' colors.

Fractal Landscapes

This is one of favorite routines, and I have written more about it here. As a fractal it is very simple, but I was able to calculate it really fast considering Amiga resources, and I still like the zoomer (try it with the mouse) a lot. You can actually zoom into it infinitely. I improved the routine on Python by adding controls on the resolution of the grid.

Raytracing

Raytracing was performed by Overlander on an Amiga ray tracing program Real3D. It only consists of ten images - remember memory and disk space were scarce resources - and, if I remember correctly, those ten images took 37 hours to calculate on his Amiga 500. All I did here was that I ran the original demo in a Amiga emulator (WinUAE) and snipped the ten images from the screen... and added a simple scroll text to get the original feel. The Reflect logo was drawn by Nighthawk.

End Credits

Not much happening here, there was some space left on the original Amiga 880 kB floppy disk, so this was added as a finishing touch. The disk was quite fully used and we actually used our own track loader (coded by Overlander) - no file system, but actually giving commands to the disk drive: move the magnetic head one step further, read a sector, etc... you probably would not do that with modern day computers any more.

The funny thing is that, despite requiring a huge amount of operating system code, the files for the Python implementation take more space, about 1.7 MB, although only 268 kB of that is Python source code and 1.0 MB and 289 kB are taken by the still graphics and music, respectively.

Thank you for reading.

Fractal Landscapes

In the introduction to my previous project, I explained the idea: Using Python to program old skool demo style real-time vector graphics. The finished project can be found here. This post is about a different part of the same demo - random Fractal Landscapes. 

Again, Python code can be found in GitHub.

Fractals They Are

Apparently, Benoit Mandelbrot has defined fractals as "a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole". These landscapes use a simple mid-point replacement algorithm to generate random fractal landscapes, which can be indefinitely zoomed into. 

The original Amiga demo (1992) used a fixed 65 x 65 point grid (i.e. 4,225 random grid values for 8,192 triangle surfaces between them), but this Python version can switch between (2^n + 1) x (2^n + 1) point grids, n being between 3 and 10 (i.e. 81 to 1,050,625 grid points and 128 to 2,097,152 surfaces). On the Amiga machine language and Blitter it took about two seconds to draw a new landscape; on my PC it takes about the same time to draw a 2^8+1 version - 16 times as many surfaces. Although the screen resolution on my PC is also a lot higher (about 25 times the number of pixels drawn), this mainly shows how slow (my) Python implementation is. 

Fractal Routine

Generating a landscape is simple, especially as its grid size is always 2^n+1. First, the corners are set. Then a simple loop goes through the mid-points so that they are set as the average of the end-points plus a random change. The size of the random change is halved after each round, as the distance of the end-points is also half of what it was the previous round. Unfortunately, I could not figure out a nicer way of achieving this without looping through single points.

    def generateGrid(self):
        
        # full grid generation. Start from corners.
        rSize = self.randSize
        startSize = self.landSize
        # set corner values. Tilt: Use higher altitudes for back of grid.
        self.grid[0, 0] = (random.random() - 0.5 + self.tilt * 2) * rSize
        self.grid[0, self.gridSize] = (random.random() - 0.5 + self.tilt * 2) * rSize
        self.grid[self.gridSize, 0] = (random.random() - 0.5 - self.tilt) * rSize
        self.grid[self.gridSize, self.gridSize] = (random.random() - 0.5 - self.tilt) * rSize
            
        # go through grid by adding a mid point first on axis 0 (X), then on axis 1 (Z), as average of end points + a random shift
        # each round the rSize will be halved as the distance between end points (step) is halved as well
        for s in range(startSize, 0, -1):
            halfStep = 2 ** (s - 1)
            step = 2 * halfStep
            # generate mid point in x for each z
            for z in range(0, self.gridSize + 1, step):
                for x in range(step, self.gridSize + 1, step):
                    self.grid[x - halfStep, z] = (self.grid[x - step, z] + self.grid[x, z]) / 2 + (random.random() - 0.5) * rSize
            # generate mid point in z for each x (including the nex x just created, so using halfStep)
            for x in range(0, self.gridSize + 1, halfStep):
                for z in range(step, self.gridSize + 1, step):
                    self.grid[x, z - halfStep] = (self.grid[x, z - step] + self.grid[x, z]) / 2 + (random.random() - 0.5) * rSize
            rSize = rSize / 2

Mountains and the sea

The coloring reflects the original demo: high altitudes are ice, then one has brown soil, and close to sea levels, green vegetation. The sea is a nice blue, and while it is generated in exactly the same way as land, it is drawn flat and the (negative) height only defines its color. For land, the color is given by how steep the triangle shape is, giving a shaded look.

To the Drawing Board

Drawing the fractals on screen is simple - start from the back, and for each grid square, draw two triangles. As the viewer is above sea level, the sea level coordinate of each new row is at a lower level than that of the previous row, and for perspective, the horizontal distance between the grid points grows the closer to the viewer we get.

Zooming in

As the definition above implies, one can take a part of a fractal, look at it closer, and it will have the same general properties as the original. These landscapes can be zoomed into indefinitely. There is a mouse-controlled zoomer, which can be used for selecting any quarter of the land area, and then zoom into it. Of course, zooming into a mountain will soon lead to that mountain growing so high that it goes entirely out of sight; so zooming in on some island in the sea is a better idea.

Zooming is quite simple. Take the zoomed area grid, and spread it to the whole grid, filling in every one in four grid points, and at the same time doubling the height. Then, use the last phase of random mid-point replacement algorithm to fill in the empty grid points.

The video clip shows zooming in action.

User Controls

There are some additional user controls in the Python version. They are listed in the information area above the landscape - cursor keys for controlling the grid size and general steepness, f to toggle full screen on/off. As in the original, left mouse button creates a new landscape, while right mouse button zooms the mouse-selected area.

Parallel Thoughts

Having a large number of grid points to calculate or triangles to draw sounds like a good candidate for using all processor cores. Alas, this is not the case here. For grid points there could be some complications as the number of points calculated in each step varies and the points depend on the previous step. Perhaps drawing the triangles would be easier, but I could not get even simple examples of Pool or Process to really work. Some say there are issues with the environment I use (namely, Spyder (4.0.1)). Perhaps sometime later...

Real-Time 3D with Python Part VIII: Finishing Touches

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, and in Part II added surfaces and perspective. Part III was about calculating object surface visibility and shading. Part IV set up an XML reader to define the objects and other properties using a common file format (XML), and added the code needed to work with multiple objects. In Part V, I added two special features: the ground and roads. Part VI calculated and drew shadows, and Part VII added moving in the cityscape and moving objects. This final part finishes the project with a number of small finishing touches.

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

Add Some Finishing

To polish the surface and round some corners, I am adding a number of smaller pieces to finish the project nicely:

• full screen mode
• music
• color blends for shadows and ground
• an info display for program resource use
• fade in and fade out

I will go through these each below.

For a Fuller Look

So far we have been running the program in a window. A more demo-ish look would of course be full screen, and this is easy to set up with Pygame. I have also set it up so that full screen mode may be entered and exited with key f as follows:

key_to_function = {
    pygame.K_ESCAPE: (lambda x: x.terminate()),         # ESC key to quit
    pygame.K_SPACE:  (lambda x: x.pause()),             # SPACE to pause
    pygame.K_f:      (lambda x: x.toggleFullScreen()),  # f to switch between windowed and full screen display
    pygame.K_i:      (lambda x: x.toggleInfoDisplay())  # i to toggle info display on/off
    }

    def toggleFullScreen(self):
        
        # switch between a windowed display and full screen
        if self.fullScreen == True:
            self.fullScreen = False
            self.screen = pygame.display.set_mode((self.width,self.height))
        else:
            self.fullScreen = True
            self.screen_blends = pygame.display.set_mode((self.width,self.height), pygame.FULLSCREEN | pygame.DOUBLEBUF | pygame.HWSURFACE)

        self.screen_blends = self.screen.copy()
        self.screen_shadows = self.screen.copy()
        self.screen_blends.fill((255,255,255))
        self.screen_shadows.fill((255,255,255))

If switching to full screen, the same screen is set up but with some specific flags making it take up the whole display, but with original resolution. For best results, resolution should obviously be selected such that it is supported in full screen. The new support screens for blends and shadows need to be initialised (copied) as well (more on these below).

Play It Again, Sam

A demo needs some music. I have no talent whatsoever on that front, but the original tunes of the 1992 Amiga demo (see introduction) can be found in some Amiga archives like Janeway. I found it surprising that the Amiga music modules, made with NoiseTracker or ProTracker etc., can be played straight out with Pygame. Note I am not including this module in github, use the link above to download it and take a note of the credits for it! The composer Jellybean is a Norwegian musician who made some great Amiga tunes for our demos. The code needed here is simple:

    music_file = "sinking2.mod"  # this mod by Jellybean is available at e.g. http://janeway.exotica.org.uk/release.php?id=45536
    vv = VectorViewer(disp_size[0], disp_size[1], music_file, font_size)

        # start music player
        pygame.mixer.music.load(self.music_file)
        pygame.mixer.music.play()

The part after the blank line is in vv.Run just before the main loop - I am just telling pygame to start playing.

Blending in

So far, the shadows have been one color irrespective of where they fall (the blue ground or the gray road). Similarly, although the ground blends to the horizon, the roads do not - they are an even gray. In the Amiga and its bitplane graphics, this was easily solved, using the Copper to change the ground and road colors dynamically line by line - although that was strictly restricted to Y axis rotation only (see Part V). In pygame, I can use a blit operation with blend to add, subtract, or multiply one screen (image) to another.

            # draw shadows always first for all visible objects
            self.screen_shadows.lock()
            shadow_rect = None
            for VectorObj in (vobj for vobj in self.VectorObjs if vobj.visible == 1 and vobj.prio == prio_nr and vobj.shadow == 1):
                node_list = self.cropEdges(VectorObj.shadowTransNodes)                
                rect = self.drawPolygon(self.screen_shadows, self.shadowColor, node_list, 0)
                if shadow_rect is None:
                    shadow_rect = rect
                else:
                    shadow_rect = shadow_rect.union(rect)
            while self.screen_shadows.get_locked():
                self.screen_shadows.unlock()
            if shadow_rect is not None:
                # blit the "multiplied" screen copy to add shadows on main screen
                # release any locks on screen
                while self.screen.get_locked():
                    self.screen.unlock()
                self.screen.blit(self.screen_shadows, shadow_rect, shadow_rect, pygame.BLEND_MULT)
                # clear the surface copy after use back to "all white"
                self.screen_shadows.fill((255,255,255), shadow_rect)

When drawing the shadows, I am using a "drawing board" image screen_shadows. It has been prefilled with all white, and the shadowColor is now a light gray. I have also modified the drawPolygon to return the (rectangular) area it has modified, and am using union to build the minimum size rectangular area holding all the shadows. This is then blit (ie. copied) to the actual image using BLEND_MULT, which in effect multiplies the colors of the actual image with the colors of the shadow image. As the shadow image background is all white, the multiplier is 100% for all colors red, green and blue, so there's no effect. The shadows are light gray, so the multiplier is less (I am using 140 of 255, ca. 55 %) so those areas appear darker. If the actual image has a gray road, a shadow falling on it will be a darker shade of gray; if the image has blue ground, a shadow falling on it will be a darker shade of blue. In the end the area used for shadows is filled again with all white, to be ready for the next frame. All the shadows are processed in one blit; this is more efficient and also avoids overlapping shadows being darker still.

For the ground, I am using the same technique, but somewhat modified. In the first phase, I am drawing the ground (in blue) and the roads (in gray) in one solid color. Then, I will blit on top of these an image, which has darker shades of gray at the horizon and lighter shades of gray close to the viewer, with the same color-multiplying blend method. This will cause the far away parts of these surfaces to blend nicely to the horizon (ie. towards black). The blend image is actually drawn at the same time as the ground, but it "waits" until the roads have been processed, and only the is used in the blit.

Information Overload

Why is my program so slow? It is nice, from a code optimization point of view, to know what takes time and what goes quickly in the program. I added an info display, which can be toggled on or off (see the first code box above). This plots information on the relative processing time taken by some of the parts or operations on the screen, and includes fps (frames per second) and some other data points. Behind are some data collected by calling measureTime below with a predefined timer_name:   

    def measureTime(self, timer_name):
        # add time elapsed from previous call to selected timer
        i = self.timer_names.index(timer_name)
        new_time = pygame.time.get_ticks()
        self.timers[i, self.timer_frame] += (new_time - self.millisecs)
        self.millisecs = new_time
        
    def nextTimeFrame(self):
        # move to next timer and clear data
        self.timer_frame += 1
        if self.timer_frame >= self.timer_avg_frames:
            self.timer_frame = 0
        self.timers[:, self.timer_frame] = 0

It stores the time elapsed from previous call to an array, which can then be used to calculate a moving average of a selected number (I am using 180) of frames. Then I am using code below to add these to the display image:

        # add measured times as percentage of total
        tot_time = np.sum(self.timers)
        if tot_time > 0:
            for i in range(len(self.timer_names)):
                info_msg = (self.timer_names[i] + ' '*16)[:16] + (' '*10 + str(round(np.sum(self.timers[i,:]) * 100 / tot_time, 1)))[-7:]
                self.screen.blit(self.font.render(info_msg, False, [255,255,255]), (10, 110 + i * 20))

Note that I am using blit again, but without any blend functionality, to add the text on top of the cityscape. (And yes, I know the text formatting used here is not very elegant.)

Fading In, Fading Out

In the Amiga demo scene, decent productions always nicely faded in from black and ended in a same way by fading out. I added a fade based on viewer movement as follows:

                # check for fade at start and end
                if loop_pos < 255 / self.fadeSpeed:
                    self.fade = (loop_pos * self.fadeSpeed) / 255
                elif loop_pos > VectorMovement.loopEnd - 255 / self.fadeSpeed:
                    self.fade = ((VectorMovement.loopEnd - loop_pos) * self.fadeSpeed) / 255
                else:
                    self.fade = 1.0

The fade is simply a multiplier between 0 and 1 and used to multiply the color components, causing the desired effect.

And finally. The end result. Feel free to compare to the original (see introduction).

Finally, Some Thinking

What could be improved? Certainly, a lot. This was my first Python project and learning by doing is a sure method to not find the ultimately best solutions. I am sure there are a multitude of ways to make this program run faster / more clear or elegant / more pythonic / more versatile etc. Some thoughts I have had during the project include the following.

Parallelism / multi-threading. While on the Amiga parallelism was restricted to simultaneous use of the CPU and the co-processors, modern computers have multiple processor cores and could divide the CPU load to several threads being processed in parallel. Maybe I will try this in some future project.

OpenGL. Would using it instead of pygame standard drawing methods make a difference? Would it be difficult? Or some other way of using more hardware support (read: graphics card) instead of using the CPU - that would definitely speed things up.

Adding features. There's a lot one could add, of course, although in 1992 on the Amiga this was really something, and already quite a stretch for its capabilities (although, clever programmers certainly made improvements after that as well). But probably adding bitmaps / texture to the walls and shadows falling on buildings could be done with Python power. Of course one could have a larger city, and user controlled steering, and add some game elements to it...

Thanks for reading.

Real-Time 3D with Python Part VII: Movement

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, and in Part II added surfaces and perspective. Part III was about calculating object surface visibility and shading. Part IV set up an XML reader to define the objects and other properties using a common file format (XML), and added the code needed to work with multiple objects. In Part V, I added two special features: the ground and roads. Part VI calculated and drew shadows. This part is about moving in the cityscape and adding moving objects.

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

Moving Around

In a game, one would add user controls for moving around the city, adjusting for direction, speed, viewing angles etc. In a demo, it is customary not to give control to the viewer, but to set up everything for show (exceptions have, of course, been made). There are two similar but separate types of movement in the demo: moving objects, and a moving viewer. Both should have control of both the position and the angles; angles meaning rotation for objects, and viewing direction for the viewer, the latter then translated into rotation of all objects.

I have defined the world as coordinates in 3D space, so it is natural to define movement in a similar fashion. However, movement should be smooth, not in a rectangular fashion, so I have defined it so (in the XML file) that at certain points of time I want to be at certain locations, and the intermediate locations (coordinates) are interpolated. I am using

from scipy.interpolate import interp1d

to get help in interpolating, and then

        # build movement timeseries array; [0] is time in seconds (if target_fps = movSpeed), [1:4] are positions X,Y,Z, [4:7] are angles X,Y,Z
        movSpeed = float(movements.findtext("speed", default="1"))
        for timedata in movements.iter('timeseries'):
            mov_times = np.zeros((7, 0))
            mov_point = np.zeros((7, 1))
            for stepdata in timedata.iter('movementstep'):
                #steptime = float(stepdata.get("time"))
                mov_point[0, 0] = float(stepdata.get("time"))
                mov_point[1, 0] = float(stepdata.findtext("movepositionX", default=str(mov_point[1, 0])))
                mov_point[2, 0] = float(stepdata.findtext("movepositionY", default=str(mov_point[2, 0])))
                mov_point[3, 0] = float(stepdata.findtext("movepositionZ", default=str(mov_point[3, 0])))
                mov_point[4, 0] = float(stepdata.findtext("moveangleX", default="0"))
                mov_point[5, 0] = float(stepdata.findtext("moveangleY", default="0"))
                mov_point[6, 0] = float(stepdata.findtext("moveangleZ", default="0"))
                mov_times = np.hstack((mov_times, mov_point))
            # sort by time (first row), just in case ordering is wrong
            mov_times = mov_times[:,mov_times[0,:].argsort()]
            if viewer == "1":
                # for viewer, invert sign of Y coordinate
                mov_times[1,:] = -1 * mov_times[1,:]
            mov.addTimeSeries(mov_times)
            # out of the time series, build frame by frame movement using interpolation. 
            fx = interp1d(mov_times[0,:], mov_times[1:7,:], kind='quadratic')
            # data needed for the whole range of time series. Use speed = "time" per second.
            num_times = int((mov_times[0,-1] - mov_times[0,0]) * vv.target_fps / movSpeed)
            time_frames = np.linspace(mov_times[0,0], mov_times[0,-1], num=num_times, endpoint=True)
            mov_moves = fx(time_frames)

So I am building an array with 7 series; the first for the time, the next three for the coordinates, and the last three for the angles. Then, using the interp1d, I am setting the interpolation function fx (I am using quadratic, but you can experiment with e.g. cubic spline) to get a spline interpolation between them. The whole time series is calculated and stored so that it can be just used later.

For some moving objects, I am happy with rotating them separately of their movement or not at all; but for some, like a moving car, I would like them to "point forwards" i.e. have their angles follow their movement. Also, for the viewer, it would be nice to be able to look forward when moving around. For this purpose, I added the following:

            mov_angleforward = movements.findtext("angleforward", default="off")
            if mov_angleforward != "off":
                # angleforward means that object angles should be such that it is rotated according to movement vector, always facing towards movement
                # NOTE: Tested for Y only! Not well defined for XYZ anyway.
                mov_diffs = mov_moves[0:3,1:] - mov_moves[0:3,:-1]
                mov_diffs = np.hstack((mov_diffs, mov_diffs[:,-1:])) # copy second last diff to last
                if mov_angleforward.find("X") >= 0:
                    mov_moves[3,:] += np.arctan2(mov_diffs[1,:], mov_diffs[2,:]) * 180 / np.pi
                if mov_angleforward.find("Y") >= 0:
                    mov_moves[4,:] += np.arctan2(mov_diffs[0,:], -mov_diffs[2,:]) * 180 / np.pi
                if mov_angleforward.find("Z") >= 0:
                    mov_moves[5,:] += np.arctan2(mov_diffs[0,:], mov_diffs[1,:]) * 180 / np.pi

Basically, if movement item angleforward has value "Y", then the Y angle (angle "around" the vertical axis or "left and right") will be defined by the movement in the plane Y=0, i.e. by the change in X and Z coordinates. It is additional to the angle calculated using the spline; by defining this for Y and using angle 90 for Y in the movement, for instance, one can have the object pointing to its side or the viewer "looking out of the side window." 

I am also changing calculating the shadows (see previous part) slightly to use an intermediate step in rotation, where the objects have been moved and rotated, but still live in a "constant coordinate system" where the plane Y = 0 is the ground. There it is easy to calculate the multiplier for the shadow vector: Let's say the light source position (its Y coordinate) is twice as high as the top of the building: multiplier = 2. Then the shadow of the top of the building will fall at [lightsource position + 2 * (top of building position - lightsource position)]. However, the same multiplier also applies to the positions after they have been rotated to any angle, even if then Y = 0 is not the ground. Applying it to the already rotated positions saves me from rotating the resulting shadow coordinates.

This is what we have. A bigger city, a moving light source object with shading and shadows following its movement, a moving car - and a moving viewer:

Next: Part VIII: Finishing Touches

Real-Time 3D with Python Part VI: Shadows

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, and in Part II added surfaces and perspective. Part III was about calculating object surface visibility and shading. Part IV set up an XML reader to define the objects and other properties using a common file format (XML), and added the code needed to work with multiple objects. In Part V, I added two special features: the ground and roads. Now it is time to add shadows to the objects

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

In the Shadows

With light source shaded objects, shadows add a dose of reality. Of course, in reality, shadows can be extremely complex, so I am going to implement a simplistic approach more suitable for a 1985 home computer (and 2020 Python processing). A shadow will be cast by an object between the ground and the light source, and only to the ground. It would be nice to add a shadow of, say, a building on another building, but that would make the calculations way too complex. In the end, we'll end up with this:

  

Like I explained before, in the original demo rotation was limited to the vertical axis to keep calculations more manageable. With vertical axis rotation only, the ground will always be at Y coordinate zero, which makes calculating shadows based on the rotated object coordinates simple. In the Python code, I have kept the ability to rotate around all three axis, so for the shadow calculations there are two alternatives:

1. project shadows directly on a rotated ground surface using rotated light source coordinates and rotated object coordinates; or
2. project shadows using unrotated coordinates, when ground is at vertical zero, and then rotate the shadow coordinates.

I chose the latter, as it is easier. Solving the shadow coordinates in (1) is quite a bit more difficult, so (2) might also be faster. (See e.g. Programming with OpenGL).

Projecting a shadow of a simple object. Source: York College CS 370

When ground is at zero, projecting the X and Z coordinates is a matter of simple scaling: Xs = Xi + (Xo - Xi) * Yi / (Yi - Yo), and similarly for Z. Ys == 0. (s = shadow, o = object, i = light source.)

But how to define the shadowed surfaces? A simplistic approach would be to calculate and draw a shadow for every surface of the object. This can easily be refined by only drawing a shadow for the surfaces which light falls on, i.e. the surfaces where angleToLightSource > 0 (remember this was defined as np.dot(self.crossProductVector, self.lightSourceVector) for each surface). Another step, assuming the object is "concave" and "whole", is to figure out the combined shadow area of these surfaces, and draw it as a single shadow. The code below does just that:

    def updateShadow(self, viewerAngles, lightNode, vectorPosition, objMinZ, zScale, midScreen):
        """ 
        Update shadowNodes (a list of nodes which define the shadow of the object).
        This routine assumes objects are "whole", that they do not have any holes - such objects should be built as several parts.
        A more resilient way would be to calculate and draw a shadow for each surface separately, but leading to extra calculations and draws.
        Update nodes by calculating and adding the required shadow nodes to the array.
        Note for objects standing on the ground, the nodes where Y=0 are already there and need no calculation / adding.
        """
        obj_pos = -vectorPosition[0:3]  # object position
        shadow_edges = [] # list of object edges that belong to surfaces facing the lightsource, i.e. producing a shadow.
        for surface in (surf for surf in self.surfaces if surf.angleToLightSource > 0 or surf.showBack == 1):
            # add all egdes using the smaller node nr first in each edge node pair.
            shadow_edges.extend([((min(surface.nodes[i], surface.nodes[i-1]), max(surface.nodes[i], surface.nodes[i-1]))) for i in range(len(surface.nodes))])
        # get all edges which are in the list only once - these should define the outer perimeter. Inner edges are used twice.
        use_edges = [list(c[0]) for c in (d for d in list(Counter(shadow_edges).items()) if d[1] == 1)]
        # these edges should form a continuous line (the perimeter of the shadowed object). Prepare a list of nodes required:
        node_list = []
        node_list.append(use_edges[0][0]) # first node from first edge
        node_list.append(use_edges[0][1]) # second node from first edge
        prev_edge = use_edges[0]
        for i in range(len(use_edges)): 
            if node_list[-1] != node_list[0]:
                for edge in use_edges:
                    if edge != prev_edge: # do not check the edge itself
                        if edge[0] == node_list[-1]:
                            node_list.append(edge[1]) # this edge begins with previous node, add its end
                            prev_edge = edge
                            break
                        if edge[1] == node_list[-1]:
                            node_list.append(edge[0]) # this edge ends with previous node, add its beginning
                            prev_edge = edge
                            break
            else:
                break # full circle reached
        node_list = node_list[0:len(node_list) - 1] # full circle - drop the last node (is equal to first)

Note that this code is still a simplified version where only vertical axis rotation is assumed. This will be fixed later.

Above, I first go through all surfaces which are shadowed, and add their edges to a list. This of a simple object - a cube for instance - where three surfaces are shown. The outer six edges belong to only one surface each, but the inner three edges all belong to two surfaces. To get the outer perimeter of the shadowed object, I use Counter to find the edges mentioned in the above list only once. Then, the loop builds a continuous list of perimeter nodes.

Having the nodes, it is time to project them on the ground:

        # then project these nodes on the ground i.e. Y = 0. If necessary. Add the required shadowNodes.
        self.shadowNodes = np.zeros((0, 4))
        for node_num in range(len(node_list)):
            node = node_list[node_num]
            # check that node is not already on the ground level or too high compared to light source
            if obj_pos[1] + self.rotatedNodes[node, 1] > 3 and obj_pos[1] + self.rotatedNodes[node, 1] < (lightNode[1] - 3):
                # node must be projected. Add a shadow node and replace current node in node_list with it.
                node_list[node_num] = self.nodeNum + np.shape(self.shadowNodes)[0]
                diff_node = (obj_pos + self.rotatedNodes[node,:]) - lightNode # vector from lightNode to this node
                self.shadowNodes = np.vstack((self.shadowNodes, np.hstack((lightNode + diff_node * (lightNode[1] / -diff_node[1]) - obj_pos, 1))))
        
        self.shadowRotatedNodes = self.shadowNodes[:,0:3]

When starting, all the nodes used for the shadow are actually object nodes. Projection to ground will only be required if the node is higher than the ground (Y > 0) and lower than the light source. If it is on the ground already, we already have the correct position. If it is at light source height or higher, it's impossible to project it. The buildings stand on the ground, so many of the nodes need no projection at all.

If a node needs to be projected, I create a new shadowNode for it, and change the reference in the node_list so that it will be used later instead of the actual object node. As I am using rotated nodes for shadow calculations, shadowRotatedNodes will equal shadowNodes.

These new shadowRotatedNodes will need to be cropped to objMinZ to prevent trying to apply perspective to something behind the viewer, and then flattened to 2D. In the end I have the shadowTransNodes, a list of 2D nodes for drawing the shadow polygon:

        # flatten rotated shadow nodes and build a list of shadowTransNodes. shadowTransNodes has all shadow nodes.
        flat_nodes = np.zeros((0, 3))
        if node_list[-1] < self.nodeNum:
            prev_node = self.rotatedNodes[node_list[-1], 0:3] # previous node XYZ coordinates
        else:
            prev_node = self.shadowRotatedNodes[node_list[-1] - self.nodeNum, 0:3]
        for node_num in range(len(node_list)):
            if node_list[node_num] < self.nodeNum:
                node = self.rotatedNodes[node_list[node_num], 0:3] # current node XYZ coordinates
            else:
                node = self.shadowRotatedNodes[node_list[node_num] - self.nodeNum, 0:3]
            diff_node = node - prev_node # surface side vector
            # if both Z coordinates behind the viewer: do not draw at all, do not add a transNode
            if (node[2] < objMinZ and prev_node[2] >= objMinZ) or (node[2] >= objMinZ and prev_node[2] < objMinZ):
                # line crosses objMinZ, so add a "crop point". Start from previous node and add difference stopping to objMinZ
                flat_nodes = np.vstack((flat_nodes, prev_node + diff_node * ((objMinZ - prev_node[2]) / diff_node[2])))
            if node[2] >= objMinZ:
                # add current node, if it is visible
                flat_nodes = np.vstack((flat_nodes, node))
            prev_node = node
        # apply perspective using Z coordinates and add midScreen to center on screen to get to transNodes
        self.shadowTransNodes = (-flat_nodes[:, 0:2] * zScale) / (flat_nodes[:, 2:3]) + midScreen

With the above, actually drawing the shadows is simple. This is done, for each object priority class, so that first all shadows are drawn, and then the objects - ensuring that shadows are behind the objects and not vice versa.

            # draw shadows always first for all visible objects
            for VectorObj in (vobj for vobj in self.VectorObjs if vobj.visible == 1 and vobj.prio == prio_nr and vobj.shadow == 1):
                node_list = self.cropEdges(VectorObj.shadowTransNodes)
                self.drawPolygon(self.shadowColor, node_list, 0)

Note that the VectorObject.shadow attribute is defined in the XML and should, obviously, be set to zero (no shadow) for roads, the light source object etc.

Buffering...

For those not from the ice age like me but used to video streaming, buffering means that you have to wait for something. For real-time graphics, it means one has to draw "in the buffer" and not directly on the screen being shown; otherwise the picture would show up half-finished. In Python pygame this is supported by a simple display.flip() operation. On the Amiga, triple buffering was commonly used. Triple buffering works by setting up three identical screens (collections of bitplanes). Let's say we draw the first image on #1. Immediately after we are finished, we start drawing on #2, and then, again when finished, on #3, and then start from #1 again. So the whole time is spent drawing, not waiting for any specific time to switch screens, unless we can draw screens faster than the display frame rate (on a PAL Amiga, 50Hz). What to show then? We always have two finished screens, and one we are working on. That's because we cannot switch the screen shown in the middle of display refresh - we would end up showing half of, say, #1 and half of #2! That's why we need two finished screens: we can wait for display refresh to finish, and then switch to the other finished screen (well, not actually wait - there's an interrupt that kicks in at the right moment). (Nowadays there are hardware solutions for the same problem.)

So are we all right with three screens on the Amiga? Unfortunately not - we need a fourth one as a temporary "drawing board" as objects cannot be drawn and filled in on the actual screen, as this would mess up the filling operation. Luckily, there's a massive 512kB of chip RAM to put these all in... how much memory do we need? A simple calculation is required: Our screen is 352 pixels (bits) wide: 352 / 8 = 44 bytes. It is 288 pixels (lines) high, so one bitplane is 44 x 288 = 12.4kB. Let's say we work with the full 32 colors, and hence need five bitplanes for one screen = 62kB. Triple buffering and one drawing board, four times that = 248kB. Whoa - we have already used half of all RAM available! The rest is then for program code, music, any bitmap graphics etc... 

The programmers those days needed to be really good at using the scarce resources. Although, their predecessors were even better with the mighty Commodore 64. Not to mention VIC-20 with 5kB of RAM... give that to some of today's programmers!  

Next: Part VII: Movement.