Inspired by a post I made to another group, I thought if I could find
a fast way to create a large amount of randomly-placed spheres on a plane
so that they don't intersect each other.

  In these images I created 5000 spheres randomly placed inside an area
between <-10, 0, -10> and <10, 0, 10>. The locations of each sphere is
individually calculated with just a honest
MinCoords+(MaxCoords-MinCoords)*<rand(Seed), 0, rand(Seed)>
ie. no cheating by creating repeating patterns which just look random
or anything. The location of each sphere is honestly calculated by
with that line.

  In the first image the radius of the spheres is 0.2 and it took
17 seconds to parse in my P4 3.4GHz. In the second image the radius
is 0.23 and it took a lot longer because the space fills faster and
it's harder to find places for new spheres: 2 minutes 44 seconds.

  The naive way of doing this (which I posted in that another group)
took more than 7 minutes to place the spheres of radius 0.2 (compared
to the 17 seconds of my optimized method). I don't know how much longer
than 7 minutes it is because I got bored of waiting and stopped it.

  The scene which created these images is 76 lines long (written in
a nice, indented way, no obfuscation nor artificial shortening, and
it even prints its progress during the calculations).

  If you want a small challenge, try replicating this result.

Post a reply to this message

Attachments:
Download 'randspheres_radius0.2.jpg' (160 KB) Download 'randspheres_radius0.23.jpg' (164 KB)

Preview of image 'randspheres_radius0.2.jpg'

Preview of image 'randspheres_radius0.23.jpg'

That's neat. Would it be much more difficult to put them on the surface of a 
sphere rather than a plane? And what if you want to make sure that they are 
as equally spaced as possible -- that they sort of repel each other. I bet 
that would take longer.

Post a reply to this message

Anthony D'Agostino wrote:
> Would it be much more difficult to put them on the surface of a 
> sphere rather than a plane?

   Not really. It would even be as fast to calculate (well, approximately
at least).

> And what if you want to make sure that they are 
> as equally spaced as possible -- that they sort of repel each other.

   That would be a bit more complicated and naturally will take longer.

Post a reply to this message

Warp wrote:

>   Inspired by a post I made to another group, I thought if I could find
> a fast way to create a large amount of randomly-placed spheres on a plane
> so that they don't intersect each other.

When faced with this problem, I usually take the easy way out and put 
them into rows and columns, with jitter to make it look random.

Regards,
John

Post a reply to this message

Oops, I had an error in my description: It was the *diameter*, not
the radius of the spheres which were 0.2 and 0.23.

   Anyways, with a small change I got the time for the spheres of
diamater 0.2 reduced to 15 seconds and the time for the ones of
diamater 0.23 to 1:50.

Post a reply to this message

John VanSickle wrote:
> When faced with this problem, I usually take the easy way out and put 
> them into rows and columns, with jitter to make it look random.

   But as I said, I don't use any fakery. The location of every single
sphere is calculated randomly accross the entire area. :)

Post a reply to this message

Hi Warp,

Here's the result from a file I set up a while ago, using your radii.

On a P3, 933MHz the parsing for the 0.1 radius was 41s, for the 0.115 
radius it was 10m20s (620s).

I wonder if we're using the same technique ...

Mike.

Warp wrote:
>   Inspired by a post I made to another group, I thought if I could find
> a fast way to create a large amount of randomly-placed spheres on a plane
> so that they don't intersect each other.
> 
>   In these images I created 5000 spheres randomly placed inside an area
> between <-10, 0, -10> and <10, 0, 10>. The locations of each sphere is
> individually calculated with just a honest
> MinCoords+(MaxCoords-MinCoords)*<rand(Seed), 0, rand(Seed)>
> ie. no cheating by creating repeating patterns which just look random
> or anything. The location of each sphere is honestly calculated by
> with that line.
> 
>   In the first image the radius of the spheres is 0.2 and it took
> 17 seconds to parse in my P4 3.4GHz. In the second image the radius
> is 0.23 and it took a lot longer because the space fills faster and
> it's harder to find places for new spheres: 2 minutes 44 seconds.
> 
>   The naive way of doing this (which I posted in that another group)
> took more than 7 minutes to place the spheres of radius 0.2 (compared
> to the 17 seconds of my optimized method). I don't know how much longer
> than 7 minutes it is because I got bored of waiting and stopped it.
> 
>   The scene which created these images is 76 lines long (written in
> a nice, indented way, no obfuscation nor artificial shortening, and
> it even prints its progress during the calculations).
> 
>   If you want a small challenge, try replicating this result.
> 
>

