Visualization Library

A lightweight C++ OpenGL middleware for 2D/3D graphics
[Home] [Tutorials] [All Classes] [Grouped Classes]

X:/dropbox/visualizationlibrary/src/vlGraphics/ActorKdTree.cpp

Go to the documentation of this file.
00001 /**************************************************************************************/
00002 /*                                                                                    */
00003 /*  Visualization Library                                                             */
00004 /*  http://www.visualizationlibrary.org                                               */
00005 /*                                                                                    */
00006 /*  Copyright (c) 2005-2010, Michele Bosi                                             */
00007 /*  All rights reserved.                                                              */
00008 /*                                                                                    */
00009 /*  Redistribution and use in source and binary forms, with or without modification,  */
00010 /*  are permitted provided that the following conditions are met:                     */
00011 /*                                                                                    */
00012 /*  - Redistributions of source code must retain the above copyright notice, this     */
00013 /*  list of conditions and the following disclaimer.                                  */
00014 /*                                                                                    */
00015 /*  - Redistributions in binary form must reproduce the above copyright notice, this  */
00016 /*  list of conditions and the following disclaimer in the documentation and/or       */
00017 /*  other materials provided with the distribution.                                   */
00018 /*                                                                                    */
00019 /*  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND   */
00020 /*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED     */
00021 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE            */
00022 /*  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR  */
00023 /*  ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES    */
00024 /*  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;      */
00025 /*  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON    */
00026 /*  ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT           */
00027 /*  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS     */
00028 /*  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.                      */
00029 /*                                                                                    */
00030 /**************************************************************************************/
00031 
00032 #include <vlGraphics/ActorKdTree.hpp>
00033 #include <vlCore/Log.hpp>
00034 #include <algorithm>
00035 
00036 using namespace vl;
00037 
00038 namespace
00039 {
00040   //-----------------------------------------------------------------------------
00041   // sortX
00042   //-----------------------------------------------------------------------------
00043   bool sortX(const ref<Actor>& a1, const ref<Actor>& a2) /*const*/
00044   {
00045     VL_CHECK(a1->lod(0))
00046     VL_CHECK(a2->lod(0))
00047     return a1->boundingBox().minCorner().x() < a2->boundingBox().minCorner().x();
00048   }
00049   //-----------------------------------------------------------------------------
00050   // sortY
00051   //-----------------------------------------------------------------------------
00052   bool sortY(const ref<Actor>& a1, const ref<Actor>& a2) /*const*/
00053   {
00054     VL_CHECK(a1->lod(0))
00055     VL_CHECK(a2->lod(0))
00056     return a1->boundingBox().minCorner().y() < a2->boundingBox().minCorner().y();
00057   }
00058   //-----------------------------------------------------------------------------
00059   // sortZ
00060   //-----------------------------------------------------------------------------
00061   bool sortZ(const ref<Actor>& a1, const ref<Actor>& a2) /*const*/
00062   {
00063     VL_CHECK(a1->lod(0))
00064     VL_CHECK(a2->lod(0))
00065     return a1->boundingBox().minCorner().z() < a2->boundingBox().minCorner().z();
00066   }
00067 }
00068 
00069 //-----------------------------------------------------------------------------
00070 ref<ActorKdTree> ActorKdTree::kdtreeFromNonLeafyActors(int max_depth, float minimum_volume)
00071 {
00072   ActorCollection acts;
00073   harvestNonLeafActors(acts);
00074   ref<ActorKdTree> newtree = new ActorKdTree;
00075   newtree->buildKdTree(acts, max_depth, minimum_volume);
00076   return newtree;
00077 }
00078 //-----------------------------------------------------------------------------
00079 void ActorKdTree::harvestNonLeafActors(ActorCollection& acts)
00080 {
00081   VL_CHECK( (actors()->size() && (mChildN == 0 && mChildP == 0)) || !(mChildN == 0 && mChildP == 0) );
00082 
00083   if ( mChildN || mChildP )
00084   {
00085     for(int i=0; i<(int)actors()->size(); ++i)
00086       acts.push_back(actors()->at(i));
00087     actors()->clear();
00088   }
00089 
00090   if(mChildN) childN()->harvestNonLeafActors( acts );
00091   if(mChildP) childP()->harvestNonLeafActors( acts );
00092 }
00093 //-----------------------------------------------------------------------------
00094 void ActorKdTree::computeLocalAABB(const ActorCollection& acts)
00095 {
00096   mAABB.setNull();
00097   for(int i=0; i<(int)acts.size(); ++i)
00098   {
00099     VL_CHECK( acts[i]->lod(0) )
00100     mAABB += acts[i]->boundingBox();
00101   }
00102 }
00103 //-----------------------------------------------------------------------------
00104 void ActorKdTree::buildKdTree(ActorCollection& acts, int max_depth, float minimum_volume)
00105 {
00106   int counter = 0;
00107   prepareActors(acts);
00108   compileTree_internal(acts, counter, max_depth, minimum_volume);
00109 }
00110 //-----------------------------------------------------------------------------
00111 void ActorKdTree::rebuildKdTree(int max_depth, float minimum_volume)
00112 {
00113   ActorCollection acts;
00114   extractActors(acts);
00115   buildKdTree(acts, max_depth, minimum_volume);
00116 }
00117 //-----------------------------------------------------------------------------
00118 void ActorKdTree::compileTree_internal(ActorCollection& acts, int& counter, int max_depth, float minimum_volume)
00119 {
00120   mChildN = NULL;
00121   mChildP = NULL;
00122   actors()->clear();
00123   mAABB.setNull();
00124   mPlane = Plane();
00125 
00126   if (acts.size() == 0)
00127     return;
00128 
00129   computeLocalAABB(acts);
00130 
00131   if (acts.size() == 1 || max_depth == 0 || mAABB.volume() < minimum_volume)
00132   {
00133     mActors = acts;
00134     return;
00135   }
00136 
00137   if ( !findBestPlane(mPlane, counter, acts) )
00138   {
00139     mActors = acts;
00140     return;
00141   }
00142 
00143   ActorCollection actorsN;
00144   ActorCollection actorsP;
00145   actorsN.reserve(acts.size());
00146   actorsP.reserve(acts.size());
00147 
00148   for(int i=0; i<(int)acts.size(); ++i)
00149   {
00150     VL_CHECK(acts[i]->lod(0))
00151     switch( mPlane.classify(acts[i]->boundingBox()) )
00152     {
00153     case  0: actors()->push_back(acts[i].get()); break;
00154     case -1: actorsN.  push_back(acts[i].get()); break;
00155     case +1: actorsP.  push_back(acts[i].get()); break;
00156     }    
00157   }
00158 
00159   int counter1 = counter;
00160   int counter2 = counter;
00161   if (actorsN.size())
00162   {
00163     setChildN(new ActorKdTree);
00164     childN()->compileTree_internal(actorsN, counter1, max_depth-1, minimum_volume);
00165   }
00166 
00167   if (actorsP.size())
00168   {
00169     setChildP(new ActorKdTree);
00170     childP()->compileTree_internal(actorsP, counter2, max_depth-1, minimum_volume);
00171   }
00172 
00173 }
00174 //-----------------------------------------------------------------------------
00175 int ActorKdTree::scorePlane(const Plane& plane, const ActorCollection& acts)
00176 {
00177   int cN=0, cC=0, cP=0;
00178   for(int i=0; i<(int)acts.size(); ++i)
00179   {
00180     VL_CHECK(acts[i]->lod(0))
00181     switch( plane.classify(acts[i]->boundingBox()) )
00182     {
00183     case -1: cN++; break;
00184     case 0:  cC++; break;
00185     case +1: cP++; break;
00186     }
00187   }
00188   return cC + ::abs(cN-cP);
00189 }
00190 //-----------------------------------------------------------------------------
00192 bool ActorKdTree::findBestPlane(Plane& plane, int& counter, ActorCollection& acts)
00193 {
00194   int median = (int)acts.size() / 2;
00195   if (counter%3 == 0)
00196   {
00197     std::sort(acts.vector().begin(), acts.vector().end(), sortX);
00198     VL_CHECK(acts[median]->lod(0))
00199     plane = Plane(acts[median]->boundingBox().minCorner().x(), vec3(1,0,0));
00200     counter++;
00201     if (scorePlane(plane, acts) == (int)acts.size())
00202     {
00203       std::sort(acts.vector().begin(), acts.vector().end(), sortY);
00204       VL_CHECK(acts[median]->lod(0))
00205       plane = Plane(acts[median]->boundingBox().minCorner().y(), vec3(0,1,0));
00206       counter++;
00207       if (scorePlane(plane, acts) == (int)acts.size())
00208       {
00209         std::sort(acts.vector().begin(), acts.vector().end(), sortZ);
00210         VL_CHECK(acts[median]->lod(0))
00211         plane = Plane(acts[median]->boundingBox().minCorner().z(), vec3(0,0,1));
00212         counter++;
00213         if (scorePlane(plane, acts) == (int)acts.size())
00214           return false;
00215       }
00216     }
00217   }
00218   else
00219   if (counter%3 == 1)
00220   {
00221     std::sort(acts.vector().begin(), acts.vector().end(), sortY);
00222     VL_CHECK(acts[median]->lod(0))
00223     plane = Plane(acts[median]->boundingBox().minCorner().y(), vec3(0,1,0));
00224     counter++;
00225     if (scorePlane(plane, acts) == (int)acts.size())
00226     {
00227       std::sort(acts.vector().begin(), acts.vector().end(), sortZ);
00228       VL_CHECK(acts[median]->lod(0))
00229       plane = Plane(acts[median]->boundingBox().minCorner().z(), vec3(0,0,1));
00230       counter++;
00231       if (scorePlane(plane, acts) == (int)acts.size())
00232       {
00233         std::sort(acts.vector().begin(), acts.vector().end(), sortX);
00234         VL_CHECK(acts[median]->lod(0))
00235         plane = Plane(acts[median]->boundingBox().minCorner().x(), vec3(1,0,0));
00236         counter++;
00237         if (scorePlane(plane, acts) == (int)acts.size())
00238           return false;
00239       }
00240     }
00241   }
00242   else
00243   if (counter%3 == 2)
00244   {
00245     std::sort(acts.vector().begin(), acts.vector().end(), sortZ);
00246     VL_CHECK(acts[median]->lod(0))
00247     plane = Plane(acts[median]->boundingBox().minCorner().z(), vec3(0,0,1));
00248     counter++;
00249     if (scorePlane(plane, acts) == (int)acts.size())
00250     {
00251       std::sort(acts.vector().begin(), acts.vector().end(), sortX);
00252       VL_CHECK(acts[median]->lod(0))
00253       plane = Plane(acts[median]->boundingBox().minCorner().x(), vec3(1,0,0));
00254       counter++;
00255       if (scorePlane(plane, acts) == (int)acts.size())
00256       {
00257         std::sort(acts.vector().begin(), acts.vector().end(), sortY);
00258         VL_CHECK(acts[median]->lod(0))
00259         plane = Plane(acts[median]->boundingBox().minCorner().y(), vec3(0,1,0));
00260         counter++;
00261         if (scorePlane(plane, acts) == (int)acts.size())
00262           return false;
00263       }
00264     }
00265   }
00266   return true;
00267 }
00268 //-----------------------------------------------------------------------------
00269 ActorKdTree* ActorKdTree::insertActor(Actor* actor)
00270 {
00271   VL_CHECK(actor->lod(0))
00272   if (childN() == 0 && childP() == 0)
00273     actors()->push_back(actor);
00274   else
00275   {
00276     switch( mPlane.classify(actor->boundingBox()) )
00277     {
00278       case -1: if (!childN()) setChildN(new ActorKdTree); return childN()->insertActor(actor);
00279       case 0:  actors()->push_back(actor); break;
00280       case +1: if (!childP()) setChildP(new ActorKdTree); return childP()->insertActor(actor);
00281     }
00282   }
00283   return this;
00284 }
00285 //-----------------------------------------------------------------------------
00286 int ActorKdTree::childrenCount() const
00287 {
00288   if (mChildN && mChildP)
00289     return 2;
00290   else
00291   if (mChildN || mChildP)
00292     return 1;
00293   else
00294     return 0;
00295 }
00296 //-----------------------------------------------------------------------------
00297 ActorTreeAbstract* ActorKdTree::child(int i)
00298 {
00299   if (i == 0)
00300     return mChildN ? mChildN.get() : mChildP.get();
00301   else
00302   if (i == 1)
00303     return mChildP.get();
00304   else
00305   {
00306     vl::Log::error( "ActorKdTree::child(int): bad child node requested, a ActorKdTree can have only 2 child nodes.\n" );
00307     return NULL;
00308   }
00309 }
00310 //-----------------------------------------------------------------------------
00311 const ActorTreeAbstract* ActorKdTree::child(int i) const
00312 {
00313   if (i == 0)
00314     return mChildN ? mChildN.get() : mChildP.get();
00315   else
00316   if (i == 1)
00317     return mChildP.get();
00318   else
00319   {
00320     vl::Log::error( "ActorKdTree::child(int): bad child node requested, a ActorKdTree can have only 2 child nodes.\n" );
00321     return NULL;
00322   }
00323 }
00324 //-----------------------------------------------------------------------------

Visualization Library 2011.09.1160 Reference Documentation
Copyright 2005-2011 Michele Bosi. All rights reserved.
Updated on Thu May 2 2013 13:40:34.
Permission is granted to use this page to write and publish articles regarding Visualization Library.