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
12static 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
19static int coincident_line(const Quadratic& quad, Quadratic& reduction) {
20    reduction[0] = reduction[1] = quad[0];
21    return 1;
22}
23
24static 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
45static 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
66static 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
127bool 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
142int 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