Project: Miniverse

[vgo]

I've improved the quality of my noise routines a lot and this means better surface features on the planets. However, it has also made the renderer a lot slower, I need to find a way to speed up the noise routines.







You can get the new version HERE.

Now I'm gonna do a complete rewrite for the renderer to make it better, then start adding all kinds of nifty detail on the surface...

[NecroDOME]

I can see my house from here !!

Nice work man! Have you any textured screenshots?

[vgo]

There's no support for textures yet, I need to figure out how to implement climate zones, terrain type on different slopes etc. before I can start texturing the planets.

I've just started rewriting the procedural planet class and hopefully I can fix the cracks between nodes with different LOD and maybe then I could try some textures on it (maybe 4-8 different textures with variation based on altitude only). I need to add the cube map rendering too, so that I can create the textures that are used to render the planet from far away.

[vgo]

Well, I thought that at this point I'd be coding the new version of the renderer, but I was not very happy with my noise routines, so I decided to do something about it.

First I implemented "Improved Perlin Noise" based on the Java reference implementation by Ken Perlin, it was slightly faster than the original, but still not fast enough.

Then I started working on a even faster version and I finally cracked it. I already had an earlier version based on code that I got from the guy who codes the Infinity MMO project, but I couldn't get it to tile properly so I scrapped that one. I took a few bits from this and the rest from the improved noise, implemented a couple of FPU tricks and voila! New very fast noise routine!

I compared this to the fast Perlin noise code by IA and it's even faster than that! Noise quality is also very good, only slightly worse than the original Perlin noise and completely unnoticeable on my planet renderer.

Here's some test results from 3 different noise routines that are all based on the Perlin noise:

Perlin Noise: 1,10200 seconds
Improved Perlin Noise: 0,90000 seconds
Fast Perlin Noise IA: 0,52000 seconds
Fast Perlin Noise: 0,39000 seconds

The first two are based on original code by Ken Perlin and the last one is my own modification of the second version. The Fast Perlin Noise IA is the "reference implementation" by IA (aka Ysaneya at gamedev.net).
My test program took 1000000 samples from each noise generator and calculated the elapsed time.

The first one is the noise routine that I've used so far, so speed improvement is quite dramatic.

I updated my planet renderer to use the new noise routine and there's hardly any stuttering on the low altitudes anymore unless you're moving too fast. You can get the new version HERE. This is hopefully the last release using the old procedural planet class.

[paul_nicholls]

Well, I thought that at this point I'd be coding the new version of the renderer, but I was not very happy with my noise routines, so I decided to do something about it.

First I implemented "Improved Perlin Noise" based on the Java reference implementation by Ken Perlin, it was slightly faster than the original, but still not fast enough.

Then I started working on a even faster version and I finally cracked it. I already had an earlier version based on code that I got from the guy who codes the Infinity MMO project, but I couldn't get it to tile properly so I scrapped that one. I took a few bits from this and the rest from the improved noise, implemented a couple of FPU tricks and voila! New very fast noise routine!

I compared this to the fast Perlin noise code by IA and it's even faster than that! Noise quality is also very good, only slightly worse than the original Perlin noise and completely unnoticeable on my planet renderer.

Here's some test results from 3 different noise routines that are all based on the Perlin noise:

Perlin Noise: 1,10200 seconds
Improved Perlin Noise: 0,90000 seconds
Fast Perlin Noise IA: 0,52000 seconds
Fast Perlin Noise: 0,39000 seconds

The first two are based on original code by Ken Perlin and the last one is my own modification of the second version. The Fast Perlin Noise IA is the "reference implementation" by IA (aka Ysaneya at gamedev.net).
My test program took 1000000 samples from each noise generator and calculated the elapsed time.

The first one is the noise routine that I've used so far, so speed improvement is quite dramatic.

I updated my planet renderer to use the new noise routine and there's hardly any stuttering on the low altitudes anymore unless you're moving too fast. You can get the new version HERE. This is hopefully the last release using the old procedural planet class.

Hi vgo,
Well done! :-)

Even your original perlin noise routine is over twice as fast as my Pascal perlin noise translation I did a while ago.

Mine takes around 2.8 seconds to do the 1000000 iterations!!

Is there any chance I can get your fast perlin noise routine off you?

EDIT:
my function:

Function TPerlinNoise.PerlinNoise3d(x,y,z: Double;
                                    Persistence: Single = 0.25;
                                    Frequency: Single = 1;
                                    Octaves: Integer = 4): Double;

I was using the above defaults for persistence, frequency and octaves...
cheers,
Paul.

[paul_nicholls]

PS. if anyone is intersted in my slower (but working) perlin noise class, here is the unit:

Unit PerlinNoiseUnit;

