Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(769)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/pathops/SkReduceOrder.cpp

Issue 75453003: optimize pathops coverage (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: remove fill parameter from reduce order Created 7 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/pathops/SkReduceOrder.h ('k') | tests/PathOpsCubicIntersectionTest.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/pathops/SkReduceOrder.cpp
diff --git a/src/pathops/SkReduceOrder.cpp b/src/pathops/SkReduceOrder.cpp
index 3dfdc9daeeb88d3e86de78980e6f9bc97a41b33a..ada52761b5c98811b59712df51641bc29ef3aeb5 100644
--- a/src/pathops/SkReduceOrder.cpp
+++ b/src/pathops/SkReduceOrder.cpp
@@ -13,12 +13,6 @@ int SkReduceOrder::reduce(const SkDLine& line) {
return 1 + different;
}
-static double interp_quad_coords(double a, double b, double c, double t) {
- double ab = SkDInterp(a, b, t);
- double bc = SkDInterp(b, c, t);
- return SkDInterp(ab, bc, t);
-}
-
static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) {
reduction[0] = reduction[1] = quad[0];
return 1;
@@ -28,49 +22,19 @@ static int reductionLineCount(const SkDQuad& reduction) {
return 1 + !reduction[0].approximatelyEqual(reduction[1]);
}
-static int vertical_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
- SkDQuad& reduction) {
- double tValue;
+static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) {
reduction[0] = quad[0];
reduction[1] = quad[2];
- if (reduceStyle == SkReduceOrder::kFill_Style) {
- return reductionLineCount(reduction);
- }
- int smaller = reduction[1].fY > reduction[0].fY;
- int larger = smaller ^ 1;
- if (SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue)) {
- double yExtrema = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY, tValue);
- if (reduction[smaller].fY > yExtrema) {
- reduction[smaller].fY = yExtrema;
- } else if (reduction[larger].fY < yExtrema) {
- reduction[larger].fY = yExtrema;
- }
- }
return reductionLineCount(reduction);
}
-static int horizontal_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
- SkDQuad& reduction) {
- double tValue;
+static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) {
reduction[0] = quad[0];
reduction[1] = quad[2];
- if (reduceStyle == SkReduceOrder::kFill_Style) {
- return reductionLineCount(reduction);
- }
- int smaller = reduction[1].fX > reduction[0].fX;
- int larger = smaller ^ 1;
- if (SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue)) {
- double xExtrema = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX, tValue);
- if (reduction[smaller].fX > xExtrema) {
- reduction[smaller].fX = xExtrema;
- } else if (reduction[larger].fX < xExtrema) {
- reduction[larger].fX = xExtrema;
- }
- }
return reductionLineCount(reduction);
}
-static int check_linear(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
+static int check_linear(const SkDQuad& quad,
int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
int startIndex = 0;
int endIndex = 2;
@@ -87,47 +51,6 @@ static int check_linear(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
// four are colinear: return line formed by outside
reduction[0] = quad[0];
reduction[1] = quad[2];
- if (reduceStyle == SkReduceOrder::kFill_Style) {
- return reductionLineCount(reduction);
- }
- int sameSide;
- bool useX = quad[maxX].fX - quad[minX].fX >= quad[maxY].fY - quad[minY].fY;
- if (useX) {
- sameSide = SkDSign(quad[0].fX - quad[1].fX) + SkDSign(quad[2].fX - quad[1].fX);
- } else {
- sameSide = SkDSign(quad[0].fY - quad[1].fY) + SkDSign(quad[2].fY - quad[1].fY);
- }
- if ((sameSide & 3) != 2) {
- return reductionLineCount(reduction);
- }
- double tValue;
- int root;
- if (useX) {
- root = SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue);
- } else {
- root = SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue);
- }
- if (root) {
- SkDPoint extrema;
- extrema.fX = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX, tValue);
- extrema.fY = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY, tValue);
- // sameSide > 0 means mid is smaller than either [0] or [2], so replace smaller
- int replace;
- if (useX) {
- if ((extrema.fX < quad[0].fX) ^ (extrema.fX < quad[2].fX)) {
- return reductionLineCount(reduction);
- }
- replace = ((extrema.fX < quad[0].fX) | (extrema.fX < quad[2].fX))
- ^ (quad[0].fX < quad[2].fX);
- } else {
- if ((extrema.fY < quad[0].fY) ^ (extrema.fY < quad[2].fY)) {
- return reductionLineCount(reduction);
- }
- replace = ((extrema.fY < quad[0].fY) | (extrema.fY < quad[2].fY))
- ^ (quad[0].fY < quad[2].fY);
- }
- reduction[replace] = extrema;
- }
return reductionLineCount(reduction);
}
@@ -137,7 +60,7 @@ static int check_linear(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
// 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 SkReduceOrder::reduce(const SkDQuad& quad, Style reduceStyle) {
+int SkReduceOrder::reduce(const SkDQuad& quad) {
int index, minX, maxX, minY, maxY;
int minXSet, minYSet;
minX = maxX = minY = maxY = 0;
@@ -168,12 +91,12 @@ int SkReduceOrder::reduce(const SkDQuad& quad, Style reduceStyle) {
if (minYSet == 0x7) { // return 1 if all four are coincident
return coincident_line(quad, fQuad);
}
- return vertical_line(quad, reduceStyle, fQuad);
+ return vertical_line(quad, fQuad);
}
if (minYSet == 0xF) { // test for horizontal line
- return horizontal_line(quad, reduceStyle, fQuad);
+ return horizontal_line(quad, fQuad);
}
- int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, fQuad);
+ int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
if (result) {
return result;
}
@@ -183,15 +106,6 @@ int SkReduceOrder::reduce(const SkDQuad& quad, Style reduceStyle) {
////////////////////////////////////////////////////////////////////////////////////
-static double interp_cubic_coords(const double* src, double t) {
- double ab = SkDInterp(src[0], src[2], t);
- double bc = SkDInterp(src[2], src[4], t);
- double cd = SkDInterp(src[4], src[6], t);
- double abc = SkDInterp(ab, bc, t);
- double bcd = SkDInterp(bc, cd, t);
- return SkDInterp(abc, bcd, t);
-}
-
static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
reduction[0] = reduction[1] = cubic[0];
return 1;
@@ -201,51 +115,15 @@ static int reductionLineCount(const SkDCubic& reduction) {
return 1 + !reduction[0].approximatelyEqual(reduction[1]);
}
-static int vertical_line(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
- SkDCubic& reduction) {
- double tValues[2];
+static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
reduction[0] = cubic[0];
reduction[1] = cubic[3];
- if (reduceStyle == SkReduceOrder::kFill_Style) {
- return reductionLineCount(reduction);
- }
- int smaller = reduction[1].fY > reduction[0].fY;
- int larger = smaller ^ 1;
- int roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cubic[3].fY, tValues);
- for (int index = 0; index < roots; ++index) {
- double yExtrema = interp_cubic_coords(&cubic[0].fY, tValues[index]);
- if (reduction[smaller].fY > yExtrema) {
- reduction[smaller].fY = yExtrema;
- continue;
- }
- if (reduction[larger].fY < yExtrema) {
- reduction[larger].fY = yExtrema;
- }
- }
return reductionLineCount(reduction);
}
-static int horizontal_line(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
- SkDCubic& reduction) {
- double tValues[2];
+static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
reduction[0] = cubic[0];
reduction[1] = cubic[3];
- if (reduceStyle == SkReduceOrder::kFill_Style) {
- return reductionLineCount(reduction);
- }
- int smaller = reduction[1].fX > reduction[0].fX;
- int larger = smaller ^ 1;
- int roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cubic[3].fX, tValues);
- for (int index = 0; index < roots; ++index) {
- double xExtrema = interp_cubic_coords(&cubic[0].fX, tValues[index]);
- if (reduction[smaller].fX > xExtrema) {
- reduction[smaller].fX = xExtrema;
- continue;
- }
- if (reduction[larger].fX < xExtrema) {
- reduction[larger].fX = xExtrema;
- }
- }
return reductionLineCount(reduction);
}
@@ -276,7 +154,7 @@ static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
return 3;
}
-static int check_linear(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
+static int check_linear(const SkDCubic& cubic,
int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
int startIndex = 0;
int endIndex = 3;
@@ -293,50 +171,6 @@ static int check_linear(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
// four are colinear: return line formed by outside
reduction[0] = cubic[0];
reduction[1] = cubic[3];
- if (reduceStyle == SkReduceOrder::kFill_Style) {
- return reductionLineCount(reduction);
- }
- int sameSide1;
- int sameSide2;
- bool useX = cubic[maxX].fX - cubic[minX].fX >= cubic[maxY].fY - cubic[minY].fY;
- if (useX) {
- sameSide1 = SkDSign(cubic[0].fX - cubic[1].fX) + SkDSign(cubic[3].fX - cubic[1].fX);
- sameSide2 = SkDSign(cubic[0].fX - cubic[2].fX) + SkDSign(cubic[3].fX - cubic[2].fX);
- } else {
- sameSide1 = SkDSign(cubic[0].fY - cubic[1].fY) + SkDSign(cubic[3].fY - cubic[1].fY);
- sameSide2 = SkDSign(cubic[0].fY - cubic[2].fY) + SkDSign(cubic[3].fY - cubic[2].fY);
- }
- if (sameSide1 == sameSide2 && (sameSide1 & 3) != 2) {
- return reductionLineCount(reduction);
- }
- double tValues[2];
- int roots;
- if (useX) {
- roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cubic[3].fX, tValues);
- } else {
- roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cubic[3].fY, tValues);
- }
- for (int index = 0; index < roots; ++index) {
- SkDPoint extrema;
- extrema.fX = interp_cubic_coords(&cubic[0].fX, tValues[index]);
- extrema.fY = interp_cubic_coords(&cubic[0].fY, tValues[index]);
- // sameSide > 0 means mid is smaller than either [0] or [3], so replace smaller
- int replace;
- if (useX) {
- if ((extrema.fX < cubic[0].fX) ^ (extrema.fX < cubic[3].fX)) {
- continue;
- }
- replace = ((extrema.fX < cubic[0].fX) | (extrema.fX < cubic[3].fX))
- ^ (cubic[0].fX < cubic[3].fX);
- } else {
- if ((extrema.fY < cubic[0].fY) ^ (extrema.fY < cubic[3].fY)) {
- continue;
- }
- replace = ((extrema.fY < cubic[0].fY) | (extrema.fY < cubic[3].fY))
- ^ (cubic[0].fY < cubic[3].fY);
- }
- reduction[replace] = extrema;
- }
return reductionLineCount(reduction);
}
@@ -366,8 +200,7 @@ http://kaba.hilvi.org
// 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 SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics,
- Style reduceStyle) {
+int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
int index, minX, maxX, minY, maxY;
int minXSet, minYSet;
minX = maxX = minY = maxY = 0;
@@ -408,12 +241,12 @@ int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics,
if (minYSet == 0xF) { // return 1 if all four are coincident
return coincident_line(cubic, fCubic);
}
- return vertical_line(cubic, reduceStyle, fCubic);
+ return vertical_line(cubic, fCubic);
}
if (minYSet == 0xF) { // test for horizontal line
- return horizontal_line(cubic, reduceStyle, fCubic);
+ return horizontal_line(cubic, fCubic);
}
- int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, fCubic);
+ int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
if (result) {
return result;
}
@@ -429,7 +262,7 @@ SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
SkDQuad quad;
quad.set(a);
SkReduceOrder reducer;
- int order = reducer.reduce(quad, kFill_Style);
+ int order = reducer.reduce(quad);
if (order == 2) { // quad became line
for (int index = 0; index < order; ++index) {
*reducePts++ = reducer.fLine[index].asSkPoint();
@@ -442,7 +275,7 @@ SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
SkDCubic cubic;
cubic.set(a);
SkReduceOrder reducer;
- int order = reducer.reduce(cubic, kAllow_Quadratics, kFill_Style);
+ int order = reducer.reduce(cubic, kAllow_Quadratics);
if (order == 2 || order == 3) { // cubic became line or quad
for (int index = 0; index < order; ++index) {
*reducePts++ = reducer.fQuad[index].asSkPoint();
« no previous file with comments | « src/pathops/SkReduceOrder.h ('k') | tests/PathOpsCubicIntersectionTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698