For a long time, I've been wanting to make a new 3D modeling tool. This tool should encourage creative experimentation by minimizing friction. The sculpting tools of Dreams were a big inspiration to me, and the idea of a sensitive tool - a tool that is simple, but which allows for great skill and expression, such as a pencil or a piano.

Dreams uses signed distance functions to implement solid modeling operations. SDFs are nice and simple, but if the list of shapes gets large, rendering it naively with ray marching would be too expensive to do in real time. Dreams uses advanced compute-shaders and point-clouds to render SDFs in a painterly style. However, I wanted to stay in the realm of triangle meshes since they're used in modern game engines and SDFs have some limitations anyway, so I decided to do look into 3D mesh boolean algorithms. I wanted them to be fast enough for real-time editing of complex meshes, but also robust to edge-case scenarios. Popular 3D software still struggle with these goals, and I wanted to try doing better.

It wasn't easy. Writing a boolean algorithm is straight forward, in theory: slice each face in each input mesh by all other faces (in both meshes), then do a raycast per face to determine which (if any) input mesh the face is inside of, and with that, determine if the face should be kept, discarded or flipped. The same algorithm applies to any kind of boolean op (subtraction / union / intersection), only the final step of deciding when to keep/discard/flip a face is different. But what happens if two faces are overlapping? This would be an annoying edge case that could be handled for example by Simulating Simplicity. With floating point math, the edge case likely wouldn't happen per se, but worse: due to small floating point rounding errors in expressions, a comparison may straight up lie to us if it's near its turning point (i.e. "X > Y" might return "true" even if X < Y and X ~= Y).

After some experiments, I took inspiration from the paper: Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs and implemented a similar scheme for dealing with geometry robustly. The idea is to represent all geometry using planes, where a plane is defined as the four fixed-size integer coefficients `A, B, C, D` of the plane equation `Ax + By + Cz + D = 0`. Edges are represented as the intersection of two planes, points by the intersection of three planes, and (convex) polygons by a plane and a list of edge planes. A nice property of boolean operations is that the result of a boolean is fully made up of polygons from either of its input meshes, possibly flipped or cut by each other's planes. That means it's possible to represent the boolean result mesh using only the original planes from the two input meshes. That's perfect, as we can then apply as many boolean operations as we want without ever growing the bit complexity or requiring quantization!

I extended my algorithm to handle self-intersections as well, as opposed to requiring 2 well-formed input meshes at a time. This means that fun things like Sketchup-style extrusions are allowed, and it will also allow for robustly moving/rotating/scaling intermediate results and quantizing vertices, as the self-intersections introduced by these operations are resolved by the algorithm. For implementing this, I took inspiration from the paper Robust Inside-Outside Segmentation using Generalized Winding Numbers. I use BSP trees to subdivide the 3D space into cells and form links from these cells to their neighbouring cells and faces. I then flood-fill the "insideness" value from each BSP cell to its neighbours using this structure and finally output faces between the cells that cross the "insideness" 0 boundary. I made this all run on a separate thread so that the user-facing UI would always stay snappy. If the computation takes more than 1 frame, the rendered mesh will just lag slightly behind the 3D wireframe UI.

The big challenge when working with 3D geometry algorithms is debugging it when something goes wrong. There are often large structures of data filled with internal links and difficult-to-visualize coordinate values, making it very hard and tedious to see what is going on. There are two things that helped me stay sane: 1. easy-to-use 3D debug drawing functions for points, lines, strings, etc... 2. Eero's replay debugger - I stole this idea from one of Media Molecule's streams (I'm a fan, can you tell?). The idea is to setup a deterministic simulation and to record all user inputs from each frame into a file. Then, if you hit a problem, you can simply feed that file into the simulation again and debug-step your way into the problem as many times as you want! I even setup a custom allocator using a fixed-address buffer so that all memory addresses would be deterministic as well. I only regret not setting this up earlier.

Recently, I've been working on the editor itself. It has been really fun to put it together and to see each feature addition noticably improve the 3D editing workflow. For the design, it's mostly trial and error, looking for inspiration from other creative tools, and going with what feels right. I feel like the editor is at a good point now with a solid base that I can extend further. I will continue working on it more and trying to pull the release date somewhere into the horizon!