 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
OK ... I finished one of these 0PPS-pictures, and went on to my next POV-project ...
I'm working on something like the clutter-macro, we've already seen here ...
At least, I want to place a lot objects (currently spheres) in the scene (currently
on a surface, so its 2D) without intersection ...
currently I use the simple, dumb, standard algorithm, that checks for every new
sphere, if theres another one already placed, which would intersect. If so, then
I calculate another position, until I find a free place ...
The thing is, that this algorithm works in O(n^2) which means it can get quite slow
in POV-SDL (of course, not only SDL). Currently for an instance of n=10,000 I have
a parse-time of ~40mins, and I want to go even higher for n.
So I wonder, if there are other, more advanced algorithms out there, which are
faster ...
I thought about doing something like putting the spheres in boxes and only test
for the spheres, that are in the current and the adjacent boxes. This would save
the time to test EVERY other sphere, but would add some overhead for small number
of objects ...
So, has anyone done something like that already, or is there interest in such a
macro or at least testresults ?
If you are interested, I could do some tests when I have some time, but don't
count on this beeing soon ...
-- Jan
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
If the spheres are very tight to each other then jittering is the keyword: instead of
true pseudo-casual (forgive the oxymoron) positions you put your spheres through a
loop, then translate each position by a little random amount.
Otherwise dividing your Universe into boxes and checking the adjacent boxes only
should speed things of course. Try also this: if a position fail don't trash it but
try and translate that by a little amount (for example the diameter of the sphere) in
the four directions. You could use the number of spheres already in the box as
indicator of the probability (so the feasibility) of success of these translations.
--
Jonathan.
Home: http://digilander.iol.it/jrgpov
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
But also small translation (or jittering) of the sphere would involve
a complete check of all other spheres if I don't do anything else...
Maybe I could (after I detected some collisions) save the nearest ones
and only check these ones ...
But I found a problem in my other approach. Does POV-Ray support some-
thing like chained-lists efficiently ? I don't know, how to find out,
if I have a given box, which of my thousands spheres are in that very
one box.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Jan Walzer" wrote:
> But also small translation (or jittering) of the sphere would involve
> a complete check of all other spheres if I don't do anything else...
> Maybe I could (after I detected some collisions) save the nearest ones
> and only check these ones ...
Usually jittering is done in such way to make it impossible to have intersections.
That would make it a O(0)... ;-)
If R is the radius of the sphere you're placing and 1/L^2 is the density you want to
get (x_step=L, z_step=L) then you can translate your sphere by L/2-R maximum in any
direction. That should prevent any intersection, and yet make it possible to have
spheres touching each other.
Of course L>=2*max(Ri)i=1,2,...n.
> But I found a problem in my other approach. Does POV-Ray support some-
> thing like chained-lists efficiently ? I don't know, how to find out,
> if I have a given box, which of my thousands spheres are in that very
> one box.
I did it once. IIRC it was a real puzzle, I began to meet arrays in my not so quiet
dreams... :-|
--
Jonathan.
Home: http://digilander.iol.it/jrgpov
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"JRG" <jrg### [at] hotmail com> schrieb im Newsbeitrag news:3cbc95a6@news.povray.org...
> "Jan Walzer" wrote:
> > But also small translation (or jittering) of the sphere would involve
> > a complete check of all other spheres if I don't do anything else...
> > Maybe I could (after I detected some collisions) save the nearest ones
> > and only check these ones ...
>
> Usually jittering is done in such way to make it impossible to have intersections.
> That would make it a O(0)... ;-)
> If R is the radius of the sphere you're placing and 1/L^2 is the density you want to
> get (x_step=L, z_step=L) then you can translate your sphere by L/2-R maximum in any
> direction. That should prevent any intersection, and yet make it possible to have
> spheres touching each other.
> Of course L>=2*max(Ri)i=1,2,...n.
lets see, if I understood this correct ...
You say, that I should first place all the spheres in a grid, and then jitter this
to make a random distribution ? ... sounds interesting ...
My current approach is, that I select a random point in the area, and compute
the size of the sphere (currently the size of the sphere depends from a function, so
I have a bit control about the size)...
Then I look through an array of the already positioned spheres and if there's
another sphere intersecting, then I look for another place ...
> > But I found a problem in my other approach. Does POV-Ray support some-
> > thing like chained-lists efficiently ? I don't know, how to find out,
> > if I have a given box, which of my thousands spheres are in that very
> > one box.
>
> I did it once. IIRC it was a real puzzle, I began to meet arrays in my not so quiet
> dreams... :-|
that doesn't sound nice ... you mean I should leave this to an external program ?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Jan Walzer" wrote:
>
> lets see, if I understood this correct ...
>
> You say, that I should first place all the spheres in a grid, and then jitter this
> to make a random distribution ? ... sounds interesting ...
Ideally. In fact you jitter the spheres as you place them. You should come up with
something like:
#declare N = 400;
#declare L = 0.3+1; //max_radius + epsilon
#declare RS = seed (123);
union {
#local i=0;
#while (i<sqrt(N))
#local j=0;
#while (j<sqrt(N))
#declare RADIUS = 0.1+0.2*rand(RS); // your function here
sphere {
0,RADIUS
translate <i*L -(L/2-RADIUS)+2*(L/2-RADIUS)*rand(RS), RADIUS, j*L -
(L/2-RADIUS)+2*(L/2-RADIUS)*rand(RS)>
pigment {rgb 1}
}
#local j=j+1;
#end
#local i=i+1;
#end
}
The pitfall of this approach is that not always it's that easy to get a reasonably
random look (you can try increasing the maximum translation amount till you can
observe clear intersections).
There's almost no parsing time...
> > I did it once. IIRC it was a real puzzle, I began to meet arrays in my not so
quiet
> > dreams... :-|
>
> that doesn't sound nice ... you mean I should leave this to an external program ?
You mean an external language (like C)? That would make it faster and simpler, but
you would lose flexibility.
--
Jonathan.
Home: http://digilander.iol.it/jrgpov
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"JRG" wrote:
> #declare N = 400;
> #declare L = 0.3+1; //max_radius + epsilon
Oops, as I said that should be:
#declare L = 2*max_radius+ delta;
No real harm done here. It's like:
#declare L = 2*0.3 + 0.7;// 2*max_radius + epsilon.
--
Jonathan.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Tue, 16 Apr 2002 19:26:01 +0200, "Jan Walzer" <jan### [at] lzernet>
wrote:
>So I wonder, if there are other, more advanced algorithms out there, which are
>faster ...
Use an oct-tree like POV does for bounding slabs.
Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG e-mail : pet### [at] tagpovrayorg
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Jan Walzer" <jan### [at] lzernet> schrieb im Newsbeitrag
news:3cbc990e@news.povray.org...
> You say, that I should first place all the spheres in a grid, and then
jitter this
> to make a random distribution ? ... sounds interesting ...
And it works very well. Look in p.b.i for my test render of 50.000 spheres.
I made a array of 500x500 squares. In every square there can only be 1
sphere. After detecting a free square I translated the sphere randomly
within the square and marked the square as loaded. That's it. Here is some
code:
// Initialising the array
#declare gitter = array[501][501];
#declare array_help_x = 0;
#declare array_help_z = 0;
#while (array_help_x < 501)
#while (array_help_z < 501)
#declare gitter[array_help_x][array_help_z] = 0;
#declare array_help_z = array_help_z + 1;
#end
#declare array_help_x = array_help_x + 1;
#declare array_help_z = 0;
#end
#declare i = 1;
#declare zufall = seed(123456);
#while (i < 50000)
// Find a square to start
#declare neu_x = floor(500*rand(zufall)+0.5);
#declare neu_z = floor(500*rand(zufall)+0.5);
// If the square is loaded, find another one
#while (gitter[neu_x][neu_z] = 1)
#declare neu_x = floor(500*rand(zufall)+0.5);
#declare neu_z = floor(500*rand(zufall)+0.5);
#end
// Mark the square as loaded
#declare gitter[neu_x][neu_z] = 1;
// Random radius
#declare neu_radius = 0.5*rand(zufall);
// Creating the sphere
sphere
{
<neu_x+2*(0.5-neu_radius)*rand(zufall)-(0.5-neu_radius),
neu_radius, neu_z+2*(0.5-neu_radius)*rand(zufall)-(0.5-neu_radius)>,
neu_radius
texture
{
pigment
{
color rgb <1, 1, 0>
}
}
}
#declare i = i + 1;
#end
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
yeah ... interesting technique ...
how well will this work with
different sized spheres ?
would this mean that I have to
mark some adjacent boxes as
loaded ?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Peter Popov" <pet### [at] vipbg> wrote:
>
> >So I wonder, if there are other, more advanced algorithms out there, which are
> >faster ...
>
> Use an oct-tree like POV does for bounding slabs.
in POV-SDL ? ...
I've thought about this, but I dunno how I could
do this, if I haven't some kind of "references"
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Jan Walzer" <jan### [at] lzernet> schrieb im Newsbeitrag
news:3cbd317a$1@news.povray.org...
> yeah ... interesting technique ...
Thanx, I did it that way, because I never used trace() before :-)
> how well will this work with
> different sized spheres ?
Good, it actually does. Look again at p.b.images ;-) The size of the sphere
radius is a random number between half of square size and 0.
> would this mean that I have to
> mark some adjacent boxes as
> loaded ?
Not in my approach. But your idea should also work, but is more complicated.
You have to have
a bigger array which is a lot slower. The advance of your approach is that
there is no free space in form of a square around a sphere:
+--------+
| |
| |
| |
| O |
+--------+
If I put a sphere into a square like above, no other sphere can be put into
this
square, even if there is enough space left. That means that you never will
fill the whole place totally. As long, as you have small amounts of spheres
(e.g. 50000) compared to the highest amount of spheres (e.g. 250000) that
fits in the array (e.g. 500x500), the result will be o.k.
So long,
Bonsai
P.S. If my englisch explanation is not clear enough, you can also mail me
directly to switch over to German ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"JRG" <jrg### [at] hotmailcom> wrote:
> Usually jittering is done in such way to make it impossible to have intersections.
> That would make it a O(0)... ;-)
BTW: I just read your text again...
O(0) is not possible for any real algorithm ...
O(1) is for normal cases the lowest you can get ...
and your algorithm is
O(n) when n is number of spheres ...
... just some nitpicking ...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Jan Walzer <jan### [at] lzernet> wrote in message
news:3cbc5eab@news.povray.org...
I wouldn't consider myself an advanced user, but I do have a suggestion.
I would cover the viewing area in rows of boxes with a random x and z size
within a range. I would then randomly select the number of balls to be
placed in each box and place the balls as I go, checking for intersections
within this small box. I think that this would give the best pseudo-random
look in the least amount of time.
-Shay
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <3cbd31c0$1@news.povray.org>, "Jan Walzer" <jan### [at] lzernet>
wrote:
> in POV-SDL ? ...
>
> I've thought about this, but I dunno how I could
> do this, if I haven't some kind of "references"
You can use unions to group objects, and you can put unions inside
unions.
Assuming you have a line of 16 objects like this:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P
Split it into two groups, put each into a union and make a union of the
unions. Split each sub-union the same way.
The resulting structure would be like:
union {
union {
union {
union {A, B},
union {C, D}
},
union {
union {E, F},
union {G, H}
}
},
union {
union {
union {I, J},
union {K, L}
},
union {
union {M, N},
union {O, P}
}
}
}
This basically makes POV do a binary search through the objects instead
of brute-force testing all of them. I used a line for simplicity, but
the technique could be used for 2D and 3D grids or other structures.
--
Christopher James Huff <chr### [at] maccom>
POV-Ray TAG e-mail: chr### [at] tagpovrayorg
TAG web site: http://tag.povray.org/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Sorry, but I don't get, how this could
help me with my current problem. Maybe
because its a bit late already... Give
me the chance to sleep about this idea
,but I doubt that this union-structure
will help me very much with a good way
to test for intersections.
What I want to to is to compute all of
the positions in SDL before postioning
them. But to do this efficient I think
I need something like references to be
able to create list or tree structures
like they are common in other programm-
ing languages.
It could be able to create such things
with the help of some arrays and a lot
macros. But the overhead would be more
than neccesary and the efficiency gets
lost, so it would no longer be faster
than my current approach...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Jan Walzer" wrote:
>
> "JRG" <jrg### [at] hotmailcom> wrote:
> > Usually jittering is done in such way to make it impossible to have
intersections.
> > That would make it a O(0)... ;-)
>
> BTW: I just read your text again...
>
> O(0) is not possible for any real algorithm ...
I was referring to the intersection testing algorithm alone, not to the placing
algorithm as a whole... no test, no algorithm, no operations, nada de nada... hence
the O(0) which, anyway, was just a joke... :)
--
Jonathan.
Home: http://digilander.iol.it/jrgpov
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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.
- Slime
[ http://www.slimeland.com/ ]
[ http://www.slimeland.com/images/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 17 Apr 2002 10:26:41 +0200, "Jan Walzer" <jan### [at] lzernet>
wrote:
>in POV-SDL ? ...
Supposedly :)
>I've thought about this, but I dunno how I could
>do this, if I haven't some kind of "references"
You can make a binary tree with a one-dimensional array. The extension
to oct-trees should be straightforward.
Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG e-mail : pet### [at] tagpovrayorg
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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.
I'm rendering now, I can post the source or the steps to the algorithm when
it's done, if you like. Might be a while... with focal blur and media, it's
going at 2 pps along the horizon line; so expect at least another day.
- Slime
[ http://www.slimeland.com/ ]
[ http://www.slimeland.com/images/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"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
|
|
| |
| |
|
|
|
|
| |
|
|
