source: GTP/trunk/App/Demos/Vis/FriendlyCulling/VisibilitySolutionConverter/VisibilitySolutionConverter.cpp @ 3282

#include "VisibilitySolutionConverter.h"
#include "Triangle3.h"
#include "Vector3.h"
#include "gzstream.h"
#include <iostream>
#include <queue>
#include <stack>


using namespace std;

// MAGIC of all bin exports
#ifndef MAGIC 
#define MAGIC 0x827923
#endif

#define BVH_VERSION 2.1

#define TYPE_INTERIOR -2
#define TYPE_LEAF -3


//static const float sScale = 0.05f;
static const float sScale = 1.0f;


static string ReplaceSuffix(const string &str, 
                                                        const string &a, 
                                                        const string &b)
{
        string result = str;

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

        return result;
}


static void LoadIndices(char *str, 
                                                const VertexArray &vertices, 
                                                const VertexArray &normals, 
                                                const vector<pair<float, float> > &texCoords,
                                                VertexArray &faceVertices,
                                                VertexArray &faceNormals,
                                                vector<TexCoord> &faceTexCoords,
                                                int line
                                                )
{
        vector<string> triples;

        char *next_token;

        // extract the triples of the form v/t/n v/t/n ...
        char *pch = strtok_s(str + 1, " ", &next_token);

        while (pch)
        {
                string s(pch);
                triples.push_back(s);
                
                pch = strtok_s(NULL, " ", &next_token);   
        }

        // throw away last symbol (\n)
        triples.back().resize(triples.back().size() - 1);

        vector<int> indices;
        vector<int> nIndices;
        vector<int> tIndices;

        char seps[] = " ";
        char seps2[] = "/";

        for (size_t i = 0; i < triples.size(); ++ i)
        {
                size_t found;
                found = triples[i].find_first_of(seps2);
                size_t prevfound = 0;

                // extract vertex, normal, texture indices
                string str = triples[i].substr(prevfound, found);

                int index = (int)strtol(str.c_str(), NULL, 10) - 1;
                int tIndex = index;
                int nIndex = index;     
                
                // try to extract texture and normal indices
                prevfound = found + 1;
                found = triples[i].find_first_of(seps2, prevfound);  

                if (found != string::npos)
                {
                        str = triples[i].substr(prevfound, found);

                        int idx = (int)strtol(str.c_str(), NULL, 10) - 1;
                        if (idx > 0) tIndex = idx;
                }
                
                if (found != string::npos)
                {
                        str = triples[i].substr(found + 1);

                        int idx = (int)strtol(str.c_str(), NULL, 10) - 1;
                        if (idx > 0) nIndex = idx;
                }

                // store indices
                if (index >= 0)
                {
                        indices.push_back(index);
                        nIndices.push_back(nIndex);
                        tIndices.push_back(tIndex);
                }

                // new triangle found
                if (indices.size() > 2)
                {
                        int idx1 = 0;
                        int idx2 = (int)indices.size() - 2;
                        int idx3 = (int)indices.size() - 1;

                        faceVertices.push_back(vertices[indices[idx1]]);
                        faceVertices.push_back(vertices[indices[idx2]]);
                        faceVertices.push_back(vertices[indices[idx3]]);

                        /*if (!normals.empty())
                        {
                                faceNormals.push_back(normals[nIndices[idx1]]);
                                faceNormals.push_back(normals[nIndices[idx2]]);
                                faceNormals.push_back(normals[nIndices[idx3]]);
                        }
                        else
                        {
                                // no face normals? => create normals
                                const CHCDemoEngine::Triangle3 
                                        tri(vertices[indices[idx1]],
                                            vertices[indices[idx2]], 
                                                vertices[indices[idx3]]);

                                const CHCDemoEngine::Vector3 n = tri.GetNormal();

                                faceNormals.push_back(n);
                                faceNormals.push_back(n);
                                faceNormals.push_back(n);
                        }*/

                        if (!texCoords.empty())
                        {
                                faceTexCoords.push_back(texCoords[tIndices[idx1]]);
                                faceTexCoords.push_back(texCoords[tIndices[idx2]]);
                                faceTexCoords.push_back(texCoords[tIndices[idx3]]);
                        }
                }
        }
}


