Introduction
Fidget is a library for representing,
compiling, and evaluating large-scale math expressions, i.e. hundreds or
thousands of arithmetic clauses. It’s mainly designed as a backend for
implicit surfaces, but the
library is flexible enough for many different uses!
What are implicit surfaces?
Implicit surfaces are expressions of the form
$f(x, y, z) rightarrow d$
returning a single distance value $d$.
If that value is positive, then the point $(x, y, z)$ is outside the model;
if it’s negative, then the point is inside the model.
For example, a sphere of radius 1 can be expressed
as
$$ f(x, y, z) = sqrt{x^2 + y^2 + z^2} – 1 $$
By evaluating the expression at many points in space and checking its sign, we
can render this function into an image. In this example, we’ll render a
heightmap, where filled-in voxels are colored based on their distance to the
camera:
Fidget focuses on closed-form implicit surfaces, which build their
expressions out of basic arithmetic operations. This is in contrast with more
flexible representations (e.g. GLSL in a pixel shader), which may run entire
Turing-complete programs to compute the distance value.
I like to think of these functions as an “assembly language for shapes”: a
low-level representation that you’re unlikely to write by hand, but easy to
target from higher-level representations.
Why implicit surfaces?
Implicit surfaces are a particularly pleasant representation: they’re compact,
philosophically straight-forward, and amenable to massively parallel evaluation
(e.g. using SIMD instructions or on the GPU).
In addition, constructive solid geometry (CSG)
operations like union or intersection – famously difficult for meshes and NURBS
– are trivial! Here’s the union of two exactly-coincident cylinders,
which is just min(a, b):
Having a closed-form equation opens the door to interesting optimizations. For
example, Fidget can capture a trace showing which branches are taken during
evaluation; this trace can be used to simplify the expression, reducing the cost
of future evaluation.
Finally, for the computer enthusiasts, implicit surfaces offer a deep well of
entertaining research topics: everything from compilers to meshing algorithms
to GPGPU programming.
In other words, I just think they’re neat.
Origins
Over the past ten years, I’ve spent a lot of time thinking about
rendering and evaluation of implicit surfaces:
- I’ve written 4-5 kernels
in various languages, at least one of which was used
in commercial CAD software. - Back in 2020, I published a SIGGRAPH paper presenting a new
strategy for fast rendering on modern GPUs
So, why write something completely new, when the industrial-strength libfive
kernel is sitting right there?
This is personal-scale, mostly-unpaid research, so I have to optimize
for my own motivation and energy. The questions that I’m currently finding
interesting would be hard or frustrating to investigate using libfive as a
foundation:
- Finding the “right” APIs for implicit kernels, with the possibility of making
substantial compatibility breaks - Experimenting with native (JIT) compilation, to improve performance without
moving to the GPU - Cross-compiling to WebAssembly and building easily-accessible web demos
libfive is 40K lines of mostly C++, and is extremely challenging to hack on,
even as the original author. It’s also frustrating to touch: if it’s been a few
months since I last compiled it, it’s inevitable that the build will have
broken, and I’ll have to mess with CMake for 10 minutes to unbreak it.
Fidget is written in Rust, which I’m also using
professionally. It compiles
with a single cargo build, cross-compiles to WebAssembly seamlessly, and can
be refactored with confidence (thanks to Rust’s strong type system and memory
safety).
With all that context, let’s get started on our tour of the library!
Library structure
The library is built as a stack of three mostly-decoupled layers, along with
demo applications. Click on one to jump to that section of the writeup, or keep
scrolling to read through in order.
Frontend: building math expressions
The frontend of Fidget goes from input script to bytecode:
It’s not mandatory to use this specific workflow; users of the library can
show up at any point in this diagram.
Let’s walk through step by step and see how things look at each stage!
Scripting
Fidget includes bindings for Rhai, an embedded scripting
language for Rust. Using operator overloading, it’s easy to write scripts to
build up math expressions:
let scale = 30;
let x = x * scale;
let y = y * scale;
let z = z * scale;
let gyroid = sin(x)*cos(y) + sin(y)*cos(z) + sin(z)*cos(x);
let fill = abs(gyroid) - 0.2;
let sphere = sqrt(square(x) + square(y) + square(z)) - 25;
draw(max(sphere, fill));
The value passed to draw is a math tree which represents the expression
built up by the script.
Tree and graph
The math tree is deduplicated to produce a directed acyclic graph:
SSA tape
Doing a topological sort
lets us flatten the graph into straight-line code.
This code is in single static assignment form;
there are arbitrarily many pseudo-registers (named rX), and each one is only
written once.
r7 = Input[0]
r6 = MulRegImm(r7, 30.0)
r26 = SquareReg(r6)
r16 = Input[2]
r15 = MulRegImm(r16, 30.0)
r25 = SquareReg(r15)
r24 = AddRegReg(r26, r25)
r10 = Input[1]
r9 = MulRegImm(r10, 30.0)
r23 = SquareReg(r9)
r22 = AddRegReg(r24, r23)
r21 = SqrtReg(r22)
r20 = SubRegImm(r21, 25.0)
r19 = SinReg(r6)
r18 = CosReg(r15)
r17 = MulRegReg(r19, r18)
r14 = SinReg(r15)
r13 = CosReg(r9)
r12 = MulRegReg(r14, r13)
r11 = AddRegReg(r17, r12)
r8 = SinReg(r9)
r5 = CosReg(r6)
r4 = MulRegReg(r8, r5)
r3 = AddRegReg(r11, r4)
r2 = AbsReg(r3)
r1 = SubRegImm(r2, 0.2)
r0 = MaxRegReg(r20, 1)
Output[0] = r0
It’s possible to evaluate this tape, but it doesn’t scale well: you have to
allocate a memory location for every single operation, since pseudo-registers
aren’t reused.
Bytecode
To improve evaluation, it’s helpful to map from pseduo-registers to
physical(ish) registers, which can be reused.
For example, the tape above can be packed into 6 reuseable registers:
r3 = Input[0]
r3 = MulRegImm(r3, 30.0)
r0 = SquareReg(r3)
r4 = Input[2]
r4 = MulRegImm(r4, 30.0)
r2 = SquareReg(r4)
r0 = AddRegReg(r0, r2)
r2 = Input[1]
r2 = MulRegImm(r2, 30.0)
r1 = SquareReg(r2)
r0 = AddRegReg(r0, r1)
r0 = SqrtReg(r0)
r0 = SubRegImm(r0, 25.0)
r1 = SinReg(r3)
r5 = CosReg(r4)
r1 = MulRegReg(r1, r5)
r4 = SinReg(r4)
r5 = CosReg(r2)
r4 = MulRegReg(r4, r5)
r1 = AddRegReg(r1, r4)
r2 = SinReg(r2)
r3 = CosReg(r3)
r2 = MulRegReg(r2, r3)
r1 = AddRegReg(r1, r2)
r1 = AbsReg(r1)
r1 = SubRegImm(r1, 0.2)
r0 = MaxRegReg(r0, r1)
Output[0] = r0
Register allocation uses the simple algorithm that I
blogged about a few years back. It’s a single-pass algorithm that trades
efficienty for speed and determinism; that blog post has much more detail and
interactive demos.
The bytecode interpreter uses 256 registers, so the register index is stored in
a u8. If we run out of registers, then the allocator inserts LOAD and
STORE operations to write to secondary memory (using a u32 index).
This bytecode tape is the end of the front-end; we now proceed to the backend
for evaluation!
Backend: fast, flexible evaluation
The Fidget backend is decoupled from the front-end with a set of traits
(Function,
TracingEvaluator, and
BulkEvaluator),
which roughly represent “things that can be evaluated”.
This decoupling means that algorithms can target a generic Function, instead
of being tightly coupled to our math tree implementation. Right now, there
aren’t any non-math-tree implementers of the Function trait, but this could
change in the future. In the current implementation, we have two different
flavors of math tree evaluation: interpreted bytecode, and JIT-compiled
functions.
Here’s a high-level sketch of the evaluation process:
Interval arithmetic
Bulk and SIMD evaluation
Bulk evaluation is straight-forward: the user provides an array of input values,
and receives an array of out
