3 ms·
O(n^2) where n is what? If it's the number of pixels, you have to touch those anyway, no? Why can't you create blue noise from walking a Hilbert curve and plac
by abetusk 1y ago
O(n^2) where n is what? If it's the number of pixels, you have to touch those anyway, no?
Why can't you create blue noise from walking a Hilbert curve and placing points randomly with a minimum and maximum threshold?
- inhumantsar 1y agoI was curious about this too so I dug into it a bit. it seems that the point placement has to be optimized to ensure they have roughly even spacing while still being randomly placed. the naive algorithm is O(n^2) where n is the number of pixels in an image. tiling and sampling pregenerated noise is O(n), so that's what most people use. the noise can be generated on the fly using a FFT-based algorithm, though it still needs to be applied iteratively so you'd typically end up with O(k n log n) s.t. 10 <= k <= 100. this has been neat stuff to read up on. my favorite nugget of learning: blue noise is white noise that's fine through a high pass filter a few times. the result of a high pass filter is the same as subtracting the result of a low pass filter from the original signal. blurring is a low pass filter for images. since blue noise is high frequency information, blurring a noised up image effectively removes the blue noise. so the result looks like a blurred version of the original even though it contains a fraction of the original's information.