shape ops work in progress
this fixes quad/line intersection
git-svn-id: http://skia.googlecode.com/svn/trunk@5277 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index f269b71..fc9c676 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -91,48 +91,41 @@
, intersections(i) {
}
-bool intersect() {
- double slope;
- double axisIntercept;
- moreHorizontal = implicitLine(line, slope, axisIntercept);
- double A = quad[2].x; // c
- double B = quad[1].x; // b
- double C = quad[0].x; // a
+int intersect() {
+/*
+ solve by rotating line+quad so line is horizontal, then finding the roots
+ set up matrix to rotate quad to x-axis
+ |cos(a) -sin(a)|
+ |sin(a) cos(a)|
+ note that cos(a) = A(djacent) / Hypoteneuse
+ sin(a) = O(pposite) / Hypoteneuse
+ since we are computing Ts, we can ignore hypoteneuse, the scale factor:
+ | A -O |
+ | O A |
+ A = line[1].x - line[0].x (adjacent side of the right triangle)
+ O = line[1].y - line[0].y (opposite side of the right triangle)
+ for each of the three points (e.g. n = 0 to 2)
+ quad[n].y' = (quad[n].y - line[0].y) * A - (quad[n].x - line[0].x) * O
+*/
+ double adj = line[1].x - line[0].x;
+ double opp = line[1].y - line[0].y;
+ double r[3];
+ for (int n = 0; n < 3; ++n) {
+ r[n] = (quad[n].y - line[0].y) * adj - (quad[n].x - line[0].x) * opp;
+ }
+ double A = r[2];
+ double B = r[1];
+ double C = r[0];
A += C - 2 * B; // A = a - 2*b + c
- B -= C; // B = -(a - b)
- double D = quad[2].y; // f
- double E = quad[1].y; // e
- double F = quad[0].y; // d
- D += F - 2 * E; // D = d - 2*e + f
- E -= F; // E = -(d - e)
- if (moreHorizontal) {
- A = A * slope - D;
- B = B * slope - E;
- C = C * slope - F + axisIntercept;
- } else {
- A = A - D * slope;
- B = B - E * slope;
- C = C - F * slope - axisIntercept;
- }
- double t[2];
- int roots = quadraticRoots(A, B, C, t);
- for (int x = 0; x < roots; ) {
- double lineT = findLineT(t[x]);
- if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) {
- if (x < --roots) {
- t[x] = t[roots];
- }
- continue;
+ B -= C; // B = -(b - c)
+ int roots = quadraticRoots(A, B, C, intersections.fT[0]);
+ for (int index = 0; index < roots; ) {
+ double lineT = findLineT(intersections.fT[0][index]);
+ if (lineIntersects(lineT, index, roots)) {
+ ++index;
}
- if (lineT < FLT_EPSILON) {
- lineT = 0;
- } else if (lineT > 1 - FLT_EPSILON) {
- lineT = 1;
- }
- intersections.add(t[x], lineT);
- ++x;
}
- return roots > 0;
+ return roots;
}
int horizontalIntersect(double axisIntercept) {
@@ -145,6 +138,19 @@
return quadraticRoots(D, E, F, intersections.fT[0]);
}
+int horizontalIntersect(double axisIntercept, double left, double right) {
+ int roots = horizontalIntersect(axisIntercept);
+ for (int index = 0; index < roots; ) {
+ double x;
+ xy_at_t(quad, intersections.fT[0][index], x, *(double*) NULL);
+ double lineT = (x - left) / (right - left);
+ if (lineIntersects(lineT, index, roots)) {
+ ++index;
+ }
+ }
+ return roots;
+}
+
int verticalIntersect(double axisIntercept) {
double D = quad[2].x; // f
double E = quad[1].x; // e
@@ -155,6 +161,19 @@
return quadraticRoots(D, E, F, intersections.fT[0]);
}
+int verticalIntersect(double axisIntercept, double top, double bottom) {
+ int roots = verticalIntersect(axisIntercept);
+ for (int index = 0; index < roots; ) {
+ double y;
+ xy_at_t(quad, intersections.fT[0][index], *(double*) NULL, y);
+ double lineT = (y - top) / (bottom - top);
+ if (lineIntersects(lineT, index, roots)) {
+ ++index;
+ }
+ }
+ return roots;
+}
+
protected:
double findLineT(double t) {
@@ -172,6 +191,22 @@
return (quadVal - lPtr[0]) / (lPtr[2] - lPtr[0]);
}
+bool lineIntersects(double lineT, const int x, int& roots) {
+ if (!approximately_zero_or_more(lineT) || !approximately_one_or_less(lineT)) {
+ if (x < --roots) {
+ intersections.fT[0][x] = intersections.fT[0][roots];
+ }
+ return false;
+ }
+ if (approximately_less_than_zero(lineT)) {
+ lineT = 0;
+ } else if (approximately_greater_than_one(lineT)) {
+ lineT = 1;
+ }
+ intersections.fT[1][x] = lineT;
+ return true;
+}
+
private:
const Quadratic& quad;
@@ -241,25 +276,7 @@
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);
- double lineT = (x - left) / (right - left);
- if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) {
- if (--result > index) {
- intersections.fT[0][index] = intersections.fT[0][result];
- }
- continue;
- }
- if (lineT < FLT_EPSILON) {
- lineT = 0;
- } else if (lineT > 1 - FLT_EPSILON) {
- lineT = 1;
- }
- intersections.fT[1][index] = lineT;
- ++index;
- }
+ int result = q.horizontalIntersect(y, left, right);
if (flipped) {
// OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
for (int index = 0; index < result; ++index) {
@@ -272,27 +289,9 @@
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);
- double lineT = (y - top) / (bottom - top);
- if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) {
- if (--result > index) {
- intersections.fT[0][index] = intersections.fT[0][result];
- }
- continue;
- }
- if (lineT < FLT_EPSILON) {
- lineT = 0;
- } else if (lineT > 1 - FLT_EPSILON) {
- lineT = 1;
- }
- intersections.fT[1][index] = lineT;
- ++index;
- }
+ int result = q.verticalIntersect(x, top, bottom);
if (flipped) {
- // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
+ // 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];
}
@@ -300,7 +299,7 @@
return result;
}
-bool intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
+int intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
LineQuadraticIntersections q(quad, line, i);
return q.intersect();
}