| 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 }
55 return TESS_WINDING_ODD;
56 }
57
58 Tessellator::Result Tessellator::Tessellate(const Path& path,
59 Scalar tolerance,
60 const BuilderCallback& callback) {
61 if (!callback) {
62 return Result::kInputError;
63 }
64
65 point_buffer_->clear();
66 auto polyline =
67 path.CreatePolyline(tolerance, std::move(point_buffer_),
68 [this](Path::Polyline::PointBufferPtr point_buffer) {
69 point_buffer_ = std::move(point_buffer);
70 });
71
72 auto fill_type = path.GetFillType();
73
74 if (polyline.points->empty()) {
75 return Result::kInputError;
76 }
77
78 auto tessellator = c_tessellator_.get();
79 if (!tessellator) {
80 return Result::kTessellationError;
81 }
82
83 constexpr int kVertexSize = 2;
84 constexpr int kPolygonSize = 3;
85
86 //----------------------------------------------------------------------------
87 /// Feed contour information to the tessellator.
88 ///
89 static_assert(sizeof(Point) == 2 * sizeof(float));
90 for (size_t contour_i = 0; contour_i < polyline.contours.size();
91 contour_i++) {
92 size_t start_point_index, end_point_index;
93 std::tie(start_point_index, end_point_index) =
94 polyline.GetContourPointBounds(contour_i);
95
96 ::tessAddContour(tessellator, // the C tessellator
97 kVertexSize, //
98 polyline.points->data() + start_point_index, //
99 sizeof(Point), //
100 end_point_index - start_point_index //
101 );
102 }
103
104 //----------------------------------------------------------------------------
105 /// Let's tessellate.
106 ///
107 auto result = ::tessTesselate(tessellator, // tessellator
108 ToTessWindingRule(fill_type), // winding
109 TESS_POLYGONS, // element type
110 kPolygonSize, // polygon size
111 kVertexSize, // vertex size
112 nullptr // normal (null is automatic)
113 );
114
115 if (result != 1) {
116 return Result::kTessellationError;
117 }
118
119 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
120
121 // We default to using a 16bit index buffer, but in cases where we generate
122 // more tessellated data than this can contain we need to fall back to
123 // dropping the index buffer entirely. Instead code could instead switch to
124 // a uint32 index buffer, but this is done for simplicity with the other
125 // fast path above.
126 if (element_item_count < USHRT_MAX) {
127 int vertex_item_count = tessGetVertexCount(tessellator);
128 auto vertices = tessGetVertices(tessellator);
129 auto elements = tessGetElements(tessellator);
130
131 // libtess uses an int index internally due to usage of -1 as a sentinel
132 // value.
133 std::vector<uint16_t> indices(element_item_count);
134 for (int i = 0; i < element_item_count; i++) {
135 indices[i] = static_cast<uint16_t>(elements[i]);
136 }
137 if (!callback(vertices, vertex_item_count, indices.data(),
138 element_item_count)) {
139 return Result::kInputError;
140 }
141 } else {
142 std::vector<Point> points;
143 std::vector<float> data;
144
145 int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize;
146 auto vertices = tessGetVertices(tessellator);
147 points.reserve(vertex_item_count);
148 for (int i = 0; i < vertex_item_count; i += 2) {
149 points.emplace_back(vertices[i], vertices[i + 1]);
150 }
151
152 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
153 auto elements = tessGetElements(tessellator);
154 data.reserve(element_item_count);
155 for (int i = 0; i < element_item_count; i++) {
156 data.emplace_back(points[elements[i]].x);
157 data.emplace_back(points[elements[i]].y);
158 }
159 if (!callback(data.data(), element_item_count, nullptr, 0u)) {
160 return Result::kInputError;
161 }
162 }
163
164 return Result::kSuccess;
165 }
166
167 Path::Polyline Tessellator::CreateTempPolyline(const Path& path,
168 Scalar tolerance) {
169 FML_DCHECK(point_buffer_);
170 point_buffer_->clear();
171 auto polyline =
172 path.CreatePolyline(tolerance, std::move(point_buffer_),
173 [this](Path::Polyline::PointBufferPtr point_buffer) {
174 point_buffer_ = std::move(point_buffer);
175 });
176 return polyline;
177 }
178
179 std::vector<Point> Tessellator::TessellateConvex(const Path& path,
180 Scalar tolerance) {
181 FML_DCHECK(point_buffer_);
182
183 std::vector<Point> output;
184 point_buffer_->clear();
185 auto polyline =
186 path.CreatePolyline(tolerance, std::move(point_buffer_),
187 [this](Path::Polyline::PointBufferPtr point_buffer) {
188 point_buffer_ = std::move(point_buffer);
189 });
190 if (polyline.points->size() == 0) {
191 return output;
192 }
193
194 output.reserve(polyline.points->size() +
195 (4 * (polyline.contours.size() - 1)));
196 bool previous_contour_odd_points = false;
197 for (auto j = 0u; j < polyline.contours.size(); j++) {
198 auto [start, end] = polyline.GetContourPointBounds(j);
199 auto first_point = polyline.GetPoint(start);
200
201 // Some polygons will not self close and an additional triangle
202 // must be inserted, others will self close and we need to avoid
203 // inserting an extra triangle.
204 if (polyline.GetPoint(end - 1) == first_point) {
205 end--;
206 }
207
208 if (j > 0) {
209 // Triangle strip break.
210 output.emplace_back(output.back());
211 output.emplace_back(first_point);
212 output.emplace_back(first_point);
213
214 // If the contour has an odd number of points, insert an extra point when
215 // bridging to the next contour to preserve the correct triangle winding
216 // order.
217 if (previous_contour_odd_points) {
218 output.emplace_back(first_point);
219 }
220 } else {
221 output.emplace_back(first_point);
222 }
223
224 size_t a = start + 1;
225 size_t b = end - 1;
226 while (a < b) {
227 output.emplace_back(polyline.GetPoint(a));
228 output.emplace_back(polyline.GetPoint(b));
229 a++;
230 b--;
231 }
232 if (a == b) {
233 previous_contour_odd_points = false;
234 output.emplace_back(polyline.GetPoint(a));
235 } else {
236 previous_contour_odd_points = true;
237 }
238 }
239 return output;
240 }
241
242 void DestroyTessellator(TESStesselator* tessellator) {
243 if (tessellator != nullptr) {
244 ::tessDeleteTess(tessellator);
245 }
246 }
247
248 static constexpr int kPrecomputedDivisionCount = 1024;
249 static int kPrecomputedDivisions[kPrecomputedDivisionCount] = {
250 // clang-format off
251 1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7,
252 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10,
253 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13,
254 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14,
255 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16,
256 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
257 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19,
258 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
259 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
260 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23,
261 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24,
262 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
263 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26,
264 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27,
265 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28,
266 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29,
267 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
268 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
269 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
270 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32,
271 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 33, 33,
272 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
273 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
274 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35,
275 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36,
276 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
277 36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
278 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38, 38, 38, 38,
279 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38,
280 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
281 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40,
282 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
283 40, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41,
284 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
285 41, 41, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
286 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43,
287 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43,
288 43, 43, 43, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 44, 44,
289 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44,
290 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
291 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
292 45, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46,
293 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 47,
294 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47,
295 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48, 48,
296 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
297 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49,
298 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49,
299 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 50, 50, 50, 50, 50,
300 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
301 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51,
302 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
303 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52,
304 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52,
305 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53,
306 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53,
307 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 54,
308 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
309 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
310 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
311 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
312 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
313 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
314 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57,
315 // clang-format on
316 };
317
318 static size_t ComputeQuadrantDivisions(Scalar pixel_radius) {
319 if (pixel_radius <= 0.0) {
320 return 1;
321 }
322 int radius_index = ceil(pixel_radius);
323 if (radius_index < kPrecomputedDivisionCount) {
324 return kPrecomputedDivisions[radius_index];
325 }
326
327 // For a circle with N divisions per quadrant, the maximum deviation of
328 // the polgyon approximation from the true circle will be at the center
329 // of the base of each triangular pie slice. We can compute that distance
330 // by finding the midpoint of the line of the first slice and compare
331 // its distance from the center of the circle to the radius. We will aim
332 // to have the length of that bisector to be within |kCircleTolerance|
333 // from the radius in pixels.
334 //
335 // Each vertex will appear at an angle of:
336 // theta(i) = (kPi / 2) * (i / N) // for i in [0..N]
337 // with each point falling at:
338 // point(i) = r * (cos(theta), sin(theta))
339 // If we consider the unit circle to simplify the calculations below then
340 // we need to scale the tolerance from its absolute quantity into a unit
341 // circle fraction:
342 // k = tolerance / radius
343 // Using this scaled tolerance below to avoid multiplying by the radius
344 // throughout all of the math, we have:
345 // first point = (1, 0) // theta(0) == 0
346 // theta = kPi / 2 / N // theta(1)
347 // second point = (cos(theta), sin(theta)) = (c, s)
348 // midpoint = (first + second) * 0.5 = ((1 + c)/2, s/2)
349 // |midpoint| = sqrt((1 + c)*(1 + c)/4 + s*s/4)
350 // = sqrt((1 + c + c + c*c + s*s) / 4)
351 // = sqrt((1 + 2c + 1) / 4)
352 // = sqrt((2 + 2c) / 4)
353 // = sqrt((1 + c) / 2)
354 // = cos(theta / 2) // using half-angle cosine formula
355 // error = 1 - |midpoint| = 1 - cos(theta / 2)
356 // cos(theta/2) = 1 - error
357 // theta/2 = acos(1 - error)
358 // kPi / 2 / N / 2 = acos(1 - error)
359 // kPi / 4 / acos(1 - error) = N
360 // Since we need error <= k, we want divisions >= N, so we use:
361 // N = ceil(kPi / 4 / acos(1 - k))
362 //
363 // Math is confirmed in https://math.stackexchange.com/a/4132095
364 // (keeping in mind that we are computing quarter circle divisions here)
365 // which also points out a performance optimization that is accurate
366 // to within an over-estimation of 1 division would be:
367 // N = ceil(kPi / 4 / sqrt(2 * k))
368 // Since we have precomputed the divisions for radii up to 1024, we can
369 // afford to be more accurate using the acos formula here for larger radii.
370 double k = Tessellator::kCircleTolerance / pixel_radius;
371 return ceil(kPiOver4 / std::acos(1 - k));
372 }
373
374 void Tessellator::Trigs::init(size_t divisions) {
375 if (!trigs_.empty()) {
376 return;
377 }
378
379 // Either not cached yet, or we are using the temp storage...
380 trigs_.reserve(divisions + 1);
381
382 double angle_scale = kPiOver2 / divisions;
383
384 trigs_.emplace_back(1.0, 0.0);
385 for (size_t i = 1; i < divisions; i++) {
386 trigs_.emplace_back(Radians(i * angle_scale));
387 }
388 trigs_.emplace_back(0.0, 1.0);
389 }
390
391 Tessellator::Trigs Tessellator::GetTrigsForDivisions(size_t divisions) {
392 return divisions < Tessellator::kCachedTrigCount
393 ? Trigs(precomputed_trigs_[divisions], divisions)
394 : Trigs(divisions);
395 }
396
397 using TessellatedVertexProc = Tessellator::TessellatedVertexProc;
398 using EllipticalVertexGenerator = Tessellator::EllipticalVertexGenerator;
399
400 EllipticalVertexGenerator::EllipticalVertexGenerator(
401 EllipticalVertexGenerator::GeneratorProc& generator,
402 Trigs&& trigs,
403 PrimitiveType triangle_type,
404 size_t vertices_per_trig,
405 Data&& data)
406 : impl_(generator),
407 trigs_(std::move(trigs)),
408 data_(data),
409 vertices_per_trig_(vertices_per_trig) {}
410
411 EllipticalVertexGenerator Tessellator::FilledCircle(
412 const Matrix& view_transform,
413 const Point& center,
414 Scalar radius) {
415 auto divisions =
416 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * radius);
417 return EllipticalVertexGenerator(Tessellator::GenerateFilledCircle,
418 GetTrigsForDivisions(divisions),
419 PrimitiveType::kTriangleStrip, 4,
420 {
421 .reference_centers = {center, center},
422 .radii = {radius, radius},
423 .half_width = -1.0f,
424 });
425 }
426
427 EllipticalVertexGenerator Tessellator::StrokedCircle(
428 const Matrix& view_transform,
429 const Point& center,
430 Scalar radius,
431 Scalar half_width) {
432 if (half_width > 0) {
433 auto divisions = ComputeQuadrantDivisions(
434 view_transform.GetMaxBasisLength() * radius + half_width);
435 return EllipticalVertexGenerator(Tessellator::GenerateStrokedCircle,
436 GetTrigsForDivisions(divisions),
437 PrimitiveType::kTriangleStrip, 8,
438 {
439 .reference_centers = {center, center},
440 .radii = {radius, radius},
441 .half_width = half_width,
442 });
443 } else {
444 return FilledCircle(view_transform, center, radius);
445 }
446 }
447
448 EllipticalVertexGenerator Tessellator::RoundCapLine(
449 const Matrix& view_transform,
450 const Point& p0,
451 const Point& p1,
452 Scalar radius) {
453 auto along = p1 - p0;
454 auto length = along.GetLength();
455 if (length > kEhCloseEnough) {
456 auto divisions =
457 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * radius);
458 return EllipticalVertexGenerator(Tessellator::GenerateRoundCapLine,
459 GetTrigsForDivisions(divisions),
460 PrimitiveType::kTriangleStrip, 4,
461 {
462 .reference_centers = {p0, p1},
463 .radii = {radius, radius},
464 .half_width = -1.0f,
465 });
466 } else {
467 return FilledCircle(view_transform, p0, radius);
468 }
469 }
470
471 EllipticalVertexGenerator Tessellator::FilledEllipse(
472 const Matrix& view_transform,
473 const Rect& bounds) {
474 if (bounds.IsSquare()) {
475 return FilledCircle(view_transform, bounds.GetCenter(),
476 bounds.GetWidth() * 0.5f);
477 }
478 auto max_radius = bounds.GetSize().MaxDimension();
479 auto divisions =
480 ComputeQuadrantDivisions(view_transform.GetMaxBasisLength() * max_radius);
481 auto center = bounds.GetCenter();
482 return EllipticalVertexGenerator(Tessellator::GenerateFilledEllipse,
483 GetTrigsForDivisions(divisions),
484 PrimitiveType::kTriangleStrip, 4,
485 {
486 .reference_centers = {center, center},
487 .radii = bounds.GetSize() * 0.5f,
488 .half_width = -1.0f,
489 });
490 }
491
492 EllipticalVertexGenerator Tessellator::FilledRoundRect(
493 const Matrix& view_transform,
494 const Rect& bounds,
495 const Size& radii) {
496 if (radii.width * 2 < bounds.GetWidth() ||
497 radii.height * 2 < bounds.GetHeight()) {
498 auto max_radius = radii.MaxDimension();
499 auto divisions = ComputeQuadrantDivisions(
500 view_transform.GetMaxBasisLength() * max_radius);
501 auto upper_left = bounds.GetLeftTop() + radii;
502 auto lower_right = bounds.GetRightBottom() - radii;
503 return EllipticalVertexGenerator(Tessellator::GenerateFilledRoundRect,
504 GetTrigsForDivisions(divisions),
505 PrimitiveType::kTriangleStrip, 4,
506 {
507 .reference_centers =
508 {
509 upper_left,
510 lower_right,
511 },
512 .radii = radii,
513 .half_width = -1.0f,
514 });
515 } else {
516 return FilledEllipse(view_transform, bounds);
517 }
518 }
519
520 void Tessellator::GenerateFilledCircle(
521 const Trigs& trigs,
522 const EllipticalVertexGenerator::Data& data,
523 const TessellatedVertexProc& proc) {
524 auto center = data.reference_centers[0];
525 auto radius = data.radii.width;
526
527 FML_DCHECK(center == data.reference_centers[1]);
528 FML_DCHECK(radius == data.radii.height);
529 FML_DCHECK(data.half_width < 0);
530
531 // Quadrant 1 connecting with Quadrant 4:
532 for (auto& trig : trigs) {
533 auto offset = trig * radius;
534 proc({center.x - offset.x, center.y + offset.y});
535 proc({center.x - offset.x, center.y - offset.y});
536 }
537
538 // The second half of the circle should be iterated in reverse, but
539 // we can instead iterate forward and swap the x/y values of the
540 // offset as the angles should be symmetric and thus should generate
541 // symmetrically reversed trig vectors.
542 // Quadrant 2 connecting with Quadrant 2:
543 for (auto& trig : trigs) {
544 auto offset = trig * radius;
545 proc({center.x + offset.y, center.y + offset.x});
546 proc({center.x + offset.y, center.y - offset.x});
547 }
548 }
549
550 void Tessellator::GenerateStrokedCircle(
551 const Trigs& trigs,
552 const EllipticalVertexGenerator::Data& data,
553 const TessellatedVertexProc& proc) {
554 auto center = data.reference_centers[0];
555
556 FML_DCHECK(center == data.reference_centers[1]);
557 FML_DCHECK(data.radii.IsSquare());
558 FML_DCHECK(data.half_width > 0 && data.half_width < data.radii.width);
559
560 auto outer_radius = data.radii.width + data.half_width;
561 auto inner_radius = data.radii.width - data.half_width;
562
563 // Zig-zag back and forth between points on the outer circle and the
564 // inner circle. Both circles are evaluated at the same number of
565 // quadrant divisions so the points for a given division should match
566 // 1 for 1 other than their applied radius.
567
568 // Quadrant 1:
569 for (auto& trig : trigs) {
570 auto outer = trig * outer_radius;
571 auto inner = trig * inner_radius;
572 proc({center.x - outer.x, center.y - outer.y});
573 proc({center.x - inner.x, center.y - inner.y});
574 }
575
576 // The even quadrants of the circle should be iterated in reverse, but
577 // we can instead iterate forward and swap the x/y values of the
578 // offset as the angles should be symmetric and thus should generate
579 // symmetrically reversed trig vectors.
580 // Quadrant 2:
581 for (auto& trig : trigs) {
582 auto outer = trig * outer_radius;
583 auto inner = trig * inner_radius;
584 proc({center.x + outer.y, center.y - outer.x});
585 proc({center.x + inner.y, center.y - inner.x});
586 }
587
588 // Quadrant 3:
589 for (auto& trig : trigs) {
590 auto outer = trig * outer_radius;
591 auto inner = trig * inner_radius;
592 proc({center.x + outer.x, center.y + outer.y});
593 proc({center.x + inner.x, center.y + inner.y});
594 }
595
596 // Quadrant 4:
597 for (auto& trig : trigs) {
598 auto outer = trig * outer_radius;
599 auto inner = trig * inner_radius;
600 proc({center.x - outer.y, center.y + outer.x});
601 proc({center.x - inner.y, center.y + inner.x});
602 }
603 }
604
605 void Tessellator::GenerateRoundCapLine(
606 const Trigs& trigs,
607 const EllipticalVertexGenerator::Data& data,
608 const TessellatedVertexProc& proc) {
609 auto p0 = data.reference_centers[0];
610 auto p1 = data.reference_centers[1];
611 auto radius = data.radii.width;
612
613 FML_DCHECK(radius == data.radii.height);
614 FML_DCHECK(data.half_width < 0);
615
616 auto along = p1 - p0;
617 along *= radius / along.GetLength();
618 auto across = Point(-along.y, along.x);
619
620 for (auto& trig : trigs) {
621 auto relative_along = along * trig.cos;
622 auto relative_across = across * trig.sin;
623 proc(p0 - relative_along + relative_across);
624 proc(p0 - relative_along - relative_across);
625 }
626
627 // The second half of the round caps should be iterated in reverse, but
628 // we can instead iterate forward and swap the sin/cos values as they
629 // should be symmetric.
630 for (auto& trig : trigs) {
631 auto relative_along = along * trig.sin;
632 auto relative_across = across * trig.cos;
633 proc(p1 + relative_along + relative_across);
634 proc(p1 + relative_along - relative_across);
635 }
636 }
637
638 void Tessellator::GenerateFilledEllipse(
639 const Trigs& trigs,
640 const EllipticalVertexGenerator::Data& data,
641 const TessellatedVertexProc& proc) {
642 auto center = data.reference_centers[0];
643 auto radii = data.radii;
644
645 FML_DCHECK(center == data.reference_centers[1]);
646 FML_DCHECK(data.half_width < 0);
647
648 // Quadrant 1 connecting with Quadrant 4:
649 for (auto& trig : trigs) {
650 auto offset = trig * radii;
651 proc({center.x - offset.x, center.y + offset.y});
652 proc({center.x - offset.x, center.y - offset.y});
653 }
654
655 // The second half of the circle should be iterated in reverse, but
656 // we can instead iterate forward and swap the x/y values of the
657 // offset as the angles should be symmetric and thus should generate
658 // symmetrically reversed trig vectors.
659 // Quadrant 2 connecting with Quadrant 2:
660 for (auto& trig : trigs) {
661 auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
662 proc({center.x + offset.x, center.y + offset.y});
663 proc({center.x + offset.x, center.y - offset.y});
664 }
665 }
666
667 void Tessellator::GenerateFilledRoundRect(
668 const Trigs& trigs,
669 const EllipticalVertexGenerator::Data& data,
670 const TessellatedVertexProc& proc) {
671 Scalar left = data.reference_centers[0].x;
672 Scalar top = data.reference_centers[0].y;
673 Scalar right = data.reference_centers[1].x;
674 Scalar bottom = data.reference_centers[1].y;
675 auto radii = data.radii;
676
677 FML_DCHECK(data.half_width < 0);
678
679 // Quadrant 1 connecting with Quadrant 4:
680 for (auto& trig : trigs) {
681 auto offset = trig * radii;
682 proc({left - offset.x, bottom + offset.y});
683 proc({left - offset.x, top - offset.y});
684 }
685
686 // The second half of the round rect should be iterated in reverse, but
687 // we can instead iterate forward and swap the x/y values of the
688 // offset as the angles should be symmetric and thus should generate
689 // symmetrically reversed trig vectors.
690 // Quadrant 2 connecting with Quadrant 2:
691 for (auto& trig : trigs) {
692 auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
693 proc({right + offset.x, bottom + offset.y});
694 proc({right + offset.x, top - offset.y});
695 }
696 }
697
698 } // namespace impeller
impeller::kAlloc
static const TESSalloc kAlloc
Definition: tessellator.cc:24
impeller::EllipticalVertexGenerator
Tessellator::EllipticalVertexGenerator EllipticalVertexGenerator
Definition: tessellator.cc:398
impeller::Tessellator::~Tessellator
~Tessellator()
polyline
const Path::Polyline & polyline
Definition: stroke_path_geometry.cc:292
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:80
impeller::HeapFree
static void HeapFree(void *userData, void *ptr)
Definition: tessellator.cc:19
impeller::Tessellator::Result::kInputError
@ kInputError
impeller::TRect::GetLeftTop
constexpr TPoint< T > GetLeftTop() const
Definition: rect.h:326
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:350
impeller::ComputeQuadrantDivisions
static size_t ComputeQuadrantDivisions(Scalar pixel_radius)
Definition: tessellator.cc:318
impeller::TRect::GetHeight
constexpr Type GetHeight() const
Returns the height of the rectangle, equivalent to |GetSize().height|.
Definition: rect.h:314
impeller::kPiOver2
constexpr float kPiOver2
Definition: constants.h:32
tessellator.h
impeller::Path::Polyline
Definition: path.h:94
impeller::TSize< Scalar >
impeller::kPrecomputedDivisions
static int kPrecomputedDivisions[kPrecomputedDivisionCount]
Definition: tessellator.cc:249
impeller::PrimitiveType
PrimitiveType
Decides how backend draws pixels based on input vertices.
Definition: formats.h:353
impeller::Point
TPoint< Scalar > Point
Definition: point.h:316
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:179
impeller::Path
Paths are lightweight objects that describe a collection of linear, quadratic, or cubic segments....
Definition: path.h:51
impeller::DestroyTessellator
void DestroyTessellator(TESStesselator *tessellator)
Definition: tessellator.cc:242
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:308
impeller::TRect::IsSquare
constexpr bool IsSquare() const
Returns true if width and height are equal and neither is NaN.
Definition: rect.h:271
impeller::Tessellator::Result::kSuccess
@ kSuccess
impeller::FillType
FillType
Definition: path.h:29
impeller::TessellatedVertexProc
Tessellator::TessellatedVertexProc TessellatedVertexProc
Definition: tessellator.cc:397
impeller::Tessellator::EllipticalVertexGenerator
The |VertexGenerator| implementation common to all shapes that are based on a polygonal representatio...
Definition: tessellator.h:123
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 which may be negative in either width or height and may have been c...
Definition: rect.h:294
impeller::TPoint::GetLength
constexpr Type GetLength() const
Definition: point.h:206
std
Definition: comparable.h:95
impeller::TPoint< Scalar >
impeller::saturated::b
SI b
Definition: saturated_math.h:87
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:58
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:228
impeller::Path::Polyline::PointBufferPtr
std::unique_ptr< std::vector< Point > > PointBufferPtr
Definition: path.h:97
impeller::TSize::height
Type height
Definition: size.h:23
impeller::kPrecomputedDivisionCount
static constexpr int kPrecomputedDivisionCount
Definition: tessellator.cc:248
offset
Point offset
Definition: stroke_path_geometry.cc:300
impeller::TRect::GetRightBottom
constexpr TPoint< T > GetRightBottom() const
Definition: rect.h:338
impeller::Tessellator::Result
Result
Definition: tessellator.h:72
impeller
Definition: aiks_blur_unittests.cc:20
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:183
impeller::Tessellator::CreateTempPolyline
Path::Polyline CreateTempPolyline(const Path &path, Scalar tolerance)
Create a temporary polyline. Only one per-process can exist at a time.
Definition: tessellator.cc:167
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:198
impeller::kPiOver4
constexpr float kPiOver4
Definition: constants.h:35
impeller::TRect< Scalar >
impeller::CTessellator
std::unique_ptr< TESStesselator, decltype(&DestroyTessellator)> CTessellator
Definition: tessellator.h:24
impeller::Matrix
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
impeller::Path::GetFillType
FillType GetFillType() const
Definition: path.cc:51