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