Subversion Repositories Scribus

Rev

Rev 14952 | Blame | Compare with Previous | Last modification | View Log | RSS feed

/*
 * Copyright © 2004 Carl Worth
 * Copyright © 2006 Red Hat, Inc.
 * Copyright © 2008 Chris Wilson
 *
 * 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, Fifth Floor, Boston, MA 02110-1301 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-combsort-private.h"

typedef struct _cairo_bo_edge cairo_bo_edge_t;
typedef struct _cairo_bo_trap cairo_bo_trap_t;

/* A deferred trapezoid of an edge */
struct _cairo_bo_trap {
    cairo_bo_edge_t *right;
    int32_t top;
};

struct _cairo_bo_edge {
    cairo_edge_t edge;
    cairo_bo_edge_t *prev;
    cairo_bo_edge_t *next;
    cairo_bo_trap_t deferred_trap;
};

typedef enum {
    CAIRO_BO_EVENT_TYPE_START,
    CAIRO_BO_EVENT_TYPE_STOP
} cairo_bo_event_type_t;

typedef struct _cairo_bo_event {
    cairo_bo_event_type_t type;
    cairo_point_t point;
    cairo_bo_edge_t *edge;
} cairo_bo_event_t;

typedef struct _cairo_bo_sweep_line {
    cairo_bo_event_t **events;
    cairo_bo_edge_t *head;
    cairo_bo_edge_t *stopped;
    int32_t current_y;
    cairo_bo_edge_t *current_edge;
} cairo_bo_sweep_line_t;

static inline int
_cairo_point_compare (const cairo_point_t *a,
                      const cairo_point_t *b)
{
    int cmp;

    cmp = a->y - b->y;
    if (likely (cmp))
        return cmp;

    return a->x - b->x;
}

static inline int
_cairo_bo_edge_compare (const cairo_bo_edge_t   *a,
                        const cairo_bo_edge_t   *b)
{
    int cmp;

    cmp = a->edge.line.p1.x - b->edge.line.p1.x;
    if (likely (cmp))
        return cmp;

    return b->edge.bottom - a->edge.bottom;
}

static inline int
cairo_bo_event_compare (const cairo_bo_event_t *a,
                        const cairo_bo_event_t *b)
{
    int cmp;

    cmp = _cairo_point_compare (&a->point, &b->point);
    if (likely (cmp))
        return cmp;

    cmp = a->type - b->type;
    if (cmp)
        return cmp;

    return a - b;
}

static inline cairo_bo_event_t *
_cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
{
    return *sweep_line->events++;
}

CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
                        cairo_bo_event_t *,
                        cairo_bo_event_compare)

static void
_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
                           cairo_bo_event_t     **events,
                           int                    num_events)
{
    _cairo_bo_event_queue_sort (events, num_events);
    events[num_events] = NULL;
    sweep_line->events = events;

    sweep_line->head = NULL;
    sweep_line->current_y = INT32_MIN;
    sweep_line->current_edge = NULL;
}

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) {
        cairo_bo_edge_t *prev, *next;
        int cmp;

        cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
        if (cmp < 0) {
            prev = sweep_line->current_edge;
            next = prev->next;
            while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
                prev = next, next = prev->next;

            prev->next = edge;
            edge->prev = prev;
            edge->next = next;
            if (next != NULL)
                next->prev = edge;
        } else if (cmp > 0) {
            next = sweep_line->current_edge;
            prev = next->prev;
            while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
                next = prev, prev = next->prev;

            next->prev = edge;
            edge->next = next;
            edge->prev = prev;
            if (prev != NULL)
                prev->next = edge;
            else
                sweep_line->head = edge;
        } else {
            prev = sweep_line->current_edge;
            edge->prev = prev;
            edge->next = prev->next;
            if (prev->next != NULL)
                prev->next->prev = edge;
            prev->next = edge;
        }
    } else {
        sweep_line->head = edge;
    }

    sweep_line->current_edge = edge;
}

static void
_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
                             cairo_bo_edge_t    *edge)
{
    if (edge->prev != NULL)
        edge->prev->next = edge->next;
    else
        sweep_line->head = edge->next;

    if (edge->next != NULL)
        edge->next->prev = edge->prev;

    if (sweep_line->current_edge == edge)
        sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
}

static inline cairo_bool_t
edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
{
    return a->edge.line.p1.x == b->edge.line.p1.x;
}

