spans: Add a Bentley-Ottmann variant on the Tor scan converter

This variant uses the Bentley-Ottmann algorithm to only maintain the
active edge list upon edge events and so can efficiently skip areas
where no change occurs. This means that it can be much quicker than the
Tor algorithm (which is still used to compute the coverages from the
active edges) for geometries consisting of long straight lines with few
intersections. However due to the computational overhead of the
Bentley-Ottmann event processing, for dense curvy paths, simply updating
the active edge list in sync with computing the coverages is a win. Due
to advantageous adaptive step size, the scan converter can be run at a
much higher subsampling with little extra overhead compared with Tor,
currently it uses a 256x256 subsampling grid to avoid any impedance
mismatch with path precision.

Given the current status of implementations, this scan converter [botor]
is likely to be advantage where detecting large regions of unchanged
span data will result in improved performance, for instance the drm
backends which convert the scan data into rectangles.

1 files changed, 16 insertions, 0 deletions

diff --git a/src/cairo-freelist-private.h b/src/cairo-freelist-private.h
index 5be22b1f9..43dde29ca 100644
--- a/src/cairo-freelist-private.h
+++ b/src/cairo-freelist-private.h
@@ -54,6 +54,7 @@ struct _cairo_freelist_pool {
 typedef struct _cairo_freepool {
     cairo_freelist_node_t *first_free_node;
     cairo_freelist_pool_t *pools;
+    cairo_freelist_pool_t *freepools;
     unsigned nodesize;
     cairo_freelist_pool_t embedded_pool;
     uint8_t embedded_data[1000];
@@ -96,6 +97,21 @@ _cairo_freepool_init (cairo_freepool_t *freepool, unsigned nodesize);
 cairo_private void
 _cairo_freepool_fini (cairo_freepool_t *freepool);
 
+static inline void
+_cairo_freepool_reset (cairo_freepool_t *freepool)
+{
+    while (freepool->pools != &freepool->embedded_pool) {
+	cairo_freelist_pool_t *pool = freepool->pools;
+	freepool->pools = pool->next;
+	pool->next = freepool->freepools;
+	freepool->freepools = pool;
+    }
+
+    freepool->embedded_pool.rem = sizeof (freepool->embedded_data);
+    freepool->embedded_pool.data = freepool->embedded_data;
+}
+
+
 cairo_private void *
 _cairo_freepool_alloc_from_new_pool (cairo_freepool_t *freepool);