Jump to content
  • Advertisement
Sign in to follow this  
phestermcs

Help with efficient Two Point Boundary ODE Solver implementation

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

I'm looking for someone to assist implementing the two-point boundary ODE solver described in this article http://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?article=1002&context=pbli (also attached to this post), ideally someone who primarily understands calculus, secondarily programming. The assistance would be in the form of helping decipher the calculus in the above article and discussing its software implementation. Actual implementation would be done by myself. Note the article offers an approach that is more efficient and accurate than using 'shooting' with an RK4 based ODE solver.

This is part of implementing a tennis game, and would be used to implement aiming the tennis ball (or more specifically used in determining the initial translational and rotational velocity vectors such that the tennis ball lands where it was aimed). The ODEs to be solved are the kinematic equations modeling tennis ball trajectories that incorporate gravity, air drag, and spin effects (Magnus effect).

I envision an adequate person would be able to decipher the above article rather quickly, and estimate the time required to assist in the range of 4-12 hours. I would be willing to more than adequately financially compensate anyone that can help (assuming sufficient prior knowledge/experience).

If you believe you can assist, or know someone who may be able to, please contact me as soon as possible.

Regards,
Paul

Share this post


Link to post
Share on other sites
Advertisement
What part are you having trouble deciphering exactly? Basically I'm trying to see exactly how many orders of magnitude your time estimate is off by.

Share this post


Link to post
Share on other sites
Well, for example: I understand basically how an RK4 ODE solver works, enough to implement one given the 5 basic equations used. That took me about 30 minutes to get, and my primary resource was a couple of paragraphs and about 10 lines of sample code from the book Physics for Game Programmers.

The article I attached to my original post is dense in calculus, with no code samples. I'm having trouble deciphering all of it, and by that I mean translating into a computer algorithm. I reason someone proficient in calculus could quickly understand the underlying conceptual approach the article describes; it quite clearly articulates all of the mathematical principles and equations it uses.

By your question, I'm assuming that you understand the article, and by your statement, that you believe it would take you in particular much longer than 12 hours to convey that understanding to someone else, someone with anough rudimentary understanding of calculus to understand an implementation of the RK4 alogrithm. Is that a fair assumption? If you do understand the article, how long would it take you to implement (and here I assume you're also quite an experienced programmer)?

From over 25 years experience in software development and enterprise consulting, I do not believe my estimate is orders-of-magnitude off, but if it ultimately is, then that's just what it took. If you're offering to actually help in someway, that would be fantastic.

Regards,
Paul Edited by phestermcs

Share this post


Link to post
Share on other sites
I was under the impression that you did not know calculus, and I stand corrected.

So, let me get this straight... you want to pre-define an initial position / velocity, and see which parameters for the various effects such as gravity and drag that correspond to a pre-defined end position?

Did you see http://www.gamedev.n...g-space-travel/ ? Edited by taby

Share this post


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

I understand calculus, but I'm not fluent in it.

I need to specify the ball's initial position vector (hit point), initial translational velocity (just 'shot-power'), initial rotational velocity vector (spin direction and rpm), and final vector position (aim point), and have returned the initial translation velocity vector (both direction and velocity) of the ball. If my calculus understanding is correct, since both the initial and final positions are supplied, and we're solving for the initial translation direction, the problem is classified as a two-point boundary problem. This is different than solving the same ODE as an initial boundary problem to animate the balls flight, which I already understand how to do using a simple RK4 ODE solver. First solving the ODE as a two-point boundary problem as part if simulating aiming the tennis ball, allows supplying all the initial dependents to solve the same ODE to animate the ball, and ensure it lands where it was aimed, all while considering gravity, air drag, AND the Magnus effect (so spin curves the ball appropriately).

