| Flutter Impeller |

Classes | Public Types | Public Member Functions | Static Public Attributes | List of all members
impeller::Tessellator Class Reference

A utility that generates triangles of the specified fill type given a polyline. This happens on the CPU. More...

`#include <tessellator.h>`

## Classes
class | EllipticalVertexGenerator
| The |VertexGenerator| implementation common to all shapes that are based on a polygonal representation of an ellipse. More...
class | VertexGenerator
| An object which produces a list of vertices as |Point|s that tessellate a previously provided shape and delivers the vertices through a |TessellatedVertexProc| callback. More...

## Public Types
enum | Result { Result::kSuccess, Result::kInputError, Result::kTessellationError }
using | TessellatedVertexProc = std::function< void(const Point &p)>
| A callback function for a |VertexGenerator| to deliver the vertices it computes as |Point| objects. More...
using | BuilderCallback = std::function< bool(const float *vertices, size_t vertices_count, const uint16_t *indices, size_t indices_count)>
| A callback that returns the results of the tessellation. More...

## Public Member Functions
| Tessellator ()
| ~Tessellator ()
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. More...
std::vector< Point > | TessellateConvex (const Path &path, Scalar tolerance)
| Given a convex path, create a triangle fan structure. More...
Path::Polyline | CreateTempPolyline (const Path &path, Scalar tolerance)
| Create a temporary polyline. Only one per-process can exist at a time. More...
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 the given center with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. More...
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 half_width around the given shared center with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. The outer edge of the stroked circle is generated at (radius + half_width) and the inner edge is generated at (radius - half_width). More...
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 radius with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. More...
EllipticalVertexGenerator | FilledEllipse (const Matrix &view_transform, const Rect &bounds)
| Create a |VertexGenerator| that can produce vertices for a filled ellipse inscribed within the given bounds with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. More...
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 and corner radii with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. More...

## Static Public Attributes
static constexpr Scalar | kCircleTolerance = 0.1f
| The pixel tolerance used by the algorighm to determine how many divisions to create for a circle. More...

## Detailed Description

A utility that generates triangles of the specified fill type given a polyline. This happens on the CPU.

This object is not thread safe, and its methods must not be called from multiple threads.

Definition at line 33 of file tessellator.h.

## Member Typedef Documentation

## ◆ BuilderCallback

using impeller::Tessellator::BuilderCallback = std::function<bool(const float* vertices, size_t vertices_count, const uint16_t* indices, size_t indices_count)>

A callback that returns the results of the tessellation.

       The index buffer may not be populated, in which case [indices] will
       be nullptr and indices_count will be 0.

Definition at line 183 of file tessellator.h.

## ◆ TessellatedVertexProc

using impeller::Tessellator::TessellatedVertexProc = std::function<void(const Point& p)>

A callback function for a |VertexGenerator| to deliver the vertices it computes as |Point| objects.

Definition at line 80 of file tessellator.h.

## Member Enumeration Documentation

## ◆ Result

enum impeller::Tessellator::Result
| strong

Enumerator
kSuccess |
kInputError |
kTessellationError |

Definition at line 72 of file tessellator.h.

72 {
73 kSuccess,
74 kInputError,
75 kTessellationError,
76 };

## Constructor & Destructor Documentation

## ◆ Tessellator()

impeller::Tessellator::Tessellator | ( |  | ) |

Definition at line 34 of file tessellator.cc.

35 : point_buffer_(std::make_unique<std::vector<Point>>()),
36 c_tessellator_(nullptr, &DestroyTessellator) {
37 point_buffer_->reserve(2048);
38 TESSalloc alloc = kAlloc;
39 {
40 // libTess2 copies the TESSalloc despite the non-const argument.
41 CTessellator tessellator(::tessNewTess(&alloc), &DestroyTessellator);
42 c_tessellator_ = std::move(tessellator);
43 }
44 }

References impeller::DestroyTessellator(), and impeller::kAlloc.

## ◆ ~Tessellator()

impeller::Tessellator::~Tessellator | ( |  | ) |
| default

## Member Function Documentation

