workbench/libs/mesa/src/gallium/state_trackers/vega/bezier.c

   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