I'm working on some code to pack a number of objects - presumably 
vegetable-based, but I guess a person could pack anything they want - 
into a rectangular area. It uses arrays to store the locations of 
individual "trees", and tests randomly-placed trees against those 
already in the arrays to make sure that their "clear areas" don't 
overlap. A confidence value tells the code to give up and stop placing 
trees after a user-defined number of placement failures.

Because of the random nature of the code and the need to test against 
every other tree when placing a new one, scenes with a lot of trees take 
a long time to parse; the example below using "clear area = 4" took 31 
minutes on my Mac G4/867! I'm contemplating some kind of automatic 
bounding so the code only tests new trees against old trees in the same 
area, which should help more the more trees there are. Other planned 
improvements include the ability to use multiple patterns to affect the 
success of tree placement, the ability to have any number of "layers" of 
trees with different placement characteristics, and some kind of 
probability system using either a user-defined threshold or a random 
test to determine whether placement in an unlikely area (such as on a 
steep slope, or close to another tree) succeeds.

Whether I'll actually MAKE any of these improvements remains to be seen...

-Xplo

Post a reply to this message

Attachments:
Download 'forgenc16.png' (9 KB) Download 'forgenc8.png' (12 KB) Download 'forgenc4.png' (19 KB)

Preview of image 'forgenc16.png'

Preview of image 'forgenc8.png'

Preview of image 'forgenc4.png'

> Because of the random nature of the code and the need to test against 
> every other tree when placing a new one, scenes with a lot of trees take 
> a long time to parse; 
A way to improve this would be something like bounding boxes - divide 
the space you're filling into n*m rectangles, each with it's own array 
where the objects of that rectangle are stored.

#local Objects = array[CellsU][CellsV][MaxObjectsPerCell];

Of course you have to add an object which overlapps a border into both 
cells it touches.

And now please go on and find me the same packing algorithm you're 
writing, but only should it:
- use 3 dimensions instead of 2
- pack a certain amount of objects in as little space as possible
- use non-spherical (cylindrical would do) objects with a random
   rotation

Haven't got any idea how to do this (Apart from actually running it
through SimPOV, which would take years IMHO).
I'd already be happy if I found some algo which produces pseudo-correct 
results, where the cylinders would overlap (but nobody would notice).

Florian

Post a reply to this message

Xplo Eristotle wrote:
> Because of the random nature of the code and the need to test against 
> every other tree when placing a new one,

Sounds like you may be just running linearly through your array when 
trying to place a new tree. Inserting the tree in order, then finding 
the trees to test against via binary search might work better.

For example, order by X axis, do a binary search, and only compare with 
trees within a certain distance of the same X.

Or, if you can fit (say) 20 across and 20 high, make a 20x20 array and 
only check the nearby cells for possible trees.

-- 
Darren New, San Diego CA USA (PST)
   I am in geosynchronous orbit, supported by
   a quantum photon exchange drive....

Post a reply to this message

Florian Brucker wrote:

>> Because of the random nature of the code and the need to test against 
>> every other tree when placing a new one, scenes with a lot of trees 
>> take a long time to parse; 
> 
> A way to improve this would be something like bounding boxes - divide 
> the space you're filling into n*m rectangles, each with it's own array 
> where the objects of that rectangle are stored.

I plan to implement something like that, yes...

> #local Objects = array[CellsU][CellsV][MaxObjectsPerCell];

...but not like that. If I'm reading this right, I could accomplish the 
same effect right now by using multiple "forests" stitched together, 
which isn't what I want; the "clear areas" around trees in adjacent 
cells would overlap because those trees don't get checked against each 
other.

Instead, I would divide the area into sections and only check against 
the trees in the sections near where the new tree is trying to be 
placed. So for example, instead of checking tree #27 against trees 
#1-26, I would check the arrays for the section where #27 is going and 
the eight sections around it, and perhaps find that the only trees in 
those sections are #4, #5, and #21. Knowing this, the code would only 
check those trees, and ignore the others, since all of the others must 
be too far away to overlap.. am I making any sense?

> And now please go on and find me the same packing algorithm you're 
> writing, but only should it:
> - use 3 dimensions instead of 2
> - pack a certain amount of objects in as little space as possible
> - use non-spherical (cylindrical would do) objects with a random
>   rotation

The tighter this algorithm packs the objects, the longer it'll take, 
since you'll have to raise the confidence to absurd levels to ensure 
that they're packed as tight as they're going to get. I suppose if you 
really wanted to be thorough, you could have a second algorithm take 
over when the first one loses its confidence and walk a fine grid, 
testing each point on the grid to make sure something can't fit there; 
at some point this would be far more efficient than random placement 
that fails over and over again.

