| Flutter Impeller |

tessellator.h
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 #ifndef FLUTTER_IMPELLER_TESSELLATOR_TESSELLATOR_H_
6 #define FLUTTER_IMPELLER_TESSELLATOR_TESSELLATOR_H_
7
8 #include <functional>
9 #include <memory>
10 #include <vector>
11
12 #include "impeller/core/formats.h"
13 #include "impeller/geometry/path.h"
14 #include "impeller/geometry/point.h"
15 #include "impeller/geometry/trig.h"
16
17 struct TESStesselator;
18
19 namespace impeller {
20
21 void DestroyTessellator(TESStesselator* tessellator);
22
23 using CTessellator =
24 std::unique_ptr<TESStesselator, decltype(&DestroyTessellator)>;
25
26 //------------------------------------------------------------------------------
27 /// @brief A utility that generates triangles of the specified fill type
28 /// given a polyline. This happens on the CPU.
29 ///
30 /// This object is not thread safe, and its methods must not be
31 /// called from multiple threads.
32 ///
33 class Tessellator {
34 private:
35 /// Essentially just a vector of Trig objects, but supports storing a
36 /// reference to either a cached vector or a locally generated vector.
37 /// The constructor will fill the vector with quarter circular samples
38 /// for the indicated number of equal divisions if the vector is new.
39 class Trigs {
40 public:
41 explicit Trigs(std::vector<Trig>& trigs, size_t divisions) : trigs_(trigs) {
42 init(divisions);
43 FML_DCHECK(trigs_.size() == divisions + 1);
44 }
45
46 explicit Trigs(size_t divisions)
47 : local_storage_(std::make_unique<std::vector<Trig>>()),
48 trigs_(*local_storage_) {
49 init(divisions);
50 FML_DCHECK(trigs_.size() == divisions + 1);
51 }
52
53 // Utility forwards of the indicated vector methods.
54 auto inline size() const { return trigs_.size(); }
55 auto inline begin() const { return trigs_.begin(); }
56 auto inline end() const { return trigs_.end(); }
57
58 private:
59 // nullptr if a cached vector is used, otherwise the actual storage
60 std::unique_ptr<std::vector<Trig>> local_storage_;
61
62 // Whether or not a cached vector or the local storage is used, this
63 // this reference will always be valid
64 std::vector<Trig>& trigs_;
65
66 // Fill the vector with the indicated number of equal divisions of
67 // trigonometric values if it is empty.
68 void init(size_t divisions);
69 };
70
71 public:
72 enum class Result {
73 kSuccess,
74 kInputError,
75 kTessellationError,
76 };
77
78 /// @brief A callback function for a |VertexGenerator| to deliver
79 /// the vertices it computes as |Point| objects.
80 using TessellatedVertexProc = std::function<void(const Point& p)>;
81
82 /// @brief An object which produces a list of vertices as |Point|s that
83 /// tessellate a previously provided shape and delivers the vertices
84 /// through a |TessellatedVertexProc| callback.
85 ///
86 /// The object can also provide advance information on how many
87 /// vertices it will generate.
88 ///
89 /// @see |Tessellator::FilledCircle|
90 /// @see |Tessellator::StrokedCircle|
91 /// @see |Tessellator::RoundCapLine|
92 /// @see |Tessellator::FilledEllipse|
93 class VertexGenerator {
94 public:
95 /// @brief Returns the |PrimitiveType| that describes the relationship
96 /// among the list of vertices produced by the |GenerateVertices|
97 /// method.
98 ///
99 /// Most generators will deliver |kTriangleStrip| triangles
100 virtual PrimitiveType GetTriangleType() const = 0;
101
102 /// @brief Returns the number of vertices that the generator plans to
103 /// produce, if known.
104 ///
105 /// This value is advisory only and can be used to reserve space
106 /// where the vertices will be placed, but the count may be an
107 /// estimate.
108 ///
109 /// Implementations are encouraged to avoid overestimating
110 /// the count by too large a number and to provide a best
111 /// guess so as to minimize potential buffer reallocations
112 /// as the vertices are delivered.
113 virtual size_t GetVertexCount() const = 0;
114
115 /// @brief Generate the vertices and deliver them in the necessary
116 /// order (as required by the PrimitiveType) to the given
117 /// callback function.
118 virtual void GenerateVertices(const TessellatedVertexProc& proc) const = 0;
119 };
120
121 /// @brief The |VertexGenerator| implementation common to all shapes
122 /// that are based on a polygonal representation of an ellipse.
123 class EllipticalVertexGenerator : public virtual VertexGenerator {
124 public:
125 /// |VertexGenerator|
126 PrimitiveType GetTriangleType() const override {
127 return PrimitiveType::kTriangleStrip;
128 }
129
130 /// |VertexGenerator|
131 size_t GetVertexCount() const override {
132 return trigs_.size() * vertices_per_trig_;
133 }
134
135 /// |VertexGenerator|
136 void GenerateVertices(const TessellatedVertexProc& proc) const override {
137 impl_(trigs_, data_, proc);
138 }
139
140 private:
141 friend class Tessellator;
142
143 struct Data {
144 // Circles and Ellipses only use one of these points.
145 // RoundCapLines use both as the endpoints of the unexpanded line.
146 // A round rect can specify its interior rectangle by using the
147 // 2 points as opposing corners.
148 const Point reference_centers[2];
149 // Circular shapes have the same value in radii.width and radii.height
150 const Size radii;
151 // half_width is only used in cases where the generator will be
152 // generating 2 different outlines, such as StrokedCircle
153 const Scalar half_width;
154 };
155
156 typedef void GeneratorProc(const Trigs& trigs,
157 const Data& data,
158 const TessellatedVertexProc& proc);
159
160 GeneratorProc& impl_;
161 const Trigs trigs_;
162 const Data data_;
163 const size_t vertices_per_trig_;
164
165 EllipticalVertexGenerator(GeneratorProc& generator,
166 Trigs&& trigs,
167 PrimitiveType triangle_type,
168 size_t vertices_per_trig,
169 Data&& data);
170 };
171
172 Tessellator();
173
174 ~Tessellator();
175
176 /// @brief A callback that returns the results of the tessellation.
177 ///
178 /// The index buffer may not be populated, in which case [indices] will
179 /// be nullptr and indices_count will be 0.
180 using BuilderCallback = std::function<bool(const float* vertices,
181 size_t vertices_count,
182 const uint16_t* indices,
183 size_t indices_count)>;
184
185 //----------------------------------------------------------------------------
186 /// @brief Generates filled triangles from the path. A callback is
187 /// invoked once for the entire tessellation.
188 ///
189 /// @param[in] path The path to tessellate.
190 /// @param[in] tolerance The tolerance value for conversion of the path to
191 /// a polyline. This value is often derived from the
192 /// Matrix::GetMaxBasisLength of the CTM applied to the
193 /// path for rendering.
194 /// @param[in] callback The callback, return false to indicate failure.
195 ///
196 /// @return The result status of the tessellation.
197 ///
198 Tessellator::Result Tessellate(const Path& path,
199 Scalar tolerance,
200 const BuilderCallback& callback);
201
202 //----------------------------------------------------------------------------
203 /// @brief Given a convex path, create a triangle fan structure.
204 ///
205 /// @param[in] path The path to tessellate.
206 /// @param[in] tolerance The tolerance value for conversion of the path to
207 /// a polyline. This value is often derived from the
208 /// Matrix::GetMaxBasisLength of the CTM applied to the
209 /// path for rendering.
210 ///
211 /// @return A point vector containing the vertices in triangle strip format.
212 ///
213 std::vector<Point> TessellateConvex(const Path& path, Scalar tolerance);
214
215 //----------------------------------------------------------------------------
216 /// @brief Create a temporary polyline. Only one per-process can exist at
217 /// a time.
218 ///
219 /// The tessellator itself is not a thread safe class and should
220 /// only be used from the raster thread.
221 Path::Polyline CreateTempPolyline(const Path& path, Scalar tolerance);
222
223 /// @brief The pixel tolerance used by the algorighm to determine how
224 /// many divisions to create for a circle.
225 ///
226 /// No point on the polygon of vertices should deviate from the
227 /// true circle by more than this tolerance.
228 static constexpr Scalar kCircleTolerance = 0.1f;
229
230 /// @brief Create a |VertexGenerator| that can produce vertices for
231 /// a filled circle of the given radius around the given center
232 /// with enough polygon sub-divisions to provide reasonable
233 /// fidelity when viewed under the given view transform.
234 ///
235 /// Note that the view transform is only used to choose the
236 /// number of sample points to use per quarter circle and the
237 /// returned points are not transformed by it, instead they are
238 /// relative to the coordinate space of the center point.
239 EllipticalVertexGenerator FilledCircle(const Matrix& view_transform,
240 const Point& center,
241 Scalar radius);
242
243 /// @brief Create a |VertexGenerator| that can produce vertices for
244 /// a stroked circle of the given radius and half_width around
245 /// the given shared center with enough polygon sub-divisions
246 /// to provide reasonable fidelity when viewed under the given
247 /// view transform. The outer edge of the stroked circle is
248 /// generated at (radius + half_width) and the inner edge is
249 /// generated at (radius - half_width).
250 ///
251 /// Note that the view transform is only used to choose the
252 /// number of sample points to use per quarter circle and the
253 /// returned points are not transformed by it, instead they are
254 /// relative to the coordinate space of the center point.
255 EllipticalVertexGenerator StrokedCircle(const Matrix& view_transform,
256 const Point& center,
257 Scalar radius,
258 Scalar half_width);
259
260 /// @brief Create a |VertexGenerator| that can produce vertices for
261 /// a line with round end caps of the given radius with enough
262 /// polygon sub-divisions to provide reasonable fidelity when
263 /// viewed under the given view transform.
264 ///
265 /// Note that the view transform is only used to choose the
266 /// number of sample points to use per quarter circle and the
267 /// returned points are not transformed by it, instead they are
268 /// relative to the coordinate space of the two points.
269 EllipticalVertexGenerator RoundCapLine(const Matrix& view_transform,
270 const Point& p0,
271 const Point& p1,
272 Scalar radius);
273
274 /// @brief Create a |VertexGenerator| that can produce vertices for
275 /// a filled ellipse inscribed within the given bounds with
276 /// enough polygon sub-divisions to provide reasonable
277 /// fidelity when viewed under the given view transform.
278 ///
279 /// Note that the view transform is only used to choose the
280 /// number of sample points to use per quarter circle and the
281 /// returned points are not transformed by it, instead they are
282 /// relative to the coordinate space of the bounds.
283 EllipticalVertexGenerator FilledEllipse(const Matrix& view_transform,
284 const Rect& bounds);
285
286 /// @brief Create a |VertexGenerator| that can produce vertices for
287 /// a filled round rect within the given bounds and corner radii
288 /// with enough polygon sub-divisions to provide reasonable
289 /// fidelity when viewed under the given view transform.
290 ///
291 /// Note that the view transform is only used to choose the
292 /// number of sample points to use per quarter circle and the
293 /// returned points are not transformed by it, instead they are
294 /// relative to the coordinate space of the bounds.
295 EllipticalVertexGenerator FilledRoundRect(const Matrix& view_transform,
296 const Rect& bounds,
297 const Size& radii);
298
299 private:
300 /// Used for polyline generation.
301 std::unique_ptr<std::vector<Point>> point_buffer_;
302 CTessellator c_tessellator_;
303
304 // Data for variouos Circle/EllipseGenerator classes, cached per
305 // Tessellator instance which is usually the foreground life of an app
306 // if not longer.
307 static constexpr size_t kCachedTrigCount = 300;
308 std::vector<Trig> precomputed_trigs_[kCachedTrigCount];
309
310 Trigs GetTrigsForDivisions(size_t divisions);
311
312 static void GenerateFilledCircle(const Trigs& trigs,
313 const EllipticalVertexGenerator::Data& data,
314 const TessellatedVertexProc& proc);
315
316 static void GenerateStrokedCircle(const Trigs& trigs,
317 const EllipticalVertexGenerator::Data& data,
318 const TessellatedVertexProc& proc);
319
320 static void GenerateRoundCapLine(const Trigs& trigs,
321 const EllipticalVertexGenerator::Data& data,
322 const TessellatedVertexProc& proc);
323
324 static void GenerateFilledEllipse(const Trigs& trigs,
325 const EllipticalVertexGenerator::Data& data,
326 const TessellatedVertexProc& proc);
327
328 static void GenerateFilledRoundRect(
329 const Trigs& trigs,
330 const EllipticalVertexGenerator::Data& data,
331 const TessellatedVertexProc& proc);
332
333 Tessellator(const Tessellator&) = delete;
334
335 Tessellator& operator=(const Tessellator&) = delete;
336 };
337
338 } // namespace impeller
339
340 #endif // FLUTTER_IMPELLER_TESSELLATOR_TESSELLATOR_H_
path.h
impeller::Tessellator::~Tessellator
~Tessellator()
point.h
impeller::Scalar
float Scalar
Definition: scalar.h:18
trig.h
impeller::Tessellator
A utility that generates triangles of the specified fill type given a polyline. This happens on the C...
Definition: tessellator.h:33
impeller::Tessellator::TessellatedVertexProc
std::function< void(const Point &p)> TessellatedVertexProc
A callback function for a |VertexGenerator| to deliver the vertices it computes as |Point| objects.
Definition: tessellator.h:80
impeller::Tessellator::Result::kInputError
@ kInputError
formats.h
impeller::Tessellator::FilledCircle
EllipticalVertexGenerator FilledCircle(const Matrix &view_transform, const Point &center, Scalar radius)
Create a |VertexGenerator| that can produce vertices for a filled circle of the given radius around t...
Definition: tessellator.cc:411
impeller::Tessellator::VertexGenerator::GenerateVertices
virtual void GenerateVertices(const TessellatedVertexProc &proc) const =0
Generate the vertices and deliver them in the necessary order (as required by the PrimitiveType) to t...
impeller::Path::Polyline
Definition: path.h:94
impeller::Tessellator::EllipticalVertexGenerator::GenerateVertices
void GenerateVertices(const TessellatedVertexProc &proc) const override
|VertexGenerator|
Definition: tessellator.h:136
impeller::TSize< Scalar >
impeller::Tessellator::VertexGenerator
An object which produces a list of vertices as |Point|s that tessellate a previously provided shape a...
Definition: tessellator.h:93
impeller::PrimitiveType::kTriangleStrip
@ kTriangleStrip
impeller::PrimitiveType
PrimitiveType
Decides how backend draws pixels based on input vertices.
Definition: formats.h:353
impeller::Tessellator::Result::kTessellationError
@ kTessellationError
impeller::Tessellator::TessellateConvex
std::vector< Point > TessellateConvex(const Path &path, Scalar tolerance)
Given a convex path, create a triangle fan structure.
Definition: tessellator.cc:179
impeller::Tessellator::FilledRoundRect
EllipticalVertexGenerator FilledRoundRect(const Matrix &view_transform, const Rect &bounds, const Size &radii)
Create a |VertexGenerator| that can produce vertices for a filled round rect within the given bounds ...
Definition: tessellator.cc:492
impeller::Path
Paths are lightweight objects that describe a collection of linear, quadratic, or cubic segments....
Definition: path.h:51
impeller::DestroyTessellator
void DestroyTessellator(TESStesselator *tessellator)
Definition: tessellator.cc:242
impeller::Tessellator::Result::kSuccess
@ kSuccess
impeller::Tessellator::StrokedCircle
EllipticalVertexGenerator StrokedCircle(const Matrix &view_transform, const Point &center, Scalar radius, Scalar half_width)
Create a |VertexGenerator| that can produce vertices for a stroked circle of the given radius and hal...
Definition: tessellator.cc:427
impeller::Tessellator::EllipticalVertexGenerator
The |VertexGenerator| implementation common to all shapes that are based on a polygonal representatio...
Definition: tessellator.h:123
impeller::Tessellator::FilledEllipse
EllipticalVertexGenerator FilledEllipse(const Matrix &view_transform, const Rect &bounds)
Create a |VertexGenerator| that can produce vertices for a filled ellipse inscribed within the given ...
Definition: tessellator.cc:471
impeller::Tessellator::RoundCapLine
EllipticalVertexGenerator RoundCapLine(const Matrix &view_transform, const Point &p0, const Point &p1, Scalar radius)
Create a |VertexGenerator| that can produce vertices for a line with round end caps of the given radi...
Definition: tessellator.cc:448
impeller::Tessellator::EllipticalVertexGenerator::GetVertexCount
size_t GetVertexCount() const override
|VertexGenerator|
Definition: tessellator.h:131
impeller::Tessellator::VertexGenerator::GetTriangleType
virtual PrimitiveType GetTriangleType() const =0
Returns the |PrimitiveType| that describes the relationship among the list of vertices produced by th...
impeller::TPoint< Scalar >
impeller::Tessellator::Tessellate
Tessellator::Result Tessellate(const Path &path, Scalar tolerance, const BuilderCallback &callback)
Generates filled triangles from the path. A callback is invoked once for the entire tessellation.
Definition: tessellator.cc:58
impeller::Tessellator::Tessellator
Tessellator()
Definition: tessellator.cc:34
impeller::Tessellator::kCircleTolerance
static constexpr Scalar kCircleTolerance
The pixel tolerance used by the algorighm to determine how many divisions to create for a circle.
Definition: tessellator.h:228
impeller::Tessellator::VertexGenerator::GetVertexCount
virtual size_t GetVertexCount() const =0
Returns the number of vertices that the generator plans to produce, if known.
impeller::Tessellator::Result
Result
Definition: tessellator.h:72
impeller::Tessellator::EllipticalVertexGenerator::GetTriangleType
PrimitiveType GetTriangleType() const override
|VertexGenerator|
Definition: tessellator.h:126
impeller
Definition: aiks_blur_unittests.cc:20
impeller::Tessellator::BuilderCallback
std::function< bool(const float *vertices, size_t vertices_count, const uint16_t *indices, size_t indices_count)> BuilderCallback
A callback that returns the results of the tessellation.
Definition: tessellator.h:183
impeller::Tessellator::CreateTempPolyline
Path::Polyline CreateTempPolyline(const Path &path, Scalar tolerance)
Create a temporary polyline. Only one per-process can exist at a time.
Definition: tessellator.cc:167
impeller::TRect< Scalar >
impeller::CTessellator
std::unique_ptr< TESStesselator, decltype(&DestroyTessellator)> CTessellator
Definition: tessellator.h:24
impeller::Matrix
A 4x4 matrix using column-major storage.
Definition: matrix.h:37