1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "CurveIntersection.h" 8 #include "CurveUtilities.h" 9 #include "LineParameters.h" 10 11 // return false if unable to clip (e.g., unable to create implicit line) 12 // caller should subdivide, or create degenerate if the values are too small 13 bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT) { 14 minT = 1; 15 maxT = 0; 16 // determine normalized implicit line equation for pt[0] to pt[3] 17 // of the form ax + by + c = 0, where a*a + b*b == 1 18 19 // find the implicit line equation parameters 20 LineParameters endLine; 21 endLine.cubicEndPoints(cubic1); 22 if (!endLine.normalize()) { 23 printf("line cannot be normalized: need more code here\n"); 24 return false; 25 } 26 27 double distance[2]; 28 distance[0] = endLine.controlPtDistance(cubic1, 1); 29 distance[1] = endLine.controlPtDistance(cubic1, 2); 30 31 // find fat line 32 double top = distance[0]; 33 double bottom = distance[1]; 34 if (top > bottom) { 35 SkTSwap(top, bottom); 36 } 37 if (top * bottom >= 0) { 38 const double scale = 3/4.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (13) 39 if (top < 0) { 40 top *= scale; 41 bottom = 0; 42 } else { 43 top = 0; 44 bottom *= scale; 45 } 46 } else { 47 const double scale = 4/9.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (15) 48 top *= scale; 49 bottom *= scale; 50 } 51 52 // compute intersecting candidate distance 53 Cubic distance2y; // points with X of (0, 1/3, 2/3, 1) 54 endLine.cubicDistanceY(cubic2, distance2y); 55 56 int flags = 0; 57 if (approximately_lesser_or_equal(distance2y[0].y, top)) { 58 flags |= kFindTopMin; 59 } else if (approximately_greater_or_equal(distance2y[0].y, bottom)) { 60 flags |= kFindBottomMin; 61 } else { 62 minT = 0; 63 } 64 65 if (approximately_lesser_or_equal(distance2y[3].y, top)) { 66 flags |= kFindTopMax; 67 } else if (approximately_greater_or_equal(distance2y[3].y, bottom)) { 68 flags |= kFindBottomMax; 69 } else { 70 maxT = 1; 71 } 72 // Find the intersection of distance convex hull and fat line. 73 char to_0[2]; 74 char to_3[2]; 75 bool do_1_2_edge = convex_x_hull(distance2y, to_0, to_3); 76 x_at(distance2y[0], distance2y[to_0[0]], top, bottom, flags, minT, maxT); 77 if (to_0[0] != to_0[1]) { 78 x_at(distance2y[0], distance2y[to_0[1]], top, bottom, flags, minT, maxT); 79 } 80 x_at(distance2y[to_3[0]], distance2y[3], top, bottom, flags, minT, maxT); 81 if (to_3[0] != to_3[1]) { 82 x_at(distance2y[to_3[1]], distance2y[3], top, bottom, flags, minT, maxT); 83 } 84 if (do_1_2_edge) { 85 x_at(distance2y[1], distance2y[2], top, bottom, flags, minT, maxT); 86 } 87 88 return minT < maxT; // returns false if distance shows no intersection 89 } 90