2D Perlin Noise (gradient noise) range = ?

Matthew Doucette · 2005-01-10T09:24:21

What is the range of 2D Perlin Noise? To be explicitly clear, I am asking about only one layer of 'gradient noise'. Gradient noise is an interpolation of gradients, which is what Perlin Noise actually is. I am *not* asking about 'value noise' which is an interpolation of values. More specifically, I am asking directly about Ken Perlin's actual 1985 implementation of Perlin Noise: http://mrl.nyu.edu/~perlin/doc/oscar.html#noise (Sorry for all that, but there is much confusion out there about what Perlin Noise actually is.) My (on paper) calculated range is -sqrt(0.5)..sqrt(0.5), not -1..1 as everyone assumes. sqrt(0.5) = 0.707106781... Upon testing, my implementation's range is also -sqrt(0.5)..sqrt(0.5). The actual range determined by polling the entire (0.0..256.0,0.0..256.0) x,y range at 0.01 intervals was: min..max=-0.694254..0.695643 (very close to -0.707..0.707) LilBudyWizer also came up with the same range in this thread: (If you choose to read the thread, please note that most responses in this thread completely misunderstood where LilBudyWizer was coming from and what he was asking.) http://www.gamedev.net/community/forums/topic.asp?topic_id=255173 ... If we are correct, to make Perlin Noise output a range of exactly -1..1, the result must be scaled by sqrt(2). Can you please test your own Perlin Noise implementations and see if you have the same results? Thanks. [Edited by - Doucette on November 29, 2004 2:28:09 PM]

technobot

239

December 06, 2004 12:51 PM

Quote:Original post by Dmytry
Ohh. it is not Gaussian, and never were Gaussian.

Gaussian distribution have __infinite__ range. And old version of Perlin noise was just gaussian-like too, it isn't possible for it to produce values outside of -1..1 range, if implemented properly.

I stand corrected on the distribution. Yes, it is only guassian-like even for the old noise. As for the range breaches, we only get those for the new version.

Quote:
As about smaller ranges than -1..1, you get smaller range if you use 3D noise and sample it on z=0 or z=1, etc. plane.

Our proofs and our testing suggest a maximum value of only about 0.87 for old 3D noise, produced at (0.5, 0.5, 0.5) - obviously not an integer z. If you have a proof that shows it should be -1..1 range for the old noise, please post it..

Quote:
hmm, maybe you're right, that noise is outta -1..1 range. I had proof only for old noise.

It would be good to find points in original implementation
*** Source Snippet Removed ***
that give results outside of -1..1 range, and then send mail to Perlin.

If you look at the thread I linked to in my first post, I posted my implementation against perlin's (the one you posted above). The two are algorythmically identical, and I am occasionally getting values outside the -1..1 range, up to 1.036 or so IIRC.

Michael K.

Matthew Doucette

384

Author

December 06, 2004 05:44 PM

Quote:Original post by Dmytry
hmm, maybe you're right, that noise is outta -1..1 range. I had proof only for old noise.

I think we are right. Did you arrive at a value of 1.02587890625, too? Please post the value you came up with.

Quote:Original post by Dmytry
It would be good to find points in original implementation that give results outside of -1..1 range, and then send mail to Perlin.

Just to clarify, you mean the original implementation of "improved" 2002 Perlin Noise, *not* the "original" 1985 Perlin Noise. gamelife has already come up with an example point and gradient vectors. The problem with testing in someone else's code (even Perlin's) is making sure the gradient vectors at each lattice corner of the current "cel" is proper.

Matthew Doucette, Xona Games

Dmytry

1,151

December 07, 2004 02:36 AM

About old noise , let's call it noise85 :

talk about 2D case where i proved that in 2D, old noise is -1..1 .

I was bit wrong about multiple dimensions, corrected:

3D case:
If we have 8 maximal gradients from corners pointing to center of cube, each gradient is [+-1,+-1,+-1] . dot product with center pos is 3*0.5=1.5

