blob: e27db7c7eb3bd9e8dd8fb121bfad4fd4b4152f5d [file] [log] [blame]
caryclark@google.comc6825902012-02-03 22:07:47 +00001#include "CurveIntersection.h"
caryclark@google.com8dcf1142012-07-02 20:27:02 +00002#include "CurveUtilities.h"
caryclark@google.com639df892012-01-10 21:46:10 +00003#include "LineParameters.h"
4#include <algorithm> // used for std::swap
5
6// return false if unable to clip (e.g., unable to create implicit line)
7// caller should subdivide, or create degenerate if the values are too small
8bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT) {
9 minT = 1;
10 maxT = 0;
11 // determine normalized implicit line equation for pt[0] to pt[3]
12 // of the form ax + by + c = 0, where a*a + b*b == 1
13
14 // find the implicit line equation parameters
15 LineParameters endLine;
16 endLine.quadEndPoints(q1);
17 if (!endLine.normalize()) {
18 printf("line cannot be normalized: need more code here\n");
19 return false;
20 }
21
22 double distance = endLine.controlPtDistance(q1);
23
24 // find fat line
25 double top = 0;
26 double bottom = distance / 2; // http://students.cs.byu.edu/~tom/557/text/cic.pdf (7.6)
27 if (top > bottom) {
28 std::swap(top, bottom);
29 }
30
31 // compute intersecting candidate distance
32 Quadratic distance2y; // points with X of (0, 1/2, 1)
33 endLine.quadDistanceY(q2, distance2y);
34
35 int flags = 0;
36 if (approximately_lesser(distance2y[0].y, top)) {
37 flags |= kFindTopMin;
38 } else if (approximately_greater(distance2y[0].y, bottom)) {
39 flags |= kFindBottomMin;
40 } else {
41 minT = 0;
42 }
43
44 if (approximately_lesser(distance2y[2].y, top)) {
45 flags |= kFindTopMax;
46 } else if (approximately_greater(distance2y[2].y, bottom)) {
47 flags |= kFindBottomMax;
48 } else {
49 maxT = 1;
50 }
51 // Find the intersection of distance convex hull and fat line.
caryclark@google.com27accef2012-01-25 18:57:23 +000052 int idx = 0;
53 do {
54 int next = idx + 1;
55 if (next == 3) {
56 next = 0;
57 }
58 x_at(distance2y[idx], distance2y[next], top, bottom, flags, minT, maxT);
59 idx = next;
60 } while (idx);
caryclark@google.com639df892012-01-10 21:46:10 +000061 return minT < maxT; // returns false if distance shows no intersection
62}