Fastest PerlinNoise : Improved version bicubic&bilinear grad&value noise

[DzzD]

another fastest something

needing a very fast Perlin noise generator, I look around on internet and did not find anything suitable, so I decided to built my own, absolutly nothing revolutionary it work the same as described by Ken Perlin on his website except that the implementation have been highly optimized.

Usage :

Raw noise :

Raw noise through a cloud function :

More advanced usage:

[url=http://demo.dzzd.net/Sky/3/]
Click to try Online Applet

[/url]

[url=http://demo.dzzd.net/Sky]

Try online Applet[/url]

It can be easily improved to use different or dynamic octave/persistence :

/*
* This file is part of 3DzzD http://dzzd.net/.
*
* Released under LGPL
*
* 3DzzD is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* 3DzzD is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 3DzzD.  If not, see <http://www.gnu.org/licenses/>.
*
* Copyright 2005 - 20010 Bruno Augier
*/


/**
 * Fast perlin noise generation
 *
 * Generate a perlin noise with 8 octave and a persistence of 0.5
 *
 * NB: 
 * - output range between 0 and 255
 * - maximum octave = 7
 * 
 * you can change type of noise between grad & value noise by commenting/uncommenting block
 * you can change type of interpolation between bicubic/bilinear by commenting/uncommenting block
 */
public class FastNoise
{
	public static int noise(double x,double y,int nbOctave)
	{
		int result=0;		
		int frequence256=256; 
		int sx=(int)((x)*frequence256); 
		int sy=(int)((y)*frequence256); 
		int octave=nbOctave;	
		while(octave!=0) 
		{
			int bX=sx&0xFF;
			int bY=sy&0xFF;

			int sxp=sx>>8;
			int syp=sy>>8;
			

			//Compute noise for each corner of current cell
			int Y1376312589_00=syp*1376312589;
			int Y1376312589_01=Y1376312589_00+1376312589;

			int XY1376312589_00=sxp+Y1376312589_00;
			int XY1376312589_10=XY1376312589_00+1;
			int XY1376312589_01=sxp+Y1376312589_01;
			int XY1376312589_11=XY1376312589_01+1;

			int XYBASE_00=(XY1376312589_00<<13)^XY1376312589_00;
			int XYBASE_10=(XY1376312589_10<<13)^XY1376312589_10;
			int XYBASE_01=(XY1376312589_01<<13)^XY1376312589_01;
			int XYBASE_11=(XY1376312589_11<<13)^XY1376312589_11;

			int alt1=(XYBASE_00 * (XYBASE_00 * XYBASE_00 * 15731 + 789221) + 1376312589) ;
			int alt2=(XYBASE_10 * (XYBASE_10 * XYBASE_10 * 15731 + 789221) + 1376312589) ;
			int alt3=(XYBASE_01 * (XYBASE_01 * XYBASE_01 * 15731 + 789221) + 1376312589) ;
			int alt4=(XYBASE_11 * (XYBASE_11 * XYBASE_11 * 15731 + 789221) + 1376312589) ;
			
			/*
			 *NOTE : on  for true grandiant noise uncomment following block
			 * for true gradiant we need to perform scalar product here, gradiant vector are created/deducted using
			 * the above pseudo random values (alt1...alt4) : by cutting thoses values in twice values to get for each a fixed x,y vector 
			 * gradX1= alt1&0xFF 
			 * gradY1= (alt1&0xFF00)>>8
			 *
			 * the last part of the PRN (alt1&0xFF0000)>>8 is used as an offset to correct one of the gradiant problem wich is zero on cell edge
			 *
			 * source vector (sXN;sYN) for scalar product are computed using (bX,bY)
			 *
			 * each four values  must be replaced by the result of the following 
			 * altN=(gradXN;gradYN) scalar (sXN;sYN)
			 *
			 * all the rest of the code (interpolation+accumulation) is identical for value & gradiant noise
			 */
			 
			 
			/*START BLOCK FOR TRUE GRADIANT NOISE*/
			
			 int grad1X=(alt1&0xFF)-128;
			 int grad1Y=((alt1>>8)&0xFF)-128;
			 int grad2X=(alt2&0xFF)-128;
			 int grad2Y=((alt2>>8)&0xFF)-128;
			 int grad3X=(alt3&0xFF)-128;
			 int grad3Y=((alt3>>8)&0xFF)-128;
			 int grad4X=(alt4&0xFF)-128;
			 int grad4Y=((alt4>>8)&0xFF)-128;
			 
			 
			 int sX1=bX>>1;
			 int sY1=bY>>1;
			 int sX2=128-sX1;
			 int sY2=sY1;
			 int sX3=sX1;
			 int sY3=128-sY1;
			 int sX4=128-sX1;
			 int sY4=128-sY1;
			 alt1=(grad1X*sX1+grad1Y*sY1)+16384+((alt1&0xFF0000)>>9); //to avoid seams to be 0 we use an offset
			 alt2=(grad2X*sX2+grad2Y*sY2)+16384+((alt2&0xFF0000)>>9);
			 alt3=(grad3X*sX3+grad3Y*sY3)+16384+((alt3&0xFF0000)>>9);
			 alt4=(grad4X*sX4+grad4Y*sY4)+16384+((alt4&0xFF0000)>>9);
			 
			/*END BLOCK FOR TRUE GRADIANT NOISE */
			
			
			/*START BLOCK FOR VALUE NOISE*/
			/*
			 alt1&=0xFFFF;
			 alt2&=0xFFFF;
			 alt3&=0xFFFF;
			 alt4&=0xFFFF;
			 */
			/*END BLOCK FOR VALUE NOISE*/
			
			
			/*START BLOCK FOR LINEAR INTERPOLATION*/
			//BiLinear interpolation 
			/*
			int f24=(bX*bY)>>8;
			int f23=bX-f24;
			int f14=bY-f24;
			int f13=256-f14-f23-f24;

			int val=(alt1*f13+alt2*f23+alt3*f14+alt4*f24);
			*/
			/*END BLOCK FOR LINEAR INTERPOLATION*/
			
			
			
			//BiCubic interpolation ( in the form alt(bX) = alt[n] - (3*bX^2 - 2*bX^3) * (alt[n] - alt[n+1]) )
			/*START BLOCK FOR BICUBIC INTERPOLATION*/
			int bX2=(bX*bX)>>8;
			int bX3=(bX2*bX)>>8;
			int _3bX2=3*bX2;
			int _2bX3=2*bX3;
			int alt12= alt1 - (((_3bX2 - _2bX3) * (alt1-alt2)) >> 8);
			int alt34= alt3 - (((_3bX2 - _2bX3) * (alt3-alt4)) >> 8);
			
			
			int bY2=(bY*bY)>>8;
			int bY3=(bY2*bY)>>8;
			int _3bY2=3*bY2;
			int _2bY3=2*bY3;
			int val= alt12 - (((_3bY2 - _2bY3) * (alt12-alt34)) >> 8);
			
			val*=256;
			/*END BLOCK FOR BICUBIC INTERPOLATION*/
			
			
			//Accumulate in result
			result+=(val<<octave);
			
			octave--;
			sx<<=1; 
			sy<<=1;
			
		}
		return result>>>(16+nbOctave+1);	
	}
}

[Captain_Awesome]

Thanks for sharing ^^

[DzzD]

arf!! I just see that another little optimisation can be done (avoiding two cast),

source code updated !

changes :

for(int n=0;n<8;n++)		
{			
 int frequence256=frequence*256;			
 int sx=(int)(x*frequence256);			
 int sy=(int)(y*frequence256);
 ...

replaced by :

 int frequence256=frequence*256;
 int sx=(int)(x*frequence256);
 int sy=(int)(y*frequence256);
 for(int n=0;n<8;n++)
 {...
 ...		
 sx<<=1;
 sy<<=1;
 }

[Roquen]

Thanks for post/code. BUT since I’m obviously in a pedantic mood this is “value noise” and not Perlin noise. We might be able to juice some extra cycles out of this by replacing the rng with something simpler. Poke me if I don’t give some options.

[DzzD]

I agree that modifying RNG is probably the easiest way to make it faster, I did not try to re-create one and just picked it somewhere, also in this version final RNGs values are clamped to 0-255, maybe it make some of the computation useless (but it let user able to increase value range easily by modifying the mask 0xFF)

hum… I never realized that it was not true perlin noise… I based it on Hugo Elias explanations, who seems to have made the same confusion as me…

To be true I cant see interrest of perlin noise (using gradiants to mak weighted interpolation) VS “value noise” (maybe you can highlite me ?), difference is only in the interpolation method (weighted) no ?
The above implementation is low quality but I would say that it is IMO more related to the fact it use a linear interpolation rather than it is not a true gradiant noise no ? (I guess that using cubic should give really nice result with still good speed)

[Roquen]

Hugo Elias’s page has been largely responsible for this misunderstand.

Value, Perlin’s gradient & simplex noises are all similar in the types of images that they can create, so if your happy with value noise then there’s no need to change. The downsides of value noise are: It’s slower to create an equivalently complex image, mostly due to the need of higher number of samples to produce. It has ‘worse’ defects.

[DzzD]

[quote]The downsides of value noise are: It’s slower to create an equivalently complex image, mostly due to the need of higher number of samples to produce. It has ‘worse’ defects.
[/quote]
I think I ve understood both technic but still cant get what the benefit of grandiant noise… less samples because no need to iterate on n octave ?

only difference I was able to found was on wikipedia
Unlike the value noise, gradient noise has more energy in the high frequencies
wich I dont understand why too…

here is a local gradiant noise from Ken Perlin himself ( I’ve read that paper a cupple of time but never notice before the link to open this animation :/)

once again I ve trouble to understand benefit of Gradiant noise VS value noise :-\ give me more info plz

[krasse]

I just read in the book “Texturing & Modeling - A procedural approach” the following:

“The gradient method uses an interpolation based on the gradients at the eight corners of a single lattice cell, rather than the 64-vertex neighborhood used in the cubic interpolation method described in the previoius section.”

I interpret this as: The gradient noise is cheaper than value noise if you want a cubic-like function.

The book also mentions that the power spectrum of gradient noise is better than for value noise. The spectrum for gradient noise looks more spread out than for the value noise but still within the required limit. This makes it more varied frequency-wise, which is good for a noise function in terms of predictability and visual regularity perhaps? I am not really sure.

[DzzD]

thanks! those are nice informations

I better understand it now, difference in complexity seems to be more true for more dimension, value noise would requiere 64 vertices for cubic in 3D (cube with 4 vertices per edges => 444 => 64 vertices), in 2D the difference is less significant.

so… I may conclude that : the above value noise implementation is probably faster than the corresponding 2D gradiant noise, but… as it use a linear interpolation the quality is lower, with one more dimension (3D) or a cubis interpolation it wil become not so interresting to use that value noise

If I get enought free time I would like to built a full Integer Gradiant noise too, seeing if it is possible to “shrink” it the same way of value noise

[Roquen]

It’s slower to create an equivalently complex image, mostly due to the need of higher number of samples to produce.

less samples because no need to iterate on n octave?

Yeah. Building with gradient noise will require less combinations (octaves is one example) of samples to create an equivalently complex image vs. value noise. (see next comment)

Unlike the value noise, gradient noise has more energy in the high frequencies

These two are related. Very roughly speaking: In the frequency domain noise needs to be “band-limited” so that it can be an efficient constructive element.

value noise would requiere 64 vertices for cubic in 3D

Value & gradient noise both have the same cell structure. The 64 number comes from the implementation in book adding extra sample points (along edges) and using splines for interpolation. This is insanely expensive.

[DzzD]

Same noise also used to produce realtime waves

http://demo.dzzd.net/Sky/SKYDYN.PNG

[DzzD]

source code update, function now accept a third parameter nbOctave, it should also be a little faster and perform computation with more precision.

Ps: I ve started a true gradiant noise based on this one, seems it will only requiere very few modifications, I will keep this thread up. ( even if I am not yet sure that it will have a real interrest, computation will be a little more complexe and then even if “one octave layer” will look better it will requiere more time so … let’s see)

[DzzD]

yet another sample :

http://demo.dzzd.net/Sky/2/

note that to animate this sampe I did not use a 3D noise, I simply multiply two noise :

finalNoise(x,y,z)=noise2D(x,y)*noise1D(z);

have used such one to make some tests of animating waves in Virtual ocean races 2, seems to give very good result

this can be simply achieved with the above code.

note:
multiplying N noise rather than computing noise in N dimension seems more powerfull for some common usage as you replace the requiered N dimension interpolation by a simple multiplication, in case of precomputed noise it make final noise computation very fast and very low memory (same noise can be used twice with an offset) => only mixing two 2d array (or same 2d array) to get a 4D noise (noise animated in 3D), it probably modify the noise main frequency but it is only a matter of scale.

[DzzD]

Improved version :
enable bicubic and bilinear interpolation
enable value or true gradiant noise (hybrid/improved one : use grad+offset value to avoid cell corner problem : always equals to zero on pure grad noise, in this one an offset is added : basically the above grad version work like if noise(x,y) = gradNoise(x,y)+valueNoise(x,y);

First results of a fast bench tests between version :
cubic interpolation give a noticable quality improvment (but not that much) at cost of speed
grad noise give a more complex image with less octaves also at cost of speed but… as it requiere less octave it maybe finally more interresting in term of speed, need more tests cases to know

NB: this new version run still pretty fast but has not been yet optimized and they may have a cupple of rooms to optimize it

[DzzD]

here is a online Applet demo of the new version using gradiant noise (+ bicubic interpolation) :
[url=http://demo.dzzd.net/Sky/3/]
Click to try Online Applet

[/url]

rendering is better than the old one (mostly because the use of cubic interpolation), but it use less octave and maybe probably a little faster

[Roquen]

Fun. But note (from an earlier post) noise(nD)*noise(1d) is a quite different effect from walking through noise(n+1 D). Stuff like this is what makes play with noise amusing. Finding diffrent ways to combine and create different effects.

[DzzD]

@Roquen

Fun. But note (from an earlier post) noise(nD)*noise(1d) is a quite different effect from walking through noise(n+1 D). Stuff like this is what makes play with noise amusing. Finding diffrent ways to combine and create different effects.

yes inded but in a lot of case, as animating surface it can do the job well ( anyways the above code can be easily extended to N dimensions )

[philfrei]

Beautiful stuff! I love the sun & clouds & especially with the rippling water added. Amazing to see it updated live, as well.

I don’t know if you are concerned about this sort of thing, but I got an odd artifact when I ran the first demo.
http://www.hexara.com/Images/dzzdCloudDemo.JPG

I had moused to the upper middle right area. Using IE8 on WindowsXP.

Also, a comment about sky2 & sky3. The first looks like it could be a “religious hallucination” with lots of crosses coming and going. The second, there is also a bit of banding, but it is more like a topo map. It’s pretty subtle though, not that bad. But I’m wondering if there isn’t some way to filter out these things? I recall reading in a music DSP discussion, one can do linear vs quadratic or cubic interpolation (for example, when taking a sound and stretching it) but the result will still have artifacts despite going to methods with higher computation costs. So, what folks do is to apply a low-pass filter to the data. Is there a similar sort of thing that can be done with these visual noise effects?

(I’m really looking forward to having the time to try programming this stuff myself one of these days. For now, am just watching in awe and with appreciation.)

[CommanderKeith]

Beautiful! I can’t say it looks a lot like clouds the way the clouds appear then disappear. Clouds tend to move across the sky. But it looks very cool and I guess you could easily use your algorithm to make more slowly animating cloud textures and then move them across the sky.

Great work

[DzzD]

[quote]I don’t know if you are concerned about this sort of thing, but I got an odd artifact when I ran the first demo.
[/quote]
this is a mapping problem for the skybox, urelated to the noise itself

[quote]Also, a comment about sky2 & sky3. The first looks like it could be a “religious hallucination” with lots of crosses coming and going. The second, there is also a bit of banding, but it is more like a topo map. It’s pretty subtle though, not that bad. But I’m wondering if there isn’t some way to filter out these things? I recall reading in a music DSP discussion, one can do linear vs quadratic or cubic interpolation (for example, when taking a sound and stretching it) but the result will still have artifacts despite going to methods with higher computation costs. So, what folks do is to apply a low-pass filter to the data. Is there a similar sort of thing that can be done with these visual noise effects?
[/quote]
the first problem arrows on sky2 comme from the interplation method, bilinear interpolation tend to produce such artefact, nothing that can really be done here as it is an inherent problem with bilinear interpolation

about the artefact on sky3 (wich seems to be a discretisation problem often related to lack of precision in integer computation) I think it come from the bicubic interpolation implementation and can be corrected by increasing the precision of the computation, I did not take a lot of attention when doing this one, and as you can see the computed value is multiplied by 256 (it is not with linear), this needed multiplication means that I have used a too low scale for the computation itslef and that it lost 8 bit precision, increasing the computation scale should correct this artefact bug.

[quote]But it looks very cool and I guess you could easily use your algorithm to make more slowly animating cloud textures and then move them across the sky.
[/quote]
yes sure, noise can be used for thousand of effects, I also use it to animate water in a shader in another project