Flutter Impeller
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  ArcVertexGenerator
 The |VertexGenerator| implementation common to all shapes that are based on a polygonal representation of an ellipse. More...
 
class  EllipticalVertexGenerator
 The |VertexGenerator| implementation common to all shapes that are based on a polygonal representation of an ellipse. More...
 
class  Trigs
 
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 class  Result {
  kSuccess ,
  kInputError ,
  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...
 

Public Member Functions

 Tessellator ()
 
virtual ~Tessellator ()
 
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. 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...
 
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 oval_bounds with the given stroke half_width with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. The outer edge of the stroked arc is generated at (radius + half_width) and the inner edge is generated at (radius - half_width). More...
 
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 oval_bounds with the given stroke half_width with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. The outer edge of the stroked arc 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...
 
std::vector< Point > & GetStrokePointCache ()
 Retrieve a pre-allocated arena of kPointArenaSize points. More...
 
Trigs GetTrigsForDeviceRadius (Scalar pixel_radius)
 

Static Public Member Functions

static void TessellateConvexInternal (const PathSource &path, std::vector< Point > &point_buffer, std::vector< uint16_t > &index_buffer, Scalar tolerance)
 

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

Protected Attributes

std::unique_ptr< std::vector< Point > > point_buffer_
 Used for polyline generation. More...
 
std::unique_ptr< std::vector< uint16_t > > index_buffer_
 
std::vector< Pointstroke_points_
 Used for stroke path generation. More...
 

Detailed Description

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

Also contains functionality for optimized generation of circles and ellipses.

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

Definition at line 37 of file tessellator.h.

Member Typedef Documentation

◆ 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 97 of file tessellator.h.

Member Enumeration Documentation

◆ Result

Enumerator
kSuccess 
kInputError 
kTessellationError 

Definition at line 89 of file tessellator.h.

89  {
90  kSuccess,
91  kInputError,
92  kTessellationError,
93  };

Constructor & Destructor Documentation

◆ Tessellator()

impeller::Tessellator::Tessellator ( )

Definition at line 296 of file tessellator.cc.

297  : point_buffer_(std::make_unique<std::vector<Point>>()),
298  index_buffer_(std::make_unique<std::vector<uint16_t>>()),
300  point_buffer_->reserve(2048);
301  index_buffer_->reserve(2048);
302 }
std::vector< Point > stroke_points_
Used for stroke path generation.
Definition: tessellator.h:382
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
static constexpr size_t kPointArenaSize
The size of the point arena buffer stored on the tessellator.
Definition: tessellator.h:25

References index_buffer_, and point_buffer_.

◆ ~Tessellator()

impeller::Tessellator::~Tessellator ( )
virtualdefault

Member Function Documentation

◆ FilledArc()

ArcVertexGenerator impeller::Tessellator::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 oval_bounds with the given stroke half_width with enough polygon sub-divisions to provide reasonable fidelity when viewed under the given view transform. The outer edge of the stroked arc 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 oval bounds.

Definition at line 556 of file tessellator.cc.

558  {
559  size_t divisions = ComputeQuadrantDivisions(
560  view_transform.GetMaxBasisLengthXY() * arc.GetOvalSize().MaxDimension());
561 
562  return ArcVertexGenerator(
563  arc.ComputeIterations(divisions), GetTrigsForDivisions(divisions),
564  arc.GetOvalBounds(), arc.IncludeCenter(), supports_triangle_fans);
565 };
Tessellator::ArcVertexGenerator ArcVertexGenerator
Definition: tessellator.cc:439

References impeller::Arc::ComputeIterations(), impeller::Matrix::GetMaxBasisLengthXY(), impeller::Arc::GetOvalBounds(), impeller::Arc::GetOvalSize(), impeller::Arc::IncludeCenter(), and impeller::TSize< T >::MaxDimension().

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

455  {
456  size_t divisions =
457  ComputeQuadrantDivisions(view_transform.GetMaxBasisLengthXY() * radius);
458  return EllipticalVertexGenerator(Tessellator::GenerateFilledCircle,
459  GetTrigsForDivisions(divisions),
461  {
462  .reference_centers = {center, center},
463  .radii = {radius, radius},
464  .half_width = -1.0f,
465  });
466 }
Tessellator::EllipticalVertexGenerator EllipticalVertexGenerator
Definition: tessellator.cc:438

