partition.cpp

Go to the documentation of this file.

/*
 * partition.cpp
 *
 * Copyright (C) 2010  Thomas A. Vaughan
 * All rights reserved.
 *
 * Program to test the glut-demo and kd-tree libraries.
 * The kd-tree demo gives a visual representation of the tree, and how it
 * interacts with the view frustum.  This demo (partition.cpp) uses a kd-tree
 * internally to partition a large 3D space and perform front-to-back drawing.
 */

// includes --------------------------------------------------------------------
#include <iostream>
#include <fstream>

#include "glut-demo/glut-demo.h"
#include "glut-model/glut-model.h"
#include "kdtree/kdtree.h"
#include "nstream/nstream.h"
#include "perf/perf.h"
#include "util/file.h"
#include "wave-glut/frustum.h"



static int s_drawCount                  = 0;    // number of objects drawn/frame
static float s_max                      = -1;


////////////////////////////////////////////////////////////////////////////////
//
//      static helper methods
//
////////////////////////////////////////////////////////////////////////////////

class CountDisplay : public glut::DisplayLine {
public:
        // virtual destructor --------------------------------------------------
        ~CountDisplay(void) throw() { }

        // glut::DisplayLine class interface methods ---------------------------
        ePosition getPosition(void) throw() { return eBottomLeft; }

        const char * getText(void) throw() {
                        sprintf(m_buffer, "%d objects drawn", s_drawCount);
                        return m_buffer;
                }

private:
        // private member data -------------------------------------------------
        char            m_buffer[256];
};



static float
getRandom
(
IN float M
)
throw()
{
        return (M * rand()) / RAND_MAX;
}



static float
getRandom2
(
IN float M
)
throw()
{
        float x = (1.0 * rand()) / RAND_MAX;
        //return x * x * x * M;
        return x * x * M;
}


static point3d_t
getRandomPosition
(
IN const rect3d_t& base
)
throw()
{
        point3d_t p;

        float buffer = 0.02 * s_max;

        p.x = base.x0 + buffer + getRandom(base.x1 - base.x0 - 2.0 * buffer);
        p.y = base.y0 + buffer + getRandom2(base.y1 - base.y0 - 2.0 * buffer);
        p.z = base.z0 + buffer + getRandom(base.z1 - base.z0 - 2.0 * buffer);

        return p;
}



static void
drawRect
(
IN const rect3d_t& r
)
throw()
{
        glBegin(GL_LINES);
        for (int i = 0; i < 12; ++i) {
                point3d_t p0, p1;
                r.getEdge(i, p0, p1);
                glVertex3fv((GLfloat *) &p0);
                glVertex3fv((GLfloat *) &p1);
        }
        glEnd();
}



static void
walkFrontToBack
(
IN const kdtree::Node * node,
IN const glut::render_context_t& rc,
IN glut::RenderQueue * rq,
IN const frustum_t& frustum,
IN glut::Renderable * model
)
throw()
{
        ASSERT(node, "null");
        ASSERT(rq, "null");
        ASSERT(model, "null");

        const point3d_t& start = rc.viewer.getPosition();

        const kdtree::plane_t& plane = node->getSortPlane();
        kdtree::eSort sort = kdtree::sortPoint(plane, start);

        const kdtree::Node * left = node->getLeftChild();
        const kdtree::Node * right = node->getRightChild();

        const kdtree::Node * farthest = left;
        const kdtree::Node * closest = right;
        if (kdtree::eSort_Left == sort) {
                farthest = right;
                closest = left;
        }

        // first visit closest
        if (closest) {
                // only visit if in frustum
                const rect3d_t& r = closest->getRect();
                if (eContains_HitMask & frustum.containsRect(r)) {
                        walkFrontToBack(closest, rc, rq, frustum, model);
                }
        }

        // visit ourselves
        const kdtree::Node::vec_entries_t& entries = node->getStaticEntries();
        for (kdtree::Node::vec_entries_t::const_iterator i = entries.begin();
             i != entries.end(); ++i) {
                const kdtree::Node::entry_rec_t& er = *i;

                // only draw if in frustum
                if (!(eContains_HitMask & frustum.containsRect(er.rect)))
                        continue;       // skip this one

                point3d_t p = er.rect.getMidpoint();

                ++s_drawCount;

                glMatrixMode(GL_MODELVIEW);
                glPushMatrix();
                glTranslatef(p.x, p.y, p.z);
                model->render(rc, rq);
                glPopMatrix();
        }

        // visit furthest last
        if (farthest) {
                // only visit if in frustum
                const rect3d_t& r = farthest->getRect();
                if (eContains_HitMask & frustum.containsRect(r)) {
                        walkFrontToBack(farthest, rc, rq, frustum, model);
                }
        }
}



class Drawer : public glut::DemoHost {
public:
        Drawer(IN int nObjects, IN const char * filename) throw() {
                        ASSERT(nObjects > 0, "Bad object count: %d", nObjects);
                        ASSERT(filename, "null");
                        m_nObjects = nObjects;
                        m_filename = filename;
                        m_scale = 1;
                }

        ~Drawer(void) throw() { }

        // glut::Host class interface methods ----------------------------------
        float getDelta(void) { return 0.25 * m_scale; }

        void getDisplayLines(IN glut::vec_display_lines_t& lines) {
                        lines.clear();

                        // add object count
                        smart_ptr<glut::DisplayLine> count = new CountDisplay;
                        ASSERT(count, "out of memory");
                        lines.push_back(count);
                }

        void onInit(void) {
                        std::string parent;
                        GetParentDirectory(m_filename.c_str(), parent);
                        DPRINTF("Using material directory: %s", parent.c_str());
                        m_registry = glut::getSimpleRegistry(parent.c_str());
                        ASSERT(m_registry, "failed to create simple registry");

                        {
                                perf::Timer timer("load wgm object");
                                m_model = glut::loadModel(m_filename.c_str(),
                                    m_registry);
                                ASSERT(m_model, "null");
                        }
                        rect3d_t modelRect = m_model->getBoundingBox();
                        modelRect.dump("Model bounding box");
                        m_scale = modelRect.getDiagonal();
                        s_max = 20.0 * m_scale;

                        perf::Timer timer("set up kd-tree");
                        ASSERT_THROW(m_nObjects > 0, "Bad object count: "
                            << m_nObjects);

                        rect3d_t bounds = modelRect;
                        bounds.inflate(s_max);
                        bounds.dump("kd-tree bounds");

                        m_root = kdtree::Node::create(bounds);
                        ASSERT(m_root, "failed to create kdtree root node");

                        for (int i = 0; i < m_nObjects; ++i) {
                                point3d_t p = getRandomPosition(bounds);
                                rect3d_t r = modelRect;
                                r.translate(p);
                                smart_ptr<kdtree::Entry> e;
                                m_root->addStaticEntry(e, r);
                        }

                        int nMaxPerNode = 8;
                        {
                                perf::Timer timer("subdivide kd-tree");
                                m_root->subdivide(kdtree::eStrategy_Balance,
                                    nMaxPerNode);
                        }
                }

        void display3D(IN const glut::render_context_t& rc,
                                IN glut::RenderQueue * rq) {
                        ASSERT(rq, "null");
                        frustum_t f;
                        glut::getViewFrustum(rc.camera, rc.viewer, f);
//                      f.dump("frustum");

                        s_drawCount = 0;
                        walkFrontToBack(m_root, rc, rq, f, m_model);

                        // draw frustum lines--ideally we won't see these!
                        glut::drawFrustumEdges(f, glut_color_t(0.2, 1.0, 0.2));
                }

private:
        // private member data -------------------------------------------------
        int                             m_nObjects;
        float                           m_scale;
        std::string                     m_filename;
        smart_ptr<kdtree::Node>         m_root;
        smart_ptr<glut::MaterialRegistry> m_registry;
        smart_ptr<glut::Renderable>     m_model;
};



////////////////////////////////////////////////////////////////////////////////
//
//      entry point
//
////////////////////////////////////////////////////////////////////////////////

int
main
(
IN int argc,
IN const char * argv[]
)
{
        ASSERT(3 == argc,
            "Usage: glut-demo-partition nObjects wgmPath");
        int nObjects = atoi(argv[1]);
        const char * wgmPath = argv[2];
        DPRINTF("Using nObjects=%d, wgmPath=%s", nObjects, wgmPath);

        try {
                // title
                const int bufSize = 1023;
                char title[bufSize + 1];
                snprintf(title, bufSize, "3D partitioned space (%d x %s)",
                    nObjects, GetFilename(wgmPath));
                title[bufSize] = 0;     // ensure null termination

                // main loop
                smart_ptr<glut::DemoHost> host = new Drawer(nObjects, wgmPath);
                ASSERT(host, "out of memory");
                glut::startDemo(argc, argv, title, host);

        } catch (std::exception& e) {
                DPRINTF("Exception: %s", e.what());
        }

        // only reach here on error
        return -1;
}