6 ms·

A Simple Hash for Perlin Noise

69 points by thisismyswamp 4y ago

ssklash 4y ago
This same hash is often used in Windows malware to avoid using the names of functions that are commonly used for malicious purposes, like `WriteProcessMemory`.
pcwalton 4y ago
FNV is slow because it only goes one byte at a time. An easy improvement for basically no extra complexity is the FxHash, which is popular in Rust for simple non-secure workloads: https://nnethercote.github.io/2021/12/08/a-brutally-effective-hash-function-in-rust.html https://nnethercote.github.io/2021/12/08/a-brutally-effectiv... Obligatory disclaimer: Don't use any of this in cryptographic contexts.
pubby 4y ago
I think I'm missing something. Why not call a PRNG for each array element? Seems like you could do this in 4 lines of code.
- foota 4y ago
  "I couldn’t rely on simple randomness since terrain generation has to be deterministic, especially for multiplayer games." You want the results to be repeatable. Now you could seed with something, but this has tradeoffs (e.g., you have to produce the same order of elements in order to get the same values out)
eerikkivistik 4y ago
Maybe I am missing something, but wouldn't a regular random number generator with a defined seed work just as well? If the problem is determinism, then using a deterministic seed should give the same result.
- thisismyswamp 4y ago
  Indeed like others mentioned, it's about being able to generate terrain chunks starting from anywhere in the world. A random number generator using the same seed would still have to follow the same steps for all users, meaning generating the world from the origin.
- pcwalton 4y ago
  Correct, you can use an RNG. It's no coincidence that many RNGs and hashes (and, for that matter, ciphers) have similar constructions.
- foota 4y ago
  A desirable property for this is to be able to generate only some part of the terrain, but if you're using a seeded PRNG then you have to generate the same bits at a time. You could solve this with chunking, but it's not trivial.
- Sharlin 4y ago
  If all you want to do is to generate a texture by looping over all pixels in sequence, then yes, you can use a RNG. But in many use cases you need to evaluate a noise function at an arbitrary (x, y) position (or (x, y, z) or even higher dimension) which means you need to hash the coordinates to get the pseudorandomness you want.
Dave_Rosenthal 4y ago
Ah, adventures in 'not quite as random as you thought' land. 1) I remember building a game in 90s where the locations of resources on a 2d game map were generated by successive calls to random() (and then were probably mod 1024ed or something). But, when we looked at the locations, they were clearly in a line pattern. Huh? After a while of confused debugging, we eventually discovered that the RNG was a linear congruential generator, which, when used the way we did to generate N-tuples, tends to produce points that tend to lie on a small number of N-1 dimensional surfaces! Oops. 2) I remember a big debate with a statistician at a company we were selling data analytics software to. We were putting random data elements into random groups to support certain types of statistical analysis. He was adamant that the randomization we were doing would introduce bias into the data and showed us similar tests he had done that "proved it". He told us that his company would be dropping our product because they couldn't trust it. I told him that there was no way bias was introduced and I took a closer look at his tests. It turns out the RNG in whatever tool he was using was just not very good and it had apparently shaken his very understanding of statistics :) Luckily, I told him that we were using MD5 for randomness (once bitten!) and that if he simply redid his experiments with MD5 he would see the bias disappear. To say he was skeptical would be an understatement, but, thankfully for our contract, his tests didn't actually crack MD5, all bias was gone, and we got a very generous email from the skeptic informing us that he would be trusting our software for everything from now on.
- adgjlsfhk1 4y ago
  Thankfully the awful linear congruential generators of past have mostly been killed by now. Mersenne twister isn't ideal (kind of slow and uses a bunch of memory), but it is pretty solid. The xoshiro family also is pretty widely used in now for programming languages, and that's a major an improvement over lcg on all fronts (except roughly tied for speed).
  - galangalalgol 4y ago
    Have they gotten one that implements well in a gpu yet? Last I read many people doing stochastic filters (resampling etc.) Were generating noise cpu side and shipping it over to the device. But that has been a while.
