New Noise Algorithms

For people working on the C++ code.
prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

New Noise Algorithms

by prestidigitator » Sun Mar 17, 2013 23:46

I am messing around with different noise algorithms including Improved Perlin Noise and Simplex Noise, and looking at what it would take to switch base noise algorithms in the server configuration settings and when requesting noise values from the Lua API.

I was wondering if there are any existing tools to test the speed of map generation, so that I can easily compare how the selection of noise algorithms affect it. Is there anything in the GUI, or are there test scripts, or should I just test the functions and classes out separately in standalone code?

Thanks!
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Wed Mar 20, 2013 11:02

Well, I wasn't able to really find anything, so I'm testing straight noise performance using stand-alone test programs.

The first change I made was to go to an object-oriented interface. The old "Noise" class was a step in this direction, but I have made it an interface instead, with virtual methods. Then I implemented LegacyNoise (the current Minetest noise algorithm), PerlinNoise (Improved Perlin Noise), and SimplexNoise.

The result of OO-ifying the API was that individual calls for single noise values slowed down by a factor of 10, but calls that generate whole blocks of data sped up by about 50%. After that, the PerlinNoise and SimplexNoise perform worse than LegacyNoise (about half as fast), but generate much smoother patterns. I'll post a visual comparison at some point.

This is just for a very simple base noise function. I have implemented, but not yet tested, transformed noise (with offsets, smoothing, and input spreading) and fractal noise (multiple octaves). So testing and comparing those will be next.

I'd like to eventually provide an option of switching noise functions, with the default remaining LegacyNoise. I'm not sure whether to stick that in the NoiseParams or just put it in minetest.conf. I'll have to take a look at the parsing and see what is simpler and makes the most sense.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Wed Mar 20, 2013 20:33

Here is the visual comparison. This is just basic noise, not fractal noise (i.e. one octave worth of noise). I used the straight noise function to create 512x512 grayscale images. Each one is for a 40x40 grid of lattice points. For reference, pretend you are seeing an elevation map, looking down at a 10km x 10km area of Minetest map (since the default noise parameters for terrain use a lattice grid spacing of 250m x 250m).

LegacyNoise
Image

PerlinNoise
Image

SimplexNoise
Image
 

User avatar
Mito551
Member
 
Posts: 1271
Joined: Sat Jun 16, 2012 15:03

by Mito551 » Wed Mar 20, 2013 20:47

