Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Seeds #9

Open
dsheets opened this issue Jan 5, 2013 · 35 comments
Open

Seeds #9

dsheets opened this issue Jan 5, 2013 · 35 comments

Comments

@dsheets
Copy link

dsheets commented Jan 5, 2013

Provide a means to seed noise generators

@stegu
Copy link
Contributor

stegu commented Jan 7, 2013

The "fake" way of doing this is to add a constant offset to one or
more coordinates at the user call to the noise function. At the
cost of one extra addition, this is a useful replacement for a real
"seed" for the use cases I have seen.
Other ways of adding a seed would add complexity and slow down
the function, and I think speed is absolutely crucial. Performing a
final churn through the permutation polynomial with a "seed" offset
added to the final index would probably do what you want, but it
would be too costly for my purposes.
Can you elaborate on where a seed would be needed, and why
adding an offset to either of the input coordinates would not do
the trick? It's not difficult to write an alternate function that does
the extra permutation with a seed, but I am hesitant to write a
function that is unnecessarily slow.

@dsheets
Copy link
Author

dsheets commented Jan 7, 2013

This feature wish came from @pyalot so perhaps he can speak to the appropriateness of translating the sample window for his application.

Perhaps a constant macro for permutation group offset would suffice? Macro parameters will soon be first-class module parameter constructs so this would give us A.) no cost and B.) easy parameterization once glol has been polished a bit more.

The down-side is a new shader program for each seed+effect combination but this isn't too bad as A.) the seeds will probably be generated in an authoring tool for aesthetic sampling and B.) seed state transitions aren't smooth.

How would you feel about the abstraction of the polynomial parameters into constant macros?

@pyalot
Copy link

pyalot commented Jan 7, 2013

I don't want to have to attach your whole preprocessor just to set a seed value.
A macro is also not useful, at all for the following reasons:

  1. The seed may be passed into a uniform
  2. It may come from a texture
  3. It may come from a calculation (such as octave depth etc.)

@dsheets
Copy link
Author

dsheets commented Jan 7, 2013

I don't want to have to attach your whole preprocessor just to set a seed value.

I was not suggesting you do that. I was merely pointing out that macros can be dynamic with sufficient software. You may use your own pre-preprocessor or manually set the value.

Please, answer Stefan's question: Can you elaborate on where a seed would be needed, and why
adding an offset to either of the input coordinates would not do the trick?

A macro is also not useful, at all for the following reasons:

  1. The seed may be passed into a uniform

Why? The seeded permutation is a finite group. Is generating a new shader insufficient? Regardless, pre-preprocessors exist which can fulfill a symbolic dependency by either macro or uniform. The crucial aspect is the penalty-free abstraction for your (undeclared) application.

  1. It may come from a texture

Directly in a single shader? What's the use case?

  1. It may come from a calculation (such as octave depth etc.)

Where is this calculation? Why is the seed changing frequently?

@pyalot
Copy link

pyalot commented Jan 7, 2013

It doesn't matter, you don't have to understand why. The fact is that fix-compiled seeds are utter fucking crap period.

@dsheets
Copy link
Author

dsheets commented Jan 7, 2013

You seem to have a problem with reading comprehension and professional communication.

Seeding/initialization at each compilation stage (including run-time) is possible. Putting penalty-free methods into the distributed source gets us a common interface to noise parameters.

Is there a reason that an offset to the input coordinates does not satisfy your use case?

@pyalot
Copy link

pyalot commented Jan 8, 2013

An offset into periodic noise is periodic.

@stegu
Copy link
Contributor

stegu commented Jan 8, 2013

Yes, but the period is long and unnoticeable for the use cases I can
imagine. Also, simplex noise has a grid that is not axis-aligned.
What is your reason to require this level of statistical randomness
instead of the apparent randomness that is OK for other cases?

Please understand that I am not being a pain, I seriously want to know.
Despite the fact that you are asking for a service by calling our hard work
"utter crap", I am perfectly willing to provide a seed-enabled version (with
some extra computational cost) if you can explain to me why you need it.
It's not a lot of work, it's just that I don't want to fork and fragment the code
without a good reason. There are already quite a few different functions to
maintain here.

