C++ ON_RTree Example

Rhino Developer
1

Hi,

Is there a simple ON_RTree example for bounding boxes?
I would like to know how search is performed because I cannot find any sample files starting from this:

  //////////////////////////////////////////////////////////////////////////////
    //create the R-tree from the input points.
    //////////////////////////////////////////////////////////////////////////////
    ON_RTree tree;

    //////////////////////////////////////////////////////////////////////////////
    // Convert Parameters to ON_Box
    //////////////////////////////////////////////////////////////////////////////
    ON_SimpleArray<ON_Box> boxes(numberOfBoxes);

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

        //Get AABB
        ON_BoundingBox bbox = box.BoundingBox();
        tree.Insert(bbox.Min(), bbox.Max(), i);
    }

//Stuck already here
   tree.Search()
2

Maybe here

3

Thank you, this helps me to get on track.
For a simple case of a list of boxes, do I make the following lines correctly?
Is there a way to skip visited closest bounding boxes to avoid duplicates?
It is a bit hard to find simple example files, due to my knowledge of C++


PINVOKE int UnsafeCollisionDetectionOBB(
    //input
    double* PositionsXYZ,
    double* XAxesXYZ,
    double* YAxesXYZ,
    double* HalfSizeXYZ,
    size_t numberOfBoxes,

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

    //////////////////////////////////////////////////////////////////////////////
    //create the R-tree from the input points.
    //////////////////////////////////////////////////////////////////////////////
    ON_RTree tree;

    //////////////////////////////////////////////////////////////////////////////
    // Convert Parameters to ON_Box
    //////////////////////////////////////////////////////////////////////////////
    ON_SimpleArray<ON_Box> OBB(numberOfBoxes);
    ON_SimpleArray<ON_BoundingBox> AABB(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]);
        OBB[i] = box;

        //Get AABB
        ON_BoundingBox bbox = box.BoundingBox();
        tree.Insert(bbox.Min(), bbox.Max(), i);
        AABB[i] = bbox;
    }

    //////////////////////////////////////////////////////////////////////////////
    // Search Closest Boxes | Skip duplicates pairs A-B == B-A | Perform callback with OBB
    //////////////////////////////////////////////////////////////////////////////
    for (int i = 0; i < numberOfBoxes; i++) {
        ON_SimpleArray<int> neighbours;
        
        tree.Search(AABB[i].Min(), AABB[i].Min(), neighbours);

    }
4

Since you’re doing Pinvoke here, maybe you could just use the C# version?

I haven’t used the R-tree myself, so not sure I can help with any questions regarding functionality. Maybe @dale can?

5

I would like to do some additional geometry checks in the callback but I have no idea how to do this in OpenNurbs.

6

Hi @Petras_Vestartas,

Can you give me a better idea what you are trying to do and why?

– Dale

7

Bigger goal: to transfer my C# timber joinery generation project to OpenNurbs, but this will take time and learning. Right now I am trying to transfer code function by function. I already using some c++ libraries, therefore the final goal is Rhino C++ plugin since I see much better performance, rather than Pinvoking each time.

For this specific issue of RTree these are steps I am trying to do:

There are 4 steps (but I need only one - RTree in C++) and I gradually want to search from the fastest to the slowest collision detection.

Input : Planar 3d polygons

  1. I compute both OBB and AABB
  2. Since RTree cannot use OBB, I would like to search an AABB RTree, which is where I am stuck with now. Where pair A and B is the same B and A. For this in C# I used HashSet, but filling hashset can be quite slow.
  3. I perform OBB intersection method that I already have
  4. I perform more detailed intersection check with polygons.
8

Not sure this is exactly what you are asking about, but here’s what I use to avoid duplicate matching with RTree

var rTree = RTree.CreateFromPointArray(pts);
    var indices = new List<int>[pts.Count];
    var lines = new List<Line>();
    for(int i = 0;i < pts.Count;i++)
    {
      rTree.Search(new Sphere(pts[i], range), (sender, args) =>
        {
        if (args.Id > i) //this avoids duplicates
        {
          lines.Add(new Line(pts[i], pts[args.Id]));
        }
        });
      };
    A = lines;

rtree_dups.gh (4.1 KB)

1 Like
9

Thanks Daniel for the help.

I want to do exactly the same with bounding boxes using C++ and OpenNurbs.

