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 */ 7a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com#include "CurveIntersection.h" 88dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#include "CurveUtilities.h" 9fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#include "Extrema.h" 10c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 11fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int isBoundedByEndPoints(double a, double b, double c, double d) 12fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com{ 1345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return between(a, b, d) && between(a, c, d); 14fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 15c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 16fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comdouble leftMostT(const Cubic& cubic, double startT, double endT) { 17fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double leftTs[2]; 18fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com _Point pt[2]; 1945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com int results = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, leftTs); 20fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com int best = -1; 21fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com for (int index = 0; index < results; ++index) { 22fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (startT > leftTs[index] || leftTs[index] > endT) { 23fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com continue; 24fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 25fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (best < 0) { 26fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com best = index; 27fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com continue; 28fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 29fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com xy_at_t(cubic, leftTs[0], pt[0].x, pt[0].y); 30fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com xy_at_t(cubic, leftTs[1], pt[1].x, pt[1].y); 31fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (pt[0].x > pt[1].x) { 32fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com best = 1; 33fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 34fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 35fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (best >= 0) { 36fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return leftTs[best]; 37fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 38fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com xy_at_t(cubic, startT, pt[0].x, pt[0].y); 39fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com xy_at_t(cubic, endT, pt[1].x, pt[1].y); 40fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return pt[0].x <= pt[1].x ? startT : endT; 41fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 42fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 43fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comvoid _Rect::setBounds(const Cubic& cubic) { 44fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com set(cubic[0]); 45fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com add(cubic[3]); 46fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double tValues[4]; 47fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com int roots = 0; 48fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (!isBoundedByEndPoints(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x)) { 4945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues); 50fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 51fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (!isBoundedByEndPoints(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y)) { 5245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com roots += findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, &tValues[roots]); 53fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 54fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com for (int x = 0; x < roots; ++x) { 55fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com _Point result; 56fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com xy_at_t(cubic, tValues[x], result.x, result.y); 57fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com add(result); 58fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 59fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 60fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 61fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comvoid _Rect::setRawBounds(const Cubic& cubic) { 62fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com set(cubic[0]); 63fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com for (int x = 1; x < 4; ++x) { 64fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com add(cubic[x]); 65fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 66fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 67