SQ in silver chrome letters, a lab's gear stacked against the S: a rack, two oscilloscopes, pizza boxes and a six-pack. Strange Query Lab

CARDIAC › rust-cardiac › Demos › Voxel processing

Voxel processing on CARDIAC

Leveraging rust-cardiac for classic Comanche-style voxels

Crater Lake from its south rim, in pixels: on the left the rim's high ground, in the middle the forested caldera wall curving down to deep blue water, and on the right Wizard Island and the lake reaching to the far rim.

Voxel space is a terrain-rendering technique popularised by NovaLogic's Comanche (1992). Rather than building the landscape from polygons, it renders a height map, a greyscale image of the terrain seen from above in which brightness encodes elevation. The scene is processed in strips perpendicular to the view direction, beginning near the camera and proceeding toward the horizon. Each strip is projected onto the screen one column at a time, and a column is drawn only where the projected terrain rises above what has already been drawn in front of it, so nearer terrain occludes farther terrain. The method requires only addition, multiplication and a single division per column, which makes it a plausible workload for a machine as limited as CARDIAC.

This article adapts the technique to CARDIAC. The image above shows Crater Lake in Oregon from its south rim, rendered from real elevation data as three 96 by 96 pixel views placed side by side. CARDIAC computes every pixel, including each point's screen position, its terrain class and its shading. The program is written in Rust and compiled with rust-cardiac rather than written directly in CARDIAC assembly, because the algorithm is considerably easier to follow as a short Rust program than as the 87 cells of CARDIAC it compiles to. Later sections place the two side by side.

Who does what

CARDIAC can't draw anything. It reads cards and outputs numbers. So the work is split the way a game splits it between a graphics chip and the rest of the program. A small shell script plays the host. It reads a height map, a picture of the land seen from above where brighter means higher. It slices the view into 120 strips, from right in front of the camera out toward the far rim, and for each strip it hands CARDIAC the land under each of the screen's 96 columns. CARDIAC hands back the screen row where that land shows up, and a colour code that says what the land is and how brightly it's lit. That's the 3D part, the perspective and the light, and it all happens on CARDIAC. The script then puts those answers on the screen, near strips first so that hills hide what's behind them, looking each colour code up in a fixed table the way a display's palette does. It adds nothing of its own to the picture except a plain sky.

Three pictures, three inputs

Here are the three pictures on their own, as CARDIAC drew them. They come from the same height map, with the camera in the same spot on the rim, at the same height, with the same lens. The only difference is which way it faces. Each picture covers 53 degrees across, so turning by exactly 53.1 degrees makes one picture start where the last one ended, and Wizard Island carries on across the join.

The rim's high ground to the west, with snow on its highest point.
LOOK=281.9
The caldera wall curving down to the lake, with the front of Wizard Island at the right edge.
LOOK=335
The rest of Wizard Island, and the lake reaching to the far eastern rim.
LOOK=28.1
MAP=craterlake.pgm CAMX=69.5 CAMY=170 CAMZ=140 ZOOM=2 HORIZON=30 BANK=0 \
  NEAR=0.5 FAR=165 WATER=0 FLAT=1 PALETTE=mountain LOOK=335 sh voxel.sh

The height map

The Crater Lake height map from above: a dark flat lake in a bright ring of caldera rim, a red square for the camera on the south rim, and white lines fanning out across the lake toward the north, short near the camera and longer farther out.

This is the input, craterlake.pgm, drawn as the image it is. It's a plain greyscale picture, 256 pixels on a side, where each pixel is 66 metres of ground and its brightness is the height, from 1,598 metres for black to 2,701 metres for white. The lake is the big flat dark patch, perfectly level in the data, which is how the script knows it's water. The red square is the camera on the south rim, and the white lines are every tenth strip of the middle picture, the land that one run of the program gets. Near the camera the strips are short and close together, so the foreground gets lots of detail. Farther out they get wider and farther apart, so the far rim comes out coarser, the same way it would in a real flight game.

