I'm working on an algorithm that computes lots of "nearest point on a triangulated surface" queries in 3d as a way to resample data sets, and I'm wondering if there is any information out there on speeding up these queries. My gut tells me that partitioning the set of query points in a voxel grid or something, and doing them in batches could be a speedup, but I can't quite see how I could efficiently use that. Also I'm not sure if the time cost of partitioning would balance the search speedup. Is running N independent queries really the best way?
I found that there are papers and research for the all-knn algorithm, but that's for searching within a single set. And then, those speedups take advantage of the previously computed neighbors or structure within the single set, so I can't use them. It feels close though.
Any help is appreciated.