VisibilitySolutionConverter::VisibilitySolutionConverter()
{}


VisibilitySolutionConverter::~VisibilitySolutionConverter()
{
        for (size_t i = 0; i < mGeometry.size(); ++ i)
        {
                delete [] mGeometry[i]->mVertices;
                delete [] mGeometry[i]->mNormals;
                delete [] mGeometry[i]->mTexCoords;

                delete mGeometry[i];
        }
        
        mGeometry.clear();
}


void VisibilitySolutionConverter::LoadShape(const VertexArray &vertices,
                                                                                        const VertexArray &normals,
                                                                                        const vector<TexCoord> &texCoords)
{
        int numElements = (int)vertices.size();
        Geometry *geom = new Geometry();

        // convert the triangles to geometry
        geom->mVertices = new CHCDemoEngine::Vector3[numElements];
        geom->mNormals = new CHCDemoEngine::Vector3[numElements];
        geom->mTexCoords = new TexCoord[numElements];

        geom->mVertexCount = numElements;
        geom->mTexcoordCount = (int)texCoords.size();

        for (int i = 0; i < numElements; ++ i)
        {
                // convert to our camera system: change y and z
                geom->mVertices[i] =  vertices[i];
                geom->mNormals[i] =  normals[i];
                
                if (i < geom->mTexcoordCount)
                {
                        geom->mTexCoords[i].first = texCoords[i].first;
                        geom->mTexCoords[i].second = texCoords[i].second;
                }
        }

        mGeometry.push_back(geom);
}


bool VisibilitySolutionConverter::Convert(const std::string &sceneInputFilename,
                                                                                  const std::string &sceneOutputFilename,
                                                                                  const std::string &bvhInputFilename,
                                                                                  const std::string &bvhOutputFilename)
{
        mNumShapes = 0;
        
        // delete previous geometry
        for (size_t i = 0; i < mGeometry.size(); ++ i)
        {
                delete [] mGeometry[i]->mVertices;
                delete [] mGeometry[i]->mNormals;
                delete [] mGeometry[i]->mTexCoords;

                delete mGeometry[i];
        }
        
        mGeometry.clear();

        if (!LoadSolutionTest(bvhInputFilename))
        //if (!LoadSolution(bvhInputFilename))
        {
                cerr << "could not read solution file" << endl;
                return false;
        }

        if (!ReadScene(sceneInputFilename))
        {
                cerr << "could not read file" << endl;
                return false;
        }

        // update bvh bounding boxes with loaded geometry
        UpdateBvh(mRoot);

        cout << "loading bvh, bb: " << mRoot->box << endl;

        cout << "writing scene" << endl;

        if (!WriteScene(sceneOutputFilename))
        {
                cerr << "could not write file" << endl;
                return false;
        }

        cout << "writing bvh" << endl;

        if (!WriteBvh(bvhOutputFilename))
        {
                cerr << "could not write bvh!" << endl;
                return false;
        }

        return true;
}


bool VisibilitySolutionConverter::ReadScene(const string &filename)
{
        /*
        VertexArray vertices;
        VertexArray normals;
        vector<TexCoord> texCoords;

        if (ReadObj(filename, vertices, normals, texCoords)) 
        {
                ConstructBvhObjects(vertices, normals, texCoords);
                return true;
        }*/

        vector<CHCDemoEngine::Triangle3 *> triangles;

        if (ReadObjSimple(filename, triangles)) 
        {
                ConstructBvhObjects2(triangles);
                return true;
        }

        /*for (size_t i = 0; i < triangles.size(); ++ i)
        delete triangles[i];
        */

        return false;
}