References impeller::Matrix::GetMaxBasisLengthXY().

Referenced by FilledEllipse(), and RoundCapLine().

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

608  {
609  if (bounds.IsSquare()) {
610  return FilledCircle(view_transform, bounds.GetCenter(),
611  bounds.GetWidth() * 0.5f);
612  }
613  auto max_radius = bounds.GetSize().MaxDimension();
614  auto divisions = ComputeQuadrantDivisions(
615  view_transform.GetMaxBasisLengthXY() * max_radius);
616  auto center = bounds.GetCenter();
617  return EllipticalVertexGenerator(Tessellator::GenerateFilledEllipse,
618  GetTrigsForDivisions(divisions),
620  {
621  .reference_centers = {center, center},
622  .radii = bounds.GetSize() * 0.5f,
623  .half_width = -1.0f,
624  });
625 }
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

References FilledCircle(), impeller::TRect< T >::GetCenter(), impeller::Matrix::GetMaxBasisLengthXY(), impeller::TRect< T >::GetSize(), impeller::TRect< T >::GetWidth(), impeller::TRect< T >::IsSquare(), and impeller::kTriangleStrip.

Referenced by FilledRoundRect().

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

630  {
631  if (radii.width * 2 < bounds.GetWidth() ||
632  radii.height * 2 < bounds.GetHeight()) {
633  auto max_radius = radii.MaxDimension();
634  auto divisions = ComputeQuadrantDivisions(
635  view_transform.GetMaxBasisLengthXY() * max_radius);
636  auto upper_left = bounds.GetLeftTop() + radii;
637  auto lower_right = bounds.GetRightBottom() - radii;
638  return EllipticalVertexGenerator(Tessellator::GenerateFilledRoundRect,
639  GetTrigsForDivisions(divisions),
641  {
642  .reference_centers =
643  {
644  upper_left,
645  lower_right,
646  },
647  .radii = radii,
648  .half_width = -1.0f,
649  });
650  } else {
651  return FilledEllipse(view_transform, bounds);
652  }
653 }
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

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

◆ GetStrokePointCache()

std::vector< Point > & impeller::Tessellator::GetStrokePointCache ( )

Retrieve a pre-allocated arena of kPointArenaSize points.

Definition at line 306 of file tessellator.cc.

306  {
307  return stroke_points_;
308 }

References stroke_points_.

◆ GetTrigsForDeviceRadius()

Tessellator::Trigs impeller::Tessellator::GetTrigsForDeviceRadius ( Scalar  pixel_radius)

Return a vector of Trig (cos, sin pairs) structs for a 90 degree circle quadrant of the specified pixel radius

Definition at line 310 of file tessellator.cc.

310  {
311  return GetTrigsForDivisions(ComputeQuadrantDivisions(pixel_radius));
312 }

Referenced by impeller::ArcStrokeGeometry::Dispatch(), impeller::StrokeRectGeometry::GetPositionBuffer(), impeller::StrokePathSegmentReceiver::RecordArc(), and impeller::testing::TEST().

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

587  {
588  auto along = p1 - p0;
589  auto length = along.GetLength();
590  if (length > kEhCloseEnough) {
591  auto divisions =
592  ComputeQuadrantDivisions(view_transform.GetMaxBasisLengthXY() * radius);
593  return EllipticalVertexGenerator(Tessellator::GenerateRoundCapLine,
594  GetTrigsForDivisions(divisions),
596  {
597  .reference_centers = {p0, p1},
598  .radii = {radius, radius},
599  .half_width = -1.0f,
600  });
601  } else {
602  return FilledCircle(view_transform, p0, radius);
603  }
604 }
constexpr float kEhCloseEnough
Definition: constants.h:57

References FilledCircle(), impeller::TPoint< T >::GetLength(), impeller::Matrix::GetMaxBasisLengthXY(), impeller::kEhCloseEnough, and impeller::kTriangleStrip.

