Author Topic: Collision detection performance  (Read 7343 times)

0 Members and 1 Guest are viewing this topic.

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: Collision detection performance
i always did like the collision mesh idea. in fact it is possible to them now with existing techniques and no code changes. but its something that has to be done mod side. could imagine it being done to the mediavps as a whole, though im not sure if it would have any unforeseen side effects. now if pcs2 would set this up automatically given a subobjectname-collision for each peice of ship, that would be awesome. as it stands you have to play with a bunch of subobject properties.
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN

 

Offline Swifty

  • 210
  • I reject your fantasy & substitute my own
Re: Collision detection performance
I actually have a patch that does exactly that. You would just add a submodel to a POF in PCS2 with a -collision suffix and FSO will do a collision query against that model instead of the real one.

I whipped it up for Diaspora. We tried using it but it was demanded too much work from our artists to get working. I'm sure other people in the community would appreciate it but it's kinda buggy at the moment.

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: Collision detection performance
it works and i like it, but it seems a little bit like a hack at worst and at best not an optimal solution for the long term. my concern here is that a lot of unnecessary data would be contained in the pof file/model data structure. a collision mesh doesnt need texture and uv mapping info, and a non-collidable mesh does not need to have complete collision data. all subobjects are essentially treated the same and you currently only apply flags to disable features. any data generated would essentially be wasted space.

a proper solution would be a newer optimized pof chunk formats and optimized model data structure. like a unified object class that contains for each subobject, visible geometry (with texture data, uv space(s), ibxes, lod stack, etc), collision geometry (polygonal object, collision trees, etc), the class would also contain a header containing hierarchy info and transform data, radius, bounding box, etc. this class is stored in the pof as a new chunk of course the actual structure would need to be dependent on how the innards of the engine actually work. all data but the header would be optional of course, you may want non-collideable geometry like fighter bay force fields, you may want to omit everything and use the object as a node for animation purposes, so all that you have is the header data.

another idea to consider is perhaps to make the model format its own library and have it shared with pcs2, so that when you make changes to the model format, you just update the library and you just have to rebuild pcs2 for compatibility. for artisitc load i dont see making a colision mesh any more complicated than an lod. just a one minute poly chop job. im sure many modders would just want you to use the second lod as a collision mesh. much of this would be a huge workload, but it might pay off in the long run. the way i see it the current model format is somewhat of a indifference to both rendering and collision detection. we just need to maintain compatibility with the old format for reverse compatibility, and its well suited to retail data and old pre-htl mods. but to run the engine with what it could do now, an optimized model format would improve performance on all fronts.
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Collision detection performance
Convex hulls wouldn't work in FS ships. Consider the Collossus

you use more than one in a composite.
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline jr2

  • The Mail Man
  • 212
  • It's prounounced jayartoo 0x6A7232
    • Steam
Re: Collision detection performance
@This whole idea: how would you detect collisions on subsystems and turrets then?

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Collision detection performance
same way you do now, those distinctions are not effected by the low level stuff.
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: Collision detection performance
@This whole idea: how would you detect collisions on subsystems and turrets then?


collision detection involves check every object in the game with every other object for collisions. it would be slow to do full polygon-accurate tests on such a scale (the maths are mind/cpu boggling) so what you do is start with a simple test. check to see if the raddi of various objects intersect. a radius test is far cheaper than checking otrees or convex hull or whatever system you have in place (iirc freespace uses bsp algorithms?). but what it does is culls out all the objects that really are not likely to collide. you get a much shorter list of objects which need more scrutiny. so you do a more expensive test with those to cull the list further, check for bounding box collisions, and toss further objects from the list. so that when you start doing mathematically expinsive tests, the list of objects is tiny, maybe 2 or 3 objects at the most. thats the theory anyway. freespace handles collisions between certain kinds of objects differently. weapons on weapon collisions only really care about the radius test, where as ship on ship collisions require a lot more work to look right.

we still consider submodels as parts of the ship so they are only tested for collisions after the ship has tested positive for potential collision. way i would do things is to treat every submodel in the game as a potential collision object, with its own radius, bbox and transform, this might seem slower at first because youre making the object list bigger. but what your doing is eliminating a lot of the list in early radius checks. so if a ship has 50 turrets, and your checking them against an incoming bomb. instead of having to recursively test all of those turrets after the ship tests positive, you might get the ship hull, one turret and one turret barrel in the list, and the rest of the turrets can be ignored. so fewer objects to run high precision collision tests on. if you get multiple positives then the closer collision position vector wins.

this kind of mentality could also be applied to rendering, where submodels get depth sorted and loded based on their distance from the camera and not their parent's distance (so when staring at the front end of a 6km capitol ****, the 2k poly tail gun 6klicks away doesnt render in full detail). it would also make subobject animation better because it would allow translating through the extra xform data in the submodel. this is why id like to see new object formats in our pof files. of course im not holding my breath on this. the number of changes to the engine to do something like this is huge. thousands of coder hours. but if i were writing a new game engine, that is how i would do things.
« Last Edit: August 11, 2011, 09:11:16 pm by Nuke »
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Collision detection performance
"freespace uses bsp algorithms"

