Sign in to follow this  

Hermite curve function [solved]

Recommended Posts

JHiemstra    122

I'm working on a game that includes a base path (vec array) that is turned into an interpolated curved path using a hermit function. I created this function based on multiple examples in different code languages than I needed. They were also for 2D paths only, and I need it for 3D. I'm using the Imgtec PVR SDK on the iPhone.

The problem is that it isn't working entirely as it should. For some reason it smooths only about half the path (and not exactly the first half of the node list but half on the X-axis I think) and makes a mess of the rest. I've spent a couple of days now trying to get this to work perfectly, checking my path, the order of the nodes in the basepath etc. My math skills are not so good, I get what the function is supposed to do, but I'm kinda lost on how to troubleshoot/fix this function.

Following is the code (posting it entirely for clarity but also because I figure it could be useful to others when it actually works):

#import "ThePath.h"

@implementation ThePath

@synthesize basePath;
@synthesize curvedPath;
@synthesize STEP, startTangent, endTangent;

- (id) init {
[super init];

basePath = [[NSMutableArray alloc] init];
return self;

- (void) setStartEndTangent {
//first two nodes
PathNode* startN0 = [self.basePath objectAtIndex:0];
PathNode* startN1 = [self.basePath objectAtIndex:1];
//last two nodes
PathNode* startN2 = [self.basePath objectAtIndex:basePath.count-1];
PathNode* startN3 = [self.basePath objectAtIndex:basePath.count-2];

PVRTVec4 startTangentTemp ((startN1.pos.x - startN0.pos.x) *2,0,0,0);
startTangent = startTangentTemp;
PVRTVec4 endTangentTemp((startN2.pos.x - startN3.pos.x)*2), 0,0,0);
endTangent = endTangentTemp;

- (int) countVerts:(int)num

int numOutVerts = 1;
for(int i=0; i < num-1; i++) {
numOutVerts += (STEP+1);
return numOutVerts;

- (void) makeCurve
int numInVerts = basePath.count;
int numOutVerts = [self countVerts:numInVerts];
//NSLog(@"numInVerts: %d numOutVerts: %d ", numInVerts, numOutVerts);

//alloc all outnodes in curvedpath
curvedPath = [[NSMutableArray alloc] init];
for (int it=0; it<numOutVerts; it++) {
PathNode* newNode = [[PathNode alloc] init];
[curvedPath addObject:newNode];

PathNode* inNode = [self.basePath objectAtIndex:0];
PathNode* outNode = [self.curvedPath objectAtIndex:0];

PVRTVec4 outPos(inNode.pos.x, inNode.pos.y, inNode.pos.z,0);
outNode.pos = outPos;
int startPosn = 1;

// tangents for the current curve segment between two points
PVRTVec4 t0(0.0f);
PVRTVec4 t1(0.0f);

for (int i=0; i < numInVerts-1; i++) {
if (i == 0) {
t0.x = startTangent.x;
t0.y = startTangent.y;
t0.z = startTangent.z;
} else { // use previous t1 tangent
t0.x = t1.x;
t0.y = t1.y;
t0.z = t1.z;

if (i == numInVerts-2) { // next point is the last one
t1.x = endTangent.x;
t1.y = endTangent.y;
t1.z = endTangent.z;
} else {

PathNode* prevNode = [basePath objectAtIndex:i-1];
PathNode* nextNode = [basePath objectAtIndex:i+1];

double xLen = nextNode.pos.x - prevNode.pos.x;
double yLen = nextNode.pos.y - prevNode.pos.y;
double zLen = nextNode.pos.z - prevNode.pos.z;

t1.x = xLen/2;
t1.y = yLen/2;
t1.z = zLen/2;

PathNode* thisInNode = [self.basePath objectAtIndex:i];
PathNode* nextInNode = [self.basePath objectAtIndex:i+1];
PathNode* thisStartPosNode = [self.curvedPath objectAtIndex:startPosn];

[self makeHermit:i :startPosn :t0 :t1];
startPosn += (STEP+1);


- (void) makeHermit:(int)i:(int)startPosn:(PVRTVec4)t0:(PVRTVec4)t1 {

double x0, y0, z0, x1, y1, z1;
PathNode* thisNode = [self.basePath objectAtIndex:i];
PathNode* nextNode = [self.basePath objectAtIndex:i+1];
x0 = thisNode.pos.x;
y0 = thisNode.pos.y;
z0 = thisNode.pos.z;
x1 = nextNode.pos.x;
y1 = nextNode.pos.y;
z1 = nextNode.pos.z;

double xCoord, yCoord, zCoord;
double tStep = 1.0/(STEP+1);
double t;

for(int i=0; i < STEP; i++) {
t = tStep * (i+1);
PathNode* thisOutNode = [self.curvedPath objectAtIndex:startPosn+i];
xCoord = ([self fh1:t] * x0) + ([self fh2:t] * x1) + ([self fh3:t] * t0.x) + ([self fh4:t] * t1.x);

yCoord = ([self fh1:t] * y0) + ([self fh2:t] * y1) + ([self fh3:t] * t0.y) + ([self fh4:t] * t1.y);

zCoord = ([self fh1:t] * z0) + ([self fh2:t] * z1) + ([self fh3:t] * t0.z) + ([self fh4:t] * t1.z);

PVRTVec4 thisOutPos(xCoord, yCoord, zCoord, 0);
thisOutNode.pos = thisOutPos;

PathNode* thislastOutNode = [self.curvedPath objectAtIndex:startPosn+STEP];
PVRTVec4 thisLastOutPos(x1, y1, z1, 0);
thislastOutNode.pos = thisLastOutPos;


- (double) fh1:(double)t { return (2.0)*pow(t,3) - (3.0*t*t) + 1; }

- (double) fh2:(double)t { return (-2.0)*pow(t,3) + (3.0*t*t); }

- (double) fh3:(double)t { return pow(t,3) - (2.0*t*t) + t; }

- (double) fh4:(double)t { return pow(t,3) - (t*t); }


// ThePath.h

#import <Foundation/Foundation.h>
#include "OGLES2Tools.h"
#import "PathNode.h"

@interface ThePath : NSObject {

NSMutableArray* basePath;
NSMutableArray* curvedPath;
NSInteger STEP;
PVRTVec4 startTangent;
PVRTVec4 endTangent;

@property(nonatomic, retain) NSMutableArray* basePath;
@property(nonatomic, retain) NSMutableArray* curvedPath;
@property(nonatomic, assign) NSInteger STEP;
@property(nonatomic, assign) PVRTVec4 startTangent;
@property(nonatomic, assign) PVRTVec4 endTangent;

- (int) countVerts:(int)num;
- (void) makeHermit:(int)i:(int)startPosn:(PVRTVec4)t0:(PVRTVec4)t1;
- (void) makeCurve;
- (double) fh1:(double)t;
- (double) fh2:(double)t;
- (double) fh3:(double)t;
- (double) fh4:(double)t;
- (void) setStartEndTangent;


STEP is set first, then setStartEndTangent is called, and then makeCurve. My basepath has 84 nodes, with STEP 30 that results in 1314 nodes in the curvedpath. It seems the curved path is about 50% correct and the rest is sorta folded onto the other half. I think I'm abs()-ing or flipping a value too much.

Any help would be appreciated. :)

[Edited by - JHiemstra on October 23, 2010 11:35:30 AM]

Share this post

Link to post
Share on other sites
JHiemstra    122
I made some progress but still not as it should be. All paths where sort of folded horizontally, at the center of the screen. I think one of my 2D examples was meant for a screen with 0,0 being at the left bottom corner instead of 0,0,0 at the center, and to avoid a portion of the path to be outside the screen it flipped the negative values to positive.

So I kinda answered it myself in the end of my post above, however, it's still not perfect. The problem is at and near the start and the end and at some corners it stutters. I changed some abs into fabs and removed some negations and it's now creating a path along the entire basepath, but it has some weird deviations so is only partly smoothed. The weird thing is that some segments are perfect and others are not. I think I can get it to work, just got yet another math book, but if you can help please let me know.

And yeah, I know it's Hermite, not hermit... let's see if I can change the thread title.

[EDIT: updated the code above, it's working now :) ]

[Edited by - JHiemstra on October 23, 2010 11:28:37 AM]

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this