| 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
5 #include "impeller/tessellator/tessellator.h"
6
7 #include "third_party/libtess2/Include/tesselator.h"
8
9 namespace impeller {
10
11 static void* HeapAlloc(void* userData, unsigned int size) {
12 return malloc(size);
13 }
14
15 static void* HeapRealloc(void* userData, void* ptr, unsigned int size) {
16 return realloc(ptr, size);
17 }
18
19 static void HeapFree(void* userData, void* ptr) {
20 free(ptr);
21 }
22
23 // Note: these units are "number of entities" for bucket size and not in KB.
24 static const TESSalloc kAlloc = {
25 HeapAlloc, HeapRealloc, HeapFree, 0, /* =userData */
26 16, /* =meshEdgeBucketSize */
27 16, /* =meshVertexBucketSize */
28 16, /* =meshFaceBucketSize */
29 16, /* =dictNodeBucketSize */
30 16, /* =regionBucketSize */
31 0 /* =extraVertices */
32 };
33
34 Tessellator::Tessellator()
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 }
45
46 Tessellator::~Tessellator() = default;
47
48 static int ToTessWindingRule(FillType fill_type) {
49 switch (fill_type) {
50 case FillType::kOdd:
51 return TESS_WINDING_ODD;
52 case FillType::kNonZero:
53 return TESS_WINDING_NONZERO;
54 case FillType::kPositive:
55 return TESS_WINDING_POSITIVE;
56 case FillType::kNegative:
57 return TESS_WINDING_NEGATIVE;
58 case FillType::kAbsGeqTwo:
59 return TESS_WINDING_ABS_GEQ_TWO;
60 }
61 return TESS_WINDING_ODD;
62 }
63
64 Tessellator::Result Tessellator::Tessellate(const Path& path,
65 Scalar tolerance,
66 const BuilderCallback& callback) {
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 }
172
173 std::vector<Point> Tessellator::TessellateConvex(const Path& path,
174 Scalar tolerance) {
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 }
220
221 void DestroyTessellator(TESStesselator* tessellator) {
222 if (tessellator != nullptr) {
223 ::tessDeleteTess(tessellator);
224 }
225 }
226
227 static constexpr int kPrecomputedDivisionCount = 1024;
228 static int kPrecomputedDivisions[kPrecomputedDivisionCount] = {
229 // clang-format off
230 1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7,
231 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10,
232 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13,
233 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14,
234 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16,
235 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
236 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19,
237 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
238 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
239 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23,
240 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24,
241 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
242 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26,
243 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27,
244 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28,
245 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29,
246 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
247 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
248 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
249 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32,
250 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 33, 33,
251 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
252 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
253 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35,
254 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36,
255 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
256 36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
257 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38, 38, 38, 38,
258 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38,
259 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
260 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40,
261 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
262 40, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41,
263 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
264 41, 41, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
265 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43,
266 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43,
267 43, 43, 43, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 44, 44,
268 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44,
269 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
270 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
271 45, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46,
272 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 47,
273 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47,
274 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48, 48,
275 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
276 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49,
277 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49,
278 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 50, 50, 50, 50, 50,
279 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
280 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51,
281 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
282 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52,
283 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52,
284 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53,
285 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53,
286 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 54,
287 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
288 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
289 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
290 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
291 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
292 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
293 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57,
294 // clang-format on
295 };
296
297 static size_t ComputeQuadrantDivisions(Scalar pixel_radius) {
298 if (pixel_radius <= 0.0) {
299 return 1;
300 }
301 int radius_index = ceil(pixel_radius);
302 if (radius_index < kPrecomputedDivisionCount) {
303 return kPrecomputedDivisions[radius_index];
304 }
305
306 // For a circle with N divisions per quadrant, the maximum deviation of
307 // the polgyon approximation from the true circle will be at the center
308 // of the base of each triangular pie slice. We can compute that distance
309 // by finding the midpoint of the line of the first slice and compare
310 // its distance from the center of the circle to the radius. We will aim
311 // to have the length of that bisector to be within |kCircleTolerance|
312 // from the radius in pixels.
313 //
314 // Each vertex will appear at an angle of:
315 // theta(i) = (kPi / 2) * (i / N) // for i in [0..N]
316 // with each point falling at:
317 // point(i) = r * (cos(theta), sin(theta))
318 // If we consider the unit circle to simplify the calculations below then
319 // we need to scale the tolerance from its absolute quantity into a unit
320 // circle fraction:
321 // k = tolerance / radius
322 // Using this scaled tolerance below to avoid multiplying by the radius
323 // throughout all of the math, we have:
324 // first point = (1, 0) // theta(0) == 0
325 // theta = kPi / 2 / N // theta(1)
326 // second point = (cos(theta), sin(theta)) = (c, s)
327 // midpoint = (first + second) * 0.5 = ((1 + c)/2, s/2)
328 // |midpoint| = sqrt((1 + c)*(1 + c)/4 + s*s/4)
329 // = sqrt((1 + c + c + c*c + s*s) / 4)
330 // = sqrt((1 + 2c + 1) / 4)
331 // = sqrt((2 + 2c) / 4)
332 // = sqrt((1 + c) / 2)
333 // = cos(theta / 2) // using half-angle cosine formula
334 // error = 1 - |midpoint| = 1 - cos(theta / 2)
335 // cos(theta/2) = 1 - error
336 // theta/2 = acos(1 - error)
337 // kPi / 2 / N / 2 = acos(1 - error)
338 // kPi / 4 / acos(1 - error) = N
339 // Since we need error <= k, we want divisions >= N, so we use:
340 // N = ceil(kPi / 4 / acos(1 - k))
341 //
342 // Math is confirmed in https://math.stackexchange.com/a/4132095
343 // (keeping in mind that we are computing quarter circle divisions here)
344 // which also points out a performance optimization that is accurate
345 // to within an over-estimation of 1 division would be:
346 // N = ceil(kPi / 4 / sqrt(2 * k))
347 // Since we have precomputed the divisions for radii up to 1024, we can
348 // afford to be more accurate using the acos formula here for larger radii.
349 double k = Tessellator::kCircleTolerance / pixel_radius;
350 return ceil(kPiOver4 / std::acos(1 - k));
351 }
352
353 void Tessellator::Trigs::init(size_t divisions) {
354 if (!trigs_.empty()) {
355 return;
356 }
357
358 // Either not cached yet, or we are using the temp storage...
359 trigs_.reserve(divisions + 1);
360
361 double angle_scale = kPiOver2 / divisions;
362
363 trigs_.emplace_back(1.0, 0.0);
364 for (size_t i = 1; i < divisions; i++) {
365 trigs_.emplace_back(Radians(i * angle_scale));
366 }
367 trigs_.emplace_back(0.0, 1.0);
368 }
369
370 Tessellator::Trigs Tessellator::GetTrigsForDivisions(size_t divisions) {
371 return divisions < Tessellator::kCachedTrigCount
372 ? Trigs(precomputed_trigs_[divisions], divisions)
373 : Trigs(divisions);
374 }
375
376 using TessellatedVertexProc = Tessellator::TessellatedVertexProc;
377 using EllipticalVertexGenerator = Tessellator::EllipticalVertexGenerator;
378
379 EllipticalVertexGenerator::EllipticalVertexGenerator(
380 EllipticalVertexGenerator::GeneratorProc& generator,
381 Trigs&& trigs,
382 PrimitiveType triangle_type,
383 size_t vertices_per_trig,
384 Data&& data)
385 : impl_(generator),
386 trigs_(std::move(trigs)),
387 data_(data),
388 vertices_per_trig_(vertices_per_trig) {}
389
390 EllipticalVertexGenerator Tessellator::FilledCircle(
391 const Matrix& view_transform,
392 const Point& center,
393 Scalar radius) {
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 }
405
406 EllipticalVertexGenerator Tessellator::StrokedCircle(
407 const Matrix& view_transform,
408 const Point& center,
409 Scalar radius,
410 Scalar half_width) {
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 }
426
427 EllipticalVertexGenerator Tessellator::RoundCapLine(
428 const Matrix& view_transform,
429 const Point& p0,
430 const Point& p1,
431 Scalar radius) {
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 }
449
450 EllipticalVertexGenerator Tessellator::FilledEllipse(
451 const Matrix& view_transform,
452 const Rect& bounds) {
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 }
470
471 EllipticalVertexGenerator Tessellator::FilledRoundRect(
472 const Matrix& view_transform,
473 const Rect& bounds,
474 const Size& radii) {
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 }
498
499 void Tessellator::GenerateFilledCircle(
500 const Trigs& trigs,
501 const EllipticalVertexGenerator::Data& data,
502 const TessellatedVertexProc& proc) {
503 auto center = data.reference_centers[0];
504 auto radius = data.radii.width;
505
506 FML_DCHECK(center == data.reference_centers[1]);
507 FML_DCHECK(radius == data.radii.height);
508 FML_DCHECK(data.half_width < 0);
509
510 // Quadrant 1 connecting with Quadrant 4:
511 for (auto& trig : trigs) {
512 auto offset = trig * radius;
513 proc({center.x - offset.x, center.y + offset.y});
514 proc({center.x - offset.x, center.y - offset.y});
515 }
516
517 // The second half of the circle should be iterated in reverse, but
518 // we can instead iterate forward and swap the x/y values of the
519 // offset as the angles should be symmetric and thus should generate
520 // symmetrically reversed trig vectors.
521 // Quadrant 2 connecting with Quadrant 2:
522 for (auto& trig : trigs) {
523 auto offset = trig * radius;
524 proc({center.x + offset.y, center.y + offset.x});
525 proc({center.x + offset.y, center.y - offset.x});
526 }
527 }
528
529 void Tessellator::GenerateStrokedCircle(
530 const Trigs& trigs,
531 const EllipticalVertexGenerator::Data& data,
532 const TessellatedVertexProc& proc) {
533 auto center = data.reference_centers[0];
534
535 FML_DCHECK(center == data.reference_centers[1]);
536 FML_DCHECK(data.radii.IsSquare());
537 FML_DCHECK(data.half_width > 0 && data.half_width < data.radii.width);
538
539 auto outer_radius = data.radii.width + data.half_width;
540 auto inner_radius = data.radii.width - data.half_width;
541
542 // Zig-zag back and forth between points on the outer circle and the
543 // inner circle. Both circles are evaluated at the same number of
544 // quadrant divisions so the points for a given division should match
545 // 1 for 1 other than their applied radius.
546
547 // Quadrant 1:
548 for (auto& trig : trigs) {
549 auto outer = trig * outer_radius;
550 auto inner = trig * inner_radius;
551 proc({center.x - outer.x, center.y - outer.y});
552 proc({center.x - inner.x, center.y - inner.y});
553 }
554
555 // The even quadrants of the circle should be iterated in reverse, but
556 // we can instead iterate forward and swap the x/y values of the
557 // offset as the angles should be symmetric and thus should generate
558 // symmetrically reversed trig vectors.
559 // Quadrant 2:
560 for (auto& trig : trigs) {
561 auto outer = trig * outer_radius;
562 auto inner = trig * inner_radius;
563 proc({center.x + outer.y, center.y - outer.x});
564 proc({center.x + inner.y, center.y - inner.x});
565 }
566
567 // Quadrant 3:
568 for (auto& trig : trigs) {
569 auto outer = trig * outer_radius;
570 auto inner = trig * inner_radius;
571 proc({center.x + outer.x, center.y + outer.y});
572 proc({center.x + inner.x, center.y + inner.y});
573 }
574
575 // Quadrant 4:
576 for (auto& trig : trigs) {
577 auto outer = trig * outer_radius;
578 auto inner = trig * inner_radius;
579 proc({center.x - outer.y, center.y + outer.x});
580 proc({center.x - inner.y, center.y + inner.x});
581 }
582 }
583
584 void Tessellator::GenerateRoundCapLine(
585 const Trigs& trigs,
586 const EllipticalVertexGenerator::Data& data,
587 const TessellatedVertexProc& proc) {
588 auto p0 = data.reference_centers[0];
589 auto p1 = data.reference_centers[1];
590 auto radius = data.radii.width;
591
592 FML_DCHECK(radius == data.radii.height);
593 FML_DCHECK(data.half_width < 0);
594
595 auto along = p1 - p0;
596 along *= radius / along.GetLength();
597 auto across = Point(-along.y, along.x);
598
599 for (auto& trig : trigs) {
600 auto relative_along = along * trig.cos;
601 auto relative_across = across * trig.sin;
602 proc(p0 - relative_along + relative_across);
603 proc(p0 - relative_along - relative_across);
604 }
605
606 // The second half of the round caps should be iterated in reverse, but
607 // we can instead iterate forward and swap the sin/cos values as they
608 // should be symmetric.
609 for (auto& trig : trigs) {
610 auto relative_along = along * trig.sin;
611 auto relative_across = across * trig.cos;
612 proc(p1 + relative_along + relative_across);
613 proc(p1 + relative_along - relative_across);
614 }
615 }
616
617 void Tessellator::GenerateFilledEllipse(
618 const Trigs& trigs,
619 const EllipticalVertexGenerator::Data& data,
620 const TessellatedVertexProc& proc) {
621 auto center = data.reference_centers[0];
622 auto radii = data.radii;
623
624 FML_DCHECK(center == data.reference_centers[1]);
625 FML_DCHECK(data.half_width < 0);
626
627 // Quadrant 1 connecting with Quadrant 4:
628 for (auto& trig : trigs) {
629 auto offset = trig * radii;
630 proc({center.x - offset.x, center.y + offset.y});
631 proc({center.x - offset.x, center.y - offset.y});
632 }
633
634 // The second half of the circle should be iterated in reverse, but
635 // we can instead iterate forward and swap the x/y values of the
636 // offset as the angles should be symmetric and thus should generate
637 // symmetrically reversed trig vectors.
638 // Quadrant 2 connecting with Quadrant 2:
639 for (auto& trig : trigs) {
640 auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
641 proc({center.x + offset.x, center.y + offset.y});
642 proc({center.x + offset.x, center.y - offset.y});
643 }
644 }
645
646 void Tessellator::GenerateFilledRoundRect(
647 const Trigs& trigs,
648 const EllipticalVertexGenerator::Data& data,
649 const TessellatedVertexProc& proc) {
650 Scalar left = data.reference_centers[0].x;
651 Scalar top = data.reference_centers[0].y;
652 Scalar right = data.reference_centers[1].x;
653 Scalar bottom = data.reference_centers[1].y;
654 auto radii = data.radii;
655
656 FML_DCHECK(data.half_width < 0);
657
658 // Quadrant 1 connecting with Quadrant 4:
659 for (auto& trig : trigs) {
660 auto offset = trig * radii;
661 proc({left - offset.x, bottom + offset.y});
662 proc({left - offset.x, top - offset.y});
663 }
664
665 // The second half of the round rect should be iterated in reverse, but
666 // we can instead iterate forward and swap the x/y values of the
667 // offset as the angles should be symmetric and thus should generate
668 // symmetrically reversed trig vectors.
669 // Quadrant 2 connecting with Quadrant 2:
670 for (auto& trig : trigs) {
671 auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
672 proc({right + offset.x, bottom + offset.y});
673 proc({right + offset.x, top - offset.y});
674 }
675 }
676
677 } // namespace impeller
impeller::kAlloc
static const TESSalloc kAlloc
Definition: tessellator.cc:24
impeller::EllipticalVertexGenerator
Tessellator::EllipticalVertexGenerator EllipticalVertexGenerator
Definition: tessellator.cc:377
impeller::Tessellator::~Tessellator
~Tessellator()
impeller::Scalar
float Scalar
Definition: scalar.h:18
impeller::FillType::kOdd
@ kOdd
impeller::HeapRealloc
static void * HeapRealloc(void *userData, void *ptr, unsigned int size)
Definition: tessellator.cc:15
impeller::kEhCloseEnough
constexpr float kEhCloseEnough
Definition: constants.h:56
impeller::Tessellator::TessellatedVertexProc
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:86
impeller::HeapFree
static void HeapFree(void *userData, void *ptr)
Definition: tessellator.cc:19
impeller::Tessellator::Result::kInputError
@ kInputError
impeller::FillType::kAbsGeqTwo
@ kAbsGeqTwo
impeller::TRect::GetLeftTop
constexpr TPoint< T > GetLeftTop() const
Definition: rect.h:205
impeller::TSize::MaxDimension
constexpr Type MaxDimension() const
Definition: size.h:88
impeller::TRect::GetCenter
constexpr Point GetCenter() const
Get the center point as a |Point|.
Definition: rect.h:225
impeller::ComputeQuadrantDivisions
static size_t ComputeQuadrantDivisions(Scalar pixel_radius)
Definition: tessellator.cc:297
impeller::TRect::GetHeight
constexpr Type GetHeight() const
Returns the height of the rectangle, equivalent to |GetSize().height|.
Definition: rect.h:175
impeller::FillType::kPositive
@ kPositive
impeller::kPiOver2
constexpr float kPiOver2
Definition: constants.h:32
tessellator.h
impeller::TSize< Scalar >
impeller::kPrecomputedDivisions
static int kPrecomputedDivisions[kPrecomputedDivisionCount]
Definition: tessellator.cc:228
impeller::PrimitiveType
PrimitiveType
Decides how backend draws pixels based on input vertices.
Definition: formats.h:350
impeller::Point
TPoint< Scalar > Point
Definition: point.h:308
impeller::Tessellator::Result::kTessellationError
@ kTessellationError
impeller::Tessellator::TessellateConvex
std::vector< Point > TessellateConvex(const Path &path, Scalar tolerance)
Given a convex path, create a triangle fan structure.
Definition: tessellator.cc:173
impeller::Path
Paths are lightweight objects that describe a collection of linear, quadratic, or cubic segments....
Definition: path.h:55
impeller::DestroyTessellator
void DestroyTessellator(TESStesselator *tessellator)
Definition: tessellator.cc:221
impeller::Matrix::GetMaxBasisLength
Scalar GetMaxBasisLength() const
Definition: matrix.cc:196
impeller::TRect::GetWidth
constexpr Type GetWidth() const
Returns the width of the rectangle, equivalent to |GetSize().width|.
Definition: rect.h:171
impeller::TRect::IsSquare
constexpr bool IsSquare() const
Returns true if width and height are equal and neither is NaN.
Definition: rect.h:141
impeller::Path::Polyline::GetContourPointBounds
std::tuple< size_t, size_t > GetContourPointBounds(size_t contour_index) const
Definition: path.cc:22
impeller::Tessellator::Result::kSuccess
@ kSuccess
impeller::FillType
FillType
Definition: path.h:30
impeller::TessellatedVertexProc
Tessellator::TessellatedVertexProc TessellatedVertexProc
Definition: tessellator.cc:376
impeller::Tessellator::EllipticalVertexGenerator
The |VertexGenerator| implementation common to all shapes that are based on a polygonal representatio...
Definition: tessellator.h:129
impeller::TSize::width
Type width
Definition: size.h:22
impeller::FillType::kNonZero
@ kNonZero
impeller::HeapAlloc
static void * HeapAlloc(void *userData, unsigned int size)
Definition: tessellator.cc:11
impeller::TRect::GetSize
constexpr TSize< Type > GetSize() const
Returns the size of the rectangle as specified when it was constructed and which may be negative in e...
Definition: rect.h:159
impeller::TPoint::GetLength
constexpr Type GetLength() const
Definition: point.h:201
std
Definition: comparable.h:95
impeller::TPoint< Scalar >
impeller::Tessellator::Tessellate
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.
Definition: tessellator.cc:64
impeller::Tessellator::Tessellator
Tessellator()
Definition: tessellator.cc:34
impeller::ToTessWindingRule
static int ToTessWindingRule(FillType fill_type)
Definition: tessellator.cc:48
impeller::Tessellator::kCircleTolerance
static constexpr Scalar kCircleTolerance
The pixel tolerance used by the algorighm to determine how many divisions to create for a circle.
Definition: tessellator.h:226
impeller::Path::Polyline::PointBufferPtr
std::unique_ptr< std::vector< Point > > PointBufferPtr
Definition: path.h:101
impeller::FillType::kNegative
@ kNegative
impeller::TSize::height
Type height
Definition: size.h:23
impeller::kPrecomputedDivisionCount
static constexpr int kPrecomputedDivisionCount
Definition: tessellator.cc:227
impeller::TRect::GetRightBottom
constexpr TPoint< T > GetRightBottom() const
Definition: rect.h:217
impeller::Tessellator::Result
Result
Definition: tessellator.h:78
impeller
Definition: aiks_context.cc:10
impeller::Tessellator::BuilderCallback
std::function< bool(const float *vertices, size_t vertices_count, const uint16_t *indices, size_t indices_count)> BuilderCallback
A callback that returns the results of the tessellation.
Definition: tessellator.h:189
impeller::Path::CreatePolyline
Polyline CreatePolyline(Scalar scale, Polyline::PointBufferPtr point_buffer=std::make_unique< std::vector< Point >>(), Polyline::ReclaimPointBufferCallback reclaim=nullptr) const
Definition: path.cc:253
impeller::kPiOver4
constexpr float kPiOver4
Definition: constants.h:35
impeller::TRect< Scalar >
impeller::CTessellator
std::unique_ptr< TESStesselator, decltype(&DestroyTessellator)> CTessellator
Definition: tessellator.h:25
impeller::Matrix
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
impeller::Path::GetFillType
FillType GetFillType() const
Definition: path.cc:55