map-kdtree.cpp

Go to the documentation of this file.

/*
 * map-kdtree.cpp
 *
 * Copyright (C) 2010  Thomas A. Vaughan
 * All rights reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 */

// includes --------------------------------------------------------------------
#include "map-kdtree.h"                 // always include our own header first!

#include "glut/frustum.h"
#include "glut/renderable.h"
#include "model-loader/model-loader.h"
#include "perf/perf.h"
#include "util/free_list.h"


namespace aesop {


// interface destructor implementation
MapKdTree::~MapKdTree(void) throw() { }


typedef free_list_t<kdtree::Node::dynamic_entry_t> free_type_t;

static const int s_maxFreeListSize = 256;


struct node_data_t {
        // constructor, manipulators
        node_data_t(void) throw() { this->clear(); }
        void clear(void) throw() {
                        leafzone = NULL;
                }

        // data fields
        LeafZone *              leafzone;
};



class KdTree;           // forward declaration

struct add_static_context_t {
        // data fields
        KdTree *                pThis;
        LeafZone *              leafzone;
};



struct add_virtual_context_t {
        // data fields
        kdtree::Node *          node;
        LeafZone *              leafzone;
};



struct add_dynamic_context_t {
        add_dynamic_context_t(void) throw() { this->clear(); }
        void clear(void) throw() {
                        root = NULL;
                        viewerZone = NULL;
                        rootZone = NULL;
                        frustum.clear();
                        freeList = NULL;
                }

