Building the NavMesh out of .adt's

[berserk85]

You can use water tris to remove all terrain covered by water (or magma) ...

Foreach water_tris calc the 2D BV(bounding volume), if it overlaps with a tris and if its Y is < of water Y than check the tris with a flag ...

btw I love Mikko's work ^^ and i'm impatient to see jump ^^

[Bananenbrot]

Okay, by now I have hopefully done the adapting stuff...
I didn't know what to use to treat the uint8 buffers like an istream.
I researched a little and tried my luck with an istringstream, hopefully that works for binary reading^^
berserk used mpqfilebuf... My question is how did you arrange that? Did you inherit from streambuf? If so, plz give me a clue of your implementation (unless mine does work) because I realize my big lack of knowledge regarding C++ STL/Syntax.

My next step would be to write an editor for showing the parsed vertices, similar to that provided by XNA. While looking in RecastDemo's source code, I figured out that SDL was used, but the purpose and usage isn't that clear to me. Are there (more or less easy) solutions for 3D projection (don't know another word for that^^) in C++ to write world editors and stuff like that?
For later use: How is it realised that I may through a click message determine the underlying Triangle/Vertex?

Thank you very much so far, you are bringing my project forward rapidly

[pendra]

You can't do it with the recast implementation as is, but it would be pretty easy to add. Just add some 'type' flags that you insert with your triangles and then carry them through the process.

For anyone thinking "Hey what about marking paths/roads using the textures!", I've given it a lot of investigation, and here's how I think it has to be done. It's a little more complicated than one would hope because many of the roads in the game use a generic 'Rock' or 'Dirt' texture that is also used all over the place with different alpha mixes, so it's hard to tell the difference between say a road and a barren piece of prairie.

The roads also do not follow the triangular face boundaries if you stripify the ADT height field, so you'd have a really nasty looking mesh if you tried to do it based on a triangulation of the ADT height field.

Note I haven't actually done this yet, but here's how I think I'd do it:

Rather than triangulate the ADT and then rasterize it back into a height field, just interpolate the height field samples and insert spans directly. This way you don't have to have the same 'type' for each entire triangle.

For each span, figure out which textures are applied in that location using the texture info in the MCNK, and hash them into a key using some kind of algorithm that will tag "close enough" alpha mixes with the same key. The sum of the characters of the texture name for all textures with alpha >= K would probably work.

Then, when you perform regionization of your height field, try not to merge spans together that have different texture keys. This should result in regions where all the spans in the region have the same texture, so your road-to-not-road boundaries should be on region boundaries.

The last step is to figure out which texture keys represent roads. It might be possible to just hard code this, but I doubt it. An alternative might be to manually set a bunch of <x,y,z> points in world space that you know are on roads, map them onto the regions, and then flood fill a 'road' flag from there once you know the appropriate texture key.

I'm not sure it's worth all that effort at the end of the day...

[Apoc]

You can't do it with the recast implementation as is, but it would be pretty easy to add. Just add some 'type' flags that you insert with your triangles and then carry them through the process.

For anyone thinking "Hey what about marking paths/roads using the textures!", I've given it a lot of investigation, and here's how I think it has to be done. It's a little more complicated than one would hope because many of the roads in the game use a generic 'Rock' or 'Dirt' texture that is also used all over the place with different alpha mixes, so it's hard to tell the difference between say a road and a barren piece of prairie.

The roads also do not follow the triangular face boundaries if you stripify the ADT height field, so you'd have a really nasty looking mesh if you tried to do it based on a triangulation of the ADT height field.

Note I haven't actually done this yet, but here's how I think I'd do it:

Rather than triangulate the ADT and then rasterize it back into a height field, just interpolate the height field samples and insert spans directly. This way you don't have to have the same 'type' for each entire triangle.

For each span, figure out which textures are applied in that location using the texture info in the MCNK, and hash them into a key using some kind of algorithm that will tag "close enough" alpha mixes with the same key. The sum of the characters of the texture name for all textures with alpha >= K would probably work.

Then, when you perform regionization of your height field, try not to merge spans together that have different texture keys. This should result in regions where all the spans in the region have the same texture, so your road-to-not-road boundaries should be on region boundaries.

The last step is to figure out which texture keys represent roads. It might be possible to just hard code this, but I doubt it. An alternative might be to manually set a bunch of <x,y,z> points in world space that you know are on roads, map them onto the regions, and then flood fill a 'road' flag from there once you know the appropriate texture key.

I'm not sure it's worth all that effort at the end of the day...

It'd be easier to just add vertex flags. If you know a vert has a 'road' on it, simply set the flag |= FLAG_ROAD. Then simply handle that when building your mesh up. You can also use the flags for water, lava, etc.

Figuring out what 'roads' are is fairly simple, since the same textures are used throughout, just alpha blended. Only hard part would be finding the road/path texture names. Other than that; it's just some math to figure out which verts are roads. Not too hard. Just the actual implementation during meshing would be a bitch.

[Bananenbrot]

So a little update today...

I got the C++ code working. It reads out the registry for the wow directory and pulls the data directly out of the .mpq's. berserk85's source gave me a good start for building my 'TerrainBuilder' class (very impressive name) around it. In my attached example code, I extracted the adt's from sw harbor to the eastern end of elwynn into a vertexbuffer and used the DXUT CFirstPersonCamera helper class for navigating through it. I had to introduce myself into DirectX programming and was away 1 week, that's why it took so long. I realized that either C++ must be performing these kind of file operations a lot better than OO C# (casting ftw) or my C# code was shit inefficient and slow, because now the extract operation is done much faster than before, although it now covers more data, more adt's and pulls the data directly out of the .mpq's. Even the Navigating through sw, which formerly had to be done at 2 fps, now is stable and fast, what I only could explain with that I choose hardware vertex processing in Navigator.exe rather than mixed or software processing which was maybe active in the C# app...

enough said, here are my questions, as I'm not yet satisfied with my result:

1. See the water around the isle with these stone circle (usually crowded with defias). There you may see 2 green vertices, which I absolutely don't know of why they are there. I used the RenderMap in MH2O to determine what to render, applied all other rules mentioned on WoWDev, but it seems, that the RenderMap is given there with explitcitly sparing out the 2 green vertices. I played around with rotating the RenderMap via switching x and y (and stuff like 7-x, hope you know what I mean^^), but find out that the current state is 'optimal'.



2. Model rotation -.- I don't know if it's the order of applying the matrices (I played around with it a lot), but some m2's need the order Z,Y,X with +rotB+180(Z), +rotC(Y), +rotA(X) and some fences need the order mentioned at WoWDev (+rotB+180(Z), +rotC(X), +rotA(Y). I use a Z-Up coordinate system, with the coordinates given like in processmemory.

Fences in front of SW (order: ZYX, ZXY, Noggit):


Boat wreck in front of redridge inn (same order as above):


Note that both matrices don't rotate the boats correct in general, they are always 180° around Z missrotated.

3. Model rotation 2nd -.--.- The doodads of sw are rotated via a quaternion... I had to play around a lot to get it at least conveying the right rotation^^ I had problems with these little boats under the bridge in front of the king's hall (<-insert right expression). Currently I'm getting the quat as follows:

                D3DXMATRIX matWorld;

                D3DXQUATERNION qRot = D3DXQUATERNION
                    (
                        rootWmo->modd[listIdx].rot[2], 
                        rootWmo->modd[listIdx].rot[3],
                        -rootWmo->modd[listIdx].rot[1],
                        rootWmo->modd[listIdx].rot[0]
                    );

                D3DXVECTOR3 vTemp;
                FLOAT fAngle;
                D3DXQuaternionToAxisAngle(&qRot, &vTemp, &fAngle);
                vTemp.y = -vTemp.y;
                D3DXQuaternionRotationAxis(&qRot, &vTemp, fAngle);

                D3DXVECTOR3 vPos = D3DXVECTOR3
                    (
                        rootWmo->modd[listIdx].pos[0],
                        rootWmo->modd[listIdx].pos[1],
                        rootWmo->modd[listIdx].pos[2]
                    );

                D3DXMatrixAffineTransformation(&matWorld, rootWmo->modd[listIdx].scale, NULL, &qRot, &vPos);

                D3DXMatrixMultiply(&matWorld, &matWorld, matWmoWorld);

I get the rotation axis and the angle to some kind of invert it... played around with it and it works, after that step, I have to negate x and z of the outcoming position vector:

                    WOWCUSTOMVERTEX finalVertex;
                    D3DXVECTOR3 vUntransformed(-vertices[v].x, vertices[v].y, -vertices[v].z);
                    D3DXVec3TransformCoord(&finalVertex.pos, &vUntransformed, &matWorld);

Again, don't really know why, but it works except for boats...

To the left mine, noggit's at the right:


4. As my last step, I read out the MLIQ's of the WmoGroups to represent sw's water in my visualization. The code works besides that the whole liq mesh seems to be moved in y or x-Axis direction and these water patches you might see at a canal's end have to be plugged at the endings of the water mesh (<3 my explanation, pic's follow).

