partition.cpp

Go to the documentation of this file.
00001 /*
00002  * partition.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  * The kd-tree demo gives a visual representation of the tree, and how it
00009  * interacts with the view frustum.  This demo (partition.cpp) uses a kd-tree
00010  * internally to partition a large 3D space and perform front-to-back drawing.
00011  */
00012 
00013 // includes --------------------------------------------------------------------
00014 #include <iostream>
00015 #include <fstream>
00016 
00017 #include "glut/frustum.h"
00018 #include "glut-demo/glut-demo.h"
00019 #include "glut-model/glut-model.h"
00020 #include "kdtree/kdtree.h"
00021 #include "nstream/nstream.h"
00022 #include "perf/perf.h"
00023 #include "util/file.h"
00024 
00025 
00026 
00027 static int s_drawCount                  = 0;    // number of objects drawn/frame
00028 static float s_max                      = -1;
00029 
00030 
00031 ////////////////////////////////////////////////////////////////////////////////
00032 //
00033 //      static helper methods
00034 //
00035 ////////////////////////////////////////////////////////////////////////////////
00036 
00037 class CountDisplay : public glut::DisplayLine {
00038 public:
00039         // virtual destructor --------------------------------------------------
00040         ~CountDisplay(void) throw() { }
00041 
00042         // glut::DisplayLine class interface methods ---------------------------
00043         ePosition getPosition(void) throw() { return eBottomLeft; }
00044 
00045         const char * getText(void) throw() {
00046                         sprintf(m_buffer, "%d objects drawn", s_drawCount);
00047                         return m_buffer;
00048                 }
00049 
00050 private:
00051         // private member data -------------------------------------------------
00052         char            m_buffer[256];
00053 };
00054 
00055 
00056 
00057 static float
00058 getRandom
00059 (
00060 IN float M
00061 )
00062 throw()
00063 {
00064         return (M * rand()) / RAND_MAX;
00065 }
00066 
00067 
00068 
00069 static float
00070 getRandom2
00071 (
00072 IN float M
00073 )
00074 throw()
00075 {
00076         float x = (1.0 * rand()) / RAND_MAX;
00077         //return x * x * x * M;
00078         return x * x * M;
00079 }
00080 
00081 
00082 static point3d_t
00083 getRandomPosition
00084 (
00085 IN const rect3d_t& base
00086 )
00087 throw()
00088 {
00089         point3d_t p;
00090 
00091         float buffer = 0.02 * s_max;
00092 
00093         p.x = base.x0 + buffer + getRandom(base.x1 - base.x0 - 2.0 * buffer);
00094         p.y = base.y0 + buffer + getRandom2(base.y1 - base.y0 - 2.0 * buffer);
00095         p.z = base.z0 + buffer + getRandom(base.z1 - base.z0 - 2.0 * buffer);
00096 
00097         return p;
00098 }
00099 
00100 
00101 
00102 static void
00103 drawRect
00104 (
00105 IN const rect3d_t& r
00106 )
00107 throw()
00108 {
00109         glBegin(GL_LINES);
00110         for (int i = 0; i < 12; ++i) {
00111                 point3d_t p0, p1;
00112                 r.getEdge(i, p0, p1);
00113                 glVertex3fv((GLfloat *) &p0);
00114                 glVertex3fv((GLfloat *) &p1);
00115         }
00116         glEnd();
00117 }
00118 
00119 
00120 
00121 static void
00122 walkFrontToBack
00123 (
00124 IN const kdtree::Node * node,
00125 IN const glut::render_context_t& rc,
00126 IN glut::RenderQueue * rq,
00127 IN const frustum_t& frustum,
00128 IN glut::Renderable * model
00129 )
00130 throw()
00131 {
00132         ASSERT(node, "null");
00133         ASSERT(rq, "null");
00134         ASSERT(model, "null");
00135 
00136         const point3d_t& start = rc.viewer.getPosition();
00137 
00138         const kdtree::plane_t& plane = node->getSortPlane();
00139         kdtree::eSort sort = kdtree::sortPoint(plane, start);
00140 
00141         const kdtree::Node * left = node->getLeftChild();
00142         const kdtree::Node * right = node->getRightChild();
00143 
00144         const kdtree::Node * farthest = left;
00145         const kdtree::Node * closest = right;
00146         if (kdtree::eSort_Left == sort) {
00147                 farthest = right;
00148                 closest = left;
00149         }
00150 
00151         // first visit closest
00152         if (closest) {
00153                 // only visit if in frustum
00154                 const rect3d_t& r = closest->getRect();
00155                 if (eContains_HitMask & frustum.containsRect(r)) {
00156                         walkFrontToBack(closest, rc, rq, frustum, model);
00157                 }
00158         }
00159 
00160         // visit ourselves
00161         const kdtree::Node::vec_entries_t& entries = node->getStaticEntries();
00162         for (kdtree::Node::vec_entries_t::const_iterator i = entries.begin();
00163              i != entries.end(); ++i) {
00164                 const kdtree::Node::entry_rec_t& er = *i;
00165 
00166                 // only draw if in frustum
00167                 if (!(eContains_HitMask & frustum.containsRect(er.rect)))
00168                         continue;       // skip this one
00169 
00170                 point3d_t p = er.rect.getMidpoint();
00171 
00172                 ++s_drawCount;
00173 
00174                 glMatrixMode(GL_MODELVIEW);
00175                 glPushMatrix();
00176                 glTranslatef(p.x, p.y, p.z);
00177                 model->render(rc, rq);
00178                 glPopMatrix();
00179         }
00180 
00181         // visit furthest last
00182         if (farthest) {
00183                 // only visit if in frustum
00184                 const rect3d_t& r = farthest->getRect();
00185                 if (eContains_HitMask & frustum.containsRect(r)) {
00186                         walkFrontToBack(farthest, rc, rq, frustum, model);
00187                 }
00188         }
00189 }
00190 
00191 
00192 
00193 class Drawer : public glut::DemoHost {
00194 public:
00195         Drawer(IN int nObjects, IN const char * filename) throw() {
00196                         ASSERT(nObjects > 0, "Bad object count: %d", nObjects);
00197                         ASSERT(filename, "null");
00198                         m_nObjects = nObjects;
00199                         m_filename = filename;
00200                         m_scale = 1;
00201                 }
00202 
00203         ~Drawer(void) throw() { }
00204 
00205         // glut::Host class interface methods ----------------------------------
00206         float getDelta(void) { return 0.25 * m_scale; }
00207 
00208         void getDisplayLines(IN glut::vec_display_lines_t& lines) {
00209                         lines.clear();
00210 
00211                         // add object count
00212                         smart_ptr<glut::DisplayLine> count = new CountDisplay;
00213                         ASSERT(count, "out of memory");
00214                         lines.push_back(count);
00215                 }
00216 
00217         void onInit(void) {
00218                         std::string parent;
00219                         GetParentDirectory(m_filename.c_str(), parent);
00220                         DPRINTF("Using material directory: %s", parent.c_str());
00221                         m_registry = glut::getSimpleRegistry(parent.c_str());
00222                         ASSERT(m_registry, "failed to create simple registry");
00223 
00224                         {
00225                                 perf::Timer timer("load wgm object");
00226                                 m_model = glut::loadModel(m_filename.c_str(),
00227                                     m_registry);
00228                                 ASSERT(m_model, "null");
00229                         }
00230                         rect3d_t modelRect = m_model->getBoundingBox();
00231                         modelRect.dump("Model bounding box");
00232                         m_scale = modelRect.getDiagonal();
00233                         s_max = 20.0 * m_scale;
00234 
00235                         perf::Timer timer("set up kd-tree");
00236                         ASSERT_THROW(m_nObjects > 0, "Bad object count: "
00237                             << m_nObjects);
00238 
00239                         rect3d_t bounds = modelRect;
00240                         bounds.inflate(s_max);
00241                         bounds.dump("kd-tree bounds");
00242 
00243                         m_root = kdtree::Node::create(bounds);
00244                         ASSERT(m_root, "failed to create kdtree root node");
00245 
00246                         for (int i = 0; i < m_nObjects; ++i) {
00247                                 point3d_t p = getRandomPosition(bounds);
00248                                 rect3d_t r = modelRect;
00249                                 r.translate(p);
00250                                 smart_ptr<kdtree::Entry> e;
00251                                 m_root->addStaticEntry(e, r);
00252                         }
00253 
00254                         int nMaxPerNode = 8;
00255                         {
00256                                 perf::Timer timer("subdivide kd-tree");
00257                                 m_root->subdivide(kdtree::eStrategy_Balance,
00258                                     nMaxPerNode);
00259                         }
00260                 }
00261 
00262         void display3D(IN const glut::render_context_t& rc,
00263                                 IN glut::RenderQueue * rq) {
00264                         ASSERT(rq, "null");
00265                         frustum_t f;
00266                         glut::getViewFrustum(rc.camera, rc.viewer, f);
00267 //                      f.dump("frustum");
00268 
00269                         s_drawCount = 0;
00270                         walkFrontToBack(m_root, rc, rq, f, m_model);
00271 
00272                         // draw frustum lines--ideally we won't see these!
00273                         glut::drawFrustumEdges(f, glut_color_t(0.2, 1.0, 0.2));
00274                 }
00275 
00276 private:
00277         // private member data -------------------------------------------------
00278         int                             m_nObjects;
00279         float                           m_scale;
00280         std::string                     m_filename;
00281         smart_ptr<kdtree::Node>         m_root;
00282         smart_ptr<glut::MaterialRegistry> m_registry;
00283         smart_ptr<glut::Renderable>     m_model;
00284 };
00285 
00286 
00287 
00288 ////////////////////////////////////////////////////////////////////////////////
00289 //
00290 //      entry point
00291 //
00292 ////////////////////////////////////////////////////////////////////////////////
00293 
00294 int
00295 main
00296 (
00297 IN int argc,
00298 IN const char * argv[]
00299 )
00300 {
00301         ASSERT(3 == argc,
00302             "Usage: glut-demo-partition nObjects wgmPath");
00303         int nObjects = atoi(argv[1]);
00304         const char * wgmPath = argv[2];
00305         DPRINTF("Using nObjects=%d, wgmPath=%s", nObjects, wgmPath);
00306 
00307         try {
00308                 // title
00309                 const int bufSize = 1023;
00310                 char title[bufSize + 1];
00311                 snprintf(title, bufSize, "3D partitioned space (%d x %s)",
00312                     nObjects, GetFilename(wgmPath));
00313                 title[bufSize] = 0;     // ensure null termination
00314 
00315                 // main loop
00316                 smart_ptr<glut::DemoHost> host = new Drawer(nObjects, wgmPath);
00317                 ASSERT(host, "out of memory");
00318                 glut::startDemo(argc, argv, title, host);
00319 
00320         } catch (std::exception& e) {
00321                 DPRINTF("Exception: %s", e.what());
00322         }
00323 
00324         // only reach here on error
00325         return -1;
00326 }
00327