Michael Ludwig | 0f80902 | 2019-06-04 09:14:37 -0400 | [diff] [blame] | 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 | |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 10 | #include "include/core/SkRect.h" |
Michael Ludwig | 0f80902 | 2019-06-04 09:14:37 -0400 | [diff] [blame] | 11 | #include "include/private/GrTypesPriv.h" |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 12 | #include "include/private/SkVx.h" |
Michael Ludwig | 0f80902 | 2019-06-04 09:14:37 -0400 | [diff] [blame] | 13 | #include "src/gpu/geometry/GrQuad.h" |
| 14 | |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 15 | using V4f = skvx::Vec<4, float>; |
| 16 | using M4f = skvx::Vec<4, int32_t>; |
| 17 | |
| 18 | // Since the local quad may not be type kRect, this uses the opposites for each vertex when |
| 19 | // interpolating, and calculates new ws in addition to new xs, ys. |
| 20 | static void interpolate_local(float alpha, int v0, int v1, int v2, int v3, |
| 21 | float lx[4], float ly[4], float lw[4]) { |
| 22 | SkASSERT(v0 >= 0 && v0 < 4); |
| 23 | SkASSERT(v1 >= 0 && v1 < 4); |
| 24 | SkASSERT(v2 >= 0 && v2 < 4); |
| 25 | SkASSERT(v3 >= 0 && v3 < 4); |
| 26 | |
| 27 | float beta = 1.f - alpha; |
| 28 | lx[v0] = alpha * lx[v0] + beta * lx[v2]; |
| 29 | ly[v0] = alpha * ly[v0] + beta * ly[v2]; |
| 30 | lw[v0] = alpha * lw[v0] + beta * lw[v2]; |
| 31 | |
| 32 | lx[v1] = alpha * lx[v1] + beta * lx[v3]; |
| 33 | ly[v1] = alpha * ly[v1] + beta * ly[v3]; |
| 34 | lw[v1] = alpha * lw[v1] + beta * lw[v3]; |
| 35 | } |
| 36 | |
| 37 | // Crops v0 to v1 based on the clipDevRect. v2 is opposite of v0, v3 is opposite of v1. |
| 38 | // It is written to not modify coordinates if there's no intersection along the edge. |
| 39 | // Ideally this would have been detected earlier and the entire draw is skipped. |
| 40 | static bool crop_rect_edge(const SkRect& clipDevRect, int v0, int v1, int v2, int v3, |
| 41 | float x[4], float y[4], float lx[4], float ly[4], float lw[4]) { |
| 42 | SkASSERT(v0 >= 0 && v0 < 4); |
| 43 | SkASSERT(v1 >= 0 && v1 < 4); |
| 44 | SkASSERT(v2 >= 0 && v2 < 4); |
| 45 | SkASSERT(v3 >= 0 && v3 < 4); |
| 46 | |
| 47 | if (SkScalarNearlyEqual(x[v0], x[v1])) { |
| 48 | // A vertical edge |
| 49 | if (x[v0] < clipDevRect.fLeft && x[v2] >= clipDevRect.fLeft) { |
| 50 | // Overlapping with left edge of clipDevRect |
| 51 | if (lx) { |
| 52 | float alpha = (x[v2] - clipDevRect.fLeft) / (x[v2] - x[v0]); |
| 53 | interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw); |
| 54 | } |
| 55 | x[v0] = clipDevRect.fLeft; |
| 56 | x[v1] = clipDevRect.fLeft; |
| 57 | return true; |
| 58 | } else if (x[v0] > clipDevRect.fRight && x[v2] <= clipDevRect.fRight) { |
| 59 | // Overlapping with right edge of clipDevRect |
| 60 | if (lx) { |
| 61 | float alpha = (clipDevRect.fRight - x[v2]) / (x[v0] - x[v2]); |
| 62 | interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw); |
| 63 | } |
| 64 | x[v0] = clipDevRect.fRight; |
| 65 | x[v1] = clipDevRect.fRight; |
| 66 | return true; |
| 67 | } |
| 68 | } else { |
| 69 | // A horizontal edge |
| 70 | SkASSERT(SkScalarNearlyEqual(y[v0], y[v1])); |
| 71 | if (y[v0] < clipDevRect.fTop && y[v2] >= clipDevRect.fTop) { |
| 72 | // Overlapping with top edge of clipDevRect |
| 73 | if (lx) { |
| 74 | float alpha = (y[v2] - clipDevRect.fTop) / (y[v2] - y[v0]); |
| 75 | interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw); |
| 76 | } |
| 77 | y[v0] = clipDevRect.fTop; |
| 78 | y[v1] = clipDevRect.fTop; |
| 79 | return true; |
| 80 | } else if (y[v0] > clipDevRect.fBottom && y[v2] <= clipDevRect.fBottom) { |
| 81 | // Overlapping with bottom edge of clipDevRect |
| 82 | if (lx) { |
| 83 | float alpha = (clipDevRect.fBottom - y[v2]) / (y[v0] - y[v2]); |
| 84 | interpolate_local(alpha, v0, v1, v2, v3, lx, ly, lw); |
| 85 | } |
| 86 | y[v0] = clipDevRect.fBottom; |
| 87 | y[v1] = clipDevRect.fBottom; |
| 88 | return true; |
| 89 | } |
| 90 | } |
| 91 | |
| 92 | // No overlap so don't crop it |
| 93 | return false; |
| 94 | } |
| 95 | |
Michael Ludwig | 0a7cab0 | 2019-07-09 17:20:08 +0000 | [diff] [blame] | 96 | // Updates x and y to intersect with clipDevRect. lx, ly, and lw are updated appropriately and may |
| 97 | // be null to skip calculations. Returns bit mask of edges that were clipped. |
| 98 | static GrQuadAAFlags crop_rect(const SkRect& clipDevRect, float x[4], float y[4], |
| 99 | float lx[4], float ly[4], float lw[4]) { |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 100 | GrQuadAAFlags clipEdgeFlags = GrQuadAAFlags::kNone; |
| 101 | |
Michael Ludwig | 0a7cab0 | 2019-07-09 17:20:08 +0000 | [diff] [blame] | 102 | // The quad's left edge may not align with the SkRect notion of left due to 90 degree rotations |
| 103 | // or mirrors. So, this processes the logical edges of the quad and clamps it to the 4 sides of |
| 104 | // clipDevRect. |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 105 | |
| 106 | // Quad's left is v0 to v1 (op. v2 and v3) |
| 107 | if (crop_rect_edge(clipDevRect, 0, 1, 2, 3, x, y, lx, ly, lw)) { |
| 108 | clipEdgeFlags |= GrQuadAAFlags::kLeft; |
| 109 | } |
| 110 | // Quad's top edge is v0 to v2 (op. v1 and v3) |
| 111 | if (crop_rect_edge(clipDevRect, 0, 2, 1, 3, x, y, lx, ly, lw)) { |
| 112 | clipEdgeFlags |= GrQuadAAFlags::kTop; |
| 113 | } |
| 114 | // Quad's right edge is v2 to v3 (op. v0 and v1) |
| 115 | if (crop_rect_edge(clipDevRect, 2, 3, 0, 1, x, y, lx, ly, lw)) { |
| 116 | clipEdgeFlags |= GrQuadAAFlags::kRight; |
| 117 | } |
| 118 | // Quad's bottom edge is v1 to v3 (op. v0 and v2) |
| 119 | if (crop_rect_edge(clipDevRect, 1, 3, 0, 2, x, y, lx, ly, lw)) { |
| 120 | clipEdgeFlags |= GrQuadAAFlags::kBottom; |
| 121 | } |
| 122 | |
Michael Ludwig | 0a7cab0 | 2019-07-09 17:20:08 +0000 | [diff] [blame] | 123 | return clipEdgeFlags; |
| 124 | } |
| 125 | |
| 126 | // Similar to crop_rect, but assumes that both the device coordinates and optional local coordinates |
| 127 | // geometrically match the TL, BL, TR, BR vertex ordering, i.e. axis-aligned but not flipped, etc. |
| 128 | static GrQuadAAFlags crop_simple_rect(const SkRect& clipDevRect, float x[4], float y[4], |
| 129 | float lx[4], float ly[4]) { |
| 130 | GrQuadAAFlags clipEdgeFlags = GrQuadAAFlags::kNone; |
| 131 | |
| 132 | // Update local coordinates proportionately to how much the device rect edge was clipped |
| 133 | const SkScalar dx = lx ? (lx[2] - lx[0]) / (x[2] - x[0]) : 0.f; |
| 134 | const SkScalar dy = ly ? (ly[1] - ly[0]) / (y[1] - y[0]) : 0.f; |
| 135 | if (clipDevRect.fLeft > x[0]) { |
| 136 | if (lx) { |
| 137 | lx[0] += (clipDevRect.fLeft - x[0]) * dx; |
| 138 | lx[1] = lx[0]; |
| 139 | } |
| 140 | x[0] = clipDevRect.fLeft; |
| 141 | x[1] = clipDevRect.fLeft; |
| 142 | clipEdgeFlags |= GrQuadAAFlags::kLeft; |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 143 | } |
Michael Ludwig | 0a7cab0 | 2019-07-09 17:20:08 +0000 | [diff] [blame] | 144 | if (clipDevRect.fTop > y[0]) { |
| 145 | if (ly) { |
| 146 | ly[0] += (clipDevRect.fTop - y[0]) * dy; |
| 147 | ly[2] = ly[0]; |
| 148 | } |
| 149 | y[0] = clipDevRect.fTop; |
| 150 | y[2] = clipDevRect.fTop; |
| 151 | clipEdgeFlags |= GrQuadAAFlags::kTop; |
| 152 | } |
| 153 | if (clipDevRect.fRight < x[2]) { |
| 154 | if (lx) { |
| 155 | lx[2] -= (x[2] - clipDevRect.fRight) * dx; |
| 156 | lx[3] = lx[2]; |
| 157 | } |
| 158 | x[2] = clipDevRect.fRight; |
| 159 | x[3] = clipDevRect.fRight; |
| 160 | clipEdgeFlags |= GrQuadAAFlags::kRight; |
| 161 | } |
| 162 | if (clipDevRect.fBottom < y[1]) { |
| 163 | if (ly) { |
| 164 | ly[1] -= (y[1] - clipDevRect.fBottom) * dy; |
| 165 | ly[3] = ly[1]; |
| 166 | } |
| 167 | y[1] = clipDevRect.fBottom; |
| 168 | y[3] = clipDevRect.fBottom; |
| 169 | clipEdgeFlags |= GrQuadAAFlags::kBottom; |
| 170 | } |
| 171 | |
| 172 | return clipEdgeFlags; |
| 173 | } |
| 174 | // Consistent with GrQuad::asRect()'s return value but requires fewer operations since we don't need |
| 175 | // to calculate the bounds of the quad. |
| 176 | static bool is_simple_rect(const GrQuad& quad) { |
| 177 | if (quad.quadType() != GrQuad::Type::kAxisAligned) { |
| 178 | return false; |
| 179 | } |
| 180 | // v0 at the geometric top-left is unique, so we only need to compare x[0] < x[2] for left |
| 181 | // and y[0] < y[1] for top, but add a little padding to protect against numerical precision |
| 182 | // on R90 and R270 transforms tricking this check. |
| 183 | return ((quad.x(0) + SK_ScalarNearlyZero) < quad.x(2)) && |
| 184 | ((quad.y(0) + SK_ScalarNearlyZero) < quad.y(1)); |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 185 | } |
| 186 | |
| 187 | // Calculates barycentric coordinates for each point in (testX, testY) in the triangle formed by |
| 188 | // (x0,y0) - (x1,y1) - (x2, y2) and stores them in u, v, w. |
| 189 | static void barycentric_coords(float x0, float y0, float x1, float y1, float x2, float y2, |
| 190 | const V4f& testX, const V4f& testY, |
| 191 | V4f* u, V4f* v, V4f* w) { |
| 192 | // Modeled after SkPathOpsQuad::pointInTriangle() but uses float instead of double, is |
| 193 | // vectorized and outputs normalized barycentric coordinates instead of inside/outside test |
| 194 | float v0x = x2 - x0; |
| 195 | float v0y = y2 - y0; |
| 196 | float v1x = x1 - x0; |
| 197 | float v1y = y1 - y0; |
| 198 | V4f v2x = testX - x0; |
| 199 | V4f v2y = testY - y0; |
| 200 | |
| 201 | float dot00 = v0x * v0x + v0y * v0y; |
| 202 | float dot01 = v0x * v1x + v0y * v1y; |
| 203 | V4f dot02 = v0x * v2x + v0y * v2y; |
| 204 | float dot11 = v1x * v1x + v1y * v1y; |
| 205 | V4f dot12 = v1x * v2x + v1y * v2y; |
| 206 | float invDenom = sk_ieee_float_divide(1.f, dot00 * dot11 - dot01 * dot01); |
| 207 | *u = (dot11 * dot02 - dot01 * dot12) * invDenom; |
| 208 | *v = (dot00 * dot12 - dot01 * dot02) * invDenom; |
| 209 | *w = 1.f - *u - *v; |
| 210 | } |
| 211 | |
| 212 | static M4f inside_triangle(const V4f& u, const V4f& v, const V4f& w) { |
| 213 | return ((u >= 0.f) & (u <= 1.f)) & ((v >= 0.f) & (v <= 1.f)) & ((w >= 0.f) & (w <= 1.f)); |
| 214 | } |
| 215 | |
Michael Ludwig | 0f80902 | 2019-06-04 09:14:37 -0400 | [diff] [blame] | 216 | namespace GrQuadUtils { |
| 217 | |
| 218 | void ResolveAAType(GrAAType requestedAAType, GrQuadAAFlags requestedEdgeFlags, const GrQuad& quad, |
| 219 | GrAAType* outAAType, GrQuadAAFlags* outEdgeFlags) { |
| 220 | // Most cases will keep the requested types unchanged |
| 221 | *outAAType = requestedAAType; |
| 222 | *outEdgeFlags = requestedEdgeFlags; |
| 223 | |
| 224 | switch (requestedAAType) { |
| 225 | // When aa type is coverage, disable AA if the edge configuration doesn't actually need it |
| 226 | case GrAAType::kCoverage: |
| 227 | if (requestedEdgeFlags == GrQuadAAFlags::kNone) { |
| 228 | // Turn off anti-aliasing |
| 229 | *outAAType = GrAAType::kNone; |
| 230 | } else { |
| 231 | // For coverage AA, if the quad is a rect and it lines up with pixel boundaries |
| 232 | // then overall aa and per-edge aa can be completely disabled |
| 233 | if (quad.quadType() == GrQuad::Type::kAxisAligned && !quad.aaHasEffectOnRect()) { |
| 234 | *outAAType = GrAAType::kNone; |
| 235 | *outEdgeFlags = GrQuadAAFlags::kNone; |
| 236 | } |
| 237 | } |
| 238 | break; |
| 239 | // For no or msaa anti aliasing, override the edge flags since edge flags only make sense |
| 240 | // when coverage aa is being used. |
| 241 | case GrAAType::kNone: |
| 242 | *outEdgeFlags = GrQuadAAFlags::kNone; |
| 243 | break; |
| 244 | case GrAAType::kMSAA: |
| 245 | *outEdgeFlags = GrQuadAAFlags::kAll; |
| 246 | break; |
Michael Ludwig | 0f80902 | 2019-06-04 09:14:37 -0400 | [diff] [blame] | 247 | } |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 248 | } |
| 249 | |
| 250 | bool CropToRect(const SkRect& cropRect, GrAA cropAA, GrQuadAAFlags* edgeFlags, GrQuad* quad, |
| 251 | GrQuad* local) { |
Michael Ludwig | ed71b7e | 2019-06-21 13:47:02 -0400 | [diff] [blame] | 252 | SkASSERT(quad->isFinite()); |
| 253 | |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 254 | if (quad->quadType() == GrQuad::Type::kAxisAligned) { |
Michael Ludwig | 0a7cab0 | 2019-07-09 17:20:08 +0000 | [diff] [blame] | 255 | // crop_rect and crop_rect_simple keep the rectangles as rectangles, so the intersection |
| 256 | // of the crop and quad can be calculated exactly. Some care must be taken if the quad |
| 257 | // is axis-aligned but does not satisfy asRect() due to flips, etc. |
| 258 | GrQuadAAFlags clippedEdges; |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 259 | if (local) { |
Michael Ludwig | 0a7cab0 | 2019-07-09 17:20:08 +0000 | [diff] [blame] | 260 | if (is_simple_rect(*quad) && is_simple_rect(*local)) { |
| 261 | clippedEdges = crop_simple_rect(cropRect, quad->xs(), quad->ys(), |
| 262 | local->xs(), local->ys()); |
| 263 | } else { |
| 264 | clippedEdges = crop_rect(cropRect, quad->xs(), quad->ys(), |
| 265 | local->xs(), local->ys(), local->ws()); |
| 266 | } |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 267 | } else { |
Michael Ludwig | 0a7cab0 | 2019-07-09 17:20:08 +0000 | [diff] [blame] | 268 | if (is_simple_rect(*quad)) { |
| 269 | clippedEdges = crop_simple_rect(cropRect, quad->xs(), quad->ys(), nullptr, nullptr); |
| 270 | } else { |
| 271 | clippedEdges = crop_rect(cropRect, quad->xs(), quad->ys(), |
| 272 | nullptr, nullptr, nullptr); |
| 273 | } |
| 274 | } |
| 275 | |
| 276 | // Apply the clipped edge updates to the original edge flags |
| 277 | if (cropAA == GrAA::kYes) { |
| 278 | // Turn on all edges that were clipped |
| 279 | *edgeFlags |= clippedEdges; |
| 280 | } else { |
| 281 | // Turn off all edges that were clipped |
| 282 | *edgeFlags &= ~clippedEdges; |
Michael Ludwig | 6132820 | 2019-06-19 14:48:58 +0000 | [diff] [blame] | 283 | } |
| 284 | return true; |
| 285 | } |
| 286 | |
| 287 | if (local) { |
| 288 | // FIXME (michaelludwig) Calculate cropped local coordinates when not kAxisAligned |
| 289 | return false; |
| 290 | } |
| 291 | |
| 292 | V4f devX = quad->x4f(); |
| 293 | V4f devY = quad->y4f(); |
| 294 | V4f devIW = quad->iw4f(); |
| 295 | // Project the 3D coordinates to 2D |
| 296 | if (quad->quadType() == GrQuad::Type::kPerspective) { |
| 297 | devX *= devIW; |
| 298 | devY *= devIW; |
| 299 | } |
| 300 | |
| 301 | V4f clipX = {cropRect.fLeft, cropRect.fLeft, cropRect.fRight, cropRect.fRight}; |
| 302 | V4f clipY = {cropRect.fTop, cropRect.fBottom, cropRect.fTop, cropRect.fBottom}; |
| 303 | |
| 304 | // Calculate barycentric coordinates for the 4 rect corners in the 2 triangles that the quad |
| 305 | // is tessellated into when drawn. |
| 306 | V4f u1, v1, w1; |
| 307 | barycentric_coords(devX[0], devY[0], devX[1], devY[1], devX[2], devY[2], clipX, clipY, |
| 308 | &u1, &v1, &w1); |
| 309 | V4f u2, v2, w2; |
| 310 | barycentric_coords(devX[1], devY[1], devX[3], devY[3], devX[2], devY[2], clipX, clipY, |
| 311 | &u2, &v2, &w2); |
| 312 | |
| 313 | // clipDevRect is completely inside this quad if each corner is in at least one of two triangles |
| 314 | M4f inTri1 = inside_triangle(u1, v1, w1); |
| 315 | M4f inTri2 = inside_triangle(u2, v2, w2); |
| 316 | if (all(inTri1 | inTri2)) { |
| 317 | // We can crop to exactly the clipDevRect. |
| 318 | // FIXME (michaelludwig) - there are other ways to have determined quad covering the clip |
| 319 | // rect, but the barycentric coords will be useful to derive local coordinates in the future |
| 320 | |
| 321 | // Since we are cropped to exactly clipDevRect, we have discarded any perspective and the |
| 322 | // type becomes kRect. If updated locals were requested, they will incorporate perspective. |
| 323 | // FIXME (michaelludwig) - once we have local coordinates handled, it may be desirable to |
| 324 | // keep the draw as perspective so that the hardware does perspective interpolation instead |
| 325 | // of pushing it into a local coord w and having the shader do an extra divide. |
| 326 | clipX.store(quad->xs()); |
| 327 | clipY.store(quad->ys()); |
| 328 | quad->ws()[0] = 1.f; |
| 329 | quad->ws()[1] = 1.f; |
| 330 | quad->ws()[2] = 1.f; |
| 331 | quad->ws()[3] = 1.f; |
| 332 | quad->setQuadType(GrQuad::Type::kAxisAligned); |
| 333 | |
| 334 | // Update the edge flags to match the clip setting since all 4 edges have been clipped |
| 335 | *edgeFlags = cropAA == GrAA::kYes ? GrQuadAAFlags::kAll : GrQuadAAFlags::kNone; |
| 336 | |
| 337 | return true; |
| 338 | } |
| 339 | |
| 340 | // FIXME (michaelludwig) - use the GrQuadPerEdgeAA tessellation inset/outset math to move |
| 341 | // edges to the closest clip corner they are outside of |
| 342 | |
| 343 | return false; |
| 344 | } |
Michael Ludwig | 0f80902 | 2019-06-04 09:14:37 -0400 | [diff] [blame] | 345 | |
| 346 | }; // namespace GrQuadUtils |