A fast and simple 32bit floating point hash function

In a previous post I reviewed two existing floating point hash functions which are suitable for use in fragment shaders.  These were the BlumBlumShub and Permutation Polynomial hash functions used in MNoise and WebGLNoise.  If curious, here is a link to the post https://briansharpe.wordpress.com/2011/10/01/gpu-texture-free-noise/

I’ve become disheartened with both.  They both contain artifacts and are slow to calculate.  The BBS hash is still useful because it can run on 16bit and 24bit floating point hardware.  But now that we have 32bit floating point hardware I’ve decided make a floating point hashing function of my own.

The hash function which is working best for me takes the form hash = mod( coord.x * coord.x * coord.y * coord.y, SOMELARGEFLOAT ) / SOMELARGEFLOAT.  The 3D version simply offsets the SOMELARGEFLOAT value by a fraction of the Z coordinate.  It takes some time to find constants which give good visual results and also to find a specific area of the noise which is most free from artifacts.  It would be good to one day use some kind of computational process to find constants which give the best possible noise, but for now my hand-picked values should work ok.

One thing to note is the x*x*y*y operation pushes the floating point number well over 2^23 causing a loss of precision, which is where a lot of the “randomness” comes from.  Because of this I’m not sure if it will give identical results across cards.  More investigation is required.  But for now its giving good results on my CPU and ATI card so I’m going to stick with it.  : )

As with the previous hash functions, here is some GLSL code which implements the new 32bit hash function to calculate pseudo random 0.0->1.0 hash values for the 4 corners of a 2D integer grid cell.

//
//    FAST_32_hash
//    A very fast 2D hashing function.  Requires 32bit support.
//
//    The hash formula takes the form....
//    hash = mod( coord.x * coord.x * coord.y * coord.y, SOMELARGEFLOAT ) / SOMELARGEFLOAT
//    We truncate and offset the domain to the most interesting part of the noise.
//
vec4 FAST_32_hash( vec2 gridcell )
{
//    gridcell is assumed to be an integer coordinate
const vec2 OFFSET = vec2( 26.0, 161.0 );
const float DOMAIN = 71.0;
const float SOMELARGEFLOAT = 951.135664;
vec4 P = vec4( gridcell.xy, gridcell.xy + 1.0.xx );
P = P - floor(P * ( 1.0 / DOMAIN )) * DOMAIN;    //    truncate the domain
P += OFFSET.xyxy;                                //    offset to interesting part of the noise
P *= P;                                          //    calculate and return the hash
return fract( P.xzxz * P.yyww * ( 1.0 / SOMELARGEFLOAT.x ).xxxx );
}

Here is an image showing a 61×61 sampling of the Fast 32bit hashing function  ( 61×61 for comparison with BBS and SGPP, the actual domain is 72×72 ).

A 61x61 sampling of the Fast 32bit floating point hash function

A 61×61 sampling of the Fast 32bit floating point hash function

Advertisements

About briansharpe

Computer games and graphics programmer interested in procedural modeling and texturing techniques. Current Work: Weta Digital. Work history: Sidhe Interactive, Sony London (SCEE), Pandromeda,
This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to A fast and simple 32bit floating point hash function

  1. Pingback: Adding a 4th dimension | briansharpe

  2. Derpson says:

    Nice! But did you know you can write the line
    P = P – floor(P * ( 1.0 / DOMAIN )) * DOMAIN;
    as:
    P = mod(P, DOMAIN);
    ?

    • briansharpe says:

      mod() internally calls a divide. If the denominator is known at compile time (as is the one here) then it is better to write the expression out explicitly. Some compilers will optimize out the divide automatically for you, others will not. So it is better to do this as a matter of course to cover both cases.
      You can read more about it here.

      • Derpson says:

        Oh ok, thank you.
        During my profiling it didn’t make any difference. So I used the shorter variant.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s