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