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