source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsParser.cpp @ 2543

// ---------------------------------------------------------------------------
//  Includes for all the program files to see
// ---------------------------------------------------------------------------
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <xercesc/util/PlatformUtils.hpp>

// ---------------------------------------------------------------------------
//  Includes
// ---------------------------------------------------------------------------
#include <xercesc/framework/StdInInputSource.hpp>
#include <xercesc/parsers/SAXParser.hpp>
#include <xercesc/util/OutOfMemoryException.hpp>

// ---------------------------------------------------------------------------
//  Includes
// ---------------------------------------------------------------------------
#include <xercesc/sax/AttributeList.hpp>
#include <xercesc/sax/SAXParseException.hpp>
#include <xercesc/sax/SAXException.hpp>

#include "ViewCellsParser.h"

#include "ViewCellsParserXerces.h"
#include "Mesh.h"
#include "VspBspTree.h"
#include "ViewCellBsp.h"
#include "ViewCellsManager.h"
#include "GzFileInputSource.h"
#include "OspTree.h"
#include "VspTree.h"
#include "KdTree.h"
#include "BvHierarchy.h"
#include "HierarchyManager.h"


using namespace std;

namespace GtpVisibilityPreprocessor {


// ---------------------------------------------------------------------------
//  Local data
//
//  doNamespaces
//      Indicates whether namespace processing should be enabled or not.
//      The default is no, but -n overrides that.
//
//  doSchema
//      Indicates whether schema processing should be enabled or not.
//      The default is no, but -s overrides that.
//
//  schemaFullChecking
//      Indicates whether full schema constraint checking should be enabled or not.
//      The default is no, but -s overrides that.
//
//  valScheme
//      Indicates what validation scheme to use. It defaults to 'auto', but
//      can be set via the -v= command.
// ---------------------------------------------------------------------------
static bool doNamespaces = false;
static bool doSchema = false;
static bool schemaFullChecking = false;
static SAXParser::ValSchemes valScheme = SAXParser::Val_Auto;

// hack for loading bvh nodes
#define PVS_HACK 0
#define USE_HASH_COMPARE 1


inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
{
        return obj1->mId < obj2->mId;
}


// ---------------------------------------------------------------------------
//  StdInParseHandlers: Constructors and Destructor
// ---------------------------------------------------------------------------
ViewCellsParseHandlers::ViewCellsParseHandlers(ObjectContainer &pvsObjects, 
                                                                                           ObjectContainer &preprocessorObjects,
                                                                                           BoundingBoxConverter *bconverter
                                                                                           ):
  mElementCount(0)
  , mAttrCount(0)
  , mCharacterCount(0)
  , mSpaceCount(0)
  , mViewCellsManager(NULL)
  , mVspBspTree(NULL)
  , mBspTree(NULL)
  , mViewCellsTree(NULL)
  , mCurrentState(PARSE_OPTIONS)
  , mCurrentViewCell(NULL)
  , mCurrentBspNode(NULL)
  , mCurrentVspNode(NULL)
  , mCurrentOspNode(NULL)
  , mCurrentBvhNode(NULL)
  , mPvsObjects(pvsObjects)
  , mPreprocessorObjects(preprocessorObjects)
  , mBoundingBoxConverter(bconverter)
  , mHierarchyManager(NULL)
  , nViewCells(0)
  , nObjects(0)
{
}


ViewCellsParseHandlers::~ViewCellsParseHandlers()
{
}


void ViewCellsParseHandlers::CreateHashVector()
{
        ObjectContainer::const_iterator oit, oit_end = mPvsObjects.end();

        for (oit = mPvsObjects.begin(); oit != oit_end; ++ oit)
        {
                mHashPvs[(*oit)->GetId()] = (*oit);
        }
        //Debug<<"\nhsize: " << mHashPvs.size() << endl;
}


// ---------------------------------------------------------------------------
//  StdInParseHandlers: Implementation of the SAX DocumentHandler interface
// ---------------------------------------------------------------------------


void ViewCellsParseHandlers::endElement(const XMLCh* const name)
{
        StrX lname(name);
        string element(lname.LocalForm());

        if (element == "BoundingBoxes")
        {
                EndBoundingBoxes();
        }
        else if (element == "ViewCells")
        {       
                EndViewCells();
                Debug << "view cell hierarchy parsed" << endl;
        }
        else if (element == "ObjectSpaceHierarchy")
        {
                EndObjectSpaceHierarchy();
                Debug << "object space hierarchy parsed" << endl;
                mObjectTimer.Exit();
        }
        // finished paring, create view cells manager
        else if (element == "VisibilitySolution")
        {
                CreateViewCellsManager();

                Debug << "pvs time: " << mPvsTimer.TotalTime() << endl;
                Debug << "object time: " << mObjectTimer.TotalTime() << endl;
                Debug << "box time: " << mBoxTimer.TotalTime() << endl;

        }
        else if (element == "Interior")
        {
                switch (mCurrentState)
                {
                case PARSE_VIEWCELLS:
                        EndViewCellInterior();
                        break;
                case PARSE_OBJECTSPACE_HIERARCHY:
                        EndObjectSpaceHierarchyInterior();
                        break;
                case PARSE_VIEWSPACE_HIERARCHY: 
                        EndViewSpaceHierarchyInterior();
                        break;
                default:
                        break;
                }
        }
}


void ViewCellsParseHandlers::EndObjectSpaceHierarchy()
{
        if (mObjectSpaceHierarchyType == OSP)
        {
                // for a spatial subdivision, it is not necessary to store
                // the objects with the leaves, they can be classified geometrically
                mHierarchyManager->mOspTree->
                        InsertObjects(mHierarchyManager->mOspTree->mRoot, mPvsObjects);
        }
}


void ViewCellsParseHandlers::EndViewSpaceHierarchyInterior()
{
        switch (mViewSpaceHierarchyType)
        {
        case BSP:
                EndBspInterior();
                break;
        case VSP:
                EndVspInterior();
                break;  
        default:
                Debug << "not implemented view space hierarchy type " << mViewSpaceHierarchyType << endl;
                break;
        }
}


void ViewCellsParseHandlers::EndObjectSpaceHierarchyInterior()
{
        switch (mObjectSpaceHierarchyType)
        {
        case OSP:
                EndOspInterior();
                break;
        case BVH:
                EndBvhInterior();
                break;  
        default:
                Debug << "not implemented object space hierarchy type " << mViewSpaceHierarchyType << endl;
                break;
        }
}


void ViewCellsParseHandlers::EndBspInterior()
{
        // go one up in the tree
        if (mCurrentBspNode->GetParent())
        {       //cout << "]";
                mCurrentBspNode = mCurrentBspNode->GetParent();
        }
}


void ViewCellsParseHandlers::EndBvhInterior()
{
        // go one up in the tree
        if (mCurrentBvhNode->GetParent())
        {       //cout << "]";
                mCurrentBvhNode = mCurrentBvhNode->GetParent();
        }
}


void ViewCellsParseHandlers::EndOspInterior()
{
        // go one up in the tree
        if (mCurrentOspNode->mParent)
        {       
                //cout << "]";
                mCurrentOspNode = mCurrentOspNode->mParent;
        }
}


void ViewCellsParseHandlers::EndVspInterior()
{
        // go one up in the tree
        if (mCurrentVspNode->GetParent())
        {       
                //cout << "]";
                mCurrentVspNode = mCurrentVspNode->GetParent();
        }
}


void ViewCellsParseHandlers::EndViewCellInterior()
{
        // go one up in the tree
        if (mCurrentViewCell->GetParent())
        {       
                //cout << "]";
                mCurrentViewCell = mCurrentViewCell->GetParent();
        }
}


inline static bool vlt(ViewCell *v1, ViewCell *v2)
{
        return v1->mId < v2->mId;
}


void ViewCellsParseHandlers::EndViewCells()
{
        // sort view cells to help associating view cells according to their id
        sort(mViewCells.begin(), mViewCells.end(), vlt);

        // not parsing view cells anymore
        mCurrentState = PARSE_OPTIONS;
}


void ViewCellsParseHandlers::EndBoundingBoxes()
{
        const long startTime = GetTime();
        
        mBoxTimer.Entry();

        if (mBoundingBoxConverter)
        {
                // all bounding boxes gathered in this step => 
                // associate object ids with bounding boxes
                mBoundingBoxConverter->IdentifyObjects(mIBoundingBoxes, mPvsObjects);
        }

        if (USE_HASH_COMPARE)
        {
                CreateHashVector();
        }
        else
        {
                // sort objects by id
                sort(mPvsObjects.begin(), mPvsObjects.end(), ilt);
        }

        Debug << "\nconverted bounding boxes to objects in "
                  << TimeDiff(startTime, GetTime()) * 1e-6 << " secs" << endl;

        mBoxTimer.Exit();
}


void ViewCellsParseHandlers::StartBspElement(string element,
                                                                                         AttributeList& attributes)
{
        if (element == "Interior") 
        {
                //cout << "[";
                StartBspInterior(attributes);
        }

        if (element == "Leaf") 
        {
                //cout << "l";
                StartBspLeaf(attributes);
        }
}


void ViewCellsParseHandlers::StartVspElement(string element,
                                                                                         AttributeList& attributes)
{
        if (element == "Interior") 
        {
                //cout << "[";
                StartVspInterior(attributes);
        }
        if (element == "Leaf") 
        {
                //cout << "l";
                StartVspLeaf(attributes);
        }
}


void ViewCellsParseHandlers::StartOspElement(string element,
                                                                                         AttributeList& attributes)
{
        if (element == "Interior") 
        {
                //cout << "[";
                StartOspInterior(attributes);
        }

        if (element == "Leaf") 
        {
                //cout << "l";
                StartOspLeaf(attributes);
        }
}


void ViewCellsParseHandlers::StartBvhElement(string element,
                                                                                         AttributeList& attributes)
{
        if (element == "Interior") 
        {
                //cout << "[";
                StartBvhInterior(attributes);
        }

        if (element == "Leaf") 
        {
                //cout << "l";
                StartBvhLeaf(attributes);
        }
}


void ViewCellsParseHandlers::StartViewSpaceHierarchyElement(const std::string &element,
                                                                                                                        AttributeList& attributes)
{
        //-- use cell type according to the chosen method
        switch (mViewSpaceHierarchyType)
        {
        case BSP:
                StartBspElement(element, attributes);
                break;
        case VSP:
                StartVspElement(element, attributes);
                break;
        default:
                Debug << "not implemented" << endl;
                break;
        }
}


void ViewCellsParseHandlers::StartObjectSpaceHierarchyElement(const std::string &element,
                                                                                                                          AttributeList& attributes)
{
        //-- use cell type according to the chosen method
        switch (mObjectSpaceHierarchyType)
        {
                case OSP:
                        StartOspElement(element, attributes);
                        break;
                case BVH:
                        StartBvhElement(element, attributes);
                        break;
                default:
                        Debug << "not implemented" << endl;
                        break;
        }
}


void ViewCellsParseHandlers::StartViewCellHierarchyElement(const std::string &element,
                                                                                                                   AttributeList& attributes)
{
        // interiors + leaves interpreted view cells else
        if (element == "Interior") 
        {
                StartViewCell(attributes, false);
                return;
        }

        if (element == "Leaf") 
        {
                StartViewCell(attributes, true);
                return;
        }

        Debug << "StartViewCellHierarchyElement: should not come here: " << element << endl;
}


void ViewCellsParseHandlers::startElement(const XMLCh* const name,
                                                                                  AttributeList& attributes)
{
        StrX lname(name);
        string element(lname.LocalForm());

        if (element == "ViewCells")
        {
                cout << "\nparsing view cells" << endl;
                Debug << "\nparsing view cells" << endl;
                
                mCurrentState = PARSE_VIEWCELLS;

                // create new view cells hierarchy
                mViewCellsTree = new ViewCellsTree();
        }
        // decides about the view cell hierarchy
        else if (element == "ViewSpaceHierarchy")
        {               
                Debug << "\nparsing view space hierarchy" << endl;
                cout  << "\nparsing view space hierarchy" << endl;

                mCurrentState = PARSE_VIEWSPACE_HIERARCHY;
                StartViewSpaceHierarchy(attributes);
        }
        // decides about the view cell hierarchy
        else if (element == "ObjectSpaceHierarchy")
        {
                cout  << "\nparsing object space hierarchy" << endl;
                Debug << "\nparsing object space hierarchy" << endl;

                mCurrentState = PARSE_OBJECTSPACE_HIERARCHY;
                mObjectTimer.Entry();
                StartObjectSpaceHierarchy(attributes);
        }
        // decides the used view cell hierarchy
        else if (element == "BoundingBox")
        {
                StartBoundingBox(attributes);
        }
        else
        {
                // parse view space hierarchy
                switch (mCurrentState)
                {
                case PARSE_VIEWSPACE_HIERARCHY:
                        if ((++ nViewCells % 1000) == 0)
                        {
                                cout << "\r" << nViewCells << " view cells parsed\r";
                                Debug << nViewCells << " view cells parsed" << endl;
                        }
                        StartViewSpaceHierarchyElement(element, attributes);
                        break;
                case PARSE_OBJECTSPACE_HIERARCHY:
                        if ((++ nObjects % 1000) == 0)
                                cout <<"\r" << nObjects << " objects parsed\r";
                
                        StartObjectSpaceHierarchyElement(element, attributes);
                        break;
                case PARSE_VIEWCELLS:
                        StartViewCellHierarchyElement(element, attributes);
                        break;
                default:
                        break;
                }
        }
        
        ++ mElementCount;
        mAttrCount += attributes.getLength();
}


void ViewCellsParseHandlers::StartViewCellPvs(ObjectPvs &pvs, const char *ptr)
{
        // handle object indices
        vector<int> objIndices;
        char *endptr;
                        
        while (1)
        {       
                // read object ids
                const int index = strtol(ptr, &endptr, 10);
                
                if (ptr == endptr) 
                        break;
                
                objIndices.push_back(index);
                ptr = endptr;
        }

        mPvsTimer.Entry();

        Intersectable::NewMail();

        // TODO: 
        // 1) find objects and add them to pvs
        // 2) get view cell with specified id
        MeshInstance dummyInst(NULL);
        pair<ObjectContainer::const_iterator, ObjectContainer::const_iterator> result;

        vector<int>::const_iterator it, it_end = objIndices.end();
        
        for (it = objIndices.begin(); it != it_end; ++ it)
        {
                const int objId = *it;  
        
#if USE_HASH_COMPARE
                pvs_hash::iterator oit = mHashPvs.find(objId);

                if ((oit != mHashPvs.end()) && ((*oit).second->GetId() == objId))
                {
                        pvs.AddSample((*oit).second, 1.0f);
                }
#else
        #if 0
                dummyInst.SetId(objId);

                ObjectContainer::iterator oit = 
                                                        lower_bound(mPvsObjects.begin(), 
                                                                                mPvsObjects.end(), 
                                                                                (Intersectable *)&dummyInst, 
                                                                                ilt);   

                if ((oit != mPvsObjects.end()) && ((*oit)->GetId() == objId))
                {
                        pvs.AddSample(*oit, 1.0f);
                }
        #else
                pvs.AddSample(mPvsObjects[objId], 1.0f);
        #endif
#endif
        }
        
        mPvsTimer.Exit();
}


void ViewCellsParseHandlers::StartViewSpaceHierarchy(AttributeList& attributes)
{
        int len = attributes.getLength();

        Vector3 bmin, bmax;

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));
                const char *ptr = attrValue.LocalForm();

                // hierarchy type
                if (attrName == "type")
                {
                        if (strcmp(ptr, "bsp") == 0)
                        {
                                Debug << "\nview space hierarchy: Bsp" << endl;
                                mViewSpaceHierarchyType = BSP;
                        }
                        else if (strcmp(ptr, "vsp") == 0)
                        {
                                Debug << "\nview space hierarchy: Vsp" << endl;
                                mViewSpaceHierarchyType = VSP;
                        }
                }
                else if (attrName == "min") // the view space extent
                {
                        sscanf(ptr, "%f %f %f",
                                   &bmin.x, &bmin.y, &bmin.z);
                }
                else if (attrName == "max") 
                {
                        sscanf(ptr, "%f %f %f",
                                   &bmax.x, &bmax.y, &bmax.z);
                }
        }

        mViewSpaceBox = AxisAlignedBox3(bmin, bmax);

        // create the hierarchy based on this information
        CreateViewSpaceHierarchy();
}


