Libart: Sorted Vector Paths

typedef struct _ArtDRect ArtDRect;
typedef struct _ArtPoint ArtPoint;

struct _ArtDRect {
  double x0, y0, x1, y1;
};

struct _ArtPoint {
  double x, y;
};

typedef struct _ArtSVP ArtSVP;
typedef struct _ArtSVPSeg ArtSVPSeg;

struct _ArtSVPSeg {
  int n_points;
  int dir; /* == 0 for "up", 1 for "down" */
  ArtDRect bbox;
  ArtPoint *points;
};

struct _ArtSVP {
  int n_segs;
  ArtSVPSeg segs[1];
};
ArtSVP is libart's data structure for representing sorted vector paths. Related data structures include Vector paths.

A sorted vector path has two features that make it more suitable for fast manipulation than ordinary vector paths. First, each segment has an enclosing bounding box, making it easy to cull segments outside the region of interest. Second, each segment contains points that are sorted in order of increasing y coordinate. Thus, the svp is the data structure of choice for scanline algorithms, including rendering and the vector geometry operations (union, intersection, difference, etc).

Because of the requirement that the points in a segment have increasing y coordinate, an svp in general has more segments than a corresponding vpath. Functions exist to convert freely between vector paths and svp's, subject to the condition that all segments are closed (i.e. the distinction between open and closed paths sharing final endpoints is not made in svp's).

An svp is represented in memory as a simple structure consisting of the number of segments, followed directly by an array of segments. Each segment contains a number of points, a direction, an enclosing bounding box, and a pointer to a list of points. The bounding box should be the minimal enclosing rectangle of the points. Regardless of the direction, the points in the array should be sorted in increasing y order. In case of tie, the x coordinate breaks the tie, i.e. the actual ordering is a lexicographical ordering over (y, x).

Most libart operations require closed svp's. This invariant can be stated formally, that a matching between all top and bottom points exists, subject to the following constraints:

The top point of each segment corresponds to either a bottom point of another segment with the same direction, or the top point of another segment with opposite direction, and conversely,
The bottom point of each segment corresponds to either a top point of another segment with the same direction, or the bottom point of another segment with opposite direction.

The matching need not be unique. Thus, figure-eight paths are legal closed svp's.

On a closed svp, the concept of winding number is well defined. The winding number of a point can be determined by counting the intersections of the horizontal line stretching from minus infinity to the point with the svp lines. The winding number is equal to the number of downward lines minus the number of upward lines.

Two other invariants apply for selected libart operations:
The nocross invariant informally requires that lines do not cross each other, i.e. that all intersections occur at the endpoints of segments. The exact formal definition of nocross is currently being revised to handle boundary cases with good numerical stability.

On a closed svp satisfying the nocross invariant, winding number of segments is also well defined. Drawing a horizontal line from negative infinity to any point on the segment, the winding number is equal to the number of downward lines crossed (including the segment being tested, if downward) minus the number of upward lines crossed (not including the segment being tested). The nocross invariant implies that the winding number is the same no matter which point on the segment is chosen.

The onewind invariant simply requires that all segments have a winding number of one. Most of the low-level rendering operations on vector paths require a closed svp satisfying the nocross and onewind invariants.

libart