bool VisibilitySolutionConverter::ReadObj(const string &filename,
                                                                                  VertexArray &vertices,
                                                                                  VertexArray &normals,
                                                                                  vector<TexCoord> &texcoords) 
{
        FILE *file;

        if ((file = fopen(filename.c_str(), "r")) == NULL) return false;
        
        VertexArray tempVertices;

        VertexArray tempNormals;
        vector<TexCoord> tempTexcoords;

        vector<int> indices;

        int line = 0;
        const int len = 10000;
        char str[len];

        const string binFilename = ReplaceSuffix(filename, ".obj", ".bn");

        if (!ReadBinObj(binFilename, vertices))
        {
                cout << "binary dump " << binFilename << " not available, loading ascii obj" << endl;

                while (fgets(str, len, file) != NULL)
                {
                        if (line % 500000 == 0)
                                cout << line << " " << str;

                        ++ line;

                        switch (str[0])
                        {
                        case 'v': // vertex or normal
                                {
                                        float x, y, z;

                                        switch (str[1]) 
                                        {
                                        case 'n' :
                                                sscanf(str + 2, "%f %f %f", &x, &y, &z);
                                                tempNormals.push_back(CHCDemoEngine::Vector3(x, -z, y));
                                                break;
                                        case 't':
                                                sscanf(str + 2, "%f %f", &x, &y);
                                                tempTexcoords.push_back(pair<float, float>(x, y));
                                                break;
                                        default:
                                                sscanf(str + 1, "%f %f %f", &x, &y, &z);
                                                CHCDemoEngine::Vector3 v = CHCDemoEngine::Vector3(x, -z, y) * sScale;
                                                tempVertices.push_back(v);
                                                //cout <<"v " << x << " " << y << " "<< z << " ";
                                        }
                                        break;
                                }
                        case 'f': 
                                {
                                        //////////
                                        //-- indices in the current line

                                        LoadIndices(str, 
                                                tempVertices, tempNormals, tempTexcoords, 
                                                vertices, normals, texcoords, line);

                                        break;
                                }  
                                break;
                        default:
                                // throw away line
                                break;
                        }
                }

                ExportBinObj(binFilename, vertices);
        }
        else if (0)
        {
                cout << "creating normals" << endl;
                normals.reserve(vertices.size());

                for (size_t i = 0; i < vertices.size(); i += 3)
                {
                        // no face normals? => create normals
                        const CHCDemoEngine::Triangle3 
                                tri(vertices[i], vertices[i + 1], vertices[i + 2]);

                        const CHCDemoEngine::Vector3 n = tri.GetNormal();

                        normals.push_back(n);
                        normals.push_back(n);
                        normals.push_back(n);
                }

                cout << "finished creating normals" << endl;
        }

        fclose(file);

        return !vertices.empty();
}


static inline float RandomColor(float x)
{
        return x + (1.0f - x) * (float)rand() / RAND_MAX; 
}


void VisibilitySolutionConverter::WriteGeometry(ogzstream &str, Geometry *geom)
{
        int vertexCount = geom->mVertexCount;
        str.write(reinterpret_cast<char *>(&vertexCount), sizeof(int));
  
        str.write(reinterpret_cast<char *>(geom->mVertices), sizeof(CHCDemoEngine::Vector3) * vertexCount);
        str.write(reinterpret_cast<char *>(geom->mNormals), sizeof(CHCDemoEngine::Vector3) * vertexCount);

        int texCoordCount = 0;//geom->mTexcoordCount;
        str.write(reinterpret_cast<char *>(&texCoordCount), sizeof(int));

        if (texCoordCount)
        {
                str.write(reinterpret_cast<char *>(geom->mTexCoords), sizeof(float) * texCoordCount * 2);
        }

        ///////
        //-- texture

        int texId = -1;
        str.write(reinterpret_cast<char *>(&texId), sizeof(int));

        bool alphaTestEnabled = false;
        bool cullFaceEnabled = true;
        //bool cullFaceEnabled = false;

        str.write(reinterpret_cast<char *>(&alphaTestEnabled), sizeof(bool));
        str.write(reinterpret_cast<char *>(&cullFaceEnabled), sizeof(bool));

        // material
        bool hasMaterial = true;
        
        str.write(reinterpret_cast<char *>(&hasMaterial), sizeof(bool));
        
        if (hasMaterial)
        {
                CHCDemoEngine::Vector3 ambient, diffuse, spec, emm;

                ambient.x = ambient.y = ambient.z = 0.2f;
                //diffuse.x = diffuse.y = diffuse.z = 1.0f;

                diffuse.x = RandomColor(0.5f); 
                diffuse.y = RandomColor(0.5f);
                diffuse.z = RandomColor(0.5f);

                spec.x = spec.y = spec.z = .0f;
                emm = spec;

                // only write rgb part of the material
                str.write(reinterpret_cast<char *>(&ambient), sizeof(CHCDemoEngine::Vector3));
                str.write(reinterpret_cast<char *>(&diffuse), sizeof(CHCDemoEngine::Vector3));
                str.write(reinterpret_cast<char *>(&spec), sizeof(CHCDemoEngine::Vector3));
                str.write(reinterpret_cast<char *>(&emm), sizeof(CHCDemoEngine::Vector3));
        }
}


