source: GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.cpp @ 2742

#include "SceneGraph.h"
#include "Exporter.h"
#include "UnigraphicsParser.h"
#include "X3dParser.h"
#include "Preprocessor.h"
#include "ViewCell.h"
#include "Environment.h"
#include "ViewCellsManager.h"
#include "ViewCellBsp.h"
#include "VspBspTree.h"
#include "RenderSimulator.h"
#include "GlRenderer.h"
#include "PlyParser.h"
#include "SamplingStrategy.h"
#include "VspTree.h"
#include "OspTree.h"
#include "ObjParser.h"
#include "BvHierarchy.h"
#include "HierarchyManager.h"
#include "VssRay.h"
#include "IntelRayCaster.h"
#include "HavranRayCaster.h"
#include "InternalRayCaster.h"
#include "GlobalLinesRenderer.h"
#include "ObjectsParser.h"
#include "SepPlanesBox3.h"


#define DEBUG_RAYCAST 0
#define SHOW_RAYCAST_TIMING 1

using namespace std;

namespace GtpVisibilityPreprocessor {


static int sCurrentDynamicId = 0;


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


Preprocessor *preprocessor = NULL;
  

Preprocessor::Preprocessor():
mKdTree(NULL),
mBspTree(NULL),
mVspBspTree(NULL),
mViewCellsManager(NULL),
mRenderSimulator(NULL),
mPass(0),
mSceneGraph(NULL),
mRayCaster(NULL),
mStopComputation(false),
mThread(NULL),
mGlobalLinesRenderer(NULL),
mUseHwGlobalLines(false),
mTotalRaysCast(0),
mSynchronize(false)
{
        Environment::GetSingleton()->GetBoolValue("Preprocessor.useGlRenderer", mUseGlRenderer);
  
        // renderer will be constructed when the scene graph and viewcell manager will be known
        renderer = NULL;
        
        Environment::GetSingleton()->GetBoolValue("Preprocessor.useGlDebugger", mUseGlDebugger);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.loadMeshes", mLoadMeshes);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.quitOnFinish", mQuitOnFinish);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.computeVisibility", mComputeVisibility);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.detectEmptyViewSpace", mDetectEmptyViewSpace);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.exportVisibility", mExportVisibility );
        
        char buffer[256];
        Environment::GetSingleton()->GetStringValue("Preprocessor.visibilityFile",  buffer);
        mVisibilityFileName = buffer;
        
        Environment::GetSingleton()->GetStringValue("Preprocessor.stats",  buffer);
        mStats.open(buffer);
                
        Environment::GetSingleton()->GetBoolValue("Preprocessor.applyVisibilityFilter", mApplyVisibilityFilter);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.applyVisibilitySpatialFilter",
                                                                                          mApplyVisibilitySpatialFilter );
        Environment::GetSingleton()->GetFloatValue("Preprocessor.visibilityFilterWidth", mVisibilityFilterWidth);

        Environment::GetSingleton()->GetBoolValue("Preprocessor.exportObj", mExportObj);
        
        Environment::GetSingleton()->GetBoolValue("Preprocessor.useViewSpaceBox", mUseViewSpaceBox);

        Environment::GetSingleton()->GetBoolValue("Preprocessor.Export.rays", mExportRays);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.Export.animation", mExportAnimation);
        Environment::GetSingleton()->GetIntValue("Preprocessor.Export.numRays", mExportNumRays);

        Environment::GetSingleton()->GetIntValue("Preprocessor.samplesPerPass", mSamplesPerPass);
        Environment::GetSingleton()->GetIntValue("Preprocessor.totalSamples", mTotalSamples);
        Environment::GetSingleton()->GetIntValue("Preprocessor.totalTime", mTotalTime);
        Environment::GetSingleton()->GetIntValue("Preprocessor.samplesPerEvaluation",
                                                                                         mSamplesPerEvaluation);

        Debug << "******* Preprocessor Options **********" << endl;
        Debug << "detect empty view space=" << mDetectEmptyViewSpace << endl;
        Debug << "load meshes: " << mLoadMeshes << endl;
        Debug << "load meshes: " << mLoadMeshes << endl;
        Debug << "export obj: " << mExportObj << endl;
        Debug << "use view space box: " << mUseViewSpaceBox << endl;

        cout << "samples per pass " << mSamplesPerPass << endl;
}


Preprocessor::~Preprocessor()
{
        cout << "cleaning up" << endl;

        cout << "Deleting view cells manager ... \n";
        DEL_PTR(mViewCellsManager);
        cout << "done.\n";
        
        cout << "Deleting bsp tree ... \n";
        DEL_PTR(mBspTree);
        cout << "done.\n";

        cout << "Deleting kd tree ...\n";
        DEL_PTR(mKdTree);
        cout << "done.\n";

        cout << "Deleting vspbsp tree ... \n";
        DEL_PTR(mVspBspTree);
        cout << "done.\n";

        cout << "Deleting scene graph ... \n";
        DEL_PTR(mSceneGraph);
        cout << "done.\n";

        cout << "deleting render simulator ... \n";
        DEL_PTR(mRenderSimulator);
        mRenderSimulator = NULL;

        cout << "deleting renderer ... \n";
        DEL_PTR(renderer);
        renderer = NULL;

        cout << "deleting ray caster ... \n";
        DEL_PTR(mRayCaster);

#ifdef USE_CG
        cout << "deleting global lines renderer ... \n";
        DEL_PTR(mGlobalLinesRenderer);
#endif
        cout << "finished" << endl;
}


GlRendererBuffer *Preprocessor::GetRenderer() 
{ 
        return renderer;
}




void Preprocessor::SetThread(PreprocessorThread *t)
{
        mThread = t;
}


PreprocessorThread *Preprocessor::GetThread() const 
{
        return mThread;
}


bool Preprocessor::LoadBinaryObj(const string &filename,
                                                                 SceneGraphLeaf *root,
                                                                 vector<FaceParentInfo> *parents,
                                                                 float scale)
{
        //ifstream inStream(filename, ios::binary);
        igzstream inStream(filename.c_str());
        
        if (!inStream.is_open())
                return false;

        cout << "binary obj dump available, loading " << filename.c_str() << endl;
        
        // read in triangle size
        int numTriangles;

        const int t = 500000;
        inStream.read(reinterpret_cast<char *>(&numTriangles), sizeof(int));
        root->mGeometry.reserve(numTriangles);
        cout << "loading " << numTriangles << " triangles (" << numTriangles * 
                (sizeof(TriangleIntersectable) + sizeof(TriangleIntersectable *)) /
                (1024 * 1024) << " MB)" << endl;

        int i = 0;

        while (1)
        {
                Triangle3 tri;
                
                inStream.read(reinterpret_cast<char *>(tri.mVertices + 0), sizeof(Vector3));
                inStream.read(reinterpret_cast<char *>(tri.mVertices + 1), sizeof(Vector3));
                inStream.read(reinterpret_cast<char *>(tri.mVertices + 2), sizeof(Vector3));

                if (scale > 0.0f)
                {
                        tri.mVertices[0] *= scale;
                        tri.mVertices[1] *= scale;
                        tri.mVertices[2] *= scale;
                }

                // end of file reached
                if (inStream.eof())
                        break;

                TriangleIntersectable *obj = new TriangleIntersectable(tri);
                root->mGeometry.push_back(obj);
                
                if ((i ++) % t == t)
                         cout<<"\r"<<i<<"/"<<numTriangles<<"\r";
        }
        
        if (i != numTriangles)
        {
                cout << "warning: triangle size does not match with loaded triangle size" << endl;
                return false;
        }

        cout << "loaded " << numTriangles << " triangles" << endl;

        return true;
}


