(root)/iphone/common : 61 : Jigs/source/Triangulation.m

//

//  Triangulation.m

//  Jigs

//

//  Created by döme on 05.08.2009.

//  Copyright 2009 __MyCompanyName__. All rights reserved.

//

 

#import "Triangulation.h"

 

#import "geometry.h"

#import "VertexArray.h"

 

//#define SHOW_LINES 1

 

struct _bezierElementExtractorRec

{

        CGPoint*        points;

        size_t          numPoints;

        float           targetResolution;

};

 

void _bezierPathElementExtractor(void *info,

    const CGPathElement *element)

{

        struct _bezierElementExtractorRec* rec = info;

        switch(element->type)

        {

                case kCGPathElementMoveToPoint:

                        if (rec->numPoints && CGPointEqualToPoint(element->points[0], rec->points[rec->numPoints-1]))

                                break;

                        rec->points = realloc(rec->points, sizeof(*rec->points)*(rec->numPoints+1));

                        rec->points[rec->numPoints++] = element->points[0];

                        break;

                case kCGPathElementAddLineToPoint:

                {

                        CGPoint c0 = element->points[0];

                        //CGPoint c1 = element->points[1];

 

                        //if (rec->numPoints && CGPointEqualToPoint(c1, lastPoint))

                        //      break;

                        rec->points = realloc(rec->points, sizeof(*rec->points)*(rec->numPoints+1));

                        rec->points[rec->numPoints++] = c0;

                        break;

                }

                case kCGPathElementAddQuadCurveToPoint:

                {

                        CGPoint c0 = rec->points[rec->numPoints-1];

                        CGPoint c1 = element->points[0];

                        CGPoint c2 = element->points[1];

                        float approxLength = sqrtf(CGPointDoubleDot(CGPointSub(c1,c0)) + CGPointDoubleDot(CGPointSub(c2,c1)));

 

                        int numSegments = 2 + (int)(approxLength/rec->targetResolution);

                        

                        rec->points = realloc(rec->points, sizeof(*rec->points)*(rec->numPoints+numSegments));

 

                        for (int i = 0; i < numSegments; ++i)

                        {

                                float t = (i+1)/(float)numSegments;

                                rec->points[rec->numPoints+i] = quadraticPointAtT(c0, c1, c2, t);

                        }

 

                        rec->numPoints += numSegments;

                        

                        break;

                }

                case kCGPathElementAddCurveToPoint:

                {

                        CGPoint c0 = rec->points[rec->numPoints-1];

                        CGPoint c1 = element->points[0];

                        CGPoint c2 = element->points[1];

                        CGPoint c3 = element->points[2];

                        //CGPoint c3 = element->points[3];

                        float approxLength = sqrtf(CGPointDoubleDot(CGPointSub(c1, c0)) + CGPointDoubleDot(CGPointSub(c2, c1)) + CGPointDoubleDot(CGPointSub(c3, c2)));

 

                        int numSegments = 3 + (int)(approxLength/rec->targetResolution);

                        

                        rec->points = realloc(rec->points, sizeof(*rec->points)*(rec->numPoints+numSegments));

 

                        for (int i = 0; i < numSegments; ++i)

                        {

                                float t = (i+1)/(float)numSegments;

                                CGPoint p = cubicPointAtT(c0, c1, c2, c3, t);

                                rec->points[rec->numPoints+i] = p;

                        }

 

                        rec->numPoints += numSegments;

                        

                        break;

                }

                case kCGPathElementCloseSubpath:

                {

                        break;

                }

        };

}

 

void SimpleBezierPathToPolyline(CGPathRef cpath, CGPoint** outPoints, size_t* numOutPoints)

{

        struct _bezierElementExtractorRec lineRec = {NULL, 0, 5.0f};

        CGPathApply(cpath, &lineRec, _bezierPathElementExtractor);

        

//      NSLog(@"points:");

//      for (size_t i = 0; i < lineRec.numPoints; ++i)

//              NSLog(@"%f %f", lineRec.points[i].x, lineRec.points[i].y);

        

        *outPoints = lineRec.points;

        *numOutPoints = lineRec.numPoints;

}

 

struct _vertex;

typedef struct _vertex _vertex;

 

struct _edge;

typedef struct _edge _edge;

 

typedef struct _polygon

{

        _edge*          firstEdge;

        size_t          numEdges;

} _polygon;

 

struct _vertex

{

        CGPoint         pos;

        _edge**         edges;

        size_t          numEdges;

};

 

struct _edge

{

        _edge*          dual;

        _edge*          prevEdge;

        _edge*          nextEdge;

        _polygon*       polygon;

        size_t          vertices[2];

};

 

void _vertexAddEdge(_vertex* self, _edge* edge)

{

        self->edges = realloc(self->edges, sizeof(*self->edges)*(self->numEdges+1));

        self->edges[self->numEdges++] = edge;

};

 

_edge* _edgeCreate(size_t v0, size_t v1, _edge* dual, _vertex* vertices)

{

        _edge* self = calloc(1, sizeof(*self));

        

        assert(v0 != v1);

        

        self->vertices[0] = v0;

        self->vertices[1] = v1;

        self->dual = dual;

        if (dual)

                dual->dual = self;

        

        _vertexAddEdge(&vertices[v0], self);

        _vertexAddEdge(&vertices[v1], self);

 

        return self;

}

 

 

_polygon* _polyCreate(void)

{

        _polygon* self = calloc(1, sizeof(*self));

        

        return self;

}

 

void _polyRemoveEdge(_polygon* self, _edge* edge)

{

        if (edge == self->firstEdge)

                self->firstEdge = edge->nextEdge;

        

        if (edge->prevEdge)

                edge->prevEdge->nextEdge = edge->nextEdge;

        if (edge->nextEdge)

                edge->nextEdge->prevEdge = edge->prevEdge;

        edge->prevEdge = NULL;

        edge->nextEdge = NULL;

        edge->polygon = NULL;

        

        self->numEdges--;

}

 

void _polyDelete(_polygon* self)

{

        while (self->numEdges)

        {

                _edge* edge = self->firstEdge;

                _polyRemoveEdge(self, edge);

                free(edge);

        }

 

        free(self);

}

 

 

void _polyReplaceEdgesWithEdge(_polygon* self, _edge* e0, _edge* e1, _edge* replacement)

{

        if (e0->polygon == self)

                e0->polygon = NULL;

        if (e1->polygon == self)

                e1->polygon = NULL;

                

        replacement->prevEdge = e0->prevEdge;

        replacement->nextEdge = e1->nextEdge;

        if (replacement->prevEdge)

                replacement->prevEdge->nextEdge = replacement;

        if (replacement->nextEdge)

                replacement->nextEdge->prevEdge = replacement;

        

        if ((self->firstEdge == e0) || (self->firstEdge == e1))

                self->firstEdge = replacement;

 

        replacement->polygon = self;

        

        self->numEdges--;

}

 

void _polyAddEdge(_polygon* self, _edge* edge)

