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 › Ray Tracing

Ray Tracing

Leveraging rust-cardiac to bring classic raytracing to CARDIAC

A mirror ball in pixels, resting low over a red and cream checkerboard under three bands of blue sky. The ball shows the sky in its top half, a white light at its upper left, and the checkerboard bent round its lower half, and it casts a dark shadow on the floor.

Turner Whitted's 1980 paper "An improved illumination model for shaded display" established ray tracing as a practical method for rendering reflection, refraction and shadows. A ray is followed from the eye through each pixel into the scene, and where it strikes a reflective surface it is traced again in the reflected direction. The paper's best-known image, mirrored and glass spheres above a checkerboard, has been the first scene rendered by almost every ray tracer since.

This article implements a reduced form of Whitted's method on CARDIAC. The scene is a mirror ball above a red and cream checkerboard under a banded sky, rendered at 96 by 48 pixels. The ball reflects the sky, a light source and the floor, and it casts a shadow. Each ray reflects once, and refraction is omitted. A ray tracer is far too large for a single CARDIAC, so the work is divided among ten machines, each running a small Rust program compiled with rust-cardiac. Together they form a pipeline in which each machine computes one stage of the rendering, such as the distance of a floor row, the surface normal at a pixel or the destination of a reflected ray. A host script passes each machine's output to the next without performing any computation of its own. Only the ball's pixels are traced, about 600 per frame, and the floor and sky are rendered a row at a time.

Why it's hard on CARDIAC

A ray tracer is usually a few pages of floating-point arithmetic. CARDIAC has none of what that needs. There's no square root, and every point on the ball needs one, to know how far its surface bulges toward the camera. The programs find it by taking away 1, 3, 5 and so on for as long as they fit, and counting how many went, because those odd numbers add up to the squares. There's no multiply or divide either. Squares are repeated additions, and finding where a ray meets the floor is a division, done by repeated subtraction. There are no fractions, so directions are whole numbers out of 98, distances along a ray are in tenths, and everything has to stay inside a card, between -999 and 999. And there are only 96 cells for a program and its data, which is far too little for a general ray tracer with a scene to describe. So there's no scene description and no recursion. Each step of the job is its own small machine, and the ball, the floor and the sky are written into them.

The floor and the sky are drawn the way old racing games drew a road, a row at a time. Only the ball's pixels are really traced, and each ray bounces once: off the ball, and then into the light, the sky or the floor.

Three pictures

FRAME picks one of 120 places along the ball's path. Along it the ball sways from side to side once and bounces every 24 places, and the floor scrolls under it. The host only passes FRAME on, and CARDIAC works out where the ball is, how high it is and how far the floor has moved. These are three of the places as CARDIAC drew them, each scaled up four times with every pixel kept as it was.

The ball high on the left side of the picture, its shadow on the checkerboard below it.
FRAME=93
The ball in the middle, at the bottom of its bounce, just over its shadow.
FRAME=0
The ball high on the right side of the picture, its shadow on the checkerboard below it.
FRAME=27

Ten machines

The work is split into ten programs, each one small enough for CARDIAC's memory. A program runs once for each thing it works on, once for the picture or once for each row or pixel, reading its cards and outputting its answers, and the host passes those answers on to the next program.

This is how they feed each other. Every colour in the picture is a code one of them chose: the row's background comes from sky or floor, a pixel of the ball from bounce or hit, and compose puts the two together. The host only turns the codes into colours.

How the ten programs feed each other: sway and hop once; for each row sky, or zrow and floor, for the background, and span for the ball's pixels; for each pixel of the ball norm, bounce and, for a ray that reaches the floor, hit; compose lays the ball's codes over the row's, and the host turns the codes into colours. ONCE swaythe ball's x hopits height; the floor's scroll x, height and scroll go to the programs below that need them ONCE A ROW, 48 TIMES sky96 sky codes, or -1 -1: a floor row zrowhow far away the row is its six cards floor96 checker codes spanwhich pixels the ball covers ONCE A PIXEL OF THE BALL normthe surface; the bounced ray bouncea code: light, sky or haze or -1: the floor hitthe checker's code composethe ball's codes overthe row's: 96 codes the row's background, from sky or floor where the ball starts, how many pixels the ball'scodes 48 rows of codes ray.sh, the host looks each code up in its 14 colours, as a display does, and writes the picture

