K3dVorBsp.cpp

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2007 by Jan Koci   *
 *   honza.koci@email.cz   *
 *   http://kengine.sourceforge.net/tutorial/
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#include "K3dVorBsp.h"

K3dVorBsp::K3dVorBsp(K3dGameData *_pGameData)
{
        m_pGameData = _pGameData;
        m_iWeigh = 0;
        m_pCentre = m_pGameData->GetVector3SP().New();
        m_pBestDivPlane = NULL;
}

K3dVorBsp::~K3dVorBsp()
{
        cout << "K3dVorBsp::~K3dVorBsp()" << endl;
        m_pCentre = m_pGameData->GetVector3SP().Delete(m_pCentre);
}

void K3dVorBsp::FindNearestVertex( const EVorBspPlaneSide _ePlaneSide)
{
        float fMinDist = (float) K_MAX_SCENE_LENGTH;
        switch(_ePlaneSide)
        {
                case K_VOR_BSP_PLANE_SIDE_FRONT:
                        // Go through all front side vertices
                        for(int i=0; i<(int) m_vFront.size(); i++)
                        {
                                // Get vertex
                                K3dVertex *pVertex = m_vFront[i];
                                // Find nearest vertex
                                K3dVector3Obj *pPoint = pVertex->GetPosition();
                                float fDist = m_pGameData->GetIntersection()->PointPlane( *m_pBestDivPlane, *pPoint);
                                // If doesn`t point on the plane
                                if (fDist != 0)
                                {
                                        if(fDist < fMinDist)
                                        {
                                                fMinDist = fDist;
                                                m_pNearestVertex = pPoint;
                                                if(m_pNearestVertex != pPoint)
                                                {
                                                        m_pNearestVertex = pPoint;
                                                }
                                        }
                                }
                        }
                        break;
                case K_VOR_BSP_PLANE_SIDE_BACK:
                        // Go through all back side vertices
                        for(int i=0; i<(int) m_vBack.size(); i++)
                        {
                                // Get vertex
                                K3dVertex *pVertex = m_vBack[i];
                                // Find nearest vertex
                                K3dVector3Obj *pPoint = pVertex->GetPosition();
                                float fDist = m_pGameData->GetIntersection()->PointPlane( *m_pBestDivPlane, *pPoint);
                                // If doesn`t point on the plane
                                if (fDist != 0)
                                {
                                        // Distance on back size is negative, so set positive distace
                                        fDist = -fDist;
                                        if(fDist < fMinDist)
                                        {
                                                fMinDist = fDist;
                                                if(m_pNearestVertex != pPoint)
                                                {
                                                        m_pNearestVertex = pPoint;
                                                }
                                        }
                                }
                        }
                        break;
                default:
                        break;
        }
}

void K3dVorBsp::MovePlane()
{
        // Calculate potectial number of plane move steps
        int iSteps = (int) ((float) m_iWeigh *(float) 0.5);
        if(((int) m_vFront.size()) > ((int) m_vBack.size()))
        {
                // Move with plane to front side
                for(int i=0; i<iSteps; i++)
                {
                        // Find nearest vertex on front side
                        FindNearestVertex(K_VOR_BSP_PLANE_SIDE_FRONT);
                        // Move plane to the nearest vertex position
                        m_pBestDivPlane->SetPosition(m_pNearestVertex);
                        m_pGameData->GetPlaneWork()->CalcDistance(m_pBestDivPlane);
                }
        }
        else
        {
                // Move with plane to back side
                for(int i=0; i<iSteps; i++)
                {
                        // Find nearest vertex on front side
                        FindNearestVertex(K_VOR_BSP_PLANE_SIDE_BACK);
                        // Move plane to the nearest vertex position
                        m_pBestDivPlane->SetPosition(m_pNearestVertex);
                        m_pGameData->GetPlaneWork()->CalcDistance(m_pBestDivPlane);
                }
        }
}

bool K3dVorBsp::CheckWeight()
{
        if((m_vFront.size() == 0) || (m_vBack.size() == 0 ))
        {
                return false;
        }
        m_iWeigh = (int) m_vFront.size() - (int) m_vBack.size();
        // Set positive number
        m_iWeigh = K3dMath::Positive( m_iWeigh);
        if(m_iWeigh > 2)
        {
                return false;
        }
        return true;
}

