lib/kdtree/test/test.cpp

Go to the documentation of this file.

/*
 * test.cpp
 *
 * Copyright (C) 2009  Thomas A. Vaughan
 * All rights reserved.
 *
 * Simple test of the kdtree API
 */

// 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 0.99 * (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 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);
}



static void
verifyFound
(
IN kdtree::Node * root,
IN const rect3d_t& r,
IN void * magic,
IN kdtree::eAction expect,
IN const char * msg
)
{
        ASSERT(root, "null");
        ASSERT(r.isValid(), "invalid");
        ASSERT(magic, "null");
        ASSERT(kdtree::eAction_Invalid != expect, "bad expect");

        // construct timer name
        std::string timerName = "search:";
        timerName += msg;

        // search (wrap with timer)
        kdtree::eAction act = kdtree::eAction_Invalid;
        {
                perf::Timer timer(timerName.c_str());
                act = root->iterateStaticEntries(r, findCallback, magic);
        }

        if (act != expect) {
                WAVE_EX(wex);
                wex << "Failed when iterating for known entry: " << msg;
        }
}



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

        rect3d_t bounds;
        const float max = s_max;

        bounds.x0 = -max;               bounds.x1 = +max;
        bounds.y0 = -max;               bounds.y1 = +max;
        bounds.z0 = -max;               bounds.z1 = +max;

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

        // add a bunch of random rects
        for (int i = 0; i < nCount; ++i) {
                smart_ptr<kdtree::Entry> e;
                rect3d_t r;
                getRandomRect(bounds, 10, r);
                root->addStaticEntry(e, r);
        }

        // create good and bad rects
        rect3d_t good;
        good.x0 = 0.0;          good.x1 = 20.0;
        good.y0 = 0.0;          good.y1 = 20.0;
        good.z0 = 0.0;          good.z1 = 20.0;

        rect3d_t bad;
        bad.x0 = 30.0;          bad.x1 = 70.0;
        bad.y0 = 30.0;          bad.y1 = 70.0;
        bad.z0 = 30.0;          bad.z1 = 70.0;

        // add a specific rect (in good rect)
        smart_ptr<kdtree::Entry> e = new Test;
        void * magic = (kdtree::Entry *) e;
        ASSERT(e, "out of memory");
        root->addStaticEntry(e, good);

        // iterate over everything, make sure we find it
        verifyFound(root, bounds, magic, kdtree::eAction_Halt,
            "full bounds");

        // iterate over good rect, make sure we find it
        verifyFound(root, good, magic, kdtree::eAction_Halt,
            "limited bounds");

        // iterate over bad rect, make sure we do NOT find it
        verifyFound(root, bad, magic, kdtree::eAction_Continue,
            "improper bounds");

        // remove it!
        int total = root->getStaticEntryCount();
        DPRINTF("%d total entries in kd-tree", total);
        kdtree::eAction act = kdtree::eAction_Invalid;
        {
                perf::Timer timer("iteration:removal");
                act = root->iterateStaticEntries(good, removeCallback, magic);
        }
        if (kdtree::eAction_Halt != act) {
                WAVE_EX(wex);
                wex << "Failed to find + remove known entry";
        }
        int newTotal = root->getStaticEntryCount();
        DPRINTF("%d entries in kd-tree after removal", newTotal);
        if (total - 1 != newTotal) {
                WAVE_EX(wex);
                wex << "Should have one less entry in kd-tree";
        }

        // verify it is gone
        verifyFound(root, good, magic, kdtree::eAction_Continue,
            "good bounds, gone");
}



////////////////////////////////////////////////////////////////////////////////
//
//      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);
                doTest2(nCount, nDivide);

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

        perf::dumpTimingSummary(std::cerr);

        return retval;
}