#include "StdAfx.h"
#ifndef CODE_INGAME

#include "TerrainOptimizer.h"
//#include "NiOptimize.h"

CTerrainOptimizer::CTerrainOptimizer(CTerrain* pTerrain, int iSensitivity)
: m_pTerrain(pTerrain),
	m_ucpQuadMatrix(NULL),
	m_iSensitivity(iSensitivity)
{
	int iNumVertexX = pTerrain->GetChunkNumX()*GRIDINCHUNK+1;	// X, Y 方向的顶点数量
	int iNumVertexY = pTerrain->GetChunkNumY()*GRIDINCHUNK+1;
	int iNumVertexTotal = iNumVertexX*iNumVertexY;	// 总顶点个数

	m_ucpQuadMatrix = new unsigned char[iNumVertexTotal];
	if (NULL == m_ucpQuadMatrix)
	{
		LOG("CTerrainOptimizer::Optimize 内存分配失败");
	}
	memset(m_ucpQuadMatrix, 0, iNumVertexTotal);
}

CTerrainOptimizer::~CTerrainOptimizer(void)
{
	SAFE_DELETE_ARRAY(m_ucpQuadMatrix);
}

void CTerrainOptimizer::Optimize(bool bFinalOptimize)
{
	/**************************************************
	*	计算地表 roughness 结果保存到 m_ucpQuadMatrix 
	***************************************************/
	int iChunkSize = GRIDINCHUNK+1;	// chunk 每边顶点数
	// 遍历每一个chunk 计算所有节点的 roughness
	for (int i=0; i<m_pTerrain->GetChunkNumY(); i++)	// 遍历行,向 Y 正方向
	{
		for (int j=0; j<m_pTerrain->GetChunkNumX(); j++)	// 遍历列,向 X 正方向
		{
			int iVertexOffsetY = i * GRIDINCHUNK;	// 当前 chunk 顶点在 X, Y 方向的偏移
			int iVertexOffsetX = j * GRIDINCHUNK;
	
			int iEdgeLength = 3;	// 从最小边长节点开始遍历
			while (iEdgeLength <= iChunkSize)
			{
				int iEdgeOffset = (iEdgeLength-1)/2;
				int iChildOffset = (iEdgeLength-1)/4;
				
				// 遍历每一个 node， 计算 D2 值，也就是 roughness
				for (int y=iEdgeOffset; y<iChunkSize; y+=(iEdgeLength-1))
				{
					for (int x=iEdgeOffset; x<iChunkSize; x+=(iEdgeLength-1))
					{
						// right-mid
						int iLocalD2 = (int)(abs((( m_pTerrain->GetVertexHeight(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);

						// 顶点 alpha 差
						iLocalD2 += (int)(abs((( m_pTerrain->GetVertexAlpha(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);
						// 顶点 颜色 差 (只取视觉敏感度高的 R,G)
						iLocalD2 += (int)(abs((( m_pTerrain->GetVertexR(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexR(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexR(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);
						iLocalD2 += (int)(abs((( m_pTerrain->GetVertexG(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexG(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexG(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);

						// up-mid
						int iDH = (int)(abs((( m_pTerrain->GetVertexHeight(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset)) +
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x, iVertexOffsetY+y+iEdgeOffset))*m_iSensitivity);

						iDH += (int)(abs((( m_pTerrain->GetVertexAlpha(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset)) +
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x, iVertexOffsetY+y+iEdgeOffset))*m_iSensitivity);

						iDH += (int)(abs((( m_pTerrain->GetVertexR(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset)) +
							m_pTerrain->GetVertexR(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexR(iVertexOffsetX+x, iVertexOffsetY+y+iEdgeOffset))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexG(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset)) +
							m_pTerrain->GetVertexG(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexG(iVertexOffsetX+x, iVertexOffsetY+y+iEdgeOffset))*m_iSensitivity);
						iLocalD2 = max(iLocalD2, iDH);

						// left-mid
						iDH = (int)(abs((( m_pTerrain->GetVertexHeight(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexAlpha(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);

						iDH += (int)(abs((( m_pTerrain->GetVertexR(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexR(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexR(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexG(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexG(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexG(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y))*m_iSensitivity);

						iLocalD2 = max(iLocalD2, iDH);

						// bottom-mid
						iDH = (int)(abs((( m_pTerrain->GetVertexHeight(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset) )/2 -
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x, iVertexOffsetY+y-iEdgeOffset))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexAlpha(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset) )/2 -
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x, iVertexOffsetY+y-iEdgeOffset))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexR(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexR(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset) )/2 -
							m_pTerrain->GetVertexR(iVertexOffsetX+x, iVertexOffsetY+y-iEdgeOffset))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexG(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexG(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset) )/2 -
							m_pTerrain->GetVertexG(iVertexOffsetX+x, iVertexOffsetY+y-iEdgeOffset))*m_iSensitivity);
						iLocalD2 = max(iLocalD2, iDH);

						// bottom-left to top-right diagonal
						iDH = (int)(abs((( m_pTerrain->GetVertexHeight(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexAlpha(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexR(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexR(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexR(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexG(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexG(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexG(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);

						iLocalD2 = max(iLocalD2, iDH);

						// bottom-right to top-left diagonal
						iDH = (int)(abs((( m_pTerrain->GetVertexHeight(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexHeight(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexAlpha(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexAlpha(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexR(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexR(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexR(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);
						iDH += (int)(abs((( m_pTerrain->GetVertexG(iVertexOffsetX+x+iEdgeOffset, iVertexOffsetY+y-iEdgeOffset)) +
							m_pTerrain->GetVertexG(iVertexOffsetX+x-iEdgeOffset, iVertexOffsetY+y+iEdgeOffset) )/2 -
							m_pTerrain->GetVertexG(iVertexOffsetX+x, iVertexOffsetY+y))*m_iSensitivity);
						iLocalD2 = max(iLocalD2, iDH);

						int iD2 = 0;
						// 最小边长节点
						if (iEdgeLength == 3)
						{
							iD2 = iLocalD2;
						}
						else
						{
							iD2 = iLocalD2;
							iD2 = (int)ceil((float)(max(GetQuadMatrixValue(iVertexOffsetX+x-iChildOffset, iVertexOffsetY+y-iChildOffset), iD2)));
							iD2 = (int)ceil((float)(max(GetQuadMatrixValue(iVertexOffsetX+x-iChildOffset, iVertexOffsetY+y+iChildOffset), iD2)));
							iD2 = (int)ceil((float)(max(GetQuadMatrixValue(iVertexOffsetX+x+iChildOffset, iVertexOffsetY+y-iChildOffset), iD2)));
							iD2 = (int)ceil((float)(max(GetQuadMatrixValue(iVertexOffsetX+x+iChildOffset, iVertexOffsetY+y+iChildOffset), iD2)));
						}
						m_ucpQuadMatrix[GetQuadMatrixIndex(iVertexOffsetX+x, iVertexOffsetY+y)] = iD2;			

					}
				}	// end of 当前边长所有节点

				// move to the next quadtree level (lower level of detail)
				iEdgeLength = (iEdgeLength<<1) - 1;
			}	// end of 当前chunk 所有边长

			// 将所有chunk 的第一级设置为分割
			m_ucpQuadMatrix[GetQuadMatrixIndex(iVertexOffsetX+GRIDINCHUNK/2, iVertexOffsetY+GRIDINCHUNK/2)] = 255;
		}
	}	// end of 所有chunk 所有边长节点

	/*****************************************************
	*	从顶向下遍历所有节点,防止相邻节点细分等级超过1
	*	规则是如果子节点细分,则与子节点相邻的邻居节点也必须细分
	********************************************************/
	for (int k=0; k<5; k++)
	{
		for (int i=0; i<m_pTerrain->GetChunkNumY(); i++)	// 遍历行,向 Y 正方向
		{
			for (int j=0; j<m_pTerrain->GetChunkNumX(); j++)	// 遍历列,向 X 正方向
			{
				int iEdgeLength = GRIDINCHUNK+1;	// 从最大边长节点开始遍历
				_StandardQuadMat(j, i, GRIDINCHUNK/2, GRIDINCHUNK/2, iEdgeLength);
			}
		}
	}

	//FILE *pFile = fopen("e:\\test\\quadMat.txt", "w");
	//
	//for (int i=0; i<m_pTerrain->GetChunkNumY(); i++)	// 遍历行,向 Y 正方向
	//{
	//	for (int j=0; j<m_pTerrain->GetChunkNumX(); j++)	// 遍历列,向 X 正方向
	//	{
	//		int iVertexOffsetY = i * GRIDINCHUNK;	// 当前 chunk 顶点在 X, Y 方向的偏移
	//		int iVertexOffsetX = j * GRIDINCHUNK;
	//		for (int y=0; y<GRIDINCHUNK; y++)
	//		{
	//			for (int x=0; x<GRIDINCHUNK; x++)
	//			{
	//				int data = GetQuadMatrixValue(iVertexOffsetX+x, iVertexOffsetY+y);
	//				fprintf(pFile, "%d	", data);
	//			}
	//			fprintf(pFile, "\n");
	//		}
	//		fprintf(pFile, "********************************\n");
	//	}
	//}
	//fclose(pFile);

	/*********************************************************
	*	遍历每个 chunk，根据 quadMatrix 逐个生成三角形数据
	**********************************************************/
	for (int i=0; i<m_pTerrain->GetChunkNumY(); i++)	// 遍历行,向 Y 正方向
	{
		for (int j=0; j<m_pTerrain->GetChunkNumX(); j++)	// 遍历列,向 X 正方向
		{
			_OptimizeChunk(j, i);
		}
	}

	if (bFinalOptimize)
	{
		_ClearUnuseVertices();

		// 修正normal [6/22/2009 hemeng]
		_ModifyNormals();
	}

}

void CTerrainOptimizer::_StandardQuadMat(int iChunkX, int iChunkY, int iX, int iY, int iEdgeLength)
{
	int iNumChunksX = m_pTerrain->GetChunkNumX();
	int iNumChunksY = m_pTerrain->GetChunkNumY();

	int iVertexOffsetX = iChunkX * GRIDINCHUNK;		// 当前 chunk 顶点在 X, Y 方向的偏移
	int iVertexOffsetY = iChunkY * GRIDINCHUNK;

	int iXInMat = iVertexOffsetX+iX;
	int iYInMat = iVertexOffsetY+iY;

	int iSize = GRIDINCHUNK+1;	// chunk 每边顶点数
	// 不分割
	//if (GetQuadMatrixValue(iXInMat, iYInMat) == 0)
	//{
	//	return;
	//}

	int iNodeOffset = iEdgeLength-1;	// 到同等级邻居节点偏移
	int iChildOffset = iEdgeLength>>2;	// 偏移到子节点

	// 四个子节点是否继续细分
	bool bRefineChildLU = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat-iChildOffset, iYInMat+iChildOffset)>0);
	bool bRefineChildLB = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat-iChildOffset, iYInMat-iChildOffset)>0);
	bool bRefineChildRU = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat+iChildOffset, iYInMat+iChildOffset)>0);
	bool bRefineChildRB = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat+iChildOffset, iYInMat-iChildOffset)>0);

	// 四个方向的邻居是否细分
	bool bRefineNeighborL = (iXInMat-iNodeOffset>0 && GetQuadMatrixValue(iXInMat-iNodeOffset, iYInMat)>0) || iXInMat-iNodeOffset<0;
	bool bRefineNeighborR = (iXInMat+iNodeOffset<iNumChunksX*GRIDINCHUNK+1 && GetQuadMatrixValue(iXInMat+iNodeOffset, iYInMat)>0) || iXInMat+iNodeOffset>=iNumChunksX*GRIDINCHUNK+1;
	bool bRefineNeighborB = (iYInMat-iNodeOffset>0 && GetQuadMatrixValue(iXInMat, iYInMat-iNodeOffset)>0) || iYInMat-iNodeOffset<0;
	bool bRefineNeighborU = (iYInMat+iNodeOffset<iNumChunksY*GRIDINCHUNK+1 && GetQuadMatrixValue(iXInMat, iYInMat+iNodeOffset)>0) || iYInMat+iNodeOffset>=iNumChunksY*GRIDINCHUNK+1;

	// 如果左上孩子细分,左邻居与右邻居也必须细分
	if (bRefineChildLU)
	{
		if (iXInMat-iNodeOffset>0 && !bRefineNeighborL)	// 左邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat-iNodeOffset, iYInMat)] = 1;
			bRefineNeighborL = true;
		}

		if (iYInMat+iNodeOffset<iNumChunksY*GRIDINCHUNK+1  && !bRefineNeighborU)	// 上邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat, iYInMat+iNodeOffset)] = 1;
			bRefineNeighborU = true;
		}

		if (iEdgeLength>3) _StandardQuadMat(iChunkX, iChunkY, iX-iChildOffset, iY+iChildOffset, iEdgeLength/2+1);
	}

	if (bRefineChildRU)
	{
		if (iXInMat+iNodeOffset<iNumChunksX*GRIDINCHUNK+1 && !bRefineNeighborR)	// 右邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat+iNodeOffset, iYInMat)] = 1;
			bRefineNeighborR = true;
		}

		if (iYInMat+iNodeOffset<iNumChunksY*GRIDINCHUNK+1  && !bRefineNeighborU)	// 上邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat, iYInMat+iNodeOffset)] = 1;
			bRefineNeighborU = true;
		}
		if (iEdgeLength>3) _StandardQuadMat(iChunkX, iChunkY, iX+iChildOffset, iY+iChildOffset, iEdgeLength/2+1);
	}

	if (bRefineChildLB)
	{
		if (iXInMat-iNodeOffset>0 && !bRefineNeighborL)	// 左邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat-iNodeOffset, iYInMat)] = 1;
			bRefineNeighborL = true;
		}

		if (iYInMat-iNodeOffset>0 && !bRefineNeighborB) // 下邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat, iYInMat-iNodeOffset)] = 1;
			bRefineNeighborB = true;
		}

		if (iEdgeLength>3) _StandardQuadMat(iChunkX, iChunkY, iX-iChildOffset, iY-iChildOffset, iEdgeLength/2+1);
	}
	
	if (bRefineChildRB)
	{
		if (iXInMat+iNodeOffset<iNumChunksX*GRIDINCHUNK+1 && !bRefineNeighborR)	// 右邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat+iNodeOffset, iYInMat)] = 1;
			bRefineNeighborR = true;
		}

		if (iYInMat-iNodeOffset>0 && !bRefineNeighborB) // 下邻居
		{
			m_ucpQuadMatrix[GetQuadMatrixIndex(iXInMat, iYInMat-iNodeOffset)] = 1;
			bRefineNeighborB = true;
		}

		if (iEdgeLength>3) _StandardQuadMat(iChunkX, iChunkY, iX+iChildOffset, iY-iChildOffset, iEdgeLength/2+1);
	}
}

void CTerrainOptimizer::_OptimizeChunk(int iX, int iY)
{
	int iVertexOffsetY = iY * GRIDINCHUNK;	// 当前 chunk 顶点在 X, Y 方向的偏移
	int iVertexOffsetX = iX * GRIDINCHUNK;
	CTerrain::stChunk* pChunk = m_pTerrain->GetChunks()+(iY*m_pTerrain->GetChunkNumX()+iX);	// 当前要优化的 chunk
	WORD* pwTriList = pChunk->geomData.pTriShape->GetTriList();
	ZeroMemory(pwTriList, GRIDINCHUNK*GRIDINCHUNK*6);

	int iNumTri = 0;
	int iEdgeLength = GRIDINCHUNK+1;
	_GenerateTriangles(iX, iY, GRIDINCHUNK/2, GRIDINCHUNK/2, iEdgeLength, pwTriList, iNumTri);

	//WORD* pwOldTriList = pChunk->geomData.pTriShape->GetTriList();


	pChunk->geomData.pTriShape->GetModelData()->MarkAsChanged(
		NiTriBasedGeomData::TRIANGLE_INDEX_MASK );
		//|NiTriBasedGeomData::TRIANGLE_COUNT_MASK
	pChunk->geomData.pTriShape->SetActiveTriangleCount(iNumTri);
	pChunk->geomData.pTriShape->Update(0.0f);
}

void CTerrainOptimizer::_GenerateTriangles(int iChunkX, int iChunkY, int iX, int iY, int iEdgeLength, WORD* pVI, int &iNumTri)
{

	int iNumChunksX = m_pTerrain->GetChunkNumX();
	int iNumChunksY = m_pTerrain->GetChunkNumY();

	int iVertexOffsetX = iChunkX * GRIDINCHUNK;		// 当前 chunk 顶点在 X, Y 方向的偏移
	int iVertexOffsetY = iChunkY * GRIDINCHUNK;

	int iXInMat = iVertexOffsetX+iX;
	int iYInMat = iVertexOffsetY+iY;

	int iSize = GRIDINCHUNK+1;	// chunk 每边顶点数
	// 不分割
	//if (GetQuadMatrixValue(iXInMat, iYInMat) == 0)
	//{
	//	return;
	//}

	int iNodeOffset = iEdgeLength-1;	// 到同等级邻居节点偏移
	int iEdgeOffset = iEdgeLength>>1;
	int iChildOffset = iEdgeLength>>2;	// 偏移到子节点
	WORD* pIndex = pVI + iNumTri*3;		// 本节点顶点索引首地址

	// 四个子节点是否继续细分
	bool bRefineChildLU = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat-iChildOffset, iYInMat+iChildOffset)>0);
	bool bRefineChildLB = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat-iChildOffset, iYInMat-iChildOffset)>0);
	bool bRefineChildRU = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat+iChildOffset, iYInMat+iChildOffset)>0);
	bool bRefineChildRB = iEdgeLength>3 && (GetQuadMatrixValue(iXInMat+iChildOffset, iYInMat-iChildOffset)>0);

	// 四个方向的邻居是否细分
	bool bRefineNeighborL = (iXInMat-iNodeOffset>0 && GetQuadMatrixValue(iXInMat-iNodeOffset, iYInMat)>0) || (iXInMat-iNodeOffset<0);
	bool bRefineNeighborR = (iXInMat+iNodeOffset<iNumChunksX*GRIDINCHUNK+1 && GetQuadMatrixValue(iXInMat+iNodeOffset, iYInMat)>0) 
																					|| (iXInMat+iNodeOffset>=iNumChunksX*GRIDINCHUNK+1);
	bool bRefineNeighborB = (iYInMat-iNodeOffset>0 && GetQuadMatrixValue(iXInMat, iYInMat-iNodeOffset)>0) || (iYInMat-iNodeOffset<0);
	bool bRefineNeighborU = (iYInMat+iNodeOffset<iNumChunksY*GRIDINCHUNK+1 && GetQuadMatrixValue(iXInMat, iYInMat+iNodeOffset)>0)
																					|| (iYInMat+iNodeOffset>=iNumChunksY*GRIDINCHUNK+1);
	/*
	|\
	|_\c
	| /
	|/
	*/
	// 判断左侧与本节点同等级的邻居节点细节等级。如果相同则判断LU及LB两个子节点是否继续细分，如果不细分则生成小三角形
	if (bRefineNeighborL)
	{
		// 判断 LU 节点是否继续细分
		if (bRefineChildLU)	//
		{
			_GenerateTriangles(iChunkX, iChunkY, iX-iChildOffset, iY+iChildOffset, iEdgeLength/2+1, pVI, iNumTri);
			
		}
		else	// 不细分
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = iY*iSize + (iX-iEdgeOffset);				// L
			*pIndex++ = iY*iSize + (iX);							// C
			*pIndex++ = (iY+iEdgeOffset)*iSize + (iX-iEdgeOffset);	// LU
			iNumTri+=1;
		}

		if (bRefineChildLB)	// LB 是否细分
		{
			_GenerateTriangles(iChunkX, iChunkY, iX-iChildOffset, iY-iChildOffset, iEdgeLength/2+1, pVI, iNumTri);
		}
		else
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = iY*iSize + (iX-iEdgeOffset);				// L
			*pIndex++ = (iY-iEdgeOffset)*iSize + (iX-iEdgeOffset);	// LB
			*pIndex++ = iY*iSize + (iX);							// C
			iNumTri += 1;
		}

	}
	else
	{
		pIndex = pVI + iNumTri*3;
		// 左侧细节等级低于本节点，省略一个顶点。生成一个大三角形
		*pIndex++ = (iY+iEdgeOffset)*iSize + (iX-iEdgeOffset);	// LU
		*pIndex++ = (iY-iEdgeOffset)*iSize + (iX-iEdgeOffset);	// LB
		*pIndex++ = iY*iSize + (iX);							// C
		iNumTri += 1;
	}

	/*
	 /|
   c/_|
	\ |
	 \| 
	*/
	// 右侧
	if (bRefineNeighborR)
	{
		// 判断 RU 节点是否继续细分
		if (bRefineChildRU)	//
		{
			_GenerateTriangles(iChunkX, iChunkY, iX+iChildOffset, iY+iChildOffset, iEdgeLength/2+1, pVI, iNumTri);
		}
		else	// 不细分
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = iY*iSize + (iX);							// C
			*pIndex++ = iY*iSize + (iX+iEdgeOffset);				// R
			*pIndex++ = (iY+iEdgeOffset)*iSize + (iX+iEdgeOffset);	// RU
			iNumTri+=1;
		}

		if (bRefineChildRB)	// RB 是否细分
		{
			_GenerateTriangles(iChunkX, iChunkY, iX+iChildOffset, iY-iChildOffset, iEdgeLength/2+1, pVI, iNumTri);
		}
		else
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = iY*iSize + (iX);							// C			
			*pIndex++ = (iY-iEdgeOffset)*iSize + (iX+iEdgeOffset);	// RB
			*pIndex++ = iY*iSize + (iX+iEdgeOffset);				// R
			iNumTri += 1;
		}

	}
	else
	{
		pIndex = pVI + iNumTri*3;
		*pIndex++ = (iY-iEdgeOffset)*iSize + (iX+iEdgeOffset);	// RB
		*pIndex++ = (iY+iEdgeOffset)*iSize + (iX+iEdgeOffset);	// RU
		*pIndex++ = iY*iSize + (iX);							// C
		iNumTri += 1;
	}

	// 下侧
	/*
	  c
	 /|\
  lb/_|_\rb
	  b	
	*/
	if (bRefineNeighborB)
	{
		// 判断 LB 节点是否继续细分
		if (bRefineChildLB)	//
		{
			// 细分过了

		}
		else	// 不细分
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = (iY-iEdgeOffset)*iSize + (iX-iEdgeOffset);		// LB
			*pIndex++ = (iY-iEdgeOffset)*iSize + (iX);					// B
			*pIndex++ = (iY)*iSize + (iX);								// C
			iNumTri+=1;
		}

		if (bRefineChildRB)	// RB 是否细分
		{
			// 细分过了

		}
		else
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = (iY-iEdgeOffset)*iSize + (iX);					// B
			*pIndex++ = (iY-iEdgeOffset)*iSize + (iX+iEdgeOffset);		// RB
			*pIndex++ = iY*iSize + (iX);								// C
			iNumTri += 1;
		}
	}
	else
	{
		pIndex = pVI + iNumTri*3;
		*pIndex++ = (iY-iEdgeOffset)*iSize + (iX-iEdgeOffset);	// LB
		*pIndex++ = (iY-iEdgeOffset)*iSize + (iX+iEdgeOffset);	// RB
		*pIndex++ = iY*iSize + (iX);							// C

		iNumTri += 1;
	}



	/*
  lu _u_ru
	 \|/
	  c
	*/
	// 上侧
	if (bRefineNeighborU)
	{
		// 判断 LU 节点是否继续细分
		if (bRefineChildLU)	//
		{
			// 细分过了

		}
		else	// 不细分
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = (iY+iEdgeOffset)*iSize + (iX-iEdgeOffset);	// LU
			*pIndex++ = iY*iSize + (iX);							// C
			*pIndex++ = (iY+iEdgeOffset)*iSize + (iX);				// U
			iNumTri+=1;
		}

		if (bRefineChildRU)	// RB 是否细分
		{
			// 细分过了

		}
		else
		{
			pIndex = pVI + iNumTri*3;
			*pIndex++ = (iY+iEdgeOffset)*iSize + (iX);				// U
			*pIndex++ = iY*iSize + (iX);							// C			
			*pIndex++ = (iY+iEdgeOffset)*iSize + (iX+iEdgeOffset);	// RU
			iNumTri += 1;
		}
	}
	else
	{
		pIndex = pVI + iNumTri*3;
		*pIndex++ = (iY+iEdgeOffset)*iSize + (iX-iEdgeOffset);	// LU
		*pIndex++ = iY*iSize + (iX);							// C
		*pIndex++ = (iY+iEdgeOffset)*iSize + (iX+iEdgeOffset);	// RU

		iNumTri += 1;
	}

}

void CTerrainOptimizer::_ClearUnuseVertices()
{
	int iChunkID = 0;
	CTerrain::stChunk* pChunks = m_pTerrain->GetChunks();

	// 遍历所有 chunk ，对每个chunk 的顶点单独进行优化
	int iNumVertInChunk = (GRIDINCHUNK+1)*(GRIDINCHUNK+1);
	unsigned int* pVertFlag = new unsigned int[iNumVertInChunk];	//
	if (NULL == pVertFlag)
	{
		// 内存分配失败
		return;
	}

	for (int i=0; i<m_pTerrain->GetChunkNumY(); i++)
	{
		for (int j=0; j<m_pTerrain->GetChunkNumX(); j++, iChunkID++)
		{
			ZeroMemory(pVertFlag, iNumVertInChunk*sizeof(unsigned int));

			NiTriShapePtr pkTriShape = pChunks[iChunkID].geomData.pTriShape;

			// 遍历所有 triangles, 找出哪些顶点在用
			for (int k=0; k<pkTriShape->GetActiveTriangleCount(); k++)
			{
				unsigned short i0, i1, i2;
				pkTriShape->GetTriangleIndices(k, i0, i1, i2);

				assert(i0<iNumVertInChunk && i1<iNumVertInChunk && i2<iNumVertInChunk);
				pVertFlag[i0] = 1;
				pVertFlag[i1] = 1;
				pVertFlag[i2] = 1;
			}

			int iNumVertInUse = 0;
			// 遍历标记数组,对于每个被使用的顶点,计算前边未使用顶点数量
			for (int k=0; k<iNumVertInChunk; k++)
			{
				if (pVertFlag[k] != 0)
				{
					// 顶点未被使用
					pVertFlag[k] = iNumVertInUse;	// new index
					iNumVertInUse++;
					// 新索引 pVertFlag[k]
				}
			}

			// 获取老的顶点数据
			NiPoint3* pOldVerts = pkTriShape->GetVertices();
			NiPoint2* pOldTexCoords = pkTriShape->GetTextures();
			NiColorA* pOldColors = pkTriShape->GetColors();
	

			// 重新构建 Tri Shape
			int iVertNum = iNumVertInUse; //pkTriShape->GetActiveVertexCount();
			int iTriNum = pkTriShape->GetActiveTriangleCount();


			// 分配渲染数据
			NiPoint3* pVerts		= NiNew NiPoint3[iVertNum];
			NiPoint3* pNormals		= NiNew NiPoint3[iVertNum];	// 包含每个顶点的 normal, tangent, binormal 
			NiPoint2* pTexCoords	= NiNew NiPoint2[iVertNum*2];
			NiColorA* pColors		= NiNew NiColorA[iVertNum];
			WORD*	  pConnect		= NiAlloc( WORD, iTriNum * 3 );

			// 遍历标记数组,将需要的旧顶点数据拷贝到新顶点数据中
			for (int k=0; k<iNumVertInChunk; k++)
			{
				if (pVertFlag[k]>0 || k == 0)	// 第一个顶点一定是在使用的
				{
					int iOldIndex = k;
					int iNewIndex = pVertFlag[k];
					pVerts[iNewIndex] = pOldVerts[iOldIndex];
					pTexCoords[iNewIndex] = pOldTexCoords[iOldIndex];
					pTexCoords[iNewIndex+iVertNum] = pOldTexCoords[iOldIndex+iNumVertInChunk];
					pColors[iNewIndex] = pOldColors[iOldIndex];
				}
			}

			// 遍历旧连接信息, 将 active triangles 的索引拷贝到 新连接信息中
			for (int k=0; k<iTriNum; k++)
			{
				unsigned short i0, i1, i2;
				pkTriShape->GetTriangleIndices(k, i0, i1, i2);
				pConnect[k*3] = pVertFlag[i0];
				pConnect[k*3+1] = pVertFlag[i1];
				pConnect[k*3+2] = pVertFlag[i2];


				//int index0  = i0 - pVertFlag[i0];
				//int index1 = i1 - pVertFlag[i1];
				//int index2  = i2 - pVertFlag[i2];

				//if (index0>=iVertNum || index1>=iVertNum || index2>=iVertNum 
				//	|| index0<0 || index1<0 || index2<0  )
				//{
				//	int kkkk  = 0;
				//}
			}

			NiTriShapeDynamicData *pNewData = NiNew NiTriShapeDynamicData(
				iVertNum, pVerts, pNormals,
				pColors, pTexCoords, 2, NiGeometryData::NBT_METHOD_NONE,
				iTriNum, pConnect, iVertNum, iTriNum );
			
			// bug fix 修正地形优化后为重新计算normal的错误 [5/15/2009 hemeng]
			pNewData->CalculateNormals();
			pChunks[iChunkID].geomData.pTriShape = NiNew NiTriShape( pNewData );	
		}
	}
	delete[] pVertFlag;	
}

bool CTerrainOptimizer::_ModifyNormals()
{
	int iChunkID = 0;

	vector<stChunkNormal> vErrorVertice;

	if (m_pTerrain->GetChunkNumX() == m_pTerrain->GetChunkNumY() && m_pTerrain->GetChunkNumX() == 1)
	{
		return true;
	}

	// 逐chunk查找 [6/22/2009 hemeng]
	for (int i=0; i<m_pTerrain->GetChunkNumY(); i++)
	{
		for (int j=0; j<m_pTerrain->GetChunkNumX(); j++, iChunkID++)
		{
			// 检查当前chunk和右chunk的边界 [6/22/2009 hemeng]
			if((j + 1) % m_pTerrain->GetChunkNumX() != 0 && (j + 1) < m_pTerrain->GetChunkNumY())
			{
				_CheckChunkBorder(iChunkID,vErrorVertice,true);
			}

			// 检查当前chunk和上chunk的边界 [6/22/2009 hemeng]
			if((i + 1) % m_pTerrain->GetChunkNumY() != 0 && (i + 1) < m_pTerrain->GetChunkNumX())
			{
				_CheckChunkBorder(iChunkID,vErrorVertice,false);
			}
		}
	}

	// 修正错误的normal [6/22/2009 hemeng]
	for (unsigned int uiIndex = 0; uiIndex < vErrorVertice.size(); uiIndex++)
	{
		CTerrain::stChunk* pChunks = m_pTerrain->GetChunks();

		stChunkNormal kVert = vErrorVertice[uiIndex];
		NiPoint3* pNormals = pChunks[kVert.uiChunkID].geomData.pTriShape->GetNormals();
		pNormals[kVert.uiVertIndex] = kVert.kNormal;
		pChunks[kVert.uiChunkID].geomData.pTriShape->GetModelData()->MarkAsChanged(NiGeometryData::NORMAL_MASK);
	}	

	return true;
}

void CTerrainOptimizer::_CheckChunkBorder(int iChunkID, vector<stChunkNormal>& vErrorVer, bool bRow)
{
	stChunkNormal stErrorVert;
	int	iCmpChunkID = 0;

	CTerrain::stChunk* pChunks = m_pTerrain->GetChunks();
	NiTriShapePtr pkTriShape = pChunks[iChunkID].geomData.pTriShape;

	if(bRow)
	{
		iCmpChunkID = iChunkID + 1;
	}
	else
	{
		iCmpChunkID = iChunkID + m_pTerrain->GetChunkNumY();
	}

	NiTriShapePtr pkCmpTriShape = pChunks[iCmpChunkID].geomData.pTriShape;
	NiPoint3* pCmpNormals = pkCmpTriShape->GetNormals();

	unsigned short usVerticeCount = pkTriShape->GetVertexCount();
	NiPoint3* pVertice = pkTriShape->GetVertices();
	NiPoint3* pNormals = pkTriShape->GetNormals();

	for (unsigned short i = 0; i < usVerticeCount; i++)
	{
		NiPoint3 kVert = pVertice[i];
		// 如果是横向检查，则检查右边界
		if(bRow)
		{
			if ((int)(kVert.x + 0.5) % GRIDINCHUNK != 0 || (int)(kVert.x + 0.5) == 0)
			{
				continue;
			}
		}
		// 反之，检查上边界
		else
		{
			if ((int)(kVert.y + 0.5) % GRIDINCHUNK != 0 || (int)(kVert.y + 0.5) == 0)
			{
				continue;
			}
		}

		int iCmpIndex = m_pTerrain->GetIndexInChunk(iCmpChunkID,kVert);
		if(iCmpIndex != -1)
		{
			if(pNormals[i] != pCmpNormals[iCmpIndex])
			{
				stErrorVert.uiChunkID = iChunkID;
				stErrorVert.kNormal = NiPoint3(pNormals[i] + pCmpNormals[iCmpIndex]) / 2;
				NiPoint3::UnitizeVector(stErrorVert.kNormal);
				stErrorVert.uiVertIndex = i;

				vErrorVer.push_back(stErrorVert);

				stErrorVert.uiChunkID = iCmpChunkID;
				stErrorVert.uiVertIndex = iCmpIndex;

				vErrorVer.push_back(stErrorVert);
			}
		}
	
	}
	
	

}

#endif