CollisionDetection Design

Hi all,

I was thinking today, if we are going to implement triangle accuracy collision detection, and pixel collision detection, they will most definetly be slower than BoundingBox’s or BoundingSphere.

So what I was thinking is that we can assign a geometry more than one BoundingSomething. Set a priority on collision and check accordingly.

E.g. You have a model surrounded by a triangle accurate boundingThing, thats surrounded by a BoundingBox. You set the priority of the box to 1, so it gets checked first, if there is a collision, check the triangle thing. If the triangle thing doesn’t have a collision, then a collision hasn’t occured.

What do you think?

That’s a good idea for what it would do. However, if you want to put bullet holes on your walls in a FPS then you need pixel level collision.

For me, I would like it to cut down on the number of polygons I need. Right now I have to use a tons because I’m building a strategy game with a hexagon based map. With pixel collision I could just have a quad. So the speed would be made up in another area.

I dont understand your last query. Pixel level collision detection is the next level after triangle so and so.

So you just put that in as another priority.

Besides, why are you using hexagons? boundingBox or spheres dont fit on those perfectly, yet a boundingBox fits on a quad perfectly (Unless you rotate).

Can you please furthur explain your opinion?

I’m creating a stragegy game with a game ‘board’.

The board is made of hexagons. Right now I’m creating tons of hexagons and putting bounding spheres in them all, just inside instead of outside.

However, with a large board this means tons of polys, since each hex is made of 6 triangles. Each hex needs to be interactive with the mouse.

However, if I had pixel level collision then I could just put one big texture of hexagons on one quad. Then just change the texture.

i see your point. So your in favour of pixel level collision? its on the "todo" list, like most things.

With pixel collision I could just have a quad. So the speed would be made up in another area.

Have you seen how "terribely" slow Area in Java2D is? and thats only 2D, whats going to happen to pixel level collision in 3D?!

It can’t be too bad. Almost every FPS that I know of has it. Unless they have some special way of doing it that I’m not aware of.


… i think all the detection levels should be optional.

Only pixel (UV - coord) detection makes no sense without triangle detection.

and imho it makes no sense to give a priority as it should always be

checking bounding vol first and then triangles because the other way would be checking triangles only.



I think they are mimicing pixel level. I have this idea, not sure whether its new or not, but basically building a Collisionable Triangle. This triangle would then be cloned and placed over every single Geometric triangle in the model. And just collide with that. As ive never heard or done this before, im not sure how great it is.

Back to the subject at hand. Can anyone see something wrong with the system?

I agree with winkmen, if you have a bounding volume then that’s highest priority. However, like DarkProphet said, if you want more than one boundling volume on the same mesh then you would need a way to set up priority.

Yes, triangle level detection has to happen before pixel level. So, really there’s no reason to even worry about pixel level until the triangle level is complete :).

Totally agree.

Winkman, what if you had a bounding box and a bounding sphere?

Imagine a sonic 3d style game, for the adventure game, you want a boundingBox; For tunnel races, you want a sphere.

In that case, you have to have priority levels.

badmi, that is not related to what we are discussing here tho. We are discussing collision detection heirachy system. You are simply discussing assigning BoundingVolumes to nodes.

"DarkProphet" wrote:
badmi, that is not related to what we are discussing here tho. We are discussing collision detection heirachy system. You are simply discussing assigning BoundingVolumes to nodes.

You seam to miss understand my post. I am talking about replacing com.jme.intersection with functions inside the Spatial that are called during update.

dark prophet and guurk

yes i agree if you have more than one bounding vol that you need sort of priority but i still think if you need high accuracy you need triangle coll detection instead of many volumes.

if you want to use different bounding volumes why not switch between them instead of use more than one at the same time?

but thats only my two € - cent :slight_smile:



oh yes ofcourse, what im saying is that triangle accuracy collision detection might cost you in performance, so to get around it, use BoundingBox’s with priorities. If a collision occurs in the boundingBox, then go on to furthur collide with the triangle accuracy bounding volume.

Wow, Mojo goes away for one second and look what he misses. XD

Mojo and I actually talked briefly about supporting multiple bounds in the past. It was more in the context of engine efficiency but would also accomplish what you are talking about. In our conversation we talked about always having a bounding sphere be checked first, then going on to check something more tightly bound. Sphere checks are pretty cheap and inclusive and if you don’t get a hit there you can avoid the messy checks of other bounding types. Multiple levels of bounds could be done instead of just sphere and one other, but going crazy with numbers of levels would eat cycles needlessly. Triangle level collision would make a good third and final level I think, but would have to be done very smartly or would as stated be very slow. No problem though, we’ve tackled such issues before.

As for pixel level collision, that is not wholely a 3d world problem near as I can tell. If you model the world in 3d space and have two objects collide, you can find the point of collision in 3d space, but you’ll still have to translate that to the 2d viewing plane to determine pixel location. It’s a lot of work for accuracy you normally don’t need (especially if you have triangle accuracy) Instead of checking collision between a bullet and a wall, why not simply use ray casting from the firing position along the trajectory to determine the collision point (as we do in our Picking demo)? We could certainly add more ray intersection routines to assist in that.

On the “scene oriented” topic, my opinion for what that’s worth… I think automatic collision detection at the spatial level is interesting, if done via a delegate of some sort. A spatial would do a collision check on updateWorldData if (and only if) it had been assigned a delegate. The same delegate could be used across multiple children, if desired and programmed to handle that, etc. The delegate would have information coded in as to what to do on a collission, when to act on the collission, etc. If we went this way, the framework for using such a system could be added to jME and a simple delegate class created. It would be up to the developer at that point to extend the delegate and have it do whatever they desired. It’s not that different from what we have already, just easier to reuse and maintain, and possibily easier to integrate into other aspects such as AI and physics.

A lot of spouting off, I know, but I want to get everything off my chest before I go in for a physical today… 8-O :slight_smile:

Thats exactly what I meant by a heirarchial system.

And guess what more? I thought of that in the toilet while having a shower! :smiley:

AABB trees and OBB trees are forth coming. DP, those are what you are referring to. They simply break up geometry into trees down to a single triangle. Highly efficient and fast. Just not easy to implement.

"DarkProphet" wrote:
I thought of that in the toilet while having a shower! :D

Your toilet is in your shower?

I just hope that one day I can actually add something worthwhile to this project like the three of you. I still have a lot to learn. -- Just a quick kudos.

as you can see, my english isn’t very good, in arabic, bathroom and toilet is the same word :slight_smile:

I am yet to add something to this project :smiley: