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