WebSVN – Kolibri OS – Diff – /programs/develop/libraries/cairo/src/cairo-bentley-ottmann.c

 /* Provide definitions for standalone compilation */
 #include "cairoint.h"
 #include "cairo-error-private.h"
 #include "cairo-freelist-private.h"
+#include "cairo-combsort-inline.h"
-#include "cairo-combsort-private.h"
+#include "cairo-traps-private.h"
 #define DEBUG_PRINT_STATE 0
 struct _cairo_bo_edge {
     cairo_edge_t edge;
     cairo_bo_edge_t *prev;
+    cairo_bo_edge_t *next;
-    cairo_bo_edge_t *next;
+    cairo_bo_edge_t *colinear;
     cairo_bo_trap_t deferred_trap;
 };
+{
     return a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
            a->p2.x == b->p2.x && a->p2.y == b->p2.y;
+}
-static int
+static inline int
-_cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t	*sweep_line,
+_cairo_bo_sweep_line_compare_edges (const cairo_bo_sweep_line_t	*sweep_line,
 				    const cairo_bo_edge_t	*a,
 				    const cairo_bo_edge_t	*b)
+{
     int cmp;
+    /* compare the edges if not identical */
+    if (! _line_equal (&a->edge.line, &b->edge.line)) {
+	if (MAX (a->edge.line.p1.x, a->edge.line.p2.x) <
+	    MIN (b->edge.line.p1.x, b->edge.line.p2.x))
+	    return -1;
+	else if (MIN (a->edge.line.p1.x, a->edge.line.p2.x) >
+		 MAX (b->edge.line.p1.x, b->edge.line.p2.x))
-    /* compare the edges if not identical */
+	    return 1;
     if (! _line_equal (&a->edge.line, &b->edge.line)) {
 	cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
 	if (cmp)
 static void
 _cairo_bo_event_queue_init (cairo_bo_event_queue_t	 *event_queue,
 			    cairo_bo_event_t		**start_events,
 			    int				  num_events)
+{
-    _cairo_bo_event_queue_sort (start_events, num_events);
-    start_events[num_events] = NULL;
     event_queue->start_events = start_events;
     _cairo_freepool_init (&event_queue->pool,
 			  sizeof (cairo_bo_queue_event_t));
 							   cairo_bo_edge_t	*left,
 							   cairo_bo_edge_t *right)
+{
     cairo_bo_point32_t intersection;
+    if (MAX (left->edge.line.p1.x, left->edge.line.p2.x) <=
+	MIN (right->edge.line.p1.x, right->edge.line.p2.x))
+	return CAIRO_STATUS_SUCCESS;
     if (_line_equal (&left->edge.line, &right->edge.line))
 	return CAIRO_STATUS_SUCCESS;
     sweep_line->stopped = NULL;
     sweep_line->current_y = INT32_MIN;
     sweep_line->current_edge = NULL;
+}
-static cairo_status_t
+static void
 _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t	*sweep_line,
 			     cairo_bo_edge_t		*edge)
+{
     if (sweep_line->current_edge != NULL) {
 		prev->next->prev = edge;
 	    prev->next = edge;
+	}
     } else {
 	sweep_line->head = edge;
+	edge->next = NULL;
+    }
-    sweep_line->current_edge = edge;
-    return CAIRO_STATUS_SUCCESS;
+    sweep_line->current_edge = edge;
+}
 static void
 	fclose (file);
+    }
+}
 #endif
+#define HAS_COLINEAR(a, b) ((cairo_bo_edge_t *)(((uintptr_t)(a))&~1) == (b))
+#define IS_COLINEAR(e) (((uintptr_t)(e))&1)
+#define MARK_COLINEAR(e, v) ((cairo_bo_edge_t *)(((uintptr_t)(e))|(v)))
 static inline cairo_bool_t
