Does anyone have any idea of how to achieve this distribution - eg no overlapping circles, still random. Don’t mind the colors (not important).
Also, Since I wan’t it to be procedural and quite fast I can’t afford doing a real packing algoritm here, rather it has to be distributed in ordo(n^2) or something.
So far, this is what I have acomplished - no variation in scaling, just remove overlapping ones (by checking if the one I will put on the canvas overlaps the right one, the bottom-left, bottom or the bottom-left, assuming filling from left to right bottom-up).
That would be the Holy Grail for procedural textures…
I never heard of any algorithm able to do anything like it. The closest approach I’ve seen (from sketching patterns), is to continue to place circles wherever there’s an empty area where a circle fits in, until there are no more valid spaces. (And this is way above n[SUP]2[/SUP]!!!)
You can try with true Voronoi/Delaunay, and use the triangle centers for the circles, but I doubt it’s going to look like what you want.
Well, seems like the original packing problem is NP-complete… Anyway, I don’t think this is the same thing since, we are allowed to set the size of each sphere when placing it. I think there might be a solution… so far still n^2 (by using modulo over the voronoi):
Yes, by iterating over the whole surface plotting random circles, but only keeping the ones not overlapping earlier is one way. You then iterate a finite set of times with different size-circles to fill the thing.
This approach will become quite slow compared to my voronoi version above which runs in O(n) (where n is number of circles).
I will keep working on the fast version a bit. Intuitively, it feels like there should be a solution using the voronoi as a scale-map eg. black is large balls and white is small, and with some resolution/constant get it to look similar to the color-blind-thing.
Ok. So I have made som research into this and this problem is quite known. Reading some math papers, the distributions to get dense filling without overlapping is a bit complex. Usual methods involves random distribution, which would be too slow for this case I believe. Instead I have done som filler-functions that finds empty space and inserts ball there. Not really satisfied, since I want to create the color-blind pattern. But my result is this so far:
RickyBlender has a point here… which on the other hand remind me of something… Do you really need for the whole calculation to be in the shader??
Because it would be simpler if you could solve the packing stuff with python, store the coordinates and radius into a text file or a point cloud, and read these in the shader.
Unfortunately I can’t solve the problem outside the shader, because all this struggle is to create a new type of procedural material that I think could be very useful. Didn’t think this would be that hard…
My current approach is quite neat though and fast (so far). Still have some ideas I want to try. Will keep posting my results here.
I still have some outstandings where i don’t limit random distribution between voronoi-sectors . These circles will be halves. Can bee seen all over the place. To solve this artifact, I need to make a “fence” that will limit these sphere’s radius.
Anyways, 8.4 sec rendering of about 10 000 spheres.
Im done! I still have some ideas of how to improve this and my code is a spaghetti monster , but for now this suffice. No half-circles and quite dense, and quite randomized and also very quick.
*edit:
(also the aquarell dots is a 4x4 grid of unique dots that are “randomly” distributed). Since I work with genereating Uv-maps instead of manipulating actual textures this gets very generic.
Some behind the scenes of above, and the real tightness of pattern even though it becomes more sparse when adding sprites to it. My best osl-shader so far!
