void Sample::handleCommonSettings()
{
	if (m_geom)
	{
		const float* bmin = m_geom->getMeshBoundsMin();
		const float* bmax = m_geom->getMeshBoundsMax();
		int gw = 0, gh = 0;
		rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
		char text[64];
		snprintf(text, 64, "Voxels  %d x %d", gw, gh);
	}
	
}

void Sample::handleCommonSettings()
{
	imguiLabel("Rasterization");
	imguiSlider("Cell Size", &m_cellSize, 0.1f, 1.0f, 0.01f);
	imguiSlider("Cell Height", &m_cellHeight, 0.1f, 1.0f, 0.01f);
	
	if (m_geom)
	{
		const float* bmin = m_geom->getMeshBoundsMin();
		const float* bmax = m_geom->getMeshBoundsMax();
		int gw = 0, gh = 0;
		rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
		char text[64];
		snprintf(text, 64, "Voxels  %d x %d", gw, gh);
		imguiValue(text);
	}
	
	imguiSeparator();
	imguiLabel("Agent");
	imguiSlider("Height", &m_agentHeight, 0.1f, 5.0f, 0.1f);
	imguiSlider("Radius", &m_agentRadius, 0.0f, 5.0f, 0.1f);
	imguiSlider("Max Climb", &m_agentMaxClimb, 0.1f, 5.0f, 0.1f);
	imguiSlider("Max Slope", &m_agentMaxSlope, 0.0f, 90.0f, 1.0f);
	
	imguiSeparator();
	imguiLabel("Region");
	imguiSlider("Min Region Size", &m_regionMinSize, 0.0f, 150.0f, 1.0f);
	imguiSlider("Merged Region Size", &m_regionMergeSize, 0.0f, 150.0f, 1.0f);

	imguiSeparator();
	imguiLabel("Partitioning");
	if (imguiCheck("Watershed", m_partitionType == SAMPLE_PARTITION_WATERSHED))
		m_partitionType = SAMPLE_PARTITION_WATERSHED;
	if (imguiCheck("Monotone", m_partitionType == SAMPLE_PARTITION_MONOTONE))
		m_partitionType = SAMPLE_PARTITION_MONOTONE;
	if (imguiCheck("Layers", m_partitionType == SAMPLE_PARTITION_LAYERS))
		m_partitionType = SAMPLE_PARTITION_LAYERS;
	
	imguiSeparator();
	imguiLabel("Polygonization");
	imguiSlider("Max Edge Length", &m_edgeMaxLen, 0.0f, 50.0f, 1.0f);
	imguiSlider("Max Edge Error", &m_edgeMaxError, 0.1f, 3.0f, 0.1f);
	imguiSlider("Verts Per Poly", &m_vertsPerPoly, 3.0f, 12.0f, 1.0f);		

	imguiSeparator();
	imguiLabel("Detail Mesh");
	imguiSlider("Sample Distance", &m_detailSampleDist, 0.0f, 16.0f, 1.0f);
	imguiSlider("Max Sample Error", &m_detailSampleMaxError, 0.0f, 16.0f, 1.0f);
	
	imguiSeparator();
}

void Sample_TileMesh::removeAllTiles()
{
	const float* bmin = m_geom->getMeshBoundsMin();
	const float* bmax = m_geom->getMeshBoundsMax();
	int gw = 0, gh = 0;
	rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
	const int ts = (int)m_tileSize;
	const int tw = (gw + ts-1) / ts;
	const int th = (gh + ts-1) / ts;
	
	for (int y = 0; y < th; ++y)
		for (int x = 0; x < tw; ++x)
			m_navMesh->removeTile(m_navMesh->getTileRefAt(x,y),0,0);
}

void Sample_TileMesh::buildAllTiles()
{
	if (!m_geom) return;
	if (!m_navMesh) return;
	
	const float* bmin = m_geom->getNavMeshBoundsMin();
	const float* bmax = m_geom->getNavMeshBoundsMax();
	int gw = 0, gh = 0;
	rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
	const int ts = (int)m_tileSize;
	const int tw = (gw + ts-1) / ts;
	const int th = (gh + ts-1) / ts;
	const float tcs = m_tileSize*m_cellSize;

	
	// Start the build process.
	m_ctx->startTimer(RC_TIMER_TEMP);

	for (int y = 0; y < th; ++y)
	{
		for (int x = 0; x < tw; ++x)
		{
			m_lastBuiltTileBmin[0] = bmin[0] + x*tcs;
			m_lastBuiltTileBmin[1] = bmin[1];
			m_lastBuiltTileBmin[2] = bmin[2] + y*tcs;
			
			m_lastBuiltTileBmax[0] = bmin[0] + (x+1)*tcs;
			m_lastBuiltTileBmax[1] = bmax[1];
			m_lastBuiltTileBmax[2] = bmin[2] + (y+1)*tcs;
			
			int dataSize = 0;
			unsigned char* data = buildTileMesh(x, y, m_lastBuiltTileBmin, m_lastBuiltTileBmax, dataSize);
			if (data)
			{
				// Remove any previous data (navmesh owns and deletes the data).
				m_navMesh->removeTile(m_navMesh->getTileRefAt(x,y,0),0,0);
				// Let the navmesh own the data.
				dtStatus status = m_navMesh->addTile(data,dataSize,DT_TILE_FREE_DATA,0,0);
				if (dtStatusFailed(status))
					dtFree(data);
			}
		}
	}
	
	// Start the build process.	
	m_ctx->stopTimer(RC_TIMER_TEMP);

	m_totalBuildTimeMs = m_ctx->getAccumulatedTime(RC_TIMER_TEMP)/1000.0f;
	
}

