SIMDop: SIMD optimized Bounding Volume Hierarchies for Collision Detection We present a novel data structure for SIMD optimized simultaneous bounding volume hierarchy (BVH) traversals like they appear for instance in collision detection tasks. In contrast to all previous approaches, we consider both the traversal algorithm and the construction of the BVH. The main idea is to increase the branching factor of the BVH according to the available SIMD registers and parallelize the simultaneous BVH traversal using SIMD operations. This requires a novel BVH construction method because traditional BVHs for collision detection usually are simple binary trees. To do that, we present a new BVH construction method based on a clustering algorithm, Batch Neural Gas, that is able to build efficient nary tree structures along with SIMD optimized simultaneous BVH traversal. Our results show that our new data structure outperforms binary trees significantly.

Volumetric Tree * : Adaptive Sparse Graph for Effective Exploration of Homotopy Classes We present volumetric tree*, a hybridization of samplingbased and optimizationbased motion planning. Volumetric tree* constructs an adaptive sparse graph with volumetric vertices, hyperspheres encoding free configurations, using a samplingbased motion planner for a homotopy exploration. The coarsegrained paths computed on the sparse graph are refined by optimizationbased planning during the execution, while exploiting the probabilistic completeness of the sampling based planning for the initial path generation. We also suggest a dropout technique probabilistically ensuring that the sampling based planner is capable of identifying all possible homotopies of solution paths. We compare the proposed algorithm against the stateoftheart planners in both synthetic and practical benchmarks with varying dimensions, and experimentally show the benefit of the proposed algorithm.