R+D Mesh Generation - Issues on AbyssalMaw_Interior (contours/ncid)

[Tanaris4]

All-

I'm working on mesh generation now for more than just Azeroth (which works quite well) and I'm running into a few problems.

In particular I'm looking at AbyssalMaw_Interior, which is QUITE tall (see pic below) and I predict this may have something to do with it.

I basically take a tile (31, 33 pictured) and split it into 16 smaller tiles. As you can see from the picture, only 1 of the meshes for the 16 sub-tiles are actually generated. The others I am not able to as my builder gives me a "no ncid" (rcGetChunksOverlappingRect) or "no contours" (rcAllocContourSet) error.

Has anyone experienced this? Or know how I can debug?



I pass my builder the tile data, as well as the tile data of tiles around it (3x3):

- (unsigned char*)buildMeshWithGeom:(InputGeom*)geom andX:(int)tx andY:(int)ty andMin:(float*)bmin andMax:(float*)bmax andSize:(int&)dataSize{
    
    NSDate *start = [NSDate date];
    
    const float* verts = geom->getMesh()->getVerts();
	const int nverts = geom->getMesh()->getVertCount();
	const rcChunkyTriMesh* chunkyMesh = geom->getChunkyMesh();
    const int ntris = geom->getMesh()->getTriCount();
    
    rcConfig m_cfg;	
	// Init build configuration from GUI
	memset(&m_cfg, 0, sizeof(m_cfg));
	m_cfg.cs = CellSize;
	m_cfg.ch = CellHeight;
	m_cfg.walkableSlopeAngle = WalkableSlopeAngle;
	m_cfg.walkableHeight = WalkableHeight;//(int)ceilf(WorldUnitWalkableHeight / m_cfg.ch);
	m_cfg.walkableClimb = WalkableClimb;//(int)floorf(WorldUnitWalkableClimb / m_cfg.ch);
	m_cfg.walkableRadius = WalkableRadius;//(int)ceilf(WorldUnitWalkableRadius / m_cfg.cs);
	m_cfg.maxEdgeLen = (int)MaxEdgeLen;//8;(int)MaxEdgeLen;
	m_cfg.maxSimplificationError = MaxSimplificationError;
	m_cfg.minRegionArea = (int)rcSqr(MinRegionSize);		// Note: area = size*size
	m_cfg.mergeRegionArea = (int)rcSqr(MergeRegionSize);	// Note: area = size*size
	m_cfg.maxVertsPerPoly = (int)m_vertsPerPoly;
	m_cfg.tileSize = (int)(GRID_SIZE / GridDiv);
	m_cfg.borderSize = BorderSize;
	m_cfg.detailSampleDist = DetailSampleDist;
	m_cfg.detailSampleMaxError = DetailSampleMaxError;
    m_cfg.width = TileWidth;
    m_cfg.height = TileWidth;
    
    NSLog(@"-- (%d, %d) --", tx, ty);

    // save the tile's max/min not the 3x3!
    rcVcopy(m_cfg.bmin, bmin);
	rcVcopy(m_cfg.bmax, bmax);
    
    m_cfg.bmin[0] -= m_cfg.borderSize*m_cfg.cs;
    m_cfg.bmin[2] -= m_cfg.borderSize*m_cfg.cs;
    m_cfg.bmax[0] += m_cfg.borderSize*m_cfg.cs;
    m_cfg.bmax[2] += m_cfg.borderSize*m_cfg.cs;
    
    rcContext *ctx = NULL;

    // set up our context
    ctx = new rcContext();
    ctx->resetTimers();
    ctx->startTimer(RC_TIMER_TOTAL);
    
    NSLog(@"Building navigation:");
	NSLog(@" - %d x %d cells", m_cfg.width, m_cfg.height);
	NSLog(@" - %.1fK verts, %.1fK tris", nverts/1000.0f, ntris/1000.0f);
    
    // Allocate voxel heightfield where we rasterize our input data to.
    rcHeightfield *m_solid = rcAllocHeightfield();
    if ( !m_solid ){
        NSLog(@"buildNavigation: Out of memory 'solid'.");
        delete ctx;
        return NULL;
    }
    if ( !rcCreateHeightfield(ctx, *m_solid, m_cfg.width, m_cfg.height, m_cfg.bmin, m_cfg.bmax, m_cfg.cs, m_cfg.ch) ){
        NSLog(@"buildNavigation: Could not create solid heightfield.");
        delete ctx;
        return NULL;
    }
    
    // Allocate array that can hold triangle flags.
    // If you have multiple meshes you need to process, allocate
    // and array which can hold the max number of triangles you need to process.
    unsigned char *m_triareas = new unsigned char[chunkyMesh->maxTrisPerChunk];
    if ( !m_triareas ){
        NSLog(@"buildNavigation: Out of memory 'm_triareas' (%d).", chunkyMesh->maxTrisPerChunk);
        delete ctx;
        return NULL;
    }
    
    float tbmin[2], tbmax[2];
    tbmin[0] = m_cfg.bmin[0];
    tbmin[1] = m_cfg.bmin[2];
    tbmax[0] = m_cfg.bmax[0];
    tbmax[1] = m_cfg.bmax[2];
    NSLog(@"Min: {%0.2f, %0.2f, %0.2f} Max: {%0.2f, %0.2f, %0.2f}", tbmin[0], tbmin[1], tbmin[2], tbmax[0], tbmax[1], tbmax[2]);
    int cid[100000];// TODO: Make grow when returning too many items.
    const int ncid = rcGetChunksOverlappingRect(chunkyMesh, tbmin, tbmax, cid, 100000);
    if ( !ncid ){
        NSLog(@"ncid error");
        delete ctx;
        return NULL;
    }
    
    int m_tileTriCount = 0;
    
    for ( int i = 0; i < ncid; ++i ){
        const rcChunkyTriMeshNode& node = chunkyMesh->nodes[cid[i]];
        const int* tris = &chunkyMesh->tris[node.i*3];
        const int ntris = node.n;
        
        m_tileTriCount += ntris;
        
        memset(m_triareas, 0, ntris*sizeof(unsigned char));
        rcMarkWalkableTriangles( ctx, m_cfg.walkableSlopeAngle, verts, nverts, tris, ntris, m_triareas );
        
        rcRasterizeTriangles( ctx, verts, nverts, tris, m_triareas, ntris, *m_solid, m_cfg.walkableClimb );
    }
    
    if ( !m_keepInterResults ){
        delete [] m_triareas;
        m_triareas = 0;
    }
    
    // Once all geometry is rasterized, we do initial pass of filtering to
    // remove unwanted overhangs caused by the conservative rasterization
    // as well as filter spans where the character cannot possibly stand.
    rcFilterLowHangingWalkableObstacles(ctx, m_cfg.walkableClimb, *m_solid);
    rcFilterLedgeSpans(ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid);
    rcFilterWalkableLowHeightSpans(ctx, m_cfg.walkableHeight, *m_solid);
    
    // Compact the heightfield so that it is faster to handle from now on.
    // This will result more cache coherent data as well as the neighbours
    // between walkable cells will be calculated.
    rcCompactHeightfield *m_chf = rcAllocCompactHeightfield();
    if ( !m_chf ){
        NSLog(@"buildNavigation: Out of memory 'chf'.");
        delete ctx;
        return NULL;
    }
    
    if ( !rcBuildCompactHeightfield(ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid, *m_chf) ){
        NSLog(@"buildNavigation: Could not build compact data.");
        delete ctx;
        return NULL;
    }
    
    if ( !m_keepInterResults ){
        rcFreeHeightField(m_solid);
        m_solid = 0;
    }
    
    // Erode the walkable area by agent radius.
    if ( !rcErodeWalkableArea(ctx, m_cfg.walkableRadius, *m_chf) ){
        NSLog(@"buildNavigation: Could not erode.");
        delete ctx;
        return NULL;
    }
    
    // (Optional) Mark areas.
    const ConvexVolume* vols = geom->getConvexVolumes();
    for (int i  = 0; i < geom->getConvexVolumeCount(); ++i)
        rcMarkConvexPolyArea(ctx, vols[i].verts, vols[i].nverts, vols[i].hmin, vols[i].hmax, (unsigned char)vols[i].area, *m_chf);
    
    if ( m_monotonePartitioning ){
        // Partition the walkable surface into simple regions without holes.
        if ( !rcBuildRegionsMonotone(ctx, *m_chf, m_cfg.borderSize, m_cfg.minRegionArea, m_cfg.mergeRegionArea) ){
            NSLog(@"buildNavigation: Could not build regions.");
            delete ctx;
            return NULL;
        }
    }
    else{
        // Prepare for region partitioning, by calculating distance field along the walkable surface.
        if ( !rcBuildDistanceField(ctx, *m_chf) ){
            NSLog(@"buildNavigation: Could not build distance field.");
            delete ctx;
            return NULL;
        }
        
        // Partition the walkable surface into simple regions without holes.
        if ( !rcBuildRegions(ctx, *m_chf, m_cfg.borderSize, m_cfg.minRegionArea, m_cfg.mergeRegionArea) ){
            NSLog(@"buildNavigation: Could not build regions.");
            delete ctx;
            return NULL;
        }
    }
    
    // Create contours.
    rcContourSet *m_cset = rcAllocContourSet();
    if ( !m_cset ){
        NSLog(@"buildNavigation: Out of memory 'cset'.");
        delete ctx;
        return NULL;
    }
    if ( !rcBuildContours(ctx, *m_chf, m_cfg.maxSimplificationError, m_cfg.maxEdgeLen, *m_cset) ){
        NSLog(@"buildNavigation: Could not create contours.");
        delete ctx;
        return NULL;
    }
    
    if ( m_cset->nconts == 0 ){
        NSLog(@"No contours ");
        delete ctx;
        return NULL;
    }
    
    // Build polygon navmesh from the contours.
    rcPolyMesh *m_pmesh = rcAllocPolyMesh();
    if ( !m_pmesh ){
        NSLog(@"buildNavigation: Out of memory 'pmesh'.");
        delete ctx;
        return NULL;
    }
    if ( !rcBuildPolyMesh(ctx, *m_cset, m_cfg.maxVertsPerPoly, *m_pmesh) ){
        NSLog(@"buildNavigation: Could not triangulate contours.");
        delete ctx;
        return NULL;
    }
    
    // Build detail mesh.
    rcPolyMeshDetail *m_dmesh = rcAllocPolyMeshDetail();
    if ( !m_dmesh ){
        NSLog(@"buildNavigation: Out of memory 'dmesh'.");
        delete ctx;
        return NULL;
    }
    
    if ( !rcBuildPolyMeshDetail(ctx, *m_pmesh, *m_chf, m_cfg.detailSampleDist, m_cfg.detailSampleMaxError, *m_dmesh) ){
        NSLog(@"buildNavigation: Could build polymesh detail.");
        delete ctx;
        return NULL;
    }
    
    if ( !m_keepInterResults ){
        rcFreeCompactHeightfield(m_chf);
        m_chf = 0;
        rcFreeContourSet(m_cset);
        m_cset = 0;
    }
    
    unsigned char *navData = NULL;
    
    if ( m_cfg.maxVertsPerPoly <= DT_VERTS_PER_POLYGON ){
        
        if ( m_pmesh->nverts >= 0xffff ){
            // The vertex indices are ushorts, and cannot point to more than 0xffff vertices.
            NSLog(@"Too many vertices per tile %d (max: %d).", m_pmesh->nverts, 0xffff);
            delete ctx;
            return NULL;
        }
        
        // Update poly flags from areas.
        for ( int i = 0; i < m_pmesh->npolys; ++i ){
            if (m_pmesh->areas[i] == RC_WALKABLE_AREA)
                m_pmesh->areas[i] = SAMPLE_POLYAREA_GROUND;
            
            if ( m_pmesh->areas[i] == SAMPLE_POLYAREA_GROUND || m_pmesh->areas[i] == SAMPLE_POLYAREA_GRASS || m_pmesh->areas[i] == SAMPLE_POLYAREA_ROAD ){
                m_pmesh->flags[i] = SAMPLE_POLYFLAGS_WALK;
            }
            else if ( m_pmesh->areas[i] == SAMPLE_POLYAREA_WATER ){
                m_pmesh->flags[i] = SAMPLE_POLYFLAGS_SWIM;
            }
            else if ( m_pmesh->areas[i] == SAMPLE_POLYAREA_DOOR ){
                m_pmesh->flags[i] = SAMPLE_POLYFLAGS_WALK | SAMPLE_POLYFLAGS_DOOR;
            }
        }
        
        dtNavMeshCreateParams params;
        memset(&params, 0, sizeof(params));
        params.verts = m_pmesh->verts;
        params.vertCount = m_pmesh->nverts;
        params.polys = m_pmesh->polys;
        params.polyAreas = m_pmesh->areas;
        params.polyFlags = m_pmesh->flags;
        params.polyCount = m_pmesh->npolys;
        params.nvp = m_pmesh->nvp;
        params.detailMeshes = m_dmesh->meshes;
        params.detailVerts = m_dmesh->verts;
        params.detailVertsCount = m_dmesh->nverts;
        params.detailTris = m_dmesh->tris;
        params.detailTriCount = m_dmesh->ntris;
        params.offMeshConVerts = geom->getOffMeshConnectionVerts();
        params.offMeshConRad = geom->getOffMeshConnectionRads();
        params.offMeshConDir = geom->getOffMeshConnectionDirs();
        params.offMeshConAreas = geom->getOffMeshConnectionAreas();
        params.offMeshConFlags = geom->getOffMeshConnectionFlags();
        params.offMeshConUserID = geom->getOffMeshConnectionId();
        params.offMeshConCount = geom->getOffMeshConnectionCount();
        params.walkableHeight = WorldUnitWalkableHeight;
        params.walkableRadius = WorldUnitWalkableRadius;
        params.walkableClimb = WorldUnitWalkableClimb;
        params.tileX = tx;
        params.tileY = ty;
        params.tileLayer = 0;
		rcVcopy(params.bmin, m_pmesh->bmin);
		rcVcopy(params.bmax, m_pmesh->bmax);
        params.cs = m_cfg.cs;
        params.ch = m_cfg.ch;
        params.buildBvTree = true;
        
        if ( !dtCreateNavMeshData(&params, &navData, &dataSize) ){
            NSLog(@"Could not build Detour navmesh.");
            delete ctx;
            return NULL;
        }		
    }
    
    ctx->stopTimer(RC_TIMER_TOTAL);
    
    NSLog(@"(%d, %d) done %0.2f seconds", tx, ty, [start timeIntervalSinceNow] * -1.0f);
    
    // save!
    if ( dataSize > 0 ){
        delete ctx;
        return navData;
    }
    
    delete ctx;
    return NULL;
}