bool VisibilitySolutionConverter::WriteScene(const string &filename)
{
        ogzstream ofile(filename.c_str());

        if (!ofile.is_open()) return false;
        
        int textureCount = 0;
        ofile.write(reinterpret_cast<char *>(&textureCount), sizeof(int));


        ///////////
        //-- write shapes

        int numShapes = (int)mGeometry.size();
        ofile.write(reinterpret_cast<char *>(&numShapes), sizeof(int));

        vector<Geometry *>::const_iterator it, it_end = mGeometry.end();

        for (it = mGeometry.begin(); it != it_end; ++ it)
        {
                WriteGeometry(ofile, *it);
        }


        int entityCount = numShapes;
        ofile.write(reinterpret_cast<char *>(&entityCount), sizeof(int));


        //////////
        //-- write single scene entity for each shape

        for (int i = 0; i < numShapes; ++ i)
        {
                // no transformation
                bool hasTrafo = false;
                ofile.write(reinterpret_cast<char *>(&hasTrafo), sizeof(bool));

                // a dummy lod
                int numLODs = 1;
                ofile.write(reinterpret_cast<char *>(&numLODs), sizeof(int));

                float dist = 0;
                ofile.write(reinterpret_cast<char *>(&dist), sizeof(float));

                int shapesPerEntity = 1;
                ofile.write(reinterpret_cast<char *>(&shapesPerEntity), sizeof(int));

                int shapeId = i;
                ofile.write(reinterpret_cast<char *>(&shapeId), sizeof(int));
        }

        return true;
}


void VisibilitySolutionConverter::ConstructBvhObjects(const VertexArray &vertices,
                                                                                                          const VertexArray &normals,
                                                                                                          const vector<TexCoord> &texCoords)
{
        CHCDemoEngine::AxisAlignedBox3 testBox;
        testBox.Initialize();

        for (int i = 0; i < vertices.size(); ++ i)
                testBox.Include(vertices[i]);
        cout << "geometry bounds: " << testBox << endl;

        mGeometry.reserve(mBvhLeaves.size());
        mNumShapes = (int)mBvhLeaves.size();

        for (size_t i = 0; i < mBvhLeaves.size(); ++ i)
        {
                BvhLeaf *node = mBvhLeaves[i];

                VertexArray _vertices;  
                VertexArray _normals;
                vector<TexCoord> _texCoords;

                const int size = node->last - node->first + 1;

                _vertices.reserve(size);
                _normals.reserve(size);

                //cout << "vtx: " << size << endl;
                for (int j = node->first; j <= node->last; ++ j)
                {
                        const int idx = 3 * mGlobalTriangleIds[j];

                        //cout << "idx: " << 3 * mGlobalTriangleIds[j] << " j " << j << " " << vertices.size()<< endl;
                        for (int k = 0; k < 3; ++ k)
                        {
                                _vertices.push_back(vertices[idx + k]);
                                //_normals.push_back(normals[idx + k]);
                                //_texCoords.push_back(texCoords[idx + k]);
                        }

                        // no face normals? => create normals
                        const CHCDemoEngine::Triangle3 
                                tri(vertices[idx], vertices[idx + 1], vertices[idx + 2]);

                        const CHCDemoEngine::Vector3 n = tri.GetNormal();

                        _normals.push_back(n);
                        _normals.push_back(n);
                        _normals.push_back(n);
                }

                LoadShape(_vertices, _normals, _texCoords);
                
                // we store geometry in our bvh => change first and last pointer
                // from triangles to geometry
                node->first = (int)mGeometry.size() - 1;
                node->last = (int)mGeometry.size() - 1;

                //_vertices.clear();
                //_normals.clear();
                //_texCoords.clear();
        }
}


