• Create Account

Orbit (ellipse) collision detection between many many objects

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.

8 replies to this topic

#1Sollum  Members

1090
Like
0Likes
Like

Posted 19 July 2013 - 08:47 AM

Afternoon

Back in University, in math classes, i remember studying something about defining ellipses in expressions, but i don't remember much of that.

Recently i had an idea and would like to test out some mechanics first, if its even possible to accomplish my goals.

Tho the trick is, i need loads (5k+) of spheres moving around other spheres and i want to check collision between them. Checking collision between each sphere will be... pain for cpu. Especially on tablet devices and phones.

So i thought that splitting them into regions, and then checking collisions in one region would be enough. But one object can pass through many regions.

Then i thought that maybe it would be possible to use such thing:

a) Create object

b) Define orbit ellipse in expression

c) Traverse tree of sphere objects to find potential collision targets

d) Calculate time when both will collide

Is such thing possible, or i am looking for an easy way?

#2apatriarca  Members

2307
Like
1Likes
Like

Posted 19 July 2013 - 09:17 AM

Two spheres moving on two elliptical orbits may collide even if the two orbits do not intersect. You thus have to somewhat compute the intersection of two tori (this is how mathematicians call donuts-like surfaces). Moreover, intersection "times" will be periodical and they will depend on the parametrization of both ellipses. It looks like you will have to maintain and work with a quite complicated data structure.

I think it is better to simply compute the intersections between the spheres (maybe using some kind of spatial acceleration structure or the GPU).

#3Milcho  Members

1177
Like
1Likes
Like

Posted 19 July 2013 - 09:54 AM

As apatriarca said, two spheres may collide even if their orbits don't intersect (and in reality orbits in 3d, which are just lines, will rarely intersect, unless you impose restriction of being on the same plane).

But you can do a sort of hybrid approach with the region idea you mentioned originally. There's two ways I can think of, off the top of my head, depending on how much data overhead you can afford.

One is to separate your space into an imaginary rectangular grid, where each cell is size NxNxN. Then, at startup, traverse the orbit of each sphere using equations for an ellipse, my suggestions is using parametric form). Each little jump you make along the ellipse (make sure jumps are of size N/2 at maximum), record which cell your ellipse passes through. Then, account for the radius of the sphere travelling along the ellipse, and record the other cells which your sphere will fall into, if it were at that position on its elliptical orbit.

This way, for each cell, you'll have a list of spheres that can possibly pass through that rectangular cell, and you only have to check for collision with those, making sure you don't repeat collision checks (so if you're on sphere A, and just checked if it collides with sphere B in that cell, don't bother checking if sphere B collides with sphere A). The problem with this is that it requires a lot of overhead, especially if you make your grid too small. And if you make your grid too large, you'll start having to go through a lot more checks - so there's a sweet spot depending on your setup.

Note: I just realized that the next method assumes all your ellipses have one common (or very nearly so) orbiting point, like planets around the sun, which may not be what you meant

