POV-Ray : Newsgroups : povray.advanced-users : Random tree position, without duplicates? Server Time: 28 Sep 2020 20:28:54 GMT
 Random tree position, without duplicates? (Message 2 to 11 of 11)
 From: SharkD Subject: Re: Random tree position, without duplicates? Date: 4 Jun 2010 19:48:50 Message: <4c0958a2@news.povray.org>
```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 multi-dimensional B-tree 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 B-tree sorting method there's no
guarantee how many items a node will hold.

--
http://isometricland.com
```
 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.
```
 From: SharkD Subject: Re: Random tree position, without duplicates? Date: 4 Jun 2010 20:57:32 Message: <4c0968bc\$1@news.povray.org>
```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
```
 From: Edouard Subject: Re: Random tree position, without duplicates? Date: 4 Jun 2010 21:30:00 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 non-overlapping 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.
```
 From: Edouard Subject: Re: Random tree position, without duplicates? Date: 4 Jun 2010 21:35:01 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
```
 From: SharkD Subject: Re: Random tree position, without duplicates? Date: 4 Jun 2010 22:55:59 Message: <4c09847f\$1@news.povray.org>
```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
```
 From: Edouard Subject: Re: Random tree position, without duplicates? Date: 5 Jun 2010 00:10:00 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.
```
 From: Jim Charter Subject: Re: Random tree position, without duplicates? Date: 5 Jun 2010 19:18:39 Message: <4c0aa30f\$1@news.povray.org>
```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?
```
 From: Edouard Subject: Re: Random tree position, without duplicates? Date: 5 Jun 2010 21:10:01 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.
```
 From: Jim Charter Subject: Re: Random tree position, without duplicates? Date: 5 Jun 2010 22:49:22 Message: <4c0ad472\$1@news.povray.org>
```Edouard wrote:
> 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.
>
>
It's a revelation, thanks.
```