Post a reply to this message

Attachments:
Download 'array_fill1.jpg' (69 KB) Download 'array_fill2.jpg' (67 KB)

Preview of image 'array_fill1.jpg'

Preview of image 'array_fill2.jpg'

"Warp" <war### [at] tagpovrayorg> wrote in message 
news:446997bb$1@news.povray.org...
>    Oops, I had an error in my description: It was the *diameter*, not
> the radius of the spheres which were 0.2 and 0.23.
> 
>    Anyways, with a small change I got the time for the spheres of
> diamater 0.2 reduced to 15 seconds and the time for the ones of
> diamater 0.23 to 1:50.

quite a difference :)

best I could come up with, is more or less the naive way, where I, in a 
way, let POV-Ray itself check the intersections, instead of doing the 
checks in POV-SDL:

-- begin code --
camera {
 location <1,8,4>*2
 look_at 0
}
light_source {<75,180,500> rgb 1}
#declare Seed=seed(354);
#declare MinCoords=<-10,0,-10>;
#declare MaxCoords=<10,0,10>;
#macro Location()
 #local R=MinCoords+(MaxCoords-MinCoords)*<rand(Seed), 0, rand(Seed)>;
 R
#end
#declare TestTexture=sphere {MaxCoords*10,.01}

#declare Count=5000;
#declare Radius=.1;

#while (Count>0)
 #local Loc=Location();
 #if (inside(TestTexture,Loc)=0)
  sphere {Loc,Radius pigment {rgb <rand(Seed),rand(Seed),rand(Seed)>} 
finish {ambient .25 specular 1}}
  #declare TestTexture=union {object{TestTexture} sphere 
{Loc,Radius*2}}
  #declare Count=Count-1;
  //#debug concat(str(Count, 0, 0)," to go\n")
 #end
#end
-- end code --

takes 1'30" for a diameter of .2 and 6'51" for a diameter of .23

(but I only have an athlon xp 2500+ :))

cu!
-- 
#macro G(b,e)b+(e-b)*C/50#end#macro _(b,e,k,l)#local C=0;#while(C<50)
sphere{G(b,e)+3*z.1pigment{rgb G(k,l)}finish{ambient 1}}#local C=C+1;
#end#end _(y-x,y,x,x+y)_(y,-x-y,x+y,y)_(-x-y,-y,y,y+z)_(-y,y,y+z,x+y)
_(0x+y.5+y/2x)_(0x-y.5+y/2x)            // ZK http://www.povplace.com

Post a reply to this message

Zeger Knaepen wrote:

> 
> takes 1'30" for a diameter of .2 and 6'51" for a diameter of .23
> 
> (but I only have an athlon xp 2500+ :))
> 
Ran it on an Athlon dualcore 3800 (64bit Linux)
33 sec for 0.2 diameter
230 sec for 0.23 diameter
-- 
Ger

Post a reply to this message

"Ger" <No.### [at] ThankYou> wrote in message 
news:4469c92d@news.povray.org...
> Zeger Knaepen wrote:
> 
> > 
> > takes 1'30" for a diameter of .2 and 6'51" for a diameter of .23
> > 
> > (but I only have an athlon xp 2500+ :))
> > 
> Ran it on an Athlon dualcore 3800 (64bit Linux)
> 33 sec for 0.2 diameter
> 230 sec for 0.23 diameter

hmm, huge difference, I think it's time for a new pc :)

cu!
-- 
#macro G(b,e)b+(e-b)*C/50#end#macro _(b,e,k,l)#local C=0;#while(C<50)
sphere{G(b,e)+3*z.1pigment{rgb G(k,l)}finish{ambient 1}}#local C=C+1;
#end#end _(y-x,y,x,x+y)_(y,-x-y,x+y,y)_(-x-y,-y,y,y+z)_(-y,y,y+z,x+y)
_(0x+y.5+y/2x)_(0x-y.5+y/2x)            // ZK http://www.povplace.com

Post a reply to this message

Hi Warp,

I like your smart programming.

But here is my question:

Let's say, I intend to place a ramdom-generated pattern of spheres (such as 
yours) on an unequal surface (maybe a heightfield or a union of objects). 
How, then, would the code look alike? Can you help me?

Greetings,

Sven

Post a reply to this message

Sven Littkowski wrote:
> Let's say, I intend to place a ramdom-generated pattern of spheres (such as 
> yours) on an unequal surface (maybe a heightfield or a union of objects). 

   My method can actually be used for any distributions of spheres,
