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
interp_quad_coords(double a,double b,double c,double t)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
coincident_line(const Quadratic & quad,Quadratic & reduction)19 static int coincident_line(const Quadratic& quad, Quadratic& reduction) {
20 reduction[0] = reduction[1] = quad[0];
21 return 1;
22 }
23
vertical_line(const Quadratic & quad,ReduceOrder_Styles reduceStyle,Quadratic & reduction)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
horizontal_line(const Quadratic & quad,ReduceOrder_Styles reduceStyle,Quadratic & reduction)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
check_linear(const Quadratic & quad,ReduceOrder_Styles reduceStyle,int minX,int maxX,int minY,int maxY,Quadratic & reduction)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
isLinear(const Quadratic & quad,int startIndex,int endIndex)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
reduceOrder(const Quadratic & quad,Quadratic & reduction,ReduceOrder_Styles reduceStyle)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