{

        edge->polygon = self;

        

        if (self->numEdges)

        {

                edge->nextEdge = self->firstEdge;

                edge->prevEdge = self->firstEdge->prevEdge;

                

                edge->nextEdge->prevEdge = edge;

                edge->prevEdge->nextEdge = edge;

        }

        else

        {

                self->firstEdge = edge;

                edge->nextEdge = edge;

                edge->prevEdge = edge;

        }

                

        self->numEdges++;

}

 

void polygonRobustnessCheck(_polygon* polygon, _vertex* vertices)

{

        _edge* edge0 = polygon->firstEdge;

        for (size_t i = 0; i < polygon->numEdges; ++i, edge0 = edge0->nextEdge)

        {

                CGPoint a0 = vertices[edge0->vertices[0]].pos;

                CGPoint a1 = vertices[edge0->vertices[1]].pos;

                

                assert(!CGPointEqualToPoint(a0, a1));

                

                _edge* edge1 = edge0->nextEdge->nextEdge;

                for (size_t j = i+2; j < polygon->numEdges; ++j, edge1 = edge1->nextEdge)

                {

                        CGPoint b0 = vertices[edge1->vertices[0]].pos;

                        CGPoint b1 = vertices[edge1->vertices[1]].pos;

                        

                        if (CGLineSegmentsIntersect(a0,a1,b0,b1))

                        {

                                NSLog(@"oops, found a baddie");

                        }

                        

                }

        }

}

 

_polygon* triangulatePolygon(_polygon* polygon, _vertex* vertices)

{

        if (polygon->numEdges < 4)

                return NULL;

 

        

        //NSMutableArray* rejectionList = [NSMutableArray array];;

        

        _edge* edge0 = polygon->firstEdge;

        for (size_t i = 0; i < polygon->numEdges; ++i, edge0 = edge0->nextEdge)

        {

                _edge* edge1 = edge0->nextEdge;

 

                assert(edge0->vertices[1] == edge1->vertices[0]);

 

                CGPoint p0 = vertices[edge0->vertices[0]].pos;

                CGPoint p1 = vertices[edge0->vertices[1]].pos;

                CGPoint p2 = vertices[edge1->vertices[1]].pos;

                CGPoint e01 = CGPointSub(p1, p0);

                CGPoint e12 = CGPointSub(p2, p1);

                

                float ecross = CGPointCross(e01, e12);

                

                if (ecross < 0.0f)

                {       

                        //[rejectionList addObject: [NSString stringWithFormat: @"wrong winding %zu %zu, %f", i0,i1, ecross]];

                        continue;

                }

                        

                // if the third edge would be in correct winding order, we need to make sure it's also

                //      1) within the adjacent edges

                //      2) not intersecting non-adjacent edges

                

 

                size_t numNonEdges = polygon->numEdges - 3;

                

                int intersectFound = 0;

                

                _edge* nonEdge = edge1->nextEdge;

                for (size_t j = 0; j < numNonEdges; ++j, nonEdge = nonEdge->nextEdge)

                {

                        CGPoint x = vertices[nonEdge->vertices[1]].pos;

                        

                        

                        if (CGPointInTriangle(x, p0, p1, p2))

                        {

                                intersectFound = 1;

                                //[rejectionList addObject: [NSString stringWithFormat: @"vertex in triangle %zu %zu X %zu", i0,i1, nonEdge->vertices[0]]];

                                break;

                        }

                }

                

                if (intersectFound)

                {

                        continue;

                }

        

                // the new edge doesn't intersect anything, so we can go on and create the new triangle

                

                _edge* edge2 = _edgeCreate(edge1->vertices[1], edge0->vertices[0], NULL, vertices);

                _edge* edgeRedux = _edgeCreate(edge0->vertices[0], edge1->vertices[1], edge2, vertices);

 

                _polyReplaceEdgesWithEdge(polygon, edge0, edge1, edgeRedux); // important to replace first, due to edge prev/next pointers

 

                _polygon* reducedPoly = _polyCreate();

                _polyAddEdge(reducedPoly, edge0);

                _polyAddEdge(reducedPoly, edge1);

                _polyAddEdge(reducedPoly, edge2);

                

                assert(edge0->vertices[1] == edge1->vertices[0]);

                assert(edge1->vertices[1] == edge2->vertices[0]);

                assert(edge2->vertices[1] == edge0->vertices[0]);

                

                assert(edge0->vertices[0] == edgeRedux->vertices[0]);

                assert(edgeRedux->vertices[1] == edge1->vertices[1]);

 

 

                

                return reducedPoly;

        }

        

        polygonRobustnessCheck(polygon, vertices);

        

        //NSLog(@"%@", rejectionList);

        

        return NULL;

}

 

long edgeCanBeFlipped(_edge* edge, _vertex* vertices)

{

        if (!edge->dual)

                return 0;

        if (edge->polygon->numEdges != 3)

                return 0;

        if (edge->dual->polygon->numEdges != 3)

                return 0;

        

        return 1;

}

 

long edgeShouldBeFlipped(_edge* edge, _vertex* vertices)

{       

        CGPoint d0 = vertices[edge->dual->nextEdge->vertices[1]].pos;

        CGPoint a0 = vertices[edge->vertices[0]].pos;

        CGPoint b0 = vertices[edge->vertices[1]].pos;

        CGPoint c0 = vertices[edge->nextEdge->vertices[1]].pos;

        

        if (CGPointInCircumCircule(d0, a0, b0, c0))

                return 1;

 

        CGPoint d1 = vertices[edge->nextEdge->vertices[1]].pos;

        CGPoint a1 = vertices[edge->dual->vertices[0]].pos;

        CGPoint b1 = vertices[edge->dual->vertices[1]].pos;

        CGPoint c1 = vertices[edge->dual->nextEdge->vertices[1]].pos;

        

        if (CGPointInCircumCircule(d1, a1, b1, c1))

                return 1;

        

        return 0;

}

 

void flipEdge(_edge* edge)

{

        _polygon* p0 = edge->polygon;

        _polygon* p1 = edge->dual->polygon;

        _edge* a0 = edge;

        _edge* b0 = a0->nextEdge;

        _edge* c0 = b0->nextEdge;

        _edge* a1 = edge->dual;

        _edge* b1 = a1->nextEdge;

        _edge* c1 = b1->nextEdge;

        

        a0->nextEdge = c0;

        a0->prevEdge = b1;

        b0->nextEdge = a1;

        b0->prevEdge = c1;

        c0->nextEdge = b1;

        c0->prevEdge = a0;

        a1->nextEdge = c1;

        a1->prevEdge = b0;

        b1->nextEdge = a0;

        b1->prevEdge = c0;

        c1->nextEdge = b0;

        c1->prevEdge = a1;

 

        if (b0 == p0->firstEdge)

                p0->firstEdge = a0;

        if (b1 == p1->firstEdge)

                p1->firstEdge = a1;

 

        b0->polygon = p1;

        b1->polygon = p0;

}

 

