shape ops work in progress
add quartic solution for intersecting quadratics
git-svn-id: http://skia.googlecode.com/svn/trunk@5541 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index 57cebf7..464e1a8 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -7,10 +7,13 @@
#ifndef Intersections_DEFINE
#define Intersections_DEFINE
+#include <algorithm> // for std::min
+
class Intersections {
public:
Intersections()
: fUsed(0)
+ , fUsed2(0)
, fCoincidentUsed(0)
, fSwap(0)
{
@@ -26,27 +29,83 @@
return;
}
}
+ assert(fUsed < 9);
fT[fSwap][fUsed] = one;
fT[fSwap ^ 1][fUsed] = two;
++fUsed;
}
// start if index == 0 : end if index == 1
- void addCoincident(double one, double two, bool cancel) {
+ void addCoincident(double one, double two) {
for (int index = 0; index < fCoincidentUsed; ++index) {
if (approximately_equal(fCoincidentT[fSwap][index], one)
&& approximately_equal(fCoincidentT[fSwap ^ 1][index], two)) {
- if (cancel) {
- --fCoincidentUsed;
- }
return;
}
}
+ assert(fCoincidentUsed < 9);
fCoincidentT[fSwap][fCoincidentUsed] = one;
fCoincidentT[fSwap ^ 1][fCoincidentUsed] = two;
++fCoincidentUsed;
}
+ void addCoincident(double s1, double e1, double s2, double e2) {
+ assert((fCoincidentUsed & 1) != 1);
+ for (int index = 0; index < fCoincidentUsed; index += 2) {
+ double cs1 = fCoincidentT[fSwap][index];
+ double ce1 = fCoincidentT[fSwap][index + 1];
+ bool s1in = approximately_between(cs1, s1, ce1);
+ bool e1in = approximately_between(cs1, e1, ce1);
+ double cs2 = fCoincidentT[fSwap ^ 1][index];
+ double ce2 = fCoincidentT[fSwap ^ 1][index + 1];
+ bool s2in = approximately_between(cs2, s2, ce2);
+ bool e2in = approximately_between(cs2, e2, ce2);
+ if ((s1in | e1in) & (s2in | e2in)) {
+ double lesser1 = std::min(cs1, ce1);
+ index += cs1 > ce1;
+ if (s1in < lesser1) {
+ fCoincidentT[fSwap][index] = s1in;
+ } else if (e1in < lesser1) {
+ fCoincidentT[fSwap][index] = e1in;
+ }
+ index ^= 1;
+ double greater1 = fCoincidentT[fSwap][index];
+ if (s1in > greater1) {
+ fCoincidentT[fSwap][index] = s1in;
+ } else if (e1in > greater1) {
+ fCoincidentT[fSwap][index] = e1in;
+ }
+ index &= ~1;
+ double lesser2 = std::min(cs2, ce2);
+ index += cs2 > ce2;
+ if (s2in < lesser2) {
+ fCoincidentT[fSwap ^ 1][index] = s2in;
+ } else if (e2in < lesser2) {
+ fCoincidentT[fSwap ^ 1][index] = e2in;
+ }
+ index ^= 1;
+ double greater2 = fCoincidentT[fSwap ^ 1][index];
+ if (s2in > greater2) {
+ fCoincidentT[fSwap ^ 1][index] = s2in;
+ } else if (e2in > greater2) {
+ fCoincidentT[fSwap ^ 1][index] = e2in;
+ }
+ return;
+ }
+ }
+ assert(fCoincidentUsed < 9);
+ fCoincidentT[fSwap][fCoincidentUsed] = s1;
+ fCoincidentT[fSwap ^ 1][fCoincidentUsed] = s2;
+ ++fCoincidentUsed;
+ fCoincidentT[fSwap][fCoincidentUsed] = e1;
+ fCoincidentT[fSwap ^ 1][fCoincidentUsed] = e2;
+ ++fCoincidentUsed;
+ }
+
+ // FIXME: this is necessary because curve/curve intersections are noisy
+ // remove once curve/curve intersections are improved
+ void cleanUp();
+
int coincidentUsed() {
return fCoincidentUsed;
}
@@ -59,10 +118,58 @@
fT[fSwap][index] = val;
}
}
+
+ void insert(double one, double two) {
+ assert(fUsed <= 1 || fT[0][0] < fT[0][1]);
+ int index;
+ for (index = 0; index < fUsed; ++index) {
+ if (approximately_equal(fT[0][index], one)
+ && approximately_equal(fT[1][index], two)) {
+ return;
+ }
+ if (fT[0][index] > one) {
+ break;
+ }
+ }
+ assert(fUsed < 9);
+ int remaining = fUsed - index;
+ if (remaining > 0) {
+ memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
+ memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
+ }
+ fT[0][index] = one;
+ fT[1][index] = two;
+ ++fUsed;
+ }
+
+ void insertOne(double t, int side) {
+ int used = side ? fUsed2 : fUsed;
+ assert(used <= 1 || fT[side][0] < fT[side][1]);
+ int index;
+ for (index = 0; index < used; ++index) {
+ if (approximately_equal(fT[side][index], t)) {
+ return;
+ }
+ if (fT[side][index] > t) {
+ break;
+ }
+ }
+ assert(used < 9);
+ int remaining = used - index;
+ if (remaining > 0) {
+ memmove(&fT[side][index + 1], &fT[side][index], sizeof(fT[side][0]) * remaining);
+ }
+ fT[side][index] = t;
+ side ? ++fUsed2 : ++fUsed;
+ }
- bool intersected() {
+ bool intersected() const {
return fUsed > 0;
}
+
+ bool insertBalanced() const {
+ return fUsed == fUsed2;
+ }
void swap() {
fSwap ^= 1;
@@ -79,6 +186,7 @@
double fT[2][9];
double fCoincidentT[2][9];
int fUsed;
+ int fUsed2;
int fCoincidentUsed;
private:
int fSwap;