Coding Challenge 181: Weighted Voronoi Stippling
ฝัง
- เผยแพร่เมื่อ 31 พ.ค. 2024
- Stippling is an artistic technique that uses numerous dots to craft an image. In this coding challenge I attempt to implement a weighted Voronoi stippling algorithm with p5.js along with the Delaunay triangulation package from d3.js. Code: thecodingtrain.com/challenges...
🚀 Watch this video ad-free on Nebula nebula.tv/videos/codingtrain-...
p5.js Web Editor Sketches:
🕹️ Weighted Voronoi Stippling: editor.p5js.org/codingtrain/s...
🕹️ Circumcircle: editor.p5js.org/codingtrain/s...
🕹️ Delaunay Triangulation: editor.p5js.org/codingtrain/s...
🕹️ Voronoi Diagram: editor.p5js.org/codingtrain/s...
🕹️ Voronoi Phyllotaxis: editor.p5js.org/codingtrain/s...
🕹️ Voronoi Diagram colored by area: editor.p5js.org/codingtrain/s...
🕹️ Lloyd's relaxation: editor.p5js.org/codingtrain/s...
🕹️ Weighted Stippling - Size and Color: editor.p5js.org/codingtrain/s...
🕹️ Weighted Stippling - Abstract Pattern: editor.p5js.org/codingtrain/s...
🕹️ Weighted Stippling - Video: editor.p5js.org/codingtrain/s...
🎥 Previous: • Coding Challenge 180: ...
🎥 All: • Coding Challenges
References:
🔗 d3-delaunay: d3js.org/d3-delaunay
🔗 Weighted Voronoi Stippling: www.cs.ubc.ca/labs/imager/tr/...
🔗 Sweep Line Algorithm: en.wikipedia.org/wiki/Sweep_l...
🔗 Lloyd's algorithm: en.wikipedia.org/wiki/Lloyd%2...
🔗 Polygons and meshes by Paul Bourke: paulbourke.net/geometry/polyg...
🎨 Pablo Jurado Ruiz: / pablojuradoruiz
🔗 Stippling: en.wikipedia.org/wiki/Stippling
🔗 Voronoi Diagram: en.wikipedia.org/wiki/Voronoi...
🔗 Delaunay Triangulation: en.wikipedia.org/wiki/Delauna...
🔗 Mike Bostock's Voronoi Stippling: observablehq.com/@mbostock/vo...
Videos:
🚂 Pixel Array: • 11.3: The Pixel Array ...
Related Coding Challenges:
🚂 C4 Worley Noise: • Coding Worley Noise
🚂 33 Poisson-disc Sampling: • Coding Challenge #33: ...
Timestamps:
0:00 Hello!
0:37 What is a Delaunay triangulation?
2:31 d3-delaunay package
2:49 Coding the delaunay triangulation.
6:38 What is a Voronoi diagram?
9:17 voronoi function on the delaunay object
10:25 Things you could try with the Voronoi diagram
10:56 Lloyd's "relaxation" algorithm
12:07 Calculate the average of a polygon's vertices
15:30 Calculate the area of a polygon
16:45 Calculate the proper centroid of a polygon
18:47 What is stippling?
19:45 Draw dots based on brightness value of pixel
21:50 Calculate a weighted centroid
24:51 Using delaunay.find()
27:52 Ideas for you to try!
28:47 Goodbye!
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: th-cam.com/users/thecodingtrainjoin
🛒 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...
#delaunaytriangulation #imagestippling #voronoi #sweepalgorithm #lloydsalgorithm #p5js #javascript
![[LIVE] : ONE ลุมพินี 65 | คู่เอก "จ้าวเสือใหญ่ vs ผึ้งหลวง"](http://i.ytimg.com/vi/TDpOh5eEJKw/mqdefault.jpg)
I love how this feels both like a University Lecture, and a kids educational channel!
I just wanted to drop by and express my heartfelt appreciation for the amazing content you've been sharing on your channel. Your videos are not only educational, but also a huge source of inspiration for me and many others in the coding community. The generosity with which you share your knowledge and passion for coding is truly commendable. Thank you for being such a fantastic resource and for all the hard work you put into making complex concepts accessible and fun. Keep up the incredible work!
100%!
Would like to second this as well Daniel for making both education and programming fun and at the same time. I've watched you for years and years and I have always enjoyed everything that you've made, especially the coding challenges. For a little while, I even replicated some of the coding challenges in Python using the p5 package for python. Keep up the great stuff and don't ever stop Sir!
I was going to say "This rules. You rule". But your's is more good words.
14:40 "This is lovely, but it's collapsing into an black hole..." That's a very funny quote 😂
it looks so organic there
Accidentally made a gravity simulator…
I'd love to see this done for each R G B channel individually. i think that would create a really cool comic book type of effect.
how fascinating it was to see Gloria Pickle turning into Gloria pixels! you make it look so easy!
I program for a living and I couldn't agree more. He makes it looks so easy! But I know it's much more complicated, he's just so good at his job.
I love the new editing style Dan! Feels refreshing to see intros and the Apple ][ jingles being used in the beginning of the video!
In college a was an undergraduate research assistant converting a 2d voronoi lattice simulation to 3d. 7 years later I think I finally have a grasp on what that simulation was actually meant to do because of this video so thank you.
I love your enthusiasm and I really appreciate that you show your mistakes and laugh about them. Let's be honest, learning to program is boring. You make it really fun.
Dude, you are doing a great job. You are personally entertaining, you are providing problem solving techniques and the projects you are doing are very cool. I'm glad I found this channel.
The Coding Train is by far the most awesome educational and inspiring coding lessons there is. Thank you so much for sharing your coding adventures, you are the best. ♥
You're doing a fantastic job. Don't ever stop creating!
This guy makes me so happy and is such an inspiration for TH-cam and coding in general. I love it
Can’t believe this guy taught me so many wonders of coding back in the day and he’s still going! Keep up the good work!
This is basically just shader math, you should try doing a video about/using glsl or hlsl, theres some fun stuff you can do with them, maybe use shader toy? (Never used it bc Im a gamedev so use shaders in engine/in opengl)
In all my (few) but intense years of learning creative coding I have not had a greater source of learning and inspiration from your channel. Your ways of teaching and exploring deep and complex topics of creative coding are amazing, fun, and highly enjoyable. The coding community cannot thank you enough!
Wonderful video, Daniel. I love how each video is so visual and leads me to learn a new algorithm or mathematical technique as well as improving my coding.
Every time you introduce some idea, I feel like, "yeah sure, I know the math, that's how that works, no way you can implement it in a single video", then you simply code it up. I am amazed.
Wow I admire your coding skills. I could not do what you keep doing. I don't have the passion to always throw myself into new coding problems.
I will never forget you, "Coding Rainbow" 🙏
As a former graphics programmer, I loved this! Also, your enthusiasm and positivity is infectious! Love it man, always happy to hop on board!
Mindblowing His ability to pick some abstract concept and just use it to solve an real problem in minutes
Love it! It reminds me of a technique you used before, which is Floyd-Steinberg dithering. However, this one seems more challenging since you used an external library, but it sets a challenge to write the whole algorithm from scratch and optimize it, which I think I will attempt!
oh, please do! I would love to see it!!!
Floyd Steinberg performs error diffusion in some direction, whatever direction you're scanning towards, say towards bottom right, so if you apply it to a moving image, your start of scan is relatively stable say top left corner but your bottom right is very noisy. This isn't visible in static images, only moving.
You could potentially start scanning out from the middle but that doesn't really solve the problem, it will still be obvious where the noise is eminating from.
There's a more modern algorithm with a similar visual outcome to Floyd Steinberg but without bias in any direction, where you use a precomputed blue noise as a threshold function, and you can reuse the same across frames or use a spatiotemporal variant, and the way to compute this blue noise, the foundation is in this very video - Lloyd's Relaxation of a random point set.
Blue noise sampling is the foundation of a lot of modern stochastic rendering methods in graphics. There's a whole research group at Nvidia concerned with blue noise.
You don't need voronoi for how it was eventually done.
You could just determine the point that is closest to the pixel ... (That point's voronoi cell will contain the pixel.)
Im so excited! I saw your video on nebula tv but i didnt had any subscription so i couldnt watch i didnt think you would upload it this early
I felt so relaxed watching this 😌with a nice touch of Dan's enthusiastic sounds every time he got the next thing to work. Jokes aside! Got lots of inspiration from this tutorial - thank you Dan!
Thank you Patt!
Hay i been braking my head on this algo for the last yr, was exploring how to go from delaney to nanite 😂 and went as mad as you have, 😅 the fact that u had a hard time, makes me not feel so dumb anymore, not to take anything away from you, love your stuff watch as many as i can, would love to see you experiment with shadertoy constraints and do some crazy stuff 😊
This has been my favorite channel since I don`t know, 2017
Thank you! Your work is inspiring 😄
You are brilliant...loving the videos, thanks 🙂
This was super fun to watch, thanks so much!
This algorithm is good for relaxing UV maps for unfolded meshes for artist texturing. The "raster dots" effect can easily be achieved by averaging the image into boxes of n by n pixels and drawing a circle scaled to the magnitude of the average value. Instead of scaled the dot can also be proportionally occluded by another offset dot masking it out, or a hole dot within the dot and whatnot...
Such a great series!
Hard work, and good explanation. Very helpful! 👍
Thank you for another great video, Mr. Shiffman 😁👍
Back in the day I made a random map generator and the coastlines and elevation features were drawn via voronoi diagrams. I coded the main app in p5 but also imported d3 for the voronoi computations, so, yeah. No shame in that, lol.
you have a great program of all time. 😊 I like to watch your own coding. nice.
Cool as always
The formula for the area of a polygon is the famous shoelace formula! Mathologer, among other people, has a nice video about it.
Hands down....Black belt in coding. I love it.
Pretty good stuff. This seems a very useful method to correctly simulate film grain in a digital photo
Maybe I should leave a comment on each video you upload. Whenever I'm coding or facing a task, I play one of your challenge videos. They inspire and empower me to overcome the obstacles in my tasks.
Watched this. Gzzz my head did hurt. You do make it look easy.
I understood the absolute number of ZERO things. Thank you.
Wow, so cool!!! ❤
babe wake up! new coding train video just dropped!
Amazing content, thanks !
14:43 God coding the fabric of spacetime
My brain hurt, but I was amazed by the beauty of mathematics and your explanation. I have been following it more or less for years. thanks
well that was awesome
Good one Dan !
Man.. I really love your videos although I don't code almost at all.. but damn i like how you integrate things that are pure abstractions for me into applicable real projects. You are a true professor.
I can't and have never coded in my life but i still love your videos!
You can. Just start somewhere and one step at a time.
Well. This was pretty amazing
Thanks!
You are the best !
Amazing video!
Just wanted to note that there are more sophisticated stippling algorithms, like the one based on power diagrams, which is a generalization of Voronoi diagrams (implementing it _is_ a coding challenge). See "Blue noise through optimal transport" paper for details.
Besides, you check whether the center of each pixel is inside the Voronoi cell to calculate its mass center. Considering each pixel as a square and calculating the intersection area with each Voronoi cell will give a significant quality improvement for the Lloyd algorithm.
Cool video. I took a computational geometry algorithms class in college where we created voronoi diagrams using a beach line sweep algorithm in nlogn time. One of the more difficult classes I had, but a lot of cool problems too.
The black hole! 😯 Unexpected but so cool!
Excellent!! :)
I like dithering in art, it looks cool
fascinating and relaxing
You are Bob Ross of programming
Very nice, with c# will be also useful
Awesome!
Stunning as always!
Thank you!
oh man ive been wanting to do this
I have no idea whats going on but this is so cool 😃
amazing :D
thats cool!
how did you and the paper fit under your pillow and did you use protection? twofish?
The black holee is mesmerizing
the point where you made the points relax based on the centre of gravity could (maybe) be used for liquid simulation
I like ,relax, followed by head scratching 😂😂
I wonder, is this algorithm used in high-end RIPs to convert gray-scale image to BW one for printing?
fun fact: we just had those in our first lecture of solid state physics this monday. i'm deffinitely tempted to make a 3D version of this, and make it efficiently, that seems like a fun geometric problem.
And if you colapse more the dots on darkness areas?
How is this (or is it) related to denoising algorithms used in image processing?
If you created a circle on every point which all expand at the same rate and had them ‘flatten’ when they collided with another circle would that create the voronoi diagram? I’m not sure how efficient that would be code-wise but I’m just curious as to whether it would work at all.
This does look like fun. I think I'll try it in C with RayLib, and use color. This might make for a really cool image viewer.
geez xD this is high vibration content
Loved it
Is it maths, cs or stand up comedy though
Small mistake on 9:07, where the last circumcircle of the right triangle should be. But overall, that was a fun and educational coding challenge! As always ;)
Where did you do your livestreams?
“Let's put them into an array. And lerp the original points towards the centroid.” It seems weird that I understand that...
Instead of converting points to voronoi, and then figuring out which polygon a pixel is in, you could just determine which point is closest to the pixel...
(The trick with remembering the previous pixel's index still works, or you could use a k-d Tree to make it efficient.)
I love your content. If you allow me, here is a suggestion. You could implement an algorithm to find the path to the goal on the Micro Mouse Race.
I have two question: Can you use it for 3d scenes? Can you use it to speedup machine vision?
What watch are you wearing?
@4:31 Other ways to convert an array of x/y into a flat array of pairwise numbers:
const somePoints = [{x:1,y:2},{x:3,y:4},{x:5,y:6}];
const method2 = [];
somePoints.forEach(p => {
method2.push(p.x);
method2.push(p.y);
});
console.log(JSON.stringify(method2));
const method3 = somePoints.reduce((vec, p) => vec.concat([p.x, p.y]), []);
console.log(JSON.stringify(method3));
.forEach is quite a bit better than writing for loops. .reduce is for functional programming weenies, although it is admittedly cool and tends to be compact.
This looks like a great way to create something that can be fed to a pen plotter. I imagine a giant stipple plot of a picture of my cat :D
It's a translation of light and shadow with a circle radius variation.
Nice
This is actually part of Solid state Physics formulation of the K-Space for electrons
Would it be possible to use both diagrams and other algorithms shown in this video to let's say, triangulate a person's unknown position? I'm no spy nor stalker of any sort, just remembered I was addicted to tv series called Numbers which used Math to solve crimes (of course in Hollywood style, but you get the point).
My idea here is how Math can be used to almost anything in life, rather than drawing (which is awesome too).
oooooh man you are really crazy
Wow! Last week, I wrote a kinetic voronoi algorithm which doesn't require any triangularization
Could be a beautiful effect to transform from the totally distributed dots to those of the image.
He already did it with the logo at 0:09 and it looks so cool!
Okay but how? Simply the reversed process?
Yes I think so
Who ever decided on "ducks" at Columbia Collage was a genius, you'd have to be to pick an animal that just says quack all day long as they walk up and down the sidewalk.
Reminded me of Origami and Crease Pattern
I hope one of you train enthusiasts can answer this - how did you know the delaunay portion of the d3 library was available from the cdn (with that particular url)? I looked on the d3 site and I couldn't find the option of linking to just portions of the d3 libraries without using import statements etc. I much prefer your method of just putting it as a source in index.html, but don't know how to find that it exists? Great video!
I'm currently learning Apps Script for work as a Python person in private, and this video gave me violent flashbacks.
Can you help me find the utility and applications of this technique?