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
