GrQuadUtils.cpp 14 KB

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