src/third_party/skia/src/pathops/SkIntersections.h

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