how to transform the navmesh produced by unity3D to the navmesh used in recastnavigation

[dzhu...@gmail.com]

Hi,everyone

Now I have the navmesh triangles produced by unity3D, and I want to use the navmesh in recastnavigation, what shoud I do?

I know I can use the triangles as polygon, but the efficient is to low in recast ,How can I merge triangles into big polygon? 

[Mark Woo]

there has a plugin for unity, please google "CritterAI"

[Christmas Eve]

Hi everyone,

Do you have any other solutions besides CritterAI?  CritterAI has not been updated for over 3 years.  I did find a link to a page that I had to translate from Chinese that claimed to have been updated 3 months ago but it didn't work either.  Every version of CritterAI I've tried cannot find its DLLs in Unity (e.g. cai-nmgen.dll).

Prior to discovering CAI, I had tried using NavMesh.CalculateTriangulation() in Unity to get all the vertices, indices and layers.  I tried to create a single tile in Detour and pathfind against it.  I encountered three different issues... (1) findStraightPath took me directly to the destination, ignoring all obstacles, (2) segmentation faults occurred, mainly due to Detour not using getTileAndPolyByRefUnsafe instead of getTileAndPolyByRef.  Would unsafe ever really try to return invalid polygons unless it was bad data?  (3) I've had it take me to a destination somewhere on the other side of the map!

A side issue is that, if you do use one "tile" for all of my navmesh geometry, Detour only supports 65535 verts per tile so that would be 65535 verts total.  I tried converting all references to unsigned int's but I still encountered one of the three issues described above.

Basically, I've spent countless hours trying to find a speedy pathfinding solution to my navigation meshes produced in Unity and I'm still back at the drawing board, looking for a solution.

Does anyone have any suggestions?  Any code?  Any utilities?  I need my non-unity-based server to be able to pathfind on its own, without the UnityEngine.  Recast/Detour seemed like the most logical choice.  

By the way, I have tried to use Recast to take my level geometry and generate a navmesh instead of me trying to feed my own navmesh into Detour and I encountered many segmentation faults which I did not try to debug.  I'm almost out of energy now.  Please help!

[Christmas Eve]

I didn't see a way to edit my post.  I wanted to make a correction: I didn't mean to say that Detour *DOES* use getTileAndPolyByRefUnsafe a lot and winds up with invalid polygons.  I'm seriously stuck between a rock and hard place.  All avenues have been blocked unless I write my own pathfinding algorithm (which I've done but it was 50x slower!! lol)

[Mikko Mononen]

A quick googling around surfaced a couple of more up to date ports:

https://github.com/Robmaister/SharpNav

https://github.com/jlalleve/rcdtcs

Maybe they work for you?

If not, or you want to use polys from Unity, could you share the code where you transform the unity data to detour. Maybe there's some obvious mistakes there. Based on what you wrote, the data is busted somehow.

--mikko

 

--

---
You received this message because you are subscribed to the Google Groups "recastnavigation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to recastnavigati...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Christmas Eve]

Hey Mikko!  Sorry for the late reply.  I'm actually still struggling with this.  I had looked into giving Recast all of the verts/inds from a Unity scene but decided I was better off where I began, and that is to give Detour NavMesh data from Unity's baking process.  I just checked the links you gave me (thanks!) and SharpNav looks like something that could be interesting.  From reading the readme, it looks like it is a C# port of your Recast/Detour system.  If it isn't able to directly accept a Unity navmesh then I'd probably stick with your C++ solution.  I'll continue checking it out.

So, I wrote some code to read in a binary file that I wrote from C# in unity.  In Unity, I use NavMesh.CalculateTriangulation() and then write the sizes of the verts, polys, and areas, followed by a binary representation of the arrays themselves.