bool Preprocessor::ExportBinaryObj(const string &filename, SceneGraphLeaf *root)
{
        ogzstream samplesOut(filename.c_str());

        if (!samplesOut.is_open())
                return false;

        int numTriangles = (int)root->mGeometry.size();

        samplesOut.write(reinterpret_cast<char *>(&numTriangles), sizeof(int));

        ObjectContainer::const_iterator oit, oit_end = root->mGeometry.end();

        for (oit = root->mGeometry.begin(); oit != oit_end; ++ oit)
        {
                Intersectable *obj = *oit;

                if (obj->Type() == Intersectable::TRIANGLE_INTERSECTABLE)
                {
                        Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();

                        samplesOut.write(reinterpret_cast<char *>(tri.mVertices + 0), sizeof(Vector3));
                        samplesOut.write(reinterpret_cast<char *>(tri.mVertices + 1), sizeof(Vector3));
                        samplesOut.write(reinterpret_cast<char *>(tri.mVertices + 2), sizeof(Vector3));
                }
                else
                {
                        cout << "not implemented intersectable type " << obj->Type() << endl;
                }
        }

        cout << "exported " << numTriangles << " triangles" << endl;

        return true;
}


bool Preprocessor::ExportObj(const string &filename, const ObjectContainer &objects)
{
        ofstream samplesOut(filename.c_str());

        if (!samplesOut.is_open())
                return false;

        ObjectContainer::const_iterator oit, oit_end = objects.end();

        //AxisAlignedBox3 bbox = mSceneGraph->GetBox(); bbox.Enlarge(30.0);
        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                Intersectable *obj = *oit;

                if (obj->Type() == Intersectable::TRIANGLE_INTERSECTABLE)
                {
                        Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();
                        //if (!(bbox.IsInside(tri.mVertices[0]) && bbox.IsInside(tri.mVertices[1]) && bbox.IsInside(tri.mVertices[2])))continue;
                        
                        samplesOut << "v " << tri.mVertices[0].x << " " << tri.mVertices[0].y << " " << tri.mVertices[0].z << endl;
                        samplesOut << "v " << tri.mVertices[1].x << " " << tri.mVertices[1].y << " " << tri.mVertices[1].z << endl;
                        samplesOut << "v " << tri.mVertices[2].x << " " << tri.mVertices[2].y << " " << tri.mVertices[2].z << endl;
                        //}
                }
                else
                {
                        cout << "not implemented intersectable type " << obj->Type() << endl;
                }
        }

        // write faces
        int i = 1;
        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                Intersectable *obj = *oit;
                if (obj->Type() == Intersectable::TRIANGLE_INTERSECTABLE)
                {
                        //Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();
                        //if (!(bbox.IsInside(tri.mVertices[0]) && bbox.IsInside(tri.mVertices[1]) && bbox.IsInside(tri.mVertices[2]))) continue;
                        
                        Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();
                        samplesOut << "f " << i << " " << i + 1 << " " << i + 2 << endl;
                        i += 3;
                }
                else
                {
                        cout << "not implemented intersectable type " << obj->Type() << endl;
                }
        }

        return true;

}



Intersectable *Preprocessor::GetParentObject(int index) const
{
        if (index < 0)
        {
                //cerr << "Warning: triangle index smaller zero! " << index << endl;
                return NULL;
        }
        
        if (!mFaceParents.empty())
        {
                if (index >= (int)mFaceParents.size())
                {
                        cerr << "Warning: triangle index out of range! " << index << endl;
                        return NULL;
                }
                else
                {
                        return mFaceParents[index].mObject;
                }
        }
        else
        {
                return mObjects[index];
        }
}


Vector3 Preprocessor::GetParentNormal(const int index) const
{
        if (!mFaceParents.empty())
        {
                return mFaceParents[index].mObject->GetNormal(mFaceParents[index].mFaceIndex);
        }       
        else
        {
                return mObjects[index]->GetNormal(0);
        }
}


bool
Preprocessor::LoadScene(const string &filename)
{
    // use leaf nodes of the original spatial hierarchy as occludees
        mSceneGraph = new SceneGraph;
  
        Parser *parser;
        vector<string> filenames;
        const int files = SplitFilenames(filename, filenames);
        cout << "number of input files: " << files << endl;

        bool result = false;
        bool isObj = false;

        // root for different files
        mSceneGraph->SetRoot(new SceneGraphInterior());

        // intel ray caster can only trace triangles
        int rayCastMethod;
        Environment::GetSingleton()->GetIntValue("Preprocessor.rayCastMethod",
                                                 rayCastMethod);

        vector<FaceParentInfo> *fi = 
          ((rayCastMethod == RayCaster::INTEL_RAYCASTER ||
                rayCastMethod == RayCaster::HAVRAN_RAYCASTER
                ) && mLoadMeshes) ?
          &mFaceParents : NULL;
        
        if (files == 1) 
        {
                SceneGraphLeaf *leaf = new SceneGraphLeaf();

                if (strstr(filename.c_str(), ".x3d"))
                {
                        parser = new X3dParser;
                        
                        result = parser->ParseFile(filename, 
                                                                           leaf,
                                                                           mLoadMeshes,
                                                                           fi);
                        delete parser;
                }
                else if (strstr(filename.c_str(), ".ply") || strstr(filename.c_str(), ".plb"))
                {
                        parser = new PlyParser;

                        result = parser->ParseFile(filename, 
                                leaf,
                                mLoadMeshes,
                                fi);
                        delete parser;
                }
                else if (strstr(filename.c_str(), ".obj"))
                {
                        isObj = true;

                        // hack: load binary dump
                        const string bnFile = ReplaceSuffix(filename, ".obj", ".bn");

                        if (!mLoadMeshes)
                        {
                                result = LoadBinaryObj(bnFile, leaf, fi);
                        }

                        // parse obj
                        if (!result)
                        {
                                cout << "no binary dump available or loading full meshes, parsing file" << endl;
                                parser = new ObjParser;

                                result = parser->ParseFile(filename, leaf, mLoadMeshes, fi);

                                cout << "loaded " << (int)leaf->mGeometry.size() << " entities" << endl;

                                // only works for triangles
                                if (result && !mLoadMeshes)
                                {
                                        cout << "exporting binary obj to " << bnFile << "... " << endl;

                                        ExportBinaryObj(bnFile, leaf);

                                        cout << "finished" << endl;
                                }

                                delete parser;
                        }
                }
                else 
                {
                        parser = new UnigraphicsParser;
                        result = parser->ParseFile(filename, leaf, mLoadMeshes, fi);
                        delete parser;
                }

                if (result)
                {
                        mSceneGraph->GetRoot()->mChildren.push_back(leaf);
                }

                cout << filename << endl;
        } 
        else 
        {
                vector<string>::const_iterator fit, fit_end = filenames.end();

                for (fit = filenames.begin(); fit != fit_end; ++ fit) 
                {
                        const string filename = *fit;

                        cout << "parsing file " << filename.c_str() << endl;
                        if (strstr(filename.c_str(), ".x3d"))
                                parser = new X3dParser;
                        else 
                                parser = new UnigraphicsParser;

                        SceneGraphLeaf *node = new SceneGraphLeaf();

                        const bool success = 
                                parser->ParseFile(filename, node, mLoadMeshes, fi);

                        if (success) 
                        { 
                                mSceneGraph->GetRoot()->mChildren.push_back(node);
                                result = true; // at least one file parsed
                        }

                        // temporare hack
                        //if (!strstr(filename.c_str(), "plane")) mSceneGraph->GetRoot()->UpdateBox();

                        delete parser;
                }
        }

        if (result) 
        {  
                int intersectables, faces;
                mSceneGraph->GetStatistics(intersectables, faces);
 
                cout<<filename<<" parsed successfully."<<endl;
                cout<<"#NUM_OBJECTS (Total numner of objects)\n"<<intersectables<<endl;
                cout<<"#NUM_FACES (Total numner of faces)\n"<<faces<<endl;
                
                mObjects.reserve(intersectables);
                mSceneGraph->CollectObjects(mObjects);
        
                mSceneGraph->AssignObjectIds();

                mSceneGraph->GetRoot()->UpdateBox();
                                
                cout << "finished loading" << endl;
        }

        return result;
}

bool
Preprocessor::ExportPreprocessedData(const string &filename)
{
        mViewCellsManager->ExportViewCells(filename, true, mObjects);
        return true;
}


bool
Preprocessor::PostProcessVisibility()
{
  
  if (mApplyVisibilityFilter || mApplyVisibilitySpatialFilter) {
        cout<<"Applying visibility filter ...";
        cout<<"filter width = " << mVisibilityFilterWidth << endl;
        
        if (!mViewCellsManager)
          return false;
        
        
        mViewCellsManager->ApplyFilter(mKdTree,
                                                                   mApplyVisibilityFilter ?
                                                                   mVisibilityFilterWidth : -1.0f,
                                                                   mApplyVisibilitySpatialFilter ?
                                                                   mVisibilityFilterWidth : -1.0f);
        cout << "done." << endl;
  }
  
  // export the preprocessed information to a file
  if (1 && mExportVisibility)
  {
          ExportPreprocessedData(mVisibilityFileName);
  }

  return true;
}


bool
Preprocessor::BuildKdTree()
{
  mKdTree = new KdTree;

  // add mesh instances of the scene graph to the root of the tree
  KdLeaf *root = (KdLeaf *)mKdTree->GetRoot();
        
  mSceneGraph->CollectObjects(root->mObjects);
  
  const long startTime = GetTime();
  cout << "building kd tree ... " << endl;

  mKdTree->Construct();
  sceneBox = mKdTree->GetBox();

  cout << "finished kd tree construction in " << TimeDiff(startTime, GetTime()) * 1e-3 
           << " secs " << endl;

  return true;
}


void
Preprocessor::KdTreeStatistics(ostream &s)
{
  s<<mKdTree->GetStatistics();
}

void
Preprocessor::BspTreeStatistics(ostream &s)
{
        s << mBspTree->GetStatistics();
}

bool
Preprocessor::Export( const string &filename,
                                         const bool scene,
                                         const bool kdtree
                                         )
{
        Exporter *exporter = Exporter::GetExporter(filename);

        if (exporter) {
                if (2 && scene)
                        exporter->ExportScene(mSceneGraph->GetRoot());

                if (1 && kdtree) {
                        exporter->SetWireframe();
                        exporter->ExportKdTree(*mKdTree);
                }

                delete exporter;
                return true;
        }

        return false;
}


bool Preprocessor::PrepareViewCells()
{
#if 0
        // load the view cells assigning the found objects to the pvss
        cerr << "loading binary view cells" << endl;
        ViewCellsManager *dummyViewCellsManager = 
                LoadViewCellsBinary("test.vc", mObjects, false, NULL);

    //cerr << "reexporting the binary view cells" << endl;
        //dummyViewCellsManager->ExportViewCellsBinary("outvc.xml.gz", true, mObjects);
        
        return false;
#endif

        ///////
        //-- parse view cells construction method

        Environment::GetSingleton()->GetBoolValue("ViewCells.loadFromFile", mLoadViewCells);
        char buf[100];

        if (mLoadViewCells)
        {       
                
#ifdef USE_BIT_PVS
                // HACK: for kd pvs, set pvs size to maximal number of kd nodes
                vector<KdLeaf *> leaves;
                preprocessor->mKdTree->CollectLeaves(leaves);

                ObjectPvs::SetPvsSize((int)leaves.size());
#endif

                Environment::GetSingleton()->GetStringValue("ViewCells.filename", buf);
                cout << "loading objects from " << buf << endl;

                // load scene objects which are the entities used as pvs entries
                ObjectContainer pvsObjects;
                if (1) LoadObjects(buf, pvsObjects, mObjects);

                const bool finalizeViewCells = true;
                cout << "loading view cells from " << buf << endl;
                
                mViewCellsManager = ViewCellsManager::LoadViewCells(buf, 
                                                                                                                        pvsObjects,
                                                                                                                        mObjects, 
                                                                                                                        finalizeViewCells, 
                                                                                                                        NULL);

                cout << "view cells loaded." << endl<<flush;

                if (!mViewCellsManager)
                {
                        cerr << "no view cells manager could be loaded" << endl;
                        return false;
                }
        }
        else
        {
                // parse type of view cells manager
                Environment::GetSingleton()->GetStringValue("ViewCells.type", buf);             
                mViewCellsManager = CreateViewCellsManager(buf);

                // default view space is the extent of the scene
                AxisAlignedBox3 viewSpaceBox;

                if (mUseViewSpaceBox)
                {
                        viewSpaceBox = mSceneGraph->GetBox();

                        // use a small box outside of the scene
                        viewSpaceBox.Scale(Vector3(0.15f, 0.3f, 0.5f));
                        //viewSpaceBox.Translate(Vector3(Magnitude(mSceneGraph->GetBox().Size()) * 0.5f, 0, 0));
                        viewSpaceBox.Translate(Vector3(Magnitude(mSceneGraph->GetBox().Size()) * 0.3f, 0, 0));
                        mViewCellsManager->SetViewSpaceBox(viewSpaceBox);
                }
                else
                {
                        viewSpaceBox = mSceneGraph->GetBox();
                        mViewCellsManager->SetViewSpaceBox(viewSpaceBox);
                }

                bool loadVcGeometry;
                Environment::GetSingleton()->GetBoolValue("ViewCells.loadGeometry", loadVcGeometry);

                bool extrudeBaseTriangles;
                Environment::GetSingleton()->GetBoolValue("ViewCells.useBaseTrianglesAsGeometry", extrudeBaseTriangles);

                char vcGeomFilename[100];
                Environment::GetSingleton()->GetStringValue("ViewCells.geometryFilename", vcGeomFilename);

                // create view cells from specified geometry
                if (loadVcGeometry)
                {
                        if (mViewCellsManager->GetType() == ViewCellsManager::BSP)
                        {
                                if (!mViewCellsManager->LoadViewCellsGeometry(vcGeomFilename, extrudeBaseTriangles))
                                        cerr << "loading view cells geometry failed" << endl;
                        }
                        else
                        {
                                cerr << "loading view cells geometry is not implemented for this manager" << endl;
                        }
                }
        }


        ////////
        //-- evaluation of render cost heuristics

        float objRenderCost = 0, vcOverhead = 0, moveSpeed = 0;

        Environment::GetSingleton()->GetFloatValue("Simulation.objRenderCost",objRenderCost);
        Environment::GetSingleton()->GetFloatValue("Simulation.vcOverhead", vcOverhead);
        Environment::GetSingleton()->GetFloatValue("Simulation.moveSpeed", moveSpeed);

        mRenderSimulator = 
                new RenderSimulator(mViewCellsManager, objRenderCost, vcOverhead, moveSpeed);

        mViewCellsManager->SetRenderer(mRenderSimulator);
        mViewCellsManager->SetPreprocessor(this);

        return true;
}

  
bool Preprocessor::ConstructViewCells()
{
        // construct view cells using it's own set of samples
        mViewCellsManager->Construct(this);

        // visualizations and statistics
        Debug << "finished view cells:" << endl;
        mViewCellsManager->PrintStatistics(Debug);

        return true;
}


