First of all, let me say that I'm still a novice when it comes to numerical methods.

Now that that's over with, I'll present my problem. I'm working on a piece of software that needs to do collision detection between spheres which have velocity and acceleration in any direction and a series of torus segments. I am attempting to use a closed solution to this problem, described as so:


Shrink the small radius of the torus by the radius of the sphere (I'm only concerned with *inner* collisions with the torus).
The "sphere" just follows a parabolic path, then, I think. We translate the parabolic path into the torus' object space.
So, we're only concerned with where the parabolic path intersects with the smaller torus segment.


This results in an octic polynomial, of which I can easily compute the coefficients. My question is, what is the best way to calculate the roots for this polynomial?

"Best" can be described as the following:


Fast! (the method has to be able to run in "real-time", preferably for multiple objects)
I don't care about complex roots. The coefficients are not complex, either. I'd rather not deal with any complex anything. :-)
I'm really only ever concerned with the *first* real root, though I'm not sure ahead of time whether one will occur, and if so, how long it'll take to get to it.
If a root doesn't occur in a reasonable about of time for the parabolic segment, I can just exit and try again next frame.
Accuracy is not quite as important as speed. The spheres aren't moving that fast, and if the "time" variable was off by a little on my root, it wouldn't be that big of a deal. I just want to find the time of the first collision, if there is any.


I'd really appreciate some help on this matter. I tried using zroots, but I'm not sure its the best solution, and its still kinda slow for my application (though there may not be anything better).

I've done sphere-sphere collisions successfully before just using a quartic solver, but obviously there is no octic equation solver, so I figure I need to use one of the generic polynomial solvers.

It may not be possible to do what I want in real time, I know, but computers have gotten pretty darn fast lately :-)

First of all, let me say that I'm still a novice when it comes to numerical methods.

Now that that's over with, I'll present my problem. I'm working on a piece of software that needs to do collision detection between spheres which have velocity and acceleration in any direction and a series of torus segments. I am attempting to use a closed solution to this problem, described as so:


Shrink the small radius of the torus by the radius of the sphere (I'm only concerned with *inner* collisions with the torus).
The "sphere" just follows a parabolic path, then, I think. We translate the parabolic path into the torus' object space.
So, we're only concerned with where the parabolic path intersects with the smaller torus segment.


This results in an octic polynomial, of which I can easily compute the coefficients. My question is, what is the best way to calculate the roots for this polynomial?

"Best" can be described as the following:


Fast! (the method has to be able to run in "real-time", preferably for multiple objects)
I don't care about complex roots. The coefficients are not complex, either. I'd rather not deal with any complex anything. :-)
I'm really only ever concerned with the *first* real root, though I'm not sure ahead of time whether one will occur, and if so, how long it'll take to get to it.
If a root doesn't occur in a reasonable about of time for the parabolic segment, I can just exit and try again next frame.
Accuracy is not quite as important as speed. The spheres aren't moving that fast, and if the "time" variable was off by a little on my root, it wouldn't be that big of a deal. I just want to find the time of the first collision, if there is any.


I'd really appreciate some help on this matter. I tried using zroots, but I'm not sure its the best solution, and its still kinda slow for my application (though there may not be anything better).

I've done sphere-sphere collisions successfully before just using a quartic solver, but obviously there is no octic equation solver, so I figure I need to use one of the generic polynomial solvers.

It may not be possible to do what I want in real time, I know, but computers have gotten pretty darn fast lately :-)

Hello Comrade
I really do appreciate if the following codes in C++ is tried .
To start with ,attempt to find points in the parabolic path and then find the root in ur own way as this program is able to render u 30 points on the parabolic path that u 've made during the collision experiment.
I leave the root finding for ur new year session/experiment
What more ,other than bestwishes for the newyear-2009
Pl feedback on this.




#include <iostream>

using namespace std;





class point {

public:

point() { x = 0; y = 0; } //default

point(double u) { x = u; y = 0;} //double to point

point(double u, double v) { x = u; y = v; }



void print() { cout << "(" << x << "," << y << ")"; }

void init(double u, double v) { x = u; y = v; }

void plus(point c);

private:

double x, y;

};



void point::plus(point c) //definition not inline

{

//offset the existing point by point c

x += c.x;

y += c.y;

}



double parabola(double x, double p) { return(x * x) / p; }



void graph(double a, double b, double incr,

double f(double, double), double p, point gr[])

{

double x = a;

for (int i = 0; x <= b; ++i, x += incr)

gr[i].init(x, f(x, p));

}



int main()

{

point g[1000]; //uses the default constructor



graph(0, 2, 0.1, parabola, 5, g );

cout << "First 30 points:" << endl;

for (int i = 0; i < 30; ++i) {

g[i].print();

if (i % 5 == 4)

cout << endl;

else

cout << " ";

}



int look; cin >> look;

}

As
Kutta(C.R.Muthukumar)
:)

Gene, did you ever get your problem figured out?

You stated you are only concerned with the *first* real root.
What do you mean by "first"? The one that is smallest in magnitude? Or simply the first one that the algorithm is able to compute?

One of the references mentioned in "Numerical Recipes" is pretty good:

“A First Course in Numerical Analysis. Second Edition”
by Anthony Ralston and Philip Rabinowitz

I don't have this book in front of me, but I seem to recall a theorem mentioned within about being able to determine how many real roots of a polynomial exist within a particular interval before actually computing the roots. Since you are only looking for real roots, perhaps you could apply this theorem to make your own program execute faster.

Please post back and let us know how your project is progressing.

Regards.


David