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 "DataTypes.h"
9#include "Intersections.h"
10
11void Intersections::insertCoincidentPair(double s1, double e1, double s2, double e2,
12        const _Point& startPt, const _Point& endPt) {
13    if (fSwap) {
14        remove(s2, e2, startPt, endPt);
15    } else {
16        remove(s1, e1, startPt, endPt);
17    }
18    SkASSERT(coincidentUsed() == fUsed);
19    SkASSERT((coincidentUsed() & 1) != 1);
20    int i1 = 0;
21    int i2 = 0;
22    do {
23        while (i1 < fUsed && !(fIsCoincident[fSwap] & (1 << i1))) {
24            ++i1;
25        }
26        if (i1 == fUsed) {
27            break;
28        }
29        SkASSERT(i1 < fUsed);
30        int iEnd1 = i1 + 1;
31        while (!(fIsCoincident[fSwap] & (1 << iEnd1))) {
32            ++iEnd1;
33        }
34        SkASSERT(iEnd1 < fUsed);
35        double cs1 = fT[fSwap][i1];
36        double ce1 = fT[fSwap][iEnd1];
37        bool s1in = between(cs1, s1, ce1) || startPt.approximatelyEqual(fPt[i1])
38                || startPt.approximatelyEqual(fPt[iEnd1]);
39        bool e1in = between(cs1, e1, ce1) || endPt.approximatelyEqual(fPt[i1])
40                || endPt.approximatelyEqual(fPt[iEnd1]);
41        while (i2 < fUsed && !(fIsCoincident[fSwap ^ 1] & (1 << i2))) {
42            ++i2;
43        }
44        int iEnd2 = i2 + 1;
45        while (!(fIsCoincident[fSwap ^ 1] & (1 << iEnd2))) {
46            ++iEnd2;
47        }
48        SkASSERT(iEnd2 < fUsed);
49        double cs2 = fT[fSwap ^ 1][i2];
50        double ce2 = fT[fSwap ^ 1][iEnd2];
51        bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2])
52                || startPt.approximatelyEqual(fPt[iEnd2]);
53        bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2])
54                || endPt.approximatelyEqual(fPt[iEnd2]);
55        if ((s1in | e1in) & (s2in | e2in)) {
56            if (s1 < cs1) {
57                fT[fSwap][i1] = s1;
58                fPt[i1] = startPt;
59            } else if (e1 < cs1) {
60                fT[fSwap][i1] = e1;
61                fPt[i1] = endPt;
62            }
63            if (s1 > ce1) {
64                fT[fSwap][iEnd1] = s1;
65                fPt[iEnd1] = startPt;
66            } else if (e1 > ce1) {
67                fT[fSwap][iEnd1] = e1;
68                fPt[iEnd1] = endPt;
69            }
70            if (s2 > e2) {
71                SkTSwap(cs2, ce2);
72                SkTSwap(i2, iEnd2);
73            }
74            if (s2 < cs2) {
75                fT[fSwap ^ 1][i2] = s2;
76            } else if (e2 < cs2) {
77                fT[fSwap ^ 1][i2] = e2;
78            }
79            if (s2 > ce2) {
80                fT[fSwap ^ 1][iEnd2] = s2;
81            } else if (e2 > ce2) {
82                fT[fSwap ^ 1][iEnd2] = e2;
83            }
84            return;
85        }
86    } while (true);
87    SkASSERT(fUsed < 9);
88    insertCoincident(s1, s2, startPt);
89    insertCoincident(e1, e2, endPt);
90}
91
92int Intersections::insert(double one, double two, const _Point& pt) {
93    SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
94    int index;
95    for (index = 0; index < fUsed; ++index) {
96        double oldOne = fT[0][index];
97        double oldTwo = fT[1][index];
98        if (roughly_equal(oldOne, one) && roughly_equal(oldTwo, two)) {
99            if ((precisely_zero(one) && !precisely_zero(oldOne))
100                    || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
101                    || (precisely_zero(two) && !precisely_zero(oldTwo))
102                    || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
103                fT[0][index] = one;
104                fT[1][index] = two;
105                fPt[index] = pt;
106            }
107            return -1;
108        }
109    #if ONE_OFF_DEBUG
110        if (pt.roughlyEqual(fPt[index])) {
111            SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
112        }
113    #endif
114        if (fT[0][index] > one) {
115            break;
116        }
117    }
118    SkASSERT(fUsed < 9);
119    int remaining = fUsed - index;
120    if (remaining > 0) {
121        memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
122        memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
123        memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
124        fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1);
125        fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1);
126    }
127    fPt[index] = pt;
128    fT[0][index] = one;
129    fT[1][index] = two;
130    ++fUsed;
131    return index;
132}
133
134void Intersections::remove(double one, double two, const _Point& startPt, const _Point& endPt) {
135    for (int index = fUsed - 1; index >= 0; --index) {
136        if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two)
137                || startPt.approximatelyEqual(fPt[index])
138                || endPt.approximatelyEqual(fPt[index]))) {
139            SkASSERT(fUsed > 0);
140            removeOne(index);
141        }
142    }
143}
144
145void Intersections::removeOne(int index) {
146    int remaining = --fUsed - index;
147    if (remaining <= 0) {
148        return;
149    }
150    memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
151    memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
152    memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
153    SkASSERT(fIsCoincident[0] == 0);
154    int coBit = fIsCoincident[0] & (1 << index);
155    fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
156    SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
157    fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
158}
159