test-dynamic.cpp

Go to the documentation of this file.

/*
 * test-dynamic.cpp
 *
 * Copyright (C) 2010  Thomas A. Vaughan
 * All rights reserved.
 *
 * Simple test of the kdtree API - especially dynamic objects
 */

// includes --------------------------------------------------------------------
#include "common/wave_ex.h"
#include "kdtree/kdtree.h"
#include "perf/perf.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 - size);
        r.y0 = bounds.y0 + getRandom(bounds.y1 - bounds.y0 - size);
        r.z0 = bounds.z0 + getRandom(bounds.z1 - bounds.z0 - 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 int
popAllDynamicEntries
(
IN kdtree::Node * node
)
{
        int count = 0;

        // pop all locally
        while (smart_ptr<kdtree::Node::dynamic_entry_t> pde =
               node->popDynamicEntry()) {
                ++count;
        }

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

        if (left) {
                count += popAllDynamicEntries(left);
        }
        if (right) {
                count += popAllDynamicEntries(right);
        }

        return count;
}


static void
doTest1
(
IN int nCount,
IN int subdivide
)
{
        perf::Timer timer("doTest1");
        ASSERT(nCount > 0, "bad count: %d", nCount);
        ASSERT(subdivide > 0, "Bad subdivide: %d", subdivide);

        rect3d_t bounds;

        DPRINTF(
            "Running test 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);
                //e.bounds.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);

        // now add dynamic objects
        DPRINTF("Adding %d dynamic objects", nCount);
        for (int i = 0; i < nCount; ++i) {
                smart_ptr<kdtree::Node::dynamic_entry_t> pde =
                    new kdtree::Node::dynamic_entry_t;
                ASSERT(pde, "out of memory");

                getRandomRect(bounds, 1.0 + getRandom(4.0), pde->rect);

                root->addDynamicEntry(pde);
        }

        // walk tree and get all dynamic entries
        int popped = popAllDynamicEntries(root);
        DPRINTF("Popped %d dynamic entries", popped);
        ASSERT_THROW(popped == nCount, "should have popped as many as added");

        // pop again on an empty tree
        ASSERT_THROW(0 == popAllDynamicEntries(root),
            "Should not have found any dynamic entries remaining");
}



////////////////////////////////////////////////////////////////////////////////
//
//      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");

                doTest1(nCount, nDivide);

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

        perf::dumpTimingSummary(std::cerr);

        return retval;
}