If you don't feel like explaining this more clearly to a person really wanting
to learn, you can add a seed yourself. Make an additional permutation of the
gradient index value just before you do the gradient lookup, after adding an
integer seed, and you should be all set. In the 2D simplex noise version,
you would do it right after this line:

vec3 p = permute( permute( i.y + vec3(0.0, i1.y, 1.0 )) + i.x + vec3(0.0, i1.x, 1.0 ));

by inserting the following line:

p = permute(p + vec3(seed));

where 'seed' is an integer value (stored as a float for compatibility).
A vec3 seed with three different values could also be useful
if you want more than 289 distinct noise fields. Using different
values for the components will get you 289^(N+1) fields for N-D
simplex noise, and 289^(2^N) for N-D classic noise, although fields with
at least one seed component in common will be partly correlated.
If you plan on using large seeds (larger than about 100), change that
extra line to:

p = permute(mod289(p + vec3(seed)));

Quite a lot of extra computations compared to a simple offset,
but it should do what you want.

@pyalot
Copy link

pyalot commented Jan 8, 2013

@stegu My beef is with dsheets not with you. I've had a lot of this kind of counterproductive conversations with him of the kind where he keeps asking "why" and I try to explain it and it goes nowhere. So him coming on with another of the "why why why" comments makes me see red all over. And secondly, I'm not asking for this. I've told dsheets that it would be handy, he choose to agree. I can live without a seed with your library, I have other noise sources that do what I need them to do. So consider this a service to you, not the other way around. And feel free to do or not do whatever you like. And if you prefer not to, that's fine. I can't make you not publish crap. That's up to you.

So I'll explain it, this one time. A lot of noise cannot be used in realtime because of two reasons. The first reason is that sometimes the result has to be the same on every machine because it carries real meaning (such as terrain height in a game for instance). And the second reason is that sometimes you do things to noise (like convolution, sharpening, blurring or any other kind of kernel filter) that make it prohobitively expensive for instance:

  • let N be the number sample points
  • let M be the number of kernel samples
  • One filte has a runtime of O(N*M)
  • Two have a runtime of O((N*M)^2)
  • X filters have a runtime of O((N*M)^X)

That means that quite often you need to bake noise (or the result of the computation) into a texture. This however has one important problem. Unbounded noise goes on forever which is nice. But baked noise has borders (the texture size). If you render unbounded noise into a texture obviously the borders will not match up. This is fine in some cases, but in others where you'd like to use this noise to provide detail it is not. The only solution to reclaim some of the quality of noise (going on forever) is to repeat the texture. Now in order do that you need repeatable noise. And while the quality of repeatable noise may not be as nice as simplex noise, it makes it feasible to bake.

So regarding the offset into the noise. The offset in repeatable noise is of course repeated. This has some nice qualities (you can choose a "soft" seed that'll wrap around) but it has some that are not so nice (you can't get a completely different pattern). For instance if you choose a size of 10x10 cells, then there's only 10 substantially different slices into that noise. Worse yet, any noise (any use you make of it) is the same, not just this one use. For artistic control it is quite often necessary to get entirely different patterns. If you only have 10 patterns to deal with and you combine them a lot, you will end up with very crappy results.

So, a real seed is one necessary component of any real noise function. I didn't think this had to be explained, but apparently it has to be explained, to the people who want to do real noise functions.

@stegu
Copy link
Contributor

stegu commented Jan 8, 2013

Thanks for the explanation. I understand your motivation perfectly now, and the change
I suggested in combination with the periodic classic noise functions ("pnoise") would
do what you suggest and give many different noise fields to choose from. However, a
very similar effect could also be achieved with a constant offset before the index wrap
in "pnoise", to cut out a different region of the full 289x289 cell field of our version of
classic noise. If you use a 10x10 cell region, you would get 28x28 independent places
to put your cookie cutter, and for larger regions, a shift of the pattern of less than the
full cookie cutter size would not be all that noticeable.

So you see, the use case really does matter a whole lot here, because it is not
immediately obvious how best to implement a seed regardless of its intended use.
I kindly ask you to consider the fact that I am a computer graphics researcher, not
a practitioner, so I need other people to tell me how they use noise, or my view will
be restricted to whatever ideas I can come up with all by myself. Research is not
meant to be performed in isolation from real world implementers. Feedback is crucial.

