









 
 




 
 


Is there a good way to, for instance, place a number of trees randomly
without having them overlap?
Currently, I use an array to store the positions and compare each new
tree to all the previous ones. This is however very slow.
I could also create a multidimensional Btree array that divides the
world into a grid, thereby reducing the number of items to look up. I
wonder if that would speed things.

http://isometricland.com
Post a reply to this message


 
 




 
 


On 6/4/2010 3:45 PM, SharkD wrote:
> Is there a good way to, for instance, place a number of trees randomly
> without having them overlap?
>
> Currently, I use an array to store the positions and compare each new
> tree to all the previous ones. This is however very slow.
>
> I could also create a multidimensional Btree array that divides the
> world into a grid, thereby reducing the number of items to look up. I
> wonder if that would speed things.
>
>
On second thought I don't think this will work because array sizes must
be known beforehand, and with a Btree sorting method there's no
guarantee how many items a node will hold.

http://isometricland.com
Post a reply to this message


 
 


From: Christian Froeschlin
Subject: Re: Random tree position, without duplicates?
Date: 4 Jun 2010 20:25:53
Message: <4c096151@news.povray.org>



 
 


SharkD wrote:
> Is there a good way to, for instance, place a number of trees randomly
> without having them overlap?
one possible way is to iterate over a grid of possible positions and
then deciding randomly or based on a distribution function whether this
particular cell should contain a tree. The actual tree position can
then be varied within the cell to avoid an obvious grid spacing.
Post a reply to this message


 
 




 
 


On 6/4/2010 4:27 PM, Christian Froeschlin wrote:
> SharkD wrote:
>
>> Is there a good way to, for instance, place a number of trees randomly
>> without having them overlap?
>
> one possible way is to iterate over a grid of possible positions and
> then deciding randomly or based on a distribution function whether this
> particular cell should contain a tree. The actual tree position can
> then be varied within the cell to avoid an obvious grid spacing.
Thanks, that sounds like it would work.

http://isometricland.com
Post a reply to this message


 
 




 
 


SharkD <mik### [at] gmailcom> wrote:
> Is there a good way to, for instance, place a number of trees randomly
> without having them overlap?
>
> Currently, I use an array to store the positions and compare each new
> tree to all the previous ones. This is however very slow.
I'd start with a halton sequence (I find myself using them everywhere...) and
seeing if it does a better job of not overlapping the trees:
#macro halton( index, base )
#local out = 0.0;
#local fraction = 1.0 / base;
#local i = index;
#while( i > 0 )
#local remainder = mod( i, base );
#local out = out + (fraction * remainder);
#local i = int(i / base);
#local fraction = fraction / base;
#end
out
#end
#macro halton2D( n )
#local baseX = 2;
#local baseY = 3;
< halton( n, baseX ), halton( n, baseY ), halton( n, baseZ ) >
#end
You additionally take the values returned by the halton2D() macro, and test them
against a pigment function to decide whether to place a tree  this would give
you nonoverlapping randomness on the small scale, and some clumping of trees on
the larger scale. My guess is that that would look quite natural, but you'd have
to give it a try to find out.
Cheers,
Edouard.
Post a reply to this message


 
 




 
 


"Edouard" <pov### [at] edouardinfo> wrote:
Opps  I mean:
#macro halton2D( n )
#local baseX = 2;
#local baseY = 3;
< halton( n, baseX ), halton( n, baseY ), 0 >
#end
Post a reply to this message


 
 




 
 


On 6/4/2010 5:31 PM, Edouard wrote:
> "Edouard"<pov### [at] edouardinfo> wrote:
>
> Opps  I mean:
>
> #macro halton2D( n )
> #local baseX = 2;
> #local baseY = 3;
>
> < halton( n, baseX ), halton( n, baseY ), 0>
> #end
Could you provide an example of how to use it? Thanks.

http://isometricland.com
Post a reply to this message


 
 




 
 


