Flutter Impeller
path_tessellator.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 
8 
9 namespace {
10 
11 using Point = impeller::Point;
12 using Scalar = impeller::Scalar;
13 
14 using SegmentReceiver = impeller::PathTessellator::SegmentReceiver;
15 using VertexWriter = impeller::PathTessellator::VertexWriter;
19 
20 /// Base class for all utility path receivers in this file. It prunes
21 /// empty contours and degenerate path segments so that all path
22 /// tessellator receivers will operate on the same data.
23 ///
24 /// Some simplifications and guarantees that it implements:
25 /// - remove duplicate MoveTo operations
26 /// - ensure Begin/EndContour on every sub-path
27 /// - ensure a single degenerate line for empty stroked sub-paths
28 /// - ensure line back to origin for filled sub-paths
29 /// - trivial Quad to Line
30 /// - trivial Conic to Quad
31 /// - trivial Conic to Line
32 ///
33 /// Some of these simplifications could be implemented in the Path object
34 /// if we controlled the entire process from end to end.
35 class PathPruner : public impeller::PathReceiver {
36  public:
37  explicit PathPruner(SegmentReceiver& receiver, bool is_stroking = false)
38  : receiver_(receiver), is_stroking_(is_stroking) {}
39 
40  void MoveTo(const Point& p2, bool will_be_closed) override {
41  if (is_stroking_) {
42  if (contour_has_segments_ && !contour_has_points_) {
43  // If we had actual path segments, but none of them went anywhere
44  // (i.e. they never generated any points) then we have to record a
45  // 0-length line so that stroker can draw "cap boxes"
46  receiver_.RecordLine(contour_origin_, contour_origin_);
47  }
48  } else { // !is_stroking_
49  if (current_point_ != contour_origin_) {
50  // We help fill operations out by manually connecting back to the
51  // contour origin - basically all fill operations implicitly close
52  // their contours. If the current point is not at the contour
53  // origin then we must have encountered both segments and points.
54  FML_DCHECK(contour_has_segments_);
55  FML_DCHECK(contour_has_points_);
56  receiver_.RecordLine(current_point_, contour_origin_);
57  }
58  }
59  if (contour_has_segments_) {
60  // contour_has_segments_ implies we have called BeginContour at some
61  // point in time, so we need to end it as we've "moved on".
62  receiver_.EndContour(contour_origin_, false);
63  }
64  contour_origin_ = current_point_ = p2;
65  contour_has_segments_ = contour_has_points_ = false;
66  contour_will_be_closed_ = will_be_closed;
67  // We will not record a BeginContour for this potential new contour
68  // until we get an actual segment within the contour.
69  // See SegmentEncountered()
70  }
71 
72  void LineTo(const Point& p2) override {
73  SegmentEncountered();
74  if (p2 != current_point_) {
75  receiver_.RecordLine(current_point_, p2);
76  current_point_ = p2;
77  contour_has_points_ = true;
78  }
79  }
80 
81  void QuadTo(const Point& cp, const Point& p2) override {
82  if (cp == current_point_ || p2 == cp) {
83  // If all 3 are the same, LineTo will handle that for us
84  LineTo(p2);
85  } else {
86  SegmentEncountered();
87  receiver_.RecordQuad(current_point_, cp, p2);
88  current_point_ = p2;
89  contour_has_points_ = true;
90  }
91  }
92 
93  bool ConicTo(const Point& cp, const Point& p2, Scalar weight) override {
94  if (weight == 1.0f) {
95  QuadTo(cp, p2);
96  } else if (cp == current_point_ || p2 == cp || weight == 0.0f) {
97  LineTo(p2);
98  } else {
99  SegmentEncountered();
100  receiver_.RecordConic(current_point_, cp, p2, weight);
101  current_point_ = p2;
102  contour_has_points_ = true;
103  }
104  return true;
105  };
106 
107  void CubicTo(const Point& cp1, const Point& cp2, const Point& p2) override {
108  SegmentEncountered();
109  if (cp1 != current_point_ || //
110  cp2 != current_point_ || //
111  p2 != current_point_) {
112  // We could check if 3 of the 4 points are equal and simplify to a
113  // LineTo, but that quantity of compares is overkill for the unlikely
114  // case that it will happen. Checking for simplifying to a QuadTo
115  // would involve computing the intersection point of the control
116  // polygon edges which is too expensive to be worth the benefit.
117  receiver_.RecordCubic(current_point_, cp1, cp2, p2);
118  current_point_ = p2;
119  contour_has_points_ = true;
120  }
121  }
122 
123  void Close() override {
124  // Even a {MoveTo(); Close();} sequence generates a "cap box" at the
125  // contour origin location, so we always consider this an "encountered"
126  // segment.
127  SegmentEncountered();
128  if (is_stroking_) {
129  if (!contour_has_points_) {
130  FML_DCHECK(contour_has_segments_);
131  receiver_.RecordLine(current_point_, contour_origin_);
132  contour_has_points_ = true;
133  }
134  } else { // !is_stroking_
135  if (current_point_ != contour_origin_) {
136  FML_DCHECK(contour_has_segments_);
137  FML_DCHECK(contour_has_points_);
138  receiver_.RecordLine(current_point_, contour_origin_);
139  }
140  }
141  receiver_.EndContour(contour_origin_, true);
142  // The following mirrors the actions of MoveTo - we remain open to
143  // recording a new contour from this origin point as if we had had
144  // a MoveTo, but we perform no other processing that a MoveTo implies.
145  current_point_ = contour_origin_;
146  contour_has_segments_ = contour_has_points_ = false;
147  // We will not record a BeginContour for this potential new contour
148  // until we get an actual segment within the contour.
149  // See SegmentEncountered()
150  }
151 
152  void PathEnd() {
153  if (!is_stroking_ && current_point_ != contour_origin_) {
154  FML_DCHECK(contour_has_segments_);
155  FML_DCHECK(contour_has_points_);
156  receiver_.RecordLine(current_point_, contour_origin_);
157  }
158  if (contour_has_segments_) {
159  receiver_.EndContour(contour_origin_, false);
160  }
161  }
162 
163  private:
164  SegmentReceiver& receiver_;
165  const bool is_stroking_;
166 
167  void SegmentEncountered() {
168  if (!contour_has_segments_) {
169  receiver_.BeginContour(contour_origin_, contour_will_be_closed_);
170  contour_has_segments_ = true;
171  }
172  }
173 
174  bool contour_has_segments_ = false;
175  bool contour_has_points_ = false;
176  bool contour_will_be_closed_ = false;
177  Point contour_origin_;
178  Point current_point_;
179 };
180 
181 class StorageCounter : public SegmentReceiver {
182  public:
183  explicit StorageCounter(impeller::Scalar scale) : scale_(scale) {}
184 
185  void BeginContour(Point origin, bool will_be_closed) override {
186  // This is a new contour
187  contour_count_++;
188 
189  // This contour will have an implicit "from" point that will be
190  // be delivered with the corresponding Segment methods below.
191  point_count_++;
192  }
193 
194  void RecordLine(Point p1, Point p2) override { point_count_++; }
195 
196  void RecordQuad(Point p1, Point cp, Point p2) override {
197  size_t count = //
198  std::ceilf(ComputeQuadradicSubdivisions(scale_, p1, cp, p2));
199  point_count_ += std::max<size_t>(count, 1);
200  }
201 
202  void RecordConic(Point p1, Point cp, Point p2, Scalar weight) override {
203  size_t count = //
204  std::ceilf(ComputeConicSubdivisions(scale_, p1, cp, p2, weight));
205  point_count_ += std::max<size_t>(count, 1);
206  }
207 
208  void RecordCubic(Point p1, Point cp1, Point cp2, Point p2) override {
209  size_t count = //
210  std::ceilf(ComputeCubicSubdivisions(scale_, p1, cp1, cp2, p2));
211  point_count_ += std::max<size_t>(count, 1);
212  }
213 
214  void EndContour(Point origin, bool with_close) override {
215  // If the close operation would have resulted in an additional line
216  // segment then the pruner will call RecordLine independently.
217  // We count contours in the BeginContour method
218  }
219 
220  size_t GetPointCount() const { return point_count_; }
221  size_t GetContourCount() const { return contour_count_; }
222 
223  private:
224  size_t point_count_ = 0u;
225  size_t contour_count_ = 0u;
226 
227  Scalar scale_;
228 };
229 
230 class PathFillWriter : public SegmentReceiver {
231  public:
232  PathFillWriter(VertexWriter& writer, Scalar scale)
233  : writer_(writer), scale_(scale) {}
234 
235  void BeginContour(Point origin, bool will_be_closed) override {
236  writer_.Write(origin);
237  }
238 
239  void RecordLine(Point p1, Point p2) override { writer_.Write(p2); }
240 
241  void RecordQuad(Point p1, Point cp, Point p2) override {
242  Quad quad{p1, cp, p2};
243  Scalar count = std::ceilf(ComputeQuadradicSubdivisions(scale_, p1, cp, p2));
244  for (size_t i = 1; i < count; i++) {
245  writer_.Write(quad.Solve(i / count));
246  }
247  writer_.Write(p2);
248  }
249 
250  void RecordConic(Point p1, Point cp, Point p2, Scalar weight) override {
251  Conic conic{p1, cp, p2, weight};
252  Scalar count =
253  std::ceilf(ComputeConicSubdivisions(scale_, p1, cp, p2, weight));
254  for (size_t i = 1; i < count; i++) {
255  writer_.Write(conic.Solve(i / count));
256  }
257  writer_.Write(p2);
258  }
259 
260  void RecordCubic(Point p1, Point cp1, Point cp2, Point p2) override {
261  Cubic cubic{p1, cp1, cp2, p2};
262  Scalar count =
263  std::ceilf(ComputeCubicSubdivisions(scale_, p1, cp1, cp2, p2));
264  for (size_t i = 1; i < count; i++) {
265  writer_.Write(cubic.Solve(i / count));
266  }
267  writer_.Write(p2);
268  }
269 
270  void EndContour(Point origin, bool with_close) override {
271  writer_.EndContour();
272  }
273 
274  private:
275  VertexWriter& writer_;
276  Scalar scale_;
277 };
278 
279 } // namespace
280 
281 namespace impeller {
282 
284  SegmentReceiver& receiver) {
285  PathPruner pruner(receiver, false);
286  source.Dispatch(pruner);
287  pruner.PathEnd();
288 }
289 
291  SegmentReceiver& receiver) {
292  PathPruner pruner(receiver, true);
293  source.Dispatch(pruner);
294  pruner.PathEnd();
295 }
296 
297 std::pair<size_t, size_t> PathTessellator::CountFillStorage(
298  const PathSource& source,
299  Scalar scale) {
300  StorageCounter counter(scale);
301  PathPruner pruner(counter, false);
302  source.Dispatch(pruner);
303  pruner.PathEnd();
304  return {counter.GetPointCount(), counter.GetContourCount()};
305 }
306 
308  VertexWriter& writer,
309  Scalar scale) {
310  PathFillWriter path_writer(writer, scale);
311  PathPruner pruner(path_writer, false);
312  source.Dispatch(pruner);
313  pruner.PathEnd();
314 }
315 
316 } // namespace impeller
Collection of functions to receive path segments from the underlying path representation via the DlPa...
Definition: path_source.h:42
virtual void CubicTo(const Point &cp1, const Point &cp2, const Point &p2)=0
virtual void LineTo(const Point &p2)=0
virtual void QuadTo(const Point &cp, const Point &p2)=0
virtual void Close()=0
virtual void MoveTo(const Point &p2, bool will_be_closed)=0
virtual bool ConicTo(const Point &cp, const Point &p2, Scalar weight)
Definition: path_source.h:48
virtual void Dispatch(PathReceiver &receiver) const =0
An interface for receiving pruned path segments.
An interface for generating a multi contour polyline as a triangle strip.
static void PathToFilledSegments(const PathSource &source, SegmentReceiver &receiver)
static void PathToStrokedSegments(const PathSource &source, SegmentReceiver &receiver)
static void PathToFilledVertices(const PathSource &source, VertexWriter &writer, Scalar scale)
static std::pair< size_t, size_t > CountFillStorage(const PathSource &source, Scalar scale)
float Scalar
Definition: scalar.h:19
TPoint< Scalar > Point
Definition: point.h:327
Scalar ComputeConicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Scalar w)
std::array< Point, 4 > Quad
Definition: point.h:332
Scalar ComputeQuadradicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2)
Scalar ComputeCubicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Point p3)