lib/kdtree/test/test.cpp

Go to the documentation of this file.
00001 /*
00002  * test.cpp
00003  *
00004  * Copyright (C) 2009  Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  * Simple test of the kdtree API
00008  */
00009 
00010 // includes --------------------------------------------------------------------
00011 #include "common/wave_ex.h"
00012 #include "kdtree/kdtree.h"
00013 #include "perf/perf.h"
00014 
00015 #include <iostream>
00016 
00017 
00018 
00019 static const float s_max                        = 5000.0;
00020 
00021 
00022 ////////////////////////////////////////////////////////////////////////////////
00023 //
00024 //      static helper methods
00025 //
00026 ////////////////////////////////////////////////////////////////////////////////
00027 
00028 class Test : public kdtree::Entry {
00029 public:
00030         ~Test(void) throw() { }
00031 };
00032 
00033 
00034 static float
00035 getRandom
00036 (
00037 IN float q
00038 )
00039 {
00040         ASSERT(q > 0, "bad q: %f", q);
00041 
00042         return 0.99 * (q * rand()) / RAND_MAX;
00043 }
00044 
00045 
00046 
00047 static void
00048 getRandomRect
00049 (
00050 IN const rect3d_t& bounds,
00051 IN float size,
00052 OUT rect3d_t& r
00053 )
00054 {
00055         ASSERT(bounds.isValid(), "invalid");
00056 
00057         r.x0 = bounds.x0 + getRandom(bounds.x1 - bounds.x0 - size);
00058         r.y0 = bounds.y0 + getRandom(bounds.y1 - bounds.y0 - size);
00059         r.z0 = bounds.z0 + getRandom(bounds.z1 - bounds.z0 - size);
00060 
00061         r.x1 = r.x0 + size;
00062         r.y1 = r.y0 + size;
00063         r.z1 = r.z0 + size;
00064 }
00065 
00066 
00067 
00068 static kdtree::eAction
00069 countCallback
00070 (
00071 IN void * context,
00072 IN kdtree::Entry * e,
00073 IN const rect3d_t& r
00074 )
00075 {
00076         long * pCount = (long *) context;
00077         ASSERT(pCount, "null context?");
00078 
00079         *pCount = (*pCount) + 1;
00080 
00081         return kdtree::eAction_Continue;
00082 }
00083 
00084 
00085 /*
00086 static kdtree::eAction
00087 printCallback
00088 (
00089 IN void * context,
00090 IN kdtree::entry_t& e
00091 )
00092 {
00093         long * pCount = (long *) context;
00094         ASSERT(pCount, "null context?");
00095 
00096         DPRINTF("Found entry in search rect");
00097         e.bounds.dump("  entry bounds");
00098 
00099         *pCount = (*pCount) + 1;
00100 
00101         return kdtree::eAction_Continue;
00102 }
00103  */
00104 
00105 
00106 static kdtree::eAction
00107 findCallback
00108 (
00109 IN void * context,
00110 IN kdtree::Entry * e,
00111 IN const rect3d_t& r
00112 )
00113 {
00114         if (e == context) {
00115                 // we have a match!
00116                 return kdtree::eAction_Halt;
00117         }
00118 
00119         // not a match...
00120         return kdtree::eAction_Continue;
00121 }
00122 
00123 
00124 
00125 static kdtree::eAction
00126 removeCallback
00127 (
00128 IN void * context,
00129 IN kdtree::Entry * e,
00130 IN const rect3d_t& r
00131 )
00132 {
00133         if (e == context) {
00134                 // matches!
00135                 return (kdtree::eAction)
00136                     (kdtree::eAction_Remove | kdtree::eAction_Halt);
00137         }
00138 
00139         // not a match...
00140         return kdtree::eAction_Continue;
00141 }
00142 
00143 
00144 
00145 static void
00146 doTest1
00147 (
00148 IN int nCount,
00149 IN int subdivide
00150 )
00151 {
00152         perf::Timer timer("doTest1");
00153         ASSERT(nCount > 0, "bad count: %d", nCount);
00154         ASSERT(subdivide > 0, "Bad subdivide: %d", subdivide);
00155 
00156         rect3d_t bounds;
00157 
00158         DPRINTF(
00159             "Running test with %d entries, subdivide at %d entries per node",
00160             nCount, subdivide);
00161 
00162         bounds.x0 = -s_max;
00163         bounds.x1 = +s_max;
00164         bounds.y0 = -(s_max / 2.5);
00165         bounds.y1 = +(s_max / 2.5);
00166         bounds.z0 = -(s_max / 5);
00167         bounds.z1 = +(s_max / 5);
00168         //bounds.dump("bounds");
00169 
00170         smart_ptr<kdtree::Node> root = kdtree::Node::create(bounds);
00171         ASSERT(root, "failed to create root node");
00172 
00173         for (int i = 0; i < nCount; ++i) {
00174                 rect3d_t r;
00175                 getRandomRect(bounds, getRandom(10), r);
00176                 //e.bounds.dump("  adding");
00177                 smart_ptr<kdtree::Entry> e;
00178 
00179                 {
00180                         perf::Timer timer("addEntry");
00181                         root->addStaticEntry(e, r);
00182                 }
00183         }
00184 
00185         DPRINTF("Tree depth: %d", root->getTreeDepth());
00186         DPRINTF("Node count: %d", root->getNodeCount());
00187         DPRINTF("Entry count: %d", root->getStaticEntryCount());
00188         if (root->getStaticEntryCount() != nCount) {
00189                 WAVE_EX(wex);
00190                 wex << "Count of entries in tree does not match what was added";
00191         }
00192 
00193         // okay, subdivide
00194         DPRINTF("Subdividing...");
00195         {
00196                 perf::Timer timer("subdivide");
00197                 root->subdivide(kdtree::eStrategy_Naive, subdivide);
00198         }
00199         DPRINTF("Tree depth: %d", root->getTreeDepth());
00200         DPRINTF("Node count: %d", root->getNodeCount());
00201         DPRINTF("Entry count: %d", root->getStaticEntryCount());
00202 
00203         long count = 0;
00204         {
00205                 perf::Timer timer("full iteration");
00206                 root->iterateStaticEntries(bounds, countCallback, (void *) &count);
00207         }
00208         if (count != nCount) {
00209                 WAVE_EX(wex);
00210                 wex << "Iteration should return all entities!";
00211         }
00212 
00213         rect3d_t sub;
00214         getRandomRect(bounds, 1000, sub);
00215         sub.dump("Search rect");
00216         count = 0;
00217         {
00218                 // warning: don't use the print callback here, it is slow
00219                 //      (writing to console)
00220                 perf::Timer timer("sub iteration");
00221                 root->iterateStaticEntries(sub, countCallback, (void *) &count);
00222         }
00223         DPRINTF("Found %ld entries in sub rect", count);
00224 }
00225 
00226 
00227 
00228 static void
00229 verifyFound
00230 (
00231 IN kdtree::Node * root,
00232 IN const rect3d_t& r,
00233 IN void * magic,
00234 IN kdtree::eAction expect,
00235 IN const char * msg
00236 )
00237 {
00238         ASSERT(root, "null");
00239         ASSERT(r.isValid(), "invalid");
00240         ASSERT(magic, "null");
00241         ASSERT(kdtree::eAction_Invalid != expect, "bad expect");
00242 
00243         // construct timer name
00244         std::string timerName = "search:";
00245         timerName += msg;
00246 
00247         // search (wrap with timer)
00248         kdtree::eAction act = kdtree::eAction_Invalid;
00249         {
00250                 perf::Timer timer(timerName.c_str());
00251                 act = root->iterateStaticEntries(r, findCallback, magic);
00252         }
00253 
00254         if (act != expect) {
00255                 WAVE_EX(wex);
00256                 wex << "Failed when iterating for known entry: " << msg;
00257         }
00258 }
00259 
00260 
00261 
00262 static void
00263 doTest2
00264 (
00265 IN int nCount,
00266 IN int subdivide
00267 )
00268 {
00269         perf::Timer timer("doTest2");
00270         ASSERT(nCount > 0, "bad count: %d", nCount);
00271         ASSERT(subdivide > 0, "bad subdivide: %d", subdivide);
00272 
00273         rect3d_t bounds;
00274         const float max = s_max;
00275 
00276         bounds.x0 = -max;               bounds.x1 = +max;
00277         bounds.y0 = -max;               bounds.y1 = +max;
00278         bounds.z0 = -max;               bounds.z1 = +max;
00279 
00280         // create tree (root)
00281         smart_ptr<kdtree::Node> root = kdtree::Node::create(bounds);
00282         ASSERT(root, "failed to create kd-tree");
00283 
00284         // add a bunch of random rects
00285         for (int i = 0; i < nCount; ++i) {
00286                 smart_ptr<kdtree::Entry> e;
00287                 rect3d_t r;
00288                 getRandomRect(bounds, 10, r);
00289                 root->addStaticEntry(e, r);
00290         }
00291 
00292         // create good and bad rects
00293         rect3d_t good;
00294         good.x0 = 0.0;          good.x1 = 20.0;
00295         good.y0 = 0.0;          good.y1 = 20.0;
00296         good.z0 = 0.0;          good.z1 = 20.0;
00297 
00298         rect3d_t bad;
00299         bad.x0 = 30.0;          bad.x1 = 70.0;
00300         bad.y0 = 30.0;          bad.y1 = 70.0;
00301         bad.z0 = 30.0;          bad.z1 = 70.0;
00302 
00303         // add a specific rect (in good rect)
00304         smart_ptr<kdtree::Entry> e = new Test;
00305         void * magic = (kdtree::Entry *) e;
00306         ASSERT(e, "out of memory");
00307         root->addStaticEntry(e, good);
00308 
00309         // iterate over everything, make sure we find it
00310         verifyFound(root, bounds, magic, kdtree::eAction_Halt,
00311             "full bounds");
00312 
00313         // iterate over good rect, make sure we find it
00314         verifyFound(root, good, magic, kdtree::eAction_Halt,
00315             "limited bounds");
00316 
00317         // iterate over bad rect, make sure we do NOT find it
00318         verifyFound(root, bad, magic, kdtree::eAction_Continue,
00319             "improper bounds");
00320 
00321         // remove it!
00322         int total = root->getStaticEntryCount();
00323         DPRINTF("%d total entries in kd-tree", total);
00324         kdtree::eAction act = kdtree::eAction_Invalid;
00325         {
00326                 perf::Timer timer("iteration:removal");
00327                 act = root->iterateStaticEntries(good, removeCallback, magic);
00328         }
00329         if (kdtree::eAction_Halt != act) {
00330                 WAVE_EX(wex);
00331                 wex << "Failed to find + remove known entry";
00332         }
00333         int newTotal = root->getStaticEntryCount();
00334         DPRINTF("%d entries in kd-tree after removal", newTotal);
00335         if (total - 1 != newTotal) {
00336                 WAVE_EX(wex);
00337                 wex << "Should have one less entry in kd-tree";
00338         }
00339 
00340         // verify it is gone
00341         verifyFound(root, good, magic, kdtree::eAction_Continue,
00342             "good bounds, gone");
00343 }
00344 
00345 
00346 
00347 ////////////////////////////////////////////////////////////////////////////////
00348 //
00349 //      entry point
00350 //
00351 ////////////////////////////////////////////////////////////////////////////////
00352 
00353 int
00354 main
00355 (
00356 IN int argc,
00357 IN const char * argv[]
00358 )
00359 {
00360         int nCount = 50 * 1000;
00361         int nDivide = 32;
00362         if (argc > 1) {
00363                 nCount = atoi(argv[1]);
00364         } else {
00365                 DPRINTF("No count provided, so using count = %d", nCount);
00366         }
00367         if (argc > 2) {
00368                 nDivide = atoi(argv[2]);
00369         } else {
00370                 DPRINTF("No subdivide threshold specified, using %d", nDivide);
00371         }
00372         int retval = 0;
00373 
00374         try {
00375                 perf::Timer timer("Total test time");
00376 
00377                 doTest1(nCount, nDivide);
00378                 doTest2(nCount, nDivide);
00379 
00380         } catch (std::exception& e) {
00381                 DPRINTF("Exception: %s", e.what());
00382                 retval = 1;
00383         }
00384 
00385         perf::dumpTimingSummary(std::cerr);
00386 
00387         return retval;
00388 }
00389