Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | 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-private.h"
  43. #include "cairo-error-private.h"
  44.  
  45. typedef struct _cairo_bo_edge cairo_bo_edge_t;
  46. typedef struct _cairo_bo_trap cairo_bo_trap_t;
  47.  
  48. /* A deferred trapezoid of an edge */
  49. struct _cairo_bo_trap {
  50.     cairo_bo_edge_t *right;
  51.     int32_t top;
  52. };
  53.  
  54. struct _cairo_bo_edge {
  55.     cairo_edge_t edge;
  56.     cairo_bo_edge_t *prev;
  57.     cairo_bo_edge_t *next;
  58.     cairo_bo_trap_t deferred_trap;
  59. };
  60.  
  61. typedef enum {
  62.     CAIRO_BO_EVENT_TYPE_START,
  63.     CAIRO_BO_EVENT_TYPE_STOP
  64. } cairo_bo_event_type_t;
  65.  
  66. typedef struct _cairo_bo_event {
  67.     cairo_bo_event_type_t type;
  68.     cairo_point_t point;
  69.     cairo_bo_edge_t *edge;
  70. } cairo_bo_event_t;
  71.  
  72. typedef struct _cairo_bo_sweep_line {
  73.     cairo_bo_event_t **events;
  74.     cairo_bo_edge_t *head;
  75.     cairo_bo_edge_t *stopped;
  76.     int32_t current_y;
  77.     cairo_bo_edge_t *current_edge;
  78. } cairo_bo_sweep_line_t;
  79.  
  80. static inline int
  81. _cairo_point_compare (const cairo_point_t *a,
  82.                       const cairo_point_t *b)
  83. {
  84.     int cmp;
  85.  
  86.     cmp = a->y - b->y;
  87.     if (likely (cmp))
  88.         return cmp;
  89.  
  90.     return a->x - b->x;
  91. }
  92.  
  93. static inline int
  94. _cairo_bo_edge_compare (const cairo_bo_edge_t   *a,
  95.                         const cairo_bo_edge_t   *b)
  96. {
  97.     int cmp;
  98.  
  99.     cmp = a->edge.line.p1.x - b->edge.line.p1.x;
  100.     if (likely (cmp))
  101.         return cmp;
  102.  
  103.     return b->edge.bottom - a->edge.bottom;
  104. }
  105.  
  106. static inline int
  107. cairo_bo_event_compare (const cairo_bo_event_t *a,
  108.                         const cairo_bo_event_t *b)
  109. {
  110.     int cmp;
  111.  
  112.     cmp = _cairo_point_compare (&a->point, &b->point);
  113.     if (likely (cmp))
  114.         return cmp;
  115.  
  116.     cmp = a->type - b->type;
  117.     if (cmp)
  118.         return cmp;
  119.  
  120.     return a - b;
  121. }
  122.  
  123. static inline cairo_bo_event_t *
  124. _cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
  125. {
  126.     return *sweep_line->events++;
  127. }
  128.  
  129. CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
  130.                         cairo_bo_event_t *,
  131.                         cairo_bo_event_compare)
  132.  
  133. static void
  134. _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
  135.                            cairo_bo_event_t     **events,
  136.                            int                    num_events)
  137. {
  138.     _cairo_bo_event_queue_sort (events, num_events);
  139.     events[num_events] = NULL;
  140.     sweep_line->events = events;
  141.  
  142.     sweep_line->head = NULL;
  143.     sweep_line->current_y = INT32_MIN;
  144.     sweep_line->current_edge = NULL;
  145. }
  146.  
  147. static void
  148. _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t      *sweep_line,
  149.                              cairo_bo_edge_t            *edge)
  150. {
  151.     if (sweep_line->current_edge != NULL) {
  152.         cairo_bo_edge_t *prev, *next;
  153.         int cmp;
  154.  
  155.         cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
  156.         if (cmp < 0) {
  157.             prev = sweep_line->current_edge;
  158.             next = prev->next;
  159.             while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
  160.                 prev = next, next = prev->next;
  161.  
  162.             prev->next = edge;
  163.             edge->prev = prev;
  164.             edge->next = next;
  165.             if (next != NULL)
  166.                 next->prev = edge;
  167.         } else if (cmp > 0) {
  168.             next = sweep_line->current_edge;
  169.             prev = next->prev;
  170.             while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
  171.                 next = prev, prev = next->prev;
  172.  
  173.             next->prev = edge;
  174.             edge->next = next;
  175.             edge->prev = prev;
  176.             if (prev != NULL)
  177.                 prev->next = edge;
  178.             else
  179.                 sweep_line->head = edge;
  180.         } else {
  181.             prev = sweep_line->current_edge;
  182.             edge->prev = prev;
  183.             edge->next = prev->next;
  184.             if (prev->next != NULL)
  185.                 prev->next->prev = edge;
  186.             prev->next = edge;
  187.         }
  188.     } else {
  189.         sweep_line->head = edge;
  190.     }
  191.  
  192.     sweep_line->current_edge = edge;
  193. }
  194.  
  195. static void
  196. _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
  197.                              cairo_bo_edge_t    *edge)
  198. {
  199.     if (edge->prev != NULL)
  200.         edge->prev->next = edge->next;
  201.     else
  202.         sweep_line->head = edge->next;
  203.  
  204.     if (edge->next != NULL)
  205.         edge->next->prev = edge->prev;
  206.  
  207.     if (sweep_line->current_edge == edge)
  208.         sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
  209. }
  210.  
  211. static inline cairo_bool_t
  212. edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
  213. {
  214.     return a->edge.line.p1.x == b->edge.line.p1.x;
  215. }
  216.  
  217. static cairo_status_t
  218. _cairo_bo_edge_end_trap (cairo_bo_edge_t        *left,
  219.                          int32_t                 bot,
  220.                          cairo_bool_t            do_traps,
  221.                          void                   *container)
  222. {
  223.     cairo_bo_trap_t *trap = &left->deferred_trap;
  224.     cairo_status_t status = CAIRO_STATUS_SUCCESS;
  225.  
  226.     /* Only emit (trivial) non-degenerate trapezoids with positive height. */
  227.     if (likely (trap->top < bot)) {
  228.         if (do_traps) {
  229.             _cairo_traps_add_trap (container,
  230.                                    trap->top, bot,
  231.                                    &left->edge.line, &trap->right->edge.line);
  232.             status =  _cairo_traps_status ((cairo_traps_t *) container);
  233.         } else {
  234.             cairo_box_t box;
  235.  
  236.             box.p1.x = left->edge.line.p1.x;
  237.             box.p1.y = trap->top;
  238.             box.p2.x = trap->right->edge.line.p1.x;
  239.             box.p2.y = bot;
  240.             status = _cairo_boxes_add (container, &box);
  241.         }
  242.     }
  243.  
  244.     trap->right = NULL;
  245.  
  246.     return status;
  247. }
  248.  
  249. /* Start a new trapezoid at the given top y coordinate, whose edges
  250.  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
  251.  * then either add it to the traps in `traps', if the trapezoid's
  252.  * right edge differs from `edge->next', or do nothing if the new
  253.  * trapezoid would be a continuation of the existing one. */
  254. static inline cairo_status_t
  255. _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t  *left,
  256.                                        cairo_bo_edge_t  *right,
  257.                                        int               top,
  258.                                        cairo_bool_t      do_traps,
  259.                                        void             *container)
  260. {
  261.     cairo_status_t status;
  262.  
  263.     if (left->deferred_trap.right == right)
  264.         return CAIRO_STATUS_SUCCESS;
  265.  
  266.     if (left->deferred_trap.right != NULL) {
  267.         if (right != NULL && edges_collinear (left->deferred_trap.right, right))
  268.         {
  269.             /* continuation on right, so just swap edges */
  270.             left->deferred_trap.right = right;
  271.             return CAIRO_STATUS_SUCCESS;
  272.         }
  273.  
  274.         status = _cairo_bo_edge_end_trap (left, top, do_traps, container);
  275.         if (unlikely (status))
  276.             return status;
  277.     }
  278.  
  279.     if (right != NULL && ! edges_collinear (left, right)) {
  280.         left->deferred_trap.top = top;
  281.         left->deferred_trap.right = right;
  282.     }
  283.  
  284.     return CAIRO_STATUS_SUCCESS;
  285. }
  286.  
  287. static inline cairo_status_t
  288. _active_edges_to_traps (cairo_bo_edge_t         *left,
  289.                         int32_t                  top,
  290.                         cairo_fill_rule_t        fill_rule,
  291.                         cairo_bool_t             do_traps,
  292.                         void                    *container)
  293. {
  294.     cairo_bo_edge_t *right;
  295.     cairo_status_t status;
  296.  
  297.     if (fill_rule == CAIRO_FILL_RULE_WINDING) {
  298.         while (left != NULL) {
  299.             int in_out;
  300.  
  301.             /* Greedily search for the closing edge, so that we generate the
  302.              * maximal span width with the minimal number of trapezoids.
  303.              */
  304.             in_out = left->edge.dir;
  305.  
  306.             /* Check if there is a co-linear edge with an existing trap */
  307.             right = left->next;
  308.             if (left->deferred_trap.right == NULL) {
  309.                 while (right != NULL && right->deferred_trap.right == NULL)
  310.                     right = right->next;
  311.  
  312.                 if (right != NULL && edges_collinear (left, right)) {
  313.                     /* continuation on left */
  314.                     left->deferred_trap = right->deferred_trap;
  315.                     right->deferred_trap.right = NULL;
  316.                 }
  317.             }
  318.  
  319.             /* End all subsumed traps */
  320.             right = left->next;
  321.             while (right != NULL) {
  322.                 if (right->deferred_trap.right != NULL) {
  323.                     status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
  324.                     if (unlikely (status))
  325.                         return status;
  326.                 }
  327.  
  328.                 in_out += right->edge.dir;
  329.                 if (in_out == 0) {
  330.                     /* skip co-linear edges */
  331.                     if (right->next == NULL ||
  332.                         ! edges_collinear (right, right->next))
  333.                     {
  334.                         break;
  335.                     }
  336.                 }
  337.  
  338.                 right = right->next;
  339.             }
  340.  
  341.             status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
  342.                                                             do_traps, container);
  343.             if (unlikely (status))
  344.                 return status;
  345.  
  346.             left = right;
  347.             if (left != NULL)
  348.                 left = left->next;
  349.         }
  350.     } else {
  351.         while (left != NULL) {
  352.             int in_out = 0;
  353.  
  354.             right = left->next;
  355.             while (right != NULL) {
  356.                 if (right->deferred_trap.right != NULL) {
  357.                     status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
  358.                     if (unlikely (status))
  359.                         return status;
  360.                 }
  361.  
  362.                 if ((in_out++ & 1) == 0) {
  363.                     cairo_bo_edge_t *next;
  364.                     cairo_bool_t skip = FALSE;
  365.  
  366.                     /* skip co-linear edges */
  367.                     next = right->next;
  368.                     if (next != NULL)
  369.                         skip = edges_collinear (right, next);
  370.  
  371.                     if (! skip)
  372.                         break;
  373.                 }
  374.  
  375.                 right = right->next;
  376.             }
  377.  
  378.             status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
  379.                                                             do_traps, container);
  380.             if (unlikely (status))
  381.                 return status;
  382.  
  383.             left = right;
  384.             if (left != NULL)
  385.                 left = left->next;
  386.         }
  387.     }
  388.  
  389.     return CAIRO_STATUS_SUCCESS;
  390. }
  391.  
  392. static cairo_status_t
  393. _cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t   **start_events,
  394.                                                int                       num_events,
  395.                                                cairo_fill_rule_t         fill_rule,
  396.                                                cairo_bool_t              do_traps,
  397.                                                void                     *container)
  398. {
  399.     cairo_bo_sweep_line_t sweep_line;
  400.     cairo_bo_event_t *event;
  401.     cairo_status_t status;
  402.  
  403.     _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
  404.  
  405.     while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
  406.         if (event->point.y != sweep_line.current_y) {
  407.             status = _active_edges_to_traps (sweep_line.head,
  408.                                              sweep_line.current_y,
  409.                                              fill_rule, do_traps, container);
  410.             if (unlikely (status))
  411.                 return status;
  412.  
  413.             sweep_line.current_y = event->point.y;
  414.         }
  415.  
  416.         switch (event->type) {
  417.         case CAIRO_BO_EVENT_TYPE_START:
  418.             _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
  419.             break;
  420.  
  421.         case CAIRO_BO_EVENT_TYPE_STOP:
  422.             _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
  423.  
  424.             if (event->edge->deferred_trap.right != NULL) {
  425.                 status = _cairo_bo_edge_end_trap (event->edge,
  426.                                                   sweep_line.current_y,
  427.                                                   do_traps, container);
  428.                 if (unlikely (status))
  429.                     return status;
  430.             }
  431.  
  432.             break;
  433.         }
  434.     }
  435.  
  436.     return CAIRO_STATUS_SUCCESS;
  437. }
  438.  
  439. cairo_status_t
  440. _cairo_bentley_ottmann_tessellate_rectilinear_polygon (cairo_traps_t     *traps,
  441.                                                        const cairo_polygon_t *polygon,
  442.                                                        cairo_fill_rule_t          fill_rule)
  443. {
  444.     cairo_status_t status;
  445.     cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
  446.     cairo_bo_event_t *events;
  447.     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
  448.     cairo_bo_event_t **event_ptrs;
  449.     cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
  450.     cairo_bo_edge_t *edges;
  451.     int num_events;
  452.     int i, j;
  453.  
  454.     if (unlikely (polygon->num_edges == 0))
  455.         return CAIRO_STATUS_SUCCESS;
  456.  
  457.     num_events = 2 * polygon->num_edges;
  458.  
  459.     events = stack_events;
  460.     event_ptrs = stack_event_ptrs;
  461.     edges = stack_edges;
  462.     if (num_events > ARRAY_LENGTH (stack_events)) {
  463.         events = _cairo_malloc_ab_plus_c (num_events,
  464.                                           sizeof (cairo_bo_event_t) +
  465.                                           sizeof (cairo_bo_edge_t) +
  466.                                           sizeof (cairo_bo_event_t *),
  467.                                           sizeof (cairo_bo_event_t *));
  468.         if (unlikely (events == NULL))
  469.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  470.  
  471.         event_ptrs = (cairo_bo_event_t **) (events + num_events);
  472.         edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
  473.     }
  474.  
  475.     for (i = j = 0; i < polygon->num_edges; i++) {
  476.         edges[i].edge = polygon->edges[i];
  477.         edges[i].deferred_trap.right = NULL;
  478.         edges[i].prev = NULL;
  479.         edges[i].next = NULL;
  480.  
  481.         event_ptrs[j] = &events[j];
  482.         events[j].type = CAIRO_BO_EVENT_TYPE_START;
  483.         events[j].point.y = polygon->edges[i].top;
  484.         events[j].point.x = polygon->edges[i].line.p1.x;
  485.         events[j].edge = &edges[i];
  486.         j++;
  487.  
  488.         event_ptrs[j] = &events[j];
  489.         events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
  490.         events[j].point.y = polygon->edges[i].bottom;
  491.         events[j].point.x = polygon->edges[i].line.p1.x;
  492.         events[j].edge = &edges[i];
  493.         j++;
  494.     }
  495.  
  496.     status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
  497.                                                             fill_rule,
  498.                                                             TRUE, traps);
  499.     if (events != stack_events)
  500.         free (events);
  501.  
  502.     traps->is_rectilinear = TRUE;
  503.  
  504.     return status;
  505. }
  506.  
  507. cairo_status_t
  508. _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon,
  509.                                                                 cairo_fill_rule_t         fill_rule,
  510.                                                                 cairo_boxes_t *boxes)
  511. {
  512.     cairo_status_t status;
  513.     cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
  514.     cairo_bo_event_t *events;
  515.     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
  516.     cairo_bo_event_t **event_ptrs;
  517.     cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
  518.     cairo_bo_edge_t *edges;
  519.     int num_events;
  520.     int i, j;
  521.  
  522.     if (unlikely (polygon->num_edges == 0))
  523.         return CAIRO_STATUS_SUCCESS;
  524.  
  525.     num_events = 2 * polygon->num_edges;
  526.  
  527.     events = stack_events;
  528.     event_ptrs = stack_event_ptrs;
  529.     edges = stack_edges;
  530.     if (num_events > ARRAY_LENGTH (stack_events)) {
  531.         events = _cairo_malloc_ab_plus_c (num_events,
  532.                                           sizeof (cairo_bo_event_t) +
  533.                                           sizeof (cairo_bo_edge_t) +
  534.                                           sizeof (cairo_bo_event_t *),
  535.                                           sizeof (cairo_bo_event_t *));
  536.         if (unlikely (events == NULL))
  537.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  538.  
  539.         event_ptrs = (cairo_bo_event_t **) (events + num_events);
  540.         edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
  541.     }
  542.  
  543.     for (i = j = 0; i < polygon->num_edges; i++) {
  544.         edges[i].edge = polygon->edges[i];
  545.         edges[i].deferred_trap.right = NULL;
  546.         edges[i].prev = NULL;
  547.         edges[i].next = NULL;
  548.  
  549.         event_ptrs[j] = &events[j];
  550.         events[j].type = CAIRO_BO_EVENT_TYPE_START;
  551.         events[j].point.y = polygon->edges[i].top;
  552.         events[j].point.x = polygon->edges[i].line.p1.x;
  553.         events[j].edge = &edges[i];
  554.         j++;
  555.  
  556.         event_ptrs[j] = &events[j];
  557.         events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
  558.         events[j].point.y = polygon->edges[i].bottom;
  559.         events[j].point.x = polygon->edges[i].line.p1.x;
  560.         events[j].edge = &edges[i];
  561.         j++;
  562.     }
  563.  
  564.     status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
  565.                                                             fill_rule,
  566.                                                             FALSE, boxes);
  567.     if (events != stack_events)
  568.         free (events);
  569.  
  570.     return status;
  571. }
  572.  
  573. cairo_status_t
  574. _cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
  575.                                                      cairo_fill_rule_t fill_rule)
  576. {
  577.     cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
  578.     cairo_bo_event_t *events;
  579.     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
  580.     cairo_bo_event_t **event_ptrs;
  581.     cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
  582.     cairo_bo_edge_t *edges;
  583.     cairo_status_t status;
  584.     int i, j, k;
  585.  
  586.     if (unlikely (traps->num_traps == 0))
  587.         return CAIRO_STATUS_SUCCESS;
  588.  
  589.     assert (traps->is_rectilinear);
  590.  
  591.     i = 4 * traps->num_traps;
  592.  
  593.     events = stack_events;
  594.     event_ptrs = stack_event_ptrs;
  595.     edges = stack_edges;
  596.     if (i > ARRAY_LENGTH (stack_events)) {
  597.         events = _cairo_malloc_ab_plus_c (i,
  598.                                           sizeof (cairo_bo_event_t) +
  599.                                           sizeof (cairo_bo_edge_t) +
  600.                                           sizeof (cairo_bo_event_t *),
  601.                                           sizeof (cairo_bo_event_t *));
  602.         if (unlikely (events == NULL))
  603.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  604.  
  605.         event_ptrs = (cairo_bo_event_t **) (events + i);
  606.         edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
  607.     }
  608.  
  609.     for (i = j = k = 0; i < traps->num_traps; i++) {
  610.         edges[k].edge.top = traps->traps[i].top;
  611.         edges[k].edge.bottom = traps->traps[i].bottom;
  612.         edges[k].edge.line = traps->traps[i].left;
  613.         edges[k].edge.dir = 1;
  614.         edges[k].deferred_trap.right = NULL;
  615.         edges[k].prev = NULL;
  616.         edges[k].next = NULL;
  617.  
  618.         event_ptrs[j] = &events[j];
  619.         events[j].type = CAIRO_BO_EVENT_TYPE_START;
  620.         events[j].point.y = traps->traps[i].top;
  621.         events[j].point.x = traps->traps[i].left.p1.x;
  622.         events[j].edge = &edges[k];
  623.         j++;
  624.  
  625.         event_ptrs[j] = &events[j];
  626.         events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
  627.         events[j].point.y = traps->traps[i].bottom;
  628.         events[j].point.x = traps->traps[i].left.p1.x;
  629.         events[j].edge = &edges[k];
  630.         j++;
  631.         k++;
  632.  
  633.         edges[k].edge.top = traps->traps[i].top;
  634.         edges[k].edge.bottom = traps->traps[i].bottom;
  635.         edges[k].edge.line = traps->traps[i].right;
  636.         edges[k].edge.dir = -1;
  637.         edges[k].deferred_trap.right = NULL;
  638.         edges[k].prev = NULL;
  639.         edges[k].next = NULL;
  640.  
  641.         event_ptrs[j] = &events[j];
  642.         events[j].type = CAIRO_BO_EVENT_TYPE_START;
  643.         events[j].point.y = traps->traps[i].top;
  644.         events[j].point.x = traps->traps[i].right.p1.x;
  645.         events[j].edge = &edges[k];
  646.         j++;
  647.  
  648.         event_ptrs[j] = &events[j];
  649.         events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
  650.         events[j].point.y = traps->traps[i].bottom;
  651.         events[j].point.x = traps->traps[i].right.p1.x;
  652.         events[j].edge = &edges[k];
  653.         j++;
  654.         k++;
  655.     }
  656.  
  657.     _cairo_traps_clear (traps);
  658.     status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
  659.                                                             fill_rule,
  660.                                                             TRUE, traps);
  661.     traps->is_rectilinear = TRUE;
  662.  
  663.     if (events != stack_events)
  664.         free (events);
  665.  
  666.     return status;
  667. }
  668.