Sign in to follow this  
Winegums

Physically enabled object bound to a bezier curve

Recommended Posts

Hi, I'm writing an application where an object is bound to a bezier curve but is able to move freely along this curve (perhaps the easiest thing to liken it to is a cab on a rollercoaster). getting the object to 'stick' to the curve was the easy part, now I'm trying to impliment gravity (i'm asuming the object has no forces it exerts by itself to begin with), but I'm a bit unsure as to how to do this. my issue is twofold really (though I think they're related). I'm unsure how to move the object along the curve through the application of gravity. I've attached my current working below:


		//Get point before and after where we're at (asume step of 0.05f)
		Vector3 lastPoint = PointOnCurve(this->mCurve->controlPointList, this->mProgressOnCurve - 0.05f);
		Vector3 nextPoint = PointOnCurve(this->mCurve->controlPointList, this->mProgressOnCurve + 0.05f);

		//Thus find gradient of current point
		Vector3 pointGradient = lastPoint - nextPoint;
		//Apply acceleration due to gravity
		float gravityAccel;
		gravityAccel = sin(pointGradient.y) *  GRAVITY_ACCELERATION;

		//Apply friction
		//Apply acceleration to velocity
		//Advect object

even if i decide that the object accelerates by n units along it's current orientation, how do I keep it 'snapped' to the line? the alternative idea I have is to use the gradient/velocity as in indicator of how many steps to take along the line (asuming the position of the object on the line is a float ranging from 0.0f->1.0f, a step would be a slight increase or decrease in this value). However this seems a bit inaccurate, and large steps would cause problems (unless I was to recalculate the acceleration after each step?). If anyone has done this and has a successful implimentation, or any advice for me I'd be really greatful. Thanks for your time.

Share this post


Link to post
Share on other sites
It might be that the best you can do with an arbitrary bezier curve is get a numerical approximation of the motion.

Note that the curve is not just restricting the acceleration from gravity; it is applying a constraint force that is keeping the velocity of the object tangent to the curve. As part of the update, project the velocity vector to the direction of the curve at the current point, to make the object only move in the direction of the curve. The object will still drift away from the curve, so after updating its position, find the closest point on the curve to the object (or at least a good enough approximation) and snap the object to that point. Just find this point numerically, by using gradient descent to minimize the distance between the object and the curve.

Share this post


Link to post
Share on other sites
I concur with Vorpy's solution, but I think he's sold it short in terms of realism.

Restricting the net force (including gravity) to the tangent of the curve is equivalent to treating the curve as a surface with a reactive force. In just the same way you'd keep an object planted on the ground by applying a counter force normal to the surface tangent (i.e. projecting out the orthogonal component), you track the object to the spline. Indeed, it's not ideal to resort to gradient-descent for the clamping, but programmers have made do with this technique since the dawn of physical simulation so I wouldn't worry too much.

Share this post


Link to post
Share on other sites
Quote:
Original post by Vorpy
The object will still drift away from the curve, so after updating its position, find the closest point on the curve to the object (or at least a good enough approximation) and snap the object to that point. Just find this point numerically, by using gradient descent to minimize the distance between the object and the curve.


I follow you up until this point. How do I find the closest point on the curve to the object? I don't understand how to do this at all. I googled this but every answer I find seems rather heavy (like, dissertations or white papers), and I was hoping there was a somewhat standard method of doing this.

EDIT: Also, if i use this method I would then have to find where on the curve the object is, in terms of a float between 0 and 1 (in order to ascertain the progress along the curve so the gradient of the current point can be found). Is there a way to do this through a standard equation or function?

Share this post


Link to post
Share on other sites
Quote:
Original post by Vorpy
How do I find the closest point on the curve to the object? I don't understand how to do this at all. I googled this but every answer I find seems rather heavy (like, dissertations or white papers), and I was hoping there was a somewhat standard method of doing this.

EDIT: Also, if i use this method I would then have to find where on the curve the object is, in terms of a float between 0 and 1 (in order to ascertain the progress along the curve so the gradient of the current point can be found).

Yes, you need to keep track of this value. The primitive way to proceed is as follows:

First, establish a bound on the parameter within which the closest point must lie. This will depend on the instantaneous speed of the particle, the arc-length of the spline segment and the maximum arc-velocity of the segment, but a rough approximation would do just fine.

From this maximum delta value and the previous parameter value, determine an upper- and a lower-bound (on the arc-length parameter) for the possible closest point. Now perform a binary-search on this up as far as the desired accuracy. That is, recursively or iteratively evaluate the distance between the point and the current interval's edges & midpoint; reassign the interval to the appropriate half-interval. When the interval becomes small enough (say, smaller than a pixel), you're done.

Obviously, this algorithm is fallible. It assumes uniqueness of a local minimum and won't work very well for splines with sharp curves. This is why you should aim to keep the object moving 'slowly' with respect to the frame-rate. But given these constraints, the algorithm is fast and effective.

If you need something a bit more advanced, look up gradient-descent. It's a more intelligent iterative procedure, but is a little harder to understand.

Quote:
Is there a way to do this through a standard equation or function?
Theoretically, yes (assuming your spline segments are polynomials of order five or less), but you'll run into no end of problems with regard to uniqueness and bounding. It's probably best avoided.

Share this post


Link to post
Share on other sites
Finding the point on the curve that minimizes distance using gradient descent:

Start with a guess as to what the closest point is.
Calculate the gradient of the curve at that point.
Use the gradient to decide if the closest point is forward or backward along the curve.
Take some small step in that direction (forward or backward along the curve).

There are some slight details here that allow for a few different variations, but the basic idea is the same...for example, the step size can vary based on the gradient of the function you are minimizing (the distance to the object) with respect to the parameter (the value from 0 to 1 that determines the point on the curve).

The other method is actually to use a golden section search, not a binary search. The goal is to find the point on the curve that minimizes the distance to the object's current location, and golden section search is used for finding a minimum. A golden section search is slightly more complicated than a binary search.

[Edited by - Vorpy on January 6, 2008 4:33:56 PM]

Share this post


Link to post
Share on other sites
hey guys. I've implimented something resembling this gradient descent method and it seems to work, however the objects movement is suspicious. I don't think the equations are substantially off, as energy appears to be conserved. however the object doesn't seem to really gain or lose momentum. I'm not sure if thats just a symptom of the setup i've made or if i'm dampening values too much:

 
static unsigned long lastCall = 0;
if(lastCall == 0)
{
lastCall = GetTickCount();
return;
}

unsigned long timeDelt = GetTickCount() - lastCall;
float timeDelta = (float)timeDelt / 1000; //To turn to seconds

//Get point before and after where we're at (use 0.001f as an arbitrary small value)
Vector3 lastPoint = PointOnCurve(this->mCurve->controlPointList, this->mProgressOnCurve - 0.001f);
Vector3 nextPoint = PointOnCurve(this->mCurve->controlPointList, this->mProgressOnCurve + 0.001f);

//Thus find gradient of current point
Vector3 pointGradient = nextPoint - lastPoint;

//Make into unit form
pointGradient = Normalise(pointGradient);
float accel = pointGradient.y * (float)GRAVITY_ACCELERATION; //y will be a value between -1.0f and 1.0f,
//depending on gradient,
//so accel will be between 9.8f and -9.8f

accel *= timeDelta; //To get in terms of time passed
this->mAcceleration *= timeDelta;
this->mAcceleration += accel; //Apply change in acceleration
this->mVelocity += (this->mAcceleration); //Increase velocity by change in acceleration
this->mOrientation = pointGradient;
//Advect object along current direction (tangent to point on curve)
this->mPos += pointGradient * (this->mVelocity * timeDelta);

//Find nearest point on line
float nearestPoint = this->FindClosestPointOnLine(5);
//Snap to that point
this->mPos = PointOnCurve(this->mCurve->controlPointList, nearestPoint);
this->mProgressOnCurve = nearestPoint;

//Rotate the object by finding the between where we're at and the next point
//And finding the dot product of that vector and the x/y/z axis.
Vector3 nextPos = PointOnCurve(this->mCurve->controlPointList, this->mProgressOnCurve - 0.001f);
Vector3 facingVec = this->mPos - nextPos;
facingVec = Normalise(facingVec);

float rotateX = Dot(facingVec, Vector3(1.0f,0.0f,0.0f));
float rotateY = Dot(facingVec, Vector3(0.0f,1.0f,0.0f));
float rotateZ = Dot(facingVec, Vector3(0.0f,0.0f,1.0f));
rotateX *= RADIAN_TO_DEGREE;
rotateY *= RADIAN_TO_DEGREE;
rotateZ *= RADIAN_TO_DEGREE;

this->mRot = Vector3(rotateX, rotateY, rotateZ);
lastCall = GetTickCount();

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