Flutter Impeller
stroke_path_geometry.cc
Go to the documentation of this file.
1 // Copyright 2013 The Flutter Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
6 
7 #include "flutter/display_list/geometry/dl_path.h"
17 
18 namespace impeller {
19 
20 namespace {
21 
22 class PositionWriter {
23  public:
24  explicit PositionWriter(std::vector<Point>& points)
25  : points_(points), oversized_() {
26  FML_DCHECK(points_.size() == kPointArenaSize);
27  }
28 
29  void AppendVertex(const Point& point) {
30  if (offset_ >= kPointArenaSize) {
31  oversized_.push_back(point);
32  } else {
33  points_[offset_++] = point;
34  }
35  }
36 
37  /// @brief Return the number of points used in the arena, followed by
38  /// the number of points allocated in the overized buffer.
39  std::pair<size_t, size_t> GetUsedSize() const {
40  return std::make_pair(offset_, oversized_.size());
41  }
42 
43  bool HasOversizedBuffer() const { return !oversized_.empty(); }
44 
45  const std::vector<Point>& GetOversizedBuffer() const { return oversized_; }
46 
47  private:
48  std::vector<Point>& points_;
49  std::vector<Point> oversized_;
50  size_t offset_ = 0u;
51 };
52 
53 } // namespace
54 
55 /// StrokePathSegmentReceiver converts path segments (fed by PathTessellator)
56 /// into a vertex strip that covers the outline of the stroked version of the
57 /// path and feeds those vertices, expressed in the form of a vertex strip
58 /// into the supplied PositionWriter.
59 ///
60 /// The general procedure follows the following basic methodology:
61 ///
62 /// Every path segment is represented by a box with two starting vertices
63 /// perpendicular to its start point and two vertices perpendicular to its
64 /// end point, all perpendiculars of length (stroke_width * 0.5).
65 ///
66 /// Joins will connect the ending "box" perpendiculars of the previous segment
67 /// to the starting "box" perpendiculars of the following segment. If the two
68 /// boxes are so aligned that their adjacent perpendiculars are less than a
69 /// threshold distance apart (kJoinPixelThreshold), the join will just be
70 /// elided so that the end of one box becomes the start of the next box.
71 /// If the join process does add decorations, it assumes that the ending
72 /// perpendicular vertices from the prior segment are the last vertices
73 /// added and ensures that it appends the two vertices for the starting
74 /// perpendiculars of the new segment's "box". Thus every join either
75 /// adds nothing and the end perpendiculars of the previous segment become
76 /// the start perpendiculars of the next segment, or it makes sure its
77 /// geometry fills in the gap and ends with the start perpendiculars for the
78 /// new segment.
79 ///
80 /// Prior to the start of an unclosed contour we insert a cap and also the
81 /// starting perpendicular segments for the first segment. Prior to the
82 /// start of a closed contour, we just insert the starting perpendiculars
83 /// for the first segment. Either way, we've initialized the path with the
84 /// starting perpendiculars of the first segment.
85 ///
86 /// After the last segment in an unclosed contour we insert a cap which
87 /// can assume that the last segment has already inserted its closing
88 /// perpendicular segments. After the last segment in a closed contour, we
89 /// insert a join back to the very first segment in that contour.
90 ///
91 /// Connecting any two contours we insert an infinitely thin connecting
92 /// thread by inserting the last point of the previous contour twice and
93 /// then inserting the first point of the next contour twice. This ensures
94 /// that there are no non-empty triangles between the two contours.
95 ///
96 /// Finally, inserting a line segment can assume that the starting
97 /// perpendiculars have already been inserted by the preceding cap, join,
98 /// or prior segment, so all it needs to do is to insert the ending
99 /// perpendiculars which set the process up for the subsequent cap, join,
100 /// or future segment.
101 ///
102 /// Inserting curve segments acts like a series of line segments except
103 /// that the opening perpendicular is taken from the curve rather than the
104 /// direction between the starting point and the first sample point. This
105 /// ensures that any cap or join will be aligned with the curve and not
106 /// tilted by the first approximating segment. The same is true of the
107 /// ending perpendicular which is taken from the curve and not the last
108 /// approximated segment. Between each approximated segment of the curve,
109 /// we insert only Cap::kRound joins so as not to polygonize a curve when
110 /// it turns very sharply. We also skip these joins for any change of
111 /// direction which is smaller than the first sample point of a round join
112 /// for performance reasons.
113 ///
114 /// To facilitate all of that work we maintain variables containing
115 /// SeparatedVector2 values that, by convention, point 90 degrees to the
116 /// right of the given path direction. This facilitates a quick add/subtract
117 /// from the point on the path to insert the necessary perpendicular
118 /// points of a segment's box. These values contain both a unit vector for
119 /// direction and a magnitude for length.
120 ///
121 /// SeparatedVector2 values also allow us to quickly test limits on when to
122 /// include joins by using a simple dot product on the previous and next
123 /// perpendiculars at a given path point which should match the dot product
124 /// of the path's direction itself at the same point since both perpendiculars
125 /// have been rotated identically to the same side of the path.
126 /// The SeparatedVector2 will perform the dot product on the unit-length
127 /// vectors so that the result is exactly the cosine of the angle between the
128 /// segments - also the angle by which the path turned at a given path point.
129 ///
130 /// @see PathTessellator::PathToStrokedSegments
132  public:
134  PositionWriter& vtx_builder,
135  const StrokeParameters& stroke,
136  const Scalar scale)
137  : tessellator_(tessellator),
138  vtx_builder_(vtx_builder),
139  half_stroke_width_(stroke.width * 0.5f),
140  maximum_join_cosine_(
141  ComputeMaximumJoinCosine(scale, half_stroke_width_)),
142  minimum_miter_cosine_(ComputeMinimumMiterCosine(stroke.miter_limit)),
143  join_(stroke.join),
144  cap_(stroke.cap),
145  scale_(scale),
146  trigs_(MakeTrigs(tessellator, scale, half_stroke_width_)) {
147  // Trigs ensures that it always contains at least 2 entries.
148  FML_DCHECK(trigs_.size() >= 2);
149  FML_DCHECK(trigs_[0].cos == 1.0f); // Angle == 0 degrees
150  FML_DCHECK(trigs_[0].sin == 0.0f);
151  FML_DCHECK(trigs_.end()[-1].cos == 0.0f); // Angle == 90 degrees
152  FML_DCHECK(trigs_.end()[-1].sin == 1.0f);
153  }
154 
155  protected:
156  // |SegmentReceiver|
157  void BeginContour(Point origin, bool will_be_closed) override {
158  if (has_prior_contour_ && origin != last_point_) {
159  // We only append these extra points if we have had a prior contour.
160  vtx_builder_.AppendVertex(last_point_);
161  vtx_builder_.AppendVertex(last_point_);
162  vtx_builder_.AppendVertex(origin);
163  vtx_builder_.AppendVertex(origin);
164  }
165  has_prior_contour_ = true;
166  has_prior_segment_ = false;
167  contour_needs_cap_ = !will_be_closed;
168  last_point_ = origin;
169  origin_point_ = origin;
170  }
171 
172  // |SegmentReceiver|
173  void RecordLine(Point p1, Point p2) override {
174  if (p2 != p1) {
175  SeparatedVector2 current_perpendicular = PerpendicularFromPoints(p1, p2);
176 
177  HandlePreviousJoin(current_perpendicular);
178  AppendVertices(p2, current_perpendicular);
179 
180  last_perpendicular_ = current_perpendicular;
181  last_point_ = p2;
182  }
183  }
184 
185  // |SegmentReceiver|
186  void RecordQuad(Point p1, Point cp, Point p2) override {
187  RecordCurve<PathTessellator::Quad>({p1, cp, p2});
188  }
189 
190  // |SegmentReceiver|
191  void RecordConic(Point p1, Point cp, Point p2, Scalar weight) override {
192  RecordCurve<PathTessellator::Conic>({p1, cp, p2, weight});
193  }
194 
195  // |SegmentReceiver|
196  void RecordCubic(Point p1, Point cp1, Point cp2, Point p2) override {
197  RecordCurve<PathTessellator::Cubic>({p1, cp1, cp2, p2});
198  }
199 
200  // Utility implementation of |SegmentReceiver| Record<Curve> methods
201  template <typename Curve>
202  inline void RecordCurve(const Curve& curve) {
203  std::optional<Point> start_direction = curve.GetStartDirection();
204  std::optional<Point> end_direction = curve.GetEndDirection();
205 
206  // The Prune receiver should have eliminated any empty curves, so any
207  // curve we see should have both start and end direction.
208  FML_DCHECK(start_direction.has_value() && end_direction.has_value());
209 
210  // In order to keep the compiler/lint happy we check for values anyway.
211  if (start_direction.has_value() && end_direction.has_value()) {
212  // We now know the curve cannot be degenerate.
213  SeparatedVector2 start_perpendicular =
214  PerpendicularFromUnitDirection(-start_direction.value());
215  SeparatedVector2 end_perpendicular =
216  PerpendicularFromUnitDirection(end_direction.value());
217 
218  // We join the previous segment to this one with a normal join
219  // The join will append the perpendicular at the start of this
220  // curve as well.
221  HandlePreviousJoin(start_perpendicular);
222 
223  Scalar count =
224  std::ceilf(curve.SubdivisionCount(scale_ * half_stroke_width_));
225 
226  Point prev = curve.p1;
227  SeparatedVector2 prev_perpendicular = start_perpendicular;
228 
229  // Handle all intermediate curve points up to but not including the end.
230  for (int i = 1; i < count; i++) {
231  Point cur = curve.Solve(i / count);
232  SeparatedVector2 cur_perpendicular = PerpendicularFromPoints(prev, cur);
233  RecordCurveSegment(prev_perpendicular, cur, cur_perpendicular);
234  prev = cur;
235  prev_perpendicular = cur_perpendicular;
236  }
237 
238  RecordCurveSegment(prev_perpendicular, curve.p2, end_perpendicular);
239 
240  last_perpendicular_ = end_perpendicular;
241  last_point_ = curve.p2;
242  }
243  }
244 
245  void RecordCurveSegment(const SeparatedVector2& prev_perpendicular,
246  const Point cur,
247  const SeparatedVector2& cur_perpendicular) {
248  if (prev_perpendicular.GetAlignment(cur_perpendicular) < trigs_[1].cos) {
249  // We only connect 2 curved segments if their change in direction
250  // is faster than a single sample of a round join.
251  AppendVertices(cur, prev_perpendicular);
252  AddJoin(Join::kRound, cur, prev_perpendicular, cur_perpendicular);
253  }
254  AppendVertices(cur, cur_perpendicular);
255  }
256 
257  // |SegmentReceiver|
258  void EndContour(Point origin, bool with_close) override {
259  FML_DCHECK(origin == origin_point_);
260  if (!has_prior_segment_) {
261  // Empty contour, fill in an axis aligned "cap box" at the origin.
262  FML_DCHECK(last_point_ == origin);
263  // kButt wouldn't fill anything so it defers to kSquare by convention.
264  Cap cap = (cap_ == Cap::kButt) ? Cap::kSquare : cap_;
265  Vector2 perpendicular = {-half_stroke_width_, 0};
266  AddCap(cap, origin, perpendicular, true);
267  if (cap == Cap::kRound) {
268  // Only round caps need the perpendicular between them to connect.
269  AppendVertices(origin, perpendicular);
270  }
271  AddCap(cap, origin, perpendicular, false);
272  } else if (with_close) {
273  // Closed contour, join back to origin.
274  FML_DCHECK(origin == origin_point_);
275  FML_DCHECK(last_point_ == origin);
276  AddJoin(join_, origin, last_perpendicular_, origin_perpendicular_);
277 
278  last_perpendicular_ = origin_perpendicular_;
279  last_point_ = origin;
280  } else {
281  AddCap(cap_, last_point_, last_perpendicular_.GetVector(), false);
282  }
283  has_prior_segment_ = false;
284  }
285 
286  // |PathAndArcSegmentReceiver|
287  void RecordArc(const Arc& arc,
288  const Point center,
289  const Size radii) override {
290  Tessellator::Trigs trigs =
291  tessellator_.GetTrigsForDeviceRadius(scale_ * radii.MaxDimension());
292  Arc::Iteration iterator = arc.ComputeIterations(trigs.GetSteps(), false);
293 
294  SeparatedVector2 prev_perpendicular =
295  PerpendicularFromUnitDirection({-iterator.start.y, iterator.start.x});
296  HandlePreviousJoin(prev_perpendicular);
297 
298  for (size_t i = 0u; i < iterator.quadrant_count; i++) {
299  Arc::Iteration::Quadrant quadrant = iterator.quadrants[i];
300  for (size_t j = quadrant.start_index; j < quadrant.end_index; j++) {
301  Vector2 direction = trigs[j] * quadrant.axis;
302  Point cur = center + direction * radii;
303  SeparatedVector2 cur_perpendicular =
304  PerpendicularFromUnitDirection({-direction.y, direction.x});
305  RecordCurveSegment(prev_perpendicular, cur, cur_perpendicular);
306  prev_perpendicular = cur_perpendicular;
307  }
308  }
309 
310  SeparatedVector2 end_perpendicular =
311  PerpendicularFromUnitDirection({-iterator.end.y, iterator.end.x});
312  Point end = center + iterator.end * radii;
313  RecordCurveSegment(prev_perpendicular, end, end_perpendicular);
314 
315  last_perpendicular_ = end_perpendicular;
316  last_point_ = end;
317  }
318 
319  private:
320  Tessellator& tessellator_;
321  PositionWriter& vtx_builder_;
322  const Scalar half_stroke_width_;
323  const Scalar maximum_join_cosine_;
324  const Scalar minimum_miter_cosine_;
325  const Join join_;
326  const Cap cap_;
327  const Scalar scale_;
328  const Tessellator::Trigs trigs_;
329 
330  SeparatedVector2 origin_perpendicular_;
331  Point origin_point_;
332  SeparatedVector2 last_perpendicular_;
333  Point last_point_;
334  bool has_prior_contour_ = false;
335  bool has_prior_segment_ = false;
336  bool contour_needs_cap_ = false;
337 
338  static Tessellator::Trigs MakeTrigs(Tessellator& tessellator,
339  Scalar scale,
340  Scalar half_stroke_width) {
341  return tessellator.GetTrigsForDeviceRadius(scale * half_stroke_width);
342  }
343 
344  // Half of the allowed distance between the ends of the perpendiculars.
345  static constexpr Scalar kJoinPixelThreshold = 0.25f;
346 
347  /// Determine the cosine of the angle where the ends of 2 vectors that are
348  /// each as long as half of the stroke width, differ by less than the
349  /// kJoinPixelThreshold.
350  ///
351  /// Any angle between 2 segments in the path for which the cosine of that
352  /// angle is greater than this return value, do not need any kind of join
353  /// geometry. The angle between the segments can be quickly computed by
354  /// the dot product of their direction vectors.
355  static Scalar ComputeMaximumJoinCosine(Scalar scale,
356  Scalar half_stroke_width) {
357  // Consider 2 perpendicular vectors, each pointing to the same side of
358  // two adjacent path segment "boxes". If they are identical, then there
359  // is no turn at that point on the path and we do not need to decorate
360  // that gap with any join geometry. If they differ, there will be a gap
361  // between them that must be decorated and the cosine of the angle of
362  // that gap will be their Dot product (with +1 meaning that there is
363  // no turn and therefore no decoration needed). We need to find the
364  // cosine of the angle between them where we start to care about adding
365  // the join geometry.
366  //
367  // Consider the right triangle where one side is the line bisecting the
368  // two perpendiculars, starting from the common point on the path and
369  // ending at the line that joins them. The hypotenuse of that triangle
370  // is one of the perpendiculars, whose length is (scale * half_width).
371  // The other non-hypotenuse side is kJoinPixelThreshold. This
372  // triangle establishes the equation:
373  // ||bisector|| ^ 2 + kJoinThreshold ^ 2 == ||hypotenuse|| ^ 2
374  // and the cosine of the angle between the perpendicular and the bisector
375  // will be (||bisector|| / ||hypotenuse||).
376  // The cosine between the perpendiculars which can be compared to the
377  // will be the cosine of double that angle.
378  Scalar hypotenuse = scale * half_stroke_width;
379  if (hypotenuse <= kJoinPixelThreshold) {
380  // The line geometry is too small to register the docorations. Return
381  // a cosine value small enough to never qualify to add join decorations.
382  return -1.1f;
383  }
384  Scalar bisector = std::sqrt(hypotenuse * hypotenuse -
385  kJoinPixelThreshold * kJoinPixelThreshold);
386  Scalar half_cosine = bisector / hypotenuse;
387  Scalar cosine = 2.0f * half_cosine * half_cosine - 1;
388  return cosine;
389  }
390 
391  /// Determine the cosine of the angle between 2 segments on the path where
392  /// the miter limit will be exceeded if their outer stroked outlines are
393  /// joined at their intersection. The miter limit is expressed as a multiple
394  /// of the stroke width and since it is dependent on lines offset from the
395  /// path by that same stroke width, the angle is based just on the miter
396  /// limit itself.
397  ///
398  /// Any angle between 2 segments in the path for which the cosine of that
399  /// angle is less than this return value would result in an intersection
400  /// point that is further than the miter limit would allow. The angle
401  /// between the segments can be quickly computed by the dot product of
402  /// their direction vectors.
403  static Scalar ComputeMinimumMiterCosine(Scalar miter_limit) {
404  if (miter_limit <= 1.0f) {
405  // Miter limits less than 1.0 are impossible to meet since the miter
406  // join will always be at least as long as half the line width, so they
407  // essentially eliminate all miters. We return a degenerate cosine
408  // value so that the join routine never adds a miter.
409  return 1.1f;
410  }
411  // We enter the join routine with a point on the path shared between
412  // two segments that must be joined and 2 perpendicular values that
413  // locate the sides of the old and new segment "boxes" relative to
414  // that point. We can think of the miter as a diamond starting at the
415  // point on the path, extending outwards by those 2 perpendicular
416  // lines, and then continuing perpendicular to those perpendiculars
417  // to a common intersection point out in the distance. If you then
418  // consider the line that extends from the path point to the far
419  // intersection point, that divides the diamond into 2 right triangles
420  // (they are right triangles due to the right angle turn we take at
421  // the ends of the path perpendiculars). If we want to know the angle
422  // at which we reach the miter limit we can assume maximum extension
423  // which places the dividing line (the hypotenuse) at a multiple of the
424  // line width which is the length of one of those segment perpendiculars.
425  // This means that the near bisected angle has a cosine of the ratio
426  // of one of the near edges (length of half the line width) with the
427  // miter length (miter_limit times half the line width). The ratio of
428  // those is (1 / miter_limit).
429  Scalar half_cosine = 1 / miter_limit;
430  Scalar cosine = 2.0f * half_cosine * half_cosine - 1;
431  return cosine;
432  }
433 
434  inline SeparatedVector2 PerpendicularFromPoints(const Point from,
435  const Point to) const {
436  return PerpendicularFromUnitDirection((to - from).Normalize());
437  }
438 
439  inline SeparatedVector2 PerpendicularFromUnitDirection(
440  const Vector2 direction) const {
441  return SeparatedVector2(Vector2{-direction.y, direction.x},
442  half_stroke_width_);
443  }
444 
445  inline void AppendVertices(const Point curve_point, Vector2 offset) {
446  vtx_builder_.AppendVertex(curve_point + offset);
447  vtx_builder_.AppendVertex(curve_point - offset);
448  }
449 
450  inline void AppendVertices(const Point curve_point,
451  SeparatedVector2 perpendicular) {
452  return AppendVertices(curve_point, perpendicular.GetVector());
453  }
454 
455  inline void HandlePreviousJoin(SeparatedVector2 new_perpendicular) {
456  FML_DCHECK(has_prior_contour_);
457  if (has_prior_segment_) {
458  AddJoin(join_, last_point_, last_perpendicular_, new_perpendicular);
459  } else {
460  has_prior_segment_ = true;
461  Vector2 perpendicular_vector = new_perpendicular.GetVector();
462  if (contour_needs_cap_) {
463  AddCap(cap_, last_point_, perpendicular_vector, true);
464  }
465  // Start the new segment's "box" at the shared "last_point_" with
466  // the new perpendicular vector.
467  AppendVertices(last_point_, perpendicular_vector);
468  origin_perpendicular_ = new_perpendicular;
469  }
470  }
471 
472  // Adds a cap to an endpoint of a contour. The location points to the
473  // centerline of the stroke. The perpendicular points clockwise to the
474  // direction the path is traveling and is the length of half of the
475  // stroke width.
476  //
477  // If contour_start is true, then the cap is being added prior to the first
478  // segment at the beginning of a contour and assumes that no points have
479  // been added for this contour yet and also that the caller will add the
480  // two points that start the segment's "box" when this method returns.
481  //
482  // If contour_start is false, then the cap is being added after the last
483  // segment at the end of a contour and assumes that the caller has already
484  // added the two segments that define the end of the "box" for the last
485  // path segment.
486  void AddCap(Cap cap,
487  Point path_point,
488  Vector2 perpendicular,
489  bool contour_start) {
490  switch (cap) {
491  case Cap::kButt:
492  break;
493  case Cap::kRound: {
494  Point along(perpendicular.y, -perpendicular.x);
495  if (contour_start) {
496  // Start with a single point at the far end of the round cap.
497  vtx_builder_.AppendVertex(path_point - along);
498 
499  // Iterate from the last non-quadrant value in the trigs vector
500  // (trigs.back() == (1, 0)) down to, but not including, the first
501  // entry (which is (0, 1)).
502  for (size_t i = trigs_.size() - 2u; i > 0u; --i) {
503  Point center = path_point - along * trigs_[i].sin;
504  Vector2 offset = perpendicular * trigs_[i].cos;
505 
506  AppendVertices(center, offset);
507  }
508  } else {
509  // Iterate from the first non-quadrant value in the trigs vector
510  // (trigs[0] == (0, 1)) up to, but not including, the last entry
511  // (which is (0, 1)).
512  size_t end = trigs_.size() - 1u;
513  for (size_t i = 1u; i < end; ++i) {
514  Point center = path_point + along * trigs_[i].sin;
515  Vector2 offset = perpendicular * trigs_[i].cos;
516 
517  AppendVertices(center, offset);
518  }
519 
520  // End with a single point at the far end of the round cap.
521  vtx_builder_.AppendVertex(path_point + along);
522  }
523  break;
524  }
525  case Cap::kSquare: {
526  Point along(perpendicular.y, -perpendicular.x);
527  Point square_center = contour_start //
528  ? path_point - along //
529  : path_point + along;
530  AppendVertices(square_center, perpendicular);
531  break;
532  }
533  }
534  }
535 
536  void AddJoin(Join join,
537  Point path_point,
538  SeparatedVector2 old_perpendicular,
539  SeparatedVector2 new_perpendicular) {
540  Scalar cosine = old_perpendicular.GetAlignment(new_perpendicular);
541  if (cosine >= maximum_join_cosine_) {
542  // If the perpendiculars are closer than a pixel to each other, then
543  // no need to add any further points, we don't even need to start
544  // the new segment's "box", we can just let it connect back to the
545  // prior segment's "box end" directly.
546  return;
547  }
548  // All cases of this switch will fall through into the code that starts
549  // the new segment's "box" down below which is good enough to bevel join
550  // the segments should they individually decide that they don't need any
551  // other decorations to bridge the gap.
552  switch (join) {
553  case Join::kBevel:
554  // Just fall through to the bevel operation after the switch.
555  break;
556 
557  case Join::kMiter: {
558  if (cosine >= minimum_miter_cosine_) {
559  Point miter_vector =
560  (old_perpendicular.GetVector() + new_perpendicular.GetVector()) /
561  (cosine + 1);
562  if (old_perpendicular.Cross(new_perpendicular) < 0) {
563  vtx_builder_.AppendVertex(path_point + miter_vector);
564  } else {
565  vtx_builder_.AppendVertex(path_point - miter_vector);
566  }
567  }
568  // Else just fall through to bevel operation after the switch.
569  break;
570  } // end of case Join::kMiter
571 
572  case Join::kRound: {
573  if (cosine >= trigs_[1].cos) {
574  // If rotating by the first (non-quadrant) entry in trigs takes
575  // us too far then we don't need to fill in anything. Just fall
576  // through to the bevel operation after the switch.
577  break;
578  }
579  if (cosine < -trigs_[1].cos) {
580  // This is closer to a 180 degree turn than the last trigs entry
581  // can distinguish. Since we are going to generate all of the
582  // sample points of the entire round join anyway, it is faster to
583  // generate them using a round cap operation. Additionally, it
584  // avoids math issues in the code below that stem from the
585  // calculations being performed on a pair of vectors that are
586  // nearly opposite each other.
587  AddCap(Cap::kRound, path_point, old_perpendicular.GetVector(), false);
588  // The bevel operation following the switch statement will set
589  // us up to start drawing the following segment.
590  break;
591  }
592  // We want to set up the from and to vectors to facilitate a
593  // clockwise angular fill from one to the other. We might generate
594  // a couple fewer points by iterating counter-clockwise in some
595  // cases so that we always go from the old to new perpendiculars,
596  // but there is a lot of code to duplicate below for just a small
597  // change in whether we negate the trigs and expect the a.Cross(b)
598  // values to be > or < 0.
599  Vector2 from_vector, to_vector;
600  bool begin_end_crossed;
601  Scalar turning = old_perpendicular.Cross(new_perpendicular);
602  if (turning > 0) {
603  // Clockwise path turn, since our prependicular vectors point to
604  // the right of the path we need to fill in the "back side" of the
605  // turn, so we fill from -old to -new perpendicular which also
606  // has a clockwise turn.
607  from_vector = -old_perpendicular.GetVector();
608  to_vector = -new_perpendicular.GetVector();
609  // Despite the fact that we are using the negative vectors, they
610  // are in the right "order" so we can connect directly from the
611  // prior segment's "box" and directly to the following segment's.
612  begin_end_crossed = false;
613  } else {
614  // Countercockwise path turn, we need to reverse the order of the
615  // perpendiculars to achieve a clockwise angular fill, and since
616  // both vectors are pointing to the right, the vectors themselves
617  // are "turning outside" the widened path.
618  from_vector = new_perpendicular.GetVector();
619  to_vector = old_perpendicular.GetVector();
620  // We are reversing the direction of traversal with respect to
621  // the old segment's and new segment's boxes so we should append
622  // extra segments to cross back and forth.
623  begin_end_crossed = true;
624  }
625  FML_DCHECK(from_vector.Cross(to_vector) > 0);
626 
627  if (begin_end_crossed) {
628  vtx_builder_.AppendVertex(path_point + from_vector);
629  }
630 
631  // We only need to trace back to the common center point on every
632  // other circular vertex we add. This generates a "corrugated"
633  // path that visits the center once for every pair of edge vertices.
634  bool visit_center = false;
635 
636  // The sum of the vectors points in the direction halfway between
637  // them. Since we only need its direction, this is enough without
638  // having to adjust for the length to get the exact midpoint of
639  // the curve we have to draw.
640  Point middle_vector = (from_vector + to_vector);
641 
642  // Iterate through trigs until we reach a full quadrant's rotation
643  // or until we pass the halfway point (middle_vector). We start at
644  // position 1 because the first value is (0, 1) and just repeats
645  // the from_vector, and we choose the end here as the last value
646  // rather than the end of the vector because it is (1, 0) and that
647  // would just repeat the to_vector. The end variable will be updated
648  // in the first loop if we stop short of a full quadrant.
649  size_t end = trigs_.size() - 1u;
650  for (size_t i = 1u; i < end; ++i) {
651  Point p = trigs_[i] * from_vector;
652  if (p.Cross(middle_vector) <= 0) {
653  // We've traversed far enough to pass the halfway vector, stop
654  // here and drop out to traverse backwards from the to_vector.
655  // Record the stopping point in the end variable as we will use
656  // it to backtrack in the next loop.
657  end = i;
658  break;
659  }
660  if (visit_center) {
661  vtx_builder_.AppendVertex(path_point);
662  visit_center = false;
663  } else {
664  visit_center = true;
665  }
666  vtx_builder_.AppendVertex(path_point + p);
667  }
668 
669  // The end variable points to the last trigs entry we decided not to
670  // use, so a pre-decrement here moves us onto the trigs we actually
671  // want to use (stopping before we use 0 which is the no rotation
672  // vector).
673  while (--end > 0u) {
674  Point p = -trigs_[end] * to_vector;
675  if (visit_center) {
676  vtx_builder_.AppendVertex(path_point);
677  visit_center = false;
678  } else {
679  visit_center = true;
680  }
681  vtx_builder_.AppendVertex(path_point + p);
682  }
683 
684  if (begin_end_crossed) {
685  vtx_builder_.AppendVertex(path_point + to_vector);
686  }
687  break;
688  } // end of case Join::kRound
689  } // end of switch
690  // All joins need a final segment that is perpendicular to the shared
691  // path point along the new perpendicular direction, and this also
692  // provides a bevel join for all cases that decided no further
693  // decoration was warranted.
694  AppendVertices(path_point, new_perpendicular);
695  }
696 };
697 
698 // Private for benchmarking and debugging
699 std::vector<Point> StrokeSegmentsGeometry::GenerateSolidStrokeVertices(
700  Tessellator& tessellator,
701  const PathSource& source,
702  const StrokeParameters& stroke,
703  Scalar scale) {
704  std::vector<Point> points(4096);
705  PositionWriter vtx_builder(points);
706  StrokePathSegmentReceiver receiver(tessellator, vtx_builder, stroke, scale);
707  PathTessellator::PathToStrokedSegments(source, receiver);
708  auto [arena, extra] = vtx_builder.GetUsedSize();
709  FML_DCHECK(extra == 0u);
710  points.resize(arena);
711  return points;
712 }
713 
715  : stroke_(stroke) {}
716 
718 
720  return stroke_.width;
721 }
722 
724  return stroke_.miter_limit;
725 }
726 
728  return stroke_.cap;
729 }
730 
732  return stroke_.join;
733 }
734 
736  const Matrix& transform) const {
738 }
739 
740 GeometryResult StrokeSegmentsGeometry::GetPositionBuffer(
741  const ContentContext& renderer,
742  const Entity& entity,
743  RenderPass& pass) const {
744  if (stroke_.width < 0.0) {
745  return {};
746  }
747  Scalar max_basis = entity.GetTransform().GetMaxBasisLengthXY();
748  if (max_basis == 0) {
749  return {};
750  }
751 
752  Scalar min_size = kMinStrokeSize / max_basis;
753  StrokeParameters adjusted_stroke = stroke_;
754  adjusted_stroke.width = std::max(stroke_.width, min_size);
755 
756  auto& host_buffer = renderer.GetTransientsBuffer();
757  auto scale = entity.GetTransform().GetMaxBasisLengthXY();
758  auto& tessellator = renderer.GetTessellator();
759 
760  PositionWriter position_writer(tessellator.GetStrokePointCache());
761  StrokePathSegmentReceiver receiver(tessellator, position_writer,
762  adjusted_stroke, scale);
763  Dispatch(receiver, tessellator, scale);
764 
765  const auto [arena_length, oversized_length] = position_writer.GetUsedSize();
766  if (!position_writer.HasOversizedBuffer()) {
767  BufferView buffer_view =
768  host_buffer.Emplace(tessellator.GetStrokePointCache().data(),
769  arena_length * sizeof(Point), alignof(Point));
770 
771  return GeometryResult{.type = PrimitiveType::kTriangleStrip,
772  .vertex_buffer =
773  {
774  .vertex_buffer = buffer_view,
775  .vertex_count = arena_length,
776  .index_type = IndexType::kNone,
777  },
778  .transform = entity.GetShaderTransform(pass),
780  }
781  const std::vector<Point>& oversized_data =
782  position_writer.GetOversizedBuffer();
783  BufferView buffer_view = host_buffer.Emplace(
784  /*buffer=*/nullptr, //
785  (arena_length + oversized_length) * sizeof(Point), //
786  alignof(Point) //
787  );
788  memcpy(buffer_view.GetBuffer()->OnGetContents() +
789  buffer_view.GetRange().offset, //
790  tessellator.GetStrokePointCache().data(), //
791  arena_length * sizeof(Point) //
792  );
793  memcpy(buffer_view.GetBuffer()->OnGetContents() +
794  buffer_view.GetRange().offset + arena_length * sizeof(Point), //
795  oversized_data.data(), //
796  oversized_data.size() * sizeof(Point) //
797  );
798  buffer_view.GetBuffer()->Flush(buffer_view.GetRange());
799 
800  return GeometryResult{.type = PrimitiveType::kTriangleStrip,
801  .vertex_buffer =
802  {
803  .vertex_buffer = buffer_view,
804  .vertex_count = arena_length + oversized_length,
805  .index_type = IndexType::kNone,
806  },
807  .transform = entity.GetShaderTransform(pass),
809 }
810 
811 GeometryResult::Mode StrokeSegmentsGeometry::GetResultMode() const {
813 }
814 
816  const Matrix& transform,
817  const Rect& path_bounds) const {
818  if (path_bounds.IsEmpty()) {
819  return std::nullopt;
820  }
821 
822  Scalar max_radius = 0.5;
823  if (stroke_.cap == Cap::kSquare) {
824  max_radius = max_radius * kSqrt2;
825  }
826  if (stroke_.join == Join::kMiter) {
827  max_radius = std::max(max_radius, stroke_.miter_limit * 0.5f);
828  }
829  Scalar max_basis = transform.GetMaxBasisLengthXY();
830  if (max_basis == 0) {
831  return {};
832  }
833  // Use the most conervative coverage setting.
834  Scalar min_size = kMinStrokeSize / max_basis;
835  max_radius *= std::max(stroke_.width, min_size);
836  return path_bounds.Expand(max_radius).TransformBounds(transform);
837 }
838 
840  const StrokeParameters& parameters)
841  : StrokeSegmentsGeometry(parameters) {}
842 
844  const Matrix& transform) const {
845  return GetStrokeCoverage(transform, GetSource().GetBounds());
846 }
847 
849  Tessellator& tessellator,
850  Scalar scale) const {
852 }
853 
855  const StrokeParameters& parameters)
856  : StrokePathSourceGeometry(parameters), path_(path) {}
857 
859  return path_;
860 }
861 
863  const StrokeParameters& parameters)
864  : StrokeSegmentsGeometry(parameters), arc_(arc) {}
865 
866 std::optional<Rect> ArcStrokeGeometry::GetCoverage(
867  const Matrix& transform) const {
869 }
870 
872  Tessellator& tessellator,
873  Scalar scale) const {
874  Point center = arc_.GetOvalCenter();
875  Size radii = arc_.GetOvalSize() * 0.5f;
876 
877  auto trigs =
878  tessellator.GetTrigsForDeviceRadius(scale * radii.MaxDimension());
879  Arc::Iteration iterator =
880  arc_.ComputeIterations(trigs.GetSteps(), /*simplify_360=*/false);
881  Point start = center + iterator.start * radii;
882  bool include_center = arc_.IncludeCenter();
883 
884  receiver.BeginContour(start, include_center);
885  receiver.RecordArc(arc_, center, radii);
886  if (include_center) {
887  Point end = center + iterator.end * radii;
888  receiver.RecordLine(end, center);
889  receiver.RecordLine(center, start);
890  }
891  receiver.EndContour(start, include_center);
892 }
893 
895  const RoundRect& outer,
896  const RoundRect& inner,
897  const StrokeParameters& parameters)
898  : StrokePathSourceGeometry(parameters), source_(outer, inner) {}
899 
901  return source_;
902 }
903 
905  Point p0,
906  Point p1,
907  Scalar on_length,
908  Scalar off_length,
909  const StrokeParameters& parameters)
910  : StrokePathSourceGeometry(parameters),
911  source_(p0, p1, on_length, off_length) {}
912 
914  return source_;
915 }
916 
917 } // namespace impeller
BufferView buffer_view
void Dispatch(PathAndArcSegmentReceiver &receiver, Tessellator &tessellator, Scalar scale) const override
ArcStrokeGeometry(const Arc &arc, const StrokeParameters &parameters)
std::optional< Rect > GetCoverage(const Matrix &transform) const override
HostBuffer & GetTransientsBuffer() const
Retrieve the currnent host buffer for transient storage.
Tessellator & GetTessellator() const
Matrix GetShaderTransform(const RenderPass &pass) const
Definition: entity.cc:48
const Matrix & GetTransform() const
Get the global transform matrix for this Entity.
Definition: entity.cc:44
static Scalar ComputeStrokeAlphaCoverage(const Matrix &entity, Scalar stroke_width)
Compute an alpha value to simulate lower coverage of fractional pixel strokes.
Definition: geometry.cc:149
A |SegmentReceiver| that also accepts Arc segments for optimal handling. A path or |PathSource| will ...
virtual void RecordArc(const Arc &arc, const Point center, const Size radii)=0
virtual void RecordLine(Point p1, Point p2)=0
virtual void EndContour(Point origin, bool with_close)=0
virtual void BeginContour(Point origin, bool will_be_closed)=0
static void PathToStrokedSegments(const PathSource &source, SegmentReceiver &receiver)
Render passes encode render commands directed as one specific render target into an underlying comman...
Definition: render_pass.h:30
const PathSource & GetSource() const override
StrokeDashedLineGeometry(Point p0, Point p1, Scalar on_length, Scalar off_length, const StrokeParameters &parameters)
StrokeDiffRoundRectGeometry(const RoundRect &outer, const RoundRect &inner, const StrokeParameters &parameters)
const PathSource & GetSource() const override
StrokePathGeometry(const flutter::DlPath &path, const StrokeParameters &parameters)
const PathSource & GetSource() const override
void BeginContour(Point origin, bool will_be_closed) override
void RecordArc(const Arc &arc, const Point center, const Size radii) override
void EndContour(Point origin, bool with_close) override
void RecordQuad(Point p1, Point cp, Point p2) override
StrokePathSegmentReceiver(Tessellator &tessellator, PositionWriter &vtx_builder, const StrokeParameters &stroke, const Scalar scale)
void RecordConic(Point p1, Point cp, Point p2, Scalar weight) override
void RecordCubic(Point p1, Point cp1, Point cp2, Point p2) override
void RecordCurveSegment(const SeparatedVector2 &prev_perpendicular, const Point cur, const SeparatedVector2 &cur_perpendicular)
void RecordLine(Point p1, Point p2) override
An abstract Geometry base class that produces fillable vertices representing the stroked outline from...
virtual const PathSource & GetSource() const =0
std::optional< Rect > GetCoverage(const Matrix &transform) const override
StrokePathSourceGeometry(const StrokeParameters &parameters)
void Dispatch(PathAndArcSegmentReceiver &receiver, Tessellator &tessellator, Scalar scale) const override
An abstract Geometry base class that produces fillable vertices representing the stroked outline of t...
virtual void Dispatch(PathAndArcSegmentReceiver &receiver, Tessellator &tessellator, Scalar scale) const =0
Scalar ComputeAlphaCoverage(const Matrix &transform) const override
std::optional< Rect > GetStrokeCoverage(const Matrix &transform, const Rect &segment_bounds) const
StrokeSegmentsGeometry(const StrokeParameters &parameters)
std::vector< Trig >::iterator end() const
Definition: tessellator.h:55
A utility that generates triangles of the specified fill type given a polyline. This happens on the C...
Definition: tessellator.h:37
Trigs GetTrigsForDeviceRadius(Scalar pixel_radius)
Definition: tessellator.cc:310
@ kNone
Does not use the index buffer.
Join
An enum that describes ways to join two segments of a path.
Point Vector2
Definition: point.h:331
float Scalar
Definition: scalar.h:19
TPoint< Scalar > Point
Definition: point.h:327
Cap
An enum that describes ways to decorate the end of a path contour.
flutter::DlPath DlPath
Definition: dl_dispatcher.h:29
constexpr float kSqrt2
Definition: constants.h:47
static constexpr size_t kPointArenaSize
The size of the point arena buffer stored on the tessellator.
Definition: tessellator.h:25
static constexpr Scalar kMinStrokeSize
Definition: geometry.h:19
impeller::Vector2 axis
Definition: arc.h:46
impeller::Vector2 end
Definition: arc.h:59
impeller::Vector2 start
Definition: arc.h:58
Quadrant quadrants[9]
Definition: arc.h:86
size_t quadrant_count
Definition: arc.h:63
Iteration ComputeIterations(size_t step_count, bool simplify_360=true) const
Definition: arc.cc:102
Rect GetTightArcBounds() const
Definition: arc.cc:59
constexpr bool IncludeCenter() const
Definition: arc.h:110
const Size GetOvalSize() const
Returns the size of the oval bounds.
Definition: arc.h:100
const Point GetOvalCenter() const
Returns the center of the oval bounds.
Definition: arc.h:97
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
Scalar GetMaxBasisLengthXY() const
Definition: matrix.h:323
A Vector2, broken down as a separate magnitude and direction. Assumes that the direction given is nor...
Scalar GetAlignment(const SeparatedVector2 &other) const
Vector2 GetVector() const
Returns the vector representation of the vector.
A structure to store all of the parameters related to stroking a path or basic geometry object.
constexpr TRect< T > Expand(T left, T top, T right, T bottom) const
Returns a rectangle with expanded edges. Negative expansion results in shrinking.
Definition: rect.h:622
constexpr TRect TransformBounds(const Matrix &transform) const
Creates a new bounding box that contains this transformed rectangle.
Definition: rect.h:476
constexpr bool IsEmpty() const
Returns true if either of the width or height are 0, negative, or NaN.
Definition: rect.h:301
constexpr Type MaxDimension() const
Definition: size.h:106
const size_t start
const size_t end
std::vector< Point > points