aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xbench/BezierBench.cpp101
-rwxr-xr-xgm/beziers.cpp87
-rwxr-xr-xgm/smallarc.cpp54
-rw-r--r--gyp/bench.gypi1
-rw-r--r--gyp/gmslides.gypi2
-rw-r--r--gyp/tests.gypi1
-rw-r--r--samplecode/SampleRotateCircles.cpp199
-rw-r--r--src/core/SkStroke.cpp858
-rw-r--r--src/core/SkStroke.h19
-rw-r--r--src/core/SkStrokeRec.cpp3
-rwxr-xr-xtests/StrokerTest.cpp452
11 files changed, 1740 insertions, 37 deletions
diff --git a/bench/BezierBench.cpp b/bench/BezierBench.cpp
new file mode 100755
index 0000000000..ec83d958bb
--- /dev/null
+++ b/bench/BezierBench.cpp
@@ -0,0 +1,101 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Benchmark.h"
+#include "SkCanvas.h"
+#include "SkPaint.h"
+#include "SkString.h"
+
+struct BezierRec {
+ SkCanvas* fCanvas;
+ SkPaint fPaint;
+ SkPath fQuad;
+ SkPath fCubic;
+};
+
+typedef const char* (*DrawProc)(const BezierRec*, int);
+
+static const char* draw_quad(const BezierRec* rec, int count) {
+ if (rec) {
+ SkCanvas* canvas = rec->fCanvas;
+ const SkPaint& paint = rec->fPaint;
+ const SkPath& path = rec->fQuad;
+ for (int i = 0; i < count; ++i) {
+ canvas->drawPath(path, paint);
+ }
+ }
+ return "quad";
+}
+
+static const char* draw_cubic(const BezierRec* rec, int count) {
+ if (rec) {
+ SkCanvas* canvas = rec->fCanvas;
+ const SkPaint& paint = rec->fPaint;
+ const SkPath& path = rec->fCubic;
+ for (int i = 0; i < count; ++i) {
+ canvas->drawPath(path, paint);
+ }
+ }
+ return "cubic";
+}
+
+class BezierBench : public Benchmark {
+ SkString fName;
+ SkPaint::Cap fCap;
+ SkPaint::Join fJoin;
+ BezierRec fRec;
+ DrawProc fProc;
+ SkScalar fWidth;
+public:
+ BezierBench(SkPaint::Cap c, SkPaint::Join j, SkScalar w, DrawProc proc) {
+ static const char* gCapName[] = {
+ "butt", "round", "square"
+ };
+ static const char* gJoinName[] = {
+ "miter", "round", "bevel"
+ };
+
+ fCap = c;
+ fJoin = j;
+ fProc = proc;
+ fWidth = SkIntToScalar(w);
+ fName.printf("draw_stroke_bezier_%s_%s_%s_%g", proc(NULL, 0), gCapName[c], gJoinName[j], w);
+
+ fRec.fQuad.moveTo(20, 20);
+ fRec.fQuad.quadTo(60, 20, 60, 60);
+ fRec.fQuad.quadTo(20, 60, 20, 100);
+ fRec.fCubic.moveTo(20, 20);
+ fRec.fCubic.cubicTo(40, 20, 60, 40, 60, 60);
+ fRec.fCubic.cubicTo(40, 60, 20, 80, 20, 100);
+ }
+
+protected:
+ virtual const char* onGetName() {
+ return fName.c_str();
+ }
+
+ virtual void onDraw(const int loops, SkCanvas* canvas) {
+ fRec.fCanvas = canvas;
+ this->setupPaint(&fRec.fPaint);
+ fRec.fPaint.setStyle(SkPaint::kStroke_Style);
+ fRec.fPaint.setStrokeCap(fCap);
+ fRec.fPaint.setStrokeJoin(fJoin);
+ fRec.fPaint.setStrokeWidth(fWidth);
+ fProc(&fRec, loops);
+ }
+
+private:
+ typedef Benchmark INHERITED;
+};
+
+DEF_BENCH( return new BezierBench(SkPaint::kButt_Cap, SkPaint::kRound_Join, 2, draw_quad); )
+DEF_BENCH( return new BezierBench(SkPaint::kSquare_Cap, SkPaint::kBevel_Join, 10, draw_quad); )
+DEF_BENCH( return new BezierBench(SkPaint::kRound_Cap, SkPaint::kMiter_Join, 50, draw_quad); )
+
+DEF_BENCH( return new BezierBench(SkPaint::kButt_Cap, SkPaint::kRound_Join, 2, draw_cubic); )
+DEF_BENCH( return new BezierBench(SkPaint::kSquare_Cap, SkPaint::kBevel_Join, 10, draw_cubic); )
+DEF_BENCH( return new BezierBench(SkPaint::kRound_Cap, SkPaint::kMiter_Join, 50, draw_cubic); )
diff --git a/gm/beziers.cpp b/gm/beziers.cpp
new file mode 100755
index 0000000000..ac212278cf
--- /dev/null
+++ b/gm/beziers.cpp
@@ -0,0 +1,87 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "gm.h"
+#include "SkRandom.h"
+
+#define W 400
+#define H 400
+#define N 10
+
+static const SkScalar SW = SkIntToScalar(W);
+static const SkScalar SH = SkIntToScalar(H);
+
+static void rnd_quad(SkPath* p, SkPaint* paint, SkLCGRandom& rand) {
+ p->moveTo(rand.nextRangeScalar(0, W), rand.nextRangeScalar(0, H));
+ for (int x = 0; x < 2; ++x) {
+ p->quadTo(rand.nextRangeScalar(W / 4, W), rand.nextRangeScalar(0, H),
+ rand.nextRangeScalar(0, W), rand.nextRangeScalar(H / 4, H));
+ }
+ paint->setColor(rand.nextU());
+ SkScalar width = rand.nextRangeScalar(1, 5);
+ width *= width;
+ paint->setStrokeWidth(width);
+ paint->setAlpha(0xFF);
+}
+
+static void rnd_cubic(SkPath* p, SkPaint* paint, SkLCGRandom& rand) {
+ p->moveTo(rand.nextRangeScalar(0, W), rand.nextRangeScalar(0, H));
+ for (int x = 0; x < 2; ++x) {
+ p->cubicTo(rand.nextRangeScalar(W / 4, W), rand.nextRangeScalar(0, H),
+ rand.nextRangeScalar(0, W), rand.nextRangeScalar(H / 4, H),
+ rand.nextRangeScalar(W / 4, W), rand.nextRangeScalar(H / 4, H));
+ }
+ paint->setColor(rand.nextU());
+ SkScalar width = rand.nextRangeScalar(1, 5);
+ width *= width;
+ paint->setStrokeWidth(width);
+ paint->setAlpha(0xFF);
+}
+
+class BeziersGM : public skiagm::GM {
+public:
+ BeziersGM() {}
+
+protected:
+ virtual uint32_t onGetFlags() const SK_OVERRIDE {
+ return kSkipTiled_Flag;
+ }
+
+ virtual SkString onShortName() {
+ return SkString("beziers");
+ }
+
+ virtual SkISize onISize() {
+ return SkISize::Make(W, H*2);
+ }
+
+ virtual void onDraw(SkCanvas* canvas) {
+ SkPaint paint;
+ paint.setStyle(SkPaint::kStroke_Style);
+ paint.setStrokeWidth(SkIntToScalar(9)/2);
+ paint.setAntiAlias(true);
+
+ SkLCGRandom rand;
+ for (int i = 0; i < N; i++) {
+ SkPath p;
+ rnd_quad(&p, &paint, rand);
+ canvas->drawPath(p, paint);
+ }
+ canvas->translate(0, SH);
+ for (int i = 0; i < N; i++) {
+ SkPath p;
+ rnd_cubic(&p, &paint, rand);
+ canvas->drawPath(p, paint);
+ }
+ }
+
+private:
+ typedef skiagm::GM INHERITED;
+};
+
+static skiagm::GM* F0(void*) { return new BeziersGM; }
+static skiagm::GMRegistry R0(F0);
diff --git a/gm/smallarc.cpp b/gm/smallarc.cpp
new file mode 100755
index 0000000000..c311460e54
--- /dev/null
+++ b/gm/smallarc.cpp
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "gm.h"
+
+namespace skiagm {
+
+// this draws a small arc scaled up
+// see https://code.google.com/p/chromium/issues/detail?id=102411
+// and https://code.google.com/p/skia/issues/detail?id=2769
+class SmallArcGM : public GM {
+public:
+ SmallArcGM() {
+ }
+
+protected:
+
+ virtual SkString onShortName() SK_OVERRIDE {
+ return SkString("smallarc");
+ }
+
+ virtual SkISize onISize() SK_OVERRIDE {
+ return SkISize::Make(762, 762);
+ }
+
+ virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE {
+ SkPaint p;
+ p.setColor(SK_ColorRED);
+ p.setAntiAlias(true);
+ p.setStyle(SkPaint::kStroke_Style);
+ p.setStrokeWidth(120);
+
+ SkPath path;
+ path.moveTo(75, 0);
+ path.cubicTo(33.5, 0, 0, 33.5, 0, 75);
+
+ canvas->translate(-400, -400);
+ canvas->scale(8, 8);
+ canvas->drawPath(path, p);
+ }
+
+private:
+ typedef GM INHERITED;
+};
+
+//////////////////////////////////////////////////////////////////////////////
+
+DEF_GM( return SkNEW(SmallArcGM); )
+
+}
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index c2c8ec90fb..b057e89186 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -24,6 +24,7 @@
'../bench/AAClipBench.cpp',
'../bench/AlternatingColorPatternBench.cpp',
+ '../bench/BezierBench.cpp',
'../bench/BitmapBench.cpp',
'../bench/BitmapRectBench.cpp',
'../bench/BitmapScaleBench.cpp',
diff --git a/gyp/gmslides.gypi b/gyp/gmslides.gypi
index 58bf17742d..6cf4767fb3 100644
--- a/gyp/gmslides.gypi
+++ b/gyp/gmslides.gypi
@@ -20,6 +20,7 @@
'../gm/arithmode.cpp',
'../gm/astcbitmap.cpp',
'../gm/beziereffects.cpp',
+ '../gm/beziers.cpp',
'../gm/bigblurs.cpp',
'../gm/bigmatrix.cpp',
'../gm/bigtext.cpp',
@@ -163,6 +164,7 @@
'../gm/shallowgradient.cpp',
'../gm/simpleaaclip.cpp',
'../gm/skbug1719.cpp',
+ '../gm/smallarc.cpp',
'../gm/stringart.cpp',
'../gm/spritebitmap.cpp',
'../gm/srcmode.cpp',
diff --git a/gyp/tests.gypi b/gyp/tests.gypi
index db87f3f7a4..fc0d69d0bf 100644
--- a/gyp/tests.gypi
+++ b/gyp/tests.gypi
@@ -192,6 +192,7 @@
'../tests/StreamTest.cpp',
'../tests/StringTest.cpp',
'../tests/StrokeTest.cpp',
+ '../tests/StrokerTest.cpp',
'../tests/SurfaceTest.cpp',
'../tests/TArrayTest.cpp',
'../tests/THashCache.cpp',
diff --git a/samplecode/SampleRotateCircles.cpp b/samplecode/SampleRotateCircles.cpp
index f9b32ea417..06350ab5b4 100644
--- a/samplecode/SampleRotateCircles.cpp
+++ b/samplecode/SampleRotateCircles.cpp
@@ -11,6 +11,7 @@
#include "SkRandom.h"
#include "SkRRect.h"
#include "SkColorPriv.h"
+#include "SkStrokerPriv.h"
static void rotateAbout(SkCanvas* canvas, SkScalar degrees,
SkScalar cx, SkScalar cy) {
@@ -177,6 +178,12 @@ static int getOnCurvePoints(const SkPath& path, SkPoint storage[]) {
#include "SkPathMeasure.h"
+struct StrokeTypeButton {
+ SkRect fBounds;
+ char fLabel;
+ bool fEnabled;
+};
+
class TestStrokeView : public SampleView {
enum {
SKELETON_COLOR = 0xFF0000FF,
@@ -187,7 +194,19 @@ class TestStrokeView : public SampleView {
kCount = 9
};
SkPoint fPts[kCount];
+ SkRect fErrorControl;
+ SkRect fWidthControl;
+ StrokeTypeButton fCubicButton;
+ StrokeTypeButton fQuadButton;
+ StrokeTypeButton fRRectButton;
SkScalar fWidth, fDWidth;
+ bool fAnimate;
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+ #define kStrokerErrorMin 0.001f
+ #define kStrokerErrorMax 5
+#endif
+ #define kWidthMin 1
+ #define kWidthMax 100
public:
TestStrokeView() {
this->setBGColor(SK_ColorLTGRAY);
@@ -206,6 +225,14 @@ public:
fWidth = 50;
fDWidth = 0.25f;
+
+ fCubicButton.fLabel = 'C';
+ fCubicButton.fEnabled = true;
+ fQuadButton.fLabel = 'Q';
+ fQuadButton.fEnabled = true;
+ fRRectButton.fLabel = 'R';
+ fRRectButton.fEnabled = true;
+ fAnimate = true;
}
protected:
@@ -217,12 +244,21 @@ protected:
return this->INHERITED::onQuery(evt);
}
+ virtual void onSizeChange() {
+ fErrorControl.setXYWH(this->width() - 100, 30, 30, 400);
+ fWidthControl.setXYWH(this->width() - 50, 30, 30, 400);
+ fCubicButton.fBounds.setXYWH(this->width() - 50, 450, 30, 30);
+ fQuadButton.fBounds.setXYWH(this->width() - 50, 500, 30, 30);
+ fRRectButton.fBounds.setXYWH(this->width() - 50, 550, 30, 30);
+ this->INHERITED::onSizeChange();
+ }
+
void draw_points(SkCanvas* canvas, const SkPath& path, SkColor color,
bool show_lines) {
SkPaint paint;
paint.setColor(color);
paint.setAlpha(0x80);
-
+ paint.setAntiAlias(true);
int n = path.countPoints();
SkAutoSTArray<32, SkPoint> pts(n);
if (show_lines) {
@@ -280,45 +316,95 @@ protected:
draw_points(canvas, fill, WIREFRAME_COLOR, false);
}
+ void draw_button(SkCanvas* canvas, const StrokeTypeButton& button) {
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ paint.setStyle(SkPaint::kStroke_Style);
+ paint.setColor(button.fEnabled ? 0xFF3F0000 : 0x6F3F0000);
+ canvas->drawRect(button.fBounds, paint);
+ paint.setTextSize(25.0f);
+ paint.setColor(button.fEnabled ? 0xFF3F0000 : 0x6F3F0000);
+ paint.setTextAlign(SkPaint::kCenter_Align);
+ paint.setStyle(SkPaint::kFill_Style);
+ canvas->drawText(&button.fLabel, 1, button.fBounds.centerX(), button.fBounds.fBottom - 5,
+ paint);
+ }
+
+ void draw_control(SkCanvas* canvas, const SkRect& bounds, SkScalar value,
+ SkScalar min, SkScalar max, const char* name) {
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ paint.setStyle(SkPaint::kStroke_Style);
+ canvas->drawRect(bounds, paint);
+ SkScalar scale = max - min;
+ SkScalar yPos = bounds.fTop + (value - min) * bounds.height() / scale;
+ paint.setColor(0xFFFF0000);
+ canvas->drawLine(bounds.fLeft - 5, yPos, bounds.fRight + 5, yPos, paint);
+ SkString label;
+ label.printf("%0.3g", value);
+ paint.setColor(0xFF000000);
+ paint.setTextSize(11.0f);
+ paint.setStyle(SkPaint::kFill_Style);
+ canvas->drawText(label.c_str(), label.size(), bounds.fLeft + 5, yPos - 5, paint);
+ paint.setTextSize(13.0f);
+ canvas->drawText(name, strlen(name), bounds.fLeft, bounds.bottom() + 11, paint);
+ }
+
virtual void onDrawContent(SkCanvas* canvas) {
SkPath path;
SkScalar width = fWidth;
- path.moveTo(fPts[0]);
- path.cubicTo(fPts[1], fPts[2], fPts[3]);
- draw_stroke(canvas, path, width);
-
- path.reset();
- path.moveTo(fPts[4]);
- path.quadTo(fPts[5], fPts[6]);
- draw_stroke(canvas, path, width);
-
- SkScalar rad = 32;
- SkRect r;
- r.set(&fPts[7], 2);
- path.reset();
- SkRRect rr;
- rr.setRectXY(r, rad, rad);
- path.addRRect(rr);
- draw_stroke(canvas, path, width);
-
- path.reset();
- SkRRect rr2;
- rr.inset(width/2, width/2, &rr2);
- path.addRRect(rr2, SkPath::kCCW_Direction);
- rr.inset(-width/2, -width/2, &rr2);
- path.addRRect(rr2, SkPath::kCW_Direction);
- SkPaint paint;
- paint.setAntiAlias(true);
- paint.setColor(0x40FF8844);
- canvas->drawPath(path, paint);
+ if (fCubicButton.fEnabled) {
+ path.moveTo(fPts[0]);
+ path.cubicTo(fPts[1], fPts[2], fPts[3]);
+ draw_stroke(canvas, path, width);
+ }
- fWidth += fDWidth;
- if (fDWidth > 0 && fWidth > 100) {
- fDWidth = -fDWidth;
- } else if (fDWidth < 0 && fWidth < 10) {
- fDWidth = -fDWidth;
+ if (fQuadButton.fEnabled) {
+ path.reset();
+ path.moveTo(fPts[4]);
+ path.quadTo(fPts[5], fPts[6]);
+ draw_stroke(canvas, path, width);
}
+
+ if (fRRectButton.fEnabled) {
+ SkScalar rad = 32;
+ SkRect r;
+ r.set(&fPts[7], 2);
+ path.reset();
+ SkRRect rr;
+ rr.setRectXY(r, rad, rad);
+ path.addRRect(rr);
+ draw_stroke(canvas, path, width);
+
+ path.reset();
+ SkRRect rr2;
+ rr.inset(width/2, width/2, &rr2);
+ path.addRRect(rr2, SkPath::kCCW_Direction);
+ rr.inset(-width/2, -width/2, &rr2);
+ path.addRRect(rr2, SkPath::kCW_Direction);
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ paint.setColor(0x40FF8844);
+ canvas->drawPath(path, paint);
+ }
+
+ if (fAnimate) {
+ fWidth += fDWidth;
+ if (fDWidth > 0 && fWidth > kWidthMax) {
+ fDWidth = -fDWidth;
+ } else if (fDWidth < 0 && fWidth < kWidthMin) {
+ fDWidth = -fDWidth;
+ }
+ }
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+ draw_control(canvas, fErrorControl, gDebugStrokerError, kStrokerErrorMin, kStrokerErrorMax,
+ "error");
+#endif
+ draw_control(canvas, fWidthControl, fWidth, kWidthMin, kWidthMax, "width");
+ draw_button(canvas, fQuadButton);
+ draw_button(canvas, fCubicButton);
+ draw_button(canvas, fRRectButton);
this->inval(NULL);
}
@@ -335,14 +421,53 @@ protected:
return new MyClick(this, (int)i);
}
}
+ const SkRect& rectPt = SkRect::MakeXYWH(x, y, 1, 1);
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+ if (fErrorControl.contains(rectPt)) {
+ return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 1);
+ }
+#endif
+ if (fWidthControl.contains(rectPt)) {
+ return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 3);
+ }
+ if (fCubicButton.fBounds.contains(rectPt)) {
+ fCubicButton.fEnabled ^= true;
+ return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 4);
+ }
+ if (fQuadButton.fBounds.contains(rectPt)) {
+ fQuadButton.fEnabled ^= true;
+ return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 5);
+ }
+ if (fRRectButton.fBounds.contains(rectPt)) {
+ fRRectButton.fEnabled ^= true;
+ return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 6);
+ }
return this->INHERITED::onFindClickHandler(x, y, modi);
}
+ static SkScalar MapScreenYtoValue(int y, const SkRect& control, SkScalar min,
+ SkScalar max) {
+ return (SkIntToScalar(y) - control.fTop) / control.height() * (max - min) + min;
+ }
+
virtual bool onClick(Click* click) {
int index = ((MyClick*)click)->fIndex;
- fPts[index].offset(SkIntToScalar(click->fICurr.fX - click->fIPrev.fX),
- SkIntToScalar(click->fICurr.fY - click->fIPrev.fY));
- this->inval(NULL);
+ if (index < (int) SK_ARRAY_COUNT(fPts)) {
+ fPts[index].offset(SkIntToScalar(click->fICurr.fX - click->fIPrev.fX),
+ SkIntToScalar(click->fICurr.fY - click->fIPrev.fY));
+ this->inval(NULL);
+ }
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+ else if (index == (int) SK_ARRAY_COUNT(fPts) + 1) {
+ gDebugStrokerError = MapScreenYtoValue(click->fICurr.fY, fErrorControl,
+ kStrokerErrorMin, kStrokerErrorMax);
+ gDebugStrokerErrorSet = true;
+ }
+#endif
+ else if (index == (int) SK_ARRAY_COUNT(fPts) + 3) {
+ fWidth = MapScreenYtoValue(click->fICurr.fY, fWidthControl, kWidthMin, kWidthMax);
+ fAnimate = fWidth <= kWidthMin;
+ }
return true;
}
diff --git a/src/core/SkStroke.cpp b/src/core/SkStroke.cpp
index 1e4ae79a5e..a9cc6cd60a 100644
--- a/src/core/SkStroke.cpp
+++ b/src/core/SkStroke.cpp
@@ -9,6 +9,48 @@
#include "SkGeometry.h"
#include "SkPath.h"
+#if QUAD_STROKE_APPROXIMATION
+
+ enum {
+ kTangent_RecursiveLimit,
+ kCubic_RecursiveLimit,
+ kQuad_RecursiveLimit
+ };
+
+ // quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure
+ // largest seen for normal cubics : 5, 26
+ // largest seen for normal quads : 11
+ static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3 }; // 3x limits seen in practical tests
+
+ SK_COMPILE_ASSERT(SK_ARRAY_COUNT(kRecursiveLimits) == kQuad_RecursiveLimit + 1,
+ recursive_limits_mismatch);
+
+ #ifdef SK_DEBUG // enables tweaking these values at runtime from SampleApp
+ bool gDebugStrokerErrorSet = false;
+ SkScalar gDebugStrokerError;
+
+ int gMaxRecursion[SK_ARRAY_COUNT(kRecursiveLimits)] = { 0 };
+ #endif
+ #ifndef DEBUG_QUAD_STROKER
+ #define DEBUG_QUAD_STROKER 0
+ #endif
+
+ #if DEBUG_QUAD_STROKER
+ /* Enable to show the decisions made in subdividing the curve -- helpful when the resulting
+ stroke has more than the optimal number of quadratics and lines */
+ #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
+ SkDebugf("[%d] %s " format "\n", depth, __FUNCTION__, __VA_ARGS__), \
+ SkDebugf(" " #resultType " t=(%g,%g)\n", quadPts->fStartT, quadPts->fEndT), \
+ resultType
+ #define STROKER_DEBUG_PARAMS(...) , __VA_ARGS__
+ #else
+ #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
+ resultType
+ #define STROKER_DEBUG_PARAMS(...)
+ #endif
+
+#endif
+
#define kMaxQuadSubdivide 5
#define kMaxCubicSubdivide 7
@@ -16,6 +58,7 @@ static inline bool degenerate_vector(const SkVector& v) {
return !SkPoint::CanNormalize(v.fX, v.fY);
}
+#if !QUAD_STROKE_APPROXIMATION
static inline bool normals_too_curvy(const SkVector& norm0, SkVector& norm1) {
/* root2/2 is a 45-degree angle
make this constant bigger for more subdivisions (but not >= 1)
@@ -43,6 +86,7 @@ static inline bool normals_too_pinchy(const SkVector& norm0, SkVector& norm1) {
SkScalar dot = SkPoint::DotProduct(norm0, norm1);
return dot <= kTooPinchyNormalDotProd;
}
+#endif
static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after,
SkScalar radius,
@@ -67,12 +111,60 @@ static bool set_normal_unitnormal(const SkVector& vec,
}
///////////////////////////////////////////////////////////////////////////////
+#if QUAD_STROKE_APPROXIMATION
+
+struct SkQuadConstruct { // The state of the quad stroke under construction.
+ SkPoint fQuad[3]; // the stroked quad parallel to the original curve
+ SkPoint fTangentStart; // a point tangent to fQuad[0]
+ SkPoint fTangentEnd; // a point tangent to fQuad[2]
+ SkScalar fStartT; // a segment of the original curve
+ SkScalar fMidT; // "
+ SkScalar fEndT; // "
+ bool fStartSet; // state to share common points across structs
+ bool fEndSet; // "
+
+ // return false if start and end are too close to have a unique middle
+ bool init(SkScalar start, SkScalar end) {
+ fStartT = start;
+ fMidT = (start + end) * SK_ScalarHalf;
+ fEndT = end;
+ fStartSet = fEndSet = false;
+ return fStartT < fMidT && fMidT < fEndT;
+ }
+
+ bool initWithStart(SkQuadConstruct* parent) {
+ if (!init(parent->fStartT, parent->fMidT)) {
+ return false;
+ }
+ fQuad[0] = parent->fQuad[0];
+ fTangentStart = parent->fTangentStart;
+ fStartSet = true;
+ return true;
+ }
+
+ bool initWithEnd(SkQuadConstruct* parent) {
+ if (!init(parent->fMidT, parent->fEndT)) {
+ return false;
+ }
+ fQuad[2] = parent->fQuad[2];
+ fTangentEnd = parent->fTangentEnd;
+ fEndSet = true;
+ return true;
+ }
+};
+#endif
class SkPathStroker {
public:
+#if QUAD_STROKE_APPROXIMATION
+ SkPathStroker(const SkPath& src,
+ SkScalar radius, SkScalar miterLimit, SkScalar error, SkPaint::Cap cap,
+ SkPaint::Join join);
+#else
SkPathStroker(const SkPath& src,
SkScalar radius, SkScalar miterLimit, SkPaint::Cap cap,
SkPaint::Join join);
+#endif
void moveTo(const SkPoint&);
void lineTo(const SkPoint&);
@@ -87,6 +179,9 @@ public:
}
private:
+#if QUAD_STROKE_APPROXIMATION
+ SkScalar fError;
+#endif
SkScalar fRadius;
SkScalar fInvMiterLimit;
@@ -102,6 +197,67 @@ private:
SkPath fInner, fOuter; // outer is our working answer, inner is temp
SkPath fExtra; // added as extra complete contours
+#if QUAD_STROKE_APPROXIMATION
+ enum StrokeType {
+ kOuter_StrokeType = 1, // use sign-opposite values later to flip perpendicular axis
+ kInner_StrokeType = -1
+ } fStrokeType;
+
+ enum ResultType {
+ kSplit_ResultType, // the caller should split the quad stroke in two
+ kDegenerate_ResultType, // the caller should add a line
+ kQuad_ResultType, // the caller should (continue to try to) add a quad stroke
+ kNormalError_ResultType, // the cubic's normal couldn't be computed -- abort
+ };
+
+ enum ReductionType {
+ kPoint_ReductionType, // all curve points are practically identical
+ kLine_ReductionType, // the control point is on the line between the ends
+ kQuad_ReductionType, // the control point is outside the line between the ends
+ kDegenerate_ReductionType, // the control point is on the line but outside the ends
+ kDegenerate2_ReductionType, // two control points are on the line but outside ends (cubic)
+ kDegenerate3_ReductionType, // three areas of max curvature found (for cubic)
+ };
+
+ enum IntersectRayType {
+ kCtrlPt_RayType,
+ kResultType_RayType,
+ };
+
+ int fRecursionDepth; // track stack depth to abort if numerics run amok
+ bool fFoundTangents; // do less work until tangents meet (cubic)
+
+ void addDegenerateLine(const SkQuadConstruct* );
+ ReductionType CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3],
+ const SkPoint** tanPtPtr);
+ ReductionType CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction);
+ ResultType compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* );
+ ResultType compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* );
+ bool cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* ) const;
+ bool cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+ SkPoint* tangent) const;
+ bool cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* );
+ bool cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* , SkPoint* mid) const;
+ bool cubicStroke(const SkPoint cubic[4], SkQuadConstruct* );
+ void init(StrokeType strokeType, SkQuadConstruct* , SkScalar tStart, SkScalar tEnd);
+ ResultType intersectRay(SkQuadConstruct* , IntersectRayType STROKER_DEBUG_PARAMS(int) ) const;
+ bool ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const;
+ void quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+ SkPoint* tangent) const;
+ bool quadStroke(const SkPoint quad[3], SkQuadConstruct* );
+ void setCubicEndNormal(const SkPoint cubic[4],
+ const SkVector& normalAB, const SkVector& unitNormalAB,
+ SkVector* normalCD, SkVector* unitNormalCD);
+ void setQuadEndNormal(const SkPoint quad[3],
+ const SkVector& normalAB, const SkVector& unitNormalAB,
+ SkVector* normalBC, SkVector* unitNormalBC);
+ void setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const;
+ static bool SlightAngle(SkQuadConstruct* );
+ ResultType strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2],
+ SkQuadConstruct* STROKER_DEBUG_PARAMS(int depth) ) const;
+ ResultType tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* );
+#endif
+
void finishContour(bool close, bool isLine);
void preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal,
bool isLine);
@@ -109,6 +265,7 @@ private:
const SkVector& unitNormal);
void line_to(const SkPoint& currPt, const SkVector& normal);
+#if !QUAD_STROKE_APPROXIMATION
void quad_to(const SkPoint pts[3],
const SkVector& normalAB, const SkVector& unitNormalAB,
SkVector* normalBC, SkVector* unitNormalBC,
@@ -117,6 +274,7 @@ private:
const SkVector& normalAB, const SkVector& unitNormalAB,
SkVector* normalCD, SkVector* unitNormalCD,
int subDivide);
+#endif
};
///////////////////////////////////////////////////////////////////////////////
@@ -187,9 +345,15 @@ void SkPathStroker::finishContour(bool close, bool currIsLine) {
///////////////////////////////////////////////////////////////////////////////
+#if QUAD_STROKE_APPROXIMATION
+SkPathStroker::SkPathStroker(const SkPath& src,
+ SkScalar radius, SkScalar miterLimit, SkScalar error,
+ SkPaint::Cap cap, SkPaint::Join join)
+#else
SkPathStroker::SkPathStroker(const SkPath& src,
SkScalar radius, SkScalar miterLimit,
SkPaint::Cap cap, SkPaint::Join join)
+#endif
: fRadius(radius) {
/* This is only used when join is miter_join, but we initialize it here
@@ -217,6 +381,17 @@ SkPathStroker::SkPathStroker(const SkPath& src,
// 1x for inner == 'wag' (worst contour length would be better guess)
fOuter.incReserve(src.countPoints() * 3);
fInner.incReserve(src.countPoints());
+#if QUAD_STROKE_APPROXIMATION
+#ifdef SK_DEBUG
+ if (!gDebugStrokerErrorSet) {
+ gDebugStrokerError = error;
+ }
+ fError = gDebugStrokerError;
+#else
+ fError = error;
+#endif
+ fRecursionDepth = 0;
+#endif
}
void SkPathStroker::moveTo(const SkPoint& pt) {
@@ -243,6 +418,7 @@ void SkPathStroker::lineTo(const SkPoint& currPt) {
this->postJoinTo(currPt, normal, unitNormal);
}
+#if !QUAD_STROKE_APPROXIMATION
void SkPathStroker::quad_to(const SkPoint pts[3],
const SkVector& normalAB, const SkVector& unitNormalAB,
SkVector* normalBC, SkVector* unitNormalBC,
@@ -278,6 +454,203 @@ void SkPathStroker::quad_to(const SkPoint pts[3],
pts[2].fX - normalBC->fX, pts[2].fY - normalBC->fY);
}
}
+#endif
+
+#if QUAD_STROKE_APPROXIMATION
+void SkPathStroker::setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB,
+ const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) {
+ if (!set_normal_unitnormal(quad[1], quad[2], fRadius, normalBC, unitNormalBC)) {
+ *normalBC = normalAB;
+ *unitNormalBC = unitNormalAB;
+ }
+}
+
+void SkPathStroker::setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB,
+ const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD) {
+ SkVector ab = cubic[1] - cubic[0];
+ SkVector cd = cubic[3] - cubic[2];
+
+ bool degenerateAB = degenerate_vector(ab);
+ bool degenerateCD = degenerate_vector(cd);
+
+ if (degenerateAB && degenerateCD) {
+ goto DEGENERATE_NORMAL;
+ }
+
+ if (degenerateAB) {
+ ab = cubic[2] - cubic[0];
+ degenerateAB = degenerate_vector(ab);
+ }
+ if (degenerateCD) {
+ cd = cubic[3] - cubic[1];
+ degenerateCD = degenerate_vector(cd);
+ }
+ if (degenerateAB || degenerateCD) {
+DEGENERATE_NORMAL:
+ *normalCD = normalAB;
+ *unitNormalCD = unitNormalAB;
+ return;
+ }
+ SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD));
+}
+
+void SkPathStroker::init(StrokeType strokeType, SkQuadConstruct* quadPts, SkScalar tStart,
+ SkScalar tEnd) {
+ fStrokeType = strokeType;
+ fFoundTangents = false;
+ quadPts->init(tStart, tEnd);
+}
+
+// returns the distance squared from the point to the line
+static SkScalar pt_to_line(const SkPoint& pt, const SkPoint& lineStart, const SkPoint& lineEnd) {
+ SkVector dxy = lineEnd - lineStart;
+ if (degenerate_vector(dxy)) {
+ return pt.distanceToSqd(lineStart);
+ }
+ SkVector ab0 = pt - lineStart;
+ SkScalar numer = dxy.dot(ab0);
+ SkScalar denom = dxy.dot(dxy);
+ SkScalar t = numer / denom;
+ SkPoint hit;
+ hit.fX = lineStart.fX * (1 - t) + lineEnd.fX * t;
+ hit.fY = lineStart.fY * (1 - t) + lineEnd.fY * t;
+ return hit.distanceToSqd(pt);
+}
+
+/* Given a cubic, determine if all four points are in a line.
+ Return true if the inner points is close to a line connecting the outermost points.
+
+ Find the outermost point by looking for the largest difference in X or Y.
+ Given the indices of the outermost points, and that outer_1 is greater than outer_2,
+ this table shows the index of the smaller of the remaining points:
+
+ outer_2
+ 0 1 2 3
+ outer_1 ----------------
+ 0 | - 2 1 1
+ 1 | - - 0 0
+ 2 | - - - 0
+ 3 | - - - -
+
+ If outer_1 == 0 and outer_2 == 1, the smaller of the remaining indices (2 and 3) is 2.
+
+ This table can be collapsed to: (1 + (2 >> outer_2)) >> outer_1
+
+ Given three indices (outer_1 outer_2 mid_1) from 0..3, the remaining index is:
+
+ mid_2 == (outer_1 ^ outer_2 ^ mid_1)
+ */
+static bool cubic_in_line(const SkPoint cubic[4]) {
+ SkScalar ptMax = -1;
+ int outer1, outer2;
+ for (int index = 0; index < 3; ++index) {
+ for (int inner = index + 1; inner < 4; ++inner) {
+ SkVector testDiff = cubic[inner] - cubic[index];
+ SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
+ if (ptMax < testMax) {
+ outer1 = index;
+ outer2 = inner;
+ ptMax = testMax;
+ }
+ }
+ }
+ SkASSERT(outer1 >= 0 && outer1 <= 2);
+ SkASSERT(outer2 >= 1 && outer2 <= 3);
+ SkASSERT(outer1 < outer2);
+ int mid1 = (1 + (2 >> outer2)) >> outer1;
+ SkASSERT(mid1 >= 0 && mid1 <= 2);
+ SkASSERT(outer1 != mid1 && outer2 != mid1);
+ int mid2 = outer1 ^ outer2 ^ mid1;
+ SkASSERT(mid2 >= 1 && mid2 <= 3);
+ SkASSERT(mid2 != outer1 && mid2 != outer2 && mid2 != mid1);
+ SkASSERT(((1 << outer1) | (1 << outer2) | (1 << mid1) | (1 << mid2)) == 0x0f);
+ SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air
+ return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= lineSlop
+ && pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= lineSlop;
+}
+
+/* Given quad, see if all there points are in a line.
+ Return true if the inside point is close to a line connecting the outermost points.
+
+ Find the outermost point by looking for the largest difference in X or Y.
+ Since the XOR of the indices is 3 (0 ^ 1 ^ 2)
+ the missing index equals: outer_1 ^ outer_2 ^ 3
+ */
+static bool quad_in_line(const SkPoint quad[3]) {
+ SkScalar ptMax = -1;
+ int outer1, outer2;
+ for (int index = 0; index < 2; ++index) {
+ for (int inner = index + 1; inner < 3; ++inner) {
+ SkVector testDiff = quad[inner] - quad[index];
+ SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
+ if (ptMax < testMax) {
+ outer1 = index;
+ outer2 = inner;
+ ptMax = testMax;
+ }
+ }
+ }
+ SkASSERT(outer1 >= 0 && outer1 <= 1);
+ SkASSERT(outer2 >= 1 && outer2 <= 2);
+ SkASSERT(outer1 < outer2);
+ int mid = outer1 ^ outer2 ^ 3;
+ SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air
+ return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= lineSlop;
+}
+
+SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic[4],
+ SkPoint reduction[3], const SkPoint** tangentPtPtr) {
+ bool degenerateAB = degenerate_vector(cubic[1] - cubic[0]);
+ bool degenerateBC = degenerate_vector(cubic[2] - cubic[1]);
+ bool degenerateCD = degenerate_vector(cubic[3] - cubic[2]);
+ if (degenerateAB & degenerateBC & degenerateCD) {
+ return kPoint_ReductionType;
+ }
+ if (degenerateAB + degenerateBC + degenerateCD == 2) {
+ return kLine_ReductionType;
+ }
+ if (!cubic_in_line(cubic)) {
+ *tangentPtPtr = degenerateAB ? &cubic[2] : &cubic[1];
+ return kQuad_ReductionType;
+ }
+ SkScalar tValues[3];
+ int count = SkFindCubicMaxCurvature(cubic, tValues);
+ if (count == 0) {
+ return kLine_ReductionType;
+ }
+ for (int index = 0; index < count; ++index) {
+ SkScalar t = tValues[index];
+ SkEvalCubicAt(cubic, t, &reduction[index], NULL, NULL);
+ }
+ SK_COMPILE_ASSERT(kQuad_ReductionType + 1 == kDegenerate_ReductionType, enum_out_of_whack);
+ SK_COMPILE_ASSERT(kQuad_ReductionType + 2 == kDegenerate2_ReductionType, enum_out_of_whack);
+ SK_COMPILE_ASSERT(kQuad_ReductionType + 3 == kDegenerate3_ReductionType, enum_out_of_whack);
+
+ return (ReductionType) (kQuad_ReductionType + count);
+}
+
+SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3],
+ SkPoint* reduction) {
+ bool degenerateAB = degenerate_vector(quad[1] - quad[0]);
+ bool degenerateBC = degenerate_vector(quad[2] - quad[1]);
+ if (degenerateAB & degenerateBC) {
+ return kPoint_ReductionType;
+ }
+ if (degenerateAB | degenerateBC) {
+ return kLine_ReductionType;
+ }
+ if (!quad_in_line(quad)) {
+ return kQuad_ReductionType;
+ }
+ SkScalar t = SkFindQuadMaxCurvature(quad);
+ if (0 == t) {
+ return kLine_ReductionType;
+ }
+ SkEvalQuadAt(quad, t, reduction, NULL);
+ return kDegenerate_ReductionType;
+}
+
+#else
void SkPathStroker::cubic_to(const SkPoint pts[4],
const SkVector& normalAB, const SkVector& unitNormalAB,
@@ -362,8 +735,42 @@ DRAW_LINE:
pts[3].fX - normalCD->fX, pts[3].fY - normalCD->fY);
}
}
+#endif
void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
+#if QUAD_STROKE_APPROXIMATION
+ const SkPoint quad[3] = { fPrevPt, pt1, pt2 };
+ SkPoint reduction;
+ ReductionType reductionType = CheckQuadLinear(quad, &reduction);
+ if (kPoint_ReductionType == reductionType) {
+ return;
+ }
+ if (kLine_ReductionType == reductionType) {
+ this->lineTo(pt2);
+ return;
+ }
+ if (kDegenerate_ReductionType == reductionType) {
+ this->lineTo(reduction);
+ SkStrokerPriv::JoinProc saveJoiner = fJoiner;
+ fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
+ this->lineTo(pt2);
+ fJoiner = saveJoiner;
+ return;
+ }
+ SkASSERT(kQuad_ReductionType == reductionType);
+ SkVector normalAB, unitAB, normalBC, unitBC;
+ this->preJoinTo(pt1, &normalAB, &unitAB, false);
+ SkQuadConstruct quadPts;
+ this->init(kOuter_StrokeType, &quadPts, 0, 1);
+ if (!this->quadStroke(quad, &quadPts)) {
+ return;
+ }
+ this->init(kInner_StrokeType, &quadPts, 0, 1);
+ if (!this->quadStroke(quad, &quadPts)) {
+ return;
+ }
+ this->setQuadEndNormal(quad, normalAB, unitAB, &normalBC, &unitBC);
+#else
bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1);
bool degenerateBC = SkPath::IsLineDegenerate(pt1, pt2);
@@ -414,12 +821,450 @@ void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
kMaxQuadSubdivide);
}
}
+#endif
this->postJoinTo(pt2, normalBC, unitBC);
}
+#if QUAD_STROKE_APPROXIMATION
+// Given a point on the curve and its derivative, scale the derivative by the radius, and
+// compute the perpendicular point and its tangent.
+void SkPathStroker::setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt,
+ SkPoint* tangent) const {
+ if (!dxy->setLength(fRadius)) { // consider moving double logic into SkPoint::setLength
+ double xx = dxy->fX;
+ double yy = dxy->fY;
+ double dscale = fRadius / sqrt(xx * xx + yy * yy);
+ dxy->fX = SkDoubleToScalar(xx * dscale);
+ dxy->fY = SkDoubleToScalar(yy * dscale);
+ }
+ SkScalar axisFlip = SkIntToScalar(fStrokeType); // go opposite ways for outer, inner
+ onPt->fX = tPt.fX + axisFlip * dxy->fY;
+ onPt->fY = tPt.fY - axisFlip * dxy->fX;
+ if (tangent) {
+ tangent->fX = onPt->fX + dxy->fX;
+ tangent->fY = onPt->fY + dxy->fY;
+ }
+}
+
+// Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular tangent.
+// Returns false if the perpendicular could not be computed (because the derivative collapsed to 0)
+bool SkPathStroker::cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+ SkPoint* tangent) const {
+ SkVector dxy;
+ SkEvalCubicAt(cubic, t, tPt, &dxy, NULL);
+ if (dxy.fX == 0 && dxy.fY == 0) {
+ if (SkScalarNearlyZero(t)) {
+ dxy = cubic[2] - cubic[0];
+ } else if (SkScalarNearlyZero(1 - t)) {
+ dxy = cubic[3] - cubic[1];
+ } else {
+ return false;
+ }
+ if (dxy.fX == 0 && dxy.fY == 0) {
+ dxy = cubic[3] - cubic[0];
+ }
+ }
+ setRayPts(*tPt, &dxy, onPt, tangent);
+ return true;
+}
+
+// Given a cubic and a t range, find the start and end if they haven't been found already.
+bool SkPathStroker::cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
+ if (!quadPts->fStartSet) {
+ SkPoint cubicStartPt;
+ if (!this->cubicPerpRay(cubic, quadPts->fStartT, &cubicStartPt, &quadPts->fQuad[0],
+ &quadPts->fTangentStart)) {
+ return false;
+ }
+ quadPts->fStartSet = true;
+ }
+ if (!quadPts->fEndSet) {
+ SkPoint cubicEndPt;
+ if (!this->cubicPerpRay(cubic, quadPts->fEndT, &cubicEndPt, &quadPts->fQuad[2],
+ &quadPts->fTangentEnd)) {
+ return false;
+ }
+ quadPts->fEndSet = true;
+ }
+ return true;
+}
+
+bool SkPathStroker::cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* quadPts,
+ SkPoint* mid) const {
+ SkPoint cubicMidPt;
+ return this->cubicPerpRay(cubic, quadPts->fMidT, &cubicMidPt, mid, NULL);
+}
+
+// Given a quad and t, return the point on curve, its perpendicular, and the perpendicular tangent.
+void SkPathStroker::quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+ SkPoint* tangent) const {
+ SkVector dxy;
+ SkEvalQuadAt(quad, t, tPt, &dxy);
+ if (dxy.fX == 0 && dxy.fY == 0) {
+ dxy = quad[2] - quad[0];
+ }
+ setRayPts(*tPt, &dxy, onPt, tangent);
+}
+
+// Find the intersection of the stroke tangents to construct a stroke quad.
+// Return whether the stroke is a degenerate (a line), a quad, or must be split.
+// Optionally compute the quad's control point.
+SkPathStroker::ResultType SkPathStroker::intersectRay(SkQuadConstruct* quadPts,
+ IntersectRayType intersectRayType STROKER_DEBUG_PARAMS(int depth)) const {
+ const SkPoint& start = quadPts->fQuad[0];
+ const SkPoint& end = quadPts->fQuad[2];
+ SkVector aLen = quadPts->fTangentStart - start;
+ SkVector bLen = quadPts->fTangentEnd - end;
+ SkScalar denom = aLen.cross(bLen);
+ SkVector ab0 = start - end;
+ SkScalar numerA = bLen.cross(ab0);
+ SkScalar numerB = aLen.cross(ab0);
+ if (!SkScalarNearlyZero(denom)) {
+ // if the perpendicular distances from the quad points to the opposite tangent line
+ // are small, a straight line is good enough
+ SkScalar dist1 = pt_to_line(start, end, quadPts->fTangentEnd);
+ SkScalar dist2 = pt_to_line(end, start, quadPts->fTangentStart);
+ if (SkTMax(dist1, dist2) <= fError * fError) {
+ return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
+ "SkTMax(dist1=%g, dist2=%g) <= fError * fError", dist1, dist2);
+ }
+ if ((numerA >= 0) != (numerB >= 0)) {
+ if (kCtrlPt_RayType == intersectRayType) {
+ numerA /= denom;
+ SkPoint* ctrlPt = &quadPts->fQuad[1];
+ ctrlPt->fX = start.fX * (1 - numerA) + quadPts->fTangentStart.fX * numerA;
+ ctrlPt->fY = start.fY * (1 - numerA) + quadPts->fTangentStart.fY * numerA;
+ }
+ return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
+ "(numerA=%g >= 0) != (numerB=%g >= 0)", numerA, numerB);
+ }
+ return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+ "(numerA=%g >= 0) == (numerB=%g >= 0)", numerA, numerB);
+ } else { // if the lines are parallel, straight line is good enough
+ return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
+ "SkScalarNearlyZero(denom=%g)", denom);
+ }
+}
+
+// Given a cubic and a t-range, determine if the stroke can be described by a quadratic.
+SkPathStroker::ResultType SkPathStroker::tangentsMeet(const SkPoint cubic[4],
+ SkQuadConstruct* quadPts) {
+ if (!this->cubicQuadEnds(cubic, quadPts)) {
+ return kNormalError_ResultType;
+ }
+ return intersectRay(quadPts, kResultType_RayType STROKER_DEBUG_PARAMS(fRecursionDepth));
+}
+
+// Intersect the line with the quad and return the t values on the quad where the line crosses.
+static int intersect_quad_ray(const SkPoint line[2], const SkPoint quad[3], SkScalar roots[2]) {
+ SkVector vec = line[1] - line[0];
+ SkScalar r[3];
+ for (int n = 0; n < 3; ++n) {
+ r[n] = (quad[n].fY - line[0].fY) * vec.fX - (quad[n].fX - line[0].fX) * vec.fY;
+ }
+ SkScalar A = r[2];
+ SkScalar B = r[1];
+ SkScalar C = r[0];
+ A += C - 2 * B; // A = a - 2*b + c
+ B -= C; // B = -(b - c)
+ return SkFindUnitQuadRoots(A, 2 * B, C, roots);
+}
+
+// Return true if the point is close to the bounds of the quad. This is used as a quick reject.
+bool SkPathStroker::ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const {
+ SkScalar xMin = SkTMin(SkTMin(quad[0].fX, quad[1].fX), quad[2].fX);
+ if (pt.fX + fError < xMin) {
+ return false;
+ }
+ SkScalar xMax = SkTMax(SkTMax(quad[0].fX, quad[1].fX), quad[2].fX);
+ if (pt.fX - fError > xMax) {
+ return false;
+ }
+ SkScalar yMin = SkTMin(SkTMin(quad[0].fY, quad[1].fY), quad[2].fY);
+ if (pt.fY + fError < yMin) {
+ return false;
+ }
+ SkScalar yMax = SkTMax(SkTMax(quad[0].fY, quad[1].fY), quad[2].fY);
+ if (pt.fY - fError > yMax) {
+ return false;
+ }
+ return true;
+}
+
+static bool points_within_dist(const SkPoint& nearPt, const SkPoint& farPt, SkScalar limit) {
+ return nearPt.distanceToSqd(farPt) <= limit * limit;
+}
+
+static bool sharp_angle(const SkPoint quad[3]) {
+ SkVector smaller = quad[1] - quad[0];
+ SkVector larger = quad[1] - quad[2];
+ SkScalar smallerLen = smaller.lengthSqd();
+ SkScalar largerLen = larger.lengthSqd();
+ if (smallerLen > largerLen) {
+ SkTSwap(smaller, larger);
+ largerLen = smallerLen;
+ }
+ if (!smaller.setLength(largerLen)) {
+ return false;
+ }
+ SkScalar dot = smaller.dot(larger);
+ return dot > 0;
+}
+
+SkPathStroker::ResultType SkPathStroker::strokeCloseEnough(const SkPoint stroke[3],
+ const SkPoint ray[2], SkQuadConstruct* quadPts STROKER_DEBUG_PARAMS(int depth)) const {
+ SkPoint strokeMid;
+ SkEvalQuadAt(stroke, SK_ScalarHalf, &strokeMid);
+ // measure the distance from the curve to the quad-stroke midpoint, compare to radius
+ if (points_within_dist(ray[0], strokeMid, fError)) { // if the difference is small
+ if (sharp_angle(quadPts->fQuad)) {
+ return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+ "sharp_angle (1) =%g,%g, %g,%g, %g,%g",
+ quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
+ quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
+ quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
+ }
+ return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
+ "points_within_dist(ray[0]=%g,%g, strokeMid=%g,%g, fError)",
+ ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY);
+ }
+ // measure the distance to quad's bounds (quick reject)
+ // an alternative : look for point in triangle
+ if (!ptInQuadBounds(stroke, ray[0])) { // if far, subdivide
+ return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+ "!pt_in_quad_bounds(stroke=(%g,%g %g,%g %g,%g), ray[0]=%g,%g)",
+ stroke[0].fX, stroke[0].fY, stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY,
+ ray[0].fX, ray[0].fY);
+ }
+ // measure the curve ray distance to the quad-stroke
+ SkScalar roots[2];
+ int rootCount = intersect_quad_ray(ray, stroke, roots);
+ if (rootCount != 1) {
+ return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+ "rootCount=%d != 1", rootCount);
+ }
+ SkPoint quadPt;
+ SkEvalQuadAt(stroke, roots[0], &quadPt);
+ SkScalar error = fError * (SK_Scalar1 - SkScalarAbs(roots[0] - 0.5f) * 2);
+ if (points_within_dist(ray[0], quadPt, error)) { // if the difference is small, we're done
+ if (sharp_angle(quadPts->fQuad)) {
+ return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+ "sharp_angle (2) =%g,%g, %g,%g, %g,%g",
+ quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
+ quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
+ quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
+ }
+ return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
+ "points_within_dist(ray[0]=%g,%g, quadPt=%g,%g, error=%g)",
+ ray[0].fX, ray[0].fY, quadPt.fX, quadPt.fY, error);
+ }
+ // otherwise, subdivide
+ return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "%s", "fall through");
+}
+
+SkPathStroker::ResultType SkPathStroker::compareQuadCubic(const SkPoint cubic[4],
+ SkQuadConstruct* quadPts) {
+ // get the quadratic approximation of the stroke
+ if (!this->cubicQuadEnds(cubic, quadPts)) {
+ return kNormalError_ResultType;
+ }
+ ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType
+ STROKER_DEBUG_PARAMS(fRecursionDepth) );
+ if (resultType != kQuad_ResultType) {
+ return resultType;
+ }
+ // project a ray from the curve to the stroke
+ SkPoint ray[2]; // point near midpoint on quad, midpoint on cubic
+ if (!this->cubicPerpRay(cubic, quadPts->fMidT, &ray[1], &ray[0], NULL)) {
+ return kNormalError_ResultType;
+ }
+ return strokeCloseEnough(quadPts->fQuad, ray, quadPts STROKER_DEBUG_PARAMS(fRecursionDepth));
+}
+
+// if false is returned, caller splits quadratic approximation
+SkPathStroker::ResultType SkPathStroker::compareQuadQuad(const SkPoint quad[3],
+ SkQuadConstruct* quadPts) {
+ // get the quadratic approximation of the stroke
+ if (!quadPts->fStartSet) {
+ SkPoint quadStartPt;
+ this->quadPerpRay(quad, quadPts->fStartT, &quadStartPt, &quadPts->fQuad[0],
+ &quadPts->fTangentStart);
+ quadPts->fStartSet = true;
+ }
+ if (!quadPts->fEndSet) {
+ SkPoint quadEndPt;
+ this->quadPerpRay(quad, quadPts->fEndT, &quadEndPt, &quadPts->fQuad[2],
+ &quadPts->fTangentEnd);
+ quadPts->fEndSet = true;
+ }
+ ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType
+ STROKER_DEBUG_PARAMS(fRecursionDepth));
+ if (resultType != kQuad_ResultType) {
+ return resultType;
+ }
+ // project a ray from the curve to the stroke
+ SkPoint ray[2];
+ this->quadPerpRay(quad, quadPts->fMidT, &ray[1], &ray[0], NULL);
+ return strokeCloseEnough(quadPts->fQuad, ray, quadPts STROKER_DEBUG_PARAMS(fRecursionDepth));
+}
+
+void SkPathStroker::addDegenerateLine(const SkQuadConstruct* quadPts) {
+ const SkPoint* quad = quadPts->fQuad;
+ SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
+ path->lineTo(quad[2].fX, quad[2].fY);
+}
+
+bool SkPathStroker::cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* quadPts) const {
+ SkPoint strokeMid;
+ if (!cubicQuadMid(cubic, quadPts, &strokeMid)) {
+ return false;
+ }
+ SkScalar dist = pt_to_line(strokeMid, quadPts->fQuad[0], quadPts->fQuad[2]);
+ return dist < fError * fError;
+}
+
+bool SkPathStroker::cubicStroke(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
+ if (!fFoundTangents) {
+ ResultType resultType = this->tangentsMeet(cubic, quadPts);
+ if (kQuad_ResultType != resultType) {
+ if (kNormalError_ResultType == resultType) {
+ return false;
+ }
+ if ((kDegenerate_ResultType == resultType
+ || points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2], fError))
+ && cubicMidOnLine(cubic, quadPts)) {
+ addDegenerateLine(quadPts);
+ return true;
+ }
+ } else {
+ fFoundTangents = true;
+ }
+ }
+ if (fFoundTangents) {
+ ResultType resultType = this->compareQuadCubic(cubic, quadPts);
+ if (kQuad_ResultType == resultType) {
+ SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
+ const SkPoint* stroke = quadPts->fQuad;
+ path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
+ return true;
+ }
+ if (kDegenerate_ResultType == resultType) {
+ addDegenerateLine(quadPts);
+ return true;
+ }
+ if (kNormalError_ResultType == resultType) {
+ return false;
+ }
+ }
+ if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) {
+ return false; // just abort if projected quad isn't representable
+ }
+ SkDEBUGCODE(gMaxRecursion[fFoundTangents] = SkTMax(gMaxRecursion[fFoundTangents],
+ fRecursionDepth + 1));
+ if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) {
+ return false; // just abort if projected quad isn't representable
+ }
+ SkQuadConstruct half;
+ if (!half.initWithStart(quadPts)) {
+ addDegenerateLine(quadPts);
+ return true;
+ }
+ if (!this->cubicStroke(cubic, &half)) {
+ return false;
+ }
+ if (!half.initWithEnd(quadPts)) {
+ addDegenerateLine(quadPts);
+ return true;
+ }
+ if (!this->cubicStroke(cubic, &half)) {
+ return false;
+ }
+ --fRecursionDepth;
+ return true;
+}
+
+bool SkPathStroker::quadStroke(const SkPoint quad[3], SkQuadConstruct* quadPts) {
+ ResultType resultType = this->compareQuadQuad(quad, quadPts);
+ if (kQuad_ResultType == resultType) {
+ const SkPoint* stroke = quadPts->fQuad;
+ SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
+ path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
+ return true;
+ }
+ if (kDegenerate_ResultType == resultType) {
+ addDegenerateLine(quadPts);
+ return true;
+ }
+ SkDEBUGCODE(gMaxRecursion[kQuad_RecursiveLimit] = SkTMax(gMaxRecursion[kQuad_RecursiveLimit],
+ fRecursionDepth + 1));
+ if (++fRecursionDepth > kRecursiveLimits[kQuad_RecursiveLimit]) {
+ return false; // just abort if projected quad isn't representable
+ }
+ SkQuadConstruct half;
+ (void) half.initWithStart(quadPts);
+ if (!this->quadStroke(quad, &half)) {
+ return false;
+ }
+ (void) half.initWithEnd(quadPts);
+ if (!this->quadStroke(quad, &half)) {
+ return false;
+ }
+ --fRecursionDepth;
+ return true;
+}
+
+#endif
+
void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2,
const SkPoint& pt3) {
+#if QUAD_STROKE_APPROXIMATION
+ const SkPoint cubic[4] = { fPrevPt, pt1, pt2, pt3 };
+ SkPoint reduction[3];
+ const SkPoint* tangentPt;
+ ReductionType reductionType = CheckCubicLinear(cubic, reduction, &tangentPt);
+ if (kPoint_ReductionType == reductionType) {
+ return;
+ }
+ if (kLine_ReductionType == reductionType) {
+ this->lineTo(pt3);
+ return;
+ }
+ if (kDegenerate_ReductionType <= reductionType && kDegenerate3_ReductionType >= reductionType) {
+ this->lineTo(reduction[0]);
+ SkStrokerPriv::JoinProc saveJoiner = fJoiner;
+ fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
+ if (kDegenerate2_ReductionType <= reductionType) {
+ this->lineTo(reduction[1]);
+ }
+ if (kDegenerate3_ReductionType == reductionType) {
+ this->lineTo(reduction[2]);
+ }
+ this->lineTo(pt3);
+ fJoiner = saveJoiner;
+ return;
+ }
+ SkASSERT(kQuad_ReductionType == reductionType);
+ SkVector normalAB, unitAB, normalCD, unitCD;
+ this->preJoinTo(*tangentPt, &normalAB, &unitAB, false);
+ SkScalar tValues[2];
+ int count = SkFindCubicInflections(cubic, tValues);
+ SkScalar lastT = 0;
+ for (int index = 0; index <= count; ++index) {
+ SkScalar nextT = index < count ? tValues[index] : 1;
+ SkQuadConstruct quadPts;
+ this->init(kOuter_StrokeType, &quadPts, lastT, nextT);
+ if (!this->cubicStroke(cubic, &quadPts)) {
+ return;
+ }
+ this->init(kInner_StrokeType, &quadPts, lastT, nextT);
+ if (!this->cubicStroke(cubic, &quadPts)) {
+ return;
+ }
+ lastT = nextT;
+ }
+ this->setCubicEndNormal(cubic, normalAB, unitAB, &normalCD, &unitCD);
+#else
bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1);
bool degenerateBC = SkPath::IsLineDegenerate(pt1, pt2);
bool degenerateCD = SkPath::IsLineDegenerate(pt2, pt3);
@@ -465,6 +1310,7 @@ void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2,
}
}
+#endif
this->postJoinTo(pt3, normalCD, unitCD);
}
@@ -498,6 +1344,13 @@ SkStroke::SkStroke(const SkPaint& p, SkScalar width) {
fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
}
+#if QUAD_STROKE_APPROXIMATION
+void SkStroke::setError(SkScalar error) {
+ SkASSERT(error > 0);
+ fError = error;
+}
+#endif
+
void SkStroke::setWidth(SkScalar width) {
SkASSERT(width >= 0);
fWidth = width;
@@ -575,8 +1428,13 @@ void SkStroke::strokePath(const SkPath& src, SkPath* dst) const {
SkAutoConicToQuads converter;
const SkScalar conicTol = SK_Scalar1 / 4;
+#if QUAD_STROKE_APPROXIMATION
+ SkPathStroker stroker(src, radius, fMiterLimit, fError, this->getCap(),
+ this->getJoin());
+#else
SkPathStroker stroker(src, radius, fMiterLimit, this->getCap(),
this->getJoin());
+#endif
SkPath::Iter iter(src, false);
SkPath::Verb lastSegment = SkPath::kMove_Verb;
diff --git a/src/core/SkStroke.h b/src/core/SkStroke.h
index a6a9f08331..cb329399a9 100644
--- a/src/core/SkStroke.h
+++ b/src/core/SkStroke.h
@@ -11,6 +11,19 @@
#include "SkPath.h"
#include "SkPoint.h"
#include "SkPaint.h"
+#include "SkStrokerPriv.h"
+
+// set to 1 to use experimental outset stroking with quads
+#ifndef QUAD_STROKE_APPROXIMATION
+#define QUAD_STROKE_APPROXIMATION 0
+#endif
+
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+extern bool gDebugStrokerErrorSet;
+extern SkScalar gDebugStrokerError;
+
+extern int gMaxRecursion[];
+#endif
/** \class SkStroke
SkStroke is the utility class that constructs paths by stroking
@@ -30,6 +43,9 @@ public:
SkPaint::Join getJoin() const { return (SkPaint::Join)fJoin; }
void setJoin(SkPaint::Join);
+#if QUAD_STROKE_APPROXIMATION
+ void setError(SkScalar);
+#endif
void setMiterLimit(SkScalar);
void setWidth(SkScalar);
@@ -46,6 +62,9 @@ public:
////////////////////////////////////////////////////////////////
private:
+#if QUAD_STROKE_APPROXIMATION
+ SkScalar fError;
+#endif
SkScalar fWidth, fMiterLimit;
uint8_t fCap, fJoin;
SkBool8 fDoFill;
diff --git a/src/core/SkStrokeRec.cpp b/src/core/SkStrokeRec.cpp
index a4c73af2c5..22f0562fe2 100644
--- a/src/core/SkStrokeRec.cpp
+++ b/src/core/SkStrokeRec.cpp
@@ -108,6 +108,9 @@ bool SkStrokeRec::applyToPath(SkPath* dst, const SkPath& src) const {
stroker.setMiterLimit(fMiterLimit);
stroker.setWidth(fWidth);
stroker.setDoFill(fStrokeAndFill);
+#if QUAD_STROKE_APPROXIMATION
+ stroker.setError(1);
+#endif
stroker.strokePath(src, dst);
return true;
}
diff --git a/tests/StrokerTest.cpp b/tests/StrokerTest.cpp
new file mode 100755
index 0000000000..804e0a1d5f
--- /dev/null
+++ b/tests/StrokerTest.cpp
@@ -0,0 +1,452 @@
+#include "PathOpsCubicIntersectionTestData.h"
+#include "PathOpsQuadIntersectionTestData.h"
+#include "SkCommonFlags.h"
+#include "SkPaint.h"
+#include "SkPath.h"
+#include "SkRandom.h"
+#include "SkStrokerPriv.h"
+#include "SkTime.h"
+#include "Test.h"
+
+DEFINE_bool2(extendedTest, x, false, "run extended tests regardless of how long takes");
+
+#define MS_TEST_DURATION 10
+
+const SkScalar widths[] = {-FLT_MAX, -1, -0.1f, -FLT_EPSILON, 0, FLT_EPSILON,
+ 0.0000001f, 0.000001f, 0.00001f, 0.0001f, 0.001f, 0.01f,
+ 0.1f, 0.2f, 0.3f, 0.4f, 0.5f, 1, 1.1f, 2, 10, 10e2f, 10e3f, 10e4f, 10e5f, 10e6f, 10e7f,
+ 10e8f, 10e9f, 10e10f, 10e20f, FLT_MAX };
+size_t widths_count = SK_ARRAY_COUNT(widths);
+
+static void pathTest(const SkPath& path) {
+ SkPaint p;
+ SkPath fill;
+ p.setStyle(SkPaint::kStroke_Style);
+ for (size_t index = 0; index < widths_count; ++index) {
+ p.setStrokeWidth(widths[index]);
+ p.getFillPath(path, &fill);
+ }
+}
+
+static void cubicTest(const SkPoint c[4]) {
+ SkPath path;
+ path.moveTo(c[0].fX, c[0].fY);
+ path.cubicTo(c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY);
+ pathTest(path);
+}
+
+static void quadTest(const SkPoint c[3]) {
+ SkPath path;
+ path.moveTo(c[0].fX, c[0].fY);
+ path.quadTo(c[1].fX, c[1].fY, c[2].fX, c[2].fY);
+ pathTest(path);
+}
+
+static void cubicSetTest(const SkDCubic* dCubic, size_t count) {
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (size_t index = 0; index < count; ++index) {
+ const SkDCubic& d = dCubic[index];
+ SkPoint c[4] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+ {(float) d[2].fX, (float) d[2].fY}, {(float) d[3].fX, (float) d[3].fY} };
+ cubicTest(c);
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+}
+
+static void cubicPairSetTest(const SkDCubic dCubic[][2], size_t count) {
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (size_t index = 0; index < count; ++index) {
+ for (int pair = 0; pair < 2; ++pair) {
+ const SkDCubic& d = dCubic[index][pair];
+ SkPoint c[4] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+ {(float) d[2].fX, (float) d[2].fY}, {(float) d[3].fX, (float) d[3].fY} };
+ cubicTest(c);
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+ }
+}
+
+static void quadSetTest(const SkDQuad* dQuad, size_t count) {
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (size_t index = 0; index < count; ++index) {
+ const SkDQuad& d = dQuad[index];
+ SkPoint c[3] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+ {(float) d[2].fX, (float) d[2].fY} };
+ quadTest(c);
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+}
+
+static void quadPairSetTest(const SkDQuad dQuad[][2], size_t count) {
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (size_t index = 0; index < count; ++index) {
+ for (int pair = 0; pair < 2; ++pair) {
+ const SkDQuad& d = dQuad[index][pair];
+ SkPoint c[3] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+ {(float) d[2].fX, (float) d[2].fY} };
+ quadTest(c);
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+ }
+}
+
+DEF_TEST(QuadStrokerSet, reporter) {
+ quadSetTest(quadraticLines, quadraticLines_count);
+ quadSetTest(quadraticPoints, quadraticPoints_count);
+ quadSetTest(quadraticModEpsilonLines, quadraticModEpsilonLines_count);
+ quadPairSetTest(quadraticTests, quadraticTests_count);
+}
+
+DEF_TEST(CubicStrokerSet, reporter) {
+ cubicSetTest(pointDegenerates, pointDegenerates_count);
+ cubicSetTest(notPointDegenerates, notPointDegenerates_count);
+ cubicSetTest(lines, lines_count);
+ cubicSetTest(notLines, notLines_count);
+ cubicSetTest(modEpsilonLines, modEpsilonLines_count);
+ cubicSetTest(lessEpsilonLines, lessEpsilonLines_count);
+ cubicSetTest(negEpsilonLines, negEpsilonLines_count);
+ cubicPairSetTest(tests, tests_count);
+}
+
+static SkScalar unbounded(SkLCGRandom& r) {
+ uint32_t val = r.nextU();
+ return SkBits2Float(val);
+}
+
+static SkScalar unboundedPos(SkLCGRandom& r) {
+ uint32_t val = r.nextU() & 0x7fffffff;
+ return SkBits2Float(val);
+}
+
+DEF_TEST(QuadStrokerUnbounded, reporter) {
+ SkLCGRandom r;
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ int best = 0;
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (int i = 0; i < 1000000; ++i) {
+ SkPath path, fill;
+ path.moveTo(unbounded(r), unbounded(r));
+ path.quadTo(unbounded(r), unbounded(r), unbounded(r), unbounded(r));
+ p.setStrokeWidth(unboundedPos(r));
+ p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (best < gMaxRecursion[2]) {
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
+ p.getStrokeWidth());
+ path.dumpHex();
+ SkDebugf("fill:\n");
+ fill.dumpHex();
+ }
+ best = gMaxRecursion[2];
+ }
+#endif
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
+ }
+#endif
+}
+
+DEF_TEST(CubicStrokerUnbounded, reporter) {
+ SkLCGRandom r;
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ int bestTan = 0;
+ int bestCubic = 0;
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (int i = 0; i < 1000000; ++i) {
+ SkPath path, fill;
+ path.moveTo(unbounded(r), unbounded(r));
+ path.cubicTo(unbounded(r), unbounded(r), unbounded(r), unbounded(r),
+ unbounded(r), unbounded(r));
+ p.setStrokeWidth(unboundedPos(r));
+ p.getFillPath(path, &fill);
+ #if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (bestTan < gMaxRecursion[0] || bestCubic < gMaxRecursion[1]) {
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
+ gMaxRecursion[1], p.getStrokeWidth());
+ path.dumpHex();
+ SkDebugf("fill:\n");
+ fill.dumpHex();
+ }
+ bestTan = SkTMax(bestTan, gMaxRecursion[0]);
+ bestCubic = SkTMax(bestCubic, gMaxRecursion[1]);
+ }
+ #endif
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, bestTan, bestCubic);
+ }
+#endif
+}
+
+DEF_TEST(QuadStrokerConstrained, reporter) {
+ SkLCGRandom r;
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ int best = 0;
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (int i = 0; i < 1000000; ++i) {
+ SkPath path, fill;
+ SkPoint quad[3];
+ quad[0].fX = r.nextRangeF(0, 500);
+ quad[0].fY = r.nextRangeF(0, 500);
+ const SkScalar halfSquared = 0.5f * 0.5f;
+ do {
+ quad[1].fX = r.nextRangeF(0, 500);
+ quad[1].fY = r.nextRangeF(0, 500);
+ } while (quad[0].distanceToSqd(quad[1]) < halfSquared);
+ do {
+ quad[2].fX = r.nextRangeF(0, 500);
+ quad[2].fY = r.nextRangeF(0, 500);
+ } while (quad[0].distanceToSqd(quad[2]) < halfSquared
+ || quad[1].distanceToSqd(quad[2]) < halfSquared);
+ path.moveTo(quad[0].fX, quad[0].fY);
+ path.quadTo(quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
+ p.setStrokeWidth(r.nextRangeF(0, 500));
+ p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (best < gMaxRecursion[2]) {
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
+ p.getStrokeWidth());
+ path.dumpHex();
+ SkDebugf("fill:\n");
+ fill.dumpHex();
+ }
+ best = gMaxRecursion[2];
+ }
+#endif
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
+ }
+#endif
+}
+
+DEF_TEST(CubicStrokerConstrained, reporter) {
+ SkLCGRandom r;
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ int bestTan = 0;
+ int bestCubic = 0;
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (int i = 0; i < 1000000; ++i) {
+ SkPath path, fill;
+ SkPoint cubic[4];
+ cubic[0].fX = r.nextRangeF(0, 500);
+ cubic[0].fY = r.nextRangeF(0, 500);
+ const SkScalar halfSquared = 0.5f * 0.5f;
+ do {
+ cubic[1].fX = r.nextRangeF(0, 500);
+ cubic[1].fY = r.nextRangeF(0, 500);
+ } while (cubic[0].distanceToSqd(cubic[1]) < halfSquared);
+ do {
+ cubic[2].fX = r.nextRangeF(0, 500);
+ cubic[2].fY = r.nextRangeF(0, 500);
+ } while ( cubic[0].distanceToSqd(cubic[2]) < halfSquared
+ || cubic[1].distanceToSqd(cubic[2]) < halfSquared);
+ do {
+ cubic[3].fX = r.nextRangeF(0, 500);
+ cubic[3].fY = r.nextRangeF(0, 500);
+ } while ( cubic[0].distanceToSqd(cubic[3]) < halfSquared
+ || cubic[1].distanceToSqd(cubic[3]) < halfSquared
+ || cubic[2].distanceToSqd(cubic[3]) < halfSquared);
+ path.moveTo(cubic[0].fX, cubic[0].fY);
+ path.cubicTo(cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY);
+ p.setStrokeWidth(r.nextRangeF(0, 500));
+ p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (bestTan < gMaxRecursion[0] || bestCubic < gMaxRecursion[1]) {
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
+ gMaxRecursion[1], p.getStrokeWidth());
+ path.dumpHex();
+ SkDebugf("fill:\n");
+ fill.dumpHex();
+ }
+ bestTan = SkTMax(bestTan, gMaxRecursion[0]);
+ bestCubic = SkTMax(bestCubic, gMaxRecursion[1]);
+ }
+#endif
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, bestTan, bestCubic);
+ }
+#endif
+}
+
+DEF_TEST(QuadStrokerRange, reporter) {
+ SkLCGRandom r;
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ int best = 0;
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (int i = 0; i < 1000000; ++i) {
+ SkPath path, fill;
+ SkPoint quad[3];
+ quad[0].fX = r.nextRangeF(0, 500);
+ quad[0].fY = r.nextRangeF(0, 500);
+ quad[1].fX = r.nextRangeF(0, 500);
+ quad[1].fY = r.nextRangeF(0, 500);
+ quad[2].fX = r.nextRangeF(0, 500);
+ quad[2].fY = r.nextRangeF(0, 500);
+ path.moveTo(quad[0].fX, quad[0].fY);
+ path.quadTo(quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
+ p.setStrokeWidth(r.nextRangeF(0, 500));
+ p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (best < gMaxRecursion[2]) {
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
+ p.getStrokeWidth());
+ path.dumpHex();
+ SkDebugf("fill:\n");
+ fill.dumpHex();
+ }
+ best = gMaxRecursion[2];
+ }
+#endif
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
+ }
+#endif
+}
+
+DEF_TEST(CubicStrokerRange, reporter) {
+ SkLCGRandom r;
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ int best[2] = { 0 };
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+ for (int i = 0; i < 1000000; ++i) {
+ SkPath path, fill;
+ path.moveTo(r.nextRangeF(0, 500), r.nextRangeF(0, 500));
+ path.cubicTo(r.nextRangeF(0, 500), r.nextRangeF(0, 500), r.nextRangeF(0, 500),
+ r.nextRangeF(0, 500), r.nextRangeF(0, 500), r.nextRangeF(0, 500));
+ p.setStrokeWidth(r.nextRangeF(0, 100));
+ p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (best[0] < gMaxRecursion[0] || best[1] < gMaxRecursion[1]) {
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
+ gMaxRecursion[1], p.getStrokeWidth());
+ path.dumpHex();
+ SkDebugf("fill:\n");
+ fill.dumpHex();
+ }
+ best[0] = SkTMax(best[0], gMaxRecursion[0]);
+ best[1] = SkTMax(best[1], gMaxRecursion[1]);
+ }
+#endif
+ if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+ return;
+ }
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, best[0], best[1]);
+ }
+#endif
+}
+
+
+DEF_TEST(QuadStrokerOneOff, reporter) {
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+ p.setStrokeWidth(SkDoubleToScalar(164.683548));
+
+ SkPath path, fill;
+path.moveTo(SkBits2Float(0x43c99223), SkBits2Float(0x42b7417e));
+path.quadTo(SkBits2Float(0x4285d839), SkBits2Float(0x43ed6645), SkBits2Float(0x43c941c8), SkBits2Float(0x42b3ace3));
+ p.getFillPath(path, &fill);
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s path\n", __FUNCTION__);
+ path.dump();
+ SkDebugf("fill:\n");
+ fill.dump();
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("max quad=%d\n", gMaxRecursion[2]);
+ }
+#endif
+}
+
+DEF_TEST(CubicStrokerOneOff, reporter) {
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+ SkPaint p;
+ p.setStyle(SkPaint::kStroke_Style);
+ p.setStrokeWidth(SkDoubleToScalar(42.835968));
+
+ SkPath path, fill;
+path.moveTo(SkBits2Float(0x433f5370), SkBits2Float(0x43d1f4b3));
+path.cubicTo(SkBits2Float(0x4331cb76), SkBits2Float(0x43ea3340), SkBits2Float(0x4388f498), SkBits2Float(0x42f7f08d), SkBits2Float(0x43f1cd32), SkBits2Float(0x42802ec1));
+ p.getFillPath(path, &fill);
+ if (FLAGS_verbose) {
+ SkDebugf("\n%s path\n", __FUNCTION__);
+ path.dump();
+ SkDebugf("fill:\n");
+ fill.dump();
+ }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+ if (FLAGS_verbose) {
+ SkDebugf("max tan=%d cubic=%d\n", gMaxRecursion[0], gMaxRecursion[1]);
+ }
+#endif
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-28 23:40:40 +0000