Octree implementation: how to quickly search through tree?

I need to do hundreds/thousands of searches comparing ~1e4 points against ~1e6-1e7 points in 3d. It's terribly slow. I currently have a functional workaround using matlab's built in KDtree implementation, but it's suboptimal because those larger point sets are accumulated and the KDT can't expand, and I only need a single radius hit to 'reject' the sample but the KDT searcher can't short-circuit.

I have been trying to make my own octree implementation, so it can easily be expanded with new points. (extremely messy) files are attached for anyone that wants a laugh. The good: building this octree is already more than 2x faster than building matlab's KDT, even when i'm using structs everywhere to make testing easy. The bad: searching is ~10x slower than the KDT search, despite having a short-circuit check and not even checking adjacent bins for potential in-radius overlap.

So how do I search through tree nodes really fast and get close to KDT speed? I can't decompile (or find) the KDT search .mex to see if it has a different implementation, and haven't found a readable KDT or octree that is fast. They tend to be orders slower.

Answer 1

[Ashutosh]

There are several strategies you can employ to improve the performance of your octree search. Here are a few suggestions:

• In the search algorithm, try to minimize unnecessary checks by utilizing early termination conditions. For example, if their is need for a single radius hit to reject a sample, you can terminate the search as soon as you find a single point within the radius.
• Consider using spatial indexing techniques, such as spatial hashing or spatial partitioning, to further accelerate the search process. These techniques can help to narrow down the search space and reduce the number of nodes to traverse.
• If your hardware supports parallel processing and has access to GPUs then One can use the Parallel Computing Toolbox, consider parallelizing the search algorithm. You can divide the search space into smaller regions and process them concurrently, which can significantly speed up the search process.
• Optimize the data structures used in your octree implementation. For example, use arrays instead of structs for storing node information to improve memory access efficiency. Additionally, consider using efficient data structures like priority queues or heaps for managing the search process.
• Use MATLAB's profiling tools to identify performance bottlenecks in your octree search algorithm. Focus on optimizing the most time-consuming parts of the code by analyzing memory usage, function calls, and loop iterations.