We have result of ease function = 3*0.25+2*0.125=0.5 in center.
We have product of 3 ease functions = 0.125
"Noise" in center is equal to 0.125*1.5*8=1.5
So it's needed to scale everything by 1/1.5 to fit into range. The best is to scale constants in ease function.

Don't see from where 0.87 or sqrt(2) can come, unless you make your random gradients be unit length (and Perlin doesn't).

About new "improved noise":

It would be the best to write java(!) program that uses code of reference implementation improved noise, and finds point where value is outside of -1..1 range. Have no time to do that. Then, if we find point in reference implementation where value is out of -1..1 range, we'll be able to mail Perlin. But only then, because he is probably spammed with e-mails about problems with wrong implementations of his noise, and will not read "equivalent implementations".
(BTW, my equivalent implementation never gave results outside of -1..1 range)

technobot

239

December 07, 2004 10:29 AM

Quote:Original post by Dmytry
About old noise , let's call it noise85 :

talk about 2D case where i proved that in 2D, old noise is -1..1 .

I'm afraid I don't entirely understand where your calculations are coming from, and I don't have the patience to read that whole thread... [rolleyes]

Quote:
I was bit wrong about multiple dimensions, corrected:

3D case:
If we have 8 maximal gradients from corners pointing to center of cube, each gradient is [+-1,+-1,+-1] . dot product with center pos is 3*0.5=1.5

We have result of ease function = 3*0.25+2*0.125=0.5 in center.
We have product of 3 ease functions = 0.125
"Noise" in center is equal to 0.125*1.5*8=1.5
So it's needed to scale everything by 1/1.5 to fit into range. The best is to scale constants in ease function.

Don't see from where 0.87 or sqrt(2) can come, unless you make your random gradients be unit length (and Perlin doesn't).

Refering to the original 1983 implementation, linked to by Doucette and also on page 6 of Ken's talk (end of 2nd paragraph), it is clear that Ken does normalize his gradient vectors:

...static void init(void){	int i, j, k;	for (i = 0 ; i < B ; i++) {		p = i;		g1 = (float)((random() % (B + B)) - B) / B;		for (j = 0 ; j < 2 ; j++)			g2[j] = (float)((random() % (B + B)) - B) / B;		normalize2(g2);		for (j = 0 ; j < 3 ; j++)			g3[j] = (float)((random() % (B + B)) - B) / B;		normalize3(g3);...

(notice the "normalize" calls)

This is also confirmed on page 17b of Ken's talk (last two paragraphs, last sentence in particular):

Quote:
So my Monte Carlo simulation worked as follows: I generated uniformally random points within the cube which surrounds the unit sphere. I threw out all the points that lie outside the unit sphere and kept all the points that lie inside the unit sphere. These are the points for which x2+y2+z2 < 1.

I stopped this process only when I had filled up a table of 256 entries. I then normalized all the entries in the table, and I was done.

This results in the reduced ranges that I've listed earlier, with the general formula of -0.5*Sqrt(n)..0.5*Sqrt(n), n being the noise dimension. If we adjust my proof from page 1 to use non-normalized gradient vectors, then we instead get -0.5*n..0.5*n. This is consistant with your ranges of -1..1 for 2D and -1.5..1.5 for 3D. However, as shown above, Ken does normalize his gradient vectors, so we get the former case.

Michael K.

Dmytry

1,151

December 07, 2004 05:06 PM

Hmm. You're right, original Perlin noise is not what i use... strange, in fact. I'm working with noise always rescaled to -1..1 range, either by changing ease function, or by final scaling...
also, i would never renormalize random values... unnecessary slowdown, there's other faster methods to discriminate against too long vectors.(e.g. |X|+|Y|+|Z| normalization)

Still, it would be alot better/more useful to find points that is outside -1..1 range in reference implementation *unchanged* (that is, in Java.) , as then one who find it will be able to mail to Perlin himself and get a reply if mail is well-written :-), consider it to be kinda challenge with prize.

Quote:Original post by technobot
Quote:Original post by Dmytry
About old noise , let's call it noise85 :

talk about 2D case where i proved that in 2D, old noise is -1..1 .

I'm afraid I don't entirely understand where your calculations are coming from, and I don't have the patience to read that whole thread... [rolleyes]
Quote:
I was bit wrong about multiple dimensions, corrected:

3D case:
If we have 8 maximal gradients from corners pointing to center of cube, each gradient is [+-1,+-1,+-1] . dot product with center pos is 3*0.5=1.5

We have result of ease function = 3*0.25+2*0.125=0.5 in center.
We have product of 3 ease functions = 0.125
"Noise" in center is equal to 0.125*1.5*8=1.5
So it's needed to scale everything by 1/1.5 to fit into range. The best is to scale constants in ease function.

Don't see from where 0.87 or sqrt(2) can come, unless you make your random gradients be unit length (and Perlin doesn't).

Refering to the original 1983 implementation, linked to by Doucette and also on page 6 of Ken's talk (end of 2nd paragraph), it is clear that Ken does normalize his gradient vectors:

*** Source Snippet Removed ***
(notice the "normalize" calls)

This is also confirmed on page 17b of Ken's talk (last two paragraphs, last sentence in particular):
Quote:
So my Monte Carlo simulation worked as follows: I generated uniformally random points within the cube which surrounds the unit sphere. I threw out all the points that lie outside the unit sphere and kept all the points that lie inside the unit sphere. These are the points for which x2+y2+z2 < 1.

I stopped this process only when I had filled up a table of 256 entries. I then normalized all the entries in the table, and I was done.

This results in the reduced ranges that I've listed earlier, with the general formula of -0.5*Sqrt(n)..0.5*Sqrt(n), n being the noise dimension. If we adjust my proof from page 1 to use non-normalized gradient vectors, then we instead get -0.5*n..0.5*n. This is consistant with your ranges of -1..1 for 2D and -1.5..1.5 for 3D. However, as shown above, Ken does normalize his gradient vectors, so we get the former case.

Matthew Doucette

384

Author

December 08, 2004 01:22 PM

To clarify, I am speaking of the "original" Perlin Noise from 1985.

Quote:Original post by Dmytry
About old noise , let's call it noise85 :

talk about 2D case where i proved that in 2D, old noise is -1..1 .

That proof was wrong because the gradient vectors were not normalized.

Quote:Original post by Dmytry
I was bit wrong about multiple dimensions, corrected:

3D case:
If we have 8 maximal gradients from corners pointing to center of cube, each gradient is [+-1,+-1,+-1] . dot product with center pos is 3*0.5=1.5

We have result of ease function = 3*0.25+2*0.125=0.5 in center.
We have product of 3 ease functions = 0.125
"Noise" in center is equal to 0.125*1.5*8=1.5
So it's needed to scale everything by 1/1.5 to fit into range. The best is to scale constants in ease function.

Also, this proof is wrong because the gradient vectors are not normalized.

Quote:Original post by Dmytry
Don't see from where 0.87 or sqrt(2) can come, unless you make your random gradients be unit length (and Perlin doesn't).

Yes he does (as technobot has already explained and you have already admitted to in a latter post.) I just wanted to make it clear.

...

Now, regarding "Improved Noise" Perlin Noise, 2002:

Quote:Original post by Dmytry
It would be the best to write java(!) program that uses code of reference implementation improved noise, and finds point where value is outside of -1..1 range. Have no time to do that. Then, if we find point in reference implementation where value is out of -1..1 range, we'll be able to mail Perlin. But only then, because he is probably spammed with e-mails about problems with wrong implementations of his noise, and will not read "equivalent implementations".

Good point. I do not have enough java experience to do this or I would.

Quote:Original post by Dmytry
(BTW, my equivalent implementation never gave results outside of -1..1 range)

