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. 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 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' 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. 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 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 // 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
