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