Solid Geometry Representations

7 minute read.

I recently published my Manifold library, which does operations on solids, specifically those represented by triangle meshes. But there are many ways to represent a solid object in a computer, so why did I choose this one? I thought it might be useful to give an overview of some of the popular data structures and what they are well- and poorly-suited to. Of course this is also my opinion and I have limited experience with many of these, so please comment if you know something I don't. 

Categorization is always a bit tricky and arbitrary, but I feel like the highest-level split is between boundary representations (B-Reps) and signed distance functions (SDFs). I'll sub-categorize below each of these.

Signed Distance Functions (SDFs)

Though less common, the SDF is in some ways the simpler idea. It explicitly represents a solid: in its simplest form it is a function that takes any point in 3D space and returns if that point is inside or outside of the solid. To make this behave better numerically and provide easy offsetting functions, the SDF was born, returning a distance to the nearest surface, positive inside and negative outside by convention. But "distance" here is often a loose term, where the sign is the critical part and the value is hopefully "well-behaved" even if not perfectly measured. 

This representation is great because any function represents a sane (potentially unbounded) solid object. It is also great because combining solids via Boolean operations is trivial: OR (union) is the maximum of the two functions, AND (intersection) is the minimum, AND NOT (difference) is the minimum with one function negated. 

Its functional nature also makes it ideal for physical simulation, and therefore for generative, organic-looking designs. Nervous System is a favorite design duo of mine who make excellent use of this technique.

So why aren't SDFs used all the time? Well, there are two main ways to store them (continuous and discrete) and they each come with computational difficulties:

Continuous Functions

The first problem with continuous functions is that it can be difficult to find a mathematical function that represents the shape you want, as it's not intuitive for most people. Second, the right function could be quite complex both to write down and to compute. Worse yet, as more and more objects are combined, the resulting function effectively contains all the parts that led to it, which means multi-step designs get very slow.

Discrete Voxels

Voxels are the 3D version of pixels: a uniform grid of values, in this case often a signed distance. The SDF simply interpolates them. They are especially popular because of medical imaging, since MRI scans create this kind of data naturally. However, they are useful for lots of sensor-related applications - for instance many photogrammetry pipelines use voxels internally to average the data from various images together into a 3D shape. 

The trouble with voxels is how they scale in memory. For whatever size object you have, if you need n divisions along each axis to get the precision you want, then you need n³ storage. That adds up quick, and most of those voxels aren't even near the surface and so aren't storing anything particularly useful. Take a powder 3D printer, which like an ink-jet is naturally processing voxels into physical media. It is not unreasonable to have a print volume of a cubic meter and 0.1 mm precision. That would require 1 terabyte of memory even if each voxel held only a single byte. 

The memory scaling can be mitigated to some degree using truncated SDFs and oct-trees, which only break down into smaller leaves near surfaces (zero crossings). They can also allow for storing data at different resolutions in different parts of the object depending on detail required. However, accessing and operating on the data becomes slower and more complex and the total data required is still quite large.

When working with either type of SDF, the Marching Cubes algorithm inevitably comes up because this is a simple way to construct a polygon mesh of the surface of the solid (even continuous functions need to be discretized at this step). But why is the surface needed when we already have the solid? That is because in fact boundary representations are the dominant method of representing solids in computers.

Boundary Representations (B-Reps)

Boundary representations implicitly define the solid by explicitly defining its boundary or surface. This method dominates largely because it is memory-efficient and particularly because it is well-suited to real-time rendering of graphics. By defining only the surface (a 2D manifold), you drop an n³ problem to an n² one, and the variable-precision part comes for free. 

However, there is a big downside to boundary representations: not all surfaces represent a solid. Take a Möbius strip: it is a lovely surface, but contains no volume. Thus we get the concept of manifoldness, specifically an oriented 2-manifold, which we can check to validate that it represents a solid. But that's not all: even a manifold mesh can be self-intersecting (or more generally, overlapping) which also makes inside and outside a bit convoluted. 

A Möbius strip is not manifold since it has open edges and therefore contains no volume.

There are lots of different B-Reps, but I'm going to start with a major division that affects the kinds of operations they support: implicit vs explicit edges. 

Implicit Edges

In this case the surface is made up of several patches, but these patches pass through each other and only their topological relationships to each other are stored, rather than their geometric intersection curves. This has formed the basis of most engineering CAD systems, primarily in the form of non-uniform rational basis splines (NURBS), but a related concept is Nef polyhedra.

NURBS

Most professional CAD systems are based on NURBS patches, which are actually pretty simple. They are fundamentally rectangular, parameterized by orthogonal UV coordinates. They are a grid of splines and are great for making long, smooth curves like you see on modern car bodies. The control points are weighted and are not on the surface itself. These patches are also great for engineering applications because they can represent conics exactly, the most common of which is the cylinder. 

Where it gets complicated is how these patches are joined. Boolean operations are fundamental to CAD, but Boolean joints do not produce nice curved rectangular patches. Instead these complex intersection curves are calculated enough to determine the topology of the attachment between patches even though the curve's geometry is not stored. It is up to the renderer to clip out extraneous portions of the patches, which is fairly easy, but when exporting to an explicit-edges format to do e.g. finite-element analysis (FEA) or computational fluid dynamics (CFD), all of these implicit edges must be calculated and if they don't match the stored topology due to rounding errors, then manifoldness can be lost.

Nef Polyhedra

CGAL uses Nef polyhedra extensively and they are sort of like a faceted version of NURBS. Each face is a half-space: an infinite plane that can be represented as a normal vector and an origin offset. An ordered set of Boolean operations can build any faceted model using one half-space per face. These Booleans implicitly represent the intersections of these facets which result in edges and vertices. An advantage Nef polyhedra have over NURBS is that like SDFs, they always represent a solid (potentially unbounded).

A little like continuous SDFs, these implicit edge methods tend to struggle as the designs get sufficiently complex as they don't have a very good way to remove data from the clipped-out portions of a patch. Also, warping operations such as a sculpting app might use are not very feasible, since the patch intersections will change in complex ways (both geometrically and topologically) when their controls points are moved in a nonlinear way. 

Explicit Edges

The alternative is to focus on defining the positions of the intersections (vertices) instead of the patches (faces) themselves. This brings us to the various mesh representations.

Polygon Meshes

One obvious choice of mesh type is the polygon mesh, since a Boolean operation on any two faceted meshes naturally produces polygonal faces. However, these meshes have two major problems: first, how should one handle the situation where the vertices in a polygon are not all coplanar, which inevitably happens due to rounding error, or especially warping operations? 

The second problem is that most formats prefer to deal with simple (single contour) polygons, while the Boolean operation is just as likely to create polygons with holes and potentially any depth of complexity. Holes are a problem because you have no edges showing a link between these contours that are topologically supposed to be part of the same face. Splitting these into simple polygons is an even harder problem than triangulation, so the supposed simplicity of the polygon mesh tends not to be realized in practice. 

Subdivision Surfaces

It would be nice to take a conveniently simple mesh and allow it to represent a smoothly curved surface like NURBS do through arbitrary refinement. The subdivision surface does this and is generally comprised mostly of quads and triangles with a refinement strategy that recursively adds and shifts vertices to approach a smooth surface. This family of approaches are popular in 3D animation software.

While it yields very pretty results, most of the popular implementations are approximating schemes, which mean that the original vertices are not on the asymptotic surface; they serve a function more like the control points of a Bezier curve or NURBS surface. As such it can be difficult to construct them in such a way as to create a precise surface; they are better-suited to sculpting. 

Additionally, many of these methods depend on quad meshes and have poorer results near extraordinary vertices (those that don't have exactly four quads attached). The trouble is that a Boolean operation will cut arbitrarily across a quad and the polygon produced cannot in general be cut back into quads without extraordinary vertices.

Triangle Meshes

This brings us to the lowest-common-denominator mesh: use only the simplex, thus meshing entirely with triangles. Any mesh can be converted to a triangle mesh and the facets are always planar by definition, so vertex warping and sculpting are trivial. 3D graphics is dominated by rasterizing triangle meshes because they are memory efficient and universal. 

However, it takes a lot of triangular facets to approximate a curved surface well. Graphics can fake this with Phong shading, interpolating the normal vectors to give smoothness to the way light is reflected. But for manufacturing no such cheats are available. 

It would be nice to create a smooth surface that interpolates the vertices of a triangle mesh so that it can better approximate the NURBS and such above without needing a huge amount of data and while maintaining a strictly manifold data structure. I've developed a scheme for this kind of refinement in the Manifold library using a two-level API: one low-level for maximum flexibility and file interchange, and another high-level for ease of use. My next post will explain in more detail.