3 ms·
No, it works because you keep an array of "active" elements during the sweep. Let's say you sweep from left to right over the elements sorted by their left boun
by jansan 6y ago
No, it works because you keep an array of "active" elements during the sweep. Let's say you sweep from left to right over the elements sorted by their left bounds. For each element you encounter you check if it collides with any of the active elements. While doing so, you check if the active element's right bounds is left of the current sweep line. If so, it cannot collide with any of the remaining elements, so you can remove it from the active elements. This way the number of active elements usually stays small and you have to check each element only against few other elements.
- CyberDildonics 6y agoWhat you described is what I said. A spatial acceleration structure is meant to skip as many comparisons as possible. What you are talking about is trading less sorting and more comparisons during the queries.
- jansan 6y agoSorry, I misunderstood the "brute force" part of your comment. You are right, for the active elements the standard implementation uses a brute force on the active elements. I had to implement sort-and-sweep to handle one specific performance problem that took 45 seconds to compute. With the simple sort-and-sweep this went down to 100ms. I also tried sorting the active elements along the secondary axis, but at least in our case this did not yield in any further performance improvements. This probably depends a lot on how many elements there are in the active list.