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

#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 "InternalRayCaster.h"



#define DEBUG_RAYCAST 0
#define SHOW_RAYCAST_TIMING 1


namespace GtpVisibilityPreprocessor {

const static bool ADDITIONAL_GEOMETRY_HACK = false;


// HACK: Artificially modify scene to watch rendercost changes
static void AddGeometry(SceneGraph *scene)
{
        scene->GetRoot()->UpdateBox();

        AxisAlignedBox3 sceneBox = scene->GetBox();

        int n = 200;

        if (0)
        {
                // form grid of boxes
                for (int i = 0; i < n; ++ i)
                {
                        for (int j = 0; j < n; ++ j)
                        {
                                const Vector3 scale2((float)j * 0.8f / n + 0.1f,  0.05f, (float)i * 0.8f  / (float)n + 0.1f);

                                const Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());

                                const Vector3 boxSize = sceneBox.Size() * Vector3(0.0025f, 0.01f, 0.0025f);
                                AxisAlignedBox3 box(pt2, pt2 + boxSize);
                                Mesh *mesh = CreateMeshFromBox(box);

                                mesh->Preprocess();

                                MeshInstance *mi = new MeshInstance(mesh);
                                scene->GetRoot()->mGeometry.push_back(mi);
                        }
                }

                for (int i = 0; i < n; ++ i)
                {
                        for (int j = 0; j < n; ++ j)
                        {
                                const Vector3 scale2(0.15f, (float)j * 0.8f / n + 0.1f, (float)i * 0.8f  / (float)n + 0.1f);

                                Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());

                                Vector3 boxSize = sceneBox.Size() * Vector3(0.0025f, 0.01f, 0.0025f);
                                AxisAlignedBox3 box(pt2, pt2 + boxSize);
                                Mesh *mesh = CreateMeshFromBox(box);

                                mesh->Preprocess();

                                MeshInstance *mi = new MeshInstance(mesh);
                                scene->GetRoot()->mGeometry.push_back(mi);
                        }
                }

                for (int i = 0; i < n; ++ i)
                {
                        const Vector3 scale2(2, 0.2f, (float)i * 0.8f  / (float)n + 0.1f);

                        Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());
                        Vector3 boxSize = sceneBox.Size() * Vector3(0.005f, 0.02f, 0.005f);

                        AxisAlignedBox3 box(pt2 + 0.1f, pt2 + boxSize);
                        Mesh *mesh = CreateMeshFromBox(box);

                        mesh->Preprocess();

                        MeshInstance *mi = new MeshInstance(mesh);
                        scene->GetRoot()->mGeometry.push_back(mi);
                }

                scene->GetRoot()->UpdateBox();
        }

        if (1)
        {
                // plane separating view space regions
                const Vector3 scale(1.0f, 0.0, 0);

                Vector3 pt = sceneBox.Min() + scale * (sceneBox.Max() - sceneBox.Min());

                Plane3 cuttingPlane(Vector3(1, 0, 0), pt);
                Mesh *planeMesh = new Mesh();

                Polygon3 *poly = sceneBox.CrossSection(cuttingPlane);
                IncludePolyInMesh(*poly, *planeMesh);

                planeMesh->Preprocess();

                MeshInstance *planeMi = new MeshInstance(planeMesh);
                scene->GetRoot()->mGeometry.push_back(planeMi);
        }       
}


Preprocessor::Preprocessor():
mKdTree(NULL),
mBspTree(NULL),
mVspBspTree(NULL),
mHierarchyManager(NULL),
mViewCellsManager(NULL),
mRenderSimulator(NULL),
mPass(0),
mSceneGraph(NULL),
mRayCaster(NULL),
mStopComputation(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.delayVisibilityComputation",
                                                                                          mDelayVisibilityComputation);
        
        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()->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);

        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;
}


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 hierarchy manager...\n";
        DEL_PTR(mHierarchyManager);
        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";

        DEL_PTR(mRenderSimulator);
        DEL_PTR(renderer);
        DEL_PTR(mRayCaster);
}


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


static int SplitFilenames(const string str, vector<string> &filenames)
{
        int pos = 0;

        while(1) {
                int npos = (int)str.find(';', pos);
                
                if (npos < 0 || npos - pos < 1)
                        break;
                filenames.push_back(string(str, pos, npos - pos));
                pos = npos + 1;
        }
        
        filenames.push_back(string(str, pos, str.size() - pos));
        return (int)filenames.size();
}


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

        cout << "binary obj dump available, loading " << filename.c_str() << endl;
        // table associating indices with vectors
        map<int, Vector3> hashTable;

        // table for vertices
        VertexContainer vertices; 
        FaceContainer faces;

        while (1)
        {
                Triangle3 tri;
                
                samplesIn.read(reinterpret_cast<char *>(tri.mVertices + 0), sizeof(Vector3));
                samplesIn.read(reinterpret_cast<char *>(tri.mVertices + 1), sizeof(Vector3));
                samplesIn.read(reinterpret_cast<char *>(tri.mVertices + 2), sizeof(Vector3));
                
                // end of file reached
                if (samplesIn.eof())
                        break;

                TriangleIntersectable *obj = new TriangleIntersectable(tri);
                root->mGeometry.push_back(obj);

                // matt: we don't really need to keep an additional data structure
                // if working with triangles => remove this
                if (parents) 
                {
                        FaceParentInfo info(obj, 0);
                        parents->push_back(info);
                }       
        }
        
        return true;
}


