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