My C++ code that attempts to build a dtNavMesh from this data is very messy, I must warn you.  I've been deleting lines, inserting lines and trying different things and have put 0 effort into cleanup so far.  I've just been trying to get something to work.   Originally, I tried to load the entire thing into a single tile but because of the ushort limit on verts/polys, I attempted a multi-tiled approach (below).  You'll see a magic (hard-coded) number 102.400004 below.  After analysis of the test level I'm using, I found that the tile boundaries seem to be every 102.400004 world units.  I'd rather autodetect this value as an enhancement in the future.  So, with this number in mind, I iterate over each tile in the XZ plane and I reconstruct a set of verts and polys (triangles) from the global verts/polys, keeping only those that fall in the XZ range for the tile. You'll notice that I have a single back reference to the global vertex array when mapping tile polygon indices.  This is because I actually discovered a 1-to-1 relationship between verts and inds in Unity's exported NavMesh data.  Currently, the navmesh seems to build but navigation fails.  I think there is more to it than I think because I had a random crash (segmentation fault) once when trying to construct the navmesh.

#define TILEWID 128 //default

#define TILEHGT 128 //default

#define WORLD 0

#define _SCALE 3

#define _HGTSCALE 5

#define MAXVerts 30000 //temporary

#define MAXPolys 10000  //temporary

