Sign in to follow this  

Finding Equidistant Point Along a Catmull-Rom Spline

This topic is 3835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a simple RTS type game and I have a situation where I have X number of units selected. After selecting the units I want to be able to hold the mouse down and drag out a shape and have the units align in this basic shape. Right now I am sampling points from the shape drawn out by the user and creating a bunch of Catmull-Rom splines to align the units on and it works OK. My problem is equally spacing all of the units along this shape. Right now I am taking the easy way out and figuring a total distance of the combined splines by adding up the straight line distance to all the control points. Obviously this is just an approximation but I thought it would work well enough since most of the control points are 5-10 pixels away from each other. After this distance approximation I figure out the average distance my units should be away from each other and then I place them along the splines by taking: Average distance / approximate spline length = u (will be between 0 - 1) Then placing units at that U location. This method works OK if a user makes simple shapes and drags the mouse around at a constant speed but if the user starts drawing more complex shapes and fluctuating the speed of the mouse the method breaks down. So... to my question. Is there a simple way to figure out where I should be placing these units so that they are spaced evenly apart from each other along my spline? I figure it has something to do with calculus and integration so I've popped out my old calc book but I'm hoping someone here could shed some light on the subject as well. Thanks! Heres some code: Vec3 SquadLeaderSM::CatmullRom( Vec3 p0, Vec3 p1, Vec3 p2, Vec3 p3, float u ) { float u_squared = u*u; float u_cubed = u_squared*u; Vec3 result = p0 * (-0.5f*u_cubed + u_squared - 0.5f*u) + p1 * (1.5f*u_cubed - 2.5f*u_squared + 1.0f) + p2 * (-1.5f*u_cubed + 2.0f*u_squared + 0.5f*u) + p3 * (0.5f*u_cubed - 0.5f*u_squared); return( result ); } And my gross current implementation: Vec3 p0, p1, p2, p3; unsigned j = 1; float leftoverDistance = 0.f; float totalPreviousDistance = 0.f; EntityList::iterator itr = squadMembers_.begin(); (*itr++)->Position(tabletPoints_[0]); while(itr != squadMembers_.end()) { Vec3 distance; float u = 5.f; float disLeft = averageDistanceBetweenSquadmembers; if(leftoverDistance > disLeft) // if we have enough space between our // last two points to place this point { --j; u = 1 - (leftoverDistance + disLeft) / totalPreviousDistance; disLeft -= leftoverDistance; ++j; } else // otherwise subtract the remaining distance from the // last two points from this point { disLeft -= leftoverDistance; while(disLeft > .01f && u > 1 + .01f) // until we reach a U //below 1 we haven't found our point { distance = tabletPoints_[j] - tabletPoints_[j-1]; u = disLeft / distance.Length(); disLeft -= distance.Length(); ++j; } } totalPreviousDistance = distance.Length(); leftoverDistance = -disLeft; p1 = tabletPoints_[j-2]; p2 = tabletPoints_[j-1]; if(j > 2) p0 = tabletPoints_[j-3]; else p0 = tabletPoints_[j-2]; if(j < tabletPoints_.size()) p3 = tabletPoints_[j]; else p3 = tabletPoints_[j-1]; (*itr++)->Position(CatmullRom(p0,p1,p2,p3,u)); }

Share this post


Link to post
Share on other sites
OK. So I found the good ol' Arc Length formula. That is:

the integral from a to b of sqrt[ 1 + ( dy/dx )^2 ] dx is the arc length from a to b of some f(x).

For my case f(x) = a*(-(1/2)*x^3+x^2-(1/2)*x)+b*((3/2)*x^3-(5/2)*x^2+1)+c*(-(3/2)*x^3+2*x^2+(1/2)*x)+d*((1/2)*x^3-(1/2)*x^2)

where a, b, c, and d are arbitrary constants.

I believe dy/dx of f(x) = -(1/2)*(3*(a-3*b+3*c-d)*x^2) + (2*a-5*b+4*c-d)*x - (1/2)*(a-c)

which makes (dy/dx)^2 = (1/4)*(3*(a-3*b+3*c-d)*x^2-2*(2*a-5*b+4*c-d)*x+a-c)^2

So now I only need to solve the integral from 0 to 1 of sqrt[ 1 + (1/4)*(3*(a-3*b+3*c-d)*x^2-2*(2*a-5*b+4*c-d)*x+a-c)^2 ]

Unfortunately my calculus skills are a little rusty so I was wondering if anyone had any hints/tips/secrets/prayers for solving this. I already tried plugging this in to my TI-89 calculator as well as the integrator but both exploded.

I'm working through it by hand now but it's slow going.

Share this post


Link to post
Share on other sites
Sign in to follow this