static cairo_status_t
_cairo_bo_edge_end_trap (cairo_bo_edge_t        *left,
                         int32_t                 bot,
                         cairo_traps_t          *traps)
{
    cairo_bo_trap_t *trap = &left->deferred_trap;

    /* Only emit (trivial) non-degenerate trapezoids with positive height. */
    if (likely (trap->top < bot)) {
        _cairo_traps_add_trap (traps,
                               trap->top, bot,
                               &left->edge.line, &trap->right->edge.line);
    }

    trap->right = NULL;

    return _cairo_traps_status (traps);
}

/* 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
_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t  *left,
                                       cairo_bo_edge_t  *right,
                                       int               top,
                                       cairo_traps_t    *traps)
{
    cairo_status_t status;

    if (left->deferred_trap.right == right)
        return CAIRO_STATUS_SUCCESS;

    if (left->deferred_trap.right != NULL) {
        if (right != NULL && edges_collinear (left->deferred_trap.right, right))
        {
            /* continuation on right, so just swap edges */
            left->deferred_trap.right = right;
            return CAIRO_STATUS_SUCCESS;
        }

        status = _cairo_bo_edge_end_trap (left, top, traps);
        if (unlikely (status))
            return status;
    }

    if (right != NULL && ! edges_collinear (left, right)) {
        left->deferred_trap.top = top;
        left->deferred_trap.right = right;
    }

    return CAIRO_STATUS_SUCCESS;
}

static inline cairo_status_t
_active_edges_to_traps (cairo_bo_edge_t         *left,
                        int32_t                  top,
                        cairo_fill_rule_t        fill_rule,
                        cairo_traps_t           *traps)
{
    cairo_bo_edge_t *right;
    cairo_status_t status;

    if (fill_rule == CAIRO_FILL_RULE_WINDING) {
        while (left != NULL) {
            int in_out;

            /* Greedily search for the closing edge, so that we generate the
             * maximal span width with the minimal number of trapezoids.
             */

            in_out = left->edge.dir;

            /* 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_collinear (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) {
                    /* skip co-linear edges */
                    if (right->next == NULL ||
                        ! edges_collinear (right, right->next))
                    {
                        break;
                    }
                }

                right = right->next;
            }

            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;
            while (right != NULL) {
                if (right->deferred_trap.right != NULL) {
                    status = _cairo_bo_edge_end_trap (right, top, traps);
                    if (unlikely (status))
                        return status;
                }

                if ((in_out++ & 1) == 0) {
                    cairo_bo_edge_t *next;
                    cairo_bool_t skip = FALSE;

                    /* skip co-linear edges */
                    next = right->next;
                    if (next != NULL)
                        skip = edges_collinear (right, next);

                    if (! skip)
                        break;
                }

                right = right->next;
            }

            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;
        }
    }

    return CAIRO_STATUS_SUCCESS;
}

static cairo_status_t
_cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t   **start_events,
                                               int                       num_events,
                                               cairo_fill_rule_t         fill_rule,
                                               cairo_traps_t    *traps)
{
    cairo_bo_sweep_line_t sweep_line;
    cairo_bo_event_t *event;
    cairo_status_t status;

    _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);

    while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
        if (event->point.y != sweep_line.current_y) {
            status = _active_edges_to_traps (sweep_line.head,
                                             sweep_line.current_y,
                                             fill_rule, traps);
            if (unlikely (status))
                return status;

            sweep_line.current_y = event->point.y;
        }

        switch (event->type) {
        case CAIRO_BO_EVENT_TYPE_START:
            _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
            break;

        case CAIRO_BO_EVENT_TYPE_STOP:
            _cairo_bo_sweep_line_delete (&sweep_line, event->edge);

            if (event->edge->deferred_trap.right != NULL) {
                status = _cairo_bo_edge_end_trap (event->edge,
                                                  sweep_line.current_y,
                                                  traps);
                if (unlikely (status))
                    return status;
            }

            break;
        }
    }

    return CAIRO_STATUS_SUCCESS;
}

