Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
cairo/src/cairo-bentley-ottmann-rectilinear.c
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
667 lines (562 sloc)
17.6 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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, 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-combsort-private.h" | |
#include "cairo-error-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_bool_t do_traps, | |
void *container) | |
{ | |
cairo_bo_trap_t *trap = &left->deferred_trap; | |
cairo_status_t status = CAIRO_STATUS_SUCCESS; | |
/* Only emit (trivial) non-degenerate trapezoids with positive height. */ | |
if (likely (trap->top < bot)) { | |
if (do_traps) { | |
_cairo_traps_add_trap (container, | |
trap->top, bot, | |
&left->edge.line, &trap->right->edge.line); | |
status = _cairo_traps_status ((cairo_traps_t *) container); | |
} else { | |
cairo_box_t box; | |
box.p1.x = left->edge.line.p1.x; | |
box.p1.y = trap->top; | |
box.p2.x = trap->right->edge.line.p1.x; | |
box.p2.y = bot; | |
status = _cairo_boxes_add (container, &box); | |
} | |
} | |
trap->right = NULL; | |
return status; | |
} | |
/* 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_bool_t do_traps, | |
void *container) | |
{ | |
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, do_traps, container); | |
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_bool_t do_traps, | |
void *container) | |
{ | |
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, do_traps, container); | |
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, | |
do_traps, container); | |
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, do_traps, container); | |
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, | |
do_traps, container); | |
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_bool_t do_traps, | |
void *container) | |
{ | |
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, do_traps, container); | |
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, | |
do_traps, container); | |
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, | |
TRUE, traps); | |
if (events != stack_events) | |
free (events); | |
traps->is_rectilinear = TRUE; | |
return status; | |
} | |
cairo_status_t | |
_cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon, | |
cairo_fill_rule_t fill_rule, | |
cairo_boxes_t *boxes) | |
{ | |
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, | |
FALSE, boxes); | |
if (events != stack_events) | |
free (events); | |
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, | |
TRUE, traps); | |
traps->is_rectilinear = TRUE; | |
if (events != stack_events) | |
free (events); | |
return status; | |
} |