void ViewCellsParseHandlers::StartObjectSpaceHierarchy(AttributeList& attributes)
{
        const int len = attributes.getLength();
        Vector3 bmin, bmax;

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));
                const char *ptr = attrValue.LocalForm();

                // hierarchy type
                if (attrName == "type")
                {
                        if (strcmp(ptr, "osp") == 0)
                        {
                                Debug << "\nobject space hierarchy: Osp" << endl;

                                mHierarchyManager = 
                                        new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);

                                DEL_PTR(mHierarchyManager->mVspTree);
                                mHierarchyManager->mVspTree = mVspTree;

                                mObjectSpaceHierarchyType = OSP;

                                //std::stable_sort(objects.begin(), objects.end(), ilt);
                                mHierarchyManager->mOspTree->mBoundingBox.Initialize();
                                ObjectContainer::const_iterator oit, oit_end = mPvsObjects.end();
                                
                                //-- compute bounding box
                                for (oit = mPvsObjects.begin(); oit != oit_end; ++ oit)
                                {
                                        Intersectable *obj = *oit;
                                        // compute bounding box of view space
                                        mHierarchyManager->mOspTree->mBoundingBox.Include(obj->GetBox());
                                }
                        }
                        else if (strcmp(ptr, "bvh") == 0)
                        {
                                Debug << "\nobject space hierarchy: Bvh" << endl;

                                mObjectSpaceHierarchyType = BVH;
                                mHierarchyManager = 
                                        new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);

                                DEL_PTR(mHierarchyManager->mVspTree);
                                mHierarchyManager->mVspTree = mVspTree;
                        }
                }
        }
}


