MiniSDF: A signed distance field language

Date: 18.03.2024

MiniSDF is a small domain-specific-language (DSL) for signed distance functions (SDF). It allows you to define the function using a tree of operations and primitives. The final program is then compiled into a linkable SPIR-V module.

field myfield(offset: vec3){
    union(){
        repeat(3.0, 10.0, 4.0){
            sub(){
                box(vec3(1.0, 2.0, 1.0))
            }{
                repeat(0.75, 0.75, 0.75){
                    sphere(0.4)
                }
            }
        }
    }{
        translate(offset){
            inter(){
                sphere(1.75)
            }{
                sub(){
                    translate(vec3(0.0, 0.0, 0.0)){
                        smooth(0.5){
                            box(vec3(1.0, 1.0, 1.0))
                        }
                    }
                }{
                    smooth(0.5){
                        union(){
                            box(vec3(2.0, 0.1, 0.1))
                        }{
                            union(){
                                box(vec3(0.1, 2.0, 0.1))
                            }{
                                box(vec3(0.1, 0.1, 2.0))
                            }
                        }
                    }
                }
            }
        }
    }
}

The resulting image for the code on the left. Note that the compiler only generates the SPIR-V code, you still need a renderer that creates the image.

Goal

To understand the reason why I went the hard way of writing a whole compiler just to display some nice objects on screen, it’s worth understanding the advantages of this approach, and what I wanted to accomplish.

Before working with SDFs I used to dabble with voxels and raytracing. Voxels are really just information in space, so it’s easy to extend them to carry information like light-emission, metallness, bounciness, etc.—really anything you’d like. While I really liked how you could encode information nicely in voxels, I was always bothered by the blockiness of them.

So the idea was to fix that by doing the same, but with those nice SDFs the demo scene and shader-toy people used.

My goal is to have a volume representation, that can be modified easily at runtime (like voxels), carrys all kinds of information (like voxels), but be in an implicit representation (like SDFs) and be able to represent smooth surfaces. Just for the fun of it, I don’t consider triangle representations smooth.

My attempts

Nako

My first take on rendering SDFs on the GPU was Nako. It was basically a GPU-site interpreter for custom byte code, that could be used on the GPU and CPU, to evaluate a signed-distance-function.

Advantages

  1. Easily modified at runtime
  2. implicit representation (no voxels or something like that), so no resolution artifacts
  3. Cross-platform representation, meaning the same source code on the GPU and CPU.

Disadvantages

  1. Only strings of operations, no trees. For instance, the image above was not possible, since we have an infinitely repeating pattern in the top tree (the boxes), and a finite subtree at the bottom (the cut-out sphere).
  2. scaled badly, while small functions worked fine, more complex functions quickly choked the GPU, since all operands had to be fetched from VRAM for each evaluation of the SDF. This can be seen nicely in my SDF-based wavetable synthesizer.

Algae

This was a small intermezzo between Nako and MiniSDF. I already came to the conclusion, that I can’t load my operands from VRAM, but for some reason I did not yet find out that I really just need some kind of compiler.

Algae pioneered the live-linking of SPIR-V modules, which later became Spv-Patcher and already brought some kind of Rust-internal DSL for chaining up SDF operations and primitives.

The project pretty much collapsed after I took the compiler course for my master’s degree. It showed me that compilers are in fact software like anything else, and there is nothing magic about it. This gave me the confidence to start my own.

Advantages

  1. Tree of operations
  2. Fully implicit as well, but on an algebraic level, instead of the SDF-operation level

Disadvantages

  1. The internal DSL becomes really wonky to work with
  2. SPIR-V only, so no CPU SDF-evaluation anymore 😢

Other attempts

I am not the first person trying this. From what I found, the vast majority uses a similar approach to Nako, but bakes that into a voxel volume at some point. That can work well, for instance, in Dreams or Claybook, if your art style permits this, as well as your use case. I aim more for a CAD application like usage, so both, the voxel-resolution problem and the fact, that you can’t represent independent subtrees in a voxel-volume are a deal-breaker. Another advantage of fully-implicit representations is, that we can use infinity, as in infinite repetition, pretty freely.

Interestingly, there are other attempts at using a GPU-site bytecode interpreter. Saft seems to be able to generate bytecode from a similar representation as Nako does.

Another approach is to just hand-roll a specific shader, that encodes exactly the SDF that is needed. While this gives the best performance (without having to employ voxels as an approximation), it is also a quite static approach. Once compiled, you can’t really change the structure of your function, only parameters.

Comparison

So to make the advantages a little bit more visible, let’s put all of that into a matrix:

Feature Nako Algae MiniSDF Voxelized1 GLSL Shader
Resolution independent ✅ ✅ ✅ ❌ ✅
Fast to render ❌ ✅ ✅ ✅ ✅
Tree-capability ❌ ✅ ✅ ❌ ✅
Runtime modifiable ✅ ✅ ✅ ✅ ❌
Cross-platform2 ✅ ❌ ❌ ❌ ❌

The key takeaway is, that most of the approaches are good in most of the features we need, but never in all. So you could argue that I’m making my life harder than it has to be.

MiniSDF

MiniSDF picks up the work of Algae, but in the context of a compiler. In that regard, it’s pretty conservative. There is a frontend based on tree-sitter, a middle-end / optimizer and a SPIR-V backend.

The most interesting part of the compiler is probably its IR, which is based on the Regionalized Value State Dependency Graph (RVSDG). The graph is factored out into its own node-agnostic crate. MiniSDF does not use the more fancy features of that IR yet. Working with the Graph-IR was pretty elegant compared to my earlier adventures in TAC-SSA-land, like handwriting SPIR-V and using MLIR/LLVM.

After compilation, a linkable SPIR-V module is emitted, which can then be linked to a shader module using the Spv-Patcher.

Shortcomings

As shown in the listing, the language is currently pretty small. You have a set of hard-coded operations and primitives, and the result is always a signed-distance, based on some position parameter. That’s something I’d like to extend in the future.

The language also has a lot of high-level optimizing potential that’s not being used right now. Imagine you have a tree that first translates, then rotates, and finally scales a subtree. Those three operations could easily be folded into one transform operation.

The domain-specific nature also allows for more unconventional use of the compiler. For instance, if the bounds of all primitives and the change of bound for all operations are known, we could generate a BVH or Kd-Tree using the compiler and code.

As you can see, once viewed through the compiler lens, a lot of interesting transformations and optimizations emerge. So see you for the next episode of SDFs and compiler crimes in a year or so 🙂.

For the time being, feel free to play around with the compiler3 and the renderer4!