OLD | NEW |
| (Empty) |
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/bezcli
p.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/bezcli
p.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 } | |
OLD | NEW |