technically it's sort of a BSP/octree hybrid, but yeah basically.

"way i would do things is to treat every submodel in the game as a potential collision object, with its own radius, bbox and transform"
problem with that is you just made the first list of possible collisions not 50 items longer, but 50 TIMES larger, that first test is n^2 complexity, if you have a static position relationship between a collection of objects, you can cull a huge swath of tests by testing the collection rather than every individual object independently, especially when in the vast majority of cases there will be no collision.
« Last Edit: August 11, 2011, 09:19:10 pm by Bobboau »
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: Collision detection performance
surely there are other less expensive tests you can do to cull colliding objects from collision lists. like objects that did not collide in the last frame and are moving away from eachother can be eliminated. you can direction eliminate things, ake velocity and make a huge plane prependicular to it, and cull everything behind that plane. if something was heading up from behind it would detect collision with you when its turn to be tested came up. coplexity will always be n^2 so your best bet is to make n smaller with trivial operations. then make the non-trivial operations simpler by removing the need to consider dynamics of child objects.
« Last Edit: August 11, 2011, 10:41:10 pm by Nuke »
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Collision detection performance
the test isn't the expensive part it's the 'touching them at all' aspect that is the killer no matter how simple and fast a test is you will still have n^2 complexity, which will overpower any optimization you put into it, unless you can avoid testing every object with every other object, which you can't when they can at any moment turn around and hit something completely different.
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline Sushi

  • Art Critic
  • 211
Re: Collision detection performance
surely there are other less expensive tests you can do to cull colliding objects from collision lists. like objects that did not collide in the last frame and are moving away from eachother can be eliminated. you can direction eliminate things, ake velocity and make a huge plane prependicular to it, and cull everything behind that plane. if something was heading up from behind it would detect collision with you when its turn to be tested came up. coplexity will always be n^2 so your best bet is to make n smaller with trivial operations. then make the non-trivial operations simpler by removing the need to consider dynamics of child objects.

There actually already are a number of optimizations that cull collision pairs exactly like you describe. They cause some grief of their own, though. :)

 

Offline Swifty

  • 210
  • I reject your fantasy & substitute my own
Re: Collision detection performance
The best optimization for broad phase culling is probably sort and sweep or object k-d trees. In terms of what's easier to implement, I chose sort and sweep in my current optimization build. As I said previously in the thread, it lessened the broad phase culling overhead but it still has some pretty noticeable bugs prompting me to give it some more time in the oven.

Treating each submodel as it's own object just doesn't make any sense. You already have a basic test to cull out all submodels in a given set and that's the radius test for an object. You're not going to make collision detection any faster from eliminating the broad to narrow hierarchy. That's like saying traversing down an k-d tree is too expensive so let's just test all the triangles.

Besides, the place where we figure out which submodels should be tested by doing quick outs on their bounding boxes, mc_check_subobj, isn't very expensive anymore. I recently committed an optimization to that function that calculates the transformation of each subobject per frame instead of per collision query. Nuke's "optimization" wouldn't do anything but make things more expensive.

 

Offline Luis Dias

  • 211
Re: Collision detection performance
Soo..... do you have any ideas going forward?

 

Offline The E

  • He's Ebeneezer Goode
  • Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Collision detection performance
He just told you what ideas he has, and what he is working on.
If I'm just aching this can't go on
I came from chasing dreams to feel alone
There must be changes, miss to feel strong
I really need lifе to touch me
--Evergrey, Where August Mourns

 

Offline Swifty

  • 210
  • I reject your fantasy & substitute my own
Re: Collision detection performance
Soo..... do you have any ideas going forward?

Did you even read any of my posts in this thread?

 

Offline Luis Dias

  • 211
Re: Collision detection performance
Oh sorry, I thought you meant that you had an almost finished build. I was merely asking the academic question of "what ideas could be placed in the future", but now I see you are still worried about these bugs in the current solution. Sorry again.

  

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: Collision detection performance
The best optimization for broad phase culling is probably sort and sweep or object k-d trees. In terms of what's easier to implement, I chose sort and sweep in my current optimization build. As I said previously in the thread, it lessened the broad phase culling overhead but it still has some pretty noticeable bugs prompting me to give it some more time in the oven.

Treating each submodel as it's own object just doesn't make any sense. You already have a basic test to cull out all submodels in a given set and that's the radius test for an object. You're not going to make collision detection any faster from eliminating the broad to narrow hierarchy. That's like saying traversing down an k-d tree is too expensive so let's just test all the triangles.

Besides, the place where we figure out which submodels should be tested by doing quick outs on their bounding boxes, mc_check_subobj, isn't very expensive anymore. I recently committed an optimization to that function that calculates the transformation of each subobject per frame instead of per collision query. Nuke's "optimization" wouldn't do anything but make things more expensive.

youve got the code figured out better than i do. only collision detection engine i did was 2d and that one was kinda buggy. i was just under the impression that it was faster to do a large number of radius checks than a small number of bbox or octree/bsp checks. but il deffer to your expertise on the matter.
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN