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 #include "src/pathops/SkIntersections.h"
8 #include "src/pathops/SkPathOpsRect.h"
9 #include "src/pathops/SkReduceOrder.h"
10 #include "tests/PathOpsCubicIntersectionTestData.h"
11 #include "tests/PathOpsQuadIntersectionTestData.h"
12 #include "tests/PathOpsTestCommon.h"
13 #include "tests/Test.h"
14
15 using namespace PathOpsCubicIntersectionTestData;
16
17 #if 0 // disable test until stroke reduction is supported
18 static bool controls_inside(const SkDCubic& cubic) {
19 return between(cubic[0].fX, cubic[1].fX, cubic[3].fX)
20 && between(cubic[0].fX, cubic[2].fX, cubic[3].fX)
21 && between(cubic[0].fY, cubic[1].fY, cubic[3].fY)
22 && between(cubic[0].fY, cubic[2].fY, cubic[3].fY);
23 }
24
25 static bool tiny(const SkDCubic& cubic) {
26 int index, minX, maxX, minY, maxY;
27 minX = maxX = minY = maxY = 0;
28 for (index = 1; index < 4; ++index) {
29 if (cubic[minX].fX > cubic[index].fX) {
30 minX = index;
31 }
32 if (cubic[minY].fY > cubic[index].fY) {
33 minY = index;
34 }
35 if (cubic[maxX].fX < cubic[index].fX) {
36 maxX = index;
37 }
38 if (cubic[maxY].fY < cubic[index].fY) {
39 maxY = index;
40 }
41 }
42 return approximately_equal(cubic[maxX].fX, cubic[minX].fX)
43 && approximately_equal(cubic[maxY].fY, cubic[minY].fY);
44 }
45
46 static void find_tight_bounds(const SkDCubic& cubic, SkDRect& bounds) {
47 SkDCubicPair cubicPair = cubic.chopAt(0.5);
48 if (!tiny(cubicPair.first()) && !controls_inside(cubicPair.first())) {
49 find_tight_bounds(cubicPair.first(), bounds);
50 } else {
51 bounds.add(cubicPair.first()[0]);
52 bounds.add(cubicPair.first()[3]);
53 }
54 if (!tiny(cubicPair.second()) && !controls_inside(cubicPair.second())) {
55 find_tight_bounds(cubicPair.second(), bounds);
56 } else {
57 bounds.add(cubicPair.second()[0]);
58 bounds.add(cubicPair.second()[3]);
59 }
60 }
61 #endif
62
DEF_TEST(PathOpsReduceOrderCubic,reporter)63 DEF_TEST(PathOpsReduceOrderCubic, reporter) {
64 size_t index;
65 SkReduceOrder reducer;
66 int order;
67 enum {
68 RunAll,
69 RunPointDegenerates,
70 RunNotPointDegenerates,
71 RunLines,
72 RunNotLines,
73 RunModEpsilonLines,
74 RunLessEpsilonLines,
75 RunNegEpsilonLines,
76 RunQuadraticLines,
77 RunQuadraticPoints,
78 RunQuadraticModLines,
79 RunComputedLines,
80 RunNone
81 } run = RunAll;
82 int firstTestIndex = 0;
83 #if 0
84 run = RunComputedLines;
85 firstTestIndex = 18;
86 #endif
87 int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates
88 ? firstTestIndex : SK_MaxS32;
89 int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates
90 ? firstTestIndex : SK_MaxS32;
91 int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
92 int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
93 int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines
94 ? firstTestIndex : SK_MaxS32;
95 int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines
96 ? firstTestIndex : SK_MaxS32;
97 int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines
98 ? firstTestIndex : SK_MaxS32;
99 int firstQuadraticPointTest = run == RunAll ? 0 : run == RunQuadraticPoints
100 ? firstTestIndex : SK_MaxS32;
101 int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines
102 ? firstTestIndex : SK_MaxS32;
103 int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines
104 ? firstTestIndex : SK_MaxS32;
105 #if 0
106 int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines
107 ? firstTestIndex : SK_MaxS32;
108 #endif
109 for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
110 const CubicPts& c = pointDegenerates[index];
111 SkDCubic cubic;
112 cubic.debugSet(c.fPts);
113 SkASSERT(ValidCubic(cubic));
114 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
115 if (order != 1) {
116 SkDebugf("[%d] pointDegenerates order=%d\n", static_cast<int>(index), order);
117 REPORTER_ASSERT(reporter, 0);
118 }
119 }
120 for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
121 const CubicPts& c = notPointDegenerates[index];
122 SkDCubic cubic;
123 cubic.debugSet(c.fPts);
124 SkASSERT(ValidCubic(cubic));
125 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
126 if (order == 1) {
127 SkDebugf("[%d] notPointDegenerates order=%d\n", static_cast<int>(index), order);
128 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
129 REPORTER_ASSERT(reporter, 0);
130 }
131 }
132 for (index = firstLinesTest; index < lines_count; ++index) {
133 const CubicPts& c = lines[index];
134 SkDCubic cubic;
135 cubic.debugSet(c.fPts);
136 SkASSERT(ValidCubic(cubic));
137 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
138 if (order != 2) {
139 SkDebugf("[%d] lines order=%d\n", static_cast<int>(index), order);
140 REPORTER_ASSERT(reporter, 0);
141 }
142 }
143 for (index = firstNotLinesTest; index < notLines_count; ++index) {
144 const CubicPts& c = notLines[index];
145 SkDCubic cubic;
146 cubic.debugSet(c.fPts);
147 SkASSERT(ValidCubic(cubic));
148 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
149 if (order == 2) {
150 SkDebugf("[%d] notLines order=%d\n", static_cast<int>(index), order);
151 REPORTER_ASSERT(reporter, 0);
152 }
153 }
154 for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
155 const CubicPts& c = modEpsilonLines[index];
156 SkDCubic cubic;
157 cubic.debugSet(c.fPts);
158 SkASSERT(ValidCubic(cubic));
159 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
160 if (order == 2) {
161 SkDebugf("[%d] line mod by epsilon order=%d\n", static_cast<int>(index), order);
162 REPORTER_ASSERT(reporter, 0);
163 }
164 }
165 for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
166 const CubicPts& c = lessEpsilonLines[index];
167 SkDCubic cubic;
168 cubic.debugSet(c.fPts);
169 SkASSERT(ValidCubic(cubic));
170 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
171 if (order != 2) {
172 SkDebugf("[%d] line less by epsilon/2 order=%d\n", static_cast<int>(index), order);
173 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
174 REPORTER_ASSERT(reporter, 0);
175 }
176 }
177 for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
178 const CubicPts& c = negEpsilonLines[index];
179 SkDCubic cubic;
180 cubic.debugSet(c.fPts);
181 SkASSERT(ValidCubic(cubic));
182 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
183 if (order != 2) {
184 SkDebugf("[%d] line neg by epsilon/2 order=%d\n", static_cast<int>(index), order);
185 REPORTER_ASSERT(reporter, 0);
186 }
187 }
188 for (index = firstQuadraticPointTest; index < quadraticPoints_count; ++index) {
189 const QuadPts& q = quadraticPoints[index];
190 SkDQuad quad;
191 quad.debugSet(q.fPts);
192 SkASSERT(ValidQuad(quad));
193 SkDCubic cubic = quad.debugToCubic();
194 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
195 if (order != 1) {
196 SkDebugf("[%d] point quad order=%d\n", static_cast<int>(index), order);
197 REPORTER_ASSERT(reporter, 0);
198 }
199 }
200 for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
201 const QuadPts& q = quadraticLines[index];
202 SkDQuad quad;
203 quad.debugSet(q.fPts);
204 SkASSERT(ValidQuad(quad));
205 SkDCubic cubic = quad.debugToCubic();
206 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
207 if (order != 2) {
208 SkDebugf("[%d] line quad order=%d\n", static_cast<int>(index), order);
209 REPORTER_ASSERT(reporter, 0);
210 }
211 }
212 for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
213 const QuadPts& q = quadraticModEpsilonLines[index];
214 SkDQuad quad;
215 quad.debugSet(q.fPts);
216 SkASSERT(ValidQuad(quad));
217 SkDCubic cubic = quad.debugToCubic();
218 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
219 if (order != 3) {
220 SkDebugf("[%d] line mod quad order=%d\n", static_cast<int>(index), order);
221 REPORTER_ASSERT(reporter, 0);
222 }
223 }
224
225 #if 0 // disable test until stroke reduction is supported
226 // test if computed line end points are valid
227 for (index = firstComputedLinesTest; index < lines_count; ++index) {
228 const SkDCubic& cubic = lines[index];
229 SkASSERT(ValidCubic(cubic));
230 bool controlsInside = controls_inside(cubic);
231 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics,
232 SkReduceOrder::kStroke_Style);
233 if (order == 2 && reducer.fLine[0] == reducer.fLine[1]) {
234 SkDebugf("[%d] line computed ends match order=%d\n", static_cast<int>(index), order);
235 REPORTER_ASSERT(reporter, 0);
236 }
237 if (controlsInside) {
238 if ( (reducer.fLine[0].fX != cubic[0].fX && reducer.fLine[0].fX != cubic[3].fX)
239 || (reducer.fLine[0].fY != cubic[0].fY && reducer.fLine[0].fY != cubic[3].fY)
240 || (reducer.fLine[1].fX != cubic[0].fX && reducer.fLine[1].fX != cubic[3].fX)
241 || (reducer.fLine[1].fY != cubic[0].fY && reducer.fLine[1].fY != cubic[3].fY)) {
242 SkDebugf("[%d] line computed ends order=%d\n", static_cast<int>(index), order);
243 REPORTER_ASSERT(reporter, 0);
244 }
245 } else {
246 // binary search for extrema, compare against actual results
247 // while a control point is outside of bounding box formed by end points, split
248 SkDRect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
249 find_tight_bounds(cubic, bounds);
250 if ( (!AlmostEqualUlps(reducer.fLine[0].fX, bounds.fLeft)
251 && !AlmostEqualUlps(reducer.fLine[0].fX, bounds.fRight))
252 || (!AlmostEqualUlps(reducer.fLine[0].fY, bounds.fTop)
253 && !AlmostEqualUlps(reducer.fLine[0].fY, bounds.fBottom))
254 || (!AlmostEqualUlps(reducer.fLine[1].fX, bounds.fLeft)
255 && !AlmostEqualUlps(reducer.fLine[1].fX, bounds.fRight))
256 || (!AlmostEqualUlps(reducer.fLine[1].fY, bounds.fTop)
257 && !AlmostEqualUlps(reducer.fLine[1].fY, bounds.fBottom))) {
258 SkDebugf("[%d] line computed tight bounds order=%d\n", static_cast<int>(index), order);
259 REPORTER_ASSERT(reporter, 0);
260 }
261 }
262 }
263 #endif
264 }
265