bool Preprocessor::ExportBinaryObj(const string filename, SceneGraphNode *root)
{
        //ifstream samplesIn(filename, ios::binary);
        ogzstream samplesOut(filename.c_str());
        if (!samplesOut.is_open())
                return false;

        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 = dynamic_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;
                }
        }

        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 = dynamic_cast<TriangleIntersectable *>(obj)->GetItem();
                        //if (bbox.IsInside(tri.mVertices[0]) && bbox.IsInside(tri.mVertices[1]) && bbox.IsInside(tri.mVertices[2]))
                        //{
                                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 = dynamic_cast<TriangleIntersectable *>(obj)->GetItem();
                        //if (bbox.IsInside(tri.mVertices[0]) && bbox.IsInside(tri.mVertices[1]) && bbox.IsInside(tri.mVertices[2]))
                        //{
                                Triangle3 tri = dynamic_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;

}

static string ReplaceSuffix(string filename, string a, string b)
{
        string result = filename;

        int pos = (int)filename.rfind(a, (int)filename.size() - 1);
        if (pos == filename.size() - a.size()) {
                result.replace(pos, a.size(), b);
        }
        return result;
}


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 SceneGraphNode());

        // intel ray caster can only trace triangles
        int rayCastMethod;
        Environment::GetSingleton()->GetIntValue("Preprocessor.rayCastMethod", rayCastMethod);
        vector<FaceParentInfo> *fi = (rayCastMethod == RayCaster::INTEL_RAYCASTER) ?
                &mFaceParents : NULL;

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

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

                        // hack: load binary dump
                        string binFile = ReplaceSuffix(filename, ".obj", ".bin");

                        if (!mLoadMeshes)
                        {
                                result = LoadBinaryObj(binFile, mSceneGraph->GetRoot(), fi);
                        }

                        if (!result)
                        {
                                cout << "no binary dump available or loading full meshes, parsing file" << endl;
                                parser = new ObjParser;
                
                                result = parser->ParseFile(filename, 
                                                                   mSceneGraph->GetRoot(),
                                                                   mLoadMeshes,
                                                                   fi);
                                                
                                // only works for triangles
                                if (!mLoadMeshes)
                                {
                                        cout << "exporting binary obj to " << binFile << "... " << endl;
                                        ExportBinaryObj(binFile, mSceneGraph->GetRoot());
                                        cout << "finished" << endl;
                                }

                                delete parser;
                        }
                        else if (0)
                        {
                                ExportBinaryObj("../data/test.bin", mSceneGraph->GetRoot());
                        }
                }
                else 
                {
                        parser = new UnigraphicsParser;
                        result = parser->ParseFile(filename, 
                                                                           mSceneGraph->GetRoot(),
                                                                           mLoadMeshes,                                                           
                                                                           fi);
                        delete parser;
                }
                
                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;

                        SceneGraphNode *node = new SceneGraphNode();
                        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) 
        { 
                // HACK 
                if (ADDITIONAL_GEOMETRY_HACK)
                        AddGeometry(mSceneGraph);

                mSceneGraph->AssignObjectIds();
 
                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);
                
                // temp hack
                //ExportObj("cropped_vienna.obj", mObjects);
                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 (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();

  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()
{
        ///////
        //-- parse view cells construction method

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

        if (mLoadViewCells)
        {       
          Environment::GetSingleton()->GetStringValue("ViewCells.filename", buf);
          cout << "loading view cells from " << buf << endl<<flush;
          
         mViewCellsManager = ViewCellsManager::LoadViewCells(buf, &mObjects, true, NULL);

         cout << "view cells loaded." << endl<<flush;
         
          if (!mViewCellsManager)
          {
                  return false;
          }
        }
        else
        {
                // parse type of view cell container
                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);
                
                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);
        
        if (mUseGlRenderer || mUseGlDebugger)
          {
                // NOTE: render texture should be power of 2 and square
                // renderer must be initialised
                // $$matt
                //              renderer = new GlRendererBuffer(1024, 768, mSceneGraph, mViewCellsManager, mKdTree);
                //              renderer->makeCurrent();
                
          }

        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;
}


