Jump to content
  • Advertisement
Sign in to follow this  
bluntman

Perlin(ish) noise, and floating point precision.

This topic is 3168 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am working on a planet rendering engine, that generated height values using a modified version of 3D Perlin noise (an SSE implementation of it I wrote myself to be exact). I am running into precision problems when I get down to the sub ~10 meters scale. I end up with ridges, and I am assuming this is caused by quantization due to the tiny value ranges I am dealing with at this detail level (the planet is 6000 km radius, the height values are all within a 10 km range, and the camera can get up to 1 m from the ground). I am trying to work out how I can eliminate this noise problem. Does anyone have any experience with this sort of problem? I have got a few ideas of how to fix it, but I really don't want to implement every one of them. I have already tried generating noise using two seperate noise generators then combining them at double precision, but as each one individually already has the quantization problems there is no benefit there. The input values are all floating point, as the algorithm uses SSE instructions to calculate 4 values at a time. If I switch the whole algorithm to double precision then I am going to ~double its execution time. Any ideas on how I can still use the float noise, but get rid of this precision problem? I know this question is a bit nebulous, I am kind of hoping someone here has run into this exact problem before and give me a hint at least in the right direction to go.

Share this post


Link to post
Share on other sites
Advertisement
I've run into this exact problem, and spent a lot of time trying to find a solution with moderate success. One thing that helps a bit is to change the input to fp64 (doubles) but keep as much of the algorithm as possible as fp32 for performance reasons. If you're using improved Perlin noise, it looks like this:


TFloat CPerlinNoise::improvedNoise3DD(const SVec3DD& xyz)
{
/// improved Perlin noise, standard version
const TInt xtr = MDoubleToInt(xyz.x - 0.5);
const TInt ytr = MDoubleToInt(xyz.y - 0.5);
const TInt ztr = MDoubleToInt(xyz.z - 0.5);

const TInt X = xtr & 255;
const TInt Y = ytr & 255;
const TInt Z = ztr & 255;

const TFloat x = (TFloat)(xyz.x - xtr);
const TFloat y = (TFloat)(xyz.y - ytr);
const TFloat z = (TFloat)(xyz.z - ztr);

const TFloat u = _smoothstep5F(x);
const TFloat v = _smoothstep5F(y);
const TFloat w = _smoothstep5F(z);

const TInt A = ms_impPerm[X] + Y;
const TInt AA = ms_impPerm[A] + Z;
const TInt AB = ms_impPerm[A + 1] + Z;
const TInt B = ms_impPerm[X + 1] + Y;
const TInt BA = ms_impPerm + Z;
const TInt BB = ms_impPerm[B + 1] + Z;

return(_lerpF(w, _lerpF(v, _lerpF(u, _gradF(ms_impPerm[AA], x, y, z),
_gradF(ms_impPerm[BA], x - 1, y, z)),
_lerpF(u, _gradF(ms_impPerm[AB], x, y - 1, z),
_gradF(ms_impPerm[BB], x - 1, y - 1, z))),
_lerpF(v, _lerpF(u, _gradF(ms_impPerm[AA + 1], x, y, z - 1),
_gradF(ms_impPerm[BA + 1], x - 1, y, z - 1)),
_lerpF(u, _gradF(ms_impPerm[AB + 1], x, y - 1, z - 1),
_gradF(ms_impPerm[BB + 1], x - 1, y - 1, z - 1)))));
}


Y.

Share this post


Link to post
Share on other sites
Ah, exactly who I was thinking of when I said "someone" :). Thanks for the reply!
So on your planets, what detail level do you actually go to? Have you made them 100% real world scale, or just close enough to look right? I remember you mentioned somewhere that you managed to move your noise generation onto the GPU (or maybe it was that you were going to), did you manage, and if so, did you manage to still get around the precision problems (as obviously there is no double support in 99% of cards)?

Share this post


Link to post
Share on other sites
Decide how many fractional bits of accuracy you need and check that your floats are actually using the full available range.

