field.cpp

QuadTree.rar

#include "Field.h"
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <complex>

#define delete_ptr(p)	if(p){delete p;   p = 0;}
#define delete_ary(p)	if(p){delete[] p; p = 0;}

extern STileParam child_param[4]    = {{0, 0}, {1, 0}, {0, 1}, {1, 1}};
extern STileParam neighbor_param[4] = {{1, 0}, {1, 1}, {0, 0}, {0, 1}};

// 限定范围生成随机数(浮点)
inline float RandFloat( float f1, float f2 )
{	
    return (f1 + (f2 - f1)*((float)rand()) / ((float)RAND_MAX));	
}

// 求整数绝对值函数
inline int abs_int(int num)
{
    return (num ^ (0 - ( unsigned(num) >> 31))) + (unsigned(num) >> 31);
}

// 求以2为底的对数
int log2(int n)
{
    int r = 0;
    while(n > 1){
        n >>= 1;
        ++r;
    }
    return r;
}


CField::CField(void)
    : m_bValid()
    , m_byHeights(NULL)
	, m_byMinHeight(0)
	, m_byMaxHeight(0)
    , m_Tiles(NULL)
    , m_TouchTiles(NULL)
    , m_byQuarters(NULL)
    , m_nFieldSize(0)
    , m_nBorderSize(0)
    , m_nMaxTilesNum(0)
    , m_nMaxTouchNum(0)
    , m_nHeightsNum(0)
{
}

CField::~CField(void)
{
	if(m_bValid)
		Destroy();
}

bool CField::Create(int nFieldSize)
{
	m_bValid = false;

	m_nFieldSize  = nFieldSize;
	m_nBorderSize = m_nFieldSize + 1;
    m_nHeightsNum = m_nBorderSize * m_nBorderSize;

	// "高度"数据
	m_byHeights = new unsigned char[m_nHeightsNum];
	if(NULL == m_byHeights)return false;
		
	// "四分标记"数据
	m_byQuarters = new unsigned char[m_nHeightsNum];
	if(NULL == m_byQuarters)return false;

	// 计算最大可能的"块"数
	m_nMaxTilesNum = 0;
	int nSteps = log2(nFieldSize);
	for(int i = 0; i < nSteps; ++i)
		m_nMaxTilesNum = (m_nMaxTilesNum * 4 + 1);

    // "块"数组
	m_Tiles = new STile[m_nMaxTilesNum];
	if(NULL == m_Tiles)return false;

    // "受影响的块"数组(因为子节点自己要加进去,所以要"+1")
    m_nMaxTouchNum = CalculateMaxTouchNum(nFieldSize) + 1;

	m_TouchTiles = new STile[m_nMaxTouchNum];
	if(NULL == m_TouchTiles)return false;

	m_bValid = true;
	return true;
}

void CField::Destroy()
{
	delete_ary(m_byHeights);
	delete_ary(m_byQuarters);
	delete_ary(m_Tiles);
    delete_ary(m_TouchTiles)

	m_bValid = false;
}

// 添加(划分)子节点时,影响的两个临节点
STileParam effect_neighbor[4] = {{2, 3}, {3, 0}, {1, 2}, {0, 1}};

void CField::UpdateQuarters(int nError)
{
    // temp
    int nDepth = 0;

    int nCurTileNum = 0;
    memset(m_byQuarters, 0, sizeof(m_byQuarters[0]) * m_nHeightsNum);

    // 加入第一个"块"
    STile tileNew(m_nFieldSize >> 1, m_nFieldSize >> 1, m_nFieldSize);
    m_byQuarters[tileNew.m_cz * m_nBorderSize + tileNew.m_cx] = 1;   // 标记
    m_Tiles[nCurTileNum++] = tileNew;

    // 开始分块
    int nIndex = 0;
    while(nIndex < nCurTileNum)
    {
        STile tileChild;
        for(int i = 0; i < 4; ++i)
        {            
            // 加入子节点
            m_Tiles[nIndex].GetChild(i, &tileChild);
            if(!IsTileValid(&tileChild))
                continue;

            if(GetTileError(&tileChild) < nError)
                continue;

            m_Tiles[nCurTileNum++] = tileChild;

            // 检查、更新受影响的节点(父节点的临节点)
            int nTouchNum = 0;
            m_TouchTiles[nTouchNum++] = tileChild;

            STile touchParent;      // 父节点
            STile parentNeighbor;   // 父节点的临节点(重复使用这一个)
            int nTouchIndex = 0;
            while(nTouchIndex < nTouchNum)
            {
                STile* pTileTouch = &m_TouchTiles[nTouchIndex];
                m_byQuarters[pTileTouch->m_cz * m_nBorderSize + pTileTouch->m_cx] = 1; // 标记

                // 父节点
                pTileTouch->GetParent(&touchParent);
                if(!IsTileValid(&touchParent)) continue;

                int nSection = touchParent.GetSection(pTileTouch);

                // 临节点1
                touchParent.GetNeighbor(effect_neighbor[nSection].value1, &parentNeighbor);
                if(IsTileValid(&parentNeighbor) 
                    && 0 == m_byQuarters[parentNeighbor.m_cz * m_nBorderSize + parentNeighbor.m_cx])
                {
                    m_TouchTiles[nTouchNum++] = parentNeighbor;
                }

                // 临节点2
                touchParent.GetNeighbor(effect_neighbor[nSection].value2, &parentNeighbor);
                if(IsTileValid(&parentNeighbor) 
                    && 0 == m_byQuarters[parentNeighbor.m_cz * m_nBorderSize + parentNeighbor.m_cx])
                {
                    m_TouchTiles[nTouchNum++] = parentNeighbor;
                }

                ++nTouchIndex;
            }
        }

        ++nIndex;
    }
}

