Better approach / faster processing for point inside solid

Hi there!

Long time lurker, first time posting.

I currently have a IronPython script in Rhino that given a CSV file which includes three columns of XYZ coordinates along with other data, it checks each row’s coordinates against an array of solids in BREP format to see which solid the XYZ coordinate is inside.

My current approach is to first convert all the rhino solids in a 3dm file into BREPs and store them in a dictionary in memory with the ID of the solid (think of a room number in a hotel) as the key and the BREP data of the solid as the value. This is done only once per script execution and only takes a few seconds.

Then, for each row in the CSV, convert the XYZ columns into a Point3d, then traverse the dictionary of BREPs and use the brep.IsPointInside() function to check if that Point3d is inside each of the solids. Store matches and return as extra columns on the CSV file. This is currently a nested for loop, so O(N^2) time complexity.

This has been working fine, but for large CSV files (hundreds of thousands of rows), this can take several minutes and our data sets keep growing.

Do you have any proposals on how I could speed this up? Multi threading for parallel processing? Using some kind of Kd-Tree implementation? Finding nearest neighbors first instead of traversing all solids? Would switching to C# instead of Python give a noticeable boost in performance?

Eventually I would like to migrate this to use Rhino compute, not sure if that changes anything.

Thank you!

Hi,

In general, whenever you run into a performance issue, it is important to detect the true bottleneck first. If you don‘t know how, its good to provide a minimal example, showing the problem.

One of the true advantages of writing in C# is that the Visual Studio Profiler is one of the best around. If you look into Rhino bug reports, you almost always see a profiling session attached, because you can pinpoint various forms of bottlenecks, which you might never detect using the scripting approach.

I‘m not saying you should switch to C# now, but I want to highlight the importance of investigating the real cause of your problem. Apart from having an algorithmic bottleneck, things like inefficient IO, using wrong collections (Dictionaries are slow) or other non-obvious things can be a bigger problem.
Nowadays even a million data-points are not alot, and you are probably not looking for optimization in milliseconds here.

From the algorithmic perspective, I would guess that you could indeed divide and conquer. Kd-Trees or similar, are graphs which tackle these types of problem. But any custom graph implementation could solve it. This problem also qualifies for a parallel execution. So sure, there is plenty of optimization doable. Do you like to share what you have?

2 Likes

I would say most of the code is parsing CSV and getting the right columns for the right type of item in the CSV files, but below is the part where I’m checking which solids match the given coordinate.

For reference, the base Rhino model has about 400 “compartments” or solids to check each of the given points against, and some CSV have 60 columns and 100k+ rows.

import rhinoscriptsyntax as rs
import scriptcontext as sc
import Rhino


compartments = {}

# Called only once
def CacheCompartmentBreps():
    # 1. Select all polysurfaces and extrusions to check coordinates against.
    # state=0 for all objects, 1 for visible only
    solids = rs.ObjectsByType(8+16+1073741824, select=False, state=1)

    # 2. Traverse through each solid and convert to brep
    for solid in solids:
        if not solid:
            return
        compartment_name = rs.ObjectName(solid)

        # 4. Get solid BREP geometry
        s_brep = sc.doc.Objects.Find(solid).Geometry
        
        # Necessary if solid is an extrusion object
        if type(s_brep) == Rhino.Geometry.Extrusion:
            s_brep = s_brep.ToBrep()

        if compartment_name and s_brep:
            compartments[compartment_name] = s_brep


# Called once per XYZ to check
def FindCompartmentForCoordinate(coordinates):

    rs.EnableRedraw(False)

    compartments_matched = []

    point = rs.coerce3dpoint(coordinates)

    if not point:
        return compartments_matched

    for compartment_name, s_brep in compartments.items():

        strict = False
        tol = sc.doc.ModelAbsoluteTolerance

        if s_brep.IsPointInside(point, tol, strict):
            compartments_matched.append(compartment_name)

    return compartments_matched