void ViewCellsParseHandlers::StartBoundingBox(AttributeList& attributes)
{
        int len = attributes.getLength();

        Vector3 bmin, bmax;
        int id;

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));

                const char *ptr = attrValue.LocalForm();

                if (attrName == "id")
                {
                        sscanf(ptr, "%d", &id);
                }
                if (attrName == "min") 
                {
                        sscanf(ptr, "%f %f %f", &bmin.x, &bmin.y, &bmin.z);
                }
                else if (attrName == "max") 
                {
                        sscanf(ptr, "%f %f %f", &bmax.x, &bmax.y, &bmax.z);
                }
        }

        AxisAlignedBox3 box(bmin, bmax);
        mIBoundingBoxes.push_back(IndexedBoundingBox(id, box));
}


void ViewCellsParseHandlers::StartBspLeaf(AttributeList& attributes)
{
        BspLeaf * leaf;

        if (mCurrentBspNode) // replace front or (if not NULL) back child
        {
                BspInterior *interior = static_cast<BspInterior *>(mCurrentBspNode);

                leaf = new BspLeaf(interior);
                interior->ReplaceChildLink(NULL, leaf);
        }
        else
        {
                leaf = new BspLeaf();
                mVspBspTree->mRoot = leaf;
        }

        ///////////
        //-- find associated view cell

        int viewCellId;
        const int len = attributes.getLength();
          
        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));

                const char *ptr = attrValue.LocalForm();
                char *endptr = NULL;

                if (attrName == "viewCellId") 
                {
                        viewCellId = strtol(ptr, &endptr, 10);
                }
        }
        
        if (viewCellId >= 0) // valid view cell found
        {
                // TODO: get view cell with specified id
                ViewCellInterior dummyVc;
                dummyVc.SetId(viewCellId);

                ViewCellContainer::iterator vit =
                        lower_bound(mViewCells.begin(), mViewCells.end(), &dummyVc, vlt);
                
                //ViewCellsMap::iterator vit = mViewCells.find(viewCellId);
//              BspViewCell *viewCell = static_cast<BspViewCell *>((*vit).second);

                BspViewCell *viewCell = static_cast<BspViewCell *>(*vit);
                if (viewCell->GetId() == viewCellId)
                {
                        // create new view cell for bsp nodes
                        leaf->SetViewCell(viewCell);
                        viewCell->mLeaves.push_back(leaf);
                }
                else
                {
                        cerr << "error: view cell does not exist" << endl;
                }
        }
        else
        {
                // add to invalid view space
                leaf->SetViewCell(mVspBspTree->GetOrCreateOutOfBoundsCell());
                leaf->SetTreeValid(false);
                mVspBspTree->PropagateUpValidity(leaf);
        }
}