cairo_status_t
_cairo_bentley_ottmann_tessellate_rectilinear_polygon (cairo_traps_t     *traps,
                                                       const cairo_polygon_t *polygon,
                                                       cairo_fill_rule_t          fill_rule)
{
    cairo_status_t status;
    cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
    cairo_bo_event_t *events;
    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
    cairo_bo_event_t **event_ptrs;
    cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
    cairo_bo_edge_t *edges;
    int num_events;
    int i, j;

    if (unlikely (polygon->num_edges == 0))
        return CAIRO_STATUS_SUCCESS;

    num_events = 2 * polygon->num_edges;

    events = stack_events;
    event_ptrs = stack_event_ptrs;
    edges = stack_edges;
    if (num_events > ARRAY_LENGTH (stack_events)) {
        events = _cairo_malloc_ab_plus_c (num_events,
                                          sizeof (cairo_bo_event_t) +
                                          sizeof (cairo_bo_edge_t) +
                                          sizeof (cairo_bo_event_t *),
                                          sizeof (cairo_bo_event_t *));
        if (unlikely (events == NULL))
            return _cairo_error (CAIRO_STATUS_NO_MEMORY);

        event_ptrs = (cairo_bo_event_t **) (events + num_events);
        edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
    }

    for (i = j = 0; i < polygon->num_edges; i++) {
        edges[i].edge = polygon->edges[i];
        edges[i].deferred_trap.right = NULL;
        edges[i].prev = NULL;
        edges[i].next = NULL;

        event_ptrs[j] = &events[j];
        events[j].type = CAIRO_BO_EVENT_TYPE_START;
        events[j].point.y = polygon->edges[i].top;
        events[j].point.x = polygon->edges[i].line.p1.x;
        events[j].edge = &edges[i];
        j++;

        event_ptrs[j] = &events[j];
        events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
        events[j].point.y = polygon->edges[i].bottom;
        events[j].point.x = polygon->edges[i].line.p1.x;
        events[j].edge = &edges[i];
        j++;
    }

    status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
                                                            fill_rule, traps);
    if (events != stack_events)
        free (events);

    traps->is_rectilinear = TRUE;

    return status;
}

cairo_status_t
_cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
                                                     cairo_fill_rule_t fill_rule)
{
    cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
    cairo_bo_event_t *events;
    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
    cairo_bo_event_t **event_ptrs;
    cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
    cairo_bo_edge_t *edges;
    cairo_status_t status;
    int i, j, k;

    if (unlikely (traps->num_traps == 0))
        return CAIRO_STATUS_SUCCESS;

    assert (traps->is_rectilinear);

    i = 4 * traps->num_traps;

    events = stack_events;
    event_ptrs = stack_event_ptrs;
    edges = stack_edges;
    if (i > ARRAY_LENGTH (stack_events)) {
        events = _cairo_malloc_ab_plus_c (i,
                                          sizeof (cairo_bo_event_t) +
                                          sizeof (cairo_bo_edge_t) +
                                          sizeof (cairo_bo_event_t *),
                                          sizeof (cairo_bo_event_t *));
        if (unlikely (events == NULL))
            return _cairo_error (CAIRO_STATUS_NO_MEMORY);

        event_ptrs = (cairo_bo_event_t **) (events + i);
        edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
    }

    for (i = j = k = 0; i < traps->num_traps; i++) {
        edges[k].edge.top = traps->traps[i].top;
        edges[k].edge.bottom = traps->traps[i].bottom;
        edges[k].edge.line = traps->traps[i].left;
        edges[k].edge.dir = 1;
        edges[k].deferred_trap.right = NULL;
        edges[k].prev = NULL;
        edges[k].next = NULL;

        event_ptrs[j] = &events[j];
        events[j].type = CAIRO_BO_EVENT_TYPE_START;
        events[j].point.y = traps->traps[i].top;
        events[j].point.x = traps->traps[i].left.p1.x;
        events[j].edge = &edges[k];
        j++;

        event_ptrs[j] = &events[j];
        events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
        events[j].point.y = traps->traps[i].bottom;
        events[j].point.x = traps->traps[i].left.p1.x;
        events[j].edge = &edges[k];
        j++;
        k++;

        edges[k].edge.top = traps->traps[i].top;
        edges[k].edge.bottom = traps->traps[i].bottom;
        edges[k].edge.line = traps->traps[i].right;
        edges[k].edge.dir = -1;
        edges[k].deferred_trap.right = NULL;
        edges[k].prev = NULL;
        edges[k].next = NULL;

        event_ptrs[j] = &events[j];
        events[j].type = CAIRO_BO_EVENT_TYPE_START;
        events[j].point.y = traps->traps[i].top;
        events[j].point.x = traps->traps[i].right.p1.x;
        events[j].edge = &edges[k];
        j++;

        event_ptrs[j] = &events[j];
        events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
        events[j].point.y = traps->traps[i].bottom;
        events[j].point.x = traps->traps[i].right.p1.x;
        events[j].edge = &edges[k];
        j++;
        k++;
    }

    _cairo_traps_clear (traps);
    status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
                                                            fill_rule,
                                                            traps);
    traps->is_rectilinear = TRUE;

    if (events != stack_events)
        free (events);

    return status;
}