rcCompactHeightfield::~rcCompactHeightfield()
{
	rcFree(cells);
	rcFree(spans);
	rcFree(dist);
	rcFree(areas);
}

void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh)
{
	if (!dmesh) return;
	rcFree(dmesh->meshes);
	rcFree(dmesh->verts);
	rcFree(dmesh->tris);
	rcFree(dmesh);
}

void rcFreeClusterSet(rcClusterSet* clusters)
{
	if (!clusters) return;
	rcFree(clusters->center);
	rcFree(clusters->nlinks);
	rcFree(clusters->links);
	rcFree(clusters);
}

void rcFreeCompactHeightfield(rcCompactHeightfield* chf)
{
	if (!chf) return;
	rcFree(chf->cells);
	rcFree(chf->spans);
	rcFree(chf->dist);
	rcFree(chf->areas);
	rcFree(chf);
}

void rcFreePolyMesh(rcPolyMesh* pmesh)
{
	if (!pmesh) return;
	rcFree(pmesh->verts);
	rcFree(pmesh->polys);
	rcFree(pmesh->regs);
	rcFree(pmesh->areaMasks);
	rcFree(pmesh);
}

void rcFreeContourSet(rcContourSet* cset)
{
	if (!cset) return;
	for (int i = 0; i < cset->nconts; ++i)
	{
		rcFree(cset->conts[i].verts);
		rcFree(cset->conts[i].rverts);
	}
	rcFree(cset->conts);
	rcFree(cset);
}

void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset)
{
	if (!lset) return;
	for (int i = 0; i < lset->nlayers; ++i)
	{
		rcFree(lset->layers[i].heights);
		rcFree(lset->layers[i].areas);
		rcFree(lset->layers[i].cons);
	}
	rcFree(lset->layers);
	rcFree(lset);
}

/// @par
/// 
/// This is usually the second to the last step in creating a fully built
/// compact heightfield.  This step is required before regions are built
/// using #rcBuildRegions or #rcBuildRegionsMonotone.
/// 
/// After this step, the distance data is available via the rcCompactHeightfield::maxDistance
/// and rcCompactHeightfield::dist fields.
///
/// @see rcCompactHeightfield, rcBuildRegions, rcBuildRegionsMonotone
bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf)
{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD);
    
    if (chf.dist)
    {
        rcFree(chf.dist);
        chf.dist = 0;
    }
    
    unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!src)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'src' (%d).", chf.spanCount);
        return false;
    }
    unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!dst)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'dst' (%d).", chf.spanCount);
        rcFree(src);
        return false;
    }
    
    unsigned short maxDist = 0;

    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
    
    calculateDistanceField(chf, src, maxDist);
    chf.maxDistance = maxDist;
    
    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
    
    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);
    
    // Blur
    if (boxBlur(chf, 1, src, dst) != src)
        rcSwap(src, dst);
    
    // Store distance.
    chf.dist = src;
    
    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);

    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD);
    
    rcFree(dst);
    
    return true;
}

void rcFreeHeightField(rcHeightfield* hf)
{
	if (!hf) return;
	// Delete span array.
	rcFree(hf->spans);
	// Delete span pools.
	while (hf->pools)
	{
		rcSpanPool* next = hf->pools->next;
		rcFree(hf->pools);
		hf->pools = next;
	}
	rcFree(hf);
}

static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
{
	const int maxVerts = ca.nverts + cb.nverts + 2;
	int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM);
	if (!verts)
		return false;

	int nv = 0;

	// Copy contour A.
	for (int i = 0; i <= ca.nverts; ++i)
	{
		int* dst = &verts[nv*4];
		const int* src = &ca.verts[((ia+i)%ca.nverts)*4];
		dst[0] = src[0];
		dst[1] = src[1];
		dst[2] = src[2];
		dst[3] = src[3];
		nv++;
	}

	// Copy contour B
	for (int i = 0; i <= cb.nverts; ++i)
	{
		int* dst = &verts[nv*4];
		const int* src = &cb.verts[((ib+i)%cb.nverts)*4];
		dst[0] = src[0];
		dst[1] = src[1];
		dst[2] = src[2];
		dst[3] = src[3];
		nv++;
	}
	
	rcFree(ca.verts);
	ca.verts = verts;
	ca.nverts = nv;

	rcFree(cb.verts);
	cb.verts = 0;
	cb.nverts = 0;
	
	return true;
}

