Jump to content

  • Log In with Google      Sign In   
  • Create Account


Line To Catmull Rom Intersection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 24 August 2012 - 05:27 PM

After extensive searches i havn't been able to find a solution.

Working in 2d, i want to find the intersection point of a line with a catmull rom spline curve.

At the moment, i'm dividing the curve segment into numerous straight lines and performing line to line intersection tests with each.

It works, but isn't very efficient and not very accurate, depending on how many sub divisions of the curve i use.

Does anybody know a much more efficient and accurate solution to this problem.

Any help would be much appreciated.

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12481

Like
1Likes
Like

Posted 25 August 2012 - 12:08 AM

To find the intersection between a straight line and a cubic piece of a spline, write the line as Ax+By+C=0, then substitute x and y by their values as a function of the parameter t. You should get a cubic equation on t, which you can either solve in terms of radicals (tricky) or using Newton's method (easy).

If you have trouble with that plan, explain how far you got and what part you can't get to work.

#3 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 25 August 2012 - 01:33 AM

Hello Alvaro.

Thanks for the response.

I've been able to google a lot of information i wasn't aware of before thanks to your explanation.

To clarify.

Using Newton's method to find the root of (Ax+By+C=0), where X and Y is a point on the curve segment.
Taking an initial guess for X ,Y (i presume t = 0.5)
Subsequent iterations narrow down the accuracy of the curve point X , Y until the root is found.

In code terms, a quick google search provided (Ax+By+C=0) to be

(y1 – y2)x + (x2 – x1)y + (x1y2 – x2y1) = 0

If my above assumptions are correct, all thats needed now is to write Newtons Method to find the root.

Another google search provided this wikipedia page explaining Newton's Method.

http://en.wikipedia.org/wiki/Newton%27s_method

#4 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 25 August 2012 - 05:35 AM

I've had some success after a bit of experimentation.

I initially choose a T value of 0.5 and calculate the spline X,Y position of T.

Then test for the of root of the line (Ax+By+C=0) using the spline X,Y values.

This returns either a positive or negative number of arbitry value.

Then i iterate N number of times (depending on the accuracy required ) and either add or subtract to T a value that gets halved each time depending on the Sign of the root value.

Since T initially has a value of 0.5, the next update of T is either +- 0.25 , +-0.125 , +- 0.0625 ect

Then recalculate the spline X,Y position for the new value of T which gets plugged back into the (Ax+By+C=0) equation.

Each iteration gets closer to the solution.


I don't know if this is the correct method to use, but so far it seems to work well, except for when the line is reversed.

So, I'm assuming this special case will need to be checked for first.

I also need to run further tests to see how robust this technique is.

#5 Álvaro   Crossbones+   -  Reputation: 12481

Like
1Likes
Like

Posted 25 August 2012 - 06:35 AM

I think you are not doing it the way I described, so maybe I'll describe it in more detail.


A cubic spline is piece-wise cubic, which means that it consists of several pieces of parametric curve (each for a range of values of t) that look like this:
x = a3*t^3+a2*t^2+a1*t+a0
y = b3*t^3+b2*t^2+b1*t+b0

If you now have an equation Ax+By+C=0, you can substitute the values of x and y from the parametrization above and you'll get
(A*a3+B*b3)*t^3 + (A*a2+B*b2)*t^2 + (A*a1+B*b1)*t + A*a0+B*b0 = 0

This is a cubic equation in t. Compute its coefficients:
C3 = A*a3+B*b3
C2 = A*a2+B*b2
C1 = A*a1+B*b1
C0 = A*a0+B*b0

Now the equation is C3*t^3 + C2*t^2 + C1*t + C0 = 0. Plug this into a solver that can get you all the real roots and look for roots in the range of values of t that this piece is for. The place where I was suggesting to use Newton's method was in the solver.

Is that more clear?

#6 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 25 August 2012 - 12:35 PM

Hello Alvaro.

Thanks for the more detailed explanation.

That makes a lot more sense to me.

Unfortunately, i'm running into a few problems.

I need clarification whether

x = a3*t^3+a2*t^2+a1*t+a0
y = b3*t^3+b2*t^2+b1*t+b0

returns a point on a Catmull Rom Spline.

I'm currently using the equation below to return x,y points on the Catmull Rom spline for a given T value.

x = 0.5 * ((2 * p1x) + (p2x - p0x) * t + (2 * p0x - 5 * p1x + 4 * p2x - p3x) * t * t + (3 * p1x + p3x - p0x - 3 * p2x) * t * t * t)
y = 0.5 * ((2 * p1y) + (p2y - p0y) * t + (2 * p0y - 5 * p1y + 4 * p2y - p3y) * t * t + (3 * p1y + p3y - p0y - 3 * p2y) * t * t * t)

After coding your more detailed explanation i found i was getting wild results when trying to obtain the root.

Further exploration seems to reveal different spline formula's.

To verify this, i simply replaced my above spline formula's with yours to see if the same curve was drawn.

And the results were not the same.

Although both of our spline equations require 4 control points each, my spline gets drawn from point 1 to 2 ( with no drawing between points 0 and 3), and your spline was being drawn from point 0.

Which obviously leads me to ask if we are dealing with 2 different sets of spline equations ?