## ◆ CreateTempPolyline()

Path::Polyline impeller::Tessellator::CreateTempPolyline | ( | const Path & | path,
|  | Scalar | tolerance
| ) |  |

Create a temporary polyline. Only one per-process can exist at a time.

The tessellator itself is not a thread safe class and should only be used from the raster thread.

Definition at line 167 of file tessellator.cc.

168 {
169 FML_DCHECK(point_buffer_);
170 point_buffer_->clear();
171 auto polyline =
172 path.CreatePolyline(tolerance, std::move(point_buffer_),
173 [this](Path::Polyline::PointBufferPtr point_buffer) {
174 point_buffer_ = std::move(point_buffer);
175 });
176 return polyline;
177 }

References impeller::Path::CreatePolyline(), and polyline.

## ◆ FilledCircle()

EllipticalVertexGenerator impeller::Tessellator::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 the given center with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform.

Note that the view transform is only used to choose the number of sample points to use per quarter circle and the returned points are not transformed by it, instead they are relative to the coordinate space of the center point.

Definition at line 411 of file tessellator.cc.

414 {
415 auto divisions =
416 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * radius);
417 return EllipticalVertexGenerator(Tessellator::GenerateFilledCircle,
418 GetTrigsForDivisions(divisions),
419 PrimitiveType::kTriangleStrip, 4,
420 {
421 .reference_centers = {center, center},
422 .radii = {radius, radius},
423 .half_width = -1.0f,
424 });
425 }

References impeller::ComputeQuadrantDivisions(), and impeller::Matrix::GetMaxBasisLength().

## ◆ FilledEllipse()

EllipticalVertexGenerator impeller::Tessellator::FilledEllipse | ( | const Matrix & | view_transform,
|  | const Rect & | bounds
| ) |  |

Create a |VertexGenerator| that can produce vertices for a filled ellipse inscribed within the given bounds with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform.

Note that the view transform is only used to choose the number of sample points to use per quarter circle and the returned points are not transformed by it, instead they are relative to the coordinate space of the bounds.

Definition at line 471 of file tessellator.cc.

473 {
474 if (bounds.IsSquare()) {
475 return FilledCircle(view_transform, bounds.GetCenter(),
476 bounds.GetWidth() * 0.5f);
477 }
478 auto max_radius = bounds.GetSize().MaxDimension();
479 auto divisions =
480 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * max_radius);
481 auto center = bounds.GetCenter();
482 return EllipticalVertexGenerator(Tessellator::GenerateFilledEllipse,
483 GetTrigsForDivisions(divisions),
484 PrimitiveType::kTriangleStrip, 4,
485 {
486 .reference_centers = {center, center},
487 .radii = bounds.GetSize() * 0.5f,
488 .half_width = -1.0f,
489 });
490 }

References impeller::ComputeQuadrantDivisions(), impeller::TRect< T >::GetCenter(), impeller::Matrix::GetMaxBasisLength(), impeller::TRect< T >::GetSize(), impeller::TRect< T >::GetWidth(), and impeller::TRect< T >::IsSquare().

## ◆ FilledRoundRect()

EllipticalVertexGenerator impeller::Tessellator::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 and corner radii with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform.

Note that the view transform is only used to choose the number of sample points to use per quarter circle and the returned points are not transformed by it, instead they are relative to the coordinate space of the bounds.

Definition at line 492 of file tessellator.cc.

495 {
496 if (radii.width * 2 < bounds.GetWidth() ||
497 radii.height * 2 < bounds.GetHeight()) {
498 auto max_radius = radii.MaxDimension();
499 auto divisions = ComputeQuadrantDivisions(
500 view_transform.GetMaxBasisLength() * max_radius);
501 auto upper_left = bounds.GetLeftTop() + radii;
502 auto lower_right = bounds.GetRightBottom() - radii;
503 return EllipticalVertexGenerator(Tessellator::GenerateFilledRoundRect,
504 GetTrigsForDivisions(divisions),
505 PrimitiveType::kTriangleStrip, 4,
506 {
507 .reference_centers =
508 {
509 upper_left,
510 lower_right,
511 },
512 .radii = radii,
513 .half_width = -1.0f,
514 });
515 } else {
516 return FilledEllipse(view_transform, bounds);
517 }
518 }