not just a plane. You only have to come up with a formula which
calculates a random placement for the spheres in whatever shape
you want (eg. the surface of an object). Of course with certain
shapes calculating an even distribution may not be as trivial
as a simple <rand(S), rand(S), rand(S)> (for example distributing
points about evenly on the surface of a sphere requires a function
slightly more complicated).
   If you want to place spheres on the surface of an object you'll
have to use trace to get points on that object and figure out a
way to distribute these points approximately equally on the surface
of the whole object (with a spherical surface it's rather easy but
with other more irregular surfaces it can be more difficult).

> How, then, would the code look alike? Can you help me?

   The naive approach is to simply store the locations of the spheres
already created in an array and then when a new sphere is created,
check it against each coordinate in this array (iow. check if the
center of the sphere you just created is closer than the diameter
of the sphere to any of the coordinates in the array; if it is closer
to any of the points, then it's not ok and you have to create another
location for the new sphere; after you successfully create it, add
its center coordinates to the array).

   My optimized method uses this basic approach but I figured out a
rather simple way of speeding up the check a *lot*.
   The good thing about this approach is that you can have *any*
distribution for the spheres you like (eg. on the surface of any
object or whatever), and this algorithm will never produce spheres
which are intersecting.

   I can post a description of my simple method in povray.general if
people are interested. (It's probably nothing new and other people
have probably already thought of it, but perhaps my specific approach
is more resource-friendly than most other attempts.)

Post a reply to this message

"Warp" <war### [at] tagpovrayorg> wrote in message 
news:446997bb$1@news.povray.org...
>   Oops, I had an error in my description: It was the *diameter*, not
> the radius of the spheres which were 0.2 and 0.23.
>
>   Anyways, with a small change I got the time for the spheres of
> diamater 0.2 reduced to 15 seconds and the time for the ones of
> diamater 0.23 to 1:50.

Well I've got 15 seconds for the 0.2 diameter spheres, but I'm currently up 
at 3 minutes 53 seconds for  the 0.23 diameter ones (on a 1.8GHz machine).

Regards,
Chris B.

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>
>    Anyways, with a small change I got the time for the spheres of
> diamater 0.2 reduced to 15 seconds and the time for the ones of
> diamater 0.23 to 1:50.

Running 3.6 on a 1.8GHz laptop with 512MB RAM:

0.2  = 0:08
0.23 = 1:26

(note: this is with the centers constrained to <-10,0,-10><10,0,10>)

-tgq

Post a reply to this message

Trevor G Quayle wrote:
> Running 3.6 on a 1.8GHz laptop with 512MB RAM:
> 
> 0.2  = 0:08
> 0.23 = 1:26

   I guess we use the same technique but you optimized the SDL more
to be faster. Or perhaps you use something really innovative?

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Trevor G Quayle wrote:
> > Running 3.6 on a 1.8GHz laptop with 512MB RAM:
> >
> > 0.2  = 0:08
> > 0.23 = 1:26
>
>    I guess we use the same technique but you optimized the SDL more
> to be faster. Or perhaps you use something really innovative?

Depends, I haven't seen yours yet... but based on the times, I would assume
they are similar.  I don't think I did anything really innovative, just
tweaked my algorithm to try to minimize the calcs required as much as
possible.  Actually I started with a bit higher times for the 0.23, but
made some algorithm optimizations to speed it up, then made some SDL
optimizations for further speeding.

-tgq

Post a reply to this message

Greetings, and thanks for your answer.

Yes, I would be interested to see how the code for the object distribution 
would be. I tried on my own, a few successless times before, but had not 
even the right beginning idea.

And to be honest, if you could show me how to trace the surface(s) of an 
object on which the objects should be distributed, I would appreciate it a 
lot! I am asking, because I also have no idea how to do that.

Thanks,

Sven



