1/*!
2 * \file tessellated_path.cpp
3 * \brief file tessellated_path.cpp
4 *
5 * Copyright 2018 by Intel.
6 *
7 * Contact: kevin.rogovin@gmail.com
8 *
9 * This Source Code Form is subject to the
10 * terms of the Mozilla Public License, v. 2.0.
11 * If a copy of the MPL was not distributed with
12 * this file, You can obtain one at
13 * http://mozilla.org/MPL/2.0/.
14 *
15 * \author Kevin Rogovin <kevin.rogovin@gmail.com>
16 *
17 */
18
19
20#include <list>
21#include <vector>
22#include <algorithm>
23#include <complex>
24#include <fastuidraw/tessellated_path.hpp>
25#include <fastuidraw/partitioned_tessellated_path.hpp>
26#include <fastuidraw/path.hpp>
27#include <fastuidraw/painter/attribute_data/stroked_path.hpp>
28#include <fastuidraw/painter/attribute_data/filled_path.hpp>
29#include <private/util_private.hpp>
30#include <private/bounding_box.hpp>
31#include <private/path_util_private.hpp>
32
33namespace
34{
35 void
36 set_lambda(fastuidraw::TessellatedPath::join &J)
37 {
38 /* Explanation:
39 * We have two curves, a(t) and b(t) with a(1) = b(0)
40 * The point p0 represents the end of a(t) and the
41 * point p1 represents the start of b(t).
42 *
43 * When stroking we have four auxiliary curves:
44 * a0(t) = a(t) + w * a_n(t)
45 * a1(t) = a(t) - w * a_n(t)
46 * b0(t) = b(t) + w * b_n(t)
47 * b1(t) = b(t) - w * b_n(t)
48 * where
49 * w = width of stroking
50 * a_n(t) = enter_join_normal() = J(m_enter_join_unit_vector)
51 * b_n(t) = leaving_join_normal() = J(m_leaving_join_unit_vector)
52 * where
53 * J(x, y) = (-y, x).
54 *
55 * A Bevel join is a triangle that connects
56 * consists of p, A and B where p is a(1) = b(0),
57 * A is one of a0(1) or a1(1) and B is one
58 * of b0(0) or b1(0). Now if we use a0(1) for
59 * A then we will use b0(0) for B because
60 * the normals are generated the same way for
61 * a(t) and b(t). Then, the questions comes
62 * down to, do we wish to add or subtract the
63 * normal. That value is represented by lambda.
64 *
65 * Now to figure out lambda. Let q0 be a point
66 * on a(t) before p = a(1). Then q0 is given by
67 *
68 * q0 = p - s * m_enter_join_unit_vector
69 *
70 * and let q1 be a point on b(t) after p=b(0),
71 *
72 * q1 = p + t * m_leaving_join_unit_vector
73 *
74 * where both s, t are positive. Let
75 *
76 * z = (q0 + q1) / 2
77 *
78 * the point z is then on the inside side of the
79 * join.
80 *
81 * With this in mind, if either of <z - p, enter_join_normal()>
82 * or <z - p, leaving_join_normal() > is positive then we want
83 * to add by -w * n (which means lambda is -1) rather than
84 * w * n (lambda is +1).
85 *
86 * Let
87 * v0 = m_enter_join_unit_vector
88 * v1 = m_leaving_join_unit_vector
89 * n0 = J(v0) = enter_join_normal()
90 * n1 = J(v1) = leaving_join_normal()
91 *
92 * <z - p, n1> = 0.5 * <-s * v0 + t * v1, n1 >
93 * = -0.5 * s * <v0, n1> + 0.5 * t * <v1, n1>
94 * = -0.5 * s * <v0, n1>
95 * = -0.5 * s * <v0, J(v1) >
96 *
97 * and
98 *
99 * <z-p, n0> = 0.5 * < -s * v0 + t * v1, n0 >
100 * = -0.5 * s * <v0, n0> + 0.5 * t * <v1, n0>
101 * = 0.5 * t * <v1, n0>
102 * = 0.5 * t * <v1, J(v0) >
103 * = -0.5 * t * <J(v1), v0>
104 *
105 * (the last line because transpose(J) = -J). Notice that
106 * the sign of <z - p, n1> and the sign of <z - p, n0>
107 * is then the same. Thus,
108 *
109 * lambda = -sign(<v1, n0>)
110 * = -sign(<v1, J(n0)>)
111 * = sign(<J(v1), v0>)
112 */
113 using namespace fastuidraw;
114 J.m_lambda = t_sign(dot(J.leaving_join_normal(),
115 J.m_enter_join_unit_vector));
116 }
117
118 void
119 set_miter_distance(fastuidraw::TessellatedPath::join &J)
120 {
121 /* We compute where the lines
122 * A = { p + L * n0 + s * v0 | s >= 0 }
123 * B = { p + L * n1 - t * v1 | t >= 0 }
124 * where
125 * L = lambda()
126 * v0 = m_enter_join_unit_vector
127 * v1 = m_leaving_join_unit_vector
128 * n0 = J(v0) = enter_join_normal()
129 * n1 = J(v1) = leaving_join_normal()
130 *
131 * The intersect at s = lambda * (1 - <v0, v1>) / <n0, v1>
132 */
133 using namespace fastuidraw;
134
135 float mag_s, v0_dot_v1, n0_dot_v1;
136 n0_dot_v1 = dot(J.m_leaving_join_unit_vector, J.enter_join_normal());
137 v0_dot_v1 = dot(J.m_enter_join_unit_vector, J.m_leaving_join_unit_vector);
138
139 /* We only care about the absolute value of s. Because v0, v1
140 * have unit length and n0 = J(v0), n1 = J(v1) algebra gives
141 *
142 * |(1 - <v0, v1>) / <n0, v1> | = | <n0, v1> / (1.0 + <v0, v1>) |
143 *
144 * This can be realized direcltly or seeing that this is
145 * really a half tangent identity
146 *
147 * tan(t / 2) = (1 - cos(t)) / sin(t)
148 * = sin(t) / (1 + cost(t))
149 *
150 * where t is the angle between v0 and v1, i.e. dot(v0, v1) = cos(t)
151 * and from that n0 is v0 rotated by 0 degrees, up to sign,
152 * sin(t) = dot(n0, v1).
153 */
154 if (v0_dot_v1 > 0.0f)
155 {
156 mag_s = n0_dot_v1 / (1.0f + v0_dot_v1);
157 }
158 else if (t_abs(n0_dot_v1) != 0.0)
159 {
160 mag_s = (v0_dot_v1 - 1.0f) / n0_dot_v1;
161 }
162 else
163 {
164 /* <v0, v1> is negative and <n0, v1> is "zero",
165 * meaning that v0 and v1 are anti-parallel which
166 * means that the miter-join goes on to infinity.
167 */
168 J.m_miter_distance = -1.0f;
169 return;
170 }
171 J.m_miter_distance = t_sqrt(1.0f + mag_s * mag_s);
172 }
173
174 inline
175 void
176 set_join_angle(fastuidraw::TessellatedPath::join &J)
177 {
178 /* n0z represents the start point of the rounded join in the complex plane
179 * as if the join was at the origin, n1z represents the end point of the
180 * rounded join in the complex plane as if the join was at the origin.
181 */
182 std::complex<float> n0z(J.m_lambda * J.enter_join_normal().x(), J.m_lambda * J.enter_join_normal().y());
183 std::complex<float> n1z(J.m_lambda * J.leaving_join_normal().x(), J.m_lambda * J.leaving_join_normal().y());
184
185 /* n1z_times_conj_n0z satisfies:
186 * n1z = n1z_times_conj_n0z * n0z
187 * i.e. it represents the arc-movement from n0z to n1z
188 */
189 std::complex<float> n1z_times_conj_n0z(n1z * std::conj(n0z));
190 J.m_join_angle = fastuidraw::t_atan2(n1z_times_conj_n0z.imag(), n1z_times_conj_n0z.real());
191 }
192
193 inline
194 void
195 set_derived_values(fastuidraw::TessellatedPath::join &J)
196 {
197 set_lambda(J);
198 set_miter_distance(J);
199 set_join_angle(J);
200 }
201
202 class RefinerEdge
203 {
204 public:
205 typedef fastuidraw::PathContour PathContour;
206 typedef PathContour::tessellation_state tessellation_state;
207 typedef fastuidraw::reference_counted_ptr<tessellation_state> tessellation_state_ref;
208 typedef PathContour::interpolator_base interpolator_base;
209 typedef fastuidraw::reference_counted_ptr<const interpolator_base> interpolator_base_ref;
210
211 tessellation_state_ref m_tess_state;
212 interpolator_base_ref m_interpolator;
213 };
214
215 class RefinerContour
216 {
217 public:
218 std::vector<RefinerEdge> m_edges;
219 bool m_is_closed;
220 fastuidraw::vec2 m_start_pt;
221 };
222
223 class RefinerPrivate
224 {
225 public:
226 fastuidraw::reference_counted_ptr<fastuidraw::TessellatedPath> m_path;
227 std::vector<RefinerContour> m_contours;
228 };
229
230 class TessellatedPathBuildingState
231 {
232 public:
233 TessellatedPathBuildingState(void):
234 m_loc(0)
235 {}
236
237 unsigned int m_loc, m_ende;
238 std::list<std::vector<fastuidraw::TessellatedPath::segment> > m_temp;
239 float m_contour_length;
240 std::list<std::vector<fastuidraw::TessellatedPath::segment> >::iterator m_start_contour;
241 };
242
243 class Edge
244 {
245 public:
246 fastuidraw::range_type<unsigned int> m_edge_range;
247 enum fastuidraw::PathEnums::edge_type_t m_edge_type;
248 };
249
250 class TessellatedContour
251 {
252 public:
253 std::vector<Edge> m_edges;
254 bool m_is_closed;
255 fastuidraw::range_type<unsigned int> m_segment_chain_range;
256 };
257
258 class TessellatedPathPrivate
259 {
260 public:
261 TessellatedPathPrivate(unsigned int number_contours,
262 fastuidraw::TessellatedPath::TessellationParams TP);
263
264 explicit
265 TessellatedPathPrivate(const fastuidraw::TessellatedPath &with_arcs,
266 float thresh);
267
268 void
269 start_contour(TessellatedPathBuildingState &b,
270 unsigned int contour,
271 const fastuidraw::vec2 contour_start,
272 unsigned int num_edges_in_contour);
273
274 void
275 add_edge(TessellatedPathBuildingState &b,
276 unsigned int contour, unsigned int edge,
277 std::vector<fastuidraw::TessellatedPath::segment> &segments,
278 float edge_max_distance);
279
280 void
281 end_contour(TessellatedPathBuildingState &b);
282
283 void
284 finalize(TessellatedPathBuildingState &b);
285
286 std::vector<TessellatedContour> m_contours;
287 std::vector<fastuidraw::TessellatedPath::segment> m_segment_data;
288 std::vector<fastuidraw::TessellatedPath::segment_chain> m_segment_chain_data;
289 std::vector<fastuidraw::TessellatedPath::join> m_join_data;
290 std::vector<fastuidraw::TessellatedPath::cap> m_cap_data;
291 fastuidraw::BoundingBox<float> m_bounding_box;
292 fastuidraw::TessellatedPath::TessellationParams m_params;
293 float m_max_distance;
294 bool m_has_arcs;
295 unsigned int m_max_recursion;
296 fastuidraw::reference_counted_ptr<const fastuidraw::StrokedPath> m_stroked;
297 fastuidraw::reference_counted_ptr<const fastuidraw::FilledPath> m_filled;
298 fastuidraw::reference_counted_ptr<const fastuidraw::PartitionedTessellatedPath> m_partitioned;
299 std::vector<fastuidraw::reference_counted_ptr<const fastuidraw::TessellatedPath> > m_linearization;
300 };
301
302 float
303 one_minus_cos(float theta)
304 {
305 /* naively doing 1.0 - cos(theta) will rise to
306 * catostrophic cancellation when theta is small.
307 * Instead, use the trig identity:
308 * cos(t) = 1 - 2sin^2(t / 2)
309 * which gives
310 * 1 - cos(t) = 2sin^2(t / 2)
311 */
312 float sin_half_theta;
313
314 sin_half_theta = fastuidraw::t_sin(theta * 0.5f);
315 return 2.0f * sin_half_theta * sin_half_theta;
316 }
317
318 void
319 union_segment(const fastuidraw::TessellatedPath::segment &S,
320 fastuidraw::BoundingBox<float> &BB)
321 {
322 using namespace fastuidraw;
323
324 BB.union_point(S.m_start_pt);
325 BB.union_point(S.m_end_pt);
326 if (S.m_type == TessellatedPath::arc_segment)
327 {
328 float s, c, l, half_angle;
329 float2x2 mat;
330 vec2 tau;
331
332 half_angle = 0.5f * (S.m_arc_angle.m_end - S.m_arc_angle.m_begin);
333 c = t_cos(S.m_arc_angle.m_begin + half_angle);
334 s = t_sin(S.m_arc_angle.m_begin + half_angle);
335 l = one_minus_cos(half_angle);
336 tau = l * vec2(c, s);
337
338 BB.union_point(S.m_start_pt + tau);
339 BB.union_point(S.m_end_pt + tau);
340 }
341 }
342
343 void
344 compute_local_segment_values(fastuidraw::TessellatedPath::segment &S)
345 {
346 using namespace fastuidraw;
347 if (S.m_type == TessellatedPath::line_segment)
348 {
349 vec2 delta(S.m_end_pt - S.m_start_pt);
350
351 S.m_length = delta.magnitude();
352 if (S.m_length > 0.0f)
353 {
354 delta /= S.m_length;
355 }
356 else
357 {
358 delta = vec2(1.0f, 0.0f);
359 }
360
361 S.m_enter_segment_unit_vector = delta;
362 S.m_leaving_segment_unit_vector = delta;
363 }
364 else
365 {
366 float sgn;
367
368 sgn = (S.m_arc_angle.m_begin < S.m_arc_angle.m_end) ? 1.0f : -1.0f;
369 S.m_length = t_abs(S.m_arc_angle.m_end - S.m_arc_angle.m_begin) * S.m_radius;
370 S.m_enter_segment_unit_vector = sgn * vec2(-t_sin(S.m_arc_angle.m_begin), t_cos(S.m_arc_angle.m_begin));
371 S.m_leaving_segment_unit_vector = sgn * vec2(-t_sin(S.m_arc_angle.m_end), t_cos(S.m_arc_angle.m_end));
372 }
373 }
374
375 void
376 add_tessellated_arc_segment(fastuidraw::vec2 start, fastuidraw::vec2 end,
377 fastuidraw::vec2 center, float radius,
378 fastuidraw::range_type<float> arc_angle,
379 bool continuation_with_predecessor,
380 std::vector<fastuidraw::TessellatedPath::segment> *d)
381 {
382 using namespace fastuidraw;
383
384 float a, da, theta;
385 unsigned int i, cnt;
386 float max_arc(FASTUIDRAW_PI / 4.0f);
387
388 a = t_abs(arc_angle.m_end - arc_angle.m_begin);
389 cnt = 1u + static_cast<unsigned int>(a / max_arc);
390 da = (arc_angle.m_end - arc_angle.m_begin) / static_cast<float>(cnt);
391
392 for (i = 0, theta = arc_angle.m_begin; i < cnt; ++i, theta += da)
393 {
394 TessellatedPath::segment S;
395
396 if (i == 0)
397 {
398 S.m_start_pt = start;
399 S.m_continuation_with_predecessor = continuation_with_predecessor;
400 }
401 else
402 {
403 S.m_start_pt = d->back().m_end_pt;
404 S.m_continuation_with_predecessor = true;
405 }
406
407 if (i + 1 == cnt)
408 {
409 S.m_end_pt = end;
410 }
411 else
412 {
413 S.m_end_pt = center + radius * vec2(t_cos(theta + da), t_sin(theta + da));
414 }
415
416 S.m_center = center;
417 S.m_arc_angle.m_begin = theta;
418 S.m_arc_angle.m_end = theta + da;
419 S.m_radius = radius;
420 S.m_type = TessellatedPath::arc_segment;
421
422 d->push_back(S);
423 }
424 }
425
426 unsigned int
427 recursion_allowed_size(float angle)
428 {
429 using namespace fastuidraw;
430 using namespace detail;
431
432 const unsigned int max_d(MAX_REFINE_RECURSION_LIMIT);
433 const float pi(FASTUIDRAW_PI), two_pi(2.0f * pi);
434 float max_size_f;
435 unsigned int max_size;
436
437 max_size_f = static_cast<float>(1u << max_d) / two_pi;
438 max_size_f *= t_abs(angle);
439
440 max_size = static_cast<unsigned int>(max_size_f);
441 return t_max(max_size, 3u);
442 }
443
444 float
445 add_linearization_of_segment(float thresh,
446 const fastuidraw::TessellatedPath::segment &S,
447 std::vector<fastuidraw::TessellatedPath::segment> *dst)
448 {
449 using namespace fastuidraw;
450 if (S.m_type == TessellatedPath::line_segment)
451 {
452 dst->push_back(S);
453 return 0.0f;
454 }
455
456 float a, da, delta_angle;
457 vec2 prev_pt;
458 unsigned int needed_size;
459 unsigned int max_size_allowed;
460
461 delta_angle = S.m_arc_angle.m_end - S.m_arc_angle.m_begin;
462 max_size_allowed = recursion_allowed_size(delta_angle);
463
464 if (thresh > 0.0f)
465 {
466 needed_size = detail::number_segments_for_tessellation(t_abs(delta_angle), thresh / S.m_radius);
467 }
468 else
469 {
470 needed_size = 3u;
471 }
472
473 if (needed_size > max_size_allowed)
474 {
475 needed_size = max_size_allowed;
476 }
477
478 delta_angle /= static_cast<float>(needed_size);
479 a = S.m_arc_angle.m_begin + delta_angle;
480 da = delta_angle;
481 prev_pt = S.m_start_pt;
482
483 for(unsigned int i = 1; i <= needed_size; ++i, a += delta_angle, da += delta_angle)
484 {
485 TessellatedPath::segment newS;
486 vec2 p;
487
488 if (i == needed_size)
489 {
490 p = S.m_end_pt;
491 }
492 else
493 {
494 float c, s;
495
496 c = S.m_radius * t_cos(a);
497 s = S.m_radius * t_sin(a);
498 p = S.m_center + vec2(c, s);
499 }
500
501 newS.m_type = TessellatedPath::line_segment;
502 newS.m_start_pt = prev_pt;
503 newS.m_end_pt = p;
504 newS.m_center = vec2(0.0f, 0.0f);
505 newS.m_arc_angle = range_type<float>(0.0f, 0.0f);
506 newS.m_radius = 0;
507 newS.m_continuation_with_predecessor = false;
508
509 dst->push_back(newS);
510 prev_pt = p;
511 }
512
513 const float pi(FASTUIDRAW_PI);
514 float error, eff(t_min(pi, t_abs(0.5f * delta_angle)));
515
516 error = S.m_radius * one_minus_cos(eff);
517 return error;
518 }
519
520 bool
521 intersection_point_in_arc(const fastuidraw::TessellatedPath::segment &src,
522 fastuidraw::vec2 pt, float *out_arc_angle)
523 {
524 using namespace fastuidraw;
525 const vec2 &pt0(src.m_start_pt);
526 const vec2 &pt1(src.m_end_pt);
527
528 vec2 v0(pt0 - src.m_center), v1(pt1 - src.m_center);
529 vec2 n0(-v0.y(), v0.x()), n1(-v1.y(), v1.x());
530
531 /* The arc's radial edges coincide with the edges of the
532 * triangle [m_center, m_pt0, m_pt1], as such we can use the
533 * edges that use m_center define the clipping planes to
534 * check if an intersection point is inside the arc.
535 */
536 pt -= src.m_center;
537 if ((dot(n0, pt) > 0.0) == (dot(n0, pt1 - src.m_center) > 0.0)
538 && (dot(n1, pt) > 0.0) == (dot(n1, pt0 - src.m_center) > 0.0))
539 {
540 /* pt is within the arc; compute the angle */
541 float theta;
542
543 theta = t_atan2(pt.y(), pt.x());
544 if (theta < t_min(src.m_arc_angle.m_begin, src.m_arc_angle.m_end))
545 {
546 theta += 2.0f * static_cast<float>(FASTUIDRAW_PI);
547 }
548 else if (theta > t_max(src.m_arc_angle.m_begin, src.m_arc_angle.m_end))
549 {
550 theta -= 2.0f * static_cast<float>(FASTUIDRAW_PI);
551 }
552
553 FASTUIDRAWassert(theta >= t_min(src.m_arc_angle.m_begin, src.m_arc_angle.m_end));
554 FASTUIDRAWassert(theta <= t_max(src.m_arc_angle.m_begin, src.m_arc_angle.m_end));
555 *out_arc_angle = theta;
556
557 return true;
558 }
559 return false;
560 }
561
562 enum fastuidraw::TessellatedPath::split_t
563 compute_segment_split(int splitting_coordinate,
564 const fastuidraw::TessellatedPath::segment &src,
565 float split_value,
566 fastuidraw::TessellatedPath::segment *dst_before,
567 fastuidraw::TessellatedPath::segment *dst_after)
568 {
569 using namespace fastuidraw;
570 float s, t, mid_angle;
571 vec2 p, mid_unit_vector;
572 vecN<TessellatedPath::segment*, 2> dst;
573 enum TessellatedPath::split_t return_value;
574
575 FASTUIDRAWassert(dst_before);
576 FASTUIDRAWassert(dst_after);
577 FASTUIDRAWassert(splitting_coordinate == 0 || splitting_coordinate == 1);
578
579 if (src.m_start_pt[splitting_coordinate] <= split_value
580 && src.m_end_pt[splitting_coordinate] <= split_value)
581 {
582 return TessellatedPath::segment_completey_before_split;
583 }
584
585 if (src.m_start_pt[splitting_coordinate] >= split_value
586 && src.m_end_pt[splitting_coordinate] >= split_value)
587 {
588 return TessellatedPath::segment_completey_after_split;
589 }
590
591 if (src.m_type == TessellatedPath::line_segment)
592 {
593 float v0, v1;
594
595 v0 = src.m_start_pt[splitting_coordinate];
596 v1 = src.m_end_pt[splitting_coordinate];
597 t = (split_value - v0) / (v1 - v0);
598 s = 1.0f - t;
599
600 p[splitting_coordinate] = split_value;
601 p[1 - splitting_coordinate] = s * src.m_start_pt[1 - splitting_coordinate]
602 + t * src.m_end_pt[1 - splitting_coordinate];
603
604 mid_unit_vector = src.m_enter_segment_unit_vector;
605
606 /* strictly speaking this is non-sense, but lets silence
607 * any writes with uninitialized data here.
608 */
609 mid_angle = 0.5f * (src.m_arc_angle.m_begin + src.m_arc_angle.m_end);
610 }
611 else
612 {
613 FASTUIDRAWassert(src.m_type == TessellatedPath::arc_segment);
614
615 /* compute t, s, p, mid_normal; We are gauranteed
616 * that the arc is monotonic, thus the splitting will
617 * split it into at most two pieces. In addition, because
618 * it is monotonic, we know it will split it in exactly
619 * two pieces.
620 */
621 float radical, d;
622 fastuidraw::vec2 test_pt;
623
624 d = split_value - src.m_center[splitting_coordinate];
625 radical = src.m_radius * src.m_radius - d * d;
626
627 FASTUIDRAWassert(radical > 0.0f);
628 radical = t_sqrt(radical);
629
630 test_pt[splitting_coordinate] = split_value;
631 test_pt[1 - splitting_coordinate] = src.m_center[1 - splitting_coordinate] - radical;
632
633 if (!intersection_point_in_arc(src, test_pt, &mid_angle))
634 {
635 bool result;
636
637 test_pt[1 - splitting_coordinate] = src.m_center[1 - splitting_coordinate] + radical;
638 result = intersection_point_in_arc(src, test_pt, &mid_angle);
639
640 FASTUIDRAWassert(result);
641 FASTUIDRAWunused(result);
642 }
643
644 p = test_pt;
645 t = (mid_angle - src.m_arc_angle.m_begin) / (src.m_arc_angle.m_end - src.m_arc_angle.m_begin);
646 s = 1.0f - t;
647
648 mid_unit_vector.x() = -src.m_radius * fastuidraw::t_sin(mid_angle);
649 mid_unit_vector.y() = +src.m_radius * fastuidraw::t_cos(mid_angle);
650 if (src.m_arc_angle.m_begin > src.m_arc_angle.m_end)
651 {
652 mid_unit_vector *= -1.0f;
653 }
654 }
655
656 /* we are going to write the sub-segment corrensponding to [0, t]
657 * to dst[0] and the sub-segment corrensponding to [t, 1] to
658 * dst[1], so we set the pointer values dependening on which
659 * side of the split the starting point is on.
660 */
661 if (src.m_start_pt[splitting_coordinate] < split_value)
662 {
663 return_value = TessellatedPath::segment_split_start_before;
664 dst[0] = dst_before;
665 dst[1] = dst_after;
666 }
667 else
668 {
669 return_value = TessellatedPath::segment_split_start_after;
670 dst[0] = dst_after;
671 dst[1] = dst_before;
672 }
673
674 dst[0]->m_type = src.m_type;
675 dst[0]->m_start_pt = src.m_start_pt;
676 dst[0]->m_end_pt = p;
677 dst[0]->m_center = src.m_center;
678 dst[0]->m_arc_angle.m_begin = src.m_arc_angle.m_begin;
679 dst[0]->m_arc_angle.m_end = mid_angle;
680 dst[0]->m_radius = src.m_radius;
681 dst[0]->m_length = t * src.m_length;
682 dst[0]->m_distance_from_edge_start = src.m_distance_from_edge_start;
683 dst[0]->m_distance_from_contour_start = src.m_distance_from_contour_start;
684 dst[0]->m_edge_length = src.m_edge_length;
685 dst[0]->m_contour_length = src.m_contour_length;
686 dst[0]->m_enter_segment_unit_vector = src.m_enter_segment_unit_vector;
687 dst[0]->m_leaving_segment_unit_vector = mid_unit_vector;
688 dst[0]->m_continuation_with_predecessor = src.m_continuation_with_predecessor;
689 dst[0]->m_contour_id = src.m_contour_id;
690 dst[0]->m_edge_id = src.m_edge_id;
691 dst[0]->m_first_segment_of_edge = src.m_first_segment_of_edge;
692 dst[0]->m_last_segment_of_edge = false;
693
694 dst[1]->m_type = src.m_type;
695 dst[1]->m_start_pt = p;
696 dst[1]->m_end_pt = src.m_end_pt;
697 dst[1]->m_center = src.m_center;
698 dst[1]->m_arc_angle.m_begin = mid_angle;
699 dst[1]->m_arc_angle.m_end = src.m_arc_angle.m_end;
700 dst[1]->m_radius = src.m_radius;
701 dst[1]->m_length = s * src.m_length;
702 dst[1]->m_distance_from_edge_start = dst[0]->m_distance_from_edge_start + dst[0]->m_length;
703 dst[1]->m_distance_from_contour_start = dst[0]->m_distance_from_contour_start + dst[0]->m_length;
704 dst[1]->m_edge_length = src.m_edge_length;
705 dst[1]->m_contour_length = src.m_contour_length;
706 dst[1]->m_enter_segment_unit_vector = mid_unit_vector;
707 dst[1]->m_leaving_segment_unit_vector = src.m_leaving_segment_unit_vector;
708 dst[1]->m_continuation_with_predecessor = true;
709 dst[1]->m_contour_id = src.m_contour_id;
710 dst[1]->m_edge_id = src.m_edge_id;
711 dst[1]->m_first_segment_of_edge = false;
712 dst[1]->m_last_segment_of_edge = src.m_last_segment_of_edge;
713
714 return return_value;
715 }
716
717}
718
719//////////////////////////////////////////////
720// TessellatedPathPrivate methods
721TessellatedPathPrivate::
722TessellatedPathPrivate(unsigned int num_contours,
723 fastuidraw::TessellatedPath::TessellationParams TP):
724 m_contours(num_contours),
725 m_params(TP),
726 m_max_distance(0.0f),
727 m_has_arcs(false),
728 m_max_recursion(0u)
729{
730}
731
732TessellatedPathPrivate::
733TessellatedPathPrivate(const fastuidraw::TessellatedPath &with_arcs,
734 float thresh):
735 m_contours(with_arcs.number_contours()),
736 m_params(with_arcs.tessellation_parameters()),
737 m_max_distance(with_arcs.max_distance()),
738 m_has_arcs(false),
739 m_max_recursion(with_arcs.max_recursion())
740{
741 using namespace fastuidraw;
742
743 FASTUIDRAWassert(with_arcs.has_arcs());
744
745 TessellatedPathBuildingState builder;
746
747 for (unsigned int C = 0, endC = with_arcs.number_contours(); C < endC; ++C)
748 {
749 start_contour(builder, C,
750 with_arcs.contour_segment_data(C).front().m_start_pt,
751 with_arcs.number_edges(C));
752 for (unsigned int E = 0, endE = with_arcs.number_edges(C); E < endE; ++E)
753 {
754 float d(m_max_distance);
755 std::vector<TessellatedPath::segment> tmp;
756 c_array<const TessellatedPath::segment> segs;
757
758 segs = with_arcs.edge_segment_data(C, E);
759 for (const TessellatedPath::segment &S : segs)
760 {
761 float f;
762 f = add_linearization_of_segment(thresh, S, &tmp);
763 d = t_max(f, d);
764 }
765 add_edge(builder, C, E, tmp, d);
766 }
767
768 end_contour(builder);
769 m_contours[C].m_is_closed = with_arcs.contour_closed(C);
770 }
771 finalize(builder);
772}
773
774void
775TessellatedPathPrivate::
776start_contour(TessellatedPathBuildingState &b,
777 unsigned int contour,
778 const fastuidraw::vec2 contour_start,
779 unsigned int num_edges)
780{
781 FASTUIDRAWassert(contour < m_contours.size());
782
783 b.m_contour_length = 0.0f;
784 b.m_ende = num_edges;
785 m_contours[contour].m_edges.resize(num_edges);
786
787 if (num_edges == 0)
788 {
789 /* If a contour has no edges, that indicates it is just
790 * a dot; that dot still needs to be realized and given
791 * room.
792 */
793 std::vector<fastuidraw::TessellatedPath::segment> tmp(1);
794
795 m_contours[contour].m_edges.resize(1);
796 tmp[0].m_type = fastuidraw::TessellatedPath::line_segment;
797 tmp[0].m_start_pt = tmp[0].m_end_pt = contour_start;
798 tmp[0].m_length = 0.0f;
799 add_edge(b, contour, 0, tmp, 0.0f);
800 }
801}
802
803void
804TessellatedPathPrivate::
805add_edge(TessellatedPathBuildingState &builder,
806 unsigned int o, unsigned int e,
807 std::vector<fastuidraw::TessellatedPath::segment> &work_room,
808 float edge_max_distance)
809{
810 using namespace fastuidraw;
811
812 unsigned int needed;
813
814 needed = work_room.size();
815 m_contours[o].m_edges[e].m_edge_range = range_type<unsigned int>(builder.m_loc, builder.m_loc + needed);
816 builder.m_loc += needed;
817
818 FASTUIDRAWassert(needed > 0u);
819 m_max_distance = t_max(m_max_distance, edge_max_distance);
820
821 for(unsigned int n = 0; n < work_room.size(); ++n)
822 {
823 m_has_arcs = m_has_arcs || (work_room[n].m_type == TessellatedPath::arc_segment);
824 union_segment(work_room[n], m_bounding_box);
825 compute_local_segment_values(work_room[n]);
826
827 if (n != 0)
828 {
829 work_room[n].m_distance_from_edge_start =
830 work_room[n - 1].m_distance_from_edge_start + work_room[n - 1].m_length;
831 }
832 else
833 {
834 work_room[n].m_distance_from_edge_start = 0.0f;
835 }
836
837 work_room[n].m_distance_from_contour_start = builder.m_contour_length;
838 builder.m_contour_length += work_room[n].m_length;
839 }
840
841 for(unsigned int n = 0; n < needed; ++n)
842 {
843 work_room[n].m_edge_length = work_room[needed - 1].m_distance_from_edge_start
844 + work_room[needed - 1].m_length;
845 }
846
847 /* append the data to temp and clear work_room for the next edge */
848 std::list<std::vector<TessellatedPath::segment> >::iterator t;
849 t = builder.m_temp.insert(builder.m_temp.end(), std::vector<TessellatedPath::segment>());
850 t->swap(work_room);
851
852 if (e == 0)
853 {
854 builder.m_start_contour = t;
855 }
856}
857
858void
859TessellatedPathPrivate::
860end_contour(TessellatedPathBuildingState &builder)
861{
862 using namespace fastuidraw;
863
864 if (builder.m_start_contour == builder.m_temp.end())
865 {
866 return;
867 }
868
869 for(std::list<std::vector<TessellatedPath::segment> >::iterator
870 t = builder.m_start_contour, endt = builder.m_temp.end(); t != endt; ++t)
871 {
872 for(unsigned int e = 0, ende = t->size(); e < ende; ++e)
873 {
874 TessellatedPath::segment &S(t->operator[](e));
875 S.m_contour_length = builder.m_contour_length;
876 }
877 }
878}
879
880void
881TessellatedPathPrivate::
882finalize(TessellatedPathBuildingState &b)
883{
884 using namespace fastuidraw;
885
886 unsigned int total_needed;
887
888 total_needed = m_contours.back().m_edges.back().m_edge_range.m_end;
889 m_segment_data.reserve(total_needed);
890 for(auto iter = b.m_temp.begin(), end_iter = b.m_temp.end(); iter != end_iter; ++iter)
891 {
892 std::copy(iter->begin(), iter->end(), std::back_inserter(m_segment_data));
893 }
894 FASTUIDRAWassert(total_needed == m_segment_data.size());
895
896 /* set the edge/contour properties of each segment */
897 for (unsigned int C = 0, endC = m_contours.size(); C < endC; ++C)
898 {
899 TessellatedContour &contour(m_contours[C]);
900 TessellatedPath::segment_chain chain;
901 const TessellatedPath::segment *prev_segment(nullptr);
902
903 chain.m_prev_to_start = nullptr;
904 contour.m_segment_chain_range.m_begin = m_segment_chain_data.size();
905 if (contour.m_edges.empty())
906 {
907 contour.m_segment_chain_range.m_end = m_segment_chain_data.size();
908 continue;
909 }
910
911 if (contour.m_is_closed)
912 {
913 prev_segment = &m_segment_data[contour.m_edges.back().m_edge_range.m_end - 1];
914 }
915 else
916 {
917 TessellatedPath::cap cap;
918 const TessellatedPath::segment *start, *end;
919
920 start = &m_segment_data[contour.m_edges.front().m_edge_range.m_begin];
921 end = &m_segment_data[contour.m_edges.back().m_edge_range.m_end - 1];
922
923 cap.m_contour_id = C;
924 cap.m_contour_length = start->m_contour_length;
925
926 cap.m_position = start->m_start_pt;
927 cap.m_unit_vector = -start->m_enter_segment_unit_vector;
928 cap.m_edge_length = start->m_edge_length;
929 cap.m_distance_from_edge_start = 0.0f;
930 cap.m_distance_from_contour_start = 0.0f;
931 cap.m_is_starting_cap = true;
932 m_cap_data.push_back(cap);
933
934 cap.m_position = end->m_end_pt;
935 cap.m_unit_vector = end->m_leaving_segment_unit_vector;
936 cap.m_edge_length = end->m_edge_length;
937 cap.m_distance_from_edge_start = end->m_edge_length;
938 cap.m_distance_from_contour_start = cap.m_contour_length;
939 cap.m_is_starting_cap = false;
940 m_cap_data.push_back(cap);
941 }
942
943 for (unsigned int E = 0, endE = contour.m_edges.size(); E < endE; ++E)
944 {
945 const Edge &edge(contour.m_edges[E]);
946 c_array<TessellatedPath::segment> edge_segs;
947
948 edge_segs = make_c_array(m_segment_data).sub_array(edge.m_edge_range);
949 FASTUIDRAWassert(!edge_segs.empty());
950
951 if (prev_segment && edge.m_edge_type == fastuidraw::PathEnums::starts_new_edge)
952 {
953 TessellatedPath::join J;
954
955 J.m_position = prev_segment->m_end_pt;
956 J.m_enter_join_unit_vector = prev_segment->m_leaving_segment_unit_vector;
957 J.m_leaving_join_unit_vector = edge_segs.front().m_enter_segment_unit_vector;
958 J.m_contour_id = C;
959 J.m_edge_into_join_id = (E == 0) ? (endE - 1) : (E + 1);
960 J.m_edge_leaving_join_id = E;
961 J.m_distance_from_previous_join = prev_segment->m_distance_from_edge_start + prev_segment->m_length;
962 J.m_distance_from_contour_start = prev_segment->m_distance_from_contour_start + prev_segment->m_length;
963 J.m_contour_length = edge_segs.front().m_contour_length;
964 set_derived_values(J);
965 m_join_data.push_back(J);
966 }
967
968 chain.m_segments = edge_segs;
969 chain.m_prev_to_start = (edge.m_edge_type == PathEnums::starts_new_edge) ?
970 nullptr:
971 prev_segment;
972 m_segment_chain_data.push_back(chain);
973
974 for (TessellatedPath::segment &S : edge_segs)
975 {
976 S.m_contour_id = C;
977 S.m_edge_id = E;
978 S.m_first_segment_of_edge = false;
979 S.m_last_segment_of_edge = false;
980 prev_segment = &S;
981 }
982 edge_segs.front().m_first_segment_of_edge = true;
983 edge_segs.back().m_last_segment_of_edge = true;
984 }
985 contour.m_segment_chain_range.m_end = m_segment_chain_data.size();
986 }
987}
988
989//////////////////////////////////////////
990// fastuidraw::TessellatedPath::segment methods
991enum fastuidraw::TessellatedPath::split_t
992fastuidraw::TessellatedPath::segment::
993compute_split_x(float x_split,
994 segment *dst_before_split,
995 segment *dst_after_split) const
996{
997 return compute_segment_split(0, *this, x_split, dst_before_split, dst_after_split);
998}
999
1000enum fastuidraw::TessellatedPath::split_t
1001fastuidraw::TessellatedPath::segment::
1002compute_split_y(float y_split,
1003 segment *dst_before_split,
1004 segment *dst_after_split) const
1005{
1006 return compute_segment_split(1, *this, y_split, dst_before_split, dst_after_split);
1007}
1008
1009enum fastuidraw::TessellatedPath::split_t
1010fastuidraw::TessellatedPath::segment::
1011compute_split(float split,
1012 segment *dst_before_split,
1013 segment *dst_after_split,
1014 int splitting_coordinate) const
1015{
1016 return compute_segment_split(splitting_coordinate, *this, split, dst_before_split, dst_after_split);
1017}
1018
1019void
1020fastuidraw::TessellatedPath::segment::
1021split_segment(float t,
1022 segment *dst_0_t,
1023 segment *dst_t_1) const
1024{
1025 float s, mid_angle;
1026 vec2 p, mid_unit_vector;
1027
1028 s = 1.0f - t;
1029 mid_angle = s * m_arc_angle.m_begin + t * m_arc_angle.m_end;
1030 if (m_type == line_segment)
1031 {
1032 p = s * m_start_pt + t * m_end_pt;
1033 mid_unit_vector = m_enter_segment_unit_vector;
1034 }
1035 else
1036 {
1037 float ca, sa;
1038
1039 ca = t_cos(mid_angle);
1040 sa = t_sin(mid_angle);
1041 p = m_center + m_radius * vec2(ca, sa);
1042 }
1043
1044 dst_0_t->m_type = m_type;
1045 dst_0_t->m_start_pt = m_start_pt;
1046 dst_0_t->m_end_pt = p;
1047 dst_0_t->m_center = m_center;
1048 dst_0_t->m_arc_angle.m_begin = m_arc_angle.m_begin;
1049 dst_0_t->m_arc_angle.m_end = mid_angle;
1050 dst_0_t->m_radius = m_radius;
1051 dst_0_t->m_length = t * m_length;
1052 dst_0_t->m_distance_from_edge_start = m_distance_from_edge_start;
1053 dst_0_t->m_distance_from_contour_start = m_distance_from_contour_start;
1054 dst_0_t->m_edge_length = m_edge_length;
1055 dst_0_t->m_contour_length = m_contour_length;
1056 dst_0_t->m_enter_segment_unit_vector = m_enter_segment_unit_vector;
1057 dst_0_t->m_leaving_segment_unit_vector = mid_unit_vector;
1058 dst_0_t->m_continuation_with_predecessor = m_continuation_with_predecessor;
1059 dst_0_t->m_contour_id = m_contour_id;
1060 dst_0_t->m_edge_id = m_edge_id;
1061 dst_0_t->m_first_segment_of_edge = m_first_segment_of_edge;
1062 dst_0_t->m_last_segment_of_edge = false;
1063
1064 dst_t_1->m_type = m_type;
1065 dst_t_1->m_start_pt = p;
1066 dst_t_1->m_end_pt = m_end_pt;
1067 dst_t_1->m_center = m_center;
1068 dst_t_1->m_arc_angle.m_begin = mid_angle;
1069 dst_t_1->m_arc_angle.m_end = m_arc_angle.m_end;
1070 dst_t_1->m_radius = m_radius;
1071 dst_t_1->m_length = s * m_length;
1072 dst_t_1->m_distance_from_edge_start = dst_0_t->m_distance_from_edge_start + dst_0_t->m_length;
1073 dst_t_1->m_distance_from_contour_start = dst_0_t->m_distance_from_contour_start + dst_0_t->m_length;
1074 dst_t_1->m_edge_length = m_edge_length;
1075 dst_t_1->m_contour_length = m_contour_length;
1076 dst_t_1->m_enter_segment_unit_vector = mid_unit_vector;
1077 dst_t_1->m_leaving_segment_unit_vector = m_leaving_segment_unit_vector;
1078 dst_t_1->m_continuation_with_predecessor = true;
1079 dst_t_1->m_contour_id = m_contour_id;
1080 dst_t_1->m_edge_id = m_edge_id;
1081 dst_t_1->m_first_segment_of_edge = false;
1082 dst_t_1->m_last_segment_of_edge = m_last_segment_of_edge;
1083}
1084
1085///////////////////////////////////////////
1086// fastuidraw::TessellatedPath::join methods
1087fastuidraw::TessellatedPath::join::
1088join(const segment &into_join, const segment &from_join):
1089 m_position(into_join.m_end_pt),
1090 m_enter_join_unit_vector(into_join.m_leaving_segment_unit_vector),
1091 m_leaving_join_unit_vector(from_join.m_enter_segment_unit_vector),
1092 m_distance_from_previous_join(into_join.m_distance_from_edge_start + into_join.m_length),
1093 m_distance_from_contour_start(into_join.m_distance_from_contour_start + into_join.m_length),
1094 m_contour_length(into_join.m_contour_length),
1095 m_contour_id(into_join.m_contour_id),
1096 m_edge_into_join_id(into_join.m_edge_id),
1097 m_edge_leaving_join_id(from_join.m_edge_id)
1098{
1099 set_derived_values(*this);
1100}
1101
1102///////////////////////////////////////////
1103// fastuidraw::TessellatedPath::cap methods
1104fastuidraw::TessellatedPath::cap::
1105cap(const segment &seg, bool is_start_cap):
1106 m_position(is_start_cap ? seg.m_start_pt : seg.m_end_pt),
1107 m_unit_vector(is_start_cap ? -seg.m_enter_segment_unit_vector : seg.m_leaving_segment_unit_vector),
1108 m_contour_length(seg.m_contour_length),
1109 m_edge_length(seg.m_edge_length),
1110 m_is_starting_cap(is_start_cap),
1111 m_contour_id(seg.m_contour_id)
1112{
1113}
1114
1115//////////////////////////////////////////////////////////
1116// fastuidraw::TessellatedPath::SegmentStorage methods
1117void
1118fastuidraw::TessellatedPath::SegmentStorage::
1119add_line_segment(vec2 start, vec2 end)
1120{
1121 segment S;
1122 std::vector<segment> *d;
1123
1124 d = static_cast<std::vector<segment>*>(m_d);
1125 S.m_start_pt = start;
1126 S.m_end_pt = end;
1127 S.m_radius = 0;
1128 S.m_center = vec2(0.0f, 0.0f);
1129 S.m_arc_angle = range_type<float>(0.0f, 0.0f);
1130 S.m_type = line_segment;
1131 S.m_continuation_with_predecessor = false;
1132
1133 d->push_back(S);
1134}
1135
1136void
1137fastuidraw::TessellatedPath::SegmentStorage::
1138add_arc_segment(vec2 start, vec2 end,
1139 vec2 center, float radius,
1140 range_type<float> arc_angle)
1141{
1142 std::vector<segment> *d;
1143 d = static_cast<std::vector<segment>*>(m_d);
1144
1145 /* tessellate the segment so that each sub-segment is monotonic in both
1146 * x and y coordinates. We are relying very closely on the implementation
1147 * of Tessellator::arc_tessellation_worker() in Path.cpp where m_begin
1148 * is ALWAYS computed by atan2 and that it is possible that one of
1149 * m_begin or m_end has 2 * PI added to it.
1150 */
1151 const float crit_angles[] =
1152 {
1153 -0.5f * FASTUIDRAW_PI,
1154 0.0f,
1155 0.5f * FASTUIDRAW_PI,
1156 FASTUIDRAW_PI,
1157 1.5f * FASTUIDRAW_PI,
1158 2.0f * FASTUIDRAW_PI,
1159 2.5f * FASTUIDRAW_PI,
1160 };
1161
1162 const vec2 crit_pts[] =
1163 {
1164 vec2(+0.0f, -1.0f), // -PI/2
1165 vec2(+1.0f, +0.0f), // 0
1166 vec2(+0.0f, +1.0f), // +PI/2
1167 vec2(-1.0f, +0.0f), // +PI
1168 vec2(+0.0f, -1.0f), // 3PI/2
1169 vec2(+1.0f, +0.0f), // 2PI
1170 vec2(+0.0f, +1.0f), // 5PI/2
1171 };
1172
1173 float prev_angle(arc_angle.m_begin);
1174 vec2 prev_pt(start);
1175 bool continuation_with_predessor(false);
1176
1177 for (unsigned int i = 0, reverse_i = 6; i < 7; ++i, --reverse_i)
1178 {
1179 unsigned int K;
1180 bool should_split;
1181
1182 if (arc_angle.m_begin < arc_angle.m_end)
1183 {
1184 K = i;
1185 should_split = (arc_angle.m_begin < crit_angles[K]
1186 && crit_angles[K] < arc_angle.m_end);
1187 }
1188 else
1189 {
1190 K = reverse_i;
1191 should_split = (arc_angle.m_end < crit_angles[K]
1192 && crit_angles[K] < arc_angle.m_begin);
1193 }
1194
1195 if (should_split)
1196 {
1197 vec2 end_pt;
1198
1199 end_pt = center + radius * crit_pts[K];
1200 add_tessellated_arc_segment(prev_pt, end_pt, center, radius,
1201 range_type<float>(prev_angle, crit_angles[K]),
1202 continuation_with_predessor, d);
1203 prev_pt = end_pt;
1204 prev_angle = crit_angles[K];
1205 continuation_with_predessor = true;
1206 }
1207 }
1208
1209 add_tessellated_arc_segment(prev_pt, end, center, radius,
1210 range_type<float>(prev_angle, arc_angle.m_end),
1211 continuation_with_predessor, d);
1212}
1213
1214///////////////////////////////////////////////
1215// fastuidraw::TessellatedPath::Refiner methods
1216fastuidraw::TessellatedPath::Refiner::
1217Refiner(fastuidraw::TessellatedPath *p, const Path &input)
1218{
1219 RefinerPrivate *d;
1220 m_d = d = FASTUIDRAWnew RefinerPrivate();
1221 d->m_path = p;
1222 d->m_contours.resize(input.number_contours());
1223 for (unsigned int i = 0, endi = input.number_contours(); i < endi; ++i)
1224 {
1225 d->m_contours[i].m_is_closed = input.contour(i)->closed();
1226 }
1227}
1228
1229fastuidraw::TessellatedPath::Refiner::
1230~Refiner()
1231{
1232 RefinerPrivate *d;
1233 d = static_cast<RefinerPrivate*>(m_d);
1234 FASTUIDRAWdelete(d);
1235}
1236
1237fastuidraw::reference_counted_ptr<fastuidraw::TessellatedPath>
1238fastuidraw::TessellatedPath::Refiner::
1239tessellated_path(void) const
1240{
1241 RefinerPrivate *d;
1242 d = static_cast<RefinerPrivate*>(m_d);
1243 return d->m_path;
1244}
1245
1246void
1247fastuidraw::TessellatedPath::Refiner::
1248refine_tessellation(float max_distance,
1249 unsigned int additional_recursion_count)
1250{
1251 RefinerPrivate *d;
1252 d = static_cast<RefinerPrivate*>(m_d);
1253
1254 if (d->m_path->max_distance() > max_distance)
1255 {
1256 d->m_path = FASTUIDRAWnew TessellatedPath(this, max_distance, additional_recursion_count);
1257 }
1258}
1259
1260//////////////////////////////////////
1261// fastuidraw::TessellatedPath methods
1262fastuidraw::TessellatedPath::
1263TessellatedPath(Refiner *p, float max_distance,
1264 unsigned int additional_recursion_count)
1265{
1266 RefinerPrivate *ref_d;
1267 TessellatedPathPrivate *d;
1268
1269 ref_d = static_cast<RefinerPrivate*>(p->m_d);
1270
1271 TessellationParams params;
1272 params.m_max_distance = max_distance;
1273 params.m_max_recursion = ref_d->m_path->max_recursion() + additional_recursion_count;
1274
1275 m_d = d = FASTUIDRAWnew TessellatedPathPrivate(ref_d->m_contours.size(), params);
1276 if (ref_d->m_contours.empty())
1277 {
1278 return;
1279 }
1280
1281 std::vector<segment> work_room;
1282 TessellatedPathBuildingState builder;
1283 for(unsigned int o = 0, endo = ref_d->m_contours.size(); o < endo; ++o)
1284 {
1285 const RefinerContour &contour(ref_d->m_contours[o]);
1286 d->start_contour(builder, o, contour.m_start_pt, contour.m_edges.size());
1287
1288 for(unsigned int e = 0, ende = contour.m_edges.size(); e < ende; ++e)
1289 {
1290 const RefinerEdge edge(contour.m_edges[e]);
1291 SegmentStorage segment_storage;
1292 float tmp;
1293
1294 FASTUIDRAWassert(work_room.empty());
1295 segment_storage.m_d = &work_room;
1296
1297 if (edge.m_tess_state)
1298 {
1299 edge.m_tess_state->resume_tessellation(d->m_params, &segment_storage, &tmp);
1300 d->m_max_recursion = t_max(d->m_max_recursion, edge.m_tess_state->recursion_depth());
1301 }
1302 else
1303 {
1304 edge.m_interpolator->produce_tessellation(d->m_params, &segment_storage, &tmp);
1305 }
1306
1307 d->add_edge(builder, o, e, work_room, tmp);
1308 d->m_contours[o].m_edges[e].m_edge_type = edge.m_interpolator->edge_type();
1309 }
1310
1311 d->end_contour(builder);
1312 d->m_contours[o].m_is_closed = contour.m_is_closed;
1313 }
1314 d->finalize(builder);
1315}
1316
1317fastuidraw::TessellatedPath::
1318TessellatedPath(const Path &input,
1319 fastuidraw::TessellatedPath::TessellationParams TP,
1320 reference_counted_ptr<Refiner> *ref)
1321{
1322 TessellatedPathPrivate *d;
1323 m_d = d = FASTUIDRAWnew TessellatedPathPrivate(input.number_contours(), TP);
1324
1325 if (input.number_contours() == 0)
1326 {
1327 return;
1328 }
1329
1330 std::vector<segment> work_room;
1331 RefinerPrivate *refiner_d(nullptr);
1332
1333 if (ref)
1334 {
1335 Refiner *r;
1336 r = FASTUIDRAWnew Refiner(this, input);
1337 *ref = r;
1338 refiner_d = static_cast<RefinerPrivate*>(r->m_d);
1339 }
1340
1341 TessellatedPathBuildingState builder;
1342 for(unsigned int o = 0, endo = input.number_contours(); o < endo; ++o)
1343 {
1344 const reference_counted_ptr<const PathContour> &contour(input.contour(o));
1345
1346 if (refiner_d)
1347 {
1348 refiner_d->m_contours[o].m_edges.resize(contour->number_interpolators());
1349 refiner_d->m_contours[o].m_start_pt = contour->point(0);
1350 }
1351
1352 d->start_contour(builder, o, contour->point(0), contour->number_interpolators());
1353 for(unsigned int e = 0, ende = contour->number_interpolators(); e < ende; ++e)
1354 {
1355 SegmentStorage segment_storage;
1356 const reference_counted_ptr<const PathContour::interpolator_base> &interpolator(contour->interpolator(e));
1357 reference_counted_ptr<PathContour::tessellation_state> tess_state;
1358 float tmp;
1359
1360 FASTUIDRAWassert(interpolator);
1361 FASTUIDRAWassert(work_room.empty());
1362 segment_storage.m_d = &work_room;
1363
1364 tess_state = interpolator->produce_tessellation(d->m_params, &segment_storage, &tmp);
1365 if (tess_state)
1366 {
1367 d->m_max_recursion = t_max(d->m_max_recursion, tess_state->recursion_depth());
1368 }
1369
1370 if (refiner_d)
1371 {
1372 refiner_d->m_contours[o].m_edges[e].m_tess_state = tess_state;
1373 refiner_d->m_contours[o].m_edges[e].m_interpolator = interpolator;
1374 }
1375
1376 d->add_edge(builder, o, e, work_room, tmp);
1377 d->m_contours[o].m_edges[e].m_edge_type = interpolator->edge_type();
1378 }
1379
1380 d->end_contour(builder);
1381 d->m_contours[o].m_is_closed = contour->closed();
1382 }
1383 d->finalize(builder);
1384}
1385
1386fastuidraw::TessellatedPath::
1387TessellatedPath(const TessellatedPath &with_arcs, float thresh)
1388{
1389 m_d = FASTUIDRAWnew TessellatedPathPrivate(with_arcs, thresh);
1390}
1391
1392fastuidraw::TessellatedPath::
1393~TessellatedPath()
1394{
1395 TessellatedPathPrivate *d;
1396 d = static_cast<TessellatedPathPrivate*>(m_d);
1397 FASTUIDRAWdelete(d);
1398 m_d = nullptr;
1399}
1400
1401const fastuidraw::TessellatedPath::TessellationParams&
1402fastuidraw::TessellatedPath::
1403tessellation_parameters(void) const
1404{
1405 TessellatedPathPrivate *d;
1406 d = static_cast<TessellatedPathPrivate*>(m_d);
1407
1408 return d->m_params;
1409}
1410
1411float
1412fastuidraw::TessellatedPath::
1413max_distance(void) const
1414{
1415 TessellatedPathPrivate *d;
1416 d = static_cast<TessellatedPathPrivate*>(m_d);
1417 return d->m_max_distance;
1418}
1419
1420unsigned int
1421fastuidraw::TessellatedPath::
1422max_recursion(void) const
1423{
1424 TessellatedPathPrivate *d;
1425 d = static_cast<TessellatedPathPrivate*>(m_d);
1426 return d->m_max_recursion;
1427}
1428
1429fastuidraw::c_array<const fastuidraw::TessellatedPath::segment>
1430fastuidraw::TessellatedPath::
1431segment_data(void) const
1432{
1433 TessellatedPathPrivate *d;
1434 d = static_cast<TessellatedPathPrivate*>(m_d);
1435
1436 return make_c_array(d->m_segment_data);
1437}
1438
1439fastuidraw::c_array<const fastuidraw::TessellatedPath::segment_chain>
1440fastuidraw::TessellatedPath::
1441segment_chain_data(void) const
1442{
1443 TessellatedPathPrivate *d;
1444 d = static_cast<TessellatedPathPrivate*>(m_d);
1445
1446 return make_c_array(d->m_segment_chain_data);
1447}
1448
1449fastuidraw::c_array<const fastuidraw::TessellatedPath::join>
1450fastuidraw::TessellatedPath::
1451join_data(void) const
1452{
1453 TessellatedPathPrivate *d;
1454 d = static_cast<TessellatedPathPrivate*>(m_d);
1455
1456 return make_c_array(d->m_join_data);
1457}
1458
1459fastuidraw::c_array<const fastuidraw::TessellatedPath::cap>
1460fastuidraw::TessellatedPath::
1461cap_data(void) const
1462{
1463 TessellatedPathPrivate *d;
1464 d = static_cast<TessellatedPathPrivate*>(m_d);
1465
1466 return make_c_array(d->m_cap_data);
1467}
1468
1469unsigned int
1470fastuidraw::TessellatedPath::
1471number_contours(void) const
1472{
1473 TessellatedPathPrivate *d;
1474 d = static_cast<TessellatedPathPrivate*>(m_d);
1475
1476 return d->m_contours.size();
1477}
1478
1479bool
1480fastuidraw::TessellatedPath::
1481contour_closed(unsigned int contour) const
1482{
1483 TessellatedPathPrivate *d;
1484 d = static_cast<TessellatedPathPrivate*>(m_d);
1485
1486 return d->m_contours[contour].m_is_closed;
1487}
1488
1489fastuidraw::range_type<unsigned int>
1490fastuidraw::TessellatedPath::
1491contour_range(unsigned int contour) const
1492{
1493 TessellatedPathPrivate *d;
1494 d = static_cast<TessellatedPathPrivate*>(m_d);
1495
1496 return range_type<unsigned int>(d->m_contours[contour].m_edges.front().m_edge_range.m_begin,
1497 d->m_contours[contour].m_edges.back().m_edge_range.m_end);
1498}
1499
1500fastuidraw::c_array<const fastuidraw::TessellatedPath::segment>
1501fastuidraw::TessellatedPath::
1502contour_segment_data(unsigned int contour) const
1503{
1504 TessellatedPathPrivate *d;
1505 d = static_cast<TessellatedPathPrivate*>(m_d);
1506
1507 return make_c_array(d->m_segment_data).sub_array(contour_range(contour));
1508}
1509
1510fastuidraw::c_array<const fastuidraw::TessellatedPath::segment_chain>
1511fastuidraw::TessellatedPath::
1512contour_chains(unsigned int contour) const
1513{
1514 TessellatedPathPrivate *d;
1515 d = static_cast<TessellatedPathPrivate*>(m_d);
1516
1517 return make_c_array(d->m_segment_chain_data).sub_array(d->m_contours[contour].m_segment_chain_range);
1518}
1519
1520unsigned int
1521fastuidraw::TessellatedPath::
1522number_edges(unsigned int contour) const
1523{
1524 TessellatedPathPrivate *d;
1525 d = static_cast<TessellatedPathPrivate*>(m_d);
1526
1527 return d->m_contours[contour].m_edges.size();
1528}
1529
1530fastuidraw::range_type<unsigned int>
1531fastuidraw::TessellatedPath::
1532edge_range(unsigned int contour, unsigned int edge) const
1533{
1534 TessellatedPathPrivate *d;
1535 d = static_cast<TessellatedPathPrivate*>(m_d);
1536
1537 return d->m_contours[contour].m_edges[edge].m_edge_range;
1538}
1539
1540enum fastuidraw::PathEnums::edge_type_t
1541fastuidraw::TessellatedPath::
1542edge_type(unsigned int contour, unsigned int edge) const
1543{
1544 TessellatedPathPrivate *d;
1545 d = static_cast<TessellatedPathPrivate*>(m_d);
1546
1547 return d->m_contours[contour].m_edges[edge].m_edge_type;
1548}
1549
1550fastuidraw::TessellatedPath::segment_chain
1551fastuidraw::TessellatedPath::
1552edge_segment_chain(unsigned int contour, unsigned int edge) const
1553{
1554 segment_chain return_value;
1555
1556 return_value.m_segments = edge_segment_data(contour, edge);
1557 if (edge_type(contour, edge) == PathEnums::starts_new_edge)
1558 {
1559 return_value.m_prev_to_start = nullptr;
1560 }
1561 else
1562 {
1563 if (edge > 0)
1564 {
1565 return_value.m_prev_to_start = &edge_segment_data(contour, edge - 1).back();
1566 }
1567 else
1568 {
1569 if (contour_closed(contour))
1570 {
1571 int prev_edge(number_edges(contour) - 1);
1572 return_value.m_prev_to_start = &edge_segment_data(contour, prev_edge).back();
1573 }
1574 else
1575 {
1576 return_value.m_prev_to_start = nullptr;
1577 }
1578 }
1579 }
1580 return return_value;
1581}
1582
1583fastuidraw::c_array<const fastuidraw::TessellatedPath::segment>
1584fastuidraw::TessellatedPath::
1585edge_segment_data(unsigned int contour, unsigned int edge) const
1586{
1587 TessellatedPathPrivate *d;
1588 d = static_cast<TessellatedPathPrivate*>(m_d);
1589
1590 return make_c_array(d->m_segment_data).sub_array(edge_range(contour, edge));
1591}
1592
1593const fastuidraw::Rect&
1594fastuidraw::TessellatedPath::
1595bounding_box(void) const
1596{
1597 TessellatedPathPrivate *d;
1598 d = static_cast<TessellatedPathPrivate*>(m_d);
1599 return d->m_bounding_box.as_rect();
1600}
1601
1602bool
1603fastuidraw::TessellatedPath::
1604has_arcs(void) const
1605{
1606 TessellatedPathPrivate *d;
1607 d = static_cast<TessellatedPathPrivate*>(m_d);
1608
1609 return d->m_has_arcs;
1610}
1611
1612const fastuidraw::StrokedPath&
1613fastuidraw::TessellatedPath::
1614stroked(void) const
1615{
1616 TessellatedPathPrivate *d;
1617 d = static_cast<TessellatedPathPrivate*>(m_d);
1618 if (!d->m_stroked)
1619 {
1620 d->m_stroked = FASTUIDRAWnew StrokedPath(*this);
1621 }
1622 return *(d->m_stroked);
1623}
1624
1625const fastuidraw::TessellatedPath&
1626fastuidraw::TessellatedPath::
1627linearization(float thresh) const
1628{
1629 TessellatedPathPrivate *d;
1630 d = static_cast<TessellatedPathPrivate*>(m_d);
1631
1632 if (!d->m_has_arcs)
1633 {
1634 return *this;
1635 }
1636
1637 if (d->m_linearization.empty())
1638 {
1639 /* default tessellation where arcs are barely tessellated */
1640 d->m_linearization.push_back(FASTUIDRAWnew TessellatedPath(*this, -1.0f));
1641 }
1642
1643 if (thresh < 0.0f)
1644 {
1645 return *(d->m_linearization.front());
1646 }
1647
1648 /* asking for a finer tessellation than the
1649 * max-distance of this TessellatedPath is
1650 * pointless.
1651 */
1652 thresh = t_max(thresh, d->m_max_distance);
1653 if (d->m_linearization.back()->max_distance() <= thresh)
1654 {
1655 typename std::vector<reference_counted_ptr<const TessellatedPath> >::const_iterator iter;
1656 iter = std::lower_bound(d->m_linearization.begin(),
1657 d->m_linearization.end(),
1658 thresh, detail::reverse_compare_max_distance);
1659 FASTUIDRAWassert(iter != d->m_linearization.end());
1660 FASTUIDRAWassert(*iter);
1661 FASTUIDRAWassert((*iter)->max_distance() <= thresh);
1662 return **iter;
1663 }
1664
1665 float current(d->m_linearization.back()->max_distance());
1666 while (current > thresh)
1667 {
1668 current *= 0.5f;
1669 d->m_linearization.push_back(FASTUIDRAWnew TessellatedPath(*this, current));
1670 }
1671 return *(d->m_linearization.back());
1672}
1673
1674const fastuidraw::TessellatedPath&
1675fastuidraw::TessellatedPath::
1676linearization(void) const
1677{
1678 return linearization(-1.0f);
1679}
1680
1681const fastuidraw::FilledPath&
1682fastuidraw::TessellatedPath::
1683filled(float thresh) const
1684{
1685 const TessellatedPath *tess;
1686 TessellatedPathPrivate *tess_d;
1687
1688 tess = &linearization(thresh);
1689 tess_d = static_cast<TessellatedPathPrivate*>(tess->m_d);
1690 if (!tess_d->m_filled)
1691 {
1692 tess_d->m_filled = FASTUIDRAWnew FilledPath(*tess);
1693 }
1694 return *(tess_d->m_filled);
1695}
1696
1697const fastuidraw::FilledPath&
1698fastuidraw::TessellatedPath::
1699filled(void) const
1700{
1701 return filled(-1.0f);
1702}
1703
1704const fastuidraw::PartitionedTessellatedPath&
1705fastuidraw::TessellatedPath::
1706partitioned(void) const
1707{
1708 TessellatedPathPrivate *d;
1709 d = static_cast<TessellatedPathPrivate*>(m_d);
1710 if (!d->m_partitioned)
1711 {
1712 d->m_partitioned = FASTUIDRAWnew PartitionedTessellatedPath(*this);
1713 }
1714 return *(d->m_partitioned);
1715}
1716