Jump to content
  • Advertisement
Sign in to follow this  
jchmack

Length of a Generalized Quadratic Bezier Curve in 3d

This topic is 3148 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 have been using this function to generate points on a curve using the Bezier quadratic equation:
D3DXVECTOR3		BezierQuadratic(D3DXVECTOR3 InputA,D3DXVECTOR3 InputB,D3DXVECTOR3 InputC,float T)
{
	//Explaination:
	//http://www.gamedev.net/reference/programming/features/curvessurfaces/
	D3DXVECTOR3 Solution;
	float A = 1-T;
	float B = T;
	float A_2 = A*A;
	float AB2 = A*B*2;
	float B_2 = B*B;

	Solution.x = InputA.x*A_2 + InputB.x*AB2 + InputC.x*B_2;
	Solution.y = InputA.y*A_2 + InputB.y*AB2 + InputC.y*B_2;
	Solution.z = InputA.z*A_2 + InputB.z*AB2 + InputC.z*B_2;


	return Solution;
}









It seems to work nicely =). But now I need to find the length of this same curve:
long double LengthOfBezierQuadratic(D3DXVECTOR3 InputA,D3DXVECTOR3 InputB,D3DXVECTOR3 InputC)
{
	//http://tutorial.math.lamar.edu/Classes/CalcII/ParaArcLength.aspx
	/*
	x(T)	=(p1.x)A^2+(p2.x)2AB+(p3.x)B^2
	A=1-T
	B=T
	x(T)	=		(p1.x)(1-T)^2
				+	(p2.x)(1-T)(T)
				+	(p3.x)(T)^2

	x(T)	=		(p1.x)(1-T)*(1-T)
				+	(p2.x)(T-T^2)
				+	(p3.x)(T^2)

	x(T)	=		(p1.x)(1-2T+T^2)
				+	(p2.x)(T-T^2)
				+	(p3.x)(T^2)

	dx/dt	= -2T(p2.x)+(p2.x)+2(P1.x)(T-1)+2(p3.x)T

	Length = integrate(0,1){ sqrt(	(dx/dt)^2 +
					(dy/dt)^2 +
					(dz/dt)^2 )
	*/

}










Now the formula is starting to get a bit long: http://www.algebrahelp.com/calculators/equation/simplifying/calc.do?equation=%28-2TB%2BB%2B2A%28T-1%29%2B2CT%29%28-2TB%2BB%2B2A%28T-1%29%2B2CT%29%3DP A = p1.x; B = p2.x; C = p3.x; (dx/dt)^2= -4AB + 12ABT + -8ABTT + -8ACT + 8ACTT + 4AA + -8AAT + 4AATT + 4BCT + -8BCTT + BB + -4BBT + 4BBTT + 4CCTT ; A = p1.y; B = p2.y; C = p3.y; (dy/dt)^2= -4AB + 12ABT + -8ABTT + -8ACT + 8ACTT + 4AA + -8AAT + 4AATT + 4BCT + -8BCTT + BB + -4BBT + 4BBTT + 4CCTT ; A = p1.z; B = p2.z; C = p3.z; (dz/dt)^2= -4AB + 12ABT + -8ABTT + -8ACT + 8ACTT + 4AA + -8AAT + 4AATT + 4BCT + -8BCTT + BB + -4BBT + 4BBTT + 4CCTT ; Not to mention the integral of the square root of all this... Am i going about this wrong? Is there a simpler way to calculate the length of this curve? I will not be firing this function very much but it seems like it might start to eat up some cpu time. Thank you guys in advance :) all help is greatly appreciated. edit: im still working on it: the antiderivative of one of the (dx/dt)^2 sections is: (-2TB+B+2A(T-1)+2Cx)^3/6(A-B+C) [Edited by - jchmack on October 26, 2009 3:08:27 AM]

Share this post


Link to post
Share on other sites
Advertisement
The quadratic Bezier is (x(t),y(t)) = (1-t)^2*(x0,y0) + 2*t*(1-t)*(x1,y1) + t^2*(x2,y2). The derivative is (x'(t),y'(t)) = -2*(1-t)*(x0,y0) + (2-4*t)*(x1,y1) + 2*t*(x2,y2). The length of the curve for 0 <= t <= 1 is Integral[0,1] sqrt((x'(t))^2 + (y'(t))^2) dt. The integrand is of the form sqrt(c*t^2 + b*t + a). Look up an antiderivative in something like the CRC Handbook of Mathematics. You have three separate cases: c = 0, c > 0, or c < 0.