Once

Once a row

Once a pixel of the ball

ProgramWhat it works out for FRAME=0RunsCells
sway
Rust · CARDIAC
sway: a line at the ball's x

The ball's x. It's 0 here, so the ball is in the middle.

once58
hop
Rust · CARDIAC
hop: a line at the height of the ball's centre

The ball's height, 14, which is the bottom of its bounce, and the floor's scroll, which is 0 both ways.

once91
sky
Rust · CARDIAC
sky: the sky's rows

A colour for each of the 22 rows above the floor: three bands of blue, then haze. For the 26 floor rows it gives -1.

once a row45
zrow
Rust · CARDIAC
zrow: a bar for each floor row, as long as its distance

How far away each floor row is, from 240 just below the haze to 33 at the bottom, and whether the ball's shadow reaches it, which it does for 6 rows.

once a row88
floor
Rust · CARDIAC, phase 2
floor: the floor's rows

The 96 checker colours of each floor row, darker inside the ball's shadow.

once a row16, then 83, in two phases
span
Rust · CARDIAC
span: the pixels the ball covers

Which pixels of each row the ball covers, 609 in all, and how far each is from the ball's centre.

once a row78
norm
Rust · CARDIAC
norm: the ball shaded by its surface's depth

How deep the surface is at each of the ball's pixels, from 14 at the centre to 1 at the edge, and which way the ray bounces off it.

once a pixel of the ball89
bounce
Rust · CARDIAC
bounce: the ball coloured by where each ray goes, grey for the floor

Where each ray goes: 43 to the light, 275 to the sky, 55 into the haze, and 236 down to the floor, in grey.

once a pixel of the ball64
hit
Rust · CARDIAC
hit: the checkers the floor-bound rays see

The checker each of the 236 floor rays lands on: 115 red and 121 cream. Those are the colours the ball shows.

once a pixel of the ball that sees the floor80
compose
Rust · CARDIAC, phase 2
compose: the finished render

Each row's 96 final codes, the ball's laid over the background: the finished render.

once a row57, then 67, in two phases

Each picture is drawn from that program's own outputs for FRAME=0, the whole of them: sway and hop as lines at the ball's x and height, zrow as a bar for each row's distance, norm as the depth it found, brighter nearer, and bounce grey where it sends the ray on to the floor. The rest are the colour codes they output. Under each name are its Rust and the CARDIAC listing cargo-cardiac compiled it to, so you can read the two side by side without installing anything. arith.rs holds the square root, remainder, division and absolute value they share, and ray.sh is the host.

Here's norm, the heart of it, and below it isqrt, the square root it calls. That comes from arith.rs, which norm and span both use, and the compiler builds it into each of their decks.

norm.rs

fn main() {
    let a = inp();
    let b = inp();
    let c = isqrt(196 - a * a - b * b);
    out(c);
    out(a * c);
    out(b * c);
    out(98 - c * c);
}

arith.rs

/// The integer square root of n (0 for n below 1): the odd numbers 1, 3, 5, ...
/// taken away while they fit, counted, since their sums are the squares.
pub fn isqrt(mut n: i16) -> i16 {
    let mut root = 0;
    let mut odd = 1;
    while n >= odd {
        n -= odd;
        odd += 2;
        root += 1;
    }
    root
}

The ball has a radius of 14 pixels, and 196 is 14 squared. A pixel a across and b up from the ball's centre is on the ball's surface at a depth of c, and the bounced ray's direction is (c a, c b, 98 - c squared), which is the mirror reflection of a ray from the eye, scaled up by 98 so that it stays in whole numbers.

Short as it is, norm asks for a lot that CARDIAC doesn't have. Line 13 multiplies two variables twice, in a * a and b * b, and lines 15, 16 and 17 do it three more times. CARDIAC can't multiply at all, and here neither side is a number the compiler knows in advance. Line 13 also calls a function and uses the value it returns. CARDIAC has no stack, and its only help with a call is that JMP leaves the return address in cell 99. Inside isqrt, line 10 of arith.rs compares two variables, n >= odd, where CARDIAC can only ask whether the accumulator is negative. Every value is also an i16, which in Rust can go up to 32767, while a CARDIAC cell holds -999 to 999.