"Warp" <war### [at] tagpovrayorg> schrieb im Newsbeitrag 
news:4469e328$1@news.povray.org...
> Sven Littkowski wrote:
>> Let's say, I intend to place a ramdom-generated pattern of spheres (such 
>> as yours) on an unequal surface (maybe a heightfield or a union of 
>> objects).
>
>   My method can actually be used for any distributions of spheres,
> not just a plane. You only have to come up with a formula which
> calculates a random placement for the spheres in whatever shape
> you want (eg. the surface of an object). Of course with certain
> shapes calculating an even distribution may not be as trivial
> as a simple <rand(S), rand(S), rand(S)> (for example distributing
> points about evenly on the surface of a sphere requires a function
> slightly more complicated).
>   If you want to place spheres on the surface of an object you'll
> have to use trace to get points on that object and figure out a
> way to distribute these points approximately equally on the surface
> of the whole object (with a spherical surface it's rather easy but
> with other more irregular surfaces it can be more difficult).
>
>> How, then, would the code look alike? Can you help me?
>
>   The naive approach is to simply store the locations of the spheres
> already created in an array and then when a new sphere is created,
> check it against each coordinate in this array (iow. check if the
> center of the sphere you just created is closer than the diameter
> of the sphere to any of the coordinates in the array; if it is closer
> to any of the points, then it's not ok and you have to create another
> location for the new sphere; after you successfully create it, add
> its center coordinates to the array).
>
>   My optimized method uses this basic approach but I figured out a
> rather simple way of speeding up the check a *lot*.
>   The good thing about this approach is that you can have *any*
> distribution for the spheres you like (eg. on the surface of any
> object or whatever), and this algorithm will never produce spheres
> which are intersecting.
>
>   I can post a description of my simple method in povray.general if
> people are interested. (It's probably nothing new and other people
> have probably already thought of it, but perhaps my specific approach
> is more resource-friendly than most other attempts.)

Post a reply to this message

94 seconds on an Athlon Xp-1700.  The first iteration gave me about 3 
minutes, the second got me to that.  Once I figured what it was, the 
only thing I could say was "Doh!"

...Chambers

Post a reply to this message

"Trevor G Quayle" <Tin### [at] hotmailcom> wrote:
> Warp <war### [at] tagpovrayorg> wrote:
> > Trevor G Quayle wrote:
> > > Running 3.6 on a 1.8GHz laptop with 512MB RAM:
> > >
> > > 0.2  = 0:08
> > > 0.23 = 1:26
> >
> >    I guess we use the same technique but you optimized the SDL more
> > to be faster. Or perhaps you use something really innovative?
>
> Depends, I haven't seen yours yet... but based on the times, I would assume
> they are similar.  I don't think I did anything really innovative, just
> tweaked my algorithm to try to minimize the calcs required as much as
> possible.  Actually I started with a bit higher times for the 0.23, but
> made some algorithm optimizations to speed it up, then made some SDL
> optimizations for further speeding.
>
> -tgq

One further refinement in the algorithm

0.2  = 0:08 (no significant change)
0.23 = 1:11

-tgq

Post a reply to this message

Interestingly if you constrain the entire sphere volume to the given area
(20x20) rather than the center positions, the parse time triples...

-tgq

Post a reply to this message

Warp wrote:

> John VanSickle wrote:
> 
>> When faced with this problem, I usually take the easy way out and put 
>> them into rows and columns, with jitter to make it look random.
> 
> 
>   But as I said, I don't use any fakery. The location of every single
> sphere is calculated randomly accross the entire area. :)

Do you have problems with it turning into an O(n^2) problem, or is there 
some kind of shortcut to make things go faster?

Regards,
John

Post a reply to this message

John VanSickle wrote:
> Do you have problems with it turning into an O(n^2) problem, or is there 
> some kind of shortcut to make things go faster?

   AFAIK the method I use is faster than O(n^2), although it might not
be immediately obvious from the code.
   (Although don't quote me on that. Trying to prove that claim is
actually quite difficult... :P )

Post a reply to this message

Sven Littkowski wrote:
> And to be honest, if you could show me how to trace the surface(s) of an 
> object on which the objects should be distributed, I would appreciate it a 
> lot! I am asking, because I also have no idea how to do that.

   Well, the POV-Ray documentation answers that question. Just look for
trace() in the docs.

Post a reply to this message

Trevor G Quayle wrote:
> Interestingly if you constrain the entire sphere volume to the given area
> (20x20) rather than the center positions, the parse time triples...
> 
> -tgq
> 
> 

Rather than do that, why not just decrease the size of the Min and Max 
coordinates?  Ie, instead of using +/- <10,0,10>, use +/- <9.9,0,9.9>? 
I'd think that would be faster, and cleaner.

...Chambers

Post a reply to this message

Ben Chambers <ben### [at] pacificwebguycom> wrote:
> Trevor G Quayle wrote:
> > Interestingly if you constrain the entire sphere volume to the given area
> > (20x20) rather than the center positions, the parse time triples...
> >
> > -tgq
> >
> >
>
> Rather than do that, why not just decrease the size of the Min and Max
> coordinates?  Ie, instead of using +/- <10,0,10>, use +/- <9.9,0,9.9>?
> I'd think that would be faster, and cleaner.
>
> ...Chambers

Actually this is what I did to test it.  Just making a comment on how filled
up the area is getting that that small of a change in area(~2.3%) has that
much of an impact on the parse time.