        // data fields
        kdtree::Node *          root;
        LeafZone *              viewerZone;
        Zone *                  rootZone;
        frustum_t               frustum;
        free_type_t *           freeList;
};



struct entry_t : public kdtree::Entry {
        // data fields
        smart_ptr<glut::Renderable>     model;
        placement_t                     placement;
        LeafZone *                      leafzone;
};



// used for sorting entries within a node
struct sort_entry_t {
        smart_ptr<entry_t>      entry;
        float                   d2;  // distance^2 from viewer to object
};


//
//      static helper methods
//

static void
determineZone
(
IN kdtree::Node * node,
IN Zone * root
)
{
        ASSERT(node, "null");
        ASSERT(root, "null");

        smart_ptr<node_data_t> nd = new node_data_t;
        ASSERT(nd, "out of memory");

        const rect3d_t& nodeRect = node->getRect();
        LeafZone * lz = root->getLeafZone(nodeRect.getMidpoint());
        if (!lz) {
                // DPRINTF("WARNING: node midpoint is not contained!");
        } else {
                // found a leaf zone.  Does it fully contain this kdtree node?
                rect3d_t zoneRect;
                lz->getBoundingRect(zoneRect);
                if (zoneRect.containsRect(nodeRect)) {
                        // yes, leaf zone fully contains kdtree node!
                        //DPRINTF("Node is fully in zone %p", lz);
                        nd->leafzone = lz;
                }
        }

        // hand over the data
        node->setUserPointer(nd.disown());

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

        if (left) {
                determineZone(left, root);
        }
        if (right) {
                determineZone(right, root);
        }
}



static void
deletePointers
(
IN kdtree::Node * node
)
throw()
{
        ASSERT(node, "null");

        void * user = node->getUserPointer();
        if (user) {
                node->setUserPointer(NULL);
                node_data_t * nd = (node_data_t *) user;
                delete nd;
        }

        kdtree::Node * left = node->getLeftChild();
        kdtree::Node * right = node->getRightChild();
        if (left)
                deletePointers(left);
        if (right)
                deletePointers(right);
}



static void
deleteAllEntries
(
IN kdtree::Node * node
)
throw()
{
        ASSERT(node, "null");

        // delete entries one at a time
        while (true) {
                kdtree::Node::vec_entries_t& vec = node->getStaticEntries();
                int nEntries = vec.size();
                if (nEntries < 1)
                        break;  // empty!

                // not empty!  remove last element
                kdtree::Entry * entry = vec[nEntries - 1].entry;
                ASSERT(entry, "null entry in list?");
                node->removeStaticEntry(entry);
        }

        // recurse
        kdtree::Node * left = node->getLeftChild();
        kdtree::Node * right = node->getRightChild();
        if (left)
                deleteAllEntries(left);
        if (right)
                deleteAllEntries(right);
}



static void
walkTree
(
IN kdtree::Node * node,
IN int depth,
IN kdtree_callback_fn callback,
IN void * context
)
{
        ASSERT(node, "null");
        ASSERT(depth >= 0, "bad depth: %d", depth);
        ASSERT(callback, "null");
        // ASSERT(context) -- we don't care

        kd_node_t kn;
        kn.rect = node->getRect();
        kn.depth = depth;
        callback(kn, context);

        // recurse
        kdtree::Node * left = node->getLeftChild();
        kdtree::Node * right = node->getRightChild();
        if (left)
                walkTree(left, depth + 1, callback, context);
        if (right)
                walkTree(right, depth + 1, callback, context);
}



static int
compareEntries
(
IN const void * p1,
IN const void * p2
)
throw()
{
        const sort_entry_t * se1 = (const sort_entry_t *) p1;
        const sort_entry_t * se2 = (const sort_entry_t *) p2;
        ASSERT(se1 && se2, "null");

        if (se1->d2 < se2->d2) {
                return -1;      // distance is less therefore closer
        } else if (se1->d2 > se2->d2) {
                return +1;
        }

        // got here?  must be equal...
        return 0;
}



static void
walkFrontToBack
(
IN kdtree::Node * node,
IN free_type_t& freeList,
IN const glut::render_context_t& rc,
IN glut::RenderQueue * rq,
IN const frustum_t * f,
IN LeafZone * viewerZone,
IN kdtree_object_fn callback,
IN void * context
)
{
        ASSERT(node, "null");
        ASSERT(rq, "null");
        // ASSERT(f) -- can be null! (no frustum check required)
        // ASSERT(viewerZone) -- can be null! (no zone check required)
        ASSERT(callback, "null");
        // ASSERT(context) -- we don't care

        // need to verify visibility?
        if (viewerZone) {
                const node_data_t * nd = (const node_data_t *) node->getUserPointer();
                ASSERT(nd, "map kd node with no user pointer?");

                // can verify if this node is itself full contained
                if (nd->leafzone) {
                        // yes, now verify
                        if (viewerZone->isLeafVisible(nd->leafzone)) {
                                // yes, verified visible!
                                // for this node and recursion, no checking
                                // needed
                                viewerZone = NULL;
                        } else {
                                // this node, and all children, are not visible!
                                return;
                        }
                }
        }

        // need to verify frustum?
        if (f) {
                const rect3d_t& r = node->getRect();
                switch (f->containsRect(r)) {
                case eContains_None:
                        return;         // this and all children aren't visible!

                case eContains_Fully:
                        f = NULL;       // this and all children are in frustum
                        break;

                default:
                        // have to keep checking as we recurse, no change
                        break;
                }
        }

        // okay, we are visible.  walk front to back in this node
        const point3d_t& start = rc.viewer.getPosition();

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

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

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

        // first visit closest
        if (closest) {
                walkFrontToBack(closest, freeList, rc, rq, f, viewerZone, callback, context);
        }

        // construct a quick array on the stack for sorting
        const int nMaxEntries = 256;
        sort_entry_t sortArray[nMaxEntries];
        int nEntries = 0;       // count of visible entries (== array size)

        // visit ourselves
        const kdtree::Node::vec_entries_t& vec = node->getStaticEntries();

        // populate with pointers
        for (kdtree::Node::vec_entries_t::const_iterator i = vec.begin();
             i != vec.end(); ++i) {
                const kdtree::Node::entry_rec_t& er = *i;

                smart_ptr<entry_t> entry = er.entry;
                ASSERT(entry, "failed to upcast");

                // visible?
                if (viewerZone &&
                    !viewerZone->isLeafVisible(entry->leafzone))
                        continue;       // skip this one--not visible

                // okay, create entry
                sort_entry_t se;
                se.entry = entry;

                // distance from viewer to object?
                point3d_t diff = entry->placement.position - start;
                se.d2 = dotProduct(diff, diff);

                // add to array for sorting
                sortArray[nEntries] = se;
                ++nEntries;
                if (nEntries > nMaxEntries) {
                        // we don't want to blow the stack.  Give up
                        DPRINTF("ERROR: too many entries (%d) in node!",
                            nEntries);
                        DPRINTF("  Giving up rendering remaining entries");
                        break;
                }
        }

        // populate with dynamic objects
        while (smart_ptr<kdtree::Node::dynamic_entry_t> pde =
               node->popDynamicEntry()) {
                // assume visible!
                sort_entry_t se;
                se.entry = pde->entry;

                // distance from viewer to object?
                point3d_t diff = se.entry->placement.position - start;
                se.d2 = dotProduct(diff, diff);

                // add to array for sorting
                sortArray[nEntries] = se;
                ++nEntries;
                if (nEntries > nMaxEntries) {
                        DPRINTF("ERROR: too many entries (%d) in node!",
                            nEntries);
                        DPRINTF("  Giving up rendering remaining entries");
                        break;
                }

                // return this to free list (or nuke!)
                freeList.returnElement(pde);
        }

        ASSERT(nEntries <= nMaxEntries, "should have at most nMaxEntries visible");
        if (nEntries > 32) {
                // probably a sign that the space isn't well partitioned
                DPRINTF("WARNING: many entries (%d) in node!", nEntries);
        }

        // sort by distance to plane
        qsort(sortArray, nEntries, sizeof(sort_entry_t), compareEntries);

        // now walk in sorted order
        for (int i = 0; i < nEntries; ++i) {
                entry_t * entry = sortArray[i].entry;
                ASSERT(entry, "null entry in sort array?");

                // update render context with this object's placement
                glut::render_context_t rc2 = rc;
                rc2.placement = entry->placement;

                // make callback
                callback(entry->model, rc2, rq, context);
        }

        // finally visit farthest
        if (farthest) {
                walkFrontToBack(farthest, freeList, rc, rq, f, viewerZone, callback, context);
        }
}



static void
addInstanceToNode
(
IN smart_ptr<Instance>& instance,
IN LeafZone * lz,
IN kdtree::Node * node
)
{
        ASSERT(instance, "null");
        ASSERT(lz, "null");
        ASSERT(node, "null");

        // look up the 3D model for this instance
        smart_ptr<glut::Renderable> model = getModel(instance);
        if (!model) {
                DPRINTF("No model for instance of type '%s'",
                    instance->getTypeId());
                return;
        }

        rect3d_t r = model->getBoundingBox();
        r.translate(instance->getPlacement().position);

        //DPRINTF("Rect for instance of type '%s'", instance->getTypeId());
        //r.dump("  bounding rect");

        smart_ptr<entry_t> entry = new entry_t;
        entry->model = model;
        entry->placement = instance->getPlacement();
        entry->leafzone = lz;

        // downcast and add
        smart_ptr<kdtree::Entry> kEntry = entry;
        node->addStaticEntry(kEntry, r);
}



static void
addDynamicObject
(
IN smart_ptr<Instance>& instance,
IN smart_ptr<PhysicsObject>& obj,
IN void * context
)
{
        ASSERT(instance, "null");
        ASSERT(obj, "null");
        add_dynamic_context_t * padc = (add_dynamic_context_t *) context;
        ASSERT(padc, "null");
        ASSERT(padc->root, "null");
        ASSERT(padc->rootZone, "null");
        // ASSERT(padc->viewerZone, "null"); can be null
        ASSERT(padc->freeList, "null");

        // is this a dynamic instance?
        if (PhysicsObject::eFlag_Static & obj->getFlags()) {
                // static!
                return;
        }

        // get leaf zone that contains instance
        const point3d_t pos = instance->getPlacement().position;
        LeafZone * lz = padc->rootZone->getLeafZone(pos);
        if (lz && padc->viewerZone &&
            !padc->viewerZone->isLeafVisible(lz)) {
                // not visible from viewer zone!
                return;
        }

        // look up the 3D model for this instance
        smart_ptr<glut::Renderable> model = getModel(instance);
        if (!model) {
                DPRINTF("No model for instance of type '%s'",
                    instance->getTypeId());
                return;
        }
        rect3d_t r = model->getBoundingBox();
        r.translate(pos);
        
        // okay, may be visible.  In frustum?
        if (eContains_None == padc->frustum.containsRect(r)) {
                return;         // does not intersect view frustum
        }

        // okay, may be visible and is in frustum.  Add as dynamic entry to
        //   kdtree.
        smart_ptr<kdtree::Node::dynamic_entry_t> pde;

        // first, attempt to pull from free list
        pde = padc->freeList->getElement();
        if (!pde->entry) {
                pde->entry = new entry_t;
                ASSERT(pde->entry, "null");
        }
        ASSERT(!pde->next, "should be null");

        // update entry
        entry_t * entry = dynamic_cast<entry_t *>((kdtree::Entry *) pde->entry);
        ASSERT(entry, "failed to upcast");
        entry->model = model;
        entry->placement = instance->getPlacement();
        entry->leafzone = lz;   // may be null!

        // add to tree
        padc->root->addDynamicEntry(pde);
}



static void
nukeAllDynamicEntries
(
IN kdtree::Node * node,
free_type_t& freeList
)
{
        ASSERT(node, "null");

        // pop all dynamic entries here, add to free list
        while (smart_ptr<kdtree::Node::dynamic_entry_t> pde = 
               node->popDynamicEntry()) {
                freeList.returnElement(pde);
        }

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

        if (left) {
                nukeAllDynamicEntries(left, freeList);
        }
        if (right) {
                nukeAllDynamicEntries(right, freeList);
        }
}



//
//      KdTree  --  object that implements the MapKdTree interface
//

class KdTree : public MapKdTree {
public:
        KdTree(void) throw();
        ~KdTree(void) throw();

