Knotty generates a single, continuous knot that resembles an arbitrary input geometry. We solve a 3D Eulerian cycle an the faces of an input object. We 3D printed a few of the output geometry files, and presented a paper at Bridges 2012.

Our class report is available, as well as a video showing the steps of our program, and a video that animates a knot.

Introduction

Knotty takes in an arbitrary OBJ file and output a “knotted” representation of it. It’s modeled using a single string, and we can output our file to OBJ or STL. We used the STL to 3d print a few of our models.

Background

I took CS285 in Fall 2011. As it was a class in solid modeling (the 3D Printing one, not the fashion kind), our final project was to create an interesting physical object.

I created Knotty along with Andrew Lee, for just the purpose of making a really nice physical object. You can read our final report, or view our project’s source.

Technical

Our project was written entirely in Python. We used PyOpenGL to display our results, and NumPy for math functions.

Besides using PyOpenGL and NumPy to assist us in hardware interaction and math functions, we wrote the project completely from scratch. That is, we wrote an OBJ/ STL reader/writer, our own voxel file format, and a sweep program, in addition to our algorithm.

The first thing we do is load the input OBJ. We then create an axis-aligned voxel grid with a user-specified resolution, and mark a voxel as “full” when a triangle exists with in it, and empty otherwise. Note that this is not a space-filling voxelization. Because we are only making a knot of the object’s outer surface, we only need the outer voxels.

Once we have the outer voxels, we view each as a cube, and select only the outwards-facing faces of each cube. This can now be viewed as a “blocky” quadrilateralization of the original input.

We then create a large graph of each connecting face. That is, each face becomes a node that can reference the nodes next to them. Because each face has four faces connected to it due to our voxelization, we can say each node has valence four. Because each node is valence four, an Eulerian cycle is guaranteed to exist. An Eulerian cycle is a path through a graph that visits every edge once.

We find an Eulerian cycle through the nodes using a modified Hierholzer’s algorithm. The algorithm is mostly the same, but we give preference to paths that are kept mostly straight.

This Eulerian cycle is converted into b-splines by creating control points in one of a three predetermined cases. Connecting the splines together, we obtain a geometrically and parametrically continuous. Since the Eulerian cycle wraps back onto itself, there is no set beginning or end, so the resulting b-spline is a single loop through the entire shape. The b-spline is sampled using De Casteljau’s algorithm.

We then create a sweep through the b-spline, meaning that we trace a 2D cross-section through the b-spline to make a 3D representation. We used a rotation minimizing frame to remove inflection and keep the mesh well behaved. In the case of our project, we used another b-spline to define a circular cross-section to look like string. The output is a watertight closed manifold, and we output it to OBJ or STL for use with a FDM.