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" 88dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#include "CurveUtilities.h" 9639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "IntersectionUtilities.h" 10639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* Given a cubic, find the convex hull described by the end and control points. 12639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com The hull may have 3 or 4 points. Cubics that degenerate into a point or line 13639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com are not considered. 14d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 15639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com The hull is computed by assuming that three points, if unique and non-linear, 16639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com form a triangle. The fourth point may replace one of the first three, may be 17639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com discarded if in the triangle or on an edge, or may be inserted between any of 18639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com the three to form a convex quadralateral. 19d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com The indices returned in order describe the convex hull. 21639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com*/ 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comint convex_hull(const Cubic& cubic, char order[4]) { 23639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com size_t index; 24639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // find top point 25639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com size_t yMin = 0; 26639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 1; index < 4; ++index) { 27639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (cubic[yMin].y > cubic[index].y || (cubic[yMin].y == cubic[index].y 28639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com && cubic[yMin].x > cubic[index].x)) { 29639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com yMin = index; 30639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 31639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 32639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[0] = yMin; 33639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int midX = -1; 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int backupYMin = -1; 35639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (int pass = 0; pass < 2; ++pass) { 36639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 0; index < 4; ++index) { 37639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (index == yMin) { 38639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com continue; 39639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 40639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // rotate line from (yMin, index) to axis 41639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // see if remaining two points are both above or below 42639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // use this to find mid 43639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int mask = other_two(yMin, index); 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int side1 = yMin ^ mask; 45639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int side2 = index ^ mask; 46639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Cubic rotPath; 47639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!rotate(cubic, yMin, index, rotPath)) { // ! if cbc[yMin]==cbc[idx] 48639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[1] = side1; 49639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[2] = side2; 50639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 3; 51639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 52639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int sides = side(rotPath[side1].y - rotPath[yMin].y); 53639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sides ^= side(rotPath[side2].y - rotPath[yMin].y); 54639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (sides == 2) { // '2' means one remaining point <0, one >0 55639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (midX >= 0) { 56639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com printf("%s unexpected mid\n", __FUNCTION__); // there can be only one mid 57639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 58639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com midX = index; 59639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else if (sides == 0) { // '0' means both to one side or the other 60639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com backupYMin = index; 61639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 62639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 63639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (midX >= 0) { 64639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com break; 65639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 66639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (backupYMin < 0) { 67639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com break; 68639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 69639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com yMin = backupYMin; 70639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com backupYMin = -1; 71639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 72639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (midX < 0) { 73639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com midX = yMin ^ 3; // choose any other point 74639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 75639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int mask = other_two(yMin, midX); 76639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int least = yMin ^ mask; 77639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int most = midX ^ mask; 78639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[0] = yMin; 79639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[1] = least; 80d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 81639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // see if mid value is on same side of line (least, most) as yMin 82639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Cubic midPath; 83639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!rotate(cubic, least, most, midPath)) { // ! if cbc[least]==cbc[most] 84639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[2] = midX; 85639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 3; 86639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 87639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int midSides = side(midPath[yMin].y - midPath[least].y); 88639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com midSides ^= side(midPath[midX].y - midPath[least].y); 89d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com if (midSides != 2) { // if mid point is not between 90639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[2] = most; 91639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 3; // result is a triangle 92639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 93639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[2] = midX; 94639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com order[3] = most; 95639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return 4; // result is a quadralateral 96639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 97639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 98639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* Find the convex hull for cubics with the x-axis interval regularly spaced. 99639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Cubics computed as distance functions are formed this way. 100d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 101639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com connectTo0[0], connectTo0[1] are the point indices that cubic[0] connects to. 102639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com connectTo3[0], connectTo3[1] are the point indices that cubic[3] connects to. 103d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 104639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Returns true if cubic[1] to cubic[2] also forms part of the hull. 105639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com*/ 106639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.combool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]) { 107639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double projectedY[4]; 108639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com projectedY[0] = 0; 109639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int index; 110639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 1; index < 4; ++index) { 111639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com projectedY[index] = (cubic[index].y - cubic[0].y) * (3.0 / index); 112639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 113639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int lower0Index = 1; 114639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int upper0Index = 1; 115639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 2; index < 4; ++index) { 1165e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (approximately_greater_or_equal(projectedY[lower0Index], projectedY[index])) { 117639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com lower0Index = index; 118639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 1195e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (approximately_lesser_or_equal(projectedY[upper0Index], projectedY[index])) { 120639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com upper0Index = index; 121639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 122639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 123639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com connectTo0[0] = lower0Index; 124639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com connectTo0[1] = upper0Index; 125639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 0; index < 3; ++index) { 126639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com projectedY[index] = (cubic[3].y - cubic[index].y) * (3.0 / (3 - index)); 127639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 128639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com projectedY[3] = 0; 129639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int lower3Index = 2; 130639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int upper3Index = 2; 131639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (index = 1; index > -1; --index) { 1325e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (approximately_greater_or_equal(projectedY[lower3Index], projectedY[index])) { 133639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com lower3Index = index; 134639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 1355e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (approximately_lesser_or_equal(projectedY[upper3Index], projectedY[index])) { 136639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com upper3Index = index; 137639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 138639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 139639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com connectTo3[0] = lower3Index; 140639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com connectTo3[1] = upper3Index; 141639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return (1 << lower0Index | 1 << upper0Index 142639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com | 1 << lower3Index | 1 << upper3Index) == 0x0F; 143639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 144