ViewCellsManager *Preprocessor::CreateViewCellsManager(const char *name)
{
        ViewCellsTree *vcTree = new ViewCellsTree;

        if (strcmp(name, "kdTree") == 0)
        {
                mViewCellsManager = new KdViewCellsManager(vcTree, mKdTree);
        }
        else if (strcmp(name, "bspTree") == 0)
        {
                Debug << "view cell type: Bsp" << endl;

                mBspTree = new BspTree();
                mViewCellsManager = new BspViewCellsManager(vcTree, mBspTree);
        }
        else if (strcmp(name, "vspBspTree") == 0)
        {
                Debug << "view cell type: VspBsp" << endl;

                mVspBspTree = new VspBspTree();
                mViewCellsManager = new VspBspViewCellsManager(vcTree, mVspBspTree);
        }
        else if (strcmp(name, "vspOspTree") == 0)
        {
                Debug << "view cell type: VspOsp" << endl;
                char buf[100];          
                Environment::GetSingleton()->GetStringValue("Hierarchy.type", buf);     

                mViewCellsManager = new VspOspViewCellsManager(vcTree, buf);
        }
        else if (strcmp(name, "sceneDependent") == 0) //TODO
        {
                Debug << "view cell type: Bsp" << endl;
                
                mBspTree = new BspTree();
                mViewCellsManager = new BspViewCellsManager(vcTree, mBspTree);
        }
        else
        {
                cerr << "Wrong view cells type " << name << "!!!" << endl;
                exit(1);
        }

        return mViewCellsManager;
}


// use ascii format to store rays
#define USE_ASCII 0


bool Preprocessor::LoadKdTree(const string &filename)
{
        mKdTree = new KdTree();
        return mKdTree->ImportBinTree(filename.c_str(), mObjects);
}


bool Preprocessor::ExportKdTree(const string &filename)
{
        return mKdTree->ExportBinTree(filename.c_str());
}


bool Preprocessor::LoadSamples(VssRayContainer &samples, 
                                                           ObjectContainer &objects) const
{
        std::stable_sort(objects.begin(), objects.end(), ilt);
        char fileName[100];
        Environment::GetSingleton()->GetStringValue("Preprocessor.samplesFilename", fileName);
        
    Vector3 origin, termination;
        // HACK: needed only for lower_bound algorithm to find the intersected objects
        MeshInstance sObj(NULL);
        MeshInstance tObj(NULL);

#if USE_ASCII
        ifstream inStream(fileName);
        if (!inStream.is_open())
                return false;

        string buf;
        while (!(getline(inStream, buf)).eof())
        {
                sscanf(buf.c_str(), "%f %f %f %f %f %f %d %d", 
                           &origin.x, &origin.y, &origin.z,
                           &termination.x, &termination.y, &termination.z, 
                           &(sObj.mId), &(tObj.mId));
                
                Intersectable *sourceObj = NULL;
                Intersectable *termObj = NULL;
                
                if (sObj.mId >= 0)
                {
                        ObjectContainer::iterator oit =
                                lower_bound(objects.begin(), objects.end(), &sObj, ilt);
                        sourceObj = *oit;
                }
                
                if (tObj.mId >= 0)
                {
                        ObjectContainer::iterator oit =
                                lower_bound(objects.begin(), objects.end(), &tObj, ilt);
                        termObj = *oit;
                }

                samples.push_back(new VssRay(origin, termination, sourceObj, termObj));
        }
#else
        ifstream inStream(fileName, ios::binary);
        if (!inStream.is_open())
                return false;

        while (1)
        {
                 inStream.read(reinterpret_cast<char *>(&origin), sizeof(Vector3));
                 inStream.read(reinterpret_cast<char *>(&termination), sizeof(Vector3));
                 inStream.read(reinterpret_cast<char *>(&(sObj.mId)), sizeof(int));
                 inStream.read(reinterpret_cast<char *>(&(tObj.mId)), sizeof(int));
                
                 if (inStream.eof())
                        break;

                Intersectable *sourceObj = NULL;
                Intersectable *termObj = NULL;
                
                if (sObj.mId >= 0)
                {
                        ObjectContainer::iterator oit =
                                lower_bound(objects.begin(), objects.end(), &sObj, ilt);
                        sourceObj = *oit;
                }
                
                if (tObj.mId >= 0)
                {
                        ObjectContainer::iterator oit =
                                lower_bound(objects.begin(), objects.end(), &tObj, ilt);
                        termObj = *oit;
                }

                samples.push_back(new VssRay(origin, termination, sourceObj, termObj));
        }
#endif

        inStream.close();

        return true;
}


bool Preprocessor::ExportSamples(const VssRayContainer &samples) const
{
        char fileName[100];
        Environment::GetSingleton()->GetStringValue("Preprocessor.samplesFilename", fileName);
        

        VssRayContainer::const_iterator it, it_end = samples.end();
        
#if USE_ASCII
        ofstream samplesOut(fileName);
        if (!samplesOut.is_open())
                return false;

        for (it = samples.begin(); it != it_end; ++ it)
        {
                VssRay *ray = *it;
                int sourceid = ray->mOriginObject ? ray->mOriginObject->mId : -1;               
                int termid = ray->mTerminationObject ? ray->mTerminationObject->mId : -1;       

                samplesOut << ray->GetOrigin().x << " " << ray->GetOrigin().y << " " << ray->GetOrigin().z << " " 
                                   << ray->GetTermination().x << " " << ray->GetTermination().y << " " << ray->GetTermination().z << " " 
                                   << sourceid << " " << termid << "\n";
        }
#else
        ofstream samplesOut(fileName, ios::binary);
        if (!samplesOut.is_open())
                return false;

        for (it = samples.begin(); it != it_end; ++ it)
        {       
                VssRay *ray = *it;
                Vector3 origin(ray->GetOrigin());
                Vector3 termination(ray->GetTermination());
                
                int sourceid = ray->mOriginObject ? ray->mOriginObject->mId : -1;               
                int termid = ray->mTerminationObject ? ray->mTerminationObject->mId : -1;               

                samplesOut.write(reinterpret_cast<char *>(&origin), sizeof(Vector3));
                samplesOut.write(reinterpret_cast<char *>(&termination), sizeof(Vector3));
                samplesOut.write(reinterpret_cast<char *>(&sourceid), sizeof(int));
                samplesOut.write(reinterpret_cast<char *>(&termid), sizeof(int));
    }
#endif
        samplesOut.close();

        return true;
}


int
Preprocessor::GenerateRays(const int number,
                                                   SamplingStrategy &strategy,
                                                   SimpleRayContainer &rays)
{
        int invalidSamples;
        return strategy.GenerateSamples(number, rays, invalidSamples);
}


int Preprocessor::GenerateRays(const int number,
                                                           SamplingStrategy &strategy,
                                                           SimpleRayContainer &rays, int &invalidSamples)
{
        return strategy.GenerateSamples(number, rays, invalidSamples);
}


int
Preprocessor::GenerateRays(const int number,
                                                   const int sampleType,
                                                   SimpleRayContainer &rays)
{
        SamplingStrategy *strategy = GenerateSamplingStrategy(sampleType);
        
        if (!strategy)
                return 0;

        int castRays = 0;
        int invalidSamples;
#if 1
        castRays = strategy->GenerateSamples(number, rays, invalidSamples);
#else
        GenerateRayBundle(rays, newRay, 16, 0);
        castRays += 16;
#endif

        delete strategy;
        return castRays;
}


SamplingStrategy *Preprocessor::GenerateSamplingStrategy(const int strategyId)
{
        switch (strategyId)
        {
        case SamplingStrategy::OBJECT_BASED_DISTRIBUTION: 
                return new ObjectBasedDistribution(*this);
        case SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION:
                return new ObjectDirectionBasedDistribution(*this);
        case SamplingStrategy::DIRECTION_BASED_DISTRIBUTION:
                return new DirectionBasedDistribution(*this);
        case SamplingStrategy::DIRECTION_BOX_BASED_DISTRIBUTION: 
                return new DirectionBoxBasedDistribution(*this);
        case SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION:
                return new SpatialBoxBasedDistribution(*this);
        case SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION:
                return new ReverseObjectBasedDistribution(*this);
        //case SamplingStrategy::VIEWCELL_BORDER_BASED_DISTRIBUTION:
        //      return new ViewCellBorderBasedDistribution(*this);
        case SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION:
                return new ReverseViewSpaceBorderBasedDistribution(*this);
        case SamplingStrategy::GLOBAL_LINES_DISTRIBUTION:
                return new GlobalLinesDistribution(*this);
                
                //case OBJECTS_INTERIOR_DISTRIBUTION:
                //      return new ObjectsInteriorDistribution(*this);
        default: // no valid strategy
                Debug << "warning: no valid sampling strategy" << endl;
                return NULL;
        }

        return NULL; // should never come here
}


bool Preprocessor::LoadInternKdTree(const string &internKdTree)
{
  bool mUseKdTree = true;


  int rayCastMethod;
  Environment::GetSingleton()->
        GetIntValue("Preprocessor.rayCastMethod", rayCastMethod);

#ifdef USE_HAVRAN_RAYCASTER

  if ((rayCastMethod == 2) || (rayCastMethod == 3)) 
  {
          HavranRayCaster *hr = 0;

          if (rayCastMethod == 3)
                  hr = reinterpret_cast<HavranDynRayCaster*>(mRayCaster);
          else
                  hr = reinterpret_cast<HavranRayCaster*>(mRayCaster);
          
          hr->Build(this->mObjects);
  }

#endif


  if (!mUseKdTree) {
        // create just a dummy KdTree
        mKdTree = new KdTree;
        return true;
  }
  
  
  
  // always try to load the kd tree
  cout << "loading kd tree file " << internKdTree << " ... " << endl;
  
  if (!LoadKdTree(internKdTree)) {
        cout << "error loading kd tree with filename " 
                 << internKdTree << ", rebuilding it instead ... " << endl;
        // build new kd tree from scene geometry
        BuildKdTree();
        
        // export kd tree?
        const long startTime = GetTime();
        cout << "exporting kd tree ... ";
        
        if (!ExportKdTree(internKdTree))
          {
                cout << " error exporting kd tree with filename " 
                         << internKdTree << endl;
          }
        else
          {
                cout << "finished in " 
                         << TimeDiff(startTime, GetTime()) * 1e-3 
                         << " secs" << endl;
          }
  }
  
  KdTreeStatistics(cout);
  sceneBox = mKdTree->GetBox();

  cout << mKdTree->GetBox() << endl;
  
  return true;
}


bool Preprocessor::InitRayCast(const string &externKdTree, 
                                                           const string &internKdTree)
{
        int rayCastMethod;
        Environment::GetSingleton()->
                GetIntValue("Preprocessor.rayCastMethod", rayCastMethod);

        if (rayCastMethod == 0)
        {
                cout << "ray cast method: internal" << endl;
                mRayCaster = new InternalRayCaster(*this);
        }
        if (rayCastMethod == 1) 
        {
#ifdef GTP_INTERNAL
                cout << "ray cast method: intel" << endl;
                mRayCaster = new IntelRayCaster(*this, externKdTree);
#endif
        }
        if (rayCastMethod == 2) 
        {
#ifdef USE_HAVRAN_RAYCASTER
          cout << "ray cast method: havran" << endl <<flush;
          mRayCaster = new GALIGN16 HavranRayCaster(*this);
#endif
        }
        if (rayCastMethod == 3) 
        {
#ifdef USE_HAVRAN_RAYCASTER
          cout << "ray cast method: havran - dyn" << endl <<flush;
          mRayCaster = new GALIGN16 HavranDynRayCaster(*this);
#endif
        }

        
        /////////////////
        //-- reserve constant block of rays
        
        // hack: If we dont't use view cells loading, there must be at least as much rays
        // as are needed for the view cells construction
        bool loadViewCells;
        Environment::GetSingleton()->GetBoolValue("ViewCells.loadFromFile", loadViewCells);

        int reserveRays;        
        int constructionSamples;

        if (!loadViewCells)
        {
                cout << "hack: setting ray pool size to view cell construction or evaluation size" << endl;

                constructionSamples = 1000000;

                char buf[100];
                Environment::GetSingleton()->GetStringValue("ViewCells.type", buf);     

                if (strcmp(buf, "vspBspTree") == 0)
                {
                        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", constructionSamples);
                        
                }
                else if (strcmp(buf, "vspOspTree") == 0)
                {
                        Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", constructionSamples);                
                }

                int evalSamplesPerPass;

                Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", evalSamplesPerPass);

                reserveRays = max(constructionSamples, evalSamplesPerPass);
                reserveRays *= 2;
        }
        else
        {
                const int n = 4;
                reserveRays = mSamplesPerPass * n;

        }

#ifdef USE_RAY_POOL
        cout << "setting ray pool size to " << reserveRays << endl;       

        cout << "======================" << endl;
        cout << "reserving " << reserveRays << " rays " << endl;

        mRayCaster->ReserveVssRayPool(reserveRays);
        
        cout<<"done."<<endl<<flush;
#endif

        return true;
}


