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
16static 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}
59#endif
60
61DEF_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