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 #ifndef SkPathOpsQuad_DEFINED
9 #define SkPathOpsQuad_DEFINED
10 
11 #include "src/core/SkArenaAlloc.h"
12 #include "src/pathops/SkPathOpsTCurve.h"
13 
14 struct SkOpCurve;
15 
16 struct SkDQuadPair {
firstSkDQuadPair17     const SkDQuad& first() const { return (const SkDQuad&) pts[0]; }
secondSkDQuadPair18     const SkDQuad& second() const { return (const SkDQuad&) pts[2]; }
19     SkDPoint pts[5];
20 };
21 
22 struct SkDQuad {
23     static const int kPointCount = 3;
24     static const int kPointLast = kPointCount - 1;
25     static const int kMaxIntersections = 4;
26 
27     SkDPoint fPts[kPointCount];
28 
collapsedSkDQuad29     bool collapsed() const {
30         return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]);
31     }
32 
controlsInsideSkDQuad33     bool controlsInside() const {
34         SkDVector v01 = fPts[0] - fPts[1];
35         SkDVector v02 = fPts[0] - fPts[2];
36         SkDVector v12 = fPts[1] - fPts[2];
37         return v02.dot(v01) > 0 && v02.dot(v12) > 0;
38     }
39 
debugInitSkDQuad40     void debugInit() {
41         sk_bzero(fPts, sizeof(fPts));
42     }
43 
44     void debugSet(const SkDPoint* pts);
45 
flipSkDQuad46     SkDQuad flip() const {
47         SkDQuad result = {{fPts[2], fPts[1], fPts[0]}  SkDEBUGPARAMS(fDebugGlobalState) };
48         return result;
49     }
50 
IsConicSkDQuad51     static bool IsConic() { return false; }
52 
setSkDQuad53     const SkDQuad& set(const SkPoint pts[kPointCount]
54             SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) {
55         fPts[0] = pts[0];
56         fPts[1] = pts[1];
57         fPts[2] = pts[2];
58         SkDEBUGCODE(fDebugGlobalState = state);
59         return *this;
60     }
61 
62     const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
63     SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
64 
65     static int AddValidTs(double s[], int realRoots, double* t);
66     void align(int endIndex, SkDPoint* dstPt) const;
67     SkDQuadPair chopAt(double t) const;
68     SkDVector dxdyAtT(double t) const;
69     static int FindExtrema(const double src[], double tValue[1]);
70 
71 #ifdef SK_DEBUG
globalStateSkDQuad72     SkOpGlobalState* globalState() const { return fDebugGlobalState; }
73 #endif
74 
75     /**
76      *  Return the number of valid roots (0 < root < 1) for this cubic intersecting the
77      *  specified horizontal line.
78      */
79     int horizontalIntersect(double yIntercept, double roots[2]) const;
80 
81     bool hullIntersects(const SkDQuad& , bool* isLinear) const;
82     bool hullIntersects(const SkDConic& , bool* isLinear) const;
83     bool hullIntersects(const SkDCubic& , bool* isLinear) const;
84     bool isLinear(int startIndex, int endIndex) const;
maxIntersectionsSkDQuad85     static int maxIntersections() { return kMaxIntersections; }
86     bool monotonicInX() const;
87     bool monotonicInY() const;
88     void otherPts(int oddMan, const SkDPoint* endPt[2]) const;
pointCountSkDQuad89     static int pointCount() { return kPointCount; }
pointLastSkDQuad90     static int pointLast() { return kPointLast; }
91     SkDPoint ptAtT(double t) const;
92     static int RootsReal(double A, double B, double C, double t[2]);
93     static int RootsValidT(const double A, const double B, const double C, double s[2]);
94     static void SetABC(const double* quad, double* a, double* b, double* c);
95     SkDQuad subDivide(double t1, double t2) const;
subDivideSkDQuad96     void subDivide(double t1, double t2, SkDQuad* quad) const { *quad = this->subDivide(t1, t2); }
97 
SubDivideSkDQuad98     static SkDQuad SubDivide(const SkPoint a[kPointCount], double t1, double t2) {
99         SkDQuad quad;
100         quad.set(a);
101         return quad.subDivide(t1, t2);
102     }
103     SkDPoint subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const;
SubDivideSkDQuad104     static SkDPoint SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& c,
105                               double t1, double t2) {
106         SkDQuad quad;
107         quad.set(pts);
108         return quad.subDivide(a, c, t1, t2);
109     }
110 
111     /**
112      *  Return the number of valid roots (0 < root < 1) for this cubic intersecting the
113      *  specified vertical line.
114      */
115     int verticalIntersect(double xIntercept, double roots[2]) const;
116 
117     SkDCubic debugToCubic() const;
118     // utilities callable by the user from the debugger when the implementation code is linked in
119     void dump() const;
120     void dumpID(int id) const;
121     void dumpInner() const;
122 
123     SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
124 };
125 
126 
127 class SkTQuad : public SkTCurve {
128 public:
129     SkDQuad fQuad;
130 
SkTQuad()131     SkTQuad() {}
132 
SkTQuad(const SkDQuad & q)133     SkTQuad(const SkDQuad& q)
134         : fQuad(q) {
135     }
136 
~SkTQuad()137     ~SkTQuad() override {}
138 
139     const SkDPoint& operator[](int n) const override { return fQuad[n]; }
140     SkDPoint& operator[](int n) override { return fQuad[n]; }
141 
collapsed()142     bool collapsed() const override { return fQuad.collapsed(); }
controlsInside()143     bool controlsInside() const override { return fQuad.controlsInside(); }
debugInit()144     void debugInit() override { return fQuad.debugInit(); }
145 #if DEBUG_T_SECT
dumpID(int id)146     void dumpID(int id) const override { return fQuad.dumpID(id); }
147 #endif
dxdyAtT(double t)148     SkDVector dxdyAtT(double t) const override { return fQuad.dxdyAtT(t); }
149 #ifdef SK_DEBUG
globalState()150     SkOpGlobalState* globalState() const override { return fQuad.globalState(); }
151 #endif
152 
hullIntersects(const SkDQuad & quad,bool * isLinear)153     bool hullIntersects(const SkDQuad& quad, bool* isLinear) const override {
154         return quad.hullIntersects(fQuad, isLinear);
155     }
156 
157     bool hullIntersects(const SkDConic& conic, bool* isLinear) const override;
158     bool hullIntersects(const SkDCubic& cubic, bool* isLinear) const override;
159 
hullIntersects(const SkTCurve & curve,bool * isLinear)160     bool hullIntersects(const SkTCurve& curve, bool* isLinear) const override {
161         return curve.hullIntersects(fQuad, isLinear);
162     }
163 
164     int intersectRay(SkIntersections* i, const SkDLine& line) const override;
IsConic()165     bool IsConic() const override { return false; }
make(SkArenaAlloc & heap)166     SkTCurve* make(SkArenaAlloc& heap) const override { return heap.make<SkTQuad>(); }
167 
maxIntersections()168     int maxIntersections() const override { return SkDQuad::kMaxIntersections; }
169 
otherPts(int oddMan,const SkDPoint * endPt[2])170     void otherPts(int oddMan, const SkDPoint* endPt[2]) const override {
171         fQuad.otherPts(oddMan, endPt);
172     }
173 
pointCount()174     int pointCount() const override { return SkDQuad::kPointCount; }
pointLast()175     int pointLast() const override { return SkDQuad::kPointLast; }
ptAtT(double t)176     SkDPoint ptAtT(double t) const override { return fQuad.ptAtT(t); }
177     void setBounds(SkDRect* ) const override;
178 
subDivide(double t1,double t2,SkTCurve * curve)179     void subDivide(double t1, double t2, SkTCurve* curve) const override {
180         ((SkTQuad*) curve)->fQuad = fQuad.subDivide(t1, t2);
181     }
182 };
183 
184 #endif
185