void ViewCellsParseHandlers::StartBspInterior(AttributeList& attributes)
{
        Plane3 plane;
        int len = attributes.getLength();

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));
                const char *ptr = attrValue.LocalForm();

                if (attrName == "plane") 
                {
                        sscanf(ptr, "%f %f %f %f",
                                   &plane.mNormal.x, &plane.mNormal.y, &plane.mNormal.z, &plane.mD);
                }
        }

        BspInterior* interior = new BspInterior(plane);
        
        if (mCurrentBspNode) // replace NULL child of parent with current node
        {
                BspInterior *parent = static_cast<BspInterior *>(mCurrentBspNode);

                parent->ReplaceChildLink(NULL, interior);
                interior->SetParent(parent);
        }
        else
        {
                mVspBspTree->mRoot = interior;
        }

        mCurrentBspNode = interior;
}


void ViewCellsParseHandlers::StartViewCell(AttributeList& attributes, const bool isLeaf)
{
        ViewCell *viewCell = NULL;
        const int len = attributes.getLength();
        float mergeCost;
        
        if (isLeaf)
        {
                viewCell = new ViewCellLeaf();
        }
        else
        {
                viewCell = new ViewCellInterior();
        }

        for (int i = 0; i < len; ++ i) 
        {
                const string attrName(StrX(attributes.getName(i)).LocalForm());
        
                if (attrName == "id") 
                {
                        const StrX attrValue(attributes.getValue(i));
                        const char *ptr = attrValue.LocalForm();
                        char *endptr = NULL;
                        const int id = strtol(ptr, &endptr, 10);

                        // create new view cell, otherwise use reference.
                        viewCell->SetId(id);

                        if (mCurrentViewCell) 
                        {       // replace front or (if not NULL) back child
                                ViewCellInterior *interior = 
                                        static_cast<ViewCellInterior *>(mCurrentViewCell);
                                interior->SetupChildLink(viewCell);
                        }
                        else 
                        {       // set the new root
                                mViewCellsTree->SetRoot(viewCell);
                        }
                        
                        if (!isLeaf)
                        {
                                mCurrentViewCell = viewCell;
                        }
                }
                if (attrName == "pvs") 
                {
                        StrX attrValue(attributes.getValue(i));
                        const char *ptr = attrValue.LocalForm();

                        // hack: assume that view cell id comes before pvs
                        // otherwise view cell is undefined

                        StartViewCellPvs(viewCell->GetPvs(), ptr); 
                        //StartViewCellPvs(pvs, ptr);
                }
                else if (attrName == "active")
                {
                        StrX attrValue(attributes.getValue(i));
                        const char *ptr = attrValue.LocalForm();
                        char *endptr = NULL;
                        const bool isActive = (bool)strtol(ptr, &endptr, 10);

                        if (isActive)
                        {
                                // TODO
                        }
                }
                else if (attrName == "mergecost")
                {
                        StrX attrValue(attributes.getValue(i));
                        
                        const char *ptr = attrValue.LocalForm();
                        char *endptr = NULL;
                        mergeCost = (float)strtod(ptr, &endptr);
                }
        }

        viewCell->SetMergeCost(mergeCost);
        //viewCell->SetPvs(pvs);
        mViewCells.push_back(viewCell);
}