void flipEdgesNextToNewPolygon(_polygon* polygon, _vertex* vertices)

{

        if (polygon->numEdges != 3)

                return;

        

        _edge* edge = polygon->firstEdge;

        for (size_t i = 0; i < 3; ++i, edge = edge->nextEdge)

        {

                if (edgeCanBeFlipped(edge, vertices) && edgeShouldBeFlipped(edge, vertices))

                {

                        //NSLog(@"flipping edge");

                        flipEdge(edge);

                }

        }

}

 

_polygon** triangulatePolygons(_polygon** polygons, size_t* numPolygonsPtr, _vertex* vertices, size_t numVertices)

{

        // starting at the last polygon on the list, we try to create a correctly winded triangle out of it

        

        size_t numPolygons = *numPolygonsPtr;

        

        for (size_t i = 0; i < numPolygons; ++i)

        {

                _polygon* reducedPoly = triangulatePolygon(polygons[i], vertices);

                

                if (reducedPoly)

                {

                        polygons = realloc(polygons, sizeof(*polygons)*(numPolygons+1));

                        polygons[numPolygons++] = reducedPoly;

                        --i;

                        

                        //flipEdgesNextToNewPolygon(reducedPoly, vertices);

                        

                //      NSLog(@"reduced to: %d %d %d", reducedPoly->edges[0]->vertices[0], reducedPoly->edges[1]->vertices[0], reducedPoly->edges[2]->vertices[0]);

                //      NSLog(@"reduced to: %d %d %d", reducedPoly->edges[1]->vertices[1], reducedPoly->edges[2]->vertices[1], reducedPoly->edges[0]->vertices[1]);

                }

                else if (polygons[i]->numEdges > 3)

                {

                        NSLog(@"Badunka, why no triangle, instead we got a %zd-angle (%zd)", polygons[i]->numEdges, numVertices);

                        _edge* edge = polygons[i]->firstEdge;

                        for (size_t j = 0; j < polygons[i]->numEdges; ++j, edge = edge->nextEdge)

                                NSLog(@"  %u,%u", edge->vertices[0], edge->vertices[1]);

                }

                

        }

        

        *numPolygonsPtr = numPolygons;

        return polygons;

}

 

VertexArray* TriangulateOutline(CGPoint* inPoints, size_t numInPoints)

{

        _polygon* initialPoly = _polyCreate();

        

        _vertex* vertices = calloc(numInPoints, sizeof(*vertices));

        

        for (size_t i = 0; i < numInPoints; ++i)

        {

                vertices[i].pos = inPoints[i];

                if (i > 0)

                        assert(!CGPointEqualToPoint(vertices[i-1].pos, vertices[i].pos));

        }

        

        if (CGPointEqualToPoint(vertices[numInPoints-1].pos, vertices[0].pos))

                numInPoints--;

        

        for (size_t i = 0; i+1 < numInPoints; ++i)

        {

                _polyAddEdge(initialPoly, _edgeCreate(i, i+1, NULL, vertices));

        }

        _polyAddEdge(initialPoly, _edgeCreate(numInPoints-1, 0, NULL, vertices));

        

        polygonRobustnessCheck(initialPoly, vertices);

 

        _polygon** polygons = calloc(1, sizeof(*polygons));

        polygons[0] = initialPoly;

        size_t numPolygons = 1;

        

        polygons = triangulatePolygons(polygons, &numPolygons, vertices, numInPoints);

        

        

        VertexArray* var = [[[VertexArray alloc] init] autorelease];

        

#ifdef SHOW_LINES

        var->mode = GL_LINES;

#else

        var->mode = GL_TRIANGLES;

#endif  

 

        var->vertices = calloc(numInPoints, sizeof(*var->vertices));

        var->numVertices = numInPoints;

        

        for (size_t i = 0; i < numInPoints; ++i)

        {

                PositionNormalTex3f3f2f* vertex = var->vertices+i;

                

                vertex->pos[0] = vertices[i].pos.x;

                vertex->pos[1] = vertices[i].pos.y;

                vertex->pos[2] = 0.0f;

                vertex->normal[0] = 0.0f;

                vertex->normal[1] = 0.0f;

                vertex->normal[2] = 1.0f;

                vertex->texcoord[0] = vertices[i].pos.x;

                vertex->texcoord[1] = vertices[i].pos.y;

        }

 

        

        size_t numIndices = 0;

#ifdef SHOW_LINES

        for (size_t i = 0; i < numPolygons; ++i)

                numIndices += 2*polygons[i]->numEdges;

        uint16_t* indices = calloc(numIndices, sizeof(*indices));

        numIndices = 0;

#else

        uint16_t* indices = calloc(3*numPolygons, sizeof(*indices));

#endif

        for (size_t i = 0; i < numPolygons; ++i)

        {

                _polygon* polygon = polygons[i];

                if (polygon->numEdges != 3)

                {

                        NSLog(@"whoops, polygon with %d sides instead of 3, skipping.", polygon->numEdges);

                #ifndef SHOW_LINES

                        continue;

                #endif

                }

                _edge* edge = polygon->firstEdge;

/*

                assert(polygon->edges[0]->vertices[0] != polygon->edges[1]->vertices[0]);

                assert(polygon->edges[1]->vertices[0] != polygon->edges[2]->vertices[0]);

                assert(polygon->edges[2]->vertices[0] != polygon->edges[0]->vertices[0]);

                assert(polygon->edges[0]->vertices[0] < numInPoints);

                assert(polygon->edges[1]->vertices[0] < numInPoints);

                assert(polygon->edges[2]->vertices[0] < numInPoints);

                assert(polygon->edges[0]->vertices[1] < numInPoints);

                assert(polygon->edges[1]->vertices[1] < numInPoints);

                assert(polygon->edges[2]->vertices[1] < numInPoints);

*/

        #ifdef SHOW_LINES

                //if (polygon->numEdges != 3)

                        for (size_t j = 0; j < polygon->numEdges; ++j, edge = edge->nextEdge)

                        {

                                indices[numIndices++] = edge->vertices[0];

                                indices[numIndices++] = edge->vertices[1];

                        }

        #else

                indices[numIndices++] = edge->vertices[0];

                edge = edge->nextEdge;

                indices[numIndices++] = edge->vertices[0];

                edge = edge->nextEdge;

                indices[numIndices++] = edge->vertices[0];

        #endif

 

        }

        

#ifdef SHOW_LINES

        if (!numIndices)

                numIndices++;

#endif

 

        var->numIndices = numIndices;

        var->indices = indices;

        

        

        for (size_t i = 0; i < numPolygons; ++i)

        {

                _polygon* polygon = polygons[i];

                _polyDelete(polygon);

        }

        free(polygons);

        for (size_t i = 0; i < numInPoints; ++i)

        {

                _vertex v = vertices[i];

                free(v.edges);

        }

 

        free(vertices);

        

//      NSLog(@"number of generated polygons: %d", numPolygons);

 

        return var;

}

 

