Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (744)
Games in Android Showcase (225)
games submitted by our members
Games in WIP (825)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Like Simplex Noise but don't like the patent? Introducing OpenSimplex Noise!  (Read 241940 times)
0 Members and 1 Guest are viewing this topic.
Offline KdotJPG
« Posted 2014-09-22 02:32:28 »

Coherent noise algorithms are a popular choice for procedural texturing and procedural terrain generation. There's Perlin Noise, which has grid artificts, and there's Simplex Noise, which is patented (for 3D+ implementations), so here's something new!

Blog Post: http://uniblock.tumblr.com/

Code: https://gist.github.com/KdotJPG/b1270127455a94ac5d19
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 485
Exp: 7 years



« Reply #1 - Posted 2014-09-22 02:37:36 »

I see you "Unlicensed" it, that's nice. Was my main concern when I saw it on reddit.

I do have question though, do you know if this runs afoul of the branch predictor?
That seems like a lot of branching and I expect it would be fairly random given that it's noise... I might investigate if I have time.
Offline KdotJPG
« Reply #2 - Posted 2014-09-22 04:03:34 »

Most if not all of the conditionals are geometry-based. Conditionals are used to figure out where you are on the lattice and figure out a small superset of the possible vertex contributions (i.e. points within one edge-length of the input point), math is done on each vertex to compute its distance away, another conditional is used to confirm whether or not that point does actually contribute, then if it does more math is done and a final value is added to a total.

EDIT: i.e., no matter what "seed" you're using, the branches will happen the same way. The "seed" just determines what happens in the last math step (gradient selection at the vertex, extrapolation, and multiplication by the distance-based attenuation).
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen

JGO Kernel


Medals: 516



« Reply #3 - Posted 2014-09-22 10:04:58 »

Table lookups are not your friend.
Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #4 - Posted 2014-09-22 11:44:27 »

thanks for sharing!

this one generates really nice patterns. compared to regular Gustavson's simplex noise it

- calculates twice as long
- doubles feature size
- generates slightly lower contrast
- generates way less visible repeating patterns.

top : simplex, bottom : opensimplex
Offline Riven
Administrator

« JGO Overlord »


Medals: 1327
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2014-09-22 17:36:15 »

Why isn't the OP medal-slapped?! Pointing

This is technically impressive, produces seriously high quality output, and above all: is usable for a lot of projects.


That it's somewhat slower than simplex noise, yet faster (allegedly) than perlin noise, is only a mere inconvenience for the performance junkies.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline ags1

JGO Kernel


Medals: 356
Projects: 7


Make code not war!


« Reply #6 - Posted 2014-09-22 20:58:56 »

Just what I have been looking for!

Offline Roquen

JGO Kernel


Medals: 516



« Reply #7 - Posted 2014-09-23 07:37:22 »

OP:  I took a quick peek at the output of a single sample and it appears like there's a bug...perhaps the output isn't full range.  Visually it looks like a lightweight blur has been applied.

Quote
Why isn't the OP medal-slapped?! Pointing
My 2011 reference implementation which is twice as fast, equal usable and patent free (assuming you don't flip the switch) has a grand total of zero.  Potentially useful things often don't get bombarded with medals as I'm sure you're aware.  Stefan Gustavson's version from 2005 is likewise patent free and equally usable.  BTW as far as patent's are concerned this one is nice as it only claims an exact formulation.  So this whole patent free thing is much ado about nothing.

Quote
... is only a mere inconvenience for the performance junkies.
But  performance is quite important for this kind of noise.  It needs to be fast enough to not require build-time generation.  If you need build-time generation then you might was well kick it up a notch to a non-realtime noise generator.
Offline Grunnt

JGO Kernel


Medals: 143
Projects: 8
Exp: 5 years


Complex != complicated


« Reply #8 - Posted 2014-09-23 11:10:12 »

And the Lord Hath spoken: "Thou shalt Slap him with Medals!".

And Lo and Behold, he was Slappeth with many Medals.

Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #9 - Posted 2014-09-23 13:42:24 »

My 2011 reference implementation ...

is it this : have http://www.java-gaming.org/topics/simplex-noise-3d/23962/view.html ?

just curious, do you have a newer version of it somewhere ? it is almost as fast as stefan gustavson's (http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf) version, easier to read but generates slightly more repeating patterns (due to hashing ?).
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen

JGO Kernel


Medals: 516



« Reply #10 - Posted 2014-09-23 14:07:36 »

A newer version is here: https://github.com/roquendm/JGO-Grabbag/blob/master/src/roquen/pg/noise/SimplexNoise3D.java

Flipping to the more expensive hash removes some defects, but this is intended to be example code not really production ready.  I really need to add a note about the patent to the source.  There's all kinds of choices about hashes depending on use-case.
Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #11 - Posted 2014-09-23 14:24:25 »

thanks Smiley that one get's even closer to the reference (speedwise with
simpleHash
). very impressive considering there are no LUT's involved.

Offline Grunnt

JGO Kernel


Medals: 143
Projects: 8
Exp: 5 years


Complex != complicated


