# Why are height maps saved in power of 2 dimensions?

## Recommended Posts

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 on other sites
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 on other sites
Ok, so the last row and column don't really do anything?

edit: ok, nevermind this statement, I'm thinking of power of 2-1.

Which is faster.

How much faster?

##### Share on other sites
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 on other sites
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 on other sites
Quote:
 Original post by FrunyWhich 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 on other sites
Quote:
 Original post by ManaStoneShouldn’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 on other sites
Perhaps this will demonstrate what I am talking about.

##### Share on other sites
Quote:
 Original post by ManaStonePerhaps 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 on other sites
Quote:
Original post by tolaris
Quote:
 Original post by ManaStonePerhaps 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 on other sites
Quote:
 Original post by ManaStoneSo 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 on other sites
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 on other sites
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 on other sites
Yes, 2n+1 works better than 2n.

##### Share on other sites
Quote:
 Original post by JohnBoltonYes, 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 on other sites
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 on other sites
Quote:
 Original post by outRiderI'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 on other sites
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 on other sites
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 on other sites
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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628281
• Total Posts
2981800

• 10
• 11
• 17
• 14
• 9