#define SQUISH_FORWARD_INNER            1

#define SQUISH_FORWARD_OUTER            2

#define SQUISH_BACKWARD_INNER           4

#define SQUISH_BACKWARD_OUTER           8

#define SQUISH_IGNORE_POINT_INNER       16

#define SQUISH_IGNORE_POINT_OUTER       32

 

void unsquishyOutline(CGPoint* points, CGPoint* innerPoints, CGPoint* outerPoints, size_t numPoints, float thickness)

{

        CGPoint* squishedInnerPoints = calloc(sizeof(*squishedInnerPoints), 2*numPoints);

        CGPoint* squishedOuterPoints = squishedInnerPoints + numPoints;

        uint8_t* squishedCorners = calloc(sizeof(*squishedCorners), numPoints);

 

        

        for (size_t i = 0; i < numPoints; ++i)

        {

                size_t i0 = (i) % numPoints;

                size_t i1 = (i+1) % numPoints;

                size_t i2 = (i+2) % numPoints;

                

                CGPoint p0 = points[i0];

                CGPoint p1 = points[i1];

                CGPoint p2 = points[i2];

 

                CGPoint pi0 = innerPoints[i0];

                CGPoint pi1 = innerPoints[i1];

                CGPoint pi2 = innerPoints[i2];

 

                CGPoint po0 = outerPoints[i0];

                CGPoint po1 = outerPoints[i1];

                CGPoint po2 = outerPoints[i2];

 

                squishedInnerPoints[i1] = p1;

                squishedOuterPoints[i1] = p1;

                

                squishedCorners[i1] = squishedCorners[i1]

                        | SQUISH_BACKWARD_OUTER*CGLineSegmentsIntersect(p0, po0, p1, po1)

                        | SQUISH_BACKWARD_INNER*CGLineSegmentsIntersect(p0, pi0, p1, pi1)

                        | SQUISH_FORWARD_OUTER*CGLineSegmentsIntersect(p2, po2, p1, po1)

                        | SQUISH_FORWARD_INNER*CGLineSegmentsIntersect(p2, pi2, p1, pi1);

        }

 

        size_t sbegin = 0;

        for (sbegin = 0; sbegin < numPoints; ++sbegin)

        {

 

                if (!(squishedCorners[sbegin] & (SQUISH_FORWARD_OUTER | SQUISH_FORWARD_INNER)))

                        break;

        }

        

        long didChange = 1;

        //while(didChange)

        {

                didChange = 0;

                // now that corners have been marked, walk em

                for (size_t ii = 0; ii < numPoints; ++ii)

                {

                        size_t i = (sbegin + ii) % numPoints;

                        if (!(squishedCorners[i] & (SQUISH_FORWARD_OUTER | SQUISH_FORWARD_INNER)))

                                continue;

                        

                        if ((squishedCorners[i] & SQUISH_FORWARD_INNER) && !(squishedCorners[i] & SQUISH_BACKWARD_INNER) && !(squishedCorners[i] & SQUISH_IGNORE_POINT_INNER))

                        {

                                size_t innerEnd = (i+1) % numPoints;

                                while ((innerEnd != i) && ((squishedCorners[innerEnd] & SQUISH_FORWARD_INNER) || (squishedCorners[innerEnd] & SQUISH_IGNORE_POINT_INNER)))

                                        innerEnd = (innerEnd+1) % numPoints;

                                        

                                if (innerEnd != i) // that'd mean we went all the way around

                                {

                                        size_t i0 = (i-1) % numPoints;

                                        size_t i1 = i;

                                        size_t i2 = innerEnd;

                                        size_t i3 = (innerEnd+1) % numPoints;

                                        CGPoint pp0 = squishedInnerPoints[i0];

                                        CGPoint pp1 = squishedInnerPoints[i1];

                                        CGPoint pp2 = squishedInnerPoints[i2];

                                        CGPoint pp3 = squishedInnerPoints[i3];

                                        

                                        CGPoint pp12 = CGLineIntersectionPoint(pp0, pp1, pp2, pp3);

                                        

                                        CGPoint e01 = CGPointSub(pp12, pp0);

                                        CGPoint e12 = CGPointSub(pp3, pp12);

 

                                        CGPoint n01 = CGPointScale(CGPointNormalize(CGPointMake(-e01.y, e01.x)), thickness*0.5f);

                                        CGPoint n12 = CGPointScale(CGPointNormalize(CGPointMake(-e12.y, e12.x)), thickness*0.5f);

                                        

                                        assert(!isnan(n01.x) && !isnan(n01.y));

                                        assert(!isnan(n12.x) && !isnan(n12.y));

                                        

                                        CGPoint hn = CGPointReverseProject(n01, CGPointAdd(n01,n12));

                                        

                                        CGPoint ip = CGPointAdd(pp12, hn);

 

                                        for (size_t k = i; k != (innerEnd+1) % numPoints; k = (k+1) % numPoints)

                                        {

                                                squishedInnerPoints[k] = pp12;

                                                innerPoints[k] = ip;

                                                //squishedCorners[k] &= ~SQUISH_FORWARD_INNER;

                                                if ((k != i) && (k != innerEnd))

                                                        squishedCorners[k] |= SQUISH_IGNORE_POINT_INNER;

                                        }

                                        didChange = 1;

                                }

                        }

                        if ((squishedCorners[i] & SQUISH_FORWARD_OUTER) && !(squishedCorners[i] & SQUISH_BACKWARD_OUTER) && !(squishedCorners[i] & SQUISH_IGNORE_POINT_OUTER))

                        {

                                size_t outerEnd = (i+1) % numPoints;

                                while ((outerEnd != i) && ((squishedCorners[outerEnd] & SQUISH_FORWARD_OUTER) || (squishedCorners[outerEnd] & SQUISH_IGNORE_POINT_OUTER)))

                                        outerEnd = (outerEnd+1) % numPoints;

                                        

                                if (outerEnd != i) // that'd mean we went all the way around

                                {

                                        size_t i0 = (i-1) % numPoints;

                                        size_t i1 = i;

                                        size_t i2 = outerEnd;

                                        size_t i3 = (outerEnd+1) % numPoints;

                                        CGPoint pp0 = squishedOuterPoints[i0];

                                        CGPoint pp1 = squishedOuterPoints[i1];

                                        CGPoint pp2 = squishedOuterPoints[i2];

                                        CGPoint pp3 = squishedOuterPoints[i3];

                                        

                                        CGPoint pp12 = CGLineIntersectionPoint(pp0, pp1, pp2, pp3);

                                        

                                        CGPoint e01 = CGPointSub(pp12, pp0);

                                        CGPoint e12 = CGPointSub(pp3, pp12);

 

                                        CGPoint n01 = CGPointScale(CGPointNormalize(CGPointMake(-e01.y, e01.x)), thickness*0.5f);

                                        CGPoint n12 = CGPointScale(CGPointNormalize(CGPointMake(-e12.y, e12.x)), thickness*0.5f);

                                        

                                        assert(!isnan(n01.x) && !isnan(n01.y));

                                        assert(!isnan(n12.x) && !isnan(n12.y));

                                        

                                        CGPoint hn = CGPointReverseProject(n01, CGPointAdd(n01,n12));

                                        

                                        CGPoint ip = CGPointSub(pp12, hn);

 

                                        for (size_t k = i; k != (outerEnd+1) % numPoints; k = (k+1) % numPoints)

                                        {

                                                squishedOuterPoints[k] = pp12;

                                                outerPoints[k] = ip;

                                                //squishedCorners[k] &= ~SQUISH_FORWARD_OUTER;

                                                if ((k != i) && (k != outerEnd))

                                                        squishedCorners[k] |= SQUISH_IGNORE_POINT_OUTER;

                                        }

                                        didChange = 1;

                                }

                        }

 

                }

 

                for (size_t i = 0; i < numPoints; ++i)

                {

                        squishedCorners[i] &= ~(SQUISH_FORWARD_INNER|SQUISH_BACKWARD_INNER|SQUISH_FORWARD_OUTER|SQUISH_BACKWARD_OUTER);

                }

                

                for (size_t i = 0; i < numPoints; ++i)

                {

                        size_t i0 = (i) % numPoints;

                        size_t i1 = (i+1) % numPoints;

                        size_t i2 = (i+2) % numPoints;

                        

                        while (squishedCorners[i0] & SQUISH_IGNORE_POINT_INNER)

                                i0 = (i0-1) % numPoints;

                        while (squishedCorners[i2] & SQUISH_IGNORE_POINT_INNER)

                                i2 = (i2+1) % numPoints;

 

                        CGPoint pii0 = squishedInnerPoints[i0];

                        CGPoint pii1 = squishedInnerPoints[i1];

                        CGPoint pii2 = squishedInnerPoints[i2];

 

 

                        CGPoint pi0 = innerPoints[i0];

                        CGPoint pi1 = innerPoints[i1];

                        CGPoint pi2 = innerPoints[i2];

 

                        

                        if (!(squishedCorners[i1] & SQUISH_IGNORE_POINT_INNER))

                        {

                                squishedCorners[i1] &= ~(SQUISH_FORWARD_INNER|SQUISH_BACKWARD_INNER);

                                squishedCorners[i1] |=

                                        SQUISH_BACKWARD_INNER*CGLineSegmentsIntersect(pii0, pi0, pii1, pi1)

                                        | SQUISH_FORWARD_INNER*CGLineSegmentsIntersect(pii2, pi2, pii1, pi1);

                        }                       

                }

 

                for (size_t i = 0; i < numPoints; ++i)

                {

                        size_t i0 = (i) % numPoints;

                        size_t i1 = (i+1) % numPoints;

                        size_t i2 = (i+2) % numPoints;

                        

                        while (squishedCorners[i0] & SQUISH_IGNORE_POINT_OUTER)

                                i0 = (i0-1) % numPoints;

                        while (squishedCorners[i2] & SQUISH_IGNORE_POINT_OUTER)

                                i2 = (i2+1) % numPoints;

 

                        CGPoint pii0 = squishedOuterPoints[i0];

                        CGPoint pii1 = squishedOuterPoints[i1];

                        CGPoint pii2 = squishedOuterPoints[i2];

 

 

                        CGPoint pi0 = outerPoints[i0];

                        CGPoint pi1 = outerPoints[i1];

                        CGPoint pi2 = outerPoints[i2];

 

                        

                        if (!(squishedCorners[i1] & SQUISH_IGNORE_POINT_OUTER))

                        {

                                squishedCorners[i1] &= ~(SQUISH_FORWARD_OUTER|SQUISH_BACKWARD_OUTER);

                                squishedCorners[i1] |=

                                        SQUISH_BACKWARD_OUTER*CGLineSegmentsIntersect(pii0, pi0, pii1, pi1)

                                        | SQUISH_FORWARD_OUTER*CGLineSegmentsIntersect(pii2, pi2, pii1, pi1);

                        }                       

                }

 

        }

        free(squishedInnerPoints);

        

        free(squishedCorners);

 

}

 