◆ StrokedArc()

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

Note that the arc may not include the center and its bounds must be a perfect circle (width == height)

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 oval bounds.

Definition at line 567 of file tessellator.cc.

570  {
571  FML_DCHECK(half_width > 0);
572  FML_DCHECK(arc.IsPerfectCircle());
573  FML_DCHECK(!arc.IncludeCenter());
574  size_t divisions =
575  ComputeQuadrantDivisions(view_transform.GetMaxBasisLengthXY() *
576  (arc.GetOvalSize().MaxDimension() + half_width));
577 
578  return ArcVertexGenerator(arc.ComputeIterations(divisions),
579  GetTrigsForDivisions(divisions),
580  arc.GetOvalBounds(), half_width, cap);
581 }

References impeller::Arc::ComputeIterations(), impeller::Matrix::GetMaxBasisLengthXY(), impeller::Arc::GetOvalBounds(), impeller::Arc::GetOvalSize(), impeller::Arc::IncludeCenter(), impeller::Arc::IsPerfectCircle(), and impeller::TSize< T >::MaxDimension().

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

472  {
473  if (half_width > 0) {
474  auto divisions = ComputeQuadrantDivisions(
475  view_transform.GetMaxBasisLengthXY() * radius + half_width);
476  return EllipticalVertexGenerator(Tessellator::GenerateStrokedCircle,
477  GetTrigsForDivisions(divisions),
479  {
480  .reference_centers = {center, center},
481  .radii = {radius, radius},
482  .half_width = half_width,
483  });
484  } else {
485  return FilledCircle(view_transform, center, radius);
486  }
487 }

References impeller::Matrix::GetMaxBasisLengthXY().

◆ TessellateConvex()

VertexBuffer impeller::Tessellator::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.

Parameters
[in]pathThe path to tessellate.
[in]host_bufferThe host buffer for allocation of vertices/index data.
[in]toleranceThe tolerance value for conversion of the path to a polyline. This value is often derived from the Matrix::GetMaxBasisLengthXY of the CTM applied to the path for rendering.
Returns
A vertex buffer containing all data from the provided curve.

Definition at line 314 of file tessellator.cc.

