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