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 "LineParameters.h" 10639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// return false if unable to clip (e.g., unable to create implicit line) 12639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// caller should subdivide, or create degenerate if the values are too small 13639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.combool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT) { 14639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minT = 1; 15639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxT = 0; 16639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // determine normalized implicit line equation for pt[0] to pt[3] 17639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // of the form ax + by + c = 0, where a*a + b*b == 1 18d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 19639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // find the implicit line equation parameters 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com LineParameters endLine; 21639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com endLine.cubicEndPoints(cubic1); 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!endLine.normalize()) { 23639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com printf("line cannot be normalized: need more code here\n"); 24639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return false; 25639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 26639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 27639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double distance[2]; 2873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com distance[0] = endLine.controlPtDistance(cubic1, 1); 2973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com distance[1] = endLine.controlPtDistance(cubic1, 2); 30d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 31639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // find fat line 32639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double top = distance[0]; 33639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bottom = distance[1]; 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (top > bottom) { 35aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(top, bottom); 36639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 37639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (top * bottom >= 0) { 38639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com const double scale = 3/4.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (13) 39639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (top < 0) { 40639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com top *= scale; 41639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com bottom = 0; 42639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 43639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com top = 0; 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com bottom *= scale; 45639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 46639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 47639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com const double scale = 4/9.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (15) 48639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com top *= scale; 49639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com bottom *= scale; 50639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 51d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 52639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // compute intersecting candidate distance 53639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Cubic distance2y; // points with X of (0, 1/3, 2/3, 1) 54639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com endLine.cubicDistanceY(cubic2, distance2y); 55d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 56639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int flags = 0; 575e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (approximately_lesser_or_equal(distance2y[0].y, top)) { 58639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com flags |= kFindTopMin; 595e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } else if (approximately_greater_or_equal(distance2y[0].y, bottom)) { 60639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com flags |= kFindBottomMin; 61639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 62639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minT = 0; 63639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 64639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 655e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (approximately_lesser_or_equal(distance2y[3].y, top)) { 66639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com flags |= kFindTopMax; 675e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } else if (approximately_greater_or_equal(distance2y[3].y, bottom)) { 68639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com flags |= kFindBottomMax; 69639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 70639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxT = 1; 71639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 72639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // Find the intersection of distance convex hull and fat line. 73639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com char to_0[2]; 74639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com char to_3[2]; 75639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com bool do_1_2_edge = convex_x_hull(distance2y, to_0, to_3); 76639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com x_at(distance2y[0], distance2y[to_0[0]], top, bottom, flags, minT, maxT); 77639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (to_0[0] != to_0[1]) { 78639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com x_at(distance2y[0], distance2y[to_0[1]], top, bottom, flags, minT, maxT); 79639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 80639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com x_at(distance2y[to_3[0]], distance2y[3], top, bottom, flags, minT, maxT); 81639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (to_3[0] != to_3[1]) { 82639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com x_at(distance2y[to_3[1]], distance2y[3], top, bottom, flags, minT, maxT); 83639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 84639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (do_1_2_edge) { 85639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com x_at(distance2y[1], distance2y[2], top, bottom, flags, minT, maxT); 86639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 87d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 88639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return minT < maxT; // returns false if distance shows no intersection 89639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 90