"Slime" <noo### [at] hotmailcom> wrote in message
news:3cbe1713$1@news.povray.org...
> > So I wonder, if there are other, more advanced algorithms out there,
which
> are
> > faster ...
>
> Here's an idea I just came up with.
>
> Do it just like you are. Except, as you place the spheres, keep the array
> that holds their positions *sorted*. So, when you add a new value to the
> array, use some sort of binary search to find the part of the array where
> the new position should be kept. (To sort the array, do something like
> sorting first in the X direction, and then in the Z direction.) Then
insert
> the new value there, pushing the rest of the values ahead.
>
> Then, when you have a new position, you still have to check the array to
> make sure it doesn't conflict with any of the positions already there.
> However, you no longer have to check the whole array - you only have to
> check the part of the array that's within twice the maximum possible
radius
> from the new position you're testing.
>
> It might be difficult to implement, but it might really speed it up. The
key
> thing here is to search the array with a binary search or something else
> that takes advantage of its sortedness.

this page http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html
has some very, very useful algorithms.
It's basically an on-line version on a book I have used many times. There's
a few sorting algorithms in section 8, but there's much more here as well.
Quite possibly, there are many people who've used this book, but the online
resource is nice.
I've posted the C version but it's also available in Fortran (the on I use).

jim

Post a reply to this message

"Slime" <noo### [at] hotmailcom> wrote:
> I have come up with an algorithm that, although it is still O(n^2), can
> place 16,000 spheres in, if I remember correctly, 13 minutes in the POV SDL.
> It gets faster, of course, when the spheres are less densely placed. In this
> example, about one out of every ten spheres needed more than one placement
> to find a place that didn't intersect with other spheres.

Sounds interesting ...

could you tell me the idea of the algo?

what are the test you do, and what are the constraints of the spheres placed ?

Post a reply to this message

> could you tell me the idea of the algo?


Sure. =)

Basically, I follow these steps, where n is the number of spheres needing
placement:
1. place n spheres randomly, ignoring collisions. Store their radii
separately.
2. sort the placement array by the X coordinate. I used mergesort.
3. for each element A in the array:
 - for each element B in the array that's after A:
 -- if A and B are too close to each other, abort the inner loop. A must be
replaced.
 -- if B's X coordinate is so far away from A that they can't possibly be
too close, abort the inner loop and continue to the next A.
 - (end inner loop)
 - if A needs to be replaced, keep trying random positions, until you find
one that doesn't conflict with any position already in the array. You can
make use of the sortedness of the array when testing these points for
collisions.

As more points are replaced, the algorithm slows down, since their new
positions have to be stored in a separate array, which isn't sorted. (They
can't remain in the original array, because keeping them in that would make
that array not sorted anymore.)

That's the gist of it.

- Slime
[ http://www.slimeland.com/ ]
[ http://www.slimeland.com/images/ ]

Post a reply to this message