1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkIntersections.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,288 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#ifndef SkIntersections_DEFINE
1.11 +#define SkIntersections_DEFINE
1.12 +
1.13 +#include "SkPathOpsCubic.h"
1.14 +#include "SkPathOpsLine.h"
1.15 +#include "SkPathOpsPoint.h"
1.16 +#include "SkPathOpsQuad.h"
1.17 +
1.18 +class SkIntersections {
1.19 +public:
1.20 + SkIntersections()
1.21 + : fSwap(0)
1.22 +#ifdef SK_DEBUG
1.23 + , fDepth(0)
1.24 +#endif
1.25 + {
1.26 + sk_bzero(fPt, sizeof(fPt));
1.27 + sk_bzero(fT, sizeof(fT));
1.28 + sk_bzero(fIsCoincident, sizeof(fIsCoincident));
1.29 + reset();
1.30 + fMax = 0; // require that the caller set the max
1.31 + }
1.32 +
1.33 + class TArray {
1.34 + public:
1.35 + explicit TArray(const double ts[9]) : fTArray(ts) {}
1.36 + double operator[](int n) const {
1.37 + return fTArray[n];
1.38 + }
1.39 + const double* fTArray;
1.40 + };
1.41 + TArray operator[](int n) const { return TArray(fT[n]); }
1.42 +
1.43 + void set(const SkIntersections& i) {
1.44 + memcpy(fPt, i.fPt, sizeof(fPt));
1.45 + memcpy(fT, i.fT, sizeof(fT));
1.46 + memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident));
1.47 + fUsed = i.fUsed;
1.48 + fMax = i.fMax;
1.49 + fSwap = i.fSwap;
1.50 + SkDEBUGCODE(fDepth = i.fDepth);
1.51 + }
1.52 +
1.53 + void allowNear(bool nearAllowed) {
1.54 + fAllowNear = nearAllowed;
1.55 + }
1.56 +
1.57 + int cubic(const SkPoint a[4]) {
1.58 + SkDCubic cubic;
1.59 + cubic.set(a);
1.60 + fMax = 1; // self intersect
1.61 + return intersect(cubic);
1.62 + }
1.63 +
1.64 + int cubicCubic(const SkPoint a[4], const SkPoint b[4]) {
1.65 + SkDCubic aCubic;
1.66 + aCubic.set(a);
1.67 + SkDCubic bCubic;
1.68 + bCubic.set(b);
1.69 + fMax = 9;
1.70 + return intersect(aCubic, bCubic);
1.71 + }
1.72 +
1.73 + int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y,
1.74 + bool flipped) {
1.75 + SkDCubic cubic;
1.76 + cubic.set(a);
1.77 + fMax = 3;
1.78 + return horizontal(cubic, left, right, y, flipped);
1.79 + }
1.80 +
1.81 + int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
1.82 + SkDCubic cubic;
1.83 + cubic.set(a);
1.84 + fMax = 3;
1.85 + return vertical(cubic, top, bottom, x, flipped);
1.86 + }
1.87 +
1.88 + int cubicLine(const SkPoint a[4], const SkPoint b[2]) {
1.89 + SkDCubic cubic;
1.90 + cubic.set(a);
1.91 + SkDLine line;
1.92 + line.set(b);
1.93 + fMax = 3;
1.94 + return intersect(cubic, line);
1.95 + }
1.96 +
1.97 + int cubicQuad(const SkPoint a[4], const SkPoint b[3]) {
1.98 + SkDCubic cubic;
1.99 + cubic.set(a);
1.100 + SkDQuad quad;
1.101 + quad.set(b);
1.102 + fMax = 6;
1.103 + return intersect(cubic, quad);
1.104 + }
1.105 +
1.106 + bool hasT(double t) const {
1.107 + SkASSERT(t == 0 || t == 1);
1.108 + return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
1.109 + }
1.110 +
1.111 + int insertSwap(double one, double two, const SkDPoint& pt) {
1.112 + if (fSwap) {
1.113 + return insert(two, one, pt);
1.114 + } else {
1.115 + return insert(one, two, pt);
1.116 + }
1.117 + }
1.118 +
1.119 + bool isCoincident(int index) {
1.120 + return (fIsCoincident[0] & 1 << index) != 0;
1.121 + }
1.122 +
1.123 + int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
1.124 + bool flipped) {
1.125 + SkDLine line;
1.126 + line.set(a);
1.127 + fMax = 2;
1.128 + return horizontal(line, left, right, y, flipped);
1.129 + }
1.130 +
1.131 + int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
1.132 + SkDLine line;
1.133 + line.set(a);
1.134 + fMax = 2;
1.135 + return vertical(line, top, bottom, x, flipped);
1.136 + }
1.137 +
1.138 + int lineLine(const SkPoint a[2], const SkPoint b[2]) {
1.139 + SkDLine aLine, bLine;
1.140 + aLine.set(a);
1.141 + bLine.set(b);
1.142 + fMax = 2;
1.143 + return intersect(aLine, bLine);
1.144 + }
1.145 +
1.146 + const SkDPoint& pt(int index) const {
1.147 + return fPt[index];
1.148 + }
1.149 +
1.150 + int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y,
1.151 + bool flipped) {
1.152 + SkDQuad quad;
1.153 + quad.set(a);
1.154 + fMax = 2;
1.155 + return horizontal(quad, left, right, y, flipped);
1.156 + }
1.157 +
1.158 + int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
1.159 + SkDQuad quad;
1.160 + quad.set(a);
1.161 + fMax = 2;
1.162 + return vertical(quad, top, bottom, x, flipped);
1.163 + }
1.164 +
1.165 + int quadLine(const SkPoint a[3], const SkPoint b[2]) {
1.166 + SkDQuad quad;
1.167 + quad.set(a);
1.168 + SkDLine line;
1.169 + line.set(b);
1.170 + fMax = 2;
1.171 + return intersect(quad, line);
1.172 + }
1.173 +
1.174 + int quadQuad(const SkPoint a[3], const SkPoint b[3]) {
1.175 + SkDQuad aQuad;
1.176 + aQuad.set(a);
1.177 + SkDQuad bQuad;
1.178 + bQuad.set(b);
1.179 + fMax = 4;
1.180 + return intersect(aQuad, bQuad);
1.181 + }
1.182 +
1.183 + // leaves flip, swap, max alone
1.184 + void reset() {
1.185 + fAllowNear = true;
1.186 + fUsed = 0;
1.187 + }
1.188 +
1.189 + void setMax(int max) {
1.190 + fMax = max;
1.191 + }
1.192 +
1.193 + void swap() {
1.194 + fSwap ^= true;
1.195 + }
1.196 +
1.197 + void swapPts();
1.198 +
1.199 + bool swapped() const {
1.200 + return fSwap;
1.201 + }
1.202 +
1.203 + int used() const {
1.204 + return fUsed;
1.205 + }
1.206 +
1.207 + void downDepth() {
1.208 + SkASSERT(--fDepth >= 0);
1.209 + }
1.210 +
1.211 + void upDepth() {
1.212 + SkASSERT(++fDepth < 16);
1.213 + }
1.214 +
1.215 + void append(const SkIntersections& );
1.216 + static double Axial(const SkDQuad& , const SkDPoint& , bool vertical);
1.217 + void cleanUpCoincidence();
1.218 + int coincidentUsed() const;
1.219 + int cubicRay(const SkPoint pts[4], const SkDLine& line);
1.220 + void flip();
1.221 + int horizontal(const SkDLine&, double y);
1.222 + int horizontal(const SkDLine&, double left, double right, double y, bool flipped);
1.223 + int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
1.224 + int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
1.225 + int horizontal(const SkDCubic&, double y, double tRange[3]);
1.226 + int horizontal(const SkDCubic&, double left, double right, double y, bool flipped);
1.227 + int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
1.228 + // FIXME : does not respect swap
1.229 + int insert(double one, double two, const SkDPoint& pt);
1.230 + void insertNear(double one, double two, const SkDPoint& pt);
1.231 + // start if index == 0 : end if index == 1
1.232 + void insertCoincident(double one, double two, const SkDPoint& pt);
1.233 + int intersect(const SkDLine&, const SkDLine&);
1.234 + int intersect(const SkDQuad&, const SkDLine&);
1.235 + int intersect(const SkDQuad&, const SkDQuad&);
1.236 + int intersect(const SkDCubic&); // return true if cubic self-intersects
1.237 + int intersect(const SkDCubic&, const SkDLine&);
1.238 + int intersect(const SkDCubic&, const SkDQuad&);
1.239 + int intersect(const SkDCubic&, const SkDCubic&);
1.240 + int intersectRay(const SkDLine&, const SkDLine&);
1.241 + int intersectRay(const SkDQuad&, const SkDLine&);
1.242 + int intersectRay(const SkDCubic&, const SkDLine&);
1.243 + static SkDPoint Line(const SkDLine&, const SkDLine&);
1.244 + int lineRay(const SkPoint pts[2], const SkDLine& line);
1.245 + void offset(int base, double start, double end);
1.246 + void quickRemoveOne(int index, int replace);
1.247 + int quadRay(const SkPoint pts[3], const SkDLine& line);
1.248 + void removeOne(int index);
1.249 + static bool Test(const SkDLine& , const SkDLine&);
1.250 + int vertical(const SkDLine&, double x);
1.251 + int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
1.252 + int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped);
1.253 + int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped);
1.254 + int verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
1.255 + int verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
1.256 + int verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
1.257 +
1.258 + int depth() const {
1.259 +#ifdef SK_DEBUG
1.260 + return fDepth;
1.261 +#else
1.262 + return 0;
1.263 +#endif
1.264 + }
1.265 +
1.266 +private:
1.267 + bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2);
1.268 + bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2);
1.269 + void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& );
1.270 + void cleanUpParallelLines(bool parallel);
1.271 + void computePoints(const SkDLine& line, int used);
1.272 + // used by addCoincident to remove ordinary intersections in range
1.273 + // void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt);
1.274 +
1.275 + SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also
1.276 + double fT[2][9];
1.277 + uint16_t fIsCoincident[2]; // bit set for each curve's coincident T
1.278 + unsigned char fUsed;
1.279 + unsigned char fMax;
1.280 + bool fAllowNear;
1.281 + bool fSwap;
1.282 +#ifdef SK_DEBUG
1.283 + int fDepth;
1.284 +#endif
1.285 +};
1.286 +
1.287 +extern int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine& );
1.288 +extern int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar top, SkScalar bottom,
1.289 + SkScalar x, bool flipped);
1.290 +
1.291 +#endif
