00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
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
00042
00043 bool sortX(const ref<Actor>& a1, const ref<Actor>& a2)
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
00051
00052 bool sortY(const ref<Actor>& a1, const ref<Actor>& a2)
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
00060
00061 bool sortZ(const ref<Actor>& a1, const ref<Actor>& a2)
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