1/*!
2 * \file path.cpp
3 * \brief file path.cpp
4 *
5 * Copyright 2016 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 <algorithm>
21#include <cmath>
22#include <vector>
23#include <fastuidraw/path.hpp>
24#include <fastuidraw/tessellated_path.hpp>
25#include <private/util_private.hpp>
26#include <private/util_private_ostream.hpp>
27#include <private/path_util_private.hpp>
28#include <private/bounding_box.hpp>
29#include <private/bezier_util.hpp>
30
31namespace
32{
33 typedef fastuidraw::vecN<fastuidraw::vec2, 4> BezierCubic;
34
35 inline
36 float
37 compute_distance(const fastuidraw::vec2 &a,
38 const fastuidraw::vec2 &p,
39 const fastuidraw::vec2 &b)
40 {
41 fastuidraw::vec2 p_a, b_a, p_b;
42 float d, p_a_mag_sq;
43
44 p_a = p - a;
45 b_a = b - a;
46 p_b = p - b;
47 d = fastuidraw::dot(p_a, b_a);
48 p_a_mag_sq = p_a.magnitudeSq();
49
50 if (fastuidraw::dot(p_b, b_a) <= 0.0f && d >= 0.0f)
51 {
52 float d_sq, r, b_a_mag_sq;
53
54 b_a_mag_sq = b_a.magnitudeSq();
55 d_sq = d * d;
56 r = p_a_mag_sq - d_sq / b_a_mag_sq;
57 r = fastuidraw::t_max(0.0f, r);
58 return fastuidraw::t_sqrt(r);
59 }
60 else
61 {
62 float r, b_p_mag_sq;
63
64 b_p_mag_sq = (b - p).magnitudeSq();
65 r = fastuidraw::t_min(p_a_mag_sq, b_p_mag_sq);
66 r = fastuidraw::t_sqrt(r);
67 return r;
68 }
69 }
70
71 class ArcSegment
72 {
73 public:
74 ArcSegment(void)
75 {}
76
77 ArcSegment(const fastuidraw::vec2 &start_pt,
78 const fastuidraw::vec2 &mid_pt,
79 const fastuidraw::vec2 &end_pt);
80
81 float
82 distance(fastuidraw::vec2 pt) const;
83
84 bool m_too_flat;
85 fastuidraw::vec2 m_center;
86 fastuidraw::range_type<float> m_angle;
87 float m_radius;
88
89 fastuidraw::vec2 m_circle_sector_boundary[2];
90 fastuidraw::vec2 m_circle_sector_center;
91 float m_circle_sector_cos_angle;
92 };
93
94 class ArcTessellatorStateNode
95 {
96 public:
97 explicit
98 ArcTessellatorStateNode(const fastuidraw::PathContour::interpolator_generic *h);
99
100 float
101 max_distance(void) const
102 {
103 return m_max_distance;
104 }
105
106 void
107 add_segment(fastuidraw::TessellatedPath::SegmentStorage *out_data) const;
108
109 unsigned int
110 recursion_depth(void) const
111 {
112 return m_recursion_depth;
113 }
114
115 ArcTessellatorStateNode
116 splitL(const fastuidraw::PathContour::interpolator_generic *h) const;
117
118 ArcTessellatorStateNode
119 splitR(const fastuidraw::PathContour::interpolator_generic *h) const;
120
121 private:
122 ArcTessellatorStateNode(const fastuidraw::PathContour::interpolator_generic *h,
123 const fastuidraw::vec2 &p0,
124 const fastuidraw::vec2 &p1,
125 fastuidraw::reference_counted_ptr<fastuidraw::PathContour::interpolator_generic::tessellated_region> rgn,
126 unsigned int depth);
127
128 void
129 compute_values(void);
130
131 fastuidraw::vec2 m_start, m_end, m_mid;
132 fastuidraw::reference_counted_ptr<fastuidraw::PathContour::interpolator_generic::tessellated_region> m_L, m_R;
133
134 float m_max_distance;
135 unsigned int m_recursion_depth;
136
137 /* The arc connecting m_start to m_end going through m_mid. */
138 ArcSegment m_arc;
139 };
140
141 class TessellationState:public fastuidraw::PathContour::tessellation_state
142 {
143 public:
144 explicit
145 TessellationState(const fastuidraw::PathContour::interpolator_generic *h);
146
147 virtual
148 unsigned int
149 recursion_depth(void) const
150 {
151 return m_recursion_depth;
152 }
153
154 virtual
155 void
156 resume_tessellation(const fastuidraw::TessellatedPath::TessellationParams &tess_params,
157 fastuidraw::TessellatedPath::SegmentStorage *out_data,
158 float *out_max_distance);
159
160 private:
161 void
162 resume_tessellation_worker(const ArcTessellatorStateNode &node,
163 const fastuidraw::TessellatedPath::TessellationParams &tess_params,
164 std::vector<ArcTessellatorStateNode> *dst);
165
166
167 fastuidraw::reference_counted_ptr<const fastuidraw::PathContour::interpolator_generic> m_h;
168 std::vector<ArcTessellatorStateNode> m_nodes;
169 unsigned int m_recursion_depth;
170 unsigned int m_minimum_tessellation_recursion;
171 };
172
173 class InterpolatorBasePrivate
174 {
175 public:
176 fastuidraw::vec2 m_start, m_end;
177 enum fastuidraw::PathEnums::edge_type_t m_type;
178 };
179
180 class BezierTessRegion:
181 public fastuidraw::PathContour::interpolator_generic::tessellated_region
182 {
183 public:
184 explicit
185 BezierTessRegion(const BezierTessRegion *parent, bool is_region_start);
186
187 explicit
188 BezierTessRegion(fastuidraw::BoundingBox<float> &bb,
189 const fastuidraw::vec2 &start,
190 fastuidraw::c_array<const fastuidraw::vec2> ct,
191 const fastuidraw::vec2 &end);
192
193 virtual
194 float
195 distance_to_line_segment(void) const;
196
197 virtual
198 float
199 distance_to_arc(float arc_radius, fastuidraw::vec2 arc_center,
200 fastuidraw::vec2 unit_vector_arc_middle,
201 float cos_arc_angle) const;
202
203 const fastuidraw::reference_counted_ptr<BezierTessRegion>&
204 left_child(void) const
205 {
206 create_children();
207 return m_L;
208 }
209
210 const fastuidraw::reference_counted_ptr<BezierTessRegion>&
211 right_child(void) const
212 {
213 create_children();
214 return m_R;
215 }
216
217 const fastuidraw::vec2&
218 front(void) const
219 {
220 return m_pts.front();
221 }
222
223 const fastuidraw::vec2&
224 back(void) const
225 {
226 return m_pts.back();
227 }
228
229 const std::vector<fastuidraw::vec2>&
230 pts(void) const
231 {
232 return m_pts;
233 }
234
235 private:
236 float
237 distance_to_line_segment_raw(const fastuidraw::vec2 &A,
238 const fastuidraw::vec2 &B) const;
239
240 float
241 distance_to_arc_raw(unsigned int depth, const ArcSegment &A) const;
242
243 void
244 create_children(void) const;
245
246 mutable fastuidraw::reference_counted_ptr<BezierTessRegion> m_L, m_R;
247 std::vector<fastuidraw::vec2> m_pts;
248 float m_start, m_end;
249 int m_arc_distance_depth;
250 };
251
252 class BezierPrivate
253 {
254 public:
255 fastuidraw::BoundingBox<float> m_bb;
256 fastuidraw::reference_counted_ptr<BezierTessRegion> m_start_region;
257 };
258
259 class ArcPrivate
260 {
261 public:
262 float m_radius, m_angle_speed;
263 float m_start_angle;
264 fastuidraw::vec2 m_center;
265 fastuidraw::BoundingBox<float> m_bb;
266 };
267
268 class PathContourPrivate
269 {
270 public:
271 PathContourPrivate(void):
272 m_ended(false),
273 m_is_flat(true),
274 m_checked_up_to(0)
275 {}
276
277 bool
278 is_flat(void)
279 {
280 update();
281 return m_is_flat;
282 }
283
284 const fastuidraw::BoundingBox<float>&
285 bb(void)
286 {
287 update();
288 return m_bb;
289 }
290
291 fastuidraw::vec2 m_start_pt;
292 std::vector<fastuidraw::vec2> m_current_control_points;
293 fastuidraw::reference_counted_ptr<const fastuidraw::PathContour::interpolator_base> m_end_to_start, m_null_interpolator;
294 std::vector<fastuidraw::reference_counted_ptr<const fastuidraw::PathContour::interpolator_base> > m_interpolators;
295 bool m_ended;
296
297 private:
298 void
299 update(void)
300 {
301 while (m_checked_up_to < m_interpolators.size())
302 {
303 fastuidraw::Rect tmp;
304
305 m_is_flat = m_is_flat && m_interpolators[m_checked_up_to]->is_flat();
306 m_interpolators[m_checked_up_to]->approximate_bounding_box(&tmp);
307 m_bb.union_point(tmp.m_min_point);
308 m_bb.union_point(tmp.m_max_point);
309 ++m_checked_up_to;
310 }
311 }
312
313 fastuidraw::BoundingBox<float> m_bb;
314 bool m_is_flat;
315 unsigned int m_checked_up_to;
316 };
317
318 class PathPrivate;
319
320 class TessellatedPathList
321 {
322 public:
323 typedef fastuidraw::TessellatedPath TessellatedPath;
324 typedef typename TessellatedPath::TessellationParams TessellationParams;
325 typedef fastuidraw::reference_counted_ptr<const TessellatedPath> TessellatedPathRef;
326
327 explicit
328 TessellatedPathList(void):
329 m_done(false)
330 {}
331
332 const TessellatedPathRef&
333 tessellation(const fastuidraw::Path &path, float max_distance);
334
335 void
336 clear(void)
337 {
338 m_data.clear();
339 m_refiner = nullptr;
340 m_done = false;
341 }
342
343 private:
344 bool m_done;
345 fastuidraw::reference_counted_ptr<TessellatedPath::Refiner> m_refiner;
346 std::vector<TessellatedPathRef> m_data;
347 };
348
349 class PathPrivate:fastuidraw::noncopyable
350 {
351 public:
352 explicit
353 PathPrivate(void);
354
355 const fastuidraw::reference_counted_ptr<fastuidraw::PathContour>&
356 current_contour(void);
357
358 void
359 move_common(const fastuidraw::vec2 &pt);
360
361 void
362 clear_tesses(void);
363
364 void
365 start_contour_if_necessary(void);
366
367 std::vector<fastuidraw::reference_counted_ptr<fastuidraw::PathContour> > m_contours;
368 enum fastuidraw::PathEnums::edge_type_t m_next_edge_type;
369
370 TessellatedPathList m_tess_list;
371
372 /* m_start_check_bb gives the index into m_contours that
373 * have not had their bounding box absorbed m_bb
374 */
375 unsigned int m_start_check_bb;
376 fastuidraw::BoundingBox<float> m_bb;
377 bool m_is_flat;
378 fastuidraw::reference_counted_ptr<const fastuidraw::ShaderFilledPath> m_shader_filled_path;
379 };
380}
381
382/////////////////////////////////
383// ArcSegment methods
384ArcSegment::
385ArcSegment(const fastuidraw::vec2 &start,
386 const fastuidraw::vec2 &mid,
387 const fastuidraw::vec2 &end)
388{
389 using namespace fastuidraw;
390
391 vec2 v0, v1, n0, n1, p0, p1;
392 float det;
393 static float tol(0.00001f);
394
395 p0 = 0.5f * (start + mid);
396 p1 = 0.5f * (mid + end);
397
398 v0 = start - mid;
399 n0 = vec2(-v0.y(), v0.x());
400
401 v1 = mid - end;
402 n1 = vec2(-v1.y(), v1.x());
403
404 det = n1.y() * n0.x() - n0.y() * n1.x();
405 m_too_flat = (t_abs(det) < tol);
406
407 if (!m_too_flat)
408 {
409 float s, invRadius;
410 vec2 cs, ce;
411 const float pi(FASTUIDRAW_PI), two_pi(2.0f * pi);
412
413 s = dot(v1, p1 - p0) / det;
414 m_center = p0 + s * n0;
415 m_radius = (m_center - mid).magnitude();
416 invRadius = 1.0f / m_radius;
417 cs = (start - m_center) * invRadius;
418 ce = (end - m_center) * invRadius;
419 m_angle.m_begin = cs.atan();
420 m_angle.m_end = ce.atan();
421
422 /* Under linear tessellation the points from start to _end
423 * would be approximated by a line segment. In that spirit,
424 * take the smaller arc always.
425 */
426 if (t_abs(m_angle.m_begin - m_angle.m_end) > pi)
427 {
428 if (m_angle.m_begin < m_angle.m_end)
429 {
430 m_angle.m_begin += two_pi;
431 }
432 else
433 {
434 m_angle.m_end += two_pi;
435 }
436 }
437
438 float theta;
439
440 theta = 0.5f * (m_angle.m_begin + m_angle.m_end);
441 m_circle_sector_center.x() = t_cos(theta);
442 m_circle_sector_center.y() = t_sin(theta);
443 m_circle_sector_cos_angle = dot(cs, m_circle_sector_center);
444 m_circle_sector_boundary[0] = cs;
445 m_circle_sector_boundary[1] = ce;
446 }
447}
448
449float
450ArcSegment::
451distance(fastuidraw::vec2 pt) const
452{
453 using namespace fastuidraw;
454
455 float d, ptmag;
456
457 pt -= m_center;
458 ptmag = pt.magnitude();
459 d = dot(m_circle_sector_center, pt / ptmag);
460 if (d >= m_circle_sector_cos_angle)
461 {
462 return t_abs(m_radius - ptmag);
463 }
464 else
465 {
466 vec2 a(pt - m_circle_sector_boundary[0]);
467 vec2 b(pt - m_circle_sector_boundary[1]);
468 return t_sqrt(t_min(dot(a, a), dot(b, b)));
469 }
470}
471
472///////////////////////////////////
473// ArcTessellatorStateNode methods
474ArcTessellatorStateNode::
475ArcTessellatorStateNode(const fastuidraw::PathContour::interpolator_generic *h):
476 m_start(h->start_pt()),
477 m_end(h->end_pt()),
478 m_recursion_depth(0)
479{
480 h->tessellate(nullptr, &m_L, &m_R, &m_mid);
481 compute_values();
482}
483
484ArcTessellatorStateNode::
485ArcTessellatorStateNode(const fastuidraw::PathContour::interpolator_generic *h,
486 const fastuidraw::vec2 &start,
487 const fastuidraw::vec2 &end,
488 fastuidraw::reference_counted_ptr<fastuidraw::PathContour::interpolator_generic::tessellated_region> rgn,
489 unsigned int depth):
490 m_start(start),
491 m_end(end),
492 m_recursion_depth(depth)
493{
494 h->tessellate(rgn, &m_L, &m_R, &m_mid);
495 compute_values();
496}
497
498void
499ArcTessellatorStateNode::
500compute_values(void)
501{
502 m_arc = ArcSegment(m_start, m_mid, m_end);
503 if (m_arc.m_too_flat)
504 {
505 m_max_distance = fastuidraw::t_max(m_L->distance_to_line_segment(),
506 m_R->distance_to_line_segment());
507 }
508 else
509 {
510 m_max_distance = fastuidraw::t_max(m_L->distance_to_arc(m_arc.m_radius, m_arc.m_center,
511 m_arc.m_circle_sector_center,
512 m_arc.m_circle_sector_cos_angle),
513 m_R->distance_to_arc(m_arc.m_radius, m_arc.m_center,
514 m_arc.m_circle_sector_center,
515 m_arc.m_circle_sector_cos_angle));
516 }
517}
518
519void
520ArcTessellatorStateNode::
521add_segment(fastuidraw::TessellatedPath::SegmentStorage *out_data) const
522{
523 if (m_arc.m_too_flat)
524 {
525 out_data->add_line_segment(m_start, m_mid);
526 out_data->add_line_segment(m_mid, m_end);
527 }
528 else
529 {
530 out_data->add_arc_segment(m_start, m_end,
531 m_arc.m_center,
532 m_arc.m_radius,
533 m_arc.m_angle);
534 }
535}
536
537ArcTessellatorStateNode
538ArcTessellatorStateNode::
539splitL(const fastuidraw::PathContour::interpolator_generic *h) const
540{
541 return ArcTessellatorStateNode(h, m_start, m_mid, m_L, m_recursion_depth + 1);
542}
543
544ArcTessellatorStateNode
545ArcTessellatorStateNode::
546splitR(const fastuidraw::PathContour::interpolator_generic *h) const
547{
548 return ArcTessellatorStateNode(h, m_mid, m_end, m_R, m_recursion_depth + 1);
549}
550
551/////////////////////////////////
552// TessellationState methods
553TessellationState::
554TessellationState(const fastuidraw::PathContour::interpolator_generic *h):
555 m_h(h),
556 m_recursion_depth(0),
557 m_minimum_tessellation_recursion(h->minimum_tessellation_recursion())
558{
559 m_nodes.push_back(ArcTessellatorStateNode(h));
560}
561
562void
563TessellationState::
564resume_tessellation(const fastuidraw::TessellatedPath::TessellationParams &tess_params,
565 fastuidraw::TessellatedPath::SegmentStorage *out_data,
566 float *out_max_distance)
567{
568 std::vector<ArcTessellatorStateNode> new_nodes;
569
570 for(const ArcTessellatorStateNode &node : m_nodes)
571 {
572 resume_tessellation_worker(node, tess_params, &new_nodes);
573 }
574
575 std::swap(new_nodes, m_nodes);
576 *out_max_distance = 0.0f;
577 m_recursion_depth = 0;
578 for(const ArcTessellatorStateNode &node : m_nodes)
579 {
580 node.add_segment(out_data);
581 m_recursion_depth = fastuidraw::t_max(m_recursion_depth, node.recursion_depth());
582 *out_max_distance = fastuidraw::t_max(*out_max_distance, node.max_distance());
583 }
584}
585
586void
587TessellationState::
588resume_tessellation_worker(const ArcTessellatorStateNode &node,
589 const fastuidraw::TessellatedPath::TessellationParams &tess_params,
590 std::vector<ArcTessellatorStateNode> *dst)
591{
592 unsigned int recurse_level;
593
594 recurse_level = node.recursion_depth();
595
596 if (recurse_level == 0
597 || recurse_level < m_minimum_tessellation_recursion
598 || (tess_params.m_max_distance > 0.0f
599 && recurse_level <= tess_params.m_max_recursion
600 && node.max_distance() > tess_params.m_max_distance))
601 {
602 resume_tessellation_worker(node.splitL(m_h.get()), tess_params, dst);
603 resume_tessellation_worker(node.splitR(m_h.get()), tess_params, dst);
604 }
605 else
606 {
607 dst->push_back(node);
608 }
609}
610
611////////////////////////////////////////////
612// fastuidraw::PathContour::interpolator_base methods
613fastuidraw::PathContour::interpolator_base::
614interpolator_base(PathContour &contour,
615 const vec2 &end, enum PathEnums::edge_type_t tp)
616{
617 InterpolatorBasePrivate *d;
618 PathContourPrivate *c_d;
619
620 c_d = static_cast<PathContourPrivate*>(contour.m_d);
621 m_d = d = FASTUIDRAWnew InterpolatorBasePrivate();
622
623 d->m_end = end;
624 if (c_d->m_interpolators.empty())
625 {
626 d->m_type = PathEnums::starts_new_edge;
627 d->m_start = c_d->m_start_pt;
628 }
629 else
630 {
631 InterpolatorBasePrivate *prev_d;
632 prev_d = static_cast<InterpolatorBasePrivate*>(c_d->m_interpolators.back()->m_d);
633
634 d->m_type = tp;
635 d->m_start = prev_d->m_end;
636 }
637 c_d->m_interpolators.push_back(this);
638}
639
640fastuidraw::PathContour::interpolator_base::
641~interpolator_base(void)
642{
643 InterpolatorBasePrivate *d;
644 d = static_cast<InterpolatorBasePrivate*>(m_d);
645 FASTUIDRAWdelete(d);
646 m_d = nullptr;
647}
648
649const fastuidraw::vec2&
650fastuidraw::PathContour::interpolator_base::
651start_pt(void) const
652{
653 InterpolatorBasePrivate *d;
654 d = static_cast<InterpolatorBasePrivate*>(m_d);
655 return d->m_start;
656}
657
658const fastuidraw::vec2&
659fastuidraw::PathContour::interpolator_base::
660end_pt(void) const
661{
662 InterpolatorBasePrivate *d;
663 d = static_cast<InterpolatorBasePrivate*>(m_d);
664 return d->m_end;
665}
666
667enum fastuidraw::PathEnums::edge_type_t
668fastuidraw::PathContour::interpolator_base::
669edge_type(void) const
670{
671 InterpolatorBasePrivate *d;
672 d = static_cast<InterpolatorBasePrivate*>(m_d);
673 return d->m_type;
674}
675
676enum fastuidraw::return_code
677fastuidraw::PathContour::interpolator_base::
678add_to_builder(ShaderFilledPath::Builder*, float) const
679{
680 return routine_fail;
681}
682
683//////////////////////////////////////////////
684// fastuidraw::PathContour::interpolator_generic methods
685fastuidraw::reference_counted_ptr<fastuidraw::PathContour::tessellation_state>
686fastuidraw::PathContour::interpolator_generic::
687produce_tessellation(const TessellatedPath::TessellationParams &tess_params,
688 TessellatedPath::SegmentStorage *out_data,
689 float *out_max_distance) const
690{
691 fastuidraw::reference_counted_ptr<fastuidraw::PathContour::tessellation_state> return_value;
692
693 return_value = FASTUIDRAWnew TessellationState(this);
694 return_value->resume_tessellation(tess_params, out_data, out_max_distance);
695 return return_value;
696}
697
698///////////////////////////////////
699// BezierTessRegion methods
700BezierTessRegion::
701BezierTessRegion(const BezierTessRegion *parent, bool is_region_start):
702 m_arc_distance_depth(parent->m_arc_distance_depth)
703{
704 float mid;
705
706 m_pts.reserve(parent->m_pts.size());
707 mid = 0.5f * (parent->m_start + parent->m_end);
708 if (is_region_start)
709 {
710 m_start = parent->m_start;
711 m_end = mid;
712 }
713 else
714 {
715 m_start = mid;
716 m_end = parent->m_end;
717 }
718}
719
720BezierTessRegion::
721BezierTessRegion(fastuidraw::BoundingBox<float> &bb,
722 const fastuidraw::vec2 &start,
723 fastuidraw::c_array<const fastuidraw::vec2> ct,
724 const fastuidraw::vec2 &end):
725 m_start(0.0f),
726 m_end(1.0f)
727{
728 m_pts.reserve(ct.size() + 2);
729 m_pts.push_back(start);
730 for (const auto &pt : ct)
731 {
732 m_pts.push_back(pt);
733 }
734 m_pts.push_back(end);
735 m_arc_distance_depth = fastuidraw::uint32_log2(m_pts.size());
736
737 for(const fastuidraw::vec2 &pt : m_pts)
738 {
739 bb.union_point(pt);
740 }
741}
742
743void
744BezierTessRegion::
745create_children(void) const
746{
747 using namespace fastuidraw;
748
749 if (m_L)
750 {
751 FASTUIDRAWassert(m_R);
752 return;
753 }
754
755 FASTUIDRAWassert(!m_R);
756 m_L = FASTUIDRAWnew BezierTessRegion(this, true);
757 m_R = FASTUIDRAWnew BezierTessRegion(this, false);
758
759 c_array<vec2> dst;
760 c_array<const vec2> src;
761 vecN<std::vector<vec2>, 2> work_room;
762
763 work_room[0].resize(m_pts.size());
764 work_room[1].resize(m_pts.size());
765
766 src = make_c_array(m_pts);
767 m_L->m_pts.push_back(src.front());
768 m_R->m_pts.push_back(src.back());
769
770 /* For a Bezier curve, given by points p(0), .., p(n),
771 * and a time 0 <= t <= 1, De Casteljau's algorithm is
772 * the following.
773 *
774 * Let
775 * q(0, j) = p(j) for 0 <= j <= n,
776 * q(i + 1, j) = (1 - t) * q(i, j) + t * q(i, j + 1) for 0 <= i <= n, 0 <= j <= n - i
777 * then
778 * The curve split at time t is given by
779 * A = { q(0, 0), q(1, 0), q(2, 0), ... , q(n, 0) }
780 * B = { q(n, 0), q(n - 1, 1), q(n - 2, 2), ... , q(0, n) }
781 * and
782 * the curve evaluated at t is given by q(n, 0).
783 * We use t = 0.5 because we are always doing mid-point cutting.
784 */
785 for(unsigned int i = 0, endi = src.size(), sz = endi - 1; sz > 0 && i < endi; ++i, --sz)
786 {
787 dst = make_c_array(work_room[i & 1]).sub_array(0, sz);
788 for(unsigned int j = 0; j < dst.size(); ++j)
789 {
790 dst[j] = 0.5f * src[j] + 0.5f * src[j + 1];
791 }
792 m_L->m_pts.push_back(dst.front());
793 m_R->m_pts.push_back(dst.back());
794 src = dst;
795 }
796 std::reverse(m_R->m_pts.begin(), m_R->m_pts.end());
797}
798
799float
800BezierTessRegion::
801distance_to_line_segment(void) const
802{
803 create_children();
804 return fastuidraw::t_max(m_L->distance_to_line_segment_raw(front(), back()),
805 m_R->distance_to_line_segment_raw(front(), back()));
806}
807
808float
809BezierTessRegion::
810distance_to_arc(float arc_radius, fastuidraw::vec2 arc_center,
811 fastuidraw::vec2 unit_vector_arc_middle,
812 float cos_arc_angle) const
813{
814 ArcSegment A;
815
816 A.m_too_flat = false;
817 A.m_center = arc_center;
818 A.m_radius = arc_radius;
819 A.m_circle_sector_boundary[0] = m_pts.front();
820 A.m_circle_sector_boundary[1] = m_pts.back();
821 A.m_circle_sector_center = unit_vector_arc_middle;
822 A.m_circle_sector_cos_angle = cos_arc_angle;
823
824 return distance_to_arc_raw(m_arc_distance_depth, A);
825}
826
827float
828BezierTessRegion::
829distance_to_line_segment_raw(const fastuidraw::vec2 &A,
830 const fastuidraw::vec2 &B) const
831{
832 using namespace fastuidraw;
833
834 /* Recall that a Bezier curve is bounded by its convex
835 * hull. Thus an upper bound on the distance between
836 * a line segment and the curve is just the maximum of
837 * the distances of each of the points (control and end
838 * points) to the line segment.
839 */
840 float return_value(0.0f);
841 for(unsigned int i = 0, endi = m_pts.size(); i < endi; ++i)
842 {
843 float v;
844 v = compute_distance(A, m_pts[i], B);
845 return_value = t_max(return_value, v);
846 }
847 return return_value;
848}
849
850float
851BezierTessRegion::
852distance_to_arc_raw(unsigned int depth, const ArcSegment &A) const
853{
854 using namespace fastuidraw;
855
856 create_children();
857 if (depth <= 1)
858 {
859 return A.distance(m_L->back());
860 }
861 else
862 {
863 return t_max(m_L->distance_to_arc_raw(depth - 1, A),
864 m_R->distance_to_arc_raw(depth - 1, A));
865 }
866}
867
868////////////////////////////////////
869// fastuidraw::PathContour::bezier methods
870fastuidraw::PathContour::bezier::
871bezier(PathContour &contour,
872 const vec2 &ct, const vec2 &end, enum PathEnums::edge_type_t tp):
873 interpolator_generic(contour, end, tp)
874{
875 BezierPrivate *d;
876 vecN<vec2, 1> ctl(ct);
877
878 d = FASTUIDRAWnew BezierPrivate();
879 d->m_start_region = FASTUIDRAWnew BezierTessRegion(d->m_bb, start_pt(), ctl, end_pt());
880 m_d = d;
881}
882
883fastuidraw::PathContour::bezier::
884bezier(PathContour &contour, const vec2 &ct1,
885 const vec2 &ct2, const vec2 &end, enum PathEnums::edge_type_t tp):
886 interpolator_generic(contour, end, tp)
887{
888 BezierPrivate *d;
889 vecN<vec2, 2> ctl(ct1, ct2);
890
891 d = FASTUIDRAWnew BezierPrivate();
892 d->m_start_region = FASTUIDRAWnew BezierTessRegion(d->m_bb, start_pt(), ctl, end_pt());
893 m_d = d;
894}
895
896fastuidraw::PathContour::bezier::
897bezier(PathContour &contour,
898 c_array<const vec2> ctl,
899 const vec2 &end, enum PathEnums::edge_type_t tp):
900 interpolator_generic(contour, end, tp)
901{
902 BezierPrivate *d;
903
904 d = FASTUIDRAWnew BezierPrivate();
905 d->m_start_region = FASTUIDRAWnew BezierTessRegion(d->m_bb, start_pt(), ctl, end_pt());
906 m_d = d;
907}
908
909fastuidraw::PathContour::bezier::
910~bezier()
911{
912 BezierPrivate *d;
913 d = static_cast<BezierPrivate*>(m_d);
914 FASTUIDRAWdelete(d);
915 m_d = nullptr;
916}
917
918bool
919fastuidraw::PathContour::bezier::
920is_flat(void) const
921{
922 BezierPrivate *d;
923 d = static_cast<BezierPrivate*>(m_d);
924 return d->m_start_region->pts().size() <= 2;
925}
926
927fastuidraw::c_array<const fastuidraw::vec2>
928fastuidraw::PathContour::bezier::
929pts(void) const
930{
931 BezierPrivate *d;
932 d = static_cast<BezierPrivate*>(m_d);
933 return make_c_array(d->m_start_region->pts());
934}
935
936void
937fastuidraw::PathContour::bezier::
938approximate_bounding_box(Rect *out_bb) const
939{
940 BezierPrivate *d;
941 d = static_cast<BezierPrivate*>(m_d);
942 out_bb->m_min_point = d->m_bb.min_point();
943 out_bb->m_max_point = d->m_bb.max_point();
944}
945
946void
947fastuidraw::PathContour::bezier::
948tessellate(reference_counted_ptr<tessellated_region> in_region,
949 reference_counted_ptr<tessellated_region> *out_regionA,
950 reference_counted_ptr<tessellated_region> *out_regionB,
951 vec2 *out_p) const
952{
953 BezierPrivate *d;
954 d = static_cast<BezierPrivate*>(m_d);
955
956 if (!in_region)
957 {
958 in_region = d->m_start_region;
959 }
960
961 BezierTessRegion *in_region_casted;
962 FASTUIDRAWassert(dynamic_cast<BezierTessRegion*>(in_region.get()) != nullptr);
963 in_region_casted = static_cast<BezierTessRegion*>(in_region.get());
964
965 *out_regionA = in_region_casted->left_child();
966 *out_regionB = in_region_casted->right_child();
967 *out_p = in_region_casted->left_child()->back();
968}
969
970fastuidraw::reference_counted_ptr<fastuidraw::PathContour::interpolator_base>
971fastuidraw::PathContour::bezier::
972deep_copy(PathContour &contour) const
973{
974 c_array<const vec2> tmp(pts());
975
976 tmp = tmp.sub_array(1, tmp.size() - 2);
977 return FASTUIDRAWnew bezier(contour, tmp, end_pt(), edge_type());
978}
979
980unsigned int
981fastuidraw::PathContour::bezier::
982minimum_tessellation_recursion(void) const
983{
984 BezierPrivate *d;
985 d = static_cast<BezierPrivate*>(m_d);
986
987 return 1 + uint32_log2(d->m_start_region->pts().size());
988}
989
990enum fastuidraw::return_code
991fastuidraw::PathContour::bezier::
992add_to_builder(ShaderFilledPath::Builder *B, float tol) const
993{
994 c_array<const vec2> p(pts());
995
996 switch (p.size())
997 {
998 case 2:
999 B->line_to(p[1]);
1000 return routine_success;
1001 case 3:
1002 B->quadratic_to(p[1], p[2]);
1003 return routine_success;
1004 case 4:
1005 {
1006 int max_recursion(5);
1007 detail::add_cubic_adaptive(max_recursion, B, p, tol);
1008 return routine_success;
1009 }
1010 default:
1011 return routine_fail;
1012 }
1013}
1014
1015//////////////////////////////////////
1016// fastuidraw::PathContour::flat methods
1017bool
1018fastuidraw::PathContour::flat::
1019is_flat(void) const
1020{
1021 return true;
1022}
1023
1024fastuidraw::reference_counted_ptr<fastuidraw::PathContour::tessellation_state>
1025fastuidraw::PathContour::flat::
1026produce_tessellation(const TessellatedPath::TessellationParams &tess_params,
1027 TessellatedPath::SegmentStorage *out_data,
1028 float *out_max_distance) const
1029{
1030 FASTUIDRAWunused(tess_params);
1031
1032 out_data->add_line_segment(start_pt(), end_pt());
1033 *out_max_distance = 0.0f;
1034 return nullptr;
1035}
1036
1037fastuidraw::reference_counted_ptr<fastuidraw::PathContour::interpolator_base>
1038fastuidraw::PathContour::flat::
1039deep_copy(PathContour &contour) const
1040{
1041 return FASTUIDRAWnew flat(contour, end_pt(), edge_type());
1042}
1043
1044void
1045fastuidraw::PathContour::flat::
1046approximate_bounding_box(Rect *out_bb) const
1047{
1048 const vec2 &p0(start_pt());
1049 const vec2 &p1(end_pt());
1050
1051 out_bb->m_min_point.x() = fastuidraw::t_min(p0.x(), p1.x());
1052 out_bb->m_min_point.y() = fastuidraw::t_min(p0.y(), p1.y());
1053
1054 out_bb->m_max_point.x() = fastuidraw::t_max(p0.x(), p1.x());
1055 out_bb->m_max_point.y() = fastuidraw::t_max(p0.y(), p1.y());
1056}
1057
1058enum fastuidraw::return_code
1059fastuidraw::PathContour::flat::
1060add_to_builder(ShaderFilledPath::Builder *B, float) const
1061{
1062 B->line_to(end_pt());
1063 return routine_success;
1064}
1065
1066//////////////////////////////////////
1067// fastuidraw::PathContour::arc methods
1068fastuidraw::PathContour::arc::
1069arc(PathContour &contour,
1070 float angle, const vec2 &end, enum PathEnums::edge_type_t tp):
1071 fastuidraw::PathContour::interpolator_base(contour, end, tp)
1072{
1073 ArcPrivate *d;
1074 d = FASTUIDRAWnew ArcPrivate();
1075 m_d = d;
1076
1077 float angle_coeff_dir;
1078 vec2 end_start, mid, n;
1079 float s, c, t;
1080
1081 angle_coeff_dir = (angle > 0.0f) ? 1.0f : -1.0f;
1082
1083 /* find the center of the circle. The center is
1084 * on the perpindicular bisecter of start and end.
1085 * The perpindicular bisector is given by
1086 * { t*n + mid | t real }
1087 */
1088 angle = fastuidraw::t_abs(angle);
1089 end_start = end_pt() - start_pt();
1090 mid = (end_pt() + start_pt()) * 0.5f;
1091 n = vec2(-end_start.y(), end_start.x());
1092 s = fastuidraw::t_sin(angle * 0.5f);
1093 c = fastuidraw::t_cos(angle * 0.5f);
1094
1095 /* Let t be the point so that m_center = t*n + mid
1096 * Then
1097 * tan(angle/2) = 0.5 * ||end - start|| / || m_center - mid ||
1098 * = 0.5 * ||end - start|| / || t * n ||
1099 * = 0.5 * || n || / || t * n||
1100 * thus
1101 * |t| = 0.5/tan(angle/2) = 0.5 * c / s
1102 */
1103 t = angle_coeff_dir * 0.5f * c / s;
1104 d->m_center = mid + (t * n);
1105
1106 vec2 start_center(start_pt() - d->m_center);
1107
1108 d->m_radius = start_center.magnitude();
1109 d->m_start_angle = start_center.atan();
1110 d->m_angle_speed = angle_coeff_dir * angle;
1111
1112 d->m_bb.union_point(start_pt());
1113 d->m_bb.union_point(end_pt());
1114
1115 /* check for the extreme points of a circle in [-PI, PI]
1116 * which are at -PI, -PI / 2, 0, PI / 2, PI
1117 */
1118 float sa, ea;
1119 const fastuidraw::vec3 criticals[] =
1120 {
1121 fastuidraw::vec3(-1.0f, +0.0f, -FASTUIDRAW_PI),
1122 fastuidraw::vec3(+0.0f, -1.0f, -0.5f * FASTUIDRAW_PI),
1123 fastuidraw::vec3(+1.0f, +0.0f, 0.0f),
1124 fastuidraw::vec3(+0.0f, +1.0f, 0.5f * FASTUIDRAW_PI),
1125 fastuidraw::vec3(-1.0f, +0.0f, FASTUIDRAW_PI),
1126 };
1127
1128 sa = fastuidraw::t_min(d->m_start_angle, d->m_angle_speed + d->m_start_angle);
1129 ea = fastuidraw::t_max(d->m_start_angle, d->m_angle_speed + d->m_start_angle);
1130 for (unsigned int i = 0; i < 5; ++i)
1131 {
1132 if (sa <= criticals[i].z() && criticals[i].z() <= ea)
1133 {
1134 vec2 p;
1135 p = d->m_center + d->m_radius * fastuidraw::vec2(criticals[i].x(), criticals[i].y());
1136 d->m_bb.union_point(p);
1137 }
1138 }
1139}
1140
1141fastuidraw::PathContour::arc::
1142arc(const arc &q, PathContour &contour):
1143 fastuidraw::PathContour::interpolator_base(contour, q.end_pt(), q.edge_type())
1144{
1145 ArcPrivate *qd;
1146 qd = static_cast<ArcPrivate*>(q.m_d);
1147 m_d = FASTUIDRAWnew ArcPrivate(*qd);
1148}
1149
1150fastuidraw::PathContour::arc::
1151~arc()
1152{
1153 ArcPrivate *d;
1154 d = static_cast<ArcPrivate*>(m_d);
1155 FASTUIDRAWdelete(d);
1156 m_d = nullptr;
1157}
1158
1159fastuidraw::vec2
1160fastuidraw::PathContour::arc::
1161center(void) const
1162{
1163 ArcPrivate *d;
1164 d = static_cast<ArcPrivate*>(m_d);
1165 return d->m_center;
1166}
1167
1168fastuidraw::range_type<float>
1169fastuidraw::PathContour::arc::
1170angle(void) const
1171{
1172 ArcPrivate *d;
1173 d = static_cast<ArcPrivate*>(m_d);
1174 return range_type<float>(d->m_start_angle,
1175 d->m_start_angle + d->m_angle_speed);
1176}
1177
1178bool
1179fastuidraw::PathContour::arc::
1180is_flat(void) const
1181{
1182 return false;
1183}
1184
1185fastuidraw::reference_counted_ptr<fastuidraw::PathContour::tessellation_state>
1186fastuidraw::PathContour::arc::
1187produce_tessellation(const TessellatedPath::TessellationParams &tess_params,
1188 TessellatedPath::SegmentStorage *out_data,
1189 float *out_max_distance) const
1190{
1191 ArcPrivate *d;
1192
1193 d = static_cast<ArcPrivate*>(m_d);
1194 out_data->add_arc_segment(start_pt(), end_pt(),
1195 d->m_center, d->m_radius,
1196 range_type<float>(d->m_start_angle,
1197 d->m_start_angle + d->m_angle_speed));
1198 *out_max_distance = 0.0f;
1199 FASTUIDRAWunused(tess_params);
1200
1201 return nullptr;
1202}
1203
1204void
1205fastuidraw::PathContour::arc::
1206approximate_bounding_box(Rect *out_bb) const
1207{
1208 ArcPrivate *d;
1209 d = static_cast<ArcPrivate*>(m_d);
1210 out_bb->m_min_point = d->m_bb.min_point();
1211 out_bb->m_max_point = d->m_bb.max_point();
1212}
1213
1214fastuidraw::reference_counted_ptr<fastuidraw::PathContour::interpolator_base>
1215fastuidraw::PathContour::arc::
1216deep_copy(PathContour &contour) const
1217{
1218 return FASTUIDRAWnew arc(*this, contour);
1219}
1220
1221enum fastuidraw::return_code
1222fastuidraw::PathContour::arc::
1223add_to_builder(ShaderFilledPath::Builder *builder, float tol) const
1224{
1225 ArcPrivate *d;
1226 d = static_cast<ArcPrivate*>(m_d);
1227
1228 const int max_recursion(5);
1229 detail::add_arc_as_cubics(max_recursion, builder, tol,
1230 start_pt(), end_pt(), d->m_center,
1231 d->m_radius, d->m_start_angle, d->m_angle_speed);
1232 return routine_success;
1233}
1234
1235///////////////////////////////////
1236// fastuidraw::PathContour methods
1237fastuidraw::PathContour::
1238PathContour(void)
1239{
1240 m_d = FASTUIDRAWnew PathContourPrivate();
1241}
1242
1243fastuidraw::PathContour::
1244~PathContour(void)
1245{
1246 PathContourPrivate *d;
1247 d = static_cast<PathContourPrivate*>(m_d);
1248 FASTUIDRAWdelete(d);
1249 m_d = nullptr;
1250}
1251
1252void
1253fastuidraw::PathContour::
1254start(const vec2 &start_pt)
1255{
1256 PathContourPrivate *d;
1257 d = static_cast<PathContourPrivate*>(m_d);
1258
1259 FASTUIDRAWassert(d->m_interpolators.empty());
1260 FASTUIDRAWassert(!d->m_end_to_start);
1261
1262 d->m_start_pt = start_pt;
1263}
1264
1265void
1266fastuidraw::PathContour::
1267add_control_point(const fastuidraw::vec2 &pt)
1268{
1269 PathContourPrivate *d;
1270 d = static_cast<PathContourPrivate*>(m_d);
1271
1272 FASTUIDRAWassert(!d->m_end_to_start);
1273 d->m_current_control_points.push_back(pt);
1274}
1275
1276void
1277fastuidraw::PathContour::
1278clear_control_points(void)
1279{
1280 PathContourPrivate *d;
1281 d = static_cast<PathContourPrivate*>(m_d);
1282 d->m_current_control_points.clear();
1283}
1284
1285void
1286fastuidraw::PathContour::
1287to_point(const fastuidraw::vec2 &pt, enum PathEnums::edge_type_t etp)
1288{
1289 PathContourPrivate *d;
1290 d = static_cast<PathContourPrivate*>(m_d);
1291
1292 reference_counted_ptr<const interpolator_base> h;
1293
1294 if (d->m_current_control_points.empty())
1295 {
1296 h = FASTUIDRAWnew flat(*this, pt, etp);
1297 }
1298 else
1299 {
1300 h = FASTUIDRAWnew bezier(*this,
1301 make_c_array(d->m_current_control_points),
1302 pt, etp);
1303 }
1304 d->m_current_control_points.clear();
1305
1306 FASTUIDRAWassert(h == d->m_interpolators.back());
1307 FASTUIDRAWunused(h);
1308}
1309
1310void
1311fastuidraw::PathContour::
1312to_arc(float angle, const vec2 &pt, enum PathEnums::edge_type_t etp)
1313{
1314 reference_counted_ptr<const interpolator_base> h;
1315 PathContourPrivate *d;
1316
1317 d = static_cast<PathContourPrivate*>(m_d);
1318
1319 h = FASTUIDRAWnew arc(*this, angle, pt, etp);
1320 FASTUIDRAWassert(h == d->m_interpolators.back());
1321 FASTUIDRAWunused(h);
1322 FASTUIDRAWunused(d);
1323}
1324
1325void
1326fastuidraw::PathContour::
1327close_generic(void)
1328{
1329 PathContourPrivate *d;
1330 d = static_cast<PathContourPrivate*>(m_d);
1331
1332 FASTUIDRAWassert(!d->m_end_to_start);
1333 FASTUIDRAWassert(d->m_current_control_points.empty());
1334 FASTUIDRAWassert(!d->m_interpolators.empty());
1335 FASTUIDRAWassert(!d->m_ended);
1336 d->m_end_to_start = d->m_interpolators.back();
1337 d->m_ended = true;
1338}
1339
1340void
1341fastuidraw::PathContour::
1342end(void)
1343{
1344 PathContourPrivate *d;
1345 d = static_cast<PathContourPrivate*>(m_d);
1346
1347 FASTUIDRAWassert(!d->m_end_to_start);
1348 FASTUIDRAWassert(d->m_current_control_points.empty());
1349 FASTUIDRAWassert(!d->m_interpolators.empty());
1350 FASTUIDRAWassert(!d->m_ended);
1351 d->m_ended = true;
1352}
1353
1354void
1355fastuidraw::PathContour::
1356close(enum PathEnums::edge_type_t etp)
1357{
1358 PathContourPrivate *d;
1359 d = static_cast<PathContourPrivate*>(m_d);
1360
1361 to_point(d->m_start_pt, etp);
1362 close_generic();
1363}
1364
1365void
1366fastuidraw::PathContour::
1367close_arc(float angle, enum PathEnums::edge_type_t etp)
1368{
1369 PathContourPrivate *d;
1370 d = static_cast<PathContourPrivate*>(m_d);
1371
1372 to_arc(angle, d->m_start_pt, etp);
1373 close_generic();
1374}
1375
1376unsigned int
1377fastuidraw::PathContour::
1378number_points(void) const
1379{
1380 PathContourPrivate *d;
1381 unsigned int sz;
1382
1383 d = static_cast<PathContourPrivate*>(m_d);
1384 sz = d->m_interpolators.size();
1385 return (d->m_end_to_start) ? sz : sz + 1u;
1386}
1387
1388unsigned int
1389fastuidraw::PathContour::
1390number_interpolators(void) const
1391{
1392 PathContourPrivate *d;
1393 d = static_cast<PathContourPrivate*>(m_d);
1394 return d->m_interpolators.size();
1395}
1396
1397const fastuidraw::vec2&
1398fastuidraw::PathContour::
1399point(unsigned int I) const
1400{
1401 PathContourPrivate *d;
1402 d = static_cast<PathContourPrivate*>(m_d);
1403 return (I == 0) ?
1404 d->m_start_pt:
1405 d->m_interpolators[I - 1]->end_pt();
1406}
1407
1408const fastuidraw::reference_counted_ptr<const fastuidraw::PathContour::interpolator_base>&
1409fastuidraw::PathContour::
1410interpolator(unsigned int I) const
1411{
1412 PathContourPrivate *d;
1413 d = static_cast<PathContourPrivate*>(m_d);
1414
1415 /* m_interpolator[I] connects point(I) to point(I + 1). */
1416 return d->m_interpolators[I];
1417}
1418
1419const fastuidraw::reference_counted_ptr<const fastuidraw::PathContour::interpolator_base>&
1420fastuidraw::PathContour::
1421prev_interpolator(void)
1422{
1423 PathContourPrivate *d;
1424 d = static_cast<PathContourPrivate*>(m_d);
1425
1426 return (d->m_interpolators.empty()) ?
1427 d->m_null_interpolator:
1428 d->m_interpolators.back();
1429}
1430
1431bool
1432fastuidraw::PathContour::
1433closed(void) const
1434{
1435 PathContourPrivate *d;
1436 d = static_cast<PathContourPrivate*>(m_d);
1437
1438 return d->m_end_to_start;
1439}
1440
1441bool
1442fastuidraw::PathContour::
1443ended(void) const
1444{
1445 PathContourPrivate *d;
1446 d = static_cast<PathContourPrivate*>(m_d);
1447
1448 return d->m_ended;
1449}
1450
1451bool
1452fastuidraw::PathContour::
1453is_flat(void) const
1454{
1455 PathContourPrivate *d;
1456 d = static_cast<PathContourPrivate*>(m_d);
1457 return d->is_flat();
1458}
1459
1460fastuidraw::reference_counted_ptr<fastuidraw::PathContour>
1461fastuidraw::PathContour::
1462deep_copy(void) const
1463{
1464 fastuidraw::reference_counted_ptr<PathContour> return_value;
1465 return_value = FASTUIDRAWnew PathContour();
1466
1467 PathContourPrivate *d, *r;
1468 d = static_cast<PathContourPrivate*>(m_d);
1469 r = static_cast<PathContourPrivate*>(return_value->m_d);
1470
1471 r->m_start_pt = d->m_start_pt;
1472 r->m_current_control_points = d->m_current_control_points;
1473
1474 /* now we need to do the deep copies of the interpolator. eww. */
1475 r->m_interpolators.reserve(d->m_interpolators.size());
1476 for(unsigned int i = 0, endi = d->m_interpolators.size(); i < endi; ++i)
1477 {
1478 reference_counted_ptr<interpolator_base> tmp;
1479
1480 tmp = d->m_interpolators[i]->deep_copy(*return_value);
1481 FASTUIDRAWassert(tmp == r->m_interpolators.back());
1482 FASTUIDRAWassert(tmp == r->m_interpolators[i]);
1483 FASTUIDRAWassert(tmp->start_pt() == d->m_interpolators[i]->start_pt());
1484 FASTUIDRAWassert(tmp->end_pt() == d->m_interpolators[i]->end_pt());
1485 }
1486
1487 r->m_ended = d->m_ended;
1488 if (d->m_end_to_start)
1489 {
1490 FASTUIDRAWassert(d->m_end_to_start == d->m_interpolators.back());
1491 r->m_end_to_start = r->m_interpolators.back();
1492 }
1493 return return_value;
1494}
1495
1496bool
1497fastuidraw::PathContour::
1498approximate_bounding_box(Rect *out_bb) const
1499{
1500 PathContourPrivate *d;
1501 d = static_cast<PathContourPrivate*>(m_d);
1502
1503 const BoundingBox<float> &bb(d->bb());
1504 out_bb->m_min_point = bb.min_point();
1505 out_bb->m_max_point = bb.max_point();
1506
1507 return !bb.empty();
1508}
1509
1510/////////////////////////////////
1511// TessellatedPathList methods
1512const typename TessellatedPathList::TessellatedPathRef&
1513TessellatedPathList::
1514tessellation(const fastuidraw::Path &path, float max_distance)
1515{
1516 using namespace fastuidraw;
1517 using namespace detail;
1518
1519 if (m_data.empty())
1520 {
1521 TessellationParams params;
1522 m_data.push_back(FASTUIDRAWnew TessellatedPath(path, params, &m_refiner));
1523 }
1524
1525 if (max_distance <= 0.0 || path.is_flat())
1526 {
1527 return m_data.front();
1528 }
1529
1530 if (m_data.back()->max_distance() <= max_distance)
1531 {
1532 typename std::vector<TessellatedPathRef>::const_iterator iter;
1533 iter = std::lower_bound(m_data.begin(),
1534 m_data.end(),
1535 max_distance,
1536 reverse_compare_max_distance);
1537
1538 FASTUIDRAWassert(iter != m_data.end());
1539 FASTUIDRAWassert(*iter);
1540 FASTUIDRAWassert((*iter)->max_distance() <= max_distance);
1541 return *iter;
1542 }
1543
1544 if (m_done)
1545 {
1546 return m_data.back();
1547 }
1548
1549 float current_max_distance;
1550
1551 current_max_distance = m_data.back()->max_distance();
1552
1553 while(!m_done && m_data.back()->max_distance() > max_distance)
1554 {
1555 current_max_distance *= 0.5f;
1556 while(!m_done && m_data.back()->max_distance() > current_max_distance)
1557 {
1558 TessellatedPathRef ref;
1559
1560 m_refiner->refine_tessellation(current_max_distance, 1);
1561 ref = m_refiner->tessellated_path();
1562
1563 /* we only add a tessellation if it is finer than the last one
1564 * added. However, we do not abort if it is not as sometimes
1565 * (especially with arc-tessellation) more refinement can make
1566 * the tessellation improve.
1567 */
1568 if (m_data.back()->max_distance() > ref->max_distance())
1569 {
1570 m_data.push_back(ref);
1571 }
1572
1573 /* We set an absolute abort at max_refine_recursion_limit
1574 * which represents that after sub-dividing that much, one
1575 * is just handling numerical garbage.
1576 */
1577 if (ref->max_recursion() > MAX_REFINE_RECURSION_LIMIT)
1578 {
1579 m_done = true;
1580 m_refiner = nullptr;
1581 }
1582 }
1583 }
1584
1585 return m_data.back();
1586}
1587
1588/////////////////////////////////
1589// PathPrivate methods
1590PathPrivate::
1591PathPrivate(void):
1592 m_next_edge_type(fastuidraw::PathEnums::starts_new_edge),
1593 m_tess_list(),
1594 m_start_check_bb(0),
1595 m_is_flat(true)
1596{
1597}
1598
1599const fastuidraw::reference_counted_ptr<fastuidraw::PathContour>&
1600PathPrivate::
1601current_contour(void)
1602{
1603 start_contour_if_necessary();
1604 FASTUIDRAWassert(!m_contours.empty());
1605 clear_tesses();
1606 return m_contours.back();
1607}
1608
1609void
1610PathPrivate::
1611move_common(const fastuidraw::vec2 &pt)
1612{
1613 bool last_contour_flat;
1614
1615 clear_tesses();
1616 last_contour_flat = m_contours.empty() || m_contours.back()->is_flat();
1617 m_is_flat = m_is_flat && last_contour_flat;
1618 if (!m_contours.empty() && !m_contours.back()->ended())
1619 {
1620 m_contours.back()->end();
1621 }
1622 m_contours.push_back(FASTUIDRAWnew fastuidraw::PathContour());
1623 m_contours.back()->start(pt);
1624}
1625
1626void
1627PathPrivate::
1628clear_tesses(void)
1629{
1630 m_shader_filled_path.clear();
1631 m_tess_list.clear();
1632}
1633
1634void
1635PathPrivate::
1636start_contour_if_necessary(void)
1637{
1638 if (!m_contours.empty() && !m_contours.back()->ended())
1639 {
1640 return;
1641 }
1642
1643 fastuidraw::vec2 pt;
1644 if (m_contours.empty())
1645 {
1646 pt = fastuidraw::vec2(0.0f, 0.0f);
1647 }
1648 else
1649 {
1650 pt = m_contours.back()->point(m_contours.back()->number_points() - 1);
1651 }
1652 move_common(pt);
1653}
1654
1655/////////////////////////////////////////
1656// fastuidraw::Path methods
1657fastuidraw::Path::
1658Path(void)
1659{
1660 m_d = FASTUIDRAWnew PathPrivate();
1661}
1662
1663fastuidraw::Path::
1664~Path()
1665{
1666 PathPrivate *d;
1667 d = static_cast<PathPrivate*>(m_d);
1668 FASTUIDRAWdelete(d);
1669 m_d = nullptr;
1670}
1671
1672void
1673fastuidraw::Path::
1674swap(Path &obj)
1675{
1676 std::swap(obj.m_d, m_d);
1677}
1678
1679bool
1680fastuidraw::Path::
1681is_flat(void) const
1682{
1683 bool last_contour_flat;
1684 PathPrivate *d;
1685
1686 d = static_cast<PathPrivate*>(m_d);
1687 last_contour_flat = d->m_contours.empty() || d->m_contours.back()->is_flat();
1688 return d->m_is_flat && last_contour_flat;
1689}
1690
1691void
1692fastuidraw::Path::
1693clear(void)
1694{
1695 PathPrivate *d;
1696 d = static_cast<PathPrivate*>(m_d);
1697 d->clear_tesses();
1698 d->m_contours.clear();
1699 d->m_start_check_bb = 0u;
1700}
1701
1702fastuidraw::Path&
1703fastuidraw::Path::
1704add_contour(const reference_counted_ptr<const PathContour> &pcontour)
1705{
1706 PathPrivate *d;
1707 d = static_cast<PathPrivate*>(m_d);
1708
1709 reference_counted_ptr<PathContour> contour, r;
1710
1711 contour = pcontour.const_cast_ptr<PathContour>();
1712 if (!contour->ended())
1713 {
1714 contour = contour->deep_copy();
1715 }
1716
1717 d->m_is_flat = d->m_is_flat && contour->is_flat();
1718 d->clear_tesses();
1719
1720 if (!d->m_contours.empty())
1721 {
1722 r = d->m_contours.back();
1723 d->m_contours.back() = contour;
1724 d->m_contours.push_back(r);
1725 }
1726 else
1727 {
1728 d->m_contours.push_back(contour);
1729 }
1730
1731 return *this;
1732}
1733
1734fastuidraw::Path&
1735fastuidraw::Path::
1736add_contours(const Path &path)
1737{
1738 PathPrivate *d, *pd;
1739 reference_counted_ptr<PathContour> r;
1740
1741 d = static_cast<PathPrivate*>(m_d);
1742 pd = static_cast<PathPrivate*>(path.m_d);
1743 if (pd->m_contours.empty())
1744 {
1745 return *this;
1746 }
1747
1748 if (!d->m_contours.empty())
1749 {
1750 r = d->m_contours.back();
1751 d->m_contours.pop_back();
1752 }
1753
1754 for (reference_counted_ptr<PathContour> c : pd->m_contours)
1755 {
1756 d->m_is_flat = d->m_is_flat && c->is_flat();
1757 if (!c->ended())
1758 {
1759 c = c->deep_copy();
1760 c->end();
1761 }
1762 d->m_contours.push_back(c);
1763 }
1764
1765 if (r)
1766 {
1767 d->m_contours.push_back(r);
1768 }
1769
1770 d->clear_tesses();
1771 return *this;
1772}
1773
1774fastuidraw::Path&
1775fastuidraw::Path::
1776move(const fastuidraw::vec2 &pt)
1777{
1778 PathPrivate *d;
1779 d = static_cast<PathPrivate*>(m_d);
1780 d->move_common(pt);
1781 return *this;
1782}
1783
1784fastuidraw::Path&
1785fastuidraw::Path::
1786end_contour(void)
1787{
1788 PathPrivate *d;
1789 d = static_cast<PathPrivate*>(m_d);
1790 const reference_counted_ptr<PathContour> &h(d->current_contour());
1791 h->end();
1792 return *this;
1793}
1794
1795fastuidraw::Path&
1796fastuidraw::Path::
1797close_contour(enum PathEnums::edge_type_t etp)
1798{
1799 PathPrivate *d;
1800 d = static_cast<PathPrivate*>(m_d);
1801 const reference_counted_ptr<PathContour> &h(d->current_contour());
1802 h->close(etp);
1803 return *this;
1804}
1805
1806fastuidraw::Path&
1807fastuidraw::Path::
1808operator<<(enum PathEnums::edge_type_t etp)
1809{
1810 PathPrivate *d;
1811 d = static_cast<PathPrivate*>(m_d);
1812 d->m_next_edge_type = etp;
1813 return *this;
1814}
1815
1816fastuidraw::Path&
1817fastuidraw::Path::
1818operator<<(const fastuidraw::vec2 &pt)
1819{
1820 PathPrivate *d;
1821 d = static_cast<PathPrivate*>(m_d);
1822
1823 if (d->m_contours.empty() || d->m_contours.back()->closed())
1824 {
1825 d->move_common(pt);
1826 }
1827 else
1828 {
1829 d->current_contour()->to_point(pt, d->m_next_edge_type);
1830 }
1831 d->m_next_edge_type = PathEnums::starts_new_edge;
1832 return *this;
1833}
1834
1835const fastuidraw::TessellatedPath&
1836fastuidraw::Path::
1837tessellation(void) const
1838{
1839 return tessellation(-1.0f);
1840}
1841
1842const fastuidraw::TessellatedPath&
1843fastuidraw::Path::
1844tessellation(float max_distance) const
1845{
1846 PathPrivate *d;
1847 d = static_cast<PathPrivate*>(m_d);
1848 return *d->m_tess_list.tessellation(*this, max_distance);
1849}
1850
1851bool
1852fastuidraw::Path::
1853approximate_bounding_box(Rect *out_bb) const
1854{
1855 PathPrivate *d;
1856 d = static_cast<PathPrivate*>(m_d);
1857
1858 for(unsigned endi = d->m_contours.size();
1859 d->m_start_check_bb < endi; ++d->m_start_check_bb)
1860 {
1861 Rect R;
1862
1863 if(d->m_contours[d->m_start_check_bb]->approximate_bounding_box(&R))
1864 {
1865 d->m_bb.union_point(R.m_min_point);
1866 d->m_bb.union_point(R.m_max_point);
1867 }
1868 }
1869
1870 out_bb->m_min_point = d->m_bb.min_point();
1871 out_bb->m_max_point = d->m_bb.max_point();
1872 return !d->m_bb.empty();
1873}
1874
1875fastuidraw::Path&
1876fastuidraw::Path::
1877operator<<(const control_point &pt)
1878{
1879 PathPrivate *d;
1880 d = static_cast<PathPrivate*>(m_d);
1881 d->current_contour()->add_control_point(pt.m_location);
1882 return *this;
1883}
1884
1885fastuidraw::Path&
1886fastuidraw::Path::
1887operator<<(const arc &a)
1888{
1889 PathPrivate *d;
1890 d = static_cast<PathPrivate*>(m_d);
1891 d->current_contour()->to_arc(a.m_angle, a.m_pt, d->m_next_edge_type);
1892 d->m_next_edge_type = PathEnums::starts_new_edge;
1893 return *this;
1894}
1895
1896fastuidraw::Path&
1897fastuidraw::Path::
1898operator<<(contour_close)
1899{
1900 PathPrivate *d;
1901 d = static_cast<PathPrivate*>(m_d);
1902 d->current_contour()->close(d->m_next_edge_type);
1903 d->m_next_edge_type = PathEnums::starts_new_edge;
1904 return *this;
1905}
1906
1907fastuidraw::Path&
1908fastuidraw::Path::
1909operator<<(contour_end)
1910{
1911 PathPrivate *d;
1912 d = static_cast<PathPrivate*>(m_d);
1913 d->current_contour()->end();
1914 d->m_next_edge_type = PathEnums::starts_new_edge;
1915 return *this;
1916}
1917
1918fastuidraw::Path&
1919fastuidraw::Path::
1920operator<<(contour_close_arc a)
1921{
1922 PathPrivate *d;
1923 d = static_cast<PathPrivate*>(m_d);
1924 d->current_contour()->close_arc(a.m_angle, d->m_next_edge_type);
1925 d->m_next_edge_type = PathEnums::starts_new_edge;
1926 return *this;
1927}
1928
1929fastuidraw::Path&
1930fastuidraw::Path::
1931line_to(const vec2 &pt,
1932 enum PathEnums::edge_type_t etp)
1933{
1934 PathPrivate *d;
1935 d = static_cast<PathPrivate*>(m_d);
1936 d->current_contour()->to_point(pt, etp);
1937 return *this;
1938}
1939
1940fastuidraw::Path&
1941fastuidraw::Path::
1942quadratic_to(const vec2 &ct, const vec2 &pt,
1943 enum PathEnums::edge_type_t etp)
1944{
1945 PathPrivate *d;
1946 d = static_cast<PathPrivate*>(m_d);
1947 const reference_counted_ptr<PathContour> &h(d->current_contour());
1948 h->clear_control_points();
1949 h->add_control_point(ct);
1950 h->to_point(pt, etp);
1951 return *this;
1952}
1953
1954fastuidraw::Path&
1955fastuidraw::Path::
1956cubic_to(const vec2 &ct1, const vec2 &ct2, const vec2 &pt,
1957 enum PathEnums::edge_type_t etp)
1958{
1959 PathPrivate *d;
1960 d = static_cast<PathPrivate*>(m_d);
1961 const reference_counted_ptr<PathContour> &h(d->current_contour());
1962 h->clear_control_points();
1963 h->add_control_point(ct1);
1964 h->add_control_point(ct2);
1965 h->to_point(pt, etp);
1966 return *this;
1967}
1968
1969fastuidraw::Path&
1970fastuidraw::Path::
1971arc_to(float angle, const vec2 &pt,
1972 enum PathEnums::edge_type_t etp)
1973{
1974 PathPrivate *d;
1975 d = static_cast<PathPrivate*>(m_d);
1976 const reference_counted_ptr<PathContour> &h(d->current_contour());
1977 h->to_arc(angle, pt, etp);
1978 return *this;
1979}
1980
1981fastuidraw::Path&
1982fastuidraw::Path::
1983close_contour_arc(float angle,
1984 enum PathEnums::edge_type_t etp)
1985{
1986 PathPrivate *d;
1987 d = static_cast<PathPrivate*>(m_d);
1988 const reference_counted_ptr<PathContour> &h(d->current_contour());
1989 h->close_arc(angle, etp);
1990 return *this;
1991}
1992
1993fastuidraw::Path&
1994fastuidraw::Path::
1995close_contour_quadratic(const vec2 &ct,
1996 enum PathEnums::edge_type_t etp)
1997{
1998 PathPrivate *d;
1999 d = static_cast<PathPrivate*>(m_d);
2000 const reference_counted_ptr<PathContour> &h(d->current_contour());
2001 h->clear_control_points();
2002 h->add_control_point(ct);
2003 h->close(etp);
2004 return *this;
2005}
2006
2007fastuidraw::Path&
2008fastuidraw::Path::
2009close_contour_cubic(const vec2 &ct1, const vec2 &ct2,
2010 enum PathEnums::edge_type_t etp)
2011{
2012 PathPrivate *d;
2013 d = static_cast<PathPrivate*>(m_d);
2014 const reference_counted_ptr<PathContour> &h(d->current_contour());
2015 h->clear_control_points();
2016 h->add_control_point(ct1);
2017 h->add_control_point(ct2);
2018 h->close(etp);
2019 return *this;
2020}
2021
2022fastuidraw::PathContour&
2023fastuidraw::Path::
2024current_contour(void)
2025{
2026 PathPrivate *d;
2027 d = static_cast<PathPrivate*>(m_d);
2028 return *d->current_contour();
2029}
2030
2031unsigned int
2032fastuidraw::Path::
2033number_contours(void) const
2034{
2035 PathPrivate *d;
2036 d = static_cast<PathPrivate*>(m_d);
2037 return d->m_contours.size();
2038}
2039
2040fastuidraw::reference_counted_ptr<const fastuidraw::PathContour>
2041fastuidraw::Path::
2042contour(unsigned int i) const
2043{
2044 PathPrivate *d;
2045 d = static_cast<PathPrivate*>(m_d);
2046 return d->m_contours[i];
2047}
2048
2049const fastuidraw::ShaderFilledPath&
2050fastuidraw::Path::
2051shader_filled_path(void) const
2052{
2053 PathPrivate *d;
2054 d = static_cast<PathPrivate*>(m_d);
2055
2056 if (!d->m_shader_filled_path)
2057 {
2058 ShaderFilledPath::Builder B;
2059 vec2 bb_sz(d->m_bb.size());
2060 const float rel_tol(1e-4);
2061 float tol;
2062
2063 tol = rel_tol * fastuidraw::t_min(bb_sz.x(), bb_sz.y());
2064 B.add_path(tol, *this);
2065 d->m_shader_filled_path = FASTUIDRAWnew ShaderFilledPath(B);
2066 }
2067 return *d->m_shader_filled_path;
2068}
2069