aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorGravatar Chris Dalton <csmartdalton@google.com>2017-06-08 13:12:02 -0600
committerGravatar Skia Commit-Bot <skia-commit-bot@chromium.org>2017-06-09 17:13:54 +0000
commitfebbffad1c24136f041d7fc2d5ffcd50e47a047f (patch)
tree860970fa626aa0901fadce958e755c107f7c97ca
parent01b2b83aba10bc3767d660cd619c1da58b5eb0b5 (diff)
Improve cubic KLM accuracy
Moves cubic root finding logic out of GrPathUtils and PathOpsCubicIntersectionTest, and unifies it in SkGeometry. "Normalizes" the homogeneous parameter values of the roots, rather than the cubic inflection function. Does this normalization by twiddling the exponents instead of division (which causes a loss of precision). Abandons the built-in derivatives in GrCubicEffect. These don't have high enough precision on many mobile gpus. Instead we pass the KLM matrix to the vertex shader via uniform, where we can use it to set up new linear functionals from which the fragment shader can calculate the gradient of the implicit function. Bug: skia:4410 Change-Id: Ibd64e999520adc8cdef7803a492d3699995aef5a Reviewed-on: https://skia-review.googlesource.com/19017 Reviewed-by: Greg Daniel <egdaniel@google.com> Commit-Queue: Chris Dalton <csmartdalton@google.com>
-rw-r--r--bench/CubicKLMBench.cpp3
-rw-r--r--gm/beziereffects.cpp111
-rw-r--r--src/core/SkGeometry.cpp152
-rw-r--r--src/core/SkGeometry.h22
-rw-r--r--src/gpu/GrPathUtils.cpp142
-rw-r--r--src/gpu/GrPathUtils.h47
-rw-r--r--src/gpu/effects/GrBezierEffect.cpp92
-rw-r--r--src/gpu/effects/GrBezierEffect.h31
-rw-r--r--src/pathops/SkPathOpsCubic.cpp17
-rw-r--r--tests/PathOpsCubicIntersectionTest.cpp3
10 files changed, 340 insertions, 280 deletions
diff --git a/bench/CubicKLMBench.cpp b/bench/CubicKLMBench.cpp
index 1cdb068c08..cbf3d13ea4 100644
--- a/bench/CubicKLMBench.cpp
+++ b/bench/CubicKLMBench.cpp
@@ -22,8 +22,7 @@ public:
fPoints[3].set(x3, y3);
fName = "cubic_klm_";
- SkScalar d[4];
- switch (SkClassifyCubic(fPoints, d)) {
+ switch (SkClassifyCubic(fPoints)) {
case SkCubicType::kSerpentine:
fName.append("serp");
break;
diff --git a/gm/beziereffects.cpp b/gm/beziereffects.cpp
index d3f1965d4f..7e492b0ca2 100644
--- a/gm/beziereffects.cpp
+++ b/gm/beziereffects.cpp
@@ -24,53 +24,36 @@
namespace skiagm {
-class BezierCubicOrConicTestOp : public GrTestMeshDrawOp {
+class BezierCubicTestOp : public GrTestMeshDrawOp {
public:
DEFINE_OP_CLASS_ID
- const char* name() const override { return "BezierCubicOrConicTestOp"; }
+ const char* name() const override { return "BezierCubicTestOp"; }
static std::unique_ptr<GrLegacyMeshDrawOp> Make(sk_sp<GrGeometryProcessor> gp,
- const SkRect& rect, GrColor color,
- const SkMatrix& klm, SkScalar sign) {
- return std::unique_ptr<GrLegacyMeshDrawOp>(
- new BezierCubicOrConicTestOp(gp, rect, color, klm, sign));
+ const SkRect& rect, GrColor color) {
+ return std::unique_ptr<GrLegacyMeshDrawOp>(new BezierCubicTestOp(gp, rect, color));
}
private:
- BezierCubicOrConicTestOp(sk_sp<GrGeometryProcessor> gp, const SkRect& rect, GrColor color,
- const SkMatrix& klm, SkScalar sign)
+ BezierCubicTestOp(sk_sp<GrGeometryProcessor> gp, const SkRect& rect, GrColor color)
: INHERITED(ClassID(), rect, color)
- , fKLM(klm)
, fRect(rect)
, fGeometryProcessor(std::move(gp)) {
- if (1 != sign) {
- fKLM.postScale(sign, sign);
- }
}
- struct Vertex {
- SkPoint fPosition;
- float fKLM[4]; // The last value is ignored. The effect expects a vec4f.
- };
void onPrepareDraws(Target* target) const override {
QuadHelper helper;
size_t vertexStride = fGeometryProcessor->getVertexStride();
- SkASSERT(vertexStride == sizeof(Vertex));
- Vertex* verts = reinterpret_cast<Vertex*>(helper.init(target, vertexStride, 1));
- if (!verts) {
+ SkASSERT(vertexStride == sizeof(SkPoint));
+ SkPoint* pts = reinterpret_cast<SkPoint*>(helper.init(target, vertexStride, 1));
+ if (!pts) {
return;
}
- verts[0].fPosition.setRectFan(fRect.fLeft, fRect.fTop, fRect.fRight, fRect.fBottom,
- sizeof(Vertex));
- for (int v = 0; v < 4; ++v) {
- SkScalar pt3[3] = {verts[v].fPosition.x(), verts[v].fPosition.y(), 1.f};
- fKLM.mapHomogeneousPoints(verts[v].fKLM, pt3, 1);
- }
+ pts[0].setRectFan(fRect.fLeft, fRect.fTop, fRect.fRight, fRect.fBottom, vertexStride);
helper.recordDraw(target, fGeometryProcessor.get(), this->pipeline());
}
- SkMatrix fKLM;
SkRect fRect;
sk_sp<GrGeometryProcessor> fGeometryProcessor;
@@ -135,13 +118,9 @@ protected:
{rand.nextRangeF(0.f, w), rand.nextRangeF(0.f, h)},
{rand.nextRangeF(0.f, w), rand.nextRangeF(0.f, h)}
};
- for(int edgeType = 0; edgeType < kGrProcessorEdgeTypeCnt; ++edgeType) {
- sk_sp<GrGeometryProcessor> gp;
- GrPrimitiveEdgeType et = (GrPrimitiveEdgeType)edgeType;
- gp = GrCubicEffect::Make(color, SkMatrix::I(), et, *context->caps());
- if (!gp) {
- continue;
- }
+ for(GrPrimitiveEdgeType edgeType : {kFillBW_GrProcessorEdgeType,
+ kFillAA_GrProcessorEdgeType,
+ kHairlineAA_GrProcessorEdgeType}) {
SkScalar x = col * w;
SkScalar y = row * h;
SkPoint controlPts[] = {
@@ -193,13 +172,16 @@ protected:
GrPaint grPaint;
grPaint.setXPFactory(GrPorterDuffXPFactory::Get(SkBlendMode::kSrc));
- SkScalar sign = 1.0f;
- if (c == loopIndex && cnt != 3) {
- sign = -1.0f;
+ bool flipKL = (c == loopIndex && cnt != 3);
+ sk_sp<GrGeometryProcessor> gp = GrCubicEffect::Make(color, SkMatrix::I(), klm,
+ flipKL, edgeType,
+ *context->caps());
+ if (!gp) {
+ break;
}
std::unique_ptr<GrLegacyMeshDrawOp> op =
- BezierCubicOrConicTestOp::Make(gp, bounds, color, klm, sign);
+ BezierCubicTestOp::Make(std::move(gp), bounds, color);
renderTargetContext->priv().testingOnly_addLegacyMeshDrawOp(
std::move(grPaint), GrAAType::kNone, std::move(op));
@@ -219,6 +201,59 @@ private:
//////////////////////////////////////////////////////////////////////////////
+class BezierConicTestOp : public GrTestMeshDrawOp {
+public:
+ DEFINE_OP_CLASS_ID
+
+ const char* name() const override { return "BezierConicTestOp"; }
+
+ static std::unique_ptr<GrLegacyMeshDrawOp> Make(sk_sp<GrGeometryProcessor> gp,
+ const SkRect& rect, GrColor color,
+ const SkMatrix& klm) {
+ return std::unique_ptr<GrLegacyMeshDrawOp>(new BezierConicTestOp(gp, rect, color, klm));
+ }
+
+private:
+ BezierConicTestOp(sk_sp<GrGeometryProcessor> gp, const SkRect& rect, GrColor color,
+ const SkMatrix& klm)
+ : INHERITED(ClassID(), rect, color)
+ , fKLM(klm)
+ , fRect(rect)
+ , fGeometryProcessor(std::move(gp)) {
+ }
+ struct Vertex {
+ SkPoint fPosition;
+ float fKLM[4]; // The last value is ignored. The effect expects a vec4f.
+ };
+
+ void onPrepareDraws(Target* target) const override {
+ QuadHelper helper;
+ size_t vertexStride = fGeometryProcessor->getVertexStride();
+ SkASSERT(vertexStride == sizeof(Vertex));
+ Vertex* verts = reinterpret_cast<Vertex*>(helper.init(target, vertexStride, 1));
+ if (!verts) {
+ return;
+ }
+ verts[0].fPosition.setRectFan(fRect.fLeft, fRect.fTop, fRect.fRight, fRect.fBottom,
+ sizeof(Vertex));
+ for (int v = 0; v < 4; ++v) {
+ SkScalar pt3[3] = {verts[v].fPosition.x(), verts[v].fPosition.y(), 1.f};
+ fKLM.mapHomogeneousPoints(verts[v].fKLM, pt3, 1);
+ }
+ helper.recordDraw(target, fGeometryProcessor.get(), this->pipeline());
+ }
+
+ SkMatrix fKLM;
+ SkRect fRect;
+ sk_sp<GrGeometryProcessor> fGeometryProcessor;
+
+ static constexpr int kVertsPerCubic = 4;
+ static constexpr int kIndicesPerCubic = 6;
+
+ typedef GrTestMeshDrawOp INHERITED;
+};
+
+
/**
* This GM directly exercises effects that draw Bezier curves in the GPU backend.
*/
@@ -332,7 +367,7 @@ protected:
grPaint.setXPFactory(GrPorterDuffXPFactory::Get(SkBlendMode::kSrc));
std::unique_ptr<GrLegacyMeshDrawOp> op =
- BezierCubicOrConicTestOp::Make(gp, bounds, color, klm, 1.f);
+ BezierConicTestOp::Make(gp, bounds, color, klm);
renderTargetContext->priv().testingOnly_addLegacyMeshDrawOp(
std::move(grPaint), GrAAType::kNone, std::move(op));
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index 17ff43cb8b..e140286e15 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -531,38 +531,6 @@ int SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) {
return count + 1;
}
-// See "Resolution Independent Curve Rendering using Programmable Graphics Hardware"
-// https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
-// discr(I) = 3*d2^2 - 4*d1*d3
-// Classification:
-// d1 != 0, discr(I) > 0 Serpentine
-// d1 != 0, discr(I) < 0 Loop
-// d1 != 0, discr(I) = 0 Cusp (with inflection at infinity)
-// d1 = 0, d2 != 0 Cusp (with cusp at infinity)
-// d1 = d2 = 0, d3 != 0 Quadratic
-// d1 = d2 = d3 = 0 Line or Point
-static SkCubicType classify_cubic(SkScalar d[4]) {
- if (!SkScalarNearlyZero(d[1])) {
- d[0] = 3 * d[2] * d[2] - 4 * d[1] * d[3];
- if (d[0] > 0) {
- return SkCubicType::kSerpentine;
- } else if (d[0] < 0) {
- return SkCubicType::kLoop;
- } else {
- SkASSERT(0 == d[0]); // Detect NaN.
- return SkCubicType::kLocalCusp;
- }
- } else {
- if (!SkScalarNearlyZero(d[2])) {
- return SkCubicType::kInfiniteCusp;
- } else if (!SkScalarNearlyZero(d[3])) {
- return SkCubicType::kQuadratic;
- } else {
- return SkCubicType::kLineOrPoint;
- }
- }
-}
-
// Assumes the third component of points is 1.
// Calcs p0 . (p1 x p2)
static SkScalar calc_dot_cross_cubic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
@@ -586,26 +554,118 @@ static void calc_cubic_inflection_func(const SkPoint p[4], SkScalar d[4]) {
SkScalar a2 = calc_dot_cross_cubic(p[1], p[0], p[3]);
SkScalar a3 = calc_dot_cross_cubic(p[2], p[1], p[0]);
- // need to scale a's or values in later calculations will grow to high
- SkScalar max = SkScalarAbs(a1);
- max = SkMaxScalar(max, SkScalarAbs(a2));
- max = SkMaxScalar(max, SkScalarAbs(a3));
- if (0 != max) {
- max = 1.f/max;
- a1 = a1 * max;
- a2 = a2 * max;
- a3 = a3 * max;
- }
-
d[3] = 3.f * a3;
d[2] = d[3] - a2;
d[1] = d[2] - a2 + a1;
d[0] = 0;
}
-SkCubicType SkClassifyCubic(const SkPoint src[4], SkScalar d[4]) {
- calc_cubic_inflection_func(src, d);
- return classify_cubic(d);
+static void normalize_t_s(float t[], float s[], int count) {
+ // Keep the exponents at or below zero to avoid overflow down the road.
+ for (int i = 0; i < count; ++i) {
+ SkASSERT(0 != s[i]);
+ union { float value; int32_t bits; } tt, ss, norm;
+ tt.value = t[i];
+ ss.value = s[i];
+ int32_t expT = ((tt.bits >> 23) & 0xff) - 127,
+ expS = ((ss.bits >> 23) & 0xff) - 127;
+ int32_t expNorm = -SkTMax(expT, expS) + 127;
+ SkASSERT(expNorm > 0 && expNorm < 255); // ensure we have a valid non-zero exponent.
+ norm.bits = expNorm << 23;
+ t[i] *= norm.value;
+ s[i] *= norm.value;
+ }
+}
+
+static void sort_and_orient_t_s(SkScalar t[2], SkScalar s[2]) {
+ // This copysign/abs business orients the implicit function so positive values are always on the
+ // "left" side of the curve.
+ t[1] = -SkScalarCopySign(t[1], t[1] * s[1]);
+ s[1] = -SkScalarAbs(s[1]);
+
+ // Ensure t[0]/s[0] <= t[1]/s[1] (s[1] is negative from above).
+ if (SkScalarCopySign(s[1], s[0]) * t[0] > -SkScalarAbs(s[0]) * t[1]) {
+ std::swap(t[0], t[1]);
+ std::swap(s[0], s[1]);
+ }
+}
+
+// See "Resolution Independent Curve Rendering using Programmable Graphics Hardware"
+// https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
+// discr(I) = 3*d2^2 - 4*d1*d3
+// Classification:
+// d1 != 0, discr(I) > 0 Serpentine
+// d1 != 0, discr(I) < 0 Loop
+// d1 != 0, discr(I) = 0 Cusp (with inflection at infinity)
+// d1 = 0, d2 != 0 Cusp (with cusp at infinity)
+// d1 = d2 = 0, d3 != 0 Quadratic
+// d1 = d2 = d3 = 0 Line or Point
+static SkCubicType classify_cubic(const SkScalar d[4], SkScalar t[2], SkScalar s[2]) {
+ SkScalar tolerance = SkTMax(SkScalarAbs(d[1]), SkScalarAbs(d[2]));
+ tolerance = SkTMax(tolerance, SkScalarAbs(d[3]));
+ tolerance = tolerance * 1e-5;
+ if (!SkScalarNearlyZero(d[1], tolerance)) {
+ const SkScalar discr = 3 * d[2] * d[2] - 4 * d[1] * d[3];
+ if (discr > 0) {
+ if (t && s) {
+ const SkScalar q = 3 * d[2] + SkScalarCopySign(SkScalarSqrt(3 * discr), d[2]);
+ t[0] = q;
+ s[0] = 6 * d[1];
+ t[1] = 2 * d[3];
+ s[1] = q;
+ normalize_t_s(t, s, 2);
+ sort_and_orient_t_s(t, s);
+ }
+ return SkCubicType::kSerpentine;
+ } else if (discr < 0) {
+ if (t && s) {
+ const SkScalar q = d[2] + SkScalarCopySign(SkScalarSqrt(-discr), d[2]);
+ t[0] = q;
+ s[0] = 2 * d[1];
+ t[1] = 2 * (d[2] * d[2] - d[3] * d[1]);
+ s[1] = d[1] * q;
+ normalize_t_s(t, s, 2);
+ sort_and_orient_t_s(t, s);
+ }
+ return SkCubicType::kLoop;
+ } else {
+ SkASSERT(0 == discr); // Detect NaN.
+ if (t && s) {
+ t[0] = d[2];
+ s[0] = 2 * d[1];
+ normalize_t_s(t, s, 1);
+ t[1] = t[0];
+ s[1] = s[0];
+ sort_and_orient_t_s(t, s);
+ }
+ return SkCubicType::kLocalCusp;
+ }
+ } else {
+ if (!SkScalarNearlyZero(d[2], tolerance)) {
+ if (t && s) {
+ t[0] = d[3];
+ s[0] = 3 * d[2];
+ normalize_t_s(t, s, 1);
+ t[1] = 1;
+ s[1] = 0; // infinity
+ }
+ return SkCubicType::kCuspAtInfinity;
+ } else {
+ if (t && s) {
+ t[0] = t[1] = 1;
+ s[0] = s[1] = 0; // infinity
+ }
+ return !SkScalarNearlyZero(d[3], tolerance) ? SkCubicType::kQuadratic
+ : SkCubicType::kLineOrPoint;
+ }
+ }
+}
+
+SkCubicType SkClassifyCubic(const SkPoint src[4], SkScalar t[2], SkScalar s[2], SkScalar d[4]) {
+ SkScalar localD[4];
+ SkScalar* dd = d ? d : localD;
+ calc_cubic_inflection_func(src, dd);
+ return classify_cubic(dd, t, s);
}
template <typename T> void bubble_sort(T array[], int count) {
diff --git a/src/core/SkGeometry.h b/src/core/SkGeometry.h
index 91b4d2d895..ef789a3bf3 100644
--- a/src/core/SkGeometry.h
+++ b/src/core/SkGeometry.h
@@ -161,23 +161,29 @@ bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]);
enum class SkCubicType {
kSerpentine,
kLoop,
- kLocalCusp, // Cusp at a non-infinite parameter value with an inflection at t=infinity.
- kInfiniteCusp, // Cusp with a cusp at t=infinity and a local inflection.
+ kLocalCusp, // Cusp at a non-infinite parameter value with an inflection at t=infinity.
+ kCuspAtInfinity, // Cusp with a cusp at t=infinity and a local inflection.
kQuadratic,
kLineOrPoint
};
/** Returns the cubic classification.
- d[] is filled with the cubic inflection function coefficients. Furthermore, since d0 is always
- zero for integral curves, if the cubic type is kSerpentine, kLoop, or kLocalCusp then d[0] will
- instead contain the cubic discriminant: 3*d2^2 - 4*d1*d3.
+ t[],s[] are set to the two homogeneous parameter values at which points the lines L & M
+ intersect with K, sorted from smallest to largest and oriented so positive values of the
+ implicit are on the "left" side. For a serpentine curve they are the inflection points. For a
+ loop they are the double point. For a local cusp, they are both equal and denote the cusp point.
+ For a cusp at an infinite parameter value, one will be the local inflection point and the other
+ +inf (t,s = 1,0). If the curve is degenerate (i.e. quadratic or linear) they are both set to a
+ parameter value of +inf (t,s = 1,0).
+
+ d[] is filled with the cubic inflection function coefficients. See "Resolution Independent
+ Curve Rendering using Programmable Graphics Hardware", 4.2 Curve Categorization:
- See "Resolution Independent Curve Rendering using Programmable Graphics Hardware",
- 4.2 Curve Categorization
https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
*/
-SkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar d[4]);
+SkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar t[2] = nullptr, SkScalar s[2] = nullptr,
+ SkScalar d[4] = nullptr);
///////////////////////////////////////////////////////////////////////////////
diff --git a/src/gpu/GrPathUtils.cpp b/src/gpu/GrPathUtils.cpp
index 91a48f7b6b..d5a237c361 100644
--- a/src/gpu/GrPathUtils.cpp
+++ b/src/gpu/GrPathUtils.cpp
@@ -8,7 +8,6 @@
#include "GrPathUtils.h"
#include "GrTypes.h"
-#include "SkGeometry.h"
#include "SkMathPriv.h"
static const int MAX_POINTS_PER_CURVE = 1 << 10;
@@ -687,8 +686,8 @@ static void calc_loop_klm(const SkPoint pts[4], SkScalar td, SkScalar sd, SkScal
SkMatrix CIT;
int skipCol = calc_inverse_transpose_power_basis_matrix(pts, &CIT);
- const SkScalar tesd = te * sd;
const SkScalar tdse = td * se;
+ const SkScalar tesd = te * sd;
SkMatrix klmCoeffs;
int col = 0;
@@ -799,108 +798,55 @@ static void calc_line_klm(const SkPoint pts[4], SkMatrix* klm) {
-nx, -ny, k);
}
+SkCubicType GrPathUtils::getCubicKLM(const SkPoint src[4], SkMatrix* klm, SkScalar t[2],
+ SkScalar s[2]) {
+ SkScalar d[4];
+ SkCubicType type = SkClassifyCubic(src, t, s, d);
+ switch (type) {
+ case SkCubicType::kSerpentine:
+ calc_serp_klm(src, t[0], s[0], t[1], s[1], klm);
+ break;
+ case SkCubicType::kLoop:
+ calc_loop_klm(src, t[0], s[0], t[1], s[1], klm);
+ break;
+ case SkCubicType::kLocalCusp:
+ calc_serp_klm(src, t[0], s[0], t[1], s[1], klm);
+ break;
+ case SkCubicType::kCuspAtInfinity:
+ calc_inf_cusp_klm(src, t[0], s[0], klm);
+ break;
+ case SkCubicType::kQuadratic:
+ calc_quadratic_klm(src, d[3], klm);
+ break;
+ case SkCubicType::kLineOrPoint:
+ calc_line_klm(src, klm);
+ break;
+ }
+
+ return type;
+}
+
int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
int* loopIndex) {
- // Variables to store the two parametric values at the loop double point.
- SkScalar t1 = 0, t2 = 0;
-
- // Homogeneous parametric values at the loop double point.
- SkScalar td, sd, te, se;
-
- SkScalar d[4];
- SkCubicType cType = SkClassifyCubic(src, d);
-
- int chop_count = 0;
- if (SkCubicType::kLoop == cType) {
- SkASSERT(d[0] < 0);
- const SkScalar q = d[2] + SkScalarCopySign(SkScalarSqrt(-d[0]), d[2]);
- td = q;
- sd = 2 * d[1];
- te = 2 * (d[2] * d[2] - d[3] * d[1]);
- se = d[1] * q;
-
- t1 = td / sd;
- t2 = te / se;
- // need to have t values sorted since this is what is expected by SkChopCubicAt
- if (t1 > t2) {
- SkTSwap(t1, t2);
- }
+ SkSTArray<2, SkScalar> chops;
+ *loopIndex = -1;
- SkScalar chop_ts[2];
- if (t1 > 0.f && t1 < 1.f) {
- chop_ts[chop_count++] = t1;
- }
- if (t2 > 0.f && t2 < 1.f) {
- chop_ts[chop_count++] = t2;
- }
- if(dst) {
- SkChopCubicAt(src, dst, chop_ts, chop_count);
- }
- } else {
- if (dst) {
- memcpy(dst, src, sizeof(SkPoint) * 4);
- }
- }
+ SkScalar t[2], s[2];
+ if (SkCubicType::kLoop == GrPathUtils::getCubicKLM(src, klm, t, s)) {
+ t[0] /= s[0];
+ t[1] /= s[1];
+ SkASSERT(t[0] <= t[1]); // Technically t0 != t1 in a loop, but there may be FP error.
- if (loopIndex) {
- if (2 == chop_count) {
+ if (t[0] > 0 && t[0] < 1) {
+ chops.push_back(t[0]);
*loopIndex = 1;
- } else if (1 == chop_count) {
- if (t1 < 0.f) {
- *loopIndex = 0;
- } else {
- *loopIndex = 1;
- }
- } else {
- if (t1 < 0.f && t2 > 1.f) {
- *loopIndex = 0;
- } else {
- *loopIndex = -1;
- }
+ }
+ if (t[1] > 0 && t[1] < 1) {
+ chops.push_back(t[1]);
+ *loopIndex = chops.count() - 1;
}
}
- if (klm) {
- switch (cType) {
- case SkCubicType::kSerpentine: {
- SkASSERT(d[0] >= 0);
- const SkScalar q = 3 * d[2] + SkScalarCopySign(SkScalarSqrt(3 * d[0]), d[2]);
- const SkScalar tl = q;
- const SkScalar sl = 6 * d[1];
- const SkScalar tm = 2 * d[3];
- const SkScalar sm = q;
- // This copysign/abs business orients the implicit function so positive values are
- // always on the "left" side of the curve.
- calc_serp_klm(src, tl, sl, -SkScalarCopySign(tm, tm * sm), -SkScalarAbs(sm), klm);
- break;
- }
- case SkCubicType::kLocalCusp: {
- SkASSERT(0 == d[0]);
- const SkScalar t = d[2];
- const SkScalar s = 2 * d[1];
- // This copysign/abs business orients the implicit function so positive values are
- // always on the "left" side of the curve.
- calc_serp_klm(src, t, s, -SkScalarCopySign(t, t * s), -SkScalarAbs(s), klm);
- break;
- }
- case SkCubicType::kLoop:
- // This copysign/abs business orients the implicit function so positive values are
- // always on the "left" side of the curve.
- calc_loop_klm(src, td, sd, -SkScalarCopySign(te, te * se), -SkScalarAbs(se), klm);
- break;
- case SkCubicType::kInfiniteCusp: {
- const SkScalar tn = d[3];
- const SkScalar sn = 3 * d[2];
- calc_inf_cusp_klm(src, tn, sn, klm);
- break;
- }
- case SkCubicType::kQuadratic:
- calc_quadratic_klm(src, d[3], klm);
- break;
- case SkCubicType::kLineOrPoint:
- calc_line_klm(src, klm);
- break;
- };
- }
- return chop_count + 1;
+ SkChopCubicAt(src, dst, chops.begin(), chops.count());
+ return chops.count() + 1;
}
diff --git a/src/gpu/GrPathUtils.h b/src/gpu/GrPathUtils.h
index fdfd375427..35f94d0329 100644
--- a/src/gpu/GrPathUtils.h
+++ b/src/gpu/GrPathUtils.h
@@ -8,6 +8,7 @@
#ifndef GrPathUtils_DEFINED
#define GrPathUtils_DEFINED
+#include "SkGeometry.h"
#include "SkRect.h"
#include "SkPathPriv.h"
#include "SkTArray.h"
@@ -123,6 +124,30 @@ namespace GrPathUtils {
SkPathPriv::FirstDirection dir,
SkTArray<SkPoint, true>* quads);
+ // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the
+ // curve (when facing in the direction of increasing parameter values) will be the area that
+ // satisfies:
+ //
+ // k^3 < l*m
+ //
+ // Output:
+ //
+ // klm: Holds the linear functionals K,L,M as row vectors:
+ //
+ // | ..K.. | | x | | k |
+ // | ..L.. | * | y | == | l |
+ // | ..M.. | | 1 | | m |
+ //
+ // NOTE: the KLM lines are calculated in the same space as the input control points. If you
+ // transform the points the lines will also need to be transformed. This can be done by mapping
+ // the lines with the inverse-transpose of the matrix used to map the points.
+ //
+ // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M
+ // intersect with K (See SkClassifyCubic).
+ //
+ // Returns the cubic's classification.
+ SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, SkScalar t[2], SkScalar s[2]);
+
// Chops the cubic bezier passed in by src, at the double point (intersection point)
// if the curve is a cubic loop. If it is a loop, there will be two parametric values for
// the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1.
@@ -132,32 +157,20 @@ namespace GrPathUtils {
// Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics,
// dst[0..3] and dst[3..6] if dst is not nullptr
// Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic,
- // dst[0..3] if dst is not nullptr
- //
- // Optional KLM Calculation:
- // The function can also return the KLM linear functionals for the cubic implicit form of
- // k^3 - lm. This can be shared by all chopped cubics.
+ // src[0..3]
//
// Output:
//
- // klm: Holds the linear functionals K,L,M as row vectors:
- //
- // | ..K.. | | x | | k |
- // | ..L.. | * | y | == | l |
- // | ..M.. | | 1 | | m |
+ // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().)
//
// loopIndex: This value will tell the caller which of the chopped sections (if any) are the
// actual loop. A value of -1 means there is no loop section. The caller can then use
// this value to decide how/if they want to flip the orientation of this section.
// The flip should be done by negating the k and l values as follows:
//
- // KLM.postScale(-1, -1)
- //
- // Notice that the KLM lines are calculated in the same space as the input control points.
- // If you transform the points the lines will also need to be transformed. This can be done
- // by mapping the lines with the inverse-transpose of the matrix used to map the points.
- int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = nullptr,
- SkMatrix* klm = nullptr, int* loopIndex = nullptr);
+ // KLM.postScale(-1, -1)
+ int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
+ int* loopIndex);
// When tessellating curved paths into linear segments, this defines the maximum distance
// in screen space which a segment may deviate from the mathmatically correct value.
diff --git a/src/gpu/effects/GrBezierEffect.cpp b/src/gpu/effects/GrBezierEffect.cpp
index 58243ea635..54a2e8576e 100644
--- a/src/gpu/effects/GrBezierEffect.cpp
+++ b/src/gpu/effects/GrBezierEffect.cpp
@@ -499,21 +499,31 @@ public:
pdman.setMatrix3f(fViewMatrixUniform, viewMatrix);
}
+ if (!fDevKLMMatrix.cheapEqualTo(ce.devKLMMatrix())) {
+ fDevKLMMatrix = ce.devKLMMatrix();
+ float devKLMMatrix[3 * 3];
+ GrGLSLGetMatrix<3>(devKLMMatrix, fDevKLMMatrix);
+ pdman.setMatrix3f(fDevKLMUniform, devKLMMatrix);
+ }
+
if (ce.color() != fColor) {
float c[4];
GrColorToRGBAFloat(ce.color(), c);
pdman.set4fv(fColorUniform, 1, c);
fColor = ce.color();
}
+
this->setTransformDataHelper(SkMatrix::I(), pdman, &transformIter);
}
private:
SkMatrix fViewMatrix;
+ SkMatrix fDevKLMMatrix;
GrColor fColor;
GrPrimitiveEdgeType fEdgeType;
UniformHandle fColorUniform;
UniformHandle fViewMatrixUniform;
+ UniformHandle fDevKLMUniform;
typedef GrGLSLGeometryProcessor INHERITED;
};
@@ -533,10 +543,6 @@ void GrGLCubicEffect::onEmitCode(EmitArgs& args, GrGPArgs* gpArgs) {
// emit attributes
varyingHandler->emitAttributes(gp);
- GrGLSLVertToFrag v(kVec4f_GrSLType);
- varyingHandler->addVarying("CubicCoeffs", &v, kHigh_GrSLPrecision);
- vertBuilder->codeAppendf("%s = %s;", v.vsOut(), gp.inCubicCoeffs()->fName);
-
GrGLSLPPFragmentBuilder* fragBuilder = args.fFragBuilder;
// Setup pass through color
if (!gp.colorIgnored()) {
@@ -551,6 +557,30 @@ void GrGLCubicEffect::onEmitCode(EmitArgs& args, GrGPArgs* gpArgs) {
gp.viewMatrix(),
&fViewMatrixUniform);
+ // Setup KLM
+ const char* devkLMMatrixName;
+ fDevKLMUniform = uniformHandler->addUniform(kVertex_GrShaderFlag, kMat33f_GrSLType,
+ kHigh_GrSLPrecision, "KLM", &devkLMMatrixName);
+ GrGLSLVertToFrag v(kVec3f_GrSLType);
+ varyingHandler->addVarying("CubicCoeffs", &v, kHigh_GrSLPrecision);
+ vertBuilder->codeAppendf("%s = %s * vec3(%s, 1);",
+ v.vsOut(), devkLMMatrixName, gpArgs->fPositionVar.c_str());
+
+
+ GrGLSLVertToFrag gradCoeffs(kVec4f_GrSLType);
+ if (kFillAA_GrProcessorEdgeType == fEdgeType || kHairlineAA_GrProcessorEdgeType == fEdgeType) {
+ varyingHandler->addVarying("GradCoeffs", &gradCoeffs, kHigh_GrSLPrecision);
+ vertBuilder->codeAppendf("highp float k = %s[0], l = %s[1], m = %s[2];",
+ v.vsOut(), v.vsOut(), v.vsOut());
+ vertBuilder->codeAppendf("highp vec2 gk = vec2(%s[0][0], %s[1][0]), "
+ "gl = vec2(%s[0][1], %s[1][1]), "
+ "gm = vec2(%s[0][2], %s[1][2]);",
+ devkLMMatrixName, devkLMMatrixName, devkLMMatrixName,
+ devkLMMatrixName, devkLMMatrixName, devkLMMatrixName);
+ vertBuilder->codeAppendf("%s = vec4(3 * k * gk, -m * gl - l * gm);",
+ gradCoeffs.vsOut());
+ }
+
// emit transforms with position
this->emitTransforms(vertBuilder,
varyingHandler,
@@ -561,42 +591,23 @@ void GrGLCubicEffect::onEmitCode(EmitArgs& args, GrGPArgs* gpArgs) {
GrShaderVar edgeAlpha("edgeAlpha", kFloat_GrSLType, 0, kHigh_GrSLPrecision);
- GrShaderVar dklmdx("dklmdx", kVec3f_GrSLType, 0, kHigh_GrSLPrecision);
- GrShaderVar dklmdy("dklmdy", kVec3f_GrSLType, 0, kHigh_GrSLPrecision);
- GrShaderVar dfdx("dfdx", kFloat_GrSLType, 0, kHigh_GrSLPrecision);
- GrShaderVar dfdy("dfdy", kFloat_GrSLType, 0, kHigh_GrSLPrecision);
GrShaderVar gF("gF", kVec2f_GrSLType, 0, kHigh_GrSLPrecision);
- GrShaderVar gFM("gFM", kFloat_GrSLType, 0, kHigh_GrSLPrecision);
GrShaderVar func("func", kFloat_GrSLType, 0, kHigh_GrSLPrecision);
fragBuilder->declAppend(edgeAlpha);
- fragBuilder->declAppend(dklmdx);
- fragBuilder->declAppend(dklmdy);
- fragBuilder->declAppend(dfdx);
- fragBuilder->declAppend(dfdy);
fragBuilder->declAppend(gF);
- fragBuilder->declAppend(gFM);
fragBuilder->declAppend(func);
switch (fEdgeType) {
case kHairlineAA_GrProcessorEdgeType: {
- fragBuilder->codeAppendf("%s = dFdx(%s.xyz);", dklmdx.c_str(), v.fsIn());
- fragBuilder->codeAppendf("%s = dFdy(%s.xyz);", dklmdy.c_str(), v.fsIn());
- fragBuilder->codeAppendf("%s = 3.0 * %s.x * %s.x * %s.x - %s.y * %s.z - %s.z * %s.y;",
- dfdx.c_str(), v.fsIn(), v.fsIn(), dklmdx.c_str(), v.fsIn(),
- dklmdx.c_str(), v.fsIn(), dklmdx.c_str());
- fragBuilder->codeAppendf("%s = 3.0 * %s.x * %s.x * %s.x - %s.y * %s.z - %s.z * %s.y;",
- dfdy.c_str(), v.fsIn(), v.fsIn(), dklmdy.c_str(), v.fsIn(),
- dklmdy.c_str(), v.fsIn(), dklmdy.c_str());
- fragBuilder->codeAppendf("%s = vec2(%s, %s);", gF.c_str(), dfdx.c_str(), dfdy.c_str());
- fragBuilder->codeAppendf("%s = sqrt(dot(%s, %s));",
- gFM.c_str(), gF.c_str(), gF.c_str());
+ fragBuilder->codeAppendf("%s = %s.x * %s.xy + %s.zw;",
+ gF.c_str(), v.fsIn(), gradCoeffs.fsIn(), gradCoeffs.fsIn());
fragBuilder->codeAppendf("%s = %s.x * %s.x * %s.x - %s.y * %s.z;",
func.c_str(), v.fsIn(), v.fsIn(),
v.fsIn(), v.fsIn(), v.fsIn());
fragBuilder->codeAppendf("%s = abs(%s);", func.c_str(), func.c_str());
- fragBuilder->codeAppendf("%s = %s / %s;",
- edgeAlpha.c_str(), func.c_str(), gFM.c_str());
+ fragBuilder->codeAppendf("%s = %s * inversesqrt(dot(%s, %s));",
+ edgeAlpha.c_str(), func.c_str(), gF.c_str(), gF.c_str());
fragBuilder->codeAppendf("%s = max(1.0 - %s, 0.0);",
edgeAlpha.c_str(), edgeAlpha.c_str());
// Add line below for smooth cubic ramp
@@ -606,23 +617,13 @@ void GrGLCubicEffect::onEmitCode(EmitArgs& args, GrGPArgs* gpArgs) {
break;
}
case kFillAA_GrProcessorEdgeType: {
- fragBuilder->codeAppendf("%s = dFdx(%s.xyz);", dklmdx.c_str(), v.fsIn());
- fragBuilder->codeAppendf("%s = dFdy(%s.xyz);", dklmdy.c_str(), v.fsIn());
- fragBuilder->codeAppendf("%s ="
- "3.0 * %s.x * %s.x * %s.x - %s.y * %s.z - %s.z * %s.y;",
- dfdx.c_str(), v.fsIn(), v.fsIn(), dklmdx.c_str(), v.fsIn(),
- dklmdx.c_str(), v.fsIn(), dklmdx.c_str());
- fragBuilder->codeAppendf("%s = 3.0 * %s.x * %s.x * %s.x - %s.y * %s.z - %s.z * %s.y;",
- dfdy.c_str(), v.fsIn(), v.fsIn(), dklmdy.c_str(), v.fsIn(),
- dklmdy.c_str(), v.fsIn(), dklmdy.c_str());
- fragBuilder->codeAppendf("%s = vec2(%s, %s);", gF.c_str(), dfdx.c_str(), dfdy.c_str());
- fragBuilder->codeAppendf("%s = sqrt(dot(%s, %s));",
- gFM.c_str(), gF.c_str(), gF.c_str());
+ fragBuilder->codeAppendf("%s = %s.x * %s.xy + %s.zw;",
+ gF.c_str(), v.fsIn(), gradCoeffs.fsIn(), gradCoeffs.fsIn());
fragBuilder->codeAppendf("%s = %s.x * %s.x * %s.x - %s.y * %s.z;",
func.c_str(),
v.fsIn(), v.fsIn(), v.fsIn(), v.fsIn(), v.fsIn());
- fragBuilder->codeAppendf("%s = %s / %s;",
- edgeAlpha.c_str(), func.c_str(), gFM.c_str());
+ fragBuilder->codeAppendf("%s = %s * inversesqrt(dot(%s, %s));",
+ edgeAlpha.c_str(), func.c_str(), gF.c_str(), gF.c_str());
fragBuilder->codeAppendf("%s = clamp(0.5 - %s, 0.0, 1.0);",
edgeAlpha.c_str(), edgeAlpha.c_str());
// Add line below for smooth cubic ramp
@@ -667,15 +668,15 @@ GrGLSLPrimitiveProcessor* GrCubicEffect::createGLSLInstance(const GrShaderCaps&)
return new GrGLCubicEffect(*this);
}
-GrCubicEffect::GrCubicEffect(GrColor color, const SkMatrix& viewMatrix,
- GrPrimitiveEdgeType edgeType)
+GrCubicEffect::GrCubicEffect(GrColor color, const SkMatrix& viewMatrix, const SkMatrix&
+ devKLMMatrix, GrPrimitiveEdgeType edgeType)
: fColor(color)
, fViewMatrix(viewMatrix)
+ , fDevKLMMatrix(devKLMMatrix)
, fEdgeType(edgeType) {
this->initClassID<GrCubicEffect>();
fInPosition = &this->addVertexAttrib("inPosition", kVec2f_GrVertexAttribType,
kHigh_GrSLPrecision);
- fInCubicCoeffs = &this->addVertexAttrib("inCubicCoeffs", kVec4f_GrVertexAttribType);
}
//////////////////////////////////////////////////////////////////////////////
@@ -690,7 +691,8 @@ sk_sp<GrGeometryProcessor> GrCubicEffect::TestCreate(GrProcessorTestData* d) {
static_cast<GrPrimitiveEdgeType>(
d->fRandom->nextULessThan(kGrProcessorEdgeTypeCnt));
gp = GrCubicEffect::Make(GrRandomColor(d->fRandom), GrTest::TestMatrix(d->fRandom),
- edgeType, *d->caps());
+ GrTest::TestMatrix(d->fRandom), d->fRandom->nextBool(), edgeType,
+ *d->caps());
} while (nullptr == gp);
return gp;
}
diff --git a/src/gpu/effects/GrBezierEffect.h b/src/gpu/effects/GrBezierEffect.h
index 3a130ec187..3a97506396 100644
--- a/src/gpu/effects/GrBezierEffect.h
+++ b/src/gpu/effects/GrBezierEffect.h
@@ -225,24 +225,30 @@ class GrCubicEffect : public GrGeometryProcessor {
public:
static sk_sp<GrGeometryProcessor> Make(GrColor color,
const SkMatrix& viewMatrix,
+ const SkMatrix& klm,
+ bool flipKL,
const GrPrimitiveEdgeType edgeType,
const GrCaps& caps) {
+ // Map KLM to something that operates in device space.
+ SkMatrix devKLM;
+ if (!viewMatrix.invert(&devKLM)) {
+ return nullptr;
+ }
+ devKLM.postConcat(klm);
+ if (flipKL) {
+ devKLM.postScale(-1, -1);
+ }
+
switch (edgeType) {
case kFillAA_GrProcessorEdgeType:
- if (!caps.shaderCaps()->shaderDerivativeSupport()) {
- return nullptr;
- }
return sk_sp<GrGeometryProcessor>(
- new GrCubicEffect(color, viewMatrix, kFillAA_GrProcessorEdgeType));
+ new GrCubicEffect(color, viewMatrix, devKLM, kFillAA_GrProcessorEdgeType));
case kHairlineAA_GrProcessorEdgeType:
- if (!caps.shaderCaps()->shaderDerivativeSupport()) {
- return nullptr;
- }
return sk_sp<GrGeometryProcessor>(
- new GrCubicEffect(color, viewMatrix, kHairlineAA_GrProcessorEdgeType));
+ new GrCubicEffect(color, viewMatrix, devKLM, kHairlineAA_GrProcessorEdgeType));
case kFillBW_GrProcessorEdgeType:
return sk_sp<GrGeometryProcessor>(
- new GrCubicEffect(color, viewMatrix, kFillBW_GrProcessorEdgeType));
+ new GrCubicEffect(color, viewMatrix, devKLM, kFillBW_GrProcessorEdgeType));
default:
return nullptr;
}
@@ -253,26 +259,27 @@ public:
const char* name() const override { return "Cubic"; }
inline const Attribute* inPosition() const { return fInPosition; }
- inline const Attribute* inCubicCoeffs() const { return fInCubicCoeffs; }
inline bool isAntiAliased() const { return GrProcessorEdgeTypeIsAA(fEdgeType); }
inline bool isFilled() const { return GrProcessorEdgeTypeIsFill(fEdgeType); }
inline GrPrimitiveEdgeType getEdgeType() const { return fEdgeType; }
GrColor color() const { return fColor; }
bool colorIgnored() const { return GrColor_ILLEGAL == fColor; }
const SkMatrix& viewMatrix() const { return fViewMatrix; }
+ const SkMatrix& devKLMMatrix() const { return fDevKLMMatrix; }
void getGLSLProcessorKey(const GrShaderCaps& caps, GrProcessorKeyBuilder* b) const override;
GrGLSLPrimitiveProcessor* createGLSLInstance(const GrShaderCaps&) const override;
private:
- GrCubicEffect(GrColor, const SkMatrix& viewMatrix, GrPrimitiveEdgeType);
+ GrCubicEffect(GrColor, const SkMatrix& viewMatrix, const SkMatrix& devKLMMatrix,
+ GrPrimitiveEdgeType);
GrColor fColor;
SkMatrix fViewMatrix;
+ SkMatrix fDevKLMMatrix;
GrPrimitiveEdgeType fEdgeType;
const Attribute* fInPosition;
- const Attribute* fInCubicCoeffs;
GR_DECLARE_GEOMETRY_PROCESSOR_TEST;
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index 794e54fdfe..d7b905cdad 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -248,20 +248,13 @@ int SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t) {
if (cubic.monotonicInX() && cubic.monotonicInY()) {
return 0;
}
- SkScalar d[4];
- SkCubicType cubicType = SkClassifyCubic(pointsPtr, d);
+ SkScalar tt[2], ss[2];
+ SkCubicType cubicType = SkClassifyCubic(pointsPtr, tt, ss);
switch (cubicType) {
case SkCubicType::kLoop: {
- // crib code from gpu path utils that finds t values where loop self-intersects
- // use it to find mid of t values which should be a friendly place to chop
- SkASSERT(d[0] < 0);
- const SkScalar q = d[2] + SkScalarCopySign(SkScalarSqrt(-d[0]), d[2]);
- const SkScalar td = q;
- const SkScalar sd = 2 * d[1];
- const SkScalar te = 2 * (d[2] * d[2] - d[3] * d[1]);
- const SkScalar se = d[1] * q;
+ const SkScalar &td = tt[0], &te = tt[1], &sd = ss[0], &se = ss[1];
if (roughly_between(0, td, sd) && roughly_between(0, te, se)) {
- SkASSERT(roughly_between(0, td / sd, 1) && roughly_between(0, te / se, 1));
+ SkASSERT(roughly_between(0, td/sd, 1) && roughly_between(0, te/se, 1));
t[0] = (td * se + te * sd) / (2 * sd * se);
SkASSERT(roughly_between(0, *t, 1));
return (int) (t[0] > 0 && t[0] < 1);
@@ -270,7 +263,7 @@ int SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t) {
// fall through if no t value found
case SkCubicType::kSerpentine:
case SkCubicType::kLocalCusp:
- case SkCubicType::kInfiniteCusp: {
+ case SkCubicType::kCuspAtInfinity: {
double inflectionTs[2];
int infTCount = cubic.findInflections(inflectionTs);
double maxCurvature[3];
diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp
index 66becf304a..6eab71d4fb 100644
--- a/tests/PathOpsCubicIntersectionTest.cpp
+++ b/tests/PathOpsCubicIntersectionTest.cpp
@@ -646,8 +646,7 @@ static void selfOneOff(skiatest::Reporter* reporter, int index) {
c[i] = cubic.fPts[i].asSkPoint();
}
SkScalar loopT[3];
- SkScalar d[4];
- SkCubicType cubicType = SkClassifyCubic(c, d);
+ SkCubicType cubicType = SkClassifyCubic(c);
int breaks = SkDCubic::ComplexBreak(c, loopT);
SkASSERT(breaks < 2);
if (breaks && cubicType == SkCubicType::kLoop) {