1 /*
2 * Copyright 2017 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
8 #include "SkInsetConvexPolygon.h"
9
10 #include "SkTemplates.h"
11
12 struct InsetSegment {
13 SkPoint fP0;
14 SkPoint fP1;
15 };
16
17 // Computes perpDot for point compared to segment.
18 // A positive value means the point is to the left of the segment,
19 // negative is to the right, 0 is collinear.
compute_side(const SkPoint & s0,const SkPoint & s1,const SkPoint & p)20 static int compute_side(const SkPoint& s0, const SkPoint& s1, const SkPoint& p) {
21 SkVector v0 = s1 - s0;
22 SkVector v1 = p - s0;
23 SkScalar perpDot = v0.cross(v1);
24 if (!SkScalarNearlyZero(perpDot)) {
25 return ((perpDot > 0) ? 1 : -1);
26 }
27
28 return 0;
29 }
30
31 // returns 1 for ccw, -1 for cw and 0 if degenerate
get_winding(const SkPoint * polygonVerts,int polygonSize)32 static int get_winding(const SkPoint* polygonVerts, int polygonSize) {
33 SkPoint p0 = polygonVerts[0];
34 SkPoint p1 = polygonVerts[1];
35
36 for (int i = 2; i < polygonSize; ++i) {
37 SkPoint p2 = polygonVerts[i];
38
39 // determine if cw or ccw
40 int side = compute_side(p0, p1, p2);
41 if (0 != side) {
42 return ((side > 0) ? 1 : -1);
43 }
44
45 // if nearly collinear, treat as straight line and continue
46 p1 = p2;
47 }
48
49 return 0;
50 }
51
52 // Offset line segment p0-p1 'd0' and 'd1' units in the direction specified by 'side'
SkOffsetSegment(const SkPoint & p0,const SkPoint & p1,SkScalar d0,SkScalar d1,int side,SkPoint * offset0,SkPoint * offset1)53 bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar d1,
54 int side, SkPoint* offset0, SkPoint* offset1) {
55 SkASSERT(side == -1 || side == 1);
56 SkVector perp = SkVector::Make(p0.fY - p1.fY, p1.fX - p0.fX);
57 if (SkScalarNearlyEqual(d0, d1)) {
58 // if distances are equal, can just outset by the perpendicular
59 perp.setLength(d0*side);
60 *offset0 = p0 + perp;
61 *offset1 = p1 + perp;
62 } else {
63 // Otherwise we need to compute the outer tangent.
64 // See: http://www.ambrsoft.com/TrigoCalc/Circles2/Circles2Tangent_.htm
65 if (d0 < d1) {
66 side = -side;
67 }
68 SkScalar dD = d0 - d1;
69 // if one circle is inside another, we can't compute an offset
70 if (dD*dD >= p0.distanceToSqd(p1)) {
71 return false;
72 }
73 SkPoint outerTangentIntersect = SkPoint::Make((p1.fX*d0 - p0.fX*d1) / dD,
74 (p1.fY*d0 - p0.fY*d1) / dD);
75
76 SkScalar d0sq = d0*d0;
77 SkVector dP = outerTangentIntersect - p0;
78 SkScalar dPlenSq = dP.lengthSqd();
79 SkScalar discrim = SkScalarSqrt(dPlenSq - d0sq);
80 offset0->fX = p0.fX + (d0sq*dP.fX - side*d0*dP.fY*discrim) / dPlenSq;
81 offset0->fY = p0.fY + (d0sq*dP.fY + side*d0*dP.fX*discrim) / dPlenSq;
82
83 SkScalar d1sq = d1*d1;
84 dP = outerTangentIntersect - p1;
85 dPlenSq = dP.lengthSqd();
86 discrim = SkScalarSqrt(dPlenSq - d1sq);
87 offset1->fX = p1.fX + (d1sq*dP.fX - side*d1*dP.fY*discrim) / dPlenSq;
88 offset1->fY = p1.fY + (d1sq*dP.fY + side*d1*dP.fX*discrim) / dPlenSq;
89 }
90
91 return true;
92 }
93
94 // Compute the intersection 'p' between segments s0 and s1, if any.
95 // 's' is the parametric value for the intersection along 's0' & 't' is the same for 's1'.
96 // Returns false if there is no intersection.
compute_intersection(const InsetSegment & s0,const InsetSegment & s1,SkPoint * p,SkScalar * s,SkScalar * t)97 static bool compute_intersection(const InsetSegment& s0, const InsetSegment& s1,
98 SkPoint* p, SkScalar* s, SkScalar* t) {
99 SkVector v0 = s0.fP1 - s0.fP0;
100 SkVector v1 = s1.fP1 - s1.fP0;
101
102 SkScalar perpDot = v0.cross(v1);
103 if (SkScalarNearlyZero(perpDot)) {
104 // segments are parallel
105 // check if endpoints are touching
106 if (s0.fP1.equalsWithinTolerance(s1.fP0)) {
107 *p = s0.fP1;
108 *s = SK_Scalar1;
109 *t = 0;
110 return true;
111 }
112 if (s1.fP1.equalsWithinTolerance(s0.fP0)) {
113 *p = s1.fP1;
114 *s = 0;
115 *t = SK_Scalar1;
116 return true;
117 }
118
119 return false;
120 }
121
122 SkVector d = s1.fP0 - s0.fP0;
123 SkScalar localS = d.cross(v1) / perpDot;
124 if (localS < 0 || localS > SK_Scalar1) {
125 return false;
126 }
127 SkScalar localT = d.cross(v0) / perpDot;
128 if (localT < 0 || localT > SK_Scalar1) {
129 return false;
130 }
131
132 v0 *= localS;
133 *p = s0.fP0 + v0;
134 *s = localS;
135 *t = localT;
136
137 return true;
138 }
139
is_convex(const SkTDArray<SkPoint> & poly)140 static bool is_convex(const SkTDArray<SkPoint>& poly) {
141 if (poly.count() <= 3) {
142 return true;
143 }
144
145 SkVector v0 = poly[0] - poly[poly.count() - 1];
146 SkVector v1 = poly[1] - poly[poly.count() - 1];
147 SkScalar winding = v0.cross(v1);
148
149 for (int i = 0; i < poly.count() - 1; ++i) {
150 int j = i + 1;
151 int k = (i + 2) % poly.count();
152
153 SkVector v0 = poly[j] - poly[i];
154 SkVector v1 = poly[k] - poly[i];
155 SkScalar perpDot = v0.cross(v1);
156 if (winding*perpDot < 0) {
157 return false;
158 }
159 }
160
161 return true;
162 }
163
164 // The objective here is to inset all of the edges by the given distance, and then
165 // remove any invalid inset edges by detecting right-hand turns. In a ccw polygon,
166 // we should only be making left-hand turns (for cw polygons, we use the winding
167 // parameter to reverse this). We detect this by checking whether the second intersection
168 // on an edge is closer to its tail than the first one.
169 //
170 // We might also have the case that there is no intersection between two neighboring inset edges.
171 // In this case, one edge will lie to the right of the other and should be discarded along with
172 // its previous intersection (if any).
173 //
174 // Note: the assumption is that inputPolygon is convex and has no coincident points.
175 //
SkInsetConvexPolygon(const SkPoint * inputPolygonVerts,int inputPolygonSize,std::function<SkScalar (int index)> insetDistanceFunc,SkTDArray<SkPoint> * insetPolygon)176 bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
177 std::function<SkScalar(int index)> insetDistanceFunc,
178 SkTDArray<SkPoint>* insetPolygon) {
179 if (inputPolygonSize < 3) {
180 return false;
181 }
182
183 int winding = get_winding(inputPolygonVerts, inputPolygonSize);
184 if (0 == winding) {
185 return false;
186 }
187
188 // set up
189 struct EdgeData {
190 InsetSegment fInset;
191 SkPoint fIntersection;
192 SkScalar fTValue;
193 bool fValid;
194 };
195
196 SkAutoSTMalloc<64, EdgeData> edgeData(inputPolygonSize);
197 for (int i = 0; i < inputPolygonSize; ++i) {
198 int j = (i + 1) % inputPolygonSize;
199 int k = (i + 2) % inputPolygonSize;
200 // check for convexity just to be sure
201 if (compute_side(inputPolygonVerts[i], inputPolygonVerts[j],
202 inputPolygonVerts[k])*winding < 0) {
203 return false;
204 }
205 SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j],
206 insetDistanceFunc(i), insetDistanceFunc(j),
207 winding,
208 &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1);
209 edgeData[i].fIntersection = edgeData[i].fInset.fP0;
210 edgeData[i].fTValue = SK_ScalarMin;
211 edgeData[i].fValid = true;
212 }
213
214 int prevIndex = inputPolygonSize - 1;
215 int currIndex = 0;
216 int insetVertexCount = inputPolygonSize;
217 while (prevIndex != currIndex) {
218 if (!edgeData[prevIndex].fValid) {
219 prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
220 continue;
221 }
222
223 SkScalar s, t;
224 SkPoint intersection;
225 if (compute_intersection(edgeData[prevIndex].fInset, edgeData[currIndex].fInset,
226 &intersection, &s, &t)) {
227 // if new intersection is further back on previous inset from the prior intersection
228 if (s < edgeData[prevIndex].fTValue) {
229 // no point in considering this one again
230 edgeData[prevIndex].fValid = false;
231 --insetVertexCount;
232 // go back one segment
233 prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
234 // we've already considered this intersection, we're done
235 } else if (edgeData[currIndex].fTValue > SK_ScalarMin &&
236 intersection.equalsWithinTolerance(edgeData[currIndex].fIntersection,
237 1.0e-6f)) {
238 break;
239 } else {
240 // add intersection
241 edgeData[currIndex].fIntersection = intersection;
242 edgeData[currIndex].fTValue = t;
243
244 // go to next segment
245 prevIndex = currIndex;
246 currIndex = (currIndex + 1) % inputPolygonSize;
247 }
248 } else {
249 // if prev to right side of curr
250 int side = winding*compute_side(edgeData[currIndex].fInset.fP0,
251 edgeData[currIndex].fInset.fP1,
252 edgeData[prevIndex].fInset.fP1);
253 if (side < 0 && side == winding*compute_side(edgeData[currIndex].fInset.fP0,
254 edgeData[currIndex].fInset.fP1,
255 edgeData[prevIndex].fInset.fP0)) {
256 // no point in considering this one again
257 edgeData[prevIndex].fValid = false;
258 --insetVertexCount;
259 // go back one segment
260 prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
261 } else {
262 // move to next segment
263 edgeData[currIndex].fValid = false;
264 --insetVertexCount;
265 currIndex = (currIndex + 1) % inputPolygonSize;
266 }
267 }
268 }
269
270 // store all the valid intersections that aren't nearly coincident
271 // TODO: look at the main algorithm and see if we can detect these better
272 static constexpr SkScalar kCleanupTolerance = 0.01f;
273
274 insetPolygon->reset();
275 insetPolygon->setReserve(insetVertexCount);
276 currIndex = -1;
277 for (int i = 0; i < inputPolygonSize; ++i) {
278 if (edgeData[i].fValid && (currIndex == -1 ||
279 !edgeData[i].fIntersection.equalsWithinTolerance((*insetPolygon)[currIndex],
280 kCleanupTolerance))) {
281 *insetPolygon->push() = edgeData[i].fIntersection;
282 currIndex++;
283 }
284 }
285 // make sure the first and last points aren't coincident
286 if (currIndex >= 1 &&
287 (*insetPolygon)[0].equalsWithinTolerance((*insetPolygon)[currIndex],
288 kCleanupTolerance)) {
289 insetPolygon->pop();
290 }
291
292 return (insetPolygon->count() >= 3 && is_convex(*insetPolygon));
293 }
294