kd-tree.cpp

Go to the documentation of this file.

/*
 * kd-tree.cpp
 *
 * Copyright (C) 2010  Thomas A. Vaughan
 * All rights reserved.
 *
 * Program to test the glut-demo and kd-tree libraries.
 */

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

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



static const float s_max                = 250.0;

static int s_displayLevel               = 0;    // root

static int s_displayWalk                = 0;    // farthest
static int s_maxWalkLevel               = 10;   // starting guess

static float s_angle                    = 0.0;  // y-rotation angle of viewer
static const float s_degreesPerRadian   = 180.0 / M_PI;
static const float s_deltaA             = 5.0 / s_degreesPerRadian;

static float s_zAngle                   = 0.0;  // z-rotation of viewer
static const float s_maxZAngle          = 0.5 * M_PI;


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

class LevelDisplay : public glut::DisplayLine {
public:
        ~LevelDisplay(void) throw() { }

        ePosition getPosition(void) throw() { return glut::DisplayLine::eBottomLeft; }
        const char * getText(void) throw() {
                        sprintf(m_buffer, "level (d/D)isplay: %d", s_displayLevel);
                        return m_buffer;
                }

private:
        char            m_buffer[256];
};



class WalkDisplay : public glut::DisplayLine {
public:
        ~WalkDisplay(void) throw() { }

        ePosition getPosition(void) throw() { return glut::DisplayLine::eBottomLeft; }
        const char * getText(void) throw() {
                        sprintf(m_buffer, "wal(k/K) level: %d", s_displayWalk);
                        return m_buffer;
                }

private:
        char            m_buffer[256];
};



class ViewAngle : public glut::DisplayLine {
public:
        ~ViewAngle(void) throw() { }

        ePosition getPosition(void) throw() { return glut::DisplayLine::eBottomLeft; }
        const char * getText(void) throw() {
                        sprintf(m_buffer, "(v)iew angle: %d degrees",
                            (int) (s_angle * s_degreesPerRadian));
                        return m_buffer;
                }

private:
        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 void
getRandomRect
(
IN const rect3d_t& base,
IN float size,
OUT rect3d_t& r
)
throw()
{
        r.x0 = base.x0 + getRandom(base.x1 - base.x0 - size);
        r.y0 = base.y0 + getRandom2(base.y1 - base.y0 - size);
        r.z0 = base.z0 + getRandom(base.z1 - base.z0 - size);

        r.x1 = r.x0 + size;
        r.y1 = r.y0 + size;
        r.z1 = r.z0 + size;
}



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
displayNode
(
IN const kdtree::Node * node,
IN int level
)
throw()
{
        ASSERT(node, "null");
        ASSERT(level >= 0, "bad level: %d", level);

        if (level == s_displayLevel) {
                glColor3f(0, 0, 1);
                rect3d_t r = node->getRect();
                r.inflate(-1);  // just to separate neighbors a bit
                drawRect(r);
        }

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

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

                glColor3f(1, 0, 1);
                drawRect(er.rect);
        }

        if (left) {
                displayNode(left, level + 1);
        }
        if (right) {
                displayNode(right, level + 1);
        }
}



static void
walkFrontToBack
(
IN const kdtree::Node * node,
IN const frustum_t& frustum,
IN const point3d_t& start,
IO int& level
)
throw()
{
        ASSERT(node, "null");
        ASSERT(level >= 0, "Bad level: %d", level);

        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) {
                walkFrontToBack(closest, frustum, start, level);
        }

        // visit ourselves -- only if we are a leaf!
        rect3d_t r = node->getRect();
        if (!left && !right &&
            (eContains_HitMask & frustum.containsRect(r))) {
                float dr = 1.0 / (1.25 * s_maxWalkLevel);
                float red = 1.0 - dr * level;
                if (red < 0.1) {
                        red = 0.1;
                }
                glColor3f(red, 0,  0);
                ++level;
                if (!s_displayWalk || s_displayWalk == level) {
                        r.inflate(-2);
                        drawRect(r);
                }
        }

        // visit furthest last
        if (farthest) {
                walkFrontToBack(farthest, frustum, start, level);
        }
}



class Drawer : public glut::DemoHost {
public:
        Drawer(IN int nEntries, IN int nMPN) throw()
                { m_nEntries = nEntries; m_nMPN = nMPN; }
        ~Drawer(void) throw() { }

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

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

                        // add our display level widget
                        smart_ptr<LevelDisplay> ld = new LevelDisplay;
                        ASSERT(ld, "out of memory");
                        lines.push_back(ld);

                        // add walk level widget
                        smart_ptr<WalkDisplay> wd = new WalkDisplay;
                        ASSERT(wd, "out of memory");
                        lines.push_back(wd);

