RTree Bounding Box Search

Grasshopper Developer
1

Hi guys,

I am doing some tests, were I am trimming a large point collection with a given closed mesh. Basically retrieving only those points which are inside.

Foremost, I want to try to use RTree to only get the points which are inside the mesh’s bounding box, to then test that reduced search space for containment.

The RTree method I am trying to use is this one

The pseudo code which I have in mind is:

 Construct RTree from points

foreach point in points:

if point is inside bounding box:
   add point to newList

return newList

After I have this new List, it would be the input to:

/// <summary>
  /// Tests weather a points is inside a closed mesh
  /// </summary>
  /// <param name="mesh"></param>
  /// <param name="ptsRTree"></param>
  /// <returns></returns>
  public void ContainmentB(Mesh mesh, List<Point3d> ptsRTree)
  {

    for (int i = 0; i < ptsRTree.Count; i++)
    {
      Point3d pointOnMesh;
      Vector3d normalAtPoint;
      int a = mesh.ClosestPoint(ptsRTree[i], out pointOnMesh, out normalAtPoint, 0);

      if(a > -1)
      {

        double dotProduct = normalAtPoint * (pointOnMesh - ptsRTree[i]);

        // if pt is inside
        if(dotProduct > 0)
        {
          culled.Add(ptsRTree[i]);
        }
      }
    }


  }

Would the pseudo code for the RTree search seem reasonable?

currently I have this:

  public void ContainmentRTree(Mesh mesh)
  {

    RTree rTree = RTree.CreateFromPointArray(pts);

    
    foreach (Point3d p in pts)
    {
      List<Point3d> inBox = new List<Point3d>();

      EventHandler<RTreeEventArgs> rTreeCallback =
        (object sender, RTreeEventArgs args) =>
        {
        inBox.Add(pts[args.Id]);
        };


      if(rTree.Search(bBox, rTreeCallback))
      {

        ContainmentB(mesh, inBox);
      }

    }

  }

But I know its totally wrong for the following reasons:

  1. List<Point3d> inBox = new List<Point3d>();
    Should be out of the loop.

 

 if(rTree.Search(bBox, rTreeCallback))
      {

        ContainmentB(mesh, inBox);
      }

Should also be out of the loop. It does not make sense to call this method here, because it will run in every iteration of the loop.

  1. For that matter the call back would have to bee defined in a different way. But right know I cant think of a way to do so.

Other details:

  • Currently without RTree and for 64 million points the code is taking roughly 3 minutes to complete. This is why I want to try to use RTree to cut down the performance a little.

  • I am not outputting the points in the viewport. I am overriding ClippingBox and DrawViewportWires

Any tips would be great!

2

Hi,

For checking points inside boundingbox. Do you really need distance search, which is always expensive ?

I would just iterate the cloud and do boundingbox intersection:

   public static bool Intersects(this BoundingBox current, Point3d p) {
        return
          (current.Min.X < p.X) && (current.Max.X > p.X) &&
          (current.Min.Y < p.Y) && (current.Max.Y > p.Y) &&
          (current.Min.Z < p.Z) && (current.Max.Z > p.Z);
    }

for aligned bounding boxes you would need to transform pointcloud to aligned box plane, and do search again. this is quite fast.

There is the question how to parallelize the for loop when iterating the cloud, but in this case you would avoid distance function.

1 Like
3

Thanks for the reply,

I am actually not doing any distance search.

And if I do Intersects, I would still need to loop through each point and call that method. So that would not really help, that is precisely what I would like to avoid. In the end I will be looping thorugh lets say 64 million items, and then looping through perhaps 20 million which are the ones in the BBox, to finally test those 20 million for mesh inclusion.

What do you mean by this?

4

You would still need to iterate because you need to construct an RTree and insert every item, which is costly. Bounding Box check is fast enough, because you just checking the coordinate xyz values. What is slow in closest point search is multiplication and square root, in this method you do not have those.

Second - aligned bounding boxes. Imagine your bounding box is rotated.

5

Yep, this I know, but why are you mentioning closest point search?

6

Because it rtree is a closest point search.

I looked at documentation and there is no bounding box search. Unless I am wrong.
https://developer.rhino3d.com/api/RhinoCommon/html/Methods_T_Rhino_Geometry_RTree.htm

I remember in Rhino 5 there was even less options, either searching by distance (a sphere) or box per point, but not search against one box as you are trying to do.

@menno Maybe you can help with RTree search?

1 Like
7

https://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_RTree_Search.htm

Ok maybe I was wrong then, but this method says “Searches for items in a bounding box.”

Ideally, there would be N bounding boxes, where N corresponds to the number of closed meshes

8

This seems to me also the way to go…as @Petras_Vestartas says, RTree creation is itself pretty expensive. If you already know your bounding box and have a collection of points, then filtering those points in the confines of your bounding box is really straightforward using the code provided. What’s good about the syntax here as well is that as soon as any one of those conditionals fails, it stops evaluating. This will quickly pre-sort your point collection.

9

Aha, so you will want to do this for several meshes…makes more sense then to use an RTree. This should do it in a C# component:

private void RunScript(List<Point3d> P, List<Mesh> M, ref object A)
{
  RTree rTree = new RTree();

  for (int i = 0; i < P.Count; i++)
  {
    rTree.Insert(P[i], i);
  }

  DataTree<Point3d> pointsOut = new DataTree<Point3d>();

  for (int i = 0; i < M.Count; i++)
  {
    Mesh m = M[i];
    GH_Path path = new GH_Path(i);

    BoundingBox bBox = m.GetBoundingBox(false);
    var boxSearchData = new BoxSearchData();
    rTree.Search(bBox, BoundingBoxCallback, boxSearchData);

    foreach (int id in boxSearchData.Ids)
    {
      if (m.IsPointInside(P[id], 0, true))
      {
        pointsOut.Add(P[id], path);
      }
    }
  }

  A = pointsOut;

}

// <Custom additional code> 


static void BoundingBoxCallback(object sender, RTreeEventArgs e)
{
  var boxSearchData = e.Tag as BoxSearchData;
  boxSearchData.Ids.Add(e.Id);
}


public class BoxSearchData
{
  public BoxSearchData()
  {
    Ids = new List<int>();
  }

  public List<int> Ids { get; set; }
}
5 Likes
10

@dave_stasiuk from Proving Ground! cool.

Yes! you posted exactly what I was imagining in my head, put could not quite put it in code. I will give it a shot, but it should definitely work.

For only one Bbox, what @Petras_Vestartas suggested is obviously the way to do it. In fact with 64 million points it drops computation time to 9 seconds

Capture
Capture1756×728 96.5 KB

I will try your code snippet, thanks for the reply.