Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Enhancement: Add faster poisson disk sampling #178

Open
BradFitz66 opened this issue Jan 8, 2024 · 0 comments
Open

Enhancement: Add faster poisson disk sampling #178

BradFitz66 opened this issue Jan 8, 2024 · 0 comments

Comments

@BradFitz66
Copy link

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')

@BradFitz66 BradFitz66 changed the title Add faster poisson disk sampling Enhancement: Add faster poisson disk sampling Jan 8, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant