dali-physics/third-party/chipmunk2d/src/cpPolyline.c

   1 // Copyright 2013 Howling Moon Software. All rights reserved.
   2 // See http://chipmunk2d.net/legal.php for more information.
   3
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7 #include <math.h>
   8
   9 #include "chipmunk/chipmunk_private.h"
  10 #include "chipmunk/cpPolyline.h"
  11
  12
  13 static inline int Next(int i, int count){return (i+1)%count;}
  14
  15 //MARK: Polylines
  16
  17 #define DEFAULT_POLYLINE_CAPACITY 16
  18
  19 static int
  20 cpPolylineSizeForCapacity(int capacity)
  21 {
  22         return sizeof(cpPolyline) + capacity*sizeof(cpVect);
  23 }
  24
  25 static cpPolyline *
  26 cpPolylineMake(int capacity)
  27 {
  28         capacity = (capacity > DEFAULT_POLYLINE_CAPACITY ? capacity : DEFAULT_POLYLINE_CAPACITY);
  29
  30         cpPolyline *line = (cpPolyline *)cpcalloc(1, cpPolylineSizeForCapacity(capacity));
  31         line->count = 0;
  32         line->capacity = capacity;
  33
  34         return line;
  35 }
  36
  37 static cpPolyline *
  38 cpPolylineMake2(int capacity, cpVect a, cpVect b)
  39 {
  40         cpPolyline *line = cpPolylineMake(capacity);
  41         line->count = 2;
  42         line->verts[0] = a;
  43         line->verts[1] = b;
  44
  45         return line;
  46 }
  47
  48 static cpPolyline *
  49 cpPolylineShrink(cpPolyline *line)
  50 {
  51         line->capacity = line->count;
  52         return (cpPolyline*) cprealloc(line, cpPolylineSizeForCapacity(line->count));
  53 }
  54
  55 void
  56 cpPolylineFree(cpPolyline *line)
  57 {
  58         cpfree(line);
  59 }
  60
  61 // Grow the allocated memory for a polyline.
  62 static cpPolyline *
  63 cpPolylineGrow(cpPolyline *line, int count)
  64 {
  65   line->count += count;
  66
  67   int capacity = line->capacity;
  68   while(line->count > capacity) capacity *= 2;
  69
  70   if(line->capacity < capacity){
  71     line->capacity = capacity;
  72                 line = (cpPolyline*) cprealloc(line, cpPolylineSizeForCapacity(capacity));
  73   }
  74
  75         return line;
  76 }
  77
  78 // Push v onto the end of line.
  79 static cpPolyline *
  80 cpPolylinePush(cpPolyline *line, cpVect v)
  81 {
  82   int count = line->count;
  83   line = cpPolylineGrow(line, 1);
  84   line->verts[count] = v;
  85
  86         return line;
  87 }
  88
  89 // Push v onto the beginning of line.
  90 static cpPolyline *
  91 cpPolylineEnqueue(cpPolyline *line, cpVect v)
  92 {
  93         // TODO could optimize this to grow in both directions.
  94         // Probably doesn't matter though.
  95   int count = line->count;
  96   line = cpPolylineGrow(line, 1);
  97   memmove(line->verts + 1, line->verts, count*sizeof(cpVect));
  98   line->verts[0] = v;
  99
 100         return line;
 101 }
 102
 103 // Returns true if the polyline starts and ends with the same vertex.
 104 cpBool
 105 cpPolylineIsClosed(cpPolyline *line)
 106 {
 107         return (line->count > 1 && cpveql(line->verts[0], line->verts[line->count-1]));
 108 }
 109
 110 // Check if a cpPolyline is longer than a certain length
 111 // Takes a range which can wrap around if the polyline is looped.
 112 static cpBool
 113 cpPolylineIsShort(cpVect *points, int count, int start, int end, cpFloat min)
 114 {
 115   cpFloat length = 0.0f;
 116         for(int i=start; i!=end; i=Next(i, count)){
 117                 length += cpvdist(points[i], points[Next(i, count)]);
 118                 if(length > min) return cpFalse;
 119         }
 120
 121   return cpTrue;
 122 }
 123
 124 //MARK: Polyline Simplification
 125
 126 static inline cpFloat
 127 Sharpness(cpVect a, cpVect b, cpVect c)
 128 {
 129         // TODO could speed this up by caching the normals instead of calculating each twice.
 130   return cpvdot(cpvnormalize(cpvsub(a, b)), cpvnormalize(cpvsub(c, b)));
 131 }
 132
 133 // Join similar adjacent line segments together. Works well for hard edged shapes.
 134 // 'tol' is the minimum anglular difference in radians of a vertex.
 135 cpPolyline *
 136 cpPolylineSimplifyVertexes(cpPolyline *line, cpFloat tol)
 137 {
 138         cpPolyline *reduced = cpPolylineMake2(0, line->verts[0], line->verts[1]);
 139
 140         cpFloat minSharp = -cpfcos(tol);
 141
 142         for(int i=2; i<line->count; i++){
 143                 cpVect vert = line->verts[i];
 144                 cpFloat sharp = Sharpness(reduced->verts[reduced->count - 2], reduced->verts[reduced->count - 1], vert);
 145
 146                 if(sharp <= minSharp){
 147                         reduced->verts[reduced->count - 1] = vert;
 148                 } else {
 149                         reduced = cpPolylinePush(reduced, vert);
 150                 }
 151         }
 152
 153         if(
 154                 cpPolylineIsClosed(line) &&
 155                 Sharpness(reduced->verts[reduced->count - 2], reduced->verts[0], reduced->verts[1]) < minSharp
 156         ){
 157                 reduced->verts[0] = reduced->verts[reduced->count - 2];
 158                 reduced->count--;
 159         }
 160
 161         // TODO shrink
 162         return reduced;
 163 }
 164
 165 // Recursive function used by cpPolylineSimplifyCurves().
 166 static cpPolyline *
 167 DouglasPeucker(
 168         cpVect *verts, cpPolyline *reduced,
 169         int length, int start, int end,
 170         cpFloat min, cpFloat tol
 171 ){
 172         // Early exit if the points are adjacent
 173   if((end - start + length)%length < 2) return reduced;
 174
 175         cpVect a = verts[start];
 176         cpVect b = verts[end];
 177
 178         // Check if the length is below the threshold
 179         if(cpvnear(a, b, min) && cpPolylineIsShort(verts, length, start, end, min)) return reduced;
 180
 181         // Find the maximal vertex to split and recurse on
 182         cpFloat max = 0.0;
 183         int maxi = start;
 184
 185         cpVect n = cpvnormalize(cpvperp(cpvsub(b, a)));
 186         cpFloat d = cpvdot(n, a);
 187
 188         for(int i=Next(start, length); i!=end; i=Next(i, length)){
 189                 cpFloat dist = fabs(cpvdot(n, verts[i]) - d);
 190
 191                 if(dist > max){
 192                         max = dist;
 193                         maxi = i;
 194                 }
 195         }
 196
 197         if(max > tol){
 198     reduced = DouglasPeucker(verts, reduced, length, start, maxi, min, tol);
 199                 reduced = cpPolylinePush(reduced, verts[maxi]);
 200     reduced = DouglasPeucker(verts, reduced, length, maxi, end, min, tol);
 201         }
 202
 203         return reduced;
 204 }
 205
 206 // Recursively reduce the vertex count on a polyline. Works best for smooth shapes.
 207 // 'tol' is the maximum error for the reduction.
 208 // The reduced polyline will never be farther than this distance from the original polyline.
 209 cpPolyline *
 210 cpPolylineSimplifyCurves(cpPolyline *line, cpFloat tol)
 211 {
 212         cpPolyline *reduced = cpPolylineMake(line->count);
 213
 214         cpFloat min = tol/2.0f;
 215
 216   if(cpPolylineIsClosed(line)){
 217                 int start, end;
 218     cpLoopIndexes(line->verts, line->count - 1, &start, &end);
 219
 220                 reduced = cpPolylinePush(reduced, line->verts[start]);
 221                 reduced = DouglasPeucker(line->verts, reduced, line->count - 1, start, end, min, tol);
 222                 reduced = cpPolylinePush(reduced, line->verts[end]);
 223                 reduced = DouglasPeucker(line->verts, reduced, line->count - 1, end, start, min, tol);
 224                 reduced = cpPolylinePush(reduced, line->verts[start]);
 225   } else {
 226                 reduced = cpPolylinePush(reduced, line->verts[0]);
 227                 reduced = DouglasPeucker(line->verts, reduced, line->count, 0, line->count - 1, min, tol);
 228                 reduced = cpPolylinePush(reduced, line->verts[line->count - 1]);
 229   }
 230
 231         return cpPolylineShrink(reduced);
 232 }
 233
 234 //MARK: Polyline Sets
 235
 236 cpPolylineSet *
 237 cpPolylineSetAlloc(void)
 238 {
 239         return (cpPolylineSet *)cpcalloc(1, sizeof(cpPolylineSet));
 240 }
 241
 242 cpPolylineSet *
 243 cpPolylineSetInit(cpPolylineSet *set)
 244 {
 245         set->count = 0;
 246         set->capacity = 8;
 247         set->lines = (cpPolyline**) cpcalloc(set->capacity, sizeof(cpPolyline));
 248
 249   return set;
 250 }
 251
 252
 253 cpPolylineSet *
 254 cpPolylineSetNew(void)
 255 {
 256         return cpPolylineSetInit(cpPolylineSetAlloc());
 257 }
 258
 259 void
 260 cpPolylineSetDestroy(cpPolylineSet *set, cpBool freePolylines)
 261 {
 262         if(freePolylines){
 263                 for(int i=0; i<set->count; i++){
 264                         cpPolylineFree(set->lines[i]);
 265                 }
 266         }
 267
 268         cpfree(set->lines);
 269 }
 270
 271
 272 void
 273 cpPolylineSetFree(cpPolylineSet *set, cpBool freePolylines)
 274 {
 275         if(set){
 276                 cpPolylineSetDestroy(set, freePolylines);
 277                 cpfree(set);
 278         }
 279 }
 280
 281 // Find the polyline that ends with v.
 282 static int
 283 cpPolylineSetFindEnds(cpPolylineSet *set, cpVect v){
 284         int count = set->count;
 285         cpPolyline **lines = set->lines;
 286
 287   for(int i=0; i<count; i++){
 288                 cpPolyline *line = lines[i];
 289     if(cpveql(line->verts[line->count - 1], v)) return i;
 290   }
 291
 292   return -1;
 293 }
 294
 295 // Find the polyline that starts with v.
 296 static int
 297 cpPolylineSetFindStarts(cpPolylineSet *set, cpVect v){
 298         int count = set->count;
 299         cpPolyline **lines = set->lines;
 300
 301   for(int i=0; i<count; i++){
 302     if(cpveql(lines[i]->verts[0], v)) return i;
 303   }
 304
 305   return -1;
 306 }
 307
 308 // Add a new polyline to a polyline set.
 309 static void
 310 cpPolylineSetPush(cpPolylineSet *set, cpPolyline *line)
 311 {
 312   // grow set
 313   set->count++;
 314   if(set->count > set->capacity){
 315     set->capacity *= 2;
 316     set->lines = (cpPolyline**) cprealloc(set->lines, set->capacity*sizeof(cpPolyline));
 317   }
 318
 319         set->lines[set->count - 1] = line;
 320 }
 321
 322 // Add a new polyline to a polyline set.
 323 static void
 324 cpPolylineSetAdd(cpPolylineSet *set, cpVect v0, cpVect v1)
 325 {
 326         cpPolylineSetPush(set, cpPolylineMake2(DEFAULT_POLYLINE_CAPACITY, v0, v1));
 327 }
 328
 329 // Join two cpPolylines in a polyline set together.
 330 static void
 331 cpPolylineSetJoin(cpPolylineSet *set, int before, int after)
 332 {
 333   cpPolyline *lbefore = set->lines[before];
 334   cpPolyline *lafter = set->lines[after];
 335
 336   // append
 337   int count = lbefore->count;
 338   lbefore = cpPolylineGrow(lbefore, lafter->count);
 339   memmove(lbefore->verts + count, lafter->verts, lafter->count*sizeof(cpVect));
 340         set->lines[before] = lbefore;
 341
 342   // delete lafter
 343   set->count--;
 344         cpPolylineFree(set->lines[after]);
 345   set->lines[after] = set->lines[set->count];
 346 }
 347
 348 // Add a segment to a polyline set.
 349 // A segment will either start a new polyline, join two others, or add to or loop an existing polyline.
 350 void
 351 cpPolylineSetCollectSegment(cpVect v0, cpVect v1, cpPolylineSet *lines)
 352 {
 353   int before = cpPolylineSetFindEnds(lines, v0);
 354   int after = cpPolylineSetFindStarts(lines, v1);
 355
 356   if(before >= 0 && after >= 0){
 357     if(before == after){
 358       // loop by pushing v1 onto before
 359       lines->lines[before] = cpPolylinePush(lines->lines[before], v1);
 360     } else {
 361       // join before and after
 362       cpPolylineSetJoin(lines, before, after);
 363     }
 364   } else if(before >= 0){
 365     // push v1 onto before
 366     lines->lines[before] = cpPolylinePush(lines->lines[before], v1);
 367   } else if(after >= 0){
 368     // enqueue v0 onto after
 369     lines->lines[after] = cpPolylineEnqueue(lines->lines[after], v0);
 370   } else {
 371     // create new line from v0 and v1
 372     cpPolylineSetAdd(lines, v0, v1);
 373   }
 374 }
 375
 376 //MARK: Convex Hull Functions
 377
 378 cpPolyline *
 379 cpPolylineToConvexHull(cpPolyline *line, cpFloat tol)
 380 {
 381         cpPolyline *hull = cpPolylineMake(line->count + 1);
 382         hull->count = cpConvexHull(line->count, line->verts, hull->verts, NULL, tol);
 383         hull = cpPolylinePush(hull, hull->verts[0]);
 384
 385         return cpPolylineShrink(hull);
 386 }
 387
 388 //MARK: Approximate Concave Decompostition
 389
 390 struct Notch {
 391         int i;
 392         cpFloat d;
 393         cpVect v;
 394         cpVect n;
 395 };
 396
 397 static cpFloat
 398 FindSteiner(int count, cpVect *verts, struct Notch notch)
 399 {
 400         cpFloat min = INFINITY;
 401         cpFloat feature = -1.0;
 402
 403         for(int i=1; i<count-1; i++){
 404                 int index = (notch.i + i)%count;
 405
 406                 cpVect seg_a = verts[index];
 407                 cpVect seg_b = verts[Next(index, count)];
 408
 409                 cpFloat thing_a = cpvcross(notch.n, cpvsub(seg_a, notch.v));
 410                 cpFloat thing_b = cpvcross(notch.n, cpvsub(seg_b, notch.v));
 411                 if(thing_a*thing_b <= 0.0){
 412                         cpFloat t = thing_a/(thing_a - thing_b);
 413                         cpFloat dist = cpvdot(notch.n, cpvsub(cpvlerp(seg_a, seg_b, t), notch.v));
 414
 415                         if(dist >= 0.0 && dist <= min){
 416                                 min = dist;
 417                                 feature = index + t;
 418                         }
 419                 }
 420         }
 421
 422         return feature;
 423 }
 424
 425 //static cpFloat
 426 //FindSteiner2(cpVect *verts, int count, struct Notch notch)
 427 //{
 428 //      cpVect a = verts[(notch.i + count - 1)%count];
 429 //      cpVect b = verts[(notch.i + 1)%count];
 430 //      cpVect n = cpvnormalize(cpvadd(cpvnormalize(cpvsub(notch.v, a)), cpvnormalize(cpvsub(notch.v, b))));
 431 //
 432 //      cpFloat min = INFINITY;
 433 //      cpFloat feature = -1.0;
 434 //
 435 //      for(int i=1; i<count-1; i++){
 436 //              int index = (notch.i + i)%count;
 437 //
 438 //              cpVect seg_a = verts[index];
 439 //              cpVect seg_b = verts[Next(index, count)];
 440 //
 441 //              cpFloat thing_a = cpvcross(n, cpvsub(seg_a, notch.v));
 442 //              cpFloat thing_b = cpvcross(n, cpvsub(seg_b, notch.v));
 443 //              if(thing_a*thing_b <= 0.0){
 444 //                      cpFloat t = thing_a/(thing_a - thing_b);
 445 //                      cpFloat dist = cpvdot(n, cpvsub(cpvlerp(seg_a, seg_b, t), notch.v));
 446 //
 447 //                      if(dist >= 0.0 && dist <= min){
 448 //                              min = dist;
 449 //                              feature = index + t;
 450 //                      }
 451 //              }
 452 //      }
 453 //
 454 //      cpAssertSoft(feature >= 0.0, "No closest features detected. This is likely due to a self intersecting polygon.");
 455 //      return feature;
 456 //}
 457
 458 //struct Range {cpFloat min, max;};
 459 //static inline struct Range
 460 //clip_range(cpVect delta_a, cpVect delta_b, cpVect clip)
 461 //{
 462 //      cpFloat da = cpvcross(delta_a, clip);
 463 //      cpFloat db = cpvcross(delta_b, clip);
 464 //      cpFloat clamp = da/(da - db);
 465 //      if(da > db){
 466 //              return (struct Range){-INFINITY, clamp};
 467 //      } else if(da < db){
 468 //              return (struct Range){clamp, INFINITY};
 469 //      } else {
 470 //              return (struct Range){-INFINITY, INFINITY};
 471 //      }
 472 //}
 473 //
 474 //static cpFloat
 475 //FindSteiner3(cpVect *verts, int count, struct Notch notch)
 476 //{
 477 //      cpFloat min = INFINITY;
 478 //      cpFloat feature = -1.0;
 479 //
 480 //      cpVect support_a = verts[(notch.i - 1 + count)%count];
 481 //      cpVect support_b = verts[(notch.i + 1)%count];
 482 //
 483 //      cpVect clip_a = cpvlerp(support_a, support_b, 0.1);
 484 //      cpVect clip_b = cpvlerp(support_b, support_b, 0.9);
 485 //
 486 //      for(int i=1; i<count - 1; i++){
 487 //              int index = (notch.i + i)%count;
 488 //              cpVect seg_a = verts[index];
 489 //              cpVect seg_b = verts[Next(index, count)];
 490 //
 491 //              cpVect delta_a = cpvsub(seg_a, notch.v);
 492 //              cpVect delta_b = cpvsub(seg_b, notch.v);
 493 //
 494 //              // Ignore if the segment faces away from the point.
 495 //              if(cpvcross(delta_b, delta_a) > 0.0){
 496 //                      struct Range range1 = clip_range(delta_a, delta_b, cpvsub(notch.v, clip_a));
 497 //                      struct Range range2 = clip_range(delta_a, delta_b, cpvsub(clip_b, notch.v));
 498 //
 499 //                      cpFloat min_t = cpfmax(0.0, cpfmax(range1.min, range2.min));
 500 //                      cpFloat max_t = cpfmin(1.0, cpfmin(range1.max, range2.max));
 501 //
 502 //                      // Ignore if the segment has been completely clipped away.
 503 //                      if(min_t < max_t){
 504 //                              cpVect seg_delta = cpvsub(seg_b, seg_a);
 505 //                              cpFloat closest_t = cpfclamp(cpvdot(seg_delta, cpvsub(notch.v, seg_a))/cpvlengthsq(seg_delta), min_t, max_t);
 506 //                              cpVect closest = cpvlerp(seg_a, seg_b, closest_t);
 507 //
 508 //                              cpFloat dist = cpvdistsq(notch.v, closest);
 509 //                              if(dist < min){
 510 //                                      min = dist;
 511 //                                      feature = index + closest_t;
 512 //                              }
 513 //                      }
 514 //              }
 515 //      }
 516 //
 517 //      cpAssertWarn(feature >= 0.0, "Internal Error: No closest features detected.");
 518 //      return feature;
 519 //}
 520
 521 //static cpBool
 522 //VertexUnobscured(int count, cpVect *verts, int index, int notch_i)
 523 //{
 524 //      cpVect v = verts[notch_i];
 525 //      cpVect n = cpvnormalize(cpvsub(verts[index], v));
 526 //
 527 //      for(int i=0; i<count; i++){
 528 //              if(i == index || i == Next(i, count) || i == notch_i || i == Next(notch_i, count)) continue;
 529 //
 530 //              cpVect seg_a = verts[i];
 531 //              cpVect seg_b = verts[Next(i, count)];
 532 //
 533 //              cpFloat thing_a = cpvcross(n, cpvsub(seg_a, v));
 534 //              cpFloat thing_b = cpvcross(n, cpvsub(seg_b, v));
 535 //              if(thing_a*thing_b <= 0.0) return cpTrue;
 536 //      }
 537 //
 538 //      return cpFalse;
 539 //}
 540 //
 541 //static cpFloat
 542 //FindSteiner4(int count, cpVect *verts, struct Notch notch, cpFloat *convexity)
 543 //{
 544 //      cpFloat min = INFINITY;
 545 //      cpFloat feature = -1.0;
 546 //
 547 //      for(int i=Next(notch.b, count); i!=notch.a; i=Next(i, count)){
 548 //              cpVect v = verts[i];
 549 //              cpFloat weight = (1.0 + 0.1*convexity[i])/(1.0*cpvdist(notch.v, v));
 550 //
 551 //              if(weight <= min && VertexUnobscured(count, verts, i, notch.i)){
 552 //                      min = weight;
 553 //                      feature = i;
 554 //              }
 555 //      }
 556 //
 557 //      cpAssertSoft(feature >= 0.0, "No closest features detected. This is likely due to a self intersecting polygon.");
 558 //      return feature;
 559 //}
 560
 561 static struct Notch
 562 DeepestNotch(int count, cpVect *verts, int hullCount, cpVect *hullVerts, int first, cpFloat tol)
 563 {
 564         struct Notch notch = {};
 565         int j = Next(first, count);
 566
 567         for(int i=0; i<hullCount; i++){
 568                 cpVect a = hullVerts[i];
 569                 cpVect b = hullVerts[Next(i, hullCount)];
 570
 571                 // TODO use a cross check instead?
 572                 cpVect n = cpvnormalize(cpvrperp(cpvsub(a, b)));
 573                 cpFloat d = cpvdot(n, a);
 574
 575                 cpVect v = verts[j];
 576                 while(!cpveql(v, b)){
 577                         cpFloat depth = cpvdot(n, v) - d;
 578
 579                         if(depth > notch.d){
 580                                 notch.d = depth;
 581                                 notch.i = j;
 582                                 notch.v = v;
 583                                 notch.n = n;
 584                         }
 585
 586                         j = Next(j, count);
 587                         v = verts[j];
 588                 }
 589
 590                 j = Next(j, count);
 591         }
 592
 593         return notch;
 594 }
 595
 596 static inline int IMAX(int a, int b){return (a > b ? a : b);}
 597
 598 static void
 599 ApproximateConcaveDecomposition(cpVect *verts, int count, cpFloat tol, cpPolylineSet *set)
 600 {
 601         int first;
 602         cpVect *hullVerts = (cpVect*) alloca(count*sizeof(cpVect));
 603         int hullCount = cpConvexHull(count, verts, hullVerts, &first, 0.0);
 604
 605         if(hullCount != count){
 606                 struct Notch notch = DeepestNotch(count, verts, hullCount, hullVerts, first, tol);
 607
 608                 if(notch.d > tol){
 609                         cpFloat steiner_it = FindSteiner(count, verts, notch);
 610
 611                         if(steiner_it >= 0.0){
 612                                 int steiner_i = (int)steiner_it;
 613                                 cpVect steiner = cpvlerp(verts[steiner_i], verts[Next(steiner_i, count)], steiner_it - steiner_i);
 614
 615                                 // Vertex counts NOT including the steiner point.
 616                                 int sub1_count = (steiner_i - notch.i + count)%count + 1;
 617                                 int sub2_count = count - (steiner_i - notch.i + count)%count;
 618                                 cpVect *scratch = (cpVect*) alloca((IMAX(sub1_count, sub2_count) + 1)*sizeof(cpVect));
 619
 620                                 for(int i=0; i<sub1_count; i++) scratch[i] = verts[(notch.i + i)%count];
 621                                 scratch[sub1_count] = steiner;
 622                                 ApproximateConcaveDecomposition(scratch, sub1_count + 1, tol, set);
 623
 624                                 for(int i=0; i<sub2_count; i++) scratch[i] = verts[(steiner_i + 1 + i)%count];
 625                                 scratch[sub2_count] = steiner;
 626                                 ApproximateConcaveDecomposition(scratch, sub2_count + 1, tol, set);
 627
 628                                 return;
 629                         }
 630                 }
 631         }
 632
 633         cpPolyline *hull = cpPolylineMake(hullCount + 1);
 634
 635         memcpy(hull->verts, hullVerts, hullCount*sizeof(cpVect));
 636         hull->verts[hullCount] = hullVerts[0];
 637         hull->count = hullCount + 1;
 638
 639         cpPolylineSetPush(set, hull);
 640 }
 641
 642 cpPolylineSet *
 643 cpPolylineConvexDecomposition_BETA(cpPolyline *line, cpFloat tol)
 644 {
 645         cpAssertSoft(cpPolylineIsClosed(line), "Cannot decompose an open polygon.");
 646         cpAssertSoft(cpAreaForPoly(line->count, line->verts, 0.0) >= 0.0, "Winding is backwards. (Are you passing a hole?)");
 647
 648         cpPolylineSet *set = cpPolylineSetNew();
 649         ApproximateConcaveDecomposition(line->verts, line->count - 1, tol, set);
 650
 651         return set;
 652 }