![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: John VanSickle
Subject: Re: Placing random spheres (~330k in attachments)
Date: 16 May 2006 16:44:35
Message: <446a39b3$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Warp
Subject: Re: Placing random spheres (~330k in attachments)
Date: 17 May 2006 10:06:33
Message: <446b2de9@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Ben Chambers
Subject: Re: Placing random spheres (~330k in attachments)
Date: 17 May 2006 12:22:19
Message: <446b4dbb@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Ben Chambers <ben### [at] pacificwebguy com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: "Jérôme M. Berger"
Subject: Re: Placing random spheres (~330k in attachments)
Date: 17 May 2006 13:16:20
Message: <446b5a64$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
-----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] free fr | ICQ: 238062172 |
| http://jeberger.free.fr/ | Jabber: jeb### [at] jabber fr |
+---------------------------------+------------------------------+
-----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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Even if you constrain by contracting the bounding box by 1D?
DLM
"Trevor G Quayle" <Tin### [at] hotmail com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
"dlm" <me### [at] address invalid> wrote:
> Even if you constrain by contracting the bounding box by 1D?
> DLM
> "Trevor G Quayle" <Tin### [at] hotmail com> 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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: JC (Exether)
Subject: Re: Placing random spheres (~330k in attachments)
Date: 22 May 2006 07:29:32
Message: <4471a09c$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |