Irrlicht Collision

[en51nm]

Hello,
Well... I've spent the past couple of weeks trying to get a solution to my collision detection problem and I've attemped to integrate Newton, Bullet and ODE to irrlicht and have failed on all three occasions. The main reason for going to these physics engines is because I was after mesh v mesh collision.

Although that is an eventual aim - I'm really struggling to get just a simple working solution at the moment, so I'm thinking of going back to just using irrlicht on it's own and using the built in collision detection it provides.

What is the most complex collision technique (shape) offered by irrlicht and can I use this to simply return a (true or false) bool as to whether or not any of my scene nodes have collided?

Thanks in advance.

[CuteAlien]

Axis aligned box (aabbox) vs aabbox and aabbox vs lines collisions do that. Also sphere-sphere collisions are trivial to do (you just have to get the distances). For all those it's easy to check if something collides or not. For boxes which are no axis aligned it's easiest to invert the rotation first and then do a aabbox test.

By the way - do you need concave or convex meshes? If you can reduce it to convex meshes it's probably a lot easier (then you can for example clip all polygons against the planes of the polygons of the other mesh and if anything is left you would be guaranteed they collide). For concave meshes - no idea really, I guess first step would be to figure out how to create convex sub-meshes for those.

[en51nm]

I could get away with concave meshes - but irrlicht won't do mesh v mesh collision even for convex meshes right?

[CuteAlien]

No, but there's not that much missing for coding that. Mainly you would need clipping of triangles against planes. Which can be be reduced to clipping the triangle-edges against planes. And we have linesegment plane collisions in Irrlicht. So I think it would basically be something like:
First create triangle-selectors for all involved meshes. From the triangle-selectors you can get the polygon-triangles of each mesh. For collision you would have to clip the edges of each triangle of one mesh against the planes of each triangle of the other mesh. If any line ever intersect a plane you have a collision. Or if any edge of the line (aka one of the triangle vertices) is on the inside of all planes of the other mesh then you have a collision.

No guarentee that I didn't miss something (so think about it before coding it), although I think it should. And note that this will only work for closed meshes which are convex.

And cetainly there are early outs to improve speed - they never can collide if the spheres or boundingboxes around the involved meshes don't collide already. So those checks should always come first.

[Mel]

I could get away with concave meshes - but irrlicht won't do mesh v mesh collision even for convex meshes right?

Concave vs concave is the MOST complex colliding system you will ever find, because it means to colide any mesh with any other mesh, and that is frankly, the most complex scenario for ANY collision system, physics based or not.

Try to simplify your problem. Try to decompose your objetcts into compositions of convex primitives, if posible, can't you use a simpler approach? Static meshes can be concave more easily than moving objects, or you can simply perform raycasts in the proper places, if they meet your needs. Triangle selectors also can be accelerated using octrees in Irrlicht, and they behave better if they static stages. But if performance is in your objectives, you definately should simplify as much as posible your problem.

[en51nm]

Sorry, I meant I can simplify the problem to convex meshes. I'll have a think about the method you mentioned cutealien, it sounds promising. Has anyone done something like this before, what's my best point of reference for getting to grips with triangle selectors, are there some tutorials for them? Also, is it possible to draw a node's aabb yo help with debugging?

[CuteAlien]

There's not much to tell about triangle-selectors. You create them with createTriangleSelector from the scenemanager and then you have functions to access triangles: http://irrlicht.sourceforge.net/docu/cl ... ector.html

And to show boundingboxes for a scenenode you can call node->setDebugDataVisible(irr::scene::EDS_BBOX).
You can also set other debug-flags, see here: http://irrlicht.sourceforge.net/docu/na ... 168fc32dbe

[en51nm]

One other quick thought. Could you create an aabb for each polygon? And then just check collision from aabb to aabb?

[en51nm]

Also, thanks for all the help with my problem if I get the code up and running i'll be sure to post it for anyone else who might need to do something similar

[CuteAlien]

Sorry, just noticed I have an error in my description above. Checking polygon-edges against triangle-planes is not enough. You have have to check additionally if the collision for that is inside the triangle you're checking (Irrlicht has a function for that as well in the triangle3d).

You can create a boundingbox for each polygon (just intialize the boundingbox with one corner and then add the other 2), but that won't give you mesh-vs-mesh collision. You don't just have to check when the polygons hit each other but you must also figure out if one mesh is already inside the other mesh. To find that out you need a way to tell if a point is inside the body of a mesh - that's the part where you can check if it's on the inside-side of all planes in a convex mesh, but which is very hard to find out for a concave mesh.

[en51nm]

Right, so my code would look something like this:
- Update node positions
- check for aabb collisions
- if TRUE:
- for each collided node pair
- for each pollygon of node1 create a plane
- for each pollygon of node2 check linesegment v plane collision
- if TRUE: check if collision point lies inside all other planes
- if TRUE: return TRUE (collision!!)

Doesn't sound too hard to implement - not sure how I would incorporate an octree to speed this up, unless you could use it on the initial aabb v aabb test?

[Mel]

AABB collisions could be made inside a hierarchical bounding box system, or an octree. or a bucket system or something so you don't have to test each of the AABBs against all the other AABBs. Or at least, reduce the scale of the problem to a local area

The stages can also be converted into BSP's. For rendering, this is outdated, but for physics is still a good choice because, even with a very large amount of triangles, there is always a good posibility that you cull half of the mesh AND BSP's store the planes of the triangles, so you don't have to perform the plane conversion Besides, you also cull most of the triangles because the BSP partitioning, so the number of tests is reduced

For the task you've proposed, the hardest part is to remove redundant/useless tests.

[en51nm]

I thought I'd try one last attempt at getting Newton integrated and use that for detecting simple convex mesh collisions, but I've got a problem...

As you can see from the image I should clearly be getting a collision, but nothing is detected:



I'm using the code from this tutorial to produce my collision object, object is a standard collision object, one sphere moves using key board input and is created by using "NewtonCreateConvexHull", the other is stactic and so uses an octree for speed and is created using "NewtonTreeCollisionEndBuild" after adding all of the faces with "NewtonTreeCollisionAddFace".

The collision detection is completed simply by calling "NewtonCollisionCollide".

The problem is that that the nHits = 0 despite there clearly being a collision...

I'm using Irrlicht 1.7.3 and Newton 1.53

Any ideas what I'm doing wrong? I've tried changing both the meshes to convex hull types. Could it be to do with the scale of my world?

[CuteAlien]

No code would be more like:
-Update node positions
- check for aabb collisions (although I would use sphere before aabb collision as it's cheaper and easier)
- if TRUE:
- for each collided node pair
- for each polygon of node1 create a plane
- for each polygon of node2 check for each edge the collision of a linesegment vs all planes of node 1
- when colliding check if that collisionpoint is inside the node 1 triangle which created the corresponding plane.
- if so you have a collision.

If all those tests failed you still have to find out if node1 is inside node2 or node2 inside node1.
- Check all vertices of node1 against all planes of node2, as soon as one is outside any of the planes you know node1 is not inside node2. If all are inside you have a collision.
- Check all vertices of node2 against all planes of node1, as soon as one is outside any of the planes you know node2 is not inside node1. If all are inside you have a collision.

[en51nm]

Okay, I'll see how I go with that. It's quite frustrating that Newton wont work, it seems pointless coding the same things that other people have already spent time coding...