SkIntersections.h

Go to the documentation of this file.

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#ifndef SkIntersections_DEFINE
#define SkIntersections_DEFINE
 
#include "include/core/SkPoint.h"
#include "include/core/SkScalar.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkMalloc.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsDebug.h"
#include "src/pathops/SkPathOpsLine.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "src/pathops/SkPathOpsTCurve.h"
#include "src/pathops/SkPathOpsTypes.h"
 
#include <array>
#include <cstdint>
 
struct SkDRect;
 
class SkIntersections {
public:
    SkIntersections(SkDEBUGCODE(SkOpGlobalState* globalState = nullptr))
        : fSwap(0)
#ifdef SK_DEBUG
        SkDEBUGPARAMS(fDebugGlobalState(globalState))
        , fDepth(0)
#endif
    {
        sk_bzero(fPt, sizeof(fPt));
        sk_bzero(fPt2, sizeof(fPt2));
        sk_bzero(fT, sizeof(fT));
        sk_bzero(fNearlySame, sizeof(fNearlySame));
#if DEBUG_T_SECT_LOOP_COUNT
        sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
#endif
        reset();
        fMax = 0;  // require that the caller set the max
    }
 
    class TArray {
    public:
        explicit TArray(const double ts[10]) : fTArray(ts) {}
        double operator[](int n) const {
            return fTArray[n];
        }
        const double* fTArray;
    };
    TArray operator[](int n) const { return TArray(fT[n]); }
 
    void allowNear(bool nearAllowed) {
        fAllowNear = nearAllowed;
    }
 
    void clearCoincidence(int index) {
        SkASSERT(index >= 0);
        int bit = 1 << index;
        fIsCoincident[0] &= ~bit;
        fIsCoincident[1] &= ~bit;
    }
 
    int conicHorizontal(const SkPoint a[3], SkScalar weight, SkScalar left, SkScalar right,
                SkScalar y, bool flipped) {
        SkDConic conic;
        conic.set(a, weight);
        fMax = 2;
        return horizontal(conic, left, right, y, flipped);
    }
 
    int conicVertical(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom,
            SkScalar x, bool flipped) {
        SkDConic conic;
        conic.set(a, weight);
        fMax = 2;
        return vertical(conic, top, bottom, x, flipped);
    }
 
    int conicLine(const SkPoint a[3], SkScalar weight, const SkPoint b[2]) {
        SkDConic conic;
        conic.set(a, weight);
        SkDLine line;
        line.set(b);
        fMax = 3; // 2;  permit small coincident segment + non-coincident intersection
        return intersect(conic, line);
    }
 
    int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y,
                        bool flipped) {
        SkDCubic cubic;
        cubic.set(a);
        fMax = 3;
        return horizontal(cubic, left, right, y, flipped);
    }
 
    int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
        SkDCubic cubic;
        cubic.set(a);
        fMax = 3;
        return vertical(cubic, top, bottom, x, flipped);
    }
 
    int cubicLine(const SkPoint a[4], const SkPoint b[2]) {
        SkDCubic cubic;
        cubic.set(a);
        SkDLine line;
        line.set(b);
        fMax = 3;
        return intersect(cubic, line);
    }
 
#ifdef SK_DEBUG
    SkOpGlobalState* globalState() const { return fDebugGlobalState; }