void RecastMapRenderer::Render()
{
	if (!m_RecastMap->GetGeometry() || !m_RecastMap->GetGeometry()->getMesh())
		return;
	// ========================================== setup
	glDepthFunc(GL_LESS);
	glDepthMask(GL_TRUE);
	DebugDrawGL dd;
	const float texScale = 1.0f / (RECAST_CELL_SIZE * 10.0f);
	duDebugDrawTriMeshSlope(&dd, 
		m_RecastMap->GetGeometry()->getMesh()->getVerts(), 
		m_RecastMap->GetGeometry()->getMesh()->getVertCount(),
		m_RecastMap->GetGeometry()->getMesh()->getTris(), 
		m_RecastMap->GetGeometry()->getMesh()->getNormals(), 
		m_RecastMap->GetGeometry()->getMesh()->getTriCount(),
		RECAST_AGENT_MAX_SLOPE, 
		texScale);
	
	DrawAgents(&dd);
	
	glDepthMask(GL_FALSE);
	// Draw bounds
	const float* bmin = m_RecastMap->GetGeometry()->getMeshBoundsMin();
	const float* bmax = m_RecastMap->GetGeometry()->getMeshBoundsMax();
	duDebugDrawBoxWire(&dd, bmin[0],bmin[1],bmin[2], bmax[0],bmax[1],bmax[2], duRGBA(255,255,255,128), 1.0f);
	
	// Tiling grid.
	int gw = 0, gh = 0;
	rcCalcGridSize(bmin, bmax, RECAST_CELL_SIZE, &gw, &gh);
	const int tw = (gw + RECAST_TILE_SIZE - 1) / RECAST_TILE_SIZE;
	const int th = (gh + RECAST_TILE_SIZE - 1) / RECAST_TILE_SIZE;
	const float s = RECAST_TILE_SIZE*RECAST_CELL_SIZE;
	duDebugDrawGridXZ(&dd, bmin[0],bmin[1],bmin[2], tw,th, s, duRGBA(0,0,0,64), 1.0f);

	if(m_RecastMap->GetMesh() && m_RecastMap->GetQuery())
	{
		duDebugDrawNavMesh(&dd, *(m_RecastMap->GetMesh()), 
			DU_DRAWNAVMESH_COLOR_TILES|DU_DRAWNAVMESH_CLOSEDLIST|DU_DRAWNAVMESH_OFFMESHCONS);
		duDebugDrawNavMeshPolysWithFlags(&dd, *(m_RecastMap->GetMesh()), POLY_ABILITY_DISABLED, duRGBA(0,0,0,128));
	}
	if (m_RecastMap->GetTileCache())
		//DrawTiles(&dd, m_RecastMap->GetTileCache());
	
	if (m_RecastMap->GetTileCache())
		DrawObstacles(&dd, m_RecastMap->GetTileCache());

	if (m_RecastMap->GetGeometry())
		DrawConvexVolumes(&dd, m_RecastMap->GetGeometry());
}

void Sample_TileMesh::buildAllTiles()
{
	if (!m_geom) return;
	if (!m_navMesh) return;
	
	const float* bmin = m_geom->getMeshBoundsMin();
	const float* bmax = m_geom->getMeshBoundsMax();
	int gw = 0, gh = 0;
	rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
	const int ts = (int)m_tileSize;
	const int tw = (gw + ts-1) / ts;
	const int th = (gh + ts-1) / ts;
	const float tcs = m_tileSize*m_cellSize;


	// Start the build process.	
	rcTimeVal totStartTime = m_ctx->getTime();

	for (int y = 0; y < th; ++y)
	{
		for (int x = 0; x < tw; ++x)
		{
			m_tileBmin[0] = bmin[0] + x*tcs;
			m_tileBmin[1] = bmin[1];
			m_tileBmin[2] = bmin[2] + y*tcs;
			
			m_tileBmax[0] = bmin[0] + (x+1)*tcs;
			m_tileBmax[1] = bmax[1];
			m_tileBmax[2] = bmin[2] + (y+1)*tcs;
			
			int dataSize = 0;
			unsigned char* data = buildTileMesh(x, y, m_tileBmin, m_tileBmax, dataSize);
			if (data)
			{
				// Remove any previous data (navmesh owns and deletes the data).
				m_navMesh->removeTile(m_navMesh->getTileRefAt(x,y),0,0);
				// Let the navmesh own the data.
				if (!m_navMesh->addTile(data,dataSize,true))
					dtFree(data);
			}
		}
	}
	
	// Start the build process.	
	rcTimeVal totEndTime = m_ctx->getTime();

	m_totalBuildTimeMs = m_ctx->getDeltaTimeUsec(totStartTime, totEndTime)/1000.0f;
}

void Sample::handleCommonSettings()
{
	imguiLabel("Rasterization");
	imguiSlider("Cell Size", &m_fCellSize, 0.1f, 1.0f, 0.01f);
	imguiSlider("Cell Height", &m_fCellHeight, 0.1f, 1.0f, 0.01f);
	
	if (m_pInputGeom)
	{
		const float* bmin = m_pInputGeom->getMeshBoundsMin();
		const float* bmax = m_pInputGeom->getMeshBoundsMax();
		int gw = 0, gh = 0;
		rcCalcGridSize(bmin, bmax, m_fCellSize, &gw, &gh);
		char text[64];
		snprintf(text, 64, "Voxels  %d x %d", gw, gh);
		imguiValue(text);
	}
	
	imguiSeparator();
	imguiLabel("Agent");
	imguiSlider("Height", &m_fAgentHeight, 0.1f, 5.0f, 0.1f);
	imguiSlider("Radius", &m_fAgentRadius, 0.0f, 5.0f, 0.1f);
	imguiSlider("Max Climb", &m_fAgentMaxClimb, 0.1f, 5.0f, 0.1f);
	imguiSlider("Max Slope", &m_fAgentMaxSlope, 0.0f, 90.0f, 1.0f);
	
	imguiSeparator();
	imguiLabel("Region");
	imguiSlider("Min Region Size", &m_fRegionMinSize, 0.0f, 150.0f, 1.0f);
	imguiSlider("Merged Region Size", &m_fRegionMergeSize, 0.0f, 150.0f, 1.0f);
	if (imguiCheck("Monotore Partitioning", m_bMonotonePartitioning))
		m_bMonotonePartitioning = !m_bMonotonePartitioning;
	
	imguiSeparator();
	imguiLabel("Polygonization");
	imguiSlider("Max Edge Length", &m_fEdgeMaxLen, 0.0f, 50.0f, 1.0f);
	imguiSlider("Max Edge Error", &m_fEdgeMaxError, 0.1f, 3.0f, 0.1f);
	imguiSlider("Verts Per Poly", &m_fVertsPerPoly, 3.0f, 12.0f, 1.0f);		

	imguiSeparator();
	imguiLabel("Detail Mesh");
	imguiSlider("Sample Distance", &m_fDetailSampleDist, 0.0f, 16.0f, 1.0f);
	imguiSlider("Max Sample Error", &m_fDetailSampleMaxError, 0.0f, 16.0f, 1.0f);
	
	imguiSeparator();
}

