Flutter Impeller
tessellator.cc
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 
6 #include <cstdint>
7 #include <cstring>
8 
11 
12 namespace {
13 static constexpr int kPrecomputedDivisionCount = 1024;
14 
15 static int kPrecomputedDivisions[kPrecomputedDivisionCount] = {
16  // clang-format off
17  1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7,
18  8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10,
19  10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13,
20  13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14,
21  15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16,
22  16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
23  18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19,
24  19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
25  20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
26  22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23,
27  23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24,
28  24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
29  25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26,
30  26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27,
31  27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28,
32  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29,
33  29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
34  29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
35  30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
36  31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32,
37  32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 33, 33,
38  33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
39  33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
40  34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35,
41  35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36,
42  36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
43  36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
44  37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38, 38, 38, 38,
45  38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38,
46  38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
47  39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40,
48  40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
49  40, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41,
50  41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
51  41, 41, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
52  42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43,
53  43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43,
54  43, 43, 43, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 44, 44,
55  44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44,
56  44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
57  45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
58  45, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46,
59  46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 47,
60  47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47,
61  47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48, 48,
62  48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
63  48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49,
64  49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49,
65  49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 50, 50, 50, 50, 50,
66  50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
67  50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51,
68  51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
69  51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52,
70  52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52,
71  52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53,
72  53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53,
73  53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 54,
74  54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
75  54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
76  54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
77  55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
78  55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
79  56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
80  56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57,
81  // clang-format on
82 };
83 
84 static size_t ComputeQuadrantDivisions(impeller::Scalar pixel_radius) {
85  if (pixel_radius <= 0.0) {
86  return 1;
87  }
88  int radius_index = ceil(pixel_radius);
89  if (radius_index < kPrecomputedDivisionCount) {
90  return kPrecomputedDivisions[radius_index];
91  }
92 
93  // For a circle with N divisions per quadrant, the maximum deviation of
94  // the polgyon approximation from the true circle will be at the center
95  // of the base of each triangular pie slice. We can compute that distance
96  // by finding the midpoint of the line of the first slice and compare
97  // its distance from the center of the circle to the radius. We will aim
98  // to have the length of that bisector to be within |kCircleTolerance|
99  // from the radius in pixels.
100  //
101  // Each vertex will appear at an angle of:
102  // theta(i) = (kPi / 2) * (i / N) // for i in [0..N]
103  // with each point falling at:
104  // point(i) = r * (cos(theta), sin(theta))
105  // If we consider the unit circle to simplify the calculations below then
106  // we need to scale the tolerance from its absolute quantity into a unit
107  // circle fraction:
108  // k = tolerance / radius
109  // Using this scaled tolerance below to avoid multiplying by the radius
110  // throughout all of the math, we have:
111  // first point = (1, 0) // theta(0) == 0
112  // theta = kPi / 2 / N // theta(1)
113  // second point = (cos(theta), sin(theta)) = (c, s)
114  // midpoint = (first + second) * 0.5 = ((1 + c)/2, s/2)
115  // |midpoint| = sqrt((1 + c)*(1 + c)/4 + s*s/4)
116  // = sqrt((1 + c + c + c*c + s*s) / 4)
117  // = sqrt((1 + 2c + 1) / 4)
118  // = sqrt((2 + 2c) / 4)
119  // = sqrt((1 + c) / 2)
120  // = cos(theta / 2) // using half-angle cosine formula
121  // error = 1 - |midpoint| = 1 - cos(theta / 2)
122  // cos(theta/2) = 1 - error
123  // theta/2 = acos(1 - error)
124  // kPi / 2 / N / 2 = acos(1 - error)
125  // kPi / 4 / acos(1 - error) = N
126  // Since we need error <= k, we want divisions >= N, so we use:
127  // N = ceil(kPi / 4 / acos(1 - k))
128  //
129  // Math is confirmed in https://math.stackexchange.com/a/4132095
130  // (keeping in mind that we are computing quarter circle divisions here)
131  // which also points out a performance optimization that is accurate
132  // to within an over-estimation of 1 division would be:
133  // N = ceil(kPi / 4 / sqrt(2 * k))
134  // Since we have precomputed the divisions for radii up to 1024, we can
135  // afford to be more accurate using the acos formula here for larger radii.
136  double k = impeller::Tessellator::kCircleTolerance / pixel_radius;
137  return ceil(impeller::kPiOver4 / std::acos(1 - k));
138 }
139 
140 /// @brief A vertex writer that generates a triangle fan and requires primitive
141 /// restart.
142 class FanPathVertexWriter : public impeller::PathTessellator::VertexWriter {
143  public:
144  explicit FanPathVertexWriter(impeller::Point* point_buffer,
145  uint16_t* index_buffer)
146  : point_buffer_(point_buffer), index_buffer_(index_buffer) {}
147 
148  ~FanPathVertexWriter() = default;
149 
150  size_t GetIndexCount() const { return index_count_; }
151  size_t GetPointCount() const { return count_; }
152 
153  void EndContour() override {
154  if (count_ == 0) {
155  return;
156  }
157  index_buffer_[index_count_++] = 0xFFFF;
158  }
159 
160  void Write(impeller::Point point) override {
161  index_buffer_[index_count_++] = count_;
162  point_buffer_[count_++] = point;
163  }
164 
165  private:
166  size_t count_ = 0;
167  size_t index_count_ = 0;
168  impeller::Point* point_buffer_ = nullptr;
169  uint16_t* index_buffer_ = nullptr;
170 };
171 
172 /// @brief A vertex writer that generates a triangle strip and requires
173 /// primitive restart.
174 class StripPathVertexWriter : public impeller::PathTessellator::VertexWriter {
175  public:
176  explicit StripPathVertexWriter(impeller::Point* point_buffer,
177  uint16_t* index_buffer)
178  : point_buffer_(point_buffer), index_buffer_(index_buffer) {}
179 
180  ~StripPathVertexWriter() = default;
181 
182  size_t GetIndexCount() const { return index_count_; }
183  size_t GetPointCount() const { return count_; }
184 
185  void EndContour() override {
186  if (count_ == 0u || contour_start_ == count_ - 1) {
187  // Empty or first contour.
188  return;
189  }
190 
191  size_t start = contour_start_;
192  size_t end = count_ - 1;
193 
194  index_buffer_[index_count_++] = start;
195 
196  size_t a = start + 1;
197  size_t b = end;
198  while (a < b) {
199  index_buffer_[index_count_++] = a;
200  index_buffer_[index_count_++] = b;
201  a++;
202  b--;
203  }
204  if (a == b) {
205  index_buffer_[index_count_++] = a;
206  }
207 
208  contour_start_ = count_;
209  index_buffer_[index_count_++] = 0xFFFF;
210  }
211 
212  void Write(impeller::Point point) override {
213  point_buffer_[count_++] = point;
214  }
215 
216  private:
217  size_t count_ = 0;
218  size_t index_count_ = 0;
219  size_t contour_start_ = 0;
220  impeller::Point* point_buffer_ = nullptr;
221  uint16_t* index_buffer_ = nullptr;
222 };
223 
224 /// @brief A vertex writer that has no hardware requirements.
225 class GLESPathVertexWriter : public impeller::PathTessellator::VertexWriter {
226  public:
227  explicit GLESPathVertexWriter(std::vector<impeller::Point>& points,
228  std::vector<uint16_t>& indices)
229  : points_(points), indices_(indices) {}
230 
231  ~GLESPathVertexWriter() = default;
232 
233  void EndContour() override {
234  if (points_.size() == 0u || contour_start_ == points_.size() - 1) {
235  // Empty or first contour.
236  return;
237  }
238 
239  auto start = contour_start_;
240  auto end = points_.size() - 1;
241  // All filled paths are drawn as if they are closed, but if
242  // there is an explicit close then a lineTo to the origin
243  // is inserted. This point isn't strictly necesary to
244  // correctly render the shape and can be dropped.
245  if (points_[end] == points_[start]) {
246  end--;
247  }
248 
249  // Triangle strip break for subsequent contours
250  if (contour_start_ != 0) {
251  auto back = indices_.back();
252  indices_.push_back(back);
253  indices_.push_back(start);
254  indices_.push_back(start);
255 
256  // If the contour has an odd number of points, insert an extra point when
257  // bridging to the next contour to preserve the correct triangle winding
258  // order.
259  if (previous_contour_odd_points_) {
260  indices_.push_back(start);
261  }
262  } else {
263  indices_.push_back(start);
264  }
265 
266  size_t a = start + 1;
267  size_t b = end;
268  while (a < b) {
269  indices_.push_back(a);
270  indices_.push_back(b);
271  a++;
272  b--;
273  }
274  if (a == b) {
275  indices_.push_back(a);
276  previous_contour_odd_points_ = false;
277  } else {
278  previous_contour_odd_points_ = true;
279  }
280  contour_start_ = points_.size();
281  }
282 
283  void Write(impeller::Point point) override { points_.push_back(point); }
284 
285  private:
286  bool previous_contour_odd_points_ = false;
287  size_t contour_start_ = 0u;
288  std::vector<impeller::Point>& points_;
289  std::vector<uint16_t>& indices_;
290 };
291 
292 } // namespace
293 
294 namespace impeller {
295 
297  : point_buffer_(std::make_unique<std::vector<Point>>()),
298  index_buffer_(std::make_unique<std::vector<uint16_t>>()),
299  stroke_points_(kPointArenaSize) {
300  point_buffer_->reserve(2048);
301  index_buffer_->reserve(2048);
302 }
303 
304 Tessellator::~Tessellator() = default;
305 
306 std::vector<Point>& Tessellator::GetStrokePointCache() {
307  return stroke_points_;
308 }
309 
311  return GetTrigsForDivisions(ComputeQuadrantDivisions(pixel_radius));
312 }
313 
315  HostBuffer& host_buffer,
316  Scalar tolerance,
317  bool supports_primitive_restart,
318  bool supports_triangle_fan) {
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 }
398 
400  std::vector<Point>& point_buffer,
401  std::vector<uint16_t>& index_buffer,
402  Scalar tolerance) {
403  point_buffer.clear();
404  index_buffer.clear();
405 
406  GLESPathVertexWriter writer(point_buffer, index_buffer);
407 
408  PathTessellator::PathToFilledVertices(path, writer, tolerance);
409 }
410 
412  : Tessellator::Trigs(ComputeQuadrantDivisions(pixel_radius)) {}
413 
414 void Tessellator::Trigs::init(size_t divisions) {
415  if (!trigs_.empty()) {
416  return;
417  }
418 
419  // Either not cached yet, or we are using the temp storage...
420  trigs_.reserve(divisions + 1);
421 
422  double angle_scale = kPiOver2 / divisions;
423 
424  trigs_.emplace_back(1.0, 0.0);
425  for (size_t i = 1; i < divisions; i++) {
426  trigs_.emplace_back(Radians(i * angle_scale));
427  }
428  trigs_.emplace_back(0.0, 1.0);
429 }
430 
431 Tessellator::Trigs Tessellator::GetTrigsForDivisions(size_t divisions) {
432  return divisions < Tessellator::kCachedTrigCount
433  ? Trigs(precomputed_trigs_[divisions], divisions)
434  : Trigs(divisions);
435 }
436 
440 
441 EllipticalVertexGenerator::EllipticalVertexGenerator(
442  EllipticalVertexGenerator::GeneratorProc& generator,
443  Trigs&& trigs,
444  PrimitiveType triangle_type,
445  size_t vertices_per_trig,
446  Data&& data)
447  : impl_(generator),
448  trigs_(std::move(trigs)),
449  data_(data),
450  vertices_per_trig_(vertices_per_trig) {}
451 
452 EllipticalVertexGenerator Tessellator::FilledCircle(
453  const Matrix& view_transform,
454  const Point& center,
455  Scalar radius) {
456  size_t divisions =
457  ComputeQuadrantDivisions(view_transform.GetMaxBasisLengthXY() * radius);
458  return EllipticalVertexGenerator(Tessellator::GenerateFilledCircle,
459  GetTrigsForDivisions(divisions),
460  PrimitiveType::kTriangleStrip, 4,
461  {
462  .reference_centers = {center, center},
463  .radii = {radius, radius},
464  .half_width = -1.0f,
465  });
466 }
467 
468 EllipticalVertexGenerator Tessellator::StrokedCircle(
469  const Matrix& view_transform,
470  const Point& center,
471  Scalar radius,
472  Scalar half_width) {
473  if (half_width > 0) {
474  auto divisions = ComputeQuadrantDivisions(
475  view_transform.GetMaxBasisLengthXY() * radius + half_width);
476  return EllipticalVertexGenerator(Tessellator::GenerateStrokedCircle,
477  GetTrigsForDivisions(divisions),
478  PrimitiveType::kTriangleStrip, 8,
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 }
488 
490  Trigs&& trigs,
491  const Rect& oval_bounds,
492  bool use_center,
493  bool supports_triangle_fans)
494  : iteration_(iteration),
495  trigs_(std::move(trigs)),
496  oval_bounds_(oval_bounds),
497  use_center_(use_center),
498  half_width_(-1.0f),
499  cap_(Cap::kButt),
500  supports_triangle_fans_(supports_triangle_fans) {}
501 
502 ArcVertexGenerator::ArcVertexGenerator(const Arc::Iteration& iteration,
503  Trigs&& trigs,
504  const Rect& oval_bounds,
505  Scalar half_width,
506  Cap cap)
507  : iteration_(iteration),
508  trigs_(std::move(trigs)),
509  oval_bounds_(oval_bounds),
510  use_center_(false),
511  half_width_(half_width),
512  cap_(cap),
513  supports_triangle_fans_(false) {}
514 
516  return (half_width_ < 0 && supports_triangle_fans_)
519 }
520 
522  size_t count = iteration_.GetPointCount();
523  if (half_width_ > 0) {
524  FML_DCHECK(!use_center_);
525  FML_DCHECK(cap_ != Cap::kRound);
526  count *= 2;
527  if (cap_ == Cap::kSquare) {
528  count += 4;
529  }
530  } else if (supports_triangle_fans_) {
531  if (use_center_) {
532  count++;
533  }
534  } else {
535  // corrugated triangle fan
536  count += (count + 1) / 2;
537  }
538  return count;
539 }
540 
542  const TessellatedVertexProc& proc) const {
543  if (half_width_ > 0) {
544  FML_DCHECK(!use_center_);
545  Tessellator::GenerateStrokedArc(trigs_, iteration_, oval_bounds_,
546  half_width_, cap_, proc);
547  } else if (supports_triangle_fans_) {
548  Tessellator::GenerateFilledArcFan(trigs_, iteration_, oval_bounds_,
549  use_center_, proc);
550  } else {
551  Tessellator::GenerateFilledArcStrip(trigs_, iteration_, oval_bounds_,
552  use_center_, proc);
553  }
554 }
555 
557  const Arc& arc,
558  bool supports_triangle_fans) {
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 };
566 
568  const Arc& arc,
569  Cap cap,
570  Scalar half_width) {
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 }
582 
584  const Matrix& view_transform,
585  const Point& p0,
586  const Point& p1,
587  Scalar radius) {
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 }
605 
607  const Matrix& view_transform,
608  const Rect& bounds) {
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 }
626 
628  const Matrix& view_transform,
629  const Rect& bounds,
630  const Size& radii) {
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 }
654 
655 void Tessellator::GenerateFilledCircle(
656  const Trigs& trigs,
657  const EllipticalVertexGenerator::Data& data,
658  const TessellatedVertexProc& proc) {
659  auto center = data.reference_centers[0];
660  auto radius = data.radii.width;
661 
662  FML_DCHECK(center == data.reference_centers[1]);
663  FML_DCHECK(radius == data.radii.height);
664  FML_DCHECK(data.half_width < 0);
665 
666  // Quadrant 1 connecting with Quadrant 4:
667  for (auto& trig : trigs) {
668  auto offset = trig * radius;
669  proc({center.x - offset.x, center.y + offset.y});
670  proc({center.x - offset.x, center.y - offset.y});
671  }
672 
673  // The second half of the circle should be iterated in reverse, but
674  // we can instead iterate forward and swap the x/y values of the
675  // offset as the angles should be symmetric and thus should generate
676  // symmetrically reversed trig vectors.
677  // Quadrant 2 connecting with Quadrant 3:
678  for (auto& trig : trigs) {
679  auto offset = trig * radius;
680  proc({center.x + offset.y, center.y + offset.x});
681  proc({center.x + offset.y, center.y - offset.x});
682  }
683 }
684 
685 void Tessellator::GenerateStrokedCircle(
686  const Trigs& trigs,
687  const EllipticalVertexGenerator::Data& data,
688  const TessellatedVertexProc& proc) {
689  auto center = data.reference_centers[0];
690 
691  FML_DCHECK(center == data.reference_centers[1]);
692  FML_DCHECK(data.radii.IsSquare());
693  FML_DCHECK(data.half_width > 0 && data.half_width < data.radii.width);
694 
695  auto outer_radius = data.radii.width + data.half_width;
696  auto inner_radius = data.radii.width - data.half_width;
697 
698  // Zig-zag back and forth between points on the outer circle and the
699  // inner circle. Both circles are evaluated at the same number of
700  // quadrant divisions so the points for a given division should match
701  // 1 for 1 other than their applied radius.
702 
703  // Quadrant 1:
704  for (auto& trig : trigs) {
705  auto outer = trig * outer_radius;
706  auto inner = trig * inner_radius;
707  proc({center.x - outer.x, center.y - outer.y});
708  proc({center.x - inner.x, center.y - inner.y});
709  }
710 
711  // The even quadrants of the circle should be iterated in reverse, but
712  // we can instead iterate forward and swap the x/y values of the
713  // offset as the angles should be symmetric and thus should generate
714  // symmetrically reversed trig vectors.
715  // Quadrant 2:
716  for (auto& trig : trigs) {
717  auto outer = trig * outer_radius;
718  auto inner = trig * inner_radius;
719  proc({center.x + outer.y, center.y - outer.x});
720  proc({center.x + inner.y, center.y - inner.x});
721  }
722 
723  // Quadrant 3:
724  for (auto& trig : trigs) {
725  auto outer = trig * outer_radius;
726  auto inner = trig * inner_radius;
727  proc({center.x + outer.x, center.y + outer.y});
728  proc({center.x + inner.x, center.y + inner.y});
729  }
730 
731  // Quadrant 4:
732  for (auto& trig : trigs) {
733  auto outer = trig * outer_radius;
734  auto inner = trig * inner_radius;
735  proc({center.x - outer.y, center.y + outer.x});
736  proc({center.x - inner.y, center.y + inner.x});
737  }
738 }
739 
740 void Tessellator::GenerateFilledArcFan(const Trigs& trigs,
741  const Arc::Iteration& iteration,
742  const Rect& oval_bounds,
743  bool use_center,
744  const TessellatedVertexProc& proc) {
745  Point center = oval_bounds.GetCenter();
746  Size radii = oval_bounds.GetSize() * 0.5f;
747 
748  if (use_center) {
749  proc(center);
750  }
751  proc(center + iteration.start * radii);
752  for (size_t i = 0; i < iteration.quadrant_count; i++) {
753  auto quadrant = iteration.quadrants[i];
754  for (size_t j = quadrant.start_index; j < quadrant.end_index; j++) {
755  proc(center + trigs[j] * quadrant.axis * radii);
756  }
757  }
758  proc(center + iteration.end * radii);
759 }
760 
761 void Tessellator::GenerateFilledArcStrip(const Trigs& trigs,
762  const Arc::Iteration& iteration,
763  const Rect& oval_bounds,
764  bool use_center,
765  const TessellatedVertexProc& proc) {
766  Point center = oval_bounds.GetCenter();
767  Size radii = oval_bounds.GetSize() * 0.5f;
768 
769  Point origin;
770  if (use_center) {
771  origin = center;
772  } else {
773  Point midpoint = (iteration.start + iteration.end) * 0.5f;
774  origin = center + midpoint * radii;
775  }
776 
777  proc(origin);
778  proc(center + iteration.start * radii);
779  bool insert_origin = false;
780  for (size_t i = 0; i < iteration.quadrant_count; i++) {
781  auto quadrant = iteration.quadrants[i];
782  for (size_t j = quadrant.start_index; j < quadrant.end_index; j++) {
783  if (insert_origin) {
784  proc(origin);
785  }
786  insert_origin = !insert_origin;
787  proc(center + trigs[j] * quadrant.axis * radii);
788  }
789  }
790  if (insert_origin) {
791  proc(origin);
792  }
793  proc(center + iteration.end * radii);
794 }
795 
796 void Tessellator::GenerateStrokedArc(const Trigs& trigs,
797  const Arc::Iteration& iteration,
798  const Rect& oval_bounds,
799  Scalar half_width,
800  Cap cap,
801  const TessellatedVertexProc& proc) {
802  Point center = oval_bounds.GetCenter();
803  Size base_radii = oval_bounds.GetSize() * 0.5f;
804  Size inner_radii = base_radii - Size(half_width, half_width);
805  Size outer_radii = base_radii + Size(half_width, half_width);
806 
807  FML_DCHECK(cap != Cap::kRound);
808  if (cap == Cap::kSquare) {
809  Vector2 offset =
810  Vector2{iteration.start.y, -iteration.start.x} * half_width;
811  proc(center + iteration.start * inner_radii + offset);
812  proc(center + iteration.start * outer_radii + offset);
813  }
814  proc(center + iteration.start * inner_radii);
815  proc(center + iteration.start * outer_radii);
816  for (size_t i = 0; i < iteration.quadrant_count; i++) {
817  auto quadrant = iteration.quadrants[i];
818  for (size_t j = quadrant.start_index; j < quadrant.end_index; j++) {
819  proc(center + trigs[j] * quadrant.axis * inner_radii);
820  proc(center + trigs[j] * quadrant.axis * outer_radii);
821  }
822  }
823  proc(center + iteration.end * inner_radii);
824  proc(center + iteration.end * outer_radii);
825  if (cap == Cap::kSquare) {
826  Vector2 offset = Vector2{-iteration.end.y, iteration.end.x} * half_width;
827  proc(center + iteration.end * inner_radii + offset);
828  proc(center + iteration.end * outer_radii + offset);
829  }
830 }
831 
832 void Tessellator::GenerateRoundCapLine(
833  const Trigs& trigs,
834  const EllipticalVertexGenerator::Data& data,
835  const TessellatedVertexProc& proc) {
836  auto p0 = data.reference_centers[0];
837  auto p1 = data.reference_centers[1];
838  auto radius = data.radii.width;
839 
840  FML_DCHECK(radius == data.radii.height);
841  FML_DCHECK(data.half_width < 0);
842 
843  auto along = p1 - p0;
844  along *= radius / along.GetLength();
845  auto across = Point(-along.y, along.x);
846 
847  for (auto& trig : trigs) {
848  auto relative_along = along * trig.cos;
849  auto relative_across = across * trig.sin;
850  proc(p0 - relative_along + relative_across);
851  proc(p0 - relative_along - relative_across);
852  }
853 
854  // The second half of the round caps should be iterated in reverse, but
855  // we can instead iterate forward and swap the sin/cos values as they
856  // should be symmetric.
857  for (auto& trig : trigs) {
858  auto relative_along = along * trig.sin;
859  auto relative_across = across * trig.cos;
860  proc(p1 + relative_along + relative_across);
861  proc(p1 + relative_along - relative_across);
862  }
863 }
864 
865 void Tessellator::GenerateFilledEllipse(
866  const Trigs& trigs,
867  const EllipticalVertexGenerator::Data& data,
868  const TessellatedVertexProc& proc) {
869  auto center = data.reference_centers[0];
870  auto radii = data.radii;
871 
872  FML_DCHECK(center == data.reference_centers[1]);
873  FML_DCHECK(data.half_width < 0);
874 
875  // Quadrant 1 connecting with Quadrant 4:
876  for (auto& trig : trigs) {
877  auto offset = trig * radii;
878  proc({center.x - offset.x, center.y + offset.y});
879  proc({center.x - offset.x, center.y - offset.y});
880  }
881 
882  // The second half of the circle should be iterated in reverse, but
883  // we can instead iterate forward and swap the x/y values of the
884  // offset as the angles should be symmetric and thus should generate
885  // symmetrically reversed trig vectors.
886  // Quadrant 2 connecting with Quadrant 2:
887  for (auto& trig : trigs) {
888  auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
889  proc({center.x + offset.x, center.y + offset.y});
890  proc({center.x + offset.x, center.y - offset.y});
891  }
892 }
893 
894 void Tessellator::GenerateFilledRoundRect(
895  const Trigs& trigs,
896  const EllipticalVertexGenerator::Data& data,
897  const TessellatedVertexProc& proc) {
898  Scalar left = data.reference_centers[0].x;
899  Scalar top = data.reference_centers[0].y;
900  Scalar right = data.reference_centers[1].x;
901  Scalar bottom = data.reference_centers[1].y;
902  auto radii = data.radii;
903 
904  FML_DCHECK(data.half_width < 0);
905 
906  // Quadrant 1 connecting with Quadrant 4:
907  for (auto& trig : trigs) {
908  auto offset = trig * radii;
909  proc({left - offset.x, bottom + offset.y});
910  proc({left - offset.x, top - offset.y});
911  }
912 
913  // The second half of the round rect should be iterated in reverse, but
914  // we can instead iterate forward and swap the x/y values of the
915  // offset as the angles should be symmetric and thus should generate
916  // symmetrically reversed trig vectors.
917  // Quadrant 2 connecting with Quadrant 2:
918  for (auto& trig : trigs) {
919  auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
920  proc({right + offset.x, bottom + offset.y});
921  proc({right + offset.x, top - offset.y});
922  }
923 }
924 
925 } // namespace impeller
bool use_center
virtual void Flush(std::optional< Range > range=std::nullopt) const
virtual uint8_t * OnGetContents() const =0
BufferView Emplace(const BufferType &buffer, size_t alignment=0)
Emplace non-uniform data (like contiguous vertices) onto the host buffer.
Definition: host_buffer.h:92
An interface for generating a multi contour polyline as a triangle strip.
virtual void Write(Point point)=0
static void PathToFilledVertices(const PathSource &source, VertexWriter &writer, Scalar scale)
static std::pair< size_t, size_t > CountFillStorage(const PathSource &source, Scalar scale)
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
Trigs(Scalar pixel_radius)
Definition: tessellator.cc:411
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
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
Tessellator::TessellatedVertexProc TessellatedVertexProc
Definition: tessellator.cc:437
PrimitiveType
Decides how backend draws pixels based on input vertices.
Definition: formats.h:352
Point Vector2
Definition: point.h:331
float Scalar
Definition: scalar.h:19
constexpr float kEhCloseEnough
Definition: constants.h:57
TRect< Scalar > Rect
Definition: rect.h:792
TPoint< Scalar > Point
Definition: point.h:327
Cap
An enum that describes ways to decorate the end of a path contour.
constexpr float kPiOver2
Definition: constants.h:32
Tessellator::EllipticalVertexGenerator EllipticalVertexGenerator
Definition: tessellator.cc:438
Tessellator::ArcVertexGenerator ArcVertexGenerator
Definition: tessellator.cc:439
constexpr float kPiOver4
Definition: constants.h:35
TSize< Scalar > Size
Definition: size.h:159
static constexpr size_t kPointArenaSize
The size of the point arena buffer stored on the tessellator.
Definition: tessellator.h:25
Definition: comparable.h:95
size_t GetPointCount() const
Definition: arc.cc:36
Iteration ComputeIterations(size_t step_count, bool simplify_360=true) const
Definition: arc.cc:102
constexpr bool IncludeCenter() const
Definition: arc.h:110
const Size GetOvalSize() const
Returns the size of the oval bounds.
Definition: arc.h:100
constexpr bool IsPerfectCircle() const
Definition: arc.h:112
const Rect & GetOvalBounds() const
Return the bounds of the oval in which this arc is inscribed.
Definition: arc.h:94
Range GetRange() const
Definition: buffer_view.h:27
const DeviceBuffer * GetBuffer() const
Definition: buffer_view.cc:17
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
Scalar GetMaxBasisLengthXY() const
Definition: matrix.h:323
size_t offset
Definition: range.h:14
constexpr Type GetLength() const
Definition: point.h:206
constexpr Type GetHeight() const
Returns the height of the rectangle, equivalent to |GetSize().height|.
Definition: rect.h:351
constexpr TSize< Type > GetSize() const
Returns the size of the rectangle which may be negative in either width or height and may have been c...
Definition: rect.h:331
constexpr bool IsSquare() const
Returns true if width and height are equal and neither is NaN.
Definition: rect.h:308
constexpr Type GetWidth() const
Returns the width of the rectangle, equivalent to |GetSize().width|.
Definition: rect.h:345
constexpr TPoint< T > GetRightBottom() const
Definition: rect.h:375
constexpr Point GetCenter() const
Get the center point as a |Point|.
Definition: rect.h:386
constexpr TPoint< T > GetLeftTop() const
Definition: rect.h:363
constexpr Type MaxDimension() const
Definition: size.h:106
Type height
Definition: size.h:29
Type width
Definition: size.h:28
const size_t start
const size_t end
std::vector< Point > points
std::shared_ptr< const fml::Mapping > data
Definition: texture_gles.cc:68