The heights are real. They come from the AWS Terrain Tiles, which are built from US Geological Survey and NASA elevation data, cut to 256 by 256 and scaled to the 0 to 255 of a greyscale image. The file's comments say how many metres a pixel is and which heights it spans, so the script can draw the land exactly as steep as it really is.

From the height map to a strip of cards

The script turns the map into strips before CARDIAC sees any of it. Each strip is a line straight across the view, a little farther out than the one before, and the script picks 96 evenly spaced points along it, one for each column of the screen. At each point it looks up the land: its height, scaled to 0 to 49, and its colour, which comes from the height (water, forest, meadow, rock or snow). It packs the two into one card, ten times the height plus the colour. Then come two more cards, the height a little to the left of the point and a little to the right, which CARDIAC uses to work out the light. Ahead of all that goes the row where the horizon crosses the column.

So the deck for one strip is the strip's distance, the camera's height, and then four cards for each of the 96 columns. That's 386 cards, and it's all CARDIAC needs to know about the world. Heights only go up to 49 because of what a card holds. The program works with 20 times the difference between the camera and the land, and that has to fit between -999 and 999. Here's the part of the script that writes one strip's deck, in awk:

printf "%d %d", d, camera
for (col = 0; col < 96; col++) {
  x = (col - 48) * d / 48 / zoom           # across: as wide as the strip is far
  land(x - 2 * u, d); left = h             # the height a little to the left,
  land(x + 2 * u, d); right = h            # and a little to the right
  land(x, d)                               # sets h, the height, and c, the colour
  printf " %d %d %d %d", horizon, 10 * h + c, left, right
}

The program

Here's the whole thing. It reads the strip's distance and the camera's height, then reads one column at a time, four cards each, and outputs two numbers back. A point that's below the camera shows up below the horizon, and the farther away it is, the closer to the horizon it lands. CARDIAC has no divide instruction, so the program divides by subtracting, a row at a time, which also stops at the edge of the screen on its own. The light is how much the land rises from left to right. The sun is low on the left, so land rising to the right faces it and is lit brightly, and land falling away is in shade.

voxel.rs

use cardiac::*;

fn main() {
    let d = inp();
    let camera = inp();
    for _ in 0..96 {
        let horizon = inp();
        let cell = inp();
        let left = inp();
        let right = inp();
        let height = cell / 10;
        let colour = cell % 10;
        let mut row = horizon;
        let below = camera - height;
        if below >= 0 {
            // below the horizon: a row down for each d in 20 (camera - h), stopping at the bottom
            let mut n = below * 20 - d;
            while n >= 0 && row < 96 {
                n -= d;
                row += 1;
            }
        } else {
            // above it: a row up for each d in 20 (h - camera), stopping at the top
            let mut n = -below * 20 - d;
            while n >= 0 && row >= 1 {
                n -= d;
                row -= 1;
            }
        }
        // the light: how much the land rises from left to right, held to -2..2, and moved up to 0..4
        let mut light = right - left + 2;
        if light < 0 {
            light = 0;
        }
        if light > 4 {
            light = 4;
        }
        out(row);
        out(colour * 10 + light);
    }
}

Many of these lines ask for something CARDIAC doesn't have. CARDIAC can add, subtract, shift, and test whether the accumulator is negative, and that's all. Line 22 divides and line 23 takes a remainder. Line 28 multiplies by 20, line 50 multiplies by 10, and line 35 negates a value. Line 17 is a range loop with a counter. Line 29 joins two tests with &&, and one of them, row < 96, compares with a number other than zero, as row >= 1 on line 36 and light > 4 on line 46 do too. The tests on lines 26 and 43 only ask whether a value is negative, and those are the only ones CARDIAC can do in a single instruction. Every value is also an i16, which in Rust can go up to 32767, while a CARDIAC cell holds -999 to 999.

rustc checks the program before cargo-cardiac ever sees it, the same way it checks any Rust. Every value here is an i16, because that's what inp() returns, and rustc won't let it mix with another type without a cast. A variable can only change if it's declared mut, and nothing can be read before it's set. cargo-cardiac adds one rule of its own, which is Rust's rule about constants moved to the size of a card. A constant past 999, like 1010 or 101 * 10, is refused at compile time. None of these checks costs CARDIAC a cell, because they all happen before the program exists.

