## Nov 22, 2020

### 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...

## Apr 25, 2020

### 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.

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
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_blends.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, disp_size, music_file, font_size)

# start music player
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
for VectorObj in (vobj for vobj in self.VectorObjs if vobj.visible == 1 and vobj.prio == prio_nr and vobj.shadow == 1):
else:
# blit the "multiplied" screen copy to add shadows on main screen
# release any locks on screen
while self.screen.get_locked():
self.screen.unlock()
# clear the surface copy after use back to "all white"
```

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.

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.)

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:
elif loop_pos > VectorMovement.loopEnd - 255 / self.fadeSpeed:
else:
```

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...

## Apr 13, 2020

### 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;  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,:]
# out of the time series, build frame by frame movement using interpolation.
# 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:

## Apr 5, 2020

### 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.

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) for c in (d for d in list(Counter(shadow_edges).items()) if d == 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) # first node from first edge
node_list.append(use_edges) # second node from first edge
prev_edge = use_edges
for i in range(len(use_edges)):
if node_list[-1] != node_list:
for edge in use_edges:
if edge != prev_edge: # do not check the edge itself
if edge == node_list[-1]:
node_list.append(edge) # this edge begins with previous node, add its end
prev_edge = edge
break
if edge == node_list[-1]:
node_list.append(edge) # 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.
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 + self.rotatedNodes[node, 1] > 3 and obj_pos + self.rotatedNodes[node, 1] < (lightNode - 3):
# node must be projected. Add a shadow node and replace current node in node_list with it.
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 / -diff_node) - obj_pos, 1))))

```

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 < objMinZ and prev_node >= objMinZ) or (node >= objMinZ and prev_node < 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) / diff_node)))
if node >= 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):
```

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!

## Mar 29, 2020

### Real-Time 3D with Python Part V: Ground and Roads

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 this part, I add two special features: the ground and roads.

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.

### Going Somewhere

The cityscape in the previous part is floating in a void of black, empty space. To make it look more realistic, we need to show the ground and add some roads. I will cover the roads first. In the original demo (see introduction) the roads seem to stretch to infinity, and that is the effect I am after here, too. For infinity, "far enough" will do just fine; I have defined the coordinates so that the roads go to ±48,000 when the city in general sits within ±1,000.

There are two problems with using the road objects: (1) they very often have nodes (corner points) both behind and in front of the viewer, causing an issue with the perspective (scaling using the Z coordinate), and (2) sorting objects using their midpoint Z coordinate does not guarantee the correct drawing order, as the roads are so long. Hence, I am adding two new attributes to the Vectorobject class:

```        self.isFlat = 0
self.prio = 0                                       # priority order when drawn. Highest prio will be drawn first
```

The isFlat attribute is set to 1 when the object is created if it has only one surface. Then, before flattening from 3D to 2D and drawing it, the surface is cropped in 3D to the positive side of objMinZ (which is set to 100) in Z coordinates:

```        if self.isFlat == 1:
# for flat objects, build a list of transNodes for the surface by first cropping the necessary surface sides to minZ
for surface in self.surfaces:
surface.setVisible(1) # set all surfaces to "visible"
flat_nodes = np.zeros((0, 3))
for node_num in range(len(surface.nodes)):
node = self.rotatedNodes[surface.nodes[node_num], 0:3] # current node XYZ coordinates
prev_node = self.rotatedNodes[surface.nodes[node_num - 1], 0:3] # previous node XYZ coordinates
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 < objMinZ and prev_node >= objMinZ) or (node >= objMinZ and prev_node < 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) / diff_node)))
if node >= objMinZ:
# add current node, if it is visible
flat_nodes = np.vstack((flat_nodes, node))
# apply perspective using Z coordinates and add midScreen to center on screen to get to transNodes
self.transNodes = (-flat_nodes[:, 0:2] * zScale) / (flat_nodes[:, 2:3]) + midScreen
```

After cropping, applying perspective can be done the usual way by dividing X and Y with the Z coordinate.

