//
//  Subdivider.m
//  B-spline
//
//  Created by Alexander Powell on Mon Aug 26 2002.
//  Copyright (c) 2002 __MyCompanyName__. All rights reserved.
//

#import "Subdivider.h"

NSMutableArray *splitAndTweak(NSMutableArray *p)
{
    NSMutableArray *newPoints, *midpoints, *altered;
    int oldSize, ii;
    
    newPoints = [[NSMutableArray alloc] init];
    midpoints = [[NSMutableArray alloc] init];
    altered = [[NSMutableArray alloc] init];
    
    oldSize = [p count];

    // Create new vertices at the midpoints of the current ones
    for (ii = 0; ii < oldSize; ii++)
    {
        MyPoint *pointOne, *pointTwo, *midPoint;
        
        pointOne = [p objectAtIndex: ii];
        pointTwo = [p objectAtIndex: ((ii + 1) % oldSize)]; 	// mod handles loops
        midPoint = [[MyPoint alloc] initWithX: (([pointOne x] + [pointTwo x]) / 2.0f) y: (([pointOne y] + [pointTwo y]) / 2.0f) z: (([pointOne z] + [pointTwo z]) / 2.0f)];	// generate the midpoint
        [midpoints addObject: midPoint];
        [midPoint release];	// leave it up to the array to do the final release
    }
    
    // Move the original points down by 1/2 of the way to their *new* neighbors
    for (ii = 0; ii < oldSize; ii++)
    {
        MyPoint *originalPoint, *leftNeighbor, *rightNeighbor, *alteredPoint;
        double mx, my, mz;	// midpoint of left and right
        
        originalPoint = [p objectAtIndex: ii];
        leftNeighbor = [midpoints objectAtIndex: ((ii - 1 + oldSize) % oldSize)]; // mod handles loops
        rightNeighbor = [midpoints objectAtIndex: ii];
        mx = ([leftNeighbor x] + [rightNeighbor x]) / 2.0f;
        my = ([leftNeighbor y] + [rightNeighbor y]) / 2.0f;
        mz = ([leftNeighbor z] + [rightNeighbor z]) / 2.0f;
        
        alteredPoint = [[MyPoint alloc] initWithX: ((mx + [originalPoint x]) / 2.0f) y: ((my + [originalPoint y]) / 2.0f) z: ((mz + [originalPoint z]) / 2.0f)];
        [altered addObject: alteredPoint];
        [alteredPoint release];
    }
    
    // Weave midpoint array and altered array into newPoints
    for (ii = 0; ii < oldSize; ii++)
    {
        [newPoints addObject: [altered objectAtIndex: ii]];
        [newPoints addObject: [midpoints objectAtIndex: ii]];
    }
    
    // Clean up
    [altered release];
    [midpoints release];
    
    return newPoints;
}

NSMutableArray *fourPoint(NSMutableArray *p)
{
    NSMutableArray *newPoints, *midpoints, *altered;
    int oldSize, ii;
    
    newPoints = [[NSMutableArray alloc] init];
    midpoints = [[NSMutableArray alloc] init];
    altered = [[NSMutableArray alloc] init];
    
    oldSize = [p count];

    // Create new vertices at the midpoints of the current ones
    for (ii = 0; ii < oldSize; ii++)
    {
        MyPoint *pointOne, *pointTwo, *midPoint;
        
        pointOne = [p objectAtIndex: ii];
        pointTwo = [p objectAtIndex: ((ii + 1) % oldSize)]; 	// mod handles loops
        midPoint = [[MyPoint alloc] initWithX: (([pointOne x] + [pointTwo x]) / 2.0f) y: (([pointOne y] + [pointTwo y]) / 2.0f) z: (([pointOne z] + [pointTwo z]) / 2.0f)];	// generate the midpoint
        [midpoints addObject: midPoint];
        [midPoint release];	// leave it up to the array to do the final release
    }
    
    // Move the midpoints by 1/8 away from their neighbors' neighbors
    for (ii = 0; ii < oldSize; ii++)
    {
        MyPoint *originalPoint, *leftNeighbor, *rightNeighbor, *alteredPoint;
        double mx, my, mz;	// midpoint of left and right
        double ox, oy, oz;	// original midpoint's coordinates
        
        originalPoint = [midpoints objectAtIndex: ii];
        ox = [originalPoint x];
        oy = [originalPoint y];
        oz = [originalPoint z];
        leftNeighbor = [p objectAtIndex: ((ii - 1 + oldSize) % oldSize)]; // mod handles loops
        rightNeighbor = [p objectAtIndex: ((ii + 2) % oldSize)];
        mx = ([leftNeighbor x] + [rightNeighbor x]) / 2.0f;
        my = ([leftNeighbor y] + [rightNeighbor y]) / 2.0f;
        mz = ([leftNeighbor z] + [rightNeighbor z]) / 2.0f;
        
        alteredPoint = [[MyPoint alloc] initWithX: (ox + ((ox - mx) / 8.0f)) y: (oy + ((oy - my) / 8.0f)) z: (oz + ((oz - mz) / 8.0f))];
        [altered addObject: alteredPoint];
        [alteredPoint release];
    }
    
    // Weave altered midpoint array and original array into newPoints
    for (ii = 0; ii < oldSize; ii++)
    {
        [newPoints addObject: [p objectAtIndex: ii]];
        [newPoints addObject: [altered objectAtIndex: ii]];
    }
    
    // Clean up
    [altered release];
    [midpoints release];
    
    return newPoints;
}