 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"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
|
|
| |
| |
|
|
|
|
| |
