after some bug fixed and some optimization I have:
[b]nodes:10000
intersected:2258
time:489 ms
memory:80808L
[/b]same node set but other settings of the algorithm:
nodes:10000
intersected:2258
time:341 ms
memory:940472L
… it’s a little faster, but needs much more memory
Impressive results! I’m going to test my octree with the same settings later tonight. What is the average intersects lookup count for each node with your algorithm? And does it find all intersections?
It’s easy to guess that my algorithm is 3D grid based. The average lookup count depends on cell size. The algorithm finds all bbox intersections for sure.
With cellsize of 8 objects the best time I can achieve without any optimization of the code is ~14 seconds and with an average of 10 look ups per object. Doing the same without doing the intersection test, the time is ~12 seconds. Building the octree for 10000 objects takes ~1.5 seconds, doing 8 look ups for each object (1 for each bounding box point) is the time eater in my case, approx 10 seconds for 10000 objects.
Looks like you beat me pretty good
there are my numbers:
nodes:10,000
0) create nodes… time: 48594 ms (very slow!!! what is your time?)
- make 3D grid-buffer (20x20x20)… time: 213 ms
- compute intersections… time: 128 ms
complete time: 341 ms
With redraw and undo off it took 2334ms to create the 10k boxes.
Maybe I should try to implement a kd-tree, just to compare with the octree and your solution. From what I’ve seen, they do a pretty efficient radius based neighbour search. Maybe a bsp-tree could do well also. Many possibilities!
is it really 2.5 sec to create 10k boxes? against 48 sec on my machine…
could any one give your numbers, please?
gc()
t1 = timestamp()
for k=1 to 10000 do box()
format "time: %
" (timestamp() - t1)
From your snippet: 10021 ms.
I got an Intel core2 quad cpu Q6660 2.4ghz, it’s over 3 years old too!
Intel Xeon X5660 @ 2,80GHz: time: 5063
q6600 @ 2.4mhz time: 3955 (max 2011 sp2 x 64/ w7 x64)
I tried creating a kd-tree, but just building it for 10k objects took ~1.2 seconds if I remember correctly, so DenisT is still beating me hard : ) Can you post your solution?