rustc checks norm before cargo-cardiac ever sees it, the same way it checks any Rust. It makes sure isqrt is given an i16 and gives one back, that n can change inside isqrt only because it's declared mut, and that nothing is read before it's set. cargo-cardiac adds one rule of its own and refuses any constant that won't fit on a card. None of this costs CARDIAC a cell.

The inp() and out() calls on lines 11, 12 and 14 to 17 come from the cardiac crate. On CARDIAC each one is a single INP or OUT instruction. With cargo run the same program reads standard input and prints its output, so the two builds can be given the same numbers and compared.

norm is built in rust-cardiac's dev profile, which normally checks every add, subtract and multiply for overflow, but rust-cardiac turns those checks off for its examples. They would cost 48 more cells. With them norm comes to 137 cells, and CARDIAC only has 96 for a program.

The build also writes norm.map, the panic map, which burn reads and CARDIAC never does. It has two lines, fn 1 3 main and fn 1 57 rt_mul, which say where main and the multiply routine start. There are no checks in it, because norm has no arrays, no assert!, and no overflow checks in this build. If a check did fail, the program would output -999 and halt, and burn would use the map to say which check it was and in which function, as in panicked in main: the value doesn't fit on a card (-999 to 999).

Here's norm's listing, all 89 cells of it, in the six columns of a CARDIAC listing. The loop from isqrt sits inside main at cells 21 to 31, and rt_mul, the multiply routine the compiler added, is at cells 57 to 79.

norm.cq

Start at 03.

03    080  main_bb0      INP  a             inp()
04    081                INP  b             inp()
05    180                CLA  a
06    683                STO  main_4        _6 = a * a
07    686                STO  rt_mul_b
08    857                JMP  rt_mul_entry
09    683  main_rr0      STO  main_4
10    189                CLA  k196
11    783                SUB  main_4        _5 = 196 - _6
12    685                STO  t1
13    181                CLA  b
14    683                STO  main_4        _7 = b * b
15    686                STO  rt_mul_b
16    857                JMP  rt_mul_entry
17    683  main_rr1      STO  main_4
18    185                CLA  t1
19    783                SUB  main_4        _4 = _5 - _7
20    683                STO  main_4
21    183  main_bb7      CLA  main_4
22    784                SUB  main_20       if _4 >= _20
23    332                TAC  main_bb9
24    683                STO  main_4
25    184                CLA  main_20
26    291                ADD  k2            _20 = _20 + 2
27    684                STO  main_20
28    182                CLA  c
29    200                ADD  00            c = c + 1
30    682                STO  c
31    821                JMP  main_bb7      goto
32    582  main_bb9      OUT  c             out(...)
33    180                CLA  a
34    683                STO  main_4        _11 = a * c
35    182                CLA  c
36    686                STO  rt_mul_b
37    857                JMP  rt_mul_entry
38    683  main_rr2      STO  main_4
39    583                OUT  main_4        out(...)
40    181                CLA  b
41    683                STO  main_4        _14 = b * c
42    182                CLA  c
43    686                STO  rt_mul_b
44    857                JMP  rt_mul_entry
45    683  main_rr3      STO  main_4
46    583                OUT  main_4        out(...)
47    182                CLA  c
48    683                STO  main_4        _18 = c * c
49    686                STO  rt_mul_b
50    857                JMP  rt_mul_entry
51    683  main_rr4      STO  main_4
52    190                CLA  k98
53    783                SUB  main_4        _17 = 98 - _18
54    685                STO  t1
55    585                OUT  t1            out(...)
56    900                HRS  00            return from main
57    199  rt_mul_entry  CLA  99
58    679                STO  rt_mul_exit
59    188                CLA  k0
60    687                STO  rt_mul_r
61    186                CLA  rt_mul_b
62    371                TAC  rt_mul_neg
63    186  rt_mul_loop   CLA  rt_mul_b
64    700                SUB  00
65    378                TAC  rt_mul_done
66    686                STO  rt_mul_b
67    187                CLA  rt_mul_r
68    283                ADD  main_4
69    687                STO  rt_mul_r
70    863                JMP  rt_mul_loop
71    188  rt_mul_neg    CLA  k0
72    786                SUB  rt_mul_b
73    686                STO  rt_mul_b
74    188                CLA  k0
75    783                SUB  main_4
76    683                STO  main_4
77    863                JMP  rt_mul_loop
78    187  rt_mul_done   CLA  rt_mul_r
79    000  rt_mul_exit   DATA 000           becomes JMP back to the caller
80    000  a             DATA 000
81    000  b             DATA 000
82    000  c             DATA 000
83    000  main_4        DATA 000           also t0, t2, rt_mul_a (never live at once)
84    001  main_20       DATA 001
85    000  t1            DATA 000           scratch
86    000  rt_mul_b      DATA 000
87    000  rt_mul_r      DATA 000
88    000  k0            DATA 000
89    196  k196          DATA 196
90    098  k98           DATA 098
91    002  k2            DATA 002
001122334455667788990000101ldr02ldr03INP04INP05CLA06STO07STO08JMP09STO10CLA11SUB12STO13CLA14STO15STO16JMP17STO18CLA19SUB20STO21CLA22SUB23TAC24STO25CLA26ADD27STO28CLA29ADD30STO31JMP32OUT33CLA34STO35CLA36STO37JMP38STO39OUT40CLA41STO42CLA43STO44JMP45STO46OUT47CLA48STO49STO50JMP51STO52CLA53SUB54STO55OUT56HRS57CLA58STO59CLA60STO61CLA62TAC63CLA64SUB65TAC66STO67CLA68ADD69STO70JMP71CLA72SUB73STO74CLA75SUB76STO77JMP78CLA79exit80a81b82c83main_484main_2085t186rt_mul_b87rt_mul_r8808919690989129293949596979899ret