bool VisibilitySolutionConverter::ReadBvh(FILE *fr) 
{
        int buffer[6]; 
        fread(buffer, sizeof(int), 6, fr);

        if (buffer[0] != MAGIC) 
        {
                cerr << "Error: Wrong file type" << endl;
                return false;
        }

        if (buffer[1] != (int)(1000 * BVH_VERSION)) 
        {
                cerr << "Error: Wrong BVH version" << endl;
                return false;
        }

        cout << "loading " << buffer[2] << " triangles" << endl;
        // load triangle ids
        size_t numTriangles = buffer[2];
        mGlobalTriangleIds.reserve(numTriangles);

        for (size_t i = 0; i < numTriangles; ++i) 
        {
                int id;
                fread(&id, sizeof(int), 1, fr);
                mGlobalTriangleIds.push_back(id);
                //triangles[i] = scene->triangles[id];
        }

        const size_t numNodes = buffer[5];

        mNumNodes = 0; // this was set to 1 in constructor!

        mRoot = LoadNode(fr, 0);

        if (mNumNodes != numNodes) 
        {
                cerr << "Warning: Loaded " << mNumNodes <<
                            " bvh nodes instead of " << buffer[5] << endl;
        }

        fclose(fr);
        
        return true;
}


void VisibilitySolutionConverter::UpdateLeafBox(BvhLeaf *leaf)
{
        leaf->box.Initialize();

        Geometry *geom = mGeometry[leaf->first];

        for (size_t i = 0; i < geom->mVertexCount; ++ i)
        {
                CHCDemoEngine::Vector3 v = geom->mVertices[i];
                leaf->box.Include(v);
        }
}


BvhNode *VisibilitySolutionConverter::LoadNode(FILE *fr, int depth)
{
        ++ mNumNodes;
        
        int buffer[4];
        fread(buffer, sizeof(int), 4, fr);

        if (buffer[2] != -1) 
        {
                BvhInterior *interior = new BvhInterior();
                
                interior->first = buffer[0];
                interior->last  = buffer[1];
                interior->axis  = buffer[2];
                interior->id    = buffer[3];
                interior->depth = depth;

                BvhNode *front, *back;

                front = LoadNode(fr, depth + 1);
                back  = LoadNode(fr, depth + 1);

                front->parent = interior;
                back->parent = interior;

                interior->front = front;
                interior->back = back;
        
                return (BvhNode *)interior;
        }
        else 
        {
                // leaf
                BvhLeaf *leaf = new BvhLeaf();

                leaf->first = buffer[0];
                leaf->last  = buffer[1];
                leaf->axis  = buffer[2];
                leaf->id    = buffer[3];

                leaf->depth = depth;

                mBvhLeaves.push_back(leaf);
        
                return (BvhNode *)leaf;
        }
}


bool VisibilitySolutionConverter::ReadDummyTree(FILE *fr)
{
        int buffer[256]; 
        fread(buffer, sizeof(int), 3, fr);

        // read dummy bounding box
        float dummy[6];
        fread(dummy, sizeof(float) * 6, 1, fr);

        int stack = 1;

        // read dummy tree
        while (stack)
        {
                int axis;
                fread(&axis, sizeof(int), 1, fr);
                -- stack;

                if (axis != - 1) 
                {
                        float dummy;
                        fread(&dummy, sizeof(float), 1, fr);
                        
                        stack += 2;
                }
        }
  
        return true;
}



bool VisibilitySolutionConverter::LoadSolution(const string &filename)
{
        FILE *fr = fopen(filename.c_str(), "rb");

        cerr << "Info: Loading visibility solution from file '" + filename + "'" << endl;
  
        if (fr == NULL) 
        {
                cerr << "Error: Cannot open file for reading" << endl;
                return false;
        }

        float totalSamples, totalTime;

        fread(&totalSamples, sizeof(float), 1, fr);
        fread(&totalTime, sizeof(float), 1, fr);

        // just need to convert objects => read dummy visibility tree
        bool ok = ReadDummyTree(fr);

        // read bvh to determine objects (= the leaves of the bvh)
        if (ok) ok = ReadBvh(fr);

        fclose(fr);
        
        if (ok) 
                cout << "Info: visibility solution loaded" << endl;
        else
                cout << "Info: loading visibility solution failed" << endl;
  
        return true;
}


