Archived

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

Succinct

Forcing a general cubic curve though 2 points

Recommended Posts

Succinct    169
Is it possible to solve a cubic equation in the form: Q(u) = Au^3 + Bu^2 + Cu + D to go though 2 points in space, such as (0,0,0) and (x,y,z). I''ve been jotting down pages and pages of tries, but I can''t see how to figure it out. Is it even possible? It''s fairly easy with a quadratic equation, Simpson''s Rule in calculus is based on this, but cubic curves? Thank you for your bandwidth, -- Succinct

Share this post


Link to post
Share on other sites
Succinct    169
If you choose a single one of the (x,y,z), such as x = 1, and solve the u for the x portion of the curve, you can use that u value to find where the curve would normally go at the other y and z.

That will give you a (x1,y1,z1) value. Now, you find the difference in the points, such as E = (x - x1,y - y1,z - z1), and as u sweeps from 0 to 1, add the difference, weighted by D:

Q(u) = Au^3 + Bu^2 + (C + E)u + D

Share this post


Link to post
Share on other sites
LilBudyWizer    491
Certainly, just use a cubic bezier curve. There are an infinite number of curves and you don't specify anything that makes one more correct than another. Two points define a line, three a quadradic and four a cubic. Now if you want a cubic passing through four points or even three then that is a bit more difficult.

One other point. You seem to imply that A, B, C and D are scalars. If they are then it is just a straight line, i.e. x=y=z. You have three cubic equations with independant coefficents. If the coefficents are the same then it is just a straight line, i.e. x=y=z. Only by using differant parameterizations would you be able to get it to pass through both points, i.e. ux(t), uy(t) and uz(t). You could substitude those for u in the equations and get them all parameterized the same, but then they have differant coefficents

Edited by - LilBudyWizer on January 3, 2002 7:35:41 PM

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
You can fit a higher-order (more than linear/1st order) through just two points. You simply need to specify additional information at those two points other than their positions. The additional information could be slope and acceleration information. That is, in addition to (x,y), you can specify dx/dy an d2x/dy2 at the points. For example, if you have two points and specify those two additional values at the two points, you can fit a 3rd order Bezier curve. The additional information is equivalent to specifying two additional points for defining the curve.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
LilBudyWizer    491
Argh, you got me stuck thinking about this problem. One problem seems to be the parameterization. If you simply had y(x)=A*x^3+B*x^2+C*x+D and you wanted the values of A, B, C and D such that it would pass through four points the order of the points would be increasing x. Finding the curve in that situation would be rather trivial because if you plug in x then you have four linear equations of four variables. The problem here though is that you don''t know the value of u at each point. Presumably you want a linear parameterization. With the simple example x1=(x1,y1).(1,0), i.e. the dot product of the position vector with the x-axis. So it seems reasonable to say that there is a line through space presenting the parameterization. If you could say where on that line was u=0 then you could use the dot product to find u for each point. So if you can find that parameterization then finding the vectors A, B, C and D is trivial.

So you need an origin and direction for that line. You are free to choose the origin wherever you please so you can arbitrarily pick any point. Now if you call the parameterization direction PD it is the unknown you are searching for. You can call any other point you please u=1. So say P(0)=P1 and P(1)=P2 then (P2-p1).PD=1. Perhaps that doesn''t seem terribly useful because it defines an infinite set of directions, but they all lie in the same half plane where the normal of that plane is (P2-P1) and they are all valid. You can just pick one that makes the equation true. I could be wrong since I haven''t tested it, but now you have a parameterization and now you can find the values of u for the other two points. That reduces the problem to solving a set of linear equations and that I assume is trivial for you.

Share this post


Link to post
Share on other sites
Focus    122
Try looking it up in a maths text book. There is a general sol/n to a cubic eqaution, but I don''t know it.Try some of the more advanced degree books (mine sure don''t have it)

Share this post


Link to post
Share on other sites
Beer Hunter    712
How about this - instead of trying to get a cubic curve that travels through all the necessary points, use a separate curve to connect each pair of points. It''s much easier...

