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

#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);

 

}

 

        

                //innerNormals[i1] = hn;

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

                

 

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