Non-uniform density / radius?

[inodentry]

I'd like to fill a space with points using Poisson-disk sampling, but varying the density/radius as a function of the coordinates (imagine a "density field" with different values at different parts of the space).

For example, to fill a 2D square with a gradient where there is a higher density of points on the left side and a lower density on the right side.

Is this possible? I am not very familiar with the algorithm.

[Kromey]

In theory this would be possible; the relevant change, I believe, would need to be made here. Specifically, for your example of a 2D square where the density decreases as the point's x coordinate increases, you'd change the 2nd parameter to the within method to the appropriate function, perhaps e.g. 1 / point[0] (obviously adding appropriate type casts as necessary).

More generically, it should be possible to expose some sort of API that would accept a Fn/FnMut and call that in the code above, where the default behavior would be of course to stick to the fixed density. It's certainly interesting, and I'm going to think about this some more, though for now at least I'm not sure if I want to include such a behavior in this crate.

Stepping back a bit, another possible alternative could be to generate a sample, then do a bit of post-processing to selectively discard points based on a probability function that matches your desired result. For instance, you could generate the Vec of points normally, and then do something like this:

let filtered_points = points.retain(|point| rng.bool(1.0 / point[0] as f64));

Realistically this is probably the better option anyway, as this crate probably should remain clean and focused on Poisson sampling as described by Bridson. Still, I think it's interesting, and I'm going to think further about this.

[inodentry]

The approach with discarding points is interesting, but 1) inefficient (you generate a lot of unneeded points and then do a second pass with more RNG to discard them), 2) difficult to control / predict, because with just a simple RNG it will probably discard too many or too few points in different areas, kinda defeating the point of Poisson Disk which is to generate points that are evenly spread out / with roughly uniform density.

Yes, the ability to use a Fn is perfect, because it gives direct control over the generation of points.

The gradient example was just something simple I came up with to illustrate what I meant. In reality, the real interesting use cases are with more complicated functions.

For a more interesting example, consider a procedural generation use case where you want to generate a forest by placing trees with the Poisson Disk algorithm, but you want there to be more trees closer to a mountain, less trees at higher altitude, and also some areas/patches with more or less dense forest (which can be accomplished by using something like a 2D perlin noise function to control the Poisson Disk algorithm). A custom function makes it very elegant to accomplish that.

This is something I can do in Blender using its Geometry Nodes workflow for procedural generation. I'd love to be able to do a similar thing in Rust. It feels like something that should be supported by a library offering the Poisson Disk algorithm. It would be very powerful.

That said, if you really are not interested in supporting this, thanks for at least giving me a pointer / explaining where to look! I could fork the crate and probably do it myself.

[Kromey]

I've done similar things myself by either layering distributions on top of each other, or once by using a large distribution (with a large radius) to set the center point for multiple smaller distributions. Of course as you might imagine both approaches have their problems and limitations, though the latter worked very well for setting up semi-isolated star clusters for a game and could be great for distributing separate groves of trees.

The more I think about this, though, the more I do want to tackle it. I've not done much with Fn objects yet, and I'm a little worried about performance impacts, but I think I can overcome both of these.

For the API, I'm thinking one of these two approaches would be best:

1. Add a with/set_radius_fn() method that would allow a function to be specified rather than a fixed radius; the with/set_dimensions() method would still require a fixed radius, but calling this new method after that would allow specifying the function.
2. Make with/set_dimensions() generic, allowing either a fixed value or a function to be specified for the radius

The first option seems like it would keep the API the cleanest and better illustrate that the radius function is an entirely separate, optional piece; on the other hand, having to specify a fixed radius when setting the distribution's dimensions just to immediately replace it with a radius function feels dirty.

A third option would be to remove radius fromwith/set_dimensions() entirely, and add separate radius() and radius_function() methods; this is probably the cleanest option, though besides breaking backwards compatibility (not a big deal, just bump to 2.0) requiring setting the radius at the same time as the dimensions was a deliberate design choice to help users avoid enormous performance pitfalls if they set a large area but forget to increase the default radius.

I'll think more about how I want to design this, but would also like to hear your thoughts on the API design as well