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