Fast Distance Queries for Triangles, Lines, and Points using SSE Instructions
Evan Shellshear, Robin Ytterlid · 2014
This paper presents a suite of routines for computing the distance between combinations of triangles, lines and points that we optimized for the x86 SSE SIMD (vector) instruction set. We measured between two and seven times throughput improvement over the naive non-SSE optimized routines. In recent years, SIMD utilization has become a major theme of high performance computing. Modern CPUs support SIMD extensions that can be used to gain some of the benefits of many-core computation while avoiding some of the drawbacks. SIMD extensions are CPU implementations of the SIMD architecture described in Flynn’s Taxonomy [Flynn 1972], and they allow a CPU core to perform a single instruction on multiple pieces of data in parallel, while maintaining the low response time inherent in CPU processing. A benefit of SIMD is the possibility to combine SIMD extensions with threaded multi-core CPU processing for even greater exploitation of parallelism. Intel’s Streaming SIMD Extensions (SSE) is a SIMD instruction set that is supported by the great majority of modern processors, and it utilizes 128-bit registers that allows a core to perform up to four single-precision floating point operations at once. Although the SSE instruction set can process at most four floating-point values at a time, with the more recent AVX and AVX2 instructions it is possible to process up to eight floating-point values in parallel. Thakkur and Huff [1999] gives a more in-depth description of SSE and SIMD extensions in general. When it comes to basic, low-level computer graphics routines, there is great interest in exploiting SSE, with articles exploring fast SIMD-based ray-triangle intersection tests [Havel and Herout 2010], sphere-box intersection tests [Larsson et al. 2007], etc. Mostly, such tests focus on using SSE in a more serial fashion where one