bool VisibilitySolutionConverter::LoadSolutionTest(const string &filename)
{
        FILE *fr = fopen(filename.c_str(), "rb");

        cout << "Loading bvh from file '" + filename + "'" << endl;
  
        if (fr == NULL) 
        {
                cerr << "Error: Cannot open file for reading" << endl;
                return false;
        }

        // read bvh to determine objects (= the leaves of the bvh)
        bool ok = ReadBvh(fr);

        fclose(fr);
        
        if (ok) 
                cout << "Info: visibility solution loaded" << endl;
        else
                cout << "Info: loading visibility solution failed" << endl;
  
        return true;
}


bool VisibilitySolutionConverter::ReadBinObj(const string &filename,
                                                                                         VertexArray &vertices
                                                                                         )
{
        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));
        vertices.reserve(numTriangles * 3);
        cout << "loading " << numTriangles * 3 << " vertices (" 
                << numTriangles * 3 * sizeof(CHCDemoEngine::Vector3) / (1024 * 1024) << " MB)" << endl;

        int i = 0;

        while (1)
        {
                CHCDemoEngine::Vector3 v;
                inStream.read(reinterpret_cast<char *>(&v), sizeof(CHCDemoEngine::Vector3));

                // end of file reached
                if (inStream.eof())     break;
                
                //v *= scale;
                vertices.push_back(v);

                if (((i ++) % t) == 0)
                         cout << "\r" << i << "/" << numTriangles * 3 << "\r";
        }
        
        cout << "finished loading vertices" << endl;

        if (i != numTriangles * 3)
                cerr << "warning: " << numTriangles * 3 << " != " << i << endl;

        inStream.close();

        return true;
}


bool VisibilitySolutionConverter::ExportBinObj(const string &filename,
                                                                                           const VertexArray &vertices)
{       
        ogzstream ofile(filename.c_str());
        if (!ofile.is_open()) return false;

        int numTriangles = (int)vertices.size() / 3;

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

        VertexArray::const_iterator it, it_end = vertices.end();

        for (it = vertices.begin(); it != it_end; ++ it)
        {
                CHCDemoEngine::Vector3 v = *it;
                ofile.write(reinterpret_cast<char *>(&v), sizeof(CHCDemoEngine::Vector3));
        }

        cout << "exported " << numTriangles * 3 << " vertices" << endl;

        ofile.close();

        return true;
}


void VisibilitySolutionConverter::WriteNextNode(ogzstream &stream, 
                                                                                                BvhNode *node)
{
        int nodeType;

        if (node->IsLeaf())
                nodeType = TYPE_LEAF;
        else 
                nodeType = TYPE_INTERIOR;
                
        stream.write(reinterpret_cast<char *>(&nodeType), sizeof(int));

        CHCDemoEngine::AxisAlignedBox3 box = node->box;
        //box.Scale(sScale);

        CHCDemoEngine::Vector3 bMin = box.Min();
        CHCDemoEngine::Vector3 bMax = box.Max();

        stream.write(reinterpret_cast<char *>(&(node->first)), sizeof(int));
        stream.write(reinterpret_cast<char *>(&(node->last)), sizeof(int));

        stream.write(reinterpret_cast<char *>(&bMin), sizeof(CHCDemoEngine::Vector3));
        stream.write(reinterpret_cast<char *>(&bMax), sizeof(CHCDemoEngine::Vector3));
}


void VisibilitySolutionConverter::UpdateBvh(BvhNode *node)
{
        if (!node->IsLeaf())
        {
                BvhInterior *interior = (BvhInterior *)node;

                UpdateBvh(interior->front);
                UpdateBvh(interior->back);

                interior->first = min(interior->front->first, interior->back->first);
                interior->last = max(interior->front->last, interior->back->last);
                
                node->box = Union(interior->front->box, interior->back->box);
        }
        else
        {
                UpdateLeafBox((BvhLeaf *)node);
                //cout << "bb: " << node->box << endl;
        }
}


