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
split_left(struct bezier * bez,VGfloat t,struct bezier * left)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
split(struct bezier * bez,struct bezier * first_half,struct bezier * second_half)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
bezier_to_polygon(struct bezier * bez)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
bezier_add_to_polygon(const struct bezier * bez,struct polygon * poly)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
add_if_close(struct bezier * bez,VGfloat * length,VGfloat error)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
bezier_length(struct bezier * bez,float error)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
bezier_init(struct bezier * bez,float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4)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
bezier_init2v(struct bezier * bez,float * pt1,float * pt2,float * pt3,float * pt4)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
bezier_transform(struct bezier * bez,struct matrix * matrix)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
bezier_point_at(const struct bezier * bez,float t,float * pt)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
bezier_normal_at(const struct bezier * bez,float t,float * norm)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
good_offset(const struct bezier * b1,const struct bezier * b2,float offset,float threshold)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
shift_line_by_normal(float * l,float offset)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
is_bezier_line(float (* points)[2],int count)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
compute_pt_normal(float * pt1,float * pt2,float * res)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
shift(const struct bezier * orig,struct bezier * shifted,float offset,float threshold)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
make_circle(const struct bezier * b,float offset,struct bezier * o)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
bezier_translate_by_normal(struct bezier * bez,struct bezier * curves,int max_curves,float normal_len,float threshold)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
bezier_bounds(const struct bezier * bez,float * bounds)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
bezier_start_tangent(const struct bezier * bez,float * tangent)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
bezier_t_at_length(struct bezier * bez,VGfloat at_length,VGfloat error)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
bezier_point_at_length(struct bezier * bez,float length,float * point,float * normal)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
bezier_point_at_t(struct bezier * bez,float t,float * point,float * normal)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
bezier_exact_bounds(const struct bezier * bez,float * bounds)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