/*
  sx,sz    ex,sz
     -------
    | \ | / |
     -------
    | / | \ |
     -------
  sx,ez     ex,ez
*/

int CField::GetTileError(const STile* pTile)
{
    int sx = pTile->m_cx - (pTile->m_size >> 1);
    int sz = pTile->m_cz - (pTile->m_size >> 1);
    int ex = sx + pTile->m_size;
    int ez = sz + pTile->m_size;

    int fAverage	= 0;
    int nError		= 0;

    fAverage = (GetHeight(sx, sz) + GetHeight(ex, sz)) >> 1;
    nError = max(nError, abs_int(fAverage - GetHeight(pTile->m_cx, sz)));

    fAverage = (GetHeight(ex, sz) + GetHeight(ex, ez)) >> 1;
    nError = max(nError, abs_int(fAverage - GetHeight(ex, pTile->m_cz)));

    fAverage = (GetHeight(ex, ez) + GetHeight(sx, ez)) >> 1;
    nError = max(nError, abs_int(fAverage - GetHeight(pTile->m_cx, ez)));

    fAverage = (GetHeight(sx, ez) + GetHeight(sx, sz)) >> 1;
    nError = max(nError, abs_int(fAverage - GetHeight(sx, pTile->m_cz)));

    fAverage = (GetHeight(sx, sz) + GetHeight(ex, ez)) >> 1;
    nError = max(nError, abs_int(fAverage - GetHeight(pTile->m_cx, pTile->m_cz)));

    fAverage = (GetHeight(ex, sz) + GetHeight(sx, ez)) >> 1;
    nError = max(nError, abs_int(fAverage - GetHeight(pTile->m_cx, pTile->m_cz)));

    return nError;
}

inline bool CField::IsTileValid(const STile* pTile)
{    
    return unsigned (1 - pTile->m_size) >> 31
        && unsigned ((pTile->m_size >> 1) - (pTile->m_cx + 1)) >> 31
        && unsigned ((pTile->m_size >> 1) - (pTile->m_cz + 1)) >> 31
        && unsigned (pTile->m_cx - (m_nFieldSize - (pTile->m_size >> 1) + 1)) >> 31
        && unsigned (pTile->m_cz - (m_nFieldSize - (pTile->m_size >> 1) + 1)) >> 31;
}

int CField::CalculateMaxTouchNum(int nFieldSize)
{
    if(nFieldSize > 8)
        return ((log2(nFieldSize) - 2) << 1) + CalculateMaxTouchNum(nFieldSize >> 1);
    else
        return 0;
}

void CField::MakeHeightsPlasma(float* fHeights, float* fMinHeight, float* fMaxHeight, float fRoughness)
{
	assert(m_nBorderSize > 2);

	// 开始生成
    float fRandRange = (float)(m_nFieldSize >> 2);
    int nRectSize = m_nFieldSize;

    while(nRectSize > 1)
    {
        int iHalfRect = nRectSize >> 1;

        // 确定中心点高度(*菱形步骤*)
        for(int iy = 0; iy < m_nFieldSize; iy += nRectSize)
        {
            for(int ix = 0; ix < m_nFieldSize; ix += nRectSize)
            {
                // 右下角坐标
                int iex = ix + nRectSize;
                int iey = iy + nRectSize;

                // 中心坐标
                int imx = ix + iHalfRect;
                int imy = iy + iHalfRect;

                // 确定中心点高度
                fHeights[imy * m_nBorderSize + imx] = (fHeights[iy  * m_nBorderSize + ix ]
                                                     + fHeights[iy  * m_nBorderSize + iex]
                                                     + fHeights[iey * m_nBorderSize + iex]
                                                     + fHeights[iey * m_nBorderSize + ix ]) / 4