Parcube

2017

• 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).
  [details] [slides]
  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.

  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"
  }
  

• W. Randolph Franklin and Salles V. G. de Magalhães. Parallel intersection detection in massive sets of cubes. In Proceedings of BigSpatial'17: 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data. Los Angeles Area, CA, USA, 7-10 Nov 2017. doi:https://doi.org/10.1145/3150919.3150921.
  [details] [full text] [slides]
  Abstract

  We present ParCube, which finds 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 is very compact because it is uses a uniform grid with a functional programming API. ParCube is very fast; even single threaded it usually beats CGAL's elapsed time, sometimes by a factor of 3. Also because it is FP, ParCube parallelizes very well. On an Nvidia GPU, processing 10M cubes to find 6M intersections, it took 0.33 elapsed seconds, beating CGAL by a factor of 131. ParCube is independent of the specific parallel architecture, whether shared memory multicore Intel Xeon using either OpenMP or TBB, or Nvidia GPUs with thousands of cores. We expect the principles used in ParCube to apply to other computational geometry problems. Efficiently finding all bipartite intersections would be an easy extension.

  BibTeX

  @inproceedings{parcube-bigspatial-2017,
      author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
      title = "Parallel intersection detection in massive sets of cubes",
      booktitle = "Proceedings of {BigSpatial'17}: 6th {ACM SIGSPATIAL} Workshop on Analytics for Big Geospatial Data",
      year = "2017",
      month = "7-10 Nov",
      address = "{Los Angeles Area, CA, USA}",
      doi = "https://doi.org/10.1145/3150919.3150921",
      href = "\bibhrefpt{224-parcube-bigspatial-2017}{224-parcube-bigspatial-2017-talk.pdf}",
      mykey = "parcube salles parallel",
      customlinkslides = "https://wrfranklin.org/p/224-parcube-bigspatial-2017-talk.pdf"
  }