Blog

Archive
| All posts |
  • The work it takes to be random

    published on 12/1/2010 8:00 PM

    Creating flexible programs like Plane9 does present some rather unique challenges.

    For example when creating a visualizer that is basically a single effect, like most other screensavers and music visualizers are, you can rather quickly put something together. If it looks ok and gives you the desired effect your done and you can quickly move onto the next feature you want to add. This however doesn't really work when a end user can create their own content so each part can be used in ways you didn't plan on from the start. This is of course both a blessing and a curse.

    Randomizer For a more concrete example of this lets take the randomizer in Plane9. Randomizers, or rather psedorandomizers as is the proper term in this case, is a well studied subject and normally adding one shouldn't take long at all. Using the build in library functions is the easiest option since its already created for you. However then we run into the problem that Plane9 requires two forms of randomizers. One that generates more true random and another that is based on a specific seed value and will generate the same random values each and every time.

    The standard randomizer has two things against it. You only have one random function so you can't easily have multiple randomization seeds going at one time. The other thing is that the standard library randomizer is a [url:linear congruential generator|http://en.wikipedia.org/wiki/Linear_congruential_generator]. So it doesn't generate very good random values from the start and further more it creates hyperplanes in multiple dimensions. This could be seen if you used the cloneexpression node and randomized the x,y and z position of the objects. Soon enough you would start to see planes form among the points. Here is the problem I mentioned at the start. Normally you could get away with the simple randomizer for the specific effect you wanted. But since this can be used in any number of ways I need to find something better than this. So there in the hunt began.

    The hunt for two randomizers The first one was rather easy to solve. The one where you want as true random as possible since there is a known good randomizer for this. It's called [url:mersenne twister|http://en.wikipedia.org/wiki/Mersenne_twister]. It's fast and creates very good random values. But this has another problem. It requires a rather large work buffer and seeding it is problematic if you need to do it many times per frame. But if you only need one its very good.

    So that takes care of the first problem. The second one however was more difficult. It should also create very good random values but have as small work buffer as possible and be very fast to reseed. I though this was going to be simpler than it was but just about all good randomizer fail in usually both of the requirements.

    I eventually found what I was looking for in the [url:xor shift|http://en.wikipedia.org/wiki/Xorshift] randomizer. It also passes the die hard tests so it should be good enough for a visualizer.

    So in the expression ports. If your calling random() you will get a value from the mersenne twister. If you however call rand() or rand(&myseedvalue) you will get a value created by the xorshift randomizer. Hopefully this will now take care of the randomizer once and for all so I too can go onto adding the next feature and you can get what you expect in your own scenes. Random values that are random.