mgcbsptree.cpp

3D Game Engine Design Source Code非常棒

// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// RESTRICTED USE SOURCE CODE
// http://www.magic-software.com/License/restricted.pdf

#include "MgcBspTree.h"
#include "MgcColor.h"
#include "MgcVector2.h"

MgcImplementRTTI(MgcBspTree,MgcBspNode);
MgcImplementStream(MgcBspTree);

//---------------------------------------------------------------------------
MgcBspTree::MgcBspTree (TriangleList& rkList)
{
    assert( rkList.GetQuantity() > 0 );
    CreateTree(rkList);
}
//---------------------------------------------------------------------------
MgcBspTree::MgcBspTree ()
{
}
//---------------------------------------------------------------------------
MgcBspTree::Triangle::Triangle ()
{
    memset(m_apkNormal,0,3*sizeof(MgcVector3*));
    memset(m_apkColor,0,3*sizeof(MgcColor*));
    memset(m_apkTexture,0,3*sizeof(MgcVector2*));
}
//---------------------------------------------------------------------------
void MgcBspTree::CreateTree (TriangleList& rkList)
{
    // construct plane of first triangle in list
    Triangle* pkTri;
    rkList.RemoveFront(pkTri);
    m_kModelPlane = MgcPlane(pkTri->m_akVertex[0],pkTri->m_akVertex[1],
        pkTri->m_akVertex[2]);

    // place first triangle on node's coincident list
    TriangleList* pkCoincident = new TriangleList;
    pkCoincident->Add(pkTri);
    m_pvData = pkCoincident;

    if ( rkList.GetQuantity() > 0 )
    {
        // split remaining triangles against plane
        TriangleList kPositive, kNegative;
        while ( rkList.GetQuantity() > 0 )
        {
            rkList.RemoveFront(pkTri);
            SplitTriangle(pkTri,kPositive,kNegative,*pkCoincident);
        }

        // recurse on left child
        if ( kPositive.GetQuantity() > 0 )
        {
            MgcBspTree* pkLeftChild = new MgcBspTree(kPositive);
            AttachLeftChild(pkLeftChild);
        }

        // recurse on right child
        if ( kNegative.GetQuantity() > 0 )
        {
            MgcBspTree* pkRightChild = new MgcBspTree(kNegative);
            AttachRightChild(pkRightChild);
        }
    }
    else
    {
        // TO DO.  This node has no children.  Create an MgcTriMesh from
        // the
    }
}
//---------------------------------------------------------------------------
void MgcBspTree::SplitTriangle (Triangle* pkTri, TriangleList& rkPositive,
    TriangleList& rkNegative, TriangleList& rkCoincident)
{
    // compute signed pseudodistances
    const MgcReal fEpsilon = 1e-06;
    MgcReal afDistance[3];
    int i, iPosCount = 0, iNegCount = 0;
    for (i = 0; i < 3; i++)
    {
        afDistance[i] = m_kModelPlane.DistanceTo(pkTri->m_akVertex[i]);
        if ( afDistance[i] > fEpsilon )
            iPosCount++;
        else if ( afDistance[i] < -fEpsilon )
            iNegCount--;
        else
            afDistance[i] = 0.0;
    }

    if ( iPosCount > 0 )
    {
        if ( iNegCount == 0 )
        {
            // triangle is on positive side of plane
            rkPositive.Add(pkTri);
            return;
        }
    }
    else
    {
        if ( iNegCount > 0 )
        {
            // triangle is on negative side of plane
            rkNegative.Add(pkTri);
        }
        else
        {
            // triangle is contained in plane
            rkCoincident.Add(pkTri);
        }
        return;
    }

    // triangle straddles plane and must be split
    if ( afDistance[0]*afDistance[1] < 0.0 )
    {
        ClipTriangle(0,1,2,pkTri,afDistance,rkPositive,rkNegative);
        return;
    }

    if ( afDistance[2]*afDistance[0] < 0.0 )
    {
        ClipTriangle(2,0,1,pkTri,afDistance,rkPositive,rkNegative);
        return;
    }

    if ( afDistance[1]*afDistance[2] < 0.0 )
    {
        ClipTriangle(1,2,0,pkTri,afDistance,rkPositive,rkNegative);
        return;
    }

    // Distances are all nonnegative or all nonpositive.  This should have
    // been caught by ((iPos > 0 && iNeg == 0) || (iPos == 0 && iNeg > 0)),
    // but just in case of numerical round-off errors screwing up the
    // theory...
    assert( false );
}
//---------------------------------------------------------------------------
void MgcBspTree::ClipTriangle (int i0, int i1, int i2, Triangle* pkTri,
    MgcReal afDistance[3], TriangleList& rkPositive,
    TriangleList& rkNegative)
{
    // Warning.  The normal interpolation is a convex combination of the
    // normals that is unitized.  You might want to use SLERP to get a more
    // standard interpolation.

    MgcReal fD0 = afDistance[i0];
    MgcReal fD1 = afDistance[i1];
    MgcReal fD2 = afDistance[i2];
    MgcVector3& rkV0 = pkTri->m_akVertex[i0];
    MgcVector3& rkV1 = pkTri->m_akVertex[i1];
    MgcVector3& rkV2 = pkTri->m_akVertex[i2];

    bool bHasNormals = (pkTri->m_apkNormal[0] != 0);
    MgcVector3* apkN[3];
    if ( bHasNormals )
    {
        apkN[0] = pkTri->m_apkNormal[0];
        apkN[1] = pkTri->m_apkNormal[1];
        apkN[2] = pkTri->m_apkNormal[2];
    }

    bool bHasColors = (pkTri->m_apkColor[0] != 0);
    MgcColor* apkC[3];
    if ( bHasColors )
    {
        apkC[0] = pkTri->m_apkColor[0];
        apkC[1] = pkTri->m_apkColor[1];
        apkC[2] = pkTri->m_apkColor[2];
    }

    bool bHasTextures = (pkTri->m_apkTexture[0] != 0);
    MgcVector2* apkT[3];
    if ( bHasTextures )
    {
        apkT[0] = pkTri->m_apkTexture[0];
        apkT[1] = pkTri->m_apkTexture[1];
        apkT[2] = pkTri->m_apkTexture[2];
    }

    // clip edge <I0,I1>
    MgcReal fT = fD0/(fD0 - fD1);
    MgcVector3 kV01 = rkV0 + fT*(rkV1 - rkV0);

    MgcVector3 kN01;
    if ( bHasNormals )
    {
        kN01 = *apkN[i0] + fT*(*apkN[i1] - *apkN[i0]);
        kN01.Unitize();
    }

    MgcColor kC01;
    if ( bHasColors )
        kC01 = *apkC[i0] + fT*(*apkC[i1] - *apkC[i0]);

    MgcVector2 kT01;
    if ( bHasTextures )
        kT01 = *apkT[i0] + fT*(*apkT[i1] - *apkT[i0]);

    MgcVector3 kV12, kN12;
    MgcColor kC12;
    MgcVector2 kT12;

    if ( fD0 > 0.0 )
    {
        if ( fD2 > 0.0 )
        {
            // clip edge <I1,I2>
            fT = fD1/(fD1 - fD2);
            kV12 = rkV1 + fT*(rkV2 - rkV1);

            if ( bHasNormals )
            {
                kN12 = *apkN[i1] + fT*(*apkN[i2] - *apkN[i1]);
                kN12.Unitize();
            }

            if ( bHasColors )
                kC12 = *apkC[i1] + fT*(*apkC[i2] - *apkC[i1]);

            if ( bHasTextures )
                kT12 = *apkT[i1] + fT*(*apkT[i2] - *apkT[i1]);

            AddTriangle(rkPositive,kV01,kV12,rkV0,bHasNormals,&kN01,&kN12,
                apkN[i0],bHasColors,&kC01,&kC12,apkC[i0],bHasTextures,&kT01,
                &kT12,apkT[i0]);

            AddTriangle(rkPositive,kV12,rkV2,rkV0,bHasNormals,&kN12,apkN[i2],
                apkN[i0],bHasColors,&kC12,apkC[i2],apkC[i0],bHasTextures,
                &kT12,apkT[i2],apkT[i0]);

            AddTriangle(rkNegative,kV01,rkV1,kV12,bHasNormals,&kV01,apkN[i1],
                &kN12,bHasColors,&kC01,apkC[i1],&kC12,bHasTextures,&kT01,
                apkT[i1],&kT12);
        }
        else if ( fD2 < 0.0 )
        {
            // clip edge <I0,I2>
            fT = fD2/(fD2 - fD0);
            kV12 = rkV2 + fT*(rkV0 - rkV2);

            if ( bHasNormals )
            {
                kN12 = *apkN[i2] + fT*(*apkN[i0] - *apkN[i2]);
                kN12.Unitize();
            }

            if ( bHasColors )
                kC12 = *apkC[i2] + fT*(*apkC[i0] - *apkC[i2]);

            if ( bHasTextures )
                kT12 = *apkT[i2] + fT*(*apkT[i0] - *apkT[i2]);

            AddTriangle(rkPositive,kV01,kV12,rkV0,bHasNormals,&kN01,&kN12,
                apkN[i0],bHasColors,&kC01,&kC12,apkC[i0],bHasTextures,&kT01,
                &kT12,apkT[i0]);

            AddTriangle(rkNegative,kV01,rkV1,rkV2,bHasNormals,&kN01,apkN[i1],
                apkN[i2],bHasColors,&kC01,apkC[i1],apkC[i2],bHasTextures,
                &kT01,apkT[i1],apkT[i2]);

            AddTriangle(rkNegative,kV01,rkV2,kV12,bHasNormals,&kN01,apkN[i2],
                &kN12,bHasColors,&kC01,apkC[i2],&kC12,bHasTextures,&kT01,
                apkT[i2],&kT12);
        }
        else
        {
            AddTriangle(rkPositive,kV01,rkV2,rkV0,bHasNormals,&kN01,apkN[i2],
                apkN[i0],bHasColors,&kC01,apkC[i2],apkC[i0],bHasTextures,
                &kT01,apkT[i2],apkT[i0]);

            AddTriangle(rkNegative,kV01,rkV1,rkV2,bHasNormals,&kN01,apkN[i1],
                apkN[i2],bHasColors,&kC01,apkC[i1],apkC[i2],bHasTextures,
                &kT01,apkT[i1],apkT[i2]);
        }
    }
    else
    {
        if ( fD2 > 0.0 )
        {
            // clip edge <I0,I2>
            fT = fD0/(fD0 - fD2);
            kV12 = rkV0 + fT*(rkV2 - rkV0);

            if ( bHasNormals )
            {
                kN12 = *apkN[i0] + fT*(*apkN[i2] - *apkN[i0]);
                kN12.Unitize();
            }

            if ( bHasColors )
                kC12 = *apkC[i0] + fT*(*apkC[i2] - *apkC[i0]);

            if ( bHasTextures )
                kT12 = *apkT[i0] + fT*(*apkT[i2] - *apkT[i0]);

            AddTriangle(rkPositive,kV01,rkV1,rkV2,bHasNormals,&kN01,apkN[i1],
                apkN[i2],bHasColors,&kC01,apkC[i1],apkC[i2],bHasTextures,
                &kT01,apkT[i1],apkT[i2]);

            AddTriangle(rkPositive,kV01,rkV2,kV12,bHasNormals,&kN01,apkN[i2],
                &kN12,bHasColors,&kC01,apkC[i2],&kC12,bHasTextures,&kT01,
                apkT[i2],&kT12);

            AddTriangle(rkNegative,kV01,kV12,rkV0,bHasNormals,&kN01,&kN12,
                apkN[i0],bHasColors,&kC01,&kC12,apkC[i0],bHasTextures,&kT01,
                &kT12,apkT[i0]);
        }
        else if ( fD2 < 0.0 )
        {
            // clip edge <I1,I2>
            fT = fD2/(fD2 - fD1);
            kV12 = rkV2 + fT*(rkV1 - rkV2);

            if ( bHasNormals )
            {
                kN12 = *apkN[i2] + fT*(*apkN[i1] - *apkN[i2]);
                kN12.Unitize();
            }

            if ( bHasColors )
                kC12 = *apkC[i2] + fT*(*apkC[i1] - *apkC[i2]);

            if ( bHasTextures )
                kT12 = *apkT[i2] + fT*(*apkT[i1] - *apkT[i2]);

            AddTriangle(rkPositive,kV01,rkV1,kV12,bHasNormals,&kN01,apkN[i1],
                &kN12,bHasColors,&kC01,apkC[i1],&kC12,bHasTextures,&kT01,
                apkT[i1],&kT12);

            AddTriangle(rkNegative,rkV0,kV01,kV12,bHasNormals,apkN[i0],&kN01,
                &kN12,bHasColors,apkC[i0],&kC01,&kC12,bHasTextures,apkT[i0],
                &kT01,&kT12);

            AddTriangle(rkNegative,rkV0,kV12,rkV2,bHasNormals,apkN[i0],&kN01,
                apkN[i2],bHasColors,apkC[i0],&kC12,apkC[i2],bHasTextures,
                apkT[i0],&kT12,apkT[i2]);
        }
        else
        {
            AddTriangle(rkPositive,kV01,rkV1,rkV2,bHasNormals,&kN01,apkN[i1],
                apkN[i2],bHasColors,&kC01,apkC[i1],apkC[i2],bHasTextures,
                &kT01,apkT[i1],apkT[i2]);

            AddTriangle(rkNegative,kV01,rkV2,rkV0,bHasNormals,&kN01,apkN[i2],
                apkN[i0],bHasColors,&kC01,apkC[i2],apkC[i0],bHasTextures,
                &kT01,apkT[i2],apkT[i0]);
        }
    }
}
//---------------------------------------------------------------------------
void MgcBspTree::AddTriangle (TriangleList& rkList, const MgcVector3& rkV0,
    const MgcVector3& rkV1, const MgcVector3& rkV2, bool bHasNormals,
    const MgcVector3* pkN0, const MgcVector3* pkN1, const MgcVector3* pkN2,
    bool bHasColors, const MgcColor* pkC0, const MgcColor* pkC1,
    const MgcColor* pkC2, bool bHasTextures, const MgcVector2* pkT0,
    const MgcVector2* pkT1, const MgcVector2* pkT2)
{
    Triangle* pkClipTri = new Triangle;
    rkList.Add(pkClipTri);

    pkClipTri->m_akVertex[0] = rkV0;
    pkClipTri->m_akVertex[1] = rkV1;
    pkClipTri->m_akVertex[2] = rkV2;

    if ( bHasNormals )
    {
        pkClipTri->m_apkNormal[0] = new MgcVector3;
        pkClipTri->m_apkNormal[1] = new MgcVector3;
        pkClipTri->m_apkNormal[2] = new MgcVector3;
        *pkClipTri->m_apkNormal[0] = *pkN0;
        *pkClipTri->m_apkNormal[1] = *pkN1;
        *pkClipTri->m_apkNormal[2] = *pkN2;
    }

    if ( bHasColors )
    {
        pkClipTri->m_apkColor[0] = new MgcColor;
        pkClipTri->m_apkColor[1] = new MgcColor;
        pkClipTri->m_apkColor[2] = new MgcColor;
        *pkClipTri->m_apkColor[0] = *pkC0;
        *pkClipTri->m_apkColor[1] = *pkC1;
        *pkClipTri->m_apkColor[2] = *pkC2;
    }

    if ( bHasTextures )
    {
        pkClipTri->m_apkTexture[0] = new MgcVector2;
        pkClipTri->m_apkTexture[1] = new MgcVector2;
        pkClipTri->m_apkTexture[2] = new MgcVector2;
        *pkClipTri->m_apkTexture[0] = *pkT0;
        *pkClipTri->m_apkTexture[1] = *pkT1;
        *pkClipTri->m_apkTexture[2] = *pkT2;
    }
}
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// streaming
//---------------------------------------------------------------------------
MgcObject* MgcBspTree::Factory (MgcStream& rkStream)
{
    MgcBspTree* pkObject = new MgcBspTree;
    MgcStream::Link* pkLink = new MgcStream::Link(pkObject);
    pkObject->Load(rkStream,pkLink);
    return pkObject;
}
//---------------------------------------------------------------------------
void MgcBspTree::Load (MgcStream& rkStream, MgcStream::Link* pkLink)
{
    MgcBspNode::Load(rkStream,pkLink);
}
//---------------------------------------------------------------------------
void MgcBspTree::Link (MgcStream& rkStream, MgcStream::Link* pkLink)
{
    MgcBspNode::Link(rkStream,pkLink);
}
//---------------------------------------------------------------------------
bool MgcBspTree::Register (MgcStream& rkStream)
{
    return MgcBspNode::Register(rkStream);
}
//---------------------------------------------------------------------------
void MgcBspTree::Save (MgcStream& rkStream)
{
    MgcBspNode::Save(rkStream);
}
//---------------------------------------------------------------------------