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