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