The end of the canal between trade district and oldtown:


5. I'm now concatenating the models to adt bounds... but I currently have no clue how to efficiently project the needed outer vertices (if only 1/2 vertices of a triangle are out of bounds) on the (x/z) / (y/z) planes... It gets more complicated if I have to project them in the region of a corner. I may implement some kind of algorithm for it, but I think a test like that is an allday situation in 3D graphics and must be documented anywhere... I really don't know much about ray casting, but it seems to go in that direction.

finally, here are the bin's:
Navigator.exe

PM me if you need sources. If they are needed for debugging, I may consider to attach them. I'm a bit shy because of my ugly (but relatively functionable) code ^^

[berserk85]

Great work ^^
M2 are rotated with quaternion only in wmo meshes ...
I have z for height.

For rotation in adt i use

for (int i = 0; i < adt.mddf.GetSize(); i++)
	{
		/* Get the M2 file name */
		std::string m2_filepath = adt.mmdx.GetOffset(adt.mmid[adt.mddf[i].nameId]);

		if (m2_filepath.find(".mdx") != std::string::npos)
			FindAndReplace(m2_filepath, ".mdx", ".m2");
		else if (m2_filepath.find(".MDX") != std::string::npos)
			FindAndReplace(m2_filepath, ".MDX", ".m2");
		else if (m2_filepath.find(".MDL") != std::string::npos)
			FindAndReplace(m2_filepath, ".MDL", ".m2");

		/* Set Translation, Rotation and scale */
		Vertex translation;

		translation.x = (17066.666666666656f - adt.mddf[i].pos[2]);
		translation.y = adt.mddf[i].pos[1];
		translation.z = -(17066.666666666656f - adt.mddf[i].pos[0]);


		RotationMatrixf rotation_matrix;
//THIS !
		rotation_matrix = rotation_matrix.FromEulerAnglesXZY((-adt.mddf[i].rot[2])*rad,(adt.mddf[i].rot[0]) * rad,(-adt.mddf[i].rot[1] + 180) * rad);
		ScaleValue scale;
		scale.n = 1024.0f / (adt.mddf[i].scale);
		METransformStrategyPtr m2_transformation = MatrixTrans::Create(
				rotation_matrix, translation, scale);

		/* add this M2 */
		MapLodObject* m2_map_object = MapLodObject::Create(m2_filepath,
				mMapResource["M2Resource"], m2_transformation,
				adt.mddf[i].uniqueId);

		/* Add element to Doodas_set */
		ret_map_node->AddMapElement(m2_map_object);
	}