void ViewCellsParseHandlers::CreateViewSpaceHierarchy()
{
        if (mViewSpaceHierarchyType == BSP)
        {
                Debug << "hierarchy type: Bsp" << endl;
                mVspBspTree = new VspBspTree();

                // set view space box
                mVspBspTree->mBoundingBox = mViewSpaceBox;

                //ViewCellsMap::iterator vit, vit_end = mViewCells.end();
                ViewCellContainer::iterator vit, vit_end = mViewCells.end();

                int i = 0;
                // remove view cells and exchange them with the 
                // view cells specialized for the current hierarchy node type
                for (vit = mViewCells.begin(); vit != vit_end; ++ vit, ++ i)
                {
                        ViewCell *vc = (*vit);

                        if (!vc->IsLeaf()) // exchange only leaves
                                continue;
                
                        BspViewCell *bspVc = new BspViewCell();

                        bspVc->SetId(vc->GetId());
                        //bspVc->GetPvs().reserve(vc->GetPvs().size());
                        bspVc->SetPvs(vc->GetPvs());

                        if (vc->IsRoot())
                        {
                                mViewCellsTree->mRoot = bspVc;
                        }
                        else
                        {
                vc->GetParent()->ReplaceChildLink(vc, bspVc);
                        }

                        // delete old view cell
                        DEL_PTR(vc);

                        //(*vit).second = bspVc;
                        (*vit) = bspVc;
                }
                cout << "finished creating view space hierarchy" << endl;
        }
        else if (mViewSpaceHierarchyType == VSP) 
        {
                Debug << "hierarchy type: Vsp" << endl;
                mVspTree = new VspTree();

                // set view space box
                mVspTree->mBoundingBox = mViewSpaceBox;

                // ViewCellsMap::iterator vit, vit_end = mViewCells.end();
                ViewCellContainer::iterator vit, vit_end = mViewCells.end();

                // reset view cells using the current node type
                for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
                {
                        //ViewCell *vc = (*vit).second;
                        ViewCell *vc = (*vit);
                        
                        if (!vc->IsLeaf()) // exchange only leaves
                                continue;

                        VspViewCell *vspVc = new VspViewCell();

                        vspVc->SetPvs(vc->GetPvs());
                        vspVc->SetId(vc->GetId());

                        if (vc->IsRoot())
                        {
                                mViewCellsTree->mRoot = vspVc;
                        }
                        else
                        {
                                vc->GetParent()->ReplaceChildLink(vc, vspVc);
                        }
                        
                        // exchange view cell with new one
                        DEL_PTR(vc);
                        //(*vit).second = vspVc;
                        (*vit) = vspVc;
                }

                if (mHierarchyManager)
                {
                        // do this only if object hierarchy was already constructed
                        mHierarchyManager->mVspTree = mVspTree;
                        mVspTree->mHierarchyManager = mHierarchyManager;
                }
        }
}


