Collision detection vessel - vessel

[kalral]

I dont have much knowledge about collisions, that is the reason that I want to learn it.
Do you think it is possible to do collision detection between vessels? If its possible I want to give it a try. There are some existing solutions like Bullet Physics(https://github.com/bulletphysics/bullet3), it can be compiled with 64 bit support.
This https://www.orbiter-forum.com/threads/collision-detection.25942/post-405187 seems to suggest its doable.

 

[jedidia]

There has been a proof of concept vehicle using bullet once, so it can be done. Now that the source is open it's not really a question anymore what is doable, but more of what should be done and how...

 

[kalral]

There has been a proof of concept vehicle using bullet once, so it can be done. Now that the source is open it's not really a question anymore what is doable, but more of what should be done and how...

Exactly. I guess we should define issues in Github so that we could keep track of all the things that we want to improve or work on. I looked at https://osdn.net/projects/orbitersoftware/ticket/ for ticket list, to port the tickets that are defined, to issues on github. Is there any place where the tickets are already created for Orbiter?

 

[jedidia]

I read somewhere that a good optimization could be to first check if the bounding spheres of two vessels intersect, followed by bounding boxes (not axis aligned), followed finally by the collision mesh, which would either use multiple convex hulls or tri -> tri intersection tests.

You can throw out the sphere. You check the bounding box, then you check the collision mesh. Checking for sphere means calculating distance, which is more expensive than checking the bounding box, for which a check merely involves comparing a maximum of 6 variable pairs at worst, and potentially as little as two if the result is negative.

However, the issue is with what you compare exactly. Iterating through bounding boxes and comparing each to each is inefficient, so you usually build a quad tree with point values that allows to find nearest neighbours in a 3-d space a lot faster. But that isn't the real problem either. Somebody like artlav can probably do all that during his lunch break.

The real work starts once the collision is detected. Calculating impact vectors, applying energies, and then most of all what on earth now happens. There's multiple levels of details that one can address here. You can just treat both objects as indestructible spheres, pool style, in which case the result becomes fairly easy to calculate, but also oftentimes hilarious, especially with time accelleration involved (accidentally being ejected from the solar system at light speed is one of the classical ones...).
Next you can start consider mesh geometry to actually turn part of the energy into rotational velocity based on the impact, then you can start considering things like rigidity and how much of the impact energy is absorbed by each object instead of just redirecting momentum, then you can start wondering about how that energy would deform the objects, etc. etc.

Really, detecting the collision is the easy part of collision detection. The hard part is all that comes afterwards, which is why libraries like bullet exist.

 

[Face]

You can just treat both objects as indestructible spheres, pool style, in which case the result becomes fairly easy to calculate, but also oftentimes hilarious, especially with time accelleration involved (accidentally being ejected from the solar system at light speed is one of the classical ones...).

Space Pool-Billard! Now that would make a nice game: take your dragonfly as cue stick and get those colorful containers into the space station with the help of that white container.

 

[jedidia]

And you have to make it hit the dockport, with proper alignement, of course... ?

 

[Arvil]

And the white one must go last . . .

 

[n72.75]

Collision detection has been on developer's minds for a while, by the looks of it: http://djvader.blogspot.com/2006/10/?m=0

With variable length timesteps maintaining conservation of energy/continuity will be the hardest part.

 

[N_Molson]

I think it should be quite high on the priority list, if we want to keep Orbiter "up-to-date" and make it more attractive.

 

[n72.75]

Collisions are hard. And yes they should be implimented, but probably not in a "vessels now just collide with each other in the new version" way.

Maybe defining some new collision features for the vessel api would be the right way to do it. That way we let addons control how and if they support colision.

 

[n72.75]

Using gpgpu (platform and hardware agnostic) would be the best way to compute the actual colisions.

 

[N_Molson]

I'm a bit confused, you mean in real-time or some kind of "precalculation" ?

 

[jedidia]

Using gpgpu (platform and hardware agnostic) would be the best way to compute the actual colisions.

I'm not just a bit confused as N_Molson, I don't get what you're getting at at all. gpgpu is definitely not hardware agnostic (writing algorithm for gpus is highly sensitive to the type of gpu!), and also, when you're playing orbiter, the gpu is already busyrendering the graphics, so you can't actually use it for anything else, unless you have two of those? Plus, using a gpu for generic calculations implies having a loopback, which I think requires a specialised board, or rigging something up.
Last but not least, calculating the collisions is really not that hard work for the CPU when using a decent algorithm. As I mentioned earlier in this threat, it's calculating everything that follows, or rather, the amount of additional data that requires. None of those problems can be solved with a gpu...

 

[n72.75]

I'm not just a bit confused as N_Molson, I don't get what you're getting at at all. gpgpu is definitely not hardware agnostic (writing algorithm for gpus is highly sensitive to the type of gpu!), and also, when you're playing orbiter, the gpu is already busyrendering the graphics, so you can't actually use it for anything else, unless you have two of those? Plus, using a gpu for generic calculations implies having a loopback, which I think requires a specialised board, or rigging something up.
Last but not least, calculating the collisions is really not that hard work for the CPU when using a decent algorithm. As I mentioned earlier in this threat, it's calculating everything that follows, or rather, the amount of additional data that requires. None of those problems can be solved with a gpu...

It's very likely that I don't know what I'm talking about.

 

[N_Molson]

I'd say that bounding boxes and "billard ball" type collisions would be a start...

 

[kuddel]

...wasn't there a demo implementation some years ago? I think I remember a DG bouncing off a station or so....
Even if that's not perfect (I doubd we will ever get a perfect solution) it might be a starting point.
Whatever it will be, as long as the user can chose to disable it, if he/she is not happy with it, it's fine.
Calculating a high-speed collision with orbital speeds is also challenging I think, as even one frame per second can mean several hundreds of meters traveled distance.
Althoug most collisions might be encountered at "relatve low" relative speeds and could therefore be handled, I think.
The after-effects however are another can-of-worms I have to admit.
Making it too generic is not nice for the ambitious addon-developer; making it too addon-specific is not nice for the "regular" quick and easy addon-developer.

/just my 2 cents

 

[N_Molson]

...wasn't there a demo implementation some years ago? I think I remember a DG bouncing off a station or so....

Artlav did that with his own OpenGL graphic client. That was a long time ago. I even had it working.

IMHO "orbital speed" collisions could be calculated using a probabilistic model. And below a given relative speed you would switch to a "bounding box" model.

 

[GLS]

I'd say that bounding boxes and "billard ball" type collisions would be a start...

...wasn't there a demo implementation some years ago? I think I remember a DG bouncing off a station or so....
Even if that's not perfect (I doubd we will ever get a perfect solution) it might be a starting point.
Whatever it will be, as long as the user can chose to disable it, if he/she is not happy with it, it's fine.
Calculating a high-speed collision with orbital speeds is also challenging I think, as even one frame per second can mean several hundreds of meters traveled distance.
Althoug most collisions might be encountered at "relatve low" relative speeds and could therefore be handled, I think.
The after-effects however are another can-of-worms I have to admit.
Making it too generic is not nice for the ambitious addon-developer; making it too addon-specific is not nice for the "regular" quick and easy addon-developer.

/just my 2 cents

A convex hull, like the touchdown point definitions, making it non-mandatory for the vessel (it would fly thru the all others as now) and having a global disable flag (reverting to the current behaviour) would be a start. The big issue here is "point coverage": if you have the NCC-1701 vessel and you place some points bounding it (top of the bridge, half-dozen around the sourcer section, a few more at the back and front of the nacelles), it would work well as touchdown points for any attitude, but if one takes the shuttlecraft, it would be possible to fly right thru the sourcer section unless lots of points are added to cover all the surface... so the system would probably need to be a bit more advanced.

What happens during a collision... probably there is no need to have a spring-damper system, like the touchdown points, so it should be simpler than that.

 

[Max-Q]

A convex hull, like the touchdown point definitions, making it non-mandatory for the vessel (it would fly thru the all others as now) and having a global disable flag (reverting to the current behaviour) would be a start.

Why not use each mesh vertex as a point instead of defining the points manually? There could be a new API function to set a meshgroup as "hard" (default is no collision, so backward compatibility is there). This would allow addon devs to decide what parts of their model are "hard" (hull, etc.) in a really easy way; something like "oapiSetMeshroupHard(int msh_idx, int group_idx, bool hard). Then, only a few groups would need to be checked for collision and high-poly stuff antennas, cockpits, etc. wouldn't need to be checked. Also it would be backward compatible! In theory, shouldn't be that hard to implement since Orbiter already gives us vertex-level access to the mesh.

 

[GLS]

Why not use each mesh vertex as a point instead of defining the points manually? There could be a new API function to set a meshgroup as "hard" (default is no collision, so backward compatibility is there). This would allow addon devs to decide what parts of their model are "hard" (hull, etc.) in a really easy way; something like "oapiSetMeshroupHard(int msh_idx, int group_idx, bool hard). Then, only a few groups would need to be checked for collision and high-poly stuff antennas, cockpits, etc. wouldn't need to be checked. Also it would be backward compatible! In theory, shouldn't be that hard to implement since Orbiter already gives us vertex-level access to the mesh.

Even picking mesh groups, the amount of points might be too high... but yes, using the mesh would be like "what you see is what you get", which is the best result. The question is: how expensive would that be?