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 "Extrema.h"
      9 #include "IntersectionUtilities.h"
     10 #include "LineParameters.h"
     11 
     12 static double interp_quad_coords(double a, double b, double c, double t)
     13 {
     14     double ab = interp(a, b, t);
     15     double bc = interp(b, c, t);
     16     return interp(ab, bc, t);
     17 }
     18 
     19 static int coincident_line(const Quadratic& quad, Quadratic& reduction) {
     20     reduction[0] = reduction[1] = quad[0];
     21     return 1;
     22 }
     23 
     24 static int vertical_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle,
     25         Quadratic& reduction) {
     26     double tValue;
     27     reduction[0] = quad[0];
     28     reduction[1] = quad[2];
     29     if (reduceStyle == kReduceOrder_TreatAsFill) {
     30         return 2;
     31     }
     32     int smaller = reduction[1].y > reduction[0].y;
     33     int larger = smaller ^ 1;
     34     if (findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue)) {
     35         double yExtrema = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue);
     36         if (reduction[smaller].y > yExtrema) {
     37             reduction[smaller].y = yExtrema;
     38         } else if (reduction[larger].y < yExtrema) {
     39             reduction[larger].y = yExtrema;
     40         }
     41     }
     42     return 2;
     43 }
     44 
     45 static int horizontal_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle,
     46         Quadratic& reduction) {
     47     double tValue;
     48     reduction[0] = quad[0];
     49     reduction[1] = quad[2];
     50     if (reduceStyle == kReduceOrder_TreatAsFill) {
     51         return 2;
     52     }
     53     int smaller = reduction[1].x > reduction[0].x;
     54     int larger = smaller ^ 1;
     55     if (findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue)) {
     56         double xExtrema = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue);
     57         if (reduction[smaller].x > xExtrema) {
     58             reduction[smaller].x = xExtrema;
     59         }  else if (reduction[larger].x < xExtrema) {
     60             reduction[larger].x = xExtrema;
     61         }
     62     }
     63     return 2;
     64 }
     65 
     66 static int check_linear(const Quadratic& quad, ReduceOrder_Styles reduceStyle,
     67         int minX, int maxX, int minY, int maxY, Quadratic& reduction) {
     68     int startIndex = 0;
     69     int endIndex = 2;
     70     while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
     71         --endIndex;
     72         if (endIndex == 0) {
     73             printf("%s shouldn't get here if all four points are about equal", __FUNCTION__);
     74             SkASSERT(0);
     75         }
     76     }
     77     if (!isLinear(quad, startIndex, endIndex)) {
     78         return 0;
     79     }
     80     // four are colinear: return line formed by outside
     81     reduction[0] = quad[0];
     82     reduction[1] = quad[2];
     83     if (reduceStyle == kReduceOrder_TreatAsFill) {
     84         return 2;
     85     }
     86     int sameSide;
     87     bool useX = quad[maxX].x - quad[minX].x >= quad[maxY].y - quad[minY].y;
     88     if (useX) {
     89         sameSide = sign(quad[0].x - quad[1].x) + sign(quad[2].x - quad[1].x);
     90     } else {
     91         sameSide = sign(quad[0].y - quad[1].y) + sign(quad[2].y - quad[1].y);
     92     }
     93     if ((sameSide & 3) != 2) {
     94         return 2;
     95     }
     96     double tValue;
     97     int root;
     98     if (useX) {
     99         root = findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue);
    100     } else {
    101         root = findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue);
    102     }
    103     if (root) {
    104         _Point extrema;
    105         extrema.x = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue);
    106         extrema.y = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue);
    107         // sameSide > 0 means mid is smaller than either [0] or [2], so replace smaller
    108         int replace;
    109         if (useX) {
    110             if (extrema.x < quad[0].x ^ extrema.x < quad[2].x) {
    111                 return 2;
    112             }
    113             replace = (extrema.x < quad[0].x | extrema.x < quad[2].x)
    114                     ^ (quad[0].x < quad[2].x);
    115         } else {
    116             if (extrema.y < quad[0].y ^ extrema.y < quad[2].y) {
    117                 return 2;
    118             }
    119             replace = (extrema.y < quad[0].y | extrema.y < quad[2].y)
    120                     ^ (quad[0].y < quad[2].y);
    121         }
    122         reduction[replace] = extrema;
    123     }
    124     return 2;
    125 }
    126 
    127 bool isLinear(const Quadratic& quad, int startIndex, int endIndex) {
    128     LineParameters lineParameters;
    129     lineParameters.quadEndPoints(quad, startIndex, endIndex);
    130     // FIXME: maybe it's possible to avoid this and compare non-normalized
    131     lineParameters.normalize();
    132     double distance = lineParameters.controlPtDistance(quad);
    133     return approximately_zero(distance);
    134 }
    135 
    136 // reduce to a quadratic or smaller
    137 // look for identical points
    138 // look for all four points in a line
    139     // note that three points in a line doesn't simplify a cubic
    140 // look for approximation with single quadratic
    141     // save approximation with multiple quadratics for later
    142 int reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles reduceStyle) {
    143     int index, minX, maxX, minY, maxY;
    144     int minXSet, minYSet;
    145     minX = maxX = minY = maxY = 0;
    146     minXSet = minYSet = 0;
    147     for (index = 1; index < 3; ++index) {
    148         if (quad[minX].x > quad[index].x) {
    149             minX = index;
    150         }
    151         if (quad[minY].y > quad[index].y) {
    152             minY = index;
    153         }
    154         if (quad[maxX].x < quad[index].x) {
    155             maxX = index;
    156         }
    157         if (quad[maxY].y < quad[index].y) {
    158             maxY = index;
    159         }
    160     }
    161     for (index = 0; index < 3; ++index) {
    162         if (AlmostEqualUlps(quad[index].x, quad[minX].x)) {
    163             minXSet |= 1 << index;
    164         }
    165         if (AlmostEqualUlps(quad[index].y, quad[minY].y)) {
    166             minYSet |= 1 << index;
    167         }
    168     }
    169     if (minXSet == 0x7) { // test for vertical line
    170         if (minYSet == 0x7) { // return 1 if all four are coincident
    171             return coincident_line(quad, reduction);
    172         }
    173         return vertical_line(quad, reduceStyle, reduction);
    174     }
    175     if (minYSet == 0xF) { // test for horizontal line
    176         return horizontal_line(quad, reduceStyle, reduction);
    177     }
    178     int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, reduction);
    179     if (result) {
    180         return result;
    181     }
    182     memcpy(reduction, quad, sizeof(Quadratic));
    183     return 3;
    184 }
    185