| 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...
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 39 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 189 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 86 of file tessellator.h.

## Member Enumeration Documentation

## ◆ Result

enum impeller::Tessellator::Result
| strong

Enumerator
kSuccess |
kInputError |
kTessellationError |

Definition at line 78 of file tessellator.h.

78 {
79 kSuccess,
80 kInputError,
81 kTessellationError,
82 };

## 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

## ◆ 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 390 of file tessellator.cc.

393 {
394 auto divisions =
395 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * radius);
396 return EllipticalVertexGenerator(Tessellator::GenerateFilledCircle,
397 GetTrigsForDivisions(divisions),
398 PrimitiveType::kTriangleStrip, 4,
399 {
400 .reference_centers = {center, center},
401 .radii = {radius, radius},
402 .half_width = -1.0f,
403 });
404 }

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 450 of file tessellator.cc.

452 {
453 if (bounds.IsSquare()) {
454 return FilledCircle(view_transform, bounds.GetCenter(),
455 bounds.GetWidth() * 0.5f);
456 }
457 auto max_radius = bounds.GetSize().MaxDimension();
458 auto divisions =
459 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * max_radius);
460 auto center = bounds.GetCenter();
461 return EllipticalVertexGenerator(Tessellator::GenerateFilledEllipse,
462 GetTrigsForDivisions(divisions),
463 PrimitiveType::kTriangleStrip, 4,
464 {
465 .reference_centers = {center, center},
466 .radii = bounds.GetSize() * 0.5f,
467 .half_width = -1.0f,
468 });
469 }

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

## ◆ 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 471 of file tessellator.cc.

474 {
475 if (radii.width * 2 < bounds.GetWidth() ||
476 radii.height * 2 < bounds.GetHeight()) {
477 auto max_radius = radii.MaxDimension();
478 auto divisions = ComputeQuadrantDivisions(
479 view_transform.GetMaxBasisLength() * max_radius);
480 auto upper_left = bounds.GetLeftTop() + radii;
481 auto lower_right = bounds.GetRightBottom() - radii;
482 return EllipticalVertexGenerator(Tessellator::GenerateFilledRoundRect,
483 GetTrigsForDivisions(divisions),
484 PrimitiveType::kTriangleStrip, 4,
485 {
486 .reference_centers =
487 {
488 upper_left,
489 lower_right,
490 },
491 .radii = radii,
492 .half_width = -1.0f,
493 });
494 } else {
495 return FilledEllipse(view_transform, bounds);
496 }
497 }

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 427 of file tessellator.cc.

431 {
432 auto along = p1 - p0;
433 auto length = along.GetLength();
434 if (length > kEhCloseEnough) {
435 auto divisions =
436 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * radius);
437 return EllipticalVertexGenerator(Tessellator::GenerateRoundCapLine,
438 GetTrigsForDivisions(divisions),
439 PrimitiveType::kTriangleStrip, 4,
440 {
441 .reference_centers = {p0, p1},
442 .radii = {radius, radius},
443 .half_width = -1.0f,
444 });
445 } else {
446 return FilledCircle(view_transform, p0, radius);
447 }
448 }

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 406 of file tessellator.cc.

410 {
411 if (half_width > 0) {
412 auto divisions = ComputeQuadrantDivisions(
413 view_transform.GetMaxBasisLength() * radius + half_width);
414 return EllipticalVertexGenerator(Tessellator::GenerateStrokedCircle,
415 GetTrigsForDivisions(divisions),
416 PrimitiveType::kTriangleStrip, 8,
417 {
418 .reference_centers = {center, center},
419 .radii = {radius, radius},
420 .half_width = half_width,
421 });
422 } else {
423 return FilledCircle(view_transform, center, radius);
424 }
425 }

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 64 of file tessellator.cc.

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

References impeller::Path::CreatePolyline(), impeller::Path::GetFillType(), kInputError, kSuccess, kTessellationError, 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 173 of file tessellator.cc.

174 {
175 std::vector<Point> output;
176
177 point_buffer_->clear();
178 auto polyline =
179 path.CreatePolyline(tolerance, std::move(point_buffer_),
180 [this](Path::Polyline::PointBufferPtr point_buffer) {
181 point_buffer_ = std::move(point_buffer);
182 });
183
184 output.reserve(polyline.points->size() +
185 (4 * (polyline.contours.size() - 1)));
186 for (auto j = 0u; j < polyline.contours.size(); j++) {
187 auto [start, end] = polyline.GetContourPointBounds(j);
188 auto first_point = polyline.GetPoint(start);
189
190 // Some polygons will not self close and an additional triangle
191 // must be inserted, others will self close and we need to avoid
192 // inserting an extra triangle.
193 if (polyline.GetPoint(end - 1) == first_point) {
194 end--;
195 }
196
197 if (j > 0) {
198 // Triangle strip break.
199 output.emplace_back(output.back());
200 output.emplace_back(first_point);
201 output.emplace_back(first_point);
202 } else {
203 output.emplace_back(first_point);
204 }
205
206 size_t a = start + 1;
207 size_t b = end - 1;
208 while (a < b) {
209 output.emplace_back(polyline.GetPoint(a));
210 output.emplace_back(polyline.GetPoint(b));
211 a++;
212 b--;
213 }
214 if (a == b) {
215 output.emplace_back(polyline.GetPoint(a));
216 }
217 }
218 return output;
219 }

References impeller::Path::CreatePolyline(), and impeller::Path::Polyline::GetContourPointBounds().

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 226 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:377
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:390
impeller::ComputeQuadrantDivisions
static size_t ComputeQuadrantDivisions(Scalar pixel_radius)
Definition: tessellator.cc:297
impeller::PrimitiveType::kTriangleStrip
@ kTriangleStrip
impeller::Point
TPoint< Scalar > Point
Definition: point.h:308
impeller::Tessellator::Result::kTessellationError
@ kTessellationError
impeller::DestroyTessellator
void DestroyTessellator(TESStesselator *tessellator)
Definition: tessellator.cc:221
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:450
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:101
impeller::CTessellator
std::unique_ptr< TESStesselator, decltype(&DestroyTessellator)> CTessellator
Definition: tessellator.h:25