Intersection.MeshMeshFast faster method?

Rhino Developer
1

Hi,

I am checking collisions between meshes.
I do not need any intersections or geometry output just true or false.

In my case is there a faster method for collision detection than:
Rhino.Geometry.Intersect.Intersection.MeshMeshFast(Mesh a, Mesh b)

2

Hi Tom,

If there were, we’d have exposed it already. :wink:

– Dale

1 Like
3

Thanks:)

6

@Tom_Holt, you might test to see if MeshClash.Search is any faster.

http://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_Intersect_MeshClash_Search.htm

– Dale

7

The return type:

Return Value
Type:MeshClash[]
An array of clash objects.

Does this return 0 if there are not clash objects or true/false array?

8

I am wondering why meshclash produces this result.

Meshes are not intersected, but it still shows a point that is inside the mesh:

result.png1920Ă—1080 339 KB

9

it may be obvious, but a (axis aligned) bounding box intersection before the mesh intersection can speed up the process quite a lot.
In case - the proper aabb intersection here (2d, but easy to extend)

bool BoxesIntersect(BoundingBox a, BoundingBox b) {
    if (a.Max.X < b.Min.X) return false; // a is left of b
    if (a.Min.X > b.Max.X) return false; // a is right of b
    if (a.Max.Y < b.Min.Y) return false; // a is above b
    if (a.Min.Y > b.Max.Y) return false; // a is below b
    return true; // boxes overlap
}
10

Are you sure your meshes are seperated more than the distance you specified? You probably want a very, very small distance. But note that such a value still can cause clashes to happen for non-intersecting meshes…

11

Dear Atair,

This was just an example. I am dealing with non regular forms.
Or you suggesting first check bboxes and then normal collision?

12

Indeed this is a good suggestion by @atair. Checking for a boundingbox overlap first will make your isearch faster as it discards sets that are not close to eachother. However, if you know the meshes will be close to begin with it’s a pointless additional check.
-WIllem

13

bounding box intersection is meant as an early discard of intersection pairs, so yes - first bbox and then normal collision. This can speed up the process orders of magnitude, but only if you are dealing with many meshes. If it is just about two, it wont help…

Another optimisation that is often used are convex mesh collisions (e.g. in realtime physics engines). Unfortunately Rhino has them not implemented.

If you supply more information on your problem (number of meshes in question, distribution and average vertex count, maybe we can give you better advice

14

Hi @atair , @Willem, @nathanletwory I am speeding up search using rtree.

But then wondering how to speed up this collision detection below instead of using mesh fast intersection.
Any ideas would be much appreciated. I am seaching in rtee by distance of one element diagonal length:

foreach (int m in _rtreeId) {
      if (!(p == id[m].Item1 && (i - 1) == id[m].Item2 && j == id[m].Item3)) {   //if not current 

               Line[] array = Rhino.Geometry.Intersect.Intersection.MeshMeshFast(t.Geometry, manyTiles[id[m].Item1][id[m].Item2][id[m].Item3].Geometry);

                 if (array != null && array.Length > 0)   { //here I break the loop if at least one intersection is found
                        flag = false;
                        break;
                   } // if 
        }
}

I mainly working with this kind of geometry below or similar:

Untitaled.png790Ă—544 32.4 KB

15

Hi
My expirience tells me that MeshMeshFast() is fast.
I used to solve some similar problems and applied same technic to yours - mesh/mesh collision detection, my sollution is attached in cs file.
I use RTree to find all meshes whose boundingBoxes intersesct and only these meshes I check for cillision by MeshMeshFast() method. Hope that this helps.

Regards,
Radovan
MeshCollision.cs (4.6 KB)

16

Hi @dale
But would checking if the bounding boxes of these meshes collide before doing any MeshMeshFast function calls improve the performance or does this happen internally in MeshMeshFast anyways? (I mean this idea is so simple… I guess you did a lot more to improve performance.)
The question is, should I invest time in trying to optimize this or is it a waste of time?

17

As i was the one that proposed the box thing, i just ran a test with 1k to 4k objects, and 8 to 32k Vertices.
The Boundingbox test speeds it up by about the factor of 4, when used in a c# GH component, maybe more when compiled.

So the speedup much less than i suggested - the native intersection is already fast.

…using some kind of octree / KD-tree would be the next thing…

18

A factor of 4 isn’t bad at all though, I will take any speed improvement I can get!

19

in that case:

  private void RunScript(List<Mesh> mesh, ref object A)
  {

    List<BoundingBox> box = new List<BoundingBox>();
    for(int i = 0; i < mesh.Count; i++) {
      box.Add(mesh[i].GetBoundingBox(false));
    }

    for(int i = 0; i < mesh.Count; i++) {
      for(int j = 0; j < mesh.Count; j++) {
        if(i != j) {
          if(collideBoxBox(box[i], box[j])) {
            Line[] l = Rhino.Geometry.Intersect.Intersection.MeshMeshFast(mesh[i], mesh[j]);
          }
        }
      }
    }

  }

  // <Custom additional code> 
  public static bool collideBoxBox(BoundingBox a, BoundingBox b) {
    if(a.Max.X < b.Min.X) return false;
    if(a.Min.X > b.Max.X) return false;
    if(a.Max.Y < b.Min.Y) return false;
    if(a.Min.Y > b.Max.Y) return false;
    if(a.Max.Z < b.Min.Z) return false;
    if(a.Min.Z > b.Max.Z) return false;
    return true;
  }

because there is no fast code to collide two axis aligned Bounding boxed in Rhino (as far as i know)

20

Thanks! :slight_smile: