I'm shocked! :-)

I'm using the animation function to generate a series of images of my scene,
where the camera position is chosen at random, using the frame number as seed.

Rnd1 = seed( frame_number )
CamX = rand(Rnd1)
CamY = rand(Rnd1)
CamZ = rand(Rnd1)

I noticed that the second random number (CamY) follows a rather clean linear
function of the seed, from 0 to 1 and then returning to 0, thus resulting in a
"sawtooth" function. So I got curious: do other random numbers follow such a not
quite random pattern. Well, yes, they do. I tried the 101st number and it shows
the same sawtooth function.
This is a rather unpleasant surprise. Shouldn't we expect random numbers to have
no direct relation with the previous number (or seed)?

Without having done a statistical analysis consecutive random values seem to
behave better. So it looks like there's just the relationship with the seed
value.
Time for a new seed function (seed2?) ?

Steven

Post a reply to this message

Am 12.05.2010 18:00, schrieb stevenvh:

> Rnd1 = seed( frame_number )
> CamX = rand(Rnd1)
> CamY = rand(Rnd1)
> CamZ = rand(Rnd1)
>
> I noticed that the second random number (CamY) follows a rather clean linear
> function of the seed, from 0 to 1 and then returning to 0, thus resulting in a
> "sawtooth" function. So I got curious: do other random numbers follow such a not
> quite random pattern. Well, yes, they do. I tried the 101st number and it shows
> the same sawtooth function.
> This is a rather unpleasant surprise. Shouldn't we expect random numbers to have
> no direct relation with the previous number (or seed)?

This is a known issue that surfaces every now and again. In a nutshell, 
while any two individual values pulled from the same random stream have 
no very obvious correlation, there /do/ exist strong correlations 
between the /seed/ and any particular value pulled from the stream 
(especially so for the very first samples, but apparently also for later 
values). This is a natural property of the random number generator used 
in POV-Ray.

As a consequence, seeding with the frame number is generally a bad idea. 
Some alternatives that have been suggested:

(A) Seed with a fixed number for the first frame, then pull one more 
random number from the stream at the end of each frame, write it to a 
file, and use it as the seed for the next frame.

(B) For each frame seed with the same fixed number, then pull and 
discard N*frame_number values from the stream, where N is equal to or 
greater than the number of random values you need per frame.


> Time for a new seed function (seed2?) ?

Better yet, time for a new RNG.

A new seed function for the existing RNG would boil down to applying 
some hashing to the seed value, which can just as well be done via an 
SDL macro or function, so there's no real need for any changes to the 
POV-Ray code in that respect.

Post a reply to this message

On 12.05.10 18:00, stevenvh wrote:
> This is a rather unpleasant surprise. Shouldn't we expect random numbers to have
> no direct relation with the previous number (or seed)?

No, not if you want your scenes to look the same very time you render them ;-)

> Without having done a statistical analysis consecutive random values seem to
> behave better. So it looks like there's just the relationship with the seed
> value.
> Time for a new seed function (seed2?) ?

No, because this is a perfectly normal, expected, and designed functionality 
in POV-Ray. In fact, it is a property of all pseudo random number 
generators. This property is shared by all software random number generators 
that have no hardware source of randomness.

	Thorsten

Post a reply to this message

"stevenvh" <nomail@nomail> wrote:
> I'm shocked! :-)
>
> I'm using the animation function to generate a series of images of my scene,
> where the camera position is chosen at random, using the frame number as seed.
>....
> Time for a new seed function (seed2?) ?
>

Ah, welcome to the *interesting* world of POV's seed() and rand(). They do
indeed produce some patterns (which are especially visible in animation, as I
found out awhile ago.)

The need for a new random-number generator is well-known.  Take a look at
something I posted awhile ago; among the replies are some suggestions for
getting *around* the repeating-pattern behavior...

http://news.povray.org/povray.general/thread/%3Cweb.497a1e5215dcf5ebf50167bc0%40news.povray.org%3E/?mtop=21

For my own animations, here's *one* of the workarounds I've come up with
(simplified for explanation):
1) Choose only *one* seed value, at the beginning of the animation file.
2) Fill an array with LOTS of rand() values from that seed().
3) In the body of the scene, pick out these values from the arrays, for use. If
you need some 'new' rand values for each frame of animation (as for your camera
position, for example), use frame_number (in whatever way is practical) to
choose different array locations and thus different rands. (This is why the
array needs to be large, to hold as many values as might be needed.)

This scheme has its pros and cons: The array needs to be loaded with its rand
values for every frame of animation--so it's kind of a 'brute-force' method. But
the values don't change from frame to frame, because seed stays the same.
(That's a GOOD thing.) And in my own experience, using a single seed value helps
hide or eliminate repeating patterns--from a practical standpoint, anyway. I.e.,
it seems to produce far more 'random' results than choosing different SEEDS for
every animation frame.

Ken

Post a reply to this message

"Kenneth" <kdw### [at] earthlinknet> wrote:

> The need for a new random-number generator is well-known.

In light of Clipka's reply, I guess what I meant was a "new RNG" scheme.
*That's* the thing that's been discussed a great deal, in the newsgroups.

Ken

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
> This property is shared by all software random number generators 
> that have no hardware source of randomness.

  No, this is a property of linear congruential generators. Higher-quality
RNGs don't suffer from this (or at least it's significantly less evident).

  As the name "linear congruential generator" suggests, there's a linear
relationship between the initial seed and the consequent stream of numbers.
Hence if the seed is changed linearly, so will the stream (although this is
often masked by how the numbers from the stream are used).

  I think you are confusing the property of pRNGs that a given seed always
gives the same random number stream (which is usually a desirable thing)
with the phenomenon described in this thread, namely the linear relationship
between the seed and the subsequent numbers.

-- 
                                                          - Warp

Post a reply to this message

stevenvh <nomail@nomail> wrote:
> Rnd1 = seed( frame_number )
> CamX = rand(Rnd1)
> CamY = rand(Rnd1)
> CamZ = rand(Rnd1)

> I noticed that the second random number (CamY) follows a rather clean linear
> function of the seed, from 0 to 1 and then returning to 0, thus resulting in a
> "sawtooth" function.

  This is a side-effect of linear congruential generators, which is what
POV-Ray uses (http://en.wikipedia.org/wiki/Linear_congruential_generator).

  As the name suggests, there's a linear relationship between the initial
seed and the subsequent values (because the RNG does nothing more than
take your seed, multiply it by a constant and add a constant, modulo the
size of unsigned int).

  Higher-quality RNGs don't usually suffer from such a clear relationship,
and adding such RNGs has been discussed.

  Currently you can try mask the problem by using some tricks. For example
you can try something like this:

#declare Rnd1 = seed(frame_number);
#declare Loops = int(rand(Rnd1)*20);
#while(Loops >= 0)
    rand(Rnd1);
    #declare Loops = Loops-1;
#end
// and then continue as normal...

  While this kind of trickery doesn't significantly improve the quality of
the randomness (and patterns might still emerge in some situations), it can
mask the effects better.

-- 
                                                          - Warp

Post a reply to this message

On 12.05.10 19:38, Warp wrote:
> Thorsten Froehlich<tho### [at] trfde>  wrote:
>> This property is shared by all software random number generators
>> that have no hardware source of randomness.
>
>    No

Yes, thank you for taking some sentence out of context, putting some random 
words in my mouth, and then providing some pointless off-topic lecture. ROFL

	Thorsten

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
> On 12.05.10 19:38, Warp wrote:
> > Thorsten Froehlich<tho### [at] trfde>  wrote:
> >> This property is shared by all software random number generators
> >> that have no hardware source of randomness.
> >
> >    No

> Yes, thank you for taking some sentence out of context, putting some random 
> words in my mouth, and then providing some pointless off-topic lecture. ROFL

  And exactly how was it taken out of context?

  The original poster had noticed (and you quoted it) that there was a
clearly distinguishable pattern between the seed and the subsequent random
numbers. In other words, when the initial seed is changed incrementally,
an obviously regular pattern emerges from the rng stream that follows.

  To that observation you responded with "the rng has been designed so, and
this is a property of *all* rngs".

  Clearly you were confusing this situation with the fact that a given seed
will always produce the same random stream, which is a completely different
matter.

  The rng used in POV-Ray was certainly not specifically designed to give
clearly distinguishable patterns in relation to successive seed values. This
is simply a side-effect of the linear congruential generator used by POV-Ray.

  Higher-quality rngs don't present such obvious patterns. You can try with
successive seed values, and such linear patterns won't emerge (at least not
as obviously). Naturally the same seed will always give the same rng stream,
but that's a completely different matter.

-- 
                                                          - Warp

Post a reply to this message

Thanks all for the replies and the tips for workarounds.
Steven

Post a reply to this message