and in wmo :

	for (int j = wmo_root.mods[doodadSetIndex].firstinstanceindex; j < wmo_root.mods[doodadSetIndex].firstinstanceindex + wmo_root.mods[doodadSetIndex].numDoodads; j++)
	{
		/* Get the file name */
		std::string m2_filepath = wmo_root.modn.GetOffset(wmo_root.modd[j].nameOffs);
		if (m2_filepath.find(".mdx") != std::string::npos)
			FindAndReplace(m2_filepath, ".mdx", ".m2");
		else if (m2_filepath.find(".MDX") != std::string::npos)
			FindAndReplace(m2_filepath, ".MDX", ".m2");
		else if (m2_filepath.find(".MDL") != std::string::npos)
			FindAndReplace(m2_filepath, ".MDL", ".m2");

/* TODO : Binary search
		if(!GetMpqConteining(m2_filepath.c_str()))
			throw std::runtime_error("WowMapTileBuilder::BuildAdt() : Can't find \"" + m2_filepath + "\".");
*/
		/* Set Translation, Rotation and scale */
		Vertex traslation;
		traslation.x =  wmo_root.modd[j].pos[0];
		traslation.y = wmo_root.modd[j].pos[2];
		traslation.z = -wmo_root.modd[j].pos[1];
//THIS !
		Quaternionf rotation_quaternion = Quaternionf(wmo_root.modd[j].rot[3],wmo_root.modd[j].rot[0], wmo_root.modd[j].rot[2], -wmo_root.modd[j].rot[1]);
		ScaleValue scale;
		scale.n = 1.0f / wmo_root.modd[j].scale;
		METransformStrategyPtr m2_transformation = QuaternionTrans::Create(rotation_quaternion,traslation,scale);
		/* Create the M2 Element */
		MapLodObject* ob = MapLodObject::Create(m2_filepath,mMapResource["M2Resource"],m2_transformation);
		/* add this element to the doodads set*/
		doodads_set->AddMapElement(ob);
	}

