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    for (float i = spacing; i < 0.99; i += spacing) {
 259       float p1[2],p2[2], d, l;
 260       float normal[2];
 261       bezier_point_at(b1, i, p1);
 262       bezier_point_at(b2, i, p2);
 263       d = (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
 264       if (ABS(d - o2) > max_dist_line)
 265          return Split;
 266
 267       bezier_normal_at(b1, i, normal);
 268       l = ABS(normal[0]) + ABS(normal[1]);
 269       if (l != 0.) {
 270          d = ABS(normal[0]*(p1[1] - p2[1]) - normal[1]*(p1[0] - p2[0]) ) / l;
 271          if (d > max_dist_normal)
 272             return Split;
 273       }
 274    }
 275    return Ok;
 276 }
 277
 278 static INLINE void shift_line_by_normal(float *l, float offset)
 279 {
 280    float norm[4];
 281    float tx, ty;
 282
 283    line_normal(l, norm);
 284    line_normalize(norm);
 285
 286    tx = (norm[2] - norm[0]) * offset;
 287    ty = (norm[3] - norm[1]) * offset;
 288    l[0] += tx; l[1] += ty;
 289    l[2] += tx; l[3] += ty;
 290 }
 291
 292 static INLINE VGboolean is_bezier_line(float (*points)[2], int count)
 293 {
 294    float dx13 = points[2][0] - points[0][0];
 295    float dy13 = points[2][1] - points[0][1];
 296
 297    float dx12 = points[1][0] - points[0][0];
 298    float dy12 = points[1][1] - points[0][1];
 299
 300    debug_assert(count > 2);
 301
 302    if (count == 3) {
 303       return floatsEqual(dx12 * dy13, dx13 * dy12);
 304    } else if (count == 4) {
 305       float dx14 = points[3][0] - points[0][0];
 306       float dy14 = points[3][1] - points[0][1];
 307
 308       return (floatsEqual(dx12 * dy13, dx13 * dy12) &&
 309               floatsEqual(dx12 * dy14, dx14 * dy12));
 310    }
 311
 312    return VG_FALSE;
 313 }
 314
 315 static INLINE void compute_pt_normal(float *pt1, float *pt2, float *res)
 316 {
 317    float line[4];
 318    float normal[4];
 319    line[0] = 0.f; line[1] = 0.f;
 320    line[2] = pt2[0] - pt1[0];
 321    line[3] = pt2[1] - pt1[1];
 322    line_normal(line, normal);
 323    line_normalize(normal);
 324
 325    res[0] = normal[2];
 326    res[1] = normal[3];
 327 }
 328
 329 static enum shift_result shift(const struct bezier *orig,
 330                                struct bezier *shifted,
 331                                float offset, float threshold)
 332 {
 333    int map[4];
 334    VGboolean p1_p2_equal = (orig->x1 == orig->x2 && orig->y1 == orig->y2);
 335    VGboolean p2_p3_equal = (orig->x2 == orig->x3 && orig->y2 == orig->y3);
 336    VGboolean p3_p4_equal = (orig->x3 == orig->x4 && orig->y3 == orig->y4);
 337
 338    float points[4][2];
 339    int np = 0;
 340    float bounds[4];
 341    float points_shifted[4][2];
 342    float prev_normal[2];
 343
 344    points[np][0] = orig->x1;
 345    points[np][1] = orig->y1;
 346    map[0] = 0;
 347    ++np;
 348    if (!p1_p2_equal) {
 349       points[np][0] = orig->x2;
 350       points[np][1] = orig->y2;
 351       ++np;
 352    }
 353    map[1] = np - 1;
 354    if (!p2_p3_equal) {
 355       points[np][0] = orig->x3;
 356       points[np][1] = orig->y3;
 357       ++np;
 358    }
 359    map[2] = np - 1;
 360    if (!p3_p4_equal) {
 361       points[np][0] = orig->x4;
 362       points[np][1] = orig->y4;
 363       ++np;
 364    }
 365    map[3] = np - 1;
 366    if (np == 1)
 367       return Discard;
 368
 369    /* We need to specialcase lines of 3 or 4 points due to numerical
 370       instability in intersection code below */
 371    if (np > 2 && is_bezier_line(points, np)) {
 372       float l[4] = { points[0][0], points[0][1],
 373                      points[np-1][0], points[np-1][1] };
 374       float ctrl1[2], ctrl2[2];
 375       if (floatsEqual(points[0][0], points[np-1][0]) &&
 376           floatsEqual(points[0][1], points[np-1][1]))
 377          return Discard;
 378
 379       shift_line_by_normal(l, offset);
 380       line_point_at(l, 0.33, ctrl1);
 381       line_point_at(l, 0.66, ctrl2);
 382       bezier_init(shifted, l[0], l[1],
 383                   ctrl1[0], ctrl1[1], ctrl2[0], ctrl2[1],
 384                   l[2], l[3]);
 385       return Ok;
 386    }
 387
 388    bezier_bounds(orig, bounds);
 389    if (np == 4 && bounds[2] < .1*offset && bounds[3] < .1*offset) {
 390       float l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +
 391                 (orig->y1 - orig->y2)*(orig->y1 - orig->y1) *
 392                 (orig->x3 - orig->x4)*(orig->x3 - orig->x4) +
 393                 (orig->y3 - orig->y4)*(orig->y3 - orig->y4);
 394       float dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +
 395                   (orig->y1 - orig->y2)*(orig->y3 - orig->y4);
 396       if (dot < 0 && dot*dot < 0.8*l)
 397          /* the points are close and reverse dirction. Approximate the whole
 398             thing by a semi circle */
 399          return Circle;
 400    }
 401
 402    compute_pt_normal(points[0], points[1], prev_normal);
 403
 404    points_shifted[0][0] = points[0][0] + offset * prev_normal[0];
 405    points_shifted[0][1] = points[0][1] + offset * prev_normal[1];
 406
 407    for (int i = 1; i < np - 1; ++i) {
 408       float normal_sum[2], r;
 409       float next_normal[2];
 410       compute_pt_normal(points[i], points[i + 1], next_normal);
 411
 412       normal_sum[0] = prev_normal[0] + next_normal[0];
 413       normal_sum[1] = prev_normal[1] + next_normal[1];
 414
 415       r = 1.0 + prev_normal[0] * next_normal[0]
 416           + prev_normal[1] * next_normal[1];
 417
 418       if (floatsEqual(r + 1, 1)) {
 419          points_shifted[i][0] = points[i][0] + offset * prev_normal[0];
 420          points_shifted[i][1] = points[i][1] + offset * prev_normal[1];
 421       } else {
 422          float k = offset / r;
 423          points_shifted[i][0] = points[i][0] + k * normal_sum[0];
 424          points_shifted[i][1] = points[i][1] + k * normal_sum[1];
 425       }
 426
 427       prev_normal[0] = next_normal[0];
 428       prev_normal[1] = next_normal[1];
 429    }
 430
 431    points_shifted[np - 1][0] = points[np - 1][0] + offset * prev_normal[0];
 432    points_shifted[np - 1][1] = points[np - 1][1] + offset * prev_normal[1];
 433
 434    bezier_init2v(shifted,
 435                  points_shifted[map[0]], points_shifted[map[1]],
 436                  points_shifted[map[2]], points_shifted[map[3]]);
 437
 438    return good_offset(orig, shifted, offset, threshold);
 439 }
 440
 441 static VGboolean make_circle(const struct bezier *b, float offset, struct bezier *o)
 442 {
 443    float normals[3][2];
 444    float dist;
 445    float angles[2];
 446    float sign = 1.f;
 447    int i;
 448    float circle[3][2];
 449
 450    normals[0][0] = b->y2 - b->y1;
 451    normals[0][1] = b->x1 - b->x2;
 452    dist = sqrt(normals[0][0]*normals[0][0] + normals[0][1]*normals[0][1]);
 453    if (floatsEqual(dist + 1, 1.f))
 454       return VG_FALSE;
 455    normals[0][0] /= dist;
 456    normals[0][1] /= dist;
 457
 458    normals[2][0] = b->y4 - b->y3;
 459    normals[2][1] = b->x3 - b->x4;
 460    dist = sqrt(normals[2][0]*normals[2][0] + normals[2][1]*normals[2][1]);
 461    if (floatsEqual(dist + 1, 1.f))
 462       return VG_FALSE;
 463    normals[2][0] /= dist;
 464    normals[2][1] /= dist;
 465
 466    normals[1][0] = b->x1 - b->x2 - b->x3 + b->x4;
 467    normals[1][1] = b->y1 - b->y2 - b->y3 + b->y4;
 468    dist = -1*sqrt(normals[1][0]*normals[1][0] + normals[1][1]*normals[1][1]);
 469    normals[1][0] /= dist;
 470    normals[1][1] /= dist;
 471
 472    for (i = 0; i < 2; ++i) {
 473       float cos_a = normals[i][0]*normals[i+1][0] + normals[i][1]*normals[i+1][1];
 474       if (cos_a > 1.)
 475          cos_a = 1.;
 476       if (cos_a < -1.)
 477          cos_a = -1;
 478       angles[i] = acos(cos_a)/M_PI;
 479    }
 480
 481    if (angles[0] + angles[1] > 1.) {
 482       /* more than 180 degrees */
 483       normals[1][0] = -normals[1][0];
 484       normals[1][1] = -normals[1][1];
 485       angles[0] = 1. - angles[0];
 486       angles[1] = 1. - angles[1];
 487       sign = -1.;
 488    }
 489
 490    circle[0][0] = b->x1 + normals[0][0]*offset;
 491    circle[0][1] = b->y1 + normals[0][1]*offset;
 492
 493    circle[1][0] = 0.5*(b->x1 + b->x4) + normals[1][0]*offset;
 494    circle[1][1] = 0.5*(b->y1 + b->y4) + normals[1][1]*offset;
 495
 496    circle[2][0] = b->x4 + normals[2][0]*offset;
 497    circle[2][1] = b->y4 + normals[2][1]*offset;
 498
 499    for (i = 0; i < 2; ++i) {
 500       float kappa = 2.*KAPPA * sign * offset * angles[i];
 501
 502       o->x1 = circle[i][0];
 503       o->y1 = circle[i][1];
 504       o->x2 = circle[i][0] - normals[i][1]*kappa;
 505       o->y2 = circle[i][1] + normals[i][0]*kappa;
 506       o->x3 = circle[i+1][0] + normals[i+1][1]*kappa;
 507       o->y3 = circle[i+1][1] - normals[i+1][0]*kappa;
 508       o->x4 = circle[i+1][0];
 509       o->y4 = circle[i+1][1];
 510
 511       ++o;
 512    }
 513    return VG_TRUE;
 514 }
 515
 516 int bezier_translate_by_normal(struct bezier *bez,
 517                                struct bezier *curves,
 518                                int max_curves,
 519                                float normal_len,
 520                                float threshold)
 521 {
 522    struct bezier beziers[10];
 523    struct bezier *b, *o;
 524
 525    /* fixme: this should really be floatsEqual */
 526    if (bez->x1 == bez->x2 && bez->x1 == bez->x3 && bez->x1 == bez->x4 &&
 527        bez->y1 == bez->y2 && bez->y1 == bez->y3 && bez->y1 == bez->y4)
 528       return 0;
 529
 530    --max_curves;
 531 redo:
 532    beziers[0] = *bez;
 533    b = beziers;
 534    o = curves;
 535
 536    while (b >= beziers) {
 537       int stack_segments = b - beziers + 1;
 538       enum shift_result res;
 539       if ((stack_segments == 10) || (o - curves == max_curves - stack_segments)) {
 540          threshold *= 1.5;
 541          if (threshold > 2.)
 542             goto give_up;
 543          goto redo;
 544       }
 545       res = shift(b, o, normal_len, threshold);
 546       if (res == Discard) {
 547          --b;
 548       } else if (res == Ok) {
 549          ++o;
 550          --b;
 551          continue;
 552       } else if (res == Circle && max_curves - (o - curves) >= 2) {
 553          /* add semi circle */
 554          if (make_circle(b, normal_len, o))
 555             o += 2;
 556          --b;
 557       } else {
 558          split(b, b+1, b);
 559          ++b;
 560       }
 561    }
 562
 563 give_up:
 564    while (b >= beziers) {
 565       enum shift_result res = shift(b, o, normal_len, threshold);
 566
 567       /* if res isn't Ok or Split then *o is undefined */
 568       if (res == Ok || res == Split)
 569          ++o;
 570
 571       --b;
 572    }
 573
 574    debug_assert(o - curves <= max_curves);
 575    return o - curves;
 576 }
 577
 578 void bezier_bounds(const struct bezier *bez,
 579                    float *bounds/*x/y/width/height*/)
 580 {
 581    float xmin = bez->x1;
 582    float xmax = bez->x1;
 583    float ymin = bez->y1;
 584    float ymax = bez->y1;
 585
 586    if (bez->x2 < xmin)
 587       xmin = bez->x2;
 588    else if (bez->x2 > xmax)
 589       xmax = bez->x2;
 590    if (bez->x3 < xmin)
 591       xmin = bez->x3;
 592    else if (bez->x3 > xmax)
 593       xmax = bez->x3;
 594    if (bez->x4 < xmin)
 595       xmin = bez->x4;
 596    else if (bez->x4 > xmax)
 597       xmax = bez->x4;
 598
 599    if (bez->y2 < ymin)
 600       ymin = bez->y2;
 601    else if (bez->y2 > ymax)
 602       ymax = bez->y2;
 603    if (bez->y3 < ymin)
 604       ymin = bez->y3;
 605    else if (bez->y3 > ymax)
 606       ymax = bez->y3;
 607    if (bez->y4 < ymin)
 608       ymin = bez->y4;
 609    else if (bez->y4 > ymax)
 610       ymax = bez->y4;
 611
 612    bounds[0] = xmin; /* x */
 613    bounds[1] = ymin; /* y */
 614    bounds[2] = xmax - xmin; /* width */
 615    bounds[3] = ymax - ymin; /* height */
 616 }
 617
 618 void bezier_start_tangent(const struct bezier *bez,
 619                           float *tangent)
 620 {
 621    tangent[0] = bez->x1;
 622    tangent[1] = bez->y1;
 623    tangent[2] = bez->x2;
 624    tangent[3] = bez->y2;
 625
 626    if (null_line(tangent)) {
 627       tangent[0] = bez->x1;
 628       tangent[1] = bez->y1;
 629       tangent[2] = bez->x3;
 630       tangent[3] = bez->y3;
 631    }
 632    if (null_line(tangent)) {
 633       tangent[0] = bez->x1;
 634       tangent[1] = bez->y1;
 635       tangent[2] = bez->x4;
 636       tangent[3] = bez->y4;
 637    }
 638 }
 639
 640
 641 static INLINE VGfloat bezier_t_at_length(struct bezier *bez,
 642                                          VGfloat at_length,
 643                                          VGfloat error)
 644 {
 645    VGfloat len = bezier_length(bez, error);
 646    VGfloat t   = 1.0;
 647    VGfloat last_bigger = 1.;
 648
 649    if (at_length > len || floatsEqual(at_length, len))
 650       return t;
 651
 652    if (floatIsZero(at_length))
 653       return 0.f;
 654
 655    t *= 0.5;
 656    while (1) {
 657       struct bezier right = *bez;
 658       struct bezier left;
 659       VGfloat tmp_len;
 660       split_left(&right, t, &left);
 661       tmp_len = bezier_length(&left, error);
 662       if (ABS(tmp_len - at_length) < error)
 663          break;
 664
 665       if (tmp_len < at_length) {
 666          t += (last_bigger - t)*.5;
 667       } else {
 668          last_bigger = t;
 669          t -= t*.5;
 670       }
 671    }
 672    return t;
 673 }
 674
 675 void bezier_point_at_length(struct bezier *bez,
 676                             float length,
 677                             float *point,
 678                             float *normal)
 679 {
 680    /* ~0.000001 seems to be required to pass G2080x tests */
 681    VGfloat t = bezier_t_at_length(bez, length, 0.000001);
 682    bezier_point_at(bez, t, point);
 683    bezier_normal_at(bez, t, normal);
 684    vector_unit(normal);
 685 }
 686
 687 void bezier_point_at_t(struct bezier *bez, float t,
 688                        float *point, float *normal)
 689 {
 690    bezier_point_at(bez, t, point);
 691    bezier_normal_at(bez, t, normal);
 692    vector_unit(normal);
 693 }
 694
 695 void bezier_exact_bounds(const struct bezier *bez,
 696                          float *bounds/*x/y/width/height*/)
 697 {
 698    struct polygon *poly = polygon_create(64);
 699    polygon_vertex_append(poly, bez->x1, bez->y1);
 700    bezier_add_to_polygon(bez, poly);
 701    polygon_bounding_rect(poly, bounds);
 702    polygon_destroy(poly);
 703 }
 704