Coding Challenge #33: Poisson-disc Sampling

References:

Live Stream Archive:

Related Coding Challenges:

Timestamps:
0:00 Introduction to Poisson Disc Sampling!
1:30 Starting to code!
3:00 Creating a 2D background grid
6:52 Inserting initial sample into a random position in the grid
10:25 Creating an active list of points
14:40 Generating up to k points
19:18 Checking neighboring samples
25:40 Removing inactive points from list
27:30 Debugging
36:50 Playing with the code!
41:25 Things you can do!

Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound

#poissondiscsampling #simondenispoisson #p5js #processing

[stropheum]

I love the ends of the video when you play around with stuff. It's so annoying how you always tend to rush through that stuff because you feel like you're dragging the video on for too long, though. I think it might be a cool thing to have something like coding challenge aftermath videos, where after the challenge is done, you're just fiddling with different ways to play with the code. It's super interesting to me (and i assume others) and will make the actual challenge videos a lot more concise

[rasm]

16:30 I think, if you randomly pick an angle and a radius, the resulting points will not be uniformly distributed in the anullus. Points lying further outwards will be spread thin as the outer circumference is bigger.

[kipu]

The video is great! Thank you for showing the algorithm.

I believe there is a small issue in the code though. When you iterate over all neighbors you only check if the element is defined but you don't check if (col + i) and (row + j) are within the grid's bounds. That way you may access an element on the opposite edge of the grid if e.g. col is 0 and i is -1.

[ShiloBuff]

26:57 Great point at making sure to run your code in consistent chunks of code. Running it after a lot of code and having an unknown issue is a lot harder to debug.

[sebastiangesemann]

Cool video of yours!

I noticed a bug. At around 22m you add a nested loop for all (i, j) in {-1, 0, 1}^2 but that's not enough of a search radius to find all of the closest existing samples because w<r. Instead, you could create lower and upper corners of a search window (sample.x-r, sample.y-r) and (sample.x+r, sample.y+r) and figure out the cells that intersect this window.

Also, your sample candidate generation doesn't exactly match the one from the paper. The paper speaks about a uniform distribution where yours is skewed towards lower radi. To get uniformly distributed samples you could use m = (sqrt(random(0, 3)+1)+1)*r or use another form of rejection sampling.

[jeffreyblack]

Also, I think the more appropriate location for the break would be when you set ok to be false. There is no need to continue checking the distance to points when you already know it is too close to a point.

[JordanJones-jbgp]

why does he use only columns not rows too when checking for the position of the point? grid[i + j * cols] 22:38 and there was another example earlier

[Brizizaz]

You have taught me from the ground up, everything about p5!! Thank you for everything!! CHOO CHOO!!

[yhjeong]

32:28, We can get better performance. don't use "break" 64 lines and "if (!found) { }", neither. Just erase 64 lines, and write just active.splice(randIndex, 1); This will really help performance.

[michalbotor]

19:13 now, that is really smart part of this algorithm!

btw. you explain it flawlessly!

[Tordek]

Hey, Daniel, there's a small issue with the part of your generator where you try to check the validity of a point: you only check the grid [-1, +1] places away, but strictly speaking you need to check [-2, +2], because it's possible that, even though all of the immediate neighbors are empty, there is a point too close two grid spots away.

That point could be as close as r/sqrt(n) (which is obviously less than r), so there's a (slim) chance that you could generate two points less than r away.

[Ziplock]

That was a lot of fun and your energy is infectious.

[kevnar]

These videos would be so boring if Dan never made any mistakes.

[Thomcat]

When you do the annulus sampling your method isn't uniform is it? You get a denser distribution closer to r.
You'd want:
theta = 360 * random(TWO_PI);
dist = sqrt(random()*(pow(R1, 2)-pow(R2, 2))+pow(R2, 2));

uniform:
vs naïve:

[jeffreyblack]

When selecting a random point you need to be careful of how you choose it to see what kind of distribution you get.
The way you generated a random point for the annulus weights the probability based upon angle and distance, rather than area, where the latter is what I assumed they meant by uniform.

i.e. if you picked based upon area then each area of the annulus would have the same probability of having a point. If instead you pick based upon angle and distance as you did, then each angle subtended has the same chance, regardless of the distance, and thus an area near the inner limit of the annulus would have a greater chance of having a point than an area near the outer limit.

One way I think would be fairer is to pick a value between r^2 and 4r^2 and then square root it to find the distance.
This will more heavily favour a greater distance, with that cancelling out the increase in area due to the greater distance.

Also, the way you determined what points to look out is flawed as if you are on the edge, in checking the points over the edge you go too far.
Also, the radius is greater than the width of the grid so you don't check all the points within the range.
i.e. if you have 1 point on the right side of a grid square, and another point on the left side 2 grid squares over, then they are separated by just over w, which is r/sqrt(2), or ~0.7 r so that is less than r.

[arne]

I think there's a bug that goes unnoticed because of the way js handles out of bounds: the initialization should create a grid of length (floor(width / w) + 1) * (floor(height / w) + 1), no? imagine a 5x5 grid. a pixel at (width, 0) would be in cell(4, 0), or simply 4. similar for (0, height). so the length of the array you create is 4x4 instead of 5x5. i noticed this when trying to implement it in another language which has IndexOutOfBounds-stuff. Anyways, maybe this is helpful to someone - I love your videos, thanks so much!

[danielescotece]

got the printed version of the nature of code and I must say Really Good Stuff Sir

[SebastianDreijer]

You are very likable. Your voice reminds me of Mitchell's from Modern Family.

[legotechnic]

also, I might be commenting prematurely, but with your 1d array storing 3d data, it will wrap around when going to the side, instead of returning undifined.

[andreasiosifelis]

on 3:51 I like that you knocked on the whiteboard!!! Super funny!