CSG-based level geometry editor

C++ D3D11 HLSL

A 3D level editor with real-time constructive solid geometry editing. Written from scratch in C++ with the goal of being fun and intuitive to use while allowing non-destructive level editing.

Introduction

It began as a dream for a new kind of 3D modeling tool - a tool that would 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 inherently simple, but which allows for great skill and expression, such as a pencil or a piano.

As for the technical foundation, Dreams uses signed distance functions to implement solid modeling operations. SDFs are nice and simple, but when the list of shapes gets large, rendering it naively with ray marching would be too expensive to do in real time. Dreams uses a series of compute-shaders to dynamically convert the SDFs into point clouds and to render them in a painterly style. However, I wanted to stay in the realm of triangle meshes as they're commonly used everywhere and fast to render (and SDFs impose some big limitations), 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.

Writing a boolean algorithm is straight forward, at least 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 exactly? This would be an annoying edge case, but it could certainly be handled for example by Simulating Simplicity. The real problem is with floating point math: due to small rounding errors in float expressions, a comparison may straight up lie if it's near its turning point (i.e. "X > Y" might return "true" even if X < Y and X ~= Y). So if there is any near-edge case, we can't expect any mathematical axiom to hold anymore and all hell breaks loose.

Implementing booleans

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 it allows for applying any number of boolean operations exactly without ever growing the bit complexity! (this sidesteps the need for bignums)

I then extended the algorithm to handle self-intersections 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.

Debugging

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. The two things that helped me stay sane were: 1. easy-to-use 3D debug drawing functions for points, lines, strings, etc... 2. deterministic replay debugger - I stole this idea from one of Media Molecule's streams. 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.

Ever since getting the geometry to work robustly, I've been working on the editor frontend. It has been really fun to put it together and to see each feature addition noticably improve the 3D editing workflow. Designing it has mostly been trial and error, looking for inspiration from other creative tools, and most importantly going with what feels right. Sometimes I've implemented an idea that I thought would be super intuitive and great just to realize it feels weird. The editor is at a good point now and has a solid base that I can keep extending further. I'm really excited about the future plans I have for this project, and this has only been a small slice of it!