No video :(

Coding Challenge #33: Poisson-disc Sampling

Подписаться 1,7 млн

Просмотров 88 тыс.

50% 1

In this coding challenge, I implement a "Poisson-disc Sampling" algorithm to evenly (but randomly) distribute a set of seed points throughout a canvas. The algorithm is implemented in JavaScript using p5.js. Code: thecodingtrain.com/challenges...
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
🎥 Previous video: • Coding Challenge #32.1...
🎥 Next video: • Coding Challenge #34: ...
🎥 All videos: • Coding Challenges
References:
🔗 Poisson Disc: www.jasondavies.com/poisson-d...
📄 Paper on Fast Poisson Disc Sampling in Multiple Dimensions: www.cs.ubc.ca/~rbridson/docs/b...
Live Stream Archive:
🔴 Coding Train Live 56: • Live Stream #56: Poiss...
Related Coding Challenges:
🚂 #98 Quadtree: • Coding Challenge #98.1...
🚂 #70 Nearest Neighbors Recommendation Engine: • Coding Challenge #70: ...
🚂 #95 Approximating the Value of Pi: • Coding Challenge 95: A...
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
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: thecodingtrain.com/discord
💖 Membership: ru-vid.comjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#poissondiscsampling #simondenispoisson #p5js #processing

Опубликовано:

30 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 120

@stropheum 7 лет назад

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

@TheCodingTrain 7 лет назад

Thanks for this feedback, it's very useful and I will take it into consideration for sure. You might try checking out the live stream archives, even though there's a lot of wasted time, there's a lot more of this fiddling too.

@stropheum 7 лет назад

Daniel Shiffman oh I have, I love them!

@Goel25 7 лет назад

+Daniel Shiffman I also agree with +stropheum I think you should make coding aftermath video's or just include it in the original video, because you can get some really cool results out of it!

@midnightrizer 5 лет назад

@@TheCodingTrain where are live stream archives?

@oamioxmocliox8082 2 года назад

;)

@Ziplock9000 3 года назад

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

@rasm523 3 года назад

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.

@IDontReadReplies42069 Год назад

thats not how angles work lol

@Cartocopia Год назад

Right - need to take the sqrt of random r, and then offset.

@legoushque697 10 месяцев назад

⁠@@IDontReadReplies42069yeah, but this is how radius works :)

@kamoroso94 8 лет назад

Wow this was a really interesting video! I think making a Grid object could have made the code a little more clear, but I learned a lot from this, thank you!

@sebastiangesemann6775 5 лет назад

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

@jeffreyblack666 3 года назад

Could I ask what the justification is for the (sqrt(random(0,3)+1)+1)*r? If I understand the terminology correctly, wouldn't that give a point between 2*r and 3*r I thought it would be simply sqrt(random(r^2,4*r^2)), which would "simplify" to r*sqrt(random(1,4)), or more akin to how you did as r*sqrt(random(0,3)+1).

@sebastiangesemann6775 3 года назад

@@jeffreyblack666 You're right. I probably made an error by adding the 2nd "+1" by accident. Or I arrived at this based on some more complicated math inbetween where I got something wrong. :-)

@danielescotece7144 8 лет назад

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

@kipu44 2 года назад

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.

@3dbob891 Год назад

yep, but if I'm not mistaken you can write an if condition to check if the values are within the boundarys of 0 and column/row count. Correct me if I'm wrong I'm usually very bad at this stuff

@n8style 7 лет назад

love the 1 second goodbyes at the end :D

@kevnar 6 лет назад

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

@michalbotor 6 лет назад

19:13 now, that is really smart part of this algorithm! btw. you explain it flawlessly!

@jeffreyblack666 3 года назад

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.

@Brizizaz 7 лет назад

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

@UTube2K6 6 лет назад

8:20 thumb up for the dart throw ! :D

@Tordek 7 лет назад

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.

@Tordek 7 лет назад

imgur.com/a/UinZO Here's "proof" of what I mean.

@TheCodingTrain 7 лет назад

+Tordek oh! Thanks for this heads up.

@timolenton1904 4 года назад

This is an underrated comment! I kept getting random overlapping points because of this issue. Thanks for flagging.

@alexanderkrewinkel8025 3 года назад

Thanks, i was thinking the same but i couldn't find the answer if 1 or 2 neighbors per side is right.

@ShiloBuff 9 месяцев назад

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.