Any help or thoughts would be greatly appreciated - I'm pretty stuck!

Thanks,
~ Tanaris

[boredevil]

maybe it got nothing to do with your problem, but as tot is pretty deep in the sea, here´s what happened to me when pushing bounds with minZ lower than -1000.0 (if i remember correctly).
no problem creating data with x/y bounds for a worldmap. but having minZ lower than -1000.0 ****ed it all up. sometimes the resulting nav geom got created a few hundreds yards higher. another time just off by 50 on the z axis. using a higher cs sometimes solved the problem. but i never got any errors as you do.

[Tanaris4]

These are my parameters, if it helps:

#define GRID_SIZE       (533.0f + (1.0f / 3.0f))
#define TileSize        (533.0f + (1.0f / 3.0f))
#define TileVoxelSize   1800
#define MinRegionSize   20
#define MergeRegionSize 40

#define CellSize        TileSize / (float)TileVoxelSize

#define CellHeight              0.4f
#define WalkableSlopeAngle      50.0f
#define MaxSimplificationError  1.3f
#define DetailSampleDist        3.0f
#define DetailSampleMaxError    1.25f

#define WorldUnitWalkableHeight     1.652778f
#define WorldUnitWalkableClimb      1.0f
#define WorldUnitWalkableRadius     0.2951389f

