work in progress
in the middle of switching to sortless version
git-svn-id: http://skia.googlecode.com/svn/trunk@3768 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/ActiveEdge_Test.cpp b/experimental/Intersection/ActiveEdge_Test.cpp
index fe7d664..03cb595 100755
--- a/experimental/Intersection/ActiveEdge_Test.cpp
+++ b/experimental/Intersection/ActiveEdge_Test.cpp
@@ -74,9 +74,9 @@
right.fWorkEdge.fEdge = &rightIn;
for (size_t x = 0; x < leftRightCount; ++x) {
left.fAbove = leftRight[x][0];
- left.fBelow = leftRight[x][1];
+ left.fTangent = left.fBelow = leftRight[x][1];
right.fAbove = leftRight[x][2];
- right.fBelow = leftRight[x][3];
+ right.fTangent = right.fBelow = leftRight[x][3];
SkASSERT(left < right);
SkASSERT(operator_less_than(left, right));
SkASSERT(!(right < left));
diff --git a/experimental/Intersection/CubicBounds.cpp b/experimental/Intersection/CubicBounds.cpp
index 3534425..5d21be6 100644
--- a/experimental/Intersection/CubicBounds.cpp
+++ b/experimental/Intersection/CubicBounds.cpp
@@ -1,10 +1,63 @@
-/*
- * CubicBounds.cpp
- * edge
- *
- * Created by Cary Clark on 1/27/12.
- * Copyright 2012 __MyCompanyName__. All rights reserved.
- *
- */
+#include "DataTypes.h"
+#include "Extrema.h"
+static int isBoundedByEndPoints(double a, double b, double c, double d)
+{
+ return (a <= b && a <= c && b <= d && c <= d)
+ || (a >= b && a >= c && b >= d && c >= d);
+}
+double leftMostT(const Cubic& cubic, double startT, double endT) {
+ double leftTs[2];
+ _Point pt[2];
+ int results = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x,
+ leftTs);
+ int best = -1;
+ for (int index = 0; index < results; ++index) {
+ if (startT > leftTs[index] || leftTs[index] > endT) {
+ continue;
+ }
+ if (best < 0) {
+ best = index;
+ continue;
+ }
+ xy_at_t(cubic, leftTs[0], pt[0].x, pt[0].y);
+ xy_at_t(cubic, leftTs[1], pt[1].x, pt[1].y);
+ if (pt[0].x > pt[1].x) {
+ best = 1;
+ }
+ }
+ if (best >= 0) {
+ return leftTs[best];
+ }
+ xy_at_t(cubic, startT, pt[0].x, pt[0].y);
+ xy_at_t(cubic, endT, pt[1].x, pt[1].y);
+ return pt[0].x <= pt[1].x ? startT : endT;
+}
+
+void _Rect::setBounds(const Cubic& cubic) {
+ set(cubic[0]);
+ add(cubic[3]);
+ double tValues[4];
+ int roots = 0;
+ if (!isBoundedByEndPoints(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x)) {
+ roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x,
+ cubic[3].x, tValues);
+ }
+ if (!isBoundedByEndPoints(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y)) {
+ roots += findExtrema(cubic[0].y, cubic[1].y, cubic[2].y,
+ cubic[3].y, &tValues[roots]);
+ }
+ for (int x = 0; x < roots; ++x) {
+ _Point result;
+ xy_at_t(cubic, tValues[x], result.x, result.y);
+ add(result);
+ }
+}
+
+void _Rect::setRawBounds(const Cubic& cubic) {
+ set(cubic[0]);
+ for (int x = 1; x < 4; ++x) {
+ add(cubic[x]);
+ }
+}
diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp
index fee179a..5551026 100644
--- a/experimental/Intersection/CubicReduceOrder.cpp
+++ b/experimental/Intersection/CubicReduceOrder.cpp
@@ -24,7 +24,7 @@
reduction[1] = cubic[3];
int smaller = reduction[1].y > reduction[0].y;
int larger = smaller ^ 1;
- int roots = SkFindCubicExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tValues);
+ int roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tValues);
for (int index = 0; index < roots; ++index) {
double yExtrema = interp_cubic_coords(&cubic[0].y, tValues[index]);
if (reduction[smaller].y > yExtrema) {
@@ -44,7 +44,7 @@
reduction[1] = cubic[3];
int smaller = reduction[1].x > reduction[0].x;
int larger = smaller ^ 1;
- int roots = SkFindCubicExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues);
+ int roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues);
for (int index = 0; index < roots; ++index) {
double xExtrema = interp_cubic_coords(&cubic[0].x, tValues[index]);
if (reduction[smaller].x > xExtrema) {
@@ -127,9 +127,9 @@
double tValues[2];
int roots;
if (useX) {
- roots = SkFindCubicExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues);
+ roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues);
} else {
- roots = SkFindCubicExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tValues);
+ roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tValues);
}
for (index = 0; index < roots; ++index) {
_Point extrema;
diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h
index 1da2d9b..38d4890 100644
--- a/experimental/Intersection/CurveIntersection.h
+++ b/experimental/Intersection/CurveIntersection.h
@@ -6,6 +6,7 @@
class Intersections;
// unit-testable utilities
+double axialIntersect(const Quadratic& q1, const _Point& p, bool vert);
bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT);
bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT);
void chop_at(const Cubic& src, CubicPair& dst, double t);
@@ -34,11 +35,26 @@
int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]);
int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
double tRange[3]);
+int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
+ bool flipped, Intersections&);
+int horizontalIntersect(const _Line& line, double left, double right,
+ double y, bool flipped, Intersections& );
int horizontalIntersect(const Quadratic& quad, double left, double right,
double y, double tRange[2]);
+int horizontalIntersect(const Quadratic& quad, double left, double right,
+ double y, bool flipped, Intersections& );
bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]);
bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& );
bool intersect(const Quadratic& quad, const _Line& line, Intersections& );
+double leftMostT(const Cubic& , double startT, double endT);
+double leftMostT(const _Line& , double startT, double endT);
+double leftMostT(const Quadratic& , double startT, double endT);
+int verticalIntersect(const Cubic& cubic, double top, double bottom, double x,
+ bool flipped, Intersections& );
+int verticalIntersect(const _Line& line, double top, double bottom, double x,
+ bool flipped, Intersections& );
+int verticalIntersect(const Quadratic& quad, double top, double bottom,
+ double x, bool flipped, Intersections& );
#endif
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp
index 1bf3c8b..002e84c 100644
--- a/experimental/Intersection/EdgeWalker.cpp
+++ b/experimental/Intersection/EdgeWalker.cpp
@@ -1,4 +1,3 @@
-
/*
* Copyright 2012 Google Inc.
*
@@ -20,9 +19,9 @@
#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
// FIXME: remove once debugging is complete
-#if 0 // set to 1 for no debugging whatsoever
+#if 01 // set to 1 for no debugging whatsoever
-const bool gRunTestsInOneThread = true;
+const bool gRunTestsInOneThread = false;
#define DEBUG_ACTIVE_LESS_THAN 0
#define DEBUG_ADD 0
@@ -1381,23 +1380,51 @@
class ActiveEdge {
public:
// this logic must be kept in sync with tooCloseToCall
- // callers expect this to only read fAbove, fBelow
+ // callers expect this to only read fAbove, fTangent
bool operator<(const ActiveEdge& rh) const {
- double topD = fAbove.fX - rh.fAbove.fX;
- if (rh.fAbove.fY < fAbove.fY) {
- topD = (rh.fBelow.fY - rh.fAbove.fY) * topD
- - (fAbove.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX);
- } else if (rh.fAbove.fY > fAbove.fY) {
- topD = (fBelow.fY - fAbove.fY) * topD
- + (rh.fAbove.fY - fAbove.fY) * (fBelow.fX - fAbove.fX);
+ if (fVerb == rh.fVerb) {
+ // FIXME: don't know what to do if verb is quad, cubic
+ return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);
}
- double botD = fBelow.fX - rh.fBelow.fX;
- if (rh.fBelow.fY > fBelow.fY) {
- botD = (rh.fBelow.fY - rh.fAbove.fY) * botD
- - (fBelow.fY - rh.fBelow.fY) * (rh.fBelow.fX - rh.fAbove.fX);
- } else if (rh.fBelow.fY < fBelow.fY) {
- botD = (fBelow.fY - fAbove.fY) * botD
- + (rh.fBelow.fY - fBelow.fY) * (fBelow.fX - fAbove.fX);
+ // figure out which is quad, line
+ // if cached data says line did not intersect quad, use top/bottom
+ if (fVerb != SkPath::kLine_Verb ? noIntersect(rh) : rh.noIntersect(*this)) {
+ return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);
+ }
+ // use whichever of top/tangent tangent/bottom overlaps more
+ // with line top/bot
+ // assumes quad/cubic can already be upconverted to cubic/cubic
+ const SkPoint* line[2];
+ const SkPoint* curve[4];
+ if (fVerb != SkPath::kLine_Verb) {
+ line[0] = &rh.fAbove;
+ line[1] = &rh.fBelow;
+ curve[0] = &fAbove;
+ curve[1] = &fTangent;
+ curve[2] = &fBelow;
+ } else {
+ line[0] = &fAbove;
+ line[1] = &fBelow;
+ curve[0] = &rh.fAbove;
+ curve[1] = &rh.fTangent;
+ curve[2] = &rh.fBelow;
+ }
+
+ }
+
+ bool abCompare(const SkPoint& a1, const SkPoint& a2, const SkPoint& b1,
+ const SkPoint& b2) const {
+ double topD = a1.fX - b1.fX;
+ if (b1.fY < a1.fY) {
+ topD = (b2.fY - b1.fY) * topD - (a1.fY - b1.fY) * (b2.fX - b1.fX);
+ } else if (b1.fY > a1.fY) {
+ topD = (a2.fY - a1.fY) * topD + (b1.fY - a1.fY) * (a2.fX - a1.fX);
+ }
+ double botD = a2.fX - b2.fX;
+ if (b2.fY > a2.fY) {
+ botD = (b2.fY - b1.fY) * botD - (a2.fY - b2.fY) * (b2.fX - b1.fX);
+ } else if (b2.fY < a2.fY) {
+ botD = (a2.fY - a1.fY) * botD + (b2.fY - a2.fY) * (a2.fX - a1.fX);
}
// return sign of greater absolute value
return (fabs(topD) > fabs(botD) ? topD : botD) < 0;
@@ -1477,6 +1504,37 @@
SkASSERT(!fExplicitTs);
fTIndex = fTs->count() + 1;
}
+
+ void calcAboveBelow(double tAbove, double tBelow) {
+ fVerb = fWorkEdge.verb();
+ switch (fVerb) {
+ case SkPath::kLine_Verb:
+ LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove);
+ LineXYAtT(fWorkEdge.fPts, tBelow, &fTangent);
+ fBelow = fTangent;
+ break;
+ case SkPath::kQuad_Verb:
+ // FIXME: put array in struct to avoid copy?
+ SkPoint quad[3];
+ QuadSubDivide(fWorkEdge.fPts, tAbove, tBelow, quad);
+ fAbove = quad[0];
+ fTangent = quad[0] != quad[1] ? quad[1] : quad[2];
+ fBelow = quad[2];
+ break;
+ case SkPath::kCubic_Verb:
+ SkPoint cubic[3];
+ CubicSubDivide(fWorkEdge.fPts, tAbove, tBelow, cubic);
+ fAbove = cubic[0];
+ // FIXME: can't see how quad logic for how tangent is used
+ // extends to cubic
+ fTangent = cubic[0] != cubic[1] ? cubic[1]
+ : cubic[0] != cubic[2] ? cubic[2] : cubic[3];
+ fBelow = cubic[3];
+ break;
+ default:
+ SkASSERT(0);
+ }
+ }
void calcLeft(SkScalar y) {
// OPTIMIZE: put a kDone_Verb at the end of the verb list?
@@ -1491,29 +1549,14 @@
}
void calcLeft() {
- void (*xyAtTFunc)(const SkPoint a[], double t, SkPoint* out);
- switch (fWorkEdge.verb()) {
- case SkPath::kLine_Verb:
- xyAtTFunc = LineXYAtT;
- break;
- case SkPath::kQuad_Verb:
- xyAtTFunc = QuadXYAtT;
- break;
- case SkPath::kCubic_Verb:
- xyAtTFunc = CubicXYAtT;
- break;
- default:
- SkASSERT(0);
- }
- // OPTIMIZATION: if fXAbove, fXBelow have already been computed
- // for the fTIndex, don't do it again
- // For identical x, this lets us know which edge is first.
- // If both edges have T values < 1, check x at next T (fXBelow).
int add = (fTIndex <= fTs->count() - fExplicitTs) - 1;
double tAbove = t(fTIndex + add);
- (*xyAtTFunc)(fWorkEdge.fPts, tAbove, &fAbove);
double tBelow = t(fTIndex - ~add);
- (*xyAtTFunc)(fWorkEdge.fPts, tBelow, &fBelow);
+ // OPTIMIZATION: if fAbove, fBelow have already been computed
+ // for the fTIndex, don't do it again
+ calcAboveBelow(tAbove, tBelow);
+ // For identical x, this lets us know which edge is first.
+ // If both edges have T values < 1, check x at next T (fBelow).
SkASSERT(tAbove != tBelow);
// FIXME: this can loop forever
// need a break if we hit the end
@@ -1523,13 +1566,12 @@
add -= 1;
SkASSERT(fTIndex + add >= 0);
tAbove = t(fTIndex + add);
- (*xyAtTFunc)(fWorkEdge.fPts, tAbove, &fAbove);
} else {
add += 1;
SkASSERT(fTIndex - ~add <= fTs->count() + 1);
tBelow = t(fTIndex - ~add);
- (*xyAtTFunc)(fWorkEdge.fPts, tBelow, &fBelow);
}
+ calcAboveBelow(tAbove, tBelow);
}
fTAbove = tAbove;
fTBelow = tBelow;
@@ -1541,28 +1583,17 @@
void fixBelow() {
if (fFixBelow) {
- switch (fWorkEdge.verb()) {
- case SkPath::kLine_Verb:
- LineXYAtT(fWorkEdge.fPts, nextT(), &fBelow);
- break;
- case SkPath::kQuad_Verb:
- QuadXYAtT(fWorkEdge.fPts, nextT(), &fBelow);
- break;
- case SkPath::kCubic_Verb:
- CubicXYAtT(fWorkEdge.fPts, nextT(), &fBelow);
- break;
- default:
- SkASSERT(0);
- }
+ fTBelow = nextT();
+ calcAboveBelow(fTAbove, fTBelow);
fFixBelow = false;
}
}
void init(const InEdge* edge) {
fWorkEdge.init(edge);
+ fDone = false;
initT();
fBelow.fY = SK_ScalarMin;
- fDone = false;
fYBottom = SK_ScalarMin;
}
@@ -1576,6 +1607,10 @@
// fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs;
// but templated arrays don't allow returning a pointer to the end() element
fTIndex = 0;
+ if (!fDone) {
+ fVerb = fWorkEdge.verb();
+ }
+ SkASSERT(fVerb > SkPath::kMove_Verb);
}
// OPTIMIZATION: record if two edges are coincident when the are intersected
@@ -1586,13 +1621,10 @@
if (fAbove != edge->fAbove || fBelow != edge->fBelow) {
return false;
}
- SkPath::Verb verb = fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();
- SkPath::Verb edgeVerb = edge->fDone ? edge->fWorkEdge.lastVerb()
- : edge->fWorkEdge.verb();
- if (verb != edgeVerb) {
+ if (fVerb != edge->fVerb) {
return false;
}
- switch (verb) {
+ switch (fVerb) {
case SkPath::kLine_Verb:
return true;
default:
@@ -1607,13 +1639,18 @@
return fAbove == edge->fAbove && fBelow == edge->fBelow;
}
- SkPath::Verb lastVerb() const {
- return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();
- }
+// SkPath::Verb lastVerb() const {
+// return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();
+// }
const SkPoint* lastPoints() const {
return fDone ? fWorkEdge.lastPoints() : fWorkEdge.points();
}
+
+ bool noIntersect(const ActiveEdge& ) const {
+ // incomplete
+ return false;
+ }
// The shortest close call edge should be moved into a position where
// it contributes if the winding is transitioning to or from zero.
@@ -1654,8 +1691,8 @@
}
bool swapUnordered(const ActiveEdge* edge, SkScalar bottom) const {
- SkASSERT(lastVerb() != SkPath::kLine_Verb
- || edge->lastVerb() != SkPath::kLine_Verb);
+ SkASSERT(fVerb != SkPath::kLine_Verb
+ || edge->fVerb != SkPath::kLine_Verb);
if (fDone || edge->fDone) {
return false;
}
@@ -1670,24 +1707,24 @@
double t1, t2, b1, b2;
// This logic must be kept in sync with operator <
if (edge->fAbove.fY < fAbove.fY) {
- t1 = (edge->fBelow.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
- t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fBelow.fX - edge->fAbove.fX);
+ t1 = (edge->fTangent.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
+ t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fTangent.fX - edge->fAbove.fX);
} else if (edge->fAbove.fY > fAbove.fY) {
- t1 = (fBelow.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
- t2 = (fAbove.fY - edge->fAbove.fY) * (fBelow.fX - fAbove.fX);
+ t1 = (fTangent.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
+ t2 = (fAbove.fY - edge->fAbove.fY) * (fTangent.fX - fAbove.fX);
} else {
t1 = fAbove.fX;
t2 = edge->fAbove.fX;
}
- if (edge->fBelow.fY > fBelow.fY) {
- b1 = (edge->fBelow.fY - edge->fAbove.fY) * (fBelow.fX - edge->fBelow.fX);
- b2 = (fBelow.fY - edge->fBelow.fY) * (edge->fBelow.fX - edge->fAbove.fX);
- } else if (edge->fBelow.fY < fBelow.fY) {
- b1 = (fBelow.fY - fAbove.fY) * (fBelow.fX - edge->fBelow.fX);
- b2 = (fBelow.fY - edge->fBelow.fY) * (fBelow.fX - fAbove.fX);
+ if (edge->fTangent.fY > fTangent.fY) {
+ b1 = (edge->fTangent.fY - edge->fAbove.fY) * (fTangent.fX - edge->fTangent.fX);
+ b2 = (fTangent.fY - edge->fTangent.fY) * (edge->fTangent.fX - edge->fAbove.fX);
+ } else if (edge->fTangent.fY < fTangent.fY) {
+ b1 = (fTangent.fY - fAbove.fY) * (fTangent.fX - edge->fTangent.fX);
+ b2 = (fTangent.fY - edge->fTangent.fY) * (fTangent.fX - fAbove.fX);
} else {
- b1 = fBelow.fX;
- b2 = edge->fBelow.fX;
+ b1 = fTangent.fX;
+ b2 = edge->fTangent.fX;
}
if (fabs(t1 - t2) > fabs(b1 - b2)) {
ulps = UlpsDiff(t1, t2);
@@ -1701,32 +1738,30 @@
if (ulps < 0 || ulps > 32) {
return false;
}
- SkPath::Verb verb = lastVerb();
- SkPath::Verb edgeVerb = edge->lastVerb();
- if (verb == SkPath::kLine_Verb && edgeVerb == SkPath::kLine_Verb) {
+ if (fVerb == SkPath::kLine_Verb && edge->fVerb == SkPath::kLine_Verb) {
return true;
}
- if (verb != SkPath::kLine_Verb && edgeVerb != SkPath::kLine_Verb) {
+ if (fVerb != SkPath::kLine_Verb && edge->fVerb != SkPath::kLine_Verb) {
return false;
}
double ts[2];
bool isLine = true;
bool curveQuad = true;
- if (verb == SkPath::kCubic_Verb) {
+ if (fVerb == SkPath::kCubic_Verb) {
ts[0] = (fTAbove * 2 + fTBelow) / 3;
ts[1] = (fTAbove + fTBelow * 2) / 3;
curveQuad = isLine = false;
- } else if (edgeVerb == SkPath::kCubic_Verb) {
+ } else if (edge->fVerb == SkPath::kCubic_Verb) {
ts[0] = (edge->fTAbove * 2 + edge->fTBelow) / 3;
ts[1] = (edge->fTAbove + edge->fTBelow * 2) / 3;
curveQuad = false;
- } else if (verb == SkPath::kQuad_Verb) {
+ } else if (fVerb == SkPath::kQuad_Verb) {
ts[0] = fTAbove;
ts[1] = (fTAbove + fTBelow) / 2;
isLine = false;
} else {
- SkASSERT(edgeVerb == SkPath::kQuad_Verb);
+ SkASSERT(edge->fVerb == SkPath::kQuad_Verb);
ts[0] = edge->fTAbove;
ts[1] = (edge->fTAbove + edge->fTBelow) / 2;
}
@@ -1775,10 +1810,10 @@
// utility used only by swapUnordered
void extractAboveBelow(ActiveEdge& extracted) const {
SkPoint curve[4];
- switch (lastVerb()) {
+ switch (fVerb) {
case SkPath::kLine_Verb:
extracted.fAbove = fAbove;
- extracted.fBelow = fBelow;
+ extracted.fTangent = fTangent;
return;
case SkPath::kQuad_Verb:
QuadSubDivide(lastPoints(), fTAbove, fTBelow, curve);
@@ -1790,19 +1825,21 @@
SkASSERT(0);
}
extracted.fAbove = curve[0];
- extracted.fBelow = curve[1];
+ extracted.fTangent = curve[1];
}
public:
WorkEdge fWorkEdge;
const SkTDArray<double>* fTs;
SkPoint fAbove;
+ SkPoint fTangent;
SkPoint fBelow;
double fTAbove; // OPTIMIZATION: only required if edge has quads or cubics
double fTBelow;
SkScalar fYBottom;
int fCoincident;
int fTIndex;
+ SkPath::Verb fVerb;
bool fSkip; // OPTIMIZATION: use bitfields?
bool fCloseCall;
bool fDone;
@@ -2253,17 +2290,16 @@
for (index = 1; index < edgeCount; ++index) {
activePtr = nextPtr;
nextPtr = edgeList[index];
- if (firstIndex != index - 1 && !activePtr->fSkip) {
- if (nextPtr->fWorkEdge.verb() == SkPath::kLine_Verb
- && activePtr->isUnordered(nextPtr)) {
- start here;
- // swap the line with the curve
- // back up to the previous edge and retest
- SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);
- SkASSERT(index > 1);
- index -= 2;
- continue;
- }
+ if (firstIndex != index - 1 && activePtr->fVerb > SkPath::kLine_Verb
+ && nextPtr->fVerb == SkPath::kLine_Verb
+ && activePtr->isUnordered(nextPtr)) {
+ // swap the line with the curve
+ // back up to the previous edge and retest
+ SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);
+ SkASSERT(index > 1);
+ index -= 2;
+ nextPtr = edgeList[index];
+ continue;
}
bool closeCall = false;
activePtr->fCoincident = firstIndex;
@@ -2444,9 +2480,9 @@
bool moreToDo, aboveBottom;
do {
double currentT = activePtr->t();
- uint8_t verb = wt.verb();
const SkPoint* points = wt.fPts;
double nextT;
+ SkPath::Verb verb = activePtr->fVerb;
do {
nextT = activePtr->nextT();
// FIXME: obtuse: want efficient way to say
@@ -2503,9 +2539,10 @@
// will use these values if they're still valid instead of
// recomputing
if (clipped[verb].fY > activePtr->fBelow.fY
- && bottom >= activePtr->fBelow.fY ) {
+ && bottom >= activePtr->fBelow.fY
+ && verb == SkPath::kLine_Verb) {
activePtr->fAbove = activePtr->fBelow;
- activePtr->fBelow = clipped[verb];
+ activePtr->fBelow = activePtr->fTangent = clipped[verb];
activePtr->fTAbove = activePtr->fTBelow < 1
? activePtr->fTBelow : 0;
activePtr->fTBelow = nextT;
@@ -2609,6 +2646,17 @@
// if a quadratic or cubic now has an intermediate T value, see if the Ts
// on either side cause the Y values to monotonically increase. If not, split
// the curve at the new T.
+
+ // try an alternate approach which does not split curves or stitch edges
+ // (may still need adjustCoincident, though)
+ // the idea is to output non-intersecting contours, then figure out their
+ // respective winding contribution
+ // each contour will need to know whether it is CW or CCW, and then whether
+ // a ray from that contour hits any a contour that contains it. The ray can
+ // move to the left and then arbitrarily move up or down (as long as it never
+ // moves to the right) to find a reference sibling contour or containing
+ // contour. If the contour is part of an intersection, the companion contour
+ // that is part of the intersection can determine the containership.
if (builder.containsCurves()) {
currentPtr = edgeList.begin();
SkTArray<InEdge> splits;
diff --git a/experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp b/experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp
new file mode 100644
index 0000000..75fd9a4
--- /dev/null
+++ b/experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp
@@ -0,0 +1,101 @@
+#include "EdgeWalker_Test.h"
+#include "Intersection_Tests.h"
+#include "SkBitmap.h"
+#include "SkCanvas.h"
+#include <assert.h>
+
+
+static void* testSimplify4x4QuadraticsMain(void* data)
+{
+ char pathStr[1024];
+ bzero(pathStr, sizeof(pathStr));
+ SkASSERT(data);
+ State4& state = *(State4*) data;
+ int ax = state.a & 0x03;
+ int ay = state.a >> 2;
+ int bx = state.b & 0x03;
+ int by = state.b >> 2;
+ int cx = state.c & 0x03;
+ int cy = state.c >> 2;
+ int dx = state.d & 0x03;
+ int dy = state.d >> 2;
+ for (int e = 0 ; e < 16; ++e) {
+ int ex = e & 0x03;
+ int ey = e >> 2;
+ for (int f = e ; f < 16; ++f) {
+ int fx = f & 0x03;
+ int fy = f >> 2;
+ for (int g = f ; g < 16; ++g) {
+ int gx = g & 0x03;
+ int gy = g >> 2;
+ for (int h = g ; h < 16; ++h) {
+ int hx = h & 0x03;
+ int hy = h >> 2;
+ SkPath path, out;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(ax, ay);
+ path.quadTo(bx, by, cx, cy);
+ path.lineTo(dx, dy);
+ path.close();
+ path.moveTo(ex, ey);
+ path.lineTo(fx, fy);
+ path.quadTo(gx, gy, hx, hy);
+ path.close();
+ if (1) { // gdb: set print elements 400
+ char* str = pathStr;
+ str += sprintf(str, " path.moveTo(%d, %d);\n", ax, ay);
+ str += sprintf(str, " path.quadTo(%d, %d, %d, %d);\n", bx, by, cx, cy);
+ str += sprintf(str, " path.lineTo(%d, %d);\n", dx, dy);
+ str += sprintf(str, " path.close();\n");
+ str += sprintf(str, " path.moveTo(%d, %d);\n", ex, ey);
+ str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy);
+ str += sprintf(str, " path.quadTo(%d, %d, %d, %d);\n", gx, gy, hx, hy);
+ str += sprintf(str, " path.close();");
+ }
+ if (!testSimplify(path, true, out, state.bitmap, state.canvas)) {
+ SkDebugf("*/\n{ SkPath::kWinding_FillType, %d, %d, %d, %d,"
+ " %d, %d, %d, %d },\n/*\n", state.a, state.b, state.c, state.d,
+ e, f, g, h);
+ }
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ if (!testSimplify(path, true, out, state.bitmap, state.canvas)) {
+ SkDebugf("*/\n{ SkPath::kEvenOdd_FillType, %d, %d, %d, %d,"
+ " %d, %d, %d, %d },\n/*\n", state.a, state.b, state.c, state.d,
+ e, f, g, h);
+ }
+ }
+ }
+ }
+ }
+ return NULL;
+}
+
+const int maxThreads = gRunTestsInOneThread ? 1 : 24;
+
+void Simplify4x4QuadraticsThreaded_Test()
+{
+ State4 threadState[maxThreads];
+ int threadIndex = 0;
+ for (int a = 0; a < 16; ++a) {
+ for (int b = a ; b < 16; ++b) {
+ for (int c = b ; c < 16; ++c) {
+ for (int d = c; d < 16; ++d) {
+ State4* statePtr = &threadState[threadIndex];
+ statePtr->a = a;
+ statePtr->b = b;
+ statePtr->c = c;
+ statePtr->d = d;
+ if (maxThreads > 1) {
+ createThread(statePtr, testSimplify4x4QuadraticsMain);
+ if (++threadIndex >= maxThreads) {
+ waitForCompletion(threadState, threadIndex);
+ }
+ } else {
+ testSimplify4x4QuadraticsMain(statePtr);
+ }
+ }
+ }
+ }
+ }
+ waitForCompletion(threadState, threadIndex);
+}
diff --git a/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
index 96ba2f3..f6bf824 100644
--- a/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
@@ -218,7 +218,22 @@
drawAsciiPaths(path, out, true);
}
+static void testSimplifyQuadratic17() {
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(0, 1);
+ path.lineTo(0, 1);
+ path.quadTo(2, 1, 3, 3);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
+
static void (*simplifyTests[])() = {
+ testSimplifyQuadratic17,
testSimplifyQuadratic16,
testSimplifyQuadratic15,
testSimplifyQuadratic14,
@@ -239,7 +254,7 @@
static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]);
-static void (*firstTest)() = 0;
+static void (*firstTest)() = testSimplifyQuadratic14;
static bool skipAll = false;
void SimplifyQuadraticPaths_Test() {
diff --git a/experimental/Intersection/Extrema.cpp b/experimental/Intersection/Extrema.cpp
index 0b85060..386f092 100644
--- a/experimental/Intersection/Extrema.cpp
+++ b/experimental/Intersection/Extrema.cpp
@@ -1,20 +1,18 @@
#include "DataTypes.h"
#include "Extrema.h"
-static int valid_unit_divide(double numer, double denom, double* ratio)
+static int validUnitDivide(double numer, double denom, double* ratio)
{
- if (numer < 0)
- {
+ if (numer < 0) {
numer = -numer;
denom = -denom;
}
-
if (denom == 0 || numer == 0 || numer >= denom)
return 0;
-
double r = numer / denom;
- if (r == 0) // catch underflow if numer <<<< denom
+ if (r == 0) { // catch underflow if numer <<<< denom
return 0;
+ }
*ratio = r;
return 1;
}
@@ -25,10 +23,10 @@
x1 = Q / A
x2 = C / Q
*/
-static int SkFindUnitQuadRoots(double A, double B, double C, double roots[2])
+static int findUnitQuadRoots(double A, double B, double C, double roots[2])
{
if (A == 0)
- return valid_unit_divide(-C, B, roots);
+ return validUnitDivide(-C, B, roots);
double* r = roots;
@@ -39,8 +37,8 @@
R = sqrt(R);
double Q = (B < 0) ? -(B-R)/2 : -(B+R)/2;
- r += valid_unit_divide(Q, A, r);
- r += valid_unit_divide(C, Q, r);
+ r += validUnitDivide(Q, A, r);
+ r += validUnitDivide(C, Q, r);
if (r - roots == 2 && approximately_equal(roots[0], roots[1])) { // nearly-equal?
r -= 1; // skip the double root
}
@@ -51,16 +49,16 @@
A = 3(-a + 3(b - c) + d)
B = 6(a - 2b + c)
C = 3(b - a)
- Solve for t, keeping only those that fit betwee 0 < t < 1
+ Solve for t, keeping only those that fit between 0 < t < 1
*/
-int SkFindCubicExtrema(double a, double b, double c, double d, double tValues[2])
+int findExtrema(double a, double b, double c, double d, double tValues[2])
{
// we divide A,B,C by 3 to simplify
double A = d - a + 3*(b - c);
double B = 2*(a - b - b + c);
double C = b - a;
- return SkFindUnitQuadRoots(A, B, C, tValues);
+ return findUnitQuadRoots(A, B, C, tValues);
}
/** Quad'(t) = At + B, where
@@ -68,10 +66,10 @@
B = 2(b - a)
Solve for t, only if it fits between 0 < t < 1
*/
-int SkFindQuadExtrema(double a, double b, double c, double tValue[1])
+int findExtrema(double a, double b, double c, double tValue[1])
{
/* At + B == 0
t = -B / A
*/
- return valid_unit_divide(a - b, a - b - b + c, tValue);
+ return validUnitDivide(a - b, a - b - b + c, tValue);
}
diff --git a/experimental/Intersection/Extrema.h b/experimental/Intersection/Extrema.h
index aae422e..0988540 100644
--- a/experimental/Intersection/Extrema.h
+++ b/experimental/Intersection/Extrema.h
@@ -1,2 +1,2 @@
-int SkFindCubicExtrema(double a, double b, double c, double d, double tValues[2]);
-int SkFindQuadExtrema(double a, double b, double c, double tValue[1]);
+int findExtrema(double a, double b, double c, double d, double tValues[2]);
+int findExtrema(double a, double b, double c, double tValue[1]);
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 0179cb7..e3c042c 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -4,12 +4,10 @@
void cubecode_test(int test);
void testSimplify();
-#define TEST_QUADS_FIRST 01
+#define TEST_QUADS_FIRST 0
void Intersection_Tests() {
-#if !TEST_QUADS_FIRST
- ActiveEdge_Test();
-#endif
+ SimplifyAddIntersectingTs_Test();
cubecode_test(1);
convert_testx();
@@ -29,8 +27,8 @@
SimplifyRectangularPaths_Test();
SimplifyQuadralateralPaths_Test();
-#if TEST_QUADS_FIRST
ActiveEdge_Test();
+#if TEST_QUADS_FIRST
Simplify4x4QuadraticsThreaded_Test();
#endif
SimplifyDegenerate4x4TrianglesThreaded_Test();
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index e0d892d..a2d9df6 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -12,6 +12,7 @@
void LineIntersection_Test();
void LineParameter_Test();
void LineQuadraticIntersection_Test();
+void SimplifyAddIntersectingTs_Test();
void SimplifyDegenerate4x4TrianglesThreaded_Test();
void SimplifyNondegenerate4x4TrianglesThreaded_Test();
void SimplifyPolygonPaths_Test();
diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp
index 8517b7e..6f2cf6c 100644
--- a/experimental/Intersection/LineCubicIntersection.cpp
+++ b/experimental/Intersection/LineCubicIntersection.cpp
@@ -109,6 +109,13 @@
return cubicRoots(A, B, C, D, range);
}
+int verticalIntersect(double axisIntercept) {
+ double A, B, C, D;
+ coefficients(&cubic[0].x, A, B, C, D);
+ D -= axisIntercept;
+ return cubicRoots(A, B, C, D, range);
+}
+
double findLineT(double t) {
const double* cPtr;
const double* lPtr;
@@ -158,6 +165,56 @@
return result;
}
+int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
+ bool flipped, Intersections& intersections) {
+ LineCubicIntersections c(cubic, *((_Line*) 0), intersections.fT[0]);
+ int result = c.horizontalIntersect(y);
+ for (int index = 0; index < result; ) {
+ double x, y;
+ xy_at_t(cubic, intersections.fT[0][index], x, y);
+ if (x < left || x > right) {
+ if (--result > index) {
+ intersections.fT[0][index] = intersections.fT[0][result];
+ }
+ continue;
+ }
+ intersections.fT[0][index] = (x - left) / (right - left);
+ ++index;
+ }
+ if (flipped) {
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
+ for (int index = 0; index < result; ++index) {
+ intersections.fT[1][index] = 1 - intersections.fT[1][index];
+ }
+ }
+ return result;
+}
+
+int verticalIntersect(const Cubic& cubic, double top, double bottom, double x,
+ bool flipped, Intersections& intersections) {
+ LineCubicIntersections c(cubic, *((_Line*) 0), intersections.fT[0]);
+ int result = c.verticalIntersect(x);
+ for (int index = 0; index < result; ) {
+ double x, y;
+ xy_at_t(cubic, intersections.fT[0][index], x, y);
+ if (y < top || y > bottom) {
+ if (--result > index) {
+ intersections.fT[0][index] = intersections.fT[0][result];
+ }
+ continue;
+ }
+ intersections.fT[0][index] = (y - top) / (bottom - top);
+ ++index;
+ }
+ if (flipped) {
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
+ for (int index = 0; index < result; ++index) {
+ intersections.fT[1][index] = 1 - intersections.fT[1][index];
+ }
+ }
+ return result;
+}
+
int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]) {
LineCubicIntersections c(cubic, line, cRange);
int roots;
diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp
index f5128ea..40e046c 100644
--- a/experimental/Intersection/LineIntersection.cpp
+++ b/experimental/Intersection/LineIntersection.cpp
@@ -1,4 +1,5 @@
#include "DataTypes.h"
+#include "Intersections.h"
#include "LineIntersection.h"
#include <algorithm> // used for std::swap
@@ -112,9 +113,9 @@
double y, double tRange[2]) {
int result = horizontalIntersect(line, y, tRange);
if (result != 1) {
+ // FIXME: this is incorrect if result == 2
return result;
}
- // FIXME: this is incorrect if result == 2
double xIntercept = line[0].x + tRange[0] * (line[1].x - line[0].x);
if (xIntercept > right || xIntercept < left) {
return 0;
@@ -122,6 +123,116 @@
return result;
}
+int horizontalIntersect(const _Line& line, double left, double right,
+ double y, bool flipped, Intersections& intersections) {
+ int result = horizontalIntersect(line, y, intersections.fT[0]);
+ switch (result) {
+ case 0:
+ break;
+ case 1: {
+ double xIntercept = line[0].x + intersections.fT[0][0]
+ * (line[1].x - line[0].x);
+ if (xIntercept > right || xIntercept < left) {
+ return 0;
+ }
+ intersections.fT[1][0] = (xIntercept - left) / (right - left);
+ break;
+ }
+ case 2:
+ double lineL = line[0].x;
+ double lineR = line[1].x;
+ if (lineL > lineR) {
+ std::swap(lineL, lineR);
+ }
+ double overlapL = std::max(left, lineL);
+ double overlapR = std::min(right, lineR);
+ if (overlapL > overlapR) {
+ return 0;
+ }
+ if (overlapL == overlapR) {
+ result = 1;
+ }
+ intersections.fT[0][0] = (overlapL - line[0].x) / (line[1].x - line[0].x);
+ intersections.fT[1][0] = (overlapL - left) / (right - left);
+ if (result > 1) {
+ intersections.fT[0][1] = (overlapR - line[0].x) / (line[1].x - line[0].x);
+ intersections.fT[1][1] = (overlapR - left) / (right - left);
+ }
+ break;
+ }
+ if (flipped) {
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
+ for (int index = 0; index < result; ++index) {
+ intersections.fT[1][index] = 1 - intersections.fT[1][index];
+ }
+ }
+ return result;
+}
+
+int verticalIntersect(const _Line& line, double x, double tRange[2]) {
+ double min = line[0].x;
+ double max = line[1].x;
+ if (min > max) {
+ std::swap(min, max);
+ }
+ if (min > x || max < x) {
+ return 0;
+ }
+ if (approximately_equal(min, max)) {
+ tRange[0] = 0;
+ tRange[1] = 1;
+ return 2;
+ }
+ tRange[0] = (x - line[0].x) / (line[1].x - line[0].x);
+ return 1;
+}
+
+int verticalIntersect(const _Line& line, double top, double bottom,
+ double x, bool flipped, Intersections& intersections) {
+ int result = verticalIntersect(line, x, intersections.fT[0]);
+ switch (result) {
+ case 0:
+ break;
+ case 1: {
+ double yIntercept = line[0].y + intersections.fT[0][0]
+ * (line[1].y - line[0].y);
+ if (yIntercept > bottom || yIntercept < top) {
+ return 0;
+ }
+ intersections.fT[1][0] = (yIntercept - top) / (bottom - top);
+ break;
+ }
+ case 2:
+ double lineT = line[0].y;
+ double lineB = line[1].y;
+ if (lineT > lineB) {
+ std::swap(lineT, lineB);
+ }
+ double overlapT = std::max(top, lineT);
+ double overlapB = std::min(bottom, lineB);
+ if (overlapT > overlapB) {
+ return 0;
+ }
+ if (overlapT == overlapB) {
+ result = 1;
+ }
+ intersections.fT[0][0] = (overlapT - line[0].y) / (line[1].y - line[0].y);
+ intersections.fT[1][0] = (overlapT - top) / (bottom - top);
+ if (result > 1) {
+ intersections.fT[0][1] = (overlapB - line[0].y) / (line[1].y - line[0].y);
+ intersections.fT[1][1] = (overlapB - top) / (bottom - top);
+ }
+ break;
+ }
+ if (flipped) {
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y
+ for (int index = 0; index < result; ++index) {
+ intersections.fT[1][index] = 1 - intersections.fT[1][index];
+ }
+ }
+ return result;
+}
+
// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
// 4 subs, 2 muls, 1 cmp
static bool ccw(const _Point& A, const _Point& B, const _Point& C) {
diff --git a/experimental/Intersection/LineIntersection.h b/experimental/Intersection/LineIntersection.h
index bb8b4b7..d88e1f4 100644
--- a/experimental/Intersection/LineIntersection.h
+++ b/experimental/Intersection/LineIntersection.h
@@ -6,6 +6,8 @@
int horizontalIntersect(const _Line& line, double y, double tRange[2]);
int horizontalLineIntersect(const _Line& line, double left, double right,
double y, double tRange[2]);
+int verticalLineIntersect(const _Line& line, double top, double bottom,
+ double x, double tRange[2]);
int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]);
bool testIntersect(const _Line& a, const _Line& b);
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index 737b767..1bc831b 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -141,6 +141,16 @@
return quadraticRoots(D, E, F, intersections.fT[0]);
}
+int verticalIntersect(double axisIntercept) {
+ double D = quad[2].x; // f
+ double E = quad[1].x; // e
+ double F = quad[0].x; // d
+ D += F - 2 * E; // D = d - 2*e + f
+ E -= F; // E = -(d - e)
+ F -= axisIntercept;
+ return quadraticRoots(D, E, F, intersections.fT[0]);
+}
+
protected:
double findLineT(double t) {
@@ -167,6 +177,46 @@
};
+// utility for pairs of coincident quads
+static double horizontalIntersect(const Quadratic& quad, const _Point& pt) {
+ Intersections intersections;
+ LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
+ int result = q.horizontalIntersect(pt.y);
+ if (result == 0) {
+ return -1;
+ }
+ assert(result == 1);
+ double x, y;
+ xy_at_t(quad, intersections.fT[0][0], x, y);
+ if (approximately_equal(x, pt.x)) {
+ return intersections.fT[0][0];
+ }
+ return -1;
+}
+
+static double verticalIntersect(const Quadratic& quad, const _Point& pt) {
+ Intersections intersections;
+ LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
+ int result = q.horizontalIntersect(pt.x);
+ if (result == 0) {
+ return -1;
+ }
+ assert(result == 1);
+ double x, y;
+ xy_at_t(quad, intersections.fT[0][0], x, y);
+ if (approximately_equal(y, pt.y)) {
+ return intersections.fT[0][0];
+ }
+ return -1;
+}
+
+double axialIntersect(const Quadratic& q1, const _Point& p, bool vertical) {
+ if (vertical) {
+ return verticalIntersect(q1, p);
+ }
+ return horizontalIntersect(q1, p);
+}
+
int horizontalIntersect(const Quadratic& quad, double left, double right,
double y, double tRange[2]) {
Intersections i;
@@ -184,6 +234,56 @@
return tCount;
}
+int horizontalIntersect(const Quadratic& quad, double left, double right, double y,
+ bool flipped, Intersections& intersections) {
+ LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
+ int result = q.horizontalIntersect(y);
+ for (int index = 0; index < result; ) {
+ double x, y;
+ xy_at_t(quad, intersections.fT[0][index], x, y);
+ if (x < left || x > right) {
+ if (--result > index) {
+ intersections.fT[0][index] = intersections.fT[0][result];
+ }
+ continue;
+ }
+ intersections.fT[0][index] = (x - left) / (right - left);
+ ++index;
+ }
+ if (flipped) {
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
+ for (int index = 0; index < result; ++index) {
+ intersections.fT[1][index] = 1 - intersections.fT[1][index];
+ }
+ }
+ return result;
+}
+
+int verticalIntersect(const Quadratic& quad, double top, double bottom, double x,
+ bool flipped, Intersections& intersections) {
+ LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
+ int result = q.verticalIntersect(x);
+ for (int index = 0; index < result; ) {
+ double x, y;
+ xy_at_t(quad, intersections.fT[0][index], x, y);
+ if (y < top || y > bottom) {
+ if (--result > index) {
+ intersections.fT[0][index] = intersections.fT[0][result];
+ }
+ continue;
+ }
+ intersections.fT[0][index] = (y - top) / (bottom - top);
+ ++index;
+ }
+ if (flipped) {
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
+ for (int index = 0; index < result; ++index) {
+ intersections.fT[1][index] = 1 - intersections.fT[1][index];
+ }
+ }
+ return result;
+}
+
bool intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
LineQuadraticIntersections q(quad, line, i);
return q.intersect();
diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
index 017a44e..a48f0af 100644
--- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
@@ -8,7 +8,9 @@
Quadratic quad;
_Line line;
} lineQuadTests[] = {
- {{{0, 0}, {0, 1}, {1, 1}}, {{0, 1}, {1, 0}}}
+ {{{2, 0}, {1, 1}, {2, 2}}, {{0, 0}, {0, 2}}},
+ {{{4, 0}, {0, 1}, {4, 2}}, {{3, 1}, {4, 1}}},
+ {{{0, 0}, {0, 1}, {1, 1}}, {{0, 1}, {1, 0}}},
};
size_t lineQuadTests_count = sizeof(lineQuadTests) / sizeof(lineQuadTests[0]);
diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp
index 1394225..38e1ba0 100644
--- a/experimental/Intersection/LineUtilities.cpp
+++ b/experimental/Intersection/LineUtilities.cpp
@@ -30,3 +30,28 @@
dst[1].x = line[0].x - t2 * delta.x;
dst[1].y = line[0].y - t2 * delta.y;
}
+
+// may have this below somewhere else already:
+// copying here because I thought it was clever
+
+// Copyright 2001, softSurfer (www.softsurfer.com)
+// This code may be freely used and modified for any purpose
+// providing that this copyright notice is included with it.
+// SoftSurfer makes no warranty for this code, and cannot be held
+// liable for any real or imagined damage resulting from its use.
+// Users of this code must verify correctness for their application.
+
+// Assume that a class is already given for the object:
+// Point with coordinates {float x, y;}
+//===================================================================
+
+// isLeft(): tests if a point is Left|On|Right of an infinite line.
+// Input: three points P0, P1, and P2
+// Return: >0 for P2 left of the line through P0 and P1
+// =0 for P2 on the line
+// <0 for P2 right of the line
+// See: the January 2001 Algorithm on Area of Triangles
+float isLeft( _Point P0, _Point P1, _Point P2 )
+{
+ return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
+}
diff --git a/experimental/Intersection/QuadraticBounds.cpp b/experimental/Intersection/QuadraticBounds.cpp
new file mode 100644
index 0000000..11591b3
--- /dev/null
+++ b/experimental/Intersection/QuadraticBounds.cpp
@@ -0,0 +1,46 @@
+#include "DataTypes.h"
+#include "Extrema.h"
+
+static int isBoundedByEndPoints(double a, double b, double c)
+{
+ return (a <= b && b <= c) || (a >= b && b >= c);
+}
+
+double leftMostT(const Quadratic& quad, double startT, double endT) {
+ double leftT;
+ if (findExtrema(quad[0].x, quad[1].x, quad[2].x, &leftT)
+ && startT <= leftT && leftT <= endT) {
+ return leftT;
+ }
+ _Point startPt;
+ xy_at_t(quad, startT, startPt.x, startPt.y);
+ _Point endPt;
+ xy_at_t(quad, endT, endPt.x, endPt.y);
+ return startPt.x <= endPt.x ? startT : endT;
+}
+
+void _Rect::setBounds(const Quadratic& quad) {
+ set(quad[0]);
+ add(quad[2]);
+ double tValues[2];
+ int roots = 0;
+ if (!isBoundedByEndPoints(quad[0].x, quad[1].x, quad[2].x)) {
+ roots = findExtrema(quad[0].x, quad[1].x, quad[2].x, tValues);
+ }
+ if (!isBoundedByEndPoints(quad[0].y, quad[1].y, quad[2].y)) {
+ roots += findExtrema(quad[0].y, quad[1].y, quad[2].y,
+ &tValues[roots]);
+ }
+ for (int x = 0; x < roots; ++x) {
+ _Point result;
+ xy_at_t(quad, tValues[x], result.x, result.y);
+ add(result);
+ }
+}
+
+void _Rect::setRawBounds(const Quadratic& quad) {
+ set(quad[0]);
+ for (int x = 1; x < 3; ++x) {
+ add(quad[x]);
+ }
+}
diff --git a/experimental/Intersection/QuadraticIntersection.cpp b/experimental/Intersection/QuadraticIntersection.cpp
index f8c43b5..a8e87ef 100644
--- a/experimental/Intersection/QuadraticIntersection.cpp
+++ b/experimental/Intersection/QuadraticIntersection.cpp
@@ -97,7 +97,6 @@
double newMinT2 = interp(minT2, maxT2, minT);
double newMaxT2 = interp(minT2, maxT2, maxT);
split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit;
-#define VERBOSE 0
#if VERBOSE
printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n", __FUNCTION__, depth,
splits, newMinT2, newMaxT2, minT2, maxT2, split);
@@ -144,6 +143,35 @@
};
bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
+ if (implicit_matches(q1, q2)) {
+ // FIXME: compute T values
+ // compute the intersections of the ends to find the coincident span
+ bool useVertical = fabs(q1[0].x - q1[2].x) < fabs(q1[0].y - q1[2].y);
+ double t;
+ if ((t = axialIntersect(q1, q2[0], useVertical)) >= 0) {
+ i.fT[0][0] = t;
+ i.fT[1][0] = 0;
+ i.fUsed++;
+ }
+ if ((t = axialIntersect(q1, q2[2], useVertical)) >= 0) {
+ i.fT[0][i.fUsed] = t;
+ i.fT[1][i.fUsed] = 1;
+ i.fUsed++;
+ }
+ useVertical = fabs(q2[0].x - q2[2].x) < fabs(q2[0].y - q2[2].y);
+ if ((t = axialIntersect(q2, q1[0], useVertical)) >= 0) {
+ i.fT[0][i.fUsed] = 0;
+ i.fT[1][i.fUsed] = t;
+ i.fUsed++;
+ }
+ if ((t = axialIntersect(q2, q1[2], useVertical)) >= 0) {
+ i.fT[0][i.fUsed] = 1;
+ i.fT[1][i.fUsed] = t;
+ i.fUsed++;
+ }
+ assert(i.fUsed <= 2);
+ return i.fUsed > 0;
+ }
QuadraticIntersections q(q1, q2, i);
return q.intersect();
}
diff --git a/experimental/Intersection/QuadraticReduceOrder.cpp b/experimental/Intersection/QuadraticReduceOrder.cpp
index e6ce044..4eef1a7 100644
--- a/experimental/Intersection/QuadraticReduceOrder.cpp
+++ b/experimental/Intersection/QuadraticReduceOrder.cpp
@@ -21,7 +21,7 @@
reduction[1] = quad[2];
int smaller = reduction[1].y > reduction[0].y;
int larger = smaller ^ 1;
- if (SkFindQuadExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue)) {
+ if (findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue)) {
double yExtrema = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue);
if (reduction[smaller].y > yExtrema) {
reduction[smaller].y = yExtrema;
@@ -38,7 +38,7 @@
reduction[1] = quad[2];
int smaller = reduction[1].x > reduction[0].x;
int larger = smaller ^ 1;
- if (SkFindQuadExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue)) {
+ if (findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue)) {
double xExtrema = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue);
if (reduction[smaller].x > xExtrema) {
reduction[smaller].x = xExtrema;
@@ -85,9 +85,9 @@
double tValue;
int root;
if (useX) {
- root = SkFindQuadExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue);
+ root = findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue);
} else {
- root = SkFindQuadExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue);
+ root = findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue);
}
if (root) {
_Point extrema;
@@ -146,8 +146,8 @@
minYSet |= 1 << index;
}
}
- if (minXSet == 0xF) { // test for vertical line
- if (minYSet == 0xF) { // return 1 if all four are coincident
+ if (minXSet == 0x7) { // test for vertical line
+ if (minYSet == 0x7) { // return 1 if all four are coincident
return coincident_line(quad, reduction);
}
return vertical_line(quad, reduction);
diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp
index ea4cd85..4b4d794 100644
--- a/experimental/Intersection/QuadraticUtilities.cpp
+++ b/experimental/Intersection/QuadraticUtilities.cpp
@@ -25,5 +25,3 @@
}
return foundRoots;
}
-
-
diff --git a/experimental/Intersection/RectUtilities.cpp b/experimental/Intersection/RectUtilities.cpp
index e7bda02..e69de29 100644
--- a/experimental/Intersection/RectUtilities.cpp
+++ b/experimental/Intersection/RectUtilities.cpp
@@ -1,44 +0,0 @@
-#include "DataTypes.h"
-#include "Extrema.h"
-
-void _Rect::setBounds(const Cubic& cubic) {
- set(cubic[0]);
- add(cubic[3]);
- double tValues[4];
- int roots = SkFindCubicExtrema(cubic[0].x, cubic[1].x, cubic[2].x,
- cubic[3].x, tValues);
- roots += SkFindCubicExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y,
- &tValues[roots]);
- for (int x = 0; x < roots; ++x) {
- _Point result;
- xy_at_t(cubic, tValues[x], result.x, result.y);
- add(result);
- }
-}
-
-void _Rect::setRawBounds(const Cubic& cubic) {
- set(cubic[0]);
- for (int x = 1; x < 4; ++x) {
- add(cubic[x]);
- }
-}
-
-void _Rect::setBounds(const Quadratic& quad) {
- set(quad[0]);
- add(quad[2]);
- double tValues[2];
- int roots = SkFindQuadExtrema(quad[0].x, quad[1].x, quad[2].x, tValues);
- roots += SkFindQuadExtrema(quad[0].y, quad[1].y, quad[2].y, &tValues[roots]);
- for (int x = 0; x < roots; ++x) {
- _Point result;
- xy_at_t(quad, tValues[x], result.x, result.y);
- add(result);
- }
-}
-
-void _Rect::setRawBounds(const Quadratic& quad) {
- set(quad[0]);
- for (int x = 1; x < 3; ++x) {
- add(quad[x]);
- }
-}
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
new file mode 100644
index 0000000..5d7209a
--- /dev/null
+++ b/experimental/Intersection/Simplify.cpp
@@ -0,0 +1,1213 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "CurveIntersection.h"
+#include "Intersections.h"
+#include "LineIntersection.h"
+#include "SkPath.h"
+#include "SkRect.h"
+#include "SkTArray.h"
+#include "SkTDArray.h"
+#include "ShapeOps.h"
+#include "TSearch.h"
+
+#undef SkASSERT
+#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
+
+// FIXME: remove once debugging is complete
+#if 0 // set to 1 for no debugging whatsoever
+
+//const bool gxRunTestsInOneThread = false;
+
+#define DEBUG_ADD_INTERSECTING_TS 0
+#define DEBUG_BRIDGE 0
+#define DEBUG_DUMP 0
+
+#else
+
+//const bool gRunTestsInOneThread = true;
+
+#define DEBUG_ADD_INTERSECTING_TS 1
+#define DEBUG_BRIDGE 1
+#define DEBUG_DUMP 1
+
+#endif
+
+#if DEBUG_DUMP
+static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
+static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
+static int gContourID;
+static int gSegmentID;
+#endif
+
+static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
+ Intersections& intersections) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
+}
+
+static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
+ Intersections& intersections) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ intersect(aQuad, bLine, intersections);
+ return intersections.fUsed;
+}
+
+static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
+ Intersections& intersections) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
+}
+
+static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
+ Intersections& intersections) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
+ intersect(aQuad, bQuad, intersections);
+ return intersections.fUsed;
+}
+
+static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
+ Intersections& intersections) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY},
+ {b[3].fX, b[3].fY}};
+ intersect(aCubic, bCubic, intersections);
+ return intersections.fUsed;
+}
+
+static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
+ SkScalar y, bool flipped, Intersections& intersections) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ return horizontalIntersect(aLine, left, right, y, flipped, intersections);
+}
+
+static int VLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
+ SkScalar y, bool flipped, Intersections& intersections) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ return verticalIntersect(aLine, left, right, y, flipped, intersections);
+}
+
+static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
+ SkScalar y, bool flipped, Intersections& intersections) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
+}
+
+static int VQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
+ SkScalar y, bool flipped, Intersections& intersections) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ return verticalIntersect(aQuad, left, right, y, flipped, intersections);
+}
+
+static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
+ SkScalar y, bool flipped, Intersections& intersections) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
+}
+
+static int VCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
+ SkScalar y, bool flipped, Intersections& intersections) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ return verticalIntersect(aCubic, left, right, y, flipped, intersections);
+}
+
+static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
+ const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ double x, y;
+ xy_at_t(line, t, x, y);
+ out->fX = SkDoubleToScalar(x);
+ out->fY = SkDoubleToScalar(y);
+}
+
+static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
+ const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ double x, y;
+ xy_at_t(quad, t, x, y);
+ out->fX = SkDoubleToScalar(x);
+ out->fY = SkDoubleToScalar(y);
+}
+
+static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
+ const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ double x, y;
+ xy_at_t(cubic, t, x, y);
+ out->fX = SkDoubleToScalar(x);
+ out->fY = SkDoubleToScalar(y);
+}
+
+static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {
+ NULL,
+ LineXYAtT,
+ QuadXYAtT,
+ CubicXYAtT
+};
+
+static SkScalar LineXAtT(const SkPoint a[2], double t) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ double x;
+ xy_at_t(aLine, t, x, *(double*) 0);
+ return SkDoubleToScalar(x);
+}
+
+static SkScalar QuadXAtT(const SkPoint a[3], double t) {
+ const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ double x;
+ xy_at_t(quad, t, x, *(double*) 0);
+ return SkDoubleToScalar(x);
+}
+
+static SkScalar CubicXAtT(const SkPoint a[4], double t) {
+ const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ double x;
+ xy_at_t(cubic, t, x, *(double*) 0);
+ return SkDoubleToScalar(x);
+}
+
+static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {
+ NULL,
+ LineXAtT,
+ QuadXAtT,
+ CubicXAtT
+};
+
+static SkScalar LineYAtT(const SkPoint a[2], double t) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ double y;
+ xy_at_t(aLine, t, *(double*) 0, y);
+ return SkDoubleToScalar(y);
+}
+
+static SkScalar QuadYAtT(const SkPoint a[3], double t) {
+ const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ double y;
+ xy_at_t(quad, t, *(double*) 0, y);
+ return SkDoubleToScalar(y);
+}
+
+static SkScalar CubicYAtT(const SkPoint a[4], double t) {
+ const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ double y;
+ xy_at_t(cubic, t, *(double*) 0, y);
+ return SkDoubleToScalar(y);
+}
+
+static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {
+ NULL,
+ LineYAtT,
+ QuadYAtT,
+ CubicYAtT
+};
+
+static void LineSubDivide(const SkPoint a[2], double startT, double endT,
+ SkPoint sub[2]) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ _Line dst;
+ sub_divide(aLine, startT, endT, dst);
+ sub[0].fX = SkDoubleToScalar(dst[0].x);
+ sub[0].fY = SkDoubleToScalar(dst[0].y);
+ sub[1].fX = SkDoubleToScalar(dst[1].x);
+ sub[1].fY = SkDoubleToScalar(dst[1].y);
+}
+
+static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
+ SkPoint sub[3]) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}};
+ Quadratic dst;
+ sub_divide(aQuad, startT, endT, dst);
+ sub[0].fX = SkDoubleToScalar(dst[0].x);
+ sub[0].fY = SkDoubleToScalar(dst[0].y);
+ sub[1].fX = SkDoubleToScalar(dst[1].x);
+ sub[1].fY = SkDoubleToScalar(dst[1].y);
+ sub[2].fX = SkDoubleToScalar(dst[2].x);
+ sub[2].fY = SkDoubleToScalar(dst[2].y);
+}
+
+static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
+ SkPoint sub[4]) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
+ Cubic dst;
+ sub_divide(aCubic, startT, endT, dst);
+ sub[0].fX = SkDoubleToScalar(dst[0].x);
+ sub[0].fY = SkDoubleToScalar(dst[0].y);
+ sub[1].fX = SkDoubleToScalar(dst[1].x);
+ sub[1].fY = SkDoubleToScalar(dst[1].y);
+ sub[2].fX = SkDoubleToScalar(dst[2].x);
+ sub[2].fY = SkDoubleToScalar(dst[2].y);
+ sub[3].fX = SkDoubleToScalar(dst[3].x);
+ sub[3].fY = SkDoubleToScalar(dst[3].y);
+}
+
+static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
+ SkRect& bounds) {
+ SkPoint dst[3];
+ QuadSubDivide(a, startT, endT, dst);
+ bounds.fLeft = bounds.fRight = dst[0].fX;
+ bounds.fTop = bounds.fBottom = dst[0].fY;
+ for (int index = 1; index < 3; ++index) {
+ bounds.growToInclude(dst[index].fX, dst[index].fY);
+ }
+}
+
+static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
+ SkRect& bounds) {
+ SkPoint dst[4];
+ CubicSubDivide(a, startT, endT, dst);
+ bounds.fLeft = bounds.fRight = dst[0].fX;
+ bounds.fTop = bounds.fBottom = dst[0].fY;
+ for (int index = 1; index < 4; ++index) {
+ bounds.growToInclude(dst[index].fX, dst[index].fY);
+ }
+}
+
+static SkPath::Verb QuadReduceOrder(const SkPoint a[4],
+ SkTDArray<SkPoint>& reducePts) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}};
+ Quadratic dst;
+ int order = reduceOrder(aQuad, dst);
+ for (int index = 0; index < order; ++index) {
+ SkPoint* pt = reducePts.append();
+ pt->fX = SkDoubleToScalar(dst[index].x);
+ pt->fY = SkDoubleToScalar(dst[index].y);
+ }
+ return (SkPath::Verb) (order - 1);
+}
+
+static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
+ SkTDArray<SkPoint>& reducePts) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
+ Cubic dst;
+ int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
+ for (int index = 0; index < order; ++index) {
+ SkPoint* pt = reducePts.append();
+ pt->fX = SkDoubleToScalar(dst[index].x);
+ pt->fY = SkDoubleToScalar(dst[index].y);
+ }
+ return (SkPath::Verb) (order - 1);
+}
+
+static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ double x[2];
+ xy_at_t(aLine, startT, x[0], *(double*) 0);
+ xy_at_t(aLine, endT, x[0], *(double*) 0);
+ return startT < endT ? startT : endT;
+}
+
+static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}};
+ return leftMostT(aQuad, startT, endT);
+}
+
+static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
+ return leftMostT(aCubic, startT, endT);
+}
+
+static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
+ NULL,
+ LineLeftMost,
+ QuadLeftMost,
+ CubicLeftMost
+};
+
+static bool IsCoincident(const SkPoint a[2], const SkPoint& above,
+ const SkPoint& below) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}};
+ return implicit_matches_ulps(aLine, bLine, 32);
+}
+
+// Bounds, unlike Rect, does not consider a vertical line to be empty.
+struct Bounds : public SkRect {
+ static bool Intersects(const Bounds& a, const Bounds& b) {
+ return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
+ a.fTop <= b.fBottom && b.fTop <= a.fBottom;
+ }
+
+ bool isEmpty() {
+ return fLeft > fRight || fTop > fBottom
+ || fLeft == fRight && fTop == fBottom
+ || isnan(fLeft) || isnan(fRight)
+ || isnan(fTop) || isnan(fBottom);
+ }
+
+ void setCubicBounds(const SkPoint a[4]) {
+ _Rect dRect;
+ Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
+ dRect.setBounds(cubic);
+ set(dRect.left, dRect.top, dRect.right, dRect.bottom);
+ }
+
+ void setQuadBounds(const SkPoint a[3]) {
+ const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}};
+ _Rect dRect;
+ dRect.setBounds(quad);
+ set(dRect.left, dRect.top, dRect.right, dRect.bottom);
+ }
+};
+
+class Segment;
+
+struct TEntry {
+ double fT;
+ const Segment* fOther;
+ double fOtherT;
+ bool fCoincident;
+};
+
+class Segment {
+public:
+ Segment() {
+#if DEBUG_DUMP
+ fID = ++gSegmentID;
+#endif
+ }
+
+ int addT(double newT, const Segment& other) {
+ // FIXME: in the pathological case where there is a ton of intercepts,
+ // binary search?
+ int insertedAt = -1;
+ TEntry* entry;
+ size_t tCount = fTs.count();
+ double delta;
+ for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
+ if (newT <= fTs[idx2].fT) {
+ insertedAt = idx2;
+ entry = fTs.insert(idx2);
+ goto finish;
+ }
+ }
+ insertedAt = tCount;
+ entry = fTs.append();
+finish:
+ entry->fT = newT;
+ entry->fOther = &other;
+ return insertedAt;
+ }
+
+ bool addCubic(const SkPoint pts[4]) {
+ fPts = pts;
+ fVerb = SkPath::kCubic_Verb;
+ fBounds.setCubicBounds(pts);
+ }
+
+ bool addLine(const SkPoint pts[2]) {
+ fPts = pts;
+ fVerb = SkPath::kLine_Verb;
+ fBounds.set(pts, 2);
+ }
+
+ // add 2 to edge or out of range values to get T extremes
+ void addOtherT(int index, double other, bool coincident) {
+ fTs[index].fOtherT = other;
+ fTs[index].fCoincident = coincident;
+ }
+
+ bool addQuad(const SkPoint pts[3]) {
+ fPts = pts;
+ fVerb = SkPath::kQuad_Verb;
+ fBounds.setQuadBounds(pts);
+ }
+
+ const Bounds& bounds() const {
+ return fBounds;
+ }
+
+ int findByT(double t, const Segment* match) const {
+ // OPTIMIZATION: bsearch if count is honkin huge
+ int count = fTs.count();
+ for (int index = 0; index < count; ++index) {
+ const TEntry& entry = fTs[index];
+ if (t == entry.fT && match == entry.fOther) {
+ return index;
+ }
+ }
+ SkASSERT(0); // should never get here
+ return -1;
+ }
+
+ int findLefty(int tIndex, const SkPoint& base) const {
+ int bestTIndex;
+ SkPoint test;
+ SkScalar bestX = DBL_MAX;
+ int testTIndex = tIndex;
+ while (--testTIndex >= 0) {
+ xyAtT(testTIndex, &test);
+ if (test != base) {
+ continue;
+ }
+ bestX = test.fX;
+ bestTIndex = testTIndex;
+ break;
+ }
+ int count = fTs.count();
+ testTIndex = tIndex;
+ while (++testTIndex < count) {
+ xyAtT(testTIndex, &test);
+ if (test == base) {
+ continue;
+ }
+ return bestX > test.fX ? testTIndex : bestTIndex;
+ }
+ return -1;
+ }
+
+ const Segment* findTop(int& tIndex) const {
+ // iterate through T intersections and return topmost
+ // topmost tangent from y-min to first pt is closer to horizontal
+ int firstT = 0;
+ int lastT = 0;
+ SkScalar topY = fPts[0].fY;
+ int count = fTs.count();
+ int index;
+ for (index = 1; index < count; ++index) {
+ const TEntry& entry = fTs[index];
+ double t = entry.fT;
+ SkScalar yIntercept = (*SegmentYAtT[fVerb])(fPts, t);
+ if (topY > yIntercept) {
+ topY = yIntercept;
+ firstT = lastT = index;
+ } else if (topY == yIntercept) {
+ lastT = index;
+ }
+ }
+ // if a pair of segments go down, choose the higher endpoint
+ if (firstT == lastT && (firstT == 0 || firstT == count - 1)) {
+ tIndex = firstT;
+ return this;
+ }
+ // if the topmost T is not on end, or is three-way or more, find left
+ SkPoint leftBase;
+ xyAtT(firstT, &leftBase);
+ int tLeft = findLefty(firstT, leftBase);
+ SkASSERT(tLeft > 0);
+ const Segment* leftSegment = this;
+ SkScalar left = leftMost(firstT, tLeft);
+ for (index = firstT; index <= lastT; ++index) {
+ const Segment* other = fTs[index].fOther;
+ double otherT = fTs[index].fOtherT;
+ int otherTIndex = other->findByT(otherT, this);
+ // pick companionT closest (but not too close) on either side
+ int otherTLeft = other->findLefty(otherTIndex, leftBase);
+ if (otherTLeft < 0) {
+ continue;
+ }
+ SkScalar otherMost = other->leftMost(otherTIndex, otherTLeft);
+ if (otherMost < left) {
+ leftSegment = other;
+ }
+ }
+ return leftSegment;
+ }
+
+ bool intersected() const {
+ return fTs.count() > 0;
+ }
+
+ bool isHorizontal() const {
+ return fBounds.fTop == fBounds.fBottom;
+ }
+
+ bool isVertical() const {
+ return fBounds.fLeft == fBounds.fRight;
+ }
+
+ SkScalar leftMost(int start, int end) const {
+ return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
+ }
+
+ const SkPoint* pts() const {
+ return fPts;
+ }
+
+ void reset() {
+ fPts = NULL;
+ fVerb = (SkPath::Verb) -1;
+ fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
+ fTs.reset();
+ }
+
+ // OPTIMIZATION: remove this function if it's never called
+ double t(int tIndex) const {
+ return fTs[tIndex].fT;
+ }
+
+ SkPath::Verb verb() const {
+ return fVerb;
+ }
+
+ SkScalar xAtT(double t) const {
+ return (*SegmentXAtT[fVerb])(fPts, t);
+ }
+
+ void xyAtT(double t, SkPoint* pt) const {
+ (*SegmentXYAtT[fVerb])(fPts, t, pt);
+ }
+
+#if DEBUG_DUMP
+ void dump() const {
+ const char className[] = "Segment";
+ const int tab = 4;
+ for (int i = 0; i < fTs.count(); ++i) {
+ SkPoint out;
+ (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
+ SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
+ " otherT=%1.9g coincident=%d\n",
+ tab + sizeof(className), className, fID,
+ kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
+ fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fCoincident);
+ }
+ SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
+ tab + sizeof(className), className, fID,
+ fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
+ }
+#endif
+
+private:
+ const SkPoint* fPts;
+ SkPath::Verb fVerb;
+ Bounds fBounds;
+ SkTDArray<TEntry> fTs;
+#if DEBUG_DUMP
+ int fID;
+#endif
+};
+
+class Contour {
+public:
+ Contour() {
+ reset();
+#if DEBUG_DUMP
+ fID = ++gContourID;
+#endif
+ }
+
+ bool operator<(const Contour& rh) const {
+ return fBounds.fTop == rh.fBounds.fTop
+ ? fBounds.fLeft < rh.fBounds.fLeft
+ : fBounds.fTop < rh.fBounds.fTop;
+ }
+
+ void addCubic(const SkPoint pts[4]) {
+ fSegments.push_back().addCubic(pts);
+ fContainsCurves = true;
+ }
+ void addLine(const SkPoint pts[2]) {
+ fSegments.push_back().addLine(pts);
+ }
+
+ void addQuad(const SkPoint pts[3]) {
+ fSegments.push_back().addQuad(pts);
+ fContainsCurves = true;
+ }
+
+ const Bounds& bounds() const {
+ return fBounds;
+ }
+
+ void complete() {
+ setBounds();
+ fContainsIntercepts = false;
+ }
+
+ void containsIntercepts() {
+ fContainsIntercepts = true;
+ }
+
+ void reset() {
+ fSegments.reset();
+ fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
+ fContainsCurves = fContainsIntercepts = false;
+ }
+
+ Segment& topSegment() {
+ return fSegments[fTopSegment];
+ }
+
+#if DEBUG_DUMP
+ void dump() {
+ int i;
+ const char className[] = "Contour";
+ const int tab = 4;
+ SkDebugf("%s %p (contour=%d)\n", className, this, fID);
+ for (i = 0; i < fSegments.count(); ++i) {
+ SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
+ className, i);
+ fSegments[i].dump();
+ }
+ SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
+ tab + sizeof(className), className,
+ fBounds.fLeft, fBounds.fTop,
+ fBounds.fRight, fBounds.fBottom);
+ SkDebugf("%*s.fTopSegment=%d\n", tab + sizeof(className), className,
+ fTopSegment);
+ SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
+ className, fContainsIntercepts);
+ SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
+ className, fContainsCurves);
+ }
+#endif
+
+protected:
+ void setBounds() {
+ int count = fSegments.count();
+ if (count == 0) {
+ SkDebugf("%s empty contour\n", __FUNCTION__);
+ SkASSERT(0);
+ // FIXME: delete empty contour?
+ return;
+ }
+ fTopSegment = 0;
+ fBounds = fSegments.front().bounds();
+ SkScalar top = fBounds.fTop;
+ for (int index = 1; index < count; ++index) {
+ fBounds.growToInclude(fSegments[index].bounds());
+ if (top > fBounds.fTop) {
+ fTopSegment = index;
+ top = fBounds.fTop;
+ }
+ }
+ }
+
+public:
+ SkTArray<Segment> fSegments; // not worth accessor functions?
+
+private:
+ Bounds fBounds;
+ int fTopSegment;
+ bool fContainsIntercepts;
+ bool fContainsCurves;
+#if DEBUG_DUMP
+ int fID;
+#endif
+};
+
+class EdgeBuilder {
+public:
+
+EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
+ : fPath(path)
+ , fCurrentContour(NULL)
+ , fContours(contours)
+{
+#if DEBUG_DUMP
+ gContourID = 0;
+ gSegmentID = 0;
+#endif
+ walk();
+}
+
+protected:
+
+void complete() {
+ if (fCurrentContour && fCurrentContour->fSegments.count()) {
+ fCurrentContour->complete();
+ fCurrentContour = NULL;
+ }
+}
+
+void startContour() {
+ if (!fCurrentContour) {
+ fCurrentContour = fContours.push_back_n(1);
+ }
+}
+
+void walk() {
+ // FIXME:remove once we can access path pts directly
+ SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed
+ SkPoint pts[4];
+ SkPath::Verb verb;
+ do {
+ verb = iter.next(pts);
+ *fPathVerbs.append() = verb;
+ if (verb == SkPath::kMove_Verb) {
+ *fPathPts.append() = pts[0];
+ } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
+ fPathPts.append(verb, &pts[1]);
+ }
+ } while (verb != SkPath::kDone_Verb);
+ // FIXME: end of section to remove once path pts are accessed directly
+
+ SkPath::Verb reducedVerb;
+ uint8_t* verbPtr = fPathVerbs.begin();
+ const SkPoint* pointsPtr = fPathPts.begin();
+ while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
+ switch (verb) {
+ case SkPath::kMove_Verb:
+ complete();
+ startContour();
+ pointsPtr += 1;
+ continue;
+ case SkPath::kLine_Verb:
+ // skip degenerate points
+ if (pointsPtr[-1].fX != pointsPtr[0].fX
+ || pointsPtr[-1].fY != pointsPtr[0].fY) {
+ fCurrentContour->addLine(&pointsPtr[-1]);
+ }
+ break;
+ case SkPath::kQuad_Verb:
+ reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
+ if (reducedVerb == 0) {
+ break; // skip degenerate points
+ }
+ if (reducedVerb == 1) {
+ fCurrentContour->addLine(fReducePts.end() - 2);
+ break;
+ }
+ fCurrentContour->addQuad(&pointsPtr[-1]);
+ break;
+ case SkPath::kCubic_Verb:
+ reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
+ if (reducedVerb == 0) {
+ break; // skip degenerate points
+ }
+ if (reducedVerb == 1) {
+ fCurrentContour->addLine(fReducePts.end() - 2);
+ break;
+ }
+ if (reducedVerb == 2) {
+ fCurrentContour->addQuad(fReducePts.end() - 3);
+ break;
+ }
+ fCurrentContour->addCubic(&pointsPtr[-1]);
+ break;
+ case SkPath::kClose_Verb:
+ SkASSERT(fCurrentContour);
+ complete();
+ continue;
+ default:
+ SkDEBUGFAIL("bad verb");
+ return;
+ }
+ pointsPtr += verb;
+ SkASSERT(fCurrentContour);
+ }
+ complete();
+ if (fCurrentContour && !fCurrentContour->fSegments.count()) {
+ fContours.pop_back();
+ }
+}
+
+private:
+ const SkPath& fPath;
+ SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
+ SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
+ Contour* fCurrentContour;
+ SkTArray<Contour>& fContours;
+ SkTDArray<SkPoint> fReducePts; // segments created on the fly
+};
+
+class Work {
+public:
+ enum SegmentType {
+ kHorizontalLine_Segment = -1,
+ kVerticalLine_Segment = 0,
+ kLine_Segment = SkPath::kLine_Verb,
+ kQuad_Segment = SkPath::kQuad_Verb,
+ kCubic_Segment = SkPath::kCubic_Verb,
+ };
+
+ void addOtherT(int index, double other, bool coincident) {
+ fContour->fSegments[fIndex].addOtherT(index, other, coincident);
+ }
+
+ // Avoid collapsing t values that are close to the same since
+ // we walk ts to describe consecutive intersections. Since a pair of ts can
+ // be nearly equal, any problems caused by this should be taken care
+ // of later.
+ // On the edge or out of range values are negative; add 2 to get end
+ int addT(double newT, const Work& other) {
+ fContour->containsIntercepts();
+ return fContour->fSegments[fIndex].addT(newT,
+ other.fContour->fSegments[other.fIndex]);
+ }
+
+ bool advance() {
+ return ++fIndex < fLast;
+ }
+
+ SkScalar bottom() const {
+ return bounds().fBottom;
+ }
+
+ const Bounds& bounds() const {
+ return fContour->fSegments[fIndex].bounds();
+ }
+
+ const SkPoint* cubic() const {
+ return fCubic;
+ }
+
+ void init(Contour* contour) {
+ fContour = contour;
+ fIndex = 0;
+ fLast = contour->fSegments.count();
+ }
+
+ SkScalar left() const {
+ return bounds().fLeft;
+ }
+
+ void promoteToCubic() {
+ fCubic[0] = pts()[0];
+ fCubic[2] = pts()[1];
+ fCubic[3] = pts()[2];
+ fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
+ fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
+ fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
+ fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
+ }
+
+ const SkPoint* pts() const {
+ return fContour->fSegments[fIndex].pts();
+ }
+
+ SkScalar right() const {
+ return bounds().fRight;
+ }
+
+ ptrdiff_t segmentIndex() const {
+ return fIndex;
+ }
+
+ SegmentType segmentType() const {
+ const Segment& segment = fContour->fSegments[fIndex];
+ SegmentType type = (SegmentType) segment.verb();
+ if (type != kLine_Segment) {
+ return type;
+ }
+ if (segment.isHorizontal()) {
+ return kHorizontalLine_Segment;
+ }
+ if (segment.isVertical()) {
+ return kVerticalLine_Segment;
+ }
+ return kLine_Segment;
+ }
+
+ bool startAfter(const Work& after) {
+ fIndex = after.fIndex;
+ return advance();
+ }
+
+ SkScalar top() const {
+ return bounds().fTop;
+ }
+
+ SkPath::Verb verb() const {
+ return fContour->fSegments[fIndex].verb();
+ }
+
+ SkScalar x() const {
+ return bounds().fLeft;
+ }
+
+ bool xFlipped() const {
+ return x() != pts()[0].fX;
+ }
+
+ SkScalar y() const {
+ return bounds().fTop;
+ }
+
+ bool yFlipped() const {
+ return y() != pts()[0].fX;
+ }
+
+protected:
+ Contour* fContour;
+ SkPoint fCubic[4];
+ int fIndex;
+ int fLast;
+};
+
+static void debugShowLineIntersection(int pts, const Work& wt,
+ const Work& wn, const double wtTs[2], const double wnTs[2]) {
+#if DEBUG_ADD_INTERSECTING_TS
+ if (!pts) {
+ return;
+ }
+ SkPoint wtOutPt, wnOutPt;
+ LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
+ LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
+ SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
+ __FUNCTION__,
+ wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
+ wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
+ if (pts == 2) {
+ SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
+ }
+ SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
+ __FUNCTION__,
+ wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
+ wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
+ if (pts == 2) {
+ SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]);
+ }
+#endif
+}
+
+static bool addIntersectingTs(Contour* test, Contour* next) {
+ if (test != next) {
+ if (test->bounds().fBottom < next->bounds().fTop) {
+ return false;
+ }
+ if (!Bounds::Intersects(test->bounds(), next->bounds())) {
+ return true;
+ }
+ }
+ Work wt, wn;
+ wt.init(test);
+ wn.init(next);
+ do {
+ if (test == next && !wn.startAfter(wt)) {
+ continue;
+ }
+ do {
+ if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
+ continue;
+ }
+ int pts;
+ Intersections ts;
+ bool swap = false;
+ switch (wt.segmentType()) {
+ case Work::kHorizontalLine_Segment:
+ swap = true;
+ switch (wn.segmentType()) {
+ case Work::kHorizontalLine_Segment:
+ case Work::kVerticalLine_Segment:
+ case Work::kLine_Segment: {
+ pts = HLineIntersect(wn.pts(), wt.left(),
+ wt.right(), wt.y(), wt.xFlipped(), ts);
+ break;
+ }
+ case Work::kQuad_Segment: {
+ pts = HQuadIntersect(wn.pts(), wt.left(),
+ wt.right(), wt.y(), wt.xFlipped(), ts);
+ break;
+ }
+ case Work::kCubic_Segment: {
+ pts = HCubicIntersect(wn.pts(), wt.left(),
+ wt.right(), wt.y(), wt.xFlipped(), ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case Work::kVerticalLine_Segment:
+ swap = true;
+ switch (wn.segmentType()) {
+ case Work::kHorizontalLine_Segment:
+ case Work::kVerticalLine_Segment:
+ case Work::kLine_Segment: {
+ pts = VLineIntersect(wn.pts(), wt.top(),
+ wt.bottom(), wt.x(), wt.yFlipped(), ts);
+ break;
+ }
+ case Work::kQuad_Segment: {
+ pts = VQuadIntersect(wn.pts(), wt.top(),
+ wt.bottom(), wt.x(), wt.yFlipped(), ts);
+ break;
+ }
+ case Work::kCubic_Segment: {
+ pts = VCubicIntersect(wn.pts(), wt.top(),
+ wt.bottom(), wt.x(), wt.yFlipped(), ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case Work::kLine_Segment:
+ switch (wn.segmentType()) {
+ case Work::kHorizontalLine_Segment:
+ pts = HLineIntersect(wt.pts(), wn.left(),
+ wn.right(), wn.y(), wn.xFlipped(), ts);
+ break;
+ case Work::kVerticalLine_Segment:
+ pts = VLineIntersect(wt.pts(), wn.top(),
+ wn.bottom(), wn.x(), wn.yFlipped(), ts);
+ break;
+ case Work::kLine_Segment: {
+ pts = LineIntersect(wt.pts(), wn.pts(), ts);
+ debugShowLineIntersection(pts, wt, wn,
+ ts.fT[1], ts.fT[0]);
+ break;
+ }
+ case Work::kQuad_Segment: {
+ swap = true;
+ pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
+ break;
+ }
+ case Work::kCubic_Segment: {
+ swap = true;
+ pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case Work::kQuad_Segment:
+ switch (wn.segmentType()) {
+ case Work::kHorizontalLine_Segment:
+ pts = HQuadIntersect(wt.pts(), wn.left(),
+ wn.right(), wn.y(), wn.xFlipped(), ts);
+ break;
+ case Work::kVerticalLine_Segment:
+ pts = VQuadIntersect(wt.pts(), wn.top(),
+ wn.bottom(), wn.x(), wn.yFlipped(), ts);
+ break;
+ case Work::kLine_Segment: {
+ pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
+ break;
+ }
+ case Work::kQuad_Segment: {
+ pts = QuadIntersect(wt.pts(), wn.pts(), ts);
+ break;
+ }
+ case Work::kCubic_Segment: {
+ wt.promoteToCubic();
+ pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case Work::kCubic_Segment:
+ switch (wn.segmentType()) {
+ case Work::kHorizontalLine_Segment:
+ pts = HCubicIntersect(wt.pts(), wn.left(),
+ wn.right(), wn.y(), wn.xFlipped(), ts);
+ break;
+ case Work::kVerticalLine_Segment:
+ pts = VCubicIntersect(wt.pts(), wn.top(),
+ wn.bottom(), wn.x(), wn.yFlipped(), ts);
+ break;
+ case Work::kLine_Segment: {
+ pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
+ break;
+ }
+ case Work::kQuad_Segment: {
+ wn.promoteToCubic();
+ pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
+ break;
+ }
+ case Work::kCubic_Segment: {
+ pts = CubicIntersect(wt.pts(), wn.pts(), ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ default:
+ SkASSERT(0);
+ }
+ // in addition to recording T values, record matching segment
+ bool coincident = pts == 2 && wn.segmentType() <= Work::kLine_Segment
+ && wt.segmentType() <= Work::kLine_Segment;
+ for (int pt = 0; pt < pts; ++pt) {
+ SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
+ SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
+ int testTAt = wt.addT(ts.fT[swap][pt], wn);
+ int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
+ wt.addOtherT(testTAt, ts.fT[!swap][pt], coincident);
+ wn.addOtherT(nextTAt, ts.fT[swap][pt], coincident);
+ }
+ } while (wn.advance());
+ } while (wt.advance());
+ return true;
+}
+
+// Each segment may have an inside or an outside. Segments contained within
+// winding may have insides on either side, and form a contour that should be
+// ignored. Segments that are coincident with opposing direction segments may
+// have outsides on either side, and should also disappear.
+// 'Normal' segments will have one inside and one outside. Subsequent connections
+// when winding should follow the intersection direction. If more than one edge
+// is an option, choose first edge that continues the inside.
+
+static void bridge(SkTDArray<Contour*>& contourList) {
+ // Start at the top. Above the top is outside, below is inside.
+ Contour* topContour = contourList[0];
+ Segment& topStart = topContour->topSegment();
+ int index;
+ const Segment* topSegment = topStart.findTop(index);
+ start here ;
+ // find span
+ // handle coincident
+ // mark neighbors winding coverage
+ // output span
+ // mark span as processed
+
+}
+
+static void makeContourList(SkTArray<Contour>& contours, Contour& sentinel,
+ SkTDArray<Contour*>& list) {
+ size_t count = contours.count();
+ if (count == 0) {
+ return;
+ }
+ for (size_t index = 0; index < count; ++index) {
+ *list.append() = &contours[index];
+ }
+ *list.append() = &sentinel;
+ QSort<Contour>(list.begin(), list.end() - 1);
+}
+
+void simplifyx(const SkPath& path, bool asFill, SkPath& simple) {
+ // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
+ int windingMask = (path.getFillType() & 1) ? 1 : -1;
+ simple.reset();
+ simple.setFillType(SkPath::kEvenOdd_FillType);
+
+ // turn path into list of segments
+ SkTArray<Contour> contours;
+ // FIXME: add self-intersecting cubics' T values to segment
+ EdgeBuilder builder(path, contours);
+ SkTDArray<Contour*> contourList;
+ Contour sentinel;
+ sentinel.reset();
+ makeContourList(contours, sentinel, contourList);
+ Contour** currentPtr = contourList.begin();
+ if (!currentPtr) {
+ return;
+ }
+ // find all intersections between segments
+ do {
+ Contour** nextPtr = currentPtr;
+ Contour* current = *currentPtr++;
+ Contour* next;
+ do {
+ next = *nextPtr++;
+ } while (next != &sentinel && addIntersectingTs(current, next));
+ } while (*currentPtr != &sentinel);
+ // construct closed contours
+ bridge(contourList);
+}
+
diff --git a/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp b/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp
new file mode 100644
index 0000000..fff07da
--- /dev/null
+++ b/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp
@@ -0,0 +1,132 @@
+#include "CurveIntersection.h"
+#include "Intersections.h"
+#include "LineIntersection.h"
+#include "SkPath.h"
+#include "SkRect.h"
+#include "SkTArray.h"
+#include "SkTDArray.h"
+#include "ShapeOps.h"
+#include "TSearch.h"
+
+namespace SimplifyAddIntersectingTsTest {
+
+#include "Simplify.cpp"
+
+} // end of SimplifyAddIntersectingTsTest namespace
+
+#include "Intersection_Tests.h"
+
+static const SkPoint lines[][2] = {
+ {{ 1, 1}, { 1, 1}}, // degenerate
+ {{ 1, 1}, { 4, 1}}, // horizontal
+ {{ 4, 1}, { 9, 1}},
+ {{ 2, 1}, { 3, 1}},
+ {{ 2, 1}, { 6, 1}},
+ {{ 5, 1}, { 9, 1}},
+ {{ 1, 1}, { 1, 4}}, // vertical
+ {{ 1, 2}, { 1, 3}},
+ {{ 1, 2}, { 1, 6}},
+ {{ 1, 5}, { 1, 9}},
+ {{ 1, 1}, { 3, 3}}, // diagonal
+ {{ 2, 2}, { 4, 4}},
+ {{ 2, 4}, { 4, 2}},
+};
+
+static const size_t lineCount = sizeof(lines) / sizeof(lines[0]);
+
+static const SkPoint quads[][3] = {
+ {{ 1, 1}, { 1, 1}, { 1, 1}}, // degenerate
+ {{ 1, 1}, { 4, 1}, { 5, 1}}, // line
+ {{ 1, 1}, { 4, 1}, { 4, 4}}, // curve
+};
+
+static const size_t quadCount = sizeof(quads) / sizeof(quads[0]);
+
+static const SkPoint cubics[][4] = {
+ {{ 1, 1}, { 1, 1}, { 1, 1}, { 1, 1}}, // degenerate
+ {{ 1, 1}, { 4, 1}, { 5, 1}, { 6, 1}}, // line
+ {{ 1, 1}, { 3, 1}, { 4, 2}, { 4, 4}}, // curve
+};
+
+static const size_t cubicCount = sizeof(cubics) / sizeof(cubics[0]);
+static const size_t testCount = lineCount + quadCount + cubicCount;
+
+static SkPath::Verb setPath(int outer, SkPath& path, const SkPoint*& pts1) {
+ SkPath::Verb c1Type;
+ if (outer < lineCount) {
+ path.moveTo(lines[outer][0].fX, lines[outer][0].fY);
+ path.lineTo(lines[outer][1].fX, lines[outer][1].fY);
+ c1Type = SkPath::kLine_Verb;
+ pts1 = lines[outer];
+ } else {
+ outer -= lineCount;
+ if (outer < quadCount) {
+ path.moveTo(quads[outer][0].fX, quads[outer][0].fY);
+ path.quadTo(quads[outer][1].fX, quads[outer][1].fY,
+ quads[outer][2].fX, quads[outer][2].fY);
+ c1Type = SkPath::kQuad_Verb;
+ pts1 = quads[outer];
+ } else {
+ outer -= quadCount;
+ path.moveTo(cubics[outer][0].fX, cubics[outer][0].fY);
+ path.cubicTo(cubics[outer][1].fX, cubics[outer][1].fY,
+ cubics[outer][2].fX, cubics[outer][2].fY,
+ cubics[outer][3].fX, cubics[outer][3].fY);
+ c1Type = SkPath::kCubic_Verb;
+ pts1 = cubics[outer];
+ }
+ }
+ return c1Type;
+}
+
+static void testPath(const SkPath& path, const SkPoint* pts1, SkPath::Verb c1Type,
+ const SkPoint* pts2, SkPath::Verb c2Type) {
+ SkTArray<SimplifyAddIntersectingTsTest::Contour> contour;
+ SimplifyAddIntersectingTsTest::EdgeBuilder builder(path, contour);
+ if (contour.count() < 2) {
+ return;
+ }
+ SimplifyAddIntersectingTsTest::Contour& c1 = contour[0];
+ SimplifyAddIntersectingTsTest::Contour& c2 = contour[1];
+ addIntersectingTs(&c1, &c2);
+ bool c1Intersected = c1.fSegments[0].intersected();
+ bool c2Intersected = c2.fSegments[0].intersected();
+#if DEBUG_DUMP
+ SkDebugf("%s %s (%1.9g,%1.9g %1.9g,%1.9g) %s %s (%1.9g,%1.9g %1.9g,%1.9g)\n",
+ __FUNCTION__, SimplifyAddIntersectingTsTest::kLVerbStr[c1Type],
+ pts1[0].fX, pts1[0].fY,
+ pts1[c1Type].fX, pts1[c1Type].fY,
+ c1Intersected ? "intersects" : "does not intersect",
+ SimplifyAddIntersectingTsTest::kLVerbStr[c2Type],
+ pts2[0].fX, pts2[0].fY,
+ pts2[c2Type].fX, pts2[c2Type].fY);
+ if (c1Intersected) {
+ c1.dump();
+ c2.dump();
+ }
+#endif
+}
+
+static const int firstO = 6;
+static const int firstI = 1;
+
+void SimplifyAddIntersectingTs_Test() {
+ const SkPoint* pts1, * pts2;
+ if (firstO > 0 || firstI > 0) {
+ SkPath path;
+ SkPath::Verb c1Type = setPath(firstO, path, pts1);
+ SkPath path2(path);
+ SkPath::Verb c2Type = setPath(firstI, path2, pts2);
+ testPath(path2, pts1, c1Type, pts2, c2Type);
+ }
+ for (int o = 0; o < testCount; ++o) {
+ SkPath path;
+ SkPath::Verb c1Type = setPath(o, path, pts1);
+ for (int i = 0; i < testCount; ++i) {
+ SkPath path2(path);
+ SkPath::Verb c2Type = setPath(i, path2, pts2);
+ testPath(path2, pts1, c1Type, pts2, c2Type);
+ }
+ }
+}
+
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 4f12c91..4df4aeb 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -1,116 +1,133 @@
<html>
<head>
<div style="height:0">
-<div id="test_1div">
-path.moveTo(213.673737, 413.292938);
-path.lineTo(225.200134, 343.616821);
-path.lineTo(236.726532, 273.940704);
-path.lineTo(219.386414, 231.373322);
-path.lineTo(213.673737, 413.292938);
-path.close();
-path.moveTo(43.485352, 308.984497);
-path.lineTo(122.610657, 305.950134);
-path.lineTo(201.735962, 302.915802);
-path.lineTo(280.861267, 299.881470);
-path.lineTo(43.485352, 308.984497);
-path.close();
+
+<div id="testSimplifyQuadratic1">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.quadTo(0, 0, 0, 1);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+}
</div>
-<div id="test_2div">
-path.moveTo(-177.878387, 265.368988);
-path.lineTo(-254.415771, 303.709961);
-path.lineTo(-317.465363, 271.325562);
-path.lineTo(-374.520386, 207.507660);
-path.lineTo(-177.878387, 265.368988);
-path.close();
-path.moveTo(-63.582489, -3.679123);
-path.lineTo(-134.496841, 26.434566);
-path.lineTo(-205.411209, 56.548256);
-path.lineTo(-276.325562, 86.661942);
-path.lineTo(-63.582489, -3.679123);
-path.close();
-path.moveTo(-57.078423, 162.633453);
-path.lineTo(-95.963928, 106.261139);
-path.lineTo(-134.849457, 49.888824);
-path.lineTo(-173.734955, -6.483480);
-path.lineTo(-57.078423, 162.633453);
-path.close();
+
+<div id="testSimplifyQuadratic2">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(20, 0, 20, 20);
+ path.close();
+ path.moveTo(20, 0);
+ path.quadTo(0, 0, 0, 20);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+}
</div>
-<div id="test_3div">
-path.moveTo(98.666489, -94.295059);
-path.lineTo(156.584320, -61.939133);
-path.lineTo(174.672974, -12.343765);
-path.lineTo(158.622345, 52.028267);
-path.lineTo(98.666489, -94.295059);
-path.close();
-path.moveTo(-133.225616, -48.622055);
-path.lineTo(-73.855499, -10.375397);
-path.lineTo(-14.485367, 27.871277);
-path.lineTo(44.884750, 66.117935);
-path.lineTo(-133.225616, -48.622055);
-path.close();
-path.moveTo( 9.030045, -163.413132);
-path.lineTo(-19.605331, -89.588760);
-path.lineTo(-48.240707, -15.764404);
-path.lineTo(-76.876053, 58.059944);
-path.lineTo( 9.030045, -163.413132);
-path.close();
+
+<div id="testSimplifyQuadratic3">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(20, 0, 20, 20);
+ path.close();
+ path.moveTo(0, 20);
+ path.quadTo(0, 0, 20, 0);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+}
</div>
-<div id="test_4div">
-path.moveTo(340.41568, -170.97171);
-path.lineTo(418.846893, -142.428329);
-path.lineTo(497.278107, -113.884933);
-path.lineTo(449.18222, -45.6723022);
-path.lineTo(340.41568, -170.97171);
-path.close();
-path.moveTo(326.610535, 34.0393639);
-path.lineTo(371.334595, -14.9620667);
-path.lineTo(416.058624, -63.9634857);
-path.lineTo(460.782654, -112.96492);
-path.lineTo(326.610535, 34.0393639);
-path.close();
+
+<div id="testSimplifyQuadratic4">
+ SkPath path, out;
+ path.moveTo(0, 20);
+ path.quadTo(20, 0, 40, 20);
+ path.close();
+ path.moveTo(40, 10);
+ path.quadTo(20, 30, 0, 10);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
-<div id="test_5div">
-original:
-path.moveTo(0, 0);
-path.quadTo(20, 0, 20, 20);
-path.lineTo(0, 0);
-path.close();
-path.moveTo(0, 20);
-path.quadTo(0, 0, 20, 0);
-path.lineTo(0, 20);
-path.close();
-simplified:
-path.moveTo(0, 0);
-path.lineTo(5, 5);
-path.quadTo(0, 10, 0, 20);
-path.lineTo(20, 20);
-path.quadTo(20, 10, 15, 5);
-path.lineTo(20, 0);
-path.quadTo(14.1421356, 0, 10, 1.71572876);
-path.quadTo(5.85786438, 0, 0, 0);
-path.close();
+
+<div id="testSimplifyQuadratic5">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(0, 0);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(0, 0, 0, 1);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
-<div id="test_6div">
-original:
-path.moveTo(0, 20);
-path.quadTo(20, 0, 40, 20);
-path.lineTo(0, 20);
-path.close();
-path.moveTo(40, 10);
-path.quadTo(20, 30, 0, 10);
-path.lineTo(40, 10);
-path.close();
-simplified:
-path.moveTo(0, 10);
-path.quadTo(2.92893219, 12.9289322, 5.85786438, 15);
-path.quadTo(2.92893219, 17.0710678, 0, 20);
-path.lineTo(40, 20);
-path.quadTo(37.0710678, 17.0710678, 34.1421356, 15);
-path.quadTo(37.0710678, 12.9289322, 40, 10);
-path.lineTo(0, 10);
-path.close();
+
+<div id="testSimplifyQuadratic6">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(1, 0);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
-<div id="test_7div">
+
+<div id="testSimplifyQuadratic7">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 2);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
+</div>
+
+<div id="testSimplifyQuadratic8">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(0, 0);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 2);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
+</div>
+
+<div id="testSimplifyQuadratic9">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(1, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 2, 2);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
+</div>
+
+<div id="testSimplifyQuadratic10">
+ SkPath path, out;
path.moveTo(0, 0);
path.quadTo(0, 0, 0, 0);
path.lineTo(0, 0);
@@ -118,67 +135,44 @@
path.moveTo(0, 0);
path.lineTo(0, 1);
path.quadTo(1, 1, 1, 2);
- path.lineTo(0, 0);
path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
-<div id="test_8div">
-original:
-path.moveTo(0, 0);
-path.lineTo(3, 1);
-path.lineTo(0, 0);
-path.close();
-path.moveTo(1, 0);
-path.lineTo(0, 1);
-path.quadTo(2, 1, 3, 3);
-path.lineTo(1, 0);
-path.close();
-simplified:
-path.moveTo(1, 0);
-path.lineTo(0, 1);
-path.quadTo(1.42857146, 1, 2.34693885, 2.02040815);
-path.lineTo(1.28571427, 0.428571433);
-path.lineTo(1, 0);
-path.close();
-path.moveTo(2.34693885, 2.02040815);
-path.quadTo(2.71428561, 2.42857146, 3, 3);
-path.lineTo(2.34693885, 2.02040815);
-path.close();
-</div>
-
-<div id="test_9div">
+<div id="testSimplifyQuadratic11">
+ SkPath path, out;
path.moveTo(0, 0);
path.quadTo(0, 0, 0, 0);
path.lineTo(0, 2);
- path.lineTo(0, 0);
path.close();
path.moveTo(0, 0);
path.lineTo(2, 1);
path.quadTo(2, 2, 3, 3);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
+</div>
+
+<div id="testSimplifyQuadratic12">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.lineTo(0, 2);
path.lineTo(0, 0);
path.close();
+ path.moveTo(3, 0);
+ path.quadTo(1, 1, 0, 2);
+ path.lineTo(3, 0);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
-<div id="test_10div">
-original:
-path.moveTo(0, 0);
-path.lineTo(0, 2);
-path.lineTo(0, 0);
-path.close();
-path.moveTo(3, 0);
-path.quadTo(1, 1, 0, 2);
-path.lineTo(3, 0);
-path.close();
-simplified:
-path.moveTo(0, 0);
-path.lineTo(0, 2);
-path.quadTo(1, 1, 3, 0);
-path.lineTo(0, 0);
-path.close();
-</div>
-
-<div id="test_11div">
-original:
+<div id="testSimplifyQuadratic13">
+ SkPath path, out;
path.moveTo(0, 0);
path.quadTo(0, 0, 1, 0);
path.lineTo(1, 1);
@@ -188,56 +182,69 @@
path.quadTo(3, 0, 1, 1);
path.lineTo(0, 0);
path.close();
-simplified:
-path.moveTo(0, 0);
-path.lineTo(1, 1);
-path.lineTo(1, 0);
-path.lineTo(0, 0);
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
-<div id="test_12div">
+<div id="testSimplifyQuadratic14">
+ SkPath path, out;
path.moveTo(0, 0);
path.quadTo(0, 0, 0, 0);
path.lineTo(1, 1);
- path.lineTo(0, 0);
path.close();
path.moveTo(0, 0);
path.lineTo(0, 0);
path.quadTo(0, 1, 2, 1);
- path.lineTo(0, 0);
path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
-<div id="test_13div">
-original:
-path.moveTo(0, 0);
-path.quadTo(0, 0, 1, 3);
-path.lineTo(3, 3);
-path.lineTo(0, 0);
-path.close();
-path.moveTo(0, 1);
-path.lineTo(1, 1);
-path.quadTo(0, 3, 3, 3);
-path.lineTo(0, 1);
-path.close();
-simplified:
-path.moveTo(0, 0);
-path.lineTo(0.333333343, 1);
-path.lineTo(0, 1);
-path.lineTo(0.428571433, 1.28571427);
-path.lineTo(0.333333343, 1);
-path.lineTo(1, 1);
-path.lineTo(0, 0);
-path.close();
-path.moveTo(1, 1);
-path.quadTo(0.857142866, 1.28571427, 0.795918345, 1.53061223);
-path.lineTo(0.428571433, 1.28571427);
-path.lineTo(1, 3);
-path.lineTo(3, 3);
-path.lineTo(0.795918345, 1.53061223);
-path.quadTo(0.428571433, 3, 3, 3);
-path.lineTo(1, 1);
-path.close();
+<div id="testSimplifyQuadratic15">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 1, 3);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(0, 1);
+ path.lineTo(1, 1);
+ path.quadTo(0, 3, 3, 3);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
+</div>
+
+<div id="testSimplifyQuadratic16">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
+</div>
+
+<div id="testSimplifyQuadratic17">
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(0, 1);
+ path.lineTo(0, 1);
+ path.quadTo(2, 1, 3, 3);
+ path.close();
+ testSimplify(path, true, out, bitmap);
+ drawAsciiPaths(path, out, true);
+}
</div>
</div>
@@ -245,19 +252,23 @@
<script type="text/javascript">
var testDivs = [
- test_13div,
- test_12div,
- test_11div,
- test_10div,
- test_9div,
- test_8div,
- test_7div,
- test_6div,
- test_5div,
- test_4div,
- test_3div,
- test_2div,
- test_1div,
+ testSimplifyQuadratic17,
+ testSimplifyQuadratic16,
+ testSimplifyQuadratic15,
+ testSimplifyQuadratic14,
+ testSimplifyQuadratic13,
+ testSimplifyQuadratic12,
+ testSimplifyQuadratic11,
+ testSimplifyQuadratic10,
+ testSimplifyQuadratic9,
+ testSimplifyQuadratic8,
+ testSimplifyQuadratic7,
+ testSimplifyQuadratic6,
+ testSimplifyQuadratic5,
+ testSimplifyQuadratic4,
+ testSimplifyQuadratic3,
+ testSimplifyQuadratic2,
+ testSimplifyQuadratic1,
];
var scale, columns, rows, xStart, yStart;
@@ -291,8 +302,18 @@
if (pts.length > 0)
verbs.push(pts);
}
- if (verbs.length > 0)
+ if (verbs.length > 0) {
+ var lastIndex = verbs.length - 1;
+ var lastVerb = verbs[lastIndex];
+ var lastLen = lastVerb.length;
+ if (verbs[0][0] != lastVerb[lastLen - 2] && verbs[0][1] != lastVerb[lastLen - 1]) {
+ var lastPts = [];
+ lastPts.push(verbs[0][0]);
+ lastPts.push(verbs[0][1]);
+ verbs.push(lastPts);
+ }
contours.push(verbs);
+ }
}
if (contours.length > 0)
tests.push(contours);
@@ -469,23 +490,24 @@
case 'n':
if (++testIndex >= tests.length)
testIndex = 0;
- // insetScale = scale;
+ mouseX = Infinity;
+ drawTop();
+ break;
+ case 'P':
+ case 'p':
+ if (--testIndex < 0)
+ testIndex = tests.length - 1;
mouseX = Infinity;
drawTop();
break;
case 'T':
case 't':
- // drawTs(testIndex);
break;
case '-':
- // if (--insetScale < 1)
- // insetScale = 1;
- // else
redraw();
break;
case '=':
case '+':
- // ++insetScale;
redraw();
break;
}