Jump to content

  • Log In with Google      Sign In   
  • Create Account


Get a point along a bezier based on distance


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 Headkaze   Members   -  Reputation: 583

Like
0Likes
Like

Posted 24 March 2012 - 04:34 AM

I have the following function for drawing a bezier curve.

static inline Vector3D linearBezierCurve(const Vector3D& pos1, const Vector3D& pos2, float t)
{
	return pos1 + (pos2 - pos1) * t;
}

static inline Vector3D quadraticBezierCurve(const Vector3D& start, const Vector3D& curve, const Vector3D& end, float t, float *radians)
{
	Vector3D startCurve = linearBezierCurve(start, curve, t);
	Vector3D curveEnd = linearBezierCurve(curve, end, t);
	*radians = vectorToRadians(curveEnd - startCurve);
	return linearBezierCurve(startCurve, curveEnd, t);
}

What I need is a way to get a point along the curve based on a distance.

I've tried using Dave Eberly's function for getting the length of the bezier curve and then taking the distance and dividing it by that. Unfortunately this is only accurate for a straight line.

Sponsor:

#2 Funkyjive   Members   -  Reputation: 125

Like
0Likes
Like

Posted 24 March 2012 - 01:30 PM

I had to do something somilar for a roller coaster game I was creating. The hardest task was to place track ties evenly spaced along a bezir curve, and on top of that get their rotation in 3d space correct. Reading your question in sounds like all you need is the total approximation of the curve. I would suggest slowly step along your path adding the total distance traveled from the last step. Once you reach your goal you have your length.

Attached is the piece of source code from the project i mentioned above. The functions of interest to you are...

be_Vector Track_Bezier_Path::Get_Path_Position(float u) Returns the position in 3d space of a bezier curve at position u where u goes from 0 to 1. Note: the distance from Get_Path_Position(.1) to Get_Path_Position(.2) is not the same as from Get_Path_Position(.4) to Get_Path_Position(.5). In other words, positions are not linear spaced based given a linear u. In the function a is the ending point of the bezier curve, b is the first control point for the curve, c is the other control point for the curve, and d is the start position of the curve.

float Track_Bezier_Path::Get_Path_Length(float end_u) Returns an approximation of the length of the bezier curve from the start point up to u where u goes from 0 to 1. A u value of 1 gives an approximation of the entire length of the curve.

