Parallel intersection detection in massive sets of cubes
| Autor: | Salles V. G. Magalhães, W. Randolph Franklin |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Multi-core processor
021103 operations research Xeon Intersection (set theory) Computer science 0211 other engineering and technologies 02 engineering and technology Parallel computing Computational geometry Set (abstract data type) Polyhedron Shared memory 020204 information systems 0202 electrical engineering electronic engineering information engineering Polygon mesh |
| Zdroj: | BigSpatial@SIGSPATIAL |
| DOI: | 10.1145/3150919.3150921 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|