CARDIAC › rust-cardiac › Demos › Ray Tracing
Ray Tracing
Leveraging rust-cardiac to bring classic raytracing to CARDIAC
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.
FRAME=93
FRAME=0
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.
Once
sway works out the ball's x, 28 times the sine of the place's angle, rounded. It's given that sine
the way people used to be given one, from a printed table: sine120.txt holds 999 times the sine for
each of the 120 places, and the host deals it the line for FRAME. Turning 999 sin into 28 sin is a division by 999,
which sway does without dividing, by counting 36s.
hop works out the ball's height from FRAME, a parabola that repeats every 24 places,
and how far the floor has scrolled across and into the distance.
Once a row
sky gives the row's colour if it's sky: one of three bands of blue, or haze just above the floor,
where the floor is too fine to draw. For a floor row it gives -1 instead.
zrow works out how far away a floor row is. The floor is 16 units below the eye and the screen 60
in front of it, so a row d rows below the horizon shows the floor at a distance of 960 divided by d. It also works
out which row of checkers that is, where the row's left edge falls on the floor, and whether the ball's shadow
reaches it.
floor steps across the row, picking red or cream for each pixel and darkening the ones in the
ball's shadow. It never divides: it adds 16 to a running remainder for each column and carries into the floor's
x, as the remainder of a long division would.
span works out which pixels of the row the ball covers, with a square root for the ball's half
width on that row, and outputs each one's offset from the ball's centre.
compose lays the ball's pixels over the row's background.
Once a pixel of the ball
norm works out which way the ball's surface faces at the pixel, and the direction a ray from the
eye bounces off it.
bounce works out where that ray goes. A ray up and to the left catches the light, any other upward
ray sees the sky, high or low, and a ray going down meets the floor, after a distance it finds by dividing. If
that's too far, the floor is lost in haze.
hit works out where on the floor a downward ray lands, and the colour of the checker there, which
is what the ball reflects.
| Program | What it works out for FRAME=0 | Runs | Cells |
sway Rust · CARDIAC |  The ball's x. It's 0 here, so the ball is in the middle. | once | 58 |
hop Rust · CARDIAC |  The ball's height, 14, which is the bottom of its bounce, and the floor's scroll, which is 0 both ways. | once | 91 |
sky Rust · CARDIAC |  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 row | 45 |
zrow Rust · CARDIAC |  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 row | 88 |
floor Rust · CARDIAC, phase 2 |  The 96 checker colours of each floor row, darker inside the ball's shadow. | once a row | 16, then 83, in two phases |
span Rust · CARDIAC |  Which pixels of each row the ball covers, 609 in all, and how far each is from the ball's centre. | once a row | 78 |
norm Rust · CARDIAC |  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 ball | 89 |
bounce Rust · CARDIAC |  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 ball | 64 |
hit Rust · CARDIAC |  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 floor | 80 |
compose Rust · CARDIAC, phase 2 |  Each row's 96 final codes, the ball's laid over the background: the finished render. | once a row | 57, 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
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
| Program | Runs for FRAME=0 |
sway | 1 |
hop | 1 |
sky | 48 |
zrow | 26 |
floor | 26 |
span | 48 |
norm | 609 |
bounce | 609 |
hit | 236 |
compose | 48 |
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=0 | 1,652 |
| CARDIAC instructions, FRAME=0 | 1,038,128 |
| Time on burn | about 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
- Lou's Pseudo 3d Page, by Louis Gorenfeld, explains how
racing games drew the road a row at a time, with a table of how far away each row of the screen is. The floor
here is drawn the same way, with CARDIAC working out each row's distance.
Back to rust-cardiac.