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

Unified Diff: src/pathops/SkReduceOrder.cpp

Issue 12880016: Add intersections for path ops (Closed) Base URL: http://skia.googlecode.com/svn/trunk/
Patch Set: Created 7 years, 9 months 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
===================================================================
--- src/pathops/SkReduceOrder.cpp (revision 0)
+++ src/pathops/SkReduceOrder.cpp (revision 0)
@@ -0,0 +1,450 @@
+/*
+ * 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 "SkReduceOrder.h"
+
+int SkReduceOrder::reduce(const SkDLine& line) {
+ fLine[0] = line[0];
+ int different = line[0] != line[1];
+ fLine[1] = line[different];
+ 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;
+}
+
+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;
+ 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;
+ 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,
+ int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
+ int startIndex = 0;
+ int endIndex = 2;
+ while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
+ --endIndex;
+ if (endIndex == 0) {
+ SkDebugf("%s shouldn't get here if all four points are about equal", __FUNCTION__);
+ SkASSERT(0);
+ }
+ }
+ if (!quad.isLinear(startIndex, endIndex)) {
+ return 0;
+ }
+ // 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);
+}
+
+// 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 SkReduceOrder::reduce(const SkDQuad& quad, Style 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].fX > quad[index].fX) {
+ minX = index;
+ }
+ if (quad[minY].fY > quad[index].fY) {
+ minY = index;
+ }
+ if (quad[maxX].fX < quad[index].fX) {
+ maxX = index;
+ }
+ if (quad[maxY].fY < quad[index].fY) {
+ maxY = index;
+ }
+ }
+ for (index = 0; index < 3; ++index) {
+ if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) {
+ minXSet |= 1 << index;
+ }
+ if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) {
+ minYSet |= 1 << index;
+ }
+ }
+ if (minXSet == 0x7) { // test for vertical line
+ if (minYSet == 0x7) { // return 1 if all four are coincident
+ return coincident_line(quad, fQuad);
+ }
+ return vertical_line(quad, reduceStyle, fQuad);
+ }
+ if (minYSet == 0xF) { // test for horizontal line
+ return horizontal_line(quad, reduceStyle, fQuad);
+ }
+ int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, fQuad);
+ if (result) {
+ return result;
+ }
+ fQuad = quad;
+ return 3;
+}
+
+////////////////////////////////////////////////////////////////////////////////////
+
+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;
+}
+
+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];
+ 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];
+ 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);
+}
+
+// check to see if it is a quadratic or a line
+static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
+ double dx10 = cubic[1].fX - cubic[0].fX;
+ double dx23 = cubic[2].fX - cubic[3].fX;
+ double midX = cubic[0].fX + dx10 * 3 / 2;
+ if (!AlmostEqualUlps(midX - cubic[3].fX, dx23 * 3 / 2)) {
+ return 0;
+ }
+ double dy10 = cubic[1].fY - cubic[0].fY;
+ double dy23 = cubic[2].fY - cubic[3].fY;
+ double midY = cubic[0].fY + dy10 * 3 / 2;
+ if (!AlmostEqualUlps(midY - cubic[3].fY, dy23 * 3 / 2)) {
+ return 0;
+ }
+ reduction[0] = cubic[0];
+ reduction[1].fX = midX;
+ reduction[1].fY = midY;
+ reduction[2] = cubic[3];
+ return 3;
+}
+
+static int check_linear(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
+ int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
+ int startIndex = 0;
+ int endIndex = 3;
+ while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) {
+ --endIndex;
+ if (endIndex == 0) {
+ SkDebugf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__);
+ SkASSERT(0);
+ }
+ }
+ if (!cubic.isLinear(startIndex, endIndex)) {
+ return 0;
+ }
+ // 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);
+}
+
+/* food for thought:
+http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html
+
+Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
+corresponding quadratic Bezier are (given in convex combinations of
+points):
+
+q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
+q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
+q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4
+
+Of course, this curve does not interpolate the end-points, but it would
+be interesting to see the behaviour of such a curve in an applet.
+
+--
+Kalle Rutanen
+http://kaba.hilvi.org
+
+*/
+
+// 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 SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics,
+ Style reduceStyle) {
+ int index, minX, maxX, minY, maxY;
+ int minXSet, minYSet;
+ minX = maxX = minY = maxY = 0;
+ minXSet = minYSet = 0;
+ for (index = 1; index < 4; ++index) {
+ if (cubic[minX].fX > cubic[index].fX) {
+ minX = index;
+ }
+ if (cubic[minY].fY > cubic[index].fY) {
+ minY = index;
+ }
+ if (cubic[maxX].fX < cubic[index].fX) {
+ maxX = index;
+ }
+ if (cubic[maxY].fY < cubic[index].fY) {
+ maxY = index;
+ }
+ }
+ for (index = 0; index < 4; ++index) {
+ double cx = cubic[index].fX;
+ double cy = cubic[index].fY;
+ double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
+ SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
+ if (denom == 0) {
+ minXSet |= 1 << index;
+ minYSet |= 1 << index;
+ continue;
+ }
+ double inv = 1 / denom;
+ if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
+ minXSet |= 1 << index;
+ }
+ if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
+ minYSet |= 1 << index;
+ }
+ }
+ if (minXSet == 0xF) { // test for vertical line
+ if (minYSet == 0xF) { // return 1 if all four are coincident
+ return coincident_line(cubic, fCubic);
+ }
+ return vertical_line(cubic, reduceStyle, fCubic);
+ }
+ if (minYSet == 0xF) { // test for horizontal line
+ return horizontal_line(cubic, reduceStyle, fCubic);
+ }
+ int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, fCubic);
+ if (result) {
+ return result;
+ }
+ if (allowQuadratics == SkReduceOrder::kAllow_Quadratics
+ && (result = check_quadratic(cubic, fCubic))) {
+ return result;
+ }
+ fCubic = cubic;
+ return 4;
+}
+
+SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkTDArray<SkPoint>* reducePts) {
+ SkDQuad quad;
+ quad.set(a);
+ SkReduceOrder reducer;
+ int order = reducer.reduce(quad, kFill_Style);
+ if (order == 2) { // quad became line
+ for (int index = 0; index < order; ++index) {
+ SkPoint* pt = reducePts->append();
+ pt->fX = SkDoubleToScalar(reducer.fLine[index].fX);
+ pt->fY = SkDoubleToScalar(reducer.fLine[index].fY);
+ }
+ }
+ return (SkPath::Verb) (order - 1);
+}
+
+SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkTDArray<SkPoint>* reducePts) {
+ SkDCubic cubic;
+ cubic.set(a);
+ SkReduceOrder reducer;
+ int order = reducer.reduce(cubic, kAllow_Quadratics, kFill_Style);
+ if (order == 2 || order == 3) { // cubic became line or quad
+ for (int index = 0; index < order; ++index) {
+ SkPoint* pt = reducePts->append();
+ pt->fX = SkDoubleToScalar(reducer.fQuad[index].fX);
+ pt->fY = SkDoubleToScalar(reducer.fQuad[index].fY);
+ }
+ }
+ return (SkPath::Verb) (order - 1);
+}
« 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