19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 7c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "CurveIntersection.h" 8639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "Extrema.h" 9639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "IntersectionUtilities.h" 10639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "LineParameters.h" 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 12639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comstatic double interp_cubic_coords(const double* src, double t) 13639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com{ 14639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ab = interp(src[0], src[2], t); 15639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bc = interp(src[2], src[4], t); 16639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double cd = interp(src[4], src[6], t); 17639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double abc = interp(ab, bc, t); 18639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bcd = interp(bc, cd, t); 19639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return interp(abc, bcd, t); 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 21639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comstatic int coincident_line(const Cubic& cubic, Cubic& reduction) { 23639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[0] = reduction[1] = cubic[0]; 24639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 1; 25639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 26639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 2747d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comstatic int vertical_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, Cubic& reduction) { 28639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double tValues[2]; 29639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[0] = cubic[0]; 30639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[1] = cubic[3]; 3147d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com if (reduceStyle == kReduceOrder_TreatAsFill) { 3247d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com return 2; 3347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com } 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int smaller = reduction[1].y > reduction[0].y; 35639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int larger = smaller ^ 1; 36fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com int roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tValues); 37639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (int index = 0; index < roots; ++index) { 38639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double yExtrema = interp_cubic_coords(&cubic[0].y, tValues[index]); 39639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (reduction[smaller].y > yExtrema) { 40639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[smaller].y = yExtrema; 41639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com continue; 42d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com } 43639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (reduction[larger].y < yExtrema) { 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[larger].y = yExtrema; 45639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 46639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 47639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 2; 48639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 49639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 5047d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comstatic int horizontal_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, Cubic& reduction) { 51639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double tValues[2]; 52639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[0] = cubic[0]; 53639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[1] = cubic[3]; 5447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com if (reduceStyle == kReduceOrder_TreatAsFill) { 5547d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com return 2; 5647d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com } 57639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int smaller = reduction[1].x > reduction[0].x; 58639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int larger = smaller ^ 1; 59fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com int roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues); 60639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (int index = 0; index < roots; ++index) { 61639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double xExtrema = interp_cubic_coords(&cubic[0].x, tValues[index]); 62639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (reduction[smaller].x > xExtrema) { 63639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[smaller].x = xExtrema; 64639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com continue; 65d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com } 66639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (reduction[larger].x < xExtrema) { 67639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[larger].x = xExtrema; 68639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 69639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 70639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 2; 71639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 72639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 73639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// check to see if it is a quadratic or a line 74a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.comstatic int check_quadratic(const Cubic& cubic, Cubic& reduction) { 75639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dx10 = cubic[1].x - cubic[0].x; 76639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dx23 = cubic[2].x - cubic[3].x; 77639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double midX = cubic[0].x + dx10 * 3 / 2; 786d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (!AlmostEqualUlps(midX - cubic[3].x, dx23 * 3 / 2)) { 79639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 0; 80639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 81639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dy10 = cubic[1].y - cubic[0].y; 82639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dy23 = cubic[2].y - cubic[3].y; 83639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double midY = cubic[0].y + dy10 * 3 / 2; 846d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (!AlmostEqualUlps(midY - cubic[3].y, dy23 * 3 / 2)) { 85639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 0; 86639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 87639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[0] = cubic[0]; 88639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[1].x = midX; 89639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[1].y = midY; 90639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[2] = cubic[3]; 91639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 3; 92639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 93639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 9447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comstatic int check_linear(const Cubic& cubic, ReduceOrder_Styles reduceStyle, 9547d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com int minX, int maxX, int minY, int maxY, Cubic& reduction) { 96639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int startIndex = 0; 97639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int endIndex = 3; 98639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) { 99639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com --endIndex; 100639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (endIndex == 0) { 1016d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com printf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__); 102aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(0); 103639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 104639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 10515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com if (!isLinear(cubic, startIndex, endIndex)) { 10615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com return 0; 107639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 108639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // four are colinear: return line formed by outside 109639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[0] = cubic[0]; 110639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[1] = cubic[3]; 11147d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com if (reduceStyle == kReduceOrder_TreatAsFill) { 11247d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com return 2; 11347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com } 114639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int sameSide1; 115639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int sameSide2; 116639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com bool useX = cubic[maxX].x - cubic[minX].x >= cubic[maxY].y - cubic[minY].y; 117639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (useX) { 118639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sameSide1 = sign(cubic[0].x - cubic[1].x) + sign(cubic[3].x - cubic[1].x); 119639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sameSide2 = sign(cubic[0].x - cubic[2].x) + sign(cubic[3].x - cubic[2].x); 120639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 121639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sameSide1 = sign(cubic[0].y - cubic[1].y) + sign(cubic[3].y - cubic[1].y); 122639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sameSide2 = sign(cubic[0].y - cubic[2].y) + sign(cubic[3].y - cubic[2].y); 123639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 124639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (sameSide1 == sameSide2 && (sameSide1 & 3) != 2) { 125639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 2; 126639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 127639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double tValues[2]; 128639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int roots; 129639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (useX) { 130fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues); 131639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 132fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tValues); 133639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 13415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com for (int index = 0; index < roots; ++index) { 135639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com _Point extrema; 136639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com extrema.x = interp_cubic_coords(&cubic[0].x, tValues[index]); 137639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com extrema.y = interp_cubic_coords(&cubic[0].y, tValues[index]); 138639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // sameSide > 0 means mid is smaller than either [0] or [3], so replace smaller 139639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int replace; 140639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (useX) { 141639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (extrema.x < cubic[0].x ^ extrema.x < cubic[3].x) { 142639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com continue; 143639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 144639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com replace = (extrema.x < cubic[0].x | extrema.x < cubic[3].x) 1459f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com ^ (cubic[0].x < cubic[3].x); 146639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 147639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (extrema.y < cubic[0].y ^ extrema.y < cubic[3].y) { 148639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com continue; 149639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 150639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com replace = (extrema.y < cubic[0].y | extrema.y < cubic[3].y) 1519f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com ^ (cubic[0].y < cubic[3].y); 152639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 153639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com reduction[replace] = extrema; 154639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 155639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 2; 156639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 157639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 15815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.combool isLinear(const Cubic& cubic, int startIndex, int endIndex) { 15915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com LineParameters lineParameters; 16015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com lineParameters.cubicEndPoints(cubic, startIndex, endIndex); 16173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // FIXME: maybe it's possible to avoid this and compare non-normalized 16273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com lineParameters.normalize(); 16385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com double distance = lineParameters.controlPtDistance(cubic, 1); 16473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!approximately_zero(distance)) { 16573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return false; 16615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com } 16785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com distance = lineParameters.controlPtDistance(cubic, 2); 16873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return approximately_zero(distance); 16915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com} 17015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 171639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* food for thought: 172639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comhttp://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html 173639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 174639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comGiven points c1, c2, c3 and c4 of a cubic Bezier, the points of the 175639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comcorresponding quadratic Bezier are (given in convex combinations of 176639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.compoints): 177639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 178639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comq1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4 179639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comq2 = -c1 + (3/2)c2 + (3/2)c3 - c4 180639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comq3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4 181639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 182639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comOf course, this curve does not interpolate the end-points, but it would 183639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.combe interesting to see the behaviour of such a curve in an applet. 184639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 185639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com-- 186639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comKalle Rutanen 187639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comhttp://kaba.hilvi.org 188639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 189639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com*/ 190639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 191639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// reduce to a quadratic or smaller 192639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// look for identical points 193d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com// look for all four points in a line 194639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // note that three points in a line doesn't simplify a cubic 195639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// look for approximation with single quadratic 196639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // save approximation with multiple quadratics for later 19747d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comint reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Quadratics allowQuadratics, 19847d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com ReduceOrder_Styles reduceStyle) { 199639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int index, minX, maxX, minY, maxY; 200639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int minXSet, minYSet; 201639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minX = maxX = minY = maxY = 0; 202639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minXSet = minYSet = 0; 203639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 1; index < 4; ++index) { 204639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (cubic[minX].x > cubic[index].x) { 205639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minX = index; 206639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 207639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (cubic[minY].y > cubic[index].y) { 208639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minY = index; 209639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 210639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (cubic[maxX].x < cubic[index].x) { 211639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxX = index; 212639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 213639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (cubic[maxY].y < cubic[index].y) { 214639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxY = index; 215639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 216639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 217639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 0; index < 4; ++index) { 21845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double cx = cubic[index].x; 21945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double cy = cubic[index].y; 22045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double denom = SkTMax(fabs(cx), SkTMax(fabs(cy), 22145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkTMax(fabs(cubic[minX].x), fabs(cubic[minY].y)))); 22245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (denom == 0) { 22345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com minXSet |= 1 << index; 22445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com minYSet |= 1 << index; 22545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com continue; 22645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 22745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double inv = 1 / denom; 22845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (approximately_equal_half(cx * inv, cubic[minX].x * inv)) { 229639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minXSet |= 1 << index; 230639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 23145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (approximately_equal_half(cy * inv, cubic[minY].y * inv)) { 232639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minYSet |= 1 << index; 233639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 234639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 235639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (minXSet == 0xF) { // test for vertical line 236639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (minYSet == 0xF) { // return 1 if all four are coincident 237639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return coincident_line(cubic, reduction); 238639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 23947d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com return vertical_line(cubic, reduceStyle, reduction); 240639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 241639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (minYSet == 0xF) { // test for horizontal line 24247d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com return horizontal_line(cubic, reduceStyle, reduction); 243639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 24447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, reduction); 245639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (result) { 246639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return result; 247639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 24847d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com if (allowQuadratics == kReduceOrder_QuadraticsAllowed 24947d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com && (result = check_quadratic(cubic, reduction))) { 250639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return result; 251639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 252639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com memcpy(reduction, cubic, sizeof(Cubic)); 253639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 4; 254639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 255