void
Preprocessor::CastRays(
                                           SimpleRayContainer &rays,
                                           VssRayContainer &vssRays,
                                           const bool castDoubleRays,
                                           const bool pruneInvalidRays
                                           )
{
        const long t1 = GetTime();

        // !!!!!!!!!!!!!!!! VH no sorting
        if (rays.size() > 10000)
        {
                mRayCaster->SortRays(rays);
                cout<<"Rays sorted in "<<TimeDiff(t1, GetTime())<<" ms."<<endl;
        }

        int numTransformed = 0;


        if (mUseHwGlobalLines) 
        {
                CastRaysWithHwGlobalLines(
                        rays,
                        vssRays,
                        castDoubleRays,
                        pruneInvalidRays
                        );
        }
        else
        {
                mRayCaster->CastRays(
                        rays,                           
                        vssRays,
                        mViewCellsManager->GetViewSpaceBox(),
                        castDoubleRays,
                        pruneInvalidRays);

                // disabled not neccessary
                UpdateDynamicObjects();
        }

        
        if (rays.size() > 10000) 
        {
                cout << endl;
                long t2 = GetTime();

#if SHOW_RAYCAST_TIMING
                if (castDoubleRays)
                        cout << 2 * rays.size() / (1e3f * TimeDiff(t1, t2)) << "M double rays/s" << endl;
                else
                        cout << rays.size() / (1e3f * TimeDiff(t1, t2)) << "M single rays/s" << endl;
#endif

        }

        DeterminePvsObjects(vssRays);
}

  
void
Preprocessor::CastRaysWithHwGlobalLines(
                                                                                SimpleRayContainer &rays,
                                                                                VssRayContainer &vssRays,
                                                                                const bool castDoubleRays,
                                                                                const bool pruneInvalidRays)
{
  SimpleRayContainer::const_iterator rit, rit_end = rays.end();
  SimpleRayContainer rayBucket;
  int i = 0;
  for (rit = rays.begin(); rit != rit_end; ++ rit, ++ i)
        {
          SimpleRay ray = *rit;
#ifdef USE_CG
                // HACK: global lines must be treated special
          if (ray.mDistribution == SamplingStrategy::HW_GLOBAL_LINES_DISTRIBUTION)
                {
                  mGlobalLinesRenderer->CastGlobalLines(ray, vssRays);
                  continue;
                }
#endif
                rayBucket.push_back(ray);

                // 16 rays gathered => do ray casting
                if (rayBucket.size() >= 16)
                {
                        mRayCaster->CastRays16(
                                rayBucket,                              
                                vssRays,
                                mViewCellsManager->GetViewSpaceBox(),
                                castDoubleRays,
                                pruneInvalidRays);

                        rayBucket.clear();
                }

                if (rays.size() > 100000 && i % 100000 == 0)
                        cout<<"\r"<<i<<"/"<<(int)rays.size()<<"\r";
        }
    
        // cast rest of rays
        SimpleRayContainer::const_iterator sit, sit_end = rayBucket.end();

        for (sit = rayBucket.begin(); sit != sit_end; ++ sit)
        {
                SimpleRay ray = *sit;

#ifdef USE_CG
                // HACK: global lines must be treated special
                if (ray.mDistribution == SamplingStrategy::HW_GLOBAL_LINES_DISTRIBUTION)
                {
                        mGlobalLinesRenderer->CastGlobalLines(ray, vssRays);
                        continue;
                }
#endif
                mRayCaster->CastRay(
                                                        ray,
                                                        vssRays,
                                                        mViewCellsManager->GetViewSpaceBox(),
                                                        castDoubleRays,
                                                        pruneInvalidRays);
                
        }

}


bool Preprocessor::GenerateJitteredRays(SimpleRayContainer &rayBundle,  
                                                                                const SimpleRay &mainRay,
                                                                                int number,
                                                                                int pertubType,
                                                                                float scale) const
{
        Vector3 pertub;

        for (int i = 0; i < number; ++ i)
        {
                pertub.x = RandomValue(-scale, scale);
                pertub.y = RandomValue(-scale, scale);
                pertub.z = RandomValue(-scale, scale);

                Vector3 newDir = mainRay.mDirection + pertub;
                const float c = Magnitude(newDir);
                newDir *= 1.0f / c;

                //const Vector3 newDir = mainRay.mDirection;
#if 0
                pertub.x = RandomValue(0.0f, pertubOrigin);
                pertub.y = RandomValue(0.0f, pertubOrigin);
                pertub.z = RandomValue(0.0f, pertubOrigin);

                const Vector3 newOrigin = mainRay.mOrigin + pertub;
#endif
                const Vector3 newOrigin = mainRay.mOrigin;

                rayBundle.push_back(SimpleRay(newOrigin, newDir, 0, 1.0f));
        }

        return true;
}


void Preprocessor::SetupRay(Ray &ray,
                                                        const Vector3 &point,
                                                        const Vector3 &direction) const
{
        ray.Clear();
        // do not store anything else then intersections at the ray
        ray.Init(point, direction, Ray::LOCAL_RAY);     
}


void Preprocessor::EvalViewCellHistogram()
{
        char filename[256];
        Environment::GetSingleton()->GetStringValue("Preprocessor.histogram.file", filename);
  
        // mViewCellsManager->EvalViewCellHistogram(filename, 1000000);
        mViewCellsManager->EvalViewCellHistogramForPvsSize(filename, 1000000);
}


bool
Preprocessor::ExportRays(const char *filename,
                                                 const VssRayContainer &vssRays,
                                                 const int number,
                                                 const bool exportScene
                                                 )
{
  cout<<"Exporting vss rays..."<<endl<<flush;
  
  Exporter *exporter = NULL;
  exporter = Exporter::GetExporter(filename);

  if (0) {
        exporter->SetWireframe();
        exporter->ExportKdTree(*mKdTree);
  }
  
  exporter->SetFilled();
  // $$JB temporarily do not export the scene
  if (exportScene)
        exporter->ExportScene(mSceneGraph->GetRoot());

  exporter->SetWireframe();

  if (1) {
        exporter->SetForcedMaterial(RgbColor(1,0,1));
        exporter->ExportBox(mViewCellsManager->GetViewSpaceBox());
        exporter->ResetForcedMaterial();
  }
  
  VssRayContainer rays;
  vssRays.SelectRays(number, rays);
  exporter->ExportRays(rays, RgbColor(1, 0, 0));
  delete exporter;
  cout<<"done."<<endl<<flush;

  return true;
}

bool
Preprocessor::ExportRayAnimation(const char *filename,
                                                                 const vector<VssRayContainer> &vssRays
                                                                 )
{
  cout<<"Exporting vss rays..."<<endl<<flush;
        
  Exporter *exporter = NULL;
  exporter = Exporter::GetExporter(filename);
  if (0) {
        exporter->SetWireframe();
        exporter->ExportKdTree(*mKdTree);
  }
  exporter->SetFilled();
  // $$JB temporarily do not export the scene
  if (0)
        exporter->ExportScene(mSceneGraph->GetRoot());
  exporter->SetWireframe();

  if (1) {
        exporter->SetForcedMaterial(RgbColor(1,0,1));
        exporter->ExportBox(mViewCellsManager->GetViewSpaceBox());
        exporter->ResetForcedMaterial();
  }
  
  exporter->ExportRaySets(vssRays, RgbColor(1, 0, 0));
        
  delete exporter;

  cout<<"done."<<endl<<flush;

  return true;
}

