Collision system performance
by Fenrir Wolf · in Torque Game Builder · 03/03/2005 (6:18 pm) · 11 replies
First off -- Josh, Melv, you two should be proud. T2D is everything I was hoping it would be! I am very glad you guys listened to our input -- and are continuing to do so.
I've had a very awesome last few days putting together a T2D demo based on one of my other projects. I don't want to go too much into it yet, but here are some very early teaser shots. (That's after my first day with T2D, I've gotten a lot more accomplished!)
However, I have hit a major snag to releasing my first T2D game. :) I'm hoping I can get some help!
I have an object that is fairly large (size of 600, 300). It has several large, overlapping mounts (around 120 to 400 size, some are square some are rectangular). Unfortunately, when my object gets on the screen -- sometimes the frame rate drops to around 2-3 fps. The main object is an fxAnimatedSprite2D, and its sub-objects are fxStaticSprite2Ds. Collision is turned on for all of the sub-objects, using collisionpolyprimitive #4 (though I have tried it with #3).
It doesn't cause a frame rate drop immediately -- unless something triggers a collision. However, if I rotate my main object (all mounted objects are set to track rotation), then a collision doesn't need to happen -- the frame rate takes a huge nosedive.
Just to make sure it wasn't fill-rate limited, I've removed all textures and replaced them with a small 32x32 blank image. I've disabled blending. I've turned off all of my backgrounds and disabled everything but the main object and the player's ship object. But it still does it.
Here's what it looks like when it's going to town.
So, what am I missing here? What sort of limitations is there on having overlapping objects, especially those that rotate? Just curious, as I want to do a very large, complicated object. I'm digging around in the code to see what's going on, but figured I'd ask too. :)
UPDATE: Ooops, looks like two seperate problems. For example, here's what happens if I set my object rotating:
So that's really slow for some reason. Oh, and in case you wonder why I want a bunch of overlapping, mounted objects: I want to a boss composed of seperate, destroyable pieces.
If I disable rotations, then collisions soak up most the per-frame time. Still investigating that.
I've had a very awesome last few days putting together a T2D demo based on one of my other projects. I don't want to go too much into it yet, but here are some very early teaser shots. (That's after my first day with T2D, I've gotten a lot more accomplished!)
However, I have hit a major snag to releasing my first T2D game. :) I'm hoping I can get some help!
I have an object that is fairly large (size of 600, 300). It has several large, overlapping mounts (around 120 to 400 size, some are square some are rectangular). Unfortunately, when my object gets on the screen -- sometimes the frame rate drops to around 2-3 fps. The main object is an fxAnimatedSprite2D, and its sub-objects are fxStaticSprite2Ds. Collision is turned on for all of the sub-objects, using collisionpolyprimitive #4 (though I have tried it with #3).
It doesn't cause a frame rate drop immediately -- unless something triggers a collision. However, if I rotate my main object (all mounted objects are set to track rotation), then a collision doesn't need to happen -- the frame rate takes a huge nosedive.
Just to make sure it wasn't fill-rate limited, I've removed all textures and replaced them with a small 32x32 blank image. I've disabled blending. I've turned off all of my backgrounds and disabled everything but the main object and the player's ship object. But it still does it.
Here's what it looks like when it's going to town.
So, what am I missing here? What sort of limitations is there on having overlapping objects, especially those that rotate? Just curious, as I want to do a very large, complicated object. I'm digging around in the code to see what's going on, but figured I'd ask too. :)
UPDATE: Ooops, looks like two seperate problems. For example, here's what happens if I set my object rotating:
%%NSTime %% Time Invoke # Name 99.926 11.746 467274 MainLoop 81.818 0.056 577 ProcessTimeEvent 70.467 0.039 577 ClientProcess 70.427 0.112 2451 updateScene2D 70.315 2.874 1880 subUpdateScene2D 67.208 0.280 9414 checksceneobjectbins2D 34.792 34.791 3643 addSceneObjectDirect2D 0.001 0.001 7 MemoryAlloc 0.000 0.000 1 MemoryRealloc 0.000 0.000 1 MemoryAlloc 0.000 0.000 1 MemoryFree 31.924 31.924 3643 removeSceneObject2D 0.212 0.054 7398 getBinRectangle2D 0.157 0.157 14796 getBinRange 0.217 0.042 5120 calculateCollision 0.175 0.175 5120 collide2D 0.016 0.006 671 getBinRectangle2D 0.010 0.010 1342 getBinRange 0.000 0.000 8 MemoryAlloc 11.151 0.039 577 RenderFrame 0.120 0.108 577 SimAdvanceTime 0.022 0.022 577 ClientNetProcess 0.001 0.001 577 ServerProcess 0.001 0.001 577 ServerNetProcess 0.000 0.000 4 MemoryAlloc 6.361 6.277 19 ProcessInputEvent
So that's really slow for some reason. Oh, and in case you wonder why I want a bunch of overlapping, mounted objects: I want to a boss composed of seperate, destroyable pieces.
If I disable rotations, then collisions soak up most the per-frame time. Still investigating that.
#2
Good work!
03/03/2005 (11:08 pm)
Great information mate! This should either be in the documentation, or perhaps part of the unofficial T2D FAQ.Good work!
#3
03/03/2005 (11:11 pm)
Nice looking project, and thanks for this detailed data! 
#4
Mr Grace, you once again "grace" us with your presence and most welcome you are too!
First-up, awesome screenies. Gotta' have them, we just gotta'!
Yes, the subject here is the broad-phase collision-detection thats functionally identical to the TGE one. I worked pretty hard to allow that setting to be changed as tuning it for your game can be critical. The problem we had was that this advanced information didn't fit anywhere for the initial EA release, hell, we've not even got official editor docs yet! I actually explained the two other parameters in another thread but I purposely skipped the bin ones. So cool to see people using the profiler (what a great tool it is)!
With regards to the debug-info, I totally agree. If you look on the debug-info banner, you'll already see the beginnings of that process. I report a value called "BinDen" which is short for "Bin Density". The idea here is that we'll show information on the broad-phase bin settings but additionally show a composite metric that gives you an approximate idea on how dense the bins are. Low-density bins means that you've currently got objects in the scene that don't fill-up the bins very well, high-density bins means that you've got the opposite problem and objects are all being lumped into the same bins, both cases decreasing the efficiency of the broad-phase check. I think adding some simple metric for the broad-phase would enable people to at least trivially regionalise the sweet-spot. We may end up changing the broad-phase check for something more adaptive though so we're holding-back on documenting too much advanced stuff. Besides, you're doing such a great job of documenting it yourself, why should we interfere. ;)
Lots of ideas coming for the debug-info banner and this is definately one of those things that'll get added first.
Awesome work David, please keep us all informed of your progress and boy would we want snapshots of that if you agreed!
- Melv.
03/04/2005 (1:57 am)
@David: Now that's what I'm talkin' 'bout right there....Mr Grace, you once again "grace" us with your presence and most welcome you are too!
First-up, awesome screenies. Gotta' have them, we just gotta'!
Yes, the subject here is the broad-phase collision-detection thats functionally identical to the TGE one. I worked pretty hard to allow that setting to be changed as tuning it for your game can be critical. The problem we had was that this advanced information didn't fit anywhere for the initial EA release, hell, we've not even got official editor docs yet! I actually explained the two other parameters in another thread but I purposely skipped the bin ones. So cool to see people using the profiler (what a great tool it is)!
With regards to the debug-info, I totally agree. If you look on the debug-info banner, you'll already see the beginnings of that process. I report a value called "BinDen" which is short for "Bin Density". The idea here is that we'll show information on the broad-phase bin settings but additionally show a composite metric that gives you an approximate idea on how dense the bins are. Low-density bins means that you've currently got objects in the scene that don't fill-up the bins very well, high-density bins means that you've got the opposite problem and objects are all being lumped into the same bins, both cases decreasing the efficiency of the broad-phase check. I think adding some simple metric for the broad-phase would enable people to at least trivially regionalise the sweet-spot. We may end up changing the broad-phase check for something more adaptive though so we're holding-back on documenting too much advanced stuff. Besides, you're doing such a great job of documenting it yourself, why should we interfere. ;)
Lots of ideas coming for the debug-info banner and this is definately one of those things that'll get added first.
Awesome work David, please keep us all informed of your progress and boy would we want snapshots of that if you agreed!
- Melv.
#5
One of the immediate ideas for changes to T2Ds container would be to also allow a configurable size for the overflow bins. Overflow bins are for objects that exceed a certain threshold in size in either direction. These get added to a linear list so we go to O(n) but luckily, these objects are typically few. At the moment, if your object exceeds in size a complete coverage of (binSize*binQty) then it gets placed in an overflow.
To say that 4 is optimal is being kind. It's kinda where we left it for most of the dev work although it does work well. We should seriously consider increasing that a little, if not to 10.
Just an idea.
- Melv.
03/04/2005 (2:04 am)
Additional...One of the immediate ideas for changes to T2Ds container would be to also allow a configurable size for the overflow bins. Overflow bins are for objects that exceed a certain threshold in size in either direction. These get added to a linear list so we go to O(n) but luckily, these objects are typically few. At the moment, if your object exceeds in size a complete coverage of (binSize*binQty) then it gets placed in an overflow.
To say that 4 is optimal is being kind. It's kinda where we left it for most of the dev work although it does work well. We should seriously consider increasing that a little, if not to 10.
Just an idea.
- Melv.
#6
These are the defaults:-
mScenePhysicsLimitFPS(40.0f) - Threshold FPS when sub-integrator kicks-in.
mScenePhysicsTargetFPS(100.0f) - Target FPS when sub-integrator tries to attain.
mScenePhysicsMaxIterations(16) - Maximum iterations allowed trying to reach TargetFPS.
16 Iterations can be quite severe if you've got lots of collision-detection going on but works well for stabilising box-stacking style physics. For side-shooters, this can be reduced drastically!
- Melv.
03/04/2005 (3:33 am)
@David: I just noticed that the Physical Iteration Count for the physics is hitting its default ceiling of 16. You can also control how high this goes. This is essentially an emergency stabilisation situation for the physics. If the FPS gets too low (below a threshold), this routine kicks-in and starts to sub-integrate, up to a limited number of iterations. In some cases, with particularly low FPS, this only makes the situation worse but what it does do is keep the physics routine from going off into crazy values, possibly even a NAN situation. Very important, especially if the computer decides to do something horrible in the background like a virus scan and T2D suddenly gets a massive time-delta.These are the defaults:-
mScenePhysicsLimitFPS(40.0f) - Threshold FPS when sub-integrator kicks-in.
mScenePhysicsTargetFPS(100.0f) - Target FPS when sub-integrator tries to attain.
mScenePhysicsMaxIterations(16) - Maximum iterations allowed trying to reach TargetFPS.
16 Iterations can be quite severe if you've got lots of collision-detection going on but works well for stabilising box-stacking style physics. For side-shooters, this can be reduced drastically!
- Melv.
#7
That's good info about the target FPS settings -- I was originally examining that as a potential culprit. (I was thinking the game was fill-rate limited and it was causing the physics engine to miss frames.) Even setting those values to very low FPS was still causing maxItr to be hit, so I knew the problem wasn't there. However, I will play with lowering the values, as you're right, there's not any actual collision-oriented physics going on it my game. I don't want to set them too low, though, as it causes player control to be a bit sloppy. :)
Aha! I didn't even notice that bin density output under the debug screen. But now that you've pointed it out, I see what it's for. That'll help me fine tune the settings, then!
@Robert: All I can see is you've got slow-down problems, try adding that initialise() command as I demonstrated above. ;)
I'm happy now, my big multi-part boss works excellently. Yaaay!
03/04/2005 (2:27 pm)
Hey Melv, thanks for the shout. Yeah, I'm still here, just been pretty busy lately, haven't had much time to hang out on here. But I just couldn't pass up the first public release of T2D, so here I am. ;)That's good info about the target FPS settings -- I was originally examining that as a potential culprit. (I was thinking the game was fill-rate limited and it was causing the physics engine to miss frames.) Even setting those values to very low FPS was still causing maxItr to be hit, so I knew the problem wasn't there. However, I will play with lowering the values, as you're right, there's not any actual collision-oriented physics going on it my game. I don't want to set them too low, though, as it causes player control to be a bit sloppy. :)
Aha! I didn't even notice that bin density output under the debug screen. But now that you've pointed it out, I see what it's for. That'll help me fine tune the settings, then!
@Robert: All I can see is you've got slow-down problems, try adding that initialise() command as I demonstrated above. ;)
I'm happy now, my big multi-part boss works excellently. Yaaay!
#8
Definately going to average-out the bin-size/qty for next release though.
Great to see you here! :)
- Melv.
03/04/2005 (2:45 pm)
@David: That BinDen is just a dummy at the moment so don't go looking at it yet. Expect it to become active in the future though.Definately going to average-out the bin-size/qty for next release though.
Great to see you here! :)
- Melv.
#9
Or am I missing the boat here?
~neo
07/27/2005 (8:34 am)
Just a quick question as I haven't had time to delve into T2D just yet. It seems there is an aweful lot of time spent in addSceneObject2D and removeSceneObject2D per frame update. Surely one should not be adding/removing stuff each frame?Or am I missing the boat here?
~neo
#10
That is repositioning the object in the broad-phase collision bins, not the scenegraph. It is a low overhead routine but in this case, it was being called an extortionate number of times! This information is used for collision detection and picking. This happens when an object moves outside of its allocated bin area. The fact that it was spending so much time in that routine is what this post is all about. In other words, the original T2D was released with a very small bin-size as default (this can be changed) resulting in an object being positioned in multiple bins and having lots of bin relocations per frame. This is particular bad for large quantities of projections and/or large objects that cover hundreds of bins!
The v1.0.2 release of T2D had a much more realistic bin size as default although you can obviously configure this value as you wish per scene. The debug-info banner also provides detail such as bin-relocations/sec etc to help guide you.
Essentially though, this post was highlighting that a bad bin setting causes a huge overhead.
- Melv.
07/27/2005 (9:55 am)
Neo,That is repositioning the object in the broad-phase collision bins, not the scenegraph. It is a low overhead routine but in this case, it was being called an extortionate number of times! This information is used for collision detection and picking. This happens when an object moves outside of its allocated bin area. The fact that it was spending so much time in that routine is what this post is all about. In other words, the original T2D was released with a very small bin-size as default (this can be changed) resulting in an object being positioned in multiple bins and having lots of bin relocations per frame. This is particular bad for large quantities of projections and/or large objects that cover hundreds of bins!
The v1.0.2 release of T2D had a much more realistic bin size as default although you can obviously configure this value as you wish per scene. The debug-info banner also provides detail such as bin-relocations/sec etc to help guide you.
Essentially though, this post was highlighting that a bad bin setting causes a huge overhead.
- Melv.
#11
the workflow. Pheew ;p
Thanx for the clarification.
~neo
07/27/2005 (10:04 am)
Thats along the lines of how it thought it works, just got scared that i had misunderstood the workflow. Pheew ;p
Thanx for the clarification.
~neo
Torque Owner Fenrir Wolf
My bin container size was too small. The defaults of 4 units per bin is probably quite optimal when you've got a lot of small objects on the screen, but in my case, my large boss was causing T2D to thrash itself to death as it created/updated/examined lots of bins. So, I added this to right after my fxSceneGraph2D creation:
10 units-per-bin was a number I pulled straight out of my butt. However, I noticed an immediate speedup of Torque 2D and it no longer thrashed when doing fxSceneContainer::checkSceneObjectBins.
Using fxSceneGraph2D::initialise() is going to be very critical to making sure that Torque 2D performs optimally in your specific game implementation! The default appearently good for lots and lots of small objects, but if you use a lot of larger objects then you will need to up the binsize. Possibly also the bincount.
I really think bin information should be a part of the debug output. Right now, it's lumped in with the physics and that's what made me think initially the problem was with either collisions or physical sim.
The docs talk about the bin system, but I saw no mention of bin size or bin count. I know it's probably already been considered, but I really recommend that this is explained in more detail. Otherwise, people will freak out and declare Torque 2D uber-slow and unlike me, won't want to dig into the code to see what's up. ;)