References impeller::ComputeQuadrantDivisions(), impeller::TRect< T >::GetHeight(), impeller::TRect< T >::GetLeftTop(), impeller::Matrix::GetMaxBasisLength(), impeller::TRect< T >::GetRightBottom(), impeller::TRect< T >::GetWidth(), impeller::TSize< T >::height, impeller::TSize< T >::MaxDimension(), and impeller::TSize< T >::width.

## ◆ RoundCapLine()

EllipticalVertexGenerator impeller::Tessellator::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 radius with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform.

Note that the view transform is only used to choose the number of sample points to use per quarter circle and the returned points are not transformed by it, instead they are relative to the coordinate space of the two points.

Definition at line 448 of file tessellator.cc.

452 {
453 auto along = p1 - p0;
454 auto length = along.GetLength();
455 if (length > kEhCloseEnough) {
456 auto divisions =
457 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * radius);
458 return EllipticalVertexGenerator(Tessellator::GenerateRoundCapLine,
459 GetTrigsForDivisions(divisions),
460 PrimitiveType::kTriangleStrip, 4,
461 {
462 .reference_centers = {p0, p1},
463 .radii = {radius, radius},
464 .half_width = -1.0f,
465 });
466 } else {
467 return FilledCircle(view_transform, p0, radius);
468 }
469 }

References impeller::ComputeQuadrantDivisions(), impeller::TPoint< T >::GetLength(), impeller::Matrix::GetMaxBasisLength(), and impeller::kEhCloseEnough.

## ◆ StrokedCircle()

EllipticalVertexGenerator impeller::Tessellator::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 half_width around the given shared center with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. The outer edge of the stroked circle is generated at (radius + half_width) and the inner edge is generated at (radius - half_width).

Note that the view transform is only used to choose the number of sample points to use per quarter circle and the returned points are not transformed by it, instead they are relative to the coordinate space of the center point.

Definition at line 427 of file tessellator.cc.

431 {
432 if (half_width > 0) {
433 auto divisions = ComputeQuadrantDivisions(
434 view_transform.GetMaxBasisLength() * radius + half_width);
435 return EllipticalVertexGenerator(Tessellator::GenerateStrokedCircle,
436 GetTrigsForDivisions(divisions),
437 PrimitiveType::kTriangleStrip, 8,
438 {
439 .reference_centers = {center, center},
440 .radii = {radius, radius},
441 .half_width = half_width,
442 });
443 } else {
444 return FilledCircle(view_transform, center, radius);
445 }
446 }

References impeller::ComputeQuadrantDivisions(), and impeller::Matrix::GetMaxBasisLength().

## ◆ Tessellate()

Tessellator::Result impeller::Tessellator::Tessellate | ( | const Path & | path,
|  | Scalar | tolerance,
|  | const BuilderCallback & | callback
| ) |  |

Generates filled triangles from the path. A callback is invoked once for the entire tessellation.

Parameters

  [in] | path | The path to tessellate.
  [in] | tolerance | The tolerance value for conversion of the path to a polyline. This value is often derived from the Matrix::GetMaxBasisLength of the CTM applied to the path for rendering.
  [in] | callback | The callback, return false to indicate failure.

Returns
  The result status of the tessellation.

Feed contour information to the tessellator.

Let's tessellate.

Definition at line 58 of file tessellator.cc.

60 {
61 if (!callback) {
62 return Result::kInputError;
63 }
64
65 point_buffer_->clear();
66 auto polyline =
67 path.CreatePolyline(tolerance, std::move(point_buffer_),
68 [this](Path::Polyline::PointBufferPtr point_buffer) {
69 point_buffer_ = std::move(point_buffer);
70 });
71
72 auto fill_type = path.GetFillType();
73
74 if (polyline.points->empty()) {
75 return Result::kInputError;
76 }
77
78 auto tessellator = c_tessellator_.get();
79 if (!tessellator) {
80 return Result::kTessellationError;
81 }
82
83 constexpr int kVertexSize = 2;
84 constexpr int kPolygonSize = 3;
85
86 //----------------------------------------------------------------------------
87 /// Feed contour information to the tessellator.
88 ///
89 static_assert(sizeof(Point) == 2 * sizeof(float));
90 for (size_t contour_i = 0; contour_i < polyline.contours.size();
91 contour_i++) {
92 size_t start_point_index, end_point_index;
93 std::tie(start_point_index, end_point_index) =
94 polyline.GetContourPointBounds(contour_i);
95
96 ::tessAddContour(tessellator, // the C tessellator
97 kVertexSize, //
98 polyline.points->data() + start_point_index, //
99 sizeof(Point), //
100 end_point_index - start_point_index //
101 );
102 }
103
104 //----------------------------------------------------------------------------
105 /// Let's tessellate.
106 ///
107 auto result = ::tessTesselate(tessellator, // tessellator
108 ToTessWindingRule(fill_type), // winding
109 TESS_POLYGONS, // element type
110 kPolygonSize, // polygon size
111 kVertexSize, // vertex size
112 nullptr // normal (null is automatic)
113 );
114
115 if (result != 1) {
116 return Result::kTessellationError;
117 }
118
119 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
120
121 // We default to using a 16bit index buffer, but in cases where we generate
122 // more tessellated data than this can contain we need to fall back to
123 // dropping the index buffer entirely. Instead code could instead switch to
124 // a uint32 index buffer, but this is done for simplicity with the other
125 // fast path above.
126 if (element_item_count < USHRT_MAX) {
127 int vertex_item_count = tessGetVertexCount(tessellator);
128 auto vertices = tessGetVertices(tessellator);
129 auto elements = tessGetElements(tessellator);
130
131 // libtess uses an int index internally due to usage of -1 as a sentinel
132 // value.
133 std::vector<uint16_t> indices(element_item_count);
134 for (int i = 0; i < element_item_count; i++) {
135 indices[i] = static_cast<uint16_t>(elements[i]);
136 }
137 if (!callback(vertices, vertex_item_count, indices.data(),
138 element_item_count)) {
139 return Result::kInputError;
140 }
141 } else {
142 std::vector<Point> points;
143 std::vector<float> data;
144
145 int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize;
146 auto vertices = tessGetVertices(tessellator);
147 points.reserve(vertex_item_count);
148 for (int i = 0; i < vertex_item_count; i += 2) {
149 points.emplace_back(vertices[i], vertices[i + 1]);
150 }
151
152 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
153 auto elements = tessGetElements(tessellator);
154 data.reserve(element_item_count);
155 for (int i = 0; i < element_item_count; i++) {
156 data.emplace_back(points[elements[i]].x);
157 data.emplace_back(points[elements[i]].y);
158 }
159 if (!callback(data.data(), element_item_count, nullptr, 0u)) {
160 return Result::kInputError;
161 }
162 }
163
164 return Result::kSuccess;
165 }

References impeller::Path::CreatePolyline(), impeller::Path::GetFillType(), kInputError, kSuccess, kTessellationError, polyline, and impeller::ToTessWindingRule().

Referenced by impeller::BM_Polyline(), impeller::Tessellate(), impeller::testing::TEST(), and impeller::testing::TEST_P().

## ◆ TessellateConvex()

std::vector< Point > impeller::Tessellator::TessellateConvex | ( | const Path & | path,
|  | Scalar | tolerance
| ) |  |

Given a convex path, create a triangle fan structure.

Parameters

  [in] | path | The path to tessellate.
  [in] | tolerance | The tolerance value for conversion of the path to a polyline. This value is often derived from the Matrix::GetMaxBasisLength of the CTM applied to the path for rendering.

Returns
  A point vector containing the vertices in triangle strip format.

Definition at line 179 of file tessellator.cc.