3D is easy. The math gets a little more complicated.

3D using cylinders is easy.. kinda. The math that tests for overlap gets 
even more complicated, but the algorithm basically stays the same.

3D using cylinders under the influence of gravity which not only moves 
the cylinders but also rotates them when they touch other objects.. 
you're on your own, pal. And you may want a sumpercomputer to run the 
simulation... ;)

-Xplo

Post a reply to this message

Xplo Eristotle wrote:

<snip/>

> Because of the random nature of the code and the need to test against 
> every other tree when placing a new one,

<snip/>

A more recursive, fractal approach might help cull the amount of trees 
you need to test against. How a "plasma" fractal is created might help 
you build the algorithm:

http://www2.vo.lu/homepages/phahn/fractals/plasma.htm

I think the "wrinkles" pattern in POV-Ray is a 3D representation of a 
plasma fractal (probabally uses a Gaussian (bell-curve) Distribution as 
well because I don't see "pyramids" in the pattern. Perhaps the POV-Ray 
code might help generate some ideas on this too?

-- 
Respectfully,
Dan P
http://<broken link>

Post a reply to this message

Dan P wrote:

> Xplo Eristotle wrote:
> 
>> Because of the random nature of the code and the need to test against 
>> every other tree when placing a new one,
> 
> A more recursive, fractal approach might help cull the amount of trees 
> you need to test against. How a "plasma" fractal is created might help 
> you build the algorithm:

I don't see what use this could possibly be. But then, it's possible 
that the math that would make its application obvious is over my head. 
*shrug*

-Xplo

Post a reply to this message

Xplo Eristotle wrote:

> Dan P wrote:
> 
>> Xplo Eristotle wrote:
>>
>>> Because of the random nature of the code and the need to test against 
>>> every other tree when placing a new one,
>>
>>
>> A more recursive, fractal approach might help cull the amount of trees 
>> you need to test against. How a "plasma" fractal is created might help 
>> you build the algorithm:
> 
> 
> I don't see what use this could possibly be. But then, it's possible 
> that the math that would make its application obvious is over my head. 
> *shrug*

It's a matter of finding a way to limit the size of your arrays by 
slicing the the scene up into smaller and smaller cubes by using 
recursion to some pre-defined limit.

-- 
Respectfully,
Dan P
http://<broken link>

Post a reply to this message

can i show mine?
i did this ages ago, and was planning to make some improvments to my 
otherwise totally brute force method, but i was pleased enough with the 
final image anyway. Sorry, i've probably lost the source, but i could 
have a dig around for it.
(in the top left panel, n is the number os dots, parse is the time it 
took to parse in seconds, i think, and bail is the amount of times it 
has failed and then bailed out to start rendering. Jeepers - it looks 
like this one took around 7 hours to generate!)
benp


Xplo Eristotle wrote:
> I'm working on some code to pack a number of objects - presumably 
> vegetable-based, but I guess a person could pack anything they want -

Post a reply to this message

Attachments:
Download 'hwdistributions3b.jpg' (34 KB)

Preview of image 'hwdistributions3b.jpg'

and...

bp wrote:
> can i show mine?
> i did this ages ago, and was planning to make some improvments to my 
> otherwise totally brute force method, but i was pleased enough with the 
> final image anyway. Sorry, i've probably lost the source, but i could 
> have a dig around for it.
> (in the top left panel, n is the number os dots, parse is the time it 
> took to parse in seconds, i think, and bail is the amount of times it 
> has failed and then bailed out to start rendering. Jeepers - it looks 
> like this one took around 7 hours to generate!)
> benp
>

Post a reply to this message

Attachments:
Download 'hwdistributions3_reallyfine.jpg' (55 KB)

Preview of image 'hwdistributions3_reallyfine.jpg'

Now the second one rocks! Can't see the parsing time properly, but it 
must have been quite some days :)

Florian

Post a reply to this message

Xplo Eristotle wrote:
> Florian Brucker wrote:
> 
>>> Because of the random nature of the code and the need to test against 
>>> every other tree when placing a new one, scenes with a lot of trees 
>>> take a long time to parse; 
>>
>>
>> A way to improve this would be something like bounding boxes

> I plan to implement something like that, yes...

> ...but not like that. If I'm reading this right, I could accomplish the 
> same effect right now by using multiple "forests" stitched together, 
> which isn't what I want; the "clear areas" around trees in adjacent 
> cells would overlap because those trees don't get checked against each 
> other.

> Instead, I would divide the area into sections and only check against 
> the trees in the sections near where the new tree is trying to be 
> placed. 
> .. am I making any sense?

That's what I tried to say with

 >> Of course you have to add an object which overlapps a border into
 >> both cells it touches.

:)

> I suppose if you 
> really wanted to be thorough, you could have a second algorithm take 
> over when the first one loses its confidence and walk a fine grid, 
> testing each point on the grid to make sure something can't fit there; 
> at some point this would be far more efficient than random placement 
> that fails over and over again.

I think a totally random approach might be a really bad idea. I thought 
more along the terms of "Take a set of cylinders which is in perfect 
order. Now find some random translations which can be applied on each 
cylinder so that the set looks totally random with as little 
intersections as possible".

> 3D is easy. The math gets a little more complicated.
Yep

> 3D using cylinders is easy.. kinda. The math that tests for overlap gets 
> even more complicated, but the algorithm basically stays the same.
Sure the tests get more complicated. While you can simply compare the 
radius with the distance of two spheres, you have to take the direction 
of the main-axis into account when dealing with cylinders. It would not 
only be harder to implement, it would also take longer to parse :(

> 3D using cylinders under the influence of gravity which not only moves 
> the cylinders but also rotates them when they touch other objects.. 
Yep. That would be the best result of course :)

> And you may want a sumpercomputer to run the 
> simulation... ;)
Got one? Hehe.

I once started trying simulating it with SimPOV, but I couldn't get it 
to work properly. Perhaps I'll try again.

Florian

Post a reply to this message

cheers! i'd love to get back to it one day.
i think it says it took 21 hours to parse! (the unit is in seconds..)
bp

Florian Brucker wrote:
> Now the second one rocks! Can't see the parsing time properly, but it 
> must have been quite some days :)
> 
> Florian
>

Post a reply to this message

Hi bp,

I've just written a 'bins' based algorithm - it creates sorted lists of 
points in a grid of bins. When you want to add a new point it looks in 
the appropriate bin or bins to see if any of the current points are 
within a given distance of the new point.

Like yours, this image places 6000 spheres. You don't say what the area 
size or the clearance radius is for yours, but the total number of tries 
is similar enough to mine that the two can be compared.

That said, mine took a little less time to parse - using official PoVWin 
3.5 on my 1Ghz Athlon it was 149 seconds! :-)

The most efficient bin size for the algorithm seems to be about four 
times the radius - trade off between length of list in each bin and 
having to look in multiple bins more often ...

I can post the code if anyone wants to have a look.

Mike Andrews.

<message_pane>
Scene contains 6228 frame level objects; 1 infinite.

Statistics for C:\Program Files\POV-Ray for Windows 
v3.5\scenes\array_fill.pov, Resolution 512 x 384
----------------------------------------------------------------------------
Pixels:          197120   Samples:         1055304   Smpls/Pxl: 5.35
Rays:           1055304   Saved:                 0   Max Level: 1/5
----------------------------------------------------------------------------
Ray->Shape Intersection          Tests       Succeeded  Percentage
----------------------------------------------------------------------------
Box                            1447721          880053     60.79
Cone/Cylinder                   379689           12704      3.35
Plane                          1684004         1055304     62.67
Sphere                         2021823          917211     45.37
True Type Font                   59885           30964     51.71
Bounding Box                   8636084         3431631     39.74
Light Buffer                  32225595        10986256     34.09
Vista Buffer                  33004346        19147603     58.02
----------------------------------------------------------------------------
Function VM calls:          445244
----------------------------------------------------------------------------
Calls to Noise:                  0   Calls to DNoise:             10
----------------------------------------------------------------------------
Shadow Ray Tests:          1350653   Succeeded:               198742
----------------------------------------------------------------------------
Smallest Alloc:                 25 bytes   Largest:            49840
Peak memory used:          7897321 bytes
----------------------------------------------------------------------------
Time For Parse:    0 hours  2 minutes  29.0 seconds (149 seconds)
Time For Trace:    0 hours  0 minutes  13.0 seconds (13 seconds)
     Total Time:    0 hours  2 minutes  42.0 seconds (162 seconds)
----------------------------------------------------------------------------
CPU time used: kernel 29.69 seconds, user 131.26 seconds, total 160.95 
seconds
Render averaged 1221.54 PPS over 196608 pixels

POV-Ray finished
</message_pane>

Post a reply to this message

Attachments:
Download 'array_fill.jpg' (53 KB)

Preview of image 'array_fill.jpg'

For tree "packing" algorithm I would suggest examining this ...

http://www.gingerbooth.com/courseware/pages/demos.html

Especially ...

http://www.cbc.yale.edu/courseware/woods.html

There is a lot of documentation and source code.
Seems a lot more realistic than 2D overhead packing that
relies on only perimeter intersection checking.

Post a reply to this message