I’m trying to accomplish precise mesh intersection detection.
I’m working on a modeling tool where the user can drag and drop objects, and I would like to detect intersections between meshes on demand (real-time is not a must, just a nice-to-have).
To showcase the problem I’m trying to solve, I created this playground:
Please note that while I am using torus knots for this example, in the application I’m using imported meshes with complex real-life-object shapes and textures .
In the playground you can find 4 shapes:
Shapes A & B: 2 torus knots where the bounding boxes intersect but the knots themselves do not.
Shapes C & D: 2 torus knots where the knots themselves intersect.
I’m looking for the most performant way to detect intersections, such that:
It correctly detects that knots A & B are not intersecting
It correctly detects that knots C & D are intersecting
Based on my research, I considered the following approaches:
Using mesh.IntersectsMesh(otherMesh) : this only does Oriented Bounding Box intersection at best, which is not enough for my purposes.
Using CSG : while I got this working with simple shapes like spheres, it seems to be very taxing on performance. Running it on 2 torus knots took more than 10 minutes, so I don’t think it’s viable for my purposes.
I noticed csg.intersect(otherCsg) calculates the geometry of the intersection. Is there a more performant algorithm that only detects intersections (i.e. returns a boolean that is true if they intersect)?
Using a physics engine : I haven’t looked too deeply into this option as I would like to avoid it if possible, since the application doesn’t need body dynamics, gravity, bouncing, etc.
Developing a trimesh collision detection can be a difficult task for both performance and result quality.
AFAIK, you’ll need a preprocessing pass on your mesh to get an acceleration structure (octree, bsp, bvh,…). This can take some computation time depending on you mesh complexity.
The idea behind that acceleration is to limit the number of triangle/triangle collision test. Without acceleration, you end up having O(n2) complexity. You test every triangle from mesh1 with every triangle from mesh2.
Depending on your input mesh and quality of result, you can go with a simpler solution and stop at any step: A OBB interesction test -> a convex hull test -> triangle/triangle tests. The principe is always to do quick broad tests and then get more precise result with more complex algorithm.
I took a quick look at what is available with ammojs/bullet physics.
btTriangleMesh only works for static mesh. Impacts points and collisions can be computed between a static mesh and another shape (sphere, box, compound of shapes,…) but not between 2 static meshes.
See comment here : bullet3/btBvhTriangleMeshShape.h at master · bulletphysics/bullet3 · GitHub
Alternatively, you can take a look at the GImpact library and code your own.
To sum up: Coding you own triangle/triangle mesh collision detection is a daunting task. If you don’t want exact solution, it is way simpler as you can use other algorithm (convex hull). It’s possible to use a physic engine only for collision detection. You can take a look at GImpact as it’s supported by ammojs but it will need some work for exposing its api. Maybe there are other collision detection libraries. If they are C/C++, it’s not that difficult to transpile to js/wasm
I would like to try the triangle/triangle tests and see how it performs on some of my meshes.
Do you have any advice on how to iterate through the triangles of a mesh?
I’ve been playing with facet and vertex data for a while with no success: https://playground.babylonjs.com/#DC5ULC#1
While it lets me iterate through all the vertices, I haven’t been able to figure out how to group them as triangles.
var indices = mesh.getIndices();
var positions = mesh.getVerticesData(BABYLON.VertexBuffer.PositionKind);
var triangles = [];
for (var i = 0; i < indices.length; i+=3) {
var index1 = indices[i];
var index2 = indices[i+1];
var index3 = indices[i+2];
var triangle = [
new BABYLON.Vector3(positions[index1*3],positions[index1*3+1],positions[index1*3+2]),
new BABYLON.Vector3(positions[index2*3],positions[index2*3+1],positions[index2*3+2]),
new BABYLON.Vector3(positions[index3*3],positions[index3*3+1],positions[index3*3+2])
]
triangles.push(triangle);
}
And if your mesh has in any way changed position away from 0,0,0 or rotated, scaled etc. you’ll have to bake the positions of the vertices as well:
mesh.bakeCurrentTransformIntoVertices();
Now for the rest, I would strongly suggest that you use a convex mesh vs. triangle mesh, as it yields both better performance and results(at least if you plan on using it for collision detection). I’m sure that whatever you want to achieve, there must be a better approach.
If you really want to do triangle vs. triangle intersection, you should use some kind of spatial partitioning as mentioned already. Then use the combined overlaps of the bounding boxes as an AABB to traverse the two bounding volumes, the resulting two lists of triangles should then be checked against each other using triangle-triangle intersection tests.
Here’s the BVH I use for static meshes: BVH · GitHub
If your models move around,a dynamic BVH with reinsertion or tree-rotation won’t really cut it, so you’ll have to recreate the BVH every time your models move/rotate. I have done this for simple models without big performance drops
I got it working with triangle checks (limiting the set of triangles to the ones intersecting the AABB overlap).
Performance seems pretty decent for on-demand purposes, will upgrade to OBB checks later if necessary.
Thank you. The original codes posted here were perfectly for me taking 15-40 ms for the tests on my very low powered little PC. For my application this is perfectly adequate.
I did not have to making any of the modifications suggested by June_Wu so happy days.
