blob: dc779b86f521ea430c77cd7ce69ad3c49ee3d79d [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"
caryclark@google.com8d0a5242013-07-16 16:11:16 +00009#include "PathOpsTestCommon.h"
caryclark@google.com9166dcb2013-04-08 11:50:00 +000010#include "SkIntersections.h"
11#include "SkPathOpsRect.h"
12#include "SkReduceOrder.h"
13#include "Test.h"
14
caryclark@google.com02352d12013-11-25 15:05:05 +000015#if 0 // disable test until stroke reduction is supported
caryclark@google.com9166dcb2013-04-08 11:50:00 +000016static 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
23static 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
44static 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}
caryclark@google.com111417a2013-11-25 14:36:58 +000059#endif
caryclark@google.com9166dcb2013-04-08 11:50:00 +000060
tfarina@chromium.org78e7b4e2014-01-02 21:45:03 +000061DEF_TEST(PathOpsReduceOrderCubic, reporter) {
caryclark@google.com9166dcb2013-04-08 11:50:00 +000062 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;
caryclark@google.com927b7022013-11-25 14:18:21 +0000103#if 0
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000104 int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines
105 ? firstTestIndex : SK_MaxS32;
caryclark@google.com927b7022013-11-25 14:18:21 +0000106#endif
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000107 for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
108 const SkDCubic& cubic = pointDegenerates[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000109 SkASSERT(ValidCubic(cubic));
caryclark@google.com927b7022013-11-25 14:18:21 +0000110 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000111 if (order != 1) {
112 SkDebugf("[%d] pointDegenerates order=%d\n", static_cast<int>(index), order);
113 REPORTER_ASSERT(reporter, 0);
114 }
115 }
116 for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
117 const SkDCubic& cubic = notPointDegenerates[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000118 SkASSERT(ValidCubic(cubic));
caryclark@google.com927b7022013-11-25 14:18:21 +0000119 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000120 if (order == 1) {
121 SkDebugf("[%d] notPointDegenerates order=%d\n", static_cast<int>(index), order);
caryclark@google.com927b7022013-11-25 14:18:21 +0000122 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000123 REPORTER_ASSERT(reporter, 0);
124 }
125 }
126 for (index = firstLinesTest; index < lines_count; ++index) {
127 const SkDCubic& cubic = lines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000128 SkASSERT(ValidCubic(cubic));
caryclark@google.com927b7022013-11-25 14:18:21 +0000129 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000130 if (order != 2) {
131 SkDebugf("[%d] lines order=%d\n", static_cast<int>(index), order);
132 REPORTER_ASSERT(reporter, 0);
133 }
134 }
135 for (index = firstNotLinesTest; index < notLines_count; ++index) {
136 const SkDCubic& cubic = notLines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000137 SkASSERT(ValidCubic(cubic));
caryclark@google.com927b7022013-11-25 14:18:21 +0000138 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000139 if (order == 2) {
140 SkDebugf("[%d] notLines order=%d\n", static_cast<int>(index), order);
141 REPORTER_ASSERT(reporter, 0);
142 }
143 }
144 for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
145 const SkDCubic& cubic = modEpsilonLines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000146 SkASSERT(ValidCubic(cubic));
caryclark@google.com927b7022013-11-25 14:18:21 +0000147 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000148 if (order == 2) {
149 SkDebugf("[%d] line mod by epsilon order=%d\n", static_cast<int>(index), order);
150 REPORTER_ASSERT(reporter, 0);
151 }
152 }
153 for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
154 const SkDCubic& cubic = lessEpsilonLines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000155 SkASSERT(ValidCubic(cubic));
caryclark@google.com927b7022013-11-25 14:18:21 +0000156 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000157 if (order != 2) {
158 SkDebugf("[%d] line less by epsilon/2 order=%d\n", static_cast<int>(index), order);
caryclark@google.com927b7022013-11-25 14:18:21 +0000159 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000160 REPORTER_ASSERT(reporter, 0);
161 }
162 }
163 for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
164 const SkDCubic& cubic = negEpsilonLines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000165 SkASSERT(ValidCubic(cubic));
caryclark@google.com927b7022013-11-25 14:18:21 +0000166 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000167 if (order != 2) {
168 SkDebugf("[%d] line neg by epsilon/2 order=%d\n", static_cast<int>(index), order);
169 REPORTER_ASSERT(reporter, 0);
170 }
171 }
172 for (index = firstQuadraticPointTest; index < quadraticPoints_count; ++index) {
173 const SkDQuad& quad = quadraticPoints[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000174 SkASSERT(ValidQuad(quad));
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000175 SkDCubic cubic = quad.toCubic();
caryclark@google.com927b7022013-11-25 14:18:21 +0000176 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000177 if (order != 1) {
178 SkDebugf("[%d] point quad order=%d\n", static_cast<int>(index), order);
179 REPORTER_ASSERT(reporter, 0);
180 }
181 }
182 for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
183 const SkDQuad& quad = quadraticLines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000184 SkASSERT(ValidQuad(quad));
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000185 SkDCubic cubic = quad.toCubic();
caryclark@google.com927b7022013-11-25 14:18:21 +0000186 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000187 if (order != 2) {
188 SkDebugf("[%d] line quad order=%d\n", static_cast<int>(index), order);
189 REPORTER_ASSERT(reporter, 0);
190 }
191 }
192 for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
193 const SkDQuad& quad = quadraticModEpsilonLines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000194 SkASSERT(ValidQuad(quad));
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000195 SkDCubic cubic = quad.toCubic();
caryclark@google.com927b7022013-11-25 14:18:21 +0000196 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000197 if (order != 3) {
198 SkDebugf("[%d] line mod quad order=%d\n", static_cast<int>(index), order);
199 REPORTER_ASSERT(reporter, 0);
200 }
201 }
202
caryclark@google.com927b7022013-11-25 14:18:21 +0000203#if 0 // disable test until stroke reduction is supported
204// test if computed line end points are valid
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000205 for (index = firstComputedLinesTest; index < lines_count; ++index) {
206 const SkDCubic& cubic = lines[index];
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000207 SkASSERT(ValidCubic(cubic));
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000208 bool controlsInside = controls_inside(cubic);
209 order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics,
210 SkReduceOrder::kStroke_Style);
211 if (order == 2 && reducer.fLine[0] == reducer.fLine[1]) {
212 SkDebugf("[%d] line computed ends match order=%d\n", static_cast<int>(index), order);
213 REPORTER_ASSERT(reporter, 0);
214 }
215 if (controlsInside) {
216 if ( (reducer.fLine[0].fX != cubic[0].fX && reducer.fLine[0].fX != cubic[3].fX)
217 || (reducer.fLine[0].fY != cubic[0].fY && reducer.fLine[0].fY != cubic[3].fY)
218 || (reducer.fLine[1].fX != cubic[0].fX && reducer.fLine[1].fX != cubic[3].fX)
219 || (reducer.fLine[1].fY != cubic[0].fY && reducer.fLine[1].fY != cubic[3].fY)) {
220 SkDebugf("[%d] line computed ends order=%d\n", static_cast<int>(index), order);
221 REPORTER_ASSERT(reporter, 0);
222 }
223 } else {
224 // binary search for extrema, compare against actual results
225 // while a control point is outside of bounding box formed by end points, split
226 SkDRect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
227 find_tight_bounds(cubic, bounds);
228 if ( (!AlmostEqualUlps(reducer.fLine[0].fX, bounds.fLeft)
229 && !AlmostEqualUlps(reducer.fLine[0].fX, bounds.fRight))
230 || (!AlmostEqualUlps(reducer.fLine[0].fY, bounds.fTop)
231 && !AlmostEqualUlps(reducer.fLine[0].fY, bounds.fBottom))
232 || (!AlmostEqualUlps(reducer.fLine[1].fX, bounds.fLeft)
233 && !AlmostEqualUlps(reducer.fLine[1].fX, bounds.fRight))
234 || (!AlmostEqualUlps(reducer.fLine[1].fY, bounds.fTop)
235 && !AlmostEqualUlps(reducer.fLine[1].fY, bounds.fBottom))) {
236 SkDebugf("[%d] line computed tight bounds order=%d\n", static_cast<int>(index), order);
237 REPORTER_ASSERT(reporter, 0);
238 }
239 }
240 }
caryclark@google.com927b7022013-11-25 14:18:21 +0000241#endif
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000242}