The case c = 0 is easy enough that I will let you derive it.

For the case c > 0, an antiderivative is (2*c*t+b)*sqrt(c*t^2+b*t+a)/(4*c) + (0.5*k)*log(2*sqrt(c*(c*t^2+b*t+a)) + 2*c*t + b)/sqrt(c), where k = 4*c/q with q = 4*a*c - b*b.

For the case c < 0, an antiderivative is (2*c*t+b)*sqrt(c*t^2+b*t+a)/(4*c) - (0.5*k)*arcsin((2*c*t+b)/sqrt(-q))/sqrt(-c).

Share this post


Link to post
Share on other sites
Thank you for the replies guys :)

I believe that the suggestions that both of you have presented are for the parameterized form in 2d:

Length = integrate(0,1){ sqrt( (dx/dt)^2 + (dy/dt)^2 );

Which is where I got the foundation to do the one I have in 3d:

Length = integrate(0,1){ sqrt( (dx/dt)^2 + (dy/dt)^2 + (dz/dt)^2 );

But it is turning out to be very complicated because this doesn't integrate.

and I am looking to see if there is a simpler way ;).

edit: the reason it is so complicated is better explained here:
http://www.gamedev.net/community/forums/topic.asp?topic_id=313018&forum_id=20&gforum_id=0

I don't really understand how to implement the solution he suggests

Share this post


Link to post
Share on other sites
I illustrated mine in 2D, but the same idea works in 3D. Integrate the length of (x'(t),y'(t),z'(t)). The integrand is still of the form sqrt(c*t^2+b*t+a) and an antiderivative exists in closed form (which is what I posted).

If you do not want to use the antiderivative, you can use a numerical integration algorithm.

Share this post


Link to post
Share on other sites
An implementation for 3D curves:

float LengthQuadraticBezier (Vector3f C[3])
{
// ASSERT: C[0], C[1], and C[2] are distinct points.

// The position is the following vector-valued function for 0 <= t <= 1.
// P(t) = (1-t)^2*C[0] + 2*(1-t)*t*C[1] + t^2*C[2].
// The derivative is
// P'(t) = -2*(1-t)*C[0] + 2*(1-2*t)*C[1] + 2*t*C[2]
// = 2*(C[0] - 2*C[1] + C[2])*t + 2*(C[1] - C[0])
// = 2*A[1]*t + 2*A[0]
// The squared length of the derivative is
// f(t) = 4*Dot(A[1],A[1])*t^2 + 8*Dot(A[0],A[1])*t + 4*Dot(A[0],A[0])
// The length of the curve is
// integral[0,1] sqrt(f(t)) dt

Vector3f A[2] =
{
C[1] - C[0], // A[0] not zero by assumption
C[0] - 2.0f*C[1] + C[2]
};

float length;

if (A[1] != Vector3f::ZERO)
{
// Coefficients of f(t) = c*t^2 + b*t + a.
float c = 4.0f*A[1].Dot(A[1]); // c > 0 to be in this block of code
float b = 8.0f*A[0].Dot(A[1]);
float a = 4.0f*A[0].Dot(A[0]); // a > 0 by assumption
float q = 4.0f*a*c - b*b; // = 16*|Cross(A0,A1)| >= 0

// Antiderivative of sqrt(c*t^2 + b*t + a) is
// F(t) = (2*c*t + b)*sqrt(c*t^2 + b*t + a)/(4*c)
// + (q/(8*c^{3/2}))*log(2*sqrt(c*(c*t^2 + b*t + a)) + 2*c*t + b)
// Integral is F(1) - F(0).

float twoCpB = 2.0f*c + b;
float sumCBA = c + b + a;
float mult0 = 0.25f/c;
float mult1 = q/(8.0f*powf(c, 1.5f));
length =
mult0*(twoCpB*sqrtf(sumCBA)-b*sqrtf(a)) +
mult1*(logf(2.0f*sqrtf(c*sumCBA)+twoCpB)-logf(2.0f*sqrtf(c*a)+b));
}
else
{
length = 2.0f*A[0].Length();
}

return length;
}


Share this post


Link to post
Share on other sites
Thank you again Dave :)

I wish I had checked back on this post sooner. Since I only needed 3 points for my curve and you can generate a 2d plane from those 3 points. I ended up finding the 2d plane my curve exists in and then solving for the Length with the simpler 2D integral. But I implemented your method and it saves me the trouble of doing a conversion. I think its easier on the cpu as well.

I believe I will go with your method.

Ratings up (if you care for that sort of thing ;) )

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!