void Sample::handleCommonSettings()
{
	imguiLabel("Rasterization");
	imguiSlider("Cell Size", &m_cellSize, 0.01f, 1.0f, 0.01f);
	imguiSlider("Cell Height", &m_cellHeight, 0.01f, 1.0f, 0.01f);
	
	if (m_geom)
	{
		const dtCoordinates bmin( m_geom->getMeshBoundsMin() );
		const dtCoordinates bmax( m_geom->getMeshBoundsMax() );
		int gw = 0, gh = 0;
		rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
		char text[64];
		snprintf(text, 64, "Voxels  %d x %d", gw, gh);
		imguiValue(text);
	}
	
	imguiSeparator();
	imguiLabel("Agent");
	imguiSlider("Height", &m_agentHeight, 0.0f, 2.0f, 0.01f);
	imguiSlider("Radius", &m_agentRadius, 0.0f, 2.0f, 0.01f);
	imguiSlider("Max Climb", &m_agentMaxClimb, 0.f, 1.0f, 0.01f);
	imguiSlider("Max Slope", &m_agentMaxSlope, 0.0f, 180.0f, 1.0f);
	
	imguiSeparator();
	imguiLabel("Region");
	imguiSlider("Min Region Size", &m_regionMinSize, 0.0f, 400.0f, 2.0f);
	imguiSlider("Merged Region Size", &m_regionMergeSize, 0.0f, 400.0f, 2.0f);
	if (imguiCheck("Monotone Partitioning", m_monotonePartitioning))
		m_monotonePartitioning = !m_monotonePartitioning;
	
	imguiSeparator();
	imguiLabel("Polygonization");
	imguiSlider("Max Edge Length", &m_edgeMaxLen, 0.0f, 100.0f, 1.0f);
	imguiSlider("Max Edge Error", &m_edgeMaxError, 0.0f, 10.0f, 0.1f);
	imguiSlider("Verts Per Poly", &m_vertsPerPoly, 3.0f, 6.0f, 1.0f);

	imguiSeparator();
	imguiLabel("Detail Mesh");
	imguiSlider("Sample Distance", &m_detailSampleDist, 0.0f, 30.0f, 1.0f);
	imguiSlider("Max Sample Error", &m_detailSampleMaxError, 0.0f, 30.0f, 1.0f);
	
	imguiSeparator();
}

unsigned char* RecastTileBuilder::build(float x, float y, const AABB& lastTileBounds, int& dataSize) {
	int gw = 0, gh = 0;

	float bmin[3];
	float bmax[3];

	bmin[0] = bounds.getXMin();
	bmin[1] = bounds.getYMin();
	bmin[2] = bounds.getZMin();


	bmax[0] = bounds.getXMax();
	bmax[1] = bounds.getYMax();
	bmax[2] = bounds.getZMax();

	rcCalcGridSize(bmin, bmax, settings.m_cellSize, &gw, &gh);
	const int ts = (int) settings.m_tileSize;
	const int tw = (gw + ts - 1) / ts;
	const int th = (gh + ts - 1) / ts;

	// Max tiles and max polys affect how the tile IDs are caculated.
	// There are 22 bits available for identifying a tile and a polygon.
	int tileBits = rcMin((int) ilog2(nextPow2(tw * th)), 14);
	int polyBits = 22 - tileBits;
	m_maxTiles = 1<<tileBits;
	m_maxPolysPerTile = 1<<polyBits;

	dtNavMeshParams params;
	params.orig[0] = bounds.getXMin();
	params.orig[1] = bounds.getYMin();
	params.orig[2] = bounds.getZMin();

	//rcVcopy(params.orig, m_geom->getNavMeshBoundsMin());
	params.tileWidth = settings.m_tileSize * settings.m_cellSize;
	params.tileHeight = settings.m_tileSize * settings.m_cellSize;
	params.maxTiles = m_maxTiles;
	params.maxPolys = m_maxPolysPerTile;

	dtStatus status;
	this->lastTileBounds = lastTileBounds;
	return buildTileMesh(x, y, dataSize);
}

void Sample_TileMesh::handleSettings()
{
	Sample::handleCommonSettings();

	if (imguiCheck("Keep Itermediate Results", m_keepInterResults))
		m_keepInterResults = !m_keepInterResults;

	if (imguiCheck("Build All Tiles", m_buildAll))
		m_buildAll = !m_buildAll;
	
	imguiLabel("Tiling");
	imguiSlider("TileSize", &m_tileSize, 16.0f, 1024.0f, 16.0f);
	
	if (m_geom)
	{
		char text[64];
		int gw = 0, gh = 0;
		const float* bmin = m_geom->getNavMeshBoundsMin();
		const float* bmax = m_geom->getNavMeshBoundsMax();
		rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
		const int ts = (int)m_tileSize;
		const int tw = (gw + ts-1) / ts;
		const int th = (gh + ts-1) / ts;
		snprintf(text, 64, "Tiles  %d x %d", tw, th);
		imguiValue(text);

		// Max tiles and max polys affect how the tile IDs are caculated.
		// There are 22 bits available for identifying a tile and a polygon.
		int tileBits = rcMin((int)ilog2(nextPow2(tw*th)), 14);
		if (tileBits > 14) tileBits = 14;
		int polyBits = 22 - tileBits;
		m_maxTiles = 1 << tileBits;
		m_maxPolysPerTile = 1 << polyBits;
		snprintf(text, 64, "Max Tiles  %d", m_maxTiles);
		imguiValue(text);
		snprintf(text, 64, "Max Polys  %d", m_maxPolysPerTile);
		imguiValue(text);
	}
	else
	{
		m_maxTiles = 0;
		m_maxPolysPerTile = 0;
	}
	
	imguiSeparator();
	
	imguiIndent();
	imguiIndent();
	
	if (imguiButton("Save"))
	{
		Sample::saveAll("all_tiles_navmesh.bin", m_navMesh);
	}

	if (imguiButton("Load"))
	{
		dtFreeNavMesh(m_navMesh);
		m_navMesh = Sample::loadAll("all_tiles_navmesh.bin");
		m_navQuery->init(m_navMesh, 2048);
	}

	imguiUnindent();
	imguiUnindent();
	
	char msg[64];
	snprintf(msg, 64, "Build Time: %.1fms", m_totalBuildTimeMs);
	imguiLabel(msg);
	
	imguiSeparator();
	
	imguiSeparator();
	
}