CGPoint* createOutline(CGPoint* points, size_t numPoints, float thickness)

{

        CGPoint* innerPoints = calloc(sizeof(*innerPoints), 2*numPoints);

        CGPoint* outerPoints = innerPoints + numPoints;

        

        for (size_t i = 0; i < numPoints; ++i)

        {

                size_t i0 = (i) % numPoints;

                size_t i1 = (i+1) % numPoints;

                size_t i2 = (i+2) % numPoints;

                

                CGPoint p0 = points[i0];

                CGPoint p1 = points[i1];

                CGPoint p2 = points[i2];

                

                CGPoint e01 = CGPointSub(p1,p0);

                CGPoint e12 = CGPointSub(p2,p1);

                

                CGPoint n01 = CGPointScale(CGPointNormalize(CGPointMake(-e01.y, e01.x)), thickness*0.5f);

                CGPoint n12 = CGPointScale(CGPointNormalize(CGPointMake(-e12.y, e12.x)), thickness*0.5f);

                

                assert(!isnan(n01.x) && !isnan(n01.y));

                assert(!isnan(n12.x) && !isnan(n12.y));

                

                CGPoint hn = CGPointReverseProject(n01, CGPointAdd(n01,n12));

                

                //innerNormals[i1] = hn;

                //outerNormals[i1] = CGPointScale(hn, -1.0);

                

                innerPoints[i1] = CGPointAdd(p1, hn);

                outerPoints[i1] = CGPointSub(p1, hn);

        }

 

//      unsquishyOutline(points, innerPoints, outerPoints, numPoints, thickness);

        

        return innerPoints;

}

 

 

void _bezierPathDataExtractor(void *info, const CGPathElement *element)

{

        NSMutableData* data = info;

        [data appendBytes: &element->type length: sizeof(element->type)];

        switch(element->type)

        {

                case kCGPathElementMoveToPoint:

                        [data appendBytes: element->points length: sizeof(*element->points)];

                        break;

                case kCGPathElementAddLineToPoint:

                {

                        [data appendBytes: element->points length: sizeof(*element->points)];

                        break;

                }

                case kCGPathElementAddQuadCurveToPoint:

                {

                        [data appendBytes: element->points length: sizeof(*element->points)*2];

                        

                        break;

                }

                case kCGPathElementAddCurveToPoint:

                {

                        [data appendBytes: element->points length: sizeof(*element->points)*3];

                        

                        break;

                }

                case kCGPathElementCloseSubpath:

                {

                        break;

                }

        };

}

 

NSData* BezierPathToData(CGPathRef cpath)

{

        NSMutableData* data = [NSMutableData data];

        CGPathApply(cpath, data, _bezierPathDataExtractor);

 

        return data;

}

 

CGPathRef CreateBezierPathFromData(NSData* data)

{

        CGMutablePathRef path = CGPathCreateMutable();

        const void* bytes = [data bytes];

        size_t nbytes = [data length];

        size_t i = 0;

        while (i < nbytes)

        {

                CGPathElementType type = *((CGPathElementType*)(bytes+i));

                i += sizeof(type);

                switch(type)

                {

                        case kCGPathElementMoveToPoint:

                        {

                                CGPoint p;

                                memcpy(&p, bytes+i, sizeof(CGPoint));

                                i += sizeof(CGPoint);

                                CGPathMoveToPoint(path, nil, p.x, p.y);

                                break;

                        }

                        case kCGPathElementAddLineToPoint:

                        {

                                CGPoint p;

                                memcpy(&p, bytes+i, sizeof(CGPoint));

                                i += sizeof(CGPoint);

                                CGPathAddLineToPoint(path, nil, p.x, p.y);

                                break;

                        }

                        case kCGPathElementAddQuadCurveToPoint:

                        {

                                CGPoint p[2];

                                memcpy(p, bytes+i, sizeof(CGPoint)*2);

                                i += sizeof(CGPoint)*2;

                                CGPathAddQuadCurveToPoint(path, nil, p[0].x, p[0].y, p[1].x, p[1].y);                           

                                break;

                        }

                        case kCGPathElementAddCurveToPoint:

                        {

                                CGPoint p[3];

                                memcpy(p, bytes+i, sizeof(CGPoint)*3);

                                i += sizeof(CGPoint)*3;

                                CGPathAddCurveToPoint(path, nil, p[0].x, p[0].y, p[1].x, p[1].y, p[2].x, p[2].y);                               

                                

                                break;

                        }

                        case kCGPathElementCloseSubpath:

                        {

                                CGPathCloseSubpath(path);                               

                                break;

                        }

                }

        }

 

        return (CGPathRef)path;

}

 

 

 

struct Spoke;

typedef struct Spoke Spoke;

 

struct Front;

typedef struct Front Front;

 

struct CollisionEstimate;

typedef struct CollisionEstimate CollisionEstimate;

 

typedef struct PolygonInsetRecord

{

        CGPoint*        vertices;

        float*          times;

        size_t          numVertices;

        uint16_t*       triangleIndices;

        size_t          numIndices;

} PolygonInsetRecord;

 

 

struct Spoke

{

        uint32_t        sourceVertexIndex, finalVertexIndex;

        CGPoint         velocity;

        float           start;

 

        Front*          leftFront;

        Front*          rightFront;

 

        size_t                          numEstimates;

        CollisionEstimate*      estimates;

};

 

struct Front

{

        Spoke*  leftSpoke;

        Spoke*  rightSpoke;

 

        CGPoint velocity;

        float   willCollapse;

        

};

 

typedef struct FrontsAndSpokesRec

{

        Front** fronts;

        size_t  numFronts;

        Spoke** spokes;

        size_t  numSpokes;

 

} FrontsAndSpokesRec;

 

enum

{

        kHitSource,

        kHitLeftRay,

        kHitRightRay,

        kHitFront,

        kHitUnknown,

        kHitLast

};

 

 

typedef struct r2

{

        float min, max;

} r2;

 

struct CollisionEstimate

{

        Front*          front;

//      Spoke*          spoke;

//      int                     face;

        r2                      range;

};

 

struct _small_pool_block

{

        size_t available, used;

        struct _small_pool_block* next;

        void* bytes;

};

 

static struct _small_pool_block*        _smallStackPoolHead = NULL;

static struct _small_pool_block*        _smallStackPoolFirstFree = NULL;

static size_t   _smallStackBaseBlockSize = 4096;

 

static void small_pool_init(void)

{

        while (_smallStackPoolHead)

        {

                struct _small_pool_block* next = _smallStackPoolHead->next;

                free(_smallStackPoolHead);

                _smallStackPoolHead = next;

        }

        _smallStackPoolHead = calloc(1,_smallStackBaseBlockSize);

        _smallStackPoolHead->bytes = _smallStackPoolHead+1;

        _smallStackPoolHead->available = _smallStackBaseBlockSize - sizeof(struct _small_pool_block);

        _smallStackPoolFirstFree = _smallStackPoolHead;

}

 

static void small_pool_destroy(void)

{

        while (_smallStackPoolHead)

        {

                struct _small_pool_block* next = _smallStackPoolHead->next;

                free(_smallStackPoolHead);

                _smallStackPoolHead = next;

        }

        _smallStackBaseBlockSize = 4096;

        _smallStackPoolFirstFree = NULL;

}

 

static void* small_malloc(size_t s)

{

        struct _small_pool_block* freeBlock = _smallStackPoolFirstFree;

        while (s > freeBlock->available)

        {

                if (freeBlock->next)

                        freeBlock = freeBlock->next;

                else

                {

                        size_t size = MAX(_smallStackBaseBlockSize, s + sizeof(struct _small_pool_block));

                        freeBlock->next = calloc(1, size);

                        _smallStackBaseBlockSize *= 2;

                        freeBlock = freeBlock->next;

                        freeBlock->bytes = (void*)freeBlock + sizeof(struct _small_pool_block);

                        freeBlock->available = size - sizeof(struct _small_pool_block);

                        break;

                }

        }

        

        

        void* result = freeBlock->bytes + freeBlock->used;

        

        freeBlock->used += s;

        freeBlock->available -= s;

        

        assert(result);

        return result;

}

 

static r2 _rayInPlane(CGPoint pr0, CGPoint v, CGPoint pp0, CGPoint pn)

{

        r2 range = {INFINITY, -INFINITY};

 

        CGPoint d = CGPointSub(pp0, pr0);

        CGPoint n = CGPointNormalize(pn);

        int rayTowardsPlaneNormal = CGPointDot(n, v) > 0.0f;

        

        float td = CGPointDot(d, n);

        float tr = CGPointDot(v, n);

        

        if (fabsf(tr) < FLT_EPSILON)

                return range;

        

        assert(!isnan(tr) && !isnan(td));

        

        float t = td/tr;

        if (rayTowardsPlaneNormal)

        {

                range.min = t;

                range.max = INFINITY;

        }

        else

        {

                range.max = t;

                range.min = -INFINITY;

        }

        

        return range;

        

}

 

static int _r2containsValue(r2 range, float x)

{

        return (range.min <= x) && (range.max >= x);

}

 

static r2 _r2intersect(r2 ra, r2 rb)

{

        return (r2){MAX(ra.min, rb.min), MIN(ra.max, rb.max)};

}

 

static int _r2isEmpty(r2 r)

{

        return r.min >= r.max;

}

 

static int _frontLoopsBelow(Front* front, int num)

{

        Front* f2 = front;

        for (int i = 0; i < num; ++i)

        {

                f2 = f2->leftSpoke->leftFront;

                if (f2 == front)

                        return 1;

        }

        return 0;

}

 

 

static r2 _estimateSpokeHittingFront(Spoke* spoke, Front* front, CGPoint* vertices)

{

        // front plane wrong???

        

        

 

        CGPoint r0 = CGPointAdd(vertices[spoke->sourceVertexIndex], CGPointScale(spoke->velocity, -spoke->start));

 

 

        Spoke* lspoke = front->leftSpoke;

        Spoke* rspoke = front->rightSpoke;

        CGPoint pl0 = CGPointAdd(vertices[lspoke->sourceVertexIndex], CGPointScale(lspoke->velocity, -lspoke->start));

        CGPoint pr0 = CGPointAdd(vertices[rspoke->sourceVertexIndex], CGPointScale(rspoke->velocity, -rspoke->start));

 

        CGPoint rays[4] = {spoke->velocity, spoke->velocity, spoke->velocity, CGPointSub(spoke->velocity, front->velocity)};

 

        CGPoint ppoints[4] = {  pl0,

                                                        pl0,

                                                        pr0,

                                                        pr0 // a point at t=0

                                                };

        CGPoint pnorms[4] = {   CGPointNormalize(front->velocity),

                                                        CGPointNormalize(CGPointNegate(CGPointNormal(lspoke->velocity))),

                                                        CGPointNormalize(CGPointNormal(rspoke->velocity)),

                                                        CGPointNormalize(CGPointNegate(front->velocity))

                                                };

                                                

        r2      ranges[4] = {{INFINITY,-INFINITY}, {INFINITY,-INFINITY}, {INFINITY,-INFINITY}, {INFINITY,-INFINITY}};

        

        

        for (size_t i = 0; i < 4; ++i)

        {

                ranges[i] = _rayInPlane(r0, rays[i], ppoints[i], pnorms[i]);

        }

        

        r2 minorr = _r2intersect(_r2intersect(ranges[0], ranges[1]), ranges[2]);

        r2 finalr = _r2intersect(minorr, ranges[3]);

 

        if ((finalr.min != ranges[3].min) || (CGPointDot(spoke->velocity, front->velocity) > 0.0f))     // if the spoke doesn't enter through the front, it doesn't count

                return (r2){INFINITY,-INFINITY};

 

        return finalr;

}

 

static int _sortCompareEstimates(const void* _a, const void* _b)

{

        const CollisionEstimate* a = *((const CollisionEstimate**)_a);

        const CollisionEstimate* b = *((const CollisionEstimate**)_b);

        

        if (a->range.min < b->range.min)

                return -1;

        else if (a->range.min > b->range.min)

                return 1;

        else

                return 0;

}

 

static int _sortCompareFronts(const void* _a, const void* _b)

{

        const Front* a = *((const Front**)_a);

        const Front* b = *((const Front**)_b);

        float timea = a->willCollapse;

        float timeb = b->willCollapse;

 

/*

        if (a->numEstimates)

                timea = MIN(timea, a->estimates[0].range.min);

        if (b->numEstimates)

                timeb = MIN(timeb, b->estimates[0].range.min);

*/

        if (timea < timeb)

                return -1;

        else if (timea > timeb)

                return 1;

        else

                return 0;

}

static int _sortCompareSpokes(const void* _a, const void* _b)

{

        const Spoke* a = *((const Spoke**)_a);

        const Spoke* b = *((const Spoke**)_b);

        float timea = INFINITY;

        float timeb = INFINITY;

 

 

        if (a->numEstimates)

                timea = a->estimates[0].range.min;

        if (b->numEstimates)

                timeb = b->estimates[0].range.min;

 

        if (timea < timeb)

                return -1;

        else if (timea > timeb)

                return 1;

        else

                return 0;

}

 

 

static void _sortFronts(Front** fronts, size_t numFronts)

{       

        mergesort(fronts, numFronts, sizeof(*fronts), _sortCompareFronts);      

}

 

static void _sortSpokes(Spoke** spokes, size_t numSpokes)

{

        for (size_t i = 0; i < numSpokes; ++i)

                mergesort(spokes[i]->estimates, spokes[i]->numEstimates, sizeof(*spokes[i]->estimates), _sortCompareEstimates);

        

        mergesort(spokes, numSpokes, sizeof(*spokes), _sortCompareSpokes);

        

}

 

/*

static void _removeEstimateFromFront(Front* front, size_t ie)

{

        if (ie+1 != front->numEstimates)

                front->estimates[ie] = front->estimates[front->numEstimates-1];

        front->numEstimates--;

}

 

static void _redactEstimateForSpokeToFronts(Spoke* spoke, Front** fronts, size_t numFronts)

{

        for (size_t i = 0; i < numFronts; ++i)

        {

                Front* front = fronts[i];

                

                if (!front->estimates)

                        continue;

 

                for (size_t i = 0; i < front->numEstimates; ++i)

                        if (front->estimates[i].spoke == spoke)

                        {

                                _removeEstimateFromFront(front, i);

                                break;

                        }

        }

}

*/

static CollisionEstimate _estimateForSpokeToFront(Spoke* spoke, Front* front, CGPoint* vertices, float time, float maxTime)

{

        CollisionEstimate estimate = {front, {INFINITY,-INFINITY}};

 

        r2 r = _estimateSpokeHittingFront(spoke, front, vertices);

        

//      if (face == 0)

//              r.min = INFINITY;

        if (r.min > r.max)

                return estimate;

//      if ((r.max <= time) || (r.min > maxTime))

//              return estimate;

 

 

//      estimate.face = face;

        

        assert(r.min > -INFINITY);

 

        estimate.range = r;

        

        return estimate;

}

 

static float _frontStart(Front* front)

{

        return MAX(front->leftSpoke->start, front->rightSpoke->start);

}

 

static void _recomputeEstimatesForSpoke(Spoke* spoke, Front** fronts, size_t numFronts, CGPoint* vertices, size_t maxEstimates, float time, float maxTime)

{

        spoke->numEstimates = 0;

        for (size_t i = 0; i < numFronts; ++i)

        {

                Front* front = fronts[i];

                

                if ((spoke == front->leftSpoke) || (spoke == front->rightSpoke) || (front->leftSpoke->leftFront->leftSpoke == spoke) || (front->rightSpoke->rightFront->rightSpoke == spoke))

                {

                        continue;

                }

                if (_frontLoopsBelow(front, 4))

                        continue;

 

                

 

                CollisionEstimate estimate = _estimateForSpokeToFront(spoke, front, vertices, time, maxTime);

                                

                if (estimate.range.min < MAX(spoke->start, _frontStart(front)))

                        estimate.range.min = INFINITY;

                        

                if (_r2isEmpty(estimate.range))

                        continue;

 

                if (!spoke->estimates)

                        spoke->estimates = small_malloc(sizeof(*spoke->estimates)*maxEstimates);

                assert(spoke->numEstimates < maxEstimates);

                spoke->estimates[spoke->numEstimates++] = estimate;

 

        }

}

 

static uint16_t _addVertex(PolygonInsetRecord* rec, CGPoint p, float t)