#endif
 
    bool hasT(double t) const {
        SkASSERT(t == 0 || t == 1);
        return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
    }
 
    bool hasOppT(double t) const {
        SkASSERT(t == 0 || t == 1);
        return fUsed > 0 && (fT[1][0] == t || fT[1][fUsed - 1] == t);
    }
 
    int insertSwap(double one, double two, const SkDPoint& pt) {
        if (fSwap) {
            return insert(two, one, pt);
        } else {
            return insert(one, two, pt);
        }
    }
 
    bool isCoincident(int index) {
        return (fIsCoincident[0] & 1 << index) != 0;
    }
 
    int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
                       bool flipped) {
        SkDLine line;
        line.set(a);
        fMax = 2;
        return horizontal(line, left, right, y, flipped);
    }
 
    int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
        SkDLine line;
        line.set(a);
        fMax = 2;
        return vertical(line, top, bottom, x, flipped);
    }
 
    int lineLine(const SkPoint a[2], const SkPoint b[2]) {
        SkDLine aLine, bLine;
        aLine.set(a);
        bLine.set(b);
        fMax = 2;
        return intersect(aLine, bLine);
    }
 
    bool nearlySame(int index) const {
        SkASSERT(index == 0 || index == 1);
        return fNearlySame[index];
    }
 
    const SkDPoint& pt(int index) const {
        return fPt[index];
    }
 
    const SkDPoint& pt2(int index) const {
        return fPt2[index];
    }
 
    int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y,
                       bool flipped) {
        SkDQuad quad;
        quad.set(a);
        fMax = 2;
        return horizontal(quad, left, right, y, flipped);
    }
 
    int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
        SkDQuad quad;
        quad.set(a);
        fMax = 2;
        return vertical(quad, top, bottom, x, flipped);
    }
 
    int quadLine(const SkPoint a[3], const SkPoint b[2]) {
        SkDQuad quad;
        quad.set(a);
        SkDLine line;
        line.set(b);
        return intersect(quad, line);
    }
 
    // leaves swap, max alone
    void reset() {
        fAllowNear = true;
        fUsed = 0;
        sk_bzero(fIsCoincident, sizeof(fIsCoincident));
    }
 
    void set(bool swap, int tIndex, double t) {
        fT[(int) swap][tIndex] = t;
    }
 
    void setMax(int max) {
        SkASSERT(max <= (int) std::size(fPt));
        fMax = max;
    }
 
    void swap() {
        fSwap ^= true;
    }
 
    bool swapped() const {
        return fSwap;
    }
 
    int used() const {
        return fUsed;
    }
 
    void downDepth() {
        SkASSERT(--fDepth >= 0);
    }
 
    bool unBumpT(int index) {
        SkASSERT(fUsed == 1);
        fT[0][index] = fT[0][index] * (1 + BUMP_EPSILON * 2) - BUMP_EPSILON;
        if (!between(0, fT[0][index], 1)) {
            fUsed = 0;
            return false;
        }
        return true;
    }
 
    void upDepth() {
        SkASSERT(++fDepth < 16);
    }
 
    void alignQuadPts(const SkPoint a[3], const SkPoint b[3]);
    int cleanUpCoincidence();
    int closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, double* dist) const;
    void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1,
                     const SkDCubic& c2);
    void flip();
    int horizontal(const SkDLine&, double left, double right, double y, bool flipped);
    int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
    int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
    int horizontal(const SkDCubic&, double y, double tRange[3]);
    int horizontal(const SkDConic&, double left, double right, double y, bool flipped);
    int horizontal(const SkDCubic&, double left, double right, double y, bool flipped);
    int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
    static double HorizontalIntercept(const SkDLine& line, double y);
    static int HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots);
    static int HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots);
    // FIXME : does not respect swap
    int insert(double one, double two, const SkDPoint& pt);
    void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2);
    // start if index == 0 : end if index == 1
    int insertCoincident(double one, double two, const SkDPoint& pt);
    int intersect(const SkDLine&, const SkDLine&);
    int intersect(const SkDQuad&, const SkDLine&);
    int intersect(const SkDQuad&, const SkDQuad&);
    int intersect(const SkDConic&, const SkDLine&);
    int intersect(const SkDConic&, const SkDQuad&);
    int intersect(const SkDConic&, const SkDConic&);
    int intersect(const SkDCubic&, const SkDLine&);
    int intersect(const SkDCubic&, const SkDQuad&);
    int intersect(const SkDCubic&, const SkDConic&);
    int intersect(const SkDCubic&, const SkDCubic&);
    int intersectRay(const SkDLine&, const SkDLine&);
    int intersectRay(const SkDQuad&, const SkDLine&);
    int intersectRay(const SkDConic&, const SkDLine&);
    int intersectRay(const SkDCubic&, const SkDLine&);
    int intersectRay(const SkTCurve& tCurve, const SkDLine& line) {
        return tCurve.intersectRay(this, line);
    }
 
    void merge(const SkIntersections& , int , const SkIntersections& , int );
    int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const;
    void removeOne(int index);
    void setCoincident(int index);
    int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
    int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped);
    int vertical(const SkDConic&, double top, double bottom, double x, bool flipped);
    int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped);
    static double VerticalIntercept(const SkDLine& line, double x);
    static int VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots);
    static int VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots);
 
    int depth() const {
#ifdef SK_DEBUG
        return fDepth;
#else
        return 0;
#endif
    }
 
    enum DebugLoop {
        kIterations_DebugLoop,
        kCoinCheck_DebugLoop,
        kComputePerp_DebugLoop,
    };
 
    void debugBumpLoopCount(DebugLoop );
    int debugCoincidentUsed() const;
    int debugLoopCount(DebugLoop ) const;
    void debugResetLoopCount();
    void dump() const;  // implemented for testing only
 
private:
    bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2);
    bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2);
    void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& );
    void cleanUpParallelLines(bool parallel);
    void computePoints(const SkDLine& line, int used);
 
    SkDPoint fPt[13];  // FIXME: since scans store points as SkPoint, this should also
    SkDPoint fPt2[2];  // used by nearly same to store alternate intersection point
    double fT[2][13];
    uint16_t fIsCoincident[2];  // bit set for each curve's coincident T
    bool fNearlySame[2];  // true if end points nearly match
    unsigned char fUsed;
    unsigned char fMax;
    bool fAllowNear;
    bool fSwap;
#ifdef SK_DEBUG
    SkOpGlobalState* fDebugGlobalState;
    int fDepth;
#endif
#if DEBUG_T_SECT_LOOP_COUNT
    int fDebugLoopCount[3];
#endif
};
 
#endif