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#include "SkIntersections.h"
9
10void SkIntersections::append(const SkIntersections& i) {
11    for (int index = 0; index < i.fUsed; ++index) {
12        insert(i[0][index], i[1][index], i.pt(index));
13    }
14}
15
16int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
17    NULL,
18    &SkIntersections::verticalLine,
19    &SkIntersections::verticalQuad,
20    &SkIntersections::verticalCubic
21};
22
23int ( SkIntersections::* const CurveRay[])(const SkPoint[], const SkDLine&) = {
24    NULL,
25    &SkIntersections::lineRay,
26    &SkIntersections::quadRay,
27    &SkIntersections::cubicRay
28};
29
30int SkIntersections::coincidentUsed() const {
31    if (!fIsCoincident[0]) {
32        SkASSERT(!fIsCoincident[1]);
33        return 0;
34    }
35    int count = 0;
36    SkDEBUGCODE(int count2 = 0;)
37    for (int index = 0; index < fUsed; ++index) {
38        if (fIsCoincident[0] & (1 << index)) {
39            ++count;
40        }
41#ifdef SK_DEBUG
42        if (fIsCoincident[1] & (1 << index)) {
43            ++count2;
44        }
45#endif
46    }
47    SkASSERT(count == count2);
48    return count;
49}
50
51int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) {
52    SkDCubic cubic;
53    cubic.set(pts);
54    fMax = 3;
55    return intersectRay(cubic, line);
56}
57
58void SkIntersections::flip() {
59    for (int index = 0; index < fUsed; ++index) {
60        fT[1][index] = 1 - fT[1][index];
61    }
62}
63
64int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
65    if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
66        // For now, don't allow a mix of coincident and non-coincident intersections
67        return -1;
68    }
69    SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
70    int index;
71    for (index = 0; index < fUsed; ++index) {
72        double oldOne = fT[0][index];
73        double oldTwo = fT[1][index];
74        if (one == oldOne && two == oldTwo) {
75            return -1;
76        }
77        if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
78            if ((precisely_zero(one) && !precisely_zero(oldOne))
79                    || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
80                    || (precisely_zero(two) && !precisely_zero(oldTwo))
81                    || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
82                fT[0][index] = one;
83                fT[1][index] = two;
84                fPt[index] = pt;
85            }
86            return -1;
87        }
88    #if ONE_OFF_DEBUG
89        if (pt.roughlyEqual(fPt[index])) {
90            SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
91        }
92    #endif
93        if (fT[0][index] > one) {
94            break;
95        }
96    }
97    if (fUsed >= fMax) {
98        SkASSERT(0);  // FIXME : this error, if it is to be handled at runtime in release, must
99                      // be propagated all the way back down to the caller, and return failure.
100        fUsed = 0;
101        return 0;
102    }
103    int remaining = fUsed - index;
104    if (remaining > 0) {
105        memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
106        memmove(&fPt2[index + 1], &fPt2[index], sizeof(fPt2[0]) * remaining);
107        memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
108        memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
109        int clearMask = ~((1 << index) - 1);
110        fIsCoincident[0] += fIsCoincident[0] & clearMask;
111        fIsCoincident[1] += fIsCoincident[1] & clearMask;
112    }
113    fPt[index] = pt;
114    fT[0][index] = one;
115    fT[1][index] = two;
116    ++fUsed;
117    return index;
118}
119
120void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) {
121    SkASSERT(one == 0 || one == 1);
122    SkASSERT(two == 0 || two == 1);
123    SkASSERT(pt1 != pt2);
124    SkASSERT(fNearlySame[(int) one]);
125    (void) insert(one, two, pt1);
126    fPt2[one ? fUsed - 1 : 0] = pt2;
127}
128
129void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
130    int index = insertSwap(one, two, pt);
131    int bit = 1 << index;
132    fIsCoincident[0] |= bit;
133    fIsCoincident[1] |= bit;
134}
135
136int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) {
137    SkDLine l;
138    l.set(pts);
139    fMax = 2;
140    return intersectRay(l, line);
141}
142
143void SkIntersections::offset(int base, double start, double end) {
144    for (int index = base; index < fUsed; ++index) {
145        double val = fT[fSwap][index];
146        val *= end - start;
147        val += start;
148        fT[fSwap][index] = val;
149    }
150}
151
152int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) {
153    SkDQuad quad;
154    quad.set(pts);
155    fMax = 2;
156    return intersectRay(quad, line);
157}
158
159void SkIntersections::quickRemoveOne(int index, int replace) {
160    if (index < replace) {
161        fT[0][index] = fT[0][replace];
162    }
163}
164
165void SkIntersections::removeOne(int index) {
166    int remaining = --fUsed - index;
167    if (remaining <= 0) {
168        return;
169    }
170    memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
171    memmove(&fPt2[index], &fPt2[index + 1], sizeof(fPt2[0]) * remaining);
172    memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
173    memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
174    SkASSERT(fIsCoincident[0] == 0);
175    int coBit = fIsCoincident[0] & (1 << index);
176    fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
177    SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
178    fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
179}
180
181void SkIntersections::swapPts() {
182    int index;
183    for (index = 0; index < fUsed; ++index) {
184        SkTSwap(fT[0][index], fT[1][index]);
185    }
186}
187
188int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom,
189        SkScalar x, bool flipped) {
190    SkDLine line;
191    line.set(a);
192    return vertical(line, top, bottom, x, flipped);
193}
194
195int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom,
196        SkScalar x, bool flipped) {
197    SkDQuad quad;
198    quad.set(a);
199    return vertical(quad, top, bottom, x, flipped);
200}
201
202int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom,
203        SkScalar x, bool flipped) {
204    SkDCubic cubic;
205    cubic.set(a);
206    return vertical(cubic, top, bottom, x, flipped);
207}
208