void ViewCellsParseHandlers::CreateViewCellsManager()
{
        if (mViewSpaceHierarchyType == BSP)
        {
                Debug << "\ncreating view cells manager: VspBsp" << endl;
                mViewCellsManager = new VspBspViewCellsManager(mViewCellsTree, mVspBspTree);
        }
        else if (mViewSpaceHierarchyType == VSP) 
        {
                Debug << "\ncreating view cells manager: VspOsp" << endl;
                mViewCellsManager = new VspOspViewCellsManager(mViewCellsTree, mHierarchyManager);
        }

        mViewCellsManager->SetViewSpaceBox(mViewSpaceBox);
}


void ViewCellsParseHandlers::characters(const XMLCh* const chars,
                                                                                const unsigned int length)
{
        mCharacterCount += length;
}


void ViewCellsParseHandlers::ignorableWhitespace(const XMLCh* const chars,
                                                                                                 const unsigned int length)
{
        mSpaceCount += length;
}


void ViewCellsParseHandlers::resetDocument()
{
        mAttrCount = 0;
        mCharacterCount = 0;
        mElementCount = 0;
        mSpaceCount = 0;
}


void ViewCellsParseHandlers::StartVspLeaf(AttributeList& attributes)
{
        VspLeaf * leaf;
                
        if (mCurrentVspNode) // replace front or (if not NULL) back child
        {
                VspInterior *interior = static_cast<VspInterior *>(mCurrentVspNode);
                leaf = new VspLeaf(interior);
                interior->ReplaceChildLink(NULL, leaf);
        }
        else
        {
                leaf = new VspLeaf();
                mVspTree->mRoot = leaf;
        }

        /////////////
        //-- find view cell associated with the id

        int viewCellId;
        const int len = attributes.getLength();
          
        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));

                const char *ptr = attrValue.LocalForm();
                char *endptr = NULL;

                if (attrName == "viewCellId") 
                {
                        viewCellId = strtol(ptr, &endptr, 10);
                }
        }
        
        if (viewCellId >= 0) // valid view cell found
        {
                // TODO: get view cell with specified id
                ViewCellInterior dummyVc;
                dummyVc.SetId(viewCellId);

                ViewCellContainer::iterator vit =
                        lower_bound(mViewCells.begin(), mViewCells.end(), &dummyVc, vlt);
                
                //ViewCellsMap::iterator vit = mViewCells.find(viewCellId);
                if (vit == mViewCells.end())
                        Debug << "error: view cell " << viewCellId << " not found" << endl;
        
                //VspViewCell *viewCell = static_cast<VspViewCell *>((*vit).second);
                VspViewCell *viewCell = static_cast<VspViewCell *>(*vit);
                
                if (viewCell->GetId() == viewCellId)
                {
                        leaf->SetViewCell(viewCell);
                        viewCell->mLeaves.push_back(leaf);
                }
                else
                {
                        Debug << "error: view cell does not exist" << endl;
                }
        }
        else
        {       
                // add to invalid view space
                leaf->SetViewCell(mVspTree->GetOrCreateOutOfBoundsCell());
                leaf->SetTreeValid(false);
                mVspTree->PropagateUpValidity(leaf);
        }
}


void ViewCellsParseHandlers::StartVspInterior(AttributeList& attributes)
{
        AxisAlignedPlane plane;
        const int len = attributes.getLength();

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));
                const char *ptr = attrValue.LocalForm();

                if (attrName == "plane") 
                {
                        sscanf(ptr, "%f %d", &plane.mPosition, &plane.mAxis);
                }
        }

        VspInterior* interior = new VspInterior(plane);
        
        if (mCurrentVspNode) // replace NULL child of parent with current node
        {
                VspInterior *parent = static_cast<VspInterior *>(mCurrentVspNode);

                parent->ReplaceChildLink(NULL, interior);
                interior->SetParent(parent);
                
                AxisAlignedBox3 frontBox, backBox;

                parent->GetBoundingBox().Split(
                        parent->GetPlane().mAxis, 
                        parent->GetPlane().mPosition, 
                        frontBox, 
                        backBox);

                if (parent->GetFront() == interior)
                        interior->SetBoundingBox(frontBox);
                else
                        interior->SetBoundingBox(backBox);
        }
        else
        {
                mVspTree->mRoot = interior;
                interior->SetBoundingBox(mVspTree->GetBoundingBox());
        }

        mCurrentVspNode = interior;
}