Sounds obvious but make sure youre taking full advantage of the negative range as well, i.e. the center of your planet is 0,0,0. Worth checking. (I've worked on 3D action games which ran into float precision problems where the fix was to reposition the entire level about the origin rather than having the origin way off the bottom left of the map)

I'm afraid I've never written a planet renderer, (well, not a good one anyway) I have written very very large flat landscape renderer where each tile had it's own float coordinate system and then there was a second integer based coordinate system over the top. The global origin was moved to whichever tile the camera was in, the transform for all adjacent tiles were adjusted accordingly, i.e. the transform for the cameras tile was always Identity * ViewMatrix, the transform for the adjacent tiles was created relative to the cameras tile, OffsetMatrix[0..7 for N,S,E,W,NE,SE,SW,NW] * ViewMatrix. That way the vertices were never transformed by any large numbers and precision is never sacrificed, my only restriction was you could never see more than current and adjacent tile (the tiles were large)

I'm not sure you could build your planet like this? Say the traditional displaced cube with each face divided into 4 local spaces?

Another idea would be to use hardware subdivision to subdivide further in view space and add final levels of noise here. i.e. subdivide on the CPU to the point at which you run our of precision, transform the vertices on viewspace at runtime and add yet more noise. Not easy though, particularly for things like collision detection.

Share this post


Link to post
Share on other sites
Yeah I am already using local coordinate spaces for every chunk-lod root (which occur on every polygon of the base planet mesh, so there are a lot). Unfortunately regardless of local coordinate systems, I still have to convert all positions back to world-local space to calculate their heights, as the noise generator requires a 3D coordinate, and only a sphere around the origin will give the correct, continuous noise function I require.

Share this post


Link to post
Share on other sites
Humm yeah I see you problem...

My gut feeling is that you could adapt the noise function to take the integer coordinate frame as well. This 'might' be as simple as simply converting the supplied float to cell indices (as usual) and adding to that.

Share this post


Link to post
Share on other sites
So I converted my entire algorithm over to using double for everything (iteratively, as each successive change didn't fix the quantization problems), and I still have the same problems. I'm thinking it may have to do with using a local transform at each chunk-lod root. I have heard that double precision numbers have the capability to represent coordinates accurate to within a cm in billions of km.
.. a few minutes later: I have just been reading the wikipedia article on Floating point numbers, and it mentions something that fits with my guess about the local transforms:
Quote:
Cancellation: subtraction of nearly equal operands may cause extreme loss of accuracy. This is perhaps the most common and serious accuracy problem.


Obviously, my local transform root for each chunk lod is relatively close to the actual vertices, so when localising and globalising to and from a particular patch back into world (planet) space I am effectively subtracting numbers that are pretty close to each other. The next thing I am going to try is completely removing the local transforms from the base dataset, and only transforming to local space when I upload to the vertex buffer. I will report for posterity once I have tried this last ditch attempt.

Share this post


Link to post
Share on other sites
Quote:
Original post by bluntman
Ah, exactly who I was thinking of when I said "someone" :). Thanks for the reply!
So on your planets, what detail level do you actually go to? Have you made them 100% real world scale, or just close enough to look right?


It is 100% real world scale, and my test planet is 6350 Km of radius. I have found that I'm starting to have precision issues at depth 13-14, but those are still acceptable. It gets much worse at level 15-16, and totally unacceptable over 16. I need depth 16-17 to get down to the meter resolution on the ground surface.

Originally I generated the procedural geometry (mesh vertices) on the CPU so I could use doubles, and had no particular precision issues.

Quote:
Original post by bluntman
I remember you mentioned somewhere that you managed to move your noise generation onto the GPU (or maybe it was that you were going to), did you manage, and if so, did you manage to still get around the precision problems (as obviously there is no double support in 99% of cards)?


Correct, that was me. One thing I was disatisfied with in the previous version was that I only generated the mesh on the cpu, and I wanted to generate normal maps too, which was too slow on the CPU (imagine generating a 512x512 unique texture per chunk, each texel requiring 40+ octaves of noise). So I implemented the procedural generation on the GPU, and now use it both for geometry (with a read-back to the CPU) and for normal maps generation.

To this day, I still have the precision issues, and as it works on the GPU I cannot use doubles (yet). I actually plan on moving back the mesh generation on the CPU, just to be able to reuse doubles and fix "cracks" in the terrain due to that lack of precision; and keep the normal maps on the GPU with the limited precision, but also limit the maximum depth the normal maps can go to, probably around depth 14-15.

Not an ideal solution but it's the best I can think of at the moment.

Quote:
Original post by bluntman
So I converted my entire algorithm over to using double for everything (iteratively, as each successive change didn't fix the quantization problems), and I still have the same problems. I'm thinking it may have to do with using a local transform at each chunk-lod root. I have heard that double precision numbers have the capability to represent coordinates accurate to within a cm in billions of km.


That's correct, doubles have enough precision for a planetary engine. If I remember well, they were good enough to have millimeter accuracy at a distance of 100 AUs (1 AU = distance Sun-Earth). If you're using doubles and still have precision issues, you must have a bug in your code somewhere, like a cast to float that you forgot somewhere..

Y.

Share this post


Link to post
Share on other sites
Yeah you were right, I was still doing a floating point operation: my matrix_transform function took and returned floating point matrices and vectors, and the matrices and vectors had (stupidly) implicit conversion constructors. So with that function converted to use a template type everything works as expected, perfect precision down to any level I want. Now I have to undo some of the changes I have done to try and make it reasonably fast again :/

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!