-edges_colinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
+edges_colinear (cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
+{
+    unsigned p;
+    if (HAS_COLINEAR(a->colinear, b))
+	return IS_COLINEAR(a->colinear);
+    if (HAS_COLINEAR(b->colinear, a)) {
+	p = IS_COLINEAR(b->colinear);
+	a->colinear = MARK_COLINEAR(b, p);
+	return p;
+    }
-{
+    p = 0;
+    p |= (a->edge.line.p1.x == b->edge.line.p1.x) << 0;
+    p |= (a->edge.line.p1.y == b->edge.line.p1.y) << 1;
+    p |= (a->edge.line.p2.x == b->edge.line.p2.x) << 3;
+    p |= (a->edge.line.p2.y == b->edge.line.p2.y) << 4;
+    if (p == ((1 << 0) | (1 << 1) | (1 << 3) | (1 << 4))) {
-    if (_line_equal (&a->edge.line, &b->edge.line))
+	a->colinear = MARK_COLINEAR(b, 1);
+	return TRUE;
-	return TRUE;
+    }
     if (_slope_compare (a, b)) {
+	a->colinear = MARK_COLINEAR(b, 0);
-    if (_slope_compare (a, b))
+	return FALSE;
 	return FALSE;
     /* The choice of y is not truly arbitrary since we must guarantee that it
      * is greater than the start of either line.
+     */
-     */
+    if (p != 0) {
-    if (a->edge.line.p1.y == b->edge.line.p1.y) {
+	/* colinear if either end-point are coincident */
-	return a->edge.line.p1.x == b->edge.line.p1.x;
+	p = (((p >> 1) & p) & 5) != 0;
     } else if (a->edge.line.p1.y < b->edge.line.p1.y) {
-	return edge_compare_for_y_against_x (b,
+	p = edge_compare_for_y_against_x (b,
-					     a->edge.line.p1.y,
+					  a->edge.line.p1.y,
-					     a->edge.line.p1.x) == 0;
+					  a->edge.line.p1.x) == 0;
     } else {
-	return edge_compare_for_y_against_x (a,
+	p = edge_compare_for_y_against_x (a,
+					  b->edge.line.p1.y,
+					  b->edge.line.p1.x) == 0;
+    }
 					     b->edge.line.p1.y,
-					     b->edge.line.p1.x) == 0;
+    a->colinear = MARK_COLINEAR(b, p);
-    }
+    return p;
+}
 /* Adds the trapezoid, if any, of the left edge to the #cairo_traps_t */
-static cairo_status_t
+static void
 _cairo_bo_edge_end_trap (cairo_bo_edge_t	*left,
 		   bot);
 #endif
+    }
-    trap->right = NULL;
-    return _cairo_traps_status (traps);
+    trap->right = NULL;
+}
 /* Start a new trapezoid at the given top y coordinate, whose edges
  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
  * then either add it to the traps in `traps', if the trapezoid's
  * right edge differs from `edge->next', or do nothing if the new
  * trapezoid would be a continuation of the existing one. */
-static inline cairo_status_t
+static inline void
 _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t	*left,
 				       cairo_bo_edge_t  *right,
-				       int               top,
-				       cairo_traps_t	*traps)
 				       int               top,
-    cairo_status_t status;
+				       cairo_traps_t	*traps)
+{
     if (left->deferred_trap.right == right)
-    if (left->deferred_trap.right == right)
+	return;
 	return CAIRO_STATUS_SUCCESS;
     assert (right);
     if (left->deferred_trap.right != NULL) {
-	if (right != NULL && edges_colinear (left->deferred_trap.right, right))
+	if (edges_colinear (left->deferred_trap.right, right))
+	{
 	    /* continuation on right, so just swap edges */
-	    left->deferred_trap.right = right;
-	    return CAIRO_STATUS_SUCCESS;
 	    left->deferred_trap.right = right;
+	    return;
 	status = _cairo_bo_edge_end_trap (left, top, traps);
 	if (unlikely (status))
-	    return status;
+	_cairo_bo_edge_end_trap (left, top, traps);
+    }
-    if (right != NULL && ! edges_colinear (left, right)) {
+    if (! edges_colinear (left, right)) {
 	left->deferred_trap.top = top;
 	left->deferred_trap.right = right;
-#if DEBUG_EVENTS
-	event_log ("begin trap: %lu %lu %d\n",
-		   (long) left,
+#if DEBUG_EVENTS
-		   (long) right,
+	event_log ("begin trap: %lu %lu %d\n",
-		   top);
+		   (long) left,
-#endif
+		   (long) right,
-    }
+		   top);
 #endif
     return CAIRO_STATUS_SUCCESS;
 }
+static inline void
-static inline cairo_status_t
+_active_edges_to_traps (cairo_bo_edge_t	*pos,
-_active_edges_to_traps (cairo_bo_edge_t		*left,
+			int32_t		 top,
-			int32_t			 top,
+			unsigned	 mask,
-			cairo_fill_rule_t	 fill_rule,
+			cairo_traps_t        *traps)
+{
-			cairo_traps_t	        *traps)
+    cairo_bo_edge_t *left;
-{
+    int in_out;
-    cairo_bo_edge_t *right;
-    cairo_status_t status;
 #if DEBUG_PRINT_STATE
-    printf ("Processing active edges for %x\n", top);
-#endif
-    if (fill_rule == CAIRO_FILL_RULE_WINDING) {
-	while (left != NULL) {
+    printf ("Processing active edges for %x\n", top);
-	    int in_out;
+#endif
-	    /* Greedily search for the closing edge, so that we generate the
-	     * maximal span width with the minimal number of trapezoids.
-	     */
+    in_out = 0;
-	    in_out = left->edge.dir;
+    left = pos;
+    while (pos != NULL) {
-	    /* Check if there is a co-linear edge with an existing trap */
-	    right = left->next;
-	    if (left->deferred_trap.right == NULL) {
-		while (right != NULL && right->deferred_trap.right == NULL)
-		    right = right->next;
-		if (right != NULL && edges_colinear (left, right)) {
-		    /* continuation on left */
-		    left->deferred_trap = right->deferred_trap;
-		    right->deferred_trap.right = NULL;
-		}
-	    }
-	    /* End all subsumed traps */
-	    right = left->next;
-	    while (right != NULL) {
-		if (right->deferred_trap.right != NULL) {
-		    status = _cairo_bo_edge_end_trap (right, top, traps);
-		    if (unlikely (status))
-			return status;
-		}
-		in_out += right->edge.dir;
-		if (in_out == 0) {
-		    cairo_bo_edge_t *next;
+	if (pos != left && pos->deferred_trap.right) {
+	    /* XXX It shouldn't be possible to here with 2 deferred traps
-		    cairo_bool_t skip = FALSE;
+	     * on colinear edges... See bug-bo-rictoz.
+	     */
-		    /* skip co-linear edges */
+	    if (left->deferred_trap.right == NULL &&
-		    next = right->next;
-		    if (next != NULL)
-			skip = edges_colinear (right, next);
-		    if (! skip)
-			break;
-		}
-		right = right->next;
 		edges_colinear (left, pos))
-	    status = _cairo_bo_edge_start_or_continue_trap (left, right,
-							    top, traps);
-	    if (unlikely (status))
-		return status;
-	    left = right;
-	    if (left != NULL)
-		left = left->next;
-	}
-    } else {
-	while (left != NULL) {
-	    int in_out = 0;
-	    right = left->next;
+	    {
+		/* continuation on left */
-	    while (right != NULL) {
+		left->deferred_trap = pos->deferred_trap;
-		if (right->deferred_trap.right != NULL) {
-		    status = _cairo_bo_edge_end_trap (right, top, traps);
+		pos->deferred_trap.right = NULL;
-		    if (unlikely (status))
+	    }
-			return status;
-		}
+	    else
 		if ((in_out++ & 1) == 0) {
-		    cairo_bo_edge_t *next;
-		    cairo_bool_t skip = FALSE;
 		_cairo_bo_edge_end_trap (pos, top, traps);
-		    /* skip co-linear edges */
-		    next = right->next;
-		    if (next != NULL)
-			skip = edges_colinear (right, next);
-		    if (! skip)
-			break;
-		}
+	    }
+	}
 		right = right->next;
-	    }
-	    status = _cairo_bo_edge_start_or_continue_trap (left, right,
-							    top, traps);
-	    if (unlikely (status))
+	in_out += pos->edge.dir;
-		return status;
+	if ((in_out & mask) == 0) {
 	    /* skip co-linear edges */
-	    left = right;
+	    if (pos->next == NULL || ! edges_colinear (pos, pos->next)) {
-	    if (left != NULL)
+		_cairo_bo_edge_start_or_continue_trap (left, pos, top, traps);
-		left = left->next;
+		left = pos->next;
-	}
+	    }
+	}
-    return CAIRO_STATUS_SUCCESS;
+	pos = pos->next;
-}
+    }
+}
 /* Execute a single pass of the Bentley-Ottmann algorithm on edges,
  * generating trapezoids according to the fill_rule and appending them
  * to traps. */
 static cairo_status_t
+_cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
+					    int			 num_events,
+					    unsigned		 fill_rule,
+					    cairo_traps_t	*traps,
+					    int			*num_intersections)
+{
-_cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
+    cairo_status_t status;
-					    int			 num_events,
+    int intersection_count = 0;
-					    cairo_fill_rule_t	 fill_rule,
+    cairo_bo_event_queue_t event_queue;
-					    cairo_traps_t	*traps,
+    cairo_bo_sweep_line_t sweep_line;
     while ((event = _cairo_bo_event_dequeue (&event_queue))) {
 	if (event->point.y != sweep_line.current_y) {
 	    for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
 		if (e1->deferred_trap.right != NULL) {
-		    status = _cairo_bo_edge_end_trap (e1,
+		    _cairo_bo_edge_end_trap (e1,
-						      e1->edge.bottom,
+					     e1->edge.bottom,
-						      traps);
-		    if (unlikely (status))
-			goto unwind;
+					     traps);
+		}
+	    }
 	    sweep_line.stopped = NULL;
-	    status = _active_edges_to_traps (sweep_line.head,
+	    _active_edges_to_traps (sweep_line.head,
-					     sweep_line.current_y,
-					     fill_rule, traps);
-	    if (unlikely (status))
+				    sweep_line.current_y,
-		goto unwind;
+				    fill_rule, traps);
 	switch (event->type) {
 	case CAIRO_BO_EVENT_TYPE_START:
 	    e1 = &((cairo_bo_start_event_t *) event)->edge;
-	    status = _cairo_bo_sweep_line_insert (&sweep_line, e1);
 	    if (unlikely (status))
-		goto unwind;
+	    _cairo_bo_sweep_line_insert (&sweep_line, e1);
+    }
     *num_intersections = intersection_count;
     for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
 	if (e1->deferred_trap.right != NULL) {
-	    status = _cairo_bo_edge_end_trap (e1, e1->edge.bottom, traps);
-	    if (unlikely (status))
-		break;
+	    _cairo_bo_edge_end_trap (e1, e1->edge.bottom, traps);
+	}
+    }
     status = traps->status;
  unwind:
     _cairo_bo_event_queue_fini (&event_queue);
 _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t	 *traps,
 					   const cairo_polygon_t *polygon,
 					   cairo_fill_rule_t	  fill_rule)
+{
     int intersections;
-    cairo_status_t status;
     cairo_bo_start_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t)];
     cairo_bo_start_event_t *events;
     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
     cairo_bo_event_t **event_ptrs;
+    cairo_bo_start_event_t *stack_event_y[64];
+    cairo_bo_start_event_t **event_y = NULL;
-    int num_events;
+    int i, num_events, y, ymin, ymax;
-    int i;
+    cairo_status_t status;
     num_events = polygon->num_edges;
     if (unlikely (0 == num_events))
+	return CAIRO_STATUS_SUCCESS;
+    if (polygon->num_limits) {
+	ymin = _cairo_fixed_integer_floor (polygon->limit.p1.y);
+	ymax = _cairo_fixed_integer_ceil (polygon->limit.p2.y) - ymin;
+	if (ymax > 64)
+	    event_y = _cairo_malloc_ab(sizeof (cairo_bo_event_t*), ymax);
+	else
+	    event_y = stack_event_y;
+	memset (event_y, 0, ymax * sizeof(cairo_bo_event_t *));
 	return CAIRO_STATUS_SUCCESS;
     events = stack_events;
     event_ptrs = stack_event_ptrs;
     if (num_events > ARRAY_LENGTH (stack_events)) {
 	event_ptrs = (cairo_bo_event_t **) (events + num_events);
+    }
-    for (i = 0; i < num_events; i++) {
 	event_ptrs[i] = (cairo_bo_event_t *) &events[i];
     for (i = 0; i < num_events; i++) {
 	events[i].type = CAIRO_BO_EVENT_TYPE_START;
 	events[i].point.y = polygon->edges[i].top;
 	events[i].point.x =
 	    _line_compute_intersection_x_for_y (&polygon->edges[i].line,
 						events[i].point.y);
 	events[i].edge.edge = polygon->edges[i];
+	events[i].edge.deferred_trap.right = NULL;
+	events[i].edge.prev = NULL;
+	events[i].edge.next = NULL;
+	events[i].edge.colinear = NULL;
+	if (event_y) {
+	    y = _cairo_fixed_integer_floor (events[i].point.y) - ymin;
+	    events[i].edge.next = (cairo_bo_edge_t *) event_y[y];
-	events[i].edge.deferred_trap.right = NULL;
+	    event_y[y] = (cairo_bo_start_event_t *) &events[i];
+	} else
+	    event_ptrs[i] = (cairo_bo_event_t *) &events[i];
+    }
+    if (event_y) {
+	for (y = i = 0; y < ymax && i < num_events; y++) {
+	    cairo_bo_start_event_t *e;
+	    int j = i;
+	    for (e = event_y[y]; e; e = (cairo_bo_start_event_t *)e->edge.next)
+		event_ptrs[i++] = (cairo_bo_event_t *) e;
+	    if (i > j + 1)
+		_cairo_bo_event_queue_sort (event_ptrs+j, i-j);
+	}
+	if (event_y != stack_event_y)
+	    free (event_y);
-	events[i].edge.prev = NULL;
+    } else
-	events[i].edge.next = NULL;
+	_cairo_bo_event_queue_sort (event_ptrs, i);
     event_ptrs[i] = NULL;
 #if DEBUG_TRAPS
     dump_edges (events, num_events, "bo-polygon-edges.txt");
 #endif
-    /* XXX: This would be the convenient place to throw in multiple
-     * passes of the Bentley-Ottmann algorithm. It would merely
+    /* XXX: This would be the convenient place to throw in multiple
-     * require storing the results of each pass into a temporary
+     * passes of the Bentley-Ottmann algorithm. It would merely
-     * cairo_traps_t. */
+     * require storing the results of each pass into a temporary
-    status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs,
+     * cairo_traps_t. */
-							 num_events,
+    status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs, num_events,
 #if DEBUG_TRAPS
     dump_traps (traps, "bo-traps-in.txt");
-#endif
+#endif
     _cairo_polygon_init (&polygon);
-    _cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
+    _cairo_polygon_init (&polygon, traps->limits, traps->num_limits);
     for (i = 0; i < traps->num_traps; i++) {

Subversion Repositories Kolibri OS

(root)/programs/develop/libraries/cairo/src/cairo-bentley-ottmann.c – Rev 1892 → 3959