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 
140 #ifdef SK_DEBUG
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         int side = winding*perpDot;
158         if (side < 0) {
159             return false;
160         }
161     }
162 
163     return true;
164 }
165 #endif
166 
167 // The objective here is to inset all of the edges by the given distance, and then
168 // remove any invalid inset edges by detecting right-hand turns. In a ccw polygon,
169 // we should only be making left-hand turns (for cw polygons, we use the winding
170 // parameter to reverse this). We detect this by checking whether the second intersection
171 // on an edge is closer to its tail than the first one.
172 //
173 // We might also have the case that there is no intersection between two neighboring inset edges.
174 // In this case, one edge will lie to the right of the other and should be discarded along with
175 // its previous intersection (if any).
176 //
177 // Note: the assumption is that inputPolygon is convex and has no coincident points.
178 //
SkInsetConvexPolygon(const SkPoint * inputPolygonVerts,int inputPolygonSize,std::function<SkScalar (int index)> insetDistanceFunc,SkTDArray<SkPoint> * insetPolygon)179 bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
180                           std::function<SkScalar(int index)> insetDistanceFunc,
181                           SkTDArray<SkPoint>* insetPolygon) {
182     if (inputPolygonSize < 3) {
183         return false;
184     }
185 
186     int winding = get_winding(inputPolygonVerts, inputPolygonSize);
187     if (0 == winding) {
188         return false;
189     }
190 
191     // set up
192     struct EdgeData {
193         InsetSegment fInset;
194         SkPoint      fIntersection;
195         SkScalar     fTValue;
196         bool         fValid;
197     };
198 
199     SkAutoSTMalloc<64, EdgeData> edgeData(inputPolygonSize);
200     for (int i = 0; i < inputPolygonSize; ++i) {
201         int j = (i + 1) % inputPolygonSize;
202         SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j],
203                         insetDistanceFunc(i), insetDistanceFunc(j),
204                         winding,
205                         &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1);
206         edgeData[i].fIntersection = edgeData[i].fInset.fP0;
207         edgeData[i].fTValue = SK_ScalarMin;
208         edgeData[i].fValid = true;
209     }
210 
211     int prevIndex = inputPolygonSize - 1;
212     int currIndex = 0;
213     int insetVertexCount = inputPolygonSize;
214     while (prevIndex != currIndex) {
215         if (!edgeData[prevIndex].fValid) {
216             prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
217             continue;
218         }
219 
220         SkScalar s, t;
221         SkPoint intersection;
222         if (compute_intersection(edgeData[prevIndex].fInset, edgeData[currIndex].fInset,
223                                  &intersection, &s, &t)) {
224             // if new intersection is further back on previous inset from the prior intersection
225             if (s < edgeData[prevIndex].fTValue) {
226                 // no point in considering this one again
227                 edgeData[prevIndex].fValid = false;
228                 --insetVertexCount;
229                 // go back one segment
230                 prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
231             // we've already considered this intersection, we're done
232             } else if (edgeData[currIndex].fTValue > SK_ScalarMin &&
233                        intersection.equalsWithinTolerance(edgeData[currIndex].fIntersection,
234                                                           1.0e-6f)) {
235                 break;
236             } else {
237                 // add intersection
238                 edgeData[currIndex].fIntersection = intersection;
239                 edgeData[currIndex].fTValue = t;
240 
241                 // go to next segment
242                 prevIndex = currIndex;
243                 currIndex = (currIndex + 1) % inputPolygonSize;
244             }
245         } else {
246             // if prev to right side of curr
247             int side = winding*compute_side(edgeData[currIndex].fInset.fP0,
248                                             edgeData[currIndex].fInset.fP1,
249                                             edgeData[prevIndex].fInset.fP1);
250             if (side < 0 && side == winding*compute_side(edgeData[currIndex].fInset.fP0,
251                                                          edgeData[currIndex].fInset.fP1,
252                                                          edgeData[prevIndex].fInset.fP0)) {
253                 // no point in considering this one again
254                 edgeData[prevIndex].fValid = false;
255                 --insetVertexCount;
256                 // go back one segment
257                 prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
258             } else {
259                 // move to next segment
260                 edgeData[currIndex].fValid = false;
261                 --insetVertexCount;
262                 currIndex = (currIndex + 1) % inputPolygonSize;
263             }
264         }
265     }
266 
267     // store all the valid intersections that aren't nearly coincident
268     // TODO: look at the main algorithm and see if we can detect these better
269     static constexpr SkScalar kCleanupTolerance = 0.01f;
270 
271     insetPolygon->reset();
272     insetPolygon->setReserve(insetVertexCount);
273     currIndex = -1;
274     for (int i = 0; i < inputPolygonSize; ++i) {
275         if (edgeData[i].fValid && (currIndex == -1 ||
276             !edgeData[i].fIntersection.equalsWithinTolerance((*insetPolygon)[currIndex],
277                                                              kCleanupTolerance))) {
278             *insetPolygon->push() = edgeData[i].fIntersection;
279             currIndex++;
280         }
281     }
282     // make sure the first and last points aren't coincident
283     if (currIndex >= 1 &&
284         (*insetPolygon)[0].equalsWithinTolerance((*insetPolygon)[currIndex],
285                                                  kCleanupTolerance)) {
286         insetPolygon->pop();
287     }
288     SkASSERT(is_convex(*insetPolygon));
289 
290     return (insetPolygon->count() >= 3);
291 }
292