Too Many Instructions: Cutting Down On the Noise
So, the implementation of Improved Perlin noise from GPU Gems 2 boils down to 48 pixel shader instruction slots (9 texture, 39 arithmetic). That's one octave of noise. What I needed, desperately, was a faster implementation of noise, where the base quality doesn't matter (especially useful for things such as fBm and the like).
In the FIRST GPU Gems, in the chapter on Improved Perlin Noise, Ken Perlin makes a quick note about how to make a cheap approximation of perlin noise in the shader, using a volume texture. The technique is straight forward, but it took me some effort to understand exactly what was supposed to go into the volume texture.
In my case, I ended up using a 32x32x32 volume texture to simulate an 8x8x8 looping sample of perlin noise space. Essentially, when sampling this texture, divide the world position by 8, and use that as the (wrapped) texcoord into the volume.
Crazy 8s: Modifying Perlin Noise To Loop At A Specified Location
The first trick is that it has to be LOOPING Perlin noise. But how do you generate such a thing?
Turns out, in the reference implementation of Improved Noise, there are a bunch of instances where there are +1s. For instance:
A = p[X ]+Y;AA = p[A]+Z;AB = p[A+1]+Z;B = p[X+1]+Y;BA = p+Z;BB = p[B+1]+Z;(Later, AA, AB, BA, and BB are also accessed with +1s).
Figuring out how to make the noise wrap at a specific value (in my case, 8), was a matter of rethinking those as follows:
A = p[X ]; // note: no +Y hereAA = p[A+Y] (+Z); // +Z in parens because it actually gets added later, like the Y does hereAB = p[A+(Y+1)] (+Z);B = p[X+1]; // again, no +YBA = p[B+Y] (+Z);BB = p[B+(Y+1)] (+Z);So, really, the +1s are added to the coordinate added earlier.
So, to make the noise wrap at a certain value, you need to take those (coordinate+1)s and change each into a ((coordinate+1)%repeatLocation).
The final version of the texture shader that generates noise that loops at a specific location is as follows:
// permutation tablestatic int permutation[] = { 151,160,137,91,90,15,131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180};// gradients for 3d noisestatic float3 g[] = { 1,1,0, -1,1,0, 1,-1,0, -1,-1,0, 1,0,1, -1,0,1, 1,0,-1, -1,0,-1, 0,1,1, 0,-1,1, 0,1,-1, 0,-1,-1, 1,1,0, 0,-1,1, -1,1,0, 0,-1,-1,};int perm(int i){ return permutation;<br>}<br><br>float3 texfade(float3 t)<br>{<br> <span class="cpp-keyword">return</span> t * t * t * (t * (t * <span class="cpp-number">6</span> - <span class="cpp-number">15</span>) + <span class="cpp-number">10</span>); <span class="cpp-comment">// new curve</span><br><span class="cpp-comment">// return t * t * (3 - 2 * t); // old curve</span><br>}<br><br><span class="cpp-keyword">float</span> texgrad(<span class="cpp-keyword">int</span> hash, float3 p)<br>{<br> <span class="cpp-keyword">return</span> dot(g[hash%<span class="cpp-number">16</span>], p);<br>}<br><br><span class="cpp-keyword">float</span> texgradperm(<span class="cpp-keyword">int</span> x, float3 p)<br>{<br> <span class="cpp-keyword">return</span> texgrad(perm(x), p);<br>}<br><br><br><span class="cpp-keyword">float</span> texShaderNoise(float3 p, <span class="cpp-keyword">int</span> repeat, <span class="cpp-keyword">int</span> base = <span class="cpp-number">0</span>)<br>{<br> int3 I = fmod(floor(p), repeat);<br> int3 J = (I+<span class="cpp-number">1</span>) % repeat.xxx;<br> I += base;<br> J += base;<br> <br> p -= floor(p);<br> <br> float3 f = texfade(p);<br> <br> <span class="cpp-keyword">int</span> A = perm(I.x);<br> <span class="cpp-keyword">int</span> AA = perm(A+I.y);<br> <span class="cpp-keyword">int</span> AB = perm(A+J.y);<br> <br> <span class="cpp-keyword">int</span> B = perm(J.x);<br> <span class="cpp-keyword">int</span> BA = perm(B+I.y);<br> <span class="cpp-keyword">int</span> BB = perm(B+J.y);<br> <br> <span class="cpp-keyword">return</span> lerp( lerp( lerp( texgradperm(AA+I.z, p + float3( <span class="cpp-number">0</span>, <span class="cpp-number">0</span>, <span class="cpp-number">0</span>) ), <br> texgradperm(BA+I.z, p + float3(-<span class="cpp-number">1</span>, <span class="cpp-number">0</span>, <span class="cpp-number">0</span>) ), f.x),<br> lerp( texgradperm(AB+I.z, p + float3( <span class="cpp-number">0</span>, -<span class="cpp-number">1</span>, <span class="cpp-number">0</span>) ),<br> texgradperm(BB+I.z, p + float3(-<span class="cpp-number">1</span>, -<span class="cpp-number">1</span>, <span class="cpp-number">0</span>) ), f.x), f.y),<br> lerp( lerp( texgradperm(AA+J.z, p + float3( <span class="cpp-number">0</span>, <span class="cpp-number">0</span>, -<span class="cpp-number">1</span>) ),<br> texgradperm(BA+J.z, p + float3(-<span class="cpp-number">1</span>, <span class="cpp-number">0</span>, -<span class="cpp-number">1</span>) ), f.x),<br> lerp( texgradperm(AB+J.z, p + float3( <span class="cpp-number">0</span>, -<span class="cpp-number">1</span>, -<span class="cpp-number">1</span>) ),<br> texgradperm(BB+J.z, p + float3(-<span class="cpp-number">1</span>, -<span class="cpp-number">1</span>, -<span class="cpp-number">1</span>) ), f.x), f.y), f.z);<br> <br>}<br><br><br></pre></div><!–ENDSCRIPT–><br><br>Whee!<br><br><br><b>Noise + Real Numbers + Imaginary Numbers == ???</b><br><br>So, the second trick: the texture actually needed to contain two values (R and G channels), to act as real and imaginary parts. Very simple, I added a base parameter (in the code above) so that I could offset into a different 8x8x8 cube of noise. I drop a different 8x8x8 noise into the G channel.<br><br>Finally! We have a texture with 8x8x8 noise. But 8-cubed noise sucks, because it's ridiculously repetative. That's where that weird imaginary part comes into play. You sample the 8-cube volume again, but at 9x scale (so it's lower frequency). You then use the (real component of) high-frequency as an angle (scaled by 2pi) to do a quaternion rotation on the low-frequency noise.<br><br><!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre><br><span class="cpp-keyword">float</span> noiseFast(float3 p)<br>{<br> p /= <span class="cpp-number">8</span>; <span class="cpp-comment">// because the volume texture is 8x8x8 noise, divide the position by 8 to keep this noise in parity with the true Perlin noise generator.</span><br> float2 hi = tex3D(noise3dSampler, p).rg*<span class="cpp-number">2</span>-<span class="cpp-number">1</span>; <span class="cpp-comment">// High frequency noise</span><br> half lo = tex3D(noise3dSampler, p/<span class="cpp-number">9</span>).r*<span class="cpp-number">2</span>-<span class="cpp-number">1</span>; <span class="cpp-comment">// Low frequency noise</span><br> <br> half angle = lo*<span class="cpp-number">2</span>.<span class="cpp-number">0</span>*PI;<br> <span class="cpp-keyword">float</span> result = hi.r * cos(angle) + hi.g * sin(angle); <span class="cpp-comment">// Use the low frequency as a quaternion rotation of the high-frequency's real and imaginary parts.</span><br> <span class="cpp-keyword">return</span> result; <span class="cpp-comment">// done!</span><br>}<br><br><br></pre></div><!–ENDSCRIPT–><br>And that's it! Compare the instruction counts of the real Perlin noise to this fast fake:<br><br><pre><br>Old (high-quality): approximately 48 instruction slots used (9 texture, 39 arithmetic)<br>New (lower-quality): approximately 20 instruction slots used (2 texture, 18 arithmetic)</pre><br>Essentially, wherever I don't need the full quality noise, I can halve my instruction count on noise generation. Score!<br><br>Here's a comparison: on the left, the weird confetticrete chair with the original noise, and on the right is the new faster noise:<br><center><a href="http://deadlyredcube.com/journal/ProcClownChair.jpg"><img src="http://deadlyredcube.com/journal/ProcClownChairs.jpg"/></a><a href="http://deadlyredcube.com/journal/ProcNewNoiseChair.jpg"><img src="http://deadlyredcube.com/journal/ProcNewNoiseChairs.jpg"/></a><br><small>Old (left) vs. New (right)<br>Click to enlarge</small></center><br><br>They look roughly the same, there are some artifacts on the new one (the diamond-shaped red blob on the upper-right of the new chair due to the trilinear filtering), but it's way faster.<br><br><br><b>Cellular Noise</b><br><br>Okay, I have some cool perlin noise stuff. But man cannot live on Perlin noise alone, so I decided to implement cellular noise, as well.<br><br>Turns out, there's something called <a href="http://petewarden.com/notes/archives/2005/05/testing.html">Worley noise</a> which does exactly what I was hoping to do. Implementation was pretty simple.<br><br><!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre><br><span class="cpp-keyword">void</span> voronoi(float3 position, out <span class="cpp-keyword">float</span> f1, out float3 pos1, out <span class="cpp-keyword">float</span> f2, out float3 pos2, <span class="cpp-keyword">float</span> jitter=.<span class="cpp-number">9</span>, <span class="cpp-keyword">bool</span> manhattanDistance = <span class="cpp-keyword">false</span> )<br>{<br> float3 thiscell = floor(position)+.<span class="cpp-number">5</span>;<br> f1 = f2 = <span class="cpp-number">1000</span>;<br> <span class="cpp-keyword">float</span> i, j, k;<br> <br> float3 c;<br> <span class="cpp-keyword">for</span>(i = -<span class="cpp-number">1</span>; i <= <span class="cpp-number">1</span>; i += <span class="cpp-number">1</span>)<br> {<br> <span class="cpp-keyword">for</span>(j = -<span class="cpp-number">1</span>; j <= <span class="cpp-number">1</span>; j += <span class="cpp-number">1</span>)<br> {<br> <span class="cpp-keyword">for</span>(k = -<span class="cpp-number">1</span>; k <= <span class="cpp-number">1</span>; k += <span class="cpp-number">1</span>)<br> {<br> float3 testcell = thiscell + float3(i,j,k);<br> float3 randomUVW = testcell * float3(<span class="cpp-number">0</span>.<span class="cpp-number">037</span>, <span class="cpp-number">0</span>.<span class="cpp-number">119</span>, .<span class="cpp-number">093</span>);<br> float3 cellnoise = perm(perm2d(randomUVW.xy)+randomUVW.z);<br> float3 pos = testcell + jitter*(cellnoise-.<span class="cpp-number">5</span>);<br> float3 offset = pos - position;<br> <span class="cpp-keyword">float</span> dist;<br> <span class="cpp-keyword">if</span>(manhattanDistance)<br> dist = abs(offset.x)+abs(offset.y) + abs(offset.z); <br> <span class="cpp-keyword">else</span><br> dist = dot(offset, offset);<br> <span class="cpp-keyword">if</span>(dist < f1)<br> {<br> f2 = f1;<br> pos2 = pos1;<br> f1 = dist;<br> pos1 = pos;<br> }<br> <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span>(dist < f2)<br> {<br> f2 = dist;<br> pos2 = pos;<br> }<br> }<br> }<br> }<br> <span class="cpp-keyword">if</span>(!manhattanDistance)<br> {<br> f1 = sqrt(f1);<br> f2 = sqrt(f2);<br> }<br>}<br><br><br></pre></div><!–ENDSCRIPT–><br>The gist is that each unit cube cell has a randomly-placed point in it. for each point being evaluated by the shader, you find the distance to the nearest point (a value called "F1"), and the distance to the next-nearest ("F2"), etc (to as many as you care about - though anything past F4 starts to look similar and uninteresting). Using linear combinations of these distances gives interesting results:<br><br><center><a href="http://deadlyredcube.com/journal/F1.jpg"><img src="http://deadlyredcube.com/journal/F1s.jpg"/></a><a href="http://deadlyredcube.com/journal/F2.jpg"><img src="http://deadlyredcube.com/journal/F2s.jpg"/></a><br><small>Left: F1 Right: F2<br>Click to enlarge</small><br><br><a href="http://deadlyredcube.com/journal/F2mF1.jpg"><img src="http://deadlyredcube.com/journal/F2mF1s.jpg"></a><a href="http://deadlyredcube.com/journal/F1F2avg.jpg"><img src="http://deadlyredcube.com/journal/F1F2avgs.jpg"/></a><br><small>Left: F2-F1 Right: (F1+F2)/2<br>Click to enlarge</small></center><br><br>Something cool to do, also, is to use <a href="http://en.wikipedia.org/wiki/Taxicab_geometry">Manhattan distance</a> instead of standard Euclidian distance to calculate the distance. You end up with much more angular results. Here are the same 4 calculations, using manhattan distance:<br><br><center><a href="http://deadlyredcube.com/journal/F1manhattan.jpg"><img src="http://deadlyredcube.com/journal/F1manhattans.jpg"/></a><a href="http://deadlyredcube.com/journal/F2manhattan.jpg"><img src="http://deadlyredcube.com/journal/F2manhattans.jpg"/></a><br><a href="http://deadlyredcube.com/journal/F2mF1manhattan.jpg"><img src="http://deadlyredcube.com/journal/F2mF1manhattans.jpg"></a><a href="http://deadlyredcube.com/journal/F1F2avgmanhattan.jpg"><img src="http://deadlyredcube.com/journal/F1F2avgmanhattans.jpg"/></a><br><small>Click to enlarge</small></center><br><br>Considering that a few levels of my current project will take place in a metallic fortress, this will especially come in handy.<br><br>So, what can you do with these?<br><br>I, predictably, have made a few test textures:<br><br><a href="http://deadlyredcube.com/journal/CellularA.jpg"><img src="http://deadlyredcube.com/journal/CellularAs.jpg"/></a><a href="http://deadlyredcube.com/journal/CellularB.jpg"><img src="http://deadlyredcube.com/journal/CellularBs.jpg"/></a><a href="http://deadlyredcube.com/journal/CellularC.jpg"><img src="http://deadlyredcube.com/journal/CellularCs.jpg"/></a><br><small>Click to enlarge</small></center><br><br>Also, it still looks pretty cool if you use fBm on it. For instance:<br><center><a href="http://deadlyredcube.com/journal/F1fBm.jpg"><img src="http://deadlyredcube.com/journal/F1fBms.jpg"/></a><br><small>4 octaves of F1 Worley noise</small></center><br><br>But I hear you asking "duz it wrok n 3deez, Drilian?!?!?!" Oh, I assure you it does!<br><br><center><a href="http://deadlyredcube.com/journal/CellDiscoChair.jpg"><img src="http://deadlyredcube.com/journal/CellDiscoChairs.jpg"/></a><br><small>Click to enlarge</small></center><br>And now I hear you asking "Can u stop typing nau? I is tir0d of reedin." (or alternately, "I is tir0d uv looking @ imagez sparsely scattered thru the text taht I dun feel liek reedin.") To this, I say: Sure, but it worries me that you're asking your questions in some form of lolcat.<br><br>That's all I got.<div>
</div>
