1/*
2 * Copyright 2019 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "src/gpu/geometry/GrQuadUtils.h"
9
10#include "include/core/SkRect.h"
11#include "include/private/GrTypesPriv.h"
12#include "include/private/SkVx.h"
13#include "src/core/SkPathPriv.h"
14#include "src/gpu/geometry/GrQuad.h"
15
16using V4f = skvx::Vec<4, float>;
17using M4f = skvx::Vec<4, int32_t>;
18
19#define AI SK_ALWAYS_INLINE
20
21// General tolerance used for denominators, checking div-by-0
22static constexpr float kTolerance = 1e-9f;
23// Increased slop when comparing signed distances / lengths
24static constexpr float kDistTolerance = 1e-2f;
25static constexpr float kDist2Tolerance = kDistTolerance * kDistTolerance;
26static constexpr float kInvDistTolerance = 1.f / kDistTolerance;
27
28// These rotate the points/edge values either clockwise or counterclockwise assuming tri strip
29// order.
30static AI V4f next_cw(const V4f& v) {
31 return skvx::shuffle<2, 0, 3, 1>(v);
32}
33
34static AI V4f next_ccw(const V4f& v) {
35 return skvx::shuffle<1, 3, 0, 2>(v);
36}
37
38static AI V4f next_diag(const V4f& v) {
39 // Same as next_ccw(next_ccw(v)), or next_cw(next_cw(v)), e.g. two rotations either direction.
40 return skvx::shuffle<3, 2, 1, 0>(v);
41}
42
43// Replaces zero-length 'bad' edge vectors with the reversed opposite edge vector.
44// e3 may be null if only 2D edges need to be corrected for.
45static AI void correct_bad_edges(const M4f& bad, V4f* e1, V4f* e2, V4f* e3) {
46 if (any(bad)) {
47 // Want opposite edges, L B T R -> R T B L but with flipped sign to preserve winding
48 *e1 = if_then_else(bad, -next_diag(*e1), *e1);
49 *e2 = if_then_else(bad, -next_diag(*e2), *e2);
50 if (e3) {
51 *e3 = if_then_else(bad, -next_diag(*e3), *e3);
52 }
53 }
54}
55
56// Replace 'bad' coordinates by rotating CCW to get the next point. c3 may be null for 2D points.
57static AI void correct_bad_coords(const M4f& bad, V4f* c1, V4f* c2, V4f* c3) {
58 if (any(bad)) {
59 *c1 = if_then_else(bad, next_ccw(*c1), *c1);
60 *c2 = if_then_else(bad, next_ccw(*c2), *c2);
61 if (c3) {
62 *c3 = if_then_else(bad, next_ccw(*c3), *c3);
63 }
64 }
65}
66
67// Since the local quad may not be type kRect, this uses the opposites for each vertex when
68// interpolating, and calculates new ws in addition to new xs, ys.
69static void interpolate_local(float alpha, int v0, int v1, int v2, int v3,
70 float lx[4], float ly[4], float lw[4]) {
71 SkASSERT(v0 >= 0 && v0 < 4);
72 SkASSERT(v1 >= 0 && v1 < 4);
73 SkASSERT(v2 >= 0 && v2 < 4);
74 SkASSERT(v3 >= 0 && v3 < 4);
75
76 float beta = 1.f - alpha;
77 lx[v0] = alpha * lx[v0] + beta * lx[v2];
78 ly[v0] = alpha * ly[v0] + beta * ly[v2];
79 lw[v0] = alpha * lw[v0] + beta * lw[v2];
80
81 lx[v1] = alpha * lx[v1] + beta * lx[v3];
82 ly[v1] = alpha * ly[v1] + beta * ly[v3];
83 lw[v1] = alpha * lw[v1] + beta * lw[v3];
84}
85
86// Crops v0 to v1 based on the clipDevRect. v2 is opposite of v0, v3 is opposite of v1.
87// It is written to not modify coordinates if there's no intersection along the edge.
88// Ideally this would have been detected earlier and the entire draw is skipped.
89static bool crop_rect_edge(const SkRect& clipDevRect, int v0, int v1, int v2, int v3,
90 float x[4], float y[4], float lx[4], float ly[4], float lw[4]) {
91 SkASSERT(v0 >= 0 && v0 < 4);
92 SkASSERT(v1 >= 0 && v1 < 4);
93 SkASSERT(v2 >= 0 && v2 < 4);
94 SkASSERT(v3 >= 0 && v3 < 4);
95
96 if (SkScalarNearlyEqual(x[v0], x[v1])) {
97 // A vertical edge
98 if (x[v0] < clipDevRect.fLeft && x[v2] >= clipDevRect.fLeft) {
99 // Overlapping with left edge of clipDevRect
100 if (lx) {
101 float alpha = (x[v2] - clipDevRect.fLeft) / (x[v2] - x[v0]);
102 interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw);
103 }
104 x[v0] = clipDevRect.fLeft;
105 x[v1] = clipDevRect.fLeft;
106 return true;
107 } else if (x[v0] > clipDevRect.fRight && x[v2] <= clipDevRect.fRight) {
108 // Overlapping with right edge of clipDevRect
109 if (lx) {
110 float alpha = (clipDevRect.fRight - x[v2]) / (x[v0] - x[v2]);
111 interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw);
112 }
113 x[v0] = clipDevRect.fRight;
114 x[v1] = clipDevRect.fRight;
115 return true;
116 }
117 } else {
118 // A horizontal edge
119 SkASSERT(SkScalarNearlyEqual(y[v0], y[v1]));
120 if (y[v0] < clipDevRect.fTop && y[v2] >= clipDevRect.fTop) {
121 // Overlapping with top edge of clipDevRect
122 if (lx) {
123 float alpha = (y[v2] - clipDevRect.fTop) / (y[v2] - y[v0]);
124 interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw);
125 }
126 y[v0] = clipDevRect.fTop;
127 y[v1] = clipDevRect.fTop;
128 return true;
129 } else if (y[v0] > clipDevRect.fBottom && y[v2] <= clipDevRect.fBottom) {
130 // Overlapping with bottom edge of clipDevRect
131 if (lx) {
132 float alpha = (clipDevRect.fBottom - y[v2]) / (y[v0] - y[v2]);
133 interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw);
134 }
135 y[v0] = clipDevRect.fBottom;
136 y[v1] = clipDevRect.fBottom;
137 return true;
138 }
139 }
140
141 // No overlap so don't crop it
142 return false;
143}
144
145// Updates x and y to intersect with clipDevRect. lx, ly, and lw are updated appropriately and may
146// be null to skip calculations. Returns bit mask of edges that were clipped.
147static GrQuadAAFlags crop_rect(const SkRect& clipDevRect, float x[4], float y[4],
148 float lx[4], float ly[4], float lw[4]) {
149 GrQuadAAFlags clipEdgeFlags = GrQuadAAFlags::kNone;
150
151 // The quad's left edge may not align with the SkRect notion of left due to 90 degree rotations
152 // or mirrors. So, this processes the logical edges of the quad and clamps it to the 4 sides of
153 // clipDevRect.
154
155 // Quad's left is v0 to v1 (op. v2 and v3)
156 if (crop_rect_edge(clipDevRect, 0, 1, 2, 3, x, y, lx, ly, lw)) {
157 clipEdgeFlags |= GrQuadAAFlags::kLeft;
158 }
159 // Quad's top edge is v0 to v2 (op. v1 and v3)
160 if (crop_rect_edge(clipDevRect, 0, 2, 1, 3, x, y, lx, ly, lw)) {
161 clipEdgeFlags |= GrQuadAAFlags::kTop;
162 }
163 // Quad's right edge is v2 to v3 (op. v0 and v1)
164 if (crop_rect_edge(clipDevRect, 2, 3, 0, 1, x, y, lx, ly, lw)) {
165 clipEdgeFlags |= GrQuadAAFlags::kRight;
166 }
167 // Quad's bottom edge is v1 to v3 (op. v0 and v2)
168 if (crop_rect_edge(clipDevRect, 1, 3, 0, 2, x, y, lx, ly, lw)) {
169 clipEdgeFlags |= GrQuadAAFlags::kBottom;
170 }
171
172 return clipEdgeFlags;
173}
174
175// Similar to crop_rect, but assumes that both the device coordinates and optional local coordinates
176// geometrically match the TL, BL, TR, BR vertex ordering, i.e. axis-aligned but not flipped, etc.
177static GrQuadAAFlags crop_simple_rect(const SkRect& clipDevRect, float x[4], float y[4],
178 float lx[4], float ly[4]) {
179 GrQuadAAFlags clipEdgeFlags = GrQuadAAFlags::kNone;
180
181 // Update local coordinates proportionately to how much the device rect edge was clipped
182 const SkScalar dx = lx ? (lx[2] - lx[0]) / (x[2] - x[0]) : 0.f;
183 const SkScalar dy = ly ? (ly[1] - ly[0]) / (y[1] - y[0]) : 0.f;
184 if (clipDevRect.fLeft > x[0]) {
185 if (lx) {
186 lx[0] += (clipDevRect.fLeft - x[0]) * dx;
187 lx[1] = lx[0];
188 }
189 x[0] = clipDevRect.fLeft;
190 x[1] = clipDevRect.fLeft;
191 clipEdgeFlags |= GrQuadAAFlags::kLeft;
192 }
193 if (clipDevRect.fTop > y[0]) {
194 if (ly) {
195 ly[0] += (clipDevRect.fTop - y[0]) * dy;
196 ly[2] = ly[0];
197 }
198 y[0] = clipDevRect.fTop;
199 y[2] = clipDevRect.fTop;
200 clipEdgeFlags |= GrQuadAAFlags::kTop;
201 }
202 if (clipDevRect.fRight < x[2]) {
203 if (lx) {
204 lx[2] -= (x[2] - clipDevRect.fRight) * dx;
205 lx[3] = lx[2];
206 }
207 x[2] = clipDevRect.fRight;
208 x[3] = clipDevRect.fRight;
209 clipEdgeFlags |= GrQuadAAFlags::kRight;
210 }
211 if (clipDevRect.fBottom < y[1]) {
212 if (ly) {
213 ly[1] -= (y[1] - clipDevRect.fBottom) * dy;
214 ly[3] = ly[1];
215 }
216 y[1] = clipDevRect.fBottom;
217 y[3] = clipDevRect.fBottom;
218 clipEdgeFlags |= GrQuadAAFlags::kBottom;
219 }
220
221 return clipEdgeFlags;
222}
223// Consistent with GrQuad::asRect()'s return value but requires fewer operations since we don't need
224// to calculate the bounds of the quad.
225static bool is_simple_rect(const GrQuad& quad) {
226 if (quad.quadType() != GrQuad::Type::kAxisAligned) {
227 return false;
228 }
229 // v0 at the geometric top-left is unique, so we only need to compare x[0] < x[2] for left
230 // and y[0] < y[1] for top, but add a little padding to protect against numerical precision
231 // on R90 and R270 transforms tricking this check.
232 return ((quad.x(0) + SK_ScalarNearlyZero) < quad.x(2)) &&
233 ((quad.y(0) + SK_ScalarNearlyZero) < quad.y(1));
234}
235
236// Calculates barycentric coordinates for each point in (testX, testY) in the triangle formed by
237// (x0,y0) - (x1,y1) - (x2, y2) and stores them in u, v, w.
238static bool barycentric_coords(float x0, float y0, float x1, float y1, float x2, float y2,
239 const V4f& testX, const V4f& testY,
240 V4f* u, V4f* v, V4f* w) {
241 // The 32-bit calculations can have catastrophic cancellation if the device-space coordinates
242 // are really big, and this code needs to handle that because we evaluate barycentric coords
243 // pre-cropping to the render target bounds. This preserves some precision by shrinking the
244 // coordinate space if the bounds are large.
245 static constexpr float kCoordLimit = 1e7f; // Big but somewhat arbitrary, fixes crbug:10141204
246 float scaleX = std::max(std::max(x0, x1), x2) - std::min(std::min(x0, x1), x2);
247 float scaleY = std::max(std::max(y0, y1), y2) - std::min(std::min(y0, y1), y2);
248 if (scaleX > kCoordLimit) {
249 scaleX = kCoordLimit / scaleX;
250 x0 *= scaleX;
251 x1 *= scaleX;
252 x2 *= scaleX;
253 } else {
254 // Don't scale anything
255 scaleX = 1.f;
256 }
257 if (scaleY > kCoordLimit) {
258 scaleY = kCoordLimit / scaleY;
259 y0 *= scaleY;
260 y1 *= scaleY;
261 y2 *= scaleY;
262 } else {
263 scaleY = 1.f;
264 }
265
266 // Modeled after SkPathOpsQuad::pointInTriangle() but uses float instead of double, is
267 // vectorized and outputs normalized barycentric coordinates instead of inside/outside test
268 float v0x = x2 - x0;
269 float v0y = y2 - y0;
270 float v1x = x1 - x0;
271 float v1y = y1 - y0;
272
273 float dot00 = v0x * v0x + v0y * v0y;
274 float dot01 = v0x * v1x + v0y * v1y;
275 float dot11 = v1x * v1x + v1y * v1y;
276
277 // Not yet 1/d, first check d != 0 with a healthy tolerance (worst case is we end up not
278 // cropping something we could have, which is better than cropping something we shouldn't have).
279 // The tolerance is partly so large because these comparisons operate in device px^4 units,
280 // with plenty of subtractions thrown in. The SkPathOpsQuad code's use of doubles helped, and
281 // because it only needed to return "inside triangle", it could compare against [0, denom] and
282 // skip the normalization entirely.
283 float invDenom = dot00 * dot11 - dot01 * dot01;
284 static constexpr SkScalar kEmptyTriTolerance = SK_Scalar1 / (1 << 5);
285 if (SkScalarNearlyZero(invDenom, kEmptyTriTolerance)) {
286 // The triangle was degenerate/empty, which can cause the following UVW calculations to
287 // return (0,0,1) for every test point. This in turn makes the cropping code think that the
288 // empty triangle contains the crop rect and we turn the draw into a fullscreen clear, which
289 // is definitely the utter opposite of what we'd expect for an empty shape.
290 return false;
291 } else {
292 // Safe to divide
293 invDenom = sk_ieee_float_divide(1.f, invDenom);
294 }
295
296 V4f v2x = (scaleX * testX) - x0;
297 V4f v2y = (scaleY * testY) - y0;
298
299 V4f dot02 = v0x * v2x + v0y * v2y;
300 V4f dot12 = v1x * v2x + v1y * v2y;
301
302 // These are relative to the vertices, so there's no need to undo the scale factor
303 *u = (dot11 * dot02 - dot01 * dot12) * invDenom;
304 *v = (dot00 * dot12 - dot01 * dot02) * invDenom;
305 *w = 1.f - *u - *v;
306
307 return true;
308}
309
310static M4f inside_triangle(const V4f& u, const V4f& v, const V4f& w) {
311 return ((u >= 0.f) & (u <= 1.f)) & ((v >= 0.f) & (v <= 1.f)) & ((w >= 0.f) & (w <= 1.f));
312}
313
314///////////////////////////////////////////////////////////////////////////////////////////////////
315
316SkRect GrQuad::projectedBounds() const {
317 V4f xs = this->x4f();
318 V4f ys = this->y4f();
319 V4f ws = this->w4f();
320 M4f clipW = ws < SkPathPriv::kW0PlaneDistance;
321 if (any(clipW)) {
322 V4f x2d = xs / ws;
323 V4f y2d = ys / ws;
324 // Bounds of just the projected points in front of w = epsilon
325 SkRect frontBounds = {
326 min(if_then_else(clipW, V4f(SK_ScalarInfinity), x2d)),
327 min(if_then_else(clipW, V4f(SK_ScalarInfinity), y2d)),
328 max(if_then_else(clipW, V4f(SK_ScalarNegativeInfinity), x2d)),
329 max(if_then_else(clipW, V4f(SK_ScalarNegativeInfinity), y2d))
330 };
331 // Calculate clipped coordinates by following CCW edges, only keeping points where the w
332 // actually changes sign between the vertices.
333 V4f t = (SkPathPriv::kW0PlaneDistance - ws) / (next_ccw(ws) - ws);
334 x2d = (t * next_ccw(xs) + (1.f - t) * xs) / SkPathPriv::kW0PlaneDistance;
335 y2d = (t * next_ccw(ys) + (1.f - t) * ys) / SkPathPriv::kW0PlaneDistance;
336 // True if (w < e) xor (ccw(w) < e), i.e. crosses the w = epsilon plane
337 clipW = clipW ^ (next_ccw(ws) < SkPathPriv::kW0PlaneDistance);
338 return {
339 min(if_then_else(clipW, x2d, V4f(frontBounds.fLeft))),
340 min(if_then_else(clipW, y2d, V4f(frontBounds.fTop))),
341 max(if_then_else(clipW, x2d, V4f(frontBounds.fRight))),
342 max(if_then_else(clipW, y2d, V4f(frontBounds.fBottom)))
343 };
344 } else {
345 // Nothing is behind the viewer, so the projection is straight forward and valid
346 ws = 1.f / ws;
347 V4f x2d = xs * ws;
348 V4f y2d = ys * ws;
349 return {min(x2d), min(y2d), max(x2d), max(y2d)};
350 }
351}
352
353///////////////////////////////////////////////////////////////////////////////////////////////////
354
355namespace GrQuadUtils {
356
357void ResolveAAType(GrAAType requestedAAType, GrQuadAAFlags requestedEdgeFlags, const GrQuad& quad,
358 GrAAType* outAAType, GrQuadAAFlags* outEdgeFlags) {
359 // Most cases will keep the requested types unchanged
360 *outAAType = requestedAAType;
361 *outEdgeFlags = requestedEdgeFlags;
362
363 switch (requestedAAType) {
364 // When aa type is coverage, disable AA if the edge configuration doesn't actually need it
365 case GrAAType::kCoverage:
366 if (requestedEdgeFlags == GrQuadAAFlags::kNone) {
367 // Turn off anti-aliasing
368 *outAAType = GrAAType::kNone;
369 } else {
370 // For coverage AA, if the quad is a rect and it lines up with pixel boundaries
371 // then overall aa and per-edge aa can be completely disabled
372 if (quad.quadType() == GrQuad::Type::kAxisAligned && !quad.aaHasEffectOnRect()) {
373 *outAAType = GrAAType::kNone;
374 *outEdgeFlags = GrQuadAAFlags::kNone;
375 }
376 }
377 break;
378 // For no or msaa anti aliasing, override the edge flags since edge flags only make sense
379 // when coverage aa is being used.
380 case GrAAType::kNone:
381 *outEdgeFlags = GrQuadAAFlags::kNone;
382 break;
383 case GrAAType::kMSAA:
384 *outEdgeFlags = GrQuadAAFlags::kAll;
385 break;
386 }
387}
388
389int ClipToW0(DrawQuad* quad, DrawQuad* extraVertices) {
390 using Vertices = TessellationHelper::Vertices;
391
392 SkASSERT(quad && extraVertices);
393
394 if (quad->fDevice.quadType() < GrQuad::Type::kPerspective) {
395 // W implicitly 1s for each vertex, so nothing to do but draw unmodified 'quad'
396 return 1;
397 }
398
399 M4f validW = quad->fDevice.w4f() >= SkPathPriv::kW0PlaneDistance;
400 if (all(validW)) {
401 // Nothing to clip, can proceed normally drawing just 'quad'
402 return 1;
403 } else if (!any(validW)) {
404 // Everything is clipped, so draw nothing
405 return 0;
406 }
407
408 // The clipped local coordinates will most likely not remain rectilinear
409 GrQuad::Type localType = quad->fLocal.quadType();
410 if (localType < GrQuad::Type::kGeneral) {
411 localType = GrQuad::Type::kGeneral;
412 }
413
414 // If we got here, there are 1, 2, or 3 points behind the w = 0 plane. If 2 or 3 points are
415 // clipped we can define a new quad that covers the clipped shape directly. If there's 1 clipped
416 // out, the new geometry is a pentagon.
417 Vertices v;
418 v.reset(quad->fDevice, &quad->fLocal);
419
420 int clipCount = (validW[0] ? 0 : 1) + (validW[1] ? 0 : 1) +
421 (validW[2] ? 0 : 1) + (validW[3] ? 0 : 1);
422 SkASSERT(clipCount >= 1 && clipCount <= 3);
423
424 // FIXME de-duplicate from the projectedBounds() calculations.
425 V4f t = (SkPathPriv::kW0PlaneDistance - v.fW) / (next_ccw(v.fW) - v.fW);
426
427 Vertices clip;
428 clip.fX = (t * next_ccw(v.fX) + (1.f - t) * v.fX);
429 clip.fY = (t * next_ccw(v.fY) + (1.f - t) * v.fY);
430 clip.fW = SkPathPriv::kW0PlaneDistance;
431
432 clip.fU = (t * next_ccw(v.fU) + (1.f - t) * v.fU);
433 clip.fV = (t * next_ccw(v.fV) + (1.f - t) * v.fV);
434 clip.fR = (t * next_ccw(v.fR) + (1.f - t) * v.fR);
435
436 M4f ccwValid = next_ccw(v.fW) >= SkPathPriv::kW0PlaneDistance;
437 M4f cwValid = next_cw(v.fW) >= SkPathPriv::kW0PlaneDistance;
438
439 if (clipCount != 1) {
440 // Simplest case, replace behind-w0 points with their clipped points by following CCW edge
441 // or CW edge, depending on if the edge crosses from neg. to pos. w or pos. to neg.
442 SkASSERT(clipCount == 2 || clipCount == 3);
443
444 // NOTE: when 3 vertices are clipped, this results in a degenerate quad where one vertex
445 // is replicated. This is preferably to inserting a 3rd vertex on the w = 0 intersection
446 // line because two parallel edges make inset/outset math unstable for large quads.
447 v.fX = if_then_else(validW, v.fX,
448 if_then_else((!ccwValid) & (!cwValid), next_ccw(clip.fX),
449 if_then_else(ccwValid, clip.fX, /* cwValid */ next_cw(clip.fX))));
450 v.fY = if_then_else(validW, v.fY,
451 if_then_else((!ccwValid) & (!cwValid), next_ccw(clip.fY),
452 if_then_else(ccwValid, clip.fY, /* cwValid */ next_cw(clip.fY))));
453 v.fW = if_then_else(validW, v.fW, clip.fW);
454
455 v.fU = if_then_else(validW, v.fU,
456 if_then_else((!ccwValid) & (!cwValid), next_ccw(clip.fU),
457 if_then_else(ccwValid, clip.fU, /* cwValid */ next_cw(clip.fU))));
458 v.fV = if_then_else(validW, v.fV,
459 if_then_else((!ccwValid) & (!cwValid), next_ccw(clip.fV),
460 if_then_else(ccwValid, clip.fV, /* cwValid */ next_cw(clip.fV))));
461 v.fR = if_then_else(validW, v.fR,
462 if_then_else((!ccwValid) & (!cwValid), next_ccw(clip.fR),
463 if_then_else(ccwValid, clip.fR, /* cwValid */ next_cw(clip.fR))));
464
465 // For 2 or 3 clipped vertices, the resulting shape is a quad or a triangle, so it can be
466 // entirely represented in 'quad'.
467 v.asGrQuads(&quad->fDevice, GrQuad::Type::kPerspective,
468 &quad->fLocal, localType);
469 return 1;
470 } else {
471 // The clipped geometry is a pentagon, so it will be represented as two quads connected by
472 // a new non-AA edge. Use the midpoint along one of the unclipped edges as a split vertex.
473 Vertices mid;
474 mid.fX = 0.5f * (v.fX + next_ccw(v.fX));
475 mid.fY = 0.5f * (v.fY + next_ccw(v.fY));
476 mid.fW = 0.5f * (v.fW + next_ccw(v.fW));
477
478 mid.fU = 0.5f * (v.fU + next_ccw(v.fU));
479 mid.fV = 0.5f * (v.fV + next_ccw(v.fV));
480 mid.fR = 0.5f * (v.fR + next_ccw(v.fR));
481
482 // Make a quad formed by the 2 clipped points, the inserted mid point, and the good vertex
483 // that is CCW rotated from the clipped vertex.
484 Vertices v2;
485 v2.fUVRCount = v.fUVRCount;
486 v2.fX = if_then_else((!validW) | (!ccwValid), clip.fX,
487 if_then_else(cwValid, next_cw(mid.fX), v.fX));
488 v2.fY = if_then_else((!validW) | (!ccwValid), clip.fY,
489 if_then_else(cwValid, next_cw(mid.fY), v.fY));
490 v2.fW = if_then_else((!validW) | (!ccwValid), clip.fW,
491 if_then_else(cwValid, next_cw(mid.fW), v.fW));
492
493 v2.fU = if_then_else((!validW) | (!ccwValid), clip.fU,
494 if_then_else(cwValid, next_cw(mid.fU), v.fU));
495 v2.fV = if_then_else((!validW) | (!ccwValid), clip.fV,
496 if_then_else(cwValid, next_cw(mid.fV), v.fV));
497 v2.fR = if_then_else((!validW) | (!ccwValid), clip.fR,
498 if_then_else(cwValid, next_cw(mid.fR), v.fR));
499 // The non-AA edge for this quad is the opposite of the clipped vertex's edge
500 GrQuadAAFlags v2EdgeFlag = (!validW[0] ? GrQuadAAFlags::kRight : // left clipped -> right
501 (!validW[1] ? GrQuadAAFlags::kTop : // bottom clipped -> top
502 (!validW[2] ? GrQuadAAFlags::kBottom : // top clipped -> bottom
503 GrQuadAAFlags::kLeft))); // right clipped -> left
504 extraVertices->fEdgeFlags = quad->fEdgeFlags & ~v2EdgeFlag;
505
506 // Make a quad formed by the remaining two good vertices, one clipped point, and the
507 // inserted mid point.
508 v.fX = if_then_else(!validW, next_cw(clip.fX),
509 if_then_else(!cwValid, mid.fX, v.fX));
510 v.fY = if_then_else(!validW, next_cw(clip.fY),
511 if_then_else(!cwValid, mid.fY, v.fY));
512 v.fW = if_then_else(!validW, clip.fW,
513 if_then_else(!cwValid, mid.fW, v.fW));
514
515 v.fU = if_then_else(!validW, next_cw(clip.fU),
516 if_then_else(!cwValid, mid.fU, v.fU));
517 v.fV = if_then_else(!validW, next_cw(clip.fV),
518 if_then_else(!cwValid, mid.fV, v.fV));
519 v.fR = if_then_else(!validW, next_cw(clip.fR),
520 if_then_else(!cwValid, mid.fR, v.fR));
521 // The non-AA edge for this quad is the clipped vertex's edge
522 GrQuadAAFlags v1EdgeFlag = (!validW[0] ? GrQuadAAFlags::kLeft :
523 (!validW[1] ? GrQuadAAFlags::kBottom :
524 (!validW[2] ? GrQuadAAFlags::kTop :
525 GrQuadAAFlags::kRight)));
526
527 v.asGrQuads(&quad->fDevice, GrQuad::Type::kPerspective,
528 &quad->fLocal, localType);
529 quad->fEdgeFlags &= ~v1EdgeFlag;
530
531 v2.asGrQuads(&extraVertices->fDevice, GrQuad::Type::kPerspective,
532 &extraVertices->fLocal, localType);
533 // Caller must draw both 'quad' and 'extraVertices' to cover the clipped geometry
534 return 2;
535 }
536}
537
538bool CropToRect(const SkRect& cropRect, GrAA cropAA, DrawQuad* quad, bool computeLocal) {
539 SkASSERT(quad->fDevice.isFinite());
540
541 if (quad->fDevice.quadType() == GrQuad::Type::kAxisAligned) {
542 // crop_rect and crop_rect_simple keep the rectangles as rectangles, so the intersection
543 // of the crop and quad can be calculated exactly. Some care must be taken if the quad
544 // is axis-aligned but does not satisfy asRect() due to flips, etc.
545 GrQuadAAFlags clippedEdges;
546 if (computeLocal) {
547 if (is_simple_rect(quad->fDevice) && is_simple_rect(quad->fLocal)) {
548 clippedEdges = crop_simple_rect(cropRect, quad->fDevice.xs(), quad->fDevice.ys(),
549 quad->fLocal.xs(), quad->fLocal.ys());
550 } else {
551 clippedEdges = crop_rect(cropRect, quad->fDevice.xs(), quad->fDevice.ys(),
552 quad->fLocal.xs(), quad->fLocal.ys(), quad->fLocal.ws());
553 }
554 } else {
555 if (is_simple_rect(quad->fDevice)) {
556 clippedEdges = crop_simple_rect(cropRect, quad->fDevice.xs(), quad->fDevice.ys(),
557 nullptr, nullptr);
558 } else {
559 clippedEdges = crop_rect(cropRect, quad->fDevice.xs(), quad->fDevice.ys(),
560 nullptr, nullptr, nullptr);
561 }
562 }
563
564 // Apply the clipped edge updates to the original edge flags
565 if (cropAA == GrAA::kYes) {
566 // Turn on all edges that were clipped
567 quad->fEdgeFlags |= clippedEdges;
568 } else {
569 // Turn off all edges that were clipped
570 quad->fEdgeFlags &= ~clippedEdges;
571 }
572 return true;
573 }
574
575 if (computeLocal) {
576 // FIXME (michaelludwig) Calculate cropped local coordinates when not kAxisAligned
577 return false;
578 }
579
580 V4f devX = quad->fDevice.x4f();
581 V4f devY = quad->fDevice.y4f();
582 // Project the 3D coordinates to 2D
583 if (quad->fDevice.quadType() == GrQuad::Type::kPerspective) {
584 V4f devW = quad->fDevice.w4f();
585 if (any(devW < SkPathPriv::kW0PlaneDistance)) {
586 // The rest of this function assumes the quad is in front of w = 0
587 return false;
588 }
589 devW = 1.f / devW;
590 devX *= devW;
591 devY *= devW;
592 }
593
594 V4f clipX = {cropRect.fLeft, cropRect.fLeft, cropRect.fRight, cropRect.fRight};
595 V4f clipY = {cropRect.fTop, cropRect.fBottom, cropRect.fTop, cropRect.fBottom};
596
597 // Calculate barycentric coordinates for the 4 rect corners in the 2 triangles that the quad
598 // is tessellated into when drawn.
599 V4f u1, v1, w1;
600 V4f u2, v2, w2;
601 if (!barycentric_coords(devX[0], devY[0], devX[1], devY[1], devX[2], devY[2], clipX, clipY,
602 &u1, &v1, &w1) ||
603 !barycentric_coords(devX[1], devY[1], devX[3], devY[3], devX[2], devY[2], clipX, clipY,
604 &u2, &v2, &w2)) {
605 // Bad triangles, skip cropping
606 return false;
607 }
608
609 // clipDevRect is completely inside this quad if each corner is in at least one of two triangles
610 M4f inTri1 = inside_triangle(u1, v1, w1);
611 M4f inTri2 = inside_triangle(u2, v2, w2);
612 if (all(inTri1 | inTri2)) {
613 // We can crop to exactly the clipDevRect.
614 // FIXME (michaelludwig) - there are other ways to have determined quad covering the clip
615 // rect, but the barycentric coords will be useful to derive local coordinates in the future
616
617 // Since we are cropped to exactly clipDevRect, we have discarded any perspective and the
618 // type becomes kRect. If updated locals were requested, they will incorporate perspective.
619 // FIXME (michaelludwig) - once we have local coordinates handled, it may be desirable to
620 // keep the draw as perspective so that the hardware does perspective interpolation instead
621 // of pushing it into a local coord w and having the shader do an extra divide.
622 clipX.store(quad->fDevice.xs());
623 clipY.store(quad->fDevice.ys());
624 quad->fDevice.setQuadType(GrQuad::Type::kAxisAligned);
625
626 // Update the edge flags to match the clip setting since all 4 edges have been clipped
627 quad->fEdgeFlags = cropAA == GrAA::kYes ? GrQuadAAFlags::kAll : GrQuadAAFlags::kNone;
628
629 return true;
630 }
631
632 // FIXME (michaelludwig) - use TessellationHelper's inset/outset math to move
633 // edges to the closest clip corner they are outside of
634
635 return false;
636}
637
638///////////////////////////////////////////////////////////////////////////////////////////////////
639// TessellationHelper implementation and helper struct implementations
640///////////////////////////////////////////////////////////////////////////////////////////////////
641
642//** EdgeVectors implementation
643
644void TessellationHelper::EdgeVectors::reset(const skvx::Vec<4, float>& xs,
645 const skvx::Vec<4, float>& ys,
646 const skvx::Vec<4, float>& ws,
647 GrQuad::Type quadType) {
648 // Calculate all projected edge vector values for this quad.
649 if (quadType == GrQuad::Type::kPerspective) {
650 V4f iw = 1.f / ws;
651 fX2D = xs * iw;
652 fY2D = ys * iw;
653 } else {
654 fX2D = xs;
655 fY2D = ys;
656 }
657
658 fDX = next_ccw(fX2D) - fX2D;
659 fDY = next_ccw(fY2D) - fY2D;
660 fInvLengths = 1.f / sqrt(fDX*fDX + fDY*fDY);
661
662 // Normalize edge vectors
663 fDX *= fInvLengths;
664 fDY *= fInvLengths;
665
666 // Calculate angles between vectors
667 if (quadType <= GrQuad::Type::kRectilinear) {
668 fCosTheta = 0.f;
669 fInvSinTheta = 1.f;
670 } else {
671 fCosTheta = fDX*next_cw(fDX) + fDY*next_cw(fDY);
672 // NOTE: if cosTheta is close to 1, inset/outset math will avoid the fast paths that rely
673 // on thefInvSinTheta since it will approach infinity.
674 fInvSinTheta = 1.f / sqrt(1.f - fCosTheta * fCosTheta);
675 }
676}
677
678//** EdgeEquations implementation
679
680void TessellationHelper::EdgeEquations::reset(const EdgeVectors& edgeVectors) {
681 V4f dx = edgeVectors.fDX;
682 V4f dy = edgeVectors.fDY;
683 // Correct for bad edges by copying adjacent edge information into the bad component
684 correct_bad_edges(edgeVectors.fInvLengths >= kInvDistTolerance, &dx, &dy, nullptr);
685
686 V4f c = dx*edgeVectors.fY2D - dy*edgeVectors.fX2D;
687 // Make sure normals point into the shape
688 V4f test = dy * next_cw(edgeVectors.fX2D) + (-dx * next_cw(edgeVectors.fY2D) + c);
689 if (any(test < -kDistTolerance)) {
690 fA = -dy;
691 fB = dx;
692 fC = -c;
693 } else {
694 fA = dy;
695 fB = -dx;
696 fC = c;
697 }
698}
699
700V4f TessellationHelper::EdgeEquations::estimateCoverage(const V4f& x2d, const V4f& y2d) const {
701 // Calculate distance of the 4 inset points (px, py) to the 4 edges
702 V4f d0 = fA[0]*x2d + (fB[0]*y2d + fC[0]);
703 V4f d1 = fA[1]*x2d + (fB[1]*y2d + fC[1]);
704 V4f d2 = fA[2]*x2d + (fB[2]*y2d + fC[2]);
705 V4f d3 = fA[3]*x2d + (fB[3]*y2d + fC[3]);
706
707 // For each point, pretend that there's a rectangle that touches e0 and e3 on the horizontal
708 // axis, so its width is "approximately" d0 + d3, and it touches e1 and e2 on the vertical axis
709 // so its height is d1 + d2. Pin each of these dimensions to [0, 1] and approximate the coverage
710 // at each point as clamp(d0+d3, 0, 1) x clamp(d1+d2, 0, 1). For rectilinear quads this is an
711 // accurate calculation of its area clipped to an aligned pixel. For arbitrary quads it is not
712 // mathematically accurate but qualitatively provides a stable value proportional to the size of
713 // the shape.
714 V4f w = max(0.f, min(1.f, d0 + d3));
715 V4f h = max(0.f, min(1.f, d1 + d2));
716 return w * h;
717}
718
719int TessellationHelper::EdgeEquations::computeDegenerateQuad(const V4f& signedEdgeDistances,
720 V4f* x2d, V4f* y2d) const {
721 // Move the edge by the signed edge adjustment.
722 V4f oc = fC + signedEdgeDistances;
723
724 // There are 6 points that we care about to determine the final shape of the polygon, which
725 // are the intersections between (e0,e2), (e1,e0), (e2,e3), (e3,e1) (corresponding to the
726 // 4 corners), and (e1, e2), (e0, e3) (representing the intersections of opposite edges).
727 V4f denom = fA * next_cw(fB) - fB * next_cw(fA);
728 V4f px = (fB * next_cw(oc) - oc * next_cw(fB)) / denom;
729 V4f py = (oc * next_cw(fA) - fA * next_cw(oc)) / denom;
730 correct_bad_coords(abs(denom) < kTolerance, &px, &py, nullptr);
731
732 // Calculate the signed distances from these 4 corners to the other two edges that did not
733 // define the intersection. So p(0) is compared to e3,e1, p(1) to e3,e2 , p(2) to e0,e1, and
734 // p(3) to e0,e2
735 V4f dists1 = px * skvx::shuffle<3, 3, 0, 0>(fA) +
736 py * skvx::shuffle<3, 3, 0, 0>(fB) +
737 skvx::shuffle<3, 3, 0, 0>(oc);
738 V4f dists2 = px * skvx::shuffle<1, 2, 1, 2>(fA) +
739 py * skvx::shuffle<1, 2, 1, 2>(fB) +
740 skvx::shuffle<1, 2, 1, 2>(oc);
741
742 // If all the distances are >= 0, the 4 corners form a valid quadrilateral, so use them as
743 // the 4 points. If any point is on the wrong side of both edges, the interior has collapsed
744 // and we need to use a central point to represent it. If all four points are only on the
745 // wrong side of 1 edge, one edge has crossed over another and we use a line to represent it.
746 // Otherwise, use a triangle that replaces the bad points with the intersections of
747 // (e1, e2) or (e0, e3) as needed.
748 M4f d1v0 = dists1 < kDistTolerance;
749 M4f d2v0 = dists2 < kDistTolerance;
750 M4f d1And2 = d1v0 & d2v0;
751 M4f d1Or2 = d1v0 | d2v0;
752
753 if (!any(d1Or2)) {
754 // Every dists1 and dists2 >= kTolerance so it's not degenerate, use all 4 corners as-is
755 // and use full coverage
756 *x2d = px;
757 *y2d = py;
758 return 4;
759 } else if (any(d1And2)) {
760 // A point failed against two edges, so reduce the shape to a single point, which we take as
761 // the center of the original quad to ensure it is contained in the intended geometry. Since
762 // it has collapsed, we know the shape cannot cover a pixel so update the coverage.
763 SkPoint center = {0.25f * ((*x2d)[0] + (*x2d)[1] + (*x2d)[2] + (*x2d)[3]),
764 0.25f * ((*y2d)[0] + (*y2d)[1] + (*y2d)[2] + (*y2d)[3])};
765 *x2d = center.fX;
766 *y2d = center.fY;
767 return 1;
768 } else if (all(d1Or2)) {
769 // Degenerates to a line. Compare p[2] and p[3] to edge 0. If they are on the wrong side,
770 // that means edge 0 and 3 crossed, and otherwise edge 1 and 2 crossed.
771 if (dists1[2] < kDistTolerance && dists1[3] < kDistTolerance) {
772 // Edges 0 and 3 have crossed over, so make the line from average of (p0,p2) and (p1,p3)
773 *x2d = 0.5f * (skvx::shuffle<0, 1, 0, 1>(px) + skvx::shuffle<2, 3, 2, 3>(px));
774 *y2d = 0.5f * (skvx::shuffle<0, 1, 0, 1>(py) + skvx::shuffle<2, 3, 2, 3>(py));
775 } else {
776 // Edges 1 and 2 have crossed over, so make the line from average of (p0,p1) and (p2,p3)
777 *x2d = 0.5f * (skvx::shuffle<0, 0, 2, 2>(px) + skvx::shuffle<1, 1, 3, 3>(px));
778 *y2d = 0.5f * (skvx::shuffle<0, 0, 2, 2>(py) + skvx::shuffle<1, 1, 3, 3>(py));
779 }
780 return 2;
781 } else {
782 // This turns into a triangle. Replace corners as needed with the intersections between
783 // (e0,e3) and (e1,e2), which must now be calculated
784 using V2f = skvx::Vec<2, float>;
785 V2f eDenom = skvx::shuffle<0, 1>(fA) * skvx::shuffle<3, 2>(fB) -
786 skvx::shuffle<0, 1>(fB) * skvx::shuffle<3, 2>(fA);
787 V2f ex = (skvx::shuffle<0, 1>(fB) * skvx::shuffle<3, 2>(oc) -
788 skvx::shuffle<0, 1>(oc) * skvx::shuffle<3, 2>(fB)) / eDenom;
789 V2f ey = (skvx::shuffle<0, 1>(oc) * skvx::shuffle<3, 2>(fA) -
790 skvx::shuffle<0, 1>(fA) * skvx::shuffle<3, 2>(oc)) / eDenom;
791
792 if (SkScalarAbs(eDenom[0]) > kTolerance) {
793 px = if_then_else(d1v0, V4f(ex[0]), px);
794 py = if_then_else(d1v0, V4f(ey[0]), py);
795 }
796 if (SkScalarAbs(eDenom[1]) > kTolerance) {
797 px = if_then_else(d2v0, V4f(ex[1]), px);
798 py = if_then_else(d2v0, V4f(ey[1]), py);
799 }
800
801 *x2d = px;
802 *y2d = py;
803 return 3;
804 }
805}
806
807//** OutsetRequest implementation
808
809void TessellationHelper::OutsetRequest::reset(const EdgeVectors& edgeVectors, GrQuad::Type quadType,
810 const skvx::Vec<4, float>& edgeDistances) {
811 fEdgeDistances = edgeDistances;
812
813 // Based on the edge distances, determine if it's acceptable to use fInvSinTheta to
814 // calculate the inset or outset geometry.
815 if (quadType <= GrQuad::Type::kRectilinear) {
816 // Since it's rectangular, the width (edge[1] or edge[2]) collapses if subtracting
817 // (dist[0] + dist[3]) makes the new width negative (minus for inset, outsetting will
818 // never be degenerate in this case). The same applies for height (edge[0] or edge[3])
819 // and (dist[1] + dist[2]).
820 fOutsetDegenerate = false;
821 float widthChange = edgeDistances[0] + edgeDistances[3];
822 float heightChange = edgeDistances[1] + edgeDistances[2];
823 // (1/len > 1/(edge sum) implies len - edge sum < 0.
824 fInsetDegenerate =
825 (widthChange > 0.f && edgeVectors.fInvLengths[1] > 1.f / widthChange) ||
826 (heightChange > 0.f && edgeVectors.fInvLengths[0] > 1.f / heightChange);
827 } else if (any(edgeVectors.fInvLengths >= kInvDistTolerance)) {
828 // Have an edge that is effectively length 0, so we're dealing with a triangle, which
829 // must always go through the degenerate code path.
830 fOutsetDegenerate = true;
831 fInsetDegenerate = true;
832 } else {
833 // If possible, the corners will move +/-edgeDistances * 1/sin(theta). The entire
834 // request is degenerate if 1/sin(theta) -> infinity (or cos(theta) -> 1).
835 if (any(abs(edgeVectors.fCosTheta) >= 0.9f)) {
836 fOutsetDegenerate = true;
837 fInsetDegenerate = true;
838 } else {
839 // With an edge-centric view, an edge's length changes by
840 // edgeDistance * cos(pi - theta) / sin(theta) for each of its corners (the second
841 // corner uses ccw theta value). An edge's length also changes when its adjacent
842 // edges move, in which case it's updated by edgeDistance / sin(theta)
843 // (or cos(theta) for the other edge).
844
845 // cos(pi - theta) = -cos(theta)
846 V4f halfTanTheta = -edgeVectors.fCosTheta * edgeVectors.fInvSinTheta;
847 V4f edgeAdjust = edgeDistances * (halfTanTheta + next_ccw(halfTanTheta)) +
848 next_ccw(edgeDistances) * next_ccw(edgeVectors.fInvSinTheta) +
849 next_cw(edgeDistances) * edgeVectors.fInvSinTheta;
850
851 // If either outsetting (plus edgeAdjust) or insetting (minus edgeAdjust) make
852 // the edge lengths negative, then it's degenerate.
853 V4f threshold = 0.1f - (1.f / edgeVectors.fInvLengths);
854 fOutsetDegenerate = any(edgeAdjust < threshold);
855 fInsetDegenerate = any(edgeAdjust > -threshold);
856 }
857 }
858}
859
860//** Vertices implementation
861
862void TessellationHelper::Vertices::reset(const GrQuad& deviceQuad, const GrQuad* localQuad) {
863 // Set vertices to match the device and local quad
864 fX = deviceQuad.x4f();
865 fY = deviceQuad.y4f();
866 fW = deviceQuad.w4f();
867
868 if (localQuad) {
869 fU = localQuad->x4f();
870 fV = localQuad->y4f();
871 fR = localQuad->w4f();
872 fUVRCount = localQuad->hasPerspective() ? 3 : 2;
873 } else {
874 fUVRCount = 0;
875 }
876}
877
878void TessellationHelper::Vertices::asGrQuads(GrQuad* deviceOut, GrQuad::Type deviceType,
879 GrQuad* localOut, GrQuad::Type localType) const {
880 SkASSERT(deviceOut);
881 SkASSERT(fUVRCount == 0 || localOut);
882
883 fX.store(deviceOut->xs());
884 fY.store(deviceOut->ys());
885 if (deviceType == GrQuad::Type::kPerspective) {
886 fW.store(deviceOut->ws());
887 }
888 deviceOut->setQuadType(deviceType); // This sets ws == 1 when device type != perspective
889
890 if (fUVRCount > 0) {
891 fU.store(localOut->xs());
892 fV.store(localOut->ys());
893 if (fUVRCount == 3) {
894 fR.store(localOut->ws());
895 }
896 localOut->setQuadType(localType);
897 }
898}
899
900void TessellationHelper::Vertices::moveAlong(const EdgeVectors& edgeVectors,
901 const V4f& signedEdgeDistances) {
902 // This shouldn't be called if fInvSinTheta is close to infinity (cosTheta close to 1).
903 // FIXME (michaelludwig) - Temporarily allow NaNs on debug builds here, for crbug:224618's GM
904 // Once W clipping is implemented, shouldn't see NaNs unless it's actually time to fail.
905 SkASSERT(all(abs(edgeVectors.fCosTheta) < 0.9f) ||
906 any(edgeVectors.fCosTheta != edgeVectors.fCosTheta));
907
908 // When the projected device quad is not degenerate, the vertex corners can move
909 // cornerOutsetLen along their edge and their cw-rotated edge. The vertex's edge points
910 // inwards and the cw-rotated edge points outwards, hence the minus-sign.
911 // The edge distances are rotated compared to the corner outsets and (dx, dy), since if
912 // the edge is "on" both its corners need to be moved along their other edge vectors.
913 V4f signedOutsets = -edgeVectors.fInvSinTheta * next_cw(signedEdgeDistances);
914 V4f signedOutsetsCW = edgeVectors.fInvSinTheta * signedEdgeDistances;
915
916 // x = x + outset * mask * next_cw(xdiff) - outset * next_cw(mask) * xdiff
917 fX += signedOutsetsCW * next_cw(edgeVectors.fDX) + signedOutsets * edgeVectors.fDX;
918 fY += signedOutsetsCW * next_cw(edgeVectors.fDY) + signedOutsets * edgeVectors.fDY;
919 if (fUVRCount > 0) {
920 // We want to extend the texture coords by the same proportion as the positions.
921 signedOutsets *= edgeVectors.fInvLengths;
922 signedOutsetsCW *= next_cw(edgeVectors.fInvLengths);
923 V4f du = next_ccw(fU) - fU;
924 V4f dv = next_ccw(fV) - fV;
925 fU += signedOutsetsCW * next_cw(du) + signedOutsets * du;
926 fV += signedOutsetsCW * next_cw(dv) + signedOutsets * dv;
927 if (fUVRCount == 3) {
928 V4f dr = next_ccw(fR) - fR;
929 fR += signedOutsetsCW * next_cw(dr) + signedOutsets * dr;
930 }
931 }
932}
933
934void TessellationHelper::Vertices::moveTo(const V4f& x2d, const V4f& y2d, const M4f& mask) {
935 // Left to right, in device space, for each point
936 V4f e1x = skvx::shuffle<2, 3, 2, 3>(fX) - skvx::shuffle<0, 1, 0, 1>(fX);
937 V4f e1y = skvx::shuffle<2, 3, 2, 3>(fY) - skvx::shuffle<0, 1, 0, 1>(fY);
938 V4f e1w = skvx::shuffle<2, 3, 2, 3>(fW) - skvx::shuffle<0, 1, 0, 1>(fW);
939 M4f e1Bad = e1x*e1x + e1y*e1y < kDist2Tolerance;
940 correct_bad_edges(e1Bad, &e1x, &e1y, &e1w);
941
942 // // Top to bottom, in device space, for each point
943 V4f e2x = skvx::shuffle<1, 1, 3, 3>(fX) - skvx::shuffle<0, 0, 2, 2>(fX);
944 V4f e2y = skvx::shuffle<1, 1, 3, 3>(fY) - skvx::shuffle<0, 0, 2, 2>(fY);
945 V4f e2w = skvx::shuffle<1, 1, 3, 3>(fW) - skvx::shuffle<0, 0, 2, 2>(fW);
946 M4f e2Bad = e2x*e2x + e2y*e2y < kDist2Tolerance;
947 correct_bad_edges(e2Bad, &e2x, &e2y, &e2w);
948
949 // Can only move along e1 and e2 to reach the new 2D point, so we have
950 // x2d = (x + a*e1x + b*e2x) / (w + a*e1w + b*e2w) and
951 // y2d = (y + a*e1y + b*e2y) / (w + a*e1w + b*e2w) for some a, b
952 // This can be rewritten to a*c1x + b*c2x + c3x = 0; a * c1y + b*c2y + c3y = 0, where
953 // the cNx and cNy coefficients are:
954 V4f c1x = e1w * x2d - e1x;
955 V4f c1y = e1w * y2d - e1y;
956 V4f c2x = e2w * x2d - e2x;
957 V4f c2y = e2w * y2d - e2y;
958 V4f c3x = fW * x2d - fX;
959 V4f c3y = fW * y2d - fY;
960
961 // Solve for a and b
962 V4f a, b, denom;
963 if (all(mask)) {
964 // When every edge is outset/inset, each corner can use both edge vectors
965 denom = c1x * c2y - c2x * c1y;
966 a = (c2x * c3y - c3x * c2y) / denom;
967 b = (c3x * c1y - c1x * c3y) / denom;
968 } else {
969 // Force a or b to be 0 if that edge cannot be used due to non-AA
970 M4f aMask = skvx::shuffle<0, 0, 3, 3>(mask);
971 M4f bMask = skvx::shuffle<2, 1, 2, 1>(mask);
972
973 // When aMask[i]&bMask[i], then a[i], b[i], denom[i] match the kAll case.
974 // When aMask[i]&!bMask[i], then b[i] = 0, a[i] = -c3x/c1x or -c3y/c1y, using better denom
975 // When !aMask[i]&bMask[i], then a[i] = 0, b[i] = -c3x/c2x or -c3y/c2y, ""
976 // When !aMask[i]&!bMask[i], then both a[i] = 0 and b[i] = 0
977 M4f useC1x = abs(c1x) > abs(c1y);
978 M4f useC2x = abs(c2x) > abs(c2y);
979
980 denom = if_then_else(aMask,
981 if_then_else(bMask,
982 c1x * c2y - c2x * c1y, /* A & B */
983 if_then_else(useC1x, c1x, c1y)), /* A & !B */
984 if_then_else(bMask,
985 if_then_else(useC2x, c2x, c2y), /* !A & B */
986 V4f(1.f))); /* !A & !B */
987
988 a = if_then_else(aMask,
989 if_then_else(bMask,
990 c2x * c3y - c3x * c2y, /* A & B */
991 if_then_else(useC1x, -c3x, -c3y)), /* A & !B */
992 V4f(0.f)) / denom; /* !A */
993 b = if_then_else(bMask,
994 if_then_else(aMask,
995 c3x * c1y - c1x * c3y, /* A & B */
996 if_then_else(useC2x, -c3x, -c3y)), /* !A & B */
997 V4f(0.f)) / denom; /* !B */
998 }
999
1000 fX += a * e1x + b * e2x;
1001 fY += a * e1y + b * e2y;
1002 fW += a * e1w + b * e2w;
1003
1004 // If fW has gone negative, flip the point to the other side of w=0. This only happens if the
1005 // edge was approaching a vanishing point and it was physically impossible to outset 1/2px in
1006 // screen space w/o going behind the viewer and being mirrored. Scaling by -1 preserves the
1007 // computed screen space position but moves the 3D point off of the original quad. So far, this
1008 // seems to be a reasonable compromise.
1009 if (any(fW < 0.f)) {
1010 V4f scale = if_then_else(fW < 0.f, V4f(-1.f), V4f(1.f));
1011 fX *= scale;
1012 fY *= scale;
1013 fW *= scale;
1014 }
1015
1016 correct_bad_coords(abs(denom) < kTolerance, &fX, &fY, &fW);
1017
1018 if (fUVRCount > 0) {
1019 // Calculate R here so it can be corrected with U and V in case it's needed later
1020 V4f e1u = skvx::shuffle<2, 3, 2, 3>(fU) - skvx::shuffle<0, 1, 0, 1>(fU);
1021 V4f e1v = skvx::shuffle<2, 3, 2, 3>(fV) - skvx::shuffle<0, 1, 0, 1>(fV);
1022 V4f e1r = skvx::shuffle<2, 3, 2, 3>(fR) - skvx::shuffle<0, 1, 0, 1>(fR);
1023 correct_bad_edges(e1Bad, &e1u, &e1v, &e1r);
1024
1025 V4f e2u = skvx::shuffle<1, 1, 3, 3>(fU) - skvx::shuffle<0, 0, 2, 2>(fU);
1026 V4f e2v = skvx::shuffle<1, 1, 3, 3>(fV) - skvx::shuffle<0, 0, 2, 2>(fV);
1027 V4f e2r = skvx::shuffle<1, 1, 3, 3>(fR) - skvx::shuffle<0, 0, 2, 2>(fR);
1028 correct_bad_edges(e2Bad, &e2u, &e2v, &e2r);
1029
1030 fU += a * e1u + b * e2u;
1031 fV += a * e1v + b * e2v;
1032 if (fUVRCount == 3) {
1033 fR += a * e1r + b * e2r;
1034 correct_bad_coords(abs(denom) < kTolerance, &fU, &fV, &fR);
1035 } else {
1036 correct_bad_coords(abs(denom) < kTolerance, &fU, &fV, nullptr);
1037 }
1038 }
1039}
1040
1041//** TessellationHelper implementation
1042
1043void TessellationHelper::reset(const GrQuad& deviceQuad, const GrQuad* localQuad) {
1044 // Record basic state that isn't recorded on the Vertices struct itself
1045 fDeviceType = deviceQuad.quadType();
1046 fLocalType = localQuad ? localQuad->quadType() : GrQuad::Type::kAxisAligned;
1047
1048 // Reset metadata validity
1049 fOutsetRequestValid = false;
1050 fEdgeEquationsValid = false;
1051
1052 // Compute vertex properties that are always needed for a quad, so no point in doing it lazily.
1053 fOriginal.reset(deviceQuad, localQuad);
1054 fEdgeVectors.reset(fOriginal.fX, fOriginal.fY, fOriginal.fW, fDeviceType);
1055
1056 fVerticesValid = true;
1057}
1058
1059V4f TessellationHelper::inset(const skvx::Vec<4, float>& edgeDistances,
1060 GrQuad* deviceInset, GrQuad* localInset) {
1061 SkASSERT(fVerticesValid);
1062
1063 Vertices inset = fOriginal;
1064 const OutsetRequest& request = this->getOutsetRequest(edgeDistances);
1065 int vertexCount;
1066 if (request.fInsetDegenerate) {
1067 vertexCount = this->adjustDegenerateVertices(-request.fEdgeDistances, &inset);
1068 } else {
1069 this->adjustVertices(-request.fEdgeDistances, &inset);
1070 vertexCount = 4;
1071 }
1072
1073 inset.asGrQuads(deviceInset, fDeviceType, localInset, fLocalType);
1074 if (vertexCount < 3) {
1075 // The interior has less than a full pixel's area so estimate reduced coverage using
1076 // the distance of the inset's projected corners to the original edges.
1077 return this->getEdgeEquations().estimateCoverage(inset.fX / inset.fW,
1078 inset.fY / inset.fW);
1079 } else {
1080 return 1.f;
1081 }
1082}
1083
1084void TessellationHelper::outset(const skvx::Vec<4, float>& edgeDistances,
1085 GrQuad* deviceOutset, GrQuad* localOutset) {
1086 SkASSERT(fVerticesValid);
1087
1088 Vertices outset = fOriginal;
1089 const OutsetRequest& request = this->getOutsetRequest(edgeDistances);
1090 if (request.fOutsetDegenerate) {
1091 this->adjustDegenerateVertices(request.fEdgeDistances, &outset);
1092 } else {
1093 this->adjustVertices(request.fEdgeDistances, &outset);
1094 }
1095
1096 outset.asGrQuads(deviceOutset, fDeviceType, localOutset, fLocalType);
1097}
1098
1099const TessellationHelper::OutsetRequest& TessellationHelper::getOutsetRequest(
1100 const skvx::Vec<4, float>& edgeDistances) {
1101 // Much of the code assumes that we start from positive distances and apply it unmodified to
1102 // create an outset; knowing that it's outset simplifies degeneracy checking.
1103 SkASSERT(all(edgeDistances >= 0.f));
1104
1105 // Rebuild outset request if invalid or if the edge distances have changed.
1106 if (!fOutsetRequestValid || any(edgeDistances != fOutsetRequest.fEdgeDistances)) {
1107 fOutsetRequest.reset(fEdgeVectors, fDeviceType, edgeDistances);
1108 fOutsetRequestValid = true;
1109 }
1110 return fOutsetRequest;
1111}
1112
1113const TessellationHelper::EdgeEquations& TessellationHelper::getEdgeEquations() {
1114 if (!fEdgeEquationsValid) {
1115 fEdgeEquations.reset(fEdgeVectors);
1116 fEdgeEquationsValid = true;
1117 }
1118 return fEdgeEquations;
1119}
1120
1121void TessellationHelper::adjustVertices(const skvx::Vec<4, float>& signedEdgeDistances,
1122 Vertices* vertices) {
1123 SkASSERT(vertices);
1124 SkASSERT(vertices->fUVRCount == 0 || vertices->fUVRCount == 2 || vertices->fUVRCount == 3);
1125
1126 if (fDeviceType < GrQuad::Type::kPerspective) {
1127 // For non-perspective, non-degenerate quads, moveAlong is correct and most efficient
1128 vertices->moveAlong(fEdgeVectors, signedEdgeDistances);
1129 } else {
1130 // For perspective, non-degenerate quads, use moveAlong for the projected points and then
1131 // reconstruct Ws with moveTo.
1132 Vertices projected = { fEdgeVectors.fX2D, fEdgeVectors.fY2D, /*w*/ 1.f, 0.f, 0.f, 0.f, 0 };
1133 projected.moveAlong(fEdgeVectors, signedEdgeDistances);
1134 vertices->moveTo(projected.fX, projected.fY, signedEdgeDistances != 0.f);
1135 }
1136}
1137
1138int TessellationHelper::adjustDegenerateVertices(const skvx::Vec<4, float>& signedEdgeDistances,
1139 Vertices* vertices) {
1140 SkASSERT(vertices);
1141 SkASSERT(vertices->fUVRCount == 0 || vertices->fUVRCount == 2 || vertices->fUVRCount == 3);
1142
1143 if (fDeviceType <= GrQuad::Type::kRectilinear) {
1144 // For rectilinear, degenerate quads, can use moveAlong if the edge distances are adjusted
1145 // to not cross over each other.
1146 SkASSERT(all(signedEdgeDistances <= 0.f)); // Only way rectilinear can degenerate is insets
1147 V4f halfLengths = -0.5f / next_cw(fEdgeVectors.fInvLengths); // Negate to inset
1148 M4f crossedEdges = halfLengths > signedEdgeDistances;
1149 V4f safeInsets = if_then_else(crossedEdges, halfLengths, signedEdgeDistances);
1150 vertices->moveAlong(fEdgeVectors, safeInsets);
1151
1152 // A degenerate rectilinear quad is either a point (both w and h crossed), or a line
1153 return all(crossedEdges) ? 1 : 2;
1154 } else {
1155 // Degenerate non-rectangular shape, must go through slowest path (which automatically
1156 // handles perspective).
1157 V4f x2d = fEdgeVectors.fX2D;
1158 V4f y2d = fEdgeVectors.fY2D;
1159 int vertexCount = this->getEdgeEquations().computeDegenerateQuad(signedEdgeDistances,
1160 &x2d, &y2d);
1161 vertices->moveTo(x2d, y2d, signedEdgeDistances != 0.f);
1162 return vertexCount;
1163 }
1164}
1165
1166}; // namespace GrQuadUtils
1167