#define MAXREFS 30000  //temporary

    sprintf(fpath,"unav.%d",WORLD); //Mikko, this is the file that I built in C# with CalculateTriangulation

    sprintf(spath,"navmesh.%d",WORLD);

    printf("Loading level from file %s...\n",fpath);

    long lSize; int numVerts,numInds,numAreas,numPolys; int i;

    uint *arData; float *vertData; uint *polys;

    FILE *fp=fopen(fpath,"rb");

    if(!fp) { printf("ERROR: Couldn't open navmesh file!\n"); return 1; }

    // obtain file size:

    fseek(fp,0,SEEK_END);

    lSize = ftell(fp);

    rewind(fp);

    if(lSize<12) { fclose(fp); printf("ERROR: missing navmesh file header!\n"); return 1; }

    fread(&numVerts,4,1,fp);

    fread(&numInds,4,1,fp); numPolys=numInds/3;

    fread(&numAreas,4,1,fp);

    vertData=(float*)malloc(numVerts*12);

    arData=(uint*)malloc(numAreas*4);

    polys=(uint*)malloc(numInds*4);

    fread(vertData,12,numVerts,fp); //load vertices

    fread(polys,4,numInds,fp); //load indices

    fread(arData,4,numAreas,fp); //load areas

    fclose(fp);

    float highX=0,highY=0,highZ=0;

    for(int i=0;i<numVerts*3;i+=3) {

        if(vertData[i]>highX) highX=vertData[i];

        if(vertData[i+1]>highY) highY=vertData[i+1];

        if(vertData[i+2]>highZ) highZ=vertData[i+2];

//        vertData[i]*=_SCALE; vertData[i+1]*=_HGTSCALE; vertData[i+2]*=_SCALE;

    }

    highX=roundUp(highX,100); highY=roundUp(highY,100); highZ=roundUp(highZ,100);

    printf("Detected world bounds (%f,%f,%f)\n",highX,highY,highZ);

    float tileW=TILEWID,vxW;

    if(WORLD==0) tileW=102.400004; //exact increment for my world 0 exported from Unity

    vxW=tileW*_SCALE;

    int xtiles=(int)ceil(highX/tileW),ytiles=(int)ceil(highZ/tileW);

    

    

    dtNavMesh *mesh=new dtNavMesh();

    dtNavMeshParams parms;

    memset(&parms,0,sizeof(dtNavMeshParams));

    parms.tileWidth=tileW; parms.tileHeight=tileW;

    parms.maxTiles=xtiles*ytiles; parms.maxPolys=65535;

    memset(parms.orig,0,12);

    dtStatus initStat=mesh->init(&parms);

    if(!initStat) {

        printf("dtNavMesh Init failed!\n"); exit(1);

    }

    ushort *vertRef=(ushort*)malloc(numVerts*2);

    for(int yy=0;yy<ytiles;yy++) {

        for(int xx=0;xx<xtiles;xx++) {

            int vptr=0,pptr=0;

            float min[3],max[3];

            min[0]=xx*tileW; min[1]=0; min[2]=yy*tileW;

            max[0]=(xx+1)*tileW; max[1]=highY; max[2]=(yy+1)*tileW;

            ushort tilePolys[MAXPolys];

            float tileVerts[MAXVerts];

            int cnt=0,rcnt=0;

            printf("Tile %d %d\n",xx,yy);

            for(int i=0;i<(numVerts*3);i+=3) {

                if(vertData[i]>highX) highX=vertData[i];

                if(vertData[i+1]>highY) highY=vertData[i+1];

                if(vertData[i+2]>highZ) highZ=vertData[i+2];

                //        vertData[i]*=_SCALE; vertData[i+1]*=_HGTSCALE; vertData[i+2]*=_SCALE;

                vertRef[cnt]=0xffff;

                if(vertData[i]>=min[0]&&vertData[i+2]>=min[2]) {

                    if(vertData[i]<=max[0]&&vertData[i+2]<=max[2]) {

////                        printf("%f %f %f\n",vertData[i],vertData[i+1],vertData[i+2]);

                        tileVerts[vptr++]=vertData[i];

                        tileVerts[vptr++]=vertData[i+1];

                        tileVerts[vptr++]=vertData[i+2];

                        vertRef[cnt]=(ushort)rcnt; //backwards reference from vert array

                        rcnt++;

                    }

                } 

                cnt++;

            }

            int numTileVerts=vptr/3,numTilePolys=0;

            for(int i=0;i<numInds;i++) {

                int newInd = vertRef[polys[i]];

                if(newInd!=0xffff) tilePolys[numTilePolys++]=newInd;

            }

            ushort *doubleInds=(ushort*)malloc(numInds*4);

            for(int i=0;i<numTilePolys;i++) {

                doubleInds[i*6]=tilePolys[i*3];

                doubleInds[i*6+1]=tilePolys[i*3+1];

                doubleInds[i*6+2]=tilePolys[i*3+2];

                doubleInds[i*6+3]=tilePolys[i*3];

                doubleInds[i*6+4]=tilePolys[i*3+1];

                doubleInds[i*6+5]=tilePolys[i*3+2];

            }

            uchar *polyareas=(uchar*)malloc(numTilePolys);

            for(int i=0;i<numTilePolys;i++) polyareas[i]=0; //******************* passable? or FLAGS

            ushort *polyflags=(ushort*)malloc(numTilePolys*2);

            for(int i=0;i<numTilePolys;i++) polyflags[i]=1; //******************* passable? or AREAS

            ushort *iverts=(ushort*)malloc(numTileVerts*6);

            for(i=0;i<numTileVerts;i++) {

                iverts[i*3]=(ushort)(tileVerts[i*3]*_SCALE);

                iverts[i*3+1]=(ushort)(tileVerts[i*3+1]*_HGTSCALE);

                iverts[i*3+2]=(ushort)(tileVerts[i*3+2]*_SCALE);

            }

            

            dtNavMeshCreateParams params;

            memset(&params, 0, sizeof(params));

            params.verts = iverts;// (uint*)vertData;

            params.vertCount = numTileVerts;

            params.polys = doubleInds;// (uint*)(data+headerSize+verts*12);

            params.polyCount = numTilePolys;

            params.polyAreas = (uchar*)polyareas;

            params.polyFlags = (ushort*)polyflags;

            params.nvp = 3;

            params.detailMeshes = 0;

            params.offMeshConAreas = 0;

            params.offMeshConCount = 0;

            params.offMeshConDir = 0;

            params.offMeshConFlags = 0;

            params.offMeshConRad = 0;

            params.offMeshConUserID = 0;

            params.offMeshConVerts = 0;

            

            params.walkableHeight = 1.8;//*_SCALE;

            params.walkableRadius = 0.5;//*_SCALE;

            params.walkableClimb = 1.2;//*_SCALE;

            memcpy(params.bmin,(float*)min,12);

            memcpy(params.bmax,(float*)max,12);

//            params.bmin[0]=0; params.bmin[1]=0; params.bmin[2]=0;

//            params.bmax[0]=10000; params.bmax[1]=600; params.bmax[2]=10000;

            params.cs = 1/(float)_SCALE;

            params.ch = 1/(float)_HGTSCALE;

            params.buildBvTree = true;

            

            unsigned char *data=NULL; int dlen=0;

            if(!dtCreateNavMeshData(&params, &data, &dlen)) printf("dtCreateNavMeshdata failed! skipping...\n");

            else {

                if(!data) dlen=0;

                if(dlen==0) {

                    printf("ERROR:There was no navmesh data for tile! aborting...\n");

                    exit(1);

                }

                ////            printf("--> %d %c %c %c\n",dlen,data[0],data[1],data[2]);

                if(!mesh->addTile(data, dlen, DT_TILE_FREE_DATA, yy*65536+xx, 0)) {

                    printf("addTile failed! aborting...\n"); exit(1);

                }

            }

            free(doubleInds); free(iverts); free(polyareas); free(polyflags);

        }

    }

    free(vertRef);

    int pathCnt,sPathCnt;

    dtPolyRef path[256],straightPathPolys[256];

    float spath[256 * 3];

    float startV[3]={4520.762f,154.73f,5782.241f},endV[3]={4519.002f,158.5f,5793.176f}; //let's get around that fence!! :)

    

    dtQueryFilter *filter=new dtQueryFilter();

    filter->setIncludeFlags(1);

    

    dtNavMeshQuery *nav=new dtNavMeshQuery();

    nav->init(mesh,2048);

    printf("about to navigate...\n");

    

    dtPolyRef m_startRef;

    dtPolyRef m_endRef;

    float m_polyPickExt[3];

    m_polyPickExt[0] = 2;

    m_polyPickExt[1] = 10;

    m_polyPickExt[2] = 2;

    nav->findNearestPoly(startV, m_polyPickExt, filter, &m_startRef, 0);

    if (m_startRef == 0) { printf("ERROR finding polygon near start point\n"); return 1; }

    printf("start ref %u\n",(uint)m_startRef);

    nav->findNearestPoly(endV, m_polyPickExt, filter, &m_endRef, 0);

    if (m_endRef == 0) { printf("ERROR finding polygon near end point\n"); return 1; }

    printf("end ref %u\n",(uint)m_endRef);

    //    exit(1);

    dtStatus stat=nav->findPath(m_startRef,m_endRef,startV,endV,filter,path,&pathCnt,256);

    if(stat) printf("Nav returned path count: %d\n",pathCnt);

    if(pathCnt>0) {

        

        dtStatus sstat=nav->findStraightPath(startV,endV,path,pathCnt,spath,0,straightPathPolys,&sPathCnt,256);

        printf("straight path returned: %d nodes!\n",sPathCnt);

        for(int i=0;i<sPathCnt;i++) {

            printf("Node: (%f,%f,%f)\n",spath[i*3],spath[i*3+1],spath[i*3+2]);

        }

    }

    return 0;

