Box.Contains(Box) Check for Coincident Boxes?

AndersDeleuran · April 4, 2018, 9:22am

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

AndersDeleuran · April 4, 2018, 9:44am

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 · April 4, 2018, 10:02am

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 )

AndersDeleuran · April 4, 2018, 10:13am

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

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.

Dani_Abalde · April 4, 2018, 10:24am

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 · April 4, 2018, 10:28am

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:

Dani_Abalde · April 4, 2018, 10:31am

Facepalm

  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;
  }

AndersDeleuran · April 4, 2018, 11:45am

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:

I am not getting any intersections with MeshMeshFast in Case A (left).
I am not getting any intersections with MeshMeshAccurate in Case A when I lower the tolerance.
With a higher tolerance, I do get results, but they’re all over the place.
MeshMeshFast work as (I) expected in Case B (right).
MeshMeshAccurate returns somewhat expected results in Case B when lowering tolerance.
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?

AndersDeleuran · April 4, 2018, 1:13pm

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

And the full penetration one from @qythium:

Basically:

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

qythium · April 4, 2018, 1:35pm

hmm… what if one box is entirely inside the other?
Or if only one corner is poking through a face:

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

AndersDeleuran · April 4, 2018, 1:51pm

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

qythium · April 4, 2018, 2:19pm

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
(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)

AndersDeleuran · April 4, 2018, 2:27pm

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

Petras_Vestartas · March 3, 2021, 9:32am

Hi @AndersDeleuran ,

I was using your method for box collision, it seems very robust and lets speeding up the RTree search.
But it cannot handle the case below. Do you have any ideas how to include this one into the box collision check you developed?

BoxCollision.3dm (113.5 KB)

AndersDeleuran · March 3, 2021, 10:43am

Hmm, maybe, can you internalise the boxes in a GH file instead of breps in a Rhino file?

Petras_Vestartas · March 3, 2021, 11:42am

These are two boxes:
Boxes.gh (5.5 KB)

AndersDeleuran · March 4, 2021, 10:05am

Yes I see what you mean. I’m afraid I don’t have any immediate ideas how to improve/extend the logic I developed to catch such cases. Considering the updates to mesh intersections in Rhino 7, that might be a tree worth barking up again?

Petras_Vestartas · March 4, 2021, 10:25am

Yup this is what I am doing now, first cheking through your code then meshmeshfast

Petras1 · August 11, 2021, 2:03pm

This post is made quite long time ago, but I found stackoverflow method that does this correctly in C++, which could be easily understood in C# or Python as well. The magic math…

// define the operations to be used in our 3D vertices
struct vec3
{
    float x, y, z;
    vec3 operator- (const vec3& rhs) const { return{ x - rhs.x, y - rhs.y, z - rhs.z }; }
    float operator* (const vec3& rhs) const { return{ x * rhs.x + y * rhs.y + z * rhs.z }; } // DOT PRODUCT
    vec3 operator^ (const vec3& rhs) const { return{ y * rhs.z - z * rhs.y, z * rhs.x - x * rhs.z, x * rhs.y - y * rhs.x }; } // CROSS PRODUCT
    vec3 operator* (const float& rhs)const { return vec3{ x * rhs, y * rhs, z * rhs }; }
};

// set the relevant elements of our oriented bounding box
struct OBB
{
    vec3 Pos, AxisX, AxisY, AxisZ, Half_size;
};

// check if there's a separating plane in between the selected axes
inline bool getSeparatingPlane(const vec3& RPos, const vec3& Plane, const OBB& box1, const OBB& box2)
{
    return (fabs(RPos * Plane) >
        (fabs((box1.AxisX * box1.Half_size.x) * Plane) +
            fabs((box1.AxisY * box1.Half_size.y) * Plane) +
            fabs((box1.AxisZ * box1.Half_size.z) * Plane) +
            fabs((box2.AxisX * box2.Half_size.x) * Plane) +
            fabs((box2.AxisY * box2.Half_size.y) * Plane) +
            fabs((box2.AxisZ * box2.Half_size.z) * Plane)));
}

// test for separating planes in all 15 axes
inline bool getCollision(const OBB& box1, const OBB& box2)
{
    static vec3 RPos;
    RPos = box2.Pos - box1.Pos;

    return !(getSeparatingPlane(RPos, box1.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box2.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisX ^ box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisX ^ box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisX ^ box2.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY ^ box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY ^ box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY ^ box2.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisZ, box1, box2));
}



