Archived

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

NeXius

Maximum Point on a Bezier/B-Spline Curve

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
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
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
I noticed that is a Catmull-rom spline. Are you the one I told that you couldn't convert between catmull-rom and beziers. If so I was wrong. Here is a link showing how to do so.

I don't see any reason for a numeric method here. Numeric methods have their place, but this doesn't seem to be one of them. I don't think it will be quite as simple as you are thinking and I suspect it will be more computationally expensive than just using the derived formula. You can simplify deriving the formula by using a substitution so that you have the equation a*t^3+b*t^2+c*t+d. The derivative is the same whether a, b, c and d are scalars or vectors of constants since they are just coefficents. The advantage of using vectors and the dot product is that it isn't limited to just the y direction but rather can be any direction you please.

It occured to me that it might worth mentioning that since the dot product is distributive (a*t^2 + b*t + c).n = (a.n)*t^2 + (b.n)*t + (c.n) so you can apply the quadradic formula without expanding it out. Also you are finding the max/min with respect to a plane and the direction is simply the normal for that plane. The quadradic equals zero is a plane passing through the origin. That may be useful if you want to find if the curve crosses a plane (max one side, min the other) that does not pass through the origin.

[edited by - LilBudyWizer on January 20, 2003 12:44:27 AM]

Share this post


Link to post
Share on other sites
Hi again

I''ve been away for the past week, so I''ve begun working on again on this problem

And using your simplified derivation (substitution somehow did not occur to me...) I got it working perfectly

First time I''ve used calculus out of the classroom =)

Nice to know all those hours spent studying didn''t go to waste!

Share this post


Link to post
Share on other sites