Share this post


Link to post
Share on other sites
LilBudyWizer    491
I tested it and it worked. I generated random vectors A, B, C and D. That gave me a cubic equation Q(v)=A*v^3+B*v^2+C*v+D. I then started with the points P1=Q(1), P2=Q(2), P3=Q(3) and P4=Q(4). My unknown equation is P(u)=A'*u^3+B'*u^2+C'*u+D'. Just as modest insurance that the order didn't matter I used P(0)=P1 and P(1)=P3 instead of P2 for u=1. So u1=0, u3=1 and then have to calculate u2 and u4 with u2=(P2-P1).DP and u4=(P4-P1).DP. Now that gives me the following set of matrices:

    
|u1^3 u1^2 u1 1 P1|
|u2^3 u2^2 u2 1 P2|
|u3^3 u3^2 u3 1 P3|
|u4^3 u4^2 u4 1 P4|


It is a set of three matrices because P1, P2, P3 and P4 are vectors not scalars. If you solve that system of equation, i.e. put it in reduced row echelon form, you get the x, y and z components of A', B', C' and D'. Now to check that it was actually correct I checked that Q(1)-P(u1)=(0,0,0) and so on for all four points. They all came out within 1*10^-13 of (0,0,0).

The only problem is that it was not a linear change in parameterization. I'm a little baffled as to how that can be. Apparently u(v) is not a polynomial. My best guess would be that it uses sine and cosine such that P(u(v))=Q(v) with the sine and cosines dropping out. I suspect that if you used the relevant axis as the direction instead of of a vector from one point to another you would get a linear mapping from one parameterization to another. I don't particularly feel like going back and doing that though because it would take three parameterizations, i.e. ux(v), uy(v) and uz(v). So I'm just guessing that once you reparameterized it in v that you would have the same equations. Without doing that I don't know how to prove it is exactly the same curve other than that four points uniquely defines a cubic.

Hum, rambling a bit there. I found one condition that creates a problem. All directions meeting the condition (P2-P1).DP=1 are not equally valid. Some directions can cause two or three points to have the same parameter value. I can see how you would check whether a direction is valid, but I can't figure out how you would choose a direction so that it will never cause two points to have the same parameter value.

Edited by - LilBudyWizer on January 6, 2002 1:55:09 AM

Share this post


Link to post
Share on other sites
LilBudyWizer    491
Hehe, nevermind. Four points do not uniquely define a cubic space curve. If you setup two 2D cubic bezier curves such that they have loops and the loops cross you can easily get the two curves to intersect six times. If four points uniquely defined a cubic curve then the most they could ever intersect is three times since a fourth point would make them the same line. Obviously that isn''t true. The points are in differant orders so perhaps given the order there is a unique cubic, but I have no idea how you would find appropriate parameter values.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
A 3rd degree polynomial is uniquely defined by 4 points GIVEN 4 parameters, 1 for each point !!!!!!

Like this :

If P(t1)=P1, P(t2)=P2, P(t3)=P3, P(t4)=P4

then
(1) P(t) = P1*[(t-t2)*(t-t3)*(t-t4)]/[(t1-t2)*(t1-t3)*(t1-t4)] + P2*... rotate the variables ... + P3*... + P4*...

This shows that you need 16 reals to define a unique Cubic ! A cubic defined as a polynomial and not a shape !

Now what happens if you dont specify t1, ... t4 and add 2 more unknowns t5, t6 and 2*3=6 constraints P(t5)=P5 and P(t6)=P6

Then I have 18 unknowns( t1,..,t6 and 3*4=12 polynomial coeffs ) and 6*3=18 equations ! That should be all right !

Currently I dont know if there is a solution but if there is one, there is only one !

I have to solve that 18*18 non linear shit ! LOL
In fact I use (1) thus I eliminate all the 12 coeffs and 12 equations !!! I only have 6 equations and 6 unknowns (t1,...,t6)

P(t5)=P5
P(t6)=P6

Then I let you solve :] LOL

Charles B

Share this post


Link to post
Share on other sites