Home | History | Annotate | Download | only in Intersection 
      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 
     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