Fast Linking Numbers
This tool, called
verifycurves, takes input models that consist of closed-loop curves, and outputs a topology certificate as a
.txt file. It is based on [Qu and James 2021]. Among the different linking-number computation methods described in [Qu and James 2021], this tool supports using Barnes–Hut or direct summation to evaluate the Gauss linking integral.
Project Webpage: https://graphics.stanford.edu/papers/fastlinkingnumbers/
Supplemental: Derivation of the Two-Tree Barnes–Hut expansion terms used in this implementation PDF
For Ubuntu, we tested with Ubuntu 18.04, gcc v7.5.0, CMake v3.10.2, gflags v2.2.1, libomp v10.0.0, and Eigen v3.3.4. For Windows, we tested with Windows 10, Visual Studio Community 2019 v16.10.2, CMake v3.20.5, and gflags v2.2.2, for 64-bit release.
You can install them on Ubuntu 18.04 via
sudo apt-get install libgflags-dev libeigen3-dev libomp-10-dev build-essential cmake -y
Building the executable verifycurves tool on Ubuntu
From the root source directory, you can build this like any other CMake project with these commands:
mkdir build cd build cmake .. make -j cd .. ln -s build/verifycurves verifycurves ln -s build/obj2bcc obj2bcc
To build only the
verifycurves executable, use
make -j verifycurves. Similarly you can use
make -j obj2bcc or
make -j libverifycurves to build the file format converter or the dynamic-link library.
Running on Windows
We've uploaded the compiled 64-bit windows binaries here. You may need to install the Microsoft Visual C++ Redistributable for Visual Studio 2019 runtime libraries if you do not already have them.
Building from the source code:
To build from the source code, download and install CMake, Eigen 3, gflags, and Microsoft Visual Studio 2019. Make a
build subdirectory. In
cmake-gui, set the project source directory and the build subdirectory. Click "Configure", making sure that it finds Eigen3 and gflags. Then click "Generate", then "Open Project". Build the solution, for Release x64, in Visual Studio.
Shared dynamic-link library
Alternately, you can also dynamically link this project against your code. To do so on Ubuntu, run the following lines after the above:
cd build sudo make install cd ..
Then simply include
includes/linking_number_certificate.h, as desired, into your project. Note that all of our projects are standalone and do not depend on this shared library.
Computing a topology certificate for an input model
verifycurves on any input model in the BCC file format to generate a certificate. The input models must contain only closed loops. The certificate will be a sparse matrix in triplet form, in plaintext (
.txt). The first row is the number of curves in the model, and in every subsequent row, the first two coordinates are the curve indices, and the third is the linking number between them. Curve indices are zero-based. Example input files are provided in the
data folder. Here is an example command:
./verifycurves --input data/glove.bcc --output results/glove.txt
This should be the output:
This output indicates that there are 70 curves and no pair of curves are linked.
You can also set
--method barneshut or
--method directsum to use Barnes–Hut or Direct Summation to compute the linking numbers. This tool by default uses Barnes–Hut. Here is another example command that tells the tool to use Direct Summation:
./verifycurves --input data/knittubebroken.bcc --output results/knittubebroken.txt --method directsum
This should be the output:
This output indicates that there are 39 curves, and curves 5 and 6 have a linking number of -2 between them, while all other curve pairs have a linking number of 0.
Comparing two topology certificates
As these sparse matrix representations are unique, one way to check the certificates is just using the bash
diff command on the two output certificate files.
./verifycurves --input data/knittubeinit.bcc --output results/knittubeinit.txt ./verifycurves --input data/knittubebroken.bcc --output results/knittubebroken.txt diff results/knittubeinit.txt results/knittubebroken.txt
Verifying an input model against an existing topology certificate
Alternately, you can also just run
verifycurves on an input model with the argument
--comparewith [CERTIFICATE_FILENAME] to compare the input model against the existing certifcate in
[CERTIFICATE_FILENAME]. You can also have it output a list of inconsistent loop pairs via
--diffpairs and a list of loops that participate in these pairs via
./verifycurves --input data/knittubebroken.bcc --comparewith results/knittubeinit.txt --diffpairs results/knittube.dp.txt --diffcurves results/knittube.dc.txt
These should be the output:
These outputs indicate, in this example, that the link between curves 5 and 6 is incorrect, with a difference of -2 between the before and after links.
Curve input file format
verifycurves takes the simple BCC (Binary Curve Collection) file format as input. See the file format specification from Cem Yuksel's Yarn-level Models webpage here and an example loading tutorial here. In addition to uniform Catmull–Rom splines, we added three more curve formats, so Bytes 4–5 in the header can be any of the following:
C0- Catmull–Rom curves with uniform parameterization
BS- Cubic B-Splines
BZ- Cubic Bézier curves
data folder has example BCC data files. You can find more input loopy structures from Cem Yuksel's Yarn-Level Models (the first 8 are looped knit structures that we can handle) and our extended input dataset (described below).
Converting from Blender and Houdini Obj files
Blender and Houdini curves can be passed to our tool by exporting them as lines in the OBJ file format, and then using
obj2bcc to convert it into BCC as closed curves.
obj2bcc with the
--input [INPUT] argument for input,
--segment_type [TYPE] to specify the segment type (we do not use the
cstype field in the OBJ format), and
--output [OUTPUT] for output:
./obj2bcc --input data/houdiniobj.obj --segment_type PL --output houdiniobj.bcc
Within the OBJ files, control points or polyline vertices must be represented as "l" (lines) rather than "curv" (curves) or "f" (faces). While most Houdini OBJ files work out of the box, when exporting from Blender, we require these line segments to be in order. One way to ensure this from Blender is by converting the object first to "Grease Pencil", and then converting it again to "Polygonal Curve." Then when you export as OBJ, the line segments will be in order. We've provided an example Blender obj and an example Houdini obj in the
data folder, as
houdiniobj.obj, respectively; these both correspond to the simpler Woundball used for the Figure 6 illustration.
We've included a few example data files in
data/ along with their reference certificates in
results/reference_certificates. You can run
. test.sh to generate your own output certificates for these files to compare against the reference certificates. Our extended dataset also has reference certificates included.
Sadly, we do not release unit or other tests in this code release. Modify this code at your own risk, and we suggest you create your own tests.
Accuracy versus performance tradeoff
The initial settings we provided produce correct linking numbers for our entire dataset and most yarn simulation data we have encountered. However, for certain specific other curve collections, you may need to tune the parameters to increase the accuracy if you do not trust the results. Here are a few ways:
To increase accuracy at the cost of performance, you can manually increase the
--barnes_hut_beta_limit parameters from their current default values of 2.0 and 10.0. Increasing beta drastically reduces error of the first Barnes–Hut run, but increases its runtime. For example, try:
./verifycurves --input data/glove.bcc --output results/glove.txt --barnes_hut_init_beta 5.0 --barnes_hut_beta_limit 10.0
The most accurate, yet slowest, method is to just use direct summation:
./verifycurves --input data/glove.bcc --output results/glove.txt --method directsum
Extended input dataset
Ante Qu and Doug L. James. 2021. Fast Linking Numbers for Topology Verification of Loopy Structures. ACM Trans. Graph. 40, 4, Article 106 (August 2021), 19 pages. https://doi.org/10.1145/3450626.3459778
The MIT license applies to all files in this codebase. In summary, you can reuse, modify, or distribute this, provided that you give attribution to us, at the minimum by copying the
If you modify them, you must maintain the license text in the headers of these files. If you have questions, reference their FAQ here.