void Sample_TempObstacles::handleSettings()
{
    Sample::handleCommonSettings();

    if (imguiCheck("Keep Itermediate Results", m_keepInterResults))
        m_keepInterResults = !m_keepInterResults;

    imguiLabel("Tiling");
    imguiSlider("TileSize", &m_tileSize, 16.0f, 128.0f, 8.0f);

    int gridSize = 1;
    if (m_geom)
    {
        const float* bmin = m_geom->getNavMeshBoundsMin();
        const float* bmax = m_geom->getNavMeshBoundsMax();
        char text[64];
        int gw = 0, gh = 0;
        rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
        const int ts = (int)m_tileSize;
        const int tw = (gw + ts-1) / ts;
        const int th = (gh + ts-1) / ts;
        snprintf(text, 64, "Tiles  %d x %d", tw, th);
        imguiValue(text);

        // Max tiles and max polys affect how the tile IDs are caculated.
        // There are 22 bits available for identifying a tile and a polygon.
        int tileBits = rcMin((int)dtIlog2(dtNextPow2(tw*th*EXPECTED_LAYERS_PER_TILE)), 14);
        if (tileBits > 14) tileBits = 14;
        int polyBits = 22 - tileBits;
        m_maxTiles = 1 << tileBits;
        m_maxPolysPerTile = 1 << polyBits;
        snprintf(text, 64, "Max Tiles  %d", m_maxTiles);
        imguiValue(text);
        snprintf(text, 64, "Max Polys  %d", m_maxPolysPerTile);
        imguiValue(text);
        gridSize = tw*th;
    }
    else
    {
        m_maxTiles = 0;
        m_maxPolysPerTile = 0;
    }

    imguiSeparator();

    imguiLabel("Tile Cache");
    char msg[64];

    const float compressionRatio = (float)m_cacheCompressedSize / (float)(m_cacheRawSize+1);

    snprintf(msg, 64, "Layers  %d", m_cacheLayerCount);
    imguiValue(msg);
    snprintf(msg, 64, "Layers (per tile)  %.1f", (float)m_cacheLayerCount/(float)gridSize);
    imguiValue(msg);

    snprintf(msg, 64, "Memory  %.1f kB / %.1f kB (%.1f%%)", m_cacheCompressedSize/1024.0f, m_cacheRawSize/1024.0f, compressionRatio*100.0f);
    imguiValue(msg);
    snprintf(msg, 64, "Navmesh Build Time  %.1f ms", m_cacheBuildTimeMs);
    imguiValue(msg);
    snprintf(msg, 64, "Build Peak Mem Usage  %.1f kB", m_cacheBuildMemUsage/1024.0f);
    imguiValue(msg);

    imguiSeparator();

    imguiIndent();
    imguiIndent();

    if (imguiButton("Save"))
    {
        saveAll("all_tiles_tilecache.bin");
    }

    if (imguiButton("Load"))
    {
        dtFreeNavMesh(m_navMesh);
        dtFreeTileCache(m_tileCache);
        loadAll("all_tiles_tilecache.bin");
        m_navQuery->init(m_navMesh, 2048);
    }

    imguiUnindent();
    imguiUnindent();

    imguiSeparator();
}

