| 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 #include <cstdint>
7 #include <cstring>
8
9 #include "impeller/core/device_buffer.h"
10 #include "impeller/geometry/path_component.h"
11
12 namespace impeller {
13
14 Tessellator::Tessellator()
15 : point_buffer_(std::make_unique<std::vector<Point>>()),
16 index_buffer_(std::make_unique<std::vector<uint16_t>>()),
17 stroke_points_(kPointArenaSize) {
18 point_buffer_->reserve(2048);
19 index_buffer_->reserve(2048);
20 }
21
22 Tessellator::~Tessellator() = default;
23
24 std::vector<Point>& Tessellator::GetStrokePointCache() {
25 return stroke_points_;
26 }
27
28 Path::Polyline Tessellator::CreateTempPolyline(const Path& path,
29 Scalar tolerance) {
30 FML_DCHECK(point_buffer_);
31 point_buffer_->clear();
32 auto polyline =
33 path.CreatePolyline(tolerance, std::move(point_buffer_),
34 [this](Path::Polyline::PointBufferPtr point_buffer) {
35 point_buffer_ = std::move(point_buffer);
36 });
37 return polyline;
38 }
39
40 VertexBuffer Tessellator::TessellateConvex(const Path& path,
41 HostBuffer& host_buffer,
42 Scalar tolerance,
43 bool supports_primitive_restart,
44 bool supports_triangle_fan) {
45 if (supports_primitive_restart) {
46 // Primitive Restart.
47 const auto [point_count, contour_count] = path.CountStorage(tolerance);
48 BufferView point_buffer = host_buffer.Emplace(
49 nullptr, sizeof(Point) * point_count, alignof(Point));
50 BufferView index_buffer = host_buffer.Emplace(
51 nullptr, sizeof(uint16_t) * (point_count + contour_count),
52 alignof(uint16_t));
53
54 if (supports_triangle_fan) {
55 FanVertexWriter writer(
56 reinterpret_cast<Point*>(point_buffer.GetBuffer()->OnGetContents() +
57 point_buffer.GetRange().offset),
58 reinterpret_cast<uint16_t*>(
59 index_buffer.GetBuffer()->OnGetContents() +
60 index_buffer.GetRange().offset));
61 path.WritePolyline(tolerance, writer);
62 point_buffer.GetBuffer()->Flush(point_buffer.GetRange());
63 index_buffer.GetBuffer()->Flush(index_buffer.GetRange());
64
65 return VertexBuffer{
66 .vertex_buffer = std::move(point_buffer),
67 .index_buffer = std::move(index_buffer),
68 .vertex_count = writer.GetIndexCount(),
69 .index_type = IndexType::k16bit,
70 };
71 } else {
72 StripVertexWriter writer(
73 reinterpret_cast<Point*>(point_buffer.GetBuffer()->OnGetContents() +
74 point_buffer.GetRange().offset),
75 reinterpret_cast<uint16_t*>(
76 index_buffer.GetBuffer()->OnGetContents() +
77 index_buffer.GetRange().offset));
78 path.WritePolyline(tolerance, writer);
79 point_buffer.GetBuffer()->Flush(point_buffer.GetRange());
80 index_buffer.GetBuffer()->Flush(index_buffer.GetRange());
81
82 return VertexBuffer{
83 .vertex_buffer = std::move(point_buffer),
84 .index_buffer = std::move(index_buffer),
85 .vertex_count = writer.GetIndexCount(),
86 .index_type = IndexType::k16bit,
87 };
88 }
89 }
90
91 FML_DCHECK(point_buffer_);
92 FML_DCHECK(index_buffer_);
93 TessellateConvexInternal(path, *point_buffer_, *index_buffer_, tolerance);
94
95 if (point_buffer_->empty()) {
96 return VertexBuffer{
97 .vertex_buffer = {},
98 .index_buffer = {},
99 .vertex_count = 0u,
100 .index_type = IndexType::k16bit,
101 };
102 }
103
104 BufferView vertex_buffer = host_buffer.Emplace(
105 point_buffer_->data(), sizeof(Point) * point_buffer_->size(),
106 alignof(Point));
107
108 BufferView index_buffer = host_buffer.Emplace(
109 index_buffer_->data(), sizeof(uint16_t) * index_buffer_->size(),
110 alignof(uint16_t));
111
112 return VertexBuffer{
113 .vertex_buffer = std::move(vertex_buffer),
114 .index_buffer = std::move(index_buffer),
115 .vertex_count = index_buffer_->size(),
116 .index_type = IndexType::k16bit,
117 };
118 }
119
120 VertexBuffer Tessellator::GenerateLineStrip(const Path& path,
121 HostBuffer& host_buffer,
122 Scalar tolerance) {
123 LineStripVertexWriter writer(stroke_points_);
124 path.WritePolyline(tolerance, writer);
125
126 const auto [arena_length, oversized_length] = writer.GetVertexCount();
127
128 if (oversized_length == 0) {
129 return VertexBuffer{
130 .vertex_buffer =
131 host_buffer.Emplace(stroke_points_.data(),
132 arena_length * sizeof(Point), alignof(Point)),
133 .index_buffer = {},
134 .vertex_count = arena_length,
135 .index_type = IndexType::kNone,
136 };
137 }
138 const std::vector<Point>& oversized_data = writer.GetOversizedBuffer();
139 BufferView buffer_view = host_buffer.Emplace(
140 /*buffer=*/nullptr, //
141 (arena_length + oversized_length) * sizeof(Point), //
142 alignof(Point) //
143 );
144 memcpy(buffer_view.GetBuffer()->OnGetContents() +
145 buffer_view.GetRange().offset, //
146 stroke_points_.data(), //
147 arena_length * sizeof(Point) //
148 );
149 memcpy(buffer_view.GetBuffer()->OnGetContents() +
150 buffer_view.GetRange().offset + arena_length * sizeof(Point), //
151 oversized_data.data(), //
152 oversized_data.size() * sizeof(Point) //
153 );
154 buffer_view.GetBuffer()->Flush(buffer_view.GetRange());
155
156 return VertexBuffer{
157 .vertex_buffer = buffer_view,
158 .index_buffer = {},
159 .vertex_count = arena_length + oversized_length,
160 .index_type = IndexType::kNone,
161 };
162 }
163
164 void Tessellator::TessellateConvexInternal(const Path& path,
165 std::vector<Point>& point_buffer,
166 std::vector<uint16_t>& index_buffer,
167 Scalar tolerance) {
168 point_buffer.clear();
169 index_buffer.clear();
170
171 GLESVertexWriter writer(point_buffer, index_buffer);
172
173 path.WritePolyline(tolerance, writer);
174 }
175
176 static constexpr int kPrecomputedDivisionCount = 1024;
177 static int kPrecomputedDivisions[kPrecomputedDivisionCount] = {
178 // clang-format off
179 1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7,
180 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10,
181 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13,
182 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14,
183 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16,
184 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
185 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19,
186 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
187 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
188 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23,
189 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24,
190 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
191 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26,
192 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27,
193 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28,
194 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29,
195 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
196 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
197 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
198 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32,
199 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 33, 33,
200 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
201 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
202 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35,
203 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36,
204 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
205 36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
206 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38, 38, 38, 38,
207 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38,
208 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
209 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40,
210 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
211 40, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41,
212 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
213 41, 41, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
214 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43,
215 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43,
216 43, 43, 43, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 44, 44,
217 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44,
218 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
219 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
220 45, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46,
221 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 47,
222 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47,
223 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48, 48,
224 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
225 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49,
226 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49,
227 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 50, 50, 50, 50, 50,
228 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
229 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51,
230 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
231 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52,
232 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52,
233 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53,
234 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53,
235 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 54,
236 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
237 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
238 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
239 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
240 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
241 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
242 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57,
243 // clang-format on
244 };
245
246 static size_t ComputeQuadrantDivisions(Scalar pixel_radius) {
247 if (pixel_radius <= 0.0) {
248 return 1;
249 }
250 int radius_index = ceil(pixel_radius);
251 if (radius_index < kPrecomputedDivisionCount) {
252 return kPrecomputedDivisions[radius_index];
253 }
254
255 // For a circle with N divisions per quadrant, the maximum deviation of
256 // the polgyon approximation from the true circle will be at the center
257 // of the base of each triangular pie slice. We can compute that distance
258 // by finding the midpoint of the line of the first slice and compare
259 // its distance from the center of the circle to the radius. We will aim
260 // to have the length of that bisector to be within |kCircleTolerance|
261 // from the radius in pixels.
262 //
263 // Each vertex will appear at an angle of:
264 // theta(i) = (kPi / 2) * (i / N) // for i in [0..N]
265 // with each point falling at:
266 // point(i) = r * (cos(theta), sin(theta))
267 // If we consider the unit circle to simplify the calculations below then
268 // we need to scale the tolerance from its absolute quantity into a unit
269 // circle fraction:
270 // k = tolerance / radius
271 // Using this scaled tolerance below to avoid multiplying by the radius
272 // throughout all of the math, we have:
273 // first point = (1, 0) // theta(0) == 0
274 // theta = kPi / 2 / N // theta(1)
275 // second point = (cos(theta), sin(theta)) = (c, s)
276 // midpoint = (first + second) * 0.5 = ((1 + c)/2, s/2)
277 // |midpoint| = sqrt((1 + c)*(1 + c)/4 + s*s/4)
278 // = sqrt((1 + c + c + c*c + s*s) / 4)
279 // = sqrt((1 + 2c + 1) / 4)
280 // = sqrt((2 + 2c) / 4)
281 // = sqrt((1 + c) / 2)
282 // = cos(theta / 2) // using half-angle cosine formula
283 // error = 1 - |midpoint| = 1 - cos(theta / 2)
284 // cos(theta/2) = 1 - error
285 // theta/2 = acos(1 - error)
286 // kPi / 2 / N / 2 = acos(1 - error)
287 // kPi / 4 / acos(1 - error) = N
288 // Since we need error <= k, we want divisions >= N, so we use:
289 // N = ceil(kPi / 4 / acos(1 - k))
290 //
291 // Math is confirmed in https://math.stackexchange.com/a/4132095
292 // (keeping in mind that we are computing quarter circle divisions here)
293 // which also points out a performance optimization that is accurate
294 // to within an over-estimation of 1 division would be:
295 // N = ceil(kPi / 4 / sqrt(2 * k))
296 // Since we have precomputed the divisions for radii up to 1024, we can
297 // afford to be more accurate using the acos formula here for larger radii.
298 double k = Tessellator::kCircleTolerance / pixel_radius;
299 return ceil(kPiOver4 / std::acos(1 - k));
300 }
301
302 void Tessellator::Trigs::init(size_t divisions) {
303 if (!trigs_.empty()) {
304 return;
305 }
306
307 // Either not cached yet, or we are using the temp storage...
308 trigs_.reserve(divisions + 1);
309
310 double angle_scale = kPiOver2 / divisions;
311
312 trigs_.emplace_back(1.0, 0.0);
313 for (size_t i = 1; i < divisions; i++) {
314 trigs_.emplace_back(Radians(i * angle_scale));
315 }
316 trigs_.emplace_back(0.0, 1.0);
317 }
318
319 Tessellator::Trigs Tessellator::GetTrigsForDivisions(size_t divisions) {
320 return divisions < Tessellator::kCachedTrigCount
321 ? Trigs(precomputed_trigs_[divisions], divisions)
322 : Trigs(divisions);
323 }
324
325 using TessellatedVertexProc = Tessellator::TessellatedVertexProc;
326 using EllipticalVertexGenerator = Tessellator::EllipticalVertexGenerator;
327
328 EllipticalVertexGenerator::EllipticalVertexGenerator(
329 EllipticalVertexGenerator::GeneratorProc& generator,
330 Trigs&& trigs,
331 PrimitiveType triangle_type,
332 size_t vertices_per_trig,
333 Data&& data)
334 : impl_(generator),
335 trigs_(std::move(trigs)),
336 data_(data),
337 vertices_per_trig_(vertices_per_trig) {}
338
339 EllipticalVertexGenerator Tessellator::FilledCircle(
340 const Matrix& view_transform,
341 const Point& center,
342 Scalar radius) {
343 size_t divisions =
344 ComputeQuadrantDivisions(view_transform.GetMaxBasisLengthXY() * radius);
345 return EllipticalVertexGenerator(Tessellator::GenerateFilledCircle,
346 GetTrigsForDivisions(divisions),
347 PrimitiveType::kTriangleStrip, 4,
348 {
349 .reference_centers = {center, center},
350 .radii = {radius, radius},
351 .half_width = -1.0f,
352 });
353 }
354
355 EllipticalVertexGenerator Tessellator::StrokedCircle(
356 const Matrix& view_transform,
357 const Point& center,
358 Scalar radius,
359 Scalar half_width) {
360 if (half_width > 0) {
361 auto divisions = ComputeQuadrantDivisions(
362 view_transform.GetMaxBasisLengthXY() * radius + half_width);
363 return EllipticalVertexGenerator(Tessellator::GenerateStrokedCircle,
364 GetTrigsForDivisions(divisions),
365 PrimitiveType::kTriangleStrip, 8,
366 {
367 .reference_centers = {center, center},
368 .radii = {radius, radius},
369 .half_width = half_width,
370 });
371 } else {
372 return FilledCircle(view_transform, center, radius);
373 }
374 }
375
376 EllipticalVertexGenerator Tessellator::RoundCapLine(
377 const Matrix& view_transform,
378 const Point& p0,
379 const Point& p1,
380 Scalar radius) {
381 auto along = p1 - p0;
382 auto length = along.GetLength();
383 if (length > kEhCloseEnough) {
384 auto divisions =
385 ComputeQuadrantDivisions(view_transform.GetMaxBasisLengthXY() * radius);
386 return EllipticalVertexGenerator(Tessellator::GenerateRoundCapLine,
387 GetTrigsForDivisions(divisions),
388 PrimitiveType::kTriangleStrip, 4,
389 {
390 .reference_centers = {p0, p1},
391 .radii = {radius, radius},
392 .half_width = -1.0f,
393 });
394 } else {
395 return FilledCircle(view_transform, p0, radius);
396 }
397 }
398
399 EllipticalVertexGenerator Tessellator::FilledEllipse(
400 const Matrix& view_transform,
401 const Rect& bounds) {
402 if (bounds.IsSquare()) {
403 return FilledCircle(view_transform, bounds.GetCenter(),
404 bounds.GetWidth() * 0.5f);
405 }
406 auto max_radius = bounds.GetSize().MaxDimension();
407 auto divisions = ComputeQuadrantDivisions(
408 view_transform.GetMaxBasisLengthXY() * max_radius);
409 auto center = bounds.GetCenter();
410 return EllipticalVertexGenerator(Tessellator::GenerateFilledEllipse,
411 GetTrigsForDivisions(divisions),
412 PrimitiveType::kTriangleStrip, 4,
413 {
414 .reference_centers = {center, center},
415 .radii = bounds.GetSize() * 0.5f,
416 .half_width = -1.0f,
417 });
418 }
419
420 EllipticalVertexGenerator Tessellator::FilledRoundRect(
421 const Matrix& view_transform,
422 const Rect& bounds,
423 const Size& radii) {
424 if (radii.width * 2 < bounds.GetWidth() ||
425 radii.height * 2 < bounds.GetHeight()) {
426 auto max_radius = radii.MaxDimension();
427 auto divisions = ComputeQuadrantDivisions(
428 view_transform.GetMaxBasisLengthXY() * max_radius);
429 auto upper_left = bounds.GetLeftTop() + radii;
430 auto lower_right = bounds.GetRightBottom() - radii;
431 return EllipticalVertexGenerator(Tessellator::GenerateFilledRoundRect,
432 GetTrigsForDivisions(divisions),
433 PrimitiveType::kTriangleStrip, 4,
434 {
435 .reference_centers =
436 {
437 upper_left,
438 lower_right,
439 },
440 .radii = radii,
441 .half_width = -1.0f,
442 });
443 } else {
444 return FilledEllipse(view_transform, bounds);
445 }
446 }
447
448 void Tessellator::GenerateFilledCircle(
449 const Trigs& trigs,
450 const EllipticalVertexGenerator::Data& data,
451 const TessellatedVertexProc& proc) {
452 auto center = data.reference_centers[0];
453 auto radius = data.radii.width;
454
455 FML_DCHECK(center == data.reference_centers[1]);
456 FML_DCHECK(radius == data.radii.height);
457 FML_DCHECK(data.half_width < 0);
458
459 // Quadrant 1 connecting with Quadrant 4:
460 for (auto& trig : trigs) {
461 auto offset = trig * radius;
462 proc({center.x - offset.x, center.y + offset.y});
463 proc({center.x - offset.x, center.y - offset.y});
464 }
465
466 // The second half of the circle should be iterated in reverse, but
467 // we can instead iterate forward and swap the x/y values of the
468 // offset as the angles should be symmetric and thus should generate
469 // symmetrically reversed trig vectors.
470 // Quadrant 2 connecting with Quadrant 2:
471 for (auto& trig : trigs) {
472 auto offset = trig * radius;
473 proc({center.x + offset.y, center.y + offset.x});
474 proc({center.x + offset.y, center.y - offset.x});
475 }
476 }
477
478 void Tessellator::GenerateStrokedCircle(
479 const Trigs& trigs,
480 const EllipticalVertexGenerator::Data& data,
481 const TessellatedVertexProc& proc) {
482 auto center = data.reference_centers[0];
483
484 FML_DCHECK(center == data.reference_centers[1]);
485 FML_DCHECK(data.radii.IsSquare());
486 FML_DCHECK(data.half_width > 0 && data.half_width < data.radii.width);
487
488 auto outer_radius = data.radii.width + data.half_width;
489 auto inner_radius = data.radii.width - data.half_width;
490
491 // Zig-zag back and forth between points on the outer circle and the
492 // inner circle. Both circles are evaluated at the same number of
493 // quadrant divisions so the points for a given division should match
494 // 1 for 1 other than their applied radius.
495
496 // Quadrant 1:
497 for (auto& trig : trigs) {
498 auto outer = trig * outer_radius;
499 auto inner = trig * inner_radius;
500 proc({center.x - outer.x, center.y - outer.y});
501 proc({center.x - inner.x, center.y - inner.y});
502 }
503
504 // The even quadrants of the circle should be iterated in reverse, but
505 // we can instead iterate forward and swap the x/y values of the
506 // offset as the angles should be symmetric and thus should generate
507 // symmetrically reversed trig vectors.
508 // Quadrant 2:
509 for (auto& trig : trigs) {
510 auto outer = trig * outer_radius;
511 auto inner = trig * inner_radius;
512 proc({center.x + outer.y, center.y - outer.x});
513 proc({center.x + inner.y, center.y - inner.x});
514 }
515
516 // Quadrant 3:
517 for (auto& trig : trigs) {
518 auto outer = trig * outer_radius;
519 auto inner = trig * inner_radius;
520 proc({center.x + outer.x, center.y + outer.y});
521 proc({center.x + inner.x, center.y + inner.y});
522 }
523
524 // Quadrant 4:
525 for (auto& trig : trigs) {
526 auto outer = trig * outer_radius;
527 auto inner = trig * inner_radius;
528 proc({center.x - outer.y, center.y + outer.x});
529 proc({center.x - inner.y, center.y + inner.x});
530 }
531 }
532
533 void Tessellator::GenerateRoundCapLine(
534 const Trigs& trigs,
535 const EllipticalVertexGenerator::Data& data,
536 const TessellatedVertexProc& proc) {
537 auto p0 = data.reference_centers[0];
538 auto p1 = data.reference_centers[1];
539 auto radius = data.radii.width;
540
541 FML_DCHECK(radius == data.radii.height);
542 FML_DCHECK(data.half_width < 0);
543
544 auto along = p1 - p0;
545 along *= radius / along.GetLength();
546 auto across = Point(-along.y, along.x);
547
548 for (auto& trig : trigs) {
549 auto relative_along = along * trig.cos;
550 auto relative_across = across * trig.sin;
551 proc(p0 - relative_along + relative_across);
552 proc(p0 - relative_along - relative_across);
553 }
554
555 // The second half of the round caps should be iterated in reverse, but
556 // we can instead iterate forward and swap the sin/cos values as they
557 // should be symmetric.
558 for (auto& trig : trigs) {
559 auto relative_along = along * trig.sin;
560 auto relative_across = across * trig.cos;
561 proc(p1 + relative_along + relative_across);
562 proc(p1 + relative_along - relative_across);
563 }
564 }
565
566 void Tessellator::GenerateFilledEllipse(
567 const Trigs& trigs,
568 const EllipticalVertexGenerator::Data& data,
569 const TessellatedVertexProc& proc) {
570 auto center = data.reference_centers[0];
571 auto radii = data.radii;
572
573 FML_DCHECK(center == data.reference_centers[1]);
574 FML_DCHECK(data.half_width < 0);
575
576 // Quadrant 1 connecting with Quadrant 4:
577 for (auto& trig : trigs) {
578 auto offset = trig * radii;
579 proc({center.x - offset.x, center.y + offset.y});
580 proc({center.x - offset.x, center.y - offset.y});
581 }
582
583 // The second half of the circle should be iterated in reverse, but
584 // we can instead iterate forward and swap the x/y values of the
585 // offset as the angles should be symmetric and thus should generate
586 // symmetrically reversed trig vectors.
587 // Quadrant 2 connecting with Quadrant 2:
588 for (auto& trig : trigs) {
589 auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
590 proc({center.x + offset.x, center.y + offset.y});
591 proc({center.x + offset.x, center.y - offset.y});
592 }
593 }
594
595 void Tessellator::GenerateFilledRoundRect(
596 const Trigs& trigs,
597 const EllipticalVertexGenerator::Data& data,
598 const TessellatedVertexProc& proc) {
599 Scalar left = data.reference_centers[0].x;
600 Scalar top = data.reference_centers[0].y;
601 Scalar right = data.reference_centers[1].x;
602 Scalar bottom = data.reference_centers[1].y;
603 auto radii = data.radii;
604
605 FML_DCHECK(data.half_width < 0);
606
607 // Quadrant 1 connecting with Quadrant 4:
608 for (auto& trig : trigs) {
609 auto offset = trig * radii;
610 proc({left - offset.x, bottom + offset.y});
611 proc({left - offset.x, top - offset.y});
612 }
613
614 // The second half of the round rect should be iterated in reverse, but
615 // we can instead iterate forward and swap the x/y values of the
616 // offset as the angles should be symmetric and thus should generate
617 // symmetrically reversed trig vectors.
618 // Quadrant 2 connecting with Quadrant 2:
619 for (auto& trig : trigs) {
620 auto offset = Point(trig.sin * radii.width, trig.cos * radii.height);
621 proc({right + offset.x, bottom + offset.y});
622 proc({right + offset.x, top - offset.y});
623 }
624 }
625
626 } // namespace impeller
buffer_view
BufferView buffer_view
Definition: blit_command_gles.cc:152
impeller::DeviceBuffer::Flush
virtual void Flush(std::optional< Range > range=std::nullopt) const
Definition: device_buffer.cc:13
impeller::DeviceBuffer::OnGetContents
virtual uint8_t * OnGetContents() const =0
impeller::FanVertexWriter
A vertex writer that generates a triangle fan and requires primitive restart.
Definition: path_component.h:29
impeller::FanVertexWriter::GetIndexCount
size_t GetIndexCount() const
Definition: path_component.cc:22
impeller::GLESVertexWriter
A vertex writer that has no hardware requirements.
Definition: path_component.h:92
impeller::HostBuffer
Definition: host_buffer.h:28
impeller::HostBuffer::Emplace
BufferView Emplace(const BufferType &buffer, size_t alignment=0)
Emplace non-uniform data (like contiguous vertices) onto the host buffer.
Definition: host_buffer.h:93
impeller::LineStripVertexWriter
A vertex writer that generates a line strip topology.
Definition: path_component.h:71
impeller::LineStripVertexWriter::GetVertexCount
std::pair< size_t, size_t > GetVertexCount() const
Definition: path_component.cc:100
impeller::LineStripVertexWriter::GetOversizedBuffer
const std::vector< Point > & GetOversizedBuffer() const
Definition: path_component.cc:96
impeller::Path
Paths are lightweight objects that describe a collection of linear, quadratic, or cubic segments....
Definition: path.h:53
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:338
impeller::Path::WritePolyline
void WritePolyline(Scalar scale, VertexWriter &writer) const
Definition: path.cc:105
impeller::Path::CountStorage
std::pair< size_t, size_t > CountStorage(Scalar scale) const
Determine required storage for points and number of contours.
Definition: path.cc:67
impeller::StripVertexWriter
A vertex writer that generates a triangle strip and requires primitive restart.
Definition: path_component.h:50
impeller::StripVertexWriter::GetIndexCount
size_t GetIndexCount() const
Definition: path_component.cc:46
impeller::Tessellator::EllipticalVertexGenerator
The |VertexGenerator| implementation common to all shapes that are based on a polygonal representatio...
Definition: tessellator.h:124
impeller::Tessellator::stroke_points_
std::vector< Point > stroke_points_
Used for stroke path generation.
Definition: tessellator.h:317
impeller::Tessellator::GetStrokePointCache
std::vector< Point > & GetStrokePointCache()
Retrieve a pre-allocated arena of kPointArenaSize points.
Definition: tessellator.cc:24
impeller::Tessellator::GenerateLineStrip
VertexBuffer GenerateLineStrip(const Path &path, HostBuffer &host_buffer, Scalar tolerance)
Given a path, create a line strip primitive structure.
Definition: tessellator.cc:120
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:238
impeller::Tessellator::TessellateConvexInternal
static void TessellateConvexInternal(const Path &path, std::vector< Point > &point_buffer, std::vector< uint16_t > &index_buffer, Scalar tolerance)
Definition: tessellator.cc:164
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:28
impeller::Tessellator::Tessellator
Tessellator()
Definition: tessellator.cc:14
impeller::Tessellator::~Tessellator
virtual ~Tessellator()
impeller::Tessellator::point_buffer_
std::unique_ptr< std::vector< Point > > point_buffer_
Used for polyline generation.
Definition: tessellator.h:314
impeller::Tessellator::index_buffer_
std::unique_ptr< std::vector< uint16_t > > index_buffer_
Definition: tessellator.h:315
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:81
impeller::Tessellator::TessellateConvex
VertexBuffer TessellateConvex(const Path &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:40
device_buffer.h
impeller
Definition: allocation.cc:12
impeller::ComputeQuadrantDivisions
static size_t ComputeQuadrantDivisions(Scalar pixel_radius)
Definition: tessellator.cc:246
impeller::IndexType::k16bit
@ k16bit
impeller::IndexType::kNone
@ kNone
Does not use the index buffer.
impeller::TessellatedVertexProc
Tessellator::TessellatedVertexProc TessellatedVertexProc
Definition: tessellator.cc:325
impeller::PrimitiveType
PrimitiveType
Decides how backend draws pixels based on input vertices.
Definition: formats.h:352
impeller::Scalar
float Scalar
Definition: scalar.h:18
impeller::kEhCloseEnough
constexpr float kEhCloseEnough
Definition: constants.h:56
impeller::kPrecomputedDivisionCount
static constexpr int kPrecomputedDivisionCount
Definition: tessellator.cc:176
impeller::Point
TPoint< Scalar > Point
Definition: point.h:327
impeller::kPiOver2
constexpr float kPiOver2
Definition: constants.h:32
impeller::EllipticalVertexGenerator
Tessellator::EllipticalVertexGenerator EllipticalVertexGenerator
Definition: tessellator.cc:326
impeller::kPrecomputedDivisions
static int kPrecomputedDivisions[kPrecomputedDivisionCount]
Definition: tessellator.cc:177
impeller::kPiOver4
constexpr float kPiOver4
Definition: constants.h:35
impeller::kPointArenaSize
static constexpr size_t kPointArenaSize
The size of the point arena buffer stored on the tessellator.
Definition: tessellator.h:22
std
Definition: comparable.h:95
path_component.h
polyline
const Path::Polyline & polyline
Definition: stroke_path_geometry.cc:311
offset
SeparatedVector2 offset
Definition: stroke_path_geometry.cc:319
impeller::BufferView
Definition: buffer_view.h:19
impeller::BufferView::GetRange
Range GetRange() const
Definition: buffer_view.h:27
impeller::BufferView::GetBuffer
const DeviceBuffer * GetBuffer() const
Definition: buffer_view.cc:17
impeller::Matrix
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
impeller::Matrix::GetMaxBasisLengthXY
constexpr Scalar GetMaxBasisLengthXY() const
Definition: matrix.h:310
impeller::Path::Polyline
Definition: path.h:111
impeller::Path::Polyline::PointBufferPtr
std::unique_ptr< std::vector< Point > > PointBufferPtr
Definition: path.h:114
impeller::Range::offset
size_t offset
Definition: range.h:14
impeller::TPoint< Scalar >
impeller::TPoint::GetLength
constexpr Type GetLength() const
Definition: point.h:206
impeller::TRect< Scalar >
impeller::TRect::GetHeight
constexpr Type GetHeight() const
Returns the height of the rectangle, equivalent to |GetSize().height|.
Definition: rect.h:351
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:331
impeller::TRect::IsSquare
constexpr bool IsSquare() const
Returns true if width and height are equal and neither is NaN.
Definition: rect.h:308
impeller::TRect::GetWidth
constexpr Type GetWidth() const
Returns the width of the rectangle, equivalent to |GetSize().width|.
Definition: rect.h:345
impeller::TRect::GetRightBottom
constexpr TPoint< T > GetRightBottom() const
Definition: rect.h:375
impeller::TRect::GetCenter
constexpr Point GetCenter() const
Get the center point as a |Point|.
Definition: rect.h:386
impeller::TRect::GetLeftTop
constexpr TPoint< T > GetLeftTop() const
Definition: rect.h:363
impeller::TSize< Scalar >
impeller::TSize::MaxDimension
constexpr Type MaxDimension() const
Definition: size.h:106
impeller::TSize::height
Type height
Definition: size.h:29
impeller::TSize::width
Type width
Definition: size.h:28
impeller::VertexBuffer
Definition: vertex_buffer.h:15
impeller::VertexBuffer::vertex_buffer
BufferView vertex_buffer
Definition: vertex_buffer.h:16
tessellator.h
data
std::shared_ptr< const fml::Mapping > data
Definition: texture_gles.cc:64