W Randolph Franklin home page
... (old version)
GeoStar2014/ home page Login


I (WRF) have been experimenting with implementing a 3D uniform grid in Thrust with a CUDA backend.

My specific example is to find pairwise intersections among a large set of small identical cubes. Two applications are these:

  1. Find all pairs of points within a given distance.
  2. Find all pairwise intersections among a large set of 3D faces (by testing their enclosing boxes).

It now generates random uniform i.i.d. cubes and then finds all pairs that intersect.

It might have errors since I haven't done serious correctness tests. However I believe that the fundamental ideas are correct, and any errors are fixable.

I start timing after creating the data.

Here is a sample result on geoxeon:

  1. Number of cubes: 10M
  2. Edge length: 0.0025
  3. Grid: 400x400x400
  4. Number of pairs of cubes: 127M
  5. Number of unique intersections: 6M
  6. Elapsed time: 0.5s.

Here are more times:

[:attachcsv cube-xsect-times.csv'border=1 cellpadding=3 cellspacing=0':]

I believe that to be extremely faster than competing methods (and welcome specifics).

The slowest step is sorting the set of (cube,cube) pairs, necessary to delete duplicates.

I could make the program perhaps twice as fast, but probably won't bother.

It would be good to read in real 3D points (and construct the cubes around them).

There are no fundamental dependencies on the cubes being identical, but this considerably simplifies the implementation.

The interesting part of my code is only about 50 lines.

The hardest part of the programming is wrapping my head around the Thrust programming model. I am doing some really neat things. There are other possible tools, like Newton, that I might try sometime.

My conclusion is that the combo of Thrust with CUDA and the uniform grid is very powerful and deserves more exploration.

My goal is a BIGSPATIAL paper, due Aug 31.

The big change from the previous version of this page is that creating the pairs took more time and space than expected, shrinking the max size that fits, and taking more time.

In return being made co-authors, the biggest thing that I need is prior art and comparisons to other SW.