w-ll 4y ago
sfc32 from http://pracrand.sourceforge.net/RNG_engines.txt http://pracrand.sourceforge.net/RNG_engines.txt works pretty well for when I need deterministic random. A simple implementation in javascript https://stackoverflow.com/questions/521295/seeding-the-random-number-generator-in-javascript https://stackoverflow.com/questions/521295/seeding-the-rando... I use it for my generative art project https://bigf.art https://bigf.art
ot 4y ago
> I ended up implementing the Fowler–Noll–Vo 1a hash, which is known for trading some quality for increased performance. It was designed to be fast This is a surprisingly resistant belief. It may have been true once, but today FNV is not even close to being a fast hash function. Check the SMHasher benchmarks: https://github.com/rurban/smhasher#smhasher https://github.com/rurban/smhasher#smhasher FNV1a almost 2x slower than blake3, a cryptographic hash function! More than 10x slower than modern hashers such as Farm, City, Spooky, ..., all of which have far better statistical quality than FNV1. There is no good reason to use an FNV function nowadays.
- thisismyswamp 4y ago
  Thanks for bringing this up! Someone replied mentioning implementation simplicity, and indeed that was an important factor that I forgot to mention in the post. Although the most important factor may have been that FNV is just easier to find. Looking for a hash algorithm is hard, the names are weird and opaque and it's hard to find a user friendly ranking or clear directions on how to pick one.
- rurban 4y ago
  The best reason to use FNV is its small codesize, which pays off in icache critical code. such as hash tables. that's why I added the hash tables benchmarks to smhasher. cycles/map shows you that FNV1a is very good with hash tables, 4x faster than the blake3 monstrosity
- ris 4y ago
  > There is no good reason to use an FNV function nowadays. Implementation simplicity? Sometimes you need a hash function in an environment that's not a Real Programming Language.
- vlmutolo 4y ago
  XxHash has some great benchmarks for various hash functions. FNV is still competitive for small inputs. Most hash functions are built to have high throughput for hashing hundreds of bytes or more. XxHash in particular has an explicit mode switch from "small data" to "big data" sizes around a couple hundred bytes (it varies by platform and compiler). It's hard to do both small and big data correctly, and FNV is one of the few that optimizes for small data. For moderately small data, larger than around 4 bytes, xxh3 beats it handily. But for extremely small sizes, FNV is still the winner. Honestly people should probably just try to switch to xxh3 if performance is a concern, but FNV is certainly competitive for integer-size keys. https://github.com/Cyan4973/xxHash/wiki/Performance-comparison#benchmarks-concentrating-on-small-data- https://github.com/Cyan4973/xxHash/wiki/Performance-comparis...