True, but you only tried a mere one million tests. That is not enough. I had to try 62 million samples just to break the -1..1 barrier at one end. I had to try 235 million samples to break both ends of the -1..1 barrier.

As I have meant to do before, I will go over Perlin's code and see if there is something we are missing. That's the only possible explanation for our results to be wrong.

Matthew Doucette, Xona Games

Matthew Doucette

384

Author

December 08, 2004 01:28 PM

Quote:Original post by Dmytry
Hmm. You're right, original Perlin noise is not what i use... strange, in fact. I'm working with noise always rescaled to -1..1 range, either by changing ease function, or by final scaling...
also, i would never renormalize random values... unnecessary slowdown, there's other faster methods to discriminate against too long vectors.(e.g. |X|+|Y|+|Z| normalization)

Normalizing is not slow as the gradient vectors are pre-stored. You only have to create (and normalize) them once.

Quote:Original post by Dmytry
Still, it would be alot better/more useful to find points that is outside -1..1 range in reference implementation *unchanged* (that is, in Java.) , as then one who find it will be able to mail to Perlin himself and get a reply if mail is well-written :-), consider it to be kinda challenge with prize.

I agree, as this would remove all the chance that we have just implemented it wrong. I do not have sufficient Java experience or I would do this right now.

Matthew Doucette, Xona Games

Dmytry

1,151

December 09, 2004 05:10 AM

proof was correct... it was just proof for different noise [grin]
actually i have not stored gradients in tables in my implementation...

Maybe you can find what cell (in 256*256*256 grid) corresponds to maximum you have found? (have same, turned or mirrored or symmetric gradients to examined ones), and therefore find point where it must be outside -1..1 range in original code...

[Edited by - Dmytry on December 9, 2004 7:10:39 AM]

Matthew Doucette

384

Author

December 09, 2004 02:44 PM

Quote:Original post by Dmytry
proof was correct... it was just proof for different noise [grin]

Quite true! :)

Quote:Original post by Dmytry
actually i have not stored gradients in tables in my implementation...

Why not? It is much faster to pre-calc and store the gradient vectors!

Quote:Original post by Dmytry
Maybe you can find what cell (in 256*256*256 grid) corresponds to maximum you have found? (have same, turned or mirrored or symmetric gradients to examined ones), and therefore find point where it must be outside -1..1 range in original code...

What developer environment should I use to code Java? I will code his original noise and figure this out. Unless, someone else does it before me!

Matthew Doucette, Xona Games

Dmytry

1,151

December 10, 2004 05:28 AM

For occasional java work on Windows, i used "scite" as editor(it have user-configurable menu where you can add options "compile", "run" , etc.) with IBM java compiler. You probably already have all necessary java classes in your JVM.

Compilers:
http://www.thefreecountry.com/compilers/java.shtml

scite configuration file(SciTEGlobal.properties) i used(i got it from somewhere and edited...):