void
Preprocessor::ComputeRenderError()
{
  // compute rendering error    
  if (renderer && renderer->mPvsStatFrames) {
        
        if (!mViewCellsManager->GetViewCellPointsList()->empty()) 
        {
          
          ViewCellPointsList *vcPoints = mViewCellsManager->GetViewCellPointsList();
          
          ViewCellPointsList::const_iterator
                vit = vcPoints->begin(),
                vit_end = vcPoints->end();

          SimpleRayContainer viewPoints;
          
          for (; vit != vit_end; ++ vit) {
                ViewCellPoints *vp = *vit;

                SimpleRayContainer::const_iterator rit = vp->second.begin(), rit_end = vp->second.end();
                for (; rit!=rit_end; ++rit)
                  viewPoints.push_back(*rit);
          }
          
          if (viewPoints.size() != renderer->mPvsErrorBuffer.size()) {
                renderer->mPvsErrorBuffer.resize(viewPoints.size());
                renderer->ClearErrorBuffer();
          }

          cout << "evaluating list of " << viewPoints.size() << " pts" << endl;
          renderer->EvalPvsStat(viewPoints);
        } else
        {
                cout << "evaluating random points" << endl;
          renderer->EvalPvsStat();
        }

        mStats <<
          "#AvgPvsRenderError\n" <<renderer->mPvsStat.GetAvgError()<<endl<<
          "#AvgPixelError\n" <<renderer->GetAvgPixelError()<<endl<<
          "#MaxPixelError\n" <<renderer->GetMaxPixelError()<<endl<<
          "#MaxPvsRenderError\n" <<renderer->mPvsStat.GetMaxError()<<endl<<
          "#ErrorFreeFrames\n" <<renderer->mPvsStat.GetErrorFreeFrames()<<endl<<
          "#AvgRenderPvs\n" <<renderer->mPvsStat.GetAvgPvs()<<endl;
  }
}


Intersectable *Preprocessor::GetObjectById(const int id)
{
#if 1
        // create a dummy mesh instance to be able to use stl
        MeshInstance object(NULL);
        object.SetId(id);

        ObjectContainer::const_iterator oit =
                lower_bound(mObjects.begin(), mObjects.end(), &object, ilt);
                                
        // objects sorted by id
        if ((oit != mObjects.end()) && ((*oit)->GetId() == object.GetId()))
        {
                return (*oit);
        }
        else
        {
                return NULL;
        }
#else
        return mObjects[id];
#endif
}


void Preprocessor::PrepareHwGlobalLines()
{
        int texHeight, texWidth;
        float eps;
        int maxDepth;
        bool sampleReverse;

        Environment::GetSingleton()->GetIntValue("Preprocessor.HwGlobalLines.texHeight", texHeight);
        Environment::GetSingleton()->GetIntValue("Preprocessor.HwGlobalLines.texWidth", texWidth);
        Environment::GetSingleton()->GetFloatValue("Preprocessor.HwGlobalLines.stepSize", eps);
        Environment::GetSingleton()->GetIntValue("Preprocessor.HwGlobalLines.maxDepth", maxDepth);
        Environment::GetSingleton()->GetBoolValue("Preprocessor.HwGlobalLines.sampleReverse", sampleReverse);

        Debug << "****** hw global line options *******" << endl;
        Debug << "texWidth: " << texWidth << endl;
        Debug << "texHeight: " << texHeight << endl;
        Debug << "sampleReverse: " << sampleReverse << endl;
        Debug << "max depth: " << maxDepth << endl;
        Debug << "step size: " << eps << endl;
        Debug << endl;

#ifdef USE_CG
        globalLinesRenderer = mGlobalLinesRenderer = 
                new GlobalLinesRenderer(this,
                                                                texHeight,
                                                                texWidth,
                                                                eps,
                                                                maxDepth,
                                                                sampleReverse);

        mGlobalLinesRenderer->InitGl();

#endif
}


void Preprocessor::DeterminePvsObjects(VssRayContainer &rays)
{
  mViewCellsManager->DeterminePvsObjects(rays, false);
}


bool Preprocessor::LoadObjects(const string &filename,
                                                           ObjectContainer &pvsObjects, 
                                                           const ObjectContainer &preprocessorObjects)
{
        ObjectsParser parser;

        const bool success = parser.ParseObjects(filename, 
                                                                                         pvsObjects, 
                                                                                         preprocessorObjects);

        if (!success)
        {
                Debug << "Error: loading objects failed!" << endl;
        }

        // hack: no bvh object could be found => take preprocessor objects
        if (pvsObjects.empty())
        {
                Debug << "no objects" << endl;
                pvsObjects = preprocessorObjects;
        }

        return success;
}


void Preprocessor::RegisterDynamicObject(SceneGraphLeaf *leaf)
{       
        mDynamicObjects.push_back(leaf);

        const int currentId = (int)mObjects.size() + sCurrentDynamicId;

        leaf->GetIntersectable()->SetId(currentId);

        for (size_t i = 0; i < leaf->mGeometry.size(); ++ i)
        {
                leaf->mGeometry[i]->SetId(currentId);
        }

        cout << "new object registered with id " << currentId << endl;

        ++ sCurrentDynamicId;

        // tell ray caster to update
        ScheduleUpdateDynamicObjects();
}


SceneGraphLeaf *Preprocessor::GenerateBoxGeometry(const AxisAlignedBox3 &box)
{
        float offs = box.Min().y;
        AxisAlignedBox3 newBox = box;
        newBox.Translate(Vector3(0.0f, -offs, 0.0f));

        const bool dynamic = true;
        SceneGraphLeaf *leaf = new SceneGraphLeaf(dynamic);
        newBox.Triangulate(leaf->mGeometry);

        leaf->UpdateBox();

        return leaf;
}


SceneGraphLeaf *Preprocessor::LoadDynamicGeometry(const string &filename)
{
        const bool dynamic = true;
        SceneGraphLeaf *leaf = new SceneGraphLeaf(dynamic);

        bool parsed = false;

        if (strstr(filename.c_str(), ".obj"))
        {
                cout<<"parsing obj file.."<<endl;
                ObjParser *p = new ObjParser;
                parsed = p->ParseFile(filename, leaf, false);
        } 
        else 
        {
                cout<<"parsing binary obj file ... " << endl;
                parsed = LoadBinaryObj(filename, leaf, NULL, 100);
        }

        if (parsed)
        {
                ObjectContainer::const_iterator it, it_end = leaf->mGeometry.end();

                for (it = leaf->mGeometry.begin(); it != it_end; ++ it)
                {
                        TriangleIntersectable *tri = static_cast<TriangleIntersectable *>(*it);

                        Triangle3 t = tri->GetItem();

                        // hack: scale object appropriately
                        float scale = 0.01f;

                        t.mVertices[0] *= scale;
                        t.mVertices[1] *= scale;
                        t.mVertices[2] *= scale;

                        tri->SetItem(t);
                }

                leaf->UpdateBox();

                float offs = -leaf->GetOriginalBox().Min().y;

                // scale so pivot is always on bottom
                for (it = leaf->mGeometry.begin(); it != it_end; ++ it)
                {
                        TriangleIntersectable *tri = static_cast<TriangleIntersectable *>(*it);

                        Triangle3 t = tri->GetItem();

                        // hack: scale object appropriately
                        t.mVertices[0].y += offs;
                        t.mVertices[1].y += offs;
                        t.mVertices[2].y += offs;

                        tri->SetItem(t);
                }

                leaf->UpdateBox();


                cout<<"Dynamic object loaded successfully: " << leaf->GetBox() << endl;

                return leaf;
        } 
                

        cout<<"Dynamic object loading failed."<<endl;
        return NULL;
}