bool Sample_TempObstacles::handleBuild()
{
    dtStatus status;

    if (!m_geom || !m_geom->getMesh())
    {
        m_ctx->log(RC_LOG_ERROR, "buildTiledNavigation: No vertices and triangles.");
        return false;
    }

    m_tmproc->init(m_geom);

    // Init cache
    const float* bmin = m_geom->getNavMeshBoundsMin();
    const float* bmax = m_geom->getNavMeshBoundsMax();
    int gw = 0, gh = 0;
    rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
    const int ts = (int)m_tileSize;
    const int tw = (gw + ts-1) / ts;
    const int th = (gh + ts-1) / ts;

    // Generation params.
    rcConfig cfg;
    memset(&cfg, 0, sizeof(cfg));
    cfg.cs = m_cellSize;
    cfg.ch = m_cellHeight;
    cfg.walkableSlopeAngle = m_agentMaxSlope;
    cfg.walkableHeight = (int)ceilf(m_agentHeight / cfg.ch);
    cfg.walkableClimb = (int)floorf(m_agentMaxClimb / cfg.ch);
    cfg.walkableRadius = (int)ceilf(m_agentRadius / cfg.cs);
    cfg.maxEdgeLen = (int)(m_edgeMaxLen / m_cellSize);
    cfg.maxSimplificationError = m_edgeMaxError;
    cfg.minRegionArea = (int)rcSqr(m_regionMinSize);		// Note: area = size*size
    cfg.mergeRegionArea = (int)rcSqr(m_regionMergeSize);	// Note: area = size*size
    cfg.maxVertsPerPoly = (int)m_vertsPerPoly;
    cfg.tileSize = (int)m_tileSize;
    cfg.borderSize = cfg.walkableRadius + 3; // Reserve enough padding.
    cfg.width = cfg.tileSize + cfg.borderSize*2;
    cfg.height = cfg.tileSize + cfg.borderSize*2;
    cfg.detailSampleDist = m_detailSampleDist < 0.9f ? 0 : m_cellSize * m_detailSampleDist;
    cfg.detailSampleMaxError = m_cellHeight * m_detailSampleMaxError;
    rcVcopy(cfg.bmin, bmin);
    rcVcopy(cfg.bmax, bmax);

    // Tile cache params.
    dtTileCacheParams tcparams;
    memset(&tcparams, 0, sizeof(tcparams));
    rcVcopy(tcparams.orig, bmin);
    tcparams.cs = m_cellSize;
    tcparams.ch = m_cellHeight;
    tcparams.width = (int)m_tileSize;
    tcparams.height = (int)m_tileSize;
    tcparams.walkableHeight = m_agentHeight;
    tcparams.walkableRadius = m_agentRadius;
    tcparams.walkableClimb = m_agentMaxClimb;
    tcparams.maxSimplificationError = m_edgeMaxError;
    tcparams.maxTiles = tw*th*EXPECTED_LAYERS_PER_TILE;
    tcparams.maxObstacles = 128;

    dtFreeTileCache(m_tileCache);

    m_tileCache = dtAllocTileCache();
    if (!m_tileCache)
    {
        m_ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not allocate tile cache.");
        return false;
    }
    status = m_tileCache->init(&tcparams, m_talloc, m_tcomp, m_tmproc);
    if (dtStatusFailed(status))
    {
        m_ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not init tile cache.");
        return false;
    }

    dtFreeNavMesh(m_navMesh);

    m_navMesh = dtAllocNavMesh();
    if (!m_navMesh)
    {
        m_ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not allocate navmesh.");
        return false;
    }

    dtNavMeshParams params;
    memset(&params, 0, sizeof(params));
    rcVcopy(params.orig, bmin);
    params.tileWidth = m_tileSize*m_cellSize;
    params.tileHeight = m_tileSize*m_cellSize;
    params.maxTiles = m_maxTiles;
    params.maxPolys = m_maxPolysPerTile;

    status = m_navMesh->init(&params);
    if (dtStatusFailed(status))
    {
        m_ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not init navmesh.");
        return false;
    }

    status = m_navQuery->init(m_navMesh, 2048);
    if (dtStatusFailed(status))
//.........这里部分代码省略.........

void Sample_TempObstacles::handleRender()
{
    if (!m_geom || !m_geom->getMesh())
        return;

    DebugDrawGL dd;

    const float texScale = 1.0f / (m_cellSize * 10.0f);

    // Draw mesh
    if (m_drawMode != DRAWMODE_NAVMESH_TRANS)
    {
        // Draw mesh
        duDebugDrawTriMeshSlope(&dd, m_geom->getMesh()->getVerts(), m_geom->getMesh()->getVertCount(),
                                m_geom->getMesh()->getTris(), m_geom->getMesh()->getNormals(), m_geom->getMesh()->getTriCount(),
                                m_agentMaxSlope, texScale);
        m_geom->drawOffMeshConnections(&dd);
    }

    if (m_tileCache && m_drawMode == DRAWMODE_CACHE_BOUNDS)
        drawTiles(&dd, m_tileCache);

    if (m_tileCache)
        drawObstacles(&dd, m_tileCache);


    glDepthMask(GL_FALSE);

    // Draw bounds
    const float* bmin = m_geom->getNavMeshBoundsMin();
    const float* bmax = m_geom->getNavMeshBoundsMax();
    duDebugDrawBoxWire(&dd, bmin[0],bmin[1],bmin[2], bmax[0],bmax[1],bmax[2], duRGBA(255,255,255,128), 1.0f);

    // Tiling grid.
    int gw = 0, gh = 0;
    rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);
    const int tw = (gw + (int)m_tileSize-1) / (int)m_tileSize;
    const int th = (gh + (int)m_tileSize-1) / (int)m_tileSize;
    const float s = m_tileSize*m_cellSize;
    duDebugDrawGridXZ(&dd, bmin[0],bmin[1],bmin[2], tw,th, s, duRGBA(0,0,0,64), 1.0f);

    if (m_navMesh && m_navQuery &&
            (m_drawMode == DRAWMODE_NAVMESH ||
             m_drawMode == DRAWMODE_NAVMESH_TRANS ||
             m_drawMode == DRAWMODE_NAVMESH_BVTREE ||
             m_drawMode == DRAWMODE_NAVMESH_NODES ||
             m_drawMode == DRAWMODE_NAVMESH_PORTALS ||
             m_drawMode == DRAWMODE_NAVMESH_INVIS))
    {
        if (m_drawMode != DRAWMODE_NAVMESH_INVIS)
            duDebugDrawNavMeshWithClosedList(&dd, *m_navMesh, *m_navQuery, m_navMeshDrawFlags/*|DU_DRAWNAVMESH_COLOR_TILES*/);
        if (m_drawMode == DRAWMODE_NAVMESH_BVTREE)
            duDebugDrawNavMeshBVTree(&dd, *m_navMesh);
        if (m_drawMode == DRAWMODE_NAVMESH_PORTALS)
            duDebugDrawNavMeshPortals(&dd, *m_navMesh);
        if (m_drawMode == DRAWMODE_NAVMESH_NODES)
            duDebugDrawNavMeshNodes(&dd, *m_navQuery);
        duDebugDrawNavMeshPolysWithFlags(&dd, *m_navMesh, SAMPLE_POLYFLAGS_DISABLED, duRGBA(0,0,0,128));
    }


    glDepthMask(GL_TRUE);

    m_geom->drawConvexVolumes(&dd);

    if (m_tool)
        m_tool->handleRender();
    renderToolStates();

    glDepthMask(GL_TRUE);
}