The prio attribute is also set when creating the objects and can be defined in the XML file for each object. It is used is a simple way so that the higher prio objects will be drawn before anything with a lower prio, and sorting for the drawing order happens within each prio class separately. By giving the roads a higher priority than for the buildings, for instance, will make sure the roads are drawn first and the buildings after them. Otherwise the roads might appear to overlap the buildings.

If you look at the original demo, the roads should nicely vanish into the horizon, but for now they are just drawn in one constant color. This will be fixed in Part VIII.

### Ground Control

The ground will be blue and nicely faded to black in the horizon. However, it will not be fixed; the fading will depend on the height of the viewer, and in the Python code I want to preserve the ability to rotate in true 3D, unlike the original purely vertical axis rotation. For this purpose I created a special ground object. There is not much special about the object itself - it is a flat square at ground level, just providing the information on rotation - but it is handled by custom code.

First, using the ground object rotated nodes, I want to find out a 3D square on that surface that has Z coordinates at either groundZ or -groundZ; this will make the fading work as intended with distance.

```    def groundData(self, midScreen, zScale, objMinZ, groundZ, groundShades, groundShadeNr):
"""
Calculate ground data for on a ground object.
Assumes the ground object "covers the ground" reasonably and isFlat = 1, and the perimeter is concave.
Ground settings are defined in VectorViewer.
Returns an array of shape(groundShadeNr + 1, 4) where each row has X,Y of left edge and X.Y of right edge starting from most distant
"""
# find the most distant node
maxZ = max(self.rotatedNodes[:, 2])
for nodenum in range(len(self.nodes)):
if self.rotatedNodes[nodenum, 2] == maxZ:
node = self.rotatedNodes[nodenum, :]
break
prev_node = self.rotatedNodes[nodenum - 1, :]
if nodenum == len(self.nodes) - 1:
next_node = self.rotatedNodes[0, :]
else:
next_node = self.rotatedNodes[nodenum + 1, :]

# get a straight line where Z (ie, distance from viewer) is constant. Start with the mid of farthest of the two lines.
# then find the point with matching Z coordinate on the other line.
# special cases: next_node or prev_node as far as node.
if node == prev_node:
mid1_node = node
mid2_node = prev_node
else:
if node == next_node:
mid1_node = node
mid2_node = next_node
else:
if next_node > prev_node:
mid1_node = (next_node + node) / 2
mid2_node = node + (prev_node - node) * (mid1_node - node) / (prev_node - node)
else:
mid1_node = (prev_node + node) / 2
mid2_node = node + (next_node - node) * (mid1_node - node) / (next_node - node)
if mid1_node < mid2_node:
# make sure mid1_node X < mid2_node X
mid1_node, mid2_node = mid2_node, mid1_node
mid1_node = mid1_node * groundZ / mid1_node
mid2_node = mid2_node * groundZ / mid2_node
# finalize a square around object position
mid2_node_back = self.position[0:3] + (self.position[0:3] - mid1_node) # from front left (mid1) to back right (mid2_back)
mid1_node_back = self.position[0:3] + (self.position[0:3] - mid2_node) # from front right (mid2) to back left (mid1_back)
```

Then, having this 3D square, I will generate groundShadeNr (defined in VectorViewer class) slices of ground, the most distant being first. When drawing these in preset colors the fading effect will be accomplished. I am using 16 shades - on the Amiga 15 was the maximum - the more you use, the better the quality, and the slower the drawing. The nodes needed for the slices  (groundShadeNr + 1 nodes) are also cropped to screen X coordinates, as the ground is very large and usually overlaps the screen by a lot.

