Subversion Repositories Kolibri OS

Rev

Rev 1892 | 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-arc-private.h"
  40.  
  41. #define MAX_FULL_CIRCLES 65536
  42.  
  43. /* Spline deviation from the circle in radius would be given by:
  44.  
  45.         error = sqrt (x**2 + y**2) - 1
  46.  
  47.    A simpler error function to work with is:
  48.  
  49.         e = x**2 + y**2 - 1
  50.  
  51.    From "Good approximation of circles by curvature-continuous Bezier
  52.    curves", Tor Dokken and Morten Daehlen, Computer Aided Geometric
  53.    Design 8 (1990) 22-41, we learn:
  54.  
  55.         abs (max(e)) = 4/27 * sin**6(angle/4) / cos**2(angle/4)
  56.  
  57.    and
  58.         abs (error) =~ 1/2 * e
  59.  
  60.    Of course, this error value applies only for the particular spline
  61.    approximation that is used in _cairo_gstate_arc_segment.
  62. */
  63. static double
  64. _arc_error_normalized (double angle)
  65. {
  66.     return 2.0/27.0 * pow (sin (angle / 4), 6) / pow (cos (angle / 4), 2);
  67. }
  68.  
  69. static double
  70. _arc_max_angle_for_tolerance_normalized (double tolerance)
  71. {
  72.     double angle, error;
  73.     int i;
  74.  
  75.     /* Use table lookup to reduce search time in most cases. */
  76.     struct {
  77.         double angle;
  78.         double error;
  79.     } table[] = {
  80.         { M_PI / 1.0,   0.0185185185185185036127 },
  81.         { M_PI / 2.0,   0.000272567143730179811158 },
  82.         { M_PI / 3.0,   2.38647043651461047433e-05 },
  83.         { M_PI / 4.0,   4.2455377443222443279e-06 },
  84.         { M_PI / 5.0,   1.11281001494389081528e-06 },
  85.         { M_PI / 6.0,   3.72662000942734705475e-07 },
  86.         { M_PI / 7.0,   1.47783685574284411325e-07 },
  87.         { M_PI / 8.0,   6.63240432022601149057e-08 },
  88.         { M_PI / 9.0,   3.2715520137536980553e-08 },
  89.         { M_PI / 10.0,  1.73863223499021216974e-08 },
  90.         { M_PI / 11.0,  9.81410988043554039085e-09 },
  91.     };
  92.     int table_size = ARRAY_LENGTH (table);
  93.  
  94.     for (i = 0; i < table_size; i++)
  95.         if (table[i].error < tolerance)
  96.             return table[i].angle;
  97.  
  98.     ++i;
  99.     do {
  100.         angle = M_PI / i++;
  101.         error = _arc_error_normalized (angle);
  102.     } while (error > tolerance);
  103.  
  104.     return angle;
  105. }
  106.  
  107. static int
  108. _arc_segments_needed (double          angle,
  109.                       double          radius,
  110.                       cairo_matrix_t *ctm,
  111.                       double          tolerance)
  112. {
  113.     double major_axis, max_angle;
  114.  
  115.     /* the error is amplified by at most the length of the
  116.      * major axis of the circle; see cairo-pen.c for a more detailed analysis
  117.      * of this. */
  118.     major_axis = _cairo_matrix_transformed_circle_major_axis (ctm, radius);
  119.     max_angle = _arc_max_angle_for_tolerance_normalized (tolerance / major_axis);
  120.  
  121.     return ceil (fabs (angle) / max_angle);
  122. }
  123.  
  124. /* We want to draw a single spline approximating a circular arc radius
  125.    R from angle A to angle B. Since we want a symmetric spline that
  126.    matches the endpoints of the arc in position and slope, we know
  127.    that the spline control points must be:
  128.  
  129.         (R * cos(A), R * sin(A))
  130.         (R * cos(A) - h * sin(A), R * sin(A) + h * cos (A))
  131.         (R * cos(B) + h * sin(B), R * sin(B) - h * cos (B))
  132.         (R * cos(B), R * sin(B))
  133.  
  134.    for some value of h.
  135.  
  136.    "Approximation of circular arcs by cubic polynomials", Michael
  137.    Goldapp, Computer Aided Geometric Design 8 (1991) 227-238, provides
  138.    various values of h along with error analysis for each.
  139.  
  140.    From that paper, a very practical value of h is:
  141.  
  142.         h = 4/3 * R * tan(angle/4)
  143.  
  144.    This value does not give the spline with minimal error, but it does
  145.    provide a very good approximation, (6th-order convergence), and the
  146.    error expression is quite simple, (see the comment for
  147.    _arc_error_normalized).
  148. */
  149. static void
  150. _cairo_arc_segment (cairo_t *cr,
  151.                     double   xc,
  152.                     double   yc,
  153.                     double   radius,
  154.                     double   angle_A,
  155.                     double   angle_B)
  156. {
  157.     double r_sin_A, r_cos_A;
  158.     double r_sin_B, r_cos_B;
  159.     double h;
  160.  
  161.     r_sin_A = radius * sin (angle_A);
  162.     r_cos_A = radius * cos (angle_A);
  163.     r_sin_B = radius * sin (angle_B);
  164.     r_cos_B = radius * cos (angle_B);
  165.  
  166.     h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
  167.  
  168.     cairo_curve_to (cr,
  169.                     xc + r_cos_A - h * r_sin_A,
  170.                     yc + r_sin_A + h * r_cos_A,
  171.                     xc + r_cos_B + h * r_sin_B,
  172.                     yc + r_sin_B - h * r_cos_B,
  173.                     xc + r_cos_B,
  174.                     yc + r_sin_B);
  175. }
  176.  
  177. static void
  178. _cairo_arc_in_direction (cairo_t          *cr,
  179.                          double            xc,
  180.                          double            yc,
  181.                          double            radius,
  182.                          double            angle_min,
  183.                          double            angle_max,
  184.                          cairo_direction_t dir)
  185. {
  186.     if (cairo_status (cr))
  187.         return;
  188.  
  189.     assert (angle_max >= angle_min);
  190.  
  191.     if (angle_max - angle_min > 2 * M_PI * MAX_FULL_CIRCLES) {
  192.         angle_max = fmod (angle_max - angle_min, 2 * M_PI);
  193.         angle_min = fmod (angle_min, 2 * M_PI);
  194.         angle_max += angle_min + 2 * M_PI * MAX_FULL_CIRCLES;
  195.     }
  196.  
  197.     /* Recurse if drawing arc larger than pi */
  198.     if (angle_max - angle_min > M_PI) {
  199.         double angle_mid = angle_min + (angle_max - angle_min) / 2.0;
  200.         if (dir == CAIRO_DIRECTION_FORWARD) {
  201.             _cairo_arc_in_direction (cr, xc, yc, radius,
  202.                                      angle_min, angle_mid,
  203.                                      dir);
  204.  
  205.             _cairo_arc_in_direction (cr, xc, yc, radius,
  206.                                      angle_mid, angle_max,
  207.                                      dir);
  208.         } else {
  209.             _cairo_arc_in_direction (cr, xc, yc, radius,
  210.                                      angle_mid, angle_max,
  211.                                      dir);
  212.  
  213.             _cairo_arc_in_direction (cr, xc, yc, radius,
  214.                                      angle_min, angle_mid,
  215.                                      dir);
  216.         }
  217.     } else if (angle_max != angle_min) {
  218.         cairo_matrix_t ctm;
  219.         int i, segments;
  220.         double step;
  221.  
  222.         cairo_get_matrix (cr, &ctm);
  223.         segments = _arc_segments_needed (angle_max - angle_min,
  224.                                          radius, &ctm,
  225.                                          cairo_get_tolerance (cr));
  226.         step = (angle_max - angle_min) / segments;
  227.         segments -= 1;
  228.  
  229.         if (dir == CAIRO_DIRECTION_REVERSE) {
  230.             double t;
  231.  
  232.             t = angle_min;
  233.             angle_min = angle_max;
  234.             angle_max = t;
  235.  
  236.             step = -step;
  237.         }
  238.  
  239.         for (i = 0; i < segments; i++, angle_min += step) {
  240.             _cairo_arc_segment (cr, xc, yc, radius,
  241.                                 angle_min, angle_min + step);
  242.         }
  243.  
  244.         _cairo_arc_segment (cr, xc, yc, radius,
  245.                             angle_min, angle_max);
  246.     } else {
  247.         cairo_line_to (cr,
  248.                        xc + radius * cos (angle_min),
  249.                        yc + radius * sin (angle_min));
  250.     }
  251. }
  252.  
  253. /**
  254.  * _cairo_arc_path:
  255.  * @cr: a cairo context
  256.  * @xc: X position of the center of the arc
  257.  * @yc: Y position of the center of the arc
  258.  * @radius: the radius of the arc
  259.  * @angle1: the start angle, in radians
  260.  * @angle2: the end angle, in radians
  261.  *
  262.  * Compute a path for the given arc and append it onto the current
  263.  * path within @cr. The arc will be accurate within the current
  264.  * tolerance and given the current transformation.
  265.  **/
  266. void
  267. _cairo_arc_path (cairo_t *cr,
  268.                  double   xc,
  269.                  double   yc,
  270.                  double   radius,
  271.                  double   angle1,
  272.                  double   angle2)
  273. {
  274.     _cairo_arc_in_direction (cr, xc, yc,
  275.                              radius,
  276.                              angle1, angle2,
  277.                              CAIRO_DIRECTION_FORWARD);
  278. }
  279.  
  280. /**
  281.  * _cairo_arc_path_negative:
  282.  * @xc: X position of the center of the arc
  283.  * @yc: Y position of the center of the arc
  284.  * @radius: the radius of the arc
  285.  * @angle1: the start angle, in radians
  286.  * @angle2: the end angle, in radians
  287.  * @ctm: the current transformation matrix
  288.  * @tolerance: the current tolerance value
  289.  * @path: the path onto which the arc will be appended
  290.  *
  291.  * Compute a path for the given arc (defined in the negative
  292.  * direction) and append it onto the current path within @cr. The arc
  293.  * will be accurate within the current tolerance and given the current
  294.  * transformation.
  295.  **/
  296. void
  297. _cairo_arc_path_negative (cairo_t *cr,
  298.                           double   xc,
  299.                           double   yc,
  300.                           double   radius,
  301.                           double   angle1,
  302.                           double   angle2)
  303. {
  304.     _cairo_arc_in_direction (cr, xc, yc,
  305.                              radius,
  306.                              angle2, angle1,
  307.                              CAIRO_DIRECTION_REVERSE);
  308. }
  309.