HierarchyManager *Preprocessor::CreateHierarchyManager(const char *name)
{
        HierarchyManager *hierarchyManager;

        if (strcmp(name, "osp") == 0)
        {
                Debug << "hierarchy manager: osp" << endl;
                // HACK for testing if per kd evaluation works!!
                const bool ishack = false;
                if (ishack)
                        hierarchyManager = new HierarchyManager(mKdTree);
                else
                        hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
        }
        else if (strcmp(name, "bvh") == 0)
        {
                Debug << "hierarchy manager: bvh" << endl;
                hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
        }
        else // only view space partition
        {
                Debug << "hierarchy manager: obj" << endl;
                hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
        }

        return hierarchyManager;
}


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);     

                mHierarchyManager = CreateHierarchyManager(buf);
                mViewCellsManager = new VspOspViewCellsManager(vcTree, mHierarchyManager);
        }
        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


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


bool Preprocessor::LoadKdTree(const string filename)
{
        mKdTree = new KdTree();

        return mKdTree->LoadBinTree(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 samplesIn(fileName);
        if (!samplesIn.is_open())
                return false;

        string buf;
        while (!(getline(samplesIn, 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 samplesIn(fileName, ios::binary);
        if (!samplesIn.is_open())
                return false;

        while (1)
        {
                 samplesIn.read(reinterpret_cast<char *>(&origin), sizeof(Vector3));
                 samplesIn.read(reinterpret_cast<char *>(&termination), sizeof(Vector3));
                 samplesIn.read(reinterpret_cast<char *>(&(sObj.mId)), sizeof(int));
                 samplesIn.read(reinterpret_cast<char *>(&(tObj.mId)), sizeof(int));
                
                 if (samplesIn.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
        samplesIn.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;
}

bool Preprocessor::GenerateRays(const int number,
                                                                const int sampleType,
                                                                SimpleRayContainer &rays)
{
        const int startSize = (int)rays.size();
        SamplingStrategy *strategy = GenerateSamplingStrategy(sampleType);

        if (!strategy)
        {
                return false;
        }

        for (int i=0; (int)rays.size() - startSize < number; ++ i) 
        {
                SimpleRay newRay;

                if (strategy->GenerateSample(newRay))
                {
#if 1
                        rays.AddRay(newRay);
#else
                        GenerateRayBundle(rays, newRay, 16, 0);
#endif
                }       
        }

        delete strategy;
    return true;
}


SamplingStrategy *Preprocessor::GenerateSamplingStrategy(const int strategyId) const
{
        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 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::InitRayCast(const string externKdTree, const string internKdTree)
{
        // 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);
        cout << mKdTree->GetBox() << endl;

        if (0)
        {
                Exporter *exporter = Exporter::GetExporter("dummykd.x3d");
                        
                if (exporter)
                {
                        exporter->ExportKdTree(*mKdTree, true);
                        delete exporter;
                }
        }

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

        if (rayCastMethod == 0)
        {
                mRayCaster = new InternalRayCaster(*this, mKdTree);
                cout << "ray cast method: internal" << endl;
        }
        else
        {
#ifdef GTP_INTERNAL
                mRayCaster = new IntelRayCaster(*this, externKdTree);
                cout << "ray cast method: intel" << endl;
#endif
        }

        return true;
}


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

        for (int i = 0; i < (int)rays.size();)
        {
                if (i + 16 < (int)rays.size()) 
                {
                        mRayCaster->CastRays16(
                                                                   i,
                                                                   rays,                                
                                                                   vssRays,
                                                                   mViewCellsManager->GetViewSpaceBox(),
                                                                   castDoubleRays,
                                                                   pruneInvalidRays);
                        i += 16;
                }
                else 
                  {
                        mRayCaster->CastRay(
                                                                rays[i],
                                                                vssRays,
                                                                mViewCellsManager->GetViewSpaceBox(),
                                                                castDoubleRays,
                                                                pruneInvalidRays);
                        i ++;
                  }
                if (i % 10000 == 0)
                  cout<<"\r"<<i<<"/"<<(int)rays.size()<<"\r";
        }
        cout<<endl;
        
        long t2 = GetTime();

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


bool Preprocessor::GenerateRayBundle(SimpleRayContainer &rayBundle,                                                                     
                                                                         const SimpleRay &mainRay,
                                                                         const int number,
                                                                         const int pertubType) const
{
        rayBundle.push_back(mainRay);

        const float pertubOrigin = 0.0f;
        const float pertubDir = 0.2f;

        for (int i = 0; i < number - 1; ++ i)
        {
                Vector3 pertub;

                pertub.x = RandomValue(0.0f, pertubDir);
                pertub.y = RandomValue(0.0f, pertubDir);
                pertub.z = RandomValue(0.0f, pertubDir);

                const Vector3 newDir = mainRay.mDirection + pertub;
                //const Vector3 newDir = mainRay.mDirection;

                pertub.x = RandomValue(0.0f, pertubOrigin);
                pertub.y = RandomValue(0.0f, pertubOrigin);
                pertub.z = RandomValue(0.0f, pertubOrigin);

                const Vector3 newOrigin = mainRay.mOrigin + pertub;
                //const Vector3 newOrigin = mainRay.mOrigin;

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

        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);     
}


}