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#define DEBUG_BEZIER_CLIP 1 12 13// return false if unable to clip (e.g., unable to create implicit line) 14// caller should subdivide, or create degenerate if the values are too small 15bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT) { 16 minT = 1; 17 maxT = 0; 18 // determine normalized implicit line equation for pt[0] to pt[3] 19 // of the form ax + by + c = 0, where a*a + b*b == 1 20 21 // find the implicit line equation parameters 22 LineParameters endLine; 23 endLine.quadEndPoints(q1); 24 if (!endLine.normalize()) { 25 printf("line cannot be normalized: need more code here\n"); 26 SkASSERT(0); 27 return false; 28 } 29 30 double distance = endLine.controlPtDistance(q1); 31 32 // find fat line 33 double top = 0; 34 double bottom = distance / 2; // http://students.cs.byu.edu/~tom/557/text/cic.pdf (7.6) 35 if (top > bottom) { 36 SkTSwap(top, bottom); 37 } 38 39 // compute intersecting candidate distance 40 Quadratic distance2y; // points with X of (0, 1/2, 1) 41 endLine.quadDistanceY(q2, distance2y); 42 43 int flags = 0; 44 if (approximately_lesser_or_equal(distance2y[0].y, top)) { 45 flags |= kFindTopMin; 46 } else if (approximately_greater_or_equal(distance2y[0].y, bottom)) { 47 flags |= kFindBottomMin; 48 } else { 49 minT = 0; 50 } 51 52 if (approximately_lesser_or_equal(distance2y[2].y, top)) { 53 flags |= kFindTopMax; 54 } else if (approximately_greater_or_equal(distance2y[2].y, bottom)) { 55 flags |= kFindBottomMax; 56 } else { 57 maxT = 1; 58 } 59 // Find the intersection of distance convex hull and fat line. 60 int idx = 0; 61 do { 62 int next = idx + 1; 63 if (next == 3) { 64 next = 0; 65 } 66 x_at(distance2y[idx], distance2y[next], top, bottom, flags, minT, maxT); 67 idx = next; 68 } while (idx); 69#if DEBUG_BEZIER_CLIP 70 _Rect r1, r2; 71 r1.setBounds(q1); 72 r2.setBounds(q2); 73 _Point testPt = {0.487, 0.337}; 74 if (r1.contains(testPt) && r2.contains(testPt)) { 75 printf("%s q1=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 76 " q2=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) minT=%1.9g maxT=%1.9g\n", 77 __FUNCTION__, q1[0].x, q1[0].y, q1[1].x, q1[1].y, q1[2].x, q1[2].y, 78 q2[0].x, q2[0].y, q2[1].x, q2[1].y, q2[2].x, q2[2].y, minT, maxT); 79 } 80#endif 81 return minT < maxT; // returns false if distance shows no intersection 82} 83