So, a real seed is one necessary component of any real noise function.

I really think you generalize too far here, and promote your view as the only right one.
Most publications in the field do not make any mention of a seed, much less tout it as
a necessary feature without which all noise is utter crap. Built-in noise functions of e.g.
RenderMan SL also do not contain a seed, so there is clearly some good use to be
had from a seedless noise, although admittedly under different conditions than yours.

X filters have a runtime of O((N*M)^X)

Hmm. Wouldn't that be just O(N_M_X) ? If not, what am I missing here?

Anyway, thanks for the constructive input.

@pyalot
Copy link

pyalot commented Jan 8, 2013

I might have bungled that a little, but it is an exponential.

Say you have a 16-tap kernel, so for discrete samples (N) it'll make 16 taps. So the runtime would be O(N*16).

If you access this discrete sample with the next kernel it will make 16 taps for each discrete sample. Each of which will do 16 taps. So it's O(N_16_16).

At 2 filters it's O(N_16_16_16) so the analytic runtime case is O(N_M^X).

If each filters result is stored say for two filters, then the example would be O(N_M + N_M) for two filters, O(N_M + N_M + N_M) for three and so on. So the cached runtime case is O(N_M*X).

If the produced result does not have to be changed in a frame, the runtime becomes O(1).

  • analytic: O(N*M^X)
  • cached: O(N_M_X)
  • baked: O(1)

@stegu
Copy link
Contributor

stegu commented Jan 9, 2013

I see. Reading "filtering", I was assuming storage of dense sample sets from each step, basically
traditional image processing, or what you refer to as "cached runtime". If intermediate storage is a
problem, then yes, successive filtering becomes prohibitively costly, and the very useful shortcut
provided by kernel decomposition also gets thrown out the window if previously computed samples
from the preceding step cannot be cached and re-used.

I must say I am not really seeing when one would need to do such full-blown uncached analytic
filtering. You don't need to elaborate, but is it a common situation for you, or more of a corner
case?

@pyalot
Copy link

pyalot commented Jan 9, 2013

Successive filters are required if you do things like source -> erode -> blur -> flow -> sharpen etc.

If the desire is for a gapless product on the borders then only repeatable sources can be used. An aperiodic source precludes usage in storing intermediary results and hence would force an analytic solution.

@stegu
Copy link
Contributor

stegu commented Jan 9, 2013

I see what you mean, but I don't quite agree. Assuming yoy are rendering a bounded area of texels and that it can be meaningfully filtered with discrete convolution kernels, the function can still be sampled, stored as a texture during filtering and then scrapped. Wasteful, yes, but not exponential in complexity for many successive filters. But then again, I have no information on the exact conditions for the applications you have in mind.

Anyway, now I should implement and test that seed argument...

@dsheets
Copy link
Author

dsheets commented Jan 14, 2013

@pyalot reported "this is your periodic 2D noise layered in 10 octaves with a lacunarity of 2 and a gain of 1" http://codeflow.org/pictures/perlin.png vs. "this is a bicubically interpolated noise from a sin/dot random source with the same parameters" http://codeflow.org/pictures/bicubic-random.png "the noise is billowy (i.e. abs(n))" and "this artifact is not as apparent when using fbm octaves, although in your noise things seem to be more regularly distributed" via freenode #webgl IRC chan and speculated "it's possible this is the artifact of a lacking seed" due to "self-similarity degradation".

@stegu
Copy link
Contributor

stegu commented Jan 15, 2013

Comparing 2D Perlin (gradient) noise to random value noise is not a
proper test case, regardless of whether the noise is periodic.
Gradient noise is bandpass, while value noise is lowpass, so the two
are not directly interchangeable, and gradient noise on a square grid
(like classic Perlin noise), will aways show the kind of artefacts
demonstrated in that picture. The raw noise() function is zero mostly
along angular-looking 0-45-90 degree "worms". I get similar results
using "unperiodic" Perlin noise even in PRMan, so the quality of this
version of Perlin noise is not the main issue. It is an issue with Perlin
noise as such. 2D simplex noise has similar issues, although the grid
that appears is then hexagonal and slightly less visible.

