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