wmlterrainpage.cpp

3D Game Engine Design Source Code非常棒

// Magic Software, Inc.
// http://www.magic-software.com
// http://www.wild-magic.com
// Copyright (c) 2003.  All Rights Reserved
//
// The Wild Magic Library (WML) source code is supplied under the terms of
// the license agreement http://www.magic-software.com/License/WildMagic.pdf
// and may not be copied or disclosed except in accordance with the terms of
// that agreement.

#include "WmlRenderer.h"
#include "WmlTerrainBlock.h"
#include "WmlTerrainPage.h"
#include "WmlTerrainVertex.h"
using namespace Wml;

WmlImplementRTTI(TerrainPage,TriMesh);
WmlImplementStream(TerrainPage);

//----------------------------------------------------------------------------
TerrainPage::TerrainPage (unsigned short usSize, unsigned short* ausHeight,
    const Vector2f& rkOrigin, float fMinElevation, float fMaxElevation,
    float fSpacing)
    :
    TriMesh(
        usSize*usSize,  // vertex quantity
        new Vector3f[usSize*usSize],  // vertices,
        0,  // no normals
        0,  // no colors
        new Vector2f[usSize*usSize],  // always use textures
        2*(usSize-1)*(usSize-1),  // triangle quantity
        new int[6*(usSize-1)*(usSize-1)])  // connectivity
{
    // usSize = 2^p + 1, p <= 7
    assert( usSize ==  3 || usSize ==  5 || usSize ==   9 || usSize == 17
        ||  usSize == 33 || usSize == 65 || usSize == 129 );

    // native data
    m_usSize = usSize;
    m_ausHeight = ausHeight;
    m_kOrigin = rkOrigin;
    m_fMinElevation = fMinElevation;
    m_fMaxElevation = fMaxElevation;
    m_fSpacing = fSpacing;

    InitializeDerivedData();
}
//----------------------------------------------------------------------------
TerrainPage::TerrainPage ()
    :
    m_kOrigin(Vector2f::ZERO)
{
    // native data
    m_usSize = 0;
    m_ausHeight = NULL;
    m_fMinElevation = 0.0f;
    m_fMaxElevation = 0.0f;
    m_fSpacing = 0.0f;

    // derived data
    m_usSizeM1 = 0;
    m_fPixelTolerance = 0.0f;
    m_fWorldTolerance = 0.0f;
    m_fInvSpacing = 0.0f;
    m_fTextureSpacing = 0.0f;
    m_fMultiplier = 0.0f;
    m_bNeedsTessellation = false;
    m_ausLookup = NULL;
    m_iConnectLength = 0;
    m_akTVertex = NULL;
    m_usBlockQuantity = 0;
    m_akBlock = NULL;
    m_usQueueQuantity = 0;
    m_ausQueue = NULL;
    m_usFront = 0;
    m_usRear = 0;
    m_usItemsInQueue = 0;
}
//----------------------------------------------------------------------------
TerrainPage::~TerrainPage ()
{
    delete[] m_ausHeight;
    delete[] m_akTVertex;
    delete[] m_akBlock;
    delete[] m_ausQueue;
    delete[] m_ausLookup;
}
//----------------------------------------------------------------------------
void TerrainPage::InitializeDerivedData ()
{
    m_usSizeM1 = m_usSize - 1;
    m_fPixelTolerance = 1.0f;
    m_fWorldTolerance = -1.0f;
    m_fInvSpacing = 1.0f/m_fSpacing;
    m_fTextureSpacing = 1.0f/float(m_usSizeM1);
    m_fMultiplier = (m_fMaxElevation - m_fMinElevation)/65535.0f;
    m_bNeedsTessellation = true;

    // for tessellation (mapping of connectivity indices)
    m_ausLookup = new unsigned short[m_iVertexQuantity];
    m_iConnectLength = 0;

    // initialize vertex information array
    m_akTVertex = new TerrainVertex[m_iVertexQuantity];
    memset(m_akTVertex,0,m_iVertexQuantity*sizeof(TerrainVertex));

    // allocate quadtree
    m_usBlockQuantity = m_usSize*(m_usSize-2)/3;
    m_akBlock = new TerrainBlock[m_usBlockQuantity];

    // initialize quadtree
    unsigned char ucStride = (unsigned char)((m_usSize-1)/2);
    m_akBlock[0].Initialize(this,m_akBlock,0,0,0,ucStride,true);
    m_akBlock[0].UpdateBoundingBox(this,m_akBlock,0,ucStride);

    // model bounding sphere contains the top level block's bounding box
    Vector3f kCenter = 0.5f*(m_akBlock[0].GetMax() + m_akBlock[0].GetMin());
    Vector3f kDiag = 0.5f*(m_akBlock[0].GetMax() - m_akBlock[0].GetMin());
    m_kBound.Center() = kCenter;
    m_kBound.Radius() = kDiag.Length();

    // allocate queue
    m_usQueueQuantity = m_usBlockQuantity - m_usBlockQuantity/4;
    m_ausQueue = new unsigned short[m_usQueueQuantity];

    // root of quadtree is initially active
    m_ausQueue[0] = 0;
    m_usFront = 0;
    m_usRear = 1;
    m_usItemsInQueue = 1;
}
//----------------------------------------------------------------------------
void TerrainPage::SetPixelTolerance (Renderer* pkRenderer, float fTolerance)
{
    float fWidth = float(pkRenderer->GetWidth());
    CameraPtr spCamera = pkRenderer->GetCamera();
    float fRight = spCamera->GetFrustumRight();
    float fNear = spCamera->GetFrustumNear();

    m_fPixelTolerance = fTolerance;
    m_fWorldTolerance = 2.0f*fRight*m_fPixelTolerance/(fNear*fWidth);
    m_fWorldTolerance *= m_fWorldTolerance;
}
//----------------------------------------------------------------------------
float TerrainPage::GetHeight (const Vector2f& rkLocation) const
{
    float fXGrid = (rkLocation.X() - m_kOrigin.X())*m_fInvSpacing;
    if ( fXGrid < 0.0f || fXGrid >= float(m_usSizeM1) )
    {
        // location not in page
        return Mathf::MAX_REAL;
    }

    float fYGrid = (rkLocation.Y() - m_kOrigin.Y())*m_fInvSpacing;
    if ( fYGrid < 0.0f || fYGrid >= float(m_usSizeM1) )
    {
        // location not in page
        return Mathf::MAX_REAL;
    }

    float fCol = floorf(fXGrid);
    unsigned short usCol = (unsigned short) fCol;
    float fRow = floorf(fYGrid);
    unsigned short usRow = (unsigned short) fRow;

    unsigned short usIndex = usCol + m_usSize*usRow;
    float fDx = fXGrid - fCol;
    float fDy = fYGrid - fRow;
    float fH00, fH10, fH01, fH11, fHeight;

    if ( (usCol & 1) == (usRow & 1) )
    {
        float fDiff = fDx - fDy;
        fH00 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex];
        fH11 = m_fMinElevation + m_fMultiplier *
            m_ausHeight[usIndex+1+m_usSize];
        if ( fDiff > 0.0f )
        {
            fH10 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex+1];
            fHeight = (1.0f-fDiff-fDy)*fH00+fDiff*fH10+fDy*fH11;
        }
        else
        {
            fH01 = m_fMinElevation + m_fMultiplier *
                m_ausHeight[usIndex+m_usSize];
            fHeight = (1.0f+fDiff-fDx)*fH00-fDiff*fH01+fDx*fH11;
        }
    }
    else
    {
        float fSum = fDx + fDy;
        fH10 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex+1];
        fH01 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex+m_usSize];
        if ( fSum <= 1.0f )
        {
            fH00 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex];
            fHeight = (1.0f-fSum)*fH00+fDx*fH10+fDy*fH01;
        }
        else
        {
            fH11 = m_fMinElevation + m_fMultiplier *
                m_ausHeight[usIndex+1+m_usSize];
            fHeight = (fSum-1.0f)*fH11+(1.0f-fDy)*fH10+(1.0f-fDx)*fH01;
        }
    }

    return fHeight;
}
//----------------------------------------------------------------------------
bool TerrainPage::IntersectFrustum (const Camera* pkCamera)
{
    // check if terrain page itself is inside frustum
    m_akBlock[0].TestIntersectFrustum(this,pkCamera);
    bool bIntersect = m_akBlock[0].GetVisible();
    m_akBlock[0].ClearBits();
    return bIntersect;
}
//----------------------------------------------------------------------------
void TerrainPage::AddToQueue (unsigned short usBlock)
{
    m_ausQueue[m_usRear] = usBlock;
    if ( ++m_usRear == m_usQueueQuantity )
        m_usRear = 0;
    m_usItemsInQueue++;
}
//----------------------------------------------------------------------------
unsigned short TerrainPage::RemoveFromQueue ()
{
    unsigned short usBlock = m_ausQueue[m_usFront];
    if ( ++m_usFront == m_usQueueQuantity )
        m_usFront = 0;
    m_usItemsInQueue--;
    return usBlock;
}
//----------------------------------------------------------------------------
unsigned short TerrainPage::ReadFromQueue (unsigned short usIndex)
{
    usIndex += m_usFront;
    if ( usIndex < m_usQueueQuantity )
        return m_ausQueue[usIndex];
    else
        return m_ausQueue[usIndex - m_usQueueQuantity];
}
//----------------------------------------------------------------------------
void TerrainPage::ResetBlocks ()
{
    unsigned short usQueue, usBlock;
    if ( m_usFront < m_usRear )
    {
        m_usNumUnprocessed = m_usRear - m_usFront;
        for (usQueue = m_usFront; usQueue < m_usRear; usQueue++)
        {
            usBlock = m_ausQueue[usQueue];
            if ( m_akBlock[usBlock].BitsSet() )
            {
                m_akBlock[usBlock].Disable(this);
                m_akBlock[usBlock].ClearBits();
            }
        }
    }
    else
    {
        m_usNumUnprocessed = m_usQueueQuantity - m_usFront + m_usRear;
        for (usQueue = m_usFront; usQueue < m_usQueueQuantity; usQueue++)
        {
            usBlock = m_ausQueue[usQueue];
            if ( m_akBlock[usBlock].BitsSet() )
            {
                m_akBlock[usBlock].Disable(this);
                m_akBlock[usBlock].ClearBits();
            }
        }
        for (usQueue = 0; usQueue < m_usRear; usQueue++)
        {
            usBlock = m_ausQueue[usQueue];
            if ( m_akBlock[usBlock].BitsSet() )
            {
                m_akBlock[usBlock].Disable(this);
                m_akBlock[usBlock].ClearBits();
            }
        }
    }
}
//----------------------------------------------------------------------------
void TerrainPage::SimplifyBlocks (const Camera* pkCamera,
    const Vector3f& rkModelEye, const Vector3f& rkModelDir,
    bool bCloseAssumption)
{
    while ( m_usNumUnprocessed > 0 )
    {
        // process the block in the front of queue
        unsigned short usBlock = RemoveFromQueue();
        TerrainBlock* pkBlock = &m_akBlock[usBlock];

        if ( !pkBlock->GetProcessed() )
        {
            m_usNumUnprocessed--;

            unsigned short usChild;
            TerrainBlock* pkChild;
            Vector2f kCLoc;
            int i;

            if ( pkBlock->IsFirstChild(usBlock) )
            {
                // first child has responsibility for replacing by parent
                if ( pkBlock->IsSibling(usBlock,ReadFromQueue(2)) )
                {
                    pkChild = pkBlock;
                    if ( bCloseAssumption )
                    {
                        for (i = 0; i < 4; i++, pkChild++)
                        {
                            kCLoc.X() = pkChild->GetX()*m_fSpacing +
                                m_kOrigin.X();
                            kCLoc.Y() = pkChild->GetY()*m_fSpacing +
                                m_kOrigin.Y();
                            pkChild->ComputeInterval(rkModelEye,rkModelDir,
                                m_fWorldTolerance,kCLoc,m_fSpacing);
                            if (pkChild->GetDeltaMax() > pkChild->GetDeltaL())
                                break;
                        }
                    }
                    else // distant assumption
                    {
                        for (i = 0; i < 4; i++, pkChild++)
                        {
                            pkChild->ComputeInterval(rkModelEye,
                                m_fWorldTolerance);
                            if (pkChild->GetDeltaMax() > pkChild->GetDeltaL())
                                break;
                        }
                    }

                    if ( i == 4 )
                    {
                        // remove child blocks (first child already removed)
                        for (i = 0; i < 3; i++)
                        {
                            usChild = RemoveFromQueue();
                            if ( !m_akBlock[usChild].GetProcessed() )
                                m_usNumUnprocessed--;
                            m_akBlock[usChild].ClearBits();
                        }

                        // add parent block
                        unsigned short usParent =
                            pkBlock->GetParentIndex(usBlock);
                        AddToQueue(usParent);
                        assert( !m_akBlock[usParent].GetProcessed() );
                        m_usNumUnprocessed++;
                        continue;
                    }
                }
            }

            if ( !pkBlock->GetVisibilityTested() )
                pkBlock->TestIntersectFrustum(this,pkCamera);

            if ( pkBlock->GetStride() > 1 )
            {
                // subdivide only if bounding box of block intersects frustum
                if ( pkBlock->GetVisible() )
                {
                    usChild = pkBlock->GetChildIndex(usBlock,1);
                    pkChild = &m_akBlock[usChild];
                    if ( bCloseAssumption ) 
                    {
                        for (i = 0; i < 4; i++, pkChild++)
                        {
                            kCLoc.X() = pkChild->GetX()*m_fSpacing +
                                m_kOrigin.X();
                            kCLoc.Y() = pkChild->GetY()*m_fSpacing +
                                m_kOrigin.Y();
                            pkChild->ComputeInterval(rkModelEye,rkModelDir,
                                m_fWorldTolerance,kCLoc,m_fSpacing);
                            if (pkChild->GetDeltaMax() > pkChild->GetDeltaL())
                                break;
                        }
                    }
                    else // distant assumption
                    {
                        for (i = 0; i < 4; i++, pkChild++)
                        {
                            pkChild->ComputeInterval(rkModelEye,
                                m_fWorldTolerance);
                            if (pkChild->GetDeltaMax() > pkChild->GetDeltaL())
                                break;
                        }
                    }

                    // subdivide only if children all agree it should happen
                    if ( i < 4 )
                    {
                        // add child blocks (parent already removed)
                        for (i = 0; i < 4; i++, usChild++)
                        {
                            // add child block
                            AddToQueue(usChild);
                            assert( !m_akBlock[usChild].GetProcessed() );
                            m_usNumUnprocessed++;
                        }
                        continue;
                    }
                }
            }

            // tag block as processed
            pkBlock->SetProcessed(true);
        }

        // put processed block at rear of queue
        AddToQueue(usBlock);
    }
}