@andreasiosifelis1691 2 года назад

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

@SebastianDreijer 7 лет назад

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

@jeffreyblack666 3 года назад

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.

@AComputerScientist 5 месяцев назад

This is quite right, in a uniform distribution equal areas should have the same probability of receiving a point. The sub-annulus between distance r and 3r/2 has a different area than the sub-annulus between distance 3r/2 and 2r, yet they have the same probability in the code. Simulating the right distribution for the radius is not extra hard, but does require some more care.

@yhjeong5317 5 лет назад

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.

@petersonic8634 8 лет назад

So smart!

@FloMoTionDJ 7 лет назад

MORE SOUNDBOARD, love it.

@Thomcat 8 лет назад

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: bl.ocks.org/mbostock/d8b1e0a25467e6034bb9 vs naïve: bl.ocks.org/mbostock/31bd072e50eaf550d79e

@Illusionaire1 7 лет назад

How can we integrate this into the actual code he is showing us? I tried to but wasnt able to wrap my head around it.

@Thomcat 7 лет назад

the code at 18:55, where he sets the magnitude m: var m = sqrt( random(1) * (pow(2*r, 2) - pow(r, 2)) + pow(r, 2) ); Basically the magnitude should equal the square root of a random amount between the inner radius squared and the outer radius squared. Instead of just a random amount between the inner and outer radiuses. This means that the distribution is uniform instead of being biased towards the centre. Another random but basically pointless fact is that p5's random is exclusive of the upper bound - meaning that we can never actually get a radius of 2*r - but because of floating points this'll basically never happen either way.

@Illusionaire1 7 лет назад

Thanks so much, Thomas! For the example and the perfect explanation, learned something new today!

@psyneur9182 7 лет назад

Is there any reason random() is denser towards the starting value?

@Thomcat 7 лет назад

PsyNeur because smaller samples when using random as a linear offset from the centre of a circle will be closer together than larger. Like the spokes of a bicycle.

@arne5752 6 лет назад

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!

@TheCodingTrain 6 лет назад

Thanks for this feedback!

@AComputerScientist 5 месяцев назад

Does js have a ceiling function to use instead of floor? This would be the perfect choice for this (no need to add 1 if the dimensions are a perfect multiple of w).

@CloudWalkBeta 6 лет назад

Awesome video! Helped me for generating things into my current map generator project using Perlin for biomes then Poisson for tree planting! I still keep hoping to find a simple to understand and write method for drawing some visually pleasingly good rivers, do any methods come to mind?

@clementeferrer5070 7 лет назад

Have you considered implementing a convex hull algorithm in a video? I think this would be interesting in either processing or p5

@vincentcleaver1925 6 лет назад

I'm trying to do this challenge in Python and taking my time. So far I have a random point and I'm drawing points near the last point, in series. I need to do a list/ array and grid yet

@legotechnic27 8 лет назад

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.

@Shockszzbyyous 7 лет назад

hsv is awesome for creating nice pallets :D

@Nulono 7 лет назад

It'd be nice to see not just the active points, but the ones currently looking around them.

@maxwellgoulding1585 7 лет назад

Could you make a video showing how to set up P5.js from the beginning?

@vincentcleaver1925 6 лет назад

I need to use this to reduce clustering of a bunch of random points; I'm subdividing a map into a bunch of polygons which form land and sea areas

@MediaFilter 2 года назад

Besides Poisson, one can alternatively use Lloyd's algorithm to relax the tightly clustered points in a purely random distribution. It's a very easy algorithm to implement. en.wikipedia.org/wiki/Lloyd%27s_algorithm

@MrZhootSe 7 лет назад

The break you have on line 68 @ 38:24 - As you said youself, the pattern would generate faster if you skipp the break. I would've skipped it instead of doing the for total thing ;)

@reyariass 3 года назад

@2:00 I KNOW WHAT YOU WERE ABOUT TO SAY 😂

@jasonreviews 8 лет назад

subbed!

@JordanJones-jb6gp 11 месяцев назад

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

@michaelfebus6393 2 года назад

I feel like this would be awesome to use with GLSL for making a dithering shader. Have the r value be based on the vue value of the current sample, darker colors are shorter range(r) while lighter colors have longer range. You'd have to be able to program some leniency though so that samples can activate other samples of r values within a small difference. Or maybe I have no clue what im talking about lmaooo

@Nekodigi 4 года назад

