scatter
scatter copied to clipboard
Enhancement: Add faster poisson disk sampling
Currently, the poisson disk sampling used for Distribute Inside (Poisson) is pretty slow, especially if you want to use it for a large area. I propose an enhancement to improve the speed of the algorithm.
Enhancement
The general idea of the enhancement comes from this medium article which shows how you can multithread poisson disk sampling using either a bucket or tile based system.
The gist of the bucket algorithm goes:
- Split the grid into buckets
- Give each bucket it's own thread (each bucket should have 'padding' to avoid buckets having to check neighboring bucket's points)
- Run the poisson disk sampling algorithm for each bucket to place evenly distributed points inside them
- Once all buckets are filled, merge neighboring buckets and fill the empty borders between them
- Repeat until area is completely filled
For the tile algorithm, the following changes need to be made:
- Only generate points in 4 or so of the buckets
- Repeat/'Stamp' those buckets for every other bucket
- Do steps 4 and 5 of the bucket algorithm (merge neighbors and fill in the empty space)
(my breakdown of these algorithms may be incorrect/subpar, see the medium article for more/better information)
Possible draw backs
The medium article states that there may be some repetition in the points if you look close enough. If this proves to be a substantial issueq, then this enhancement can either be it's own modifier (for example, under the name 'Distribute Inside (Fast Poisson)') or as a optional checkbox inside the current modifier (i.e. 'Enable buckets'/'Enable tiles')