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
bezier_clip(const Cubic & cubic1,const Cubic & cubic2,double & minT,double & maxT)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