Introduction
It was a sunny Monday afternoon, and I was trying to summon Cthulhu.
Not the full-size eldrich abomination -- that would be irresponsible. I was trying to print out a small model downloaded from Thingiverse, and it was not going well.
The model looked good on my laptop screen but wasn't suitable for printing, a problem that will sound familiar to anyone working in the field. It had zero-area faces, incomplete topology, and normals pointing in the wrong direction. The model was a nonsensical description of a real, physical object.
This document discusses my ongoing research into improved workflows and interfaces for computer-aided design and manufacturing. These workflows are based on volumetric representation of solid objects, which eliminate many of the usual pain points of digital fabrication.
We start in the middle, discussing volumetric object representations. Next, we backtrack into functional representations and design tools that enable both sophisticated designs and personalization by novice users. We conclude with the physical portion of the workflow, including path planning and fabrication.
Volumetric Representation
The workflows described in this document use adaptively sampled distance fields (ASDFs) on an octree to represent solid objects.
In most other personal manufacturing workflows, solid objects are modelled with boundary representations. Examples of boundary representations include triangulated meshes and NURBS surfaces.
Unless a design represents an inflatable or fabric model, boundary representations are a poor approximation for reality. If you scratch away a patch on the surface of a solid object, you don't find an empty cavity inside; it is solid all the way through.
An ASDF represents a volume, not a boundary. It stores a recursive tree of cells subdividing a spatial region. Each cell is labelled as either filled, empty, branch, or leaf. Filled and empty cells are self-explanatory; branch cells split into eight subtrees; and leaf cells store samples of a signed distance field at all eight cell corners. The distance field measures how far this point is from the surface of the object, with negative values inside and positive outside.
Sample 2D part. Click to show treeRed cells are solid, blue are empty, green are leaf
The octree data structure takes advantage of spatial regularity, as filled parts of an object tend to be near other filled parts. The ASDF samples enable reconstruction of the surface and normals. The ASDF also merges neighboring cells to reduce the number of leaf nodes.
Functional Representation
How do we generate the samples defining an ASDF? In this workflow, we use functional representations as a powerful backend for CAD tools.
A functional representation represents a solid object as a mathematical expression that evaluates to the distance from a surface. This expression has a negative value inside the object, a positive value outside the object, and a zero value at the object's surface. For example, a sphere of radius one can be represented as F(X,Y,Z) = X2 +Y2 +Z2 - 1.
There are several advantages of this representation. Computation solid geometry becomes trivial: the intersection of two expressions A and B is simply max(A, B). The resulting expressions are also resolution-independent. To evaluate at a higher resolution, simply sample more points.
These expressions can be efficiently evaluated with interval arithmetic and recursive spatial subdivision. This evaluation strategy dovetails with the ASDF + octree volumetric representation discussed above, which is also based on spatial subdivision.
The picture below shows a complex model along with part of its functional representation.
In our workflow, functional representations are rendered to ASDFs by an high-speed computational geometry engine.
Design Tools
No one wants to write out math expressions by hand. This section presents a software tool named kokopelli which allow for high-level design. This tool also allows designers to create templates which can be personalized by novice users. It is one of multiple tools emerging from this research, all of which use functional representations as their geometry engine.
kokopelli mixes Python code with interactive UI elements to define solid objects. Python was chosen to remove the barrier of a custom hardware description language. The UI is inspired by Bret Victor's talk "Inventing on Principle".
Design by Sam Calisch It includes a set of Python libraries that define common 2 and 3-dimensional shapes, operations, and transforms. The flexible backend makes it easy to add user-defined geometric primitives.
In addition, it allows users to create interactive UI primitives (such as points, lines, and shapes), then refer to these primitives in the script. These primitives are themselves scriptable. In the image below, the x parameter of the point is defined as the radius of the larger circle.
Parameters are treated as arbitrary Python expressions and can refer to each other, forming a directed acyclic graph of constraints and definitions.
This workflow enables template designs that expose a subset of parameters for novice users to personalize. The video below shows a customizable design for a 2D pressfit boat. By dragging points, novice users can customize the size and shape of the boat without editing the source script.
Fabrication
The last step in the workflow transforms designs into physical objects.
This work extends a set of tools called the fab modules. These tools are used around the world in fab labs, community centers with tools for personal manufacturing.
Fab boombox made with the tools and techniques of the fab lab community. These tools interpret greyscale bitmaps as height maps of solid objects. Using bitmaps allows users to design with tools as simple as paint programs; more advanced users can export from their tool of choice. Working with a discrete representation also simplifies the path planning problem. The fab modules use a distance transform to offset for tool radius, then a variation on marching squares to find the required cuts.
The screenshot below shows path planning to manufacture the traces of a printed circuit board.
The fab modules share a common set of path-planning algorithms for many machines. Users are not required to learn a new workflow for each machine in a workshop, as the interfaces and terminology remains consistent.
In upcoming research, the fab modules will be extended to ASDF models. We are starting with two and three axis path planning and machining, directly from the ASDF representation and without triangulation. In the near future, this will be extended to additive and five-axis processes.
Conclusion
This document has described a broad swath of ongoing research in representations, workflows, and interfaces for digital fabrication.
We started by drawing a distinction between boundary and volumetric representations, summarizing the merits of distance field representations, and discussing ways to generate a volumetric model from a functional representation.
Next, we presented a specific design tool, kokopelli, and showed how it can be used to make both sophisticated designs and templates that can be personalized by novice users.
Finally, we discussed current and future work on path planning and manufacturing, all in the context of a triangle-free workflow.
Resources
My thesis proposal is a few months out of date but provides a more substantial bibliography and overview of prior work in this field.
kokopelli has been bundled into a stand-alone application (Mac OS 10.6+). The download includes a set of example files to get started. If it doesn't work on your machine, send me an email.
Source for the complete set of fab modules can be found on the downloads page. Compiling from source requires the listed dependancies.