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
13struct 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.
21static 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
33static 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'
54bool 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.
98static 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
141static 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//
177bool 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