Alternatively,  instead of making a rectangular grid, make spherical shells, of certain thickness (again, varied depending on your setup, and again having a sweet spot of being neither too thick, nor too thin). You can easily calculate the perihelion and aphelion of each elliptical orbit (and add/subtract the sphere's radius) so you will know which of these spherical shells your sphere can pass through. Then when performing collision for a sphere check which other spheres pass through the same spherical shell in which your sphere currently is.

The upside is that you'll need a lot less data storage here, than in the cubical grid method. The downside, as I mentioned in the note, is that this will really only work well when all your elliptical orbits have a common, or nearly common, orbiting point.

#4Muzzy A  Members

737
Like
1Likes
Like

Posted 19 July 2013 - 09:48 PM

There's this thing called the KD Tree I think? It can get quite complex, but basically puts every object in to a list of AABB's and objects only check collision in the surrounding AABB's.

You can define the size of your AABB's yourself obviously. And there's no limit to how big you can make this tree, there's alot of overhead for it, but it's extremely useful when you have a large amount of objects like that.

Edited by Muzzy A, 19 July 2013 - 09:50 PM.

#5serumas  Members

787
Like
1Likes
Like

Posted 20 July 2013 - 12:50 AM

5k very small objects in limited space i think is not a problem at all.

i think much more time will took to move objects compared to collision broadphase algorithm and collision response.

#6Sollum  Members

1090
Like
0Likes
Like

Posted 20 July 2013 - 06:49 AM

5k very small objects in limited space i think is not a problem at all.

i think much more time will took to move objects compared to collision broadphase algorithm and collision response.

I had done this many months ago, checking collision between each was slow.

Thank everyone for tips! Ill try them out.

#7serumas  Members

787
Like
0Likes
Like

Posted 20 July 2013 - 09:25 AM

So you need a broadphase algorithm. For all moving objects one of the best and simple algorithm would be uniform(limited space) or hash(unlimited spaces) grid (than most of objects are small according to space).

I could give you good source code for that, its grid with sweapandprune, and it takes just ~50 lines of code .

#8h4tt3n  Members

1917
Like
0Likes
Like

Posted 20 July 2013 - 10:26 AM

I have implemented a uniform grid broad phase algorithm in a SPH fluid simulation, and it ran very smoothly with around 5-10k particles even though there were many collisions to handle all the time. I'd definitely recommend going that way, as serumas also mentions.

Just out of curiosity, I'd like to see your source too :-)

Cheers,

Mike

#9serumas  Members

787
Like
1Likes
Like

Posted 21 July 2013 - 11:23 AM

Object (mechanism) routine:

void mechanism::do_loop()
{
//move object
vec==...;

//satisfy constrains

//find AABB object bounding box
box.bbox[0]=...;//min
box.bbox[1]=...;//max

//needs update if box leevs last cells ragions  // cellw cellh - cells width and height
if(	box.bbox[0].x<fminx ||
box.bbox[0].x>fminx+cellw ||
box.bbox[0].y<fminy ||
box.bbox[0].y>fminy+cellh ||
box.bbox[1].x<fmaxx ||
box.bbox[1].x>fmaxx+cellw ||
box.bbox[1].y<fmaxy ||
box.bbox[1].y>fmaxy+cellh)
{
//appears that object must be updated in grid
upid++;       //update id
};
}


Grid routine:

void GRID::add(mechanism * m)
{
mech_data md; //object info
md.mech	=m;
md.upid	=m->upid;

//convert bounding box coords to cells indexes - float to integer
int iminx=f_to_i(m->box.bbox[0].x*inv_cellw);//inv_cellw=1/cellw;
int iminy=f_to_i(m->box.bbox[0].y*inv_cellh);
int imaxx=f_to_i(m->box.bbox[1].x*inv_cellw);
int imaxy=f_to_i(m->box.bbox[1].y*inv_cellh);

m->fminx=(float)(iminx)*cellw;//maybe fmodf
m->fminy=(float)(iminy)*cellh;
m->fmaxx=(float)(imaxx)*cellw;
m->fmaxy=(float)(imaxy)*cellh;

//insert object infos to to cells lists
for(int i=iminx;i<=imaxx;i++)
for(int k=iminy;k<=imaxy;k++)
{
md.prix=i==iminx;//these prix and oriy is needed to avoid dublication collision checks
md.priy=k==iminy;
node[i][k].mechs.push_back(md);
}
};
void GRID::collisions(int d)
{
collision_list.clear();
for(int i=0;i<width;i++)
for(int k=0;k<height;k++)
if(node[i][k].mechs.size()>0)
{
//delete old id objects and sort
_loop(its,it,ite,mech_data,node[i][k].mechs)  //  it - iterator for all node[i][k].mechs
{
if(it->mech->upid!=it->upid)
{
//old id
_erase(its,it,ite,mech_data,node[i][k].mechs,it); //safe erase
it--;
}else
{
//sort
mech_data* s2it=it-1;
if(it > its && it->mech->box.bbox[0].x < s2it->mech->box.bbox[0].x)
{
const mech_data tmp = *it;
*it = *s2it;
mech_data * s2it_1=s2it-1;
while (s2it > its && s2it_1->mech->box.bbox[0].x > tmp.mech->box.bbox[0].x)*(s2it--)=*(s2it_1--);
*s2it = tmp;
}
}
}
//find possible collisions with sweapandprune and fill collision_list
if(node[i][k].mechs.size()>1)
{
_loop(its,it,ite,mech_data,node[i][k].mechs)
{
mech_data * it2 =it+1;
while(it2<ite)
{
if(it->mech->box.bbox[1].x <= it2->mech->box.bbox[0].x)break;
if(it->prix || it2->prix )  //one of two objects has primary column
if(it->priy || it2->priy )  //one of two objects has primary row
if(it->mech->box.intersect_y(&it2->mech->box))  //box intersection check
{
//push it->mech and it2->mech to collision_list
collision_list.push_back(...);
}
it2++;
}
}
}
}
};



Thats the simplest but I think better performance than usualy googled implementation. Becouse grid it self deletes old id objects , so there is no need to delete object manualy, object can be deleted in 2 loops: update id  and finally delete. No need to rebuild grid every loop. Becouse of prix and priy can be avoided dublicates and no need any cell be checked with neighbours. Objects must stay in the same memory address from creation to deletion.

This code is JUST for all moving objects.

Checking dynamic objects with static there are ~20 additional lines of code.

Sory for macros found in source code I just copy/paste..

_loop(its,it,ite)       ==                   it=its;while(it<ite){it++;}

_erase(its,it,ite)    safe erase than using <vector> container

testing application with statistics:

Edited by serumas, 21 July 2013 - 11:38 AM.

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.