where QuaternionTrans and MatrixTrans are only a function that applies the transformation

Hope this can help

PS: Bounding mesh is different from view mesh ... in boat I think that there is a mismatch of bounding box and mesh

[Bananenbrot]

Thanks for your reply, it was the order of rotations applied to the models Now the boat in front of redridge inn are rotated right as well as the fences.
I think I have to port my app to Y-up for Recast, but at first I want to get this model concatenation at adt borders working... I would go some kind of a brute force method if there isn't a more elegant way than clustering my source with if's and bounds tests.
I must admit that I did not fully understand how in detail the components of a quaternion affect the rotation, but except for those boats they seem to work properly.
What I did not use at all where the doodad sets. I got all sub-doodads for the wmo's while reading modd and did not have any need for using those sets. What purpose do they serve?

[berserk85]

Doodads in WoW are M2 model files. There are 32 bytes per doodad set, and nSets entries. Doodad sets specify several versions of "interior decoration" for a WMO. Like, a small house might have tables and a bed laid out neatly in one set called "Set_$DefaultGlobal", and have a horrible mess of abandoned broken things in another set called "Set_Abandoned01". The names are only informative.

from WMO - WoW.Dev Wiki

[Bananenbrot]

... The are only informative.

I hope that's true, because I really don't get the sense of ordering them in a set for my purpose^^

Ok, so far I could fix the matrix rotation bug with your help, thanks... unfortunately there are still 3 other sort of bug things.
I recognized that the 5th problem isn't really a problem, because I may delete the overlapping nav mesh tiles. I'm planning to have a tiled mesh with each tile in MCNK size.

So far, only the RenderMap seems to be incorrect, the water of Stormwind is still patched and the boats and their ropes are missrotated, probably due to my quat rotation, which despite of that seems to be right... here's my new version:
Navigator.exe

It would be interesting to know how the developers of noggit and the other mapeditors solved that.

I think now I should go further and getting Recast work.

[pendra]

As for clipping polygons to ADT bounds, just let recast do it if you're going to use recast. Set your height field bounds to be the ADT and then rasterize all the triangles which intersect the ADT. Recast will only rasterize the portions of the triangles that are within height field bounds. rcRasterizeTriangles is reasonably efficient and it has to do the checks whether or not you clip them yourself ahead of time.

Using MCNK size tiles rather than ADT size tiles would probably be a good idea for recast, since that's the smallest size where you can get reasonably compact m2/wmo lists.

[namreeb]

As for clipping polygons to ADT bounds, just let recast do it if you're going to use recast. Set your height field bounds to be the ADT and then rasterize all the triangles which intersect the ADT. Recast will only rasterize the portions of the triangles that are within height field bounds. rcRasterizeTriangles is reasonably efficient and it has to do the checks whether or not you clip them yourself ahead of time.

Using MCNK size tiles rather than ADT size tiles would probably be a good idea for recast, since that's the smallest size where you can get reasonably compact m2/wmo lists.

That will not be enough. I believe that it will throw out whole triangles that fall outside of the bounding box you give it, but you need to do more than that. What about the triangles that land on the border, with some vertices inside and some outside? You'll have to throw out the external vertices and add new ones along the same directional vector only that stop when they touch the border, and recreate the offending triangle.

[pendra]

That will not be enough. I believe that it will throw out whole triangles that fall outside of the bounding box you give it, but you need to do more than that. What about the triangles that land on the border, with some vertices inside and some outside? You'll have to throw out the external vertices and add new ones along the same directional vector only that stop when they touch the border, and recreate the offending triangle.

It throws out triangles if they are entirely outside the bounding box. if the bounding box of the height field overlaps the bounding box of the triangle, it finds the height field rows/columns that overlaps and inserts the proper spans. It works just fine. Just have a look at the code for rcRasterizeTriangles.

[Bananenbrot]

If I choose MCNK sized tiles, I would only save the tiles I want to have (those within adt bounds / 16 * 16 field) and ignore the data generated for ovelapping tiles.
That shouldn't be a problem I think, even if I tell recast to generate a heightfield for the overlapping triangles too. At least I hope so^^

EDIT: btw., pendra and namreeb, you seem to have an almost working navmesh implementation. Did you face the same problems?

[namreeb]

Probably I'm not clear on what you're saying. Are you trying to generate these tiles in-game on demand?

[pendra]

If I choose MCNK sized tiles, I would only save the tiles I want to have (those within adt bounds / 16 * 16 field) and ignore the data generated for ovelapping tiles.
That shouldn't be a problem I think, even if I tell recast to generate a heightfield for the overlapping triangles too. At least I hope so^^

EDIT: btw., pendra and namreeb, you seem to have an almost working navmesh implementation. Did you face the same problems?

I'm not quite sure what you're getting it, but here is what I would suggest:

Create a recast height field for each ADT MCNK. Insert into this height field:

-- The terrain triangles for the MCNK in question
-- The 4.16 meter strip of triangles from all the adjacent MCNKs, so you have some border for distance calculation
-- All M2s and WMOs which might intersect the height field, which would be the set referenced in any of the3x3 grid of MCNKs. For efficiency, do a bounds check of the whole WMO/M2 against your height field bounding volume and only insert the triangles on intersection. Make sure you never insert the same M2/WMO twice by using the unique ids.


The bounds on the height field would be 41.6x41.6 meters, since the MCNK is 33.333 x 33.333 and you're adding a 4.16 meter border all around.

In my case I did my own implementation so I don't insert triangles for terrain at all, I just interpolate the ADT height field data directly into the nav spanfield and insert triangles only for m2/wmo. The result should be the same, but interpolation is way faster than rasterization.

I did have some minor problems getting the MPQ parsing right, but the data on wow.dev is mostly accurate.