Why are height maps saved in power of 2 dimensions?

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<
Which is faster.

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?

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?

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.

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.

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...)

Perhaps this will demonstrate what I am talking about.

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.

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?

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'

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.

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?

Yes, 2ⁿ+1 works better than 2ⁿ.

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.

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...

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.

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.

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.