mesh.nearest.signed_distance out of memory error

[MChaus]

While using mesh.nearest.signed_distance I found out that for some meshes this method uses a lot of memory. Hence, all my laptop's memory become used and process being killed. I found a solution - calculate distance in chunks:

sdf_list = []
chunk_len = 100
n = len(sampled_points)
gen_chunks = (sampled_points[i:i + chunk_len] for i in range(0, n, chunk_len))

for points in gen_chunks:
    sdf_list.append(mesh.nearest.signed_distance(points))

My suggestion: would it be beneficial to add an opportunity for processing mesh.nearest.signed_distance iterativly in memory constrained environments? Or maybe add a constraint for algorithm you used?

[ErlerPhilipp]

I had the same problem. It seems to depend on the size (e.g. number of vertices) of the input mesh. If you can work with a simplified mesh, you shouldn't run into memory issues.

Maybe, the used acceleration structure is somehow inefficient. It looks to me like O(num_mesh_vertices * num_query_points).

[mikedh]

Yeah the broad-phase data structure is an rtree-bucket-per-triangle so on large meshes it isn't great. It has the advantage of not needing to implement a data structure, but is absolutely the limiting factor for performance and memory usage for signed distance (in a profile on some test data just now it was 8.0/12.9 seconds). In previous issues we had thrown around using octree/fixed-voxel-bucket or similar, but never found a suitable dependency or easy way to implement it using vectorized checks. PR's or ideas definitely appreciated!

[ErlerPhilipp]

How about using a scipy.spatial.KDTree? https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html
I'm not sure with the details, but you could perhaps use a ball query with triangle radius as a first guess.

[mikedh]

Yeah I couldn't figure out a way to use scipy.spatial.cKDtree it to query cuboid regions, although the skimag.neighbors.BallTree implementation does let you do multiple radius queries. Last time I tried that I saw a LOT more false hits from a bounding sphere of a triangle than a rectangle and it ended up being slower in the end.