Interface

{$R-}
{$Q-}

Const
  _B = $100;
  BM = $ff;

  N = $1000;

Type
    TPerlinNoise = Class
    Private
        P : Array[0..(_B+_B+2)-1] Of Integer;
        G1: Array[0..(_B+_B+2)-1] Of Double;
    Public
        Constructor Create(Seed: Integer);

        Procedure InitNoise(Seed: Integer);
        Function Noise1d(x: Double): Double;
        Function Noise2d(x,y: Double): Double;
        Function Noise3d(x,y,z: Double): Double;

        Function PerlinNoise1d(x: Double;
                               Persistence: Single = 0.25;
                               Frequency: Single = 1;
                               Octaves: Integer = 4): Double;
        Function PerlinNoise2d(x,y: Double;
                               Persistence: Single = 0.25;
                               Frequency: Single = 1;
                               Octaves: Integer = 4): Double;
        Function PerlinNoise3d(x,y,z: Double;
                               Persistence: Single = 0.25;
                               Frequency: Single = 1;
                               Octaves: Integer = 4): Double;
    End;

Implementation

Uses
    SysUtils;

Function TPerlinNoise.Noise1d(x: Double): Double;
Var
  bx0,bx1: Integer;
  rx0,sx,t,u,v: Double;
Begin
  t := x+N;
  bx0 := Trunc(t) And BM;
  bx1 := (bx0+1) And BM;
  rx0 := t-Trunc(t);

  sx := (rx0*rx0*(3.0-2.0*rx0));

  u := G1[P[bx0]];
  v := G1[P[bx1]];

  Result := u+sx*(v-u);
End;

Function TPerlinNoise.Noise2d(x,y: Double): Double;
Var
  bx0,bx1,by0,by1: Integer;
  i,j: Integer;
  rx0,ry0: Double;
  sx,sy: Double;
  a,b,t,u,v: Double;
Begin
  t := x+N;
  bx0 := Trunc(t) And BM;
  bx1 := (bx0+1) And BM;
  rx0 := t-Trunc(t);

  t := y+N;
  by0 := Trunc(t) And BM;
  by1 := (by0+1) And BM;
  ry0 := t-Trunc(t);

  i := P[bx0];
  j := P[bx1];

  sx := (rx0*rx0*(3.0-2.0*rx0));
  sy := (ry0*ry0*(3.0-2.0*ry0));

  u := G1[P[i+by0]];
  v := G1[P[j+by0]];
  a := u+sx*(v-u);

  u := G1[P[i+by1]];
  v := G1[P[j+by1]];
  b := u+sx*(v-u);

  Result := a+sy*(b-a);
End;

Function TPerlinNoise.Noise3d(x,y,z: Double): Double;
Var
  bx0,bx1,by0,by1,bz0,bz1: Integer;
  i,j,k,l: Integer;
  rx0,ry0,rz0: Double;
  sx,sy,sz: Double;
  a,b,c,d,t,u,v: Double;
Begin
  t := x+N;
  bx0 := Trunc(t) And BM;
  bx1 := (bx0+1) And BM;
  rx0 := t-Trunc(t);

  t := y+N;
  by0 := Trunc(t) And BM;
  by1 := (by0+1) And BM;
  ry0 := t-Trunc(t);

  t := z+N;
  bz0 := Trunc(t) And BM;
  bz1 := (bz0+1) And BM;
  rz0 := t-Trunc(t);

  i := P[bx0];
  j := P[bx1];

  k := P[i+by0];
  l := P[j+by0];
  i := P[i+by1];
  j := P[j+by1];

  sx := (rx0*rx0*(3.0-2.0*rx0));
  sy := (ry0*ry0*(3.0-2.0*ry0));
  sz := (rz0*rz0*(3.0-2.0*rz0));

  u := G1[P[k+bz0]];
  v := G1[P[l+bz0]];
  a := u+sx*(v-u);

  u := G1[P[i+bz0]];
  v := G1[P[j+bz0]];
  b := u+sx*(v-u);

  c := a+sy*(b-a);

  u := G1[P[k+bz1]];
  v := G1[P[l+bz1]];
  a := u+sx*(v-u);

  u := G1[P[i+bz1]];
  v := G1[P[j+bz1]];
  b := u+sx*(v-u);

  d := a+sy*(b-a);

  Result := c+sz*(d-c);
End;

constructor TPerlinNoise.Create(Seed: Integer);
Begin
  inherited Create;

  InitNoise(Seed);
End;

procedure TPerlinNoise.InitNoise(Seed: Integer);
Var
  i,j: Integer;
