0
\$\begingroup\$

Usually this is solved via something like Poisson Disk Sampling, but it is both slow and not able to be parallelized making it even slower as well as needs information of previous placed objects that I do not always have.

Currently I am using Jittered Grid placement but while the performance and parallelism is good, it creates several unwanted overlaps that causes issues in my case.

I am searching for an alternative that does not suffer from these problems. A mix of both implementations kinda

\$\endgroup\$
6
  • \$\begingroup\$ it would help if you could provide more info about the quantity of points you're trying to distribute & what your profiling results were. Poisson Disk Sampling can be done in linear time (as shown here); unless you have a huge # of points &/or need real time updates (which is info you should also include if you do), it's likely to be fast enough. If not, since it uses a grid, you could parallelize by chunking the grid & then dealing with the seams. \$\endgroup\$ Commented Nov 25, 2022 at 21:40
  • \$\begingroup\$ You may be interested in Layer-Based Procedural Generation for Infinite Worlds, which solves the "previous placement information" problem by dividing generation into layers. Layer 0 can be an initial naive shaken grid. Layer 1 can then nudge/filter those points according to their immediate neighbours to respect the no-overlap constraint. So you generate the area you need plus some margin at layer 0, in order to have all the information needed to generate layer 1. \$\endgroup\$ Commented Nov 25, 2022 at 21:44
  • \$\begingroup\$ There's also been published research on parallel algorithms for Poisson disc sampling. Though for games it often suffices to pre-bake a tiling Poisson disc distribution into a texture and sample it - I remember finding a good resource for such textures a while back but I'm having trouble finding it now. I'll update this comment if I can find the link again. \$\endgroup\$ Commented Nov 25, 2022 at 21:49
  • \$\begingroup\$ @Pikalek several hundred thousand points up to millions. i did some experimenting with grid based parallelism but the stitching created several issues for me. i have no profiling results as i didn't even attempt to run it at this scale \$\endgroup\$ Commented Nov 26, 2022 at 12:45
  • \$\begingroup\$ @DMGregory both sound quite interesting and i have to take a better look at them and if i can adapt my current setup so that i have the information of neighboring cells for that. also are poisson disc sampled texture not just blue noise textures? \$\endgroup\$ Commented Nov 26, 2022 at 13:51

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.