Jump to content
  • Advertisement
Sign in to follow this  

Populating worley noise grid cells

This topic is 702 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I was reading the book "Texturing and modeling: a procedural approach" to learn how to create tileable worley/cell noise ( so I can use it in the technique described in this thread :P http://www.gamedev.net/topic/680832-horizonzero-dawn-cloud-system) and there is only one thing that it's not entirely clear to me, and that is how to calculate the amount of points that are inside each of the cells using the poisson distribution.

The poisson distribution gives me the probability of a certain number of points being in a cell (given a known average of the amount of points in a cell), but I don't understand how to sample the equation for the cells. In the book they use some kind of number generator with a seed that they get from the id of each cell, but I can't wrap my head around it.

In university I remember having a subject about probabilities and statistics, but the problems were always relatively simple ( 'calculate the probability of...' ) and I've never used probabilities outside of the university classes so now the time has come, and I'm a bit lost.

Any help is appreciated, thanks!

Edited by ramiro_fages

Share this post

Link to post
Share on other sites

Here's an example with a hash function:



You can start by always using 1 point per cell. You use the hash function to lookup a repeatable seed value for the cell, which you feed into a repeatable random number generator, which you can use to find the position within that cell.

Thanks, I've also read that and still there is something unclear to me, I'll quote a phrase from that link:



By generating a random number between zero and one (using the generator from step 2) and comparing its value with the calculated probabilities we can determine the number of feature points in a specific cube.

How is the comparison made?

Share this post

Link to post
Share on other sites

He uses a lookup function based on the result of a random number from the random generator:

    /// <summary>
    /// Given a uniformly distributed random number this function returns the number of feature points in a given cube.
    /// </summary>
    /// <param name="value">a uniformly distributed random number</param>
    /// <returns>The number of feature points in a cube.</returns>
    // Generated using mathmatica with "AccountingForm[N[Table[CDF[PoissonDistribution[4], i], {i, 1, 9}], 20]*2^32]"
    private static uint probLookup(uint value)
        if (value < 393325350) return 1;
        if (value < 1022645910) return 2;
        if (value < 1861739990) return 3;
        if (value < 2700834071) return 4;
        if (value < 3372109335) return 5;
        if (value < 3819626178) return 6;
        if (value < 4075350088) return 7;
        if (value < 4203212043) return 8;
        return 9;

If for example the random number gives a number between 0 and 8 inclusive, for instance, and you want a 1 a third of the time, then you can say 0, 1, or 2 give a 1 .. etc. A lookup table essentially, based on the particular distribution you want.


I myself just used 1 point per cell, as it fit my purpose, but if I were doing it I'd probably just use a lookup table of 0 to 255. Choose a random number between 0 and 255, lookup the resulting number of points.


If you want to know how to calculate your own lookup table (not having done this myself, but I assume it would be something as follows):


1) Start with your distribution function, with a probability 'p' (0-1) for each number of points..

2) Allocate p * 255 of the lookup table to this number of points, then do the next number of points etc etc until all 255 lookups are done.

Share this post

Link to post
Share on other sites

Hmm I see. So if I understood correctly:

For an average number of points = 1, I calculate the poisson cumulative distribution for each of the number of points that I would like to have in each cell, so if I want a maximum of 4 points, I would calculate a table as follows:

poisson_table[0] = 0.367879441171442

poisson_table[1] = 0.367879441171442    + poisson_table[0]

poisson_table[2] = 0.183939720585721    + poisson_table[1]

poisson_table[3] = 0.0613132401952404  + poisson_table[2]

poisson_table[4] = 0.0153283100488101  + poisson_table[3]


then having that, using a uniform random number generator in the range of 0..1 , I use that to populate the lookup table of size 256 by sampling the poisson_table. For each element in the 256 table, I generate a random number (0..1) and search in the poisson_table for a higher number than the one I generated. If, for instance, poisson_table[2] is higher than the generated number, then I put the number 2 as the element in the current array index.

Here I leave some pseudocode:

foreach element in table256
    element = get_number_of_points( generate_random()); //generate random returns a value between 0..1

get_number_of_points( number)
   if(number < poisson_table[0] ) return 0;
   if(number < poisson_table[1]) return 1;
   if(number < poisson_table[2]) return 2;
   if(number < poisson_table[3]) return 3;
   if(number < poisson_table[4]) return 4;

   return 1; //by default     


Then finally, when I'm populating the cells, I just generate again a random number between 0..1 and multiply it by 256 and sample the lookup table with that.


Is that...correct?

Edited by ramiro_fages

Share this post

Link to post
Share on other sites

Yup that's the general idea I think.


As an aside rather than generate a number between 0 and 1, if you use the random function from the linked source code, I think it returns an unsigned int between 0 and UINT_MAX. In which case to scale it between 0 and 255 you may be able to do some bit twiddling, like ANDing it with 255, or bitshifting it >> 24. Not that it is likely to be a big bottleneck, but stuff like that is fun. :) Of course, profile things to get an idea of where to optimize.


Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!