Subversion Repositories Kolibri OS

/*

 * 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 

 *	Chris Wilson 

 */

/* 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 

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;

}