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
13bool 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