octrope_link, octrope_linkstruct, octrope_link_new, octrope_link_free, octrope_link_read, octrope_link_write, octrope_link_edges, octrope_link_fix_wrap, pline - interface functions and data types for storing links in the octrope library.


Octrope library (liboctrope, -loctrope)


 typedef struct octrope_vector_type {   /* A point in 3-space. */
    double c[3];
  } octrope_vector;
 typedef struct octrope_color_type {
  double r;
  double g;
  double b;
  double alpha;
} octrope_color;

typedef struct octrope_pline_type { int acyclic; /* True if pline has distinct ends */ int nv; /* Number of vertices */ int cc; /* Color count (number of colors) */ octrope_vector *vt; /* Vertex buffer */ octrope_color *clr; /* Actual colors */ } octrope_pline;>

octrope_link *octrope_link_new(int components, int *nv, int *acyclic); void octrope_link_free(octrope_link *L);

octrope_link *octrope_link_read(FILE *infile); int octrope_link_write(FILE *outfile, octrope_link *L);

void octrope_link_fix_wrap(const octrope_link *L); int octrope_link_edges(const octrope_link *L); octrope_link *octrope_link_copy(octrope_link *L);


The octrope_link library consists of data types and interface functions designed for the efficient representation of polygonal links in 3-space. The fundamental data types, as given above, are the octrope_vector, the octrope_pline, and the octrope_link.

As expected, the octrope_vector is a 3-vector.

The octrope_pline type

The octrope_pline is a bit more subtle. The data type contains a buffer of nv vertices and the acyclic tag. The value of acyclic is TRUE (nonzero) when the space polygon has two ends, and FALSE (zero) when the space polygon is closed. For example, a line segment has nv == 2 and acyclic == TRUE, while a triangle has nv == 3 and acyclic == FALSE.

However, nv is not the size of the buffer vt allocated by octrope_link_new() and freed by octrope_link_free(). The reason for this is that in many geometric functions on polygonal curves, it is convenient to allow at least one step of ``wraparound'' addressing for closed curves. Using this feature often makes code much cleaner, faster, and more stable.

But implementing this efficiently is a problem for the library designer. The obvious solution (allowing access only through special interface functions or macros which encode wraparound addressing via modular arithmetic or branching) turns out to be too slow. For instance, a test implementation of the library with this interface was almost 30% slower than the current version. Therefore, we have chosen to implement one step of wraparound by adding copies of the last and first vertices to the buffer locations vt[-1] and vt[nv] when acyclic == FALSE. As long as the extra memory is correctly allocated (by octrope_link_new()) and freed (by octrope_link_free()), this should be transparent to users of this code.

Users may read and write freely from the buffer vt as long as their code does not depend on wraparound addressing. To use the wraparound addressing facility, call octrope_link_fix_wrap(L) to update the ``hidden'' elements of the array vt from the ``visible'' ones. Since octrope_link_fix_wrap() is very fast, it is acceptable to simply insert calls to it whenever one switches from writing to reading data from an octrope_link, or whenever one is unsure whether the hidden elements have been updated since the last write to the data structure. Many internal library functions use this procedure to ensure that wraparound addressing is updated before any other work is done.

The octrope_pline type also contains space for a buffer of colors, to ensure compatibility with the Geomview VECT specification. Currently, no use is made of these colors within the library, but they are read by octrope_link_read() and written by octrope_link_write().

The octrope_link type.

An octrope_link is simply an array of nc pointers to octrope_pline. No facility has been provided in this version of Octrope to work with these plines separately, and we discourage taking octrope_pline types out of their octrope_link wrappers: the proper representation for a single polygon in this library is as an octrope_link with one component.

octrope_link_new(): Allocating the octrope_link type

 octrope_link *octrope_link_new(int components, int *nv, int *acyclic);

creates a pointer to an octrope_link structure containing space for components octrope_pline structures where the ith octrope_pline has space for nv[i] vertices. The octrope_link structure itself is allocated inside octrope_link_new, and must be later freed (the function octrope_link_free() handles this automatically). The buffers nv and acyclic are copied into new memory locations inside octrope_link_new. It is hence safe to free them after a call to octrope_link_new if desired.

The acyclic array contains TRUE in acyclic[i] if the ith component of the link has distinct end vertices and FALSE if the ith component is closed.

octrope_link_free(): Destroying the octrope_link type

 void octrope_link_free(octrope_link *L);

frees all the memory associated with an octrope_link structure. As above, we note that the vertex buffers in the octrope_pline members of the cp array are larger than they appear, so freeing an octrope_link without using this function is likely to cause a memory leak.

octrope_link_read(): Read an octrope_link from a Geomview VECT file

 octrope_link *octrope_link_read(FILE *infile);

creates an octrope_link from the data in infile, which is assumed to be a Geomview VECT file. A VECT file is a text file which stores multi-component polygonal curves in human-readable format, with comments. The file format is documented with Geomview, at, which provides an interactive 3d viewer for such links on X windows/OpenGL capable systems. The VECT format also contains color information, which is recorded by octrope_link_read().

octrope_link_write(): Write an octrope_link to a Geomview VECT file

 int octrope_link_write(FILE *outfile, octrope_link *L);

writes the octrope_link L to the (open) text file outfile in the Geomview VECT format mentioned above. Returns TRUE if the write was successful, FALSE otherwise.

octrope_link_fix_wrap(): Provide ``wraparound addressing'' for octrope_pline.

 void octrope_link_fix_wrap(const octrope_link *L);

updates the vt (vertex) buffers in the members of L's cp array so that if a component L->cp[i] is closed (that is, L->cp[i]->acyclic == FALSE), then

   L->cp[i]->vt[-1] == L->cp[i]->vt[L->cp[i]->nv-1]


   L->cp[i]->vt[L->cp[i]->nv] = L->cp[i]->vt[0].

That is, it provides one element of ``wraparound addressing'' in the buffer L->cp[i]->vt. To implement this, the buffer L->cp[i]->vt actually contains L->cp[i]->nv + 2 elements, and L->cp[i]->vt[0] points to the second element of the buffer. This procedure copies the elements L->cp[i]->vt[0] and L->cp[i]->vt[L->cp[i]->nv-1] to the ``hidden'' locations in the vt buffer.

Call this procedure before any code which depends on wraparound addressing in the vt array.

octrope_link_edges(): Return edge count in an octrope_link.

 int octrope_link_edges(const octrope_link *L);

returns the number of edges in the octrope_link L.

octrope_link_copy(): Copy an octrope_link to new memory.

  octrope_link *octrope_link_copy(octrope_link *L);

allocates new memory using octrope_link_new() and copies the data from L into that space.


Ted Ashton and Jason Cantarella.


the liboctrope manpage


This library was first released in September 2004. It is described in the paper A Fast Octree-Based Algorithm for Computing Ropelength by Ashton and Cantarella, which is included in the library distribution as octrope-paper.pdf, and published in the World Scientific Press volume.


This library is covered by the GNU Public License for free software, modified as follows. Any publication of computations performed using the Octrope library must include a citation of the paper A Fast Octree-Based Algorithm for Computing Ropelength mentioned above.


Reading a link with octrope_link_read() and then writing it with octrope_link_write() loses information from the initial VECT file, since comments aren't preserved.