The inp() and out() calls on lines 15 to 21, 49 and 50 come from the cardiac crate, which line 12 brings in. On CARDIAC each one is a single INP or OUT instruction, straight into or out of the variable's own cell. With cargo run the same program reads numbers from standard input and prints what it outputs, one per line, so the native build and the CARDIAC build can be given the same input and compared. The native out() panics if it's given a value that couldn't be on a card.

The build below says it uses the dev profile, which normally checks every add, subtract and multiply for overflow. The listing has none of those checks, because rust-cardiac turns them off for its examples. They would cost 47 more cells. With them voxel comes to 134 cells, and CARDIAC only has 96 for a program.

Building it also writes voxel.map, the panic map. It sits beside the deck the way a .pdb sits beside an .exe, and CARDIAC never reads it. It says where the program's panic routine is, where each function starts, and where each check is, with the message Rust would give for it. On CARDIAC a panic outputs -999 and halts, and that's all the machine shows. When burn finds a map beside the deck, it works out which check led to the halt, prints the function and the message the way Rust does, and exits with 101 as cargo run would. It doesn't give a line number. voxel's map has a single line, fn 1 3 main, which says that main starts at cell 03. There's nothing else in it, because voxel has no arrays to check the bounds of, no assert!, and no overflow checks in this build, so nothing in it can panic. The collatz example in the same repository is built with overflow checks on, and it shows what a failed check looks like when 3n + 1 climbs past 999.

$ burn collatz.cqb 700
700
350
175
526
263
790
395
-999
     halted after 5107 instructions
burn: collatz.cqb: panicked in main: the value doesn't fit on a card (-999 to 999)

Compiling it

cargo-cardiac builds it with cargo. Asking for a listing as well as the deck gives you the program in CARDIAC's six columns: the cell, what's in it, a label, the instruction, its address, and a comment.

$ cargo cardiac build --bin voxel --emit deck,listing,map
   Compiling examples (1 program, cardiac-unknown-none, dev profile)
voxel.rs: 1 phase, 87 cells

That writes voxel.cqb, the deck, voxel.map, its panic map, and voxel.cq, the listing. Here's the listing, all 87 cells of it. Each cell is named after the Rust variable it holds, and the comments are the compiler's: each one shows the line of Rust that the instruction came from. A name like _12 is a value the compiler made along the way, which has no name in the source. When two variables share a cell, the cell takes the first one's name, and its line says which others it holds.

Start at 03.

