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 */ 79d5f99bc309a7d733e33a149bef295ae3c8b3ac1caryclark@google.com#include "CubicUtilities.h" 8639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "IntersectionUtilities.h" 9639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 10639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Given a cubic c, t1, and t2, find a small cubic segment. 12d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 13639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com The new cubic is defined as points A, B, C, and D, where 14639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com s1 = 1 - t1 15639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com s2 = 1 - t2 16639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com A = c[0]*s1*s1*s1 + 3*c[1]*s1*s1*t1 + 3*c[2]*s1*t1*t1 + c[3]*t1*t1*t1 17639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com D = c[0]*s2*s2*s2 + 3*c[1]*s2*s2*t2 + 3*c[2]*s2*t2*t2 + c[3]*t2*t2*t2 18d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 19639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com We don't have B or C. So We define two equations to isolate them. 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com First, compute two reference T values 1/3 and 2/3 from t1 to t2: 21d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com c(at (2*t1 + t2)/3) == E 23639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com c(at (t1 + 2*t2)/3) == F 24d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 25639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Next, compute where those values must be if we know the values of B and C: 26d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 27639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com _12 = A*2/3 + B*1/3 28639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 12_ = A*1/3 + B*2/3 29639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com _23 = B*2/3 + C*1/3 30639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 23_ = B*1/3 + C*2/3 31639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com _34 = C*2/3 + D*1/3 32639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 34_ = C*1/3 + D*2/3 33639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com _123 = (A*2/3 + B*1/3)*2/3 + (B*2/3 + C*1/3)*1/3 = A*4/9 + B*4/9 + C*1/9 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 123_ = (A*1/3 + B*2/3)*1/3 + (B*1/3 + C*2/3)*2/3 = A*1/9 + B*4/9 + C*4/9 35639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com _234 = (B*2/3 + C*1/3)*2/3 + (C*2/3 + D*1/3)*1/3 = B*4/9 + C*4/9 + D*1/9 36639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 234_ = (B*1/3 + C*2/3)*1/3 + (C*1/3 + D*2/3)*2/3 = B*1/9 + C*4/9 + D*4/9 37639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com _1234 = (A*4/9 + B*4/9 + C*1/9)*2/3 + (B*4/9 + C*4/9 + D*1/9)*1/3 38639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com = A*8/27 + B*12/27 + C*6/27 + D*1/27 39639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com = E 40639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 1234_ = (A*1/9 + B*4/9 + C*4/9)*1/3 + (B*1/9 + C*4/9 + D*4/9)*2/3 41639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com = A*1/27 + B*6/27 + C*12/27 + D*8/27 42639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com = F 43639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com E*27 = A*8 + B*12 + C*6 + D 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com F*27 = A + B*6 + C*12 + D*8 45d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 46639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comGroup the known values on one side: 47d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 48639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com M = E*27 - A*8 - D = B*12 + C* 6 49639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com N = F*27 - A - D*8 = B* 6 + C*12 50639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com M*2 - N = B*18 51639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com N*2 - M = C*18 52639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com B = (M*2 - N)/18 53639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com C = (N*2 - M)/18 54639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com */ 55d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 56639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comstatic double interp_cubic_coords(const double* src, double t) 57639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com{ 58639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ab = interp(src[0], src[2], t); 59639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bc = interp(src[2], src[4], t); 60639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double cd = interp(src[4], src[6], t); 61639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double abc = interp(ab, bc, t); 62639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bcd = interp(bc, cd, t); 63639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double abcd = interp(abc, bcd, t); 64639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return abcd; 65639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 66d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 67639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comvoid sub_divide(const Cubic& src, double t1, double t2, Cubic& dst) { 681304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com if (t1 == 0 && t2 == 1) { 691304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com dst[0] = src[0]; 701304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com dst[1] = src[1]; 711304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com dst[2] = src[2]; 721304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com dst[3] = src[3]; 7303682beb8c1c5dfe714933e9419e1412b33c932dskia.committer@gmail.com return; 741304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com } 75639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ax = dst[0].x = interp_cubic_coords(&src[0].x, t1); 76639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ay = dst[0].y = interp_cubic_coords(&src[0].y, t1); 77639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ex = interp_cubic_coords(&src[0].x, (t1*2+t2)/3); 78639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ey = interp_cubic_coords(&src[0].y, (t1*2+t2)/3); 79639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double fx = interp_cubic_coords(&src[0].x, (t1+t2*2)/3); 80639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double fy = interp_cubic_coords(&src[0].y, (t1+t2*2)/3); 81639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dx = dst[3].x = interp_cubic_coords(&src[0].x, t2); 82639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double dy = dst[3].y = interp_cubic_coords(&src[0].y, t2); 83639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double mx = ex * 27 - ax * 8 - dx; 84639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double my = ey * 27 - ay * 8 - dy; 85639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double nx = fx * 27 - ax - dx * 8; 86639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ny = fy * 27 - ay - dy * 8; 87639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com /* bx = */ dst[1].x = (mx * 2 - nx) / 18; 88639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com /* by = */ dst[1].y = (my * 2 - ny) / 18; 89639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com /* cx = */ dst[2].x = (nx * 2 - mx) / 18; 90639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com /* cy = */ dst[2].y = (ny * 2 - my) / 18; 91639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 92639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 93c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.comvoid sub_divide(const Cubic& src, const _Point& a, const _Point& d, 94c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double t1, double t2, _Point dst[2]) { 95c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double ex = interp_cubic_coords(&src[0].x, (t1 * 2 + t2) / 3); 96c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double ey = interp_cubic_coords(&src[0].y, (t1 * 2 + t2) / 3); 97c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double fx = interp_cubic_coords(&src[0].x, (t1 + t2 * 2) / 3); 98c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double fy = interp_cubic_coords(&src[0].y, (t1 + t2 * 2) / 3); 99c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double mx = ex * 27 - a.x * 8 - d.x; 100c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double my = ey * 27 - a.y * 8 - d.y; 101c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double nx = fx * 27 - a.x - d.x * 8; 102c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com double ny = fy * 27 - a.y - d.y * 8; 103c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com /* bx = */ dst[0].x = (mx * 2 - nx) / 18; 104c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com /* by = */ dst[0].y = (my * 2 - ny) / 18; 105c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com /* cx = */ dst[1].x = (nx * 2 - mx) / 18; 106c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com /* cy = */ dst[1].y = (ny * 2 - my) / 18; 107c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com} 108c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com 109639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* classic one t subdivision */ 110639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comstatic void interp_cubic_coords(const double* src, double* dst, double t) 111639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com{ 112639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ab = interp(src[0], src[2], t); 113639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bc = interp(src[2], src[4], t); 114639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double cd = interp(src[4], src[6], t); 115639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double abc = interp(ab, bc, t); 116639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bcd = interp(bc, cd, t); 117639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double abcd = interp(abc, bcd, t); 118639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 119639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[0] = src[0]; 120639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[2] = ab; 121639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[4] = abc; 122639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[6] = abcd; 123639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[8] = bcd; 124639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[10] = cd; 125639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com dst[12] = src[6]; 126639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 127639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 128639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comvoid chop_at(const Cubic& src, CubicPair& dst, double t) 129639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com{ 1306d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (t == 0.5) { 1316d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[0] = src[0]; 1326d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[1].x = (src[0].x + src[1].x) / 2; 1336d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[1].y = (src[0].y + src[1].y) / 2; 1346d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[2].x = (src[0].x + 2 * src[1].x + src[2].x) / 4; 1356d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[2].y = (src[0].y + 2 * src[1].y + src[2].y) / 4; 1366d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[3].x = (src[0].x + 3 * (src[1].x + src[2].x) + src[3].x) / 8; 1376d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[3].y = (src[0].y + 3 * (src[1].y + src[2].y) + src[3].y) / 8; 1386d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[4].x = (src[1].x + 2 * src[2].x + src[3].x) / 4; 1396d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[4].y = (src[1].y + 2 * src[2].y + src[3].y) / 4; 1406d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[5].x = (src[2].x + src[3].x) / 2; 1416d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[5].y = (src[2].y + src[3].y) / 2; 1426d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com dst.pts[6] = src[3]; 1436d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com return; 1446d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com } 145639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com interp_cubic_coords(&src[0].x, &dst.pts[0].x, t); 146639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com interp_cubic_coords(&src[0].y, &dst.pts[0].y, t); 147639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 148