Compound path is a connected sequence of elementary curves (rational Bézier curves, segments and elliptic arcs – see Elementary curves).
GEOMLIB contains two classes that can hold compound paths of arbitrary length, path and fpath.
The first one only extends the group class by geometrical routines. The second path type can be used only
in some specific situations and implements extra internal allocator to increase performance of curves inserting. All methods common to
elementary curves should also work for compound paths (with differences in parametrization).
struct geom_path {
struct geom_group group; /* ancestor instance structure */
real alength; /* cached Euclidean arc length */
};
The previous structure is derived from the group class, which implements manipulation with ordered sets of items.
Compound paths use inherited functions to store the list of connected elementary curves and cannot contain other
item descendants. Exact continuity of neighbor curves is not checked, but it is assumed, that there are
only inconsiderable errors. In the other case, behaviour of some algorithms is undefined.
The TIME parametrization of compound path is defined as a composition of all TIME parametrization intervals incident to
contained elementary curves. Parameter t in the i-th curve (started from zero) corresponds to i+t
parameter in the compound path.
The major part of implementation is redefinition of abstract geometrical routines derived from the group class.
Most of them are very intuitive and do not need detailed description. Usually, a specialized method is called for
each elementary curve and results are merged to agree with entire path. If it is necessary, TIME parameters
are converted between the path and elementary curves. Full implementation with brief comments can be found
in geomlib/path.h and geomlib/path.c.
Paths remember their Bézier expansions when they are generated. There is no automated mechanism
how to propagate changes to the path from elementary curves or inherited group methods.
After any change in the path (insertion, deletion or a curve modification), user should manually
call geom_path_after_change to invalidate cached values.
Left curves in common paths are automatically freed in the path destructor. All inserted curves, that were
not allocated using xmalloc must be removed manually before calling the destructor.
Here follows a simple example of path structure usage:
struct geom_path path;
struct geom_segment *segment1, *segment2;
struct geom_elliptic_arc *arc;
void *curve;
/* ... curves allocation */
/* path instance creation */
geom_instance_init(&path, GEOM_CLASS(path));
geom_path_create(&path);
/* insertion of some preallocated elementary curves */
geom_group_add_tail(&path, segment1);
geom_group_add_tail(&path, arc);
geom_group_add_tail(&path, segment2);
geom_path_after_change(&path);
/* loop over inserted curves */
GEOM_GROUP_WALK(&path, curve) {
/*... */
}
/* path instance destruction,
curves are freed automatically */
geom_path_destroy(&path);
struct geom_fpath {
struct geom_path path; /* ancestor instance structure */
struct geom_fpath_block *block_last; /* set of allocated memory blocks */
byte *block_ptr; /* start of unused part of last block */
uns block_free; /* size of last block unused part in bytes */
uns total_size; /* size of last block in bytes */
};
/* memory block of fpath allocator */
struct geom_fpath_block {
struct geom_fpath_block *prev; /* linked list pointer */
byte start; /* start of data buffer */
};
The class fpath is derived from path. The added feature is a simple greedy internal allocator for elementary curves,
that is optimized for fast memory allocation. Releasing of allocated memory is impossible until the path is cleared or destroyed.
The life cycle of a fpath instance has two phases. In the first phase, only allocations and insertions are allowed.
To get to the second phase, geom_fpath_finish must be called. After that, the path is fixed and no changes may not be made.
Geometric routines can be called in the second phase only. This interface is more strict than it would be necessary for implemented
allocator, but it allows some planned future optimizations. A typical situation where fpath outperforms path in
combination with global allocator is computing of Bézier expansions.
The allocator contains a link list of memory blocks reserved by xmalloc. New curves are always placed at
the first unused byte of the last block. If there is not enough space, a new block is allocated and added to end of the list.
Sizes of new blocks increase exponentially.
The function headers and source code can be found in geomlib/fpath.h and geomlib/fpath.c.
The following example shows a typical fpath usage:
struct geom_fpath path;
struct geom_segment *segment1, *segment2;
struct geom_elliptic_arc *arc;
void *curve;
/* fpath instance creation */
geom_instance_init(&path, GEOM_CLASS(fpath));
geom_fpath_create(&path);
/* FIRST PHASE */
/* insertion of some preallocated elementary curves */
segment1 = GEOM_FPATH_APPEND_NEW(&path, segment);
/* ... segment1 initialization */
arc = GEOM_FPATH_APPEND_NEW(&path, elliptic_arc);
/* ... arc initialization */
segment2 = GEOM_FPATH_APPEND_NEW(&path, segment);
/* ... segment2 initialization */
geom_fpath_finish(&path);
/* SECOND PHASE */
/* ... from now, geometric routines are allowed */
/* fpath instance destruction */
geom_fpath_destroy(&path);