318  {
319  if (supports_primitive_restart) {
320  // Primitive Restart.
321  const auto [point_count, contour_count] =
322  PathTessellator::CountFillStorage(path, tolerance);
323  BufferView point_buffer = host_buffer.Emplace(
324  nullptr, sizeof(Point) * point_count, alignof(Point));
325  BufferView index_buffer = host_buffer.Emplace(
326  nullptr, sizeof(uint16_t) * (point_count + contour_count),
327  alignof(uint16_t));
328 
329  if (supports_triangle_fan) {
330  FanPathVertexWriter writer(
331  reinterpret_cast<Point*>(point_buffer.GetBuffer()->OnGetContents() +
332  point_buffer.GetRange().offset),
333  reinterpret_cast<uint16_t*>(
334  index_buffer.GetBuffer()->OnGetContents() +
335  index_buffer.GetRange().offset));
336  PathTessellator::PathToFilledVertices(path, writer, tolerance);
337  FML_DCHECK(writer.GetPointCount() <= point_count);
338  FML_DCHECK(writer.GetIndexCount() <= (point_count + contour_count));
339  point_buffer.GetBuffer()->Flush(point_buffer.GetRange());
340  index_buffer.GetBuffer()->Flush(index_buffer.GetRange());
341 
342  return VertexBuffer{
343  .vertex_buffer = std::move(point_buffer),
344  .index_buffer = std::move(index_buffer),
345  .vertex_count = writer.GetIndexCount(),
346  .index_type = IndexType::k16bit,
347  };
348  } else {
349  StripPathVertexWriter writer(
350  reinterpret_cast<Point*>(point_buffer.GetBuffer()->OnGetContents() +
351  point_buffer.GetRange().offset),
352  reinterpret_cast<uint16_t*>(
353  index_buffer.GetBuffer()->OnGetContents() +
354  index_buffer.GetRange().offset));
355  PathTessellator::PathToFilledVertices(path, writer, tolerance);
356  FML_DCHECK(writer.GetPointCount() <= point_count);
357  FML_DCHECK(writer.GetIndexCount() <= (point_count + contour_count));
358  point_buffer.GetBuffer()->Flush(point_buffer.GetRange());
359  index_buffer.GetBuffer()->Flush(index_buffer.GetRange());
360 
361  return VertexBuffer{
362  .vertex_buffer = std::move(point_buffer),
363  .index_buffer = std::move(index_buffer),
364  .vertex_count = writer.GetIndexCount(),
365  .index_type = IndexType::k16bit,
366  };
367  }
368  }
369 
370  FML_DCHECK(point_buffer_);
371  FML_DCHECK(index_buffer_);
373 
374  if (point_buffer_->empty()) {
375  return VertexBuffer{
376  .vertex_buffer = {},
377  .index_buffer = {},
378  .vertex_count = 0u,
379  .index_type = IndexType::k16bit,
380  };
381  }
382 
383  BufferView vertex_buffer = host_buffer.Emplace(
384  point_buffer_->data(), sizeof(Point) * point_buffer_->size(),
385  alignof(Point));
386 
387  BufferView index_buffer = host_buffer.Emplace(
388  index_buffer_->data(), sizeof(uint16_t) * index_buffer_->size(),
389  alignof(uint16_t));
390 
391  return VertexBuffer{
392  .vertex_buffer = std::move(vertex_buffer),
393  .index_buffer = std::move(index_buffer),
394  .vertex_count = index_buffer_->size(),
395  .index_type = IndexType::k16bit,
396  };
397 }
static void PathToFilledVertices(const PathSource &source, VertexWriter &writer, Scalar scale)
static std::pair< size_t, size_t > CountFillStorage(const PathSource &source, Scalar scale)
static void TessellateConvexInternal(const PathSource &path, std::vector< Point > &point_buffer, std::vector< uint16_t > &index_buffer, Scalar tolerance)
Definition: tessellator.cc:399
TPoint< Scalar > Point
Definition: point.h:327

References impeller::PathTessellator::CountFillStorage(), impeller::HostBuffer::Emplace(), impeller::DeviceBuffer::Flush(), impeller::BufferView::GetBuffer(), impeller::BufferView::GetRange(), index_buffer_, impeller::k16bit, impeller::Range::offset, impeller::DeviceBuffer::OnGetContents(), impeller::PathTessellator::PathToFilledVertices(), point_buffer_, TessellateConvexInternal(), and impeller::VertexBuffer::vertex_buffer.

◆ TessellateConvexInternal()

void impeller::Tessellator::TessellateConvexInternal ( const PathSource path,
std::vector< Point > &  point_buffer,
std::vector< uint16_t > &  index_buffer,
Scalar  tolerance 
)
static

Visible for testing.

This method only exists for the ease of benchmarking without using the real allocator needed by the [host_buffer].

Definition at line 399 of file tessellator.cc.

402  {
403  point_buffer.clear();
404  index_buffer.clear();
405 
406  GLESPathVertexWriter writer(point_buffer, index_buffer);
407 
408  PathTessellator::PathToFilledVertices(path, writer, tolerance);
409 }

References impeller::PathTessellator::PathToFilledVertices().

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

Member Data Documentation

◆ index_buffer_

std::unique_ptr<std::vector<uint16_t> > impeller::Tessellator::index_buffer_
protected

Definition at line 380 of file tessellator.h.

Referenced by TessellateConvex(), and Tessellator().

◆ kCircleTolerance

constexpr Scalar impeller::Tessellator::kCircleTolerance = 0.1f
staticconstexpr

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 263 of file tessellator.h.

Referenced by impeller::testing::TEST().

◆ point_buffer_

std::unique_ptr<std::vector<Point> > impeller::Tessellator::point_buffer_
protected

Used for polyline generation.

Definition at line 379 of file tessellator.h.

Referenced by TessellateConvex(), and Tessellator().

◆ stroke_points_

std::vector<Point> impeller::Tessellator::stroke_points_
protected

Used for stroke path generation.

Definition at line 382 of file tessellator.h.

Referenced by GetStrokePointCache().


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