03    077  main_bb0   INP  d          inp()
04    078             INP  camera     inp()
05    079  main_bb31  INP  horizon    inp()
06    082             INP  cell       inp()
07    080             INP  left       inp()
08    081             INP  right      inp()
09    182             CLA  cell
10    401             SFT  01         height = cell / 10
11    683             STO  height
12    182             CLA  cell
13    433             SFT  33         cell = cell % 10
14    682             STO  cell
15    178             CLA  camera
16    783             SUB  height     height = camera - height
17    683             STO  height
18    355             TAC  main_bb15
19    283             ADD  height
20    410             SFT  10
21    777             SUB  d          n = _12 - d
22    683             STO  height
23    183  main_bb9   CLA  height
24    328             TAC  main_bb22
25    179             CLA  horizon
26    786             SUB  k96        if horizon < 96
27    348             TAC  main_bb11
28    181  main_bb22  CLA  right
29    780             SUB  left       _25 = right - left
30    287             ADD  k2         light = _25 + 2
31    680             STO  left
32    374             TAC  main_bb23
33    788             SUB  k5         if light > 4
34    337             TAC  main_bb28
35    189             CLA  k4
36    680             STO  left       light = 4
37    579  main_bb28  OUT  horizon    out(...)
38    182             CLA  cell
39    410             SFT  10
40    280             ADD  left       _32 = _33 + light
41    679             STO  horizon
42    579             OUT  horizon    out(...)
43    184             CLA  iter_0
44    200             ADD  00         iter_0 = iter_0 + 1
45    684             STO  iter_0
46    305             TAC  main_bb31
47    900             HRS  00         return from main
48    183  main_bb11  CLA  height
49    777             SUB  d          n = n - d
50    683             STO  height
51    179             CLA  horizon
52    200             ADD  00         horizon = horizon + 1
53    679             STO  horizon
54    823             JMP  main_bb9   goto
55    185  main_bb15  CLA  k0         _19 = -height
56    783             SUB  height
57    683             STO  height
58    283             ADD  height
59    410             SFT  10
60    777             SUB  d          n_2 = _18 - d
61    683             STO  height
62    183  main_bb16  CLA  height
63    328             TAC  main_bb22
64    179             CLA  horizon
65    700             SUB  00         if horizon >= 1
66    328             TAC  main_bb22
67    183             CLA  height
68    777             SUB  d          n_2 = n_2 - d
69    683             STO  height
70    179             CLA  horizon
71    700             SUB  00         horizon = horizon - 1
72    679             STO  horizon
73    862             JMP  main_bb16  goto
74    185  main_bb23  CLA  k0
75    680             STO  left       light = 0
76    837             JMP  main_bb28  goto
77    000  d          DATA 000
78    000  camera     DATA 000
79    000  horizon    DATA 000        also row   ; also t1 (never live at once)
80    000  left       DATA 000        also light (never live at once)
81    000  right      DATA 000
82    000  cell       DATA 000        also colour
83    000  height     DATA 000        also below   ; also n, n_2, t0 (never live at once)
84   -096  iter_0     DATA -096
85    000  k0         DATA 000
86    096  k96        DATA 096
87    002  k2         DATA 002
88    005  k5         DATA 005
89    004  k4         DATA 004
001122334455667788990000101ldr02ldr03INP04INP05INP06INP07INP08INP09CLA10SFT11STO12CLA13SFT14STO15CLA16SUB17STO18TAC19ADD20SFT21SUB22STO23CLA24TAC25CLA26SUB27TAC28CLA29SUB30ADD31STO32TAC33SUB34TAC35CLA36STO37OUT38CLA39SFT40ADD41STO42OUT43CLA44ADD45STO46TAC47HRS48CLA49SUB50STO51CLA52ADD53STO54JMP55CLA56SUB57STO58ADD59SFT60SUB61STO62CLA63TAC64CLA65SUB66TAC67CLA68SUB69STO70CLA71SUB72STO73JMP74CLA75STO76JMP77d78camera79horizon80left81right82cell83height84iter_0850869687288589490919293949596979899ret

Reading the cards (03-08)Height, colour and below (09-18)Below the horizon (19-27, 48-54)Above the horizon (55-73)The light (28-36, 74-76)Output (37-42)Loop count and stop (43-47)VariablesConstants, by value00 holds 001, 01-02 the loader, 99 the return addressFreeShared by five values

How the compiler laid voxel out in CARDIAC's 100 cells, with the code coloured by the part of the Rust it came from.

Rust compilation notes

A divide and a remainder in the Rust. CARDIAC has neither, but its shift works in decimal, so the compiler makes each one a single SFT.

voxel.rs

let height = cell / 10;
let colour = cell % 10;

voxel.cq

voxel.rs:22
09    182             CLA  cell
10    401             SFT  01         height = cell / 10
11    683             STO  height
voxel.rs:23
12    182             CLA  cell
13    433             SFT  33         cell = cell % 10
14    682             STO  cell

A multiply. The compiler sees the 20 and makes it an add and a shift: the value doubled, then moved one place.

voxel.rs

let mut n = below * 20 - d;

voxel.cq

voxel.rs:28
19    283             ADD  height
20    410             SFT  10
21    777             SUB  d          n = _12 - d

A plain range. CARDIAC's only test is whether the accumulator is negative, so the compiler counts up from -96 and stops at zero, which leaves one TAC as the whole test. For the 1 it adds each time, it uses cell 00, which always holds 001.

voxel.rs