#define WalkableHeight      (int)ceilf(WorldUnitWalkableHeight / CellHeight)
#define WalkableClimb       (int)floorf(WorldUnitWalkableClimb  / CellHeight)
#define WalkableRadius      (int)ceilf(WorldUnitWalkableRadius / CellSize)

#define MaxEdgeLen          (int)(WalkableRadius * 8.0f)
#define BorderSize          (int)(WalkableRadius + 4.0f)
#define TileWidth           (TileVoxelSize / GridDiv) + (BorderSize * 2)

#define GridDiv 4
#define MaxPoly  1048576 / ( GridDiv*GridDiv)

/////



#define m_vertsPerPoly          6.0f

#define m_keepInterResults      false
#define m_monotonePartitioning  false

And how it is set up:

    const float* verts = geom->getMesh()->getVerts();
	const int nverts = geom->getMesh()->getVertCount();
	const rcChunkyTriMesh* chunkyMesh = geom->getChunkyMesh();
    const int ntris = geom->getMesh()->getTriCount();
    
    rcConfig m_cfg;	
	// Init build configuration from GUI
	memset(&m_cfg, 0, sizeof(m_cfg));
	m_cfg.cs = CellSize;
	m_cfg.ch = CellHeight;
	m_cfg.walkableSlopeAngle = WalkableSlopeAngle;
	m_cfg.walkableHeight = WalkableHeight;//(int)ceilf(WorldUnitWalkableHeight / m_cfg.ch);
	m_cfg.walkableClimb = WalkableClimb;//(int)floorf(WorldUnitWalkableClimb / m_cfg.ch);
	m_cfg.walkableRadius = WalkableRadius;//(int)ceilf(WorldUnitWalkableRadius / m_cfg.cs);
	m_cfg.maxEdgeLen = (int)MaxEdgeLen;//8;(int)MaxEdgeLen;
	m_cfg.maxSimplificationError = MaxSimplificationError;
	m_cfg.minRegionArea = (int)rcSqr(MinRegionSize);		// Note: area = size*size
	m_cfg.mergeRegionArea = (int)rcSqr(MergeRegionSize);	// Note: area = size*size
	m_cfg.maxVertsPerPoly = (int)m_vertsPerPoly;
	m_cfg.tileSize = (int)(GRID_SIZE / GridDiv);
	m_cfg.borderSize = BorderSize;
	m_cfg.detailSampleDist = DetailSampleDist;
	m_cfg.detailSampleMaxError = DetailSampleMaxError;
    m_cfg.width = TileWidth;
    m_cfg.height = TileWidth;
    
    NSLog(@"-- (%d, %d) --", tx, ty);

    // save the tile's max/min not the 3x3!
    rcVcopy(m_cfg.bmin, bmin);
	rcVcopy(m_cfg.bmax, bmax);
    
    m_cfg.bmin[0] -= m_cfg.borderSize*m_cfg.cs;
    m_cfg.bmin[2] -= m_cfg.borderSize*m_cfg.cs;
    m_cfg.bmax[0] += m_cfg.borderSize*m_cfg.cs;
    m_cfg.bmax[2] += m_cfg.borderSize*m_cfg.cs;
    
    rcContext *ctx = NULL;

    // set up our context
    ctx = new rcContext();
    ctx->resetTimers();
    ctx->startTimer(RC_TIMER_TOTAL);

