walk.cpp

Go to the documentation of this file.

/*
 * walk.cpp
 *
 * Copyright (C) 2010  Thomas A. Vaughan
 * All rights reserved.
 *
 * Simple test of the kdtree API, focusing on walking the structure externally.
 */

// includes --------------------------------------------------------------------
#include "common/wave_ex.h"
#include "kdtree/kdtree.h"
#include "perf/perf.h"

#include <math.h>
#include <iostream>



static const float s_max                        = 5000.0;


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

class Test : public kdtree::Entry {
public:
        ~Test(void) throw() { }
};


static float
getRandom
(
IN float q
)
{
        ASSERT(q > 0, "bad q: %f", q);

        return (q * rand()) / RAND_MAX;
}



static void
getRandomRect
(
IN const rect3d_t& bounds,
IN float size,
OUT rect3d_t& r
)
{
        ASSERT(bounds.isValid(), "invalid");

        r.x0 = bounds.x0 + getRandom(bounds.x1 - bounds.x0 - 1.01 * size);
        r.y0 = bounds.y0 + getRandom(bounds.y1 - bounds.y0 - 1.01 * size);
        r.z0 = bounds.z0 + getRandom(bounds.z1 - bounds.z0 - 1.01 * size);

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



static kdtree::eAction
countCallback
(
IN void * context,
IN kdtree::Entry * e,
IN const rect3d_t& r
)
{
        long * pCount = (long *) context;
        ASSERT(pCount, "null context?");

        *pCount = (*pCount) + 1;

        return kdtree::eAction_Continue;
}


/*
static kdtree::eAction
printCallback
(
IN void * context,
IN kdtree::entry_t& e
)
{
        long * pCount = (long *) context;
        ASSERT(pCount, "null context?");

        DPRINTF("Found entry in search rect");
        e.bounds.dump("  entry bounds");

        *pCount = (*pCount) + 1;

        return kdtree::eAction_Continue;
}
 */


static kdtree::eAction
findCallback
(
IN void * context,
IN kdtree::Entry * e,
IN const rect3d_t& r
)
{
        if (e == context) {
                // we have a match!
                return kdtree::eAction_Halt;
        }

        // not a match...
        return kdtree::eAction_Continue;
}



static kdtree::eAction
removeCallback
(
IN void * context,
IN kdtree::Entry * e,
IN const rect3d_t& r
)
{
        if (e == context) {
                // matches!
                return (kdtree::eAction)
                    (kdtree::eAction_Remove | kdtree::eAction_Halt);
        }

        // not a match...
        return kdtree::eAction_Continue;
}



static smart_ptr<kdtree::Node>
populateTree
(
IN int nCount,
IN int subdivide
)
{
        perf::Timer timer("populateTree");
        ASSERT(nCount > 0, "bad count: %d", nCount);
        ASSERT(subdivide > 0, "Bad subdivide: %d", subdivide);

        rect3d_t bounds;

        DPRINTF(
            "Populating tree with %d entries, subdivide at %d entries per node",
            nCount, subdivide);

        bounds.x0 = -s_max;
        bounds.x1 = +s_max;
        bounds.y0 = -(s_max / 2.5);
        bounds.y1 = +(s_max / 2.5);
        bounds.z0 = -(s_max / 5);
        bounds.z1 = +(s_max / 5);
        //bounds.dump("bounds");

        smart_ptr<kdtree::Node> root = kdtree::Node::create(bounds);
        ASSERT(root, "failed to create root node");

        for (int i = 0; i < nCount; ++i) {
                rect3d_t r;
                getRandomRect(bounds, getRandom(10), r);
                r.dump("  adding");
                smart_ptr<kdtree::Entry> e;

                {
                        perf::Timer timer("addEntry");
                        root->addStaticEntry(e, r);
                }
        }

        DPRINTF("Tree depth: %d", root->getTreeDepth());
        DPRINTF("Node count: %d", root->getNodeCount());
        DPRINTF("Entry count: %d", root->getStaticEntryCount());
        if (root->getStaticEntryCount() != nCount) {
                WAVE_EX(wex);
                wex << "Count of entries in tree does not match what was added";
        }

        // okay, subdivide
        DPRINTF("Subdividing...");
        {
                perf::Timer timer("subdivide");
                root->subdivide(kdtree::eStrategy_Naive, subdivide);
        }
        DPRINTF("Tree depth: %d", root->getTreeDepth());
        DPRINTF("Node count: %d", root->getNodeCount());
        DPRINTF("Entry count: %d", root->getStaticEntryCount());

        long count = 0;
        {
                perf::Timer timer("full iteration");
                root->iterateStaticEntries(bounds, countCallback, (void *) &count);
        }
        if (count != nCount) {
                WAVE_EX(wex);
                wex << "Iteration should return all entities!";
        }

        rect3d_t sub;
        getRandomRect(bounds, 1000, sub);
        sub.dump("Search rect");
        count = 0;
        {
                // warning: don't use the print callback here, it is slow
                //      (writing to console)
                perf::Timer timer("sub iteration");
                root->iterateStaticEntries(sub, countCallback, (void *) &count);
        }
        DPRINTF("Found %ld entries in sub rect", count);

        // all done
        return root;
}



static void
walkNearToFar
(
IN const kdtree::Node * node,
IN const point3d_t& start,
IN const point3d_t& end,
IN const point3d_t& n           // normalized direction of walk
)
throw()
{
        ASSERT(node, "null");

        // look at the given node and its children (if any)
        //  - walk farthest child
        //  - walk local spanning objects
        //  - walk closest child

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

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

        // determine farthest, closest nodes
        const kdtree::Node * farthest = left;
        const kdtree::Node * closest = right;
        if (kdtree::eSort_Left == sort) {
                farthest = right;
                closest = left;
        }

        // walk closest first
        if (closest) {
                walkNearToFar(closest, start, end, n);
        }

        // walk straddling objects
        const kdtree::Node::vec_entries_t& vec = node->getStaticEntries();
        if (vec.size()) {
                DPRINTF("%d entries in this node", (int) vec.size());
        }
        for (kdtree::Node::vec_entries_t::const_iterator i = vec.begin();
             i != vec.end(); ++i) {
                const kdtree::Node::entry_rec_t& er = *i;
                point3d_t mid = er.rect.getMidpoint();
                mid = mid - start;
                float d = fabs(dotProduct(n, mid));
                DPRINTF("Object at distance: %f", d);
        }

        // walk farthest
        if (farthest) {
                walkNearToFar(farthest, start, end, n);
        }
}



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

int
main
(
IN int argc,
IN const char * argv[]
)
{
        int nCount = 50 * 1000;
        int nDivide = 32;
        if (argc > 1) {
                nCount = atoi(argv[1]);
        } else {
                DPRINTF("No count provided, so using count = %d", nCount);
        }
        if (argc > 2) {
                nDivide = atoi(argv[2]);
        } else {
                DPRINTF("No subdivide threshold specified, using %d", nDivide);
        }
        int retval = 0;

        try {
                perf::Timer timer("Total test time");

                smart_ptr<kdtree::Node> root = populateTree(nCount, nDivide);
                ASSERT(root, "failed to create kd-tree");

                point3d_t start(0, 0, 0);
                point3d_t end(s_max, s_max, s_max);

                point3d_t n = end - start;
                normalize(n);
                n.dump("Walk direction");

                walkNearToFar(root, start, end, n);

        } catch (std::exception& e) {
                DPRINTF("Exception: %s", e.what());
                retval = 1;
        }

        perf::dumpTimingSummary(std::cerr);

        return retval;
}