recastnavigation can not support big terrain

[GoogleCodeExporter]

hi Mikko Mononen:
I use your recastnavigation in my 3d game develop.
My terrain size is 2048 * 2048. 
I use Sample_TileMesh to generate navmesh. 
The vertexs and indices are too large, so rcMeshLoaderObj::load(const char* 
filename) frequently crashed.

 The crash is are occured in this case:
m_normals = new float[m_triCount*3];  //crashed

void rcMeshLoaderObj::addVertex(float x, float y, float z, int& cap)
{
 if (m_vertCount+1 > cap)
 {
  cap = !cap ? 8 : cap*2;
  float* nv = new float[cap*3]; //crashed

void rcMeshLoaderObj::addTriangle(int a, int b, int c, int& cap)
{
 if (m_triCount+1 > cap)
 {
  cap = !cap ? 8 : cap*2;
  int* nv = new int[cap*3]; //crashed

Original issue reported on code.google.com by tangb...@163.com on 3 Dec 2010 at 2:30

[GoogleCodeExporter]

How much memory are you trying to allocate?

Original comment by memono...@gmail.com on 3 Dec 2010 at 8:08

[GoogleCodeExporter]

bool rcCreateChunkyTriMesh(const float* verts, const int* tris, int ntris,
                           int trisPerChunk, rcChunkyTriMesh* cm)
{
    int nchunks = (ntris + trisPerChunk-1) / trisPerChunk;

    cm->nodes = new rcChunkyTriMeshNode[nchunks*4];
    if (!cm->nodes)
        return false;

    cm->tris = new int[ntris*3];
    if (!cm->tris)
        return false;

    cm->ntris = ntris;

    // Build tree
    BoundsItem* items = new BoundsItem[ntris];
    if (!items)
        return false;

    for (int i = 0; i < ntris; i++)
    {
        const int* t = &tris[i*3];
        BoundsItem& it = items[i];
        it.i = i;
        // Calc triangle XZ bounds.
        it.bmin[0] = it.bmax[0] = verts[t[0]*3+0];
        it.bmin[1] = it.bmax[1] = verts[t[0]*3+2];
        for (int j = 1; j < 3; ++j)
        {
            const float* v = &verts[t[j]*3];
            if (v[0] < it.bmin[0]) it.bmin[0] = v[0]; 
            if (v[2] < it.bmin[1]) it.bmin[1] = v[2]; 

            if (v[0] > it.bmax[0]) it.bmax[0] = v[0]; 
            if (v[2] > it.bmax[1]) it.bmax[1] = v[2]; 
        }
    }

    int curTri = 0;
    int curNode = 0;
    subdivide(items, ntris, 0, ntris, trisPerChunk, curNode, cm->nodes, nchunks*4, curTri, cm->tris, tris);

    delete [] items;

    cm->nnodes = curNode;

    // Calc max tris per node.
    cm->maxTrisPerChunk = 0;
    for (int i = 0; i < cm->nnodes; ++i)
    {
        rcChunkyTriMeshNode& node = cm->nodes[i];
        const bool isLeaf = node.i >= 0;
        if (!isLeaf) continue;
        if (node.n > cm->maxTrisPerChunk)
            cm->maxTrisPerChunk = node.n;
    }

    return true;
}

In this function,

BoundsItem* items = new BoundsItem[ntris];
failed.
my terrain is 2048*2048 size.
and ntris = 8844520.

Original comment by tangb...@163.com on 7 Dec 2010 at 9:03

[GoogleCodeExporter]

Looks like you run out of memory.

In that case the only thing you can do is to generate the navmesh smaller 
pieces at a time and load the terrain mesh in chunks too.

The basic idea is that you select Recast tile size to be the same as for 
example a 128x128 chunk of your terrain.

When generating a tile, you pass the triangles from the center tile and all 
surrounding tiles to Recast. This is required so that Recast can handle the 
tile borders. In that case there is no need to use chunky mesh.

Pseudo code:

Sample_TileMesh::buildTileMesh(tx,ty)
{
    // Init stuff as per example code

    // Put this at the spot where rcGetChunksOverlappingRect() is called.

    for (int y = ty-1; y <= ty+1; ++y)
    {
        for (int x = tx-1; x <= tx+1; ++x)
        {
            // Rasterize terrain
            TerrainMeshPiece* ter = getTerrainMeshAt(x,y);
            memset(m_triareas, 0, ter->ntris*sizeof(unsigned char));
                    rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, ter->verts, ter->nverts, ter->tris, ter->ntris, m_triareas);
                    rcRasterizeTriangles(m_ctx, ter->verts, ter->nverts, ter->tris, m_triareas, ter->ntris, *m_solid, m_cfg.walkableClimb);

            // Rasterize props (rocks, tree, etc)
            PropMesh* props[MAX_PROPS];
            int nprops = getTerrainPropsAt(x,y props, MAX_PROPS);
            for (int i = 0; i < nprops; ++i)
            {
                PropMesh* m = props[i];
                memset(m_triareas, 0, m->ntris*sizeof(unsigned char));
                        rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, m->verts, m->nverts, m->tris, m->ntris, m_triareas);
                        rcRasterizeTriangles(m_ctx, m->verts, m->nverts, m->tris, m_triareas, m->ntris, *m_solid, m_cfg.walkableClimb);
            }
        }
    }

    // Finish the rest of the steps.
}

Original comment by memono...@gmail.com on 7 Dec 2010 at 9:27

[GoogleCodeExporter]

If I use this func.

Sample_TileMesh::buildTileMesh(tx,ty)
{
    // Init stuff as per example code

    // Put this at the spot where rcGetChunksOverlappingRect() is called.

    for (int y = ty-1; y <= ty+1; ++y)
    {
        for (int x = tx-1; x <= tx+1; ++x)
        {
            // Rasterize terrain
            TerrainMeshPiece* ter = getTerrainMeshAt(x,y);
            memset(m_triareas, 0, ter->ntris*sizeof(unsigned char));
                    rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, ter->verts, ter->nverts, ter->tris, ter->ntris, m_triareas);
                    rcRasterizeTriangles(m_ctx, ter->verts, ter->nverts, ter->tris, m_triareas, ter->ntris, *m_solid, m_cfg.walkableClimb);

            // Rasterize props (rocks, tree, etc)
            PropMesh* props[MAX_PROPS];
            int nprops = getTerrainPropsAt(x,y props, MAX_PROPS);
            for (int i = 0; i < nprops; ++i)
            {
                PropMesh* m = props[i];
                memset(m_triareas, 0, m->ntris*sizeof(unsigned char));
                        rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, m->verts, m->nverts, m->tris, m->ntris, m_triareas);
                        rcRasterizeTriangles(m_ctx, m->verts, m->nverts, m->tris, m_triareas, m->ntris, *m_solid, m_cfg.walkableClimb);
            }
        }
    }

    // Finish the rest of the steps.
}

