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 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