for _ in 0..96 {

voxel.cq

voxel.rs:17
43    184             CLA  iter_0
44    200             ADD  00         iter_0 = iter_0 + 1
45    684             STO  iter_0
46    305             TAC  main_bb31
…
voxel.rs:17
84   -096  iter_0     DATA -096

The program has thirteen variables, the compiler's own temporaries come on top of those, and CARDIAC has 100 cells. The compiler works out which values are never needed at the same time and gives them the same cell. Cell 83 holds five of them: height, below, the two ns and one of its own.

voxel.rs

let height = cell / 10;
…
let below = camera - height;
…
    let mut n = below * 20 - d;
…
    let mut n = -below * 20 - d;

voxel.cq

77    000  d          DATA 000
78    000  camera     DATA 000
79    000  horizon    DATA 000        also row   ; also t1 (never live at once)
80    000  left       DATA 000        also light (never live at once)
81    000  right      DATA 000
82    000  cell       DATA 000        also colour
voxel.rs:22, 25, 28, 35
83    000  height     DATA 000        also below   ; also n, n_2, t0 (never live at once)
84   -096  iter_0     DATA -096
85    000  k0         DATA 000
86    096  k96        DATA 096
87    002  k2         DATA 002
88    005  k5         DATA 005
89    004  k4         DATA 004

The one thing the Rust has to respect is the card. Every number has to stay between -999 and 999, which is why heights only go up to 49.

One strip, in and out

Each strip is one run of the program. Strip 90 of the middle picture is about two and a half kilometres out across the lake, and its deck starts like this:

23 27 30 242 23 24 30 242 24 25 ...

The 23 is the strip's distance as CARDIAC is given it, scaled down to suit the lens so that hills come out as tall as they are wide, and the 27 is the camera's height. Then come the four cards for the first column: the horizon crosses it at row 30, the land there is 242 (height 24, colour 2, forest), and it's 23 high a little to its left and 24 a little to its right. Take column 36, which is out on the lake. Its land card is 130, which is water at height 13, so it's 14 below the camera. Twenty times 14 is 280, and 280 divided by 23 is 12, so the water shows 12 rows below the horizon, at row 42. It's flat, so its light is the middle one, and CARDIAC outputs 42 and 2. Column 6 is a meadow on the rim, at height 25 and rising from 24 on its left to 27 on its right. It faces the sun, so its light is the brightest, 4, and CARDIAC outputs row 31 and colour code 34.

Watch one strip in Cardigan

This button opens the program in Cardigan, exactly as cargo-cardiac compiled it, with strip 90 loaded as its input cards. Step through it to watch a column's four cards go in and its row and colour code come out, or press Run and watch all 96 columns go by.

Watch it in Cardigan

How much it costs

The program, compiled87 of CARDIAC's 96 cells
Runs of the program360, 120 strips for each of the three pictures
CARDIAC instructions in all17,154,958
Time on burnabout 16 milliseconds of CARDIAC

The script takes a few seconds for all three pictures, but almost none of that is CARDIAC. Most of it is starting burn 360 times, and awk reading the map and putting the answers on the screen. On a real cardboard CARDIAC, worked by hand at about four seconds an instruction, the same three pictures would take a little over two years, day and night.

Try it

The program, the script and the height map are in rust-cardiac's examples, as voxel.rs, voxel.sh and craterlake.pgm. With cargo-cardiac and burn installed, in the examples folder:

cargo cardiac build --bin voxel
MAP=craterlake.pgm CAMX=69.5 CAMY=170 CAMZ=140 ZOOM=2 HORIZON=30 BANK=0 \
  NEAR=0.5 FAR=165 WATER=0 FLAT=1 PALETTE=mountain LOOK=335 sh voxel.sh

That writes the picture as voxel.ppm, and the map with its strips as voxel_map.ppm, with a .png of each on a Mac. Turn the camera with LOOK, move it with CAMX and CAMY, or give it a height map of your own: any plain 256 by 256 PGM will do. The program on CARDIAC stays the same. It's left as an exercise for the reader to make an animated flyover.

References

The voxel space algorithm

The terrain data

Back to rust-cardiac.