This use case is actually the worst possible case for gradient noise.
At least the base frequency of abs(noise) needs to have a small offset
added to it, like abs(noise(st)+0.2) or something, possibly also with the offset
affected by a lower frequency noise, to hide the regular zero crossings
that become very visible when you go from noise() to abs(noise()).
Successive octaves could also be rotated to avoid the blocky look, or
if you don't rotate it, the scale factor between octaves (the lacunarity)
should not be exactly 2 if you can avoid it, because then some zero
crossings will coincide between all octaves.

Just compare billowy noise abs(noise) and abs(noise+0.2) from a
RenderMan shader (rendered in Aqsis, because that's what I have
available to me right now):

http://www.itn.liu.se/~stegu/aqsis/absnoisetest/noisetest_nooffset.jpg
http://www.itn.liu.se/~stegu/aqsis/absnoisetest/noisetest_offset.jpg

The difference is subtle at the code level, but the visual change is
dramatic and makes all the difference between ugly and nice.
Small tricks like these are often needed to hide the underlying
regularity of ordinary Perlin noise, whether periodic or not.

@bfishman
Copy link

@stegu This conversation happened 3 years ago, so hoping for a response is admittedly a bit of a shot in the dark. I've successfully incorporated the integer seed using the process you suggested into the 3D noise function, giving me 289 unique noisefields. I'm generating a procedural galaxy, so planets must use a unique seed, as the periodicity is too small to use offsets. Eventually I'll replace this with a texture-lookup implementation if that proves faster, but having the ability to modify the seed from within my development environment (Unity) in real-time is invaluable.

Anyway, perhaps unsurprisingly, the 289 unique seeds are insufficient, and so I naively attempted to implement the 'vector seed' idea you suggested.

//seed is a float4
float4 seedInt = floor(seed + .5);
p = permute(mod289(p + seedInt));

This produces extreme artifacts, where the simplex grid is clearly visible:

image

I expect this result is fully due to my naive implementation, and not your idea. If you're still around, would you mind elucidating how I might go about incorporating the vector seed?

Either way, thank you to everyone here!

@johanhelsing
Copy link

@bfishman I used this project for my own procedural terrain modeler. I implemented the vector based seed, but I don't remember getting any artifacts.

It's too long ago that I remember exactly what I did, but my changes are here:

https://github.com/noisemodeler/noisemodeler/blob/master/nmlib/codegeneration/glsl/glslsourcenoise2d.hpp

If you want to see for yourself, there are packages available for my project if you run windows or arch linux.

@bfishman
Copy link

@johanhelsing Thank you, but unfortunately I'm working with 3D noise. I implemented the exact same code as you did, in 2D, and it worked fine. But apparently this technique requires modification in 3D.

I'm still reading through the pre-publication article and attempting to understand how the additional permutation actually works, mathematically, so hopefully will come to a solution on my own. In that case, I'll report back here for posterity. But any hints from @stegu would be greatly appreciated!!

@bfishman
Copy link

Quick update: The following code seems to work.. although I haven't figured out a way to rigorously test all of the combinations. I'm not convinced that it's functioning as intended, although the artifacts are gone:

    float3 seedInt = floor(seed + .5);                   
                                 // Permutations
    i = mod289(i);
    float4 p = permute(
        permute(
            permute(i.z + float4(0.0, i1.z, i2.z, 1.0) + seedInt.z)
            + i.y + float4(0.0, i1.y, i2.y, 1.0) + seedInt.y)
        + i.x + float4(0.0, i1.x, i2.x, 1.0) + seedInt.x);

@stegu
Copy link
Contributor

stegu commented Jan 13, 2016 via email

@pyalot
Copy link

pyalot commented Jan 13, 2016

It's not important that every random seed produces a good result. However, it is important that at least half of them do. You don't want to end up in a situation where a user has to mash the "new seed" button 20x to get a good alternative seed. But mashing it two or three times is ok.

@johanhelsing
Copy link

@pyalot Maybe in your specific use case it's not important.

For me, however, that's not the case. I work on procedural content generation for games (no human author involved). Imagine if half of all started games looked like crap.

@bfishman
Copy link