SharkD <mik### [at] gmailcom> wrote:
> On 6/4/2010 5:31 PM, Edouard wrote:
> > "Edouard"<pov### [at] edouardinfo> wrote:
> >
> > Opps  I mean:
> >
> > #macro halton2D( n )
> > #local baseX = 2;
> > #local baseY = 3;
> >
> > < halton( n, baseX ), halton( n, baseY ), 0>
> > #end
>
>
> Could you provide an example of how to use it? Thanks.
I'll try!
The halton macro returns a number from 0..1, and halton2D() returns a vector
where the X is 0..1, Y is 0..1 and the Z = 0.
You call halton2D() with an incrementing integer, so it works best in a loop.
If you had a macro called PlaceTree(), you could loop through values from
halton2D calling the tree macro like this:
#declare n = 1;
#while( n < number_of_trees_wanted )
#declare position = halton2D( n );
// position is <0..1, 0..1, 0>  scale the vector here
// to the size you need for PlaceTree
PlaceTree( position )
#declare n = n + 1;
#end
Does my explanation make sense?
Cheers,
Edouard.
Post a reply to this message


 
 




 
 


Edouard wrote:
> SharkD <mik### [at] gmailcom> wrote:
>> On 6/4/2010 5:31 PM, Edouard wrote:
>>> "Edouard"<pov### [at] edouardinfo> wrote:
>>>
>>> Opps  I mean:
>>>
>>> #macro halton2D( n )
>>> #local baseX = 2;
>>> #local baseY = 3;
>>>
>>> < halton( n, baseX ), halton( n, baseY ), 0>
>>> #end
>>
>> Could you provide an example of how to use it? Thanks.
>
> I'll try!
>
> The halton macro returns a number from 0..1, and halton2D() returns a vector
> where the X is 0..1, Y is 0..1 and the Z = 0.
>
> You call halton2D() with an incrementing integer, so it works best in a loop.
>
> If you had a macro called PlaceTree(), you could loop through values from
> halton2D calling the tree macro like this:
>
> #declare n = 1;
> #while( n < number_of_trees_wanted )
> #declare position = halton2D( n );
> // position is <0..1, 0..1, 0>  scale the vector here
> // to the size you need for PlaceTree
> PlaceTree( position )
> #declare n = n + 1;
> #end
>
> Does my explanation make sense?
>
> Cheers,
> Edouard.
>
>
This is very useful! I see that the increasing integer eliminates the
overlap of points. Is there a relationship between the size of the
object and the size of the increment that can be used to prevent
objects intersecting?
Post a reply to this message


 
 




 
 


Jim Charter <jrc### [at] msncom> wrote:
> Edouard wrote:
> > SharkD <mik### [at] gmailcom> wrote:
> >> On 6/4/2010 5:31 PM, Edouard wrote:
> >>> "Edouard"<pov### [at] edouardinfo> wrote:
> >>>
> >>> Opps  I mean:
> >>>
> >>> #macro halton2D( n )
> >>> #local baseX = 2;
> >>> #local baseY = 3;
> >>>
> >>> < halton( n, baseX ), halton( n, baseY ), 0>
> >>> #end
> >>
> >> Could you provide an example of how to use it? Thanks.
> >
> > I'll try!
> >
> > The halton macro returns a number from 0..1, and halton2D() returns a vector
> > where the X is 0..1, Y is 0..1 and the Z = 0.
> >
> > You call halton2D() with an incrementing integer, so it works best in a loop.
> >
> > If you had a macro called PlaceTree(), you could loop through values from
> > halton2D calling the tree macro like this:
> >
> > #declare n = 1;
> > #while( n < number_of_trees_wanted )
> > #declare position = halton2D( n );
> > // position is <0..1, 0..1, 0>  scale the vector here
> > // to the size you need for PlaceTree
> > PlaceTree( position )
> > #declare n = n + 1;
> > #end
> >
> > Does my explanation make sense?
> >
> > Cheers,
> > Edouard.
> >
> >
> This is very useful! I see that the increasing integer eliminates the
> overlap of points. Is there a relationship between the size of the
> object and the size of the increment that can be used to prevent
> objects intersecting?
Unfortunately not  all it does is generate numbers that have a distribution
that looks random, but have the property that they don't clump together. As you
generate more numbers, each new item fills a position that was empty, and as you
generate more and more numbers in the sequence, space gets filled denser and
denser.
If your objects aren't too closely packed, a halton sequence is a very easy
replacement for rand(), and may work well. I posted it mainly because it should
be very easy to try out for the problem described.
Cheers,
Edouard.
Post a reply to this message


 
 




 

