Box.Contains(Box) Check for Coincident Boxes?

rhinocommon

#1

Hi All,

I’m attempting to implement the Box.Contains(Box) method to check for coincident boxes. The API states that this method will return:

true if the box is on the inside of or coincident with this Box.

I might be misunderstanding what exactly is meant by coincident here, but am getting a False for cases like the left one here (I did try out a bunch of higher/lower Rhino document tolerances with the same result):


180404_BoxBoxContainment_00.gh (6.0 KB)

Is this the expected behavior?

Best,

Anders


#2

Oh hang on, looks like is this coincidence that is checked:

In which case, I might move to BrepBrep or MeshMesh intersections (which also have built-in tolerances for allowing gaps and such). But will likely be substantially slower (I’m looking at cases with many boxes), maybe an existing BoxBox intersection function (with tolerance) is available somewhere. Will do some digging.


(qythium) #3

Hmm, that looks exactly how I would expect “Contains” to work - return True only if all the vertices of the inner box are within the bounds of the outer box? I think ‘coincident’ in this context just means that the inequality checking is non-strict… min(x_1) \le x_2 \le max(x_1) and so on, such that a box is considered to contain itself.

(RTrees are great for intersecting tons of boxes :slight_smile: )


#4

Which makes perfect sense, think I was overly fixated on the coincident property, and not the contain one :wink:

I should have been more specific: I’m looking at cases where boxes are not aligned and of arbitrary height (i.e. in 3D), like these bad boys:

Where RTrees wouldn’t work, I assume?

Looks like there’s a ton of stuff on box-box collisions for real-time graphics, so hopefully that might yield something clever. Will have a look at MeshMesh and MeshClash first though.


#5

To detect if two boxes collide, I think this works:

public bool BoxBoxCollide(Box A, Box B){
    foreach(Point3d p in A.GetCorners())
      if(B.Contains(p))return true;
    foreach(Point3d p in B.GetCorners())
      if(A.Contains(p))return true;
    return false;
  }

(qythium) #6

I think an RTree would still help in that case to quickly narrow the scope of candidates to test, because 3d intersections between two objects happen if and only if their axis-aligned bounding boxes intersect.

@Dani_Abalde That logic does not work for cases like this:


#7

Facepalm :see_no_evil:

  public bool BoxBoxCollide(Box A, Box B){
    MeshFace[] faces = new MeshFace[]{
      new MeshFace(0, 3, 2, 1), new MeshFace(0, 1, 5, 4),
      new MeshFace(1, 2, 6, 5), new MeshFace(2, 3, 7, 6),
      new MeshFace(3, 0, 4, 7), new MeshFace(4, 5, 6, 7)
      };
    Mesh MA = new Mesh(); 
    MA.Vertices.AddVertices(A.GetCorners());
    MA.Faces.AddFaces(faces);
    Mesh MB = new Mesh(); 
    MB.Vertices.AddVertices(B.GetCorners());
    MB.Faces.AddFaces(faces);
    return Rhino.Geometry.Intersect.Intersection.MeshMeshFast(MA, MB).Length > 0;
  }

#8

Cheers guys. I also just tested the two MeshMesh intersections methods, and am not seeing the results I was expecting, again I may be misunderstanding their design:


180404_MeshMeshIntersections_00.gh (22.9 KB)

Notably:

  1. I am not getting any intersections with MeshMeshFast in Case A (left).
  2. I am not getting any intersections with MeshMeshAccurate in Case A when I lower the tolerance.
  3. With a higher tolerance, I do get results, but they’re all over the place.
  4. MeshMeshFast work as (I) expected in Case B (right).
  5. MeshMeshAccurate returns somewhat expected results in Case B when lowering tolerance.
  6. But also returns “wacky” results like Case A with a higher tolerance.

The meshes are close to the origin, and have reasonable dimensions. But perhaps this is another one of these “meshy” things?


#9

Think I came up with a decent conjecture, covering my cases:

And the full penetration one from @qythium:

Basically:

  1. For all corners in BoxA (green): Find the closest point on BoxB (purple)
  2. For these points on BoxB: Find the closest point on BoxA (not rendered)
  3. Make a line between these points (yellow)
  4. If the length of this line is zero, the two boxes intersect (I think!)

Check if two boundingboxes intersects/collides
(qythium) #10

hmm… what if one box is entirely inside the other?
Or if only one corner is poking through a face:
image
You might cover everything by checking box.Contains(point) for all the corners, but this method is probably quite expensive due to all the ClosestPoint checks.

A bit of Googling around shows that there’s a standard algorithm called Separating Axis Theorem used for oriented bounding box (OBB) intersection checks, requiring only 15 steps to verify that two boxes do not intersect (fewer if they do, and the algorithm gets an early exit) : http://www.jkh.me/files/tutorials/Separating%20Axis%20Theorem%20for%20Oriented%20Bounding%20Boxes.pdf


#11

The algorithm catches both these cases:

That said, I’m sure there are some cases it doesn’t. Although so far I’m surprised at how robust it appears to be. Will run some more testing before implementing it, but pretty sure it passes the smell test for our current purposes. Would love to dig into all this some more if time wasn’t a concern, thanks for the link :slight_smile:


(qythium) #12

Oh I see– Box.ClosestPoint returns the closest point in the box’s volume, not its surface as I had assumed (from the way Rhino works in general). That’s useful to know :smile:
(And yes, I’d actually much rather go with your simple-to-understand method versus 30 lines of dense vector calculations where typos can easily happen)


#13

Exactly, and with the bounce back to the starting box, I think that covers most cases :see_no_evil: