123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262 |
- /*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "src/pathops/SkIntersections.h"
- #include "src/pathops/SkPathOpsRect.h"
- #include "src/pathops/SkReduceOrder.h"
- #include "tests/PathOpsCubicIntersectionTestData.h"
- #include "tests/PathOpsQuadIntersectionTestData.h"
- #include "tests/PathOpsTestCommon.h"
- #include "tests/Test.h"
- #if 0 // disable test until stroke reduction is supported
- static bool controls_inside(const SkDCubic& cubic) {
- return between(cubic[0].fX, cubic[1].fX, cubic[3].fX)
- && between(cubic[0].fX, cubic[2].fX, cubic[3].fX)
- && between(cubic[0].fY, cubic[1].fY, cubic[3].fY)
- && between(cubic[0].fY, cubic[2].fY, cubic[3].fY);
- }
- static bool tiny(const SkDCubic& cubic) {
- int index, minX, maxX, minY, maxY;
- minX = maxX = minY = maxY = 0;
- for (index = 1; index < 4; ++index) {
- if (cubic[minX].fX > cubic[index].fX) {
- minX = index;
- }
- if (cubic[minY].fY > cubic[index].fY) {
- minY = index;
- }
- if (cubic[maxX].fX < cubic[index].fX) {
- maxX = index;
- }
- if (cubic[maxY].fY < cubic[index].fY) {
- maxY = index;
- }
- }
- return approximately_equal(cubic[maxX].fX, cubic[minX].fX)
- && approximately_equal(cubic[maxY].fY, cubic[minY].fY);
- }
- static void find_tight_bounds(const SkDCubic& cubic, SkDRect& bounds) {
- SkDCubicPair cubicPair = cubic.chopAt(0.5);
- if (!tiny(cubicPair.first()) && !controls_inside(cubicPair.first())) {
- find_tight_bounds(cubicPair.first(), bounds);
- } else {
- bounds.add(cubicPair.first()[0]);
- bounds.add(cubicPair.first()[3]);
- }
- if (!tiny(cubicPair.second()) && !controls_inside(cubicPair.second())) {
- find_tight_bounds(cubicPair.second(), bounds);
- } else {
- bounds.add(cubicPair.second()[0]);
- bounds.add(cubicPair.second()[3]);
- }
- }
- #endif
- DEF_TEST(PathOpsReduceOrderCubic, reporter) {
- size_t index;
- SkReduceOrder reducer;
- int order;
- enum {
- RunAll,
- RunPointDegenerates,
- RunNotPointDegenerates,
- RunLines,
- RunNotLines,
- RunModEpsilonLines,
- RunLessEpsilonLines,
- RunNegEpsilonLines,
- RunQuadraticLines,
- RunQuadraticPoints,
- RunQuadraticModLines,
- RunComputedLines,
- RunNone
- } run = RunAll;
- int firstTestIndex = 0;
- #if 0
- run = RunComputedLines;
- firstTestIndex = 18;
- #endif
- int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates
- ? firstTestIndex : SK_MaxS32;
- int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates
- ? firstTestIndex : SK_MaxS32;
- int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
- int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
- int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines
- ? firstTestIndex : SK_MaxS32;
- int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines
- ? firstTestIndex : SK_MaxS32;
- int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines
- ? firstTestIndex : SK_MaxS32;
- int firstQuadraticPointTest = run == RunAll ? 0 : run == RunQuadraticPoints
- ? firstTestIndex : SK_MaxS32;
- int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines
- ? firstTestIndex : SK_MaxS32;
- int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines
- ? firstTestIndex : SK_MaxS32;
- #if 0
- int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines
- ? firstTestIndex : SK_MaxS32;
- #endif
- for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
- const CubicPts& c = pointDegenerates[index];
- SkDCubic cubic;
- cubic.debugSet(c.fPts);
- SkASSERT(ValidCubic(cubic));
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order != 1) {
- SkDebugf("[%d] pointDegenerates order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
- const CubicPts& c = notPointDegenerates[index];
- SkDCubic cubic;
- cubic.debugSet(c.fPts);
- SkASSERT(ValidCubic(cubic));
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order == 1) {
- SkDebugf("[%d] notPointDegenerates order=%d\n", static_cast<int>(index), order);
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstLinesTest; index < lines_count; ++index) {
- const CubicPts& c = lines[index];
- SkDCubic cubic;
- cubic.debugSet(c.fPts);
- SkASSERT(ValidCubic(cubic));
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order != 2) {
- SkDebugf("[%d] lines order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstNotLinesTest; index < notLines_count; ++index) {
- const CubicPts& c = notLines[index];
- SkDCubic cubic;
- cubic.debugSet(c.fPts);
- SkASSERT(ValidCubic(cubic));
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order == 2) {
- SkDebugf("[%d] notLines order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
- const CubicPts& c = modEpsilonLines[index];
- SkDCubic cubic;
- cubic.debugSet(c.fPts);
- SkASSERT(ValidCubic(cubic));
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order == 2) {
- SkDebugf("[%d] line mod by epsilon order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
- const CubicPts& c = lessEpsilonLines[index];
- SkDCubic cubic;
- cubic.debugSet(c.fPts);
- SkASSERT(ValidCubic(cubic));
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order != 2) {
- SkDebugf("[%d] line less by epsilon/2 order=%d\n", static_cast<int>(index), order);
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
- const CubicPts& c = negEpsilonLines[index];
- SkDCubic cubic;
- cubic.debugSet(c.fPts);
- SkASSERT(ValidCubic(cubic));
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order != 2) {
- SkDebugf("[%d] line neg by epsilon/2 order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstQuadraticPointTest; index < quadraticPoints_count; ++index) {
- const QuadPts& q = quadraticPoints[index];
- SkDQuad quad;
- quad.debugSet(q.fPts);
- SkASSERT(ValidQuad(quad));
- SkDCubic cubic = quad.debugToCubic();
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order != 1) {
- SkDebugf("[%d] point quad order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
- const QuadPts& q = quadraticLines[index];
- SkDQuad quad;
- quad.debugSet(q.fPts);
- SkASSERT(ValidQuad(quad));
- SkDCubic cubic = quad.debugToCubic();
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order != 2) {
- SkDebugf("[%d] line quad order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
- const QuadPts& q = quadraticModEpsilonLines[index];
- SkDQuad quad;
- quad.debugSet(q.fPts);
- SkASSERT(ValidQuad(quad));
- SkDCubic cubic = quad.debugToCubic();
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
- if (order != 3) {
- SkDebugf("[%d] line mod quad order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- #if 0 // disable test until stroke reduction is supported
- // test if computed line end points are valid
- for (index = firstComputedLinesTest; index < lines_count; ++index) {
- const SkDCubic& cubic = lines[index];
- SkASSERT(ValidCubic(cubic));
- bool controlsInside = controls_inside(cubic);
- order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics,
- SkReduceOrder::kStroke_Style);
- if (order == 2 && reducer.fLine[0] == reducer.fLine[1]) {
- SkDebugf("[%d] line computed ends match order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- if (controlsInside) {
- if ( (reducer.fLine[0].fX != cubic[0].fX && reducer.fLine[0].fX != cubic[3].fX)
- || (reducer.fLine[0].fY != cubic[0].fY && reducer.fLine[0].fY != cubic[3].fY)
- || (reducer.fLine[1].fX != cubic[0].fX && reducer.fLine[1].fX != cubic[3].fX)
- || (reducer.fLine[1].fY != cubic[0].fY && reducer.fLine[1].fY != cubic[3].fY)) {
- SkDebugf("[%d] line computed ends order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- } else {
- // binary search for extrema, compare against actual results
- // while a control point is outside of bounding box formed by end points, split
- SkDRect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
- find_tight_bounds(cubic, bounds);
- if ( (!AlmostEqualUlps(reducer.fLine[0].fX, bounds.fLeft)
- && !AlmostEqualUlps(reducer.fLine[0].fX, bounds.fRight))
- || (!AlmostEqualUlps(reducer.fLine[0].fY, bounds.fTop)
- && !AlmostEqualUlps(reducer.fLine[0].fY, bounds.fBottom))
- || (!AlmostEqualUlps(reducer.fLine[1].fX, bounds.fLeft)
- && !AlmostEqualUlps(reducer.fLine[1].fX, bounds.fRight))
- || (!AlmostEqualUlps(reducer.fLine[1].fY, bounds.fTop)
- && !AlmostEqualUlps(reducer.fLine[1].fY, bounds.fBottom))) {
- SkDebugf("[%d] line computed tight bounds order=%d\n", static_cast<int>(index), order);
- REPORTER_ASSERT(reporter, 0);
- }
- }
- }
- #endif
- }
|