You'll also notice, in this code, that I create an array called doubleinds.  I wanted to ask you about this too.  I'm duplicating each polygon because, there is code in DetourNavMeshBuilder that does stuff like this:

const unsigned short* p = &params->polys[i*2*nvp];

What's the *2 for?  nvp would be 3 because all of my polygons are triangles but it's skipping ahead by SIX instead of THREE to get to the next polygon.  Not understanding what exactly it's doing with this params->polys array could be the whole issue.  Or, this could be part of the issue.

In advance, let me thank you so much for your help Mikko!!

[Christmas Eve]

Actually, I did find one error but now I get segmentations faults after adding a couple hundred tiles or so.  I was missing:

            params.tileX=xx; params.tileY=yy; params.tileLayer=0;

...in my params.

[Christmas Eve]

I figured out that the index list is *not* just a list of short integers pointing to the list of vertices that I gave it for the tile...

struct rcPolyMesh

{

unsigned short* verts; ///< The mesh vertices. [Form: (x, y, z) * #nverts]

unsigned short* polys; ///< Polygon and neighbor data. [Length: #maxpolys * 2 * #nvp]

unsigned short* regs; ///< The region id assigned to each polygon. [Length: #maxpolys]

unsigned short* flags; ///< The user defined flags for each polygon. [Length: #maxpolys]

unsigned char* areas; ///< The area id assigned to each polygon. [Length: #maxpolys]

...

};

