• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
K_J_M

Line To Catmull Rom Intersection

12 posts in this topic

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.
0

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
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.

[url="http://en.wikipedia.org/wiki/Newton%27s_method"]http://en.wikipedia.org/wiki/Newton%27s_method[/url]
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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?
1

Share this post


Link to post
Share on other sites
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 ?
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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#
0

Share this post


Link to post
Share on other sites
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.

[url="http://www.trinosis.com/files/line_to_catmul_rom_spline_intersection_demo.zip"]http://www.trinosis.com/files/line_to_catmul_rom_spline_intersection_demo.zip[/url]
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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. :)
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0