next »

[akademiks]

Hi guys,

I implemented a precise (triangle vs triangle tests) collision detection system for my 3D app. I did not implemented any broad phase detection so for now the performance is really bad since when i test object A, its tested for collisions against all object in the scene.

I thought about implementing an octree to partition the space so i can only evaluate objects near object A but due to the nature of the app, i don't think its a good fit because its a CAD application use to build small structures like table, chair or a patio. Objects in the scene would be wood pieces like 2x4x12 and stuff like that so usually all objects are really close to each other. There are good chances that a lot of objects would occupy all the first children of the octree root which is not what we want.

Most of the objects are rectangle shapes of type inchXinchXinch. I guess that i could implement a broad phase using OBB? comparing OBB of 2 rectangles should still be more efficient than comparing each triangles of 2 rectangles...

Any better idea for space partitionning or broad phase approach?
Thx.

[Netsu]

Besides octrees and various bounding geometry methods, spatial hashing is also pretty popular, have you considered that? But it would require that your objects have a reasonable upper boundary on their size.

[epcc]

Usually you don't need triangle-triangle tests. As most of your objects are wooden planks, you can just do OBB vs OBB test and get as good results as from triangle-triangle tests.

Just to check if two planks are colliding means doing 12^2 triangle-triangle checks. With SAT theorem, you need to check 6 planes maximum and usually it stops early if there is no intersection.

For broadphase, sweep and prune is quite efficient and easy to implement.

Only use triangle checks when the planks are colliding with level geometry, and even then there might be something more efficient (OOB vs triangle?, idk)

PS: and writing your own physics is useful only if you want to learn or if you want to do something really weird. Otherwise just try a physics engine. If you just want to write your own game, I'd recommend Bullet. It's free and probably a lot faster and mature than yours.

[akademiks]

Thx for the advices guys, I will investigate the space hashing and pruning stuff

[Fallsburg]

Have you tried the simplest option yet? Straight up distance squared vs radii tests, doing a triangular check?

Something like:

Code:

for i = 1:number of objects-1
   for j = i+1:number of objects
       radii = obj[i].radius + obj[j].radius
       distSq = distanceSquared(obj[i], obj[j])
       if (distSq < radii*radii)
         // do fine collision detection
       end
    end
end

Depending on how many objects you are doing/how expensive the fine collision detection is, that might be all you need to see an improvement.

[akademiks]

That solution would be a good fit in most games but in my app an a lot of objects can have one of their x,y,z component size almost equals to the world/scene bounding box so your algo will end up evaluating all objects in the scene. Thats why i need a more customized solution, this is due to the nature of the app I am working on. An example of a scene would be a 12x12 patio, where each planks making the floor defines the max value of the scene bounding box...

I implemented the octree and a search fonction : octreeRoot.getObjectsNear(myObj)
My problem is how to classify each point in the octree, the pseudo code and implementations I found on the Web just treat objects as points,
so its either in the current evaluated octree node or not...but in reality my objects has 8 vertices and its size might be greater than the lowest possible octree cube size. I am classifying all vertices of the objects in an octree node but thats not correct since if the shape is a rectangle then only the octree nodes near the vertices will contains the actual object reference, not the nodes near the middle of the rectangle shape...

So i guess now i have to create an oriented bounding box for my object and test if it intersects with the current evaluated node bounding box...I will have to investigate the OBB, don't really know how to implement but i already have the bounding box and the rotation mat

[yesfish]

If an object spans two or more octree nodes, then just put a reference to them in every node they overlap. Unless you can/want to split the objects into parts (I think BSP does that?), which isn't worth the effort IMO.

Anyway, about using octrees for broad phase: It's slow. Octrees are a structure that is very efficient to search but slow to update, especially every frame, is very slow. That's why realtime raytracing is so difficult. Having an octree for testing collisions between thousands of static polygons is a fine way to go about things, you only need to create the octree once for each mesh, then transform whatever coordinates you work with! Fast!

But for dynamic objects (or animated meshes), octree won't do much for you, infact the time it takes to test which nodes it's in, you could have used that time to broadphase it with the rest of the scene! Fallsburg's solution is the best I think, the sphere test. It's fast and simple.


There are other things you can do such as only testing objects you know have moved for example. If that's still not fast enough then consider implementing a collision engine such as bullet or physx. Otherwise you'll only be reinventing a really complex and exacting wheel.

[akademiks]

Well, there is only one objects that is moving at a given frame so i have to update the octree for that object only each frame it moves. I think this is acceptable for my current implementation. I am currently adding the oriented bounding box test to be able to properly classify each octree nodes that are touching my scene objects.

[bateleur]

Just to check if two planks are colliding means doing 12^2 triangle-triangle checks. With SAT theorem, you need to check 6 planes maximum and usually it stops early if there is no intersection.

This is the second time I've seen someone say this...

...am I being really dim, or is it in fact not true?

Consider this scenario: Take two cubes and place them such that they are not quite overlapping with the closest points at the midpoints of two edges such that the edges in question are perpendicular and a line drawn between the midpoints of the two cubes passes through the closest points.

It seems to me that none of the six face planes is a separating axis here. I think 3D SAT also requires that the cross products of pairs of edges be tested.

If I'm horribly confused then A) I apologise - and B) Please could someone correct me, because I'm actually using this stuff!

[Triplefox]

SAT doesn't specify a face plane to be a separating axis, it only says that such an axis exists. From that, we've derived ad-hoc methods of getting one; it's straightforward to find one in convex sets via naive "test all normals, process of elimination" algorithms, which is the underlying reason why it's relevant to game collision.

If the collision bounds remain axis-aligned, of course, it will always be a face plane. But that's the happy case - hence the popularity of making an AABB/circle/sphere just for the broadphase.

[ubik]

I'd advise implementing a number of different collision detection algorithms.  Then, try all of them on your scene to see which one runs fastest-- should only take a few frames.  From then on, run the fastest one.