I don't know if this is my only problem.  Hopefully it is.  Nevertheless, I cannot figure out how to reconstruct this polygon and neighbor data without going thru the recast process.  Since I already have my navmesh data from Unity and all I have is a list of verts, tris, and areas, how can I do this?

If this or any other obvious problems are visible in my code, please let me know  :) Thank you!

[Mikko Mononen]

The first nvp indices are for vertices and the next nvp indices are indices to neighbours. If the polygon has less than nvp vertices, then the rest must be 0xffff. If an edge does not have neighbout, then it must be 0xffff.

The default nvp is 6, you have to take that into account:

https://github.com/recastnavigation/recastnavigation/blob/master/Detour/Include/DetourNavMesh.h#L61

--mikko

 

--

[Christmas Eve]

Thank you Mikko.  I knew it was something like that.  I saw references to neis and figured it was neighboring polygons.  I still have a problem though.  Unity didn't give me neighbor information in the export and the only thing that comes to mind for me to do it myself would be a very very slow process.  Is there a routine already written in Recast or Detour, or perhaps you might have a function that can scan and rebuild neighbors?  Given a tile with polys in it (in my case only triangles) I need to find all triangles in the same array of tile polys that, I guess, have two of the same vertices.. now what makes this even more complicated is I think the data Unity spit out did not re-use vertices.  Unless my scan didn't work correctly, I think that's the case.  Will this screw things up?  Any suggestions or code would be greatly appreciated.  I think this could be the last step to pathfinding on a NavMesh built with Unity.

Oh, one more thing, when you say "indices to neighbors" are stored in the second half of each nvp*2 group, do you mean that they're indices into the same poly array, pointing to 1 or more neighbors?

So, a triangle could be: (nvp=3)

423, 425, 424,

18, 19, 0xffff

...And this would mean that vertex 423, 425 and 424 form this triangle and it has two neighbors whose indices are 18 and 19 and these are indexes used in THIS SAME tile polys array?

[Mikko Mononen]

Maybe the duplicate vertices are the vertices along the tile border?

Here's how Recast calculates the neighbours:
https://github.com/recastnavigation/recastnavigation/blob/master/Recast/Source/RecastMesh.cpp#L34

Yes, your example about the neighbours seems correct. There's special flags to indicate that an edge is potentially leading to a neighbour tile too:

https://github.com/recastnavigation/recastnavigation/blob/master/Detour/Source/DetourNavMeshBuilder.cpp#L500

--mikko 

[Christmas Eve]

Oh crap (lol) I have to worry about tile to tile connections too... I didn't realize that.  I thought addTile would take care of that.

