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

#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"


#ifdef GTP_INTERNAL
#include "ArchModeler2MLRT.hxx"
#endif

#define DEBUG_RAYCAST 0


namespace GtpVisibilityPreprocessor {

const static bool ADDITIONAL_GEOMETRY_HACK = false;

//Preprocessor *preprocessor;


// 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.0025, 0.01, 0.0025);
                        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),
mRayCastMethod(0),
mSceneGraph(NULL)
{
        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 );
        Environment::GetSingleton()->GetIntValue("Preprocessor.rayCastMethod", mRayCastMethod);

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

        Debug << "detect empty view space=" << mDetectEmptyViewSpace << endl;
        Debug << "load meshes: " << mLoadMeshes << endl;

        if (mRayCastMethod == 0)
                cout << "ray cast method: internal" << endl;
        else
                cout << "ray cast method: intel" << 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);
}

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

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

        // intel ray caster can only trace triangles
        vector<FaceParentInfo> *fi = (mRayCastMethod == Preprocessor::INTEL_RAYCASTER) ?
                &mFaceParents : NULL;

        if (files == 1) {
                
                if (strstr(filename.c_str(), ".x3d"))
                  parser = new X3dParser;
                else
                  if (strstr(filename.c_str(), ".ply") || strstr(filename.c_str(), ".plb"))
                        parser = new PlyParser;
                  else if (strstr(filename.c_str(), ".obj"))
                          parser = new ObjParser;
                  else 
                          parser = new UnigraphicsParser;

                cout << filename << endl;
                
                result = parser->ParseFile(
                                filename, 
                                mSceneGraph->GetRoot(),
                                mLoadMeshes,
                                fi);
                        
                delete parser;

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

                        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;
                mSceneGraph->CollectObjects(&mObjects);
                mSceneGraph->GetRoot()->UpdateBox();
 
                if (0)
                {
                        Exporter *exporter = Exporter::GetExporter("testload.x3d");
                        if (exporter)
                        {
                                exporter->ExportGeometry(mObjects);
                                delete exporter;
                        }
                }
        }

        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,
                                          const bool bsptree
                                          )
{
  Exporter *exporter = Exporter::GetExporter(filename);
        
  if (exporter) {
    if (0 && scene)
      exporter->ExportScene(mSceneGraph->GetRoot());

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

        if (0 && bsptree) {
                //exporter->SetWireframe();
                exporter->ExportBspTree(*mBspTree);
        }

    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;
                mViewCellsManager = ViewCellsManager::LoadViewCells(buf, &mObjects, true);
        }
        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
                mViewCellsManager->SetViewSpaceBox(mSceneGraph->GetBox());
        }
        
        //-- parameters for render heuristics evaluation
        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();
                
        }
        
        return true;
}

  
bool
Preprocessor::ConstructViewCells()
{
  // if not already loaded, construct view cells from file
  if (!mLoadViewCells) {
        mViewCellsManager->SetViewSpaceBox(mKdTree->GetBox());
        
        // construct view cells using it's own set of samples
        mViewCellsManager->Construct(this);
        
        //-- several visualizations and statistics
        Debug << "view cells construction finished: " << 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);     

                HierarchyManager *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 OBJECT_BASED_DISTRIBUTION: 
                return new ObjectBasedDistribution(*this);
        case OBJECT_DIRECTION_BASED_DISTRIBUTION:
                return new ObjectDirectionBasedDistribution(*this);
        case DIRECTION_BASED_DISTRIBUTION:
                return new DirectionBasedDistribution(*this);
        case DIRECTION_BOX_BASED_DISTRIBUTION: 
                return new DirectionBoxBasedDistribution(*this);
        case SPATIAL_BOX_BASED_DISTRIBUTION:
                return new SpatialBoxBasedDistribution(*this);
        //case OBJECTS_INTERIOR_DISTRIBUTION:
        //      return new ObjectsInteriorDistribution(*this);
        default: // no valid strategy
                Debug << "warning: no valid sampling strategy" << endl;
                return NULL;
        }

        // should never come here
        return NULL;
}