        // public class methods ------------------------------------------------
        void initialize(IN smart_ptr<MapDynamics>& map);

        // aesop::MapKdTree class interface methods ----------------------------
        MapDynamics * getMapDynamics(void) throw() { return m_map; }
        void walkNodes(IN kdtree_callback_fn callback,
                                IN void * context);
        void walkFrontToBack(IN const glut::render_context_t& rc,
                                IN glut::RenderQueue * rq,
                                IN kdtree_object_fn callback,
                                IN void * context);
        void update(void);

private:
        // private typedefs ----------------------------------------------------
        typedef std::vector<smart_ptr<kdtree::Node> > node_vec_t;

        struct dyn_rec_t {
                entry_t *       entry;
                bool            updated;
        };

        // private helper methods ----------------------------------------------
        static void addZones(IN Zone * zone, IN void * context);
        static void addObjectsFromZone(IN Zone * zone, IN void * context);
        static void addStaticInstance(IN smart_ptr<Instance>& instance,
                                IN void * context);
        static void addVirtualLeafInstance(IN smart_ptr<Instance>& instance,
                                IN void * context);
        void addStaticInstance(IN smart_ptr<Instance>& instance,
                                IN LeafZone * lz);
        void addVirtualLeaf(IN LeafZone * lz);

        // private member data -------------------------------------------------
        smart_ptr<MapDynamics>          m_map;  // map we are tracking
        smart_ptr<kdtree::Node>         m_root; // root of kd tree
        free_type_t                     m_freeList;// list of free de's
        node_vec_t                      m_virtuals; // virtual leaf zones
};



KdTree::KdTree
(
void
)
throw() :
m_freeList(s_maxFreeListSize)
{
}



KdTree::~KdTree
(
void
)
throw()
{
        // walk tree and delete user pointers (if any)
        if (m_root) {
                deletePointers(m_root);
        }

        // walk virtuals and delete user pointers
        for (node_vec_t::iterator i = m_virtuals.begin(); i != m_virtuals.end();
             ++i) {
                kdtree::Node * node = *i;
                ASSERT(node, "null node in virtual list");
                void * user = node->getUserPointer();
                if (user) {
                        node->setUserPointer(NULL);
                        node_data_t * nd = (node_data_t *) user;
                        delete nd;
                }
        }
}



//
//      KdTree  --  public class methods
//

void
KdTree::initialize
(
IN smart_ptr<MapDynamics>& map
)
{
        perf::Timer timer("MapKdTree::initialize");
        ASSERT(map, "null");

        // remember map
        m_map = map;

        // get the underlying readonly map object from the map dynamics
        smart_ptr<Map> romap = map->getMap();
        ASSERT(romap, "null map in map dynamics");

        // get the root zone
        Zone * rz = romap->getRootZone();
        ASSERT(rz, "map contains null root zone?");
        rect3d_t mapBounds;
        rz->getBoundingRect(mapBounds);
        //mapBounds.dump("Map bounds");

        // create root node of kd tree
        ASSERT(!m_root, "already have a root node");
        m_root = kdtree::Node::create(mapBounds);
        ASSERT(m_root, "failed to create kdtree root node");

        // pass one: add all leaf zones as objects
        romap->iterateZones(addZones, this);

        // end of pass one: subdivide based on zones
        DPRINTF("Assembling rendering kdtree, pass 1: zones");
        int nMaxEntriesPerNode = 1;
        {
                perf::Timer timer("MapKdTree::subdivide pass 1");
                m_root->subdivide(kdtree::eStrategy_Balance,
                    nMaxEntriesPerNode);
        }
        DPRINTF("  pass 1 tree depth: %d", m_root->getTreeDepth());
        DPRINTF("  pass 1 nodes in tree: %d", m_root->getNodeCount());
        DPRINTF("  pass 1 entries in tree: %d", m_root->getStaticEntryCount());

        // clear all zone entitries from kd tree
        deleteAllEntries(m_root);

        // pass two: iterate over all (static) objects
        romap->iterateZones(addObjectsFromZone, this);

        // okay, quickly dump stats
        DPRINTF("Loaded %d entries into root of kdtree, subdividing...",
            m_root->getStaticEntryCount());
        nMaxEntriesPerNode = 7;
        {
                perf::Timer timer("MapKdTree::subdivide pass 2");
                m_root->subdivide(kdtree::eStrategy_Balance,
                    nMaxEntriesPerNode);
        }
        DPRINTF("  pass 2 tree depth: %d", m_root->getTreeDepth());
        DPRINTF("  pass 2 nodes in tree: %d", m_root->getNodeCount());
        DPRINTF("  pass 2 entries in tree: %d", m_root->getStaticEntryCount());

        // determine zone containment for each kdtree node
        determineZone(m_root, rz);
}



//
//      KdTree -- MapKdTree class interface methods 
//

void
KdTree::walkNodes
(
IN kdtree_callback_fn callback,
IN void * context
)
{
        ASSERT(callback, "null");
        // ASSERT(context) -- we don't care

        walkTree(m_root, 0, callback, context);
}



void
KdTree::walkFrontToBack
(
IN const glut::render_context_t& rc,
IN glut::RenderQueue * rq,
IN kdtree_object_fn callback,
IN void * context
)
{
        perf::Timer timer("MapKdTree::walkFrontToBack");
        ASSERT(callback, "null");
        // ASSERT(context) -- we don't care

        // get view frustum
        frustum_t f;
        glut::getViewFrustum(rc.camera, rc.viewer, f);

        // what zone are we in?
        Map * map = m_map->getMap();
        ASSERT(map, "null map in map dynamics?");
        Zone * rz = map->getRootZone();
        ASSERT(rz, "null root zone in map?");
        LeafZone * viewerZone = rz->getLeafZone(rc.viewer.getPosition());
        if (!viewerZone) {
                DPRINTF("WARNING: viewer is not in a leaf zone!  Drawing everything...");
        }

        // nuke all dynamic objects in tree
        nukeAllDynamicEntries(m_root, m_freeList);

        // add all dynamic entries from map
        add_dynamic_context_t adc;
        adc.root = m_root;
        adc.frustum = f;
        adc.viewerZone = viewerZone;
        adc.rootZone = rz;
        adc.freeList = &m_freeList;
        m_map->iterateInstancesInZone(rz, addDynamicObject, &adc);

        // perform regular front-to-back walk with non-virtual zones
        {
                perf::Timer timer("MapKdTree::walkFtB (regular zones)");
                aesop::walkFrontToBack(m_root, m_freeList, rc, rq, &f, viewerZone, callback, context);
        }

        // now add virtual leaf zones
        // we perform zone visibility determinations ourselves
        {
                perf::Timer timer("MapKdTree::walkFtB (virtual zones)");
                for (node_vec_t::iterator i = m_virtuals.begin();
                     i != m_virtuals.end(); ++i) {
                        kdtree::Node * node = *i;
                        ASSERT(node, "null node in virtuals list");
        
                        node_data_t * nd = (node_data_t *) node->getUserPointer();
                        ASSERT(nd, "null node data in virtual node");

                        if (!viewerZone->isLeafVisible(nd->leafzone)) {
                                // this virtual leaf isn't visible to viewer
                                continue;  
                        }

                        // visible!  call front-to-back visitor with null leafzone
                        aesop::walkFrontToBack(node, m_freeList, rc, rq, &f, NULL, callback, context);
                }
        }
}



void
KdTree::update
(
void
)
{
        perf::Timer timer("MapKdTree::update");

}



//
//      KdTree -- private helper methods
//

void
KdTree::addZones
(
IN Zone * zone,
IN void * context
)
{
        ASSERT(zone, "null");
        KdTree * pThis = (KdTree *) context;
        ASSERT(pThis, "null");
        ASSERT(pThis->m_root, "need to create kdtree root node first");

        LeafZone * lz = dynamic_cast<LeafZone *>(zone);
        if (!lz) {
                return;         // skip non-leaf zones
        }
        if (Zone::eType_VirtualLeaf == zone->getType()) {
                pThis->addVirtualLeaf(lz);
                return;         // don't add virtual leaf zones to main kd-tree
        }

        // have a leaf zone!  Add it as an entry
        smart_ptr<entry_t> entry = new entry_t;
        ASSERT(entry, "out of memory");

        rect3d_t r;
        lz->getBoundingRect(r);

        // downcast and add
        smart_ptr<kdtree::Entry> kEntry = entry;
        ASSERT(kEntry, "failed to downcast");
        pThis->m_root->addStaticEntry(kEntry, r);
}



void
KdTree::addObjectsFromZone
(
IN Zone * zone,
IN void * context
)
{
        ASSERT(zone, "null");
        ASSERT(context, "null");

        if (Zone::eType_Leaf != zone->getType()) {
                return;         // only iterate leaf zones (not virtuals either)
        }
        LeafZone * lz = dynamic_cast<LeafZone *>(zone);
        if (!lz) {
                DPRINTF("ERROR: leaf zone can't be upcasted?");
                return;         // skip non-leaf zones
        }

        add_static_context_t asc;
        asc.pThis = (KdTree *) context;
        asc.leafzone = lz;
        lz->iterateStaticInstances(addStaticInstance, &asc);
}



void
KdTree::addStaticInstance
(
IN smart_ptr<Instance>& instance,
IN void * context
)
{
        ASSERT(instance, "null");
        add_static_context_t * pasc = (add_static_context_t *) context;
        ASSERT(pasc, "null context");
        ASSERT(pasc->pThis, "null");
        ASSERT(pasc->leafzone, "null");

        // we have a static instance!  Work off placement for partitioning
        pasc->pThis->addStaticInstance(instance, pasc->leafzone);
}



void
KdTree::addVirtualLeafInstance
(
IN smart_ptr<Instance>& instance,
IN void * context
)
{
        ASSERT(instance, "null");
        add_virtual_context_t * pavc = (add_virtual_context_t *) context;
        ASSERT(pavc, "null context");
        ASSERT(pavc->node, "null");
        ASSERT(pavc->leafzone, "null");

        addInstanceToNode(instance, pavc->leafzone, pavc->node);
}



void
KdTree::addStaticInstance
(
IN smart_ptr<Instance>& instance,
IN LeafZone * lz
)
{
        ASSERT(instance, "null");
        ASSERT(lz, "null");
        ASSERT(m_root, "need to create kdtree root first");

        addInstanceToNode(instance, lz, m_root);
}



void
KdTree::addVirtualLeaf
(
IN LeafZone * lz
)
{
        ASSERT(lz, "null");
        ASSERT(Zone::eType_VirtualLeaf == lz->getType(),
            "zone is not a virtual leaf");

        // get dimensions
        DPRINTF("Adding virtual leaf...");
        rect3d_t r;
        lz->getBoundingRect(r);
        r.dump("  virtual leaf dimensions");

        // create an isolated kd-tree node for this virtual leaf
        smart_ptr<kdtree::Node> node = kdtree::Node::create(r);
        ASSERT(node, "out of memory");

        // set node data
        smart_ptr<node_data_t> nd = new node_data_t;
        ASSERT(nd, "out of memory");
        nd->leafzone = lz;
        node->setUserPointer(nd.disown());

        // iterate over all objects in the leaf and add them as entries to the
        //   kdtree node.
        add_virtual_context_t avc;
        avc.node = node;
        avc.leafzone = lz;
        lz->iterateStaticInstances(addVirtualLeafInstance, &avc);
        DPRINTF("Virtual leaf node contains %d entries",
            node->getStaticEntryCount());

        // add this isolated node to our list of virtual leaf nodes
        m_virtuals.push_back(node);
}



//
//      public API
//

smart_ptr<MapKdTree>
MapKdTree::create
(
IN smart_ptr<MapDynamics>& map
)
{
        ASSERT(map, "null");

        smart_ptr<KdTree> local = new KdTree;
        ASSERT(local, "out of memory");

        local->initialize(map);

        return local;
}



};      // aesop namespace