PDA

View Full Version : how to musgrave's ridged multifractal?



xoxos
04-07-2012, 01:00 PM
apologies for not recalling the name of the members whose posts drew me here. my introduction thread:
http://www.cartographersguild.com/showthread.php?18283-you-guys!&p=182445#post182445
the map is eight unsmoothed perlin octaves with cosine interpolation.

the references i am finding on musgrave's ridged multifractal point to URLs that no longer exist and were blocked from archive.org

while i have found musgrave's script, i admit that stylistic differences often make it difficult for me to apprehend the intent of other coders.

what i understand is that all, or the larger octaves of this perlin-based algorithm use absolute values. this alone does not a ridge elicit.

i have read that the amplitude of higher octaves is derived from precedent layers (thus the 'fractal' description) i am guessing this is what i have missed.

would anyone care to give me a nudge on this? tia :)



not sure where i'm going with this.. will explore the terrain generation for a while. i'm way behind on 2 and 3 d. may take it back to audio.

Redrobes
04-07-2012, 01:17 PM
You need to look out for posts by Waldronate who knows his noise and fractals. There is also Su-Liam who does a lot of dabbling with noise functions. Have a search on their threads.

There is a noise library libnoise (http://libnoise.sourceforge.net/index.html) if you can stand to use C/C++ under VC or gcc.

I give away my little app Instant Islands

http://www.viewing.ltd.uk/cgi-bin/viewingdale.pl?category=instant_islands

but I am not one to use a soap box to say that noise is a good method for creating good terrain. I think the system needs to know more than mere noise functions to do it well.

xoxos
04-07-2012, 02:22 PM
cheers, i hadn't found libnoise previously.

i'd still be interested in a brief english description of the method :) coming from an audio background, i inline everything. eg. linear interpolation is a + decimal * (b - a) and i would never use a function (lerp?) to perform these things.

for all i know, i may well end up applying the noise techniques to audio more than contributing to this field :)

waldronate
04-07-2012, 04:05 PM
https://engineering.purdue.edu/~ebertd/texture/1stEdition/musgrave/musgrave.c has the original C implementation of Musgrave's RidgedMultiFractal procedure. It s tweak of the classic Perlin fBm function with the addition that it uses the absolute value of the current octave's noise function and the previous octave's noise in the output. http://paulbourke.net/texture_colour/perlin/ is a good discussion of the Perlin noise function. http://forums.planetside.co.uk/index.php?topic=1168 looks to have some nice examples of noise to fractal functions.. The basicPerlin-type fractal forgeries are based on a space-filling noise function that gets sampled at progressively larger distances from the original point and with each successive point scaled by 1/2^n to reduce the magnitude of successive additions. The noise function is what's critical for the appearance of the final result. The traditional sinuous rills in the RidgedMultifractal routine come from an absolute value of a cubic-interpolated noise field (it's the cubic interpolation that gives the smooth transitiions).

If you can, I'd recommend locating a copy of Texturing and Modeling: A procedural approach ( http://www.amazon.com/Texturing-Modeling-Third-Edition-Procedural/dp/1558608486/ ). Earlier editions of the book are pretty much as good as the latest for the discussion of basic noise functions.

waldronate
04-07-2012, 04:10 PM
I am not one to use a soap box to say that noise is a good method for creating good terrain. I think the system needs to know more than mere noise functions to do it well.

http://www.pandromeda.com/ also says that you might want to do more than just basic noise functions (it's where Musgrave ended up).

xoxos
04-07-2012, 04:40 PM
waldronate - TY for replies, and i do hope not to take up too much of anyone's attention.

i've been using perlin in audio, and as an audio coder i'm well used to octaves, and certain conventions in procedure. i'll explain my implementation somewhat, which may elicit why i'm seeing things differently.

audio requires speed, so wherever possible, i use INTs, and unsigned ones at that. my noise map is unsigned short[x][y] and each octave is a stored array smaller by a power of two.

(or what i prefer to call a tower of poo)

each octave is stored and cosine interpolation is used at summing each octave to discern any coordinate (i'm familiar with bicubic interpolation but cosine looks well enough and is faster given that i'm using INTs and ^2, so all cosine functions use a ^2 array of float values).

so my variables for each octave range 0 - 65535. i sum them using n^2 for successive octaves.. typical perlin, and squish this range into my desired outcome (0-255 for bitmap output, data is retained in the 2^16 for processing).