bool VisibilitySolutionConverter::WriteBvh(const string &filename)
{
        std::queue<BvhNode *> tQueue;
        ogzstream stream(filename.c_str());

        if (!stream.is_open()) return NULL;

        WriteNextNode(stream, mRoot);

        tQueue.push(mRoot);
        
        while (!tQueue.empty())
        {
                BvhNode *node = tQueue.front();
                tQueue.pop();

                if (!node->IsLeaf())
                {
                        BvhInterior *interior = static_cast<BvhInterior *>(node);

                        BvhNode *front = interior->front;
                        BvhNode *back = interior->back;

                        WriteNextNode(stream, front);
                        WriteNextNode(stream, back);

                        tQueue.push(front);                     
                        tQueue.push(back);
                }
        }

        return true;
}


bool VisibilitySolutionConverter::ReadObjSimple(const string &filename,
                                                                                                vector<CHCDemoEngine::Triangle3 *> &triangles
                                                                                                ) 
{
        FILE *file;

        if ((file = fopen(filename.c_str(), "r")) == NULL) return false;
        
        VertexArray vertices;

        int line = 0;
        const int len = 10000;
        char str[len];

        const string binFilename = ReplaceSuffix(filename, ".obj", ".bn");

        cout << "binary dump " << binFilename << " not available, loading ascii obj" << endl;

        while (fgets(str, len, file) != NULL)
        {
                if (line % 500000 == 0)
                        cout << line << " " << str;

                ++ line;

                switch (str[0])
                {
                case 'v': // vertex or normal
                        {
                                float x, y, z;

                                sscanf(str + 1, "%f %f %f", &x, &y, &z);
                                CHCDemoEngine::Vector3 v = CHCDemoEngine::Vector3(x, -z, y) * sScale;
                                vertices.push_back(v);

                                if (vertices.size() == 3)
                                {
                                        CHCDemoEngine::Triangle3 *tri = 
                                                new CHCDemoEngine::Triangle3(vertices[0], vertices[1], vertices[2]);

                                        triangles.push_back(tri);
                                        vertices.clear();
                                }
                                break;
                        }
                default:
                        // throw away line
                        break;
                }
        }

        fclose(file);

        return !triangles.empty();
}


void VisibilitySolutionConverter::ConstructBvhObjects2(const vector<CHCDemoEngine::Triangle3 *> &triangles)
{
        CHCDemoEngine::AxisAlignedBox3 testBox;
        testBox.Initialize();

        for (size_t i = 0; i < triangles.size(); ++ i)
        {
                testBox.Include(triangles[i]->mVertices[0]);
                testBox.Include(triangles[i]->mVertices[1]);
                testBox.Include(triangles[i]->mVertices[2]);
        }

        cout << "geometry bounds: " << testBox << endl;

        mGeometry.reserve(mBvhLeaves.size());
        mNumShapes = (int)mBvhLeaves.size();

        VertexArray _vertices;  
        VertexArray _normals;
        vector<TexCoord> _texCoords;

        int total = 0;
        for (size_t i = 0; i < mBvhLeaves.size(); ++ i)
        {
                BvhLeaf *node = mBvhLeaves[i];
                const int size = node->last - node->first + 1;

                total += size;

                if (i % 1000 == 0)
                        cout << "o " << i << " " << size << " " << total << endl;

                _vertices.clear();
                _normals.clear();
                _texCoords.clear();

                //cout << "vtx: " << size << endl;
                for (int j = node->first; j <= node->last; ++ j)
                {
                        const int idx = mGlobalTriangleIds[j];

                        //cout << "idx: " << 3 * mGlobalTriangleIds[j] << " j " << j << " " << vertices.size()<< endl;
                        for (int k = 0; k < 3; ++ k)
                        {
                                _vertices.push_back(triangles[idx]->mVertices[k]);
                        }

                        const CHCDemoEngine::Vector3 n = triangles[idx]->GetNormal();

                        _normals.push_back(n);
                        _normals.push_back(n);
                        _normals.push_back(n);

                        delete triangles[idx];
                }

                LoadShape(_vertices, _normals, _texCoords);
                
                // we store geometry in our bvh => change first and last pointer
                // from triangles to geometry
                node->first = (int)mGeometry.size() - 1;
                node->last = (int)mGeometry.size() - 1;

                //_vertices.clear();
                //_normals.clear();
                //_texCoords.clear();
        }
}