/// @par
///
/// Using this method ensures the array is at least large enough to hold
/// the specified number of elements.  This can improve performance by
/// avoiding auto-resizing during use.
void rcIntArray::doResize(int n)
{
	if (!m_cap) m_cap = n;
	while (m_cap < n) m_cap *= 2;
	int* newData = (int*)rcAlloc(m_cap*sizeof(int), RC_ALLOC_TEMP);
	rcAssert(newData);
	if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int));
	rcFree(m_data);
	m_data = newData;
}

    EXPORT_API void nmcsFreeSetData(rcContourSet* cset)
    {
        if (!cset || !cset->conts)
            return;

	    for (int i = 0; i < cset->nconts; ++i)
	    {
		    rcFree(cset->conts[i].verts);
		    rcFree(cset->conts[i].rverts);
	    }

	    rcFree(cset->conts);

        cset->ch = 0;
        cset->borderSize = 0;
        cset->conts = 0;
        cset->cs = 0;
        cset->height = 0;
        cset->nconts = 0;
        cset->width = 0;

        memset(&cset->bmin, 0, sizeof(float) * 6);
    }

/// @par
/// 
/// This is usually the second to the last step in creating a fully built
/// compact heightfield.  This step is required before regions are built
/// using #rcBuildRegions or #rcBuildRegionsMonotone.
/// 
/// After this step, the distance data is available via the rcCompactHeightfield::maxDistance
/// and rcCompactHeightfield::dist fields.
///
/// @see rcCompactHeightfield, rcBuildRegions, rcBuildRegionsMonotone
bool rcBuildDistanceField(rcCompactHeightfield& chf)
{
	if (chf.dist)
	{
		rcFree(chf.dist);
		chf.dist = 0;
	}
	
	unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
	if (!src)
	{
		return false;
	}
	unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
	if (!dst)
	{
		rcFree(src);
		return false;
	}
	
	unsigned short maxDist = 0;

	calculateDistanceField(chf, src, maxDist);
	chf.maxDistance = maxDist;
	
	// Blur
	if (boxBlur(chf, 1, src, dst) != src)
		rcSwap(src, dst);
	
	// Store distance.
	chf.dist = src;
	
	rcFree(dst);
	
	return true;
}

bool rcBuildHeightfieldLayersChunky(rcContext* ctx, rcCompactHeightfield& chf,
									const int borderSize, const int walkableHeight,
									const int chunkSize,
									rcHeightfieldLayerSet& lset)
{
	rcAssert(ctx);

	ctx->startTimer(RC_TIMER_BUILD_LAYERS);

	rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
	if (!srcReg)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount);
		return false;
	}
	memset(srcReg,0xff,sizeof(unsigned short)*chf.spanCount);

	rcLayerRegionMonotone* regs = NULL;
	int nregs = 0;

	const bool bHasRegions = CollectLayerRegionsChunky(ctx, chf, borderSize, chunkSize, srcReg, regs, nregs);
	if (!bHasRegions)
	{
		return false;
	}

	const bool bHasSaved = SplitAndStoreLayerRegions(ctx, chf, borderSize, walkableHeight, srcReg, regs, nregs, lset);
	rcFree(regs);

	if (!bHasSaved)
	{
		return false;
	}

	ctx->stopTimer(RC_TIMER_BUILD_LAYERS);

	return true;
}

void rcFreeHeightField(rcHeightfield* hf)
{
	if (!hf) return;
	// Delete span array.
	rcFree(hf->spans);
	// Delete span pools.
	while (hf->pools)
	{
		rcSpanPool* next = hf->pools->next;
		rcFree(hf->pools);
		hf->pools = next;
	}
#if EPIC_ADDITION_USE_NEW_RECAST_RASTERIZER
	rcFree(hf->EdgeHits);
	rcFree(hf->RowExt);
	rcFree(hf->tempspans);
#endif
	rcFree(hf);
}

