Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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 {
  51.     cairo_bo_edge_t *right;
  52.     int32_t top;
  53. };
  54.  
  55. struct _cairo_bo_edge {
  56.     cairo_edge_t edge;
  57.     cairo_bo_edge_t *prev;
  58.     cairo_bo_edge_t *next;
  59.     cairo_bo_trap_t deferred_trap;
  60. };
  61.  
  62. typedef enum {
  63.     CAIRO_BO_EVENT_TYPE_START,
  64.     CAIRO_BO_EVENT_TYPE_STOP
  65. } cairo_bo_event_type_t;
  66.  
  67. typedef struct _cairo_bo_event {
  68.     cairo_bo_event_type_t type;
  69.     cairo_point_t point;
  70.     cairo_bo_edge_t *edge;
  71. } cairo_bo_event_t;
  72.  
  73. typedef struct _cairo_bo_sweep_line {
  74.     cairo_bo_event_t **events;
  75.     cairo_bo_edge_t *head;
  76.     cairo_bo_edge_t *stopped;
  77.     int32_t current_y;
  78.     cairo_bo_edge_t *current_edge;
  79. } cairo_bo_sweep_line_t;
  80.  
  81. static inline int
  82. _cairo_point_compare (const cairo_point_t *a,
  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
  95. _cairo_bo_edge_compare (const cairo_bo_edge_t   *a,
  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
  108. cairo_bo_event_compare (const cairo_bo_event_t *a,
  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 *
  125. _cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
  126. {
  127.     return *sweep_line->events++;
  128. }
  129.  
  130. CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
  131.                         cairo_bo_event_t *,
  132.                         cairo_bo_event_compare)
  133.  
  134. static void
  135. _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
  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
  149. _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t      *sweep_line,
  150.                              cairo_bo_edge_t            *edge)
  151. {
  152.     if (sweep_line->current_edge != NULL) {
  153.         cairo_bo_edge_t *prev, *next;
  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
  197. _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
  198.                              cairo_bo_edge_t    *edge)
  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
  213. edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
  214. {
  215.     return a->edge.line.p1.x == b->edge.line.p1.x;
  216. }
  217.  
  218. static cairo_status_t
  219. _cairo_bo_edge_end_trap (cairo_bo_edge_t        *left,
  220.                          int32_t                 bot,
  221.                          cairo_bool_t            do_traps,
  222.                          void                   *container)
  223. {
  224.     cairo_bo_trap_t *trap = &left->deferred_trap;
  225.     cairo_status_t status = CAIRO_STATUS_SUCCESS;
  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 {
  235.             cairo_box_t box;
  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;
  241.             status = _cairo_boxes_add (container, CAIRO_ANTIALIAS_DEFAULT, &box);
  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
  256. _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t  *left,
  257.                                        cairo_bo_edge_t  *right,
  258.                                        int               top,
  259.                                        cairo_bool_t      do_traps,
  260.                                        void             *container)
  261. {
  262.     cairo_status_t status;
  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
  289. _active_edges_to_traps (cairo_bo_edge_t         *left,
  290.                         int32_t                  top,
  291.                         cairo_fill_rule_t        fill_rule,
  292.                         cairo_bool_t             do_traps,
  293.                         void                    *container)
  294. {
  295.     cairo_bo_edge_t *right;
  296.     cairo_status_t status;
  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.  
  342.             status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
  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) {
  364.                     cairo_bo_edge_t *next;
  365.                     cairo_bool_t skip = FALSE;
  366.  
  367.                     /* skip co-linear edges */
  368.                     next = right->next;
  369.                     if (next != NULL)
  370.                         skip = edges_collinear (right, next);
  371.  
  372.                     if (! skip)
  373.                         break;
  374.                 }
  375.  
  376.                 right = right->next;
  377.             }
  378.  
  379.             status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
  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
  394. _cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t   **start_events,
  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;
  402.     cairo_status_t status;
  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) {
  418.         case CAIRO_BO_EVENT_TYPE_START:
  419.             _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
  420.             break;
  421.  
  422.         case CAIRO_BO_EVENT_TYPE_STOP:
  423.             _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
  424.  
  425.             if (event->edge->deferred_trap.right != NULL) {
  426.                 status = _cairo_bo_edge_end_trap (event->edge,
  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.  
  440. cairo_status_t
  441. _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon,
  442.                                                                 cairo_fill_rule_t         fill_rule,
  443.                                                                 cairo_boxes_t *boxes)
  444. {
  445.     cairo_status_t status;
  446.     cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
  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))
  470.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  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.  
  497.     status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
  498.                                                             fill_rule,
  499.                                                             FALSE, boxes);
  500.     if (events != stack_events)
  501.         free (events);
  502.  
  503.     return status;
  504. }
  505.  
  506. cairo_status_t
  507. _cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
  508.                                                      cairo_fill_rule_t fill_rule)
  509. {
  510.     cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
  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;
  516.     cairo_status_t status;
  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))
  536.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  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);
  591.     status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
  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. }
  601.