Should I need to change the m_navMesh?

Original comment by tangb...@163.com on 9 Dec 2010 at 5:36

[GoogleCodeExporter]

Nope, that function is creating one tile of data for the navmesh.

Original comment by memono...@gmail.com on 9 Dec 2010 at 7:59

[GoogleCodeExporter]

memononen ,Thank you for your passion to help
I use your method to do it, but can't gen navmesh.
Can you add a function on your project to handle big terrain.

Original comment by tangb...@163.com on 9 Dec 2010 at 9:47

[GoogleCodeExporter]

Querying only a subset of data is specific to your game and thus is not 
something I can add to the project.

Do you have your own engine you use to render the terrain?

Original comment by memono...@gmail.com on 9 Dec 2010 at 9:59

[GoogleCodeExporter]

Yes, I use my own engine to render the terrain.
I just need a method to gen navmesh data and use the data to find a path.
Your PathFind is very good, and I have used it to my 3D game.
But in the big scene, the gen function  consumes memory too much.
Do you consider to reduce the memory allocation?

Original comment by tangb...@163.com on 10 Dec 2010 at 1:34

[GoogleCodeExporter]

Recast has two ways to build a navmesh: the whole world at a time and a tile at 
a time. The way to reduce the memory usage is to use the tiled generation. 

The .obj mesh loader is provided as an example on how to load data. Since 
you're running out of memory, you should write your own loader to load your 
specific kind of data, and adjust the example code to use your data loader.

Original comment by memono...@gmail.com on 10 Dec 2010 at 7:16

[GoogleCodeExporter]

Original comment by memono...@gmail.com on 3 Feb 2011 at 9:31

• Changed state: Done