blob: 3de45cb4c71b0580e6ede1896f58014823800e39 [file] [log] [blame]
caryclark@google.com235f56a2012-09-14 14:19:30 +00001/*
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 */
skia.committer@gmail.com055c7c22012-09-15 02:01:41 +00007
caryclark@google.com235f56a2012-09-14 14:19:30 +00008#include "DataTypes.h"
9#include "Intersections.h"
10
caryclark@google.com45a8fc62013-02-14 15:29:11 +000011void 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];
skia.committer@gmail.com044679e2013-02-15 07:16:57 +000051 bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2])
caryclark@google.com45a8fc62013-02-14 15:29:11 +000052 || startPt.approximatelyEqual(fPt[iEnd2]);
53 bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2])
54 || endPt.approximatelyEqual(fPt[iEnd2]);
caryclark@google.com73ca6242013-01-17 21:02:47 +000055 if ((s1in | e1in) & (s2in | e2in)) {
caryclark@google.com45a8fc62013-02-14 15:29:11 +000056 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;
caryclark@google.com73ca6242013-01-17 21:02:47 +000062 }
caryclark@google.com45a8fc62013-02-14 15:29:11 +000063 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;
caryclark@google.com73ca6242013-01-17 21:02:47 +000069 }
caryclark@google.com45a8fc62013-02-14 15:29:11 +000070 if (s2 > e2) {
71 SkTSwap(cs2, ce2);
72 SkTSwap(i2, iEnd2);
caryclark@google.com73ca6242013-01-17 21:02:47 +000073 }
caryclark@google.com45a8fc62013-02-14 15:29:11 +000074 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;
caryclark@google.com73ca6242013-01-17 21:02:47 +000083 }
84 return;
85 }
caryclark@google.com45a8fc62013-02-14 15:29:11 +000086 } while (true);
87 SkASSERT(fUsed < 9);
88 insertCoincident(s1, s2, startPt);
89 insertCoincident(e1, e2, endPt);
caryclark@google.com73ca6242013-01-17 21:02:47 +000090}
91
caryclark@google.com45a8fc62013-02-14 15:29:11 +000092int Intersections::insert(double one, double two, const _Point& pt) {
caryclark@google.comaa358312013-01-29 20:28:49 +000093 SkASSERT(fUsed <= 1 || fT[0][0] < fT[0][1]);
caryclark@google.com73ca6242013-01-17 21:02:47 +000094 int index;
95 for (index = 0; index < fUsed; ++index) {
caryclark@google.com45a8fc62013-02-14 15:29:11 +000096 if (approximately_equal(fT[0][index], one) || pt.approximatelyEqual(fPt[index])) {
97 return -1;
caryclark@google.com73ca6242013-01-17 21:02:47 +000098 }
99 if (fT[0][index] > one) {
100 break;
101 }
102 }
caryclark@google.comaa358312013-01-29 20:28:49 +0000103 SkASSERT(fUsed < 9);
caryclark@google.com73ca6242013-01-17 21:02:47 +0000104 int remaining = fUsed - index;
105 if (remaining > 0) {
caryclark@google.com45a8fc62013-02-14 15:29:11 +0000106 memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
caryclark@google.com73ca6242013-01-17 21:02:47 +0000107 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);
caryclark@google.com45a8fc62013-02-14 15:29:11 +0000109 fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1);
110 fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1);
caryclark@google.com73ca6242013-01-17 21:02:47 +0000111 }
caryclark@google.com45a8fc62013-02-14 15:29:11 +0000112 fPt[index] = pt;
caryclark@google.com73ca6242013-01-17 21:02:47 +0000113 fT[0][index] = one;
114 fT[1][index] = two;
115 ++fUsed;
caryclark@google.com45a8fc62013-02-14 15:29:11 +0000116 return index;
caryclark@google.com73ca6242013-01-17 21:02:47 +0000117}
118
caryclark@google.com45a8fc62013-02-14 15:29:11 +0000119void Intersections::remove(double one, double two, const _Point& startPt, const _Point& endPt) {
120 for (int index = fUsed - 1; index >= 0; --index) {
121 if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two)
122 || startPt.approximatelyEqual(fPt[index])
123 || endPt.approximatelyEqual(fPt[index]))) {
124 SkASSERT(fUsed > 0);
caryclark@google.com47d73da2013-02-17 01:41:25 +0000125 removeOne(index);
caryclark@google.com73ca6242013-01-17 21:02:47 +0000126 }
127 }
caryclark@google.combeda3892013-02-07 13:13:41 +0000128}
caryclark@google.com47d73da2013-02-17 01:41:25 +0000129
130void Intersections::removeOne(int index) {
131 int remaining = --fUsed - index;
132 if (remaining <= 0) {
133 return;
134 }
135 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
136 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
137 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
138 SkASSERT(fIsCoincident[0] == 0);
139 int coBit = fIsCoincident[0] & (1 << index);
140 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
141 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
142 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
143}