Processing version has bug? I fixed the bug and support for 2D array float r = 10; int k = 30; PVector[][] grid; float w = r / sqrt(2); ArrayList active; int cols, rows; ArrayList ordered; void setup() { //size(400, 400); fullScreen(); strokeWeight(4); colorMode(HSB, 360, 100, 100); // STEP 0 cols = floor(width / w); rows = floor(height / w); reset(); // STEP 1 addPoint(width/2, height/2); //frameRate(1); } void draw() { background(51); //noLoop(); for (int total = 0; total < 25; total++) { if (active.size() > 0) { int randIndex = floor(random(active.size())); PVector pos = active.get(randIndex); boolean found = false; for (int n = 0; n < k; n++) { PVector sample = PVector.random2D(); float m = random(r, 2 * r); sample.setMag(m); sample.add(pos); int col = floor(sample.x / w); int row = floor(sample.y / w); //println(col, row, cols, rows, grid[col + row * cols]); if (col > 0 && row > 0 && col < cols-1 && row < rows-1 && grid[col][row] == null) { boolean ok = true; for (int i = -1; i

@kim15742 7 лет назад

Bridson is awesome! He did some Fluid Simulation Stuff! His Book is 70 EUR, though...

@fizipcfx 3 года назад

i might have a pdf of the book

@kim15742 3 года назад

@@fizipcfx Thanks, I got it in the Humble Bundle a year back

@ImperfectFormation 7 лет назад

Dammit Shiffman why are you so awesome?

@matthewbraun6517 7 лет назад

Because he's pure and happy with his career :)

@ningwang3780 7 лет назад

you can add "break" after the line "ok = false" to save some time....

@realcygnus 7 лет назад

cool

@classawarrior 4 года назад

Nice! There's a small issue here with how you pick candidate points (in the donut shaped area around the active point). You randomly choose an angle, and then a distance between r and 2r. But this doesn't result in an even distribution - points generated by this method with smaller distance are clumped together more densely than those further away. So, you're biased towards picking points closer to the reference point.

@defjam993 4 года назад

Same Observation here! I coded something for scriptographer and come to the same conclusion!

@defjam993 4 года назад

ibb.co/hWmkp9D Proof

@anjalisethi1929 3 года назад

Please help I wrote the full code till 90 lines and then it is showing Uncaught SyntaxError: Unexpected end of input (sketch: line 90). This has happened with me a lot of times while doing projects in p5js while watching your videos and I am absolutely frustrated as I had to skip a lot of my favorite projects due to this issue. And also it is showing i is already defined. Regards

@peabrainiac6370 7 лет назад

Do you know a good graphics library for c++ on windows? I couldn't find one

@drunkenskaterguy 7 лет назад

For what kind of graphics? openGL is pretty dominant from what I've seen although I rarely use any graphics.

@Ph34dz 8 лет назад

Hey Daniel, can you do JavaScript tutorials?, you make your videos so much fun, and if you have fun learning you learn faster. If you can, try to cover as if you're teaching new students :P. Would be really helpful

@carlitoz450 Год назад

I really - mean really like - your videos. I only wonder is it a good idea to start coding even without reading the whole algorithm ? Just kidding... ;) I know for sure you've already read it. Thanks for sharing.

@alejandrocambraherrera8242 2 года назад

3:09 LOL

@abeechr 8 лет назад

Where can I get a coding rainbow sticker?!

@Jova 3 года назад

Yes, read that academic maths paper to me...

@everestgjonaj 8 лет назад

hi daniel ! can you actually make programs with p5.js that you can sell or you do them just for fun? can i make this types of things in javascript (drawing objects.etc) without using p5 program?

@lejeunerenard 8 лет назад

You definitely can make these examples without p5 by just using the javascript canvas API. p5 just makes it easier by abstracting the canvas API into simple concepts like points, lines, etc. If you're interested in learning the canvas API, you can check these tutorials: www.html5canvastutorials.com/

@darkfrei2 Год назад

Nice thing, amazing result! But why it's named Poisson?

@3dbob891 Год назад

after the guy inventing the algorithm. ig. i think it's french

@AComputerScientist 5 месяцев назад

@@3dbob891 Definitely not named after the guy who invented the algorithm. Poisson does refer to 19th century French mathematician Denis Poisson, but there is a definition of random point sets called "Poisson point process" named after him. What I don't get is why this is called Poisson, because a Poisson process does clump points together. Poisson is also the French word for "fish", incidentally.

