VTKOBBTree::InsideOrOutside Strange running time

Support
1

Hi, teams.

I have used vtkobbtree::InsideOrOutside to detect the intersection of two polys.
Then I made a tree for poly_a, and detect if poly_b.point(i) is in poly_a.

Here is the problem,
If b is far away from a, (completely outside of a).
Its running time is almost 100 seconds (For 5000+ points in b, while a is a very complex mesh)

However, if b and a intersects, it will run very fast (almost 12 seconds).

I think here comes a big logical problem in this situation.

Internal and external detection for obb tree should check the outermost box in first. If it is outside, there will be an early stop method I think.

Therefore, the farther a and b are, the faster the program should run.
But why is the situation in my test completely opposite?
If b is completely inside a, all levels of node will be judged, is it right?

In addition, I hope someone can give me a suggestion to find out the intersection part of a and b smarter.

Thank you!
Best regards.

Here is the code

    auto num = m_cup->GetNumberOfPoints();
    auto nptr = static_cast<float*>(m_cup->GetPoints()->GetVoidPointer(0));
    int a = 0;
    for(int i = 0; i < num; i++){
        a = m_tree->InsideOrOutside(ndata->GetPoint(i));
        std::cout<<i<<"/ "<<num <<":" <<a <<std::endl;
    }
2

I believe that you have found a bug in vtkOBBTree, it is not checking the trivial rejection case. The code is also in need of performance and other clean up.

Having said that, if your intent is to determine whether one polygon intersects with another, there are several other ways to do this which would be much faster. Probably the easiest is to use a combination of a cell locator (e.g., vtkCellLocator or vtkStaticCellLocator), bounding box (e.g., vtkBoundingBox), and polygon intersection code (vtkPolygon::IntersectPolygonWithPolygon()). That is, you want to use the cell locator to find candidate intersection polygons quickly (e.g., FindCellsWithinBounds()).