Is the following code equivalent ?

    for (int i = 0; i < numberOfBoxes; i++) {
        ON_SimpleArray<int> neighbours;
        
        tree.Search(AABB[i].Min(), AABB[i].Min(), neighbours);

        for (int j = 0; j < neighbours.Count(); j++) {
            if (neighbours[j] > i) {

            }

        }

    }
10

I think the code below illustrates what you want.

void AddBoxWithName(ON_BoundingBox bb, ON_wString name, CRhinoDoc& doc)
{
  ON_3dPoint corners[8];
  ON_3dPoint brepCorners[8];
  ON_Box boxI(bb);
  boxI.GetCorners(corners);
  brepCorners[0] = corners[0];
  brepCorners[1] = corners[1];
  brepCorners[2] = corners[5];
  brepCorners[3] = corners[4];
  brepCorners[4] = corners[2];
  brepCorners[5] = corners[3];
  brepCorners[6] = corners[7];
  brepCorners[7] = corners[6];

  ON_Brep* pBrep = ON_BrepBox(brepCorners);

  CRhinoBrepObject* pObject = new CRhinoBrepObject();
  ON_3dmObjectAttributes newAttributes;
  newAttributes.SetName(name, true);
  pObject->ModifyAttributes(newAttributes);
  pObject->SetBrep(pBrep);
  doc.AddObject(pObject);
}

CRhinoCommand::result MyPlugIn::RunCommand( const CRhinoCommandContext& context )
{
  ON_RTree tree;

  CRhinoGetObject go;
  go.SetCommandPrompt(L"Select curves");
  go.AcceptNothing(false);
  go.SetGeometryFilter(CRhinoGetObject::curve_object);
  CRhinoGet::result res;
  res = go.GetObjects(1, 0);

  if (res == CRhinoGet::object)
  {
    // create array of curves, bounding boxes and build the RTree
    ON_CurveArray crvs;
    ON_SimpleArray<ON_BoundingBox> bbs;
    ON_RTree tree;
    for(int i = 0; i < go.ObjectCount(); ++i)
    {
      auto obj = go.Object(i);
      const ON_Curve* crv = obj.Curve();
      crvs.Append(crv->DuplicateCurve());
      ON_BoundingBox bb(ON_BoundingBox::EmptyBoundingBox);
      crv->GetTightBoundingBox(bb);
      bbs.Append(bb);
      tree.Insert(bb.Min(), bb.Max(), i);
    }

    // search all the bounding boxes
    for(int i = 0; i < bbs.Count(); ++i)
    {
      const ON_BoundingBox& bb = bbs[i];
      ON_SimpleArray<int> neighbors;
      if (tree.Search(bb.Min(), bb.Max(), neighbors))
      {
        ON_wString name;
        name.Format(L"%d box", i);
        AddBoxWithName(bbs[i], name, context.m_doc);

        for(int j = 0; j < neighbors.Count(); ++j)
        {
          if (i != neighbors[j]) // avoid duplicates
          {
            ON_wString overlapName;
            overlapName.Format(L"%d overlap %d", i, neighbors[j]);
            AddBoxWithName(bbs[neighbors[j]], overlapName, context.m_doc);            
          }
        }

        // return here to only show the overlap with the first bounding box.
        //context.m_doc.Redraw();
        //return success;
      }
    }
  }

  context.m_doc.Redraw();
  return success;
}
1 Like
11

Thank you very much:)

It is really great to have this solution.

12

And is it correct that if I change this line to
if (i > neighbors[j])
Then I will always have unique pairs of elements considering 0-1 is the same as 1-0 ?

13

I suppose so, yes.

1 Like
14

When RTree searches through elements I have to input BoundingBox min max points.
tree.Search(AABB[i].Min(), AABB[i].Max(), neighbours);

Is there any way to iterate by id or somehow retrieve bounding boxes from a tree?

Pseudo code:
tree.Search(tree[i].Min(), tree[i].Max(), neighbours)

Or actually it is not possible? Once bounding boxes are inserted in the tree they are actually gone because Rtree is constructed from individual points only?

15

The R-tree has branches and leafs, each of which contains a bounding box. Maybe you can iterate the leafs, they should contain the bounding box and id, but I’m not sure how to do this. Check the docs for ON_RTreeNode and ON_RTreeBranch.

1 Like
16

Thanks I ll give it a try