@bassam.2023 4 года назад

What IDE is Daniel using here?

@yonatanlinik562 8 лет назад

wasn't this already uploaded?

@Mrlarswiegers 8 лет назад

yeah i thought aswell weird

@ackdood 8 лет назад

I'm thinking that it was done under the 'coding live' thing and this is the edited version. It's just a guess.

@MrKA1961 6 лет назад

I'd rather make a point grid and then add to each point position a little bit of random noise.

@crankyunicorn4423 3 года назад

the point of this is chunks are better then no chunks

@dickheadrecs 8 лет назад

can you read all of my academic papers for me? thanks

@hyggen7613 7 лет назад

how about you just do your homework yourself? Ass hat!

@Luke-tu1yc 7 лет назад

Hyggen76 doesn't understand a joke lol

@legotechnic27 8 лет назад

I would love to see a video about quadtree things. I am actually making my own 2d physics engine (as a fun challenge) and am using a cell system like this to store my bodies. I have read a lot about quadtrees on the internet though, and don't see the benefit of them.

@kamoroso94 8 лет назад

The benefit of using quadtrees is bring able to compare an element to its neighbors in O(log n) versus O(n) time using a plain array.

@dawalton7435 6 лет назад

"This is the tofu of the algorithm" im gonna start using that now!

@psyneur9182 7 лет назад

13:12 "its more readable this way" how is for (var i = 0; i < grid.length; i++) more readable than grid.forEach(function (cell) {})

@joaovitordossantos9949 7 лет назад

stay in GD

@psyneur9182 7 лет назад

what? why is that even relevant? am i not allowed to have multiple interests?

@joaovitordossantos9949 7 лет назад

fine.

@meunomejaestavaemuso 6 лет назад

Nothing beats 'for cell in grid:'

@adrianschemel 6 лет назад

I just implemented this algorithm in 3D: alpha.editor.p5js.org/full/SJ67PLdg7 Looks great imho Didn't try to make it n-Dimensional because I could never show it on a canvas Didn't even start thinking of using webgl to draw points in space so I used projections

@manuelbonet 8 лет назад

Bootyful? Are you sure?

@manuelbonet 8 лет назад

I only saw points

@toxicore1190 7 лет назад

why don't you use "const" and "let" ? =(

@Shockszzbyyous 7 лет назад

why should you use those ? (just curious)

@toxicore1190 7 лет назад

***** because those do not let you redefine the value later on in the code again, the value of the variable can only be set *once* and then it stays that way. The difference between "let" and "const" is the scope so that if I use a "let" in a function it can have different values between different calls - that is not true for "const". It's meant to provide some safety for your code and comes from pure functional languages like Haskell. There it has the benefit that multihtrrading is as easy as creating threads because the code is pure ;) It's a more mathematical and therefore natural style of writing code where you do not have to care about the time you look at the variable as it cannot ever change. I hope that summarized it a bit :)

@Shockszzbyyous 7 лет назад

cool that makes sense and sounds very useful !

@haha-eg8fj 7 лет назад

I think he's more familiar with ES 5 syntax. Anyway he is doing a good job showing the big picture and the methodology here. I won't bother with the language details in the video.

@oamioxmocliox8082 2 года назад

;)

@TheAzelothmaster 6 месяцев назад

He's got really nice stuff, extremely instructive and eases people into coding, but for me personally he sounds too much like Blippy (from the toddler show, who sounds kinda ADHD and agitated in order to keep toddlers' short attentions). Don't know if that's by design, e.g. he wants to appeal to a younger audience, or an attempt to make subject matter appear less frightening, but it's disconcerting and breaks my flow -- all the clowning around. In terms of quality of content they are similar, but in terms of exposition and communication I have to say I prefer something like Coding Adventures. Neverthless, excellent and educational work!

@yannickbergs5209 7 лет назад

Great video! Please someone try to convince me that I should use Python rather than Java Can't understand why everybody seems to use Python today

@9427gyan 3 года назад

When I am trying to run the code I am getting an error for vector function which states copy of undefined

@mr.musecs4071 7 лет назад

38:00 south America!!!

@mr.musecs4071 7 лет назад

or brazil?

@ajjana3703 7 лет назад

your videos are just awesome. could you implement this algorithm arxiv.org/pdf/physics/9907025.pdf and make an interesting code out of this algorithm.