Reading a and b (03-04)196 - a * a - b * b (05-20)isqrt, inlined (21-31)The four outputs (32-56)rt_mul (57-79)VariablesConstants, by value00 holds 001, 01-02 the loader, 99 the return addressFreeCalls, exit cell, shared cell

How the compiler laid norm out in CARDIAC's 100 cells, with the five calls into rt_mul and its exit cell, 79, outlined in red.

Rust compilation notes

isqrt is a function call in the Rust. The compiler inlines it, so the loop sits right inside norm and takes eleven cells, with no call at all.

norm.rs

let c = isqrt(196 - a * a - b * b);

arith.rs

pub fn isqrt(mut n: i16) -> i16 {
    let mut root = 0;
    let mut odd = 1;
    while n >= odd {
        n -= odd;
        odd += 2;
        root += 1;
    }
    root
}

norm.cq

arith.rs:10
21    183  main_bb7  CLA  main_4
22    784            SUB  main_20   if _4 >= _20
23    332            TAC  main_bb9
arith.rs:11
24    683            STO  main_4
arith.rs:12
25    184            CLA  main_20
26    291            ADD  k2        _20 = _20 + 2
27    684            STO  main_20
arith.rs:13
28    182            CLA  c
29    200            ADD  00        c = c + 1
30    682            STO  c
arith.rs:10
31    821            JMP  main_bb7  goto

a * a multiplies two variables, and CARDIAC can only add. So the compiler adds a small routine, rt_mul, that adds one operand to itself as many times as the other says, and it calls that routine five times. Coming back from it uses the one return mechanism CARDIAC has. JMP writes the address just after it into cell 99, and the routine copies that into its own last cell, where it becomes a JMP back to the caller.

norm.rs

let c = isqrt(196 - a * a - b * b);

norm.cq

norm.rs:13
05    180                CLA  a
06    683                STO  main_4        _6 = a * a
07    686                STO  rt_mul_b
08    857                JMP  rt_mul_entry
09    683  main_rr0      STO  main_4
…
rt_mul, the compiler's
57    199  rt_mul_entry  CLA  99
58    679                STO  rt_mul_exit
…
79    000  rt_mul_exit   DATA 000           becomes JMP back to the caller

In sway, 28 * b multiplies by a number the compiler already knows, so it doesn't need the routine. b is added to itself, shifted one place to make 20 b, and then added eight more times, all in one straight run of ADDs.

sway.rs

let x = 28 * b - 500 + 9 * a;

sway.cq

sway.rs:17
19    156  main_bb6  CLA  b
20    256            ADD  b
21    410            SFT  10
22    256            ADD  b
23    256            ADD  b
24    256            ADD  b
25    256            ADD  b
26    256            ADD  b
27    256            ADD  b
28    256            ADD  b
29    256            ADD  b
30    760            SUB  k500  _8 = _9 - 500

The one thing the Rust has to respect is the card. Directions are out of 98 and the ball's radius is 14 because the arithmetic has to stay between -999 and 999.

One ray, in and out

With FRAME=0, sway is dealt 0 from the table and outputs 0, so the ball is in the middle, and hop is dealt 0 and outputs 14 0 0: the ball is at its lowest, and the floor hasn't moved yet. For row 28, span is dealt 28 0 14 and outputs 37 23 -8 and then the offsets -11 to 11. So the ball covers 23 pixels of that row, starting at column 37, and the row is 8 below the ball's centre.

Take the pixel at offset 5. norm is dealt 5 -8 and outputs 10 50 -80 -2. The surface there is 10 deep, which is the square root of 196 - 25 - 64 = 107, rounded down, and the ray bounces off it slightly to the right, steeply down and a little back toward the camera. bounce is dealt 50 -80 -8 14 and outputs -1 0, which means the ray reaches the floor almost at once, since the pixel is only 6 units above it. So hit is dealt 0 50 -2 5 10 0 0 0, and it outputs 11, the reflected cream checker. A pixel near the top left of the ball goes differently. At offset -6 on a row 8 above the centre, norm outputs 9 -54 72 17, a ray going up and to the left, and bounce outputs 13, the light.

What the host does

The host is a shell script, ray.sh, and it's strict about its job. It deals each machine its cards, passes what one outputs on to the next, looks up each colour code in a fixed palette the way a display does, and writes the picture. First it runs sway and hop, then for each of the 48 rows it runs sky, and zrow and floor when sky says the row is floor. It runs span, and for each pixel span gives it runs norm and bounce, and hit when bounce outputs -1. Then compose puts the row together.

The script never works anything out itself. It doesn't know where the horizon is, how big the ball is, where it is or which way a ray goes, and it adds nothing to the picture. Every colour code in it came from CARDIAC. The only numbers it handles of its own are FRAME, the line of the sine table it reads for it, and its count of the rows.

How much it costs

ProgramRuns for FRAME=0
sway1
hop1
sky48
zrow26
floor26
span48
norm609
bounce609
hit236
compose48

Two of the programs don't fit in 96 cells as one, so they come in two phases. The first phase reads the cards, and then calls overlay(), which loads the second phase's code over the first's while the data stays where it is. For floor that's 7 cells of data, and for compose it's 32, most of them the ball's pixels for the row. burn loads the second deck, floor.2.cqb or compose.2.cqb, by itself when the first one asks for it.

Runs of the programs, FRAME=01,652
CARDIAC instructions, FRAME=01,038,128
Time on burnabout a millisecond of CARDIAC

The script takes about five seconds for a picture on a Mac, and nearly all of that is starting burn 1,652 times. On a real cardboard CARDIAC, worked by hand at about four seconds an instruction, the same picture would take about 48 days, day and night.

Checking it

Every one of the programs is ordinary Rust, so each also runs natively with cargo run, and cargo-cardiac's tests check that each prints the same both ways. The whole picture was checked too. All 120 places were drawn twice, once with the decks on burn and once with native builds of the same programs, and the two came out identical, pixel for pixel. They also match a separate ray tracer written in plain Rust, without CARDIAC's limits on the arithmetic, pixel for pixel.

Try it

The programs are in rust-cardiac's examples, in the ray folder, with the sine table and the script that printed it, and the host is ray.sh. With cargo-cardiac and burn installed, in the examples folder:

cargo cardiac build
FRAME=27 sh ray.sh

That writes the picture as ray.ppm, with a .png of it on a Mac. FRAME can be anything from 0 to 119. To watch it work, add VERBOSE=1. Then each program's run is shown as it starts, with the cards it's dealt, and when it ends, with what it output and how many instructions it took. At the end come the totals: for FRAME=0, 1,652 runs and 1,038,128 instructions.

VERBOSE=1 FRAME=0 sh ray.sh
norm     5 -8 -> 10 50 -80 -2 (808 instructions)

Each program also runs on its own, natively or on burn, so you can follow one ray the way this page does:

echo 5 -8 | cargo run -q --bin norm
burn ray/norm.cqb -- 5 -8

Both print 10, 50, -80 and -2.

References

Ray tracing

The floor

Back to rust-cardiac.