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