15f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)/* 25f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) * Copyright 2012 Google Inc. 35f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) * 45f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) * Use of this source code is governed by a BSD-style license that can be 55f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) * found in the LICENSE file. 65f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) */ 75f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "CurveIntersection.h" 85f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "Extrema.h" 95f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "IntersectionUtilities.h" 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "LineParameters.h" 115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)static double interp_quad_coords(double a, double b, double c, double t) 135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles){ 145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double ab = interp(a, b, t); 155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double bc = interp(b, c, t); 165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return interp(ab, bc, t); 175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)static int coincident_line(const Quadratic& quad, Quadratic& reduction) { 205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[0] = reduction[1] = quad[0]; 215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return 1; 225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)static int vertical_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle, 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) Quadratic& reduction) { 265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double tValue; 275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[0] = quad[0]; 285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[1] = quad[2]; 295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (reduceStyle == kReduceOrder_TreatAsFill) { 305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return 2; 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int smaller = reduction[1].y > reduction[0].y; 335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int larger = smaller ^ 1; 345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue)) { 355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double yExtrema = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue); 365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (reduction[smaller].y > yExtrema) { 375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[smaller].y = yExtrema; 385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } else if (reduction[larger].y < yExtrema) { 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[larger].y = yExtrema; 405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return 2; 435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)static int horizontal_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle, 465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) Quadratic& reduction) { 475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double tValue; 485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[0] = quad[0]; 495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[1] = quad[2]; 505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (reduceStyle == kReduceOrder_TreatAsFill) { 515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return 2; 525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int smaller = reduction[1].x > reduction[0].x; 545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int larger = smaller ^ 1; 555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue)) { 565f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double xExtrema = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue); 575f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (reduction[smaller].x > xExtrema) { 585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[smaller].x = xExtrema; 595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } else if (reduction[larger].x < xExtrema) { 605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) reduction[larger].x = xExtrema; 615f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 635f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return 2; 645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 655f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 665f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)static int check_linear(const Quadratic& quad, ReduceOrder_Styles reduceStyle, 675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int minX, int maxX, int minY, int maxY, Quadratic& reduction) { 685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int startIndex = 0; 695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int endIndex = 2; 705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while (quad[startIndex].approximatelyEqual(quad[endIndex])) { 715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) --endIndex; 725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (endIndex == 0) { 735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) printf("%s shouldn't get here if all four points are about equal", __FUNCTION__); 745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) SkASSERT(0); 755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (!isLinear(quad, startIndex, endIndex)) { 785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return 0; 795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // four are colinear: return line formed by outside 81 reduction[0] = quad[0]; 82 reduction[1] = quad[2]; 83 if (reduceStyle == kReduceOrder_TreatAsFill) { 84 return 2; 85 } 86 int sameSide; 87 bool useX = quad[maxX].x - quad[minX].x >= quad[maxY].y - quad[minY].y; 88 if (useX) { 89 sameSide = sign(quad[0].x - quad[1].x) + sign(quad[2].x - quad[1].x); 90 } else { 91 sameSide = sign(quad[0].y - quad[1].y) + sign(quad[2].y - quad[1].y); 92 } 93 if ((sameSide & 3) != 2) { 94 return 2; 95 } 96 double tValue; 97 int root; 98 if (useX) { 99 root = findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue); 100 } else { 101 root = findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue); 102 } 103 if (root) { 104 _Point extrema; 105 extrema.x = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue); 106 extrema.y = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue); 107 // sameSide > 0 means mid is smaller than either [0] or [2], so replace smaller 108 int replace; 109 if (useX) { 110 if (extrema.x < quad[0].x ^ extrema.x < quad[2].x) { 111 return 2; 112 } 113 replace = (extrema.x < quad[0].x | extrema.x < quad[2].x) 114 ^ (quad[0].x < quad[2].x); 115 } else { 116 if (extrema.y < quad[0].y ^ extrema.y < quad[2].y) { 117 return 2; 118 } 119 replace = (extrema.y < quad[0].y | extrema.y < quad[2].y) 120 ^ (quad[0].y < quad[2].y); 121 } 122 reduction[replace] = extrema; 123 } 124 return 2; 125} 126 127bool isLinear(const Quadratic& quad, int startIndex, int endIndex) { 128 LineParameters lineParameters; 129 lineParameters.quadEndPoints(quad, startIndex, endIndex); 130 // FIXME: maybe it's possible to avoid this and compare non-normalized 131 lineParameters.normalize(); 132 double distance = lineParameters.controlPtDistance(quad); 133 return approximately_zero(distance); 134} 135 136// reduce to a quadratic or smaller 137// look for identical points 138// look for all four points in a line 139 // note that three points in a line doesn't simplify a cubic 140// look for approximation with single quadratic 141 // save approximation with multiple quadratics for later 142int reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles reduceStyle) { 143 int index, minX, maxX, minY, maxY; 144 int minXSet, minYSet; 145 minX = maxX = minY = maxY = 0; 146 minXSet = minYSet = 0; 147 for (index = 1; index < 3; ++index) { 148 if (quad[minX].x > quad[index].x) { 149 minX = index; 150 } 151 if (quad[minY].y > quad[index].y) { 152 minY = index; 153 } 154 if (quad[maxX].x < quad[index].x) { 155 maxX = index; 156 } 157 if (quad[maxY].y < quad[index].y) { 158 maxY = index; 159 } 160 } 161 for (index = 0; index < 3; ++index) { 162 if (AlmostEqualUlps(quad[index].x, quad[minX].x)) { 163 minXSet |= 1 << index; 164 } 165 if (AlmostEqualUlps(quad[index].y, quad[minY].y)) { 166 minYSet |= 1 << index; 167 } 168 } 169 if (minXSet == 0x7) { // test for vertical line 170 if (minYSet == 0x7) { // return 1 if all four are coincident 171 return coincident_line(quad, reduction); 172 } 173 return vertical_line(quad, reduceStyle, reduction); 174 } 175 if (minYSet == 0xF) { // test for horizontal line 176 return horizontal_line(quad, reduceStyle, reduction); 177 } 178 int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, reduction); 179 if (result) { 180 return result; 181 } 182 memcpy(reduction, quad, sizeof(Quadratic)); 183 return 3; 184} 185