w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

cairo-bentley-ottmann-rectilinear.c
Go to the documentation of this file.
1 /*
2  * Copyright © 2004 Carl Worth
3  * Copyright © 2006 Red Hat, Inc.
4  * Copyright © 2008 Chris Wilson
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it either under the terms of the GNU Lesser General Public
8  * License version 2.1 as published by the Free Software Foundation
9  * (the "LGPL") or, at your option, under the terms of the Mozilla
10  * Public License Version 1.1 (the "MPL"). If you do not alter this
11  * notice, a recipient may use your version of this file under either
12  * the MPL or the LGPL.
13  *
14  * You should have received a copy of the LGPL along with this library
15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17  * You should have received a copy of the MPL along with this library
18  * in the file COPYING-MPL-1.1
19  *
20  * The contents of this file are subject to the Mozilla Public License
21  * Version 1.1 (the "License"); you may not use this file except in
22  * compliance with the License. You may obtain a copy of the License at
23  * http://www.mozilla.org/MPL/
24  *
25  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27  * the specific language governing rights and limitations.
28  *
29  * The Original Code is the cairo graphics library.
30  *
31  * The Initial Developer of the Original Code is Carl Worth
32  *
33  * Contributor(s):
34  * Carl D. Worth <cworth@cworth.org>
35  * Chris Wilson <chris@chris-wilson.co.uk>
36  */
37 
38 /* Provide definitions for standalone compilation */
39 #include "cairoint.h"
40 
41 #include "cairo-boxes-private.h"
42 #include "cairo-combsort-inline.h"
43 #include "cairo-error-private.h"
44 #include "cairo-traps-private.h"
45 
46 typedef struct _cairo_bo_edge cairo_bo_edge_t;
47 typedef struct _cairo_bo_trap cairo_bo_trap_t;
48 
49 /* A deferred trapezoid of an edge */
50 struct _cairo_bo_trap {
52  int32_t top;
53 };
54 
55 struct _cairo_bo_edge {
60 };
61 
62 typedef enum {
66 
67 typedef struct _cairo_bo_event {
72 
73 typedef struct _cairo_bo_sweep_line {
80 
81 static inline int
83  const cairo_point_t *b)
84 {
85  int cmp;
86 
87  cmp = a->y - b->y;
88  if (likely (cmp))
89  return cmp;
90 
91  return a->x - b->x;
92 }
93 
94 static inline int
96  const cairo_bo_edge_t *b)
97 {
98  int cmp;
99 
100  cmp = a->edge.line.p1.x - b->edge.line.p1.x;
101  if (likely (cmp))
102  return cmp;
103 
104  return b->edge.bottom - a->edge.bottom;
105 }
106 
107 static inline int
109  const cairo_bo_event_t *b)
110 {
111  int cmp;
112 
113  cmp = _cairo_point_compare (&a->point, &b->point);
114  if (likely (cmp))
115  return cmp;
116 
117  cmp = a->type - b->type;
118  if (cmp)
119  return cmp;
120 
121  return a - b;
122 }
123 
124 static inline cairo_bo_event_t *
126 {
127  return *sweep_line->events++;
128 }
129 
133 
134 static void
136  cairo_bo_event_t **events,
137  int num_events)
138 {
139  _cairo_bo_event_queue_sort (events, num_events);
140  events[num_events] = NULL;
141  sweep_line->events = events;
142 
143  sweep_line->head = NULL;
144  sweep_line->current_y = INT32_MIN;
145  sweep_line->current_edge = NULL;
146 }
147 
148 static void
151 {
152  if (sweep_line->current_edge != NULL) {
154  int cmp;
155 
156  cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
157  if (cmp < 0) {
158  prev = sweep_line->current_edge;
159  next = prev->next;
160  while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
161  prev = next, next = prev->next;
162 
163  prev->next = edge;
164  edge->prev = prev;
165  edge->next = next;
166  if (next != NULL)
167  next->prev = edge;
168  } else if (cmp > 0) {
169  next = sweep_line->current_edge;
170  prev = next->prev;
171  while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
172  next = prev, prev = next->prev;
173 
174  next->prev = edge;
175  edge->next = next;
176  edge->prev = prev;
177  if (prev != NULL)
178  prev->next = edge;
179  else
180  sweep_line->head = edge;
181  } else {
182  prev = sweep_line->current_edge;
183  edge->prev = prev;
184  edge->next = prev->next;
185  if (prev->next != NULL)
186  prev->next->prev = edge;
187  prev->next = edge;
188  }
189  } else {
190  sweep_line->head = edge;
191  }
192 
193  sweep_line->current_edge = edge;
194 }
195 
196 static void
199 {
200  if (edge->prev != NULL)
201  edge->prev->next = edge->next;
202  else
203  sweep_line->head = edge->next;
204 
205  if (edge->next != NULL)
206  edge->next->prev = edge->prev;
207 
208  if (sweep_line->current_edge == edge)
209  sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
210 }
211 
212 static inline cairo_bool_t
214 {
215  return a->edge.line.p1.x == b->edge.line.p1.x;
216 }
217 
218 static cairo_status_t
220  int32_t bot,
221  cairo_bool_t do_traps,
222  void *container)
223 {
224  cairo_bo_trap_t *trap = &left->deferred_trap;
226 
227  /* Only emit (trivial) non-degenerate trapezoids with positive height. */
228  if (likely (trap->top < bot)) {
229  if (do_traps) {
230  _cairo_traps_add_trap (container,
231  trap->top, bot,
232  &left->edge.line, &trap->right->edge.line);
233  status = _cairo_traps_status ((cairo_traps_t *) container);
234  } else {
236 
237  box.p1.x = left->edge.line.p1.x;
238  box.p1.y = trap->top;
239  box.p2.x = trap->right->edge.line.p1.x;
240  box.p2.y = bot;
242  }
243  }
244 
245  trap->right = NULL;
246 
247  return status;
248 }
249 
250 /* Start a new trapezoid at the given top y coordinate, whose edges
251  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
252  * then either add it to the traps in `traps', if the trapezoid's
253  * right edge differs from `edge->next', or do nothing if the new
254  * trapezoid would be a continuation of the existing one. */
255 static inline cairo_status_t
258  int top,
259  cairo_bool_t do_traps,
260  void *container)
261 {
263 
264  if (left->deferred_trap.right == right)
265  return CAIRO_STATUS_SUCCESS;
266 
267  if (left->deferred_trap.right != NULL) {
268  if (right != NULL && edges_collinear (left->deferred_trap.right, right))
269  {
270  /* continuation on right, so just swap edges */
271  left->deferred_trap.right = right;
272  return CAIRO_STATUS_SUCCESS;
273  }
274 
275  status = _cairo_bo_edge_end_trap (left, top, do_traps, container);
276  if (unlikely (status))
277  return status;
278  }
279 
280  if (right != NULL && ! edges_collinear (left, right)) {
281  left->deferred_trap.top = top;
282  left->deferred_trap.right = right;
283  }
284 
285  return CAIRO_STATUS_SUCCESS;
286 }
287 
288 static inline cairo_status_t
290  int32_t top,
291  cairo_fill_rule_t fill_rule,
292  cairo_bool_t do_traps,
293  void *container)
294 {
297 
298  if (fill_rule == CAIRO_FILL_RULE_WINDING) {
299  while (left != NULL) {
300  int in_out;
301 
302  /* Greedily search for the closing edge, so that we generate the
303  * maximal span width with the minimal number of trapezoids.
304  */
305  in_out = left->edge.dir;
306 
307  /* Check if there is a co-linear edge with an existing trap */
308  right = left->next;
309  if (left->deferred_trap.right == NULL) {
310  while (right != NULL && right->deferred_trap.right == NULL)
311  right = right->next;
312 
313  if (right != NULL && edges_collinear (left, right)) {
314  /* continuation on left */
315  left->deferred_trap = right->deferred_trap;
316  right->deferred_trap.right = NULL;
317  }
318  }
319 
320  /* End all subsumed traps */
321  right = left->next;
322  while (right != NULL) {
323  if (right->deferred_trap.right != NULL) {
324  status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
325  if (unlikely (status))
326  return status;
327  }
328 
329  in_out += right->edge.dir;
330  if (in_out == 0) {
331  /* skip co-linear edges */
332  if (right->next == NULL ||
333  ! edges_collinear (right, right->next))
334  {
335  break;
336  }
337  }
338 
339  right = right->next;
340  }
341 
343  do_traps, container);
344  if (unlikely (status))
345  return status;
346 
347  left = right;
348  if (left != NULL)
349  left = left->next;
350  }
351  } else {
352  while (left != NULL) {
353  int in_out = 0;
354 
355  right = left->next;
356  while (right != NULL) {
357  if (right->deferred_trap.right != NULL) {
358  status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
359  if (unlikely (status))
360  return status;
361  }
362 
363  if ((in_out++ & 1) == 0) {
366 
367  /* skip co-linear edges */
368  next = right->next;
369  if (next != NULL)
371 
372  if (! skip)
373  break;
374  }
375 
376  right = right->next;
377  }
378 
380  do_traps, container);
381  if (unlikely (status))
382  return status;
383 
384  left = right;
385  if (left != NULL)
386  left = left->next;
387  }
388  }
389 
390  return CAIRO_STATUS_SUCCESS;
391 }
392 
393 static cairo_status_t
395  int num_events,
396  cairo_fill_rule_t fill_rule,
397  cairo_bool_t do_traps,
398  void *container)
399 {
400  cairo_bo_sweep_line_t sweep_line;
401  cairo_bo_event_t *event;
403 
404  _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
405 
406  while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
407  if (event->point.y != sweep_line.current_y) {
408  status = _active_edges_to_traps (sweep_line.head,
409  sweep_line.current_y,
410  fill_rule, do_traps, container);
411  if (unlikely (status))
412  return status;
413 
414  sweep_line.current_y = event->point.y;
415  }
416 
417  switch (event->type) {
419  _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
420  break;
421 
423  _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
424 
425  if (event->edge->deferred_trap.right != NULL) {
427  sweep_line.current_y,
428  do_traps, container);
429  if (unlikely (status))
430  return status;
431  }
432 
433  break;
434  }
435  }
436 
437  return CAIRO_STATUS_SUCCESS;
438 }
439 
442  cairo_fill_rule_t fill_rule,
443  cairo_boxes_t *boxes)
444 {
447  cairo_bo_event_t *events;
448  cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
449  cairo_bo_event_t **event_ptrs;
450  cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
451  cairo_bo_edge_t *edges;
452  int num_events;
453  int i, j;
454 
455  if (unlikely (polygon->num_edges == 0))
456  return CAIRO_STATUS_SUCCESS;
457 
458  num_events = 2 * polygon->num_edges;
459 
460  events = stack_events;
461  event_ptrs = stack_event_ptrs;
462  edges = stack_edges;
463  if (num_events > ARRAY_LENGTH (stack_events)) {
464  events = _cairo_malloc_ab_plus_c (num_events,
465  sizeof (cairo_bo_event_t) +
466  sizeof (cairo_bo_edge_t) +
467  sizeof (cairo_bo_event_t *),
468  sizeof (cairo_bo_event_t *));
469  if (unlikely (events == NULL))
471 
472  event_ptrs = (cairo_bo_event_t **) (events + num_events);
473  edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
474  }
475 
476  for (i = j = 0; i < polygon->num_edges; i++) {
477  edges[i].edge = polygon->edges[i];
478  edges[i].deferred_trap.right = NULL;
479  edges[i].prev = NULL;
480  edges[i].next = NULL;
481 
482  event_ptrs[j] = &events[j];
483  events[j].type = CAIRO_BO_EVENT_TYPE_START;
484  events[j].point.y = polygon->edges[i].top;
485  events[j].point.x = polygon->edges[i].line.p1.x;
486  events[j].edge = &edges[i];
487  j++;
488 
489  event_ptrs[j] = &events[j];
490  events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
491  events[j].point.y = polygon->edges[i].bottom;
492  events[j].point.x = polygon->edges[i].line.p1.x;
493  events[j].edge = &edges[i];
494  j++;
495  }
496 
498  fill_rule,
499  FALSE, boxes);
500  if (events != stack_events)
501  free (events);
502 
503  return status;
504 }
505 
508  cairo_fill_rule_t fill_rule)
509 {
511  cairo_bo_event_t *events;
512  cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
513  cairo_bo_event_t **event_ptrs;
514  cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
515  cairo_bo_edge_t *edges;
517  int i, j, k;
518 
519  if (unlikely (traps->num_traps == 0))
520  return CAIRO_STATUS_SUCCESS;
521 
522  assert (traps->is_rectilinear);
523 
524  i = 4 * traps->num_traps;
525 
526  events = stack_events;
527  event_ptrs = stack_event_ptrs;
528  edges = stack_edges;
529  if (i > ARRAY_LENGTH (stack_events)) {
530  events = _cairo_malloc_ab_plus_c (i,
531  sizeof (cairo_bo_event_t) +
532  sizeof (cairo_bo_edge_t) +
533  sizeof (cairo_bo_event_t *),
534  sizeof (cairo_bo_event_t *));
535  if (unlikely (events == NULL))
537 
538  event_ptrs = (cairo_bo_event_t **) (events + i);
539  edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
540  }
541 
542  for (i = j = k = 0; i < traps->num_traps; i++) {
543  edges[k].edge.top = traps->traps[i].top;
544  edges[k].edge.bottom = traps->traps[i].bottom;
545  edges[k].edge.line = traps->traps[i].left;
546  edges[k].edge.dir = 1;
547  edges[k].deferred_trap.right = NULL;
548  edges[k].prev = NULL;
549  edges[k].next = NULL;
550 
551  event_ptrs[j] = &events[j];
552  events[j].type = CAIRO_BO_EVENT_TYPE_START;
553  events[j].point.y = traps->traps[i].top;
554  events[j].point.x = traps->traps[i].left.p1.x;
555  events[j].edge = &edges[k];
556  j++;
557 
558  event_ptrs[j] = &events[j];
559  events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
560  events[j].point.y = traps->traps[i].bottom;
561  events[j].point.x = traps->traps[i].left.p1.x;
562  events[j].edge = &edges[k];
563  j++;
564  k++;
565 
566  edges[k].edge.top = traps->traps[i].top;
567  edges[k].edge.bottom = traps->traps[i].bottom;
568  edges[k].edge.line = traps->traps[i].right;
569  edges[k].edge.dir = -1;
570  edges[k].deferred_trap.right = NULL;
571  edges[k].prev = NULL;
572  edges[k].next = NULL;
573 
574  event_ptrs[j] = &events[j];
575  events[j].type = CAIRO_BO_EVENT_TYPE_START;
576  events[j].point.y = traps->traps[i].top;
577  events[j].point.x = traps->traps[i].right.p1.x;
578  events[j].edge = &edges[k];
579  j++;
580 
581  event_ptrs[j] = &events[j];
582  events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
583  events[j].point.y = traps->traps[i].bottom;
584  events[j].point.x = traps->traps[i].right.p1.x;
585  events[j].edge = &edges[k];
586  j++;
587  k++;
588  }
589 
590  _cairo_traps_clear (traps);
592  fill_rule,
593  TRUE, traps);
594  traps->is_rectilinear = TRUE;
595 
596  if (events != stack_events)
597  free (events);
598 
599  return status;
600 }
#define box(a)
Definition: aptex-macros.h:675
#define next(a)
Definition: aptex-macros.h:924
int cmp(const void *p, const void *q)
Definition: bkmk2uni.c:1611
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)
struct _cairo_bo_event cairo_bo_event_t
struct _cairo_bo_sweep_line cairo_bo_sweep_line_t
cairo_status_t _cairo_bentley_ottmann_tessellate_rectilinear_traps(cairo_traps_t *traps, cairo_fill_rule_t fill_rule)
cairo_status_t _cairo_boxes_add(cairo_boxes_t *boxes, cairo_antialias_t antialias, const cairo_box_t *box)
Definition: cairo-boxes.c:184
#define CAIRO_COMBSORT_DECLARE(NAME, TYPE, CMP)
#define CAIRO_STACK_ARRAY_LENGTH(T)
cairo_status_t _cairo_error(cairo_status_t status)
Definition: cairo-error.c:65
#define _cairo_malloc_ab_plus_c(a, size, c)
#define _cairo_traps_status(T)
void _cairo_traps_add_trap(cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom, const cairo_line_t *left, const cairo_line_t *right)
Definition: cairo-traps.c:151
void _cairo_traps_clear(cairo_traps_t *traps)
Definition: cairo-traps.c:98
enum _cairo_fill_rule cairo_fill_rule_t
int cairo_bool_t
Definition: cairo.h:107
@ CAIRO_STATUS_SUCCESS
Definition: cairo.h:315
@ CAIRO_STATUS_NO_MEMORY
Definition: cairo.h:317
@ CAIRO_ANTIALIAS_DEFAULT
Definition: cairo.h:710
enum _cairo_status cairo_status_t
@ CAIRO_FILL_RULE_WINDING
Definition: cairo.h:754
#define ARRAY_LENGTH(__array)
Definition: cairoint.h:137
static cairo_bo_event_t * _cairo_bo_event_dequeue(cairo_bo_sweep_line_t *sweep_line)
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)
static int _cairo_point_compare(const cairo_point_t *a, const cairo_point_t *b)
static int cairo_bo_event_compare(const cairo_bo_event_t *a, const cairo_bo_event_t *b)
static 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)
static void _cairo_bo_sweep_line_init(cairo_bo_sweep_line_t *sweep_line, cairo_bo_event_t **events, int num_events)
static 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)
static void _cairo_bo_sweep_line_delete(cairo_bo_sweep_line_t *sweep_line, cairo_bo_edge_t *edge)
static void _cairo_bo_sweep_line_insert(cairo_bo_sweep_line_t *sweep_line, cairo_bo_edge_t *edge)
static void _cairo_bo_event_queue_sort(cairo_bo_event_t **base, unsigned int nmemb)
static int _cairo_bo_edge_compare(const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
static cairo_status_t _cairo_bo_edge_end_trap(cairo_bo_edge_t *left, int32_t bot, cairo_bool_t do_traps, void *container)
static cairo_bool_t edges_collinear(const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
#define b
Definition: jpegint.h:372
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
#define free(a)
Definition: decNumber.cpp:310
#define skip(p, c)
Definition: ptexmac.h:70
static FIELD_PTR prev
Definition: genind.c:36
#define a(n)
Definition: gpos-common.c:148
assert(pcxLoadImage24((char *)((void *) 0), fp, pinfo, hdr))
#define likely(x)
Definition: jbig2arith.cc:115
#define unlikely(x)
Definition: jbig2arith.cc:116
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
@ right
Definition: annotate.c:15
int int double double double char double char * top
Definition: gdfx.h:19
#define INT32_MIN
Definition: stdint.h:136
signed int int32_t
Definition: stdint.h:77
int k
Definition: otp-parser.c:70
#define status
static void(* trap)(void)
Definition: memory.c:38
cairo_line_t line
cairo_point_t p1
cairo_trapezoid_t * traps
unsigned int is_rectilinear
Definition: jquant2.c:258
struct quorem x
struct edge * prev
struct edge * next
struct edge * edges
int j
Definition: t4ht.c:1589