| Flutter Impeller |

shadow_path_geometry.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 "flutter/impeller/entity/geometry/shadow_path_geometry.h"
6
7 #include "flutter/impeller/entity/contents/pipelines.h"
8 #include "flutter/impeller/geometry/path_source.h"
9 #include "flutter/impeller/tessellator/path_tessellator.h"
10
11 namespace {
12
13 using impeller::kEhCloseEnough;
14 using impeller::Matrix;
15 using impeller::PathTessellator;
16 using impeller::Point;
17 using impeller::Scalar;
18 using impeller::ScalarNearlyZero;
19 using impeller::ShadowVertices;
20 using impeller::Tessellator;
21 using impeller::Trig;
22 using impeller::Vector2;
23
24 /// Each point in the polygon form of the path is turned into a structure
25 /// that tracks the gradient of the shadow at that point in the path. The
26 /// shape is turned into a sort of pin cushion where each struct acts
27 /// like a pin pushed into that cushion in the direction of the shadow
28 /// gradient at that location.
29 ///
30 /// Each entry contains the direction of the pin at that location and the
31 /// depth to which the pin is inserted, expressed as a fraction of the full
32 /// umbra size indicated by the shadow parameters. A depth of 1.0 means
33 /// the pin was inserted all the way to the depth of the shadow gradient
34 /// and didn't collide with any other pins. A fraction less than 1.0 can
35 /// occur if either the shape was too small and the pins intersected with
36 /// other pins across the shape from them, or if the curvature in a given
37 /// area was so tight that adjacent pins started bumping into their neighbors
38 /// even if the overall size of the shape was larger than the shadow.
39 ///
40 /// Different pins will be shortened by different amounts in the same shape
41 /// depending on their local geometry (tight curves or narrow cross section).
42 struct UmbraPin {
43 /// An initial value for the pin fraction that indicates that we have
44 /// not yet visited this pin during the clipping process.
45 static constexpr Scalar kFractionUninitialized = -1.0f;
46
47 /// The point on the original path that generated this entry into the
48 /// umbra geometry.
49 ///
50 /// AKA the point on the path at which this pin was stabbed.
51 Point path_vertex;
52
53 /// The relative vector from this path segment to the next.
54 Vector2 path_delta;
55
56 /// The vector from the path_vertex to the head of the pin (the part
57 /// outside the shape).
58 Vector2 penumbra_delta;
59
60 /// The location of the end of this pin, taking into account the reduction
61 /// of the umbra_size due to minimum distance to centroid, but ignoring
62 /// clipping against other pins.
63 Point pin_tip;
64
65 /// The location that this pin confers to the umbra polygon. Initially,
66 /// this is the same as the pin_tip, but can be reduced by intersecting
67 /// and clipping against other pins and even eliminated if the other
68 /// nearby pins make it redundant for defining the umbra polygon.
69 ///
70 /// Redundant or "removed" pins are indicated by no longer being a part
71 /// of the linked list formed by the |p_next| and |p_prev| pointers.
72 ///
73 /// Eventually, if this pin's umbra_vertex was eliminated, this location
74 /// will be overwritten by the surviving umbra vertex that best servies
75 /// this pin's path_vertex in a follow-on step.
76 Point umbra_vertex;
77
78 /// The index in the vertices vector where the umbra_vertex is eventually
79 /// inserted. Used to enter triangles into the indices vector.
80 uint16_t umbra_index = 0u;
81
82 /// The interior penetration of the umbra starts out at the full blur
83 /// radius as modified by the global distance of the path segments to
84 /// the centroid, but can be shortened when pins are too crowded and start
85 /// intersecting each other due to tight curvature.
86 ///
87 /// It's initial value is actually the uninitialized constant so that the
88 /// algorithm can treat it specially the first time it is encountered.
89 Scalar umbra_fraction = kFractionUninitialized;
90
91 /// Pointers used to create a circular linked list while pruning the umbra
92 /// polygon. The final list of vertices that remain in the umbra polygon
93 /// are the vertices that remain on this linked list from a "head" pin.
94 UmbraPin* p_next = nullptr;
95 UmbraPin* p_prev = nullptr;
96
97 /// Returns true after the umbra_fraction is first initialized to a real
98 /// value representing its potential intersections with other pins. At
99 /// that point it will be a number from 0 to 1.
100 bool IsFractionInitialized() const {
101 return umbra_fraction > kFractionUninitialized;
102 }
103 };
104
105 /// Simple cross products of nearby vertices don't catch all cases of
106 /// non-convexity so we count the number of times that the sign of the
107 /// dx/dy of the edges change. It must be <= 3 times for the path to
108 /// be convex. Think of drawing a circle from the top. First you head
109 /// to the right, then reverse to the left as you round the bottom of
110 /// the circle, then back near the top you head to the right again,
111 /// totalling 3 changes in direction.
112 struct DirectionDetector {
113 Scalar last_direction_ = 0.0f;
114 size_t change_count = 0u;
115
116 /// Check the coordinate delta for a new polygon edge to see if it
117 /// represents another change in direction for the path on this axis.
118 void AccumulateDirection(Scalar new_direction) {
119 if (last_direction_ == 0.0f || last_direction_ * new_direction < 0.0f) {
120 last_direction_ = std::copysign(1.0f, new_direction);
121 change_count++;
122 }
123 }
124
125 /// Returns true if the path must be concave.
126 bool IsConcave() const {
127 // See comment above on the struct for why 3 changes is the most you
128 // should see in a convex path.
129 return change_count > 3u;
130 }
131 };
132
133 /// Utility class to receive the vertices of a path and turn them into
134 /// a vector of UmbraPins along with a centroid Point.
135 ///
136 /// The class will immediately flag and stop processing any path that
137 /// has more than one contour since algorithms of the nature implemented
138 /// here won't be able to process such paths.
139 ///
140 /// The class will also flag and stop processing any path that has a
141 /// non-convex section because the current algorithm only works for convex
142 /// paths. Though it is possible to improve the algorithm to handle
143 /// concave single-contour paths in the future as the Skia utilities
144 /// provide a solution for those paths.
145 class UmbraPinAccumulator : public PathTessellator::VertexWriter {
146 public:
147 /// Parameters that determine the sub-pixel grid we will use to simplify
148 /// the contours to avoid degenerate differences in the vertices.
149 /// These 2 constants are a pair used in the implementation of the
150 /// ToDeviceGrid method and must be reciprocals of each other.
151 ///
152 /// @see ToPixelGrid
153 static constexpr Scalar kSubPixelCount = 16.0f;
154 static constexpr Scalar kSubPixelScale = (1.0f / kSubPixelCount);
155
156 /// The classification status of the path after all of the points are
157 /// accumulated.
158 enum class PathStatus {
159 /// The path was empty either because it contained no points or
160 /// because they enclosed no area.
161 kEmpty,
162
163 /// The path was complete, a single contour, and convex all around.
164 kConvex,
165
166 /// The path violated one of the conditions of convexity. Either it
167 /// had points that turned different ways along its perimeter, or it
168 /// turned more than 360 degrees, or it self-intersected.
169 kNonConvex,
170
171 /// The path had multiple contours.
172 kMultipleContours,
173 };
174
175 UmbraPinAccumulator() = default;
176 ~UmbraPinAccumulator() = default;
177
178 /// Reserve enough pins for the indicated number of path vertices to
179 /// avoid having to grow the vector during processing.
180 void Reserve(size_t vertex_count) { pins_.reserve(vertex_count); }
181
182 /// Return the status properties of the path.
183 /// see |PathStatus|
184 PathStatus GetStatus() { return GetResults().status; }
185
186 /// Returns a reference to the accumulated vector of UmbraPin structs.
187 /// Only valid if the status is kConvex.
188 std::vector<UmbraPin>& GetPins() { return pins_; }
189
190 /// Returns the centroid of the path.
191 /// Only valid if the status is kConvex.
192 Point GetCentroid() { return GetResults().centroid; }
193
194 /// Returns the turning direction of the path.
195 /// Only valid if the status is kConvex.
196 Scalar GetDirection() { return GetResults().path_direction; }
197
198 private:
199 /// The data computed when completing (finalizing) the analysis of the
200 /// path.
201 struct PathResults {
202 /// The type of path determined during the final analysis.
203 PathStatus status;
204
205 /// The centroid ("center of mass") of the path around which we will
206 /// build the shadow mesh.
207 Point centroid;
208
209 /// The direction of the path as determined by cross products. This
210 /// value is important to further processing to know when pins are
211 /// intersecting each other as the calculations for that condition
212 /// depend on the direction of the path.
213 Scalar path_direction = 0.0f;
214 };
215
216 // |VertexWriter|
217 void Write(Point point) override;
218
219 // |VertexWriter|
220 void EndContour() override;
221
222 /// Rounds the device coordinate to the sub-pixel grid.
223 static Point ToDeviceGrid(Point point);
224
225 /// The list of pins being accumulated for further processing by the
226 /// mesh generation code.
227 std::vector<UmbraPin> pins_;
228
229 /// Internal state variable used by the VertexWriter callbacks to know
230 /// if the path contained multiple contours. It is set to true when the
231 /// first contour is ended by a call to EndContour().
232 bool first_contour_ended_ = false;
233
234 /// Internal state variable used by the VertexWriter callbacks to know
235 /// if the path contained multiple contours. It is set to true if additional
236 /// path points are delivered after the first contour is ended.
237 bool has_multiple_contours_ = false;
238
239 /// The results of finalizing the analysis of the path, set only after
240 /// the final analysis method is run.
241 std::optional<PathResults> results_;
242
243 /// Finalize the path analysis if necessary and return the structure with
244 /// the results of the analysis.
245 PathResults& GetResults() {
246 if (results_.has_value()) {
247 return results_.value();
248 }
249 return (results_ = FinalizePath()).value();
250 }
251
252 /// Run through the accumulated, de-duplicated, de-collinearized points
253 /// and check for a convex, non-self-intersecting path.
254 PathResults FinalizePath();
255 };
256
257 /// The |PolygonInfo| class does most of the work of generating a mesh from
258 /// a path, including transforming it into device space, computing new vertices
259 /// by applying the inset and outset for the indicated occluder_height, and
260 /// then stitching all of those vertices together into a mesh that can be
261 /// used to render the shadow complete with gaussian coefficients for the
262 /// location of the mesh points within the shadow.
263 class PolygonInfo {
264 public:
265 /// Return the radius of the rounded corners of the shadow for the
266 /// indicated occluder_height.
267 static constexpr Scalar GetTrigRadiusForHeight(Scalar occluder_height) {
268 return GetPenumbraSizeForHeight(occluder_height);
269 }
270
271 /// Construct a PolygonInfo that will accept a path and compute a shadow
272 /// mesh at the indicated occluder_height.
273 explicit PolygonInfo(Scalar occluder_height);
274
275 /// Computes a shadow mesh for the indicated path (source) under the
276 /// given matrix with the associated trigs. If the algorithm is successful,
277 /// it will return the resulting mesh (which may be empty if the path
278 /// contained no area) or nullptr if it was unable to process the path.
279 ///
280 /// @param source The PathSource object that delivers the path segments
281 /// that define the path being shadowed.
282 /// @param matrix The transform matrix under which the shadow is being
283 /// viewed.
284 /// @param trigs The Trigs array that contains precomputed sin and cos
285 /// values for a flattened arc at the required radius for
286 /// rounding out the edges of the shadow as we turn corners
287 /// in the path.
288 ///
289 /// @see GetTrigRadiusForHeight
290 const std::shared_ptr<ShadowVertices> CalculateConvexShadowMesh(
291 const impeller::PathSource& source,
292 const impeller::Matrix& matrix,
293 const Tessellator::Trigs& trigs);
294
295 private:
296 /// Compute the size of the penumbra for a given occluder_height which
297 /// can vary depending on the type of shadow. Here we are only processing
298 /// ambient shadows.
299 static constexpr Scalar GetPenumbraSizeForHeight(Scalar occluder_height) {
300 return occluder_height;
301 }
302
303 /// Compute the size of the umbra for a given occluder_height which
304 /// can vary depending on the type of shadow. Here we are only processing
305 /// ambient shadows.
306 static constexpr Scalar GetUmbraSizeForHeight(Scalar occluder_height) {
307 return occluder_height;
308 }
309
310 /// The minimum distance (squared) between points on the mesh before we
311 /// eliminate them as redundant.
312 static constexpr Scalar kMinSubPixelDistanceSquared =
313 UmbraPinAccumulator::kSubPixelScale * UmbraPinAccumulator::kSubPixelScale;
314
315 /// The occluder_height for which we are processing this shadow.
316 const Scalar occluder_height_;
317
318 /// The maximum gaussian of the umbra part of the shadow, usually 1.0f
319 /// but can be reduced if the umbra size was clipped.
320 Scalar umbra_gaussian_ = 1.0f;
321
322 /// The vertex mesh result that represents the shadow, to be rendered
323 /// using a modified indexed variant of DrawVertices that also adjusts
324 /// the alpha of the colors on a per-pixel basis by mapping their linear
325 /// gaussian coefficients into the associated gaussian integral values.
326
327 /// vertices_ stores all of the points in the mesh.
328 std::vector<Point> vertices_;
329
330 /// indices_ stores the indexes of the triangles in the mesh, in a
331 /// raw triangle format (i.e. not a triangle fan or strip).
332 std::vector<uint16_t> indices_;
333
334 /// gaussians_ stores the gaussian values associated with each vertex
335 /// in the mesh, the values being 1:1 with the equivalent vertex in
336 /// the vertices_ vedtor.
337 std::vector<Scalar> gaussians_;
338
339 /// Run through the pins and determine the closest pin to the centroid
340 /// and, in particular, adjust the umbra_gaussian value if the closest pin
341 /// is less than the required umbra distance.
342 void ComputePinDirectionsAndMinDistanceToCentroid(std::vector<UmbraPin>& pins,
343 const Point& centroid,
344 Scalar direction);
345
346 /// The head and count for the list of UmbraPins that contribute to the
347 /// umbra vertex ring.
348 ///
349 /// The forward and backward pointers for the linked list are stored
350 /// in the UmbraPin struct as p_next, p_prev.
351 struct UmbraPinLinkedList {
352 UmbraPin* p_head_pin = nullptr;
353 size_t pin_count = 0u;
354
355 bool IsNull() { return p_head_pin == nullptr; }
356 };
357
358 /// Run through the pins and determine if they intersect each other
359 /// internally, whether they are completely obscured by other pins,
360 /// their new relative lengths if they defer to another pin at some
361 /// depth, and which remaining pins are part of the umbra polygon,
362 /// and then return the pointer to the first pin in the "umbra polygon".
363 UmbraPinLinkedList ResolveUmbraIntersections(std::vector<UmbraPin>& pins,
364 Scalar direction);
365
366 /// Structure to store the result of computing the intersection between
367 /// 2 pins, pin0 and pin1, containing the point of intersection and the
368 /// relative fractions at which the 2 pins intersected (expressed as a
369 /// ratio of 0 to 1 where 0 represents intersecting at the path outline
370 /// and 1 represents intersecting at the tip of the pin where the umbra
371 /// is darkest.
372 struct PinIntersection {
373 // The Point of the intersection between the pins.
374 Point intersection;
375 // The fraction along pin0 of the intersection.
376 Scalar fraction0;
377 // The fraction along pin1 of the intersection
378 Scalar fraction1;
379 };
380
381 /// Return the intersection between the 2 pins pin0 and pin1 if there
382 /// is an intersection, otherwise a nullopt to indicate that there is
383 /// no intersection.
384 static std::optional<PinIntersection> ComputeIntersection(UmbraPin& pin0,
385 UmbraPin& pin1);
386
387 /// Constants used to resolve pin intersections, adopted from the Skia
388 /// version of the algorithm.
389 static constexpr Scalar kCrossTolerance = 1.0f / 2048.0f;
390 static constexpr Scalar kIntersectionTolerance = 1.0e-6f;
391
392 /// Compute the squared length of a vector or a special out of bounds
393 /// value if the vector becomes infinite.
394 static constexpr Scalar FiniteVectorLengthSquared(Vector2 v) {
395 return !v.IsFinite() ? -1.0f : v.Dot(v);
396 }
397
398 /// Determine if the numerator and denominator are outside of the
399 /// interval that makes sense for an umbra intersection.
400 ///
401 /// Note calculation borrowed from Skia's SkPathUtils.
402 static constexpr inline bool OutsideInterval(Scalar numer,
403 Scalar denom,
404 bool denom_positive) {
405 return (denom_positive && (numer < 0 || numer > denom)) ||
406 (!denom_positive && (numer > 0 || numer < denom));
407 }
408
409 /// Remove the pin at p_pin from the linked list of pins when the caller
410 /// determines that it should not contribute to the final umbra polygon.
411 /// The pointer to the head pin at *p_head will also be adjusted if we've
412 /// eliminated the head pin itself and it will be additionally set to
413 /// nullptr if that was the last pin in the list.
414 ///
415 /// @param p_pin The pin to be eliminated from the list.
416 /// @param p_head The pointer to the head of the list which might also
417 /// need adjustment depending on which pin is removed.
418 static void RemovePin(UmbraPin* p_pin, UmbraPin** p_head);
419
420 /// A helper method for resolving pin conflicts, adopted directly from the
421 /// associated Skia algorithm.
422 ///
423 /// Note calculation borrowed from Skia's SkPathUtils.
424 static int ComputeSide(const Point& p0, const Vector2& v, const Point& p);
425
426 /// Run through the path calculating the outset vertices for the penumbra
427 /// and connecting them to the inset vertices of the umbra and then to
428 /// the centroid in a system of triangles with the appropriate alpha values
429 /// representing the intensity of the (non-gamma-adjusted) shadow at those
430 /// points. The resulting mesh should consist of 2 rings of triangles, an
431 /// inner ring connecting the centroid to the umbra polygon, and another
432 /// outer ring connecting vertices in the umbra polygon to vertices on the
433 /// outer edge of the penumbra.
434 ///
435 /// @param pins The list of pins, one for each edge of the polygon.
436 /// @param centroid The centroid ("center of mass") of the polygon.
437 /// @param list The linked list of the subset of pins that have
438 /// umbra vertices which appear in the umbra polygon.
439 /// @param trigs The vector of sin and cos for subdivided arcs that
440 /// can round the penumbra corner at each polygon corner.
441 /// @param direction The overall direction of the path as determined by
442 /// the consistent cross products of each edge turn.
443 void ComputeMesh(std::vector<UmbraPin>& pins,
444 const Point& centroid,
445 UmbraPinLinkedList& list,
446 const impeller::Tessellator::Trigs& trigs,
447 Scalar direction);
448
449 /// After the umbra_vertices of the pins are accumulated and linked into a
450 /// ring using their p_prev/p_next pointers, compute the best surviving umbra
451 /// vertex for each pin and set its location and index into the UmbraPin.
452 ///
453 /// @param pins The list of pins, one for each edge of the polygon.
454 /// @param list The linked list of the subset of pins that have
455 /// umbra vertices which appear in the umbra polygon.
456 /// @param centroid The centroid ("center of mass") of the polygon.
457 void PopulateUmbraVertices(std::vector<UmbraPin>& pins,
458 UmbraPinLinkedList& list,
459 const Point centroid);
460
461 /// Appends a fan of penumbra vertices centered on the path vertex of the
462 /// |p_curr_pin| starting from the absolute point |fan_start| and ending
463 /// at the absolute point |fan_end|, both of which should be equi-distant
464 /// from the path vertex. The index of the vertex at |fan_start| should
465 /// already be in the vector of vertices at an index given by |start_index|.
466 ///
467 /// @param p_curr_pin The pin at the corner around which the penumbra is
468 /// rotating.
469 /// @param fan_start The point on the penumbra where the fan starts.
470 /// @param fan_start The point on the penumbra where the fan ends.
471 /// @param start_index The index in the vector of vertices where the
472 /// fan_start vertex has already been inserted.
473 /// @param trigs The vector of sin and cos for subdivided arcs that
474 /// can round the penumbra corner at each polygon corner.
475 /// @param direction The overall direction of the path as determined by
476 /// the consistent cross products of each edge turn.
477 uint16_t AppendFan(const UmbraPin* p_curr_pin,
478 const Point& fan_start,
479 const Point& fan_end,
480 uint16_t start_index,
481 const impeller::Tessellator::Trigs& trigs,
482 Scalar direction);
483
484 /// Append a vertex and its associated gaussian coefficient to the lists
485 /// of vertices and guassians and return their (shared) index.
486 uint16_t AppendVertex(const Point& vertex, Scalar gaussian);
487
488 /// Append 3 indices to the indices vector to form a new triangle in the mesh.
489 void AddTriangle(uint16_t v0, uint16_t v1, uint16_t v2);
490 };
491
492 PolygonInfo::PolygonInfo(Scalar occluder_height)
493 : occluder_height_(occluder_height) {}
494
495 const std::shared_ptr<ShadowVertices> PolygonInfo::CalculateConvexShadowMesh(
496 const impeller::PathSource& source,
497 const Matrix& matrix,
498 const Tessellator::Trigs& trigs) {
499 if (!matrix.IsInvertible()) {
500 return ShadowVertices::kEmpty;
501 }
502
503 Scalar scale = matrix.GetMaxBasisLengthXY();
504
505 UmbraPinAccumulator pin_accumulator;
506
507 auto [point_count, contour_count] =
508 impeller::PathTessellator::CountFillStorage(source, scale);
509 pin_accumulator.Reserve(point_count);
510
511 PathTessellator::PathToTransformedFilledVertices(source, pin_accumulator,
512 matrix);
513
514 switch (pin_accumulator.GetStatus()) {
515 case UmbraPinAccumulator::PathStatus::kEmpty:
516 return ShadowVertices::kEmpty;
517 case UmbraPinAccumulator::PathStatus::kNonConvex:
518 case UmbraPinAccumulator::PathStatus::kMultipleContours:
519 return nullptr;
520 case UmbraPinAccumulator::PathStatus::kConvex:
521 break;
522 }
523
524 std::vector<UmbraPin>& pins = pin_accumulator.GetPins();
525 const Point& centroid = pin_accumulator.GetCentroid();
526 Scalar direction = pin_accumulator.GetDirection();
527
528 ComputePinDirectionsAndMinDistanceToCentroid(pins, centroid, direction);
529
530 UmbraPinLinkedList list = ResolveUmbraIntersections(pins, direction);
531 if (list.IsNull()) {
532 // Ideally the Resolve algorithm will always be able to create an
533 // inner loop of umbra vertices, but it is not perfect.
534 //
535 // The Skia algorithm from which this was taken tries to fake an
536 // umbra polygon that is 95% from the path polygon to the centroid,
537 // but that result does not resemble a proper shadow. If we run into
538 // this case a lot we should either beef up the ResolveIntersections
539 // algorithm or find a better approximation than "95% to the centroid".
540 return nullptr;
541 }
542
543 ComputeMesh(pins, centroid, list, trigs, direction);
544
545 Matrix inverted_matrix = matrix.Invert();
546 for (Point& vertex : vertices_) {
547 vertex = inverted_matrix * vertex;
548 }
549 return ShadowVertices::Make(std::move(vertices_), std::move(indices_),
550 std::move(gaussians_));
551 }
552
553 // Enter a new point for the polygon approximation of the shape. Points are
554 // normalized to a device subpixel grid based on |kSubPixelCount|, duplicates
555 // at that sub-pixel grid are ignored, collinear points are reduced to just
556 // the endpoints, and the centroid is updated from the remaining non-duplicate
557 // grid points.
558 void UmbraPinAccumulator::Write(Point point) {
559 // This type of algorithm will never be able to handle multiple contours.
560 if (first_contour_ended_) {
561 has_multiple_contours_ = true;
562 return;
563 }
564 FML_DCHECK(!has_multiple_contours_);
565
566 point = ToDeviceGrid(point);
567
568 if (!pins_.empty()) {
569 // If this isn't the first point then we need to perform de-duplication
570 // and possibly convexity checking and centroid updates.
571 Point prev = pins_.back().path_vertex;
572
573 // Adjusted points are rounded so == testing is OK here even for floating
574 // point coordinates.
575 if (point == prev) {
576 // Ignore this point as a duplicate
577 return;
578 }
579
580 if (pins_.size() >= 2u) {
581 // A quick collinear check to avoid extra processing later.
582 Point prev_prev = pins_.end()[-2].path_vertex;
583 Vector2 v0 = prev - prev_prev;
584 Vector2 v1 = point - prev_prev;
585 Scalar cross = v0.Cross(v1);
586 if (cross == 0) {
587 // This point is on the same line as the line between the last
588 // 2 points, so skip the intermediate point. Points that are
589 // collinear only contribute to the edge of the shape the vector
590 // from the first to the last of them.
591 pins_.pop_back();
592 if (point == prev_prev) {
593 // Not only do we eliminate the previous point as collinear, but
594 // we also eliminate this point as a duplicate.
595 // This point would tend to be eliminated anyway because it would
596 // automatically be collinear with whatever the next point would
597 // be, but we just avoid inserting it anyway to reduce processing.
598 return;
599 }
600 }
601 }
602 }
603
604 pins_.emplace_back(point);
605 }
606
607 // Called at the end of every contour of which we hope there is only one.
608 // If we detect more than one contour then the shadow tessellation becomes
609 // invalid.
610 //
611 // Each contour will have exactly one point at the beginning and end which
612 // are duplicates. The extra repeat of the first point actually helped the
613 // centroid accumulation do its math for ever segment in the path, but
614 // going forward we don't need the extra pin in the shape so we verify that
615 // it is a duplicate and then we delete it.
616 void UmbraPinAccumulator::EndContour() {
617 // This type of algorithm will never be able to handle multiple contours.
618 if (first_contour_ended_) {
619 has_multiple_contours_ = true;
620 return;
621 }
622 FML_DCHECK(!has_multiple_contours_);
623
624 // PathTessellator always ensures the path is closed back to the origin
625 // by an extra call to Write(Point).
626 FML_DCHECK(pins_.front().path_vertex == pins_.back().path_vertex);
627 pins_.pop_back();
628 first_contour_ended_ = true;
629 }
630
631 // Adjust the device point to its nearest sub-pixel grid location.
632 Point UmbraPinAccumulator::ToDeviceGrid(Point point) {
633 return (point * kSubPixelCount).Round() * kSubPixelScale;
634 }
635
636 // This method assumes that the pins have been accumulated by the PathVertex
637 // methods which ensure that no adjacent points are identical or collinear.
638 // It returns a PathResults that contains all of the relevant information
639 // depending on the geometric state of the path itself (ignoring whether
640 // the rest of the shadow processing will succeed).
641 //
642 // It performs 4 functions:
643 // - Normalizes empty paths (either too few vertices, or no turning directin)
644 // to an empty pins vector.
645 // - Accumulates and sets the centroid of the path
646 // - Accumulates and sets the overall direction of the path as determined by
647 // the sign of the cross products which must all agree.
648 // - Checks for convexity, including:
649 // - The direction vector determined above.
650 // - The turning direction of every triplet of points.
651 // - The signs of the area accumulated using cross products.
652 // - The number of times that the path edges change sign in X or Y.
653 UmbraPinAccumulator::PathResults UmbraPinAccumulator::FinalizePath() {
654 FML_DCHECK(!results_.has_value());
655
656 if (has_multiple_contours_) {
657 return {.status = PathStatus::kMultipleContours};
658 }
659
660 if (pins_.size() < 3u) {
661 return {.status = PathStatus::kEmpty};
662 }
663
664 DirectionDetector x_direction_detector;
665 DirectionDetector y_direction_detector;
666
667 Point relative_centroid;
668 Scalar path_direction = 0.0f;
669 Scalar path_area = 0.0f;
670
671 Point prev = pins_.back().path_vertex;
672 Point prev_prev = pins_.end()[-2].path_vertex;
673 Point first = pins_.front().path_vertex;
674 for (UmbraPin& pin : pins_) {
675 Point new_point = pin.path_vertex;
676
677 // Check for going around more than once in the same direction.
678 {
679 Vector2 delta = new_point - prev;
680 x_direction_detector.AccumulateDirection(delta.x);
681 y_direction_detector.AccumulateDirection(delta.y);
682 if (x_direction_detector.IsConcave() ||
683 y_direction_detector.IsConcave()) {
684 return {.status = PathStatus::kNonConvex};
685 }
686 }
687
688 // Check if the path is locally convex over the most recent 3 vertices.
689 if (path_direction != 0.0f) {
690 Vector2 v0 = prev - prev_prev;
691 Vector2 v1 = new_point - prev_prev;
692 Scalar cross = v0.Cross(v1);
693 // We should have eliminated adjacent collinear points in the first pass.
694 FML_DCHECK(cross != 0.0f);
695 if (cross * path_direction < 0.0f) {
696 return {.status = PathStatus::kNonConvex};
697 }
698 }
699
700 // Check if the path is globally convex with respect to the first vertex.
701 {
702 Vector2 v0 = prev - first;
703 Vector2 v1 = new_point - first;
704 Scalar quad_area = v0.Cross(v1);
705 if (quad_area != 0) {
706 // convexity check for whole path which can detect if we turn more than
707 // 360 degrees and start going the other way wrt the start point, but
708 // does not detect if any pair of points are concave (checked above).
709 if (path_direction == 0) {
710 path_direction = std::copysign(1.0f, quad_area);
711 } else if (quad_area * path_direction < 0) {
712 return {.status = PathStatus::kNonConvex};
713 }
714
715 relative_centroid += (v0 + v1) * quad_area;
716 path_area += quad_area;
717 }
718 }
719
720 prev_prev = prev;
721 prev = new_point;
722 }
723
724 if (path_direction == 0.0f) {
725 // We never changed direction, indicate emptiness.
726 return {.status = PathStatus::kEmpty};
727 }
728
729 // We are computing the centroid using a weighted average of all of the
730 // centroids of the triangles in a tessellation of the polygon, in this
731 // case a triangle fan tessellation relative to the first point in the
732 // polygon. We could use any point, but since we had to compute the cross
733 // product above relative to the initial point in order to detect if the
734 // path turned more than once, we already have values available relative
735 // to that first point here.
736 //
737 // The centroid of each triangle is the 3-way average of the corners of
738 // that triangle. Since the triangles are all relative to the first point,
739 // one of those corners is (0, 0) in this relative triangle and so we can
740 // simply add up the x,y of the two relative points and divide by 3.0.
741 // Since all values in the sum are divided by 3.0, we can save that
742 // constant division until the end when we finalize the average computation.
743 //
744 // We also weight these centroids by the area of the triangle so that we
745 // adjust for the parts of the polygon that are represented more densely
746 // and the parts that span a larger part of its circumference. A simple
747 // average would bias the centroid towards parts of the polygon where the
748 // points are denser. If we are rendering a polygonal representation of
749 // a round rect with only one round corner, all of the many approximating
750 // segments of the flattened round corner would overwhelm the handful of
751 // other simple segments for the flat sides. A weighted average places the
752 // centroid back at the "center of mass" of the polygon.
753 //
754 // Luckily, the same cross product used above that helps us determine the
755 // turning and convexity of the polygon also provides us with the area of
756 // the parallelogram projected from the 3 points in the triangle. That
757 // area is exactly double the area of the triangle itself. We could divide
758 // by 2 here, but since we are also accumulating these cross product values
759 // for the final weighted division, the factors of 2 all cancel out.
760 //
761 // path_area is (2 * triangle area).
762 // relative_centroid is accumulating sum(3 * triangle centroid * quad area).
763 // path_area_ is accumulating sum(quad area).
764 //
765 // The final combined average weight factor will be (3 * sum(quad area)).
766 relative_centroid /= 3.0f * path_area;
767
768 // The centroid accumulation was relative to the first point in the
769 // polygon so we make it absolute here.
770 return {
771 .status = PathStatus::kConvex,
772 .centroid = pins_[0].path_vertex + relative_centroid,
773 .path_direction = path_direction,
774 };
775 }
776
777 void PolygonInfo::ComputePinDirectionsAndMinDistanceToCentroid(
778 std::vector<UmbraPin>& pins,
779 const Point& centroid,
780 Scalar direction) {
781 Scalar desired_umbra_size = GetUmbraSizeForHeight(occluder_height_);
782 Scalar min_umbra_squared = desired_umbra_size * desired_umbra_size;
783 FML_DCHECK(direction == 1.0f || direction == -1.0f);
784
785 // For simplicity of iteration, we start with the last vertex as the
786 // "previous" pin and then iterate once over the vector of pins,
787 // performing these calculations on the path segment from the previous
788 // pin to the current pin. In the end, all pins and therefore all path
789 // segments are processed once even if we start with the last pin.
790
791 // First pass, compute the smallest distance to the centroid.
792 UmbraPin* p_prev_pin = &pins.back();
793 for (UmbraPin& pin : pins) {
794 UmbraPin* p_curr_pin = &pin;
795
796 // Accumulate (min) the distance from the centroid to "this" segment.
797 Scalar distance_squared = centroid.GetDistanceToSegmentSquared(
798 p_prev_pin->path_vertex, p_curr_pin->path_vertex);
799 min_umbra_squared = std::min(min_umbra_squared, distance_squared);
800
801 p_prev_pin = p_curr_pin;
802 }
803
804 static constexpr auto kTolerance = 1.0e-2f;
805 Scalar umbra_size = std::sqrt(min_umbra_squared);
806 if (umbra_size < desired_umbra_size + kTolerance) {
807 // if the umbra would collapse, we back off a bit on the inner blur and
808 // adjust the alpha
809 auto newInset = umbra_size - kTolerance;
810 auto ratio = 0.5f * (newInset / desired_umbra_size + 1);
811 FML_DCHECK(std::isfinite(ratio));
812
813 umbra_gaussian_ = ratio;
814 umbra_size = newInset;
815 } else {
816 FML_DCHECK(umbra_gaussian_ == 1.0f);
817 }
818
819 // Second pass, fill out the pin data with the final umbra size.
820 //
821 // We also link all of the pins into a circular linked list so they can be
822 // quickly eliminated in the method that resolves intersections of the pins.
823 Scalar penumbra_scale = -GetPenumbraSizeForHeight(occluder_height_);
824 p_prev_pin = &pins.back();
825 for (UmbraPin& pin : pins) {
826 UmbraPin* p_curr_pin = &pin;
827 p_curr_pin->p_prev = p_prev_pin;
828 p_prev_pin->p_next = p_curr_pin;
829
830 // We compute the vector along the path segment from the previous
831 // path vertex to this one as well as the unit direction vector
832 // that points from that pin towards the center of the shape,
833 // perpendicular to that segment.
834 p_prev_pin->path_delta = p_curr_pin->path_vertex - p_prev_pin->path_vertex;
835 Vector2 pin_direction = p_prev_pin
836 ->path_delta //
837 .Normalize()
838 .PerpendicularRight() *
839 direction;
840
841 p_prev_pin->penumbra_delta = pin_direction * penumbra_scale;
842 p_prev_pin->umbra_vertex = //
843 p_prev_pin->pin_tip =
844 p_prev_pin->path_vertex + pin_direction * umbra_size;
845
846 p_prev_pin = p_curr_pin;
847 }
848 }
849
850 // Compute the intersection 'p' between the two pins pin 0 and pin 1, if any.
851 // The intersection structure will contain the fractional distances along the
852 // pins of the intersection and the intersection point itself if there is an
853 // intersection.
854 //
855 // The intersection structure will be reset to empty otherwise.
856 //
857 // This method was converted nearly verbatim from the Skia source files
858 // SkShadowTessellator.cpp and SkPolyUtils.cpp, except for variable
859 // naming and differences in the methods on Point and Vertex2.
860 std::optional<PolygonInfo::PinIntersection> PolygonInfo::ComputeIntersection(
861 UmbraPin& pin0,
862 UmbraPin& pin1) {
863 Vector2 v0 = pin0.path_delta;
864 Vector2 v1 = pin1.path_delta;
865 Vector2 tip_delta = pin1.pin_tip - pin0.pin_tip;
866 Vector2 w = tip_delta;
867 Scalar denom = pin0.path_delta.Cross(pin1.path_delta);
868 bool denom_positive = (denom > 0);
869 Scalar numerator0, numerator1;
870
871 if (ScalarNearlyZero(denom, kCrossTolerance)) {
872 // This code also exists in the Skia version of this method, but it is
873 // not clear that we can ever enter here. In particular, since points
874 // were normalized to a grid (1/16th of a pixel), de-duplicated, and
875 // collinear points eliminated, denom can never be 0. And since the
876 // denom value was computed from a cross product of non-normalized
877 // delta vectors, its magnitude must exceed 1/256 which is far greater
878 // than the tolerance value.
879 //
880 // Note that in the Skia code, this method lived in a general polygon
881 // module that was unaware that it was being fed de-duplicated vertices
882 // from the Shadow module, so this code might be possible to trigger
883 // for "unfiltered" polygons, but not the normalized polygons that our
884 // (and Skia's) shadow code uses.
885 //
886 // Though entering here seems unlikely, we include the code until we can
887 // perform more due diligence in vetting that this is truly dead code.
888
889 // segments are parallel, but not collinear
890 if (!ScalarNearlyZero(tip_delta.Cross(pin0.path_delta), kCrossTolerance) ||
891 !ScalarNearlyZero(tip_delta.Cross(pin1.path_delta), kCrossTolerance)) {
892 return std::nullopt;
893 }
894
895 // Check for zero-length segments
896 Scalar v0_length_squared = FiniteVectorLengthSquared(v0);
897 if (v0_length_squared <= 0.0f) {
898 // Both are zero-length
899 Scalar v1_length_squared = FiniteVectorLengthSquared(v1);
900 if (v1_length_squared <= 0.0f) {
901 // Check if they're the same point
902 if (w.IsFinite() && !w.IsZero()) {
903 return {{
904 .intersection = pin0.pin_tip,
905 .fraction0 = 0.0f,
906 .fraction1 = 0.0f,
907 }};
908 } else {
909 // Intersection is indeterminate
910 return std::nullopt;
911 }
912 }
913 // Otherwise project segment0's origin onto segment1
914 numerator1 = v1.Dot(-w);
915 denom = v1_length_squared;
916 if (OutsideInterval(numerator1, denom, true)) {
917 return std::nullopt;
918 }
919 numerator0 = 0;
920 } else {
921 // Project segment1's endpoints onto segment0
922 numerator0 = v0.Dot(w);
923 denom = v0_length_squared;
924 numerator1 = 0;
925 if (OutsideInterval(numerator0, denom, true)) {
926 // The first endpoint doesn't lie on segment0
927 // If segment1 is degenerate, then there's no collision
928 Scalar v1_length_squared = FiniteVectorLengthSquared(v1);
929 if (v1_length_squared <= 0.0f) {
930 return std::nullopt;
931 }
932
933 // Otherwise try the other one
934 Scalar old_numerator0 = numerator0;
935 numerator0 = v0.Dot(w + v1);
936 numerator1 = denom;
937 if (OutsideInterval(numerator0, denom, true)) {
938 // it's possible that segment1's interval surrounds segment0
939 // this is false if params have the same signs, and in that case
940 // no collision
941 if (numerator0 * old_numerator0 > 0) {
942 return std::nullopt;
943 }
944 // otherwise project segment0's endpoint onto segment1 instead
945 numerator0 = 0;
946 numerator1 = v1.Dot(-w);
947 denom = v1_length_squared;
948 }
949 }
950 }
951 } else {
952 numerator0 = w.Cross(v1);
953 if (OutsideInterval(numerator0, denom, denom_positive)) {
954 return std::nullopt;
955 }
956 numerator1 = w.Cross(v0);
957 if (OutsideInterval(numerator1, denom, denom_positive)) {
958 return std::nullopt;
959 }
960 }
961
962 Scalar fraction0 = numerator0 / denom;
963 Scalar fraction1 = numerator1 / denom;
964
965 return {{
966 .intersection = pin0.pin_tip + v0 * fraction0,
967 .fraction0 = fraction0,
968 .fraction1 = fraction1,
969 }};
970 }
971
972 void PolygonInfo::RemovePin(UmbraPin* p_pin, UmbraPin** p_head) {
973 UmbraPin* p_next = p_pin->p_next;
974 UmbraPin* p_prev = p_pin->p_prev;
975 p_prev->p_next = p_next;
976 p_next->p_prev = p_prev;
977 if (*p_head == p_pin) {
978 *p_head = (p_next == p_pin) ? nullptr : p_next;
979 }
980 }
981
982 // Computes the relative direction for point p compared to segment defined
983 // by origin p0 and vector v. A positive value means the point is to the
984 // left of the segment, negative is to the right, 0 is collinear.
985 int PolygonInfo::ComputeSide(const Point& p0,
986 const Vector2& v,
987 const Point& p) {
988 Vector2 w = p - p0;
989 Scalar cross = v.Cross(w);
990 if (!impeller::ScalarNearlyZero(cross, kCrossTolerance)) {
991 return ((cross > 0) ? 1 : -1);
992 }
993
994 return 0;
995 }
996
997 // This method was converted nearly verbatim from the Skia source files
998 // SkShadowTessellator.cpp and SkPolyUtils.cpp, except for variable
999 // naming and differences in the methods on Point and Vertex2.
1000 PolygonInfo::UmbraPinLinkedList PolygonInfo::ResolveUmbraIntersections(
1001 std::vector<UmbraPin>& pins,
1002 Scalar direction) {
1003 UmbraPin* p_head_pin = &pins.front();
1004 UmbraPin* p_curr_pin = p_head_pin;
1005 UmbraPin* p_prev_pin = p_curr_pin->p_prev;
1006 size_t umbra_vertex_count = pins.size();
1007
1008 // we should check each edge against each other edge at most once
1009 size_t allowed_iterations = pins.size() * pins.size() + 1u;
1010
1011 while (p_head_pin && p_prev_pin != p_curr_pin) {
1012 if (--allowed_iterations == 0) {
1013 return {};
1014 }
1015
1016 std::optional<PinIntersection> intersection =
1017 ComputeIntersection(*p_prev_pin, *p_curr_pin);
1018 if (intersection.has_value()) {
1019 // If the new intersection is further back on previous inset from the
1020 // prior intersection...
1021 if (intersection->fraction0 < p_prev_pin->umbra_fraction) {
1022 // no point in considering this one again
1023 RemovePin(p_prev_pin, &p_head_pin);
1024 --umbra_vertex_count;
1025 // go back one segment
1026 p_prev_pin = p_prev_pin->p_prev;
1027 } else if (p_curr_pin->IsFractionInitialized() &&
1028 p_curr_pin->umbra_vertex.GetDistanceSquared(
1029 intersection->intersection) < kIntersectionTolerance) {
1030 // We've already considered this intersection and come to the same
1031 // result, we're done.
1032 break;
1033 } else {
1034 // Add intersection.
1035 p_curr_pin->umbra_vertex = intersection->intersection;
1036 p_curr_pin->umbra_fraction = intersection->fraction1;
1037
1038 // go to next segment
1039 p_prev_pin = p_curr_pin;
1040 p_curr_pin = p_curr_pin->p_next;
1041 }
1042 } else {
1043 // if previous pin is to right side of the current pin...
1044 int side = direction * ComputeSide(p_curr_pin->pin_tip, //
1045 p_curr_pin->path_delta, //
1046 p_prev_pin->pin_tip);
1047 if (side < 0 &&
1048 side == direction * ComputeSide(p_curr_pin->pin_tip, //
1049 p_curr_pin->path_delta, //
1050 p_prev_pin->pin_tip +
1051 p_prev_pin->path_delta)) {
1052 // no point in considering this one again
1053 RemovePin(p_prev_pin, &p_head_pin);
1054 --umbra_vertex_count;
1055 // go back one segment
1056 p_prev_pin = p_prev_pin->p_prev;
1057 } else {
1058 // move to next segment
1059 RemovePin(p_curr_pin, &p_head_pin);
1060 --umbra_vertex_count;
1061 p_curr_pin = p_curr_pin->p_next;
1062 }
1063 }
1064 }
1065
1066 if (!p_head_pin) {
1067 return {};
1068 }
1069
1070 // Now remove any duplicates from the umbra polygon. The head pin is
1071 // automatically included as the first point of the umbra polygon.
1072 p_prev_pin = p_head_pin;
1073 p_curr_pin = p_head_pin->p_next;
1074 size_t umbra_vertices = 1u;
1075 while (p_curr_pin != p_head_pin) {
1076 if (p_prev_pin->umbra_vertex.GetDistanceSquared(p_curr_pin->umbra_vertex) <
1077 kMinSubPixelDistanceSquared) {
1078 RemovePin(p_curr_pin, &p_head_pin);
1079 p_curr_pin = p_curr_pin->p_next;
1080 } else {
1081 umbra_vertices++;
1082 p_prev_pin = p_curr_pin;
1083 p_curr_pin = p_curr_pin->p_next;
1084 }
1085 FML_DCHECK(p_curr_pin == p_prev_pin->p_next);
1086 FML_DCHECK(p_prev_pin == p_curr_pin->p_prev);
1087 }
1088
1089 if (umbra_vertices < 3u) {
1090 return {};
1091 }
1092
1093 return {p_head_pin, umbra_vertices};
1094 }
1095
1096 // The mesh computed connects all of the points in two rings. The outermost
1097 // ring represents the point where the shadow disappears and those points
1098 // are associated with an alpha of 0. The umbra polygon represents the ring
1099 // where the shadow is its darkest, usually fully "opaque" (potentially
1100 // modulated by a non-opaque shadow color, but opaque with respect to the
1101 // shadow's varying intensity). The umbra polygon may not be fully "opaque"
1102 // with respect to the shadow cast by the shape if the shadows radius is
1103 // larger than the cross-section of the shape. If the umbra polygon is pulled
1104 // back from extending the shadow distance inward due to this phenomenon,
1105 // then the umbra_gaussian will be computed to be less than fully opaque.
1106 //
1107 // The mesh will connect the centroid to the umbra (inner) polygon at a
1108 // constant level as computed in umbra_gaussian, and then the umbra polygon
1109 // is connected to the nearest points on the penumbra (outer) polygon which
1110 // is seeded with points that are fully transparent (umbra level 0).
1111 //
1112 // This creates 2 rings of triangles that are interspersed in the vertices_
1113 // and connected into triangles using indices_ both to reuse the vertices
1114 // as best we can and also because we don't generate the vertices in any
1115 // kind of useful fan or strip format. The points are reused as such:
1116 //
1117 // - The centroid vertex will be used once for each pair of umbra vertices
1118 // to make triangles for the inner ring.
1119 // - Each umbra vertex will be used in both the inner and the outer rings.
1120 // In particular, in 2 of the inner ring triangles and in an arbitrary
1121 // number of the outer ring vertices (each outer ring vertex is connected
1122 // to the neariest inner ring vertex so the mapping is not predictable).
1123 // - Each outer ring vertex is used in at least 2 outer ring triangles, the
1124 // one that links to the vertex before it and the one that links to the
1125 // vertex following it, plus we insert extra vertices on the outer ring
1126 // to turn the corners beteween the projected segments.
1127 void PolygonInfo::ComputeMesh(std::vector<UmbraPin>& pins,
1128 const Point& centroid,
1129 UmbraPinLinkedList& list,
1130 const impeller::Tessellator::Trigs& trigs,
1131 Scalar direction) {
1132 // Centroid and umbra polygon...
1133 size_t vertex_count = list.pin_count + 1u;
1134 size_t triangle_count = list.pin_count;
1135
1136 // Penumbra corners - likely many more fan vertices than estimated...
1137 size_t penumbra_count = pins.size() * 2; // 2 perp at each vertex.
1138 penumbra_count += trigs.size() * 4; // total 360 degrees of fans.
1139 vertex_count += penumbra_count;
1140 triangle_count += penumbra_count;
1141
1142 vertices_.reserve(vertex_count);
1143 gaussians_.reserve(vertex_count);
1144 indices_.reserve(triangle_count * 3);
1145
1146 // First we populate the umbra_vertex and umbra_index of each pin with its
1147 // nearest point on the umbra polygon (the linked list computed earlier).
1148 //
1149 // This step simplifies the following operations because we will always
1150 // know which umbra vertex each pin object is associated with and whether
1151 // we need to bridge between them as we progress through the pins, without
1152 // having to search through the linked list every time.
1153 //
1154 // This method will also fill in the inner part of the mesh that connects
1155 // the centroid to every vertex in the umbra polygon with triangles that
1156 // are all at the maximum umbra gaussian coefficient.
1157 PopulateUmbraVertices(pins, list, centroid);
1158
1159 // We now run through the list of all pins and append points and triangles
1160 // to our internal vectors to cover the part of the mesh that extends
1161 // out from the umbra polygon to the outer penumbra points.
1162 //
1163 // Each pin assumes that the previous pin contributed some points to the
1164 // penumbra polygon that ended with the point that is perpendicular to
1165 // the side between that previous path vertex and its own path vertex.
1166 // This pin will then contribute any number of the following points to
1167 // the penumbra polygon:
1168 //
1169 // - If this pin uses a different umbra vertex than the previous pin
1170 // (common for simple large polygons that have no clipping of their
1171 // inner umbra points) then it inserts a bridging quad that connects
1172 // from the ending segment of the previous pin to the starting segment
1173 // of this pin. If both are based on the same umbra vertex then the
1174 // end of the previous pin is identical to the start of this one.
1175 // - Possibly a fan of extra vertices to round the corner from the
1176 // last segment added, which is perpendicular to the previous path
1177 // segment, to the final segmet of this pin, which will be perpendicular
1178 // to the following path segment.
1179 // - The last penumbra point added will be the penumbra point that is
1180 // perpendicular to the following segment, which prepares for the
1181 // initial conditions that the next pin will expect.
1182 const UmbraPin* p_prev_pin = &pins.back();
1183
1184 // This point may be duplicated at the end of the path. We can try to
1185 // avoid adding it twice with some bookkeeping, but it is simpler to
1186 // just add it here for the pre-conditions of the start of the first
1187 // pin and allow the duplication to happen naturally as we process the
1188 // final pin later. One extra point should not be very noticeable in
1189 // the long list of mesh vertices.
1190 Point last_penumbra_point =
1191 p_prev_pin->path_vertex + p_prev_pin->penumbra_delta;
1192 uint16_t last_penumbra_index = AppendVertex(last_penumbra_point, 0.0f);
1193
1194 for (const UmbraPin& pin : pins) {
1195 const UmbraPin* p_curr_pin = &pin;
1196
1197 // Preconditions:
1198 // - last_penumbra_point was the last outer vertex added by the
1199 // previous pin
1200 // - last_penumbra_index is its index in the vertices to be used
1201 // for creating indexed triangles.
1202
1203 if (p_prev_pin->umbra_index != p_curr_pin->umbra_index) {
1204 // We've moved on to a new umbra index to anchor our penumbra triangles.
1205 // We need to bridge the gap so that we are now building a new fan from
1206 // a point that has the same relative angle from the current pin's
1207 // path vertex as the previous penumbra point had from the previous
1208 // pin's path vertex.
1209 //
1210 // Our previous penumbra fan vector would have gone from the previous
1211 // pin's umbra point to the previous pen's final penumbra point:
1212 // - prev->umbra_vertex
1213 // => prev->path_vertex + prev->penumbra_delta
1214 // We will connect to a parallel vector that extends from the new
1215 // (current pin's) umbra index in the same direction:
1216 // - curr->umbra_vertex
1217 // => curr->path_vertex + prev->penumbra_delta
1218
1219 // First we pivot about the old penumbra point to bridge from the old
1220 // umbra vertex to our new umbra point.
1221 AddTriangle(last_penumbra_index, //
1222 p_prev_pin->umbra_index, p_curr_pin->umbra_index);
1223 }
1224
1225 // Then we bridge from the old penumbra point to the new parallel
1226 // penumbra point, pivoting around the new umbra index.
1227 Point new_penumbra_point =
1228 p_curr_pin->path_vertex + p_prev_pin->penumbra_delta;
1229 uint16_t new_penumbra_index = AppendVertex(new_penumbra_point, 0.0f);
1230
1231 if (last_penumbra_index != new_penumbra_index) {
1232 AddTriangle(p_curr_pin->umbra_index, last_penumbra_index,
1233 new_penumbra_index);
1234 }
1235
1236 last_penumbra_point = new_penumbra_point;
1237 last_penumbra_index = new_penumbra_index;
1238
1239 // Now draw a fan from the current pin's umbra vertex to all of the
1240 // penumbra points associated with this pin's path vertex, ending at
1241 // our new final penumbra point associated with this pin.
1242 new_penumbra_point = p_curr_pin->path_vertex + p_curr_pin->penumbra_delta;
1243 new_penumbra_index =
1244 AppendFan(p_curr_pin, last_penumbra_point, new_penumbra_point,
1245 last_penumbra_index, trigs, direction);
1246
1247 last_penumbra_point = new_penumbra_point;
1248 last_penumbra_index = new_penumbra_index;
1249 p_prev_pin = p_curr_pin;
1250 }
1251 }
1252
1253 // Visit each pin and find the nearest umbra_vertex from the linked list of
1254 // surviving umbra pins so we don't have to constantly find this as we stitch
1255 // together the mesh.
1256 void PolygonInfo::PopulateUmbraVertices(std::vector<UmbraPin>& pins,
1257 UmbraPinLinkedList& list,
1258 const Point centroid) {
1259 // We should be having the first crack at the vertex list, filling it with
1260 // the centroid, the umbra vertices, and the mesh connecting those into the
1261 // central core of the shadow.
1262 FML_DCHECK(list.p_head_pin != nullptr);
1263 FML_DCHECK(vertices_.empty());
1264 FML_DCHECK(gaussians_.empty());
1265 FML_DCHECK(indices_.empty());
1266
1267 // Always start with the centroid.
1268 uint16_t last_umbra_index = AppendVertex(centroid, umbra_gaussian_);
1269 FML_DCHECK(last_umbra_index == 0u);
1270
1271 // curr_umbra_pin is the most recently matched umbra vertex pin.
1272 // next_umbra_pin is the next umbra vertex pin to consider.
1273 // These pointers will always point to one of the pins that is on the
1274 // linked list of surviving umbra pins, possibly jumping over many
1275 // other umbra pins that were eliminated when we inset the polygon.
1276 UmbraPin* p_next_umbra_pin = list.p_head_pin;
1277 UmbraPin* p_curr_umbra_pin = p_next_umbra_pin->p_prev;
1278 for (UmbraPin& pin : pins) {
1279 if (p_next_umbra_pin == &pin ||
1280 (pin.path_vertex.GetDistanceSquared(p_curr_umbra_pin->umbra_vertex) >
1281 pin.path_vertex.GetDistanceSquared(p_next_umbra_pin->umbra_vertex))) {
1282 // We always bump to the next vertex when it was generated from this
1283 // pin, and also when it is closer to this path_vertex than the last
1284 // matched pin (curr).
1285 p_curr_umbra_pin = p_next_umbra_pin;
1286 p_next_umbra_pin = p_next_umbra_pin->p_next;
1287
1288 // New umbra vertex - append it and remember its index.
1289 uint16_t new_umbra_index =
1290 AppendVertex(p_curr_umbra_pin->umbra_vertex, umbra_gaussian_);
1291 p_curr_umbra_pin->umbra_index = new_umbra_index;
1292 if (last_umbra_index != 0u) {
1293 AddTriangle(0u, last_umbra_index, new_umbra_index);
1294 }
1295 last_umbra_index = new_umbra_index;
1296 }
1297 if (p_curr_umbra_pin != &pin) {
1298 pin.umbra_vertex = p_curr_umbra_pin->umbra_vertex;
1299 pin.umbra_index = last_umbra_index;
1300 }
1301 FML_DCHECK(pin.umbra_index != 0u);
1302 }
1303 if (last_umbra_index != pins.front().umbra_index) {
1304 AddTriangle(0u, last_umbra_index, pins.front().umbra_index);
1305 }
1306 }
1307
1308 // Appends a fan based on center from the relative point in start_delta to
1309 // the relative point in end_delta, potentially adding additional relative
1310 // vectors if the turning rate is faster than the trig values in trigs_.
1311 uint16_t PolygonInfo::AppendFan(const UmbraPin* p_curr_pin,
1312 const Vector2& start,
1313 const Vector2& end,
1314 uint16_t start_index,
1315 const impeller::Tessellator::Trigs& trigs,
1316 Scalar direction) {
1317 Point center = p_curr_pin->path_vertex;
1318 uint16_t center_index = p_curr_pin->umbra_index;
1319 uint16_t prev_index = start_index;
1320
1321 Vector2 start_delta = start - center;
1322 Vector2 end_delta = end - center;
1323 size_t trig_count = trigs.size();
1324 for (size_t i = 1u; i < trig_count; i++) {
1325 Trig trig = trigs[i];
1326 Point fan_delta = (direction >= 0 ? trig : -trig) * start_delta;
1327 if (fan_delta.Cross(end_delta) * direction <= 0) {
1328 break;
1329 }
1330 uint16_t cur_index = AppendVertex(center + fan_delta, 0.0f);
1331 if (prev_index != cur_index) {
1332 AddTriangle(center_index, prev_index, cur_index);
1333 prev_index = cur_index;
1334 }
1335 if (i == trig_count - 1) {
1336 // This corner was >90 degrees so we start the loop over in case there
1337 // are more intermediate angles to emit.
1338 //
1339 // We set the loop variable to 0u which looks like it might apply a
1340 // 0 rotation to the new start_delta, but the for loop is about to
1341 // auto-incrment the variable to 1u, which will start at the next
1342 // non-0 rotation angle.
1343 i = 0u;
1344 start_delta = fan_delta;
1345 }
1346 }
1347 uint16_t cur_index = AppendVertex(center + end_delta, 0.0f);
1348 if (prev_index != cur_index) {
1349 AddTriangle(center_index, prev_index, cur_index);
1350 }
1351 return cur_index;
1352 }
1353
1354 // Appends a vertex and gaussian value into the associated std::vectors
1355 // and returns the index at which the point was inserted.
1356 uint16_t PolygonInfo::AppendVertex(const Point& vertex, Scalar gaussian) {
1357 FML_DCHECK(gaussian >= 0.0f && gaussian <= 1.0f);
1358 uint16_t index = vertices_.size();
1359 FML_DCHECK(index == gaussians_.size());
1360 // TODO(jimgraham): Turn this condition into a failure of the tessellation
1361 FML_DCHECK(index <= std::numeric_limits<uint16_t>::max());
1362 if (index > 0u) {
1363 FML_DCHECK(!gaussians_.empty() && !vertices_.empty());
1364 if (gaussian == gaussians_.back() && vertex == vertices_.back()) {
1365 return index - 1;
1366 }
1367 }
1368 vertices_.push_back(vertex);
1369 gaussians_.push_back(gaussian);
1370 return index;
1371 }
1372
1373 // Appends a triangle of the 3 indices into the indices_ vector.
1374 void PolygonInfo::AddTriangle(uint16_t v0, uint16_t v1, uint16_t v2) {
1375 FML_DCHECK(std::max(std::max(v0, v1), v2) < vertices_.size());
1376 indices_.push_back(v0);
1377 indices_.push_back(v1);
1378 indices_.push_back(v2);
1379 }
1380
1381 } // namespace
1382
1383 namespace impeller {
1384
1385 const std::shared_ptr<ShadowVertices> ShadowVertices::kEmpty =
1386 std::make_shared<ShadowVertices>();
1387
1388 std::optional<Rect> ShadowVertices::GetBounds() const {
1389 return Rect::MakePointBounds(vertices_);
1390 }
1391
1392 ShadowPathGeometry::ShadowPathGeometry(Tessellator& tessellator,
1393 const Matrix& matrix,
1394 const PathSource& source,
1395 Scalar occluder_height)
1396 : shadow_vertices_(MakeAmbientShadowVertices(tessellator,
1397 source,
1398 occluder_height,
1399 matrix)) {}
1400
1401 bool ShadowPathGeometry::CanRender() const {
1402 return shadow_vertices_ != nullptr;
1403 }
1404
1405 bool ShadowPathGeometry::IsEmpty() const {
1406 return shadow_vertices_ != nullptr && shadow_vertices_->IsEmpty();
1407 }
1408
1409 const std::shared_ptr<ShadowVertices>& ShadowPathGeometry::GetShadowVertices()
1410 const {
1411 return shadow_vertices_;
1412 }
1413
1414 const std::shared_ptr<ShadowVertices> ShadowPathGeometry::TakeShadowVertices() {
1415 return std::move(shadow_vertices_);
1416 }
1417
1418 GeometryResult ShadowVertices::GetPositionBuffer(const ContentContext& renderer,
1419 const Entity& entity,
1420 RenderPass& pass) const {
1421 using VS = ShadowVerticesVertexShader;
1422
1423 size_t vertex_count = GetVertexCount();
1424
1425 BufferView vertex_buffer = renderer.GetTransientsDataBuffer().Emplace(
1426 vertex_count * sizeof(VS::PerVertexData), alignof(VS::PerVertexData),
1427 [&](uint8_t* data) {
1428 VS::PerVertexData* vtx_contents =
1429 reinterpret_cast<VS::PerVertexData*>(data);
1430 for (size_t i = 0u; i < vertex_count; i++) {
1431 vtx_contents[i] = {
1432 .position = vertices_[i],
1433 .gaussian = gaussians_[i],
1434 };
1435 }
1436 });
1437
1438 size_t index_count = GetIndexCount();
1439 const uint16_t* indices_data = GetIndices().data();
1440 BufferView index_buffer = {};
1441 index_buffer = renderer.GetTransientsIndexesBuffer().Emplace(
1442 indices_data, index_count * sizeof(uint16_t), alignof(uint16_t));
1443
1444 return GeometryResult{
1445 .type = PrimitiveType::kTriangle,
1446 .vertex_buffer =
1447 {
1448 .vertex_buffer = vertex_buffer,
1449 .index_buffer = index_buffer,
1450 .vertex_count = index_count,
1451 .index_type = IndexType::k16bit,
1452 },
1453 .transform = entity.GetShaderTransform(pass),
1454 };
1455 }
1456
1457 std::shared_ptr<ShadowVertices> ShadowPathGeometry::MakeAmbientShadowVertices(
1458 Tessellator& tessellator,
1459 const PathSource& source,
1460 Scalar occluder_height,
1461 const Matrix& matrix) {
1462 Scalar trig_radius = PolygonInfo::GetTrigRadiusForHeight(occluder_height);
1463 Tessellator::Trigs trigs = tessellator.GetTrigsForDeviceRadius(trig_radius);
1464
1465 PolygonInfo polygon(occluder_height);
1466
1467 return polygon.CalculateConvexShadowMesh(source, matrix, trigs);
1468 }
1469
1470 } // namespace impeller
impeller::ContentContext
Definition: content_context.h:122
impeller::ContentContext::GetTransientsIndexesBuffer
HostBuffer & GetTransientsIndexesBuffer() const
Retrieve the current host buffer for transient storage of indexes used for indexed draws.
Definition: content_context.h:290
impeller::ContentContext::GetTransientsDataBuffer
HostBuffer & GetTransientsDataBuffer() const
Retrieve the current host buffer for transient storage of other non-index data.
Definition: content_context.h:299
impeller::Entity
Definition: entity.h:26
impeller::Entity::GetShaderTransform
Matrix GetShaderTransform(const RenderPass &pass) const
Definition: entity.cc:50
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:92
impeller::PathSource
Definition: path_source.h:55
impeller::PathTessellator
Definition: path_tessellator.h:17
impeller::PathTessellator::CountFillStorage
static std::pair< size_t, size_t > CountFillStorage(const PathSource &source, Scalar scale)
Definition: path_tessellator.cc:298
impeller::RenderPass
Render passes encode render commands directed as one specific render target into an underlying comman...
Definition: render_pass.h:30
impeller::ShadowPathGeometry::GetShadowVertices
const std::shared_ptr< ShadowVertices > & GetShadowVertices() const
Definition: shadow_path_geometry.cc:1409
impeller::ShadowPathGeometry::ShadowPathGeometry
ShadowPathGeometry(Tessellator &tessellator, const Matrix &matrix, const PathSource &source, Scalar occluder_height)
Definition: shadow_path_geometry.cc:1392
impeller::ShadowPathGeometry::CanRender
bool CanRender() const
Definition: shadow_path_geometry.cc:1401
impeller::ShadowPathGeometry::IsEmpty
bool IsEmpty() const
Returns true if this shadow has no effect, is not visible.
Definition: shadow_path_geometry.cc:1405
impeller::ShadowPathGeometry::TakeShadowVertices
const std::shared_ptr< ShadowVertices > TakeShadowVertices()
Definition: shadow_path_geometry.cc:1414
impeller::ShadowPathGeometry::MakeAmbientShadowVertices
static std::shared_ptr< ShadowVertices > MakeAmbientShadowVertices(Tessellator &tessellator, const PathSource &source, Scalar occluder_height, const Matrix &matrix)
Definition: shadow_path_geometry.cc:1457
impeller::ShadowVertices
Definition: shadow_path_geometry.h:24
impeller::ShadowVertices::GetVertexCount
size_t GetVertexCount() const
Definition: shadow_path_geometry.h:47
impeller::ShadowVertices::GetIndices
const std::vector< uint16_t > & GetIndices() const
Definition: shadow_path_geometry.h:53
impeller::ShadowVertices::GetBounds
std::optional< Rect > GetBounds() const
Definition: shadow_path_geometry.cc:1388
impeller::ShadowVertices::kEmpty
static const std::shared_ptr< ShadowVertices > kEmpty
Definition: shadow_path_geometry.h:26
impeller::ShadowVertices::GetPositionBuffer
GeometryResult GetPositionBuffer(const ContentContext &renderer, const Entity &entity, RenderPass &pass) const
Definition: shadow_path_geometry.cc:1418
impeller::ShadowVertices::GetIndexCount
size_t GetIndexCount() const
The count of the indices that define the mesh.
Definition: shadow_path_geometry.h:50
impeller::Tessellator::Trigs
Definition: tessellator.h:48
impeller::Tessellator::Trigs::size
size_t size() const
Definition: tessellator.h:53
impeller::Tessellator
A utility that generates triangles of the specified fill type given a polyline. This happens on the C...
Definition: tessellator.h:37
impeller::Tessellator::GetTrigsForDeviceRadius
Trigs GetTrigsForDeviceRadius(Scalar pixel_radius)
Definition: tessellator.cc:425
impeller
Definition: allocation.cc:12
impeller::PrimitiveType::kTriangle
@ kTriangle
impeller::Vector2
Point Vector2
Definition: point.h:429
impeller::Scalar
float Scalar
Definition: scalar.h:19
impeller::IndexType::k16bit
@ k16bit
impeller::kEhCloseEnough
constexpr float kEhCloseEnough
Definition: constants.h:57
impeller::ScalarNearlyZero
constexpr bool ScalarNearlyZero(Scalar x, Scalar tolerance=kEhCloseEnough)
Definition: scalar.h:31
impeller::Point
TPoint< Scalar > Point
Definition: point.h:425
impeller::Convexity::kConvex
@ kConvex
impeller::VS
LinePipeline::VertexShader VS
Definition: line_contents.cc:13
path_source.h
path_tessellator.h
pipelines.h
shadow_path_geometry.h
impeller::BufferView
Definition: buffer_view.h:19
impeller::GeometryResult
Definition: geometry.h:21
impeller::GeometryResult::type
PrimitiveType type
Definition: geometry.h:37
impeller::Matrix
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
impeller::TPoint::Round
static constexpr TPoint Round(const TPoint< U > &other)
Definition: point.h:50
impeller::TPoint::Normalize
constexpr TPoint Normalize() const
Definition: point.h:285
impeller::TPoint::PerpendicularRight
constexpr TPoint PerpendicularRight() const
Definition: point.h:323
impeller::TRect< Scalar >::MakePointBounds
constexpr static std::optional< TRect > MakePointBounds(const U &value)
Definition: rect.h:165
impeller::Trig
A structure to store the sine and cosine of an angle.
Definition: trig.h:16
start
const size_t start
Definition: tessellator_libtess.cc:62
end
const size_t end
Definition: tessellator_libtess.cc:63
data
std::shared_ptr< const fml::Mapping > data
Definition: texture_gles.cc:69