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:
- project shadows directly on a rotated ground surface using rotated light source coordinates and rotated object coordinates; or
- project shadows using unrotated coordinates, when ground is at vertical zero, and then rotate the shadow coordinates.
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)
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.
No comments:
Post a Comment