```       # then generate arrays with necessary node data and transNode data
left_nodes = np.zeros((groundShadeNr + 1, 3), dtype=float)
right_nodes = np.zeros((groundShadeNr + 1, 3), dtype=float)
# multipliers will span ground component span between groundZ/2 (furthest) and objMinZ
mult = (mid1_node / 2 - objMinZ) / ((mid1_node - mid1_node_back) / 2)
# the most distant component (at groundZ). Most distant component will be very large (half of total)
left_nodes[0,:] = mid1_node
right_nodes[0,:] = mid2_node

# other components from groundZ/2 to objMinZ
mult_i =  mult * math.sqrt((i+1) / groundShadeNr)
left_nodes[i+1,:] = (mid1_node * (1.0 - mult_i) + mid1_node_back * mult_i) / 2
right_nodes[i+1,:] = (mid2_node * (1.0 - mult_i) + mid2_node_back * mult_i) / 2
left_transNodes = (-left_nodes[:, 0:2] * zScale) / (left_nodes[:, 2:3]) + midScreen
right_transNodes = (-right_nodes[:, 0:2] * zScale) / (right_nodes[:, 2:3]) + midScreen

# crop these nodes to screen X edges
diff_transNodes = right_transNodes - left_transNodes
mult_nodes = right_transNodes[:, 0] / diff_transNodes[:, 0]
left_transNodes = right_transNodes - np.multiply(np.transpose(np.vstack((mult_nodes, mult_nodes))), diff_transNodes)
diff_transNodes = right_transNodes - left_transNodes
mult_nodes = (midScreen * 2) / diff_transNodes[:,0]
right_transNodes = left_transNodes + np.multiply(np.transpose(np.vstack((mult_nodes, mult_nodes))), diff_transNodes)

# the first component is "the top of the sky".
if left_transNodes[0,1] < left_transNodes[1,1]:
# "normal ground", add a node to the top of the screen
if left_transNodes[0,1] < 0:
# if ground already covers the whole screen, use the top node
left_skynode = left_transNodes[0,:]
else:
left_skynode = np.array([0, 0])
else:
# inverted ground ie. going upside down, add a node to the bottom of the screen
if left_transNodes[0,1] > midScreen * 2:
# if ground already covers the whole screen, use the top node
left_skynode = left_transNodes[0,:]
else:
left_skynode = np.array([0, midScreen * 2])
if right_transNodes[0,1] < right_transNodes[1,1]:
# "normal ground", add a node to the top of the screen
if right_transNodes[0,1] < 0:
# if ground already covers the whole screen, use the top node
right_skynode = right_transNodes[0,:]
else:
right_skynode = np.array([midScreen * 2, 0])
else:
# inverted ground ie. going upside down, add a node to the bottom of the screen
if right_transNodes[0,1] > midScreen * 2:
# if ground already covers the whole screen, use the top node
right_skynode = right_transNodes[0,:]
else:
right_skynode = midScreen * 2
# add the first component and build an array of all the transnodes
transNodes = np.vstack((np.hstack((left_skynode, right_skynode)), np.hstack((left_transNodes, right_transNodes))))
```

Since the ground is the first object to be drawn - it has the highest prio - and usually covers about half of the screen, I am also adding an extra component; see "the top of the sky" in the above code. By adding the part of the screen not covered by the ground, I can skip clearing the screen altogether. In effect I am only clearing the part that will not be overwritten by the ground anyway, in an effort to save some time.

### Size Does Matter

With the new, big objects ground and roads, they will certainly be stretching outside of our screen. I already used cropping with the Z coordinate above, and now I am adding code to crop also X and Y transNodes i.e. 2D screen coordinates to fit the screen, so that we will not try to draw anything outside of the viewing area. The code below goes through a list of polygon nodes and makes the necessary deletions and modifications. It also converts the list of nodes to integer values.

```    def cropEdges(self, node_list, cropX = True, cropY = True):
# crop to screen size. "Auto crop" does not seem to work if points very far outside.
# takes list of nodes (X,Y) in drawing order as input.
# returns list of nodes (X,Y) cropped to screen edges.
# crop both X, Y, if cropX and cropY = True; X: i=0, Y: i=1
if len(node_list) > 2:
for i in range(2):
if (i == 0 and cropX == True) or (i == 1 and cropY == True):
crop_nodes = [] # empty list
prev_node = node_list[-1]
for node in node_list:
diff_node = node - prev_node # surface side vector
# start cropping from prev_node direction, as order must stay the same
if node[i] >= 0 and prev_node[i] < 0:
# line crosses 0, so add a "crop point". Start from previous node and add difference stopping to 0
crop_nodes.append(prev_node + diff_node * ((0 - prev_node[i]) / diff_node[i]))
if node[i] <= self.midScreen[i] * 2 and prev_node[i] > self.midScreen[i] * 2:
# line crosses screen maximum, so add a "crop point". Start from previous node and add difference stopping to midScreen[i] * 2
crop_nodes.append(prev_node + diff_node * ((self.midScreen[i] * 2 - prev_node[i]) / diff_node[i]))
# then crop current node
if node[i] < 0 and prev_node[i] >= 0:
# line crosses 0, so add a "crop point". Start from previous node and add difference stopping to 0
crop_nodes.append(prev_node + diff_node * ((0 - prev_node[i]) / diff_node[i]))
if node[i] > self.midScreen[i] * 2 and prev_node[i] <= self.midScreen[i] * 2:
# line crosses screen maximum, so add a "crop point". Start from previous node and add difference stopping to midScreen[i] * 2
crop_nodes.append(prev_node + diff_node * ((self.midScreen[i] * 2 - prev_node[i]) / diff_node[i]))
# always add current node, if it is on screen
if node[i] >= 0 and node[i] <= self.midScreen[i] * 2:
crop_nodes.append(node)
prev_node = node
# for next i, copy results. Quit loop if no nodes to look at
node_list = crop_nodes
if len(node_list) < 3:
break
# convert to integers
node_list = [(int(x + 0.5), int(x + 0.5)) for x in node_list]
return node_list
```

Now the end result looks like this:

### To Blit or not to Blit?

On the Amiga, the Blitter co-processor is capable of drawing lines between the given coordinates. In addition, it has a special mode that only sets one bit (i.e. draws one pixel) per horizontal line. This comes in handy when combined with the Blitter fill operation, which will go through each horizontal line in an area bit by bit, and each time it encounters a bit that is set, it will turn area fill mode on if it was off, and off if it was on. So, by drawing the edges of a square using the special mode, it possible to fill that square with the fill operation.

Remember that the Amiga uses bitplane graphics so that one can choose the depth - the number of bitplanes - of the screen freely between one and five (special modes have six) and the number of colors available is two to the power of that, so with five bitplanes one gets 2^5 = 32 colors. If I needed a rotating cube, for example, like in Part III, I would only need three colors as that's the maximum number of surfaces drawn simultaneously. Obviously, I also need one color for the background. These four colors can be defined with two bitplanes. For any one pixel, the first bitplane defines the least significant bit of the color used, and the second bitplane the next bit. So, if both bitplanes are cleared, I would have color 00 (binary) = 0 (decimal) - this is the background. If I only draw a filled surface on the first bitplane, it will have color 01 = 1, and if only on the second bitplane, color 10 = 2. If both bitplanes are filled, the color is 11 = 3.

How to actually draw this on the Amiga then? To be efficient, the best way is not to draw the surfaces one by one, like the Python code and it's pygame.draw.polygon do. It's more efficient to first figure out for each edge of the cube if it needs to be drawn or not. For our cube, let's say there are three surfaces (1, 2 and 3) to be drawn, and we have defined that they will have colors 1, 2 and 3, respectively. The colors needed (in binary) will then be 01, 10, and 11. Furthermore, both surfaces 1 and 2 will have one edge in common with surface 3. In practice, then, I need to fill the area of surfaces 1 and 3 on bitplane 1, and the area of surfaces 2 and 3 on bitplane 2. So, instead of drawing and filling each surface with four operations (surface 1 on biplane 1, s. 2 on 2, s. 3 on 1, and s. 3 on 2) it will be much more efficient to draw the common boundaries of surfaces 1 and 3 on bitplane 1 and then fill it in one blitter fill operation, and then the common boundaries of surfaces 2 and 3 on bitplane 2 and then fill that in another blitter fill operation. In addition, the fill operation needs a "virgin" bitplane to work properly; trying to draw and fill a surface next to another already drawn and filled would mess up the second fill operation. Figuring out which edges need to be drawn in which colors is actually very simple by using an XOR logical operation on the edge colors with each surface drawn.

With multiple objects on top of each other, it is necessary to have separate bitplanes for drawing the next object, and then copy that to the main bitplanes on top of the other objects, again using the blitter.