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'
![array_fill.jpg](/povray.binaries.images/attachment/%3C406c53e1%40news.povray.org%3E/array_fill.jpg?preview=1)
|