Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

NeXius

Maximum Point on a Bezier/B-Spline Curve

This topic is 5799 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

Hi. In trying to find the maximum and minimum points on a b-spline curve, I took the formula I''m using for it, derived it with respect to ''t'', and set that equal to zero So, you would get a root for x, y, and z. The root for x should represent the point at which the vector tangent to the curve has an x-component of 0. And actually there are two roots for each dimension (since it''s a quadratic, and it ends up as +/-) This doesn''t work... I don''t know why... Any other suggestions or maybe someone knows why this doesn''t work??? THANKS
"If you gaze long into an abyss, the abyss will gaze back into you." - Friedrich Nietzsche (1844-1900) (my site)

Share this post


Link to post
Share on other sites
Advertisement
Hi,

Try this:
x(t), y(t), z(t) => {insert} => f(x,y,z)
Now calc grad f and see where it''s zero.

"It is an illusion that something is known when we possess a mathematical formula for an event: it is only designated, described; nothing more"
- Friedrich Nietzsche (1885-1886)



/Mankind gave birth to God.

Share this post


Link to post
Share on other sites
f(x(t),y(t),z(t)). Seperately I would think you want the max/min with respect to some direction. So perhaps the dot product of the tangent vector and some direction vector is zero.

Share this post


Link to post
Share on other sites
Thanks for your replies.

But I''m still not sure how to do this.
What is f(x(t),y(t),z(t)) supposed to evaluate to?

I thought you meant a position vector along the curve, but then how would you get the gradient of a vector?

I''m confused...

Share this post


Link to post
Share on other sites
Sorry, I didn't really pay attention to what f(x,y,z) was. I'm not sure what a gradiant of a space curve is.

Just to give an example of what I was talking about say you had the curve r(t)=(1,t,t^2). The tangent vector is given by (0,1,2t). If you wanted to find the max/min x value then you would solve (0,1,2t).(1,0,0)=0*1+1*0+2t*0=0 which is true for every value of t. This makes sense since it is a parabola in the plane x=1. The critical points for the y direction is (0,1,2t).(0,1,0)=0*0+1*1+2t*0=1=0 which is not true for any value of t. This makes sense since within the plane x=1 the parabola is z=y^2 where the domain is (-inf,+inf). The critical points for z direction is (0,1,2t).(0,0,1)=0*0+1*0+2t*1=2t=0 which is true when t=0.

[edited by - LilBudyWizer on January 20, 2003 1:41:21 AM]

Share this post


Link to post
Share on other sites
OK

So basically take the equation I have for say, x, derive it, set it equal to zero, and solve, right?

That's what I've been trying... It's still not working...

This is my equation for x: (the same for y and z)

point_x = 0.5f * ((-p1.x + 3.0f * p2.x - 3.0f * p3.x + p4.x) * t * t * t + (2.0f * p1.x - 5.0f * p2.x + 4.0f * p3.x - p4.x) * t * t + (-p1.x + p3.x) * t + 2.0f * p2.x);


When I derive that, I get this:


tangent_x = (3.0f/2.0f) * (-p1.x + 3 * p2.x - 3 * p3.x + p4.x) * t * t + (2 * p1.x - 5 * p2.x + 4 * p3.x - p4.x) * t + (-p1.x + p3.x)/2;


Which is right I think, since I've tested the tangent...
When I solve this for zero (using the quadratic formula), I get this:



CVector3 getMaxPointOn(CVector3 p1, CVector3 p2, CVector3 p3, CVector3 p4)
{
float root;
float a;
float b_neg;
float b_squared;
float c;

a = (3.0f/2.0f) * (-p1.x + 3.0f * p2.x - 3.0f * p3.x + p4.x);
b_neg = -2 * p1.x + 5 * p2.x - 4 * p3.x + p4.x;
b_squared = 4 * p1.x * p1.x + 25.0f * p2.x * p2.x + 16.0f * p3.x * p3.x - 20.0f * p1.x * p2.x + 16.0f * p1.x * p3.x - 4.0f * p1.x * p4.x - 40.0f * p2.x * p3.x + 10.0f * p2.x * p4.x - 8.0f * p3.x * p4.x;
c = 0.5f * (-p1.x + p3.x);
root = (b_neg + sqrt(b_squared - 4.0f * a * c)) / (2.0f * a);

return PointOnCurve(p1, p2, p3, p4, root);
}


Which doesn't work at all...

[edited by - nexius on January 20, 2003 5:28:46 AM]

Share this post


Link to post
Share on other sites
hmmmm...
I hope I didn''t scare you away with all that code

OK now it''s semi-working, after checking my solution over and changing the x-values to y (dumb mistake)

However, there are still a few occasions when for some reason or other I can''t find the maximum

I made a test project that you can find here

You can move the fourth control point around to change the curve using the arrow keys

The two yellow spheres represent the calculated max and min points, which work most of the time.

Can you guess why it wouldn''t work for certain positions of the last control point? For example, if you press down enough, it will fly off the curve...

thx for the help so far




"If you gaze long into an abyss, the abyss will gaze back into you."
- Friedrich Nietzsche (1844-1900)

(my site)

Share this post


Link to post
Share on other sites
Nope, just busy, I''ll have more time later. One thing is that if r(t)=(x(t),y(t),z(t)) then r''(t)=(x''(t),y''(t),z''(t)) is a vector tangent to the curve at r(t) and points in the direction of increasing t. If t was time then r''(t) would be your velocity vector. Another is that your max/min may not be between 0 and 1 so that may be the "flying off the curve" you mention. Another is that a critical point may be a max, min or inflection point. So you need to check the second derivative. Similar to r''(t), r''''(t) would be your acceleration vector. It is just like the second derivative test for a normal function in 2D except it is the dot product of the acceleration vector with some direction.

Share this post


Link to post
Share on other sites

"Another is that your max/min may not be between 0 and 1 so that may be the 'flying off the curve' you mention"


Ya, that must be it. I just thought of another method of finding it while reading your post:

Check the tangent at value 0.5. If it is increasing, go right 0.25 units. If not, go left 0.25 units. If the value there is increasing, go right again 0.125 units, otherwise go left 0.125 units, see what I'm getting at?

I haven't implemented this yet, but I'm pretty confident it will work.

Thanks again =)

[edited by - nexius on January 20, 2003 10:16:07 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!