it is trivial to use 0 or 65535 for the outcome of each cell, but this doesn't look too different from standard perlin. the outcome of the previous layer is used to determine the magnitude of the subsequent, or something like that? :)

the approach in musgrave.h is very different from my set of discretised arrays... so i've been searching for a non-code explanation of the procedure :)

here's an example of output using perlin octaves, no smoothing to illustrate my current progress.. :)
43812

xoxos
04-07-2012, 04:50 PM
(to be unnecessarily thorough..)

if each layer is 0-65535, the summing is as such:

layer 0 65536 / 1 = 65536
layer 1 65536 / 2 = 32768
layer 2 65536 / 4 = 16384
layer 3 65536 / 8 = 8192
layer 4 65536 / 16 = 4096
layer 5 65536 / 32 = 2048
layer 6 65536 / 64 = 1024
layer 7 65536 / 128 = 512
sum of all layers = 130,560

fitting this to a range of 256 for pixelation = divide total by 510 (256 * 510 = 130,560)

as such, i can manipulate the data for each layer without having to recalculate every layer, only resum the output....

given my b/g, using unsigned INTs seems natural to me, it's fast, it's the way i do things.. so eg. a lacunarity coefficient doesn't fit into my method at all.

xoxos
04-07-2012, 06:01 PM
unseen post #3....

i have yet to test it, but it looks like i've found my answer.

and, like all frustrating referential answers for programming, it is absurdly simple.. i confused my understanding by using an unsigned range. when casual descriptions said "absolute value" i assumed a switched output (the 0 OR 65535 mentioned above...) because negative outcomes never factored in...

.....what it appears to be, from the reference i have found (pp. 553 Multifractals, Probability and Statistical Mechanics, Applications google preview) is bloody simple...

..referencing audio.. if you have a curvy (interpolated) waveform and rectify it (flip sign of negative samples.. or *absolute* value ;) ...you get a bunch of bumps (eg. sinewave becomes mcdonalds "M" logo) - so the "ridges" are merely (1-McDonalds)... aargh.. so infuriatingly simple.. if that page had still been up it would have saved me about five hours of browsing for the answer....

..i expect i'll be back. i'm not going to duplicate the functionality of wilbur, but i do wish to explore many of these functions :) TY all

xoxos
04-07-2012, 06:02 PM
?? there were two posts before that that were tagged "must be approved by moderator" that had lengthy explanations of my perspective here... i hope they haven't been cast to the abyss....

xoxos
04-07-2012, 06:19 PM
well, for the sake of comprehension..... i will reiterate my statements concicely.

i was elaborating on my familiarity with the topic, and posted a map that is visible in my introductory thread indicating my use of 2d perlin. i described my background as an audio coder, my preference for INTs (and unsigned INTs) for speed, and my algorithm (which was a lengthy description) which, as you may now suspect, used unsigned shorts for my height field.. i described how i stored a separate array for each octave for editing, and subsequently why, using unsigned variables, much of the other code i had found was quite different from my own sensibility.

well, i'll take some deep breaths, and report back with hopefully improved results for ridgyness.

xoxos
04-07-2012, 06:22 PM
(meanwhile... this is the statement i am still confused by..

http://libnoise.sourceforge.net/docs/classnoise_1_1module_1_1RidgedMulti.html

Ridged-multifractal noise does not use a persistence value. This is because the persistence values of the octaves are based on the values generated from from previous octaves, creating a feedback loop (or that's what it looks like after reading the code.)

a line or two concreting the intent of this would be much appreciated :)

xoxos
04-07-2012, 09:17 PM
perlin noise, 8 octaves, cosine interpolation, no smoothing
(imo workable since it's fantasy mapping anyway)
43823

square curve (n * n) to height field
(imo better results crossfaded between this and previous)
43820

rectified interpolation on each octave
(lol no)
43821

rectified interpolation on octaves 3-8
(for example)
43822

i expect i'll find a method to achieve preferable results (pondering shift and erosion models.. being fairly nescient about the geologic processes, i'm licensed to use elementary methods to model them). still, i'd like to find out how it's normally accomplished.

waldronate
04-08-2012, 02:41 AM
Important notice: I'm not a mathematician, nor do I play one in real life (I have to remind the folks at work about that a lot as well, do don't be offended).

The basic monofractal fBm(x,y) noise uses a noise function that is repeatedly sampled over multiple octaves at (x*2^octave,y*2^octave) and scaled by 1/(2^octave) so that scaled copies of the noise function are added together. The noise function is what makes the whole fractal thing work. The classic description of the basic property of the noise function is "zero mean and unit variance", meaning that the noise goes from -1 to +1 and will average out to 0.

In addition to the basic fBm function, Perlin also describes a turbulence function. The primary difference between the basic fBm and turbulence is the use of an absolute value returned from sampling the noise function.

Musgrave takes the turbulence function further by using the previous noise function value as a further scaling factor to move the sampling point in addition to the basic 2^octave scaling. What this does is cause broad smooth areas to form where the noise function is large and rougher areas to form where the noise function is small. It's this variation in apparent fractal dimension over the result set that makes the results more typical of a multifractal than a monofractal (where the fractal dimension is uniform over the results).

Musgrave's models also include a whole lot of other controls over the system (for example, instead of 2^octaves for scaling factors, the 2 can be controlled). Other models use similar methods, but different terms for the controlling parameters such as persistence.

xoxos
04-08-2012, 06:17 PM
cheers for the reply waldronate. i took a moment to verify that it was you that brought me here.. lol
http://www.cartographersguild.com/showthread.php?7160-Random-Terrain-Generation

i work in audio dsp as a facilitator. many of my peers are certainly more formally inclined than myself. the affinity for mathematics is not the most significant factor in modeling. some people have "golden ears" and some not so :) my awards are more for muddling through with my less quantifiable skill set - here's an audio demo of my recent water model, i hope it will illustrate a parallel between the disciplines.

http://www.xoxos.net/vst/mp3/water.mp3

it's a simple parametric model that requires a blob of chewing gum and some cellotape to hold it together -
http://www.xoxos.net/vst/images/water.jpg

when i saw this image from your wilbur tutorial, and seeing your disavowals of comprehensive tectonic knowledge, i did expect that you are one of the people whose capabilitity is a matter of "art" as much as anything -

this is very good. brilliant, if you'll permit me to say so. i've spent a lot of time in airplanes. you have calibrated the process, which i am guessing is simple, like my water model, artistically.

http://www.ridgenet.net/~jslayton/FunWithWilburVol1/image011.jpg

hopefully you will forgive me for assessing you.

i am quite familiar with this station in a technical field - the perlin 'turbulence' is known as 'rectification' in audio, and probably something like "ya just flip them bitsy things there, by gum" in yorkshire. i have frittered away years of my life translating julius orion smith's documentation, for instance :) so "zero mean and unit variance" is trivial to me. that's my bread and butter, and i was able to perform the rectification around a mean without having to abandon my unsigned shorts, of course.

so often, these techniques are extremely elementary when the exclusory vernacular is shed. i also realise the utility and other more subtle factors that weight its use ;)


so:

given your experimentation with this venue, i expect you can confirm that my 'turbulence'/'rectification'/flipping half the waveform results are due to my use of cosine interpolation instead of bicubic. i would expect that long ago you probably used cosine interpolation for perlin noise as well.

i'm not convinced that switching to bicubic, hermite, or improved interpolations would give me results like this -
http://www.noisemachine.com/talk1/imgs/flameball.jpg
(from perlin's lecture http://www.noisemachine.com/talk1/22.html )

the somewhat ridgyness here seems more fortuitous/a result of selection. i'm sure improved interpolation would give a better result, but not like this -

http://www.neilblevins.com/cg_education/procedural_noise/musgrave_ridged_furymap2.jpg

which looks like a typical example of the output of musgrave's ridged multifractan ttbomk
>>
Musgrave takes the turbulence function further by using the previous noise function value as a further scaling factor to move the sampling point in addition to the basic 2^octave scaling


this could be something like...

n1 = [-1,+1] = a sample of generic perlin noise
nt = 1 - abs(n1) = rectified perlin noise octave with "pointy bits up" to produce a contour like waves, rarifying peaks, placing nt in the range [0,1]

"scaling" could be something like..
scale = ((n1 * .5) + .5) to give the range [0,1]

output = nt * scale * scale which would certainly rarify peaks



also - image processing is extremely new to me. i have occasionally happened across it in my own work, i am generally out of touch with estimating what someone knows based on their demonstrated knowledge. as said, i don't know where i'm going with this, i do hope that it's not to ask you annoying questions for the next six months......

so... i expect you are familiar to some degree with allpass filters, which have a group delay/phase response (appellation depending on your discipline) effect and pass frequencies with different temporal effects..

an elementary first order allpass may pass high frequencies immediately but delay low frequencies by 180 degrees... if you pass a waveform through an allpass, you'll have no audible difference but an effect that can be used for fine tuning....

however..... knowing absolutely nothing about the effect of allpasses in 2d/image processing, i certainly believe that you could run a perlin noise terrain map through a very simple allpass and achieve a continental shift effect... this would pile up amplitude transitions towards one edge (pending a monodirectional allpass from left to right on the x-axis) so that mountains would build along the left edge of the landmasses.

one could do nifty things like modulate the allpass coefficient by the sample, or.. get out that blob of chewing gum and cellotape i mentioned earlier. it's less about mathematic education and more about prolific creativity, and, equipped with a wide and potentiating vocabulary of transformations, a very crude person could indeed achieve very realistic simulations :)

anyway.. do you remember how that scaling thingy works? :)

xoxos
04-08-2012, 06:26 PM
(i'll add that i am interested in your incise flow algorithm.. i have yet to attempt it, i'm assuming it's some combination of averaging filter with lookup table or similar nonlinearity)

xoxos
04-08-2012, 07:42 PM
(and... again, i apologise for asking.. if anyone would care to direct me to good any good sources/tutorial sites for general graphic procedure.. eg. how to draw antialiased borders for my continents so i don't keep asking.. otherwise i'd head to gamedev.net first, and it tends to be a swamp........)

waldronate
04-09-2012, 04:44 AM
The image you provided is exactly Perlin's turbulence function (fractalsum(1-abs(noise(n,pos))) rather than the simpler fractal sum(noise(n,pos))) where n is the current octave number and pos is the input position to sample. Musgrave's RidgedMultifractal adds only an additional term that is more along the lines of fractalsum((1-abs(noise(n,pos))*(1-abs(noise(n-1,pos)))). That extra term makes for much broader basins and rougher mountain areas.

The image you provided is most likely based on either a cubic interpolation or a quintic interpolation function ( http://mrl.nyu.edu/~perlin/noise/ for the quintic-based noise function and the justification for it over the basic cubic). The interpolant is the basis of the noise function; the character of the result depends to a large extent on the basic table used for random numbers and the interpolant between samples in that table. Some folks use an arbitrary image as the input to the noise function, while others dispense with the noise table entirely and generate the noise values directly from the sample coordinates themselves.

Distorting the inputs before doing the inputs is described by Musgrave as "domain distortion" and a search on that term might be fruitful.

The incise flow algorithm is a very simple one: a direction map is calculated for each point on the surface that shows the local "down" in altitude. Then that map is traversed and each pixel sends a counter up the gradient, adding one to each sample on the flow map. At the end of this operation, every point on the surface then contains a value that represents the number of cells that would contribute to the flow at that point. Applying a logarithm operator and a threshold operator to the flow map will generate "rivers" across the map.

Antialiasing is also pretty simple: just sample the noise function multiple times at each displayed pixel, then use the average of those samples as your noise value. If you'd rather do coverage sampling, then the percentage of samples above sea level would represent your land opacity over ocean at that point. The same algorithms used by ray tracers and a lot of GPU renderers can be used here as well.

xoxos
04-09-2012, 03:57 PM
simple solutions. musgrave's process is really then squaring [0,1] ranged samples, and as you gather from my prose, is likely to be expressed in yorkshirean consequently :)

i absolutely dispensed with the fractal perlin. i generate each octave as a separate array in series, obviously the choice of doing so has no discernible effect on the outcome.. as of yet, anyway. (except for efficiency.. presuming the scale makes the size of the data immaterial as long as the lower octave are not repeated at an implemented scale, so that an array indexed by unsigned chars would produce faster processing).

my guess for drawing borders is to weight adjacent pixels by 50% and corners by 25%, generate one layer from this and another run or two using similar filters.


ftr i spent a bit of time running triangle waves through allpasses yesterday for gauging height field transformations.. this would of course move data eg. along x, i'd think two or three further steps would be necessary to contain it to the desired range and distribution. i'm sure there are simpler ways to achieve similar results.


in audio dsp there is a repository for common algorithms at musicdsp.org. i've been searching for something similar for graphics. posted here for those with similar interests, my best find was - http://femto.cs.uiuc.edu/faqs/cga-faq.html and a reference to the "graphics gems" books, which should at least provide enough vocabulary for interested parties to refine searches.

thank you for your assistance, and enjoy the inspirational high desert :)

(nb. i wonder if this site would benefit from the addition of a generative coders forum)