{

        assert(rec->numVertices < USHRT_MAX);

        uint16_t i = rec->numVertices++;

        rec->vertices = realloc(rec->vertices, sizeof(*rec->vertices)*(rec->numVertices));

        rec->times = realloc(rec->times, sizeof(*rec->times)*(rec->numVertices));

        rec->vertices[i] = p;

        rec->times[i] = t;

        return i;

}

 

static void _addTriangle(PolygonInsetRecord* rec, uint16_t a, uint16_t b, uint16_t c)

{

        rec->triangleIndices = realloc(rec->triangleIndices, sizeof(*rec->triangleIndices)*(rec->numIndices+3));

        rec->triangleIndices[rec->numIndices++] = a;

        rec->triangleIndices[rec->numIndices++] = b;

        rec->triangleIndices[rec->numIndices++] = c;

}

 

 

static Spoke* _allocSpoke(FrontsAndSpokesRec* activeWalls, FrontsAndSpokesRec* inactiveWalls)

{

        Spoke* spoke = NULL;

        if (!inactiveWalls->numSpokes)

                spoke = small_malloc(sizeof(Spoke));

        else

        {

                spoke = inactiveWalls->spokes[--inactiveWalls->numSpokes];

        }

        activeWalls->spokes[activeWalls->numSpokes++] = spoke;

        //memset(spoke, 0x00, sizeof(*spoke));

        return spoke;

}

 

static Front* _allocFront(FrontsAndSpokesRec* activeWalls, FrontsAndSpokesRec* inactiveWalls)

{

        Front* front = NULL;

        if (!inactiveWalls->numFronts)

                front = small_malloc(sizeof(Front));

        else

        {

                front = inactiveWalls->fronts[--inactiveWalls->numFronts];

        }

        activeWalls->fronts[activeWalls->numFronts++] = front;

        //memset(front, 0x00, sizeof(*front));

        return front;

}

 

static void _deactivateFront(Front* front, FrontsAndSpokesRec* activeWalls, FrontsAndSpokesRec* inactiveWalls)

{

        //memset(front, 0xFF, sizeof(*front));

        inactiveWalls->fronts[inactiveWalls->numFronts++] = front;

        

        for (size_t i = 0; i < activeWalls->numFronts; ++i)

        {

                if (activeWalls->fronts[i] == front)

                {

                        if (i+1 < activeWalls->numFronts)

                                activeWalls->fronts[i] = activeWalls->fronts[activeWalls->numFronts-1];

                        

                        activeWalls->numFronts--;

                        break;

                }

        }

}

 

static void _deactivateSpoke(Spoke* spoke, FrontsAndSpokesRec* activeWalls, FrontsAndSpokesRec* inactiveWalls)

{

        //memset(spoke, 0xFF, sizeof(*spoke));

        inactiveWalls->spokes[inactiveWalls->numSpokes++] = spoke;

        

        for (size_t i = 0; i < activeWalls->numSpokes; ++i)

        {

                if (activeWalls->spokes[i] == spoke)

                {

                        if (i < activeWalls->numSpokes-1)

                                activeWalls->spokes[i] = activeWalls->spokes[activeWalls->numSpokes-1];

                        

                        activeWalls->numSpokes--;

                        break;

                }

        }

}

 

static void _updateCollapseTime(Front* front, CGPoint* vertices, float now)

{

        

        Spoke* spoke0 = front->leftSpoke;

        Spoke* spoke1 = front->rightSpoke;

        CGPoint a = vertices[spoke0->sourceVertexIndex], b = vertices[spoke1->sourceVertexIndex];

        

        CGPoint va = spoke0->velocity;

        CGPoint vb = spoke1->velocity;

        CGPoint vab = CGPointSub(vb,va);

        a = CGPointAdd(a, CGPointScale(va, -spoke0->start));

        b = CGPointAdd(b, CGPointScale(vb, -spoke1->start));

 

        CGPoint ab = CGPointSub(b,a);

        float se  = CGPointDot(vab, ab);

        

        float t = - CGPointDot(ab,ab)/se;

 

        if (t > now)

                front->willCollapse = t;

        else

                front->willCollapse = INFINITY;

 

}

 

static void _assertFrontIntegrity(Front* front)

{

        assert(front->leftSpoke != front->rightSpoke);

        assert(front->leftSpoke->rightFront == front);

        assert(front->rightSpoke->leftFront == front);

 

        assert(!CGPointEqualToPoint(CGPointZero, front->velocity));

}

 

static void _assertSpokeIntegrity(Spoke* spoke)

{

        assert(spoke->leftFront != spoke->rightFront);

        assert(spoke->rightFront->leftSpoke == spoke);

        assert(spoke->leftFront->rightSpoke == spoke);

 

        assert(!CGPointEqualToPoint(CGPointZero, spoke->velocity));

}

 

static void _collapseEndFront(Front* front0, float time, PolygonInsetRecord* rec, FrontsAndSpokesRec* activeWalls, FrontsAndSpokesRec* inactiveWalls)

{

        NSLog(@"collapsing endcap... %f (%p)", time, front0);

        Front* front1 = front0->rightSpoke->rightFront;

        Front* front2 = front1->rightSpoke->rightFront;

        

        Spoke* spoke = front0->leftSpoke;

        CGPoint c = CGPointAdd(rec->vertices[spoke->sourceVertexIndex], CGPointScale(spoke->velocity, time - spoke->start));

        uint16_t mvi = _addVertex(rec, c, time);

 

        _addTriangle(rec, front0->leftSpoke->sourceVertexIndex, front0->rightSpoke->sourceVertexIndex, mvi);

        _addTriangle(rec, front1->leftSpoke->sourceVertexIndex, front1->rightSpoke->sourceVertexIndex, mvi);

        _addTriangle(rec, front2->leftSpoke->sourceVertexIndex, front2->rightSpoke->sourceVertexIndex, mvi);

 

        _deactivateSpoke(front0->rightSpoke, activeWalls, inactiveWalls);

        _deactivateSpoke(front1->rightSpoke, activeWalls, inactiveWalls);

        _deactivateSpoke(front2->rightSpoke, activeWalls, inactiveWalls);

        _deactivateFront(front0, activeWalls, inactiveWalls);

        _deactivateFront(front1, activeWalls, inactiveWalls);

        _deactivateFront(front2, activeWalls, inactiveWalls);

 

}

 

static void _collapseFront(Front* front, float time, PolygonInsetRecord* rec, FrontsAndSpokesRec* activeWalls, FrontsAndSpokesRec* inactiveWalls, size_t maxEstimates, float maxTime)

{

//      NSLog(@"collapsing front... %f (%p,%f)", time, front, front->willCollapse);

 

        Spoke* leftSpoke = front->leftSpoke;

        Spoke* rightSpoke = front->rightSpoke;

        Front* leftFront = leftSpoke->leftFront;

        Front* rightFront = rightSpoke->rightFront;

 

        if (front->leftSpoke->leftFront->leftSpoke->leftFront->leftSpoke->leftFront == front)

        {