Home | History | Annotate | Download | only in pathops 
      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 #ifndef SkIntersections_DEFINE
      8 #define SkIntersections_DEFINE
      9 
     10 #include "SkPathOpsConic.h"
     11 #include "SkPathOpsCubic.h"
     12 #include "SkPathOpsLine.h"
     13 #include "SkPathOpsPoint.h"
     14 #include "SkPathOpsQuad.h"
     15 
     16 class SkIntersections {
     17 public:
     18     SkIntersections()
     19         : fSwap(0)
     20 #ifdef SK_DEBUG
     21         , fDepth(0)
     22 #endif
     23     {
     24         sk_bzero(fPt, sizeof(fPt));
     25         sk_bzero(fPt2, sizeof(fPt2));
     26         sk_bzero(fT, sizeof(fT));
     27         sk_bzero(fNearlySame, sizeof(fNearlySame));
     28         reset();
     29         fMax = 0;  // require that the caller set the max
     30     }
     31 
     32     class TArray {
     33     public:
     34         explicit TArray(const double ts[10]) : fTArray(ts) {}
     35         double operator[](int n) const {
     36             return fTArray[n];
     37         }
     38         const double* fTArray;
     39     };
     40     TArray operator[](int n) const { return TArray(fT[n]); }
     41 
     42     void allowNear(bool nearAllowed) {
     43         fAllowNear = nearAllowed;
     44     }
     45 
     46     void clearCoincidence(int index) {
     47         SkASSERT(index >= 0);
     48         int bit = 1 << index;
     49         fIsCoincident[0] &= ~bit;
     50         fIsCoincident[1] &= ~bit;
     51     }
     52 
     53     int conicHorizontal(const SkPoint a[3], SkScalar weight, SkScalar left, SkScalar right,
     54                 SkScalar y, bool flipped) {
     55         SkDConic conic;
     56         conic.set(a, weight);
     57         fMax = 2;
     58         return horizontal(conic, left, right, y, flipped);
     59     }
     60 
     61     int conicVertical(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom,
     62             SkScalar x, bool flipped) {
     63         SkDConic conic;
     64         conic.set(a, weight);
     65         fMax = 2;
     66         return vertical(conic, top, bottom, x, flipped);
     67     }
     68 
     69     int conicLine(const SkPoint a[3], SkScalar weight, const SkPoint b[2]) {
     70         SkDConic conic;
     71         conic.set(a, weight);
     72         SkDLine line;
     73         line.set(b);
     74         fMax = 3; // 2;  permit small coincident segment + non-coincident intersection
     75         return intersect(conic, line);
     76     }
     77 
     78     int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y,
     79                         bool flipped) {
     80         SkDCubic cubic;
     81         cubic.set(a);
     82         fMax = 3;
     83         return horizontal(cubic, left, right, y, flipped);
     84     }
     85 
     86     int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
     87         SkDCubic cubic;
     88         cubic.set(a);
     89         fMax = 3;
     90         return vertical(cubic, top, bottom, x, flipped);
     91     }
     92 
     93     int cubicLine(const SkPoint a[4], const SkPoint b[2]) {
     94         SkDCubic cubic;
     95         cubic.set(a);
     96         SkDLine line;
     97         line.set(b);
     98         fMax = 3;
     99         return intersect(cubic, line);
    100     }
    101 
    102     bool hasT(double t) const {
    103         SkASSERT(t == 0 || t == 1);
    104         return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
    105     }
    106 
    107     int insertSwap(double one, double two, const SkDPoint& pt) {
    108         if (fSwap) {
    109             return insert(two, one, pt);
    110         } else {
    111             return insert(one, two, pt);
    112         }
    113     }
    114 
    115     bool isCoincident(int index) {
    116         return (fIsCoincident[0] & 1 << index) != 0;
    117     }
    118 
    119     int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
    120                        bool flipped) {
    121         SkDLine line;
    122         line.set(a);
    123         fMax = 2;
    124         return horizontal(line, left, right, y, flipped);
    125     }
    126 
    127     int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
    128         SkDLine line;
    129         line.set(a);
    130         fMax = 2;
    131         return vertical(line, top, bottom, x, flipped);
    132     }
    133 
    134     int lineLine(const SkPoint a[2], const SkPoint b[2]) {
    135         SkDLine aLine, bLine;
    136         aLine.set(a);
    137         bLine.set(b);
    138         fMax = 2;
    139         return intersect(aLine, bLine);
    140     }
    141 
    142     bool nearlySame(int index) const {
    143         SkASSERT(index == 0 || index == 1);
    144         return fNearlySame[index];
    145     }
    146 
    147     const SkDPoint& pt(int index) const {
    148         return fPt[index];
    149     }
    150 
    151     const SkDPoint& pt2(int index) const {
    152         return fPt2[index];
    153     }
    154 
    155     int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y,
    156                        bool flipped) {
    157         SkDQuad quad;
    158         quad.set(a);
    159         fMax = 2;
    160         return horizontal(quad, left, right, y, flipped);
    161     }
    162 
    163     int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
    164         SkDQuad quad;
    165         quad.set(a);
    166         fMax = 2;
    167         return vertical(quad, top, bottom, x, flipped);
    168     }
    169 
    170     int quadLine(const SkPoint a[3], const SkPoint b[2]) {
    171         SkDQuad quad;
    172         quad.set(a);
    173         SkDLine line;
    174         line.set(b);
    175         fMax = 3; // 2;  permit small coincident segment + non-coincident intersection
    176         return intersect(quad, line);
    177     }
    178 
    179     // leaves swap, max alone
    180     void reset() {
    181         fAllowNear = true;
    182         fUsed = 0;
    183         sk_bzero(fIsCoincident, sizeof(fIsCoincident));
    184     }
    185 
    186     void set(bool swap, int tIndex, double t) {
    187         fT[(int) swap][tIndex] = t;
    188     }
    189 
    190     void setMax(int max) {
    191         fMax = max;
    192     }
    193 
    194     void swap() {
    195         fSwap ^= true;
    196     }
    197 
    198     bool swapped() const {
    199         return fSwap;
    200     }
    201 
    202     int used() const {
    203         return fUsed;
    204     }
    205 
    206     void downDepth() {
    207         SkASSERT(--fDepth >= 0);
    208     }
    209 
    210     bool unBumpT(int index) {
    211         SkASSERT(fUsed == 1);
    212         fT[0][index] = fT[0][index] * (1 + BUMP_EPSILON * 2) - BUMP_EPSILON;
    213         if (!between(0, fT[0][index], 1)) {
    214             fUsed = 0;
    215             return false;
    216         }
    217         return true;
    218     }
    219 
    220     void upDepth() {
    221         SkASSERT(++fDepth < 16);
    222     }
    223 
    224     void alignQuadPts(const SkPoint a[3], const SkPoint b[3]);
    225     int cleanUpCoincidence();
    226     int closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, double* dist) const;
    227     void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1,
    228                      const SkDCubic& c2);
    229     void flip();
    230     int horizontal(const SkDLine&, double left, double right, double y, bool flipped);
    231     int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
    232     int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
    233     int horizontal(const SkDCubic&, double y, double tRange[3]);
    234     int horizontal(const SkDConic&, double left, double right, double y, bool flipped);
    235     int horizontal(const SkDCubic&, double left, double right, double y, bool flipped);
    236     int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
    237     static double HorizontalIntercept(const SkDLine& line, double y);
    238     static int HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots);
    239     static int HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots);
    240     // FIXME : does not respect swap
    241     int insert(double one, double two, const SkDPoint& pt);
    242     void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2);
    243     // start if index == 0 : end if index == 1
    244     int insertCoincident(double one, double two, const SkDPoint& pt);
    245     int intersect(const SkDLine&, const SkDLine&);
    246     int intersect(const SkDQuad&, const SkDLine&);
    247     int intersect(const SkDQuad&, const SkDQuad&);
    248     int intersect(const SkDConic&, const SkDLine&);
    249     int intersect(const SkDConic&, const SkDQuad&);
    250     int intersect(const SkDConic&, const SkDConic&);
    251     int intersect(const SkDCubic&, const SkDLine&);
    252     int intersect(const SkDCubic&, const SkDQuad&);
    253     int intersect(const SkDCubic&, const SkDConic&);
    254     int intersect(const SkDCubic&, const SkDCubic&);
    255     int intersectRay(const SkDLine&, const SkDLine&);
    256     int intersectRay(const SkDQuad&, const SkDLine&);
    257     int intersectRay(const SkDConic&, const SkDLine&);
    258     int intersectRay(const SkDCubic&, const SkDLine&);
    259     void merge(const SkIntersections& , int , const SkIntersections& , int );
    260     int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const;
    261     void removeOne(int index);
    262     void setCoincident(int index);
    263     int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
    264     int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped);
    265     int vertical(const SkDConic&, double top, double bottom, double x, bool flipped);
    266     int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped);
    267     static double VerticalIntercept(const SkDLine& line, double x);
    268     static int VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots);
    269     static int VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots);
    270 
    271     int depth() const {
    272 #ifdef SK_DEBUG
    273         return fDepth;
    274 #else
    275         return 0;
    276 #endif
    277     }
    278 
    279     int debugCoincidentUsed() const;
    280     void dump() const;  // implemented for testing only
    281 
    282 private:
    283     bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2);
    284     bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2);
    285     void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& );
    286     void cleanUpParallelLines(bool parallel);
    287     void computePoints(const SkDLine& line, int used);
    288 
    289     SkDPoint fPt[10];  // FIXME: since scans store points as SkPoint, this should also
    290     SkDPoint fPt2[2];  // used by nearly same to store alternate intersection point
    291     double fT[2][10];
    292     uint16_t fIsCoincident[2];  // bit set for each curve's coincident T
    293     bool fNearlySame[2];  // true if end points nearly match
    294     unsigned char fUsed;
    295     unsigned char fMax;
    296     bool fAllowNear;
    297     bool fSwap;
    298 #ifdef SK_DEBUG
    299     int fDepth;
    300 #endif
    301 };
    302 
    303 #endif
    304