Math help needed - packing algorithm


(poromaa) #1

Ok, So I have programmed a bit over the weekend to create a fast packing algoritm. What I want to achieve is a procedural version of below:


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).


same, but without above filtering


Any ideas?


(Secrop) #2

That would be the Holy Grail for procedural textures… :slight_smile:

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.


(RickyBlender) #3

is not there a way with particles random sizes and locations to get some circles like that ?
but overlapping or not
not certain at all !

happy bl


(poromaa) #4

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):


Will continue trying.


(poromaa) #5

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.


(poromaa) #6

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:


So, no overlapping. Now I just need to work on the filling some more.


(RickyBlender) #7

here is another idea why not make a dense mesh randomize the verts
and select some verts then add some circles with dupliverts

not certain if this would not be faster but distribution might not be the same then what you want I guess

if you find something let us know
it is an interesting problem

did you ask in python forum or the other forum blender stack?

happy bl


(Secrop) #8

@poromaa,

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.


(poromaa) #9

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.


(RickyBlender) #10

one problem is that the random gen in bl is probably not the one you need
so the quickest way to do it would be using python scripting I think!

also to be fast it has to be with less then let say around 1K circles
if higher it will get sluggish

happy bl


(poromaa) #11

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.



and a close-up

I think I will leave it at this for a moment - will dream about these fucking spheres… :eek:


(poromaa) #12


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.


(poromaa) #13




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!