PathOpsCubicReduceOrderTest.cpp revision 58190644c30e1c4aa8e527f3503c58f841e0fcf3 
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
15static bool controls_inside(const SkDCubic& cubic) {
16    return between(cubic[0].fX, cubic[1].fX, cubic[3].fX)
17            && between(cubic[0].fX, cubic[2].fX, cubic[3].fX)
18            && between(cubic[0].fY, cubic[1].fY, cubic[3].fY)
19            && between(cubic[0].fY, cubic[2].fY, cubic[3].fY);
20}
21
22static bool tiny(const SkDCubic& cubic) {
23    int index, minX, maxX, minY, maxY;
24    minX = maxX = minY = maxY = 0;
25    for (index = 1; index < 4; ++index) {
26        if (cubic[minX].fX > cubic[index].fX) {
27            minX = index;
28        }
29        if (cubic[minY].fY > cubic[index].fY) {
30            minY = index;
31        }
32        if (cubic[maxX].fX < cubic[index].fX) {
33            maxX = index;
34        }
35        if (cubic[maxY].fY < cubic[index].fY) {
36            maxY = index;
37        }
38    }
39    return     approximately_equal(cubic[maxX].fX, cubic[minX].fX)
40            && approximately_equal(cubic[maxY].fY, cubic[minY].fY);
41}
42
43static void find_tight_bounds(const SkDCubic& cubic, SkDRect& bounds) {
44    SkDCubicPair cubicPair = cubic.chopAt(0.5);
45    if (!tiny(cubicPair.first()) && !controls_inside(cubicPair.first())) {
46        find_tight_bounds(cubicPair.first(), bounds);
47    } else {
48        bounds.add(cubicPair.first()[0]);
49        bounds.add(cubicPair.first()[3]);
50    }
51    if (!tiny(cubicPair.second()) && !controls_inside(cubicPair.second())) {
52        find_tight_bounds(cubicPair.second(), bounds);
53    } else {
54        bounds.add(cubicPair.second()[0]);
55        bounds.add(cubicPair.second()[3]);
56    }
57}
58
59static void PathOpsReduceOrderCubicTest(skiatest::Reporter* reporter) {
60    size_t index;
61    SkReduceOrder reducer;
62    int order;
63    enum {
64        RunAll,
65        RunPointDegenerates,
66        RunNotPointDegenerates,
67        RunLines,
68        RunNotLines,
69        RunModEpsilonLines,
70        RunLessEpsilonLines,
71        RunNegEpsilonLines,
72        RunQuadraticLines,
73        RunQuadraticPoints,
74        RunQuadraticModLines,
75        RunComputedLines,
76        RunNone
77    } run = RunAll;
78    int firstTestIndex = 0;
79#if 0
80    run = RunComputedLines;
81    firstTestIndex = 18;
82#endif
83    int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates
84            ? firstTestIndex : SK_MaxS32;
85    int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates
86            ? firstTestIndex : SK_MaxS32;
87    int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
88    int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
89    int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines
90            ? firstTestIndex : SK_MaxS32;
91    int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines
92            ? firstTestIndex : SK_MaxS32;
93    int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines
94            ? firstTestIndex : SK_MaxS32;
95    int firstQuadraticPointTest = run == RunAll ? 0 : run == RunQuadraticPoints
96            ? firstTestIndex : SK_MaxS32;
97    int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines
98            ? firstTestIndex : SK_MaxS32;
99    int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines
100            ? firstTestIndex : SK_MaxS32;
101    int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines
102            ? firstTestIndex : SK_MaxS32;
103
104    for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
105        const SkDCubic& cubic = pointDegenerates[index];
106        SkASSERT(ValidCubic(cubic));
107        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
108        if (order != 1) {
109            SkDebugf("[%d] pointDegenerates order=%d\n", static_cast<int>(index), order);
110            REPORTER_ASSERT(reporter, 0);
111        }
112    }
113    for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
114        const SkDCubic& cubic = notPointDegenerates[index];
115        SkASSERT(ValidCubic(cubic));
116        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
117        if (order == 1) {
118            SkDebugf("[%d] notPointDegenerates order=%d\n", static_cast<int>(index), order);
119            REPORTER_ASSERT(reporter, 0);
120        }
121    }
122    for (index = firstLinesTest; index < lines_count; ++index) {
123        const SkDCubic& cubic = lines[index];
124        SkASSERT(ValidCubic(cubic));
125        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
126        if (order != 2) {
127            SkDebugf("[%d] lines order=%d\n", static_cast<int>(index), order);
128            REPORTER_ASSERT(reporter, 0);
129        }
130    }
131    for (index = firstNotLinesTest; index < notLines_count; ++index) {
132        const SkDCubic& cubic = notLines[index];
133        SkASSERT(ValidCubic(cubic));
134        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
135        if (order == 2) {
136            SkDebugf("[%d] notLines order=%d\n", static_cast<int>(index), order);
137            REPORTER_ASSERT(reporter, 0);
138       }
139    }
140    for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
141        const SkDCubic& cubic = modEpsilonLines[index];
142        SkASSERT(ValidCubic(cubic));
143        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
144        if (order == 2) {
145            SkDebugf("[%d] line mod by epsilon order=%d\n", static_cast<int>(index), order);
146            REPORTER_ASSERT(reporter, 0);
147        }
148    }
149    for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
150        const SkDCubic& cubic = lessEpsilonLines[index];
151        SkASSERT(ValidCubic(cubic));
152        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
153        if (order != 2) {
154            SkDebugf("[%d] line less by epsilon/2 order=%d\n", static_cast<int>(index), order);
155            REPORTER_ASSERT(reporter, 0);
156        }
157    }
158    for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
159        const SkDCubic& cubic = negEpsilonLines[index];
160        SkASSERT(ValidCubic(cubic));
161        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
162        if (order != 2) {
163            SkDebugf("[%d] line neg by epsilon/2 order=%d\n", static_cast<int>(index), order);
164            REPORTER_ASSERT(reporter, 0);
165        }
166    }
167    for (index = firstQuadraticPointTest; index < quadraticPoints_count; ++index) {
168        const SkDQuad& quad = quadraticPoints[index];
169        SkASSERT(ValidQuad(quad));
170        SkDCubic cubic = quad.toCubic();
171        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
172        if (order != 1) {
173            SkDebugf("[%d] point quad order=%d\n", static_cast<int>(index), order);
174            REPORTER_ASSERT(reporter, 0);
175        }
176    }
177    for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
178        const SkDQuad& quad = quadraticLines[index];
179        SkASSERT(ValidQuad(quad));
180        SkDCubic cubic = quad.toCubic();
181        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
182        if (order != 2) {
183            SkDebugf("[%d] line quad order=%d\n", static_cast<int>(index), order);
184            REPORTER_ASSERT(reporter, 0);
185        }
186    }
187    for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
188        const SkDQuad& quad = quadraticModEpsilonLines[index];
189        SkASSERT(ValidQuad(quad));
190        SkDCubic cubic = quad.toCubic();
191        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
192        if (order != 3) {
193            SkDebugf("[%d] line mod quad order=%d\n", static_cast<int>(index), order);
194            REPORTER_ASSERT(reporter, 0);
195        }
196    }
197
198    // test if computed line end points are valid
199    for (index = firstComputedLinesTest; index < lines_count; ++index) {
200        const SkDCubic& cubic = lines[index];
201        SkASSERT(ValidCubic(cubic));
202        bool controlsInside = controls_inside(cubic);
203        order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics,
204                SkReduceOrder::kStroke_Style);
205        if (order == 2 && reducer.fLine[0] == reducer.fLine[1]) {
206            SkDebugf("[%d] line computed ends match order=%d\n", static_cast<int>(index), order);
207            REPORTER_ASSERT(reporter, 0);
208        }
209        if (controlsInside) {
210            if (       (reducer.fLine[0].fX != cubic[0].fX && reducer.fLine[0].fX != cubic[3].fX)
211                    || (reducer.fLine[0].fY != cubic[0].fY && reducer.fLine[0].fY != cubic[3].fY)
212                    || (reducer.fLine[1].fX != cubic[0].fX && reducer.fLine[1].fX != cubic[3].fX)
213                    || (reducer.fLine[1].fY != cubic[0].fY && reducer.fLine[1].fY != cubic[3].fY)) {
214                SkDebugf("[%d] line computed ends order=%d\n", static_cast<int>(index), order);
215                REPORTER_ASSERT(reporter, 0);
216            }
217        } else {
218            // binary search for extrema, compare against actual results
219                // while a control point is outside of bounding box formed by end points, split
220            SkDRect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
221            find_tight_bounds(cubic, bounds);
222            if (      (!AlmostEqualUlps(reducer.fLine[0].fX, bounds.fLeft)
223                    && !AlmostEqualUlps(reducer.fLine[0].fX, bounds.fRight))
224                   || (!AlmostEqualUlps(reducer.fLine[0].fY, bounds.fTop)
225                    && !AlmostEqualUlps(reducer.fLine[0].fY, bounds.fBottom))
226                   || (!AlmostEqualUlps(reducer.fLine[1].fX, bounds.fLeft)
227                    && !AlmostEqualUlps(reducer.fLine[1].fX, bounds.fRight))
228                   || (!AlmostEqualUlps(reducer.fLine[1].fY, bounds.fTop)
229                    && !AlmostEqualUlps(reducer.fLine[1].fY, bounds.fBottom))) {
230                SkDebugf("[%d] line computed tight bounds order=%d\n", static_cast<int>(index), order);
231                REPORTER_ASSERT(reporter, 0);
232            }
233        }
234    }
235}
236
237#include "TestClassDef.h"
238DEFINE_TESTCLASS_SHORT(PathOpsReduceOrderCubicTest)
239