a_e_k 4y ago
See also "GPU Random Numbers via the Tiny Encryption Algorithm" by Zafar, Olano, and Curtis. HPG '10: Proceedings of the Conference on High Performance Graphics Paper: https://www.csee.umbc.edu/~olano/papers/GPUTEA.pdf https://www.csee.umbc.edu/~olano/papers/GPUTEA.pdf Slides: https://highperformancegraphics.org/previous/www_2010/media/GPUAlgorithms/HPG2010_GPUAlgorithms_Zafar.pdf https://highperformancegraphics.org/previous/www_2010/media/...
Lerc 4y ago
For my stack based texture generator I used (utilizing https://github.com/skeeto/hash-prospector https://github.com/skeeto/hash-prospector ) let intHash = x => { x *= 0xed5ad4bb; x ^= x >> 11; x = Math.imul(x,0xac4c1b51); x ^= x >> 15; x = Math.imul(x,0x31848bab); x ^= x >> 14; return x; } With a little wrapper to blend it with a seed via intHash(x+inthash(x+seed)) Used in a Perlin flame here http://fingswotidun.com/stackie/?code=x1x-*5*dx4**y3*p%2By!-&palette=xy!1%2B*e&seed=991150 http://fingswotidun.com/stackie/?code=x1x-*5*dx4**y3*p%2By!-...
- WaxedChewbacca 4y ago
dannyking 4y ago
If you'd like to see an implementation of something that uses Perlin noise, check out this generative art project I did: https://dannyking.uk/artwork/colororbs https://dannyking.uk/artwork/colororbs Perlin noise is how the lines flow togeher rather than crossing each other during the animations. I have a technical write up that explains how it works at the bottom.
- mleonhard 4y ago
  Thanks for sharing that. Someday, an AI will want an eye-catching way to display its mood to others. I expect it will use images like your color orbs.

69 points by thisismyswamp 4y ago

This same hash is often used in Windows malware to avoid using the names of functions that are commonly used for malicious purposes, like `WriteProcessMemory`.

pcwalton 4y ago

FNV is slow because it only goes one byte at a time. An easy improvement for basically no extra complexity is the FxHash, which is popular in Rust for simple non-secure workloads: https://nnethercote.github.io/2021/12/08/a-brutally-effective-hash-function-in-rust.html https://nnethercote.github.io/2021/12/08/a-brutally-effectiv... Obligatory disclaimer: Don't use any of this in cryptographic contexts.

pubby 4y ago

I think I'm missing something. Why not call a PRNG for each array element? Seems like you could do this in 4 lines of code.

foota 4y ago
"I couldn’t rely on simple randomness since terrain generation has to be deterministic, especially for multiplayer games." You want the results to be repeatable. Now you could seed with something, but this has tradeoffs (e.g., you have to produce the same order of elements in order to get the same values out)

eerikkivistik 4y ago

Maybe I am missing something, but wouldn't a regular random number generator with a defined seed work just as well? If the problem is determinism, then using a deterministic seed should give the same result.

thisismyswamp 4y ago
Indeed like others mentioned, it's about being able to generate terrain chunks starting from anywhere in the world. A random number generator using the same seed would still have to follow the same steps for all users, meaning generating the world from the origin.
pcwalton 4y ago
Correct, you can use an RNG. It's no coincidence that many RNGs and hashes (and, for that matter, ciphers) have similar constructions.
foota 4y ago
A desirable property for this is to be able to generate only some part of the terrain, but if you're using a seeded PRNG then you have to generate the same bits at a time. You could solve this with chunking, but it's not trivial.
Sharlin 4y ago
If all you want to do is to generate a texture by looping over all pixels in sequence, then yes, you can use a RNG. But in many use cases you need to evaluate a noise function at an arbitrary (x, y) position (or (x, y, z) or even higher dimension) which means you need to hash the coordinates to get the pseudorandomness you want.

Dave_Rosenthal 4y ago

Ah, adventures in 'not quite as random as you thought' land. 1) I remember building a game in 90s where the locations of resources on a 2d game map were generated by successive calls to random() (and then were probably mod 1024ed or something). But, when we looked at the locations, they were clearly in a line pattern. Huh? After a while of confused debugging, we eventually discovered that the RNG was a linear congruential generator, which, when used the way we did to generate N-tuples, tends to produce points that tend to lie on a small number of N-1 dimensional surfaces! Oops. 2) I remember a big debate with a statistician at a company we were selling data analytics software to. We were putting random data elements into random groups to support certain types of statistical analysis. He was adamant that the randomization we were doing would introduce bias into the data and showed us similar tests he had done that "proved it". He told us that his company would be dropping our product because they couldn't trust it. I told him that there was no way bias was introduced and I took a closer look at his tests. It turns out the RNG in whatever tool he was using was just not very good and it had apparently shaken his very understanding of statistics :) Luckily, I told him that we were using MD5 for randomness (once bitten!) and that if he simply redid his experiments with MD5 he would see the bias disappear. To say he was skeptical would be an understatement, but, thankfully for our contract, his tests didn't actually crack MD5, all bias was gone, and we got a very generous email from the skeptic informing us that he would be trusting our software for everything from now on.

adgjlsfhk1 4y ago
Thankfully the awful linear congruential generators of past have mostly been killed by now. Mersenne twister isn't ideal (kind of slow and uses a bunch of memory), but it is pretty solid. The xoshiro family also is pretty widely used in now for programming languages, and that's a major an improvement over lcg on all fronts (except roughly tied for speed).
- galangalalgol 4y ago
  Have they gotten one that implements well in a gpu yet? Last I read many people doing stochastic filters (resampling etc.) Were generating noise cpu side and shipping it over to the device. But that has been a while.

w-ll 4y ago

sfc32 from http://pracrand.sourceforge.net/RNG_engines.txt http://pracrand.sourceforge.net/RNG_engines.txt works pretty well for when I need deterministic random. A simple implementation in javascript https://stackoverflow.com/questions/521295/seeding-the-random-number-generator-in-javascript https://stackoverflow.com/questions/521295/seeding-the-rando... I use it for my generative art project https://bigf.art https://bigf.art

