| The algorithm discussed here reminds me very much of the "Line of Sight" problem. Line of Sight is calculated on a 2-d topographical map, where each 2d point is a height-map. The question is: does location "X" have a line-of-sight to location "Y" ?? You solve this question by marching rays from X towards Y, and seeing if any intermediate 2d point has a height that would block the sight. I bring this up because line-of-sight has been SIMD-optimized and is highly efficient to calculate now. Line-of-sight is similar enough that the large body of research behind that problem can probably serve as inspiration to algorithms in this 'ray marching shadows' algorithm. Its quite possible that your calculation here is "just" a 2-value line of sight: where 0 means "sight is not blocked" and 1 means "sight is blocked". ------ Ray Marching itself seems innately "sequential", because you need to calculate the closest "solid object" to know how far to march. In contrast, the naive "try every pixel" approach is easily parallelized if you understand prefix-sum style computations (see: https://en.wikipedia.org/wiki/Prefix_sum). If you could easily group pixels into 1-bit objects (see PEXT or PDEP: https://www.felixcloutier.com/x86/pdep), I'm sure that a SIMD-parallel version would be outstandingly fast to compute for "small" 256-pixel (aka: AVX2) bit-vectors. ------- EDIT: Now that I think of it: the computation of the distance field is likely sequential. But the use of the distance-field is probably read-only / parallel. A SIMD-line of sight style algorithm using the distance field could be "scheduled" using a sequential algorithm, but then computed with SIMD techniques. |