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 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().
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 *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.
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 *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 http://www.geomview.org, 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().
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.
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]
and
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.
int octrope_link_edges(const octrope_link *L);
returns the number of edges in the octrope_link L.
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.
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.