#include "track_bezier_path.h"
#include <SDL/SDL_opengl.h>
#include <math.h>
#include <stdio.h>
Track_Bezier_Path::Track_Bezier_Path() : start(NULL), end(NULL)
{
}
bool Track_Bezier_Path::Validate() const
{
	if(start != NULL && end != NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void Track_Bezier_Path::Set_Start_Node(Track_Node * start)
{
	this->start = start;
}
void Track_Bezier_Path::Set_End_Node(Track_Node * end)
{
	this->end = end;
}
Track_Node * Track_Bezier_Path::Get_Start_Node()
{
	return start;
}
Track_Node * Track_Bezier_Path::Get_End_Node()
{
	return end;
}
/*This is the core algo for calculating a position on a cubic curve. Algo
from nehe.gamedev.net*/
be_Vector Track_Bezier_Path::Get_Path_Position(float u) const
{
	if(Validate())
	{
		be_Vector a = end->Get_Orientation().Get_Position() * pow(u, 3);
		be_Vector b = end->Get_Control_Point_In() * 3 * pow(u, 2) * (1 - u);
		be_Vector c = start->Get_Control_Point_Out() * 3 * u * pow((1 - u), 2);
		be_Vector d = start->Get_Orientation().Get_Position() * pow((1 - u), 3);
		return (a + b + c + d);
	}
	else
	{
		return be_Vector(0.0, 0.0, 0.0);
	}
}
float Track_Bezier_Path::Get_Path_Length(float end_u) const
{
	float length_sum = 0.0;
	if(Validate())
	{
		be_Vector last_point = start->Get_Orientation().Get_Position();
		be_Vector this_point;
		be_Vector change;
		for(unsigned int i = 1; i <= LENGTH_DIVISIONS; i++)
		{
			float u = ((float)i / LENGTH_DIVISIONS) * end_u;
			this_point = Get_Path_Position(u);
			change = this_point - last_point;
			length_sum += change.Magnitude();
			last_point = this_point;
		}
	}
	return length_sum;
}
void Track_Bezier_Path::Recalculate()
{
	cross_sections.clear();
	if(Validate())
	{
		float length = Get_Path_Length(1.0);
		/*Add half the ideal distance to the length to "round" when truncated. Divide by the ideal distance to get
		the final number of cross sections. Add 1 to account for the final cross section.*/
		int num_cross_sections = ((length + (IDEAL_CROSS_SECTION_DISTANCE / 2)) / IDEAL_CROSS_SECTION_DISTANCE) + 1;
		//Calculate the actual distance between the cross sections.
		float distance_between_sections = length / (num_cross_sections - 1);
		//Generate the positions of the cross sections and add them to the vector.
		Recursive_Cross_Section_Decent(num_cross_sections, distance_between_sections);
		//Apply the roll to the cross sections.
		Apply_Roll();
	}
}
const std::vector<be_Matrix> & Track_Bezier_Path::Get_Cross_Sections() const
{
	return cross_sections;
}
void Track_Bezier_Path::Debug_Render()
{
	glDisable(GL_TEXTURE_2D);
	glBegin(GL_POINTS);
	glColor3f(1.0, 0.0, 0.0);
	for(unsigned int i = 0; i < cross_sections.size(); i++)
	{
		be_Vector pos = cross_sections[i].Get_Position();
		glVertex3f(pos.Get_X(), pos.Get_Y(), pos.Get_Z());
	}
	glEnd();
}
float Track_Bezier_Path::Recursive_Cross_Section_Decent(int level, float distance_between_sections)
{
	be_Matrix cross_section;
	if(level == 1)
	{
		//We are at the start node so simply add it to the vector
		cross_section.Set_Rotation(start->Get_Orientation().Get_X(), start->Get_Orientation().Get_Y(), start->Get_Orientation().Get_Z());
		cross_section.Set_Position(start->Get_Orientation().Get_Position());
		cross_sections.push_back(cross_section);
		return 0.0;
	}
	else
	{
		//We are not at the start yet so find the cross section before.
		float prev_u = Recursive_Cross_Section_Decent(level - 1, distance_between_sections);
		be_Matrix prev_node = cross_sections.back();
		//Find the u value of the current node.
		float distance_past_prev = 0.0;
		float current_u = prev_u;
		be_Vector prev_point = prev_node.Get_Position();
		while(distance_past_prev < distance_between_sections)
		{
			current_u += U_INCREMENT;
			be_Vector current_point = Get_Path_Position(current_u);
			be_Vector difference = current_point - prev_point;
			distance_past_prev += difference.Magnitude();
			prev_u = current_u;
			prev_point = current_point;
		}
		float length_to_current_u = Get_Path_Length(current_u);
		float length_to_prev_u = Get_Path_Length(current_u - U_INCREMENT);
		float overshot = distance_past_prev - distance_between_sections;
		float distance_between_u = length_to_current_u - length_to_prev_u;
		float percent_overshot = overshot / distance_between_u;
		float final_u = (percent_overshot * U_INCREMENT) + (current_u - U_INCREMENT);
		/*Now that the u value of the current cross section is know calculate the
		position and roation of the cross section.*/
		//Find an axis to transform the previous matrix to the current.
		be_Vector tangent = Get_Path_Tangent(final_u);
		float rot_angle = prev_node.Get_Z().Dot(tangent);
		be_Vector rot_axis = tangent.Cross(prev_node.Get_Z());
		be_Matrix transformation;
		transformation.Set_Rotation(rot_angle, rot_axis);
		//Apply that transformation to get current orientation.
		cross_section = prev_node * transformation;
		cross_section.Set_Position(Get_Path_Position(final_u));
		//Add the cross section to the collection.
		cross_sections.push_back(cross_section);
		return final_u;
	}
}
void Track_Bezier_Path::Apply_Roll()
{
	if(Validate())
	{
		//Find how much to correct.
		be_Vector end_perpendicular = end->Get_Orientation().Get_Y();
		float delta_roll = cross_sections.back().Get_Y().Dot(end_perpendicular);
		//If there is no roll just end and save computing time.
		if(delta_roll > .0001 && delta_roll < .0001)
		{
			return;
		}
		//Determine if the roll should be positive or negative.
		be_Matrix positive_roll;
		be_Matrix negative_roll;
		positive_roll.Set_Rotation(delta_roll / 2, be_Vector(0.0, 0.0, 1.0));
		negative_roll.Set_Rotation(-delta_roll / 2, be_Vector(0.0, 0.0, 1.0));
		be_Matrix test_roll_pos = positive_roll * cross_sections.back();
		be_Matrix test_roll_neg = negative_roll * cross_sections.back();
		if(test_roll_neg.Get_Y().Dot(end_perpendicular) < test_roll_pos.Get_Y().Dot(end_perpendicular))
		{
			delta_roll *= -1;
		}
		for(unsigned int i = 1; i < cross_sections.size(); i++)
		{
			//The interpolation method is currently linear, this could be a log function.
			float roll = delta_roll * (i / (float)(cross_sections.size() - 1));
			be_Matrix relative_roll;
			relative_roll.Set_Rotation(roll, be_Vector(0.0, 0.0, 1.0));
			cross_sections[i] = relative_roll * cross_sections[i];
		}
	}
}
be_Vector Track_Bezier_Path::Get_Path_Tangent(float u)
{
	be_Vector previous_point = Get_Path_Position(u - TANGENT_OFFSET_DISTANCE);
	be_Vector next_point = Get_Path_Position(u + TANGENT_OFFSET_DISTANCE);
	be_Vector direction = next_point - previous_point;
	direction.Normalize();
	return direction;
}

"I would rather be in the boat with a drink on the rocks, than in the drink with a boat on the rocks" -Unknown

#3 Headkaze   Members   -  Reputation: 583

Like
0Likes
Like

Posted 24 March 2012 - 04:23 PM

Thanks Funkyjive although I'm really hoping to find an algorithm rather than looping through the bezier and measuring divisions.

#4 JTippetts   Moderators   -  Reputation: 8408

Like
1Likes
Like

Posted 24 March 2012 - 04:43 PM

Solving this problem analytically is hard. It requires integrating the curve, and in many cases the integral can not be computed analytically, so a numeric approximation might be your only solution.

An optimization that you can make involves constructing a look-up table that maps t to s, t being the parameter and s being the arc-length, and another table that is the inverse, mapping arc-length s to the parameter t. This way, if you need a particular arc-length point, rather than iterating the curve you can just dereference s in the s->t table, and solve for the t value the table stores.

#5 Gorbstein   Members   -  Reputation: 120

Like
0Likes
Like

Posted 26 March 2012 - 02:49 PM

I came across this problem once when designing a railway system. After all, often you want to be able to move something along a curve at a defined speed, right?

At first I was using Bezier curves, and the best solution I came up with personally was to pre-evaluate the curve at the point of creating it, stepping over the curve and building a lookup table as JTippets suggests. The only remaining issue is one of accuracy, as you will a finite number of entries in the lookup. If the point you want lies between two lookup entries, then you'll need to linearly interpolate between them. Not a big deal, but if your curve is very long and the number of lookup entries small, then the amount of deviation will be enough to notice stepping as something moves along it.

However, the very best solution I found was to scrap beziers entirely and move to catmull-rom splines, evaluating with the newton-raphson method. (Google catmull rom newton raphson and you'll no doubt find it). This gives a accurate and reliable method of evaulating the spline by arc-length without any lookups.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS