michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #ifndef SkIntersections_DEFINE
michael@0: #define SkIntersections_DEFINE
michael@0: 
michael@0: #include "SkPathOpsCubic.h"
michael@0: #include "SkPathOpsLine.h"
michael@0: #include "SkPathOpsPoint.h"
michael@0: #include "SkPathOpsQuad.h"
michael@0: 
michael@0: class SkIntersections {
michael@0: public:
michael@0:     SkIntersections()
michael@0:         : fSwap(0)
michael@0: #ifdef SK_DEBUG
michael@0:         , fDepth(0)
michael@0: #endif
michael@0:     {
michael@0:         sk_bzero(fPt, sizeof(fPt));
michael@0:         sk_bzero(fT, sizeof(fT));
michael@0:         sk_bzero(fIsCoincident, sizeof(fIsCoincident));
michael@0:         reset();
michael@0:         fMax = 0;  // require that the caller set the max
michael@0:     }
michael@0: 
michael@0:     class TArray {
michael@0:     public:
michael@0:         explicit TArray(const double ts[9]) : fTArray(ts) {}
michael@0:         double operator[](int n) const {
michael@0:             return fTArray[n];
michael@0:         }
michael@0:         const double* fTArray;
michael@0:     };
michael@0:     TArray operator[](int n) const { return TArray(fT[n]); }
michael@0: 
michael@0:     void set(const SkIntersections& i) {
michael@0:         memcpy(fPt, i.fPt, sizeof(fPt));
michael@0:         memcpy(fT, i.fT, sizeof(fT));
michael@0:         memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident));
michael@0:         fUsed = i.fUsed;
michael@0:         fMax = i.fMax;
michael@0:         fSwap = i.fSwap;
michael@0:         SkDEBUGCODE(fDepth = i.fDepth);
michael@0:     }
michael@0: 
michael@0:     void allowNear(bool nearAllowed) {
michael@0:         fAllowNear = nearAllowed;
michael@0:     }
michael@0: 
michael@0:     int cubic(const SkPoint a[4]) {
michael@0:         SkDCubic cubic;
michael@0:         cubic.set(a);
michael@0:         fMax = 1;  // self intersect
michael@0:         return intersect(cubic);
michael@0:     }
michael@0: 
michael@0:     int cubicCubic(const SkPoint a[4], const SkPoint b[4]) {
michael@0:         SkDCubic aCubic;
michael@0:         aCubic.set(a);
michael@0:         SkDCubic bCubic;
michael@0:         bCubic.set(b);
michael@0:         fMax = 9;
michael@0:         return intersect(aCubic, bCubic);
michael@0:     }
michael@0: 
michael@0:     int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y,
michael@0:                         bool flipped) {
michael@0:         SkDCubic cubic;
michael@0:         cubic.set(a);
michael@0:         fMax = 3;
michael@0:         return horizontal(cubic, left, right, y, flipped);
michael@0:     }
michael@0: 
michael@0:     int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
michael@0:         SkDCubic cubic;
michael@0:         cubic.set(a);
michael@0:         fMax = 3;
michael@0:         return vertical(cubic, top, bottom, x, flipped);
michael@0:     }
michael@0: 
michael@0:     int cubicLine(const SkPoint a[4], const SkPoint b[2]) {
michael@0:         SkDCubic cubic;
michael@0:         cubic.set(a);
michael@0:         SkDLine line;
michael@0:         line.set(b);
michael@0:         fMax = 3;
michael@0:         return intersect(cubic, line);
michael@0:     }
michael@0: 
michael@0:     int cubicQuad(const SkPoint a[4], const SkPoint b[3]) {
michael@0:         SkDCubic cubic;
michael@0:         cubic.set(a);
michael@0:         SkDQuad quad;
michael@0:         quad.set(b);
michael@0:         fMax = 6;
michael@0:         return intersect(cubic, quad);
michael@0:     }
michael@0: 
michael@0:     bool hasT(double t) const {
michael@0:         SkASSERT(t == 0 || t == 1);
michael@0:         return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
michael@0:     }
michael@0: 
michael@0:     int insertSwap(double one, double two, const SkDPoint& pt) {
michael@0:         if (fSwap) {
michael@0:             return insert(two, one, pt);
michael@0:         } else {
michael@0:             return insert(one, two, pt);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     bool isCoincident(int index) {
michael@0:         return (fIsCoincident[0] & 1 << index) != 0;
michael@0:     }
michael@0: 
michael@0:     int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
michael@0:                        bool flipped) {
michael@0:         SkDLine line;
michael@0:         line.set(a);
michael@0:         fMax = 2;
michael@0:         return horizontal(line, left, right, y, flipped);
michael@0:     }
michael@0: 
michael@0:     int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
michael@0:         SkDLine line;
michael@0:         line.set(a);
michael@0:         fMax = 2;
michael@0:         return vertical(line, top, bottom, x, flipped);
michael@0:     }
michael@0: 
michael@0:     int lineLine(const SkPoint a[2], const SkPoint b[2]) {
michael@0:         SkDLine aLine, bLine;
michael@0:         aLine.set(a);
michael@0:         bLine.set(b);
michael@0:         fMax = 2;
michael@0:         return intersect(aLine, bLine);
michael@0:     }
michael@0: 
michael@0:     const SkDPoint& pt(int index) const {
michael@0:         return fPt[index];
michael@0:     }
michael@0: 
michael@0:     int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y,
michael@0:                        bool flipped) {
michael@0:         SkDQuad quad;
michael@0:         quad.set(a);
michael@0:         fMax = 2;
michael@0:         return horizontal(quad, left, right, y, flipped);
michael@0:     }
michael@0: 
michael@0:     int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
michael@0:         SkDQuad quad;
michael@0:         quad.set(a);
michael@0:         fMax = 2;
michael@0:         return vertical(quad, top, bottom, x, flipped);
michael@0:     }
michael@0: 
michael@0:     int quadLine(const SkPoint a[3], const SkPoint b[2]) {
michael@0:         SkDQuad quad;
michael@0:         quad.set(a);
michael@0:         SkDLine line;
michael@0:         line.set(b);
michael@0:         fMax = 2;
michael@0:         return intersect(quad, line);
michael@0:     }
michael@0: 
michael@0:     int quadQuad(const SkPoint a[3], const SkPoint b[3]) {
michael@0:         SkDQuad aQuad;
michael@0:         aQuad.set(a);
michael@0:         SkDQuad bQuad;
michael@0:         bQuad.set(b);
michael@0:         fMax = 4;
michael@0:         return intersect(aQuad, bQuad);
michael@0:     }
michael@0: 
michael@0:     // leaves flip, swap, max alone
michael@0:     void reset() {
michael@0:         fAllowNear = true;
michael@0:         fUsed = 0;
michael@0:     }
michael@0: 
michael@0:     void setMax(int max) {
michael@0:         fMax = max;
michael@0:     }
michael@0: 
michael@0:     void swap() {
michael@0:         fSwap ^= true;
michael@0:     }
michael@0: 
michael@0:     void swapPts();
michael@0: 
michael@0:     bool swapped() const {
michael@0:         return fSwap;
michael@0:     }
michael@0: 
michael@0:     int used() const {
michael@0:         return fUsed;
michael@0:     }
michael@0: 
michael@0:     void downDepth() {
michael@0:         SkASSERT(--fDepth >= 0);
michael@0:     }
michael@0: 
michael@0:     void upDepth() {
michael@0:         SkASSERT(++fDepth < 16);
michael@0:     }
michael@0: 
michael@0:     void append(const SkIntersections& );
michael@0:     static double Axial(const SkDQuad& , const SkDPoint& , bool vertical);
michael@0:     void cleanUpCoincidence();
michael@0:     int coincidentUsed() const;
michael@0:     int cubicRay(const SkPoint pts[4], const SkDLine& line);
michael@0:     void flip();
michael@0:     int horizontal(const SkDLine&, double y);
michael@0:     int horizontal(const SkDLine&, double left, double right, double y, bool flipped);
michael@0:     int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
michael@0:     int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
michael@0:     int horizontal(const SkDCubic&, double y, double tRange[3]);
michael@0:     int horizontal(const SkDCubic&, double left, double right, double y, bool flipped);
michael@0:     int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
michael@0:     // FIXME : does not respect swap
michael@0:     int insert(double one, double two, const SkDPoint& pt);
michael@0:     void insertNear(double one, double two, const SkDPoint& pt);
michael@0:     // start if index == 0 : end if index == 1
michael@0:     void insertCoincident(double one, double two, const SkDPoint& pt);
michael@0:     int intersect(const SkDLine&, const SkDLine&);
michael@0:     int intersect(const SkDQuad&, const SkDLine&);
michael@0:     int intersect(const SkDQuad&, const SkDQuad&);
michael@0:     int intersect(const SkDCubic&);  // return true if cubic self-intersects
michael@0:     int intersect(const SkDCubic&, const SkDLine&);
michael@0:     int intersect(const SkDCubic&, const SkDQuad&);
michael@0:     int intersect(const SkDCubic&, const SkDCubic&);
michael@0:     int intersectRay(const SkDLine&, const SkDLine&);
michael@0:     int intersectRay(const SkDQuad&, const SkDLine&);
michael@0:     int intersectRay(const SkDCubic&, const SkDLine&);
michael@0:     static SkDPoint Line(const SkDLine&, const SkDLine&);
michael@0:     int lineRay(const SkPoint pts[2], const SkDLine& line);
michael@0:     void offset(int base, double start, double end);
michael@0:     void quickRemoveOne(int index, int replace);
michael@0:     int quadRay(const SkPoint pts[3], const SkDLine& line);
michael@0:     void removeOne(int index);
michael@0:     static bool Test(const SkDLine& , const SkDLine&);
michael@0:     int vertical(const SkDLine&, double x);
michael@0:     int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
michael@0:     int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped);
michael@0:     int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped);
michael@0:     int verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
michael@0:     int verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
michael@0:     int verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
michael@0: 
michael@0:     int depth() const {
michael@0: #ifdef SK_DEBUG
michael@0:         return fDepth;
michael@0: #else
michael@0:         return 0;
michael@0: #endif
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2);
michael@0:     bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2);
michael@0:     void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& );
michael@0:     void cleanUpParallelLines(bool parallel);
michael@0:     void computePoints(const SkDLine& line, int used);
michael@0:     // used by addCoincident to remove ordinary intersections in range
michael@0:  //   void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt);
michael@0: 
michael@0:     SkDPoint fPt[9];  // FIXME: since scans store points as SkPoint, this should also
michael@0:     double fT[2][9];
michael@0:     uint16_t fIsCoincident[2];  // bit set for each curve's coincident T
michael@0:     unsigned char fUsed;
michael@0:     unsigned char fMax;
michael@0:     bool fAllowNear;
michael@0:     bool fSwap;
michael@0: #ifdef SK_DEBUG
michael@0:     int fDepth;
michael@0: #endif
michael@0: };
michael@0: 
michael@0: extern int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine& );
michael@0: extern int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar top, SkScalar bottom,
michael@0:             SkScalar x, bool flipped);
michael@0: 
michael@0: #endif