bool Preprocessor::InitRayCast(const string externKdTree, const string internkdtree)
{
        bool loadKdTree;
        Environment::GetSingleton()->GetBoolValue("Preprocessor.loadKdTree", loadKdTree);
        
        if (!loadKdTree)
        {       
                //-- build new kd tree from scene geometry
                BuildKdTree();
                KdTreeStatistics(cout);
        }
        else
        {
                const long startTime = GetTime();
                cout << "loading kd tree file " << internkdtree << " ... ";

                if (!LoadKdTree(internkdtree))
                {
                        cout << "error loading kd tree with filename " << internkdtree << ", rebuilding it instead ..." << endl;

                        BuildKdTree();
                        KdTreeStatistics(cout);
                }

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

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

        switch (mRayCastMethod) // use intel ray tracing
        {
        case INTEL_RAYCASTER:
#ifdef GTP_INTERNAL
          cout<<"Ray Cast file: " << externKdTree << endl;
          return mlrtaLoadAS(externKdTree.c_str());
#endif
        case INTERNAL_RAYCASTER:
        default:
                break;
        }

        return true;
}


int Preprocessor::CastIntelDoubleRay(
                                                                         const Vector3 &viewPoint,
                                                                         const Vector3 &direction,
                                                                         const float probability,
                                                                         VssRayContainer &vssRays,
                                                                         const AxisAlignedBox3 &box
                                                                         )
{
#ifdef GTP_INTERNAL
        //cout << "intel ray" << endl;
        VssRay *vssRay  = NULL;
        int hits = 0;
        int hittriangle;
        Vector3 pointA, pointB;
        Vector3 normalA, normalB;
        Intersectable *objectA = NULL, *objectB = NULL;
        float dist;
        double normal[3];

        hittriangle = mlrtaIntersectAS(&viewPoint.x,
                &direction.x,
                normal,
                dist);

        if (hittriangle != -1 ) {
                if (hittriangle >= mFaceParents.size())
                        cerr<<"Warning: triangle index out of range! "<<hittriangle<<endl;
                else {
                        objectA = mFaceParents[hittriangle].mObject;
                        normalA = Vector3(normal[0], normal[1], normal[2]);
                        // Get the normal of that face
                        //              Mesh *mesh = ((MeshInstance *)objectA)->GetMesh();
                        //              normalA = mesh->GetFacePlane(mFaceParents[forward_hit_triangles[i]].mFaceIndex).mNormal;
                        //-rays[index+i].mDirection; // $$ temporary
                        pointA = viewPoint + direction*dist;
                }
        }


        Vector3 dir = -direction;
        hittriangle = mlrtaIntersectAS(&viewPoint.x,
                &dir.x,
                normal,
                dist);

        if (hittriangle != -1 ) {
                if (hittriangle >= mFaceParents.size())
                        cerr<<"Warning: triangle index out of range! "<<hittriangle<<endl;
                else {
                        objectB = mFaceParents[hittriangle].mObject;
                        normalB = Vector3(normal[0], normal[1], normal[2]);
                        // Get the normal of that face
                        //              Mesh *mesh = ((MeshInstance *)objectB)->GetMesh();
                        //              normalA = mesh->GetFacePlane(mFaceParents[forward_hit_triangles[i]].mFaceIndex).mNormal;
                        //-rays[index+i].mDirection; // $$ temporary
                        pointB = viewPoint + dir * dist;
                }
        }

        return ProcessRay(viewPoint,
                direction,
                objectA, pointA, normalA,
                objectB, pointB, normalB,
                probability,
                vssRays,
                box
                );
#else
        return -1;
#endif
}


Intersectable *Preprocessor::CastIntelSingleRay(const Vector3 &viewPoint,
                                                                                                const Vector3 &direction,
                                                                                                //const float probability,
                                                                                                Vector3 &tPoint,
                                                                                                const AxisAlignedBox3 &box
                                                                                                )
{
        AxisAlignedBox3 sbox = box;
        sbox.Enlarge(Vector3(-Limits::Small));

        if (!sbox.IsInside(viewPoint))
                return 0;
        
#ifdef GTP_INTERNAL
        float pforg[3];
        float pfdir[3];
        double pfnorm[3];

        pforg[0] = viewPoint[0]; pforg[1] = viewPoint[1]; pforg[2] = viewPoint[2];
        pfdir[0] = direction[0]; pfdir[1] = direction[1]; pfdir[2] = direction[2];

        float dist;
        const int hittriangle = mlrtaIntersectAS(pforg, pfdir, pfnorm, dist);

        if (hittriangle == -1)
          {
                static Ray ray;
                SetupRay(ray, viewPoint, direction);
                
                float tmin = 0, tmax;
                if (box.ComputeMinMaxT(ray, &tmin, &tmax) && tmin < tmax)
                  {
                        tPoint = ray.Extrap(tmax);
                  }
                
                return NULL;
          }
        else {
          if (hittriangle >= mFaceParents.size()) {
                cerr<<"Warning: triangle index out of range! "<<hittriangle<<endl;
                return NULL;
          }
          else {
                
                tPoint[0] = pforg[0] + pfdir[0] * dist;
                tPoint[1] = pforg[1] + pfdir[1] * dist;
                tPoint[2] = pforg[2] + pfdir[2] * dist;
                
                return mFaceParents[hittriangle].mObject;
          }
        }

#else
        const int hittriangle = -1;
        return NULL;
#endif

}


int Preprocessor::CastInternalRay(
                                                                  const Vector3 &viewPoint,
                                                                  const Vector3 &direction,
                                                                  const float probability,
                                                                  VssRayContainer &vssRays,
                                                                  const AxisAlignedBox3 &box
                                                                  )
{
  //cout << "internal ray" << endl;
  int hits = 0;
  static Ray ray;
  Intersectable *objectA, *objectB;
  Vector3 pointA, pointB;

  //  AxisAlignedBox3 box = Union(mKdTree->GetBox(), mViewCellsManager->GetViewSpaceBox());
  AxisAlignedBox3 sbox = box;
  sbox.Enlarge(Vector3(-Limits::Small));
  if (!sbox.IsInside(viewPoint))
        return 0;
        
  SetupRay(ray, viewPoint, direction);
  ray.mFlags &= ~Ray::CULL_BACKFACES;

  // cast ray to KD tree to find intersection with other objects
  float bsize = Magnitude(box.Size());
  
  
  if (mKdTree->CastRay(ray)) {
        objectA = ray.intersections[0].mObject;
        pointA = ray.Extrap(ray.intersections[0].mT);
        if (mDetectEmptyViewSpace)
          if (DotProd(ray.intersections[0].mNormal, direction) >= 0) {
                // discard the sample
                return 0;
          }
        
  } else {
        objectA = NULL;
        // compute intersection with the scene bounding box
        float tmin, tmax;
        if (box.ComputeMinMaxT(ray, &tmin, &tmax) && tmin < tmax)
          pointA = ray.Extrap(tmax);
        else
          return 0;
  }

  SetupRay(ray, viewPoint, -direction);
  ray.mFlags &= ~Ray::CULL_BACKFACES;
  
  if (mKdTree->CastRay(ray)) {
        objectB = ray.intersections[0].mObject;
        pointB = ray.Extrap(ray.intersections[0].mT);
        if (mDetectEmptyViewSpace)
          if (DotProd(ray.intersections[0].mNormal, direction) <= 0) {
                // discard the sample
                return 0;
          }
  } else {
        objectB = NULL;
        float tmin, tmax;
        if (box.ComputeMinMaxT(ray, &tmin, &tmax) && tmin < tmax)
          pointB = ray.Extrap(tmax);
        else
          return 0;
  }
  
  
  VssRay *vssRay  = NULL;
  bool validSample = (objectA != objectB);
  if (validSample) {
        if (objectA) {
          vssRay = new VssRay(pointB,
                                                  pointA,
                                                  objectB,
                                                  objectA,
                                                  mPass,
                                                  probability
                                                  );
          vssRays.push_back(vssRay);
          //cout << "ray: " << *vssRay << endl;
          hits ++;
        }
        
        if (objectB) {
          vssRay = new VssRay(pointA,
                                                  pointB,
                                                  objectA,
                                                  objectB,
                                                  mPass,
                                                  probability
                                                  );
          vssRays.push_back(vssRay);
          //cout << "ray: " << *vssRay << endl;
          hits ++;
        }
  }
  
  return hits;
}


int
Preprocessor::ProcessRay(
                                                 const Vector3 &viewPoint,
                                                 const Vector3 &direction,
                                                 Intersectable *objectA,
                                                 Vector3 &pointA,
                                                 const Vector3 &normalA,
                                                 Intersectable *objectB,
                                                 Vector3 &pointB,
                                                 const Vector3 &normalB,
                                                 const float probability,
                                                 VssRayContainer &vssRays,
                                                 const AxisAlignedBox3 &box
                                                 )
{
  int hits=0;
#if DEBUG_RAYCAST
  Debug<<"PR ";
#endif
  if (objectA == NULL && objectB == NULL)
        return 0;
  
  AxisAlignedBox3 sbox = box;
  sbox.Enlarge(Vector3(-Limits::Small));

  if (!sbox.IsInside(viewPoint))
        return 0;

  if (objectA == NULL) {
        // compute intersection with the scene bounding box
        static Ray ray;
        SetupRay(ray, viewPoint, direction);
        
        float tmin, tmax;
        if (box.ComputeMinMaxT(ray, &tmin, &tmax) && tmin < tmax)
          pointA = ray.Extrap(tmax);
        else
          return 0;
  } else {
        if (mDetectEmptyViewSpace)
          if (DotProd(normalA, direction) >= 0) {
                // discard the sample
                return 0;
          }
  }

  if (objectB == NULL) {
        // compute intersection with the scene bounding box
        static Ray ray;
        SetupRay(ray, viewPoint, -direction);

        float tmin, tmax;
        if (box.ComputeMinMaxT(ray, &tmin, &tmax) && tmin < tmax)
          pointB = ray.Extrap(tmax);
        else
          return 0;
  } else {
        if (mDetectEmptyViewSpace)
          if (DotProd(normalB, direction) <= 0) {
                // discard the sample
                return 0;
          }
  }
  
  VssRay *vssRay  = NULL;
  bool validSample = (objectA != objectB);
  if (validSample) {
        if (objectA) {
          vssRay = new VssRay(pointB,
                                                  pointA,
                                                  objectB,
                                                  objectA,
                                                  mPass,
                                                  probability
                                                  );
          vssRays.push_back(vssRay);
          //cout << "ray: " << *vssRay << endl;
          hits ++;
        }
        
        if (objectB) {
          vssRay = new VssRay(pointA,
                                                  pointB,
                                                  objectA,
                                                  objectB,
                                                  mPass,
                                                  probability
                                                  );
          vssRays.push_back(vssRay);
          //cout << "ray: " << *vssRay << endl;
          hits ++;
        }
  }


  return hits;
}

void
Preprocessor::CastRays16(const int index,
                                                 SimpleRayContainer &rays, 
                                                 VssRayContainer &vssRays,
                                                 const AxisAlignedBox3 &sbox)
{
  int i;
  const int num = 16;

#if DEBUG_RAYCAST
  Debug<<"C16 "<<flush;
#endif
  if (mRayCastMethod == INTEL_RAYCASTER) {
#ifdef GTP_INTERNAL

  int forward_hit_triangles[16];
  float forward_dist[16];

  int backward_hit_triangles[16];
  float backward_dist[16];


  Vector3 min = sbox.Min();
  Vector3 max = sbox.Max();
  
  for (i=0; i < num; i++) {
        mlrtaStoreRayAS16(&rays[index + i].mOrigin.x,
                                          &rays[index + i].mDirection.x,
                                          i);
  }
  
  mlrtaTraverseGroupAS16(&min.x,
                                                 &max.x,
                                                 forward_hit_triangles,
                                                 forward_dist);

  for (i=0; i < num; i++) {
        Vector3 dir = -rays[index + i].mDirection;
        mlrtaStoreRayAS16(&rays[index+i].mOrigin.x,
                                          &dir.x,
                                          i);
  }
  
  mlrtaTraverseGroupAS16(&min.x,
                                                 &max.x,
                                                 backward_hit_triangles,
                                                 backward_dist);
  

  for (i=0; i < num; i++) {
        Intersectable *objectA = NULL, *objectB = NULL;
        Vector3 pointA, pointB;
        Vector3 normalA, normalB;

        if (forward_hit_triangles[i] != -1 ) {
          if (forward_hit_triangles[i] >= mFaceParents.size())
                cerr<<"Warning: triangle index out of range! "<<forward_hit_triangles[i]<<endl;
          else { 
                objectA = mFaceParents[forward_hit_triangles[i]].mObject;
                // Get the normal of that face
                normalA = objectA->GetNormal(mFaceParents[forward_hit_triangles[i]].mFaceIndex);
                //-rays[index+i].mDirection; // $$ temporary
                pointA = rays[index+i].Extrap(forward_dist[i]);
          }
        }
         
        if (backward_hit_triangles[i]!=-1) {
          if (backward_hit_triangles[i] >= mFaceParents.size())
                cerr<<"Warning: triangle  index out of range! "<<backward_hit_triangles[i]<<endl;
          else { 
                objectB = mFaceParents[backward_hit_triangles[i]].mObject;
                normalB = objectB->GetNormal(mFaceParents[forward_hit_triangles[i]].mFaceIndex);
                
                // normalB = rays[index+i].mDirection; // $$ temporary
                pointB = rays[index+i].Extrap(-backward_dist[i]);
          }
        }
 
        ProcessRay(rays[index+i].mOrigin,
                           rays[index+i].mDirection,
                           objectA, pointA, normalA,
                           objectB, pointB, normalB,
                           rays[index+i].mPdf,
                           vssRays,
                           sbox
                           );
  }
  
#endif
  
  } else {

        for (i=index; i < index + num; i++) {
          CastRay(rays[i].mOrigin,
                          rays[i].mDirection,
                          rays[i].mPdf,
                          vssRays,
                          sbox);
        }
  }
#if DEBUG_RAYCAST
  Debug<<"C16F\n"<<flush;
#endif
}

void
Preprocessor::CastRays(
                                           SimpleRayContainer &rays,
                                           VssRayContainer &vssRays
                                           )
{
  long t1 = GetTime();
  
  for (int i = 0; i < (int)rays.size(); ) {
          // method only available for intel raycaster yet
        if (i + 16 < (int)rays.size()) {

          CastRays16(
                                 i,
                                 rays,
                                 vssRays,
                                 mViewCellsManager->GetViewSpaceBox());
          i += 16;
        } else {
          CastRay(rays[i].mOrigin,
                          rays[i].mDirection,
                          rays[i].mPdf,
                          vssRays,
                          mViewCellsManager->GetViewSpaceBox());
          i++;
        }
        if (i % 10000 == 0)
          cout<<".";
  }

  long t2 = GetTime();
  cout<<2*rays.size()/(1e3*TimeDiff(t1, t2))<<"M rays/s"<<endl;
}

Intersectable *
Preprocessor::CastSimpleRay(
                                                        const Vector3 &viewPoint,
                                                        const Vector3 &direction,
                                                        const AxisAlignedBox3 &box,
                                                        Vector3 &point,
                                                        Vector3 &normal
                                                        )
{
  Intersectable *result = NULL;
  switch (mRayCastMethod)
        {
        case INTEL_RAYCASTER: {
         
          int hittriangle;

#ifdef GTP_INTERNAL
          float dist; 
          double n[3];

          hittriangle = mlrtaIntersectAS(&viewPoint.x,
                                                                         &direction.x,
                                                                         n,
                                                                         dist);

           if (hittriangle !=-1 ) {
                if (hittriangle >= mFaceParents.size())
                  cerr<<"Warning: triangle index out of range! "<<hittriangle<<endl;
                else {
                  result = mFaceParents[hittriangle].mObject;
                  normal = Vector3(n[0], n[1], n[2]);
                  point = viewPoint + direction*dist;
                }
          }
#else
          hittriangle = -1;
#endif

          break;
        }
        case INTERNAL_RAYCASTER:
        default: {
          static Ray ray;
          
          ray.intersections.clear();
          // do not store anything else then intersections at the ray
          ray.Init(viewPoint, direction, Ray::LOCAL_RAY);
          
          ray.mFlags &= ~Ray::CULL_BACKFACES;
          
          if (mKdTree->CastRay(ray)) {
                result = ray.intersections[0].mObject;
                point = ray.Extrap(ray.intersections[0].mT);
                normal = ray.intersections[0].mNormal;
          }
          break;
        }
        }
  return result;
}

int
Preprocessor::CastRay(
                                          const Vector3 &viewPoint,
                                          const Vector3 &direction,
                                          const float probability,
                                          VssRayContainer &vssRays,
                                          const AxisAlignedBox3 &box
                                          )
{
#if DEBUG_RAYCAST
  Debug<<"CR "<<flush;
#endif
  switch (mRayCastMethod)
        {
        case INTEL_RAYCASTER:
                return CastIntelDoubleRay(viewPoint, direction, probability, vssRays, box);
        case INTERNAL_RAYCASTER:
        default:
                return CastInternalRay(viewPoint, direction, probability, vssRays, box);
        }
#if DEBUG_RAYCAST       
  Debug<<"CRF "<<flush;
#endif  
}


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

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

        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
                                                        )
{
        ray.Clear();
        // do not store anything else then intersections at the ray
        ray.Init(point, direction, Ray::LOCAL_RAY);
}

}