Courbe Catmull-rom sans cuspides ni auto-intersections

Question

J'ai le code suivant pour calculer des points entre quatre points de contrôle pour générer une courbe catmull-rom :

 CGPoint interpolatedPosition(CGPoint p0, CGPoint p1, CGPoint p2, CGPoint p3, float t)
{
    float t3 = t * t * t;
    float t2 = t * t;

    float f1 = -0.5 * t3 + t2 - 0.5 * t;
    float f2 = 1.5 * t3 - 2.5 * t2 + 1.0;
    float f3 = -1.5 * t3 + 2.0 * t2 + 0.5 * t;
    float f4 = 0.5 * t3 - 0.5 * t2;

    float x = p0.x * f1 + p1.x * f2 + p2.x * f3 + p3.x * f4;
    float y = p0.y * f1 + p1.y * f2 + p2.y * f3 + p3.y * f4;

    return CGPointMake(x, y);
}

Cela fonctionne bien, mais je veux créer quelque chose qui, je pense, s'appelle le paramétrage centripète. Cela signifie que la courbe n'aura pas de cuspides ni d'auto-intersections. Si je déplace un point de contrôle très près d'un autre, la courbe devrait devenir "plus petite". J'ai googlé mes yeux en essayant de trouver un moyen de le faire. Quelqu'un sait-il comment faire ça?

Answer 1

Voici une version iOS du code de Ted. J'ai exclu les parties 'z'.

.h

 typedef enum {
    CatmullRomTypeUniform,
    CatmullRomTypeChordal,
    CatmullRomTypeCentripetal
} CatmullRomType ;

.m

 -(NSMutableArray *)interpolate:(NSArray *)coordinates withPointsPerSegment:(NSInteger)pointsPerSegment andType:(CatmullRomType)curveType {

    NSMutableArray *vertices = [[NSMutableArray alloc] initWithArray:coordinates copyItems:YES];

    if (pointsPerSegment < 3)
        return vertices;

    //start point
    CGPoint pt1 = [vertices[0] CGPointValue];
    CGPoint pt2 = [vertices[1] CGPointValue];

    double dx = pt2.x - pt1.x;
    double dy = pt2.y - pt1.y;

    double x1 = pt1.x - dx;
    double y1 = pt1.y - dy;

    CGPoint start = CGPointMake(x1*.5, y1);

    //end point
    pt2 = [vertices[vertices.count-1] CGPointValue];
    pt1 = [vertices[vertices.count-2] CGPointValue];

    dx = pt2.x - pt1.x;
    dy = pt2.y - pt1.y;

    x1 = pt2.x + dx;
    y1 = pt2.y + dy;

    CGPoint end = CGPointMake(x1, y1);

    [vertices insertObject:[NSValue valueWithCGPoint:start] atIndex:0];
    [vertices addObject:[NSValue valueWithCGPoint:end]];

    NSMutableArray *result = [[NSMutableArray alloc] init];

    for (int i = 0; i < vertices.count - 3; i++) {
        NSMutableArray *points = [self interpolate:vertices forIndex:i withPointsPerSegment:pointsPerSegment andType:curveType];

        if ([points count] > 0)
            [points removeObjectAtIndex:0];

        [result addObjectsFromArray:points];
    }

    return result;
}

-(double)interpolate:(double*)p  time:(double*)time t:(double) t {
    double L01 = p[0] * (time[1] - t) / (time[1] - time[0]) + p[1] * (t - time[0]) / (time[1] - time[0]);
    double L12 = p[1] * (time[2] - t) / (time[2] - time[1]) + p[2] * (t - time[1]) / (time[2] - time[1]);
    double L23 = p[2] * (time[3] - t) / (time[3] - time[2]) + p[3] * (t - time[2]) / (time[3] - time[2]);
    double L012 = L01 * (time[2] - t) / (time[2] - time[0]) + L12 * (t - time[0]) / (time[2] - time[0]);
    double L123 = L12 * (time[3] - t) / (time[3] - time[1]) + L23 * (t - time[1]) / (time[3] - time[1]);
    double C12 = L012 * (time[2] - t) / (time[2] - time[1]) + L123 * (t - time[1]) / (time[2] - time[1]);
    return C12;
    }

-(NSMutableArray*)interpolate:(NSArray *)points forIndex:(NSInteger)index withPointsPerSegment:(NSInteger)pointsPerSegment andType:(CatmullRomType)curveType {
    NSMutableArray *result = [[NSMutableArray alloc] init];

    double x[4];
    double y[4];
    double time[4];

    for (int i=0; i < 4; i++) {
        x[i] = [points[index+i] CGPointValue].x;
        y[i] = [points[index+i] CGPointValue].y;
        time[i] = i;
    }

    double tstart = 1;
    double tend = 2;

    if (curveType != CatmullRomTypeUniform) {
        double total = 0;

        for (int i=1; i < 4; i++) {
            double dx = x[i] - x[i-1];
            double dy = y[i] - y[i-1];

            if (curveType == CatmullRomTypeCentripetal) {
                total += pow(dx * dx + dy * dy, 0.25);
            }
            else {
                total += pow(dx * dx + dy * dy, 0.5); //sqrt
            }
            time[i] = total;
        }
        tstart = time[1];
        tend = time[2];
    }

    int segments = pointsPerSegment - 1;

    [result addObject:points[index+1]];

    for (int i =1; i < segments; i++) {
        double xi = [self interpolate:x time:time t:tstart + (i * (tend - tstart)) / segments];
        double yi = [self interpolate:y time:time t:tstart + (i * (tend - tstart)) / segments];
        NSLog(@"(%f,%f)",xi,yi);
        [result addObject:[NSValue valueWithCGPoint:CGPointMake(xi, yi)]];
    }
    [result addObject:points[index+2]];

    return result;
}

En outre, voici une méthode pour transformer un tableau de points en un chemin de Bézier pour le dessin, en utilisant ce qui précède

 -(UIBezierPath*)bezierPathFromPoints:(NSArray *)points withGranulaity:(NSInteger)granularity
{
    UIBezierPath __block *path = [[UIBezierPath alloc] init];

    NSMutableArray *curve = [self interpolate:points withPointsPerSegment:granularity andType:CatmullRomTypeCentripetal];

    CGPoint __block p0 = [curve[0] CGPointValue];

    [path moveToPoint:p0];

    //use this loop to draw lines between all points
    for (int idx=1; idx < [curve count]; idx+=1) {
        CGPoint c1 = [curve[idx] CGPointValue];

        [path addLineToPoint:c1];
    };

    //or use this loop to use actual control points (less smooth but probably faster)
//    for (int idx=0; idx < [curve count]-3; idx+=3) {
//        CGPoint c1 = [curve[idx+1] CGPointValue];
//        CGPoint c2 = [curve[idx+2] CGPointValue];
//        CGPoint p1 = [curve[idx+3] CGPointValue];
//
//        [path addCurveToPoint:p1 controlPoint1:c1 controlPoint2:c2];
//    };

    return path;
}