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 "CurveIntersection.h"
8 #include "CubicIntersection_TestData.h"
9 #include "Intersection_Tests.h"
10 #include "QuadraticIntersection_TestData.h"
11 #include "TestUtilities.h"
12
CubicReduceOrder_Test()13 void CubicReduceOrder_Test() {
14 size_t index;
15 Cubic reduce;
16 int order;
17 enum {
18 RunAll,
19 RunPointDegenerates,
20 RunNotPointDegenerates,
21 RunLines,
22 RunNotLines,
23 RunModEpsilonLines,
24 RunLessEpsilonLines,
25 RunNegEpsilonLines,
26 RunQuadraticLines,
27 RunQuadraticModLines,
28 RunComputedLines,
29 RunNone
30 } run = RunAll;
31 int firstTestIndex = 0;
32 #if 0
33 run = RunComputedLines;
34 firstTestIndex = 18;
35 #endif
36 int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates ? firstTestIndex : SK_MaxS32;
37 int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates ? firstTestIndex : SK_MaxS32;
38 int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
39 int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
40 int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines ? firstTestIndex : SK_MaxS32;
41 int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines ? firstTestIndex : SK_MaxS32;
42 int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines ? firstTestIndex : SK_MaxS32;
43 int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines ? firstTestIndex : SK_MaxS32;
44 int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines ? firstTestIndex : SK_MaxS32;
45 int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines ? firstTestIndex : SK_MaxS32;
46
47 for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
48 const Cubic& cubic = pointDegenerates[index];
49 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
50 kReduceOrder_TreatAsFill);
51 if (order != 1) {
52 SkDebugf("[%d] pointDegenerates order=%d\n", (int) index, order);
53 }
54 }
55 for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
56 const Cubic& cubic = notPointDegenerates[index];
57 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
58 kReduceOrder_TreatAsFill);
59 if (order == 1) {
60 SkDebugf("[%d] notPointDegenerates order=%d\n", (int) index, order);
61 }
62 }
63 for (index = firstLinesTest; index < lines_count; ++index) {
64 const Cubic& cubic = lines[index];
65 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
66 kReduceOrder_TreatAsFill);
67 if (order != 2) {
68 SkDebugf("[%d] lines order=%d\n", (int) index, order);
69 }
70 }
71 for (index = firstNotLinesTest; index < notLines_count; ++index) {
72 const Cubic& cubic = notLines[index];
73 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
74 kReduceOrder_TreatAsFill);
75 if (order == 2) {
76 SkDebugf("[%d] notLines order=%d\n", (int) index, order);
77 }
78 }
79 for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
80 const Cubic& cubic = modEpsilonLines[index];
81 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
82 kReduceOrder_TreatAsFill);
83 if (order == 2) {
84 SkDebugf("[%d] line mod by epsilon order=%d\n", (int) index, order);
85 }
86 }
87 for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
88 const Cubic& cubic = lessEpsilonLines[index];
89 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
90 kReduceOrder_TreatAsFill);
91 if (order != 2) {
92 SkDebugf("[%d] line less by epsilon/2 order=%d\n", (int) index, order);
93 }
94 }
95 for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
96 const Cubic& cubic = negEpsilonLines[index];
97 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
98 kReduceOrder_TreatAsFill);
99 if (order != 2) {
100 SkDebugf("[%d] line neg by epsilon/2 order=%d\n", (int) index, order);
101 }
102 }
103 for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
104 const Quadratic& quad = quadraticLines[index];
105 Cubic cubic;
106 quad_to_cubic(quad, cubic);
107 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
108 kReduceOrder_TreatAsFill);
109 if (order != 2) {
110 SkDebugf("[%d] line quad order=%d\n", (int) index, order);
111 }
112 }
113 for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
114 const Quadratic& quad = quadraticModEpsilonLines[index];
115 Cubic cubic;
116 quad_to_cubic(quad, cubic);
117 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
118 kReduceOrder_TreatAsFill);
119 if (order != 3) {
120 SkDebugf("[%d] line mod quad order=%d\n", (int) index, order);
121 }
122 }
123
124 // test if computed line end points are valid
125 for (index = firstComputedLinesTest; index < lines_count; ++index) {
126 const Cubic& cubic = lines[index];
127 bool controlsInside = controls_inside(cubic);
128 order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
129 kReduceOrder_TreatAsFill);
130 if (reduce[0].x == reduce[1].x && reduce[0].y == reduce[1].y) {
131 SkDebugf("[%d] line computed ends match order=%d\n", (int) index, order);
132 }
133 if (controlsInside) {
134 if ( (reduce[0].x != cubic[0].x && reduce[0].x != cubic[3].x)
135 || (reduce[0].y != cubic[0].y && reduce[0].y != cubic[3].y)
136 || (reduce[1].x != cubic[0].x && reduce[1].x != cubic[3].x)
137 || (reduce[1].y != cubic[0].y && reduce[1].y != cubic[3].y)) {
138 SkDebugf("[%d] line computed ends order=%d\n", (int) index, order);
139 }
140 } else {
141 // binary search for extrema, compare against actual results
142 // while a control point is outside of bounding box formed by end points, split
143 _Rect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
144 find_tight_bounds(cubic, bounds);
145 if ( (!AlmostEqualUlps(reduce[0].x, bounds.left) && !AlmostEqualUlps(reduce[0].x, bounds.right))
146 || (!AlmostEqualUlps(reduce[0].y, bounds.top) && !AlmostEqualUlps(reduce[0].y, bounds.bottom))
147 || (!AlmostEqualUlps(reduce[1].x, bounds.left) && !AlmostEqualUlps(reduce[1].x, bounds.right))
148 || (!AlmostEqualUlps(reduce[1].y, bounds.top) && !AlmostEqualUlps(reduce[1].y, bounds.bottom))) {
149 SkDebugf("[%d] line computed tight bounds order=%d\n", (int) index, order);
150 }
151
152 }
153 }
154 }
155