I'm in the same boat as @johanhelsing - my use case is that of entirely procedural content generation (at runtime), with no option for human filtering.

But what is more important to me than 'good looking' noise, personally, is stability and variety. As long as the algorithm produces a noise field whose output remains bounded within the expected range, which is continuous in the 0th, 1st, and 2nd derivative, and where each seed is different than 99.9% of other seeds: even if the differences between unique seeds are generally small to minute - if it meets these criteria, I'm a happy coder.

At that point, I'll count on my hybrid multi fractals and other noise shaping algorithms to chaotically expand upon those minute differences to produce satisfyingly different terrains. But as the idiom goes, garbage in, garbage out.

@stegu Thanks for checking in to help validate the technique. And, of course, thanks for your work in the first place :) your presentation of the simplex noise algorithm (and subsequent textureless variant) is so much more approachable the Mr. Perlin's, and is no doubt responsible for its widespread adoption (although I still see people starting modern projects using the first version of Perlin Noise... It boggles..)

@bfishman
Copy link

I'll be posting the code in complete form soon, also incorporating gradient calculation. Is @ijm or anyone else from Ashima around? I'd be happy to make a PR, or I could create a new project entirely if that's preferred. Standing by for now.

@unicomp21
Copy link

Please keep me in the loop!

On Friday, January 15, 2016, bfishman notifications@github.com wrote:

I'll be posting the code in complete form soon, also incorporating
gradient calculation. Is @ijm https://github.com/ijm or anyone else
from Ashima around? I'd be happy to make a PR, or I could create a new
project entirely if that's preferred. Standing by for now.


Reply to this email directly or view it on GitHub
#9 (comment).

@unicomp21
Copy link

Maybe I'm missing something, why not use 4d noise? Where the button
changes the value on the 4th dimension?

On Friday, January 15, 2016, John Davis jdavis@pcprogramming.com wrote:

Please keep me in the loop!

On Friday, January 15, 2016, bfishman <notifications@github.com
javascript:_e(%7B%7D,'cvml','notifications@github.com');> wrote:

I'll be posting the code in complete form soon, also incorporating
gradient calculation. Is @ijm https://github.com/ijm or anyone else
from Ashima around? I'd be happy to make a PR, or I could create a new
project entirely if that's preferred. Standing by for now.


Reply to this email directly or view it on GitHub
#9 (comment).

@bfishman
Copy link

4D noise is much more computationally expensive than using 3D noise with a seed.

@unicomp21
Copy link

In that case, probably best to fork.

On Friday, January 15, 2016, bfishman notifications@github.com wrote:

4D noise is much more computationally expensive than using 3D noise with a
seed.


Reply to this email directly or view it on GitHub
#9 (comment).

@stegu
Copy link
Contributor

stegu commented Oct 14, 2020

Seeing how this thread is still very informative and discusses some optional and potentially useful changes which have not been incorporated into the versions in the repository, I am keeping it open, despite some very insulting and rude comments in the thread.

@CliveMcCarthy
Copy link

I added p = permute(p + vec3(289 * stroke_number));
where stroke_number is a random number between 0.0 and 1.0 that I pass, via a uniform, to my shader generated by Intel's RDRAND CPU based random number generator:
https://www.intel.com/content/www/us/en/developer/articles/guide/intel-digital-random-number-generator-drng-software-implementation-guide.html
It seems to do what I want.

@stegu
Copy link
Contributor

stegu commented Jul 29, 2023 via email

@stegu
Copy link
Contributor

stegu commented Jul 29, 2023 via email

@CliveMcCarthy
Copy link

Thank you Stephan,
I have modified my shader as you suggest. I am using the noise to produce a "patch" in the alpha of a texture. This is to represent randomly wiped "paint" from the "canvas" texture. Should a bit of correlation turn up, odds are it will simply look like the periodicity of the "canvas" weave.
This is a painting artwork but I had the notion to see if I could represent the paint being rubbed off the canvas with a turpentine rag. I capture an image of the canvas beneath, then render it with a randomly transparent peripheral area. Whether I actually find a use for it in an artwork remains to be seen...

@stegu
Copy link
Contributor

stegu commented Jul 30, 2023 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

7 participants