[MaiN]

maybe it got nothing to do with your problem, but as tot is pretty deep in the sea, here´s what happened to me when pushing bounds with minZ lower than -1000.0 (if i remember correctly).
no problem creating data with x/y bounds for a worldmap. but having minZ lower than -1000.0 ****ed it all up. sometimes the resulting nav geom got created a few hundreds yards higher. another time just off by 50 on the z axis. using a higher cs sometimes solved the problem. but i never got any errors as you do.

I have determined the cause of this. Recast stores the spans min/max (not world coordinates, cells!) using 13 bits (check rcSpan).
13 bits is however not enough when you have very deep terrain. The max height of the bounding box can be determined by 8191 (1 << 13 - 1 ) * ch. 8191 comes from the max value 13 bits can contain (check RC_SPAN_MAX_HEIGHT). Recast translates by -bmin.Y, like it should. This means that any terrain that is above bmin.Y + 8191 * ch will be regarded as being at bmin.Y + 8191 * ch.
To fix this, you can either choose a higher cellheight or change Recast to use more bits for the span height.

For more information, check Recast's rasterizeTri function.

EDIT: I just realized mikko actually responded to this exact problem just a few days ago (I hadn't seen this by the time of this post). You can check his response here: http://groups.google.com/group/recas...3d8a6cd3baad39