Home | History | Annotate | Download | only in Intersection 
      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/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