Begin
  RandSeed := Seed;

  For i := 0 to _B - 1 Do
  Begin
    P[i] := i;
    G1[i] := 2*Random-1;
  End;

  For i := 0 to _B - 1 Do
  Begin
    j := Random(_B);
    P[i] := P[i] xor P[j];
    P[j] := P[j] xor P[i];
    P[i] := P[i] xor P[j];
  End;

  For i := 0 to _B+2 - 1 Do
  Begin
    P[_B+i] := P[i];
    G1[_B+i] := G1[i];
  End
End;

Function TPerlinNoise.PerlinNoise1d(x: Double;
                                    Persistence: Single = 0.25;
                                    Frequency: Single = 1;
                                    Octaves: Integer = 4): Double;
Var
    i: Integer;
    p,s: Double;
Begin
    Result := 0;
    s := Frequency;
    p := 1;
    For i := 0 to Octaves - 1 Do
    Begin
        Result := Result + p * Noise1d(x * s);
        s := s * 2;
        p := p * Persistence;
    End;
End;

Function TPerlinNoise.PerlinNoise2d(x,y: Double;
                                    Persistence: Single = 0.25;
                                    Frequency: Single = 1;
                                    Octaves: Integer = 4): Double;
Var
    i: Integer;
    p,s: Double;
Begin
    Result := 0;
    s := Frequency;
    p := 1;
    For i := 0 to Octaves - 1 Do
    Begin
        Result := Result + p * Noise2d(x * s,y * s);
        s := s * 2;
        p := p * Persistence;
    End;
End;

Function TPerlinNoise.PerlinNoise3d(x,y,z: Double;
                                    Persistence: Single = 0.25;
                                    Frequency: Single = 1;
                                    Octaves: Integer = 4): Double;
Var
    i: Integer;
    p,s: Double;
Begin
    Result := 0;
    s := Frequency;
    p := 1;
    For i := 0 to Octaves - 1 Do
    Begin
        Result := Result + p * Noise3d(x * s,y * s,z * s);
        s := s * 2;
        p := p * Persistence;
    End;
End;

End.

cheers,
Paul.

[vgo]

I might clean up my code a bit and then post it here. But there's a catch in it (there always is ), it MAY NOT work as expected if you use Trunc/Floor/Round/etc. in your code, this is because of the fpu tricks that I use. The VCL code in Delphi may alter the fpu registers which will stop the noise routine from working properly... So, it's pretty much "use only if you really know what you're doing".

This could be easily fixed by checking/resetting the fpu registers, but this would also nullify the speed increase, making it just as slow as it was before... It's fast because the code expects to find the fpu always in a certain state.

The best approach would be to code the whole noise routine in MMX assembly, but I don't have time for that.

Anyway, the noise code is not directly comparable to yours, because I don't handle the octaves/frequency in the actual noise generator, instead I use fractal and other routines to control this.

But I could try another similar test with 16 octaves etc. to see what's what.

I also noticed a bit of a problem in your implementation: You can't use Trunc instead of Floor when calculating the gradient indices. The results may look similar, but especially on higher octaves you get artifacts and the noise output won't tile properly in 3D.

By default my planet renderer uses 16 octaves fBm and when combined with ridged multifractal that's 16 + 8 octaves for each point generated on the planet and if I use Trunc instead of Floor the results are BAD...

[paul_nicholls]

Thanks for the reply and interesting information vgo :-)
I am still interested in seeing your noise generation code anyway when you are ready to post it, regardless of catches and tricks <G>

Keep up the excellent work

cheers,
Paul

[Chavez_US]

Nice work vgo!...Are you still experimenting with project miniverse?

This could be easily fixed by checking/resetting the fpu registers, but this would also nullify the speed increase, making it just as slow as it was before... It's fast because the code expects to find the fpu always in a certain state...The best approach would be to code the whole noise routine in MMX assembly,...

Because the MMX registers overlay the FPU registers, you cannot mix FPU and MMX instructions in the same computation sequence. You can begin executing an MMX instruction sequence at any time; however, once you execute an MMX instruction you cannot execute another FPU instruction until you execute a special MMX instruction, EMMS (Exit MMX Machine State). This instruction resets the FPU so you may begin a new sequence of FPU calculations. The CPU does not save the FPU state across the execution of the MMX instructions; executing EMMS clears all the FPU registers. Because saving FPU state is very expensive, and the EMMS instruction is quite slow, it's not a good idea to frequently switch between MMX and FPU calculations. Instead, you should attempt to execute the MMX and FPU instructions at different times during your program's execution. http://webster.cs.ucr.edu/AoA/Window...uctionSet.html

Can speed be increased by buffering (flushing) and caching? I think more data can be transferred with less procedural calls, which in turn reduces system call overhead...and items in a cache are not limited to a specific type, form, or size...

Rick (Chavez_US)