MaxCube Computation CUDA Range Search, Geometric Computation


Here is a problem I am trying to solve.

Input: B = Collection of 3D boxes, each box specified as {xlo, ylo, zlo: xhi, yhi, zhi}
Query Point: P = {px, py, pz}, and an offset delta

I need to compute the size of the largest cube centered at P that does not intersect any of the boxes in B. I am guaranteed to find one of the boxes in B in the query region {px - delta, py-delta, pz - delta, px+delta, py+delta, pz+delta} and thus can restrict the search to the boxes of B in this query region.

The size of B will be less than 1000. The number of queries will be several million.

I implemented the following algorithm:

  1. Construct a 2D grid and bin the boxes in B into the bins.
    Given a query point and region, find all grid elements that overlap the query region and compute the distance to the boxes stored at these grid elements from the query point.

In my application, I have several threads, each thread does many max cube operations. The query point keeps changing randomly beginning from a start point. Each thread will be searching different regions of space for maxcube.

This scheme is not giving much speedup, compared to a similar implementation on the CPU. Further, when the number of boxes is small, a brute force search shows better results than a grid search.

Any tips on how to efficiently solve this problem will be much appreciated.