I looked at both links you sent me and I only have one question.  I understand poly to poly connections within a tile and I also think I understand tile-to-tile (-X +X -Z +Z) but there is also a 0x8000 with a low byte of 0x0f which is supposed to indicate "border" (so basically a value of 0x800f).  What is this?  I thought that is what -X,+X,-Z,+Z were supposed to indicate, and a poly that has no connection on an edge (whether it's on the edge of a tile or not) I thought would just be 0xffff.

I already wrote code to establish connections within each tile but not between tiles.  You pointed me to a function that seems to build connections inside a tile (which is what I did) but I don't see that it handles tile-to-tile.  Is there something else I can call?  Otherwise, I'm going to have to understand it more.

[Christmas Eve]

Scratch that last reply.  I found the code in Recast that builds portals at the borders and used it to finish the job:

...

Adding Tile #9507: 1, 97

TILE TRI #9507: 0 1 2 - neis: 32770 32770 1

TILE TRI #9507: 0 2 3 - neis: 0 32770 32770

Adding Tile #9508: 2, 97

TILE TRI #9508: 0 1 2 - neis: 32771 32768 1

TILE TRI #9508: 0 2 3 - neis: 0 32771 32770

Adding Tile #9509: 3, 97

TILE TRI #9509: 0 1 2 - neis: 32771 32770 1

TILE TRI #9509: 0 2 3 - neis: 0 32771 32768

Adding Tile #9510: 4, 97

TILE TRI #9510: 0 1 2 - neis: 32770 32769 1

TILE TRI #9510: 0 2 3 - neis: 0 32770 32770

Adding Tile #9511: 5, 97

TILE TRI #9511: 0 1 2 - neis: 65535 32768 1

TILE TRI #9511: 0 2 3 - neis: 0 65535 32769

Adding Tile #9512: 6, 97

TILE TRI #9512: 0 1 2 - neis: 32768 32768 1

TILE TRI #9512: 0 2 3 - neis: 0 32768 32768

Adding Tile #9513: 7, 97

TILE TRI #9513: 0 1 2 - neis: 65535 65535 1

TILE TRI #9513: 0 2 3 - neis: 0 65535 65535

TILE TRI #9513: 4 5 6 - neis: 65535 32770 65535

TILE TRI #9513: 7 8 9 - neis: 65535 65535 65535

...

But, I still can't pathfind.  It can find some locations but most of locations cannot be found.  And, 0,0,0 can find a close poly even though my beginning poly is quite far from 0,0,0 and my search area, or poly extents box is only {2,10,2}.  

So I'm a bit confused.  my CS is 1/3 and CH is 1/5.  I've multiplied all verts by (3,5,3} and converted to ushorts.

Plus these three values have been multiplied by my CS value: (for ease of reference, I plugged in the actual value of 3 instead of my inverse CS var):

            params.walkableHeight = 1.8 * 3;

            params.walkableRadius = 0.5* 3;

            params.walkableClimb = 1.2 * 3;

Does it sound like I did everything right?  I must be SO CLOSE now.  I even have it auto-detecting the tile borders from the data I get from Unity.  So I should be able to load as many maps as I want from files exported from my custom script, and pathfind against them!  It will be a remarkable goal!  I literally need not give it any additional information.  I'm so excited but frustrated at the same time!  I look forward to your reply.  Thanks in advance.

[Christmas Eve]

I have an idea. (Sorry about all the replies in a row.)  Wanted to get this out there.

I saved my navmesh to navmesh.0 (all 98x98 tiles with headers, etc).  RecastDemo doesn't seem to have a function to load just a navmesh and since I'm not starting with a level geometry file (.obj) I have no way to analyze this data to see if it's correct.

I've zipped my testmesh and uploaded placed it here (https://drive.google.com/open?id=0B1kLYgaVTkWgM29MWDZETm9SNTA).  Do you have a way of quickly analyzing a navmesh to see if it has any problems with neighboring, or to ensure that the scale and parameters are correct?

In case you wouldn't mind looking at this, here is what you SHOULD find:

It is ~10000x10000 world units.

The XZ voxel size (cs) should be 0.1.

The Y voxel size (ch) should be 0.1.

There should be a DISCONTINUITY between {3670.368,202,3981.9} and {3663.063,189.6423,4045.331} due to a fence (which it should be pathfinding around), and this whole test level should have many such long discontinuities.

I can sample points throughout the world and get the right height but pathfinding takes me directly to the destination, even if there is a break in continuity between the starting and ending points.

[Christmas Eve]

I figured this out.  I still had duplicate vertices.