180 {
181 FML_DCHECK(point_buffer_);
182
183 std::vector<Point> output;
184 point_buffer_->clear();
185 auto polyline =
186 path.CreatePolyline(tolerance, std::move(point_buffer_),
187 [this](Path::Polyline::PointBufferPtr point_buffer) {
188 point_buffer_ = std::move(point_buffer);
189 });
190 if (polyline.points->size() == 0) {
191 return output;
192 }
193
194 output.reserve(polyline.points->size() +
195 (4 * (polyline.contours.size() - 1)));
196 bool previous_contour_odd_points = false;
197 for (auto j = 0u; j < polyline.contours.size(); j++) {
198 auto [start, end] = polyline.GetContourPointBounds(j);
199 auto first_point = polyline.GetPoint(start);
200
201 // Some polygons will not self close and an additional triangle
202 // must be inserted, others will self close and we need to avoid
203 // inserting an extra triangle.
204 if (polyline.GetPoint(end - 1) == first_point) {
205 end--;
206 }
207
208 if (j > 0) {
209 // Triangle strip break.
210 output.emplace_back(output.back());
211 output.emplace_back(first_point);
212 output.emplace_back(first_point);
213
214 // If the contour has an odd number of points, insert an extra point when
215 // bridging to the next contour to preserve the correct triangle winding
216 // order.
217 if (previous_contour_odd_points) {
218 output.emplace_back(first_point);
219 }
220 } else {
221 output.emplace_back(first_point);
222 }
223
224 size_t a = start + 1;
225 size_t b = end - 1;
226 while (a < b) {
227 output.emplace_back(polyline.GetPoint(a));
228 output.emplace_back(polyline.GetPoint(b));
229 a++;
230 b--;
231 }
232 if (a == b) {
233 previous_contour_odd_points = false;
234 output.emplace_back(polyline.GetPoint(a));
235 } else {
236 previous_contour_odd_points = true;
237 }
238 }
239 return output;
240 }

References impeller::saturated::b, impeller::Path::CreatePolyline(), and polyline.

Referenced by impeller::BM_Convex(), and impeller::testing::TEST().

## Member Data Documentation

## ◆ kCircleTolerance

constexpr Scalar impeller::Tessellator::kCircleTolerance = 0.1f
| static constexpr

The pixel tolerance used by the algorighm to determine how many divisions to create for a circle.

No point on the polygon of vertices should deviate from the true circle by more than this tolerance.

Definition at line 228 of file tessellator.h.

Referenced by impeller::ComputeQuadrantDivisions(), and impeller::testing::TEST().

The documentation for this class was generated from the following files:

- impeller/tessellator/tessellator.h
- impeller/tessellator/tessellator.cc

impeller::kAlloc
static const TESSalloc kAlloc
Definition: tessellator.cc:24
impeller::EllipticalVertexGenerator
Tessellator::EllipticalVertexGenerator EllipticalVertexGenerator
Definition: tessellator.cc:398
polyline
const Path::Polyline & polyline
Definition: stroke_path_geometry.cc:292
impeller::kEhCloseEnough
constexpr float kEhCloseEnough
Definition: constants.h:56
impeller::Tessellator::Result::kInputError
@ kInputError
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::ComputeQuadrantDivisions
static size_t ComputeQuadrantDivisions(Scalar pixel_radius)
Definition: tessellator.cc:318
impeller::PrimitiveType::kTriangleStrip
@ kTriangleStrip
impeller::Point
TPoint< Scalar > Point
Definition: point.h:316
impeller::Tessellator::Result::kTessellationError
@ kTessellationError
impeller::DestroyTessellator
void DestroyTessellator(TESStesselator *tessellator)
Definition: tessellator.cc:242
impeller::Tessellator::Result::kSuccess
@ kSuccess
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::saturated::b
SI b
Definition: saturated_math.h:87
impeller::ToTessWindingRule
static int ToTessWindingRule(FillType fill_type)
Definition: tessellator.cc:48
impeller::Path::Polyline::PointBufferPtr
std::unique_ptr< std::vector< Point > > PointBufferPtr
Definition: path.h:97
impeller::CTessellator
std::unique_ptr< TESStesselator, decltype(&DestroyTessellator)> CTessellator
Definition: tessellator.h:24