Height maps on server

[Auntie Mangos]

Unfortunately, this isn't very easy to explain with plaintext only...

v9 and v8 store only the z value (in wow and mangos, z is height). It is the same in the client (but for rendering they compute xy values and tessellate)

• In the server, the triangle vertices' xy values aren't needed to calculate height - as seen in GridMap::getHeightFromFloat(float,float), the player position and triangle position are translated to {0,0}, and the calculation is done on a unit square (the player position is adjusted to be relative to the corners of a 1x1 square).
  
• If you care to render the terrain, you should probably look at the TerrainBuilder class from mmaps redux, in contrib/mmap/src/. (shameless plug )
  

As I said above, the server has the same data that the client has. Each vertex is only 2 'yards' away from another vertex, which ends up being fairly smooth in appearance. It's not super high resolution, but you don't 'snap' to a terrain mesh vertex when you want height - you calculate the z value of the position on the surface of a triangle.

I should mention that the terrain height calculation isn't ray intersection - there is no mystery about which triangle will be hit, so we don't need to trace a ray through polygon soup.

Ray intersection comes in the form of the vmap, which stores data for buildings, rocks, trees, fences, platforms, boats, and other static doodads. While the terrain may be viewed as 2.5d (it is 3d, but it never overlaps itself so it is easier to represent and handle), objects in the vmap are fully 3d (they can be round, get stacked on top of other objects, intersect other objects, etc). A ray can intersect multiple triangles, and with a naive implementation we have to test all triangles to find which ones.

The BIH (Bounding Interval Hierarchy) is a tree for space-partitioning 3d scenes - their purpose is to let us do as few intersection tests as possible. The nodes in the BIH are essentially bounding boxes for all models in child nodes - if your ray doesn't collide with a node's bounding box, you can prune all of the geometry under that node from the search space. [if any of this is wrong, I apologize - from descriptions, BIH and BVH sound exactly alike. Maybe Lynx3d can help ]

[Auntie Mangos]

Unfortunately, this isn't very easy to explain with plaintext only...

v9 and v8 store only the z value (in wow and mangos, z is height). It is the same in the client (but for rendering they compute xy values and tessellate)

• In the server, the triangle vertices' xy values aren't needed to calculate height - as seen in GridMap::getHeightFromFloat(float,float), the player position and triangle position are translated to {0,0}, and the calculation is done on a unit square (the player position is adjusted to be relative to the corners of a 1x1 square).
  
• If you care to render the terrain, you should probably look at the TerrainBuilder class from mmaps redux, in contrib/mmap/src/. (shameless plug )
  

As I said above, the server has the same data that the client has. Each vertex is only 2 'yards' away from another vertex, which ends up being fairly smooth in appearance. It's not super high resolution, but you don't 'snap' to a terrain mesh vertex when you want height - you calculate the z value of the position on the surface of a triangle.

I should mention that the terrain height calculation isn't ray intersection - there is no mystery about which triangle will be hit, so we don't need to trace a ray through polygon soup.

Great info.. I'm still kind of confused though just due to my lack of experience here..

What is the difference between v9 and v8? (other than the obvious that I can see from the initialization.. which is that they're back to back 128*128 and 129*129 in the map file) I'm not sure what they represent, other than 'triangles' in general.. how exactly? and how does it become '2 yard' resolution? (based on what yard dimensions of the map tile, 533.3333~?)

I understand that once the v9/v8 are triangles, the layout of the data already IS the x,y values on the map tile.. I'm not sure why translating to 0,0 helps though?

As for rendering the terrain in the client, I just have the entire terrain model, load it into a mesh structure in directx and render it.. is that bad?

But yes, I am snapping the character to the height value using intersection.. as you say, that sucks. But you said you already know which triangle of the terrain it will intersect with, how so? I understand from the data layout you already somehow have the x,y range that the triangles cover (though if you could answer what exactly the v9/v8 represent that would clarify it) but that resolution of 2 yards isn't enough to render the character models exactly at the right height based on the higher resolution terrain of the model?

also, @Lynx3d thanks for that info... kd-tree, terms i don't know =)

If either of you guys also would recommend any books or online sources for dealing with this sort of thing, I'd be very interested.. my way of going about things is making stuff very slow

[relaxok]

Hi there -- I've been making an mmo client/server similar to wow and I've looked at some of mangos for some insight.

However, I can't really tell how height is dealt with on the server side..

Obviously on the server side, the server must know terrain geometry/height in order to move mobs around, know distance between objects, etc...

Can someone explain how this works in the server or where I can look?

Where are the heightmaps generated from and how big are they? Are they about 4096x4096*32bit floats? That is 67 megs per tile and seems unlikely.. is it at a smaller resolution and then interpolated?

I do client side height by simple ray intersection with the terrain at the given X Z value, but that's sort of expensive and im sure the server doesn't actually load in all the vertices of the tile and do that much math!

I'm very curious how this works.. thanks..

-relaxx

[faramir118]

For terrain height, look at GridMap::getHeightFromFloat(float,float), it should give you a lot of information on the height calculation itself.

The vmap uses ray intersection (the BIH speeds things up by limiting which models are tested)

[zergtmn]

Where are the heightmaps generated from and how big are they?

Artists make them. You can use Difference Clouds filter in Photoshop to generate a heighmap and then export it as single channel raw grayscale image. It is the simplest format to work with. To calculate vertex height at any point of terrain you'll need to find interpolated height from heightmap (for example, using bilinear interpolation) in 0.0..1.0 range and multiply it by maximum height of terrain.

[darkstalker]

you can use the fractal plasma algorithm to generate terrains

[relaxok]

For terrain height, look at GridMap::getHeightFromFloat(float,float), it should give you a lot of information on the height calculation itself.

The vmap uses ray intersection (the BIH speeds things up by limiting which models are tested)

Thanks, this is very interesting code.. what is BIH though?

[relaxok]

Where are the heightmaps generated from and how big are they?

Artists make them. You can use Difference Clouds filter in Photoshop to generate a heighmap and then export it as single channel raw grayscale image. It is the simplest format to work with. To calculate vertex height at any point of terrain you'll need to find interpolated height from heightmap (for example, using bilinear interpolation) in 0.0..1.0 range and multiply it by maximum height of terrain.

Hm, I'm asking specifically about what mangos uses - it looks like there are two grids of 129 x 129 and 128 x 128 - what do the floats in m_V9 and m_V8 represent? They describe a triangle list somehow? (According to comments) - how are these made from the terrain model data? (adt)

But, how is 128 x 128 high enough resolution to get accurate terrain heights on a map tile that big?

Previous poster mentioned that it ALSO uses ray intersection (not just a height map check)- does that mean the server has all the terrain vertices loaded as well?

Or does the client do the last bit of 'snapping' to terrain and the distance between objects on the server side can be significantly wrong because of the lack of resolution of the height map?

[Lynx3d]

Bounding interval hierarchy is sortof a hybrid between kd-tree ("axis aligned binary space partitioning tree") and bounding volume hierarchy.

It doesn't define full 3d-volumes per node, it just forms the child bounds by limiting the node bound in one axis, but unlike a kd-tree, you don't have a strict left/right border but two delimiters that define two volumes that can overlap, or leave a gap.

Our implementation also supports a special node case that only define one smaller child bound by cutting off empty space left and right on its defined axis.

Advantage is that you get more deterministic memory requirements (and easier on-demand loading) and less (time-) complex construction algorithms compared to kd-trees, donwside is that it can perform worse when very large objects exist among many small ones.

Note that the kd-tree derived from G3D that was used in the previous vmap implementation didn't "split" primitives and strictly store them in leaf nodes, but store them in interior nodes, which gives it similar problems as BIH, together with inferior empty space cut-off, resulting in pretty much guaranteed inferior performance to either "common" versions

Plus, the memory layout was horrible...it was made to allow dynamic adding of objects, but the price was quite extreme.

[Lynx3d]

"V8" and "V9" come from the internal file layout of WoW, more information here:

http://www.madx.dk/wowdev/wiki/index.php?title=ADT/v18#MCVT_sub-chunk

It's basically two interleaved regular grids (you could actually also see it as one 45° rotated grid), so the x and y coordinates are implicitly defined, only the z needs to be stored.

As mentioned, this is often called a heightfield, however it does get tesselated to actual triangles in client for rendering. But since you can always compute in which "V9" grid square you are, you don't have to do any raytracing to determine the height, just lookup the surrounding height values, determine which of the 4 inner triangles you are on, and calculate the height on the triangle by simple linear math.

All caves and building however are "real" geometry that require raytracing.

[relaxok]

Wow it's been 6 months and I just now looked up this thread again.. didn't have time to look at stuff much due to work duties =)

I actually borrowed a few functions from GridMap code to try loading heightmaps in my own code (don't worry, nobody will ever see it but me =p)

I went through the code and other than not understanding the math, I totally get it indeed now.. great stuff..

I was banging my head against a wall for awhile trying to figure out why the return values were so messed up... and then realized.. i'm exporting terrain models from 4.2.2 with machinimastudio, but the maps are from 3.x! Cataclysm has wrought changes on the height maps as well Around echo isles was totally messed up.. so well, i knew Mulgore hasn't changed too much, so I used kalimdor 32_35 -- it's mostly correct but still seems weird so apparently it's changed a little bit as well..

i wonder, if it's possible to create .map files from the current client? the available ad.exe is of course for running with the supported 3.x client...

or else i'd need a way to export terrain from the 3.x client... seems the extractor would be easier to find a version of though..?

sorry if this is a bit off-topic.. you guys are just the most knowledgable in the world in this area outside Blizzard