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
bezier_clip(const Quadratic & q1,const Quadratic & q2,double & minT,double & maxT)15 bool 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