Elysian Shadows

Let's say for example, we have 3 different meshes (or models) in 3D space, we needs to check if any of these three intersects with another.

There are many ways of doing it, with spheres, hit boxes, per triangle, ray casting etc.

BUT, let's say we're going to use a sphere or a hit box (per triangle is slow, rays doesn't always cut it).

The size we would create this sphere or box would be completely unknown.

What we could do, is go through each triangle and look for the smallest and largest value of each vertex, but then this will probably take much longer than handling the collision itself.

Is there some standard way of dealing with this, or any advice on how to tackle such a problem?

Thanks!

Doing world to actor collisions is going to require a lot of geometry pre-processing if the mesh is irregular. You don't want to be using render meshes for collision detection. The relative complexity of a renderable mesh is considerably moreso than that which is necessary for a collision. A collision mesh has less resolution. For physics engines such as PhysX, Bullet, and what have you, when we submit world meshes they are "cooked". This entails finding co-planar adjacent surfaces and subtracting out unnecessary complexity. It may also involve decomposing the mesh into a simpler form.

The second aspect of this involves spatial locality. "Where are we and what is here?". You NEED a spatial partition, whether its amorphic, regular, whatever. The spatial partition that you choose is going to depend on the application. What works well for culling away renderable objects may not work so well for culling away collidable objects. You will want to investigate this.

It seems like you're trying to develop your own physics engine, while the actual collisions themselves aren't a terribly difficult matter, the spatial organization and pre-processing can be quite a chore but are required for efficient collisions. The collisions themselves that you're alluding to are "Sphere to plane" collisions. Start there.

Im one to talk seeing as last time I "optimized" my collision system I broke it . Anyway... I use my own method of collision called "Scan Area Collision".
It lags incredibly, so I just put a bounding box around each one, and only check the collisions and do secondary calculations if the bounding box is hit.
I plan to do further BB optimization in the future by making "Bounding Box Regions" before detecting the more detailed "Scan Area Collision".

Hope this helps

THe Floating Brain wrote:Anyway... I use my own method of collision called "Scan Area Collision".

Hope this helps

How would that help? You said you made up your own method, gave it a random name, and provided absolutely no information on how it actually works. The broad-phase bounding box check is far from a new idea, and is implemented in some fashion by essentially every high-performance collision system.

dandymcgee wrote:

THe Floating Brain wrote:Anyway... I use my own method of collision called "Scan Area Collision".

Hope this helps

How would that help? You said you made up your own method, gave it a random name, and provided absolutely no information on how it actually works. The broad-phase bounding box check is far from a new idea, and is implemented in some fashion by essentially every high-performance collision system.

Yaaaa reading over that it was kinda hard to get the point . Basically I was trying to say "I made a collision system that lags so I put a bounding box around it and it worked better, and allowed me to do secondary calculations like rotation later".

THe Floating Brain wrote: Basically I was trying to say "I made a collision system that lags so I put a bounding box around it and it worked better, and allowed me to do secondary calculations like rotation later".

Ah, okay. Yes, as with any collision system it is wise to do a really fast rough check before bothering with a really expensive accurate check.

dandymcgee wrote:

THe Floating Brain wrote: Basically I was trying to say "I made a collision system that lags so I put a bounding box around it and it worked better, and allowed me to do secondary calculations like rotation later".

Ah, okay. Yes, as with any collision system it is wise to do a really fast rough check before bothering with a really expensive accurate check.

You got it

Sorry it's taken so long to reply to this. Life is hell.

The approach I took was to just (at initialization) compute the minimum and maximum value of each axis to create a bounding box for the mesh. It works pretty well, and if you generate one per each frame it's quite fine. (And quick).

I do find it interesting though that of all mesh file formats I've come by (Quakes Md's, 3DS, Wavefront, Collada etc) none of which pre-calculate any of this. It's not a big deal to do it yourself, but speed is always important.

Either way, Thanks for the help!

The MD3 format in Quake3, for example, is a character model. This is a third person visual model. For purposes of a first person "actor", no such resolution is necessary and is COMPLETELY overkill. First person collision models are generally treated as capsule objects. Camera "bobbing" effects are just that....effects. They have no real basis in physical precision.

The trick is in representing the collidable world itself. This is where the "baking", as mentioned before, occurs. Its critically important that spatial relationships be as fast as possible to determine in realtime such that the ray marches involved in the collision sweeps are as few as possible.