Spatial search AABB boxes

[petrasvestartas]

Issue Details

I am searching for a spatial search method for 3d bounding boxes instead of points.

Describe your issue. Please be specific (compilation error, runtime error, unexpected behavior, wrong results, etc.). I would like to check collision between series of axis aligned bounding boxes, often defined by 2 points min and max. Is there a method in CGAL that can do this?

Environment

Windows

[sloriot]

This package should do what you want: https://doc.cgal.org/latest/Box_intersection_d/

[petrasvestartas]

Thank you.

Question 1: Do you know if this search is Faster than RTree or other spatial searches? It would super nice to have in CGAL RTree following this implementation which appears to be completely free and unrestricted considering license, this is the C++ source code: https://pointclouds.org/documentation/opennurbs__rtree_8h_source.html https://superliminal.com/sources/#C_Code

Question 2: And if it is possible to check oriented bounding boxes (OBB) too? Or it is better first to search for AABB and then do a second check for OBB

[petrasvestartas]

Dear @sloriot,

I started learning from CGAL documentation about this package. I have hard time understanding how to set up 3D bounding box search to call the callback. I do not know how to run this line in the code below:

 CGAL::box_self_intersection_d(AABBs.begin(), AABBs.end(),callback);

I am trying to learn how to perform collision check between all boxes to obtain adjacency list that does not have duplicates meaning, BoxA and BoxB is the same pair as BoxB and BoxA

#include <iostream>
#include <fstream>

#include <CGAL/box_intersection_d.h>
#include <CGAL/Bbox_3.h>

std::ofstream myfile;

void callback(const Box& a, const Box& b) {

    myfile.open("C:\\Users\\petra\\AppData\\Roaming\\McNeel\\Rhinoceros\\packages\\7.0\\ngon\\3.1.0\\BoxInclusion.txt");
    myfile << "box " << a.id() << " intersects box " << b.id() << "\n";
    myfile.close();
}

typedef CGAL::Box_intersection_d::Box_d<double, 3> Box;
typedef CGAL::Bbox_3                               BBox;
int UnsafeCGALCollisionDetectionOBB(

    //input
    double* PositionsXYZ,
    double* XAxesXYZ,
    double* YAxesXYZ,
    double* HalfSizeXYZ,
    size_t numberOfBoxes,

    //output
    int*& pairs, int& numberOfPairs) {

    //////////////////////////////////////////////////////////////////////////////
    // Convert Parameters to ON_Box
    //////////////////////////////////////////////////////////////////////////////
    std::vector<Box> AABBs(numberOfBoxes);

    for (int i = 0; i < numberOfBoxes; i++) {

        //Create OBB
        ON_Box box;
        ON_Point position(PositionsXYZ[i * 3], PositionsXYZ[i * 3 + 1], PositionsXYZ[i * 3 + 2]);
        ON_Point xAxis(XAxesXYZ[i * 3], XAxesXYZ[i * 3 + 1], XAxesXYZ[i * 3 + 2]);
        ON_Point yAxis(YAxesXYZ[i * 3], YAxesXYZ[i * 3 + 1], YAxesXYZ[i * 3 + 2]);
        box.plane = ON_Plane(position, xAxis, yAxis);
        box.dx = ON_Interval(-HalfSizeXYZ[i * 3], HalfSizeXYZ[i * 3]);
        box.dy = ON_Interval(-HalfSizeXYZ[i * 3 + 1], HalfSizeXYZ[i * 3 + 1]);
        box.dz = ON_Interval(-HalfSizeXYZ[i * 3 + 2], HalfSizeXYZ[i * 3 + 2]);

        //Get AABB
        ON_BoundingBox bbox = box.BoundingBox();    
        AABBs[i] = BBox(bbox.Min().x, bbox.Min().y, bbox.Min().z, bbox.Max().x, bbox.Max().y, bbox.Max().z);
    }

    //////////////////////////////////////////////////////////////////////////////
    // Search Closest Boxes | Skip duplicates pairs | Perform callback with OBB
    //////////////////////////////////////////////////////////////////////////////

    CGAL::box_self_intersection_d(AABBs.begin(), AABBs.end(),callback);

}