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