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