Index: experimental/Intersection/QuadraticReduceOrder.cpp |
diff --git a/experimental/Intersection/QuadraticReduceOrder.cpp b/experimental/Intersection/QuadraticReduceOrder.cpp |
deleted file mode 100644 |
index 27c7a29bf299be19e9fc2d1dce32f2ba587f919c..0000000000000000000000000000000000000000 |
--- a/experimental/Intersection/QuadraticReduceOrder.cpp |
+++ /dev/null |
@@ -1,184 +0,0 @@ |
-/* |
- * 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 "Extrema.h" |
-#include "IntersectionUtilities.h" |
-#include "LineParameters.h" |
- |
-static double interp_quad_coords(double a, double b, double c, double t) |
-{ |
- double ab = interp(a, b, t); |
- double bc = interp(b, c, t); |
- return interp(ab, bc, t); |
-} |
- |
-static int coincident_line(const Quadratic& quad, Quadratic& reduction) { |
- reduction[0] = reduction[1] = quad[0]; |
- return 1; |
-} |
- |
-static int vertical_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle, |
- Quadratic& reduction) { |
- double tValue; |
- reduction[0] = quad[0]; |
- reduction[1] = quad[2]; |
- if (reduceStyle == kReduceOrder_TreatAsFill) { |
- return 2; |
- } |
- int smaller = reduction[1].y > reduction[0].y; |
- int larger = smaller ^ 1; |
- 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; |
- } else if (reduction[larger].y < yExtrema) { |
- reduction[larger].y = yExtrema; |
- } |
- } |
- return 2; |
-} |
- |
-static int horizontal_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle, |
- Quadratic& reduction) { |
- double tValue; |
- reduction[0] = quad[0]; |
- reduction[1] = quad[2]; |
- if (reduceStyle == kReduceOrder_TreatAsFill) { |
- return 2; |
- } |
- int smaller = reduction[1].x > reduction[0].x; |
- int larger = smaller ^ 1; |
- 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; |
- } else if (reduction[larger].x < xExtrema) { |
- reduction[larger].x = xExtrema; |
- } |
- } |
- return 2; |
-} |
- |
-static int check_linear(const Quadratic& quad, ReduceOrder_Styles reduceStyle, |
- int minX, int maxX, int minY, int maxY, Quadratic& reduction) { |
- int startIndex = 0; |
- int endIndex = 2; |
- while (quad[startIndex].approximatelyEqual(quad[endIndex])) { |
- --endIndex; |
- if (endIndex == 0) { |
- printf("%s shouldn't get here if all four points are about equal", __FUNCTION__); |
- SkASSERT(0); |
- } |
- } |
- if (!isLinear(quad, startIndex, endIndex)) { |
- return 0; |
- } |
- // four are colinear: return line formed by outside |
- reduction[0] = quad[0]; |
- reduction[1] = quad[2]; |
- if (reduceStyle == kReduceOrder_TreatAsFill) { |
- return 2; |
- } |
- int sameSide; |
- bool useX = quad[maxX].x - quad[minX].x >= quad[maxY].y - quad[minY].y; |
- if (useX) { |
- sameSide = sign(quad[0].x - quad[1].x) + sign(quad[2].x - quad[1].x); |
- } else { |
- sameSide = sign(quad[0].y - quad[1].y) + sign(quad[2].y - quad[1].y); |
- } |
- if ((sameSide & 3) != 2) { |
- return 2; |
- } |
- double tValue; |
- int root; |
- if (useX) { |
- root = findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue); |
- } else { |
- root = findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue); |
- } |
- if (root) { |
- _Point extrema; |
- extrema.x = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue); |
- extrema.y = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue); |
- // sameSide > 0 means mid is smaller than either [0] or [2], so replace smaller |
- int replace; |
- if (useX) { |
- if (extrema.x < quad[0].x ^ extrema.x < quad[2].x) { |
- return 2; |
- } |
- replace = (extrema.x < quad[0].x | extrema.x < quad[2].x) |
- ^ (quad[0].x < quad[2].x); |
- } else { |
- if (extrema.y < quad[0].y ^ extrema.y < quad[2].y) { |
- return 2; |
- } |
- replace = (extrema.y < quad[0].y | extrema.y < quad[2].y) |
- ^ (quad[0].y < quad[2].y); |
- } |
- reduction[replace] = extrema; |
- } |
- return 2; |
-} |
- |
-bool isLinear(const Quadratic& quad, int startIndex, int endIndex) { |
- LineParameters lineParameters; |
- lineParameters.quadEndPoints(quad, startIndex, endIndex); |
- // FIXME: maybe it's possible to avoid this and compare non-normalized |
- lineParameters.normalize(); |
- double distance = lineParameters.controlPtDistance(quad); |
- return approximately_zero(distance); |
-} |
- |
-// reduce to a quadratic or smaller |
-// look for identical points |
-// look for all four points in a line |
- // note that three points in a line doesn't simplify a cubic |
-// look for approximation with single quadratic |
- // save approximation with multiple quadratics for later |
-int reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles reduceStyle) { |
- int index, minX, maxX, minY, maxY; |
- int minXSet, minYSet; |
- minX = maxX = minY = maxY = 0; |
- minXSet = minYSet = 0; |
- for (index = 1; index < 3; ++index) { |
- if (quad[minX].x > quad[index].x) { |
- minX = index; |
- } |
- if (quad[minY].y > quad[index].y) { |
- minY = index; |
- } |
- if (quad[maxX].x < quad[index].x) { |
- maxX = index; |
- } |
- if (quad[maxY].y < quad[index].y) { |
- maxY = index; |
- } |
- } |
- for (index = 0; index < 3; ++index) { |
- if (AlmostEqualUlps(quad[index].x, quad[minX].x)) { |
- minXSet |= 1 << index; |
- } |
- if (AlmostEqualUlps(quad[index].y, quad[minY].y)) { |
- minYSet |= 1 << index; |
- } |
- } |
- 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, reduceStyle, reduction); |
- } |
- if (minYSet == 0xF) { // test for horizontal line |
- return horizontal_line(quad, reduceStyle, reduction); |
- } |
- int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, reduction); |
- if (result) { |
- return result; |
- } |
- memcpy(reduction, quad, sizeof(Quadratic)); |
- return 3; |
-} |