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