//.........这里部分代码省略.........
				const navAreaMask areaMask = chf.areaMasks[ i ];
				
				verts.resize(0);
				simplified.resize(0);

				ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
				walkContour(x, y, i, chf, flags, verts);
				ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);

				ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
				simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags);
				removeDegenerateSegments(simplified);
				ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
				

				// Store region->contour remap info.
				// Create contour.
				if (simplified.size()/4 >= 3)
				{
					if (cset.nconts >= maxContours)
					{
						// Allocate more contours.
						// This happens when a region has holes.
						const int oldMax = maxContours;
						maxContours *= 2;
						rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
						for (int j = 0; j < cset.nconts; ++j)
						{
							newConts[j] = cset.conts[j];
							// Reset source pointers to prevent data deletion.
							cset.conts[j].verts = 0;
							cset.conts[j].rverts = 0;
						}
						rcFree(cset.conts);
						cset.conts = newConts;
					
						ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours);
					}
					
					rcContour* cont = &cset.conts[cset.nconts++];
					
					cont->nverts = simplified.size()/4;
					cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM);
					if (!cont->verts)
					{
						ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts);
						return false;
					}
					memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
					if (borderSize > 0)
					{
						// If the heightfield was build with bordersize, remove the offset.
						for (int j = 0; j < cont->nverts; ++j)
						{
							int* v = &cont->verts[j*4];
							v[0] -= borderSize;
							v[2] -= borderSize;
						}
					}
					
					cont->nrverts = verts.size()/4;
					cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM);
					if (!cont->rverts)
					{
						ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts);
						return false;

//.........这里部分代码省略.........
		while (stack.size() > 0)
		{
			// Pop front
			rcRegion& reg = regions[stack[0]];
			for (int j = 0; j < stack.size()-1; ++j)
				stack[j] = stack[j+1];
			stack.resize(stack.size()-1);
			
			const int ncons = (int)reg.connections.size();
			for (int j = 0; j < ncons; ++j)
			{
				const int nei = reg.connections[j];
				rcRegion& regn = regions[nei];
				// Skip already visited.
				if (regn.id != 0)
					continue;
				// Skip if the neighbour is overlapping root region.
				bool overlap = false;
				for (int k = 0; k < root.floors.size(); k++)
				{
					if (root.floors[k] == nei)
					{
						overlap = true;
						break;
					}
				}
				if (overlap)
					continue;
					
				// Deepen
				stack.push(nei);
					
				// Mark layer id
				regn.id = layerId;
				// Merge current layers to root.
				for (int k = 0; k < regn.floors.size(); ++k)
					addUniqueFloorRegion(root, regn.floors[k]);
				root.ymin = rcMin(root.ymin, regn.ymin);
				root.ymax = rcMax(root.ymax, regn.ymax);
				root.spanCount += regn.spanCount;
				regn.spanCount = 0;
				root.connectsToBorder = root.connectsToBorder || regn.connectsToBorder;
			}
		}
		
		layerId++;
	}
	
	// Remove small regions
	for (int i = 0; i < nreg; ++i)
	{
		if (regions[i].spanCount > 0 && regions[i].spanCount < minRegionArea && !regions[i].connectsToBorder)
		{
			unsigned short reg = regions[i].id;
			for (int j = 0; j < nreg; ++j)
				if (regions[j].id == reg)
					regions[j].id = 0;
		}
	}
	
	// Compress region Ids.
	for (int i = 0; i < nreg; ++i)
	{
		regions[i].remap = false;
		if (regions[i].id == 0) continue;				// Skip nil regions.
		if (regions[i].id & RC_BORDER_REG) continue;    // Skip external regions.
		regions[i].remap = true;
	}
	
	unsigned short regIdGen = 0;
	for (int i = 0; i < nreg; ++i)
	{
		if (!regions[i].remap)
			continue;
		unsigned short oldId = regions[i].id;
		unsigned short newId = ++regIdGen;
		for (int j = i; j < nreg; ++j)
		{
			if (regions[j].id == oldId)
			{
				regions[j].id = newId;
				regions[j].remap = false;
			}
		}
	}
	maxRegionId = regIdGen;
	
	// Remap regions.
	for (int i = 0; i < chf.spanCount; ++i)
	{
		if ((srcReg[i] & RC_BORDER_REG) == 0)
			srcReg[i] = regions[srcReg[i]].id;
	}
	
	for (int i = 0; i < nreg; ++i)
		regions[i].~rcRegion();
	rcFree(regions);
	
	return true;
}

