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 
      8 #include "CubicUtilities.h"
      9 #include "CurveIntersection.h"
     10 #include "Intersections.h"
     11 #include "IntersectionUtilities.h"
     12 #include "LineIntersection.h"
     13 
     14 static const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf see Multiple intersections
     15 
     16 class CubicIntersections : public Intersections {
     17 public:
     18 
     19 CubicIntersections(const Cubic& c1, const Cubic& c2, Intersections& i)
     20     : cubic1(c1)
     21     , cubic2(c2)
     22     , intersections(i)
     23     , depth(0)
     24     , splits(0) {
     25 }
     26 
     27 bool intersect() {
     28     double minT1, minT2, maxT1, maxT2;
     29     if (!bezier_clip(cubic2, cubic1, minT1, maxT1)) {
     30         return false;
     31     }
     32     if (!bezier_clip(cubic1, cubic2, minT2, maxT2)) {
     33         return false;
     34     }
     35     int split;
     36     if (maxT1 - minT1 < maxT2 - minT2) {
     37         intersections.swap();
     38         minT2 = 0;
     39         maxT2 = 1;
     40         split = maxT1 - minT1 > tClipLimit;
     41     } else {
     42         minT1 = 0;
     43         maxT1 = 1;
     44         split = (maxT2 - minT2 > tClipLimit) << 1;
     45     }
     46     return chop(minT1, maxT1, minT2, maxT2, split);
     47 }
     48 
     49 protected:
     50 
     51 bool intersect(double minT1, double maxT1, double minT2, double maxT2) {
     52     Cubic smaller, larger;
     53     // FIXME: carry last subdivide and reduceOrder result with cubic
     54     sub_divide(cubic1, minT1, maxT1, intersections.swapped() ? larger : smaller);
     55     sub_divide(cubic2, minT2, maxT2, intersections.swapped() ? smaller : larger);
     56     Cubic smallResult;
     57     if (reduceOrder(smaller, smallResult, kReduceOrder_NoQuadraticsAllowed,
     58             kReduceOrder_TreatAsFill) <= 2) {
     59         Cubic largeResult;
     60         if (reduceOrder(larger, largeResult, kReduceOrder_NoQuadraticsAllowed,
     61                 kReduceOrder_TreatAsFill) <= 2) {
     62             const _Line& smallLine = (const _Line&) smallResult;
     63             const _Line& largeLine = (const _Line&) largeResult;
     64             Intersections lineTs;
     65             // FIXME: this doesn't detect or deal with coincident lines
     66             if (!::intersect(smallLine, largeLine, lineTs)) {
     67                 return false;
     68             }
     69             if (intersections.swapped()) {
     70                 lineTs.fT[0][0] = interp(minT2, maxT2, lineTs.fT[0][0]);
     71                 lineTs.fT[1][0] = interp(minT1, maxT1, lineTs.fT[1][0]);
     72             } else {
     73                 lineTs.fT[0][0] = interp(minT1, maxT1, lineTs.fT[0][0]);
     74                 lineTs.fT[1][0] = interp(minT2, maxT2, lineTs.fT[1][0]);
     75             }
     76             _Point pt;
     77             xy_at_t(cubic1, lineTs.fT[0][0], pt.x, pt.y);
     78             intersections.insert(lineTs.fT[0][0], lineTs.fT[1][0], pt);
     79             return true;
     80         }
     81     }
     82     double minT, maxT;
     83     if (!bezier_clip(smaller, larger, minT, maxT)) {
     84         if (minT == maxT) {
     85             if (intersections.swapped()) {
     86                 minT1 = (minT1 + maxT1) / 2;
     87                 minT2 = interp(minT2, maxT2, minT);
     88             } else {
     89                 minT1 = interp(minT1, maxT1, minT);
     90                 minT2 = (minT2 + maxT2) / 2;
     91             }
     92             _Point pt;
     93             xy_at_t(cubic1, minT1, pt.x, pt.y);
     94             intersections.insert(minT1, minT2, pt);
     95             return true;
     96         }
     97         return false;
     98     }
     99 
    100     int split;
    101     if (intersections.swapped()) {
    102         double newMinT1 = interp(minT1, maxT1, minT);
    103         double newMaxT1 = interp(minT1, maxT1, maxT);
    104         split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1;
    105 #define VERBOSE 0
    106 #if VERBOSE
    107         printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n",
    108                 __FUNCTION__, depth, splits, newMinT1, newMaxT1, minT1, maxT1,
    109                 split);
    110 #endif
    111         minT1 = newMinT1;
    112         maxT1 = newMaxT1;
    113     } else {
    114         double newMinT2 = interp(minT2, maxT2, minT);
    115         double newMaxT2 = interp(minT2, maxT2, maxT);
    116         split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit;
    117 #if VERBOSE
    118         printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n",
    119                 __FUNCTION__, depth, splits, newMinT2, newMaxT2, minT2, maxT2,
    120                 split);
    121 #endif
    122         minT2 = newMinT2;
    123         maxT2 = newMaxT2;
    124     }
    125     return chop(minT1, maxT1, minT2, maxT2, split);
    126 }
    127 
    128 bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) {
    129     ++depth;
    130     intersections.swap();
    131     if (split) {
    132         ++splits;
    133         if (split & 2) {
    134             double middle1 = (maxT1 + minT1) / 2;
    135             intersect(minT1, middle1, minT2, maxT2);
    136             intersect(middle1, maxT1, minT2, maxT2);
    137         } else {
    138             double middle2 = (maxT2 + minT2) / 2;
    139             intersect(minT1, maxT1, minT2, middle2);
    140             intersect(minT1, maxT1, middle2, maxT2);
    141         }
    142         --splits;
    143         intersections.swap();
    144         --depth;
    145         return intersections.intersected();
    146     }
    147     bool result = intersect(minT1, maxT1, minT2, maxT2);
    148     intersections.swap();
    149     --depth;
    150     return result;
    151 }
    152 
    153 private:
    154 
    155 const Cubic& cubic1;
    156 const Cubic& cubic2;
    157 Intersections& intersections;
    158 int depth;
    159 int splits;
    160 };
    161 
    162 bool intersect(const Cubic& c1, const Cubic& c2, Intersections& i) {
    163     CubicIntersections c(c1, c2, i);
    164     return c.intersect();
    165 }
    166