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 #define DEBUG_BEZIER_CLIP 1
     12 
     13 // return false if unable to clip (e.g., unable to create implicit line)
     14 // caller should subdivide, or create degenerate if the values are too small
     15 bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT) {
     16     minT = 1;
     17     maxT = 0;
     18     // determine normalized implicit line equation for pt[0] to pt[3]
     19     //   of the form ax + by + c = 0, where a*a + b*b == 1
     20 
     21     // find the implicit line equation parameters
     22     LineParameters endLine;
     23     endLine.quadEndPoints(q1);
     24     if (!endLine.normalize()) {
     25         printf("line cannot be normalized: need more code here\n");
     26         SkASSERT(0);
     27         return false;
     28     }
     29 
     30     double distance = endLine.controlPtDistance(q1);
     31 
     32     // find fat line
     33     double top = 0;
     34     double bottom = distance / 2; // http://students.cs.byu.edu/~tom/557/text/cic.pdf (7.6)
     35     if (top > bottom) {
     36         SkTSwap(top, bottom);
     37     }
     38 
     39     // compute intersecting candidate distance
     40     Quadratic distance2y; // points with X of (0, 1/2, 1)
     41     endLine.quadDistanceY(q2, distance2y);
     42 
     43     int flags = 0;
     44     if (approximately_lesser_or_equal(distance2y[0].y, top)) {
     45         flags |= kFindTopMin;
     46     } else if (approximately_greater_or_equal(distance2y[0].y, bottom)) {
     47         flags |= kFindBottomMin;
     48     } else {
     49         minT = 0;
     50     }
     51 
     52     if (approximately_lesser_or_equal(distance2y[2].y, top)) {
     53         flags |= kFindTopMax;
     54     } else if (approximately_greater_or_equal(distance2y[2].y, bottom)) {
     55         flags |= kFindBottomMax;
     56     } else {
     57         maxT = 1;
     58     }
     59     // Find the intersection of distance convex hull and fat line.
     60     int idx = 0;
     61     do {
     62         int next = idx + 1;
     63         if (next == 3) {
     64             next = 0;
     65         }
     66         x_at(distance2y[idx], distance2y[next], top, bottom, flags, minT, maxT);
     67         idx = next;
     68     } while (idx);
     69 #if DEBUG_BEZIER_CLIP
     70     _Rect r1, r2;
     71     r1.setBounds(q1);
     72     r2.setBounds(q2);
     73     _Point testPt = {0.487, 0.337};
     74     if (r1.contains(testPt) && r2.contains(testPt)) {
     75         printf("%s q1=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
     76                 " q2=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) minT=%1.9g maxT=%1.9g\n",
     77                 __FUNCTION__, q1[0].x, q1[0].y, q1[1].x, q1[1].y, q1[2].x, q1[2].y,
     78                 q2[0].x, q2[0].y, q2[1].x, q2[1].y, q2[2].x, q2[2].y, minT, maxT);
     79     }
     80 #endif
     81     return minT < maxT; // returns false if distance shows no intersection
     82 }
     83