# Global initialisation file for SC1.EXE used with Jikes & MS VM# Place in Windows directory along with Sc1.EXE#This is the line for compiling with jikes on Windows98#jc=jikes +E -classpath C:\Windows\java\classes\classes.zip#jc=jikes +E -classpath C:\Windows\java\classes\rt.jarjc=jikes +E -classpath "C:\40gb\program files\java\j2re1.4.0\lib\rt.jar"pasc=c:\freepasc.al\bin\go32v2\fpccppc=compile.bat#I think that this is the line for compiling on NT & 2K#jc=jikes +E -classpath C:\WINNT\java\classes\classes.zip#Compiling & running Java programs with the MS VMcommand.compile.*.java=$(jc) $(FileNameExt)command.compile.*.cpp=$(cppc) $(FileNameExt)command.build.*.java=$(jc) $(FileNameExt)command.build.*.cpp=$(cppc) $(FileNameExt)#command.go.*.java=jview $(FileName)command.go.*.java=java $(FileName)command.go.subsystem.*.java=0command.go.*.cpp=$(FileName)#pascalcommand.compile.*.pas=$(pasc) $(FileNameExt)command.build.*.pas=$(pasc) $(FileNameExt)command.go.*.pas=start $(FileName).execommand.go.subsystem.*.pas=0# Change preceeding line to =2 if you want to launch GUI apps instead# These use the HTML - Help Viewer to view HTML pages [instead of the browser]# Change hh to launch your browser if you likecommand.go.*.html=hh $(FilePath)command.go.subsystem.*.html=1# This adds the Appletviewer command to the menu and launches it when# the current file in the editor is an html file.command.name.0.*.html=Appletviewercommand.0.*.html=jview /a $(FileNameExt)command.subsystem.0.*.html=1#my owncommand.name.0.*.java=ViewAppletcommand.0.*.java=appv.bat $(FileName)command.subsystem.0.*.java=0command.name.1.*.java=ViewApplet in browsercommand.1.*.java=appv_ie.bat $(FileName)command.subsystem.1.*.java=0# Globals# Number of files open at oncebuffers=10# Tabs & indentingtabsize=4indent.size=4use.tabs=0indent.automatic=1indent.opening=0indent.closing=0caret.period=500# Window sizeposition.left=1position.top=1position.width=640position.height=480are.you.sure=1line.numbers=0#Toolbar, tabbar, & statusbarstatusbar.visible=1toolbar.visible=1tabbar.visible=1tabbar.multiple=1buffered.draw=1selection.back=#E0E0E8split.vertical=0use.palette=0margin.width=16blank.margin.left=4blank.margin.right=4clear.before.execute=0braces.check=1braces.sloppy=1edge.column=200edge.mode=0edge.colour=#C0DCC0default.file.ext=.javaview.whitespace=0view.indentation.whitespace=1view.indentation.guides=1highlight.indentation.guides=1win95.death.delay=1000# enable folding, and show lines below when collapsed.fold=1fold.flags=16fold.use.plus=1chars.alpha=abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZchars.numeric=0123456789#removed for shortness:#chars.accented=source.files=*.py;*.c;*.cc;*.cpp;*.cxx;*.h;*.hh;*.hxx;*.hpp;*.idl;*.rc;*.java;*.js;*.vb;*.vbs;makefile;makefile_vc;makefile_bor;*.lua;*.html;*.properties;*.pas;# The open.filter setting os only used on Windows where the file selector has a menu of filters to apply# to the types of files seen when opening.open.filter=All Source|$(source.files)|All Files (*.*)|*.*|$(filter.python)$(filter.cpp)$(filter.java)$(filter.web)$(filter.js)$(filter.vb)$(filter.properties)$(filter.text)$(filter.idl)$(filter.lua)$(filter.perl)$(filter.php)$(filter.sql)$(filter.pas)# Japanese#code.page=932# Unicode#code.page=65001code.page=0import cppimport htmlimport lateximport luaimport othersimport perlimport pythonimport sqlimport vb# Give symbolic names to the set of fonts used in the standard styles.font.base=font:Courier,size:12font.small=font:Courier,size:10font.comment=font:Courier,size:12font.text=font:Courier,size:12font.monospace=font:Courier Bold,size:12font.vbs=font:Lucida Sans Unicode,size:12font.js=$(font.comment)# Global default styles for all languages# Defaultstyle.*.32=$(font.base)# Line numberstyle.*.33=back:#C0C0C0,$(font.base)# Brace highlightstyle.*.34=fore:#0000FF,bold# Brace incomplete highlightstyle.*.35=fore:#FF0000,bold# Control charactersstyle.*.36=# Indentation guidesstyle.*.37=fore:#C0C0C0,back:#FFFFFF

edit: can somebody tell me why "source" box extends horisontally so much?

2D Perlin Noise (gradient noise) range = ?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

2D Perlin Noise (gradient noise) range = ?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines