Skip to main content
GameDev.net gamedev.net
🔒 Locked

Length of a Generalized Quadratic Bezier Curve in 3d

Started by jchmack Oct 25, 2009 at 7:29 PM 5 replies 6.6k views
Original Post
jchmack
jchmack
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]
Semei
Semei
http://segfaultlabs.com/graphics/qbezierlen/?
Dave Eberly
Dave Eberly
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).
jchmack
jchmack
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
Dave Eberly
Dave Eberly
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.
Dave Eberly
Dave Eberly
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;}

jchmack
jchmack
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 ;) )

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.