« Reply #12 - Posted 2014-09-23 14:37:37 »

In case someone is interested, here is a stripped-down 2D version of Gustavson's SimplexNoise implementation that is relatively readable. Performance is quite OK, although I do not have any benchmarking. Also, this uses a fast pseudo-random number generator, but you could use any other random generator as well.

Edit: put the code in the pastebin:
http://pastebin.java-gaming.org/fa70a2c870418

Offline philfrei
« Reply #13 - Posted 2014-09-23 19:16:59 »

I tried converting all the doubles to floats in Gustavson's version a couple weeks ago, and found no measurable performance difference. Maybe this says more about my benchmarking ability than the code.

This is the first I've heard of patents being an issue with the Simplex algorithm. I have an app with a background graphic where 2D cirrus clouds are floating by, making use of 3D translation. I'm wondering if this use requires any sort of payment. Right now I'm just acknowledging Gustavson, as he requests in his code.

Roquen makes a very good point about performance being relevant. At this point, I'm calling the Simplex graphic effect a "placeholder" because it uses over twice the amount of cpu of the main program, e.g., a usage level of 15% jumps to 45% when I turn on this skin animation. So, I'm glad for the reminder, and will be giving Roquen's a try again.

Roquen: marketing and pitching is an art. (Just finishing reading Jane Bussman's "A Journey into the Dark Heart of Nameless Unspeakable Evil"--Hilarious, with many insights into how the world works. I recommend it to all JGO'ers.) 

music and music apps: http://adonax.com
Offline Roquen

JGO Kernel


Medals: 516



« Reply #14 - Posted 2014-09-24 06:58:45 »

OP: I just turned up a multiply factor and started to see results in line with my expectations, so I think the problem with your code is that it's isn't returning full range.

Gustavson's version from the paper is out of date, at least the last time I looked at the paper, check the code: http://webstaff.itn.liu.se/~stegu/simplexnoise/

Quote
... all the doubles to floats in ... no measurable performance difference
I use singles because doubles don't bring anything to the table.  On intel the time to issue and latency of single and double add/mul are the same so without reading/writing they should be the same.  Who knows embedded devices might take off sometime in the future which don't use intel desktop/mobile CPUs.
Offline philfrei
« Reply #15 - Posted 2014-09-24 09:23:30 »

OP: I just turned up a multiply factor and started to see results in line with my expectations, so I think the problem with your code is that it's isn't returning full range.

Gustavson's version from the paper is out of date, at least the last time I looked at the paper, check the code: http://webstaff.itn.liu.se/~stegu/simplexnoise/

Quote
... all the doubles to floats in ... no measurable performance difference
I use singles because doubles don't bring anything to the table.  On intel the time to issue and latency of single and double add/mul are the same so without reading/writing they should be the same.  Who knows embedded devices might take off sometime in the future which don't use intel desktop/mobile CPUs.
Makes sense. I think the bottom graphic looks a little "faded" compared to the top, which had me wondering if the new version wasn't reaching the same extremes in range.

I didn't know that the difference between floats and doubles are not so much in calculations, but in pipeline. Thanks for that! That is also in line with what I experienced.

music and music apps: http://adonax.com
Offline Roquen

JGO Kernel


Medals: 516



« Reply #16 - Posted 2014-09-24 09:56:31 »

singles and doubles only have the same latency numbers for the most basic operations, so divide will differ etc...add,mul,fabs..the super basics are the same.
Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #17 - Posted 2014-09-24 11:06:28 »

output range test of 65000 samples normalized to 0.0 ... 1.0 :

value noise         : 0.012 - 0.988
reference simplex   : 0.013 - 0.986
roquen's simplex    : 0.018 - 0.985
open simplex        : 0.038 - 0.959


slightly off.
Offline KdotJPG
« Reply #18 - Posted 2014-10-06 02:31:20 »

BTW I went ahead and updated the code to include 2D and 4D implementations alongside the 3D implementation, as well as tweaked the gradient set that's being used for the 3D implementation.

http://uniblock.tumblr.com/post/99279694832/2d-and-4d-noise-too

https://gist.github.com/KdotJPG/b1270127455a94ac5d19

Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #19 - Posted 2014-10-07 22:56:47 »

thanks alot again!  Grin

- 2d version is "only" 1.5 times slower then Gustavson's simplex noise.
- 4d version is, as expected, way slower but generates much better patterns.

output range after 80000 samples :

2D : 0.068 - 0.932
3D : 0.060 - 0.932
4D : 0.060 - 0.935


nicely in range.

a bit of comparison :

4D, top : opensimplex, bottom Gustavson's



4D false color, top : opensimplex, bottom Gustavson's



4D false color + FBM, top : opensimplex, bottom Gustavson's



colors could be better i know Smiley but we can see opensimplex's patterns are much better.
Online LiquidNitrogen
« Reply #20 - Posted 2014-10-10 07:15:07 »

This is fantastic, I've been sitting here half the day thinking about using noise to generate terrain but feeling too brain dead to actually research how to implement it. Then I remembered this thread and have it producing nice patterns in 10 minutes without having to use any brain power Cheesy
Offline philfrei
« Reply #21 - Posted 2014-10-20 23:27:17 »

@KdotJPG  -- or anyone else that understands these legal issues:

If your "open" implementation makes use of a geometrical "Simplex" for generating gradient noise uses of 3D or more, what exactly is it that you've done that puts this out of the reach of Ken Perlin's patent?

This is an honest question, not an attempt to shoot anything down. I don't have much knowledge of how patent law works in this situation. How is your implementation any more or less restricted than what Gustavson coded?

I'm assuming Simplexes are involved, since they are part of the title of the project.

music and music apps: http://adonax.com
Offline KdotJPG
« Reply #22 - Posted 2014-10-21 01:54:20 »

Here's my non-lawyer take on it: If you read the patent claims: http://www.google.com/patents/US6867776:

Claim #1 talks about the hardware-implementation-optimized gradient generator. Most software implementations of Simplex Noise don't use this anyway, and OpenSimplex Noise certainly doesn't.

Claim #2(&3&4) talk about using (x',y',z')=(x+s,y+s,z+s) where s=(x+y+z)/3 to transform the input (render space) coordinate onto a simplical grid, with the intention to make all of the "path-simplices" approximately regular. OpenSimplex Noise (in 3D) uses s=-(x+y+z)/6 to transform the input point to a point on the Simplectic honeycomb lattice so that the simplices bounding the (hyper)cubes at (0,0,..,0) and (1,1,...,1) work out to be regular. It then mathematically works out that s=(x+y+z)/3 is needed for the inverse transform, but that's performing a different (and opposite) function.

Claim #5(&6) are specific to the path-simplex lattice. Simplex Noise divides the (squashed) n-dimensional (hyper)cube into n! simplices based on ordered edge traversals, whereas OpenSimplex Noise divides the (stretched) n-dimensional (hyper)cube into n polytopes (simplices, rectified simplices, birectified simplices, etc.) based on the separation (hyper)planes at integer values of (x'+y'+z'+...). In 3D this works out to six approximately-regular "path simplices" per cube for Simplex Noise, and two regular tetrahedra plus one regular octahedron per cube for OpenSimplex Noise.

The other interesting point is that, if you read all of the claims, none of them appear to apply to the 2D analogue of Simplex noise so long as it uses a gradient generator separate from the one described in claim #1. The skew function in Claim #2 only applies to 3D, and #5 explicitly refers to n>=3. Also, both Simplex Noise and OpenSimplex Noise generalize to different orientations of the equilateral triangle tiling in 2D.

And none of the patent claims speak about using surflets / "spherically symmetric kernels" to generate the "images with texture that do not have visible grid artifacts," which is probably the biggest similarity between the two algorithms.

TL;DR it's not doing the same thing.
Offline Roquen

JGO Kernel


Medals: 516



« Reply #23 - Posted 2014-10-21 07:19:17 »

The patent claim is very nice.  It narrow and its intention is targeting same results everywhere and primarily hardware implementations.  So pretty much only CG houses with specialized hardware...unless GPU IHVs decide to make native ops.  Much ado about nothing.
Online princec

« JGO Spiffy Duke »


Medals: 982
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #24 - Posted 2014-10-21 10:14:24 »

Indeed, I wouldn't bat an eyelid if I were to implement the original simplex noise somewhere inside a game to make some clouds or terrain or whatnot.

Cas Smiley

Offline DarkCart

JGO Kernel


Medals: 121
Projects: 9
Exp: 50 years


It's all in the mind, y'know.


« Reply #25 - Posted 2014-10-21 21:56:23 »

Oh. My. Gosh. Where has this been all my life? Thank you so much!


The darkest of carts.
Offline ags1

JGO Kernel


Medals: 356
Projects: 7


Make code not war!


« Reply #26 - Posted 2014-10-21 21:57:02 »

Very pretty, DarkCart!

Offline DarkCart

JGO Kernel


Medals: 121
Projects: 9
Exp: 50 years


It's all in the mind, y'know.


« Reply #27 - Posted 2014-10-21 21:58:32 »

Thanks. Just fooling around with it, then that popped up. Well done.

The darkest of carts.
Pages: [1]
  ignore  |  Print  
 
 

 
Ecumene (149 views)
2017-09-30 02:57:34

theagentd (222 views)
2017-09-26 18:23:31

cybrmynd (301 views)
2017-08-02 12:28:51

cybrmynd (288 views)
2017-08-02 12:19:43

cybrmynd (297 views)
2017-08-02 12:18:09

Sralse (291 views)
2017-07-25 17:13:48

Archive (978 views)
2017-04-27 17:45:51

buddyBro (1102 views)
2017-04-05 03:38:00

CopyableCougar4 (1678 views)
2017-03-24 15:39:42

theagentd (1430 views)
2017-03-24 15:32:08
Java Gaming Resources
by philfrei
2017-12-05 19:38:37

Java Gaming Resources
by philfrei
2017-12-05 19:37:39

Java Gaming Resources
by philfrei
2017-12-05 19:36:10

Java Gaming Resources
by philfrei
2017-12-05 19:33:10

List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!