Octrope: Fast computation of polygonal tube radius

Octrope is a library for quickly finding the thickness or ropelength of polygonal knots. While the precise definition of thickness is given in our paper describing the algorithm , a rough definition is that the thickness of a space curve is the diameter of the largest tubular neighborhood of the knot without self-intersections. For polygons, of course, the definition of tubular neighborhood poses some problems, so what Octrope computes is closely related to Rawdon’s definition of the thickness of a space polygon.

Octrope uses a fast clustering algorithm based on the idea of octrees to find thickness. We believe it to be the fastest currently available code for this computation (see our paper for details on our performance claims for the code), but the code is not fully modernized for the GPU computation era. It is likely that a vectorized/GPU algorithm could significantly outperform the current octrope code. The octrope distribution below was prepared using the GNU Autotools, and should configure itself and build under any reasonable Unix-like system with an ANSI-compatible C compiler. Please contact us if you have build problems. The octrope source is freely available under the GNU GPL . Users should note that some of the demo programs provided with the octrope distribution use argtable2 , which is also covered by the GPL.

Octrope, and its’ sister package Tsnnls form the computational core of our [Ridgerunner] software for simulating the tightening of knotted strings and other self-contact problems in physics and graphics. Some  animations of the Ridgerunner tightenings are posted here .


These links document octrope and some of the sample programs included in the distribution:


A bleeding edge version of octrope is always available from the Subversion repository at https://jasoncantarella.com/octrope. However, most users should stick to the point releases below.


As of version 1.3, liboctrope is changing its definition of thickness (and hence, of ropelength). Previous versions used DIAMETER of the tube as the thickness. 1.3 and all future versions use RADIUS of the tube as the thickness. So the thickness returned by octrope_thickness() will be half what it was previously and the ropelength returned by octrope_ropelength() will be twice what it was.

The parameter order for the octrope_thickness(), octrope_ropelength() and octrope() calls has changed to make this particularly visible to programmers using the library.


We were supported by the NSF during the development of octrope, and would also like to thank our collaborators, Eric Rawdon and Michael Piatek at Duquesne University for alpha-testing octrope. This work was funded by the the University of Georgia VIGRE grant DMS-00-8992 and DMS-02-04826 (to Cantarella and Fu).