Poisson-Disc Sampling?

General Usage
,
1

Has anyone implemented a Poisson-Disc Sampling algorithm in Julia? I didn’t see anything with a quick google search or by looking through previous discussions.

2

“Poisson-disk” seems to be a more common spelling of it, and searching for that brings up a function in MRIReco.jl (code), and another in Meshes.jl (code).

3 Likes
3

I wrote one too

http://juliagraphics.github.io/Luxor.jl/dev/howto/geometrytools/

juliahub.com’s search doesn’t always find everything… :wink:

1 Like
4

A few months ago I also needed the Poisson disk sampling, and implemented the Bridson algorithm: https://nbviewer.org/github/empet/PoissonDisk/blob/main/Bridson-algo-Poisson-disk.ipynb

1 Like
5

Interesting. It seems like a decent number of people have needed this algorithm and implemented on their own. I wonder if it would be worth having some type of procedural noise package? Poisson-Disc sampling is a type of blue noise, you could add simplex noise, worley noise, perlin noise etc.

It looks like there is a Noise.jl package mainly for images and a ProceduralNoise.jl package that has long been forgotten.

6

I came across BlueNoise.jl also, with pre-generated sources of blue noise.

Creating a new ProceduralNoise.jl seems like a good idea. The linked one seems pre-Julia 1.0 and doesn’t seem registered in General, so the name should be available for a fresh new package to use.

7

I like the idea of organizing these efforts into a common place. Just wondering if instead of creating a new package we could leverage the advanced mesh types in Meshes.jl for that. In particular, we did a huge amount of work to make these sampling methods work out of the box in unstructured meshes, images, or any type of geospatial domain. Besides, we have a well-defined interface already.

8

I might use a small focussed noise package - but I might not require meshes, so adding the Meshes.jl package as an additional dependency just to get a small piece of functionality isn’t ideal.

9

Fair enough :slight_smile:

Any effort to consolidate the different implementations would be great. In particular, I think we could still organize these sampling noise methods for images (or signals) and the wrap them up in Meshes.jl to generalize to the case of unstructured meshes. So users only interested in sampling within “boxes” will load this package X and users interested in more complicated domains can load Meshes.jl that in turn loads X and extends the functionality.

10

Just for fun, here is an example of Poisson disk sampling over the mesh of Beethoven:

using Meshes
using PlyIO

# helper function to read *.ply files
function readply(fname)
  ply = load_ply(fname)
  x = ply["vertex"]["x"]
  y = ply["vertex"]["y"]
  z = ply["vertex"]["z"]
  points = Point3.(x, y, z)
  connec = [connect(Tuple(c.+1)) for c in ply["face"]["vertex_indices"]]
  SimpleMesh(points, connec)
end

# download mesh from the web
file = download(
  "https://raw.githubusercontent.com/juliohm/JuliaCon2021/master/data/beethoven.ply"
)

# read mesh from disk
mesh = readply(file)

# Poisson disk sampling with radius 1.0 and 0.5
pts1 = sample(mesh, MinDistanceSampling(1.0))
pts2 = sample(mesh, MinDistanceSampling(0.5))

using MeshViz
import GLMakie as Mke

viz(mesh)
viz!(pts1, color=:red)
viz!(pts2, color=:blue)

image

and here is Poisson disk sampling on the first triangle of the mesh:

pts = sample(mesh[1], MinDistanceSampling(0.01))

viz(mesh[1])
viz!(pts, color=:red)

image

1 Like
11

At the moment, while there’s still overhead in precompiling/loading packages, one has to think twice before adding dependencies. For example, if I wanted to use a small feature from Meshes.jl in Luxor.jl:

julia> @time using Luxor
  0.561545 seconds (1.03 M allocations: 71.399 MiB, 2.33% gc time, 
    6.37% compilation time)

julia> @time using Meshes
  2.713017 seconds (4.93 M allocations: 319.778 MiB, 4.18% gc time, 
     52.45% compilation time)

it could increase the TimeToFirstWhatever quite a bit. Whereas a smaller package that just does one thing - such as Distances.jl - is easy enough to add:

julia> @time using Distances
  0.008614 seconds (12.32 k allocations: 1.030 MiB, 
    22.47% compilation time)
12

Yes, I am working on the assumption that precompilation will be a solved issue in the future. Basically betting on the work of the Julia core team and the community to build additional tooling to precompile these efforts easily and effortlessly. :pray:

In any case the proposed separation I shared above would work for both worlds.

13

First off, the functionality of Meshes.jl looks amazing. The Poisson disk sampling on Beethoven head is both impressive and hilarious.

I like the suggestion @juliohm made about having a lightweight package just for people who want to do sampling within “boxes” that then generalizes to Meshes.jl. When I needed Poisson disk (disc? :person_shrugging:) sampling originally it was in a context far removed from mesh generation so I think that’s why I didn’t find it immediately. If such a package was created in the JuliaGeometry organization I would definitely contribute to it :grin:

1 Like
14

I have been working on a procedural noise library for a couple weeks. It has many algorithms with a pipeline to compose and modify them in interesting ways. It is nearing completion, so expect an announcement soon.

1 Like
15
1 Like