0,0 → 1,690 |
/* |
* Copyright © 2004 Carl Worth |
* Copyright © 2006 Red Hat, Inc. |
* Copyright © 2009 Chris Wilson |
* Copyright © 2011 Intel Corporation |
* |
* This library is free software; you can redistribute it and/or |
* modify it either under the terms of the GNU Lesser General Public |
* License version 2.1 as published by the Free Software Foundation |
* (the "LGPL") or, at your option, under the terms of the Mozilla |
* Public License Version 1.1 (the "MPL"). If you do not alter this |
* notice, a recipient may use your version of this file under either |
* the MPL or the LGPL. |
* |
* You should have received a copy of the LGPL along with this library |
* in the file COPYING-LGPL-2.1; if not, write to the Free Software |
* Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA |
* You should have received a copy of the MPL along with this library |
* in the file COPYING-MPL-1.1 |
* |
* The contents of this file are subject to the Mozilla Public License |
* Version 1.1 (the "License"); you may not use this file except in |
* compliance with the License. You may obtain a copy of the License at |
* http://www.mozilla.org/MPL/ |
* |
* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY |
* OF ANY KIND, either express or implied. See the LGPL or the MPL for |
* the specific language governing rights and limitations. |
* |
* The Original Code is the cairo graphics library. |
* |
* The Initial Developer of the Original Code is Carl Worth |
* |
* Contributor(s): |
* Carl D. Worth <cworth@cworth.org> |
* Chris Wilson <chris@chris-wilson.co.uk> |
*/ |
|
/* Provide definitions for standalone compilation */ |
#include "cairoint.h" |
|
#include "cairo-boxes-private.h" |
#include "cairo-error-private.h" |
#include "cairo-combsort-inline.h" |
#include "cairo-list-private.h" |
|
#include <setjmp.h> |
|
typedef struct _rectangle rectangle_t; |
typedef struct _edge edge_t; |
|
struct _edge { |
edge_t *next, *prev; |
edge_t *right; |
cairo_fixed_t x, top; |
int a_or_b; |
int dir; |
}; |
|
struct _rectangle { |
edge_t left, right; |
int32_t top, bottom; |
}; |
|
#define UNROLL3(x) x x x |
|
/* the parent is always given by index/2 */ |
#define PQ_PARENT_INDEX(i) ((i) >> 1) |
#define PQ_FIRST_ENTRY 1 |
|
/* left and right children are index * 2 and (index * 2) +1 respectively */ |
#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1) |
|
typedef struct _pqueue { |
int size, max_size; |
|
rectangle_t **elements; |
rectangle_t *elements_embedded[1024]; |
} pqueue_t; |
|
typedef struct _sweep_line { |
rectangle_t **rectangles; |
pqueue_t pq; |
edge_t head, tail; |
edge_t *insert_left, *insert_right; |
int32_t current_y; |
int32_t last_y; |
|
jmp_buf unwind; |
} sweep_line_t; |
|
#define DEBUG_TRAPS 0 |
|
#if DEBUG_TRAPS |
static void |
dump_traps (cairo_traps_t *traps, const char *filename) |
{ |
FILE *file; |
int n; |
|
if (getenv ("CAIRO_DEBUG_TRAPS") == NULL) |
return; |
|
file = fopen (filename, "a"); |
if (file != NULL) { |
for (n = 0; n < traps->num_traps; n++) { |
fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n", |
traps->traps[n].top, |
traps->traps[n].bottom, |
traps->traps[n].left.p1.x, |
traps->traps[n].left.p1.y, |
traps->traps[n].left.p2.x, |
traps->traps[n].left.p2.y, |
traps->traps[n].right.p1.x, |
traps->traps[n].right.p1.y, |
traps->traps[n].right.p2.x, |
traps->traps[n].right.p2.y); |
} |
fprintf (file, "\n"); |
fclose (file); |
} |
} |
#else |
#define dump_traps(traps, filename) |
#endif |
|
static inline int |
rectangle_compare_start (const rectangle_t *a, |
const rectangle_t *b) |
{ |
return a->top - b->top; |
} |
|
static inline int |
rectangle_compare_stop (const rectangle_t *a, |
const rectangle_t *b) |
{ |
return a->bottom - b->bottom; |
} |
|
static inline void |
pqueue_init (pqueue_t *pq) |
{ |
pq->max_size = ARRAY_LENGTH (pq->elements_embedded); |
pq->size = 0; |
|
pq->elements = pq->elements_embedded; |
pq->elements[PQ_FIRST_ENTRY] = NULL; |
} |
|
static inline void |
pqueue_fini (pqueue_t *pq) |
{ |
if (pq->elements != pq->elements_embedded) |
free (pq->elements); |
} |
|
static cairo_bool_t |
pqueue_grow (pqueue_t *pq) |
{ |
rectangle_t **new_elements; |
pq->max_size *= 2; |
|
if (pq->elements == pq->elements_embedded) { |
new_elements = _cairo_malloc_ab (pq->max_size, |
sizeof (rectangle_t *)); |
if (unlikely (new_elements == NULL)) |
return FALSE; |
|
memcpy (new_elements, pq->elements_embedded, |
sizeof (pq->elements_embedded)); |
} else { |
new_elements = _cairo_realloc_ab (pq->elements, |
pq->max_size, |
sizeof (rectangle_t *)); |
if (unlikely (new_elements == NULL)) |
return FALSE; |
} |
|
pq->elements = new_elements; |
return TRUE; |
} |
|
static inline void |
pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle) |
{ |
rectangle_t **elements; |
int i, parent; |
|
if (unlikely (sweep->pq.size + 1 == sweep->pq.max_size)) { |
if (unlikely (! pqueue_grow (&sweep->pq))) { |
longjmp (sweep->unwind, |
_cairo_error (CAIRO_STATUS_NO_MEMORY)); |
} |
} |
|
elements = sweep->pq.elements; |
for (i = ++sweep->pq.size; |
i != PQ_FIRST_ENTRY && |
rectangle_compare_stop (rectangle, |
elements[parent = PQ_PARENT_INDEX (i)]) < 0; |
i = parent) |
{ |
elements[i] = elements[parent]; |
} |
|
elements[i] = rectangle; |
} |
|
static inline void |
pqueue_pop (pqueue_t *pq) |
{ |
rectangle_t **elements = pq->elements; |
rectangle_t *tail; |
int child, i; |
|
tail = elements[pq->size--]; |
if (pq->size == 0) { |
elements[PQ_FIRST_ENTRY] = NULL; |
return; |
} |
|
for (i = PQ_FIRST_ENTRY; |
(child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size; |
i = child) |
{ |
if (child != pq->size && |
rectangle_compare_stop (elements[child+1], |
elements[child]) < 0) |
{ |
child++; |
} |
|
if (rectangle_compare_stop (elements[child], tail) >= 0) |
break; |
|
elements[i] = elements[child]; |
} |
elements[i] = tail; |
} |
|
static inline rectangle_t * |
rectangle_pop_start (sweep_line_t *sweep_line) |
{ |
return *sweep_line->rectangles++; |
} |
|
static inline rectangle_t * |
rectangle_peek_stop (sweep_line_t *sweep_line) |
{ |
return sweep_line->pq.elements[PQ_FIRST_ENTRY]; |
} |
|
CAIRO_COMBSORT_DECLARE (_rectangle_sort, |
rectangle_t *, |
rectangle_compare_start) |
|
static void |
sweep_line_init (sweep_line_t *sweep_line, |
rectangle_t **rectangles, |
int num_rectangles) |
{ |
_rectangle_sort (rectangles, num_rectangles); |
rectangles[num_rectangles] = NULL; |
sweep_line->rectangles = rectangles; |
|
sweep_line->head.x = INT32_MIN; |
sweep_line->head.right = NULL; |
sweep_line->head.dir = 0; |
sweep_line->head.next = &sweep_line->tail; |
sweep_line->tail.x = INT32_MAX; |
sweep_line->tail.right = NULL; |
sweep_line->tail.dir = 0; |
sweep_line->tail.prev = &sweep_line->head; |
|
sweep_line->insert_left = &sweep_line->tail; |
sweep_line->insert_right = &sweep_line->tail; |
|
sweep_line->current_y = INT32_MIN; |
sweep_line->last_y = INT32_MIN; |
|
pqueue_init (&sweep_line->pq); |
} |
|
static void |
sweep_line_fini (sweep_line_t *sweep_line) |
{ |
pqueue_fini (&sweep_line->pq); |
} |
|
static void |
end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot, cairo_boxes_t *out) |
{ |
if (likely (left->top < bot)) { |
cairo_status_t status; |
cairo_box_t box; |
|
box.p1.x = left->x; |
box.p1.y = left->top; |
box.p2.x = left->right->x; |
box.p2.y = bot; |
|
status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box); |
if (unlikely (status)) |
longjmp (sweep_line->unwind, status); |
} |
|
left->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 void |
start_or_continue_box (sweep_line_t *sweep_line, |
edge_t *left, |
edge_t *right, |
int top, |
cairo_boxes_t *out) |
{ |
if (left->right == right) |
return; |
|
if (left->right != NULL) { |
if (right != NULL && left->right->x == right->x) { |
/* continuation on right, so just swap edges */ |
left->right = right; |
return; |
} |
|
end_box (sweep_line, left, top, out); |
} |
|
if (right != NULL && left->x != right->x) { |
left->top = top; |
left->right = right; |
} |
} |
|
static inline int is_zero(const int *winding) |
{ |
return winding[0] == 0 || winding[1] == 0; |
} |
|
static inline void |
active_edges (sweep_line_t *sweep, cairo_boxes_t *out) |
{ |
int top = sweep->current_y; |
int winding[2] = { 0 }; |
edge_t *pos; |
|
if (sweep->last_y == sweep->current_y) |
return; |
|
pos = sweep->head.next; |
if (pos == &sweep->tail) |
return; |
|
do { |
edge_t *left, *right; |
|
left = pos; |
do { |
winding[left->a_or_b] += left->dir; |
if (!is_zero (winding)) |
break; |
if (left->next == &sweep->tail) |
goto out; |
|
if (unlikely (left->right != NULL)) |
end_box (sweep, left, top, out); |
|
left = left->next; |
} while (1); |
|
right = left->next; |
do { |
if (unlikely (right->right != NULL)) |
end_box (sweep, right, top, out); |
|
winding[right->a_or_b] += right->dir; |
if (is_zero (winding)) { |
/* skip co-linear edges */ |
if (likely (right->x != right->next->x)) |
break; |
} |
|
right = right->next; |
} while (TRUE); |
|
start_or_continue_box (sweep, left, right, top, out); |
|
pos = right->next; |
} while (pos != &sweep->tail); |
|
out: |
sweep->last_y = sweep->current_y; |
} |
|
static inline void |
sweep_line_delete_edge (sweep_line_t *sweep_line, edge_t *edge, cairo_boxes_t *out) |
{ |
if (edge->right != NULL) { |
edge_t *next = edge->next; |
if (next->x == edge->x) { |
next->top = edge->top; |
next->right = edge->right; |
} else { |
end_box (sweep_line, edge, sweep_line->current_y, out); |
} |
} |
|
if (sweep_line->insert_left == edge) |
sweep_line->insert_left = edge->next; |
if (sweep_line->insert_right == edge) |
sweep_line->insert_right = edge->next; |
|
edge->prev->next = edge->next; |
edge->next->prev = edge->prev; |
} |
|
static inline void |
sweep_line_delete (sweep_line_t *sweep, |
rectangle_t *rectangle, |
cairo_boxes_t *out) |
{ |
sweep_line_delete_edge (sweep, &rectangle->left, out); |
sweep_line_delete_edge (sweep, &rectangle->right, out); |
|
pqueue_pop (&sweep->pq); |
} |
|
static inline void |
insert_edge (edge_t *edge, edge_t *pos) |
{ |
if (pos->x != edge->x) { |
if (pos->x > edge->x) { |
do { |
UNROLL3({ |
if (pos->prev->x <= edge->x) |
break; |
pos = pos->prev; |
}) |
} while (TRUE); |
} else { |
do { |
UNROLL3({ |
pos = pos->next; |
if (pos->x >= edge->x) |
break; |
}) |
} while (TRUE); |
} |
} |
|
pos->prev->next = edge; |
edge->prev = pos->prev; |
edge->next = pos; |
pos->prev = edge; |
} |
|
static inline void |
sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle) |
{ |
edge_t *pos; |
|
/* right edge */ |
pos = sweep->insert_right; |
insert_edge (&rectangle->right, pos); |
sweep->insert_right = &rectangle->right; |
|
/* left edge */ |
pos = sweep->insert_left; |
if (pos->x > sweep->insert_right->x) |
pos = sweep->insert_right->prev; |
insert_edge (&rectangle->left, pos); |
sweep->insert_left = &rectangle->left; |
|
pqueue_push (sweep, rectangle); |
} |
|
static cairo_status_t |
intersect (rectangle_t **rectangles, int num_rectangles, cairo_boxes_t *out) |
{ |
sweep_line_t sweep_line; |
rectangle_t *rectangle; |
cairo_status_t status; |
|
sweep_line_init (&sweep_line, rectangles, num_rectangles); |
if ((status = setjmp (sweep_line.unwind))) |
goto unwind; |
|
rectangle = rectangle_pop_start (&sweep_line); |
do { |
if (rectangle->top != sweep_line.current_y) { |
rectangle_t *stop; |
|
stop = rectangle_peek_stop (&sweep_line); |
while (stop != NULL && stop->bottom < rectangle->top) { |
if (stop->bottom != sweep_line.current_y) { |
active_edges (&sweep_line, out); |
sweep_line.current_y = stop->bottom; |
} |
|
sweep_line_delete (&sweep_line, stop, out); |
|
stop = rectangle_peek_stop (&sweep_line); |
} |
|
active_edges (&sweep_line, out); |
sweep_line.current_y = rectangle->top; |
} |
|
sweep_line_insert (&sweep_line, rectangle); |
} while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL); |
|
while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) { |
if (rectangle->bottom != sweep_line.current_y) { |
active_edges (&sweep_line, out); |
sweep_line.current_y = rectangle->bottom; |
} |
|
sweep_line_delete (&sweep_line, rectangle, out); |
} |
|
unwind: |
sweep_line_fini (&sweep_line); |
return status; |
} |
|
static cairo_status_t |
_cairo_boxes_intersect_with_box (const cairo_boxes_t *boxes, |
const cairo_box_t *box, |
cairo_boxes_t *out) |
{ |
cairo_status_t status; |
int i, j; |
|
if (out == boxes) { /* inplace update */ |
struct _cairo_boxes_chunk *chunk; |
|
out->num_boxes = 0; |
for (chunk = &out->chunks; chunk != NULL; chunk = chunk->next) { |
for (i = j = 0; i < chunk->count; i++) { |
cairo_box_t *b = &chunk->base[i]; |
|
b->p1.x = MAX (b->p1.x, box->p1.x); |
b->p1.y = MAX (b->p1.y, box->p1.y); |
b->p2.x = MIN (b->p2.x, box->p2.x); |
b->p2.y = MIN (b->p2.y, box->p2.y); |
if (b->p1.x < b->p2.x && b->p1.y < b->p2.y) { |
if (i != j) |
chunk->base[j] = *b; |
j++; |
} |
} |
/* XXX unlink empty chains? */ |
chunk->count = j; |
out->num_boxes += j; |
} |
} else { |
const struct _cairo_boxes_chunk *chunk; |
|
_cairo_boxes_clear (out); |
_cairo_boxes_limit (out, box, 1); |
for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) { |
for (i = 0; i < chunk->count; i++) { |
status = _cairo_boxes_add (out, |
CAIRO_ANTIALIAS_DEFAULT, |
&chunk->base[i]); |
if (unlikely (status)) |
return status; |
} |
} |
} |
|
return CAIRO_STATUS_SUCCESS; |
} |
|
cairo_status_t |
_cairo_boxes_intersect (const cairo_boxes_t *a, |
const cairo_boxes_t *b, |
cairo_boxes_t *out) |
{ |
rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)]; |
rectangle_t *rectangles; |
rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1]; |
rectangle_t **rectangles_ptrs; |
const struct _cairo_boxes_chunk *chunk; |
cairo_status_t status; |
int i, j, count; |
|
if (unlikely (a->num_boxes == 0 || b->num_boxes == 0)) { |
_cairo_boxes_clear (out); |
return CAIRO_STATUS_SUCCESS; |
} |
|
if (a->num_boxes == 1) { |
cairo_box_t box = a->chunks.base[0]; |
return _cairo_boxes_intersect_with_box (b, &box, out); |
} |
if (b->num_boxes == 1) { |
cairo_box_t box = b->chunks.base[0]; |
return _cairo_boxes_intersect_with_box (a, &box, out); |
} |
|
rectangles = stack_rectangles; |
rectangles_ptrs = stack_rectangles_ptrs; |
count = a->num_boxes + b->num_boxes; |
if (count > ARRAY_LENGTH (stack_rectangles)) { |
rectangles = _cairo_malloc_ab_plus_c (count, |
sizeof (rectangle_t) + |
sizeof (rectangle_t *), |
sizeof (rectangle_t *)); |
if (unlikely (rectangles == NULL)) |
return _cairo_error (CAIRO_STATUS_NO_MEMORY); |
|
rectangles_ptrs = (rectangle_t **) (rectangles + count); |
} |
|
j = 0; |
for (chunk = &a->chunks; chunk != NULL; chunk = chunk->next) { |
const cairo_box_t *box = chunk->base; |
for (i = 0; i < chunk->count; i++) { |
if (box[i].p1.x < box[i].p2.x) { |
rectangles[j].left.x = box[i].p1.x; |
rectangles[j].left.dir = 1; |
|
rectangles[j].right.x = box[i].p2.x; |
rectangles[j].right.dir = -1; |
} else { |
rectangles[j].right.x = box[i].p1.x; |
rectangles[j].right.dir = 1; |
|
rectangles[j].left.x = box[i].p2.x; |
rectangles[j].left.dir = -1; |
} |
|
rectangles[j].left.a_or_b = 0; |
rectangles[j].left.right = NULL; |
rectangles[j].right.a_or_b = 0; |
rectangles[j].right.right = NULL; |
|
rectangles[j].top = box[i].p1.y; |
rectangles[j].bottom = box[i].p2.y; |
|
rectangles_ptrs[j] = &rectangles[j]; |
j++; |
} |
} |
for (chunk = &b->chunks; chunk != NULL; chunk = chunk->next) { |
const cairo_box_t *box = chunk->base; |
for (i = 0; i < chunk->count; i++) { |
if (box[i].p1.x < box[i].p2.x) { |
rectangles[j].left.x = box[i].p1.x; |
rectangles[j].left.dir = 1; |
|
rectangles[j].right.x = box[i].p2.x; |
rectangles[j].right.dir = -1; |
} else { |
rectangles[j].right.x = box[i].p1.x; |
rectangles[j].right.dir = 1; |
|
rectangles[j].left.x = box[i].p2.x; |
rectangles[j].left.dir = -1; |
} |
|
rectangles[j].left.a_or_b = 1; |
rectangles[j].left.right = NULL; |
rectangles[j].right.a_or_b = 1; |
rectangles[j].right.right = NULL; |
|
rectangles[j].top = box[i].p1.y; |
rectangles[j].bottom = box[i].p2.y; |
|
rectangles_ptrs[j] = &rectangles[j]; |
j++; |
} |
} |
assert (j == count); |
|
_cairo_boxes_clear (out); |
status = intersect (rectangles_ptrs, j, out); |
if (rectangles != stack_rectangles) |
free (rectangles); |
|
return status; |
} |