dtNavMesh* buildMesh(InputGeom* geom, WCellBuildContext* wcellContext, int numCores)
{
	dtNavMesh* mesh = 0;

	if (!geom || !geom->getMesh())
	{
		CleanupAfterBuild();
		wcellContext->log(RC_LOG_ERROR, "buildTiledNavigation: No vertices and triangles.");
		return 0;
	}
	
	mesh = dtAllocNavMesh();
	if (!mesh)
	{
		CleanupAfterBuild();
		wcellContext->log(RC_LOG_ERROR, "buildTiledNavigation: Could not allocate navmesh.");
		return 0;
	}

	// setup some default parameters
	rcConfig cfg;
	memset(&cfg, 0, sizeof(rcConfig));
	const float agentHeight = 2.1f;				// most character toons are about this tall
	const float agentRadius = 0.6f;				// most character toons are about this big around
	const float agentClimb = 1.0f;				// character toons can step up this far. Seems ridiculously high ...
	const float tileSize = 1600.0f/3.0f/16.0f;	// The size of one chunk

	cfg.cs = 0.1f;										// cell size is a sort of resolution -> the bigger the faster
	cfg.ch = 0.05f;										// cell height -> distance from mesh to ground, if too low, recast will not build essential parts of the mesh for some reason
	cfg.walkableSlopeAngle = 50.0f;						// max climbable slope, bigger values won't make much of a change
	cfg.walkableHeight = (int)ceilf(agentHeight/cfg.ch);// minimum space to ceiling
	cfg.walkableClimb = (int)floorf(agentClimb/cfg.ch); // how high the agent can climb in one step
	cfg.walkableRadius = (int)ceilf(agentRadius/cfg.cs);// minimum distance to objects
	cfg.tileSize = (int)(tileSize/cfg.cs + 0.5f);
	cfg.maxEdgeLen = cfg.tileSize/2;;
	cfg.borderSize = cfg.walkableRadius + 3;
	cfg.width = cfg.tileSize + cfg.borderSize*2;
	cfg.height = cfg.tileSize + cfg.borderSize*2;	
	cfg.maxSimplificationError = 1.3f;
	cfg.minRegionArea = (int)rcSqr(8);		// Note: area = size*size
	cfg.mergeRegionArea = (int)rcSqr(20);	// Note: area = size*size
	cfg.maxVertsPerPoly = 3;
	cfg.detailSampleDist = cfg.cs * 9;
	cfg.detailSampleMaxError = cfg.ch * 1.0f;

	// default calculations - for some reason not included in basic recast
	const float* bmin = geom->getMeshBoundsMin();
	const float* bmax = geom->getMeshBoundsMax();
	
	int gw = 0, gh = 0;
	rcCalcGridSize(bmin, bmax, cfg.cs, &gw, &gh);
	const int ts = cfg.tileSize;
	const int tw = (gw + ts-1) / ts;
	const int th = (gh + ts-1) / ts;

	// Max tiles and max polys affect how the tile IDs are caculated.
	// There are 22 bits available for identifying a tile and a polygon.
	int tileBits = rcMin((int)ilog2(nextPow2(tw*th)), 14);
	if (tileBits > 14) tileBits = 14;
	int polyBits = 22 - tileBits;
	int maxTiles = 1 << tileBits;
	int maxPolysPerTile = 1 << polyBits;

	dtNavMeshParams params;
	rcVcopy(params.orig, geom->getMeshBoundsMin());
	params.tileWidth = cfg.tileSize * cfg.cs;
	params.tileHeight = cfg.tileSize * cfg.cs;
	params.maxTiles = maxTiles;
	params.maxPolys = maxPolysPerTile;
	
	dtStatus status;
	
	status = mesh->init(&params);
	if (dtStatusFailed(status))
	{
		CleanupAfterBuild();
		wcellContext->log(RC_LOG_ERROR, "buildTiledNavigation: Could not init navmesh.");
		return 0;
	}
	
	// start building
	const float tcs = cfg.tileSize*cfg.cs;
	wcellContext->startTimer(RC_TIMER_TEMP);
	
	TileAdder Adder;

	dispatcher.Reset();
	dispatcher.maxHeight = th;
	dispatcher.maxWidth = tw;

	int numThreads = 0;
	numThreads = std::min(2*numCores, 8);

	boost::thread *threads[8];
	for(int i = 0; i < numThreads; ++i)
	{
		QuadrantTiler newTiler;
		newTiler.geom = geom;
		newTiler.cfg = cfg;
		newTiler.ctx = *wcellContext;
//.........这里部分代码省略.........

/*!
	Build a NAVIGATION mesh from an OBJ mesh index. Usually this OBJMESH is either a collision map
	or a mesh that have been built especially for navigation.
	
	\param[in,out] navigation A valid NAVIGATION structure pointer.
	\param[in] obj A valid OBJ structure pointer.
	\param[in] mesh_index The mesh index of the OBJMESH to use to create the NAVIGATION mesh.
	
	\return Return 1 if the NAVIGATION mesh have been generated successfully, else this function will return 0.
*/
unsigned char NAVIGATION_build( NAVIGATION *navigation, OBJ *obj, unsigned int mesh_index )
{
	unsigned int i = 0,
				 j = 0,
				 k = 0,
				 triangle_count = 0;
	
	int *indices = NULL;
	
	OBJMESH *objmesh = &obj->objmesh[ mesh_index ];
	
	vec3 *vertex_array = ( vec3 * ) malloc( objmesh->n_objvertexdata * sizeof( vec3 ) ),
		 *vertex_start = vertex_array;

	rcHeightfield *rcheightfield;
	
	rcCompactHeightfield *rccompactheightfield;
	
	rcContourSet *rccontourset;

	rcPolyMesh *rcpolymesh;
	
	rcPolyMeshDetail *rcpolymeshdetail;
	
	
	while( i != objmesh->n_objvertexdata )
	{ 
		memcpy( vertex_array,
				&obj->indexed_vertex[ objmesh->objvertexdata[ i ].vertex_index ],
				sizeof( vec3 ) );
				
		vec3_to_recast( vertex_array );
		
		++vertex_array;						
		++i;
	}
	
	
	i = 0;
	while( i != objmesh->n_objtrianglelist )
	{
		triangle_count += objmesh->objtrianglelist[ i ].n_indice_array;
	
		indices = ( int * ) realloc( indices, triangle_count * sizeof( int ) );
	
		j = 0;
		while( j != objmesh->objtrianglelist[ i ].n_indice_array )
		{
			indices[ k ] = objmesh->objtrianglelist[ i ].indice_array[ j ];
		
			++k;
			++j;
		}

		++i;
	}
	
	triangle_count /= 3;
	
	rcConfig rcconfig;

	memset( &rcconfig, 0, sizeof( rcConfig ) );
	
	rcconfig.cs						= navigation->navigationconfiguration.cell_size;
	rcconfig.ch						= navigation->navigationconfiguration.cell_height;
	rcconfig.walkableHeight			= ( int )ceilf ( navigation->navigationconfiguration.agent_height / rcconfig.ch );
	rcconfig.walkableRadius			= ( int )ceilf ( navigation->navigationconfiguration.agent_radius / rcconfig.cs );
	rcconfig.walkableClimb			= ( int )floorf( navigation->navigationconfiguration.agent_max_climb / rcconfig.ch );
	rcconfig.walkableSlopeAngle		= navigation->navigationconfiguration.agent_max_slope;
	rcconfig.minRegionSize			= ( int )rcSqr( navigation->navigationconfiguration.region_min_size );
	rcconfig.mergeRegionSize		= ( int )rcSqr( navigation->navigationconfiguration.region_merge_size );
	rcconfig.maxEdgeLen				= ( int )( navigation->navigationconfiguration.edge_max_len / rcconfig.cs );
	rcconfig.maxSimplificationError = navigation->navigationconfiguration.edge_max_error;
	rcconfig.maxVertsPerPoly		= ( int )navigation->navigationconfiguration.vert_per_poly;
	rcconfig.detailSampleDist		= rcconfig.cs * navigation->navigationconfiguration.detail_sample_dst;
	rcconfig.detailSampleMaxError   = rcconfig.ch * navigation->navigationconfiguration.detail_sample_max_error;
			
	
	rcCalcBounds( ( float * )vertex_start,
				  objmesh->n_objvertexdata,
				  rcconfig.bmin,
				  rcconfig.bmax );
	
	
	rcCalcGridSize(  rcconfig.bmin,
					 rcconfig.bmax,
					 rcconfig.cs,
					&rcconfig.width,
					&rcconfig.height );

//.........这里部分代码省略.........

PDT_NAV_MESH gkRecast::createNavMesh(PMESHDATA meshData, const Config& config)
{
	if (!meshData.get())
		return PDT_NAV_MESH(0);

	rcConfig cfg;

	cfg.cs = config.CELL_SIZE;
	cfg.ch = config.CELL_HEIGHT;

	GK_ASSERT(cfg.ch && "cfg.ch cannot be zero");
	GK_ASSERT(cfg.ch && "cfg.ch cannot be zero");

	cfg.walkableSlopeAngle = config.AGENT_MAX_SLOPE;
	cfg.walkableHeight = (int)ceilf(config.AGENT_HEIGHT / cfg.ch);
	cfg.walkableClimb = (int)ceilf(config.AGENT_MAX_CLIMB / cfg.ch);
	cfg.walkableRadius = (int)ceilf(config.AGENT_RADIUS / cfg.cs);
	cfg.maxEdgeLen = (int)(config.EDGE_MAX_LEN / cfg.cs);
	cfg.maxSimplificationError = config.EDGE_MAX_ERROR;
	cfg.minRegionSize = (int)rcSqr(config.REGION_MIN_SIZE);
	cfg.mergeRegionSize = (int)rcSqr(config.REGION_MERGE_SIZE);
	cfg.maxVertsPerPoly = gkMin(config.VERTS_PER_POLY, DT_VERTS_PER_POLYGON);
	cfg.tileSize = config.TILE_SIZE;
	cfg.borderSize = cfg.walkableRadius + 4; // Reserve enough padding.
	cfg.detailSampleDist = config.DETAIL_SAMPLE_DIST < 0.9f ? 0 : cfg.cs * config.DETAIL_SAMPLE_DIST;
	cfg.detailSampleMaxError = cfg.ch * config.DETAIL_SAMPLE_ERROR;

	if (!meshData->getVertCount())
		return PDT_NAV_MESH(0);

	gkScalar bmin[3], bmax[3];

	const gkScalar* verts = meshData->getVerts();
	int nverts = meshData->getVertCount();
	const int* tris = meshData->getTris();
	const gkScalar* trinorms = meshData->getNormals();
	int ntris = meshData->getTriCount();

	rcCalcBounds(verts, nverts, bmin, bmax);

	//
	// Step 1. Initialize build config.
	//

	// Set the area where the navigation will be build.
	// Here the bounds of the input mesh are used, but the
	// area could be specified by an user defined box, etc.
	rcVcopy(cfg.bmin, bmin);
	rcVcopy(cfg.bmax, bmax);
	rcCalcGridSize(cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height);

	rcBuildTimes m_buildTimes;
	// Reset build times gathering.
	memset(&m_buildTimes, 0, sizeof(m_buildTimes));
	rcSetBuildTimes(&m_buildTimes);

	// Start the build process.
	rcTimeVal totStartTime = rcGetPerformanceTimer();

	//gkPrintf("Building navigation:");
	//gkPrintf(" - %d x %d cells", cfg.width, cfg.height);
	//gkPrintf(" - %.1fK verts, %.1fK tris", nverts/1000.0f, ntris/1000.0f);

	//
	// Step 2. Rasterize input polygon soup.
	//

	// Allocate voxel heighfield where we rasterize our input data to.
	rcHeightfield heightField;

	if (!rcCreateHeightfield(heightField, cfg.width, cfg.height, cfg.bmin, cfg.bmax, cfg.cs, cfg.ch))
	{
		gkPrintf("buildNavigation: Could not create solid heightfield.");
		return PDT_NAV_MESH(0);
	}

	{
		// 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.

		utArray<unsigned char> triflags;
		triflags.resize(ntris);

		// Find triangles which are walkable based on their slope and rasterize them.
		// If your input data is multiple meshes, you can transform them here, calculate
		// the flags for each of the meshes and rasterize them.
		memset(triflags.ptr(), 0, ntris * sizeof(unsigned char));
		rcMarkWalkableTriangles(cfg.walkableSlopeAngle, verts, nverts, tris, ntris, triflags.ptr());
		rcRasterizeTriangles(verts, nverts, tris, triflags.ptr(), ntris, heightField);
	}

	//
	// Step 3. Filter walkables surfaces.
	//

	// Once all geoemtry 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.
	rcFilterLedgeSpans(cfg.walkableHeight, cfg.walkableClimb, heightField);
//.........这里部分代码省略.........

    void MapBuilder::buildMoveMapTile(uint32 mapID, uint32 tileX, uint32 tileY,
        MeshData &meshData, float bmin[3], float bmax[3],
        dtNavMesh* navMesh)
    {
        // console output
        std::string tileString = Trinity::StringFormat("[Map %04u] [%02i,%02i]: ", mapID, tileX, tileY);
        printf("%s Building movemap tiles...\n", tileString.c_str());

        IntermediateValues iv;

        float* tVerts = meshData.solidVerts.getCArray();
        int tVertCount = meshData.solidVerts.size() / 3;
        int* tTris = meshData.solidTris.getCArray();
        int tTriCount = meshData.solidTris.size() / 3;

        float* lVerts = meshData.liquidVerts.getCArray();
        int lVertCount = meshData.liquidVerts.size() / 3;
        int* lTris = meshData.liquidTris.getCArray();
        int lTriCount = meshData.liquidTris.size() / 3;
        uint8* lTriFlags = meshData.liquidType.getCArray();

        // these are WORLD UNIT based metrics
        // this are basic unit dimentions
        // value have to divide GRID_SIZE(533.3333f) ( aka: 0.5333, 0.2666, 0.3333, 0.1333, etc )
        const static float BASE_UNIT_DIM = m_bigBaseUnit ? 0.5333333f : 0.2666666f;

        // All are in UNIT metrics!
        const static int VERTEX_PER_MAP = int(GRID_SIZE/BASE_UNIT_DIM + 0.5f);
        const static int VERTEX_PER_TILE = m_bigBaseUnit ? 40 : 80; // must divide VERTEX_PER_MAP
        const static int TILES_PER_MAP = VERTEX_PER_MAP/VERTEX_PER_TILE;

        rcConfig config;
        memset(&config, 0, sizeof(rcConfig));

        rcVcopy(config.bmin, bmin);
        rcVcopy(config.bmax, bmax);

        config.maxVertsPerPoly = DT_VERTS_PER_POLYGON;
        config.cs = BASE_UNIT_DIM;
        config.ch = BASE_UNIT_DIM;
        config.walkableSlopeAngle = m_maxWalkableAngle;
        config.tileSize = VERTEX_PER_TILE;
        config.walkableRadius = m_bigBaseUnit ? 1 : 2;
        config.borderSize = config.walkableRadius + 3;
        config.maxEdgeLen = VERTEX_PER_TILE + 1;        // anything bigger than tileSize
        config.walkableHeight = m_bigBaseUnit ? 3 : 6;
        // a value >= 3|6 allows npcs to walk over some fences
        // a value >= 4|8 allows npcs to walk over all fences
        config.walkableClimb = m_bigBaseUnit ? 4 : 8;
        config.minRegionArea = rcSqr(60);
        config.mergeRegionArea = rcSqr(50);
        config.maxSimplificationError = 1.8f;           // eliminates most jagged edges (tiny polygons)
        config.detailSampleDist = config.cs * 64;
        config.detailSampleMaxError = config.ch * 2;

        // this sets the dimensions of the heightfield - should maybe happen before border padding
        rcCalcGridSize(config.bmin, config.bmax, config.cs, &config.width, &config.height);

        // allocate subregions : tiles
        Tile* tiles = new Tile[TILES_PER_MAP * TILES_PER_MAP];

        // Initialize per tile config.
        rcConfig tileCfg = config;
        tileCfg.width = config.tileSize + config.borderSize*2;
        tileCfg.height = config.tileSize + config.borderSize*2;

        // merge per tile poly and detail meshes
        rcPolyMesh** pmmerge = new rcPolyMesh*[TILES_PER_MAP * TILES_PER_MAP];
        rcPolyMeshDetail** dmmerge = new rcPolyMeshDetail*[TILES_PER_MAP * TILES_PER_MAP];
        int nmerge = 0;
        // build all tiles
        for (int y = 0; y < TILES_PER_MAP; ++y)
        {
            for (int x = 0; x < TILES_PER_MAP; ++x)
            {
                Tile& tile = tiles[x + y * TILES_PER_MAP];

                // Calculate the per tile bounding box.
                tileCfg.bmin[0] = config.bmin[0] + float(x*config.tileSize - config.borderSize)*config.cs;
                tileCfg.bmin[2] = config.bmin[2] + float(y*config.tileSize - config.borderSize)*config.cs;
                tileCfg.bmax[0] = config.bmin[0] + float((x+1)*config.tileSize + config.borderSize)*config.cs;
                tileCfg.bmax[2] = config.bmin[2] + float((y+1)*config.tileSize + config.borderSize)*config.cs;

                // build heightfield
                tile.solid = rcAllocHeightfield();
                if (!tile.solid || !rcCreateHeightfield(m_rcContext, *tile.solid, tileCfg.width, tileCfg.height, tileCfg.bmin, tileCfg.bmax, tileCfg.cs, tileCfg.ch))
                {
                    printf("%s Failed building heightfield!            \n", tileString.c_str());
                    continue;
                }

                // mark all walkable tiles, both liquids and solids
                unsigned char* triFlags = new unsigned char[tTriCount];
                memset(triFlags, NAV_GROUND, tTriCount*sizeof(unsigned char));
                rcClearUnwalkableTriangles(m_rcContext, tileCfg.walkableSlopeAngle, tVerts, tVertCount, tTris, tTriCount, triFlags);
                rcRasterizeTriangles(m_rcContext, tVerts, tVertCount, tTris, triFlags, tTriCount, *tile.solid, config.walkableClimb);
                delete[] triFlags;

                rcFilterLowHangingWalkableObstacles(m_rcContext, config.walkableClimb, *tile.solid);
                rcFilterLedgeSpans(m_rcContext, tileCfg.walkableHeight, tileCfg.walkableClimb, *tile.solid);
//.........这里部分代码省略.........