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?

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

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.

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.

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.

Have you made objects to move properly allready?

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.

Have you made objects to move properly allready?

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

Thank everyone for tips! Ill try them out.

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 .

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

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
		machina.add(this); //readd to grid with new 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:

http://serumas.gamedev.lt/temp/testing.zip