-tgq

Post a reply to this message

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Warp wrote:
> John VanSickle wrote:
>> Do you have problems with it turning into an O(n^2) problem, or is
>> there some kind of shortcut to make things go faster?
> 
>   AFAIK the method I use is faster than O(n^2), although it might not
> be immediately obvious from the code.
>   (Although don't quote me on that. Trying to prove that claim is
> actually quite difficult... :P )
	I would bet O(n.log(n) although I can't prove it either ;)

		Jerome
- --
+------------------------- Jerome M. BERGER ---------------------+
|    mailto:jeb### [at] freefr      | ICQ:    238062172            |
|    http://jeberger.free.fr/     | Jabber: jeb### [at] jabberfr   |
+---------------------------------+------------------------------+
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFEa1pkd0kWM4JG3k8RAg88AJ960Ua77/qWgcukC9/FRKq9T5C4wACgjsGX
cEof8uIXFGlWrcdfw3wL+r0=
=aDFv
-----END PGP SIGNATURE-----

Post a reply to this message

Even if you constrain by contracting the bounding box by 1D?
DLM
"Trevor G Quayle" <Tin### [at] hotmailcom> wrote in message 
news:web.446a1f9ef5b1f07d6c4803960@news.povray.org...
> Interestingly if you constrain the entire sphere volume to the given area
> (20x20) rather than the center positions, the parse time triples...
>
> -tgq
>
>

Post a reply to this message

"dlm" <me### [at] addressinvalid> wrote:
> Even if you constrain by contracting the bounding box by 1D?
> DLM
> "Trevor G Quayle" <Tin### [at] hotmailcom> wrote in message
> news:web.446a1f9ef5b1f07d6c4803960@news.povray.org...
> > Interestingly if you constrain the entire sphere volume to the given area
> > (20x20) rather than the center positions, the parse time triples...
> >
> > -tgq
> >
> >

Yes,  i just happens that at these parameters, the area is fairly filled up,
so randomly finding a usable location gets more difficult, so much so that a
such a small change in area has a large impact on the search time.  Perhaps
this is why Warp chose these parameters to test in the first place (or
perhaps it's just a coincidence)

-tgq

Post a reply to this message

I did a macro package some time ago that does that in various 
configurations:
http://sibylone.free.fr/index.php?sub=repartition&lang=en

Enjoy ! :-)

Warp wrote:
>   Inspired by a post I made to another group, I thought if I could find
> a fast way to create a large amount of randomly-placed spheres on a plane
> so that they don't intersect each other.
> 
>   In these images I created 5000 spheres randomly placed inside an area
> between <-10, 0, -10> and <10, 0, 10>. The locations of each sphere is
> individually calculated with just a honest
> MinCoords+(MaxCoords-MinCoords)*<rand(Seed), 0, rand(Seed)>
> ie. no cheating by creating repeating patterns which just look random
> or anything. The location of each sphere is honestly calculated by
> with that line.
> 
>   In the first image the radius of the spheres is 0.2 and it took
> 17 seconds to parse in my P4 3.4GHz. In the second image the radius
> is 0.23 and it took a lot longer because the space fills faster and
> it's harder to find places for new spheres: 2 minutes 44 seconds.
> 
>   The naive way of doing this (which I posted in that another group)
> took more than 7 minutes to place the spheres of radius 0.2 (compared
> to the 17 seconds of my optimized method). I don't know how much longer
> than 7 minutes it is because I got bored of waiting and stopped it.
> 
>   The scene which created these images is 76 lines long (written in
> a nice, indented way, no obfuscation nor artificial shortening, and
> it even prints its progress during the calculations).
> 
>   If you want a small challenge, try replicating this result.
> 
> 


-- 
http://sibylone.free.fr

Post a reply to this message

JC (Exether) wrote:
> I did a macro package some time ago that does that in various 
> configurations:

   Does what?
   My point was not how to do it, but how to do it *fast*.

Post a reply to this message

Ah, OK, mine just does it. :-)

When talking about efficiency, I think that external programming (C++, 
Java ...) will be much faster.

Warp wrote:
> JC (Exether) wrote:
> 
>> I did a macro package some time ago that does that in various 
>> configurations:
> 
> 
>   Does what?
>   My point was not how to do it, but how to do it *fast*.


-- 
http://sibylone.free.fr

Post a reply to this message

JC (Exether) wrote:
> When talking about efficiency, I think that external programming (C++, 
> Java ...) will be much faster.

   With less than 70 lines of code? I don't think so.

Post a reply to this message