#7 Álvaro   Crossbones+   -  Reputation: 12481

Like
0Likes
Like

Posted 25 August 2012 - 03:10 PM

My a0,a1,a2,a3,b0,b1,b2,b3 are simply whatever numbers you use in the spline's equations. I didn't say anything about how those numbers are derived from control points or anything of that sort.

#8 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 25 August 2012 - 03:32 PM

Ok, i just assumed they were the control points for the spline.

In that case i'm at a loss as to where to go from here.

Can you elaborate on what the a0,a1,a2,a3,b0,b1,b2,b3 terms are relating to my specific problem, as i have no idea.

Thanks in advance

#9 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 26 August 2012 - 02:47 AM

Heres what i have so far.

The code might serve to help others.

But it's not working correctly and the root returned isn't correct.

The terms a0,a1,a2,a3, b0,b1,b2,b3 are what i've found from google searches, i think they are correct for a Catmull Rom spline, but i'm not sure.

\\ Spline Control Points
\\ p0x#
\\ p0y#

\\ p1x#
\\ p1y#

\\ p2x#
\\ p2y#

\\ p3x#
\\ p3y#

t# = 0.5

spline_x_pos# = 0.5 * ((2 * p1x#) + (p2x# - p0x#) * t# + (2 * p0x# - 5 * p1x# + 4 * p2x# - p3x#) * t# * t# + (3 * p1x# + p3x# - p0x# - 3 * p2x#) * t# * t# * t#)
spline_y_pos# = 0.5 * ((2 * p1y#) + (p2y# - p0y#) * t# + (2 * p0y# - 5 * p1y# + 4 * p2y# - p3y#) * t# * t# + (3 * p1y# + p3y# - p0y# - 3 * p2y#) * t# * t# * t#)

A# = (line_point_1_y# - line_point_2_y#) * spline_x_pos#
B# = (line_point_2_x# - line_point_1_x#) * spline_y_pos#

a0# = -0.5 * p0x# + 1.5 * p1x# - 1.5 * p2x# + 0.5 * p3x#
a1# = p0x# - 2.5 * p1x# + 2 * p2x# - 0.5 * p3x#
a2# = -0.5 * p0x# + 0.5 * p2x#
a3# = p1x#

b0# = -0.5 * p0y# + 1.5 * p1y# - 1.5 * p2y# + 0.5 * p3y#
b1# = p0y# - 2.5 * p1y# + 2 * p2y# - 0.5 * p3y#
b2# = -0.5 * p0y# + 0.5 * p2y#
b3# = p1y#

c0# = (A# * a0#) + (B# * b0#)
c1# = (A# * a1#) + (B# * b1#)
c2# = (A# * a2#) + (B# * b2#)
c3# = (A# * a3#) + (B# * b3#)

root# = ((c3# * t#) ^ 3) + ((c2# * t#) ^ 2) + (c1# * t#) + c0#



And heres my previous code which does return a correct root.

t# = 0.5

spline_x_pos# = 0.5 * ((2 * p1x#) + (p2x# - p0x#) * t# + (2 * p0x# - 5 * p1x# + 4 * p2x# - p3x#) * t# * t# + (3 * p1x# + p3x# - p0x# - 3 * p2x#) * t# * t# * t#)
spline_y_pos# = 0.5 * ((2 * p1y#) + (p2y# - p0y#) * t# + (2 * p0y# - 5 * p1y# + 4 * p2y# - p3y#) * t# * t# + (3 * p1y# + p3y# - p0y# - 3 * p2y#) * t# * t# * t#)

temp_1# = (line_point_1_y# - line_point_2_y#) * spline_x_pos#

temp_2# = (line_point_2_x# - line_point_1_x#) * spline_y_pos#

temp_3# = ((line_point_1_x# * line_point_2_y#) - (line_point_2_x# * line_point_1_y#))

root# = temp_1# + temp_2# + temp_3#

#10 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 26 August 2012 - 05:34 PM

For anyone thats interested i've created a small demo with source code demonstrating the intersection method described in my third post here.

655k. Windows only.

http://www.trinosis.com/files/line_to_catmul_rom_spline_intersection_demo.zip

#11 Catmull Dog   Members   -  Reputation: 136

Like
0Likes
Like

Posted 27 August 2012 - 12:59 PM

Thanks K_J_M.

It seems to me that basic, building-block code like this should be available in a standard form we could all share.

Instead it seems we all implement the same algorithms and (never having common test data in most cases) we often don't know about the bugs we have in our version.

The alternative is to buy some API that has more than what you need.

#12 K_J_M   Members   -  Reputation: 400

Like
0Likes
Like

Posted 27 August 2012 - 05:07 PM

Hi Catmull Dog.

Yes, i totally agree with you.

Theres nothing worse than having to re invent the wheel.

I'm really suprised i havn't been able to find an already established algorithm for solving this problem.

But if i find one, i'll definately share it with the community. :)

#13 Catmull Dog   Members   -  Reputation: 136

Like
0Likes
Like

Posted 28 August 2012 - 08:22 AM

I think that everyone is so happy to get theirs working they regard it as a trade secret once it does work.

It often seems as though the very authors of the articles resent it when you get it working.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS