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 "IntersectionUtilities.h" 99d5f99bc309a7d733e33a149bef295ae3c8b3ac1caryclark@google.com#include "QuadraticUtilities.h" 10639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* 12639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comGiven a quadratic q, t1, and t2, find a small quadratic segment. 13639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 14639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comThe new quadratic is defined by A, B, and C, where 15639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1 16639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1 17639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 18639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comTo find B, compute the point halfway between t1 and t2: 19639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comq(at (t1 + t2)/2) == D 21639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comNext, compute where D must be if we know the value of B: 23639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 24639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com_12 = A/2 + B/2 25639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com12_ = B/2 + C/2 26639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com123 = A/4 + B/2 + C/4 27639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com = D 28d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 29639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comGroup the known values on one side: 30639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 31639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comB = D*2 - A/2 - C/2 32639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com*/ 33639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comstatic double interp_quad_coords(const double* src, double t) 35639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com{ 36639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ab = interp(src[0], src[2], t); 37639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bc = interp(src[2], src[4], t); 38639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double abc = interp(ab, bc, t); 39639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return abc; 40639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 41639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 42639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comvoid sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst) { 43639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ax = dst[0].x = interp_quad_coords(&src[0].x, t1); 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ay = dst[0].y = interp_quad_coords(&src[0].y, t1); 45639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dx = interp_quad_coords(&src[0].x, (t1 + t2) / 2); 46639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dy = interp_quad_coords(&src[0].y, (t1 + t2) / 2); 47639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double cx = dst[2].x = interp_quad_coords(&src[0].x, t2); 48639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double cy = dst[2].y = interp_quad_coords(&src[0].y, t2); 49639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com /* bx = */ dst[1].x = 2*dx - (ax + cx)/2; 50639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com /* by = */ dst[1].y = 2*dy - (ay + cy)/2; 51639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 52639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 53c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com_Point sub_divide(const Quadratic& src, const _Point& a, const _Point& c, double t1, double t2) { 54c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com _Point b; 55c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double dx = interp_quad_coords(&src[0].x, (t1 + t2) / 2); 56c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double dy = interp_quad_coords(&src[0].y, (t1 + t2) / 2); 57c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com b.x = 2 * dx - (a.x + c.x) / 2; 58c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com b.y = 2 * dy - (a.y + c.y) / 2; 59c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com return b; 60c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com} 61c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com 62639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* classic one t subdivision */ 63639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comstatic void interp_quad_coords(const double* src, double* dst, double t) 64639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com{ 65639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ab = interp(src[0], src[2], t); 66639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bc = interp(src[2], src[4], t); 67639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 68639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[0] = src[0]; 69639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[2] = ab; 70639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[4] = interp(ab, bc, t); 71639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[6] = bc; 72639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[8] = src[4]; 73639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 74639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 75639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comvoid chop_at(const Quadratic& src, QuadraticPair& dst, double t) 76639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com{ 77639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com interp_quad_coords(&src[0].x, &dst.pts[0].x, t); 78639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com interp_quad_coords(&src[0].y, &dst.pts[0].y, t); 79639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 80