| 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/wangs_formula.h"
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;
16 using Quad = impeller::PathTessellator::Quad;
17 using Conic = impeller::PathTessellator::Conic;
18 using Cubic = impeller::PathTessellator::Cubic;
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
283 void PathTessellator::PathToFilledSegments(const PathSource& source,
284 SegmentReceiver& receiver) {
285 PathPruner pruner(receiver, false);
286 source.Dispatch(pruner);
287 pruner.PathEnd();
288 }
289
290 void PathTessellator::PathToStrokedSegments(const PathSource& source,
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
307 void PathTessellator::PathToFilledVertices(const PathSource& source,
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
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:283
impeller::PathTessellator::PathToStrokedSegments
static void PathToStrokedSegments(const PathSource &source, SegmentReceiver &receiver)
Definition: path_tessellator.cc:290
impeller::PathTessellator::PathToFilledVertices
static void PathToFilledVertices(const PathSource &source, VertexWriter &writer, Scalar scale)
Definition: path_tessellator.cc:307
impeller::PathTessellator::CountFillStorage
static std::pair< size_t, size_t > CountFillStorage(const PathSource &source, Scalar scale)
Definition: path_tessellator.cc:297
impeller
Definition: allocation.cc:12
impeller::Scalar
float Scalar
Definition: scalar.h:19
impeller::Point
TPoint< Scalar > Point
Definition: point.h:327
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:332
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_tessellator.h
impeller::PathTessellator::Conic
Definition: path_tessellator.h:98
impeller::PathTessellator::Cubic
Definition: path_tessellator.h:141
wangs_formula.h