void ViewCellsParseHandlers::StartOspInterior(AttributeList& attributes)
{
        AxisAlignedPlane plane;
        int len = attributes.getLength();

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));
                const char *ptr = attrValue.LocalForm();

                if (attrName == "plane") 
                {
                        sscanf(ptr, "%f %d", &plane.mPosition, &plane.mAxis);
                }
        }

        KdInterior* interior = new KdInterior(NULL);
        
        interior->mAxis = plane.mAxis;
        interior->mPosition = plane.mPosition;

        if (mCurrentOspNode) // replace NULL child of parent with current node
        {
                KdInterior *parent = static_cast<KdInterior *>(mCurrentOspNode);
                parent->ReplaceChildLink(NULL, interior);
                interior->mParent = parent;

                AxisAlignedBox3 frontBox, backBox;

                parent->mBox.Split(parent->mAxis, parent->mPosition, frontBox, backBox);

                if (parent->mFront == interior)
                        interior->mBox = frontBox;
                else
                        interior->mBox = backBox;
        }
        else
        {
                mHierarchyManager->mOspTree->mRoot = interior;
                interior->mBox = mHierarchyManager->mOspTree->mBoundingBox;
        }

        mCurrentOspNode = interior;
}


void ViewCellsParseHandlers::StartOspLeaf(AttributeList& attributes)
{
        KdLeaf * leaf = new KdLeaf(static_cast<KdInterior *>(mCurrentOspNode), NULL);

        if (mCurrentOspNode)
        {
                 // replace front or (if not NULL) back child
                static_cast<KdInterior *>(mCurrentOspNode)->ReplaceChildLink(NULL, leaf);
        }
        else
        {
                mHierarchyManager->mOspTree->mRoot = leaf;
        }
}


void ViewCellsParseHandlers::StartBvhLeaf(AttributeList& attributes)
{
        const int len = attributes.getLength();
        Vector3 minBox, maxBox;

        ObjectContainer objects;

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));
                const char *ptr = attrValue.LocalForm();

                if (attrName == "min") 
                {
                        sscanf(ptr, "%f %f %f", &minBox.x, &minBox.y, &minBox.z);
                }
                if (attrName == "max") 
                {
                        sscanf(ptr, "%f %f %f", &maxBox.x, &maxBox.y, &maxBox.z);
                }
                if (attrName == "objects")
                {
                        if (!mPreprocessorObjects.empty())
                                StartBvhLeafObjects(objects, ptr);
                }
        }

        AxisAlignedBox3 box = AxisAlignedBox3(minBox, maxBox);

        BvhLeaf *leaf;

        if (mCurrentBvhNode) // replace front or (if not NULL) back child
        {
                BvhInterior *interior = static_cast<BvhInterior *>(mCurrentBvhNode);

                leaf = new BvhLeaf(box, interior, (int)objects.size());
                interior->ReplaceChildLink(NULL, leaf);
        }
        else
        {
                leaf = new BvhLeaf(box, NULL, (int)objects.size());
                mHierarchyManager->mBvHierarchy->mRoot = leaf;
        }

        leaf->mObjects = objects;
        BvHierarchy::AssociateObjectsWithLeaf(leaf);
}


void ViewCellsParseHandlers::StartBvhLeafObjects(ObjectContainer &objects, 
                                                                                                 const char *ptr)
{
        vector<int> objIndices;
        char *endptr;
                        
        while (1)
        {
                const int index = strtol(ptr, &endptr, 10);
                if (ptr == endptr) break;

                objIndices.push_back(index);
                ptr = endptr;
        }

        MeshInstance dummyInst(NULL);
        vector<int>::const_iterator it, it_end = objIndices.end();

        for (it = objIndices.begin(); it != it_end; ++ it)
        {
                const int objId = *it;  
                dummyInst.SetId(objId);

                ObjectContainer::const_iterator oit =
                        lower_bound(mPreprocessorObjects.begin(), 
                                                mPreprocessorObjects.end(), 
                                                (Intersectable *)&dummyInst, 
                                                ilt);   
                                                        
                if ((oit != mPreprocessorObjects.end()) && ((*oit)->GetId() == objId))
                {
                        objects.push_back(*oit);
                }
                else
                {
                        //cerr << "StartBvhLeafObjects error: object with id " << objId << " does not exist" << endl;
                }
        }
}


void ViewCellsParseHandlers::StartBvhInterior(AttributeList& attributes)
{
        const int len = attributes.getLength();
        Vector3 minBox, maxBox;

        for (int i = 0; i < len; ++ i) 
        {
                string attrName(StrX(attributes.getName(i)).LocalForm());
                StrX attrValue(attributes.getValue(i));
                const char *ptr = attrValue.LocalForm();

                if (attrName == "min") 
                {
                        sscanf(ptr, "%f %f %f", &minBox.x, &minBox.y, &minBox.z);
                }
                if (attrName == "max") 
                {
                        sscanf(ptr, "%f %f %f", &maxBox.x, &maxBox.y, &maxBox.z);
                }
        }

        BvhInterior* interior = new BvhInterior(AxisAlignedBox3(minBox, maxBox));

        if (mCurrentBvhNode) // replace NULL child of parent with current node
        {
                BvhInterior *parent = static_cast<BvhInterior *>(mCurrentBvhNode);
                parent->ReplaceChildLink(NULL, interior);
                interior->SetParent(parent);
        }
        else
        {
                mHierarchyManager->mBvHierarchy->mRoot = interior;
        }

        mCurrentBvhNode = interior;
}


// ---------------------------------------------------------------------------
//  StdInParseHandlers: Overrides of the SAX ErrorHandler interface
// ---------------------------------------------------------------------------


void
ViewCellsParseHandlers::error(const SAXParseException& e)
{
  XERCES_STD_QUALIFIER cerr << "\nError at (file " << StrX(e.getSystemId())
                            << ", line " << e.getLineNumber()
                            << ", char " << e.getColumnNumber()
                            << "): " << StrX(e.getMessage()) << XERCES_STD_QUALIFIER endl;
}

void
ViewCellsParseHandlers::fatalError(const SAXParseException& e)
{
  XERCES_STD_QUALIFIER cerr << "\nFatal Error at (file " << StrX(e.getSystemId())
                            << ", line " << e.getLineNumber()
                            << ", char " << e.getColumnNumber()
                            << "): " << StrX(e.getMessage()) << XERCES_STD_QUALIFIER endl;
}

void
ViewCellsParseHandlers::warning(const SAXParseException& e)
{
  XERCES_STD_QUALIFIER cerr << "\nWarning at (file " << StrX(e.getSystemId())
                            << ", line " << e.getLineNumber()
                            << ", char " << e.getColumnNumber()
                            << "): " << StrX(e.getMessage()) << XERCES_STD_QUALIFIER endl;
}


bool ViewCellsParser::ParseViewCellsFile(const string &filename, 
                                                                                 ViewCellsManager **viewCells,
                                                                                 ObjectContainer &pvsObjects,
                                                                                 ObjectContainer &preprocessorObjects,
                                                                                 BoundingBoxConverter *bconverter)
{
        // Initialize the XML4C system
        try {
                XMLPlatformUtils::Initialize();
        }

        catch (const XMLException& toCatch)
        {
                XERCES_STD_QUALIFIER cerr << "Error during initialization! Message:\n"
                        << StrX(toCatch.getMessage()) << XERCES_STD_QUALIFIER endl;
                return false;
        }

        //  cout<<"parsing started"<<endl<<flush;

        //
        //  Create a SAX parser object. Then, according to what we were told on
        //  the command line, set the options.
        //
        SAXParser* parser = new SAXParser;
        parser->setValidationScheme(valScheme);
        parser->setDoNamespaces(doNamespaces);
        parser->setDoSchema(doSchema);
        parser->setValidationSchemaFullChecking(schemaFullChecking);


        //
        //  Create our SAX handler object and install it on the parser, as the
        //  document and error handler. We are responsible for cleaning them
        //  up, but since its just stack based here, there's nothing special
        //  to do.
        //
        ViewCellsParseHandlers handler(pvsObjects, preprocessorObjects, bconverter);
        parser->setDocumentHandler(&handler);
        parser->setErrorHandler(&handler);

        unsigned long duration;
        int errorCount = 0;
        // create a faux scope so that 'src' destructor is called before
        // XMLPlatformUtils::Terminate
        {
                //
                //  Kick off the parse and catch any exceptions. Create a standard
                //  input input source and tell the parser to parse from that.
                //
                //    StdInInputSource src;
                try
                {
                        const unsigned long startMillis = XMLPlatformUtils::getCurrentMillis();

#if USE_GZLIB
                        XMLCh *myFilePath = XMLString::transcode(filename.c_str());

                        GzFileInputSource isource(myFilePath);
                        parser->parse(isource);
#else
                        parser->parse(filename.c_str());

#endif

                        //if (mCreatePvsObjects)
                        //      handler.ReplacePvs();

                        const unsigned long endMillis = XMLPlatformUtils::getCurrentMillis();
                        duration = endMillis - startMillis;
                        errorCount = parser->getErrorCount();
                }
                catch (const OutOfMemoryException&)
                {
                        XERCES_STD_QUALIFIER cerr << "OutOfMemoryException" << XERCES_STD_QUALIFIER endl;
                        errorCount = 2;
                        return false;
                }
                catch (const XMLException& e)
                {
                        XERCES_STD_QUALIFIER cerr << "\nError during parsing: \n"
                                << StrX(e.getMessage())
                                << "\n" << XERCES_STD_QUALIFIER endl;
                        errorCount = 1;
                        return false;
                }


                // Print out the stats that we collected and time taken
                if (!errorCount) 
                {
                        XERCES_STD_QUALIFIER cerr << filename << ": " << duration << " ms ("
                                << handler.GetElementCount() << " elems, "
                                << handler.GetAttrCount() << " attrs, "
                                << handler.GetSpaceCount() << " spaces, "
                                << handler.GetCharacterCount() << " chars)" << XERCES_STD_QUALIFIER endl;
                }
        }

        //
        //  Delete the parser itself.  Must be done prior to calling Terminate, below.
        //
        delete parser;

        XMLPlatformUtils::Terminate();

        //-- assign new view cells manager
        *viewCells = handler.mViewCellsManager;

        if (errorCount > 0)
                return false;
        else
                return true;
}

}