For a simple 3D game with a level mesh and some obstacles I did a "roll your own" collision system.
Because I had already written the rendering engine I had code for matrices vectors and planes already.
All the levels were less then 15,000 polys so I wrote a super quick function to store them in a 32x32 grid structure.
So to test a sphere against it results in about 20-30 triangles being tested in a sphere vs triangle routine.
Very little code and adequately satisfying results. It was easy to integrate and very very fast.
BUT - and there is usually a but - this was only suitable for the situation and will not suit most use cases.
It was a simple game with only very basic physics, gravity/collisions/orient-to-surface, that kinda thing, no full blown rigid body dynamics. So no proper rotations, inertia, mass or any of that stuff.
If I had more bodies in the levels with more realistic physics then and engine would have been the way to go. It would have been overkill for me though as it was a simple environment.
So it does truly depend on the situation, including what resources you already have available and you knowledge level.
Do you need proper collision response or just basic detection.
Collision detection is pretty easy if you know what you are doing.
i.e. to write a sphere vs triangle, sphere vs box, box vs capsule etc... it fairly straight forward.
You then might need some structures for broadphase.
If you do not need solid collision resolution then you should be fine to roll your own. Managing contact resolution though is a whole new beast - and a scary one at that.
So in summary, if you only need the detection - roll your own or take a look around there are plenty of collision detection libraries out there (or at least well structured engines where you can just take the detection package). If you need rock solid resolution of said collisions, i.e. anything more complex that simple reprojection or stopping, then I would run with a full lib such as bullet.
Probably a really easy question for you season pros, but I can't seem to think of an obvious solution to this problem.
Here it is in a simple form:
Imagine a rectangle travelling horizontally, it collides with another rectangle that is above it, overlapping it only slightly from above:
___ | |
| | |-------|
| | ----->
This will result in the object being pushed down into the floor (the penetration in the downward direction may be the smallest) which will lead to it being pushed back up by the floor.
How do you avoid this problem and ensure that the object stops dead on collision rather than gets pushed down.
I though about separating the collision into stages, testing only one axis at a time but that feels clunky.
Hold the phones, whilst writing this I think maybe I should never check the bottom side of the top body because its normal (if dotted with the direction of the other body) would show that they should never be tested against each other.
Maybe that is more important than I though, never check a face if its normal dot the direction is greater than 0? Am I on the right lines? Am only really dabbling here so not the end of the world if I can work it out. Thanks for your time.
8 FPS is pretty slow, I would wager that it is more your GPU that is slowing it rather than the culling though. (could even be falling back to software as even with 10,000 objects in the scene it should only be rendering about 800 meshes which shouldn't be too stressful)*
The time for culling should be displayed in the upper left (on my machine it would be about 1ms for 10,000 objects occasionally flicking to 2ms)
Forgot to tell you the controls, "m" to change materials, there are a couple in there one is normal mapped, and "n" to change the mesh you can see if how a higer triangle count affects things.
Just read you mentioned fill rate (one day I will learn to read a whole post before replying), this deffo makes sense as when you reduce the window size the culling if anything will have more work to do so yeah probably not an issue.
If you click the link on the page above to go to the demo then press the "+" key to start adding objects, you should see that you can smash though the 10,000 (not on screen but in the world) barrier no sweat barely a millisecond of time on my machine (which isn't amazing or anything)
Not to mention this is actionscript 3, EASILY 10 time slower than most normal languages.
All I am doing is fast frustum culling with caching.
Posted by bwhiting
on 27 September 2012 - 05:12 AM
1st off, that's the kinda thing that would be a piece of cake in flash, lolz
2ndly, as the above will not help you in the slightest here is an idea:
For everything you draw in your canvas. draw the same thing again in a second canvas (offscreen/invisible) but draw it with a solid colour, this colour must be unique and will be used ad an identifier, so keep track of it - make a link somehow between the element you are drawing and that colour.
then when the user clicks or moves their mouse over the canvas, just locate the x,y coordinates and use that as a lookup on the hidden canvas, you can then use the colour to identify the element they are over in the visible canvas, make sense?
you will have to draw everything twice (so bad idea for fullscreen canvas with tonnes of elements)
it will only give the id 1 element (the top most one) as you cannot hold references to muliple elements easily in one colour... would be rather tricky to implement)
it will be lightning fast to work out what the users mouse is over
I think this (for a lot of cases - but not all) will be a simpler and faster approach, detecting if a point is within a path can be quite tricky, especially if the path is complex and has curves/overlaps etc...
If you can't do it that way let me know and I will try to dig out some point in path algorithms.
I have simple frustum culling (running in flash) and it will culll away 10-20,000 objects in about 1ms... on a more low level languange that number should be 5 - 10 times smaller still!
Sounds suspect to me, are you frustum culling triangles or something?
If that really is an issue for you I recommend caching (it gave me a whopping speed increase). Its real simple to add in, just store the id of the plane of plane that cause the frustum check to fail, then check that one 1st next time round... about 2 minutes of coding and can almost double your speed.
With that in mind for any scene comprising of less then 10,000 objects or so its not really worth implementing any tree structure for me.