Sign in to follow this  
ManaStone

Why are height maps saved in power of 2 dimensions?

Recommended Posts

ManaStone    148
Shouldn’t height maps be saved in powers of 2 +1? If you have a 64x64 height map and you need to find the midpoint for doing LOD stuff, you are not going to be able to find the vertex midpoint since it divides evenly. I’m asking this because I’m trying to build a practical height map editor( I already built a none practical one).

Share this post


Link to post
Share on other sites
xor    516
Powers of two are used to avoid multiplications.
In an array, instead of doing something like:

array[y][x] or array[y*sizex+sizex]

To access it's values, you can use instead:

array[(y<<shift)sizex]

Which is faster.

Share this post


Link to post
Share on other sites
Fingers_    410
It used to be significantly faster, you'd definitely use powers of two and shifting on a 486 (or clever tricks like storing 8-bit X and Y in the two bytes of a short)... Nowadays your CPU multiplies pretty fast and spends most of its time waiting for the video card anyway so this little optimization won't affect the performance.

Share this post


Link to post
Share on other sites
ManaStone    148
Ok, so how are you going to do a triangle split if you don't have a midpoint? Are you going to have to ignore a whole lot of height map values or round up or down for the midpoint?

Share this post


Link to post
Share on other sites
xor    516
Quote:
Original post by Fruny
Which is faster.
How much faster?

I guess what you're asking is, "Is it worth it?", implying that it isn't. [smile]

I'de say you're mostly right, only in critical parts of some code will this little trick be of any use nowadays, if at all. And if we're talking about a static array, using this method can even be slower because we'll need to do an extra memory access to read the shift value instead of using an hardcoded one.

Share this post


Link to post
Share on other sites
tolaris    288
Quote:
Original post by ManaStone
Shouldn’t height maps be saved in powers of 2 +1? If you have a 64x64 height map and you need to find the midpoint for doing LOD stuff, you are not going to be able to find the vertex midpoint since it divides evenly. I’m asking this because I’m trying to build a practical height map editor( I already built a none practical one).

Wouldn't the midpoint be simply centre of quad formed by 4 actual points of the height map "around" it?

("quad" in the loosest sense, obviously...)

Share this post


Link to post
Share on other sites
tolaris    288
Quote:
Original post by ManaStone
Perhaps this will demonstrate what I am talking about.

I understand... what i meant was, 4x4 height map doesn't necessarily mean your geometry made out of it also has to be 4x4 points. Consider the last line in your picture, the one with 5x5 height field -- if you place 4x4 height bitmap over it, you'll see each pixel can 'cleanly' contribute to height of 4 points of the height field 'surrounding' this pixel.

Share this post


Link to post
Share on other sites
ManaStone    148
Quote:
Original post by tolaris
Quote:
Original post by ManaStone
Perhaps this will demonstrate what I am talking about.

I understand... what i meant was, 4x4 height map doesn't necessarily mean your geometry made out of it also has to be 4x4 points. Consider the last line in your picture, the one with 5x5 height field -- if you place 4x4 height bitmap over it, you'll see each pixel can 'cleanly' contribute to height of 4 points of the height field 'surrounding' this pixel.


So you are saying to just round it to either the 2nd or 3rd point to get the value or use the average of the two?

Share this post


Link to post
Share on other sites
tolaris    288
Quote:
Original post by ManaStone
So you are saying to just round it to either the 2nd or 3rd point to get the value or use the average of the two?

Average of the four, kind of like this:

0 1 2 3
+---+---+---+---+
0 | | | | |
+---+---+---+---+
1 | | x | x | |
+---+---*---+---+
2 | | x | x | |
+---+---+---+---+
3 | | | | |
+---+---+---+---+

4x4 pixel height map, 4x4 quads mesh build over it... the middle point (marked *) would be average of height values defined by 4 pixels of the bitmap, the ones marked with 'x'

Share this post


Link to post
Share on other sites
RAZORUNREAL    567
Shifting is a pretty insignificant optimisation. It'd be more important to make sure you always iterate in the x direction not the y, so you make good use of the cache.

Share this post


Link to post
Share on other sites
outRider    852
I've always used 2^n+1 sized heightmaps, for exactly the reason you mentioned, and others. Terragen does it too. Out of curiosity, where did you see 2^n heightmaps?

Share this post


Link to post
Share on other sites
Ilici    862
Quote:
Original post by JohnBolton
Yes, 2n+1 works better than 2n.


I think everybody should learn that and stop posting a thousand threads about having very high or very low ridges on the sides of their terrains.

Share this post


Link to post
Share on other sites
d000hg    1199
I thought most heightmaps used 2^1 +1. But the actual length of the edge of the map is 2^n. This also makes splitting for quadtrees work properly...

Share this post


Link to post
Share on other sites
ManaStone    148
Quote:
Original post by outRider
I've always used 2^n+1 sized heightmaps, for exactly the reason you mentioned, and others. Terragen does it too. Out of curiosity, where did you see 2^n heightmaps?


Scapex used 2^n so I thought it was standard.

Share this post


Link to post
Share on other sites
matches81    474
I´ve only done one fractal algorithm for terrain yet, but for the one I´ve done (Diamond-Square-Algorithm) you actually NEED 2^n + 1 sized fields, otherwise it wouldn´t work. IIRC Terragen also uses fractals to generate the terrain, so this could be a reason, why it uses 2^n + 1 as heightmap sizes. The reason why you need 2^n + 1 is the same as for quadtree and so on, to divide it properly without having to do some ugly tricks.

Share this post


Link to post
Share on other sites
subi    157
what heightmap size you use is usually dictated to you by what terrain algo you are using ...for e.g Geometrical mipmapping requires the use of 2n+1 size heightmaps,so each patch/block you make(also 2n+1) will always be a perfect quad.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Some thoughts from experience:

Consider a triangle list terrain patch quadtree that has sides of 2^n + 1 everywhere.

That very last row and column of any given patch typically are duplications of the first row and column of neighboring terrain patches. In reality the dataset isnt divided into 2^n + 1 blocks at all, but rather 2^n blocks with 1 row and column of redundancy.

Subdividing a patch into smaller patches (ok, lets face it.. its precalculated) under 2^n+1 always yields another 2^n+1 sized patch, complete with that 1 row and column of redundancy.

This line of reasoning ends up with using 2^n+1 not because its 'right' but because its 'simple' - you dont need to access neighbors because you've got the relevent neighbor data duplicated all over the place.

Now, in the case of using a heightfield.. you no longer need that sort of simplification. 'Neighbor Patch' is meaningless in a heighfield. Whats more important is being able to handle arbitrarily sized pieces of the terrain so that you can drive your LOD system with optimal sizes rather than fixed sizes.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this