Avoid Intersection of Objects Using Galapagos

Hi guys,

I am spreading objects randomly on a surface and would like to minimize intersecting ones using galapagos... I haven't found a way yet and was wondering if any of you would have an idea on how to do it ?

Below is an image of what I am getting.

Many thanks,

Arthur

Replies to This Discussion

Permalink Reply by David Rutten on June 28, 2011 at 4:28am

Hi Arthur,

you want to position each and every individual leaf so that the total number of intersections is minimized?

If so. Wow. You'll need 3 sliders per leaf (x-position, y-position & rotation) which would amount to -at a rough guess based on your image- about 1000 genes. I'm not sure how well Galapagos will be able to deal with such an amount (ironically the biggest problem will probably be the interface, not the solver algorithm).

The main theoretical problem I see is the fitness function definition for this. It won't be good enough to count intersections and minimize those. Reason being is that the number of intersections is an integer (it doesn't vary smoothly) and as such there's no 'selection pressure' towards better solutions. If you start with a setup like this:

it would have a 'fitness' of 2. We'd like to move these two shapes apart but even if we move them a large distance in the correct direction, we still have a fitness of 2:

It seems like a more useful metric would be the area of the overlap, at least then when leaves move apart, the fitness value will change, which allows the algorithm to make an informed decision.

Computing curve region intersections and areas will be a very intense step, making the whole process even slower than it already is. If I had to do this, I'd first try and tackle this using pixels, as computers are very good at dealing quickly with them. You could draw an image of all the shapes, drawing them each in a transparent black. Then, when two shapes overlap, the resulting pixel will be darker than the fill. If three shapes overlap it will be darker still. Then, once you've created the image, you could all the pixels and compute a value based on how many dark pixels there are.

This can probably be done in a reasonably low resolution, but you'd need to write some code to create and analyse the images.

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Arthur Mamou-Mani on June 28, 2011 at 5:11am

Thanks so much David! Amazing reply.

For the positioning of the leaves, I used a random component which defines the amount of leaves and generate values for x and y. The rotation is also done in a similar way.

I just tried using an intersect component between all the leaves and use Galapagos to minimize the list length. It's giving me some organized patterns, not sure if it is actually working:

Would there be a tool in GH that works with pixels already ? I will try this solution ASAP!

Thanks again,

Arthur

Attachments:

Pattern_.ghx, 782 KB

Permalink Reply by David Rutten on June 28, 2011 at 5:24am

You certainly won't be able to get away with a Random component. The only thing you can really 'mutate' is the seed, and there is no relationship between random seed and random numbers. Basically when you change the seed a little bit, the resulting random sequence will be utterly different. You really will need individual genes for every single variable in your problem.

I can write a small VB script that generates an image and counts pixels, that much I think is not too difficult. But you'll still need to remodel your network.

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Arthur Mamou-Mani on June 28, 2011 at 5:43am

I see, this is why I saw no progress in the "genomes".

I am going to have a massive definition :) I'll work on it tonight.

Should I still make the leaves as curves?

Many thanks!

Permalink Reply by David Rutten on June 28, 2011 at 6:47am

I wrote a small 'geometry to bitmap' script. It probably won't do what you need just yet, but it might be a good start.

ps. I made the bitmap black by default, it's somewhat easier to count this way as zero equals no shapes.

David Rutten

david@mcneel.com

Poprad, Slovakia

Attachments:

shape_pixel_statistics.ghx, 83 KB

Permalink Reply by David Rutten on June 28, 2011 at 7:18am

You'll also notice that the bitmaps appear to be upside down. That's because the y-axis in Rhino points upwards whereas the y-axis in the Windows graphics environment points downwards (0,0 is the top left corner of the page, not the bottom left corner). I didn't bother to add an additional transform to flip the geometry prior to drawing it because it doesn't matter in terms of counting pixels.

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Gwyll on June 29, 2011 at 7:43pm

Thanks for the vb component david. I had a go at doing some bitmap based object packing with your script and a function I found online for testing similarity between bitmaps and managed to get a proof of concept going, but unfortunately it is considerably slower than other methods of testing intersection/containment presumably because I have to create so many bitmaps. Could you suggest any ways to get around this bottlenecking?

Attachments:

bmp intersections.ghx, 59 KB

Permalink Reply by David Rutten on June 30, 2011 at 7:48am

Hi Gwyll,

testing circles for intersections is very cheap, just compute the distance between the center-points and if that distance is less than the sum of both radii, the circles intersect.

Your script is pretty big, I'll need to spend some time looking at it, but one think I've learned in the art of optimization is that when you use words like "presumably" you've already lost.

You need to add detailed performance tracking code to your script so that you know for a fact which operations(s) is/are taking the most time.

You can use the System.Diagnostics.Stopwatch class to very accurately measure time spend between two lines of code. Don't use DateTime.Now as it has a much coarser accuracy.

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Gwyll on June 30, 2011 at 6:23pm

Thanks david, Ill take a look. Should be able to substitute the circles for any other curve pretty easily. The scripts actually not too slow when its comparing small bitmaps (maximium size of the curve to pack stays quite small), it just gets very bogged down with larger comparisons.

Permalink Reply by Arthur Mamou-Mani on August 2, 2011 at 9:59am

Hi David,

Thank you so much for writing this script, I finally had a chance to work with it and it is very fast !

I have connected the "Empty" VB component output to the Galapagos fitness and the several U, V and Rotation Sliders to the Genome. Then I tried to Minimize and Maximize the results. Since the leaves get larger when their Z-Value are higher I thought I would get all the leaves stuck towards the bottom when maximizing the empty area and towards the top when minimizing it. Hereafter are the actual results I got:

Maximizing empty Area

Minimizing empty Area

Maximizing Weight

Minimizing Weight

When maximizing the empty area, the leaves stay in the center and when minimizing it, I still get some rebels at the bottom. When minimizing the weight (total occupancy), the leaves do not go towards the very bottom of the surface...

Would there an output in the AnalyseBitmap function which I could use to maximize black pixels?

Hope it all makes sense and thanks so much again!

Arthur

Attachments:

leaf Pattern.3dm, 47 KB
Leaf Pattern_Simplified.gh, 28 KB

Permalink Reply by Yoann Mescam (Systemiq) on June 28, 2011 at 6:01am

You could also try this (very) basic packing algorithm with hoopsnake (http://www.grasshopper3d.com/xn/detail/2985220:Comment:244292).

Permalink Reply by Christina Cogdell on August 1, 2011 at 2:40pm

Hi Arthur - I'm trying to learn how to use Galapagos and would love to see the full grasshopper file for the image you posted above, which cuts off the beginning and what comes after. I'm trying to see which components get fed into the genome section, and what you connect the fitness to. Any chance you can email me your grasshopper file for this image above, to christina.cogdell@gmail.com ? I can blow up the image enough also to see the names of the components you're using. Thanks! Christina

ps - the image i'm referring to is the very first one you posted in this thread, though if you got it to work for you in a later file i'd be curious to see that one too.