ot 4y ago

> I ended up implementing the Fowler–Noll–Vo 1a hash, which is known for trading some quality for increased performance. It was designed to be fast This is a surprisingly resistant belief. It may have been true once, but today FNV is not even close to being a fast hash function. Check the SMHasher benchmarks: https://github.com/rurban/smhasher#smhasher https://github.com/rurban/smhasher#smhasher FNV1a almost 2x slower than blake3, a cryptographic hash function! More than 10x slower than modern hashers such as Farm, City, Spooky, ..., all of which have far better statistical quality than FNV1. There is no good reason to use an FNV function nowadays.

thisismyswamp 4y ago
Thanks for bringing this up! Someone replied mentioning implementation simplicity, and indeed that was an important factor that I forgot to mention in the post. Although the most important factor may have been that FNV is just easier to find. Looking for a hash algorithm is hard, the names are weird and opaque and it's hard to find a user friendly ranking or clear directions on how to pick one.
rurban 4y ago
The best reason to use FNV is its small codesize, which pays off in icache critical code. such as hash tables. that's why I added the hash tables benchmarks to smhasher. cycles/map shows you that FNV1a is very good with hash tables, 4x faster than the blake3 monstrosity
ris 4y ago
> There is no good reason to use an FNV function nowadays. Implementation simplicity? Sometimes you need a hash function in an environment that's not a Real Programming Language.
vlmutolo 4y ago
XxHash has some great benchmarks for various hash functions. FNV is still competitive for small inputs. Most hash functions are built to have high throughput for hashing hundreds of bytes or more. XxHash in particular has an explicit mode switch from "small data" to "big data" sizes around a couple hundred bytes (it varies by platform and compiler). It's hard to do both small and big data correctly, and FNV is one of the few that optimizes for small data. For moderately small data, larger than around 4 bytes, xxh3 beats it handily. But for extremely small sizes, FNV is still the winner. Honestly people should probably just try to switch to xxh3 if performance is a concern, but FNV is certainly competitive for integer-size keys. https://github.com/Cyan4973/xxHash/wiki/Performance-comparison#benchmarks-concentrating-on-small-data- https://github.com/Cyan4973/xxHash/wiki/Performance-comparis...

a_e_k 4y ago

See also "GPU Random Numbers via the Tiny Encryption Algorithm" by Zafar, Olano, and Curtis. HPG '10: Proceedings of the Conference on High Performance Graphics Paper: https://www.csee.umbc.edu/~olano/papers/GPUTEA.pdf https://www.csee.umbc.edu/~olano/papers/GPUTEA.pdf Slides: https://highperformancegraphics.org/previous/www_2010/media/GPUAlgorithms/HPG2010_GPUAlgorithms_Zafar.pdf https://highperformancegraphics.org/previous/www_2010/media/...

Lerc 4y ago

For my stack based texture generator I used (utilizing https://github.com/skeeto/hash-prospector https://github.com/skeeto/hash-prospector ) let intHash = x => { x *= 0xed5ad4bb; x ^= x >> 11; x = Math.imul(x,0xac4c1b51); x ^= x >> 15; x = Math.imul(x,0x31848bab); x ^= x >> 14; return x; } With a little wrapper to blend it with a seed via intHash(x+inthash(x+seed)) Used in a Perlin flame here http://fingswotidun.com/stackie/?code=x1x-*5*dx4**y3*p%2By!-&palette=xy!1%2B*e&seed=991150 http://fingswotidun.com/stackie/?code=x1x-*5*dx4**y3*p%2By!-...

WaxedChewbacca 4y ago

dannyking 4y ago

If you'd like to see an implementation of something that uses Perlin noise, check out this generative art project I did: https://dannyking.uk/artwork/colororbs https://dannyking.uk/artwork/colororbs Perlin noise is how the lines flow togeher rather than crossing each other during the animations. I have a technical write up that explains how it works at the bottom.

mleonhard 4y ago
Thanks for sharing that. Someday, an AI will want an eye-catching way to display its mood to others. I expect it will use images like your color orbs.