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"
15 #include "impeller/geometry/arc.h"
19 #include "impeller/geometry/trig.h"
20 
21 namespace impeller {
22 
23 /// The size of the point arena buffer stored on the tessellator.
24 [[maybe_unused]]
25 static constexpr size_t kPointArenaSize = 4096u;
26 
27 //------------------------------------------------------------------------------
28 /// @brief A utility that generates triangles of the specified fill type
29 /// given a polyline. This happens on the CPU.
30 ///
31 /// Also contains functionality for optimized generation of circles
32 /// and ellipses.
33 ///
34 /// This object is not thread safe, and its methods must not be
35 /// called from multiple threads.
36 ///
37 class Tessellator {
38  public:
39  /// Essentially just a vector of Trig objects, but supports storing a
40  /// reference to either a cached vector or a locally generated vector.
41  /// The constructor will fill the vector with quarter circular samples
42  /// for the indicated number of equal divisions if the vector is new.
43  ///
44  /// A given instance of Trigs will always contain at least 2 entries
45  /// which is the minimum number of samples to traverse a quarter circle
46  /// in a single step. The first sample will always be (0, 1) and the last
47  /// sample will always be (1, 0).
48  class Trigs {
49  public:
50  explicit Trigs(Scalar pixel_radius);
51 
52  // Utility forwards of the indicated vector methods.
53  size_t inline size() const { return trigs_.size(); }
54  std::vector<Trig>::iterator inline begin() const { return trigs_.begin(); }
55  std::vector<Trig>::iterator inline end() const { return trigs_.end(); }
56  const inline Trig& operator[](size_t index) const { return trigs_[index]; }
57 
58  size_t inline GetSteps() const { return trigs_.size() - 1u; }
59 
60  private:
61  friend class Tessellator;
62 
63  explicit Trigs(std::vector<Trig>& trigs, size_t divisions) : trigs_(trigs) {
64  FML_DCHECK(divisions >= 1);
65  init(divisions);
66  FML_DCHECK(trigs_.size() == divisions + 1);
67  }
68 
69  explicit Trigs(size_t divisions)
70  : local_storage_(std::make_unique<std::vector<Trig>>()),
71  trigs_(*local_storage_) {
72  FML_DCHECK(divisions >= 1);
73  init(divisions);
74  FML_DCHECK(trigs_.size() == divisions + 1);
75  }
76 
77  // nullptr if a cached vector is used, otherwise the actual storage
78  std::unique_ptr<std::vector<Trig>> local_storage_;
79 
80  // Whether or not a cached vector or the local storage is used, this
81  // this reference will always be valid
82  std::vector<Trig>& trigs_;
83 
84  // Fill the vector with the indicated number of equal divisions of
85  // trigonometric values if it is empty.
86  void init(size_t divisions);
87  };
88 
89  enum class Result {
90  kSuccess,
93  };
94 
95  /// @brief A callback function for a |VertexGenerator| to deliver
96  /// the vertices it computes as |Point| objects.
97  using TessellatedVertexProc = std::function<void(const Point& p)>;
98 
99  /// @brief An object which produces a list of vertices as |Point|s that
100  /// tessellate a previously provided shape and delivers the vertices
101  /// through a |TessellatedVertexProc| callback.
102  ///
103  /// The object can also provide advance information on how many
104  /// vertices it will generate.
105  ///
106  /// @see |Tessellator::FilledCircle|
107  /// @see |Tessellator::StrokedCircle|
108  /// @see |Tessellator::RoundCapLine|
109  /// @see |Tessellator::FilledEllipse|
111  public:
112  /// @brief Returns the |PrimitiveType| that describes the relationship
113  /// among the list of vertices produced by the |GenerateVertices|
114  /// method.
115  ///
116  /// Most generators will deliver |kTriangleStrip| triangles
117  virtual PrimitiveType GetTriangleType() const = 0;
118 
119  /// @brief Returns the number of vertices that the generator plans to
120  /// produce, if known.
121  ///
122  /// This value is advisory only and can be used to reserve space
123  /// where the vertices will be placed, but the count may be an
124  /// estimate.
125  ///
126  /// Implementations are encouraged to avoid overestimating
127  /// the count by too large a number and to provide a best
128  /// guess so as to minimize potential buffer reallocations
129  /// as the vertices are delivered.
130  virtual size_t GetVertexCount() const = 0;
131 
132  /// @brief Generate the vertices and deliver them in the necessary
133  /// order (as required by the PrimitiveType) to the given
134  /// callback function.
135  virtual void GenerateVertices(const TessellatedVertexProc& proc) const = 0;
136  };
137 
138  /// @brief The |VertexGenerator| implementation common to all shapes
139  /// that are based on a polygonal representation of an ellipse.
141  public:
142  /// |VertexGenerator|
143  PrimitiveType GetTriangleType() const override {
145  }
146 
147  /// |VertexGenerator|
148  size_t GetVertexCount() const override {
149  return trigs_.size() * vertices_per_trig_;
150  }
151 
152  /// |VertexGenerator|
153  void GenerateVertices(const TessellatedVertexProc& proc) const override {
154  impl_(trigs_, data_, proc);
155  }
156 
157  private:
158  friend class Tessellator;
159 
160  struct Data {
161  // Circles and Ellipses only use one of these points.
162  // RoundCapLines use both as the endpoints of the unexpanded line.
163  // A round rect can specify its interior rectangle by using the
164  // 2 points as opposing corners.
165  const Point reference_centers[2];
166  // Circular shapes have the same value in radii.width and radii.height
167  const Size radii;
168  // half_width is only used in cases where the generator will be
169  // generating 2 different outlines, such as StrokedCircle
170  const Scalar half_width;
171  };
172 
173  typedef void GeneratorProc(const Trigs& trigs,
174  const Data& data,
175  const TessellatedVertexProc& proc);
176 
177  GeneratorProc& impl_;
178  const Trigs trigs_;
179  const Data data_;
180  const size_t vertices_per_trig_;
181 
182  EllipticalVertexGenerator(GeneratorProc& generator,
183  Trigs&& trigs,
184  PrimitiveType triangle_type,
185  size_t vertices_per_trig,
186  Data&& data);
187  };
188 
189  /// @brief The |VertexGenerator| implementation common to all shapes
190  /// that are based on a polygonal representation of an ellipse.
191  class ArcVertexGenerator : public virtual VertexGenerator {
192  public:
193  /// |VertexGenerator|
194  PrimitiveType GetTriangleType() const override;
195 
196  /// |VertexGenerator|
197  size_t GetVertexCount() const override;
198 
199  /// |VertexGenerator|
200  void GenerateVertices(const TessellatedVertexProc& proc) const override;
201 
202  private:
203  friend class Tessellator;
204 
205  const Arc::Iteration iteration_;
206  const Trigs trigs_;
207  const Rect oval_bounds_;
208  const bool use_center_;
209  const Scalar half_width_;
210  const Cap cap_;
211  const bool supports_triangle_fans_;
212 
213  ArcVertexGenerator(const Arc::Iteration& iteration,
214  Trigs&& trigs,
215  const Rect& oval_bounds,
216  bool use_center,
217  bool supports_triangle_fans);
218 
219  ArcVertexGenerator(const Arc::Iteration& iteration,
220  Trigs&& trigs,
221  const Rect& oval_bounds,
222  Scalar half_width,
223  Cap cap);
224  };
225 
226  Tessellator();
227 
228  virtual ~Tessellator();
229 
230  //----------------------------------------------------------------------------
231  /// @brief Given a convex path, create a triangle fan structure.
232  ///
233  /// @param[in] path The path to tessellate.
234  /// @param[in] host_buffer The host buffer for allocation of vertices/index
235  /// data.
236  /// @param[in] tolerance The tolerance value for conversion of the path to
237  /// a polyline. This value is often derived from the
238  /// Matrix::GetMaxBasisLengthXY of the CTM applied to
239  /// the path for rendering.
240  ///
241  /// @return A vertex buffer containing all data from the provided curve.
243  HostBuffer& host_buffer,
244  Scalar tolerance,
245  bool supports_primitive_restart = false,
246  bool supports_triangle_fan = false);
247 
248  /// Visible for testing.
249  ///
250  /// This method only exists for the ease of benchmarking without using the
251  /// real allocator needed by the [host_buffer].
252  static void TessellateConvexInternal(const PathSource& path,
253  std::vector<Point>& point_buffer,
254  std::vector<uint16_t>& index_buffer,
255  Scalar tolerance);
256 
257  //----------------------------------------------------------------------------
258  /// @brief The pixel tolerance used by the algorighm to determine how
259  /// many divisions to create for a circle.
260  ///
261  /// No point on the polygon of vertices should deviate from the
262  /// true circle by more than this tolerance.
263  static constexpr Scalar kCircleTolerance = 0.1f;
264 
265  /// @brief Create a |VertexGenerator| that can produce vertices for
266  /// a filled circle of the given radius around the given center
267  /// with enough polygon sub-divisions to provide reasonable
268  /// fidelity when viewed under the given view transform.
269  ///
270  /// Note that the view transform is only used to choose the
271  /// number of sample points to use per quarter circle and the
272  /// returned points are not transformed by it, instead they are
273  /// relative to the coordinate space of the center point.
274  EllipticalVertexGenerator FilledCircle(const Matrix& view_transform,
275  const Point& center,
276  Scalar radius);
277 
278  /// @brief Create a |VertexGenerator| that can produce vertices for
279  /// a stroked circle of the given radius and half_width around
280  /// the given shared center with enough polygon sub-divisions
281  /// to provide reasonable fidelity when viewed under the given
282  /// view transform. The outer edge of the stroked circle is
283  /// generated at (radius + half_width) and the inner edge is
284  /// generated at (radius - half_width).
285  ///
286  /// Note that the view transform is only used to choose the
287  /// number of sample points to use per quarter circle and the
288  /// returned points are not transformed by it, instead they are
289  /// relative to the coordinate space of the center point.
290  EllipticalVertexGenerator StrokedCircle(const Matrix& view_transform,
291  const Point& center,
292  Scalar radius,
293  Scalar half_width);
294 
295  /// @brief Create a |VertexGenerator| that can produce vertices for
296  /// a stroked arc inscribed within the given oval_bounds with
297  /// the given stroke half_width with enough polygon sub-divisions
298  /// to provide reasonable fidelity when viewed under the given
299  /// view transform. The outer edge of the stroked arc is
300  /// generated at (radius + half_width) and the inner edge is
301  /// generated at (radius - half_width).
302  ///
303  /// Note that the view transform is only used to choose the
304  /// number of sample points to use per quarter circle and the
305  /// returned points are not transformed by it, instead they are
306  /// relative to the coordinate space of the oval bounds.
307  ArcVertexGenerator FilledArc(const Matrix& view_transform,
308  const Arc& arc,
309  bool supports_triangle_fans);
310 
311  /// @brief Create a |VertexGenerator| that can produce vertices for
312  /// a stroked arc inscribed within the given oval_bounds with
313  /// the given stroke half_width with enough polygon sub-divisions
314  /// to provide reasonable fidelity when viewed under the given
315  /// view transform. The outer edge of the stroked arc is
316  /// generated at (radius + half_width) and the inner edge is
317  /// generated at (radius - half_width).
318  ///
319  /// Note that the arc may not include the center and its bounds
320  /// must be a perfect circle (width == height)
321  ///
322  /// Note that the view transform is only used to choose the
323  /// number of sample points to use per quarter circle and the
324  /// returned points are not transformed by it, instead they are
325  /// relative to the coordinate space of the oval bounds.
326  ArcVertexGenerator StrokedArc(const Matrix& view_transform,
327  const Arc& arc,
328  Cap cap,
329  Scalar half_width);
330 
331  /// @brief Create a |VertexGenerator| that can produce vertices for
332  /// a line with round end caps of the given radius with enough
333  /// polygon sub-divisions to provide reasonable fidelity when
334  /// viewed under the given view transform.
335  ///
336  /// Note that the view transform is only used to choose the
337  /// number of sample points to use per quarter circle and the
338  /// returned points are not transformed by it, instead they are
339  /// relative to the coordinate space of the two points.
340  EllipticalVertexGenerator RoundCapLine(const Matrix& view_transform,
341  const Point& p0,
342  const Point& p1,
343  Scalar radius);
344 
345  /// @brief Create a |VertexGenerator| that can produce vertices for
346  /// a filled ellipse inscribed within the given bounds with
347  /// enough polygon sub-divisions to provide reasonable
348  /// fidelity when viewed under the given view transform.
349  ///
350  /// Note that the view transform is only used to choose the
351  /// number of sample points to use per quarter circle and the
352  /// returned points are not transformed by it, instead they are
353  /// relative to the coordinate space of the bounds.
354  EllipticalVertexGenerator FilledEllipse(const Matrix& view_transform,
355  const Rect& bounds);
356 
357  /// @brief Create a |VertexGenerator| that can produce vertices for
358  /// a filled round rect within the given bounds and corner radii
359  /// with enough polygon sub-divisions to provide reasonable
360  /// fidelity when viewed under the given view transform.
361  ///
362  /// Note that the view transform is only used to choose the
363  /// number of sample points to use per quarter circle and the
364  /// returned points are not transformed by it, instead they are
365  /// relative to the coordinate space of the bounds.
366  EllipticalVertexGenerator FilledRoundRect(const Matrix& view_transform,
367  const Rect& bounds,
368  const Size& radii);
369 
370  /// Retrieve a pre-allocated arena of kPointArenaSize points.
371  std::vector<Point>& GetStrokePointCache();
372 
373  /// Return a vector of Trig (cos, sin pairs) structs for a 90 degree
374  /// circle quadrant of the specified pixel radius
375  Trigs GetTrigsForDeviceRadius(Scalar pixel_radius);
376 
377  protected:
378  /// Used for polyline generation.
379  std::unique_ptr<std::vector<Point>> point_buffer_;
380  std::unique_ptr<std::vector<uint16_t>> index_buffer_;
381  /// Used for stroke path generation.
382  std::vector<Point> stroke_points_;
383 
384  private:
385  // Data for various Circle/EllipseGenerator classes, cached per
386  // Tessellator instance which is usually the foreground life of an app
387  // if not longer.
388  static constexpr size_t kCachedTrigCount = 300;
389  std::vector<Trig> precomputed_trigs_[kCachedTrigCount];
390 
391  Trigs GetTrigsForDivisions(size_t divisions);
392 
393  static void GenerateFilledCircle(const Trigs& trigs,
394  const EllipticalVertexGenerator::Data& data,
395  const TessellatedVertexProc& proc);
396 
397  static void GenerateStrokedCircle(const Trigs& trigs,
398  const EllipticalVertexGenerator::Data& data,
399  const TessellatedVertexProc& proc);
400 
401  static void GenerateFilledArcFan(const Trigs& trigs,
402  const Arc::Iteration& iteration,
403  const Rect& oval_bounds,
404  bool use_center,
405  const TessellatedVertexProc& proc);
406 
407  static void GenerateFilledArcStrip(const Trigs& trigs,
408  const Arc::Iteration& iteration,
409  const Rect& oval_bounds,
410  bool use_center,
411  const TessellatedVertexProc& proc);
412 
413  static void GenerateStrokedArc(const Trigs& trigs,
414  const Arc::Iteration& iteration,
415  const Rect& oval_bounds,
416  Scalar half_width,
417  Cap cap,
418  const TessellatedVertexProc& proc);
419 
420  static void GenerateRoundCapLine(const Trigs& trigs,
421  const EllipticalVertexGenerator::Data& data,
422  const TessellatedVertexProc& proc);
423 
424  static void GenerateFilledEllipse(const Trigs& trigs,
425  const EllipticalVertexGenerator::Data& data,
426  const TessellatedVertexProc& proc);
427 
428  static void GenerateFilledRoundRect(
429  const Trigs& trigs,
430  const EllipticalVertexGenerator::Data& data,
431  const TessellatedVertexProc& proc);
432 
433  Tessellator(const Tessellator&) = delete;
434 
435  Tessellator& operator=(const Tessellator&) = delete;
436 };
437 
438 } // namespace impeller
439 
440 #endif // FLUTTER_IMPELLER_TESSELLATOR_TESSELLATOR_H_
bool use_center
The |VertexGenerator| implementation common to all shapes that are based on a polygonal representatio...
Definition: tessellator.h:191
size_t GetVertexCount() const override
|VertexGenerator|
Definition: tessellator.cc:521
PrimitiveType GetTriangleType() const override
|VertexGenerator|
Definition: tessellator.cc:515
void GenerateVertices(const TessellatedVertexProc &proc) const override
|VertexGenerator|
Definition: tessellator.cc:541
The |VertexGenerator| implementation common to all shapes that are based on a polygonal representatio...
Definition: tessellator.h:140
PrimitiveType GetTriangleType() const override
|VertexGenerator|
Definition: tessellator.h:143
size_t GetVertexCount() const override
|VertexGenerator|
Definition: tessellator.h:148
void GenerateVertices(const TessellatedVertexProc &proc) const override
|VertexGenerator|
Definition: tessellator.h:153
std::vector< Trig >::iterator begin() const
Definition: tessellator.h:54
std::vector< Trig >::iterator end() const
Definition: tessellator.h:55
Trigs(Scalar pixel_radius)
Definition: tessellator.cc:411
const Trig & operator[](size_t index) const
Definition: tessellator.h:56
An object which produces a list of vertices as |Point|s that tessellate a previously provided shape a...
Definition: tessellator.h:110
virtual size_t GetVertexCount() const =0
Returns the number of vertices that the generator plans to produce, if known.
virtual PrimitiveType GetTriangleType() const =0
Returns the |PrimitiveType| that describes the relationship among the list of vertices produced by th...
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...
A utility that generates triangles of the specified fill type given a polyline. This happens on the C...
Definition: tessellator.h:37
Trigs GetTrigsForDeviceRadius(Scalar pixel_radius)
Definition: tessellator.cc:310
std::vector< Point > stroke_points_
Used for stroke path generation.
Definition: tessellator.h:382
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:583
std::vector< Point > & GetStrokePointCache()
Retrieve a pre-allocated arena of kPointArenaSize points.
Definition: tessellator.cc:306
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:627
VertexBuffer TessellateConvex(const PathSource &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:314
static constexpr Scalar kCircleTolerance
The pixel tolerance used by the algorighm to determine how many divisions to create for a circle.
Definition: tessellator.h:263
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:452
ArcVertexGenerator StrokedArc(const Matrix &view_transform, const Arc &arc, Cap cap, Scalar half_width)
Create a |VertexGenerator| that can produce vertices for a stroked arc inscribed within the given ova...
Definition: tessellator.cc:567
static void TessellateConvexInternal(const PathSource &path, std::vector< Point > &point_buffer, std::vector< uint16_t > &index_buffer, Scalar tolerance)
Definition: tessellator.cc:399
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:468
std::unique_ptr< std::vector< Point > > point_buffer_
Used for polyline generation.
Definition: tessellator.h:379
std::unique_ptr< std::vector< uint16_t > > index_buffer_
Definition: tessellator.h:380
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:606
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:97
ArcVertexGenerator FilledArc(const Matrix &view_transform, const Arc &arc, bool supports_triangle_fans)
Create a |VertexGenerator| that can produce vertices for a stroked arc inscribed within the given ova...
Definition: tessellator.cc:556
PrimitiveType
Decides how backend draws pixels based on input vertices.
Definition: formats.h:352
float Scalar
Definition: scalar.h:19
Cap
An enum that describes ways to decorate the end of a path contour.
Tessellator::ArcVertexGenerator ArcVertexGenerator
Definition: tessellator.cc:439
static constexpr size_t kPointArenaSize
The size of the point arena buffer stored on the tessellator.
Definition: tessellator.h:25
Definition: comparable.h:95
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
A structure to store the sine and cosine of an angle.
Definition: trig.h:16
std::shared_ptr< const fml::Mapping > data
Definition: texture_gles.cc:68