PINVOKE inline bool OBBCollide(
    float APosX, float APosY, float APosZ,//set the first obb's properties
    float AHalfSizeX, float AHalfSizeY, float AHalfSizeZ,//set the half size
    float AAxis0X, float AAxis0Y, float AAxis0Z,//set XAxis
    float AAxis1X, float AAxis1Y, float AAxis1Z,//set YAxis
    float AAxis2X, float AAxis2Y, float AAxis2Z,//set ZAxis

    float BPosX, float BPosY, float BPosZ,//set the first obb's properties
    float BHalfSizeX, float BHalfSizeY, float BHalfSizeZ,//set the half size
    float BAxis0X, float BAxis0Y, float BAxis0Z,//set XAxis
    float BAxis1X, float BAxis1Y, float BAxis1Z,//set YAxis
    float BAxis2X, float BAxis2Y, float BAxis2Z//set ZAxis


) {

    //Test
    // create two obbs
    OBB A, B;

    // set the first obb's properties
    A.Pos = { APosX, APosY, APosZ }; // set its center position

    // set the half size
    A.Half_size.x = AHalfSizeX;
    A.Half_size.y = AHalfSizeY;
    A.Half_size.z = AHalfSizeZ;

    // set the axes orientation
    A.AxisX = { AAxis0X, AAxis0Y, AAxis0Z };
    A.AxisY = { AAxis1X, AAxis1Y, AAxis1Z };
    A.AxisZ = { AAxis2X, AAxis2Y, AAxis2Z };

    // set the second obb's properties
    B.Pos = { BPosX, BPosY, BPosZ }; // set its center position

    // set the half size
    B.Half_size.x = BHalfSizeX;
    B.Half_size.y = BHalfSizeY;
    B.Half_size.z = BHalfSizeZ;

    // set the axes orientation
    B.AxisX = { BAxis0X, BAxis0Y, BAxis0Z };
    B.AxisY = { BAxis1X, BAxis1Y, BAxis1Z };
    B.AxisZ = { BAxis2X, BAxis2Y, BAxis2Z };

    // run the code and get the result as a message
    return getCollision(A, B);


}

Petras_Vestartas · June 8, 2023, 2:29pm

This is a conversion to C# from C++ incase some needs it, thanks to ChatGPT:


private void RunScript(Brep x, Brep y, ref object A)
  {
  
    //example with boxes
    Box box1 = Box.Unset;
    Plane xPlane = Plane.Unset;
    x.Surfaces[0].FrameAt(0, 0, out xPlane);
    x.GetBoundingBox(xPlane, out box1);
    
    Box box2 = Box.Unset;
    Plane yPlane = Plane.Unset;
    y.Surfaces[0].FrameAt(0, 0, out yPlane);
    y.GetBoundingBox(yPlane, out box2);

    A = GetCollision(box1,box2);

    //example with bounding boxes
   // A = GetCollision(x.GetBoundingBox(true), y.GetBoundingBox(true));
  }

  // <Custom additional code> 

  // define the operations to be used in our 3D vertices
  // define the operations to be used in our 3D vertices
  public struct Vec3
  {
    public float x, y, z;

    public Vec3(float x, float y, float z){
      this.x = x;
      this.y = y;
      this.z = z;
    }

    public static Vec3 operator -(Vec3 lhs, Vec3 rhs)
    {
      return new Vec3 { x = lhs.x - rhs.x, y = lhs.y - rhs.y, z = lhs.z - rhs.z };
    }

    public static float operator *(Vec3 lhs, Vec3 rhs)
    {
      return lhs.x * rhs.x + lhs.y * rhs.y + lhs.z * rhs.z;
    }

    public static Vec3 operator ^(Vec3 lhs, Vec3 rhs)
    {
      return new Vec3 { x = lhs.y * rhs.z - lhs.z * rhs.y, y = lhs.z * rhs.x - lhs.x * rhs.z, z = lhs.x * rhs.y - lhs.y * rhs.x };
    }

    public static Vec3 operator *(Vec3 lhs, float rhs)
    {
      return new Vec3 { x = lhs.x * rhs, y = lhs.y * rhs, z = lhs.z * rhs };
    }
  }

  // set the relevant elements of our oriented bounding box
  public struct OBB
  {
    public Vec3 Pos, AxisX, AxisY, AxisZ, Half_size;

    public OBB(BoundingBox bbox)
    {
      // Calculate the center position of the bounding box
      Pos = new Vec3((float) (bbox.Min.X + bbox.Max.X) / 2f,
        (float) (bbox.Min.Y + bbox.Max.Y) / 2f,
        (float) (bbox.Min.Z + bbox.Max.Z) / 2f);

      // Calculate the size of the bounding box in each dimension
      float sizeX = (float) (bbox.Max.X - bbox.Min.X) / 2f;
      float sizeY = (float) (bbox.Max.Y - bbox.Min.Y) / 2f;
      float sizeZ = (float) (bbox.Max.Z - bbox.Min.Z) / 2f;

      // Set the axis vectors
      AxisX = new Vec3(1f, 0f, 0f);
      AxisY = new Vec3(0f, 1f, 0f);
      AxisZ = new Vec3(0f, 0f, 1f);

      // Set the half size of the bounding box
      Half_size = new Vec3(sizeX, sizeY, sizeZ);
    }

    public OBB(Box box)
    {
     

      // Calculate the center position of the box
      var center_points = box.PointAt(0.5, 0.5, 0.5);
      Pos = new Vec3((float) (center_points.X),
        (float) (center_points.Y),
        (float) (center_points.Z));

      // Calculate the axis vectors
      AxisX = new Vec3((float) (box.Plane.XAxis.X),
        (float) (box.Plane.XAxis.Y),
        (float) (box.Plane.XAxis.Z));
      AxisY = new Vec3((float) (box.Plane.YAxis.X),
        (float) (box.Plane.YAxis.Y),
        (float) (box.Plane.YAxis.Z));
      AxisZ = new Vec3((float) (box.Plane.ZAxis.X),
        (float) (box.Plane.ZAxis.Y),
        (float) (box.Plane.ZAxis.Z));

      // Set the half size of the box
      Half_size = new Vec3((float) (box.X.Length) / 2f,
        (float) (box.Y.Length) / 2f,
        (float) (box.Z.Length) / 2f);
    }
  }

  // check if there's a separating plane in between the selected axes
  public static bool GetSeparatingPlane(Vec3 RPos, Vec3 Plane, OBB box1, OBB box2)
  {
    return Math.Abs(RPos * Plane) >
      (Math.Abs((box1.AxisX * box1.Half_size.x) * Plane) +
      Math.Abs((box1.AxisY * box1.Half_size.y) * Plane) +
      Math.Abs((box1.AxisZ * box1.Half_size.z) * Plane) +
      Math.Abs((box2.AxisX * box2.Half_size.x) * Plane) +
      Math.Abs((box2.AxisY * box2.Half_size.y) * Plane) +
      Math.Abs((box2.AxisZ * box2.Half_size.z) * Plane));
  }

  // test for separating planes in all 15 axes
  public static int GetCollision(BoundingBox _box1, BoundingBox _box2) // -1_outside_0_intersected_1_inside
  {
    OBB box1 = new OBB(_box1);
    OBB box2 = new OBB(_box2);
    
    if(_box1.Contains(_box2))
      return 1;
    
    Vec3 RPos;
    RPos = box2.Pos - box1.Pos;

    bool result =  !(GetSeparatingPlane(RPos, box1.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box2.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisZ, box1, box2));
    
    if(result)
      return 0;
    else
      return -1;
  }
  
  public static int GetCollision(Box _box1, Box _box2) // -1_outside_0_intersected_1_inside
  {
    OBB box1 = new OBB(_box1);
    OBB box2 = new OBB(_box2);
    
 
     if(_box1.Contains(_box2))
        return 1;
  

    Vec3 RPos;
    RPos = box2.Pos - box1.Pos;

    bool result =  !(GetSeparatingPlane(RPos, box1.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box2.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisX ^ box2.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisY ^ box2.AxisZ, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisX, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisY, box1, box2) ||
      GetSeparatingPlane(RPos, box1.AxisZ ^ box2.AxisZ, box1, box2));
    
    if(result)
      return 0;
    else
      return -1;
  }