void K3dVorBsp::CalcFrontBackVertices()
{
        // Clear front back and onplane vertex array
        m_vFront.clear();
        m_vBack.clear();
        // Go through all vertices
        for(int i=0; i<(int) m_vVertex.size(); i++)
        {
                // Get vertex
                K3dVertexObj *pVertex = m_vVertex[i];
                // Test if vertex on front or back side of plane
                K3dVector3Obj *pPos = pVertex->GetPosition();
                float fDist = m_pGameData->GetIntersection()->PointPlane( *m_pBestDivPlane, *pPos);
                if(fDist >= 0)
                {
                        m_vFront.push_back(pVertex);
                }
                else
                {
                        m_vBack.push_back(pVertex);
                }
        }
}

void K3dVorBsp::CalcVertexArrayCentre()
{
        // Get number of vertices
        int iNum = (int) m_vVertex.size();
        m_pCentre->Reset();
        
        // Go through all vertices
        for(int i=0; i<iNum; i++)
        {
                K3dVector3Obj *pPos = m_vVertex[i]->GetPosition();
                *m_pCentre += *pPos;
        }
        if(iNum > 0)
        {
                *m_pCentre /= (float) iNum;
        }
}

void K3dVorBsp::SetPlane()
{
        // Create plane
        switch(m_ePlane)
        {
                case K_VOR_BSP_PLANE_X:
                        *m_pBestDivPlane->GetPosition() = *m_pCentre;
                        m_pBestDivPlane->GetNormal()->Set((float)1, (float)0, (float)0);
                        m_pGameData->GetPlaneWork()->Init(m_pBestDivPlane);
                        break;
                case K_VOR_BSP_PLANE_Y:
                        *m_pBestDivPlane->GetPosition() = *m_pCentre;
                        m_pBestDivPlane->GetNormal()->Set((float)0, (float)1, (float)0);
                        m_pGameData->GetPlaneWork()->Init(m_pBestDivPlane);
                        break;
                case K_VOR_BSP_PLANE_Z:
                        *m_pBestDivPlane->GetPosition() = *m_pCentre;
                        m_pBestDivPlane->GetNormal()->Set((float)0, (float)0, (float)1);
                        m_pGameData->GetPlaneWork()->Init(m_pBestDivPlane);
                        break;
                default:
                        break;
        }
}

void K3dVorBsp::ChangePlaneNormal()
{
        // Create plane
        switch(m_ePlane)
        {
                case K_VOR_BSP_PLANE_X:
                        m_ePlane = K_VOR_BSP_PLANE_Y;
                        SetPlane();
                        break;
                case K_VOR_BSP_PLANE_Y:
                        m_ePlane = K_VOR_BSP_PLANE_Z;
                        SetPlane();
                        break;
                case K_VOR_BSP_PLANE_Z:
                        m_ePlane = K_VOR_BSP_PLANE_X;
                        SetPlane();
                        break;
                default:
                        m_ePlane = K_VOR_BSP_PLANE_X;
                        SetPlane();
                        break;
        }
}

K3dPlaneObj *K3dVorBsp::FindBestDividingPlane(const TVertexArray &_rvVertex, const EVorBspPlane &_ePlane)
{
        m_vVertex = _rvVertex;
        if(m_vVertex.size() >= 3)
        {
                m_pBestDivPlane = m_pGameData->GetPlaneBuild()->CreateNewPlaneObj();
                m_ePlane = _ePlane;
                // Calculate centre of vertex array
                CalcVertexArrayCentre();
                // Set plane position and normal vector
                SetPlane();
                // Calculate number of vertices on front and back plane side
                CalcFrontBackVertices();
                // Check weight between front and back vertices
                while(!CheckWeight())
                {
                        if((m_vFront.size() == 0) || (m_vBack.size() == 0))
                        {
                                // Change plane normal
                                ChangePlaneNormal();
                                CalcFrontBackVertices();
                        }
                        else
                        {
                                // If wrong weigh, move plane to the better position
                                MovePlane();
                                CalcFrontBackVertices();
                        }
                }
                return m_pBestDivPlane;
        }
        else
        {
                cerr << "Error -- K3dVorBsp::FindBestDividingPlane() -- Vertex array must contains min 3 vertices" << endl;
                return NULL;
        }
}

---