Parallel intersection detection in massive sets of cubes | W. Randolph Franklin, Rensselaer Polytechnic Institute, Troy NY USA

W. Randolph Franklin and Salles V. G. de Magalhães. Parallel intersection detection in massive sets of cubes. In 27th Fall Workshop on Computational Geometry. Stony Brook University, New York, USA, 3–4 Nov 2017. (talk).
[slides] [BibTeX▼]

@inproceedings{parcube-fwcg-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Parallel intersection detection in massive sets of cubes",
    booktitle = "27th Fall Workshop on Computational Geometry",
    year = "2017",
    month = "3--4 Nov",
    address = "{Stony Brook University, New York, USA}",
    note = "(talk)",
    href = "\bibhrefat{225-parcube-fwcg-2017-abs}{225-parcube-fwcg-2017-talk.pdf}",
    mykey = "salles parcube parallel",
    customlinkslides = "https://wrfranklin.org/p/225-parcube-fwcg-2017-talk.pdf"
}

Abstract

We present ParCube, a very fast parallel algorithm and implementation for finding the pairwise intersections in a set of millions of congruent cubes. This operation is required when computing boolean combinations of meshes or polyhedra in CAD/CAM and additive manufacturing, and in determining close points in a 3D set. ParCube expresses a 3D uniform grid using functional programming concepts in Nvidia Thrust. The underlying HW can be either regular single-threaded C++, an Nvidia GPU with CUDA, or a multicore Intel Xeon with OpenMP or TBB. ParCube can intersect 10M i.i.d. cubes with 6M intersections in 0.32 elapsed seconds, which is 131x faster than CGAL. Even running single threaded on the CPU, ParCube ran this case three times as fast as CGAL. ParCube can also find bipartite intersections without expensive preprocessing.