In a world of 48 KB, 2D platform games, Knight Lore represented a quantum leap forward with its strikingly realistic 3D world based on isometric perspective. Ultimate called this rendering technique Filmation. I used to wonder how they could implement Filmation in such a limited computer as the ZX Spectrum, but the math behind it turns out to be simpler than it might seem.
A given room consists of a background set (the stone walls in the example above) and a bunch of objects. We can assume that the objects are roughly convex: if an object is not convex, for instance if it has holes like the arched gateways, we can just decompose it into a number of convex elements.
Since isometric perspective does not introduce any scaling effect (distant objects are drawn the same size as closer ones), rendering a frame boils down to drawing the background set and then all the room objects, applying a simple projection rule:
(x,y,z) → (x0 + √3 x/2 − √3 y/2, y0 − x/2 − y/2 + z)
which is generally approximated by the following:
so as to simplify computations as well as graphic design (the x and y axes are projected to easily pixelizable lines wih slope 1/2). But there is one detail left: if an object A appears behind B, we must draw A before we render B. So, room objects have to be ordered for drawing purposes according to the "is behind" relation. In which situations is A behind B? As objects are assumed to be convex and they do not overlap (i.e. A∩B = ∅), we can approximate them by prisms with opposite vertices (xA,yA,zA), (x'A,y'A,z'A) and (xB,yB,zB), (x'B,y'B,z'B), with xA<x'A, yA<y'A, zA<z'A, and similarly for B. These prisms are projected to hexagons as depicted in the figure:
A little calculation shows that the hexagons for A and B overlap if and only if:
- [xA−y'A,x'A−yA] and [xB−y'B,x'B−yB] overlap, and
- [xA−z'A,x'A−zA] and [xB−z'B,x'B−zB] overlap, and
- [−y'A+zA,−yA+z'A] and [−y'B+zB,−yB+z'B] overlap.
If the hexagons do not overlap, it is immaterial which object we draw first; if they do overlap, we can apply the following easily provable properties:
- x'A < xB → A is behind B,
- x'B < xA → B is behind A,
- y'A < yB → A is behind B,
- y'B < yA → B is behind A,
- z'A < zB → A is behind B,
- z'B < zA → B is behind A.
Since the prisms A and B do not overlap (in 3D), it can be seen that at least one of the clauses 1-6 can be applied, so we can use these properties to sort all the room objects and then proceed to drawing. Note that the relation "is behind" defined by the algorithm above is not total: if the projections of two blocks do not intersect, then neither block is behind the other; thus, in general blocks can be sorted in more than one acceptable manner.
Are we done then? It looks so, and actually a rendering algorithm can be implemented along these lines and seemingly works fine. But there is a fundamental flaw in our analysis. The relation "is behind" is not transitive:
In the figure, A is behind B, B is behind C and C is behind A! There is no way that these objects can be sorted so that they are rendered properly; if we wish to keep our basic algorithm, at least one of the objects should be split in two so as to restore transitivity, but knowing when and how to do this is not trivial. How did Ultimate programmers solve this problem? Well, the answer is that they did not solve it. Consider for instance the following snapshot, taken from Nigel Barford's Java Spectrum Emulator:
One table is on top of the other and slightly displaced with respect to it. If we position our hero so that he stands behind the bottom table and in front of the top one, something unexpected happens:
The top table is suddenly rendered as if it were behind the bottom table: if you examine this configuration you will see that we have indeed an antitransitive cycle composed of the two tables and the main character. As these situations are uncommon, the programmers of the Filmation engine decided to just ignore them. So, next time you play a Filmation game and observe one of these rendering quirks, you will know the math behind them.