float Preprocessor::_HackComputeRenderCost(ViewCell *vc)
{
        ObjectPvsIterator pit = vc->GetPvs().GetIterator();

        float renderCost = 0;
        int i = 0;
        
        // first mark all objects from this pvs
        while (pit.HasMoreEntries())    
        {
                Intersectable *obj = pit.Next();
                if (obj->Type() == Intersectable::KD_INTERSECTABLE)
                {
                        KdIntersectable *kdObj = static_cast<KdIntersectable *>(obj);

                        /*if (mShowDistanceWeightedPvs)
                        {
                        const AxisAlignedBox3 box = kdObj->GetBox();

                        const float dist = SqrDistance(vc->GetBox().Center(), box.Center());
                        renderCost += 1.0f / dist;
                        }
                        else if (mShowDistanceWeightedTriangles)
                        {
                        const AxisAlignedBox3 box = kdObj->GetBox();

                        const float dist = SqrDistance(vc->GetBox().Center(), box.Center());
                        renderCost += kdObj->ComputeNumTriangles() / dist;
                        }
                        else //if (mShowWeightedTriangles)
                        {
                        */
                        renderCost += kdObj->ComputeNumTriangles();
                        //}
                }
                else if (obj->Type() == Intersectable::SCENEGRAPHLEAF_INTERSECTABLE)
                {
                        renderCost += (float)static_cast<SceneGraphLeafIntersectable *>(obj)->GetItem()->mGeometry.size();
                }
                
        }

        return renderCost;
}




/** Object has moved - must dynamically update all affected PVSs */
void
Preprocessor::ObjectMoved(SceneGraphLeaf *leaf)
{
  // first invalidate all PVS from which this object is visible
  ViewCellContainer::const_iterator vit, vit_end = mViewCellsManager->GetViewCells().end();
  
  AxisAlignedBox3 box = leaf->GetBox();
  Intersectable *inter = leaf->GetIntersectable();
  int removedEntries = 0;
  int removedSelfEntries = 0;
  CSeparatingAxisTester shadowVolume;
  int maxPlanes = 0;
  int allEntries = 0;

  int viewCells = 0;

  // now search for pvss which contained any mailed node
  for (vit = mViewCellsManager->GetViewCells().begin(); vit != vit_end; ++ vit) 
  {
          ViewCell *vc = *vit;
          ObjectPvs &pvs = vc->GetPvs();

          bool pvsChanged = false;

          if (Overlap(box, vc->GetBox())) 
          {
                  pvs.Clear();
                  removedEntries += pvs.GetSize();
                  pvsChanged = true;
          } 
          else 
          {
                  //cout<<vc->GetBox()<<" "<<box<<endl;
                  shadowVolume.Init(vc->GetBox(), box);
                  if (shadowVolume.CntPlanes() > maxPlanes)
                          maxPlanes = shadowVolume.CntPlanes();

                  int j = 0;
                  for (int i=0; i < pvs.mEntries.size(); i++) 
                  {
                          allEntries++;
                          Intersectable *o = pvs.mEntries[i].mObject;
                          if (o == inter) 
                          {
                                  removedSelfEntries++;
                                  pvsChanged = true;
                          } 
                          else 
                          {
                                  if (!shadowVolume.TestIsInsideShaft(o->GetBox())) 
                                  {
                                          if (j != i)
                                                  pvs.mEntries[j] = pvs.mEntries[i];
                                          j++;
                                  } 
                                  else 
                                  {
                                          removedEntries++;
                                          pvsChanged = true;
                                  }
                          }
                  }

                  // now the pvs has to be resorted
                  pvs.mLastSorted = 0;
                  if (j==0)
                          pvs.mEntries.clear();
                  else 
                  {
                          pvs.mEntries.resize(j);
                          if (j>1)
                                  pvs.SimpleSort();
                  }
          }

          if (pvsChanged)
          {
                  // recompute render cost
                  float renderCost = _HackComputeRenderCost(vc);
                  vc->GetPvs().mStats.mWeightedTriangles = renderCost;
          }
  }

  cerr<<"Number of removed pvs entries = "<<removedEntries<<" ("<<
        100.0f*removedEntries/(float)allEntries<<"%)"<<endl;
  cerr<<"Number of removed pvs self-entries = "<<removedSelfEntries<<endl;
  cerr<<"Max shadow planes used:"<<maxPlanes<<endl;
  //    cout<<"Cleared "<<pvsCounter<<" PVSs ("<<mViewCellsManager->GetViewCells().size()/
  //      (float)pvsCounter*100.0f<<"%) "<<endl;
  
}


void Preprocessor::ObjectRemoved(SceneGraphLeaf *leaf)
{
        ObjectMoved(leaf);
}


void Preprocessor::UpdateDynamicObjects()
{
        if (mUpdateDynamicObjects) 
        {
                // delete ALL dynamic stuff and rebuild using the new trafos
                preprocessor->mRayCaster->DeleteDynamicObjects();

#define MULTIPLE_OBJECTS 1

#if MULTIPLE_OBJECTS 
                static ObjectContainer objects;
                CLEAR_CONTAINER(objects);

                for (size_t i = 0; i < mDynamicObjects.size(); ++ i) 
                {
                        SceneGraphLeaf *l = mDynamicObjects[i];

                        for (size_t j=0; j < l->mGeometry.size(); j++) 
                        {
                                if (l->mGeometry[j]->Type() == Intersectable::TRIANGLE_INTERSECTABLE) 
                                {
                                        Triangle3 t(((TriangleIntersectable *)l->mGeometry[j])->GetItem());
                                        t.ApplyTransformation(l->GetTransformation());
                                        TriangleIntersectable *to = new TriangleIntersectable(t);
                                        to->SetId(l->GetIntersectable()->GetId());
                                        objects.push_back(to);
                                }
                        }
                }

                mRayCaster->AddDynamicObjecs(objects, IdentityMatrix());
#endif    

                SceneGraphLeaf *toUpdate = NULL;

                for (size_t i = 0; i < mDynamicObjects.size(); ++ i) 
                {
                        SceneGraphLeaf *l = mDynamicObjects[i];

#if  !MULTIPLE_OBJECTS
                        PrepareObjectsForRayCaster(l);
#endif

                        if (l->HasChanged())
                        {
                                cout<<"Updating affected PVSs..."<<endl;
                                preprocessor->ObjectMoved(l);
                                cout<<"done."<<endl;    
                                l->SetHasChanged(false);
                        }
                }
                
                mUpdateDynamicObjects = false;
        }
}


void Preprocessor::ScheduleUpdateDynamicObjects()
{
        mUpdateDynamicObjects = true;
}


void Preprocessor::PrepareObjectsForRayCaster(SceneGraphLeaf *l)
{
        cout<<"Updating dynamic objects in ray caster..."<<endl;

        mRayCaster->AddDynamicObjecs(l->mGeometry, l->GetTransformation());
        cout<<"done."<<endl;
}

}