Subversion Repositories Kolibri OS

Rev

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

  1. /**************************************************************************
  2.  *
  3.  * Copyright 2009 VMware, Inc.  All Rights Reserved.
  4.  *
  5.  * Permission is hereby granted, free of charge, to any person obtaining a
  6.  * copy of this software and associated documentation files (the
  7.  * "Software"), to deal in the Software without restriction, including
  8.  * without limitation the rights to use, copy, modify, merge, publish,
  9.  * distribute, sub license, and/or sell copies of the Software, and to
  10.  * permit persons to whom the Software is furnished to do so, subject to
  11.  * the following conditions:
  12.  *
  13.  * The above copyright notice and this permission notice (including the
  14.  * next paragraph) shall be included in all copies or substantial portions
  15.  * of the Software.
  16.  *
  17.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18.  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19.  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  20.  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  21.  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  22.  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  23.  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24.  *
  25.  **************************************************************************/
  26.  
  27. #include "bezier.h"
  28.  
  29. #include "matrix.h"
  30. #include "polygon.h"
  31.  
  32. #include "pipe/p_compiler.h"
  33. #include "util/u_debug.h"
  34.  
  35. #include <stdlib.h>
  36. #include <stdio.h>
  37. #include <assert.h>
  38. #include <math.h>
  39.  
  40. static const float flatness = 0.5;
  41.  
  42.  
  43. static INLINE void split_left(struct bezier *bez, VGfloat t, struct bezier* left)
  44. {
  45.     left->x1 = bez->x1;
  46.     left->y1 = bez->y1;
  47.  
  48.     left->x2 = bez->x1 + t * (bez->x2 - bez->x1);
  49.     left->y2 = bez->y1 + t * (bez->y2 - bez->y1);
  50.  
  51.     left->x3 = bez->x2 + t * (bez->x3 - bez->x2);
  52.     left->y3 = bez->y2 + t * (bez->y3 - bez->y2);
  53.  
  54.     bez->x3 = bez->x3 + t * (bez->x4 - bez->x3);
  55.     bez->y3 = bez->y3 + t * (bez->y4 - bez->y3);
  56.  
  57.     bez->x2 = left->x3 + t * (bez->x3 - left->x3);
  58.     bez->y2 = left->y3 + t * (bez->y3 - left->y3);
  59.  
  60.     left->x3 = left->x2 + t * (left->x3 - left->x2);
  61.     left->y3 = left->y2 + t * (left->y3 - left->y2);
  62.  
  63.     left->x4 = bez->x1 = left->x3 + t * (bez->x2 - left->x3);
  64.     left->y4 = bez->y1 = left->y3 + t * (bez->y2 - left->y3);
  65. }
  66.  
  67. static INLINE void split(struct bezier *bez,
  68.                          struct bezier *first_half,
  69.                          struct bezier *second_half)
  70. {
  71.    double c         = (bez->x2 + bez->x3) * 0.5;
  72.    first_half->x2  = (bez->x1 + bez->x2) * 0.5;
  73.    second_half->x3 = (bez->x3 + bez->x4) * 0.5;
  74.    first_half->x1  = bez->x1;
  75.    second_half->x4 = bez->x4;
  76.    first_half->x3  = (first_half->x2 + c) * 0.5;
  77.    second_half->x2 = (second_half->x3 + c) * 0.5;
  78.    first_half->x4  = second_half->x1 =
  79.                      (first_half->x3 + second_half->x2) * 0.5;
  80.  
  81.    c = (bez->y2 + bez->y3) / 2;
  82.    first_half->y2  = (bez->y1 + bez->y2) * 0.5;
  83.    second_half->y3 = (bez->y3 + bez->y4) * 0.5;
  84.    first_half->y1  = bez->y1;
  85.    second_half->y4 = bez->y4;
  86.    first_half->y3  = (first_half->y2 + c) * 0.5;
  87.    second_half->y2 = (second_half->y3 + c) * 0.5;
  88.    first_half->y4  = second_half->y1 =
  89.                      (first_half->y3 + second_half->y2) * 0.5;
  90. }
  91.  
  92. struct polygon * bezier_to_polygon(struct bezier *bez)
  93. {
  94.    struct polygon *poly = polygon_create(64);
  95.    polygon_vertex_append(poly, bez->x1, bez->y1);
  96.    bezier_add_to_polygon(bez, poly);
  97.    return poly;
  98. }
  99.  
  100. void bezier_add_to_polygon(const struct bezier *bez,
  101.                            struct polygon *poly)
  102. {
  103.    struct bezier beziers[32];
  104.    struct bezier *b;
  105.  
  106.    beziers[0] = *bez;
  107.    b = beziers;
  108.  
  109.    while (b >= beziers) {
  110.       double y4y1 = b->y4 - b->y1;
  111.       double x4x1 = b->x4 - b->x1;
  112.       double l = ABS(x4x1) + ABS(y4y1);
  113.       double d;
  114.       if (l > 1.f) {
  115.          d = ABS((x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2))
  116.              + ABS((x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3));
  117.       } else {
  118.          d = ABS(b->x1 - b->x2) + ABS(b->y1 - b->y2) +
  119.              ABS(b->x1 - b->x3) + ABS(b->y1 - b->y3);
  120.          l = 1.;
  121.       }
  122.       if (d < flatness*l || b == beziers + 31) {
  123.          /* good enough, we pop it off and add the endpoint */
  124.          polygon_vertex_append(poly, b->x4, b->y4);
  125.          --b;
  126.       } else {
  127.          /* split, second half of the bezier goes lower into the stack */
  128.          split(b, b+1, b);
  129.          ++b;
  130.       }
  131.    }
  132. }
  133.  
  134. static void add_if_close(struct bezier *bez, VGfloat *length, VGfloat error)
  135. {
  136.    struct bezier left, right;     /* bez poly splits */
  137.    VGfloat len = 0.0;        /* arc length */
  138.    VGfloat chord;            /* chord length */
  139.  
  140.    len = len + line_length(bez->x1, bez->y1, bez->x2, bez->y2);
  141.    len = len + line_length(bez->x2, bez->y2, bez->x3, bez->y3);
  142.    len = len + line_length(bez->x3, bez->y3, bez->x4, bez->y4);
  143.  
  144.    chord = line_length(bez->x1, bez->y1, bez->x4, bez->y4);
  145.  
  146.    if ((len-chord) > error) {
  147.       split(bez, &left, &right);                 /* split in two */
  148.       add_if_close(&left, length, error);       /* try left side */
  149.       add_if_close(&right, length, error);      /* try right side */
  150.       return;
  151.    }
  152.  
  153.    *length = *length + len;
  154.  
  155.    return;
  156. }
  157.  
  158. float bezier_length(struct bezier *bez, float error)
  159. {
  160.    VGfloat length = 0.f;
  161.  
  162.    add_if_close(bez, &length, error);
  163.    return length;
  164. }
  165.  
  166. void bezier_init(struct bezier *bez,
  167.                  float x1, float y1,
  168.                  float x2, float y2,
  169.                  float x3, float y3,
  170.                  float x4, float y4)
  171. {
  172.    bez->x1 = x1;
  173.    bez->y1 = y1;
  174.    bez->x2 = x2;
  175.    bez->y2 = y2;
  176.    bez->x3 = x3;
  177.    bez->y3 = y3;
  178.    bez->x4 = x4;
  179.    bez->y4 = y4;
  180. #if 0
  181.    debug_printf("bezier in [%f, %f, %f, %f, %f, %f]\n",
  182.                 x1, y1, x2, y2, x3, y3, x4, y4);
  183. #endif
  184. }
  185.  
  186.  
  187. static INLINE void bezier_init2v(struct bezier *bez,
  188.                                  float *pt1,
  189.                                  float *pt2,
  190.                                  float *pt3,
  191.                                  float *pt4)
  192. {
  193.    bez->x1 = pt1[0];
  194.    bez->y1 = pt1[1];
  195.  
  196.    bez->x2 = pt2[0];
  197.    bez->y2 = pt2[1];
  198.  
  199.    bez->x3 = pt3[0];
  200.    bez->y3 = pt3[1];
  201.  
  202.    bez->x4 = pt4[0];
  203.    bez->y4 = pt4[1];
  204. }
  205.  
  206.  
  207. void bezier_transform(struct bezier *bez,
  208.                       struct matrix *matrix)
  209. {
  210.    assert(matrix_is_affine(matrix));
  211.    matrix_map_point(matrix, bez->x1, bez->y1, &bez->x1, &bez->y1);
  212.    matrix_map_point(matrix, bez->x2, bez->y2, &bez->x2, &bez->y2);
  213.    matrix_map_point(matrix, bez->x3, bez->y3, &bez->x3, &bez->y3);
  214.    matrix_map_point(matrix, bez->x4, bez->y4, &bez->x4, &bez->y4);
  215. }
  216.  
  217. static INLINE void bezier_point_at(const struct bezier *bez, float t, float *pt)
  218. {
  219.    float a, b, c, d;
  220.    float m_t;
  221.    m_t = 1. - t;
  222.    b = m_t * m_t;
  223.    c = t * t;
  224.    d = c * t;
  225.    a = b * m_t;
  226.    b *= 3. * t;
  227.    c *= 3. * m_t;
  228.    pt[0] = a*bez->x1 + b*bez->x2 + c*bez->x3 + d*bez->x4;
  229.    pt[1] = a*bez->y1 + b*bez->y2 + c*bez->y3 + d*bez->y4;
  230. }
  231.  
  232. static INLINE void bezier_normal_at(const struct bezier *bez, float t, float *norm)
  233. {
  234.    float m_t = 1. - t;
  235.    float a = m_t * m_t;
  236.    float b = t * m_t;
  237.    float c = t * t;
  238.  
  239.    norm[0] =  (bez->y2-bez->y1) * a + (bez->y3-bez->y2) * b + (bez->y4-bez->y3) * c;
  240.    norm[1] = -(bez->x2-bez->x1) * a - (bez->x3-bez->x2) * b - (bez->x4-bez->x3) * c;
  241. }
  242.  
  243. enum shift_result {
  244.    Ok,
  245.    Discard,
  246.    Split,
  247.    Circle
  248. };
  249.  
  250. static enum shift_result good_offset(const struct bezier *b1,
  251.                                      const struct bezier *b2,
  252.                                      float offset, float threshold)
  253. {
  254.    const float o2 = offset*offset;
  255.    const float max_dist_line = threshold*offset*offset;
  256.    const float max_dist_normal = threshold*offset;
  257.    const float spacing = 0.25;
  258.    float i;
  259.    for (i = spacing; i < 0.99; i += spacing) {
  260.       float p1[2],p2[2], d, l;
  261.       float normal[2];
  262.       bezier_point_at(b1, i, p1);
  263.       bezier_point_at(b2, i, p2);
  264.       d = (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
  265.       if (ABS(d - o2) > max_dist_line)
  266.          return Split;
  267.  
  268.       bezier_normal_at(b1, i, normal);
  269.       l = ABS(normal[0]) + ABS(normal[1]);
  270.       if (l != 0.) {
  271.          d = ABS(normal[0]*(p1[1] - p2[1]) - normal[1]*(p1[0] - p2[0]) ) / l;
  272.          if (d > max_dist_normal)
  273.             return Split;
  274.       }
  275.    }
  276.    return Ok;
  277. }
  278.  
  279. static INLINE void shift_line_by_normal(float *l, float offset)
  280. {
  281.    float norm[4];
  282.    float tx, ty;
  283.  
  284.    line_normal(l, norm);
  285.    line_normalize(norm);
  286.  
  287.    tx = (norm[2] - norm[0]) * offset;
  288.    ty = (norm[3] - norm[1]) * offset;
  289.    l[0] += tx; l[1] += ty;
  290.    l[2] += tx; l[3] += ty;
  291. }
  292.  
  293. static INLINE VGboolean is_bezier_line(float (*points)[2], int count)
  294. {
  295.    float dx13 = points[2][0] - points[0][0];
  296.    float dy13 = points[2][1] - points[0][1];
  297.  
  298.    float dx12 = points[1][0] - points[0][0];
  299.    float dy12 = points[1][1] - points[0][1];
  300.  
  301.    debug_assert(count > 2);
  302.  
  303.    if (count == 3) {
  304.       return floatsEqual(dx12 * dy13, dx13 * dy12);
  305.    } else if (count == 4) {
  306.       float dx14 = points[3][0] - points[0][0];
  307.       float dy14 = points[3][1] - points[0][1];
  308.  
  309.       return (floatsEqual(dx12 * dy13, dx13 * dy12) &&
  310.               floatsEqual(dx12 * dy14, dx14 * dy12));
  311.    }
  312.  
  313.    return VG_FALSE;
  314. }
  315.  
  316. static INLINE void compute_pt_normal(float *pt1, float *pt2, float *res)
  317. {
  318.    float line[4];
  319.    float normal[4];
  320.    line[0] = 0.f; line[1] = 0.f;
  321.    line[2] = pt2[0] - pt1[0];
  322.    line[3] = pt2[1] - pt1[1];
  323.    line_normal(line, normal);
  324.    line_normalize(normal);
  325.  
  326.    res[0] = normal[2];
  327.    res[1] = normal[3];
  328. }
  329.  
  330. static enum shift_result shift(const struct bezier *orig,
  331.                                struct bezier *shifted,
  332.                                float offset, float threshold)
  333. {
  334.    int i;
  335.    int map[4];
  336.    VGboolean p1_p2_equal = (orig->x1 == orig->x2 && orig->y1 == orig->y2);
  337.    VGboolean p2_p3_equal = (orig->x2 == orig->x3 && orig->y2 == orig->y3);
  338.    VGboolean p3_p4_equal = (orig->x3 == orig->x4 && orig->y3 == orig->y4);
  339.  
  340.    float points[4][2];
  341.    int np = 0;
  342.    float bounds[4];
  343.    float points_shifted[4][2];
  344.    float prev_normal[2];
  345.  
  346.    points[np][0] = orig->x1;
  347.    points[np][1] = orig->y1;
  348.    map[0] = 0;
  349.    ++np;
  350.    if (!p1_p2_equal) {
  351.       points[np][0] = orig->x2;
  352.       points[np][1] = orig->y2;
  353.       ++np;
  354.    }
  355.    map[1] = np - 1;
  356.    if (!p2_p3_equal) {
  357.       points[np][0] = orig->x3;
  358.       points[np][1] = orig->y3;
  359.       ++np;
  360.    }
  361.    map[2] = np - 1;
  362.    if (!p3_p4_equal) {
  363.       points[np][0] = orig->x4;
  364.       points[np][1] = orig->y4;
  365.       ++np;
  366.    }
  367.    map[3] = np - 1;
  368.    if (np == 1)
  369.       return Discard;
  370.  
  371.    /* We need to specialcase lines of 3 or 4 points due to numerical
  372.       instability in intersection code below */
  373.    if (np > 2 && is_bezier_line(points, np)) {
  374.       float l[4] = { points[0][0], points[0][1],
  375.                      points[np-1][0], points[np-1][1] };
  376.       float ctrl1[2], ctrl2[2];
  377.       if (floatsEqual(points[0][0], points[np-1][0]) &&
  378.           floatsEqual(points[0][1], points[np-1][1]))
  379.          return Discard;
  380.  
  381.       shift_line_by_normal(l, offset);
  382.       line_point_at(l, 0.33, ctrl1);
  383.       line_point_at(l, 0.66, ctrl2);
  384.       bezier_init(shifted, l[0], l[1],
  385.                   ctrl1[0], ctrl1[1], ctrl2[0], ctrl2[1],
  386.                   l[2], l[3]);
  387.       return Ok;
  388.    }
  389.  
  390.    bezier_bounds(orig, bounds);
  391.    if (np == 4 && bounds[2] < .1*offset && bounds[3] < .1*offset) {
  392.       float l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +
  393.                 (orig->y1 - orig->y2)*(orig->y1 - orig->y1) *
  394.                 (orig->x3 - orig->x4)*(orig->x3 - orig->x4) +
  395.                 (orig->y3 - orig->y4)*(orig->y3 - orig->y4);
  396.       float dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +
  397.                   (orig->y1 - orig->y2)*(orig->y3 - orig->y4);
  398.       if (dot < 0 && dot*dot < 0.8*l)
  399.          /* the points are close and reverse dirction. Approximate the whole
  400.             thing by a semi circle */
  401.          return Circle;
  402.    }
  403.  
  404.    compute_pt_normal(points[0], points[1], prev_normal);
  405.  
  406.    points_shifted[0][0] = points[0][0] + offset * prev_normal[0];
  407.    points_shifted[0][1] = points[0][1] + offset * prev_normal[1];
  408.  
  409.    for (i = 1; i < np - 1; ++i) {
  410.       float normal_sum[2], r;
  411.       float next_normal[2];
  412.       compute_pt_normal(points[i], points[i + 1], next_normal);
  413.  
  414.       normal_sum[0] = prev_normal[0] + next_normal[0];
  415.       normal_sum[1] = prev_normal[1] + next_normal[1];
  416.  
  417.       r = 1.0 + prev_normal[0] * next_normal[0]
  418.           + prev_normal[1] * next_normal[1];
  419.  
  420.       if (floatsEqual(r + 1, 1)) {
  421.          points_shifted[i][0] = points[i][0] + offset * prev_normal[0];
  422.          points_shifted[i][1] = points[i][1] + offset * prev_normal[1];
  423.       } else {
  424.          float k = offset / r;
  425.          points_shifted[i][0] = points[i][0] + k * normal_sum[0];
  426.          points_shifted[i][1] = points[i][1] + k * normal_sum[1];
  427.       }
  428.  
  429.       prev_normal[0] = next_normal[0];
  430.       prev_normal[1] = next_normal[1];
  431.    }
  432.  
  433.    points_shifted[np - 1][0] = points[np - 1][0] + offset * prev_normal[0];
  434.    points_shifted[np - 1][1] = points[np - 1][1] + offset * prev_normal[1];
  435.  
  436.    bezier_init2v(shifted,
  437.                  points_shifted[map[0]], points_shifted[map[1]],
  438.                  points_shifted[map[2]], points_shifted[map[3]]);
  439.  
  440.    return good_offset(orig, shifted, offset, threshold);
  441. }
  442.  
  443. static VGboolean make_circle(const struct bezier *b, float offset, struct bezier *o)
  444. {
  445.    float normals[3][2];
  446.    float dist;
  447.    float angles[2];
  448.    float sign = 1.f;
  449.    int i;
  450.    float circle[3][2];
  451.  
  452.    normals[0][0] = b->y2 - b->y1;
  453.    normals[0][1] = b->x1 - b->x2;
  454.    dist = sqrt(normals[0][0]*normals[0][0] + normals[0][1]*normals[0][1]);
  455.    if (floatsEqual(dist + 1, 1.f))
  456.       return VG_FALSE;
  457.    normals[0][0] /= dist;
  458.    normals[0][1] /= dist;
  459.  
  460.    normals[2][0] = b->y4 - b->y3;
  461.    normals[2][1] = b->x3 - b->x4;
  462.    dist = sqrt(normals[2][0]*normals[2][0] + normals[2][1]*normals[2][1]);
  463.    if (floatsEqual(dist + 1, 1.f))
  464.       return VG_FALSE;
  465.    normals[2][0] /= dist;
  466.    normals[2][1] /= dist;
  467.  
  468.    normals[1][0] = b->x1 - b->x2 - b->x3 + b->x4;
  469.    normals[1][1] = b->y1 - b->y2 - b->y3 + b->y4;
  470.    dist = -1*sqrt(normals[1][0]*normals[1][0] + normals[1][1]*normals[1][1]);
  471.    normals[1][0] /= dist;
  472.    normals[1][1] /= dist;
  473.  
  474.    for (i = 0; i < 2; ++i) {
  475.       float cos_a = normals[i][0]*normals[i+1][0] + normals[i][1]*normals[i+1][1];
  476.       if (cos_a > 1.)
  477.          cos_a = 1.;
  478.       if (cos_a < -1.)
  479.          cos_a = -1;
  480.       angles[i] = acos(cos_a)/M_PI;
  481.    }
  482.  
  483.    if (angles[0] + angles[1] > 1.) {
  484.       /* more than 180 degrees */
  485.       normals[1][0] = -normals[1][0];
  486.       normals[1][1] = -normals[1][1];
  487.       angles[0] = 1. - angles[0];
  488.       angles[1] = 1. - angles[1];
  489.       sign = -1.;
  490.    }
  491.  
  492.    circle[0][0] = b->x1 + normals[0][0]*offset;
  493.    circle[0][1] = b->y1 + normals[0][1]*offset;
  494.  
  495.    circle[1][0] = 0.5*(b->x1 + b->x4) + normals[1][0]*offset;
  496.    circle[1][1] = 0.5*(b->y1 + b->y4) + normals[1][1]*offset;
  497.  
  498.    circle[2][0] = b->x4 + normals[2][0]*offset;
  499.    circle[2][1] = b->y4 + normals[2][1]*offset;
  500.  
  501.    for (i = 0; i < 2; ++i) {
  502.       float kappa = 2.*KAPPA * sign * offset * angles[i];
  503.  
  504.       o->x1 = circle[i][0];
  505.       o->y1 = circle[i][1];
  506.       o->x2 = circle[i][0] - normals[i][1]*kappa;
  507.       o->y2 = circle[i][1] + normals[i][0]*kappa;
  508.       o->x3 = circle[i+1][0] + normals[i+1][1]*kappa;
  509.       o->y3 = circle[i+1][1] - normals[i+1][0]*kappa;
  510.       o->x4 = circle[i+1][0];
  511.       o->y4 = circle[i+1][1];
  512.  
  513.       ++o;
  514.    }
  515.    return VG_TRUE;
  516. }
  517.  
  518. int bezier_translate_by_normal(struct bezier *bez,
  519.                                struct bezier *curves,
  520.                                int max_curves,
  521.                                float normal_len,
  522.                                float threshold)
  523. {
  524.    struct bezier beziers[10];
  525.    struct bezier *b, *o;
  526.  
  527.    /* fixme: this should really be floatsEqual */
  528.    if (bez->x1 == bez->x2 && bez->x1 == bez->x3 && bez->x1 == bez->x4 &&
  529.        bez->y1 == bez->y2 && bez->y1 == bez->y3 && bez->y1 == bez->y4)
  530.       return 0;
  531.  
  532.    --max_curves;
  533. redo:
  534.    beziers[0] = *bez;
  535.    b = beziers;
  536.    o = curves;
  537.  
  538.    while (b >= beziers) {
  539.       int stack_segments = b - beziers + 1;
  540.       enum shift_result res;
  541.       if ((stack_segments == 10) || (o - curves == max_curves - stack_segments)) {
  542.          threshold *= 1.5;
  543.          if (threshold > 2.)
  544.             goto give_up;
  545.          goto redo;
  546.       }
  547.       res = shift(b, o, normal_len, threshold);
  548.       if (res == Discard) {
  549.          --b;
  550.       } else if (res == Ok) {
  551.          ++o;
  552.          --b;
  553.          continue;
  554.       } else if (res == Circle && max_curves - (o - curves) >= 2) {
  555.          /* add semi circle */
  556.          if (make_circle(b, normal_len, o))
  557.             o += 2;
  558.          --b;
  559.       } else {
  560.          split(b, b+1, b);
  561.          ++b;
  562.       }
  563.    }
  564.  
  565. give_up:
  566.    while (b >= beziers) {
  567.       enum shift_result res = shift(b, o, normal_len, threshold);
  568.  
  569.       /* if res isn't Ok or Split then *o is undefined */
  570.       if (res == Ok || res == Split)
  571.          ++o;
  572.  
  573.       --b;
  574.    }
  575.  
  576.    debug_assert(o - curves <= max_curves);
  577.    return o - curves;
  578. }
  579.  
  580. void bezier_bounds(const struct bezier *bez,
  581.                    float *bounds/*x/y/width/height*/)
  582. {
  583.    float xmin = bez->x1;
  584.    float xmax = bez->x1;
  585.    float ymin = bez->y1;
  586.    float ymax = bez->y1;
  587.  
  588.    if (bez->x2 < xmin)
  589.       xmin = bez->x2;
  590.    else if (bez->x2 > xmax)
  591.       xmax = bez->x2;
  592.    if (bez->x3 < xmin)
  593.       xmin = bez->x3;
  594.    else if (bez->x3 > xmax)
  595.       xmax = bez->x3;
  596.    if (bez->x4 < xmin)
  597.       xmin = bez->x4;
  598.    else if (bez->x4 > xmax)
  599.       xmax = bez->x4;
  600.  
  601.    if (bez->y2 < ymin)
  602.       ymin = bez->y2;
  603.    else if (bez->y2 > ymax)
  604.       ymax = bez->y2;
  605.    if (bez->y3 < ymin)
  606.       ymin = bez->y3;
  607.    else if (bez->y3 > ymax)
  608.       ymax = bez->y3;
  609.    if (bez->y4 < ymin)
  610.       ymin = bez->y4;
  611.    else if (bez->y4 > ymax)
  612.       ymax = bez->y4;
  613.  
  614.    bounds[0] = xmin; /* x */
  615.    bounds[1] = ymin; /* y */
  616.    bounds[2] = xmax - xmin; /* width */
  617.    bounds[3] = ymax - ymin; /* height */
  618. }
  619.  
  620. void bezier_start_tangent(const struct bezier *bez,
  621.                           float *tangent)
  622. {
  623.    tangent[0] = bez->x1;
  624.    tangent[1] = bez->y1;
  625.    tangent[2] = bez->x2;
  626.    tangent[3] = bez->y2;
  627.  
  628.    if (null_line(tangent)) {
  629.       tangent[0] = bez->x1;
  630.       tangent[1] = bez->y1;
  631.       tangent[2] = bez->x3;
  632.       tangent[3] = bez->y3;
  633.    }
  634.    if (null_line(tangent)) {
  635.       tangent[0] = bez->x1;
  636.       tangent[1] = bez->y1;
  637.       tangent[2] = bez->x4;
  638.       tangent[3] = bez->y4;
  639.    }
  640. }
  641.  
  642.  
  643. static INLINE VGfloat bezier_t_at_length(struct bezier *bez,
  644.                                          VGfloat at_length,
  645.                                          VGfloat error)
  646. {
  647.    VGfloat len = bezier_length(bez, error);
  648.    VGfloat t   = 1.0;
  649.    VGfloat last_bigger = 1.;
  650.  
  651.    if (at_length > len || floatsEqual(at_length, len))
  652.       return t;
  653.  
  654.    if (floatIsZero(at_length))
  655.       return 0.f;
  656.  
  657.    t *= 0.5;
  658.    while (1) {
  659.       struct bezier right = *bez;
  660.       struct bezier left;
  661.       VGfloat tmp_len;
  662.       split_left(&right, t, &left);
  663.       tmp_len = bezier_length(&left, error);
  664.       if (ABS(tmp_len - at_length) < error)
  665.          break;
  666.  
  667.       if (tmp_len < at_length) {
  668.          t += (last_bigger - t)*.5;
  669.       } else {
  670.          last_bigger = t;
  671.          t -= t*.5;
  672.       }
  673.    }
  674.    return t;
  675. }
  676.  
  677. void bezier_point_at_length(struct bezier *bez,
  678.                             float length,
  679.                             float *point,
  680.                             float *normal)
  681. {
  682.    /* ~0.000001 seems to be required to pass G2080x tests */
  683.    VGfloat t = bezier_t_at_length(bez, length, 0.000001);
  684.    bezier_point_at(bez, t, point);
  685.    bezier_normal_at(bez, t, normal);
  686.    vector_unit(normal);
  687. }
  688.  
  689. void bezier_point_at_t(struct bezier *bez, float t,
  690.                        float *point, float *normal)
  691. {
  692.    bezier_point_at(bez, t, point);
  693.    bezier_normal_at(bez, t, normal);
  694.    vector_unit(normal);
  695. }
  696.  
  697. void bezier_exact_bounds(const struct bezier *bez,
  698.                          float *bounds/*x/y/width/height*/)
  699. {
  700.    struct polygon *poly = polygon_create(64);
  701.    polygon_vertex_append(poly, bez->x1, bez->y1);
  702.    bezier_add_to_polygon(bez, poly);
  703.    polygon_bounding_rect(poly, bounds);
  704.    polygon_destroy(poly);
  705. }
  706.  
  707.