                        // add view angle widget
                        smart_ptr<ViewAngle> va = new ViewAngle;
                        ASSERT(va, "out of memory");
                        lines.push_back(va);
                }

        void onInit(void) {
                        perf::Timer timer("set up kd-tree");
                        ASSERT_THROW(m_nEntries > 0, "Bad entry count: "
                            << m_nEntries);

                        rect3d_t bounds;
                        bounds.clear();
                        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_nEntries; ++i) {
                                rect3d_t r;
                                getRandomRect(bounds, getRandom(10), r);
                                smart_ptr<kdtree::Entry> e;
                                m_root->addStaticEntry(e, r);
                        }

                        {
                                perf::Timer timer("subdivide kd-tree");
                                m_root->subdivide(kdtree::eStrategy_Balance, m_nMPN);
                        }

                        m_maxDisplay = m_root->getTreeDepth() + 1;
                }

        void onKey(IN int key, IN int mods) {
                        switch (key) {
                        case 'Z':
                                s_zAngle -= s_deltaA;
                                if (s_zAngle < -s_maxZAngle) {
                                        s_zAngle = -s_maxZAngle;
                                }
                                break;

                        case 'z':
                                s_zAngle += s_deltaA;
                                if (s_zAngle > s_maxZAngle) {
                                        s_zAngle = s_maxZAngle;
                                }
                                break;

                        case 'V':
                                s_angle -= s_deltaA;
                                if (s_angle < -M_PI) {
                                        s_angle += 2.0 * M_PI;
                                }
                                break;

                        case 'v':
                                s_angle += s_deltaA;
                                if (s_angle > M_PI) {
                                        s_angle -= 2.0 * M_PI;
                                }
                                break;

                        case 'K':
                                s_displayWalk--;
                                if (s_displayWalk < 0) {
                                        s_displayWalk = 0;
                                }
                                break;

                        case 'k':
                                ++s_displayWalk;
                                if (s_displayWalk > s_maxWalkLevel) {
                                        s_displayWalk = s_maxWalkLevel;
                                }
                                break;

                        case 'D':
                                s_displayLevel--;
                                if (s_displayLevel < 0) {
                                        s_displayLevel = m_maxDisplay - 1;
                                }
                                break;
                                
                        case 'd':
                                s_displayLevel++;
                                break;
                        }
                        s_displayLevel = s_displayLevel % m_maxDisplay;
                }

        void display3D(IN const glut::render_context_t& rc,
                                IN glut::RenderQueue * rq) {
                        ASSERT(rq, "null");
                        glDisable(GL_LIGHTING);
                        displayNode(m_root, 0);

                        // set up another camera, viewer, frustum for demo
                        glut::camera_t camera;
                        float zFar = 300.0;     // shorter zfar for demo
                        camera.setZFar(zFar);
                        m_viewer.setYRotation(s_angle);
                        m_viewer.setUpRotation(s_zAngle);

                        point3d_t start = m_viewer.getPosition();
                        point3d_t end = start + zFar * m_viewer.getFacing();

                        glColor3f(1, 1, 0);
                        glBegin(GL_LINES);
                                glVertex3fv((GLfloat *) &start);
                                glVertex3fv((GLfloat *) &end);
                        glEnd();

                        // display example frustum
                        frustum_t frustum;
                        glut::getViewFrustum(camera, m_viewer, frustum);
                        glColor3f(1, 1, 1);
                        glBegin(GL_LINES);
                        for (int i = 0; i < 12; ++i) {
                                point3d_t p0, p1;
                                frustum.getEdge(i, p0, p1);
                                glVertex3fv((GLfloat *) &p0);
                                glVertex3fv((GLfloat *) &p1);
                        }
                        glEnd();

                        glColor3f(1, 0.5, 0.5);
                        int level = 0;
                        walkFrontToBack(m_root, frustum, start, level);
                        s_maxWalkLevel = level + 1;
                }

private:
        // private member data -------------------------------------------------
        int                     m_nEntries;
        int                     m_nMPN; // max per node
        int                     m_maxDisplay;
        smart_ptr<kdtree::Node> m_root;
        glut::Viewer            m_viewer;
};



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

int
main
(
IN int argc,
IN const char * argv[]
)
{
        DPRINTF("Usage: glut-demo-kd-tree [nEntries [maxPerNode]]");
        int nEntries = 1000;
        int nMPN = 16;

        if (argc > 1) {
                nEntries = atoi(argv[1]);
        }
        if (argc > 2) {
                nMPN = atoi(argv[2]);
        }
        DPRINTF("Using nEntries=%d, maxPerNode=%d", nEntries, nMPN);

        try {
                // title
                char title[128];
                sprintf(title, "kd-tree viewer (%d entries)", nEntries);

                // main loop
                smart_ptr<glut::DemoHost> host = new Drawer(nEntries, nMPN);
                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;
}