map-kdtree.cpp

Go to the documentation of this file.
00001 /*
00002  * map-kdtree.cpp
00003  *
00004  * Copyright (C) 2010  Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions are met:
00010  *     * Redistributions of source code must retain the above copyright
00011  *       notice, this list of conditions and the following disclaimer.
00012  *     * Redistributions in binary form must reproduce the above copyright
00013  *       notice, this list of conditions and the following disclaimer in the
00014  *       documentation and/or other materials provided with the distribution.
00015  *     * Neither the name of the <organization> nor the
00016  *       names of its contributors may be used to endorse or promote products
00017  *       derived from this software without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
00020  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00021  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00022  * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
00023  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00024  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00025  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00026  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  *
00031  */
00032 
00033 // includes --------------------------------------------------------------------
00034 #include "map-kdtree.h"                 // always include our own header first!
00035 
00036 #include "glut/frustum.h"
00037 #include "glut/renderable.h"
00038 #include "model-loader/model-loader.h"
00039 #include "perf/perf.h"
00040 #include "util/free_list.h"
00041 
00042 
00043 namespace aesop {
00044 
00045 
00046 // interface destructor implementation
00047 MapKdTree::~MapKdTree(void) throw() { }
00048 
00049 
00050 typedef free_list_t<kdtree::Node::dynamic_entry_t> free_type_t;
00051 
00052 static const int s_maxFreeListSize = 256;
00053 
00054 
00055 struct node_data_t {
00056         // constructor, manipulators
00057         node_data_t(void) throw() { this->clear(); }
00058         void clear(void) throw() {
00059                         leafzone = NULL;
00060                 }
00061 
00062         // data fields
00063         LeafZone *              leafzone;
00064 };
00065 
00066 
00067 
00068 class KdTree;           // forward declaration
00069 
00070 struct add_static_context_t {
00071         // data fields
00072         KdTree *                pThis;
00073         LeafZone *              leafzone;
00074 };
00075 
00076 
00077 
00078 struct add_virtual_context_t {
00079         // data fields
00080         kdtree::Node *          node;
00081         LeafZone *              leafzone;
00082 };
00083 
00084 
00085 
00086 struct add_dynamic_context_t {
00087         add_dynamic_context_t(void) throw() { this->clear(); }
00088         void clear(void) throw() {
00089                         root = NULL;
00090                         viewerZone = NULL;
00091                         rootZone = NULL;
00092                         frustum.clear();
00093                         freeList = NULL;
00094                 }
00095 
00096         // data fields
00097         kdtree::Node *          root;
00098         LeafZone *              viewerZone;
00099         Zone *                  rootZone;
00100         frustum_t               frustum;
00101         free_type_t *           freeList;
00102 };
00103 
00104 
00105 
00106 struct entry_t : public kdtree::Entry {
00107         // data fields
00108         smart_ptr<glut::Renderable>     model;
00109         placement_t                     placement;
00110         LeafZone *                      leafzone;
00111 };
00112 
00113 
00114 
00115 // used for sorting entries within a node
00116 struct sort_entry_t {
00117         smart_ptr<entry_t>      entry;
00118         float                   d2;  // distance^2 from viewer to object
00119 };
00120 
00121 
00122 ////////////////////////////////////////////////////////////////////////////////
00123 //
00124 //      static helper methods
00125 //
00126 ////////////////////////////////////////////////////////////////////////////////
00127 
00128 static void
00129 determineZone
00130 (
00131 IN kdtree::Node * node,
00132 IN Zone * root
00133 )
00134 {
00135         ASSERT(node, "null");
00136         ASSERT(root, "null");
00137 
00138         smart_ptr<node_data_t> nd = new node_data_t;
00139         ASSERT(nd, "out of memory");
00140 
00141         const rect3d_t& nodeRect = node->getRect();
00142         LeafZone * lz = root->getLeafZone(nodeRect.getMidpoint());
00143         if (!lz) {
00144                 // DPRINTF("WARNING: node midpoint is not contained!");
00145         } else {
00146                 // found a leaf zone.  Does it fully contain this kdtree node?
00147                 rect3d_t zoneRect;
00148                 lz->getBoundingRect(zoneRect);
00149                 if (zoneRect.containsRect(nodeRect)) {
00150                         // yes, leaf zone fully contains kdtree node!
00151                         //DPRINTF("Node is fully in zone %p", lz);
00152                         nd->leafzone = lz;
00153                 }
00154         }
00155 
00156         // hand over the data
00157         node->setUserPointer(nd.disown());
00158 
00159         // recurse
00160         kdtree::Node * left = node->getLeftChild();
00161         kdtree::Node * right = node->getRightChild();
00162 
00163         if (left) {
00164                 determineZone(left, root);
00165         }
00166         if (right) {
00167                 determineZone(right, root);
00168         }
00169 }
00170 
00171 
00172 
00173 static void
00174 deletePointers
00175 (
00176 IN kdtree::Node * node
00177 )
00178 throw()
00179 {
00180         ASSERT(node, "null");
00181 
00182         void * user = node->getUserPointer();
00183         if (user) {
00184                 node->setUserPointer(NULL);
00185                 node_data_t * nd = (node_data_t *) user;
00186                 delete nd;
00187         }
00188 
00189         kdtree::Node * left = node->getLeftChild();
00190         kdtree::Node * right = node->getRightChild();
00191         if (left)
00192                 deletePointers(left);
00193         if (right)
00194                 deletePointers(right);
00195 }
00196 
00197 
00198 
00199 static void
00200 deleteAllEntries
00201 (
00202 IN kdtree::Node * node
00203 )
00204 throw()
00205 {
00206         ASSERT(node, "null");
00207 
00208         // delete entries one at a time
00209         while (true) {
00210                 kdtree::Node::vec_entries_t& vec = node->getStaticEntries();
00211                 int nEntries = vec.size();
00212                 if (nEntries < 1)
00213                         break;  // empty!
00214 
00215                 // not empty!  remove last element
00216                 kdtree::Entry * entry = vec[nEntries - 1].entry;
00217                 ASSERT(entry, "null entry in list?");
00218                 node->removeStaticEntry(entry);
00219         }
00220 
00221         // recurse
00222         kdtree::Node * left = node->getLeftChild();
00223         kdtree::Node * right = node->getRightChild();
00224         if (left)
00225                 deleteAllEntries(left);
00226         if (right)
00227                 deleteAllEntries(right);
00228 }
00229 
00230 
00231 
00232 static void
00233 walkTree
00234 (
00235 IN kdtree::Node * node,
00236 IN int depth,
00237 IN kdtree_callback_fn callback,
00238 IN void * context
00239 )
00240 {
00241         ASSERT(node, "null");
00242         ASSERT(depth >= 0, "bad depth: %d", depth);
00243         ASSERT(callback, "null");
00244         // ASSERT(context) -- we don't care
00245 
00246         kd_node_t kn;
00247         kn.rect = node->getRect();
00248         kn.depth = depth;
00249         callback(kn, context);
00250 
00251         // recurse
00252         kdtree::Node * left = node->getLeftChild();
00253         kdtree::Node * right = node->getRightChild();
00254         if (left)
00255                 walkTree(left, depth + 1, callback, context);
00256         if (right)
00257                 walkTree(right, depth + 1, callback, context);
00258 }
00259 
00260 
00261 
00262 static int
00263 compareEntries
00264 (
00265 IN const void * p1,
00266 IN const void * p2
00267 )
00268 throw()
00269 {
00270         const sort_entry_t * se1 = (const sort_entry_t *) p1;
00271         const sort_entry_t * se2 = (const sort_entry_t *) p2;
00272         ASSERT(se1 && se2, "null");
00273 
00274         if (se1->d2 < se2->d2) {
00275                 return -1;      // distance is less therefore closer
00276         } else if (se1->d2 > se2->d2) {
00277                 return +1;
00278         }
00279 
00280         // got here?  must be equal...
00281         return 0;
00282 }
00283 
00284 
00285 
00286 static void
00287 walkFrontToBack
00288 (
00289 IN kdtree::Node * node,
00290 IN free_type_t& freeList,
00291 IN const glut::render_context_t& rc,
00292 IN glut::RenderQueue * rq,
00293 IN const frustum_t * f,
00294 IN LeafZone * viewerZone,
00295 IN kdtree_object_fn callback,
00296 IN void * context
00297 )
00298 {
00299         ASSERT(node, "null");
00300         ASSERT(rq, "null");
00301         // ASSERT(f) -- can be null! (no frustum check required)
00302         // ASSERT(viewerZone) -- can be null! (no zone check required)
00303         ASSERT(callback, "null");
00304         // ASSERT(context) -- we don't care
00305 
00306         // need to verify visibility?
00307         if (viewerZone) {
00308                 const node_data_t * nd = (const node_data_t *) node->getUserPointer();
00309                 ASSERT(nd, "map kd node with no user pointer?");
00310 
00311                 // can verify if this node is itself full contained
00312                 if (nd->leafzone) {
00313                         // yes, now verify
00314                         if (viewerZone->isLeafVisible(nd->leafzone)) {
00315                                 // yes, verified visible!
00316                                 // for this node and recursion, no checking
00317                                 // needed
00318                                 viewerZone = NULL;
00319                         } else {
00320                                 // this node, and all children, are not visible!
00321                                 return;
00322                         }
00323                 }
00324         }
00325 
00326         // need to verify frustum?
00327         if (f) {
00328                 const rect3d_t& r = node->getRect();
00329                 switch (f->containsRect(r)) {
00330                 case eContains_None:
00331                         return;         // this and all children aren't visible!
00332 
00333                 case eContains_Fully:
00334                         f = NULL;       // this and all children are in frustum
00335                         break;
00336 
00337                 default:
00338                         // have to keep checking as we recurse, no change
00339                         break;
00340                 }
00341         }
00342 
00343         // okay, we are visible.  walk front to back in this node
00344         const point3d_t& start = rc.viewer.getPosition();
00345 
00346         const kdtree::plane_t& plane = node->getSortPlane();
00347         kdtree::eSort sort = kdtree::sortPoint(plane, start);
00348 
00349         kdtree::Node * left = node->getLeftChild();
00350         kdtree::Node * right = node->getRightChild();
00351 
00352         kdtree::Node * closest = left;
00353         kdtree::Node * farthest = right;
00354         if (kdtree::eSort_Right == sort) {
00355                 closest = right;
00356                 farthest = left;
00357         }
00358 
00359         // first visit closest
00360         if (closest) {
00361                 walkFrontToBack(closest, freeList, rc, rq, f, viewerZone, callback, context);
00362         }
00363 
00364         // construct a quick array on the stack for sorting
00365         const int nMaxEntries = 256;
00366         sort_entry_t sortArray[nMaxEntries];
00367         int nEntries = 0;       // count of visible entries (== array size)
00368 
00369         // visit ourselves
00370         const kdtree::Node::vec_entries_t& vec = node->getStaticEntries();
00371 
00372         // populate with pointers
00373         for (kdtree::Node::vec_entries_t::const_iterator i = vec.begin();
00374              i != vec.end(); ++i) {
00375                 const kdtree::Node::entry_rec_t& er = *i;
00376 
00377                 smart_ptr<entry_t> entry = er.entry;
00378                 ASSERT(entry, "failed to upcast");
00379 
00380                 // visible?
00381                 if (viewerZone &&
00382                     !viewerZone->isLeafVisible(entry->leafzone))
00383                         continue;       // skip this one--not visible
00384 
00385                 // okay, create entry
00386                 sort_entry_t se;
00387                 se.entry = entry;
00388 
00389                 // distance from viewer to object?
00390                 point3d_t diff = entry->placement.position - start;
00391                 se.d2 = dotProduct(diff, diff);
00392 
00393                 // add to array for sorting
00394                 sortArray[nEntries] = se;
00395                 ++nEntries;
00396                 if (nEntries > nMaxEntries) {
00397                         // we don't want to blow the stack.  Give up
00398                         DPRINTF("ERROR: too many entries (%d) in node!",
00399                             nEntries);
00400                         DPRINTF("  Giving up rendering remaining entries");
00401                         break;
00402                 }
00403         }
00404 
00405         // populate with dynamic objects
00406         while (smart_ptr<kdtree::Node::dynamic_entry_t> pde =
00407                node->popDynamicEntry()) {
00408                 // assume visible!
00409                 sort_entry_t se;
00410                 se.entry = pde->entry;
00411 
00412                 // distance from viewer to object?
00413                 point3d_t diff = se.entry->placement.position - start;
00414                 se.d2 = dotProduct(diff, diff);
00415 
00416                 // add to array for sorting
00417                 sortArray[nEntries] = se;
00418                 ++nEntries;
00419                 if (nEntries > nMaxEntries) {
00420                         DPRINTF("ERROR: too many entries (%d) in node!",
00421                             nEntries);
00422                         DPRINTF("  Giving up rendering remaining entries");
00423                         break;
00424                 }
00425 
00426                 // return this to free list (or nuke!)
00427                 freeList.returnElement(pde);
00428         }
00429 
00430         ASSERT(nEntries <= nMaxEntries, "should have at most nMaxEntries visible");
00431         if (nEntries > 32) {
00432                 // probably a sign that the space isn't well partitioned
00433                 DPRINTF("WARNING: many entries (%d) in node!", nEntries);
00434         }
00435 
00436         // sort by distance to plane
00437         qsort(sortArray, nEntries, sizeof(sort_entry_t), compareEntries);
00438 
00439         // now walk in sorted order
00440         for (int i = 0; i < nEntries; ++i) {
00441                 entry_t * entry = sortArray[i].entry;
00442                 ASSERT(entry, "null entry in sort array?");
00443 
00444                 // update render context with this object's placement
00445                 glut::render_context_t rc2 = rc;
00446                 rc2.placement = entry->placement;
00447 
00448                 // make callback
00449                 callback(entry->model, rc2, rq, context);
00450         }
00451 
00452         // finally visit farthest
00453         if (farthest) {
00454                 walkFrontToBack(farthest, freeList, rc, rq, f, viewerZone, callback, context);
00455         }
00456 }
00457 
00458 
00459 
00460 static void
00461 addInstanceToNode
00462 (
00463 IN smart_ptr<Instance>& instance,
00464 IN LeafZone * lz,
00465 IN kdtree::Node * node
00466 )
00467 {
00468         ASSERT(instance, "null");
00469         ASSERT(lz, "null");
00470         ASSERT(node, "null");
00471 
00472         // look up the 3D model for this instance
00473         smart_ptr<glut::Renderable> model = getModel(instance);
00474         if (!model) {
00475                 DPRINTF("No model for instance of type '%s'",
00476                     instance->getTypeId());
00477                 return;
00478         }
00479 
00480         rect3d_t r = model->getBoundingBox();
00481         r.translate(instance->getPlacement().position);
00482 
00483         //DPRINTF("Rect for instance of type '%s'", instance->getTypeId());
00484         //r.dump("  bounding rect");
00485 
00486         smart_ptr<entry_t> entry = new entry_t;
00487         entry->model = model;
00488         entry->placement = instance->getPlacement();
00489         entry->leafzone = lz;
00490 
00491         // downcast and add
00492         smart_ptr<kdtree::Entry> kEntry = entry;
00493         node->addStaticEntry(kEntry, r);
00494 }
00495 
00496 
00497 
00498 static void
00499 addDynamicObject
00500 (
00501 IN smart_ptr<Instance>& instance,
00502 IN smart_ptr<PhysicsObject>& obj,
00503 IN void * context
00504 )
00505 {
00506         ASSERT(instance, "null");
00507         ASSERT(obj, "null");
00508         add_dynamic_context_t * padc = (add_dynamic_context_t *) context;
00509         ASSERT(padc, "null");
00510         ASSERT(padc->root, "null");
00511         ASSERT(padc->rootZone, "null");
00512         // ASSERT(padc->viewerZone, "null"); can be null
00513         ASSERT(padc->freeList, "null");
00514 
00515         // is this a dynamic instance?
00516         if (PhysicsObject::eFlag_Static & obj->getFlags()) {
00517                 // static!
00518                 return;
00519         }
00520 
00521         // get leaf zone that contains instance
00522         const point3d_t pos = instance->getPlacement().position;
00523         LeafZone * lz = padc->rootZone->getLeafZone(pos);
00524         if (lz && padc->viewerZone &&
00525             !padc->viewerZone->isLeafVisible(lz)) {
00526                 // not visible from viewer zone!
00527                 return;
00528         }
00529 
00530         // look up the 3D model for this instance
00531         smart_ptr<glut::Renderable> model = getModel(instance);
00532         if (!model) {
00533                 DPRINTF("No model for instance of type '%s'",
00534                     instance->getTypeId());
00535                 return;
00536         }
00537         rect3d_t r = model->getBoundingBox();
00538         r.translate(pos);
00539         
00540         // okay, may be visible.  In frustum?
00541         if (eContains_None == padc->frustum.containsRect(r)) {
00542                 return;         // does not intersect view frustum
00543         }
00544 
00545         // okay, may be visible and is in frustum.  Add as dynamic entry to
00546         //   kdtree.
00547         smart_ptr<kdtree::Node::dynamic_entry_t> pde;
00548 
00549         // first, attempt to pull from free list
00550         pde = padc->freeList->getElement();
00551         if (!pde->entry) {
00552                 pde->entry = new entry_t;
00553                 ASSERT(pde->entry, "null");
00554         }
00555         ASSERT(!pde->next, "should be null");
00556 
00557         // update entry
00558         entry_t * entry = dynamic_cast<entry_t *>((kdtree::Entry *) pde->entry);
00559         ASSERT(entry, "failed to upcast");
00560         entry->model = model;
00561         entry->placement = instance->getPlacement();
00562         entry->leafzone = lz;   // may be null!
00563 
00564         // add to tree
00565         padc->root->addDynamicEntry(pde);
00566 }
00567 
00568 
00569 
00570 static void
00571 nukeAllDynamicEntries
00572 (
00573 IN kdtree::Node * node,
00574 free_type_t& freeList
00575 )
00576 {
00577         ASSERT(node, "null");
00578 
00579         // pop all dynamic entries here, add to free list
00580         while (smart_ptr<kdtree::Node::dynamic_entry_t> pde = 
00581                node->popDynamicEntry()) {
00582                 freeList.returnElement(pde);
00583         }
00584 
00585         // recurse
00586         kdtree::Node * left = node->getLeftChild();
00587         kdtree::Node * right = node->getRightChild();
00588 
00589         if (left) {
00590                 nukeAllDynamicEntries(left, freeList);
00591         }
00592         if (right) {
00593                 nukeAllDynamicEntries(right, freeList);
00594         }
00595 }
00596 
00597 
00598 
00599 ////////////////////////////////////////////////////////////////////////////////
00600 //
00601 //      KdTree  --  object that implements the MapKdTree interface
00602 //
00603 ////////////////////////////////////////////////////////////////////////////////
00604 
00605 class KdTree : public MapKdTree {
00606 public:
00607         KdTree(void) throw();
00608         ~KdTree(void) throw();
00609 
00610         // public class methods ------------------------------------------------
00611         void initialize(IN smart_ptr<MapDynamics>& map);
00612 
00613         // aesop::MapKdTree class interface methods ----------------------------
00614         MapDynamics * getMapDynamics(void) throw() { return m_map; }
00615         void walkNodes(IN kdtree_callback_fn callback,
00616                                 IN void * context);
00617         void walkFrontToBack(IN const glut::render_context_t& rc,
00618                                 IN glut::RenderQueue * rq,
00619                                 IN kdtree_object_fn callback,
00620                                 IN void * context);
00621         void update(void);
00622 
00623 private:
00624         // private typedefs ----------------------------------------------------
00625         typedef std::vector<smart_ptr<kdtree::Node> > node_vec_t;
00626 
00627         struct dyn_rec_t {
00628                 entry_t *       entry;
00629                 bool            updated;
00630         };
00631 
00632         // private helper methods ----------------------------------------------
00633         static void addZones(IN Zone * zone, IN void * context);
00634         static void addObjectsFromZone(IN Zone * zone, IN void * context);
00635         static void addStaticInstance(IN smart_ptr<Instance>& instance,
00636                                 IN void * context);
00637         static void addVirtualLeafInstance(IN smart_ptr<Instance>& instance,
00638                                 IN void * context);
00639         void addStaticInstance(IN smart_ptr<Instance>& instance,
00640                                 IN LeafZone * lz);
00641         void addVirtualLeaf(IN LeafZone * lz);
00642 
00643         // private member data -------------------------------------------------
00644         smart_ptr<MapDynamics>          m_map;  // map we are tracking
00645         smart_ptr<kdtree::Node>         m_root; // root of kd tree
00646         free_type_t                     m_freeList;// list of free de's
00647         node_vec_t                      m_virtuals; // virtual leaf zones
00648 };
00649 
00650 
00651 
00652 KdTree::KdTree
00653 (
00654 void
00655 )
00656 throw() :
00657 m_freeList(s_maxFreeListSize)
00658 {
00659 }
00660 
00661 
00662 
00663 KdTree::~KdTree
00664 (
00665 void
00666 )
00667 throw()
00668 {
00669         // walk tree and delete user pointers (if any)
00670         if (m_root) {
00671                 deletePointers(m_root);
00672         }
00673 
00674         // walk virtuals and delete user pointers
00675         for (node_vec_t::iterator i = m_virtuals.begin(); i != m_virtuals.end();
00676              ++i) {
00677                 kdtree::Node * node = *i;
00678                 ASSERT(node, "null node in virtual list");
00679                 void * user = node->getUserPointer();
00680                 if (user) {
00681                         node->setUserPointer(NULL);
00682                         node_data_t * nd = (node_data_t *) user;
00683                         delete nd;
00684                 }
00685         }
00686 }
00687 
00688 
00689 
00690 ////////////////////////////////////////////////////////////////////////////////
00691 //
00692 //      KdTree  --  public class methods
00693 //
00694 ////////////////////////////////////////////////////////////////////////////////
00695 
00696 void
00697 KdTree::initialize
00698 (
00699 IN smart_ptr<MapDynamics>& map
00700 )
00701 {
00702         perf::Timer timer("MapKdTree::initialize");
00703         ASSERT(map, "null");
00704 
00705         // remember map
00706         m_map = map;
00707 
00708         // get the underlying readonly map object from the map dynamics
00709         smart_ptr<Map> romap = map->getMap();
00710         ASSERT(romap, "null map in map dynamics");
00711 
00712         // get the root zone
00713         Zone * rz = romap->getRootZone();
00714         ASSERT(rz, "map contains null root zone?");
00715         rect3d_t mapBounds;
00716         rz->getBoundingRect(mapBounds);
00717         //mapBounds.dump("Map bounds");
00718 
00719         // create root node of kd tree
00720         ASSERT(!m_root, "already have a root node");
00721         m_root = kdtree::Node::create(mapBounds);
00722         ASSERT(m_root, "failed to create kdtree root node");
00723 
00724         // pass one: add all leaf zones as objects
00725         romap->iterateZones(addZones, this);
00726 
00727         // end of pass one: subdivide based on zones
00728         DPRINTF("Assembling rendering kdtree, pass 1: zones");
00729         int nMaxEntriesPerNode = 1;
00730         {
00731                 perf::Timer timer("MapKdTree::subdivide pass 1");
00732                 m_root->subdivide(kdtree::eStrategy_Balance,
00733                     nMaxEntriesPerNode);
00734         }
00735         DPRINTF("  pass 1 tree depth: %d", m_root->getTreeDepth());
00736         DPRINTF("  pass 1 nodes in tree: %d", m_root->getNodeCount());
00737         DPRINTF("  pass 1 entries in tree: %d", m_root->getStaticEntryCount());
00738 
00739         // clear all zone entitries from kd tree
00740         deleteAllEntries(m_root);
00741 
00742         // pass two: iterate over all (static) objects
00743         romap->iterateZones(addObjectsFromZone, this);
00744 
00745         // okay, quickly dump stats
00746         DPRINTF("Loaded %d entries into root of kdtree, subdividing...",
00747             m_root->getStaticEntryCount());
00748         nMaxEntriesPerNode = 7;
00749         {
00750                 perf::Timer timer("MapKdTree::subdivide pass 2");
00751                 m_root->subdivide(kdtree::eStrategy_Balance,
00752                     nMaxEntriesPerNode);
00753         }
00754         DPRINTF("  pass 2 tree depth: %d", m_root->getTreeDepth());
00755         DPRINTF("  pass 2 nodes in tree: %d", m_root->getNodeCount());
00756         DPRINTF("  pass 2 entries in tree: %d", m_root->getStaticEntryCount());
00757 
00758         // determine zone containment for each kdtree node
00759         determineZone(m_root, rz);
00760 }
00761 
00762 
00763 
00764 ////////////////////////////////////////////////////////////////////////////////
00765 //
00766 //      KdTree -- MapKdTree class interface methods 
00767 //
00768 ////////////////////////////////////////////////////////////////////////////////
00769 
00770 void
00771 KdTree::walkNodes
00772 (
00773 IN kdtree_callback_fn callback,
00774 IN void * context
00775 )
00776 {
00777         ASSERT(callback, "null");
00778         // ASSERT(context) -- we don't care
00779 
00780         walkTree(m_root, 0, callback, context);
00781 }
00782 
00783 
00784 
00785 void
00786 KdTree::walkFrontToBack
00787 (
00788 IN const glut::render_context_t& rc,
00789 IN glut::RenderQueue * rq,
00790 IN kdtree_object_fn callback,
00791 IN void * context
00792 )
00793 {
00794         perf::Timer timer("MapKdTree::walkFrontToBack");
00795         ASSERT(callback, "null");
00796         // ASSERT(context) -- we don't care
00797 
00798         // get view frustum
00799         frustum_t f;
00800         glut::getViewFrustum(rc.camera, rc.viewer, f);
00801 
00802         // what zone are we in?
00803         Map * map = m_map->getMap();
00804         ASSERT(map, "null map in map dynamics?");
00805         Zone * rz = map->getRootZone();
00806         ASSERT(rz, "null root zone in map?");
00807         LeafZone * viewerZone = rz->getLeafZone(rc.viewer.getPosition());
00808         if (!viewerZone) {
00809                 DPRINTF("WARNING: viewer is not in a leaf zone!  Drawing everything...");
00810         }
00811 
00812         // nuke all dynamic objects in tree
00813         nukeAllDynamicEntries(m_root, m_freeList);
00814 
00815         // add all dynamic entries from map
00816         add_dynamic_context_t adc;
00817         adc.root = m_root;
00818         adc.frustum = f;
00819         adc.viewerZone = viewerZone;
00820         adc.rootZone = rz;
00821         adc.freeList = &m_freeList;
00822         m_map->iterateInstancesInZone(rz, addDynamicObject, &adc);
00823 
00824         // perform regular front-to-back walk with non-virtual zones
00825         {
00826                 perf::Timer timer("MapKdTree::walkFtB (regular zones)");
00827                 aesop::walkFrontToBack(m_root, m_freeList, rc, rq, &f, viewerZone, callback, context);
00828         }
00829 
00830         // now add virtual leaf zones
00831         // we perform zone visibility determinations ourselves
00832         {
00833                 perf::Timer timer("MapKdTree::walkFtB (virtual zones)");
00834                 for (node_vec_t::iterator i = m_virtuals.begin();
00835                      i != m_virtuals.end(); ++i) {
00836                         kdtree::Node * node = *i;
00837                         ASSERT(node, "null node in virtuals list");
00838         
00839                         node_data_t * nd = (node_data_t *) node->getUserPointer();
00840                         ASSERT(nd, "null node data in virtual node");
00841 
00842                         if (!viewerZone->isLeafVisible(nd->leafzone)) {
00843                                 // this virtual leaf isn't visible to viewer
00844                                 continue;  
00845                         }
00846 
00847                         // visible!  call front-to-back visitor with null leafzone
00848                         aesop::walkFrontToBack(node, m_freeList, rc, rq, &f, NULL, callback, context);
00849                 }
00850         }
00851 }
00852 
00853 
00854 
00855 void
00856 KdTree::update
00857 (
00858 void
00859 )
00860 {
00861         perf::Timer timer("MapKdTree::update");
00862 
00863 }
00864 
00865 
00866 
00867 ////////////////////////////////////////////////////////////////////////////////
00868 //
00869 //      KdTree -- private helper methods
00870 //
00871 ////////////////////////////////////////////////////////////////////////////////
00872 
00873 void
00874 KdTree::addZones
00875 (
00876 IN Zone * zone,
00877 IN void * context
00878 )
00879 {
00880         ASSERT(zone, "null");
00881         KdTree * pThis = (KdTree *) context;
00882         ASSERT(pThis, "null");
00883         ASSERT(pThis->m_root, "need to create kdtree root node first");
00884 
00885         LeafZone * lz = dynamic_cast<LeafZone *>(zone);
00886         if (!lz) {
00887                 return;         // skip non-leaf zones
00888         }
00889         if (Zone::eType_VirtualLeaf == zone->getType()) {
00890                 pThis->addVirtualLeaf(lz);
00891                 return;         // don't add virtual leaf zones to main kd-tree
00892         }
00893 
00894         // have a leaf zone!  Add it as an entry
00895         smart_ptr<entry_t> entry = new entry_t;
00896         ASSERT(entry, "out of memory");
00897 
00898         rect3d_t r;
00899         lz->getBoundingRect(r);
00900 
00901         // downcast and add
00902         smart_ptr<kdtree::Entry> kEntry = entry;
00903         ASSERT(kEntry, "failed to downcast");
00904         pThis->m_root->addStaticEntry(kEntry, r);
00905 }
00906 
00907 
00908 
00909 void
00910 KdTree::addObjectsFromZone
00911 (
00912 IN Zone * zone,
00913 IN void * context
00914 )
00915 {
00916         ASSERT(zone, "null");
00917         ASSERT(context, "null");
00918 
00919         if (Zone::eType_Leaf != zone->getType()) {
00920                 return;         // only iterate leaf zones (not virtuals either)
00921         }
00922         LeafZone * lz = dynamic_cast<LeafZone *>(zone);
00923         if (!lz) {
00924                 DPRINTF("ERROR: leaf zone can't be upcasted?");
00925                 return;         // skip non-leaf zones
00926         }
00927 
00928         add_static_context_t asc;
00929         asc.pThis = (KdTree *) context;
00930         asc.leafzone = lz;
00931         lz->iterateStaticInstances(addStaticInstance, &asc);
00932 }
00933 
00934 
00935 
00936 void
00937 KdTree::addStaticInstance
00938 (
00939 IN smart_ptr<Instance>& instance,
00940 IN void * context
00941 )
00942 {
00943         ASSERT(instance, "null");
00944         add_static_context_t * pasc = (add_static_context_t *) context;
00945         ASSERT(pasc, "null context");
00946         ASSERT(pasc->pThis, "null");
00947         ASSERT(pasc->leafzone, "null");
00948 
00949         // we have a static instance!  Work off placement for partitioning
00950         pasc->pThis->addStaticInstance(instance, pasc->leafzone);
00951 }
00952 
00953 
00954 
00955 void
00956 KdTree::addVirtualLeafInstance
00957 (
00958 IN smart_ptr<Instance>& instance,
00959 IN void * context
00960 )
00961 {
00962         ASSERT(instance, "null");
00963         add_virtual_context_t * pavc = (add_virtual_context_t *) context;
00964         ASSERT(pavc, "null context");
00965         ASSERT(pavc->node, "null");
00966         ASSERT(pavc->leafzone, "null");
00967 
00968         addInstanceToNode(instance, pavc->leafzone, pavc->node);
00969 }
00970 
00971 
00972 
00973 void
00974 KdTree::addStaticInstance
00975 (
00976 IN smart_ptr<Instance>& instance,
00977 IN LeafZone * lz
00978 )
00979 {
00980         ASSERT(instance, "null");
00981         ASSERT(lz, "null");
00982         ASSERT(m_root, "need to create kdtree root first");
00983 
00984         addInstanceToNode(instance, lz, m_root);
00985 }
00986 
00987 
00988 
00989 void
00990 KdTree::addVirtualLeaf
00991 (
00992 IN LeafZone * lz
00993 )
00994 {
00995         ASSERT(lz, "null");
00996         ASSERT(Zone::eType_VirtualLeaf == lz->getType(),
00997             "zone is not a virtual leaf");
00998 
00999         // get dimensions
01000         DPRINTF("Adding virtual leaf...");
01001         rect3d_t r;
01002         lz->getBoundingRect(r);
01003         r.dump("  virtual leaf dimensions");
01004 
01005         // create an isolated kd-tree node for this virtual leaf
01006         smart_ptr<kdtree::Node> node = kdtree::Node::create(r);
01007         ASSERT(node, "out of memory");
01008 
01009         // set node data
01010         smart_ptr<node_data_t> nd = new node_data_t;
01011         ASSERT(nd, "out of memory");
01012         nd->leafzone = lz;
01013         node->setUserPointer(nd.disown());
01014 
01015         // iterate over all objects in the leaf and add them as entries to the
01016         //   kdtree node.
01017         add_virtual_context_t avc;
01018         avc.node = node;
01019         avc.leafzone = lz;
01020         lz->iterateStaticInstances(addVirtualLeafInstance, &avc);
01021         DPRINTF("Virtual leaf node contains %d entries",
01022             node->getStaticEntryCount());
01023 
01024         // add this isolated node to our list of virtual leaf nodes
01025         m_virtuals.push_back(node);
01026 }
01027 
01028 
01029 
01030 ////////////////////////////////////////////////////////////////////////////////
01031 //
01032 //      public API
01033 //
01034 ////////////////////////////////////////////////////////////////////////////////
01035 
01036 smart_ptr<MapKdTree>
01037 MapKdTree::create
01038 (
01039 IN smart_ptr<MapDynamics>& map
01040 )
01041 {
01042         ASSERT(map, "null");
01043 
01044         smart_ptr<KdTree> local = new KdTree;
01045         ASSERT(local, "out of memory");
01046 
01047         local->initialize(map);
01048 
01049         return local;
01050 }
01051 
01052 
01053 
01054 };      // aesop namespace
01055