Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /* cairo - a vector graphics library with display and print output
  2.  *
  3.  * Copyright © 2002 University of Southern California
  4.  *
  5.  * This library is free software; you can redistribute it and/or
  6.  * modify it either under the terms of the GNU Lesser General Public
  7.  * License version 2.1 as published by the Free Software Foundation
  8.  * (the "LGPL") or, at your option, under the terms of the Mozilla
  9.  * Public License Version 1.1 (the "MPL"). If you do not alter this
  10.  * notice, a recipient may use your version of this file under either
  11.  * the MPL or the LGPL.
  12.  *
  13.  * You should have received a copy of the LGPL along with this library
  14.  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  15.  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  16.  * You should have received a copy of the MPL along with this library
  17.  * in the file COPYING-MPL-1.1
  18.  *
  19.  * The contents of this file are subject to the Mozilla Public License
  20.  * Version 1.1 (the "License"); you may not use this file except in
  21.  * compliance with the License. You may obtain a copy of the License at
  22.  * http://www.mozilla.org/MPL/
  23.  *
  24.  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  25.  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  26.  * the specific language governing rights and limitations.
  27.  *
  28.  * The Original Code is the cairo graphics library.
  29.  *
  30.  * The Initial Developer of the Original Code is University of Southern
  31.  * California.
  32.  *
  33.  * Contributor(s):
  34.  *      Carl D. Worth <cworth@cworth.org>
  35.  */
  36.  
  37. #include "cairoint.h"
  38.  
  39. #include "cairo-error-private.h"
  40. #include "cairo-slope-private.h"
  41.  
  42. void
  43. _cairo_polygon_init (cairo_polygon_t *polygon)
  44. {
  45.     VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
  46.  
  47.     polygon->status = CAIRO_STATUS_SUCCESS;
  48.  
  49.     polygon->num_edges = 0;
  50.  
  51.     polygon->edges = polygon->edges_embedded;
  52.     polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
  53.  
  54.     polygon->has_current_point = FALSE;
  55.     polygon->has_current_edge = FALSE;
  56.     polygon->num_limits = 0;
  57.  
  58.     polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
  59.     polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
  60. }
  61.  
  62. void
  63. _cairo_polygon_limit (cairo_polygon_t   *polygon,
  64.                       const cairo_box_t *limits,
  65.                       int num_limits)
  66. {
  67.     int n;
  68.  
  69.     polygon->limits = limits;
  70.     polygon->num_limits = num_limits;
  71.  
  72.     if (polygon->num_limits) {
  73.         polygon->limit = limits[0];
  74.         for (n = 1; n < num_limits; n++) {
  75.             if (limits[n].p1.x < polygon->limit.p1.x)
  76.                 polygon->limit.p1.x = limits[n].p1.x;
  77.  
  78.             if (limits[n].p1.y < polygon->limit.p1.y)
  79.                 polygon->limit.p1.y = limits[n].p1.y;
  80.  
  81.             if (limits[n].p2.x > polygon->limit.p2.x)
  82.                 polygon->limit.p2.x = limits[n].p2.x;
  83.  
  84.             if (limits[n].p2.y > polygon->limit.p2.y)
  85.                 polygon->limit.p2.y = limits[n].p2.y;
  86.         }
  87.     }
  88. }
  89.  
  90. void
  91. _cairo_polygon_fini (cairo_polygon_t *polygon)
  92. {
  93.     if (polygon->edges != polygon->edges_embedded)
  94.         free (polygon->edges);
  95.  
  96.     VG (VALGRIND_MAKE_MEM_NOACCESS (polygon, sizeof (cairo_polygon_t)));
  97. }
  98.  
  99. /* make room for at least one more edge */
  100. static cairo_bool_t
  101. _cairo_polygon_grow (cairo_polygon_t *polygon)
  102. {
  103.     cairo_edge_t *new_edges;
  104.     int old_size = polygon->edges_size;
  105.     int new_size = 4 * old_size;
  106.  
  107.     if (CAIRO_INJECT_FAULT ()) {
  108.         polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
  109.         return FALSE;
  110.     }
  111.  
  112.     if (polygon->edges == polygon->edges_embedded) {
  113.         new_edges = _cairo_malloc_ab (new_size, sizeof (cairo_edge_t));
  114.         if (new_edges != NULL)
  115.             memcpy (new_edges, polygon->edges, old_size * sizeof (cairo_edge_t));
  116.     } else {
  117.         new_edges = _cairo_realloc_ab (polygon->edges,
  118.                                        new_size, sizeof (cairo_edge_t));
  119.     }
  120.  
  121.     if (unlikely (new_edges == NULL)) {
  122.         polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
  123.         return FALSE;
  124.     }
  125.  
  126.     polygon->edges = new_edges;
  127.     polygon->edges_size = new_size;
  128.  
  129.     return TRUE;
  130. }
  131.  
  132. static void
  133. _add_edge (cairo_polygon_t *polygon,
  134.            const cairo_point_t *p1,
  135.            const cairo_point_t *p2,
  136.            int top, int bottom,
  137.            int dir)
  138. {
  139.     cairo_edge_t *edge;
  140.  
  141.     assert (top < bottom);
  142.  
  143.     if (unlikely (polygon->num_edges == polygon->edges_size)) {
  144.         if (! _cairo_polygon_grow (polygon))
  145.             return;
  146.     }
  147.  
  148.     edge = &polygon->edges[polygon->num_edges++];
  149.     edge->line.p1 = *p1;
  150.     edge->line.p2 = *p2;
  151.     edge->top = top;
  152.     edge->bottom = bottom;
  153.     edge->dir = dir;
  154.  
  155.     if (top < polygon->extents.p1.y)
  156.         polygon->extents.p1.y = top;
  157.     if (bottom > polygon->extents.p2.y)
  158.         polygon->extents.p2.y = bottom;
  159.  
  160.     if (p1->x < polygon->extents.p1.x || p1->x > polygon->extents.p2.x) {
  161.         cairo_fixed_t x = p1->x;
  162.         if (top != p1->y)
  163.             x = _cairo_edge_compute_intersection_x_for_y (p1, p2, top);
  164.         if (x < polygon->extents.p1.x)
  165.             polygon->extents.p1.x = x;
  166.         if (x > polygon->extents.p2.x)
  167.             polygon->extents.p2.x = x;
  168.     }
  169.  
  170.     if (p2->x < polygon->extents.p1.x || p2->x > polygon->extents.p2.x) {
  171.         cairo_fixed_t x = p2->x;
  172.         if (bottom != p2->y)
  173.             x = _cairo_edge_compute_intersection_x_for_y (p1, p2, bottom);
  174.         if (x < polygon->extents.p1.x)
  175.             polygon->extents.p1.x = x;
  176.         if (x > polygon->extents.p2.x)
  177.             polygon->extents.p2.x = x;
  178.     }
  179. }
  180.  
  181. static void
  182. _add_clipped_edge (cairo_polygon_t *polygon,
  183.                    const cairo_point_t *p1,
  184.                    const cairo_point_t *p2,
  185.                    const int top, const int bottom,
  186.                    const int dir)
  187. {
  188.     cairo_point_t p[2];
  189.     int top_y, bot_y;
  190.     int n;
  191.  
  192.     for (n = 0; n < polygon->num_limits; n++) {
  193.         const cairo_box_t *limits = &polygon->limits[n];
  194.  
  195.         if (top >= limits->p2.y)
  196.             continue;
  197.         if (bottom <= limits->p1.y)
  198.             continue;
  199.  
  200.         if (p1->x >= limits->p1.x && p2->x >= limits->p1.x &&
  201.             p1->x <= limits->p2.x && p2->x <= limits->p2.x)
  202.         {
  203.             top_y = top;
  204.             if (top_y < limits->p1.y)
  205.                 top_y = limits->p1.y;
  206.  
  207.             bot_y = bottom;
  208.             if (bot_y > limits->p2.y)
  209.                 bot_y = limits->p2.y;
  210.  
  211.             _add_edge (polygon, p1, p2, top_y, bot_y, dir);
  212.         }
  213.         else if (p1->x <= limits->p1.x && p2->x <= limits->p1.x)
  214.         {
  215.             p[0].x = limits->p1.x;
  216.             p[0].y = limits->p1.y;
  217.             top_y = top;
  218.             if (top_y < p[0].y)
  219.                 top_y = p[0].y;
  220.  
  221.             p[1].x = limits->p1.x;
  222.             p[1].y = limits->p2.y;
  223.             bot_y = bottom;
  224.             if (bot_y > p[1].y)
  225.                 bot_y = p[1].y;
  226.  
  227.             _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
  228.         }
  229.         else if (p1->x >= limits->p2.x && p2->x >= limits->p2.x)
  230.         {
  231.             p[0].x = limits->p2.x;
  232.             p[0].y = limits->p1.y;
  233.             top_y = top;
  234.             if (top_y < p[0].y)
  235.                 top_y = p[0].y;
  236.  
  237.             p[1].x = limits->p2.x;
  238.             p[1].y = limits->p2.y;
  239.             bot_y = bottom;
  240.             if (bot_y > p[1].y)
  241.                 bot_y = p[1].y;
  242.  
  243.             _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
  244.         }
  245.         else
  246.         {
  247.             int left_y, right_y;
  248.             int p1_y, p2_y;
  249.  
  250.             left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
  251.                                                                limits->p1.x);
  252.             right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
  253.                                                                 limits->p2.x);
  254.  
  255.             if (left_y == right_y) /* horizontal within bounds */
  256.                 continue;
  257.  
  258.             p1_y = top;
  259.             p2_y = bottom;
  260.  
  261.             if (left_y < right_y) {
  262.                 if (p1->x < limits->p1.x && left_y > limits->p1.y) {
  263.                     p[0].x = limits->p1.x;
  264.                     p[0].y = limits->p1.y;
  265.                     top_y = p1_y;
  266.                     if (top_y < p[0].y)
  267.                         top_y = p[0].y;
  268.  
  269.                     p[1].x = limits->p1.x;
  270.                     p[1].y = limits->p2.y;
  271.                     bot_y = left_y;
  272.                     if (bot_y > p[1].y)
  273.                         bot_y = p[1].y;
  274.  
  275.                     if (bot_y > top_y)
  276.                         _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
  277.                     p1_y = bot_y;
  278.                 }
  279.  
  280.                 if (p2->x > limits->p2.x && right_y < limits->p2.y) {
  281.                     p[0].x = limits->p2.x;
  282.                     p[0].y = limits->p1.y;
  283.                     top_y = right_y;
  284.                     if (top_y < p[0].y)
  285.                         top_y = p[0].y;
  286.  
  287.                     p[1].x = limits->p2.x;
  288.                     p[1].y = limits->p2.y;
  289.                     bot_y = p2_y;
  290.                     if (bot_y > p[1].y)
  291.                         bot_y = p[1].y;
  292.  
  293.                     if (bot_y > top_y)
  294.                         _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
  295.                     p2_y = top_y;
  296.                 }
  297.             } else {
  298.                 if (p1->x > limits->p2.x && right_y > limits->p1.y) {
  299.                     p[0].x = limits->p2.x;
  300.                     p[0].y = limits->p1.y;
  301.                     top_y = p1_y;
  302.                     if (top_y < p[0].y)
  303.                         top_y = p[0].y;
  304.  
  305.                     p[1].x = limits->p2.x;
  306.                     p[1].y = limits->p2.y;
  307.                     bot_y = right_y;
  308.                     if (bot_y > p[1].y)
  309.                         bot_y = p[1].y;
  310.  
  311.                     if (bot_y > top_y)
  312.                         _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
  313.                     p1_y = bot_y;
  314.                 }
  315.  
  316.                 if (p2->x < limits->p1.x && left_y < limits->p2.y) {
  317.                     p[0].x = limits->p1.x;
  318.                     p[0].y = limits->p1.y;
  319.                     top_y = left_y;
  320.                     if (top_y < p[0].y)
  321.                         top_y = p[0].y;
  322.  
  323.                     p[1].x = limits->p1.x;
  324.                     p[1].y = limits->p2.y;
  325.                     bot_y = p2_y;
  326.                     if (bot_y > p[1].y)
  327.                         bot_y = p[1].y;
  328.  
  329.                     if (bot_y > top_y)
  330.                         _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
  331.                     p2_y = top_y;
  332.                 }
  333.             }
  334.  
  335.             if (p1_y < limits->p1.y)
  336.                 p1_y = limits->p1.y;
  337.             if (p2_y > limits->p2.y)
  338.                 p2_y = limits->p2.y;
  339.             if (p2_y > p1_y)
  340.                 _add_edge (polygon, p1, p2, p1_y, p2_y, dir);
  341.         }
  342.     }
  343. }
  344.  
  345. static void
  346. _cairo_polygon_add_edge (cairo_polygon_t *polygon,
  347.                          const cairo_point_t *p1,
  348.                          const cairo_point_t *p2)
  349. {
  350.     int dir;
  351.  
  352.     /* drop horizontal edges */
  353.     if (p1->y == p2->y)
  354.         return;
  355.  
  356.     if (p1->y < p2->y) {
  357.         dir = 1;
  358.     } else {
  359.         const cairo_point_t *t;
  360.         t = p1, p1 = p2, p2 = t;
  361.         dir = -1;
  362.     }
  363.  
  364.     if (polygon->num_limits) {
  365.         if (p2->y <= polygon->limit.p1.y)
  366.             return;
  367.  
  368.         if (p1->y >= polygon->limit.p2.y)
  369.             return;
  370.  
  371.         _add_clipped_edge (polygon, p1, p2, p1->y, p2->y, dir);
  372.     } else
  373.         _add_edge (polygon, p1, p2, p1->y, p2->y, dir);
  374. }
  375.  
  376. cairo_status_t
  377. _cairo_polygon_add_external_edge (void *polygon,
  378.                                   const cairo_point_t *p1,
  379.                                   const cairo_point_t *p2)
  380. {
  381.     _cairo_polygon_add_edge (polygon, p1, p2);
  382.     return _cairo_polygon_status (polygon);
  383. }
  384.  
  385. cairo_status_t
  386. _cairo_polygon_add_line (cairo_polygon_t *polygon,
  387.                          const cairo_line_t *line,
  388.                          int top, int bottom,
  389.                          int dir)
  390. {
  391.     /* drop horizontal edges */
  392.     if (line->p1.y == line->p2.y)
  393.         return CAIRO_STATUS_SUCCESS;
  394.  
  395.     if (bottom <= top)
  396.         return CAIRO_STATUS_SUCCESS;
  397.  
  398.     if (polygon->num_limits) {
  399.         if (line->p2.y <= polygon->limit.p1.y)
  400.             return CAIRO_STATUS_SUCCESS;
  401.  
  402.         if (line->p1.y >= polygon->limit.p2.y)
  403.             return CAIRO_STATUS_SUCCESS;
  404.  
  405.         _add_clipped_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
  406.     } else
  407.         _add_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
  408.  
  409.     return polygon->status;
  410. }
  411.  
  412. /* flattened path operations */
  413.  
  414. cairo_status_t
  415. _cairo_polygon_move_to (cairo_polygon_t *polygon,
  416.                         const cairo_point_t *point)
  417. {
  418.     if (polygon->has_current_edge) {
  419.         _cairo_polygon_add_edge (polygon,
  420.                                  &polygon->last_point,
  421.                                  &polygon->current_point);
  422.         polygon->has_current_edge = FALSE;
  423.     }
  424.  
  425.     if (! polygon->has_current_point) {
  426.         polygon->first_point = *point;
  427.         polygon->has_current_point = TRUE;
  428.     }
  429.  
  430.     polygon->current_point = *point;
  431.     return polygon->status;
  432. }
  433.  
  434. cairo_status_t
  435. _cairo_polygon_line_to (cairo_polygon_t *polygon,
  436.                         const cairo_point_t *point)
  437. {
  438.     /* squash collinear edges */
  439.     if (polygon->has_current_edge) {
  440.         if (polygon->current_point.x != point->x ||
  441.             polygon->current_point.y != point->y)
  442.         {
  443.             cairo_slope_t this;
  444.  
  445.             _cairo_slope_init (&this, &polygon->current_point, point);
  446.             if (_cairo_slope_equal (&polygon->current_edge, &this)) {
  447.                 polygon->current_point = *point;
  448.                 return CAIRO_STATUS_SUCCESS;
  449.             }
  450.  
  451.             _cairo_polygon_add_edge (polygon,
  452.                                      &polygon->last_point,
  453.                                      &polygon->current_point);
  454.  
  455.             polygon->last_point = polygon->current_point;
  456.             polygon->current_edge = this;
  457.         }
  458.     } else if (polygon->has_current_point) {
  459.         if (polygon->current_point.x != point->x ||
  460.             polygon->current_point.y != point->y)
  461.         {
  462.             polygon->last_point = polygon->current_point;
  463.             _cairo_slope_init (&polygon->current_edge,
  464.                                &polygon->last_point,
  465.                                point);
  466.             polygon->has_current_edge = TRUE;
  467.         }
  468.     } else {
  469.         polygon->first_point = *point;
  470.         polygon->has_current_point = TRUE;
  471.     }
  472.  
  473.     polygon->current_point = *point;
  474.     return polygon->status;
  475. }
  476.  
  477. cairo_status_t
  478. _cairo_polygon_close (cairo_polygon_t *polygon)
  479. {
  480.     cairo_status_t status;
  481.  
  482.     if (polygon->has_current_point) {
  483.         status = _cairo_polygon_line_to (polygon, &polygon->first_point);
  484.         polygon->has_current_point = FALSE;
  485.     }
  486.  
  487.     if (polygon->has_current_edge) {
  488.         _cairo_polygon_add_edge (polygon,
  489.                                  &polygon->last_point,
  490.                                  &polygon->current_point);
  491.         polygon->has_current_edge = FALSE;
  492.     }
  493.  
  494.     return polygon->status;
  495. }
  496.