I reviewed the link you supplied and the Java code that was associated with it, and I don't believe it's applicable. Again, if my understanding of calculus is correct, while the java code does seem to fundamentally solve a kinematic ODE (computing thrust based on mass) using two points (initial location and velocity, and final location and velocity), the underlying ODE is fundamentally a 1st order, linear ODE, with a closed form solution, and can be solved algebraically (there actually is a way to solve that problem without iteration, see http://wiki.beyondun...ojectile_Aiming). I believe my problem is a 2nd order, non-linear ODE, with no closed form solution (thereby requiring a numerical solver) because the forces of drag (from air resistance) and lift (from spin) at any time are derivatives of translational and rotational velocity, both effected by those same changing forces (thus non-linear). The approach described in the article referenced in my original post is specifically intended to efficiently solve this class of ODE problems.

My problem is even a little more complicated, in that I need to also ensure the ball's trajectory is above a certain height at a certain time (to clear the net, or to do a lob shot), and because the player's inputs are not absolute, but rather relative values of power and spin rpm. However, those problems will most likely be solved by applying a 'shooting' algorithm over the ODE solver.

Do you understand the conceptual approach the article details? I can't tell if it's fundamentally an iterative based solver, can you? I ask because it may, in the end, be more efficient to use shooting with RK4 to simultaneously solve the two-point problem, the above-a-height problem, and determining the absolute translational and rotational velocities (power and spin) based on the player inputed relative power and spin.

How well do you understand calculus, kinematics, and implemeting them in software?

Regards,
Paul Edited by phestermcs

Share this post


Link to post
Share on other sites
My guess is that you know more about this than I do, and so I wish you luck. For what it's worth, I think you're quite right that 4-12 hours is not enough time to introduce anyone to this topic well enough so that they could implement it on their own, and that you'd be much better off not overthinking the problem.

P.S. Did you hear about this a couple of weeks ago? http://physics.stackexchange.com/questions/28931/what-are-the-precise-statements-by-shouryya-ray-of-particle-dynamics-problems-po ? Perhaps you may have better luck finding a tutor on stackexchange. Edited by taby

Share this post


Link to post
Share on other sites
Not that I expect buddy to come back, but ...

It occurred to me that one could first model the problem with just gravity (assuming constant acceleration), in order to find an initial up/down angle that gets the projectile to the target (or, alternatively, the angle that gets the projectile closest to the target, if the target is too far away for the currently selected speed to reach). Of course, there are most often two angles that can get the projectile to the target (one low and one high), so I guess you'd work on two paths/angles simultaneously. Perhaps SUVAT and all that might be useful here, keeping in mind that the height of the racket and the height of the playing field are generally not the same. Perhaps it would be good to have previously disregarded all targets that are not in bounds on the opponent's side of the court.

After one has an initial up/down angle, one could divide the spin RPM and drag coefficient into, say, 10 or 100 smaller units, and then integrate it all in using 10 or 100 steps. At each step, one would increase the spin RPM and drag coefficient by one smaller unit, and then readjust the up/down angle incrementally to nudge it to where it comes closest to the target distance (forget about aiming left and right for now). Of course, each path that one carves during all of this nudging would be created by integrating using RK4 or whatever, as normal. Perhaps a larger than normal RK4 time step size would be a good idea. Perhaps Newtonian integration would be an even better idea. The idea is that this can all be fairly rough.

After all of the 10 or 100 smaller units have been integrated in, and assuming that there is an up/down angle that can reach sufficiently close to the target distance, one could then slowly decrease the RK4/Newton time step size while slowly adjusting the up/down angle, if one wishes to get a final path with more definition.

After all this, one would simply have to rotate the direction vector along the y axis to match the target's location in terms of left and right (the target position and the path's actual end point are ideally the same distance from the starting point, so they ideally both lie along the same circle on y = 0 that has the racket's xz position at its origin). This single left and right rotation is bound to be good enough, since physics is rotationally symmetric (Noether's theorem). No incremental nudging required in this final step. Of course, this step assumes that the rotation axis involved with the Magnus effect can be oriented so as to allow for hooking/slicing, and not just lift. If the rotation axis is always perpendicular to the path and parallel to the playing field at the same time, then I guess only lift would be allowed for.

Finally, one could test to see if the path intersects with the net.

Perhaps it's best to keep in mind that some of the initial input might not be solvable. Edited by taby

Share this post


Link to post
Share on other sites
I think I am complicating this too much. The initial path could be the line spanning from the start position to the target position. The gravitational acceleration constant could be subdivided and integrated, like the spin RPM and drag coefficients already are. Acceleration is acceleration.

Share this post


Link to post
Share on other sites
Taby, thanks for your continued thinking on this. The approach you've described is somewhat similar to what I've begun attempting. If you, or anyone who has read this thread, is interested in the solution, please let me know and I will eventually post (C# code) here. If not, thanks for your time!

Share this post


Link to post
Share on other sites
I was overthinking it too much even so, I'm sure of it. There is the issue that the solution most often bifurcates into two solutions once the forces start being applied, so I decided to go the cheap and easy route of attacking the problem by matching the horizontal range to the angle using brute force and subdivision. Get the horizontal range for -90 through 90 degrees (0 through 90 in the case where the start point is at y = 0) in steps of 10 degrees or whatnot, find the two angles that give the closest to the desired horizontal range, and sample around them using smaller steps. Handle special cases where the two closest angles merge into one because the desired horizontal range is close to the maximum horizontal range or beyond it, etc, etc. Continually repeat subdivision and sampling, if desired. If there are no variable forces (like wind), then I guess some range/angle/spin/speed combinations could be precomputed and stored for later look up, to help speed up the brute force algorithm at runtime by helping give a good initial guess for the angle.

I am interested in seeing how you approached it all. I'll post the code when I finish as well.

Also, I'm calculating the "Magnus" force just using the same parameters as the drag force, which is not quite right, but good enough for what I'm doing in the end:

drag = (-velocity_vector)*(velocity_vector.length())*0.5*fluid_density*drag_coeff*ball_cross_section_area
// or... drag = - normalize(velocity_vector)*speed*speed*0.5*fluid_density*drag_coeff*ball_cross_section_area

Magnus = angular_velocity_vector.cross(velocity_vector)*0.5*fluid_density*drag_coeff*ball_cross_section_area

accel = (drag + Magnus) / ball_mass

accel.y += -9.81 // constant gravitation

I calculated the angular velocity vector length to be spin RPM / 60 * 2 * pi. I used a drag coefficient of 0.47 (spherical body), and a fluid density of 1.2 (air at 1 atm pressure, at around 20 degrees temperature), and cross-section area and mass for the average of a few different tennis balls. I am reading these tonight:
http://www.wseas.us/...2008/MGR-09.pdf
http://www.physics.u...rajectories.pdf

Setting the spin RPM to the high thousands makes for some interesting paths. Edited by taby

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!