SimplexNoise looks cool. is there a way to implement them all at once so that they intersect or something? (i'm not that good with programming and stuff)
Last edited by Mito551 on Wed Mar 20, 2013 20:53, edited 1 time in total.
 

User avatar
jojoa1997
Member
 
Posts: 2890
Joined: Thu Dec 13, 2012 05:11
Location: Earth

by jojoa1997 » Wed Mar 20, 2013 20:52

They should all be used differently because you have height, humidity,and other stuff I don't remember
Coding;
1X coding
3X debugging
12X tweaking to be just right
 

User avatar
Mito551
Member
 
Posts: 1271
Joined: Sat Jun 16, 2012 15:03

by Mito551 » Wed Mar 20, 2013 20:53

or some kind of fractal stuff: a set of regions is generated with one type of noise, then environment inside the region is generated with another one. something like that :P
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Wed Mar 20, 2013 23:04

Yeah. I've implemented FractalNoise so its octaves can be built with any of those basic noise algorithms. It would be easy enough to create another variant that could use an arbitrary Noise of any type for each different octave. That'll probably be an exercise for the future though.

Note that I'm going to try to expose this to Lua, too, so when you ask the engine for a noise object you can specify which kind you want. If you use the existing API you'll get LegacyNoise (exactly what you get now). If you add maybe a "type" attribute when you request it, you'll be able to get one of the other types.
Last edited by prestidigitator on Wed Mar 20, 2013 23:06, edited 1 time in total.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 22, 2013 22:55

Okay. So for PerinNoise and SimplexNoise I simplified the lattice point hash function, which was a little heavy for gradient based noise. These noise functions are now a little slower than LegacyNoise for single octaves, but faster for multiple octaves (implemented by wrapping each object with a FractalNoise object)?! Strange, but anyway they seem to be somewhat competative in terms of performance, being a bit faster or a bit slower depending on the amount of data being produced.

But here's a neat outcome: the quality of PerlinNoise and SimplexNoise is better, meaning that it is likely you could get away with fewer octaves than when using LegacyNoise. So this might easily make up for any straight one-for-one performance comparison.

Here is a texture generated from each of the different base noise functions wrapped by a FractalNoise. Each one uses 3 octaves of noise (and persistence of 0.5 with automatic normalization back to the [-1, 1] output range), and I have reduced the size to 4 lattice cell lengths on a side to "zoom in" and show the fractal noise details better. So instead of imagining this as a 10km x 10km patch of terrain, imagine instead that it is 1km x 1km.

LegacyNoise
Image

PerlinNoise
Image

SimplexNoise
Image
Last edited by prestidigitator on Fri Mar 22, 2013 22:58, edited 1 time in total.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Sat Mar 23, 2013 08:52

Unfortunately I've been told in no uncertain terms that the existing NoiseParams is "set in stone" so there's no room for adding some kind of "type" parameter to it. This is from a source who apparently thinks I want to reinvent Mapgen when I really just want to provide each Mapgen an alternate source of noise (polymorphism through composition, not inheritance) to use for its source of pseudo-random numbers.

That brick wall will probably make it tough to mix noise types. I think the only real tenable solution left is to change the base noise algorithm used by all parameterized noise (terrain, trees, beach, biome, heat, humidity, etc.).

(Unfortunately there may be some resistance to this change because someone else has recently revamped the noise and mapgen code and may not like it being changed again. I hope that doesn't show up when and if this is ready for a pull request, but even if it does it's still a fun exercise.)
Last edited by prestidigitator on Sat Mar 23, 2013 10:19, edited 1 time in total.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Sat Mar 23, 2013 10:12

I just spoke to celeron55, who seems interested in this change for the fact that the generalized API will make dynamic modification of fractal noise parameters (scale, persistence, etc.) very easy to change. This would result in the ability to create smoother terrain in some places and more jagged terrain in others. So it looks like this may be a valued enough contribution that small extra requirements like optional settings format changes may be acceptable even if they might touch on some pieces of logic, ah, folks touchy about code they may have changed in the recent past.

(For further info, see the IRC log: http://irc.minetest.ru/minetest/2013-03-23#i_2949428)
Last edited by prestidigitator on Sat Mar 23, 2013 11:14, edited 1 time in total.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Sat Mar 23, 2013 11:19

I'm going to rename "LegacyNoise" to "ValueNoise" because it's a bit presumptuous, and the goal isn't really to replace or obsolete it but to provide additional options to anyone who likes to tweak their settings.
 

proller
Member
 
Posts: 186
Joined: Sat Jan 26, 2013 15:22

by proller » Sat Mar 23, 2013 15:19

how you draw this noise images?
its possible for custom noise and noiseparams?
i want to play with farscale and farspread params from here https://github.com/minetest/minetest/pull/559
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Sun Mar 24, 2013 05:46

It's not fully integrated yet. I've got some test programs that use the new Noise classes to generate noise values and spit out raw image data that I import into the GIMP (I have to specify height and width when importing) so that I can export them again as PNGs. In fact, all I do is write 512x512 RGB triplets where R=G=B (grayscale) to std::cout, and pipe the program's output to a file. However, soon I should be able to show screenshots of actual generated terrain, and hopefully not long after that I'll have a pull request ready.

I'm paused briefly with the actual noise work so that I can enhance the NoiseParams parsing from the server config file. Currently it assumes that the struct (or any struct you are going to read) is 100% static and will be for all time. I'm working on instead allowing Lua table syntax, so that new name/value pairs can be used but the existing syntax and current behavior will continue to function correctly.
 

proller
Member
 
Posts: 186
Joined: Sat Jan 26, 2013 15:22

by proller » Tue Mar 26, 2013 00:46

you can try use json parser for one config string with noiseparams, its easiest way.
find deSerializeJson in serverlist.cpp
 

User avatar
rubenwardy
Moderator
 
Posts: 5965
Joined: Tue Jun 12, 2012 18:11
Location: United Kingdom
GitHub: rubenwardy
IRC: rubenwardy
In-game: rubenwardy

by rubenwardy » Tue Mar 26, 2013 13:20

Hybrid Dog wrote:(translated)

It is not fully integrated yet. I have some test programs using the new noise classes to generate noise and spit raw image that I. Import into the GIMP (I have to specify the height and width, the import), so that I can export it again as PNGs In fact, everything I do write to 512x512 RGB triplets, where R = G = B (grayscale) to std :: cout and Pipe. The program's output to a file But soon I should be able to show screenshots of the current generated terrain, and hopefully not long after that I will provide a pull request.

I just stopped using the actual noise work, so I can improve the NoiseParams parsing the server configuration file. Currently it is believed that the structure (or struct you'll read) 100% is static and will remain for all time. I'm at work so instead of Lua syntax table so that new name / value pairs can be used, but the existing syntax and current behavior will continue to function correctly.


please write in English.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 08:44

rubenwardy wrote:please write in English.

From the round-trip, I'd say Google Translate did a pretty good job. ;-)
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 08:46

proller wrote:you can try use json parser for one config string with noiseparams, its easiest way.
find deSerializeJson in serverlist.cpp

Now you tell me! I've actually utilized the Lua parser to do this already, but I set that aside for the moment and will integrate it later. For now I'm going to create a pull request that JUST changes the noise interface, and doesn't provide a way to get to it from the settings file or Lua. The second pull request will have the settings/Lua interface. That way even if people have a problem with the parsing, the noise will at least get in.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 08:53

Performance test results are in! And they're pretty incredible.

Celeron55 pointed me at F6 (twice) to get the time it takes the game to generate map chunks. So after creating a branch on which I made a rather exhaustive replacement of all calls to noise{23}d_perlin(), NoisePerlin{23}D(), etc., I switched to the branch with the old code, then to the branch with the new code and each of LegacyNoise (soon to be renamed ValueNoise), PerlinNoise, and SimplexNoise selected as the base noise algorithm.

With the old, mostly functional noise calls, generating a map chunk took on average about 120-130ms (this includes lighting calculations of around 50ms).

With ANY of the object oriented calls (LegacyNoise, PerlinNoise, SimplexNoise), generating a map chunk is taking on average about 120-140ms.

So, ah, yeah, it seems to work pretty damn well. (This is on an AMD Athlon(tm) II X4 630 with 8GB of RAM running (K)Ubuntu 12.10, just FYI.)
Last edited by prestidigitator on Fri Mar 29, 2013 09:11, edited 1 time in total.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 09:06

And now some Simplex Noise terrain screenshots, for your pleasure:

Image

Image

Image

Image

These just look nice, and show it is working. The speed was the exiting part for now. I'll try to get some good tangible comparisons of the actual noise up soon.
Last edited by prestidigitator on Fri Mar 29, 2013 10:17, edited 1 time in total.
 

User avatar
Calinou
Moderator
 
Posts: 3159
Joined: Mon Aug 01, 2011 14:26
Location: Troyes, France
GitHub: Calinou
IRC: Calinou
In-game: Calinou

by Calinou » Fri Mar 29, 2013 12:44

Looks good, why not put that as default if it is faster than the current map generation? We could still keep the old noise in a different mapgen, since we can have several mapgens now.
 

User avatar
jojoa1997
Member
 
Posts: 2890
Joined: Thu Dec 13, 2012 05:11
Location: Earth

by jojoa1997 » Fri Mar 29, 2013 12:48

Yeah maps could be configurable with different map gens.
Coding;
1X coding
3X debugging
12X tweaking to be just right
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 20:09

Well, what I was thinking is that the NoiseParams could select the noise type. That way any type of noise could be used with any mapgen, just by changing the config file. I expect that for the most part different mapgens will differ by a lot more than just which noise algorithm they choose.

But certainly different mapgens COULD select different noise algorithms, both before and after the noise type is added to NoiseParams. I've changed all allocation of noise to call a factory method (createDefaultBaseNoise()), so anywhere you explicitly wanted a particular type of noise, you could create your own factory method or just call "new" with the concrete type you wanted.

It's not faster, but it is about the same, though it might allow for speedups if the noise quality is better enough that fewer octaves of noise can be used. I'll leave it up to others to make it the default if they like; myself I'm a little afraid of messing up existing configurations or worlds (generate new chunks with a different noise functions and you'll get pieces that don't fit at all, like a mixed up jigsaw puzzle.
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 20:22

Okay. Here are some comparisons. I have generated 3 worlds with different noise algorithms but the same parameters (including seed, though that's a little irrelevant when using different noise algorithms). In each I flew around the square (x,z)={(-250,-250), (250,-250), (250,250), (-250,250)} to generate the map and then went to two specific points and took screenshots with roughly the same camera angles. These three shots are from the first point (x,y,z)=(0,250,0):

ValueNoise (called "LegacyNoise" above)
Image

PerlinNoise
Image

SimplexNoise
Image

(Sorry for the clouds. Forgot to turn them off in time.)
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 20:29

Here is the same region of the same three worlds, viewed straight down from (x,y,z)=(0,500,0):

ValueNoise
Image

PerlinNoise
Image

SimplexNoise
Image
 

prestidigitator
Member
 
Posts: 640
Joined: Thu Feb 21, 2013 23:54

by prestidigitator » Fri Mar 29, 2013 20:34

You'll notice that you can see somewhat correlating features between the Perlin Noise and Simplex Noise terrain. This is because they use the same gradients to produce the outputs, but the Simplex Noise uses skewed coordinates for the lattice points and does the interpolation a little differently. That's why there are similar major features, but their shapes and locations are distorted a little and the details are different. Value noise, on the other hand, uses the hashes of the lattice coordinates in a fundamentally different way, so there isn't going to be much similar in its features.
 

Next

Return to Partly official engine development



Who is online

Users browsing this forum: No registered users and 2 guests