Visualization Library v1.0.3A lightweight C++ OpenGL middleware for 2D/3D graphics |
[Download] [Tutorials] [All Classes] [Grouped Classes] |
00001 /**************************************************************************************/ 00002 /* */ 00003 /* Visualization Library */ 00004 /* http://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 //-----------------------------------------------------------------------------