kd-tree.cpp

Go to the documentation of this file.
00001 /*
00002  * kd-tree.cpp
00003  *
00004  * Copyright (C) 2010  Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  * Program to test the glut-demo and kd-tree libraries.
00008  */
00009 
00010 // includes --------------------------------------------------------------------
00011 #include <iostream>
00012 #include <fstream>
00013 
00014 #include "glut/frustum.h"
00015 #include "glut-demo/glut-demo.h"
00016 #include "kdtree/kdtree.h"
00017 #include "nstream/nstream.h"
00018 #include "perf/perf.h"
00019 #include "util/file.h"
00020 
00021 
00022 
00023 static const float s_max                = 250.0;
00024 
00025 static int s_displayLevel               = 0;    // root
00026 
00027 static int s_displayWalk                = 0;    // farthest
00028 static int s_maxWalkLevel               = 10;   // starting guess
00029 
00030 static float s_angle                    = 0.0;  // y-rotation angle of viewer
00031 static const float s_degreesPerRadian   = 180.0 / M_PI;
00032 static const float s_deltaA             = 5.0 / s_degreesPerRadian;
00033 
00034 static float s_zAngle                   = 0.0;  // z-rotation of viewer
00035 static const float s_maxZAngle          = 0.5 * M_PI;
00036 
00037 
00038 ////////////////////////////////////////////////////////////////////////////////
00039 //
00040 //      static helper methods
00041 //
00042 ////////////////////////////////////////////////////////////////////////////////
00043 
00044 class LevelDisplay : public glut::DisplayLine {
00045 public:
00046         ~LevelDisplay(void) throw() { }
00047 
00048         ePosition getPosition(void) throw() { return glut::DisplayLine::eBottomLeft; }
00049         const char * getText(void) throw() {
00050                         sprintf(m_buffer, "level (d/D)isplay: %d", s_displayLevel);
00051                         return m_buffer;
00052                 }
00053 
00054 private:
00055         char            m_buffer[256];
00056 };
00057 
00058 
00059 
00060 class WalkDisplay : public glut::DisplayLine {
00061 public:
00062         ~WalkDisplay(void) throw() { }
00063 
00064         ePosition getPosition(void) throw() { return glut::DisplayLine::eBottomLeft; }
00065         const char * getText(void) throw() {
00066                         sprintf(m_buffer, "wal(k/K) level: %d", s_displayWalk);
00067                         return m_buffer;
00068                 }
00069 
00070 private:
00071         char            m_buffer[256];
00072 };
00073 
00074 
00075 
00076 class ViewAngle : public glut::DisplayLine {
00077 public:
00078         ~ViewAngle(void) throw() { }
00079 
00080         ePosition getPosition(void) throw() { return glut::DisplayLine::eBottomLeft; }
00081         const char * getText(void) throw() {
00082                         sprintf(m_buffer, "(v)iew angle: %d degrees",
00083                             (int) (s_angle * s_degreesPerRadian));
00084                         return m_buffer;
00085                 }
00086 
00087 private:
00088         char            m_buffer[256];
00089 };
00090 
00091 
00092 static float
00093 getRandom
00094 (
00095 IN float M
00096 )
00097 throw()
00098 {
00099         return (M * rand()) / RAND_MAX;
00100 }
00101 
00102 
00103 
00104 static float
00105 getRandom2
00106 (
00107 IN float M
00108 )
00109 throw()
00110 {
00111         float x = (1.0 * rand()) / RAND_MAX;
00112         //return x * x * x * M;
00113         return x * x * M;
00114 }
00115 
00116 
00117 static void
00118 getRandomRect
00119 (
00120 IN const rect3d_t& base,
00121 IN float size,
00122 OUT rect3d_t& r
00123 )
00124 throw()
00125 {
00126         r.x0 = base.x0 + getRandom(base.x1 - base.x0 - size);
00127         r.y0 = base.y0 + getRandom2(base.y1 - base.y0 - size);
00128         r.z0 = base.z0 + getRandom(base.z1 - base.z0 - size);
00129 
00130         r.x1 = r.x0 + size;
00131         r.y1 = r.y0 + size;
00132         r.z1 = r.z0 + size;
00133 }
00134 
00135 
00136 
00137 static void
00138 drawRect
00139 (
00140 IN const rect3d_t& r
00141 )
00142 throw()
00143 {
00144         glBegin(GL_LINES);
00145         for (int i = 0; i < 12; ++i) {
00146                 point3d_t p0, p1;
00147                 r.getEdge(i, p0, p1);
00148                 glVertex3fv((GLfloat *) &p0);
00149                 glVertex3fv((GLfloat *) &p1);
00150         }
00151         glEnd();
00152 }
00153 
00154 
00155 
00156 static void
00157 displayNode
00158 (
00159 IN const kdtree::Node * node,
00160 IN int level
00161 )
00162 throw()
00163 {
00164         ASSERT(node, "null");
00165         ASSERT(level >= 0, "bad level: %d", level);
00166 
00167         if (level == s_displayLevel) {
00168                 glColor3f(0, 0, 1);
00169                 rect3d_t r = node->getRect();
00170                 r.inflate(-1);  // just to separate neighbors a bit
00171                 drawRect(r);
00172         }
00173 
00174         const kdtree::Node * left = node->getLeftChild();
00175         const kdtree::Node * right = node->getRightChild();
00176 
00177         const kdtree::Node::vec_entries_t& vec = node->getStaticEntries();
00178         for (kdtree::Node::vec_entries_t::const_iterator i = vec.begin();
00179              i != vec.end(); ++i) {
00180                 const kdtree::Node::entry_rec_t& er = *i;
00181 
00182                 glColor3f(1, 0, 1);
00183                 drawRect(er.rect);
00184         }
00185 
00186         if (left) {
00187                 displayNode(left, level + 1);
00188         }
00189         if (right) {
00190                 displayNode(right, level + 1);
00191         }
00192 }
00193 
00194 
00195 
00196 static void
00197 walkFrontToBack
00198 (
00199 IN const kdtree::Node * node,
00200 IN const frustum_t& frustum,
00201 IN const point3d_t& start,
00202 IO int& level
00203 )
00204 throw()
00205 {
00206         ASSERT(node, "null");
00207         ASSERT(level >= 0, "Bad level: %d", level);
00208 
00209         const kdtree::plane_t& plane = node->getSortPlane();
00210         kdtree::eSort sort = kdtree::sortPoint(plane, start);
00211 
00212         const kdtree::Node * left = node->getLeftChild();
00213         const kdtree::Node * right = node->getRightChild();
00214 
00215         const kdtree::Node * farthest = left;
00216         const kdtree::Node * closest = right;
00217         if (kdtree::eSort_Left == sort) {
00218                 farthest = right;
00219                 closest = left;
00220         }
00221 
00222         // first visit closest
00223         if (closest) {
00224                 walkFrontToBack(closest, frustum, start, level);
00225         }
00226 
00227         // visit ourselves -- only if we are a leaf!
00228         rect3d_t r = node->getRect();
00229         if (!left && !right &&
00230             (eContains_HitMask & frustum.containsRect(r))) {
00231                 float dr = 1.0 / (1.25 * s_maxWalkLevel);
00232                 float red = 1.0 - dr * level;
00233                 if (red < 0.1) {
00234                         red = 0.1;
00235                 }
00236                 glColor3f(red, 0,  0);
00237                 ++level;
00238                 if (!s_displayWalk || s_displayWalk == level) {
00239                         r.inflate(-2);
00240                         drawRect(r);
00241                 }
00242         }
00243 
00244         // visit furthest last
00245         if (farthest) {
00246                 walkFrontToBack(farthest, frustum, start, level);
00247         }
00248 }
00249 
00250 
00251 
00252 class Drawer : public glut::DemoHost {
00253 public:
00254         Drawer(IN int nEntries, IN int nMPN) throw()
00255                 { m_nEntries = nEntries; m_nMPN = nMPN; }
00256         ~Drawer(void) throw() { }
00257 
00258         // glut::Host class interface methods ----------------------------------
00259         float getDelta(void) { return 5; }
00260 
00261         void getDisplayLines(OUT glut::vec_display_lines_t& lines) {
00262                         lines.clear();
00263 
00264                         // add our display level widget
00265                         smart_ptr<LevelDisplay> ld = new LevelDisplay;
00266                         ASSERT(ld, "out of memory");
00267                         lines.push_back(ld);
00268 
00269                         // add walk level widget
00270                         smart_ptr<WalkDisplay> wd = new WalkDisplay;
00271                         ASSERT(wd, "out of memory");
00272                         lines.push_back(wd);
00273 
00274                         // add view angle widget
00275                         smart_ptr<ViewAngle> va = new ViewAngle;
00276                         ASSERT(va, "out of memory");
00277                         lines.push_back(va);
00278                 }
00279 
00280         void onInit(void) {
00281                         perf::Timer timer("set up kd-tree");
00282                         ASSERT_THROW(m_nEntries > 0, "Bad entry count: "
00283                             << m_nEntries);
00284 
00285                         rect3d_t bounds;
00286                         bounds.clear();
00287                         bounds.inflate(s_max);
00288                         bounds.dump("kd-tree bounds");
00289 
00290                         m_root = kdtree::Node::create(bounds);
00291                         ASSERT(m_root, "failed to create kdtree root node");
00292 
00293                         for (int i = 0; i < m_nEntries; ++i) {
00294                                 rect3d_t r;
00295                                 getRandomRect(bounds, getRandom(10), r);
00296                                 smart_ptr<kdtree::Entry> e;
00297                                 m_root->addStaticEntry(e, r);
00298                         }
00299 
00300                         {
00301                                 perf::Timer timer("subdivide kd-tree");
00302                                 m_root->subdivide(kdtree::eStrategy_Balance, m_nMPN);
00303                         }
00304 
00305                         m_maxDisplay = m_root->getTreeDepth() + 1;
00306                 }
00307 
00308         void onKey(IN int key, IN int mods) {
00309                         switch (key) {
00310                         case 'Z':
00311                                 s_zAngle -= s_deltaA;
00312                                 if (s_zAngle < -s_maxZAngle) {
00313                                         s_zAngle = -s_maxZAngle;
00314                                 }
00315                                 break;
00316 
00317                         case 'z':
00318                                 s_zAngle += s_deltaA;
00319                                 if (s_zAngle > s_maxZAngle) {
00320                                         s_zAngle = s_maxZAngle;
00321                                 }
00322                                 break;
00323 
00324                         case 'V':
00325                                 s_angle -= s_deltaA;
00326                                 if (s_angle < -M_PI) {
00327                                         s_angle += 2.0 * M_PI;
00328                                 }
00329                                 break;
00330 
00331                         case 'v':
00332                                 s_angle += s_deltaA;
00333                                 if (s_angle > M_PI) {
00334                                         s_angle -= 2.0 * M_PI;
00335                                 }
00336                                 break;
00337 
00338                         case 'K':
00339                                 s_displayWalk--;
00340                                 if (s_displayWalk < 0) {
00341                                         s_displayWalk = 0;
00342                                 }
00343                                 break;
00344 
00345                         case 'k':
00346                                 ++s_displayWalk;
00347                                 if (s_displayWalk > s_maxWalkLevel) {
00348                                         s_displayWalk = s_maxWalkLevel;
00349                                 }
00350                                 break;
00351 
00352                         case 'D':
00353                                 s_displayLevel--;
00354                                 if (s_displayLevel < 0) {
00355                                         s_displayLevel = m_maxDisplay - 1;
00356                                 }
00357                                 break;
00358                                 
00359                         case 'd':
00360                                 s_displayLevel++;
00361                                 break;
00362                         }
00363                         s_displayLevel = s_displayLevel % m_maxDisplay;
00364                 }
00365 
00366         void display3D(IN const glut::render_context_t& rc,
00367                                 IN glut::RenderQueue * rq) {
00368                         ASSERT(rq, "null");
00369                         glDisable(GL_LIGHTING);
00370                         displayNode(m_root, 0);
00371 
00372                         // set up another camera, viewer, frustum for demo
00373                         glut::camera_t camera;
00374                         float zFar = 300.0;     // shorter zfar for demo
00375                         camera.setZFar(zFar);
00376                         m_viewer.setYRotation(s_angle);
00377                         m_viewer.setUpRotation(s_zAngle);
00378 
00379                         point3d_t start = m_viewer.getPosition();
00380                         point3d_t end = start + zFar * m_viewer.getFacing();
00381 
00382                         glColor3f(1, 1, 0);
00383                         glBegin(GL_LINES);
00384                                 glVertex3fv((GLfloat *) &start);
00385                                 glVertex3fv((GLfloat *) &end);
00386                         glEnd();
00387 
00388                         // display example frustum
00389                         frustum_t frustum;
00390                         glut::getViewFrustum(camera, m_viewer, frustum);
00391                         glColor3f(1, 1, 1);
00392                         glBegin(GL_LINES);
00393                         for (int i = 0; i < 12; ++i) {
00394                                 point3d_t p0, p1;
00395                                 frustum.getEdge(i, p0, p1);
00396                                 glVertex3fv((GLfloat *) &p0);
00397                                 glVertex3fv((GLfloat *) &p1);
00398                         }
00399                         glEnd();
00400 
00401                         glColor3f(1, 0.5, 0.5);
00402                         int level = 0;
00403                         walkFrontToBack(m_root, frustum, start, level);
00404                         s_maxWalkLevel = level + 1;
00405                 }
00406 
00407 private:
00408         // private member data -------------------------------------------------
00409         int                     m_nEntries;
00410         int                     m_nMPN; // max per node
00411         int                     m_maxDisplay;
00412         smart_ptr<kdtree::Node> m_root;
00413         glut::Viewer            m_viewer;
00414 };
00415 
00416 
00417 
00418 ////////////////////////////////////////////////////////////////////////////////
00419 //
00420 //      entry point
00421 //
00422 ////////////////////////////////////////////////////////////////////////////////
00423 
00424 int
00425 main
00426 (
00427 IN int argc,
00428 IN const char * argv[]
00429 )
00430 {
00431         DPRINTF("Usage: glut-demo-kd-tree [nEntries [maxPerNode]]");
00432         int nEntries = 1000;
00433         int nMPN = 16;
00434 
00435         if (argc > 1) {
00436                 nEntries = atoi(argv[1]);
00437         }
00438         if (argc > 2) {
00439                 nMPN = atoi(argv[2]);
00440         }
00441         DPRINTF("Using nEntries=%d, maxPerNode=%d", nEntries, nMPN);
00442 
00443         try {
00444                 // title
00445                 char title[128];
00446                 sprintf(title, "kd-tree viewer (%d entries)", nEntries);
00447 
00448                 // main loop
00449                 smart_ptr<glut::DemoHost> host = new Drawer(nEntries, nMPN);
00450                 ASSERT(host, "out of memory");
00451                 glut::startDemo(argc, argv, title, host);
00452 
00453         } catch (std::exception& e) {
00454                 DPRINTF("Exception: %s", e.what());
00455         }
00456 
00457         // only reach here on error
00458         return -1;
00459 }
00460