static bool buildMeshAdjacency(unsigned short* polys, const int npolys,
							   const int nverts, const int vertsPerPoly)
{
	// Based on code by Eric Lengyel from:
	// http://www.terathon.com/code/edges.php
	
	int maxEdgeCount = npolys*vertsPerPoly;
	unsigned short* firstEdge = (unsigned short*)rcAlloc(sizeof(unsigned short)*(nverts + maxEdgeCount), RC_ALLOC_TEMP);
	if (!firstEdge)
		return false;
	unsigned short* nextEdge = firstEdge + nverts;
	int edgeCount = 0;
	
	rcEdge* edges = (rcEdge*)rcAlloc(sizeof(rcEdge)*maxEdgeCount, RC_ALLOC_TEMP);
	if (!edges)
	{
		rcFree(firstEdge);
		return false;
	}
	
	for (int i = 0; i < nverts; i++)
		firstEdge[i] = RC_MESH_NULL_IDX;
	
	for (int i = 0; i < npolys; ++i)
	{
		unsigned short* t = &polys[i*vertsPerPoly*2];
		for (int j = 0; j < vertsPerPoly; ++j)
		{
			unsigned short v0 = t[j];
			unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
			if (v0 < v1)
			{
				rcEdge& edge = edges[edgeCount];
				edge.vert[0] = v0;
				edge.vert[1] = v1;
				edge.poly[0] = (unsigned short)i;
				edge.polyEdge[0] = (unsigned short)j;
				edge.poly[1] = (unsigned short)i;
				edge.polyEdge[1] = 0;
				// Insert edge
				nextEdge[edgeCount] = firstEdge[v0];
				firstEdge[v0] = (unsigned short)edgeCount;
				edgeCount++;
			}
		}
	}
	
	for (int i = 0; i < npolys; ++i)
	{
		unsigned short* t = &polys[i*vertsPerPoly*2];
		for (int j = 0; j < vertsPerPoly; ++j)
		{
			unsigned short v0 = t[j];
			unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
			if (v0 > v1)
			{
				for (unsigned short e = firstEdge[v1]; e != RC_MESH_NULL_IDX; e = nextEdge[e])
				{
					rcEdge& edge = edges[e];
					if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
					{
						edge.poly[1] = (unsigned short)i;
						edge.polyEdge[1] = (unsigned short)j;
						break;
					}
				}
			}
		}
	}
	
	// Store adjacency
	for (int i = 0; i < edgeCount; ++i)
	{
		const rcEdge& e = edges[i];
		if (e.poly[0] != e.poly[1])
		{
			unsigned short* p0 = &polys[e.poly[0]*vertsPerPoly*2];
			unsigned short* p1 = &polys[e.poly[1]*vertsPerPoly*2];
			p0[vertsPerPoly + e.polyEdge[0]] = e.poly[1];
			p1[vertsPerPoly + e.polyEdge[1]] = e.poly[0];
		}
	}
	
	rcFree(firstEdge);
	rcFree(edges);
	
	return true;
}

bool rcMedianFilterWalkableArea(rcCompactHeightfield& chf)
{
	const int w = chf.width;
	const int h = chf.height;
	
	rcTimeVal startTime = rcGetPerformanceTimer();
	
	unsigned char* areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
	if (!areas)
		return false;
	
	// Init distance.
	memset(areas, 0xff, sizeof(unsigned char)*chf.spanCount);
	
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			const rcCompactCell& c = chf.cells[x+y*w];
			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
			{
				const rcCompactSpan& s = chf.spans[i];
				if (chf.areas[i] == RC_NULL_AREA)
				{
					areas[i] = chf.areas[i];
					continue;
				}
				
				unsigned char nei[9];
				for (int j = 0; j < 9; ++j)
					nei[j] = chf.areas[i];
				
				for (int dir = 0; dir < 4; ++dir)
				{
					if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
					{
						const int ax = x + rcGetDirOffsetX(dir);
						const int ay = y + rcGetDirOffsetY(dir);
						const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
						if (chf.areas[ai] != RC_NULL_AREA)
							nei[dir*2+0] = chf.areas[ai];
						
						const rcCompactSpan& as = chf.spans[ai];
						const int dir2 = (dir+1) & 0x3;
						if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
						{
							const int ax2 = ax + rcGetDirOffsetX(dir2);
							const int ay2 = ay + rcGetDirOffsetY(dir2);
							const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
							if (chf.areas[ai2] != RC_NULL_AREA)
								nei[dir*2+1] = chf.areas[ai2];
						}
					}
				}
				insertSort(nei, 9);
				areas[i] = nei[4];
			}
		}
	}
	
	memcpy(chf.areas, areas, sizeof(unsigned char)*chf.spanCount);
	
	rcFree(areas);

	rcTimeVal endTime = rcGetPerformanceTimer();
	
	if (rcGetBuildTimes())
	{
		rcGetBuildTimes()->filterMedian += rcGetDeltaTimeUsec(startTime, endTime);
	}
	
	return true;
}

//.........这里部分代码省略.........
    {
        mergeCount = 0;
        for (int i = 0; i < nreg; ++i)
        {
            rcRegion& reg = regions[i];
            if (reg.id == 0 || (reg.id & RC_BORDER_REG))
                continue;                       
            if (reg.spanCount == 0)
                continue;
            
            // Check to see if the region should be merged.
            if (reg.spanCount > mergeRegionSize && isRegionConnectedToBorder(reg))
                continue;
            
            // Small region with more than 1 connection.
            // Or region which is not connected to a border at all.
            // Find smallest neighbour region that connects to this one.
            int smallest = 0xfffffff;
            unsigned short mergeId = reg.id;
            for (int j = 0; j < reg.connections.size(); ++j)
            {
                if (reg.connections[j] & RC_BORDER_REG) continue;
                rcRegion& mreg = regions[reg.connections[j]];
                if (mreg.id == 0 || (mreg.id & RC_BORDER_REG)) continue;
                if (mreg.spanCount < smallest &&
                    canMergeWithRegion(reg, mreg) &&
                    canMergeWithRegion(mreg, reg))
                {
                    smallest = mreg.spanCount;
                    mergeId = mreg.id;
                }
            }
            // Found new id.
            if (mergeId != reg.id)
            {
                unsigned short oldId = reg.id;
                rcRegion& target = regions[mergeId];
                
                // Merge neighbours.
                if (mergeRegions(target, reg))
                {
                    // Fixup regions pointing to current region.
                    for (int j = 0; j < nreg; ++j)
                    {
                        if (regions[j].id == 0 || (regions[j].id & RC_BORDER_REG)) continue;
                        // If another region was already merged into current region
                        // change the nid of the previous region too.
                        if (regions[j].id == oldId)
                            regions[j].id = mergeId;
                        // Replace the current region with the new one if the
                        // current regions is neighbour.
                        replaceNeighbour(regions[j], oldId, mergeId);
                    }
                    mergeCount++;
                }
            }
        }
    }
    while (mergeCount > 0);
    
    // Compress region Ids.
    for (int i = 0; i < nreg; ++i)
    {
        regions[i].remap = false;
        if (regions[i].id == 0) continue;       // Skip nil regions.
        if (regions[i].id & RC_BORDER_REG) continue;    // Skip external regions.
        regions[i].remap = true;
    }
    
    unsigned short regIdGen = 0;
    for (int i = 0; i < nreg; ++i)
    {
        if (!regions[i].remap)
            continue;
        unsigned short oldId = regions[i].id;
        unsigned short newId = ++regIdGen;
        for (int j = i; j < nreg; ++j)
        {
            if (regions[j].id == oldId)
            {
                regions[j].id = newId;
                regions[j].remap = false;
            }
        }
    }
    maxRegionId = regIdGen;
    
    // Remap regions.
    for (int i = 0; i < chf.spanCount; ++i)
    {
        if ((srcReg[i] & RC_BORDER_REG) == 0)
            srcReg[i] = regions[srcReg[i]].id;
    }
    
    for (int i = 0; i < nreg; ++i)
        regions[i].~rcRegion();
    rcFree(regions);
    
    return true;
}