[1163] | 1 | /*
|
---|
| 2 | -----------------------------------------------------------------------------
|
---|
| 3 | This source file is part of the GameTools Project
|
---|
| 4 | http://www.gametools.org
|
---|
| 5 |
|
---|
| 6 | Author: Martin Szydlowski
|
---|
| 7 | -----------------------------------------------------------------------------
|
---|
| 8 | */
|
---|
| 9 |
|
---|
| 10 | #include <OgreCamera.h>
|
---|
| 11 | #include "OgreKdTree.h"
|
---|
| 12 | #include "OgreKdRenderable.h"
|
---|
| 13 | #include "OgreKdTreeSceneNode.h"
|
---|
| 14 | #include "OgreKdTreeSceneManager.h"
|
---|
| 15 |
|
---|
| 16 | #include <OgreStringConverter.h>
|
---|
| 17 | #include <OgreLogManager.h>
|
---|
| 18 | #include <OgreRoot.h>
|
---|
| 19 | #include <OgreTimer.h>
|
---|
| 20 |
|
---|
| 21 | #include <OgreMaterialManager.h>
|
---|
| 22 |
|
---|
| 23 | #define KDTREE_LOGNAME "KdTreeBuild.log"
|
---|
| 24 |
|
---|
| 25 | namespace Ogre
|
---|
| 26 | {
|
---|
| 27 | Real PlaneEvent::KT = 2.0;
|
---|
| 28 | Real PlaneEvent::KI = 1.0;
|
---|
| 29 |
|
---|
| 30 | void PlaneEvent::classify(const PlaneEvent& e, PlaneEvent::Side side)
|
---|
| 31 | {
|
---|
| 32 | // only classify events of the same dimension
|
---|
| 33 | if (mDimension == e.mDimension)
|
---|
| 34 | {
|
---|
| 35 | if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
|
---|
| 36 | {
|
---|
| 37 | mRenderable->setSide(PES_LEFT);
|
---|
| 38 | }
|
---|
| 39 | else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
|
---|
| 40 | {
|
---|
| 41 | mRenderable->setSide(PES_RIGHT);
|
---|
| 42 | }
|
---|
| 43 | else if (mType == PET_ON)
|
---|
| 44 | {
|
---|
| 45 | if (mPosition[mDimension] < e.mPosition[e.mDimension] ||
|
---|
| 46 | (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
|
---|
| 47 | {
|
---|
| 48 | mRenderable->setSide(PES_LEFT);
|
---|
| 49 | }
|
---|
| 50 | if (mPosition[mDimension] > e.mPosition[e.mDimension] ||
|
---|
| 51 | (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
|
---|
| 52 | {
|
---|
| 53 | mRenderable->setSide(PES_RIGHT);
|
---|
| 54 | }
|
---|
| 55 | }
|
---|
| 56 | }
|
---|
| 57 | }
|
---|
| 58 |
|
---|
| 59 | PlaneEvent PlaneEvent::clip(AxisAlignedBox& box, PlaneEvent::Dimension dim)
|
---|
| 60 | {
|
---|
| 61 | Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
|
---|
| 62 | if (newpos[dim] < min[dim])
|
---|
| 63 | newpos[dim] = min[dim];
|
---|
| 64 | else if (newpos[dim] > max[dim])
|
---|
| 65 | newpos[dim] = max[dim];
|
---|
| 66 |
|
---|
| 67 | return PlaneEvent(mRenderable, newpos, mDimension, mType);
|
---|
| 68 | }
|
---|
| 69 |
|
---|
| 70 | void PlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split)
|
---|
| 71 | {
|
---|
| 72 |
|
---|
| 73 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 74 | Real mu = splitBox(parent, split.bleft, split.bright);
|
---|
| 75 | Real sav = surfaceArea(parent); // optimize?? called several times for the same box
|
---|
| 76 | Real savl = surfaceArea(split.bleft);
|
---|
| 77 | Real savr = surfaceArea(split.bright);
|
---|
| 78 | Real pl = savl / sav;
|
---|
| 79 | Real pr = savr / sav;
|
---|
| 80 | Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
|
---|
| 81 | Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
|
---|
| 82 |
|
---|
| 83 | Log * log = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
|
---|
| 84 | log->logMessage("SAH: SA-parent=" + StringConverter::toString(sav) +
|
---|
| 85 | "\n\tSA-left=" + StringConverter::toString(savl) +
|
---|
| 86 | " SA-right=" + StringConverter::toString(savr) +
|
---|
| 87 | "\n\tp-left=" + StringConverter::toString(pl) +
|
---|
| 88 | " p-right=" + StringConverter::toString(pr) +
|
---|
| 89 | "\n\tmu=" + StringConverter::toString(mu) +
|
---|
| 90 | "\n\tcost-left=" + StringConverter::toString(costl) +
|
---|
| 91 | " cost-right=" + StringConverter::toString(costr));
|
---|
| 92 | #else
|
---|
| 93 | Real mu = splitBox(parent, split.bleft, split.bright);
|
---|
| 94 | Real sav = surfaceArea(parent); // optimize?? called several times for the same box
|
---|
| 95 | Real pl = surfaceArea(split.bleft) / sav;
|
---|
| 96 | Real pr = surfaceArea(split.bright) / sav;
|
---|
| 97 | Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
|
---|
| 98 | Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
|
---|
| 99 |
|
---|
| 100 | #endif
|
---|
| 101 | if (costl < costr)
|
---|
| 102 | {
|
---|
| 103 | split.cost = costl;
|
---|
| 104 | split.side = PES_LEFT;
|
---|
| 105 | split.nleft = nLeft + nPlane;
|
---|
| 106 | split.nright = nRight;
|
---|
| 107 | }
|
---|
| 108 | else
|
---|
| 109 | {
|
---|
| 110 | split.cost = costr;
|
---|
| 111 | split.side = PES_RIGHT;
|
---|
| 112 | split.nleft = nLeft;
|
---|
| 113 | split.nright = nPlane + nRight;
|
---|
| 114 |
|
---|
| 115 | }
|
---|
| 116 | split.event = *this;
|
---|
| 117 | }
|
---|
| 118 |
|
---|
| 119 | Real PlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
|
---|
| 120 | {
|
---|
| 121 | Vector3 bmin = parent.getMinimum();
|
---|
| 122 | Vector3 bmax = parent.getMaximum();
|
---|
| 123 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 124 | if(bmin[mDimension] > mPosition[mDimension] || bmax[mDimension] < mPosition[mDimension])
|
---|
| 125 | {
|
---|
| 126 | Log * log = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
|
---|
| 127 | log->logMessage("SPLITBOX SNAFU in event " + print() +
|
---|
| 128 | "\n\tmin=" + StringConverter::toString(bmin[mDimension]) +
|
---|
| 129 | " split=" + StringConverter::toString(mPosition[mDimension]) +
|
---|
| 130 | " max=" + StringConverter::toString(bmax[mDimension]));
|
---|
| 131 | }
|
---|
| 132 | #endif
|
---|
| 133 | // calculate the penalty for spliting the box that way
|
---|
| 134 | Real mu = lookupPenalty((mPosition[mDimension] - bmin[mDimension]) / (bmax[mDimension] - bmin[mDimension]));
|
---|
| 135 | // set corners which are the same as parent AABB
|
---|
| 136 | left.setMinimum(bmin);
|
---|
| 137 | right.setMaximum(bmax);
|
---|
| 138 | // modify "inner" corners
|
---|
| 139 | bmin[mDimension] = mPosition[mDimension];
|
---|
| 140 | bmax[mDimension] = mPosition[mDimension];
|
---|
| 141 | // set the corners on the split plane
|
---|
| 142 | left.setMaximum(bmax);
|
---|
| 143 | right.setMinimum(bmin);
|
---|
| 144 |
|
---|
| 145 | return mu;
|
---|
| 146 | }
|
---|
| 147 |
|
---|
| 148 | Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
|
---|
| 149 | {
|
---|
| 150 | //assert(pLeft <= 1.0 && pRight <= 1.0);
|
---|
| 151 |
|
---|
| 152 | // reward splitting off chunks of empty space
|
---|
| 153 | Real lambda = 1.0;
|
---|
| 154 | if (nLeft == 0 || nRight == 0)
|
---|
| 155 | {
|
---|
| 156 | lambda = 0.8;
|
---|
| 157 | }
|
---|
| 158 |
|
---|
| 159 | // penalize splitting off small chunks
|
---|
| 160 | Real mu = 1.0;
|
---|
| 161 | if (pLeft < 0.1 || pRight < 0.1 || pLeft > 0.9 || pRight > 0.9)
|
---|
| 162 | {
|
---|
| 163 | mu = 1.5;
|
---|
| 164 | }
|
---|
| 165 | return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
|
---|
| 166 |
|
---|
| 167 | //return lambda * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
|
---|
| 168 | }
|
---|
| 169 |
|
---|
| 170 | Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
|
---|
| 171 | {
|
---|
| 172 | //assert(pLeft <= 1.0 && pRight <= 1.0);
|
---|
| 173 |
|
---|
| 174 | // reward splitting off chunks of empty space
|
---|
| 175 | Real lambda = 1.0;
|
---|
| 176 | if (nLeft == 0 || nRight == 0)
|
---|
| 177 | {
|
---|
| 178 | lambda = 0.8;
|
---|
| 179 | }
|
---|
| 180 |
|
---|
| 181 | return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
|
---|
| 182 | }
|
---|
| 183 |
|
---|
| 184 | Real PlaneEvent::surfaceArea(const AxisAlignedBox& box)
|
---|
| 185 | {
|
---|
| 186 | Vector3 sides = box.getMaximum() - box.getMinimum();
|
---|
| 187 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 188 | if(sides.x < 0 || sides.y < 0 || sides.z < 0)
|
---|
| 189 | {
|
---|
| 190 | Log * log = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
|
---|
| 191 | log->logMessage("AABB SNAFU: x=" + StringConverter::toString(sides.x) +
|
---|
| 192 | " y=" + StringConverter::toString(sides.y) + " z=" + StringConverter::toString(sides.z) +
|
---|
| 193 | " BOX=" + StringConverter::toString(box.getMinimum()) + "," + StringConverter::toString(box.getMaximum()));
|
---|
| 194 | }
|
---|
| 195 | #endif
|
---|
| 196 | return 2 * sides.x * sides.y +
|
---|
| 197 | 2 * sides.y * sides.z +
|
---|
| 198 | 2 * sides.z * sides.x;
|
---|
| 199 | }
|
---|
| 200 |
|
---|
| 201 | void PlaneEvent::pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight, AxisAlignedBox& parentBox, SplitInfo& split)
|
---|
| 202 | {
|
---|
| 203 | Real mu = splitBox(parentBox, split.bleft, split.bright);
|
---|
| 204 | Real p = parentSA / globalSA;
|
---|
| 205 | Real pl = surfaceArea(split.bleft) / globalSA;
|
---|
| 206 | Real pr = surfaceArea(split.bright) / globalSA;
|
---|
| 207 | Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
|
---|
| 208 | Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
|
---|
| 209 |
|
---|
| 210 | if (costl < costr)
|
---|
| 211 | {
|
---|
| 212 | split.cost = costl;
|
---|
| 213 | split.side = PES_LEFT;
|
---|
| 214 | split.nleft = nLeft + nPlane;
|
---|
| 215 | split.nright = nRight;
|
---|
| 216 | }
|
---|
| 217 | else
|
---|
| 218 | {
|
---|
| 219 | split.cost = costr;
|
---|
| 220 | split.side = PES_RIGHT;
|
---|
| 221 | split.nleft = nLeft;
|
---|
| 222 | split.nright = nPlane + nRight;
|
---|
| 223 |
|
---|
| 224 | }
|
---|
| 225 | split.event = *this;
|
---|
| 226 | }
|
---|
| 227 |
|
---|
| 228 | Real PlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
|
---|
| 229 | {
|
---|
| 230 | // reward splitting off chunks of empty space
|
---|
| 231 | //Real lambda = 1.0;
|
---|
| 232 | //if (nLeft == 0 || nRight == 0)
|
---|
| 233 | //{
|
---|
| 234 | // lambda = 0.8;
|
---|
| 235 | //}
|
---|
| 236 |
|
---|
| 237 | return /* lambda * mu * */ (pParent*KT + (KI * (pLeft*nLeft + pRight*nRight)));
|
---|
| 238 | }
|
---|
| 239 |
|
---|
| 240 | #define PLT_SIZE 101
|
---|
| 241 |
|
---|
| 242 | // lookup the penalty for placing the splitting plane near to the edge of the AABB
|
---|
| 243 | // 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
|
---|
| 244 | Real PlaneEvent::lookupPenalty(Real p)
|
---|
| 245 | {
|
---|
| 246 | // precomputed table of {x^6 + 1|0 <= x <= 1}
|
---|
| 247 | static Real mPenaltyLookupTable[PLT_SIZE];
|
---|
| 248 | static bool init_done = false;
|
---|
| 249 |
|
---|
| 250 | if (!init_done)
|
---|
| 251 | {
|
---|
| 252 | Real step = 1.0 / (PLT_SIZE - 1);
|
---|
| 253 | Real x = 0.0;
|
---|
| 254 | //LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
|
---|
| 255 | for (int i = 0; i < PLT_SIZE; i++)
|
---|
| 256 | {
|
---|
| 257 | mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
|
---|
| 258 | x += step;
|
---|
| 259 | //LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
|
---|
| 260 | }
|
---|
| 261 | init_done = true;
|
---|
| 262 | //LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
|
---|
| 263 | }
|
---|
| 264 |
|
---|
| 265 | // normalize p to [0,1]
|
---|
| 266 | Real x = Math::Abs(p * 2 - 1);
|
---|
| 267 | int i = Math::IFloor(x * (PLT_SIZE - 1));
|
---|
| 268 |
|
---|
| 269 | return mPenaltyLookupTable[i];
|
---|
| 270 | }
|
---|
| 271 |
|
---|
| 272 | // DEBUG
|
---|
| 273 | String PlaneEvent::print()
|
---|
| 274 | {
|
---|
| 275 | String dim, type;
|
---|
| 276 | if (mDimension == PED_X)
|
---|
| 277 | dim = "X";
|
---|
| 278 | if (mDimension == PED_Y)
|
---|
| 279 | dim = "Y";
|
---|
| 280 | if (mDimension == PED_Z)
|
---|
| 281 | dim = "Z";
|
---|
| 282 | if (mType == PET_END)
|
---|
| 283 | type = "END ";
|
---|
| 284 | if (mType == PET_ON)
|
---|
| 285 | type = "ON ";
|
---|
| 286 | if (mType == PET_START)
|
---|
| 287 | type = "START";
|
---|
| 288 | //return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
|
---|
| 289 | return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
|
---|
| 290 | };
|
---|
| 291 |
|
---|
| 292 | String SplitInfo::print()
|
---|
| 293 | {
|
---|
| 294 | String sside;
|
---|
| 295 | if (side == PlaneEvent::PES_BOTH)
|
---|
| 296 | sside = "BOTH ";
|
---|
| 297 | if (side == PlaneEvent::PES_LEFT)
|
---|
| 298 | sside = "LEFT ";
|
---|
| 299 | if (side == PlaneEvent::PES_RIGHT)
|
---|
| 300 | sside = "RIGHT";
|
---|
| 301 | return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " +
|
---|
| 302 | StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
|
---|
| 303 | " Side: " + sside + " Event: " + event.print() + " Leftbox: " +
|
---|
| 304 | StringConverter::toString(bleft.getMinimum()) + ", " +
|
---|
| 305 | StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
|
---|
| 306 | StringConverter::toString(bright.getMinimum()) + ", " +
|
---|
| 307 | StringConverter::toString(bright.getMaximum());
|
---|
| 308 | };
|
---|
| 309 |
|
---|
| 310 | String KdTree::SplitCandidate::print()
|
---|
| 311 | {
|
---|
| 312 | String sside;
|
---|
| 313 | if (side == PlaneEvent::PES_BOTH)
|
---|
| 314 | sside = "BOTH ";
|
---|
| 315 | if (side == PlaneEvent::PES_LEFT)
|
---|
| 316 | sside = "LEFT ";
|
---|
| 317 | if (side == PlaneEvent::PES_RIGHT)
|
---|
| 318 | sside = "RIGHT";
|
---|
| 319 | return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
|
---|
| 320 | StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
|
---|
| 321 | " Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
|
---|
| 322 | best->print() + " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
|
---|
| 323 | + StringConverter::toString(aabb.getMaximum());
|
---|
| 324 |
|
---|
| 325 | };
|
---|
| 326 |
|
---|
| 327 | //----------------------------------------------------------------------------
|
---|
| 328 | //----------------------------------------------------------------------------
|
---|
| 329 | //----------------------------------------------------------------------------
|
---|
| 330 |
|
---|
| 331 | KdTree::KdTree(int maxdepth): mMaxDepth(maxdepth), mKdRoot(0), mBuildMethod(KDBM_RECURSIVE), mBuildLog(0)
|
---|
| 332 | {
|
---|
| 333 | #ifdef KDTREE_DEBUG
|
---|
| 334 | try
|
---|
| 335 | {
|
---|
| 336 | ColourValue cv(0.0, 1.0, 0.0);
|
---|
| 337 | MaterialPtr mp = MaterialManager::getSingleton().create("aabbHiLite","General");
|
---|
| 338 | mp->setSelfIllumination(cv);
|
---|
| 339 | mp->setDiffuse(cv);
|
---|
| 340 | }
|
---|
| 341 | catch (Ogre::Exception&)
|
---|
| 342 | {
|
---|
| 343 | // SO FUCKING DON'T CARE !!!
|
---|
| 344 | }
|
---|
| 345 | #endif
|
---|
| 346 | try
|
---|
| 347 | {
|
---|
| 348 | mBuildLog = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
|
---|
| 349 | }
|
---|
| 350 | catch (Exception&)
|
---|
| 351 | {
|
---|
| 352 | mBuildLog = LogManager::getSingleton().createLog(KDTREE_LOGNAME);
|
---|
| 353 | }
|
---|
| 354 | }
|
---|
| 355 |
|
---|
| 356 | KdTree::~KdTree()
|
---|
| 357 | {
|
---|
| 358 | delete mKdRoot;
|
---|
| 359 | }
|
---|
| 360 |
|
---|
| 361 | void KdTree::remove(KdRenderable * rend)
|
---|
| 362 | {
|
---|
| 363 | // DEBUG
|
---|
| 364 | //LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
|
---|
| 365 | std::queue<LeafPtr> cleanup;
|
---|
| 366 | LeafPtr leaf;
|
---|
| 367 | LeafSet ls = rend->getLeaves();
|
---|
| 368 | LeafSet::iterator it = ls.begin();
|
---|
| 369 | LeafSet::iterator end = ls.end();
|
---|
| 370 | while (it != end)
|
---|
| 371 | {
|
---|
| 372 | cleanup.push(*it);
|
---|
| 373 | it++;
|
---|
| 374 | }
|
---|
| 375 | while (!cleanup.empty())
|
---|
| 376 | {
|
---|
| 377 | leaf = cleanup.front();
|
---|
| 378 | cleanup.pop();
|
---|
| 379 | leaf->remove(rend);
|
---|
| 380 | bool gone = rend->detachFrom(leaf);
|
---|
| 381 | assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
|
---|
| 382 | //dump();
|
---|
| 383 | recDelete(leaf);
|
---|
| 384 | //dump();
|
---|
| 385 | }
|
---|
| 386 | }
|
---|
| 387 |
|
---|
| 388 | void KdTree::recDelete(KdTree::Node * node)
|
---|
| 389 | {
|
---|
| 390 | if (node == 0) // DEBUG
|
---|
| 391 | {
|
---|
| 392 | OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
|
---|
| 393 | "SNAFU while inserting KdRenderable into KdTree.",
|
---|
| 394 | "KdTree::recInsert" );
|
---|
| 395 | return;
|
---|
| 396 | }
|
---|
| 397 |
|
---|
| 398 | if (node->isEmpty())
|
---|
| 399 | {
|
---|
| 400 | if (node == mKdRoot)
|
---|
| 401 | {
|
---|
| 402 | OGRE_DELETE(mKdRoot);
|
---|
| 403 | }
|
---|
| 404 | else
|
---|
| 405 | {
|
---|
| 406 | KdTree::Branch * parent = node->mParent;
|
---|
| 407 | if (node == parent->mLeft)
|
---|
| 408 | {
|
---|
| 409 | OGRE_DELETE(parent->mLeft);
|
---|
| 410 | }
|
---|
| 411 | else if (node == parent->mRight)
|
---|
| 412 | {
|
---|
| 413 | OGRE_DELETE(parent->mRight);
|
---|
| 414 | }
|
---|
| 415 | recDelete(parent);
|
---|
| 416 | }
|
---|
| 417 | }
|
---|
| 418 | }
|
---|
| 419 |
|
---|
| 420 | void KdTree::insert(KdRenderable * rend)
|
---|
| 421 | {
|
---|
| 422 | // make sure the tree exists
|
---|
| 423 | if (mKdRoot)
|
---|
| 424 | {
|
---|
| 425 | // make sure the renderable is inside the world bounding box
|
---|
| 426 | AxisAlignedBox aabb = rend->getBoundingBox();
|
---|
| 427 | AxisAlignedBox isect = mKdRoot->mAABB.intersection(aabb);
|
---|
| 428 | if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
|
---|
| 429 | {
|
---|
| 430 | recInsert(mKdRoot, rend);
|
---|
| 431 | }
|
---|
| 432 | else
|
---|
| 433 | {
|
---|
| 434 | //LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
|
---|
| 435 | KdRenderableList nodelist;
|
---|
| 436 | nodelist.push_back(rend);
|
---|
| 437 | addRendToList(mKdRoot, nodelist);
|
---|
| 438 | OGRE_DELETE(mKdRoot);
|
---|
| 439 | mKdRoot = buildFromList(nodelist, 0, AxisAlignedBox());
|
---|
| 440 | }
|
---|
| 441 | }
|
---|
| 442 | // otherwise build a new one
|
---|
| 443 | else
|
---|
| 444 | {
|
---|
| 445 | build(rend);
|
---|
| 446 | }
|
---|
| 447 | }
|
---|
| 448 |
|
---|
| 449 | void KdTree::recInsert(KdTree::Node * node, KdRenderable * rend)
|
---|
| 450 | {
|
---|
| 451 | if (node == 0) // DEBUG
|
---|
| 452 | {
|
---|
| 453 | OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
|
---|
| 454 | "SNAFU while inserting KdRenderable into KdTree.",
|
---|
| 455 | "KdTree::recInsert" );
|
---|
| 456 | return;
|
---|
| 457 | }
|
---|
| 458 |
|
---|
| 459 | // rebuild the leaf/replace with subtree ...
|
---|
| 460 | if (node->isLeaf())
|
---|
| 461 | {
|
---|
| 462 | //LogManager::getSingleton().logMessage("## Replacing leaf.");
|
---|
| 463 | rebuildSubtree(node, rend);
|
---|
| 464 | }
|
---|
| 465 | else
|
---|
| 466 | {
|
---|
[1170] | 467 | KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
|
---|
[1163] | 468 | AxisAlignedBox aabb = rend->getBoundingBox();
|
---|
| 469 | Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
|
---|
| 470 | Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
|
---|
| 471 | if (smin == smax)
|
---|
| 472 | {
|
---|
| 473 | if (smax == Plane::NEGATIVE_SIDE ||
|
---|
| 474 | (smax == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_LEFT))
|
---|
| 475 | {
|
---|
| 476 | if (branch->mLeft)
|
---|
| 477 | recInsert(branch->mLeft, rend);
|
---|
| 478 | else
|
---|
| 479 | recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
|
---|
| 480 | }
|
---|
| 481 | else if (smin == Plane::POSITIVE_SIDE ||
|
---|
| 482 | (smin == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_RIGHT))
|
---|
| 483 | {
|
---|
| 484 | if (branch->mRight)
|
---|
| 485 | recInsert(branch->mRight, rend);
|
---|
| 486 | else
|
---|
| 487 | recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
|
---|
| 488 | }
|
---|
| 489 | }
|
---|
| 490 | else
|
---|
| 491 | {
|
---|
| 492 | if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
|
---|
| 493 | {
|
---|
| 494 | if (branch->mLeft)
|
---|
| 495 | recInsert(branch->mLeft, rend);
|
---|
| 496 | else
|
---|
| 497 | recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
|
---|
| 498 | }
|
---|
| 499 | else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
|
---|
| 500 | {
|
---|
| 501 | if (branch->mRight)
|
---|
| 502 | recInsert(branch->mRight, rend);
|
---|
| 503 | else
|
---|
| 504 | recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
|
---|
| 505 | }
|
---|
| 506 | else
|
---|
| 507 | {
|
---|
| 508 | // to avoid SNAFUs, rebuild whole subtree
|
---|
| 509 | //LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
|
---|
| 510 | rebuildSubtree(node, rend);
|
---|
| 511 | }
|
---|
| 512 | }
|
---|
| 513 | }
|
---|
| 514 | }
|
---|
| 515 |
|
---|
| 516 | void KdTree::recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend)
|
---|
| 517 | {
|
---|
| 518 | //LogManager::getSingleton().logMessage("## Inserting into new subtree");
|
---|
| 519 |
|
---|
| 520 | AxisAlignedBox left, rigth, aabb;
|
---|
| 521 | PlaneEventList events;
|
---|
| 522 | int nObjects;
|
---|
| 523 |
|
---|
| 524 | rend->computeScene(events, aabb, nObjects, false);
|
---|
| 525 |
|
---|
| 526 | // override aabb
|
---|
| 527 | splitBox(*parent, left, rigth);
|
---|
| 528 | if (side == PlaneEvent::PES_LEFT)
|
---|
| 529 | {
|
---|
| 530 | aabb = left;
|
---|
| 531 | if (mBuildMethod == KDBM_RECURSIVE)
|
---|
| 532 | parent->mLeft = recBuild(events, nObjects, aabb, parent);
|
---|
| 533 | else if (mBuildMethod == KDBM_PRIORITYQUEUE)
|
---|
| 534 | parent->mLeft = pqBuild(events, nObjects, aabb, parent);
|
---|
| 535 | else
|
---|
| 536 | {
|
---|
| 537 | OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
|
---|
| 538 | "Invalid build method for the KdTree.",
|
---|
| 539 | "KdTree::buildFromList");
|
---|
| 540 | parent->mLeft = 0;
|
---|
| 541 | }
|
---|
| 542 |
|
---|
| 543 | }
|
---|
| 544 | else if (side == PlaneEvent::PES_RIGHT)
|
---|
| 545 | {
|
---|
| 546 | aabb = rigth;
|
---|
| 547 | if (mBuildMethod == KDBM_RECURSIVE)
|
---|
| 548 | parent->mRight = recBuild(events, nObjects, aabb, parent);
|
---|
| 549 | else if (mBuildMethod == KDBM_PRIORITYQUEUE)
|
---|
| 550 | parent->mRight = pqBuild(events, nObjects, aabb, parent);
|
---|
| 551 | else
|
---|
| 552 | {
|
---|
| 553 | OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
|
---|
| 554 | "Invalid build method for the KdTree.",
|
---|
| 555 | "KdTree::buildFromList");
|
---|
| 556 | parent->mRight = 0;
|
---|
| 557 | }
|
---|
| 558 | }
|
---|
| 559 | }
|
---|
| 560 |
|
---|
| 561 | void KdTree::rebuildSubtree(KdTree::Node * node, KdRenderable * rend)
|
---|
| 562 | {
|
---|
| 563 | //LogManager::getSingleton().logMessage("## Rebuilding subtree");
|
---|
| 564 |
|
---|
| 565 | AxisAlignedBox aabb = node->mAABB;
|
---|
| 566 |
|
---|
| 567 | KdRenderableList nodelist;
|
---|
| 568 | nodelist.push_back(rend);
|
---|
| 569 | addRendToList(node, nodelist);
|
---|
| 570 |
|
---|
| 571 | if (node == mKdRoot)
|
---|
| 572 | {
|
---|
| 573 | OGRE_DELETE(mKdRoot);
|
---|
| 574 | mKdRoot = buildFromList(nodelist, 0, aabb);
|
---|
| 575 | }
|
---|
| 576 | else
|
---|
| 577 | {
|
---|
[1170] | 578 | KdTree::Branch * parent = KDBRANCHPTR_CAST(node->mParent);
|
---|
[1163] | 579 |
|
---|
| 580 | if (node == parent->mLeft)
|
---|
| 581 | {
|
---|
| 582 | OGRE_DELETE(parent->mLeft);
|
---|
| 583 | parent->mLeft = buildFromList(nodelist, parent, aabb);
|
---|
| 584 | }
|
---|
| 585 | else if (node == parent->mRight)
|
---|
| 586 | {
|
---|
| 587 | OGRE_DELETE(parent->mRight);
|
---|
| 588 | parent->mRight = buildFromList(nodelist, parent, aabb);
|
---|
| 589 | }
|
---|
| 590 | else
|
---|
| 591 | {
|
---|
| 592 | OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
|
---|
| 593 | "SNAFU while inserting KdRenderable into KdTree.",
|
---|
| 594 | "KdTree::recInsert" );
|
---|
| 595 | }
|
---|
| 596 | }
|
---|
| 597 | }
|
---|
| 598 |
|
---|
| 599 | // compute both AABB then return the requested one.
|
---|
| 600 | void KdTree::splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
|
---|
| 601 | {
|
---|
| 602 | Vector3 bmin = parent.mAABB.getMinimum();
|
---|
| 603 | Vector3 bmax = parent.mAABB.getMaximum();
|
---|
| 604 | Real pos = - parent.mSplitPlane->d;
|
---|
| 605 | int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
|
---|
| 606 | // set corners which are the same as parent AABB
|
---|
| 607 | left.setMinimum(bmin);
|
---|
| 608 | right.setMaximum(bmax);
|
---|
| 609 | // modify "inner" corners
|
---|
| 610 | bmin[dim] = pos;
|
---|
| 611 | bmax[dim] = pos;
|
---|
| 612 | // set the corners on the split plane
|
---|
| 613 | left.setMaximum(bmax);
|
---|
| 614 | right.setMinimum(bmin);
|
---|
| 615 | }
|
---|
| 616 |
|
---|
| 617 | void KdTree::addRendToList(KdTree::Node * node, KdRenderableList& nodelist)
|
---|
| 618 | {
|
---|
| 619 | if (node->isLeaf())
|
---|
| 620 | {
|
---|
[1170] | 621 | KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
|
---|
[1163] | 622 | KdRenderableList::iterator it = leaf->mKdRenderables.begin();
|
---|
| 623 | KdRenderableList::iterator end = leaf->mKdRenderables.end();
|
---|
| 624 | while (it != end)
|
---|
| 625 | {
|
---|
| 626 | nodelist.push_back(*it);
|
---|
| 627 | it++;
|
---|
| 628 | }
|
---|
| 629 | }
|
---|
| 630 | else
|
---|
| 631 | {
|
---|
[1170] | 632 | KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
|
---|
[1163] | 633 | if (branch->mLeft)
|
---|
| 634 | addRendToList(branch->mLeft, nodelist);
|
---|
| 635 | if (branch->mRight)
|
---|
| 636 | addRendToList(branch->mRight, nodelist);
|
---|
| 637 | }
|
---|
| 638 | }
|
---|
| 639 |
|
---|
| 640 | void KdTree::build(KdRenderable * sceneRoot)
|
---|
| 641 | {
|
---|
| 642 | // DEBUG
|
---|
| 643 | //LogManager *lm = LogManager::getSingletonPtr();
|
---|
| 644 | Timer *timer = Root::getSingleton().getTimer();
|
---|
| 645 | unsigned long t1, t2, t3, t4;
|
---|
| 646 | //AxisAlignedBox aabb;
|
---|
| 647 |
|
---|
| 648 | // data we want to collect
|
---|
| 649 | PlaneEventList events;
|
---|
| 650 | AxisAlignedBox aabb;
|
---|
| 651 | int nObjects = 0;
|
---|
| 652 |
|
---|
| 653 | t1 = timer->getMicroseconds(); // DEBUG
|
---|
| 654 | sceneRoot->computeScene(events, aabb, nObjects);
|
---|
| 655 | t2 = timer->getMicroseconds(); // DEBUG
|
---|
| 656 | events.sort();
|
---|
| 657 | t3 = timer->getMicroseconds(); // DEBUG
|
---|
| 658 |
|
---|
| 659 | // <DEBUG>
|
---|
| 660 | //lm->logMessage("# of perfect splits " + StringConverter::toString(events.size()));
|
---|
| 661 | //PlaneEventList::iterator it;
|
---|
| 662 | //for (it = events.begin(); it != events.end(); it++)
|
---|
| 663 | //{
|
---|
| 664 | // lm->logMessage(it->print());
|
---|
| 665 | //}
|
---|
| 666 | // </DEBUG>
|
---|
| 667 |
|
---|
| 668 | assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
|
---|
| 669 | // hack to avoid SNAFU with "2-dimensional" scene
|
---|
| 670 | aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
|
---|
| 671 | aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
|
---|
| 672 |
|
---|
| 673 | if (mBuildMethod == KDBM_RECURSIVE)
|
---|
| 674 | mKdRoot = recBuild(events, nObjects, aabb, 0);
|
---|
| 675 | else if (mBuildMethod == KDBM_PRIORITYQUEUE)
|
---|
| 676 | mKdRoot = pqBuild(events, nObjects, aabb, 0);
|
---|
| 677 | else
|
---|
| 678 | {
|
---|
| 679 | OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
|
---|
| 680 | "Invalid build method for the KdTree.",
|
---|
| 681 | "KdTree::build");
|
---|
| 682 | mKdRoot = 0;
|
---|
| 683 | }
|
---|
| 684 |
|
---|
| 685 | t4 = timer->getMicroseconds(); // DEBUG
|
---|
| 686 |
|
---|
| 687 | mBuildLog->logMessage("######## SAH Statistics ########");
|
---|
| 688 | mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
|
---|
| 689 | mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
|
---|
| 690 | mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
|
---|
| 691 | mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
|
---|
| 692 | mBuildLog->logMessage("######## SAH Statistics ########");
|
---|
| 693 | calcCost();
|
---|
| 694 | }
|
---|
| 695 |
|
---|
| 696 | KdTree::Node * KdTree::buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb)
|
---|
| 697 | {
|
---|
| 698 | // data we want to collect
|
---|
| 699 | PlaneEventList events;
|
---|
| 700 | AxisAlignedBox nodeaabb;
|
---|
| 701 | int nObjects = 0;
|
---|
| 702 |
|
---|
| 703 | KdRenderableList::iterator it = nodelist.begin();
|
---|
| 704 | KdRenderableList::iterator end = nodelist.end();
|
---|
| 705 | while (it != end)
|
---|
| 706 | {
|
---|
| 707 | (*it)->computeScene(events, nodeaabb, nObjects, false);
|
---|
| 708 | it++;
|
---|
| 709 | }
|
---|
| 710 | events.sort();
|
---|
| 711 | // HACK
|
---|
| 712 | if (aabb.isNull())
|
---|
| 713 | {
|
---|
| 714 | //LogManager::getSingleton().logMessage("AABB empty, using node AABB.");
|
---|
| 715 | aabb = nodeaabb;
|
---|
| 716 | }
|
---|
| 717 |
|
---|
| 718 | // this must never happen!!
|
---|
| 719 | //AxisAlignedBox isect = aabb.intersection(nodeaabb);
|
---|
| 720 | //if (isect.getMinimum() != nodeaabb.getMinimum() || isect.getMaximum() != nodeaabb.getMaximum())
|
---|
| 721 | //{
|
---|
| 722 | // LogManager::getSingleton().logMessage("#+#+#+#+#+ SceneNodes outside of node AABB.");
|
---|
| 723 | //}
|
---|
| 724 |
|
---|
| 725 | if (mBuildMethod == KDBM_RECURSIVE)
|
---|
| 726 | return recBuild(events, nObjects, aabb, parent);
|
---|
| 727 | else if (mBuildMethod == KDBM_PRIORITYQUEUE)
|
---|
| 728 | return pqBuild(events, nObjects, aabb, parent);
|
---|
| 729 | else
|
---|
| 730 | {
|
---|
| 731 | OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
|
---|
| 732 | "Invalid build method for the KdTree.",
|
---|
| 733 | "KdTree::buildFromList");
|
---|
| 734 | return 0;
|
---|
| 735 | }
|
---|
| 736 | }
|
---|
| 737 |
|
---|
| 738 | KdTree::Node * KdTree::recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
|
---|
| 739 | {
|
---|
| 740 | // determine the depth we are on
|
---|
| 741 | int level = 0;
|
---|
| 742 | if (parent)
|
---|
| 743 | {
|
---|
| 744 | level = parent->mLevel + 1;
|
---|
| 745 | }
|
---|
| 746 |
|
---|
| 747 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 748 | mBuildLog->logMessage("events.size()=" + StringConverter::toString(events.size()));
|
---|
| 749 | #endif
|
---|
| 750 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 751 | PlaneEventList::iterator xit, xbegin, xend;
|
---|
| 752 | xbegin = events.begin();
|
---|
| 753 | xend = events.end();
|
---|
| 754 | xit = xbegin;
|
---|
| 755 | while (xit != xend)
|
---|
| 756 | {
|
---|
| 757 | mBuildLog->logMessage(xit->print());
|
---|
| 758 | xit++;
|
---|
| 759 | }
|
---|
| 760 | #endif
|
---|
| 761 |
|
---|
| 762 | /************************************************/
|
---|
| 763 | /**************** BEGIN FINDPLANE ***************/
|
---|
| 764 | /************************************************/
|
---|
| 765 | // find optimal split plane and split node accordingly
|
---|
| 766 | const int dim = 3;
|
---|
| 767 | int pStart, pOn, pEnd;
|
---|
| 768 | int nLeft[dim], nPlane[dim], nRight[dim];
|
---|
| 769 | for (int i = 0; i < dim; i++)
|
---|
| 770 | {
|
---|
| 771 | nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
|
---|
| 772 | }
|
---|
| 773 |
|
---|
| 774 | SplitInfo split, best;
|
---|
| 775 | best.cost = Math::POS_INFINITY;
|
---|
| 776 |
|
---|
| 777 |
|
---|
| 778 | PlaneEventList::iterator begin = events.begin();
|
---|
| 779 | PlaneEventList::iterator end = events.end();
|
---|
| 780 | PlaneEventList::iterator it = begin;
|
---|
| 781 | // try all planes to find the best one for the given set of objects
|
---|
| 782 | while (it != end)
|
---|
| 783 | {
|
---|
| 784 | PlaneEventList::iterator p = it;
|
---|
| 785 | pStart = pOn = pEnd = 0;
|
---|
| 786 | while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
|
---|
| 787 | {
|
---|
| 788 | it++; pEnd++;
|
---|
| 789 | }
|
---|
| 790 | while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
|
---|
| 791 | {
|
---|
| 792 | it++; pOn++;
|
---|
| 793 | }
|
---|
| 794 | while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
|
---|
| 795 | {
|
---|
| 796 | it++; pStart++;
|
---|
| 797 | }
|
---|
| 798 | int d = p->getDimension();
|
---|
| 799 | nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
|
---|
| 800 | p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split);
|
---|
| 801 | if (split.cost < best.cost)
|
---|
| 802 | {
|
---|
| 803 | best = split;
|
---|
| 804 | }
|
---|
| 805 | nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
|
---|
| 806 | }
|
---|
| 807 |
|
---|
| 808 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 809 | Real lvol = best.bleft.volume();
|
---|
| 810 | Real rvol = best.bright.volume();
|
---|
| 811 |
|
---|
| 812 | if (lvol == 0 || rvol == 0)
|
---|
| 813 | {
|
---|
| 814 | mBuildLog->logMessage("WARNING INVALID SPLIT!!!");
|
---|
| 815 | String side;
|
---|
| 816 | if (best.side == PlaneEvent::PES_LEFT)
|
---|
| 817 | side = "left";
|
---|
| 818 | else
|
---|
| 819 | side = "right";
|
---|
| 820 |
|
---|
| 821 | mBuildLog->logMessage("Splitting node on level " + StringConverter::toString(level) +
|
---|
| 822 | "\n\tcost=" + StringConverter::toString(best.cost) + " term=" + StringConverter::toString(PlaneEvent::KI*nObjects) +
|
---|
| 823 | " side=" + side +
|
---|
| 824 | "\n\tVolume: left=" + StringConverter::toString(lvol) +
|
---|
| 825 | " right=" + StringConverter::toString(rvol));
|
---|
| 826 | }
|
---|
| 827 | #endif
|
---|
| 828 | /************************************************/
|
---|
| 829 | /**************** BEGIN TERMINATE ***************/
|
---|
| 830 | /************************************************/
|
---|
| 831 | // check terminating condition
|
---|
| 832 | if (best.cost > PlaneEvent::KI*nObjects || level >= mMaxDepth)
|
---|
| 833 | {
|
---|
| 834 | // Terminating condition reached, create leaf and add renderables to list
|
---|
| 835 | KdTree::Leaf * leaf = new KdTree::Leaf(level, aabb, parent);
|
---|
| 836 | KdRenderable *rend;
|
---|
| 837 | it = begin;
|
---|
| 838 | while (it != end)
|
---|
| 839 | {
|
---|
| 840 | rend = it->getRenderable();
|
---|
| 841 | rend->setClassified(false);
|
---|
| 842 | if (rend->attachTo(leaf, this))
|
---|
| 843 | {
|
---|
| 844 | leaf->insert(rend);
|
---|
| 845 | //LogManager::getSingleton().logMessage("++ Adding SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
|
---|
| 846 | }
|
---|
| 847 | it++;
|
---|
| 848 | }
|
---|
| 849 | return leaf;
|
---|
| 850 | }
|
---|
| 851 |
|
---|
| 852 | /************************************************/
|
---|
| 853 | /**************** BEGIN CLASSIFY ****************/
|
---|
| 854 | /************************************************/
|
---|
| 855 | else
|
---|
| 856 | {
|
---|
| 857 | PlaneEventList eventsRight, eventsLeft;
|
---|
| 858 | it = begin;
|
---|
| 859 | // slightly redundant, since we mark each renderable up to 6 times
|
---|
| 860 | while (it != end)
|
---|
| 861 | {
|
---|
| 862 | it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
|
---|
| 863 | it->getRenderable()->setClassified(false);
|
---|
| 864 | it++;
|
---|
| 865 | }
|
---|
| 866 | // now classify all renderables. do they belong to the left child, the right child or both?
|
---|
| 867 | it = begin;
|
---|
| 868 | while (it != end)
|
---|
| 869 | {
|
---|
| 870 | it->classify(best.event, best.side);
|
---|
| 871 | it++;
|
---|
| 872 | }
|
---|
| 873 | // divide the event lists
|
---|
| 874 | int nLeftS = 0, nRightS = 0, nBothS = 0;
|
---|
| 875 | it = begin;
|
---|
| 876 | while (it != end)
|
---|
| 877 | {
|
---|
| 878 | // right-only nodes get moved
|
---|
| 879 | if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
|
---|
| 880 | {
|
---|
| 881 | if (!it->getRenderable()->isClassified())
|
---|
| 882 | {
|
---|
| 883 | it->getRenderable()->setClassified(true);
|
---|
| 884 | nRightS++;
|
---|
| 885 | }
|
---|
| 886 |
|
---|
| 887 | eventsRight.push_back(*it);
|
---|
| 888 | }
|
---|
| 889 | // both-only nodes get copied
|
---|
| 890 | // must clip AABBs to child AABB !!!
|
---|
| 891 | else if (it->getRenderable()->getSide() == PlaneEvent::PES_BOTH)
|
---|
| 892 | {
|
---|
| 893 | if (!it->getRenderable()->isClassified())
|
---|
| 894 | {
|
---|
| 895 | it->getRenderable()->setClassified(true);
|
---|
| 896 | nBothS++;
|
---|
| 897 | }
|
---|
| 898 |
|
---|
| 899 | //eventsRight.push_back(*it);
|
---|
| 900 | //eventsLeft.push_back(*it);
|
---|
| 901 | eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
|
---|
| 902 | eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
|
---|
| 903 | }
|
---|
| 904 | else
|
---|
| 905 | {
|
---|
| 906 | if (!it->getRenderable()->isClassified())
|
---|
| 907 | {
|
---|
| 908 | it->getRenderable()->setClassified(true);
|
---|
| 909 | nLeftS++;
|
---|
| 910 | }
|
---|
| 911 | eventsLeft.push_back(*it);
|
---|
| 912 | }
|
---|
| 913 | it++;
|
---|
| 914 | }
|
---|
| 915 |
|
---|
| 916 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 917 | mBuildLog->logMessage("Splitting on " + best.event.print());
|
---|
| 918 | mBuildLog->logMessage("eventsLeft.size()=" + StringConverter::toString(eventsLeft.size()));
|
---|
| 919 | mBuildLog->logMessage("eventsRight.size()=" + StringConverter::toString(eventsRight.size()));
|
---|
| 920 | #endif
|
---|
| 921 | KdTree::Branch * branch = new KdTree::Branch(level, aabb, parent, best.event.getSplitPlane(), best.side);
|
---|
| 922 |
|
---|
| 923 | // now create the child nodes and continue recursion
|
---|
| 924 | if (eventsLeft.size() > 0)
|
---|
| 925 | {
|
---|
| 926 | branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
|
---|
| 927 | }
|
---|
| 928 | if (eventsRight.size() > 0)
|
---|
| 929 | {
|
---|
| 930 | branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
|
---|
| 931 | }
|
---|
| 932 |
|
---|
| 933 | //assert(branch->mRight || branch->mLeft);
|
---|
| 934 |
|
---|
| 935 | return branch;
|
---|
| 936 | }
|
---|
| 937 | }
|
---|
| 938 |
|
---|
| 939 | KdTree::Node * KdTree::pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
|
---|
| 940 | {
|
---|
| 941 | SplitCandidatePQ pqueue;
|
---|
| 942 | Real globalTreeCost;
|
---|
| 943 | Real globalSA;
|
---|
| 944 |
|
---|
| 945 | KdTree::Node * newNode = 0, * topNode = 0;
|
---|
| 946 | // init global tree cost
|
---|
| 947 | globalTreeCost = PlaneEvent::KI * nObjects;
|
---|
| 948 | globalSA = PlaneEvent::surfaceArea(aabb);
|
---|
| 949 |
|
---|
| 950 | PlaneEventList * e = new PlaneEventList(events);
|
---|
| 951 |
|
---|
| 952 | // inital split candidate
|
---|
| 953 | SplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
|
---|
| 954 | SplitCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost, globalTreeCost - best->cost, best, PlaneEvent::PES_BOTH);
|
---|
| 955 | pqueue.push(splitcandidate);
|
---|
| 956 |
|
---|
| 957 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 958 | //mBuildLog->logMessage("best.pevent=" + best->event.print() +
|
---|
| 959 | // " events.size()=" + StringConverter::toString(events.size()));
|
---|
| 960 | mBuildLog->logMessage("New split on " + splitcandidate.print());
|
---|
| 961 | #endif
|
---|
| 962 |
|
---|
| 963 |
|
---|
| 964 | /*** BEGIN ITERATIVE BUILD ***/
|
---|
| 965 | while (!pqueue.empty())
|
---|
| 966 | {
|
---|
| 967 | SplitCandidate sc = pqueue.top();
|
---|
| 968 | pqueue.pop();
|
---|
| 969 |
|
---|
| 970 | // determine the depth we are on
|
---|
| 971 | int level = 0;
|
---|
| 972 | if (sc.parent)
|
---|
| 973 | {
|
---|
| 974 | level = sc.parent->mLevel + 1;
|
---|
| 975 | }
|
---|
| 976 |
|
---|
| 977 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 978 | //mBuildLog->logMessage("Splitting on " + sc.best->event.print() +
|
---|
| 979 | // " sc.events.size()=" + StringConverter::toString(sc.events->size()));
|
---|
| 980 | mBuildLog->logMessage("Splitting on " + sc.print());
|
---|
| 981 | #endif
|
---|
| 982 |
|
---|
| 983 | /************************************************/
|
---|
| 984 | /**************** BEGIN TERMINATE ***************/
|
---|
| 985 | /************************************************/
|
---|
| 986 | // check terminating condition
|
---|
| 987 | //if (best.cost > PlaneEvent::KI*sc.nObjects || level >= mMaxDepth)
|
---|
| 988 | if (sc.decrease < 0.0 || level >= mMaxDepth)
|
---|
| 989 | {
|
---|
| 990 | // Terminating condition reached, create leaf and add renderables to list
|
---|
| 991 | KdTree::Leaf * leaf = new KdTree::Leaf(level, sc.aabb, sc.parent);
|
---|
| 992 | KdRenderable *rend;
|
---|
| 993 | PlaneEventList::iterator begin = sc.events->begin();
|
---|
| 994 | PlaneEventList::iterator end = sc.events->end();
|
---|
| 995 | PlaneEventList::iterator it = begin;
|
---|
| 996 | while (it != end)
|
---|
| 997 | {
|
---|
| 998 | rend = it->getRenderable();
|
---|
| 999 | rend->setClassified(false);
|
---|
| 1000 | if (rend->attachTo(leaf, this))
|
---|
| 1001 | {
|
---|
| 1002 | leaf->insert(rend);
|
---|
| 1003 | //LogManager::getSingleton().logMessage("++ Adding SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
|
---|
| 1004 | }
|
---|
| 1005 | it++;
|
---|
| 1006 | }
|
---|
| 1007 | newNode = leaf;
|
---|
| 1008 | if (!topNode)
|
---|
| 1009 | topNode = leaf;
|
---|
| 1010 | }
|
---|
| 1011 |
|
---|
| 1012 | /************************************************/
|
---|
| 1013 | /**************** BEGIN CLASSIFY ****************/
|
---|
| 1014 | /************************************************/
|
---|
| 1015 | else
|
---|
| 1016 | {
|
---|
| 1017 | PlaneEventList * eventsLeft = new PlaneEventList();
|
---|
| 1018 | PlaneEventList * eventsRight = new PlaneEventList();
|
---|
| 1019 | PlaneEventList::iterator begin = sc.events->begin();
|
---|
| 1020 | PlaneEventList::iterator end = sc.events->end();
|
---|
| 1021 | PlaneEventList::iterator it = begin;
|
---|
| 1022 | // slightly redundant, since we mark each renderable up to 6 times
|
---|
| 1023 | while (it != end)
|
---|
| 1024 | {
|
---|
| 1025 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 1026 | mBuildLog->logMessage(it->print());
|
---|
| 1027 | #endif
|
---|
| 1028 | it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
|
---|
| 1029 | it->getRenderable()->setClassified(false);
|
---|
| 1030 | it++;
|
---|
| 1031 | }
|
---|
| 1032 | // now classify all renderables. do they belong to the left child, the right child or both?
|
---|
| 1033 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 1034 | bool bla = true;
|
---|
| 1035 | it = begin;
|
---|
| 1036 | while (it != end)
|
---|
| 1037 | {
|
---|
| 1038 | it->classify(sc.best->event, sc.best->side);
|
---|
| 1039 | if (*it == sc.best->event)
|
---|
| 1040 | {
|
---|
| 1041 | mBuildLog->logMessage("YEEPEE classified against valid event");
|
---|
| 1042 | bla = false;
|
---|
| 1043 | }
|
---|
| 1044 | it++;
|
---|
| 1045 | }
|
---|
| 1046 | if (bla)
|
---|
| 1047 | mBuildLog->logMessage("FUCKIT! Invalid classification");
|
---|
| 1048 | #else
|
---|
| 1049 | it = begin;
|
---|
| 1050 | while (it != end)
|
---|
| 1051 | {
|
---|
| 1052 | it->classify(sc.best->event, sc.best->side);
|
---|
| 1053 | it++;
|
---|
| 1054 | }
|
---|
| 1055 | #endif
|
---|
| 1056 |
|
---|
| 1057 |
|
---|
| 1058 | // divide the event lists
|
---|
| 1059 | int nLeftS = 0, nRightS = 0, nBothS = 0;
|
---|
| 1060 | it = begin;
|
---|
| 1061 | while (it != end)
|
---|
| 1062 | {
|
---|
| 1063 | if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
|
---|
| 1064 | {
|
---|
| 1065 | if (!it->getRenderable()->isClassified())
|
---|
| 1066 | {
|
---|
| 1067 | it->getRenderable()->setClassified(true);
|
---|
| 1068 | nRightS++;
|
---|
| 1069 | }
|
---|
| 1070 |
|
---|
| 1071 | eventsRight->push_back(*it);
|
---|
| 1072 | }
|
---|
| 1073 | else if (it->getRenderable()->getSide() == PlaneEvent::PES_BOTH)
|
---|
| 1074 | {
|
---|
| 1075 | if (!it->getRenderable()->isClassified())
|
---|
| 1076 | {
|
---|
| 1077 | it->getRenderable()->setClassified(true);
|
---|
| 1078 | nBothS++;
|
---|
| 1079 | }
|
---|
| 1080 |
|
---|
| 1081 | eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
|
---|
| 1082 | eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
|
---|
| 1083 | }
|
---|
| 1084 | else
|
---|
| 1085 | {
|
---|
| 1086 | if (!it->getRenderable()->isClassified())
|
---|
| 1087 | {
|
---|
| 1088 | it->getRenderable()->setClassified(true);
|
---|
| 1089 | nLeftS++;
|
---|
| 1090 | }
|
---|
| 1091 | eventsLeft->push_back(*it);
|
---|
| 1092 | }
|
---|
| 1093 | it++;
|
---|
| 1094 | }
|
---|
| 1095 |
|
---|
| 1096 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 1097 | mBuildLog->logMessage("#### Splitting node on level " + StringConverter::toString(level));
|
---|
| 1098 | Plane * vplane;
|
---|
| 1099 | int count = 0;
|
---|
| 1100 | PlaneEventList::iterator vit, vbegin, vend;
|
---|
| 1101 | vbegin = eventsLeft->begin();
|
---|
| 1102 | vend = eventsLeft->end();
|
---|
| 1103 | vit = vbegin;
|
---|
| 1104 | while (vit != vend)
|
---|
| 1105 | {
|
---|
| 1106 | vplane = vit->getSplitPlane();
|
---|
| 1107 | if (!sc.best.bleft.intersects(*vplane))
|
---|
| 1108 | {
|
---|
| 1109 | mBuildLog->logMessage("Invalid event classification! Plane: " +
|
---|
| 1110 | StringConverter::toString(vplane->normal) + ", " + StringConverter::toString(-vplane->d) +
|
---|
| 1111 | " Box: |" + StringConverter::toString(sc.best.bleft.getMinimum()) + "|" +
|
---|
| 1112 | StringConverter::toString(sc.best.bleft.getMaximum()) + "|");
|
---|
| 1113 | count++;
|
---|
| 1114 | }
|
---|
| 1115 | OGRE_DELETE(vplane);
|
---|
| 1116 | vit++;
|
---|
| 1117 | }
|
---|
| 1118 | mBuildLog->logMessage("@@@@ Number of invalid events on the left: " +
|
---|
| 1119 | StringConverter::toString(count) +
|
---|
| 1120 | " Number of events on both sides: " + StringConverter::toString(nBothS));
|
---|
| 1121 | count = 0;
|
---|
| 1122 | vbegin = eventsRight->begin();
|
---|
| 1123 | vend = eventsRight->end();
|
---|
| 1124 | vit = vbegin;
|
---|
| 1125 | while (vit != vend)
|
---|
| 1126 | {
|
---|
| 1127 | vplane = vit->getSplitPlane();
|
---|
| 1128 | if (!sc.best.bright.intersects(*vplane))
|
---|
| 1129 | {
|
---|
| 1130 | mBuildLog->logMessage("Invalid event classification! Plane: " +
|
---|
| 1131 | StringConverter::toString(vplane->normal) + ", " + StringConverter::toString(-vplane->d) +
|
---|
| 1132 | " Box: |" + StringConverter::toString(sc.best.bright.getMinimum()) + "|" +
|
---|
| 1133 | StringConverter::toString(sc.best.bright.getMaximum()) + "|");
|
---|
| 1134 | count++;
|
---|
| 1135 | }
|
---|
| 1136 | OGRE_DELETE(vplane);
|
---|
| 1137 | vit++;
|
---|
| 1138 | }
|
---|
| 1139 | mBuildLog->logMessage("@@@@ Number of invalid events on the right: " +
|
---|
| 1140 | StringConverter::toString(count) +
|
---|
| 1141 | " Number of events on both sides: " + StringConverter::toString(nBothS));
|
---|
| 1142 | #endif
|
---|
| 1143 |
|
---|
| 1144 | KdTree::Branch * branch =
|
---|
| 1145 | new KdTree::Branch(level, sc.aabb, sc.parent, sc.best->event.getSplitPlane(), sc.best->side);
|
---|
| 1146 |
|
---|
| 1147 | //Real decr = (PlaneEvent::surfaceArea(sc.aabb)/globalSA*PlaneEvent::KI*sc.nObjects) - sc.best.cost;
|
---|
| 1148 | globalTreeCost -= sc.decrease;
|
---|
| 1149 |
|
---|
| 1150 | //mBuildLog->logMessage("Splitting, cost is now " + StringConverter::toString(globalTreeCost) + "");
|
---|
| 1151 |
|
---|
| 1152 | // now create the child nodes and continue recursion
|
---|
| 1153 | if (eventsLeft->size() > 0)
|
---|
| 1154 | {
|
---|
| 1155 | best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
|
---|
| 1156 | Real old = PlaneEvent::surfaceArea(sc.best->bleft)/globalSA*PlaneEvent::KI*(nLeftS + nBothS);
|
---|
| 1157 | SplitCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
|
---|
| 1158 | branch, old, old - best->cost, best, PlaneEvent::PES_LEFT);
|
---|
| 1159 | pqueue.push(scleft);
|
---|
| 1160 |
|
---|
| 1161 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 1162 | //mBuildLog->logMessage("best.pevent: " + best->event.print() +
|
---|
| 1163 | // " eventsLeft.size()=" + StringConverter::toString(eventsLeft->size()));
|
---|
| 1164 | mBuildLog->logMessage("New split on " + scleft.print());
|
---|
| 1165 | Plane * plane = best->event.getSplitPlane();
|
---|
| 1166 | if (!sc.best->bleft.intersects(*plane))
|
---|
| 1167 | {
|
---|
| 1168 | mBuildLog->logMessage("Best plane outside parent box on level " +
|
---|
| 1169 | StringConverter::toString(level));
|
---|
| 1170 | }
|
---|
| 1171 | OGRE_DELETE(plane);
|
---|
| 1172 | #endif
|
---|
| 1173 | }
|
---|
| 1174 | if (eventsRight->size() > 0)
|
---|
| 1175 | {
|
---|
| 1176 | best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
|
---|
| 1177 | Real old = PlaneEvent::surfaceArea(sc.best->bright)/globalSA*PlaneEvent::KI*(nBothS + nRightS);
|
---|
| 1178 | SplitCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
|
---|
| 1179 | branch, old, old - best->cost, best, PlaneEvent::PES_RIGHT);
|
---|
| 1180 | pqueue.push(scright);
|
---|
| 1181 |
|
---|
| 1182 | #ifdef KDTREE_DEBUG_OFF
|
---|
| 1183 | //mBuildLog->logMessage("best.pevent: " + best->event.print() +
|
---|
| 1184 | // " eventsRight.size()=" + StringConverter::toString(eventsRight->size()));
|
---|
| 1185 | mBuildLog->logMessage("New split on " + scright.print());
|
---|
| 1186 | Plane * plane = best->event.getSplitPlane();
|
---|
| 1187 | if (!sc.best->bright.intersects(*plane))
|
---|
| 1188 | {
|
---|
| 1189 | mBuildLog->logMessage("Best plane outside parent box on level " +
|
---|
| 1190 | StringConverter::toString(level));
|
---|
| 1191 | }
|
---|
| 1192 | OGRE_DELETE(plane);
|
---|
| 1193 | #endif
|
---|
| 1194 | }
|
---|
| 1195 |
|
---|
| 1196 | newNode = branch;
|
---|
| 1197 | if (!topNode)
|
---|
| 1198 | topNode = branch;
|
---|
| 1199 | }
|
---|
| 1200 |
|
---|
| 1201 | // attach new node to parent
|
---|
| 1202 | if (sc.parent)
|
---|
| 1203 | {
|
---|
| 1204 | if (sc.side == PlaneEvent::PES_LEFT)
|
---|
| 1205 | {
|
---|
| 1206 | sc.parent->mLeft = newNode;
|
---|
| 1207 | }
|
---|
| 1208 | else if (sc.side == PlaneEvent::PES_RIGHT)
|
---|
| 1209 | {
|
---|
| 1210 | sc.parent->mRight = newNode;
|
---|
| 1211 | }
|
---|
| 1212 | else
|
---|
| 1213 | {
|
---|
| 1214 | OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
|
---|
| 1215 | "PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","KdTree::pqBuild");
|
---|
| 1216 | }
|
---|
| 1217 | }
|
---|
| 1218 |
|
---|
| 1219 | //cleanup
|
---|
| 1220 | OGRE_DELETE(sc.events);
|
---|
| 1221 | OGRE_DELETE(sc.best);
|
---|
| 1222 | }
|
---|
| 1223 | mBuildLog->logMessage("Cost after PQBUILD " + StringConverter::toString(globalTreeCost));
|
---|
| 1224 | return topNode;
|
---|
| 1225 | }
|
---|
| 1226 |
|
---|
| 1227 | SplitInfo * KdTree::pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
|
---|
| 1228 | {
|
---|
| 1229 | static const int dim = 3;
|
---|
| 1230 | int pStart, pOn, pEnd;
|
---|
| 1231 | int nLeft[dim], nPlane[dim], nRight[dim];
|
---|
| 1232 | for (int i = 0; i < dim; i++)
|
---|
| 1233 | {
|
---|
| 1234 | nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
|
---|
| 1235 | }
|
---|
| 1236 |
|
---|
| 1237 | SplitInfo split, best;
|
---|
| 1238 | best.cost = Math::POS_INFINITY;
|
---|
| 1239 |
|
---|
| 1240 | Real parentSA = PlaneEvent::surfaceArea(aabb);
|
---|
| 1241 |
|
---|
| 1242 | PlaneEventList::iterator begin = events->begin();
|
---|
| 1243 | PlaneEventList::iterator end = events->end();
|
---|
| 1244 | PlaneEventList::iterator it = begin;
|
---|
| 1245 | // try all planes to find the best one for the given set of objects
|
---|
| 1246 | while (it != end)
|
---|
| 1247 | {
|
---|
| 1248 | PlaneEventList::iterator p = it;
|
---|
| 1249 | pStart = pOn = pEnd = 0;
|
---|
| 1250 | while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
|
---|
| 1251 | {
|
---|
| 1252 | it++; pEnd++;
|
---|
| 1253 | }
|
---|
| 1254 | while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
|
---|
| 1255 | {
|
---|
| 1256 | it++; pOn++;
|
---|
| 1257 | }
|
---|
| 1258 | while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
|
---|
| 1259 | {
|
---|
| 1260 | it++; pStart++;
|
---|
| 1261 | }
|
---|
| 1262 | int d = p->getDimension();
|
---|
| 1263 | nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
|
---|
| 1264 | p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
|
---|
| 1265 | if (split.cost < best.cost)
|
---|
| 1266 | {
|
---|
| 1267 | best = split;
|
---|
| 1268 | }
|
---|
| 1269 | nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
|
---|
| 1270 | }
|
---|
| 1271 | return new SplitInfo(best);
|
---|
| 1272 | }
|
---|
| 1273 |
|
---|
[1170] | 1274 | void KdTree::queueVisibleObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters,
|
---|
| 1275 | KdTree::RenderMethod renderMethod, bool showBoxes)
|
---|
[1163] | 1276 | {
|
---|
[1170] | 1277 | // for now only recurse or stack render methods
|
---|
[1163] | 1278 | if (mKdRoot)
|
---|
[1170] | 1279 | {
|
---|
| 1280 | //if (renderMethod == KdTree::KDRM_STACK)
|
---|
| 1281 | //{
|
---|
| 1282 | // stackQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(),
|
---|
| 1283 | // cam, queue, onlyShadowCasters, showBoxes);
|
---|
| 1284 | //}
|
---|
| 1285 | //else
|
---|
| 1286 | //{
|
---|
| 1287 | recQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(),
|
---|
| 1288 | cam, queue, onlyShadowCasters, showBoxes);
|
---|
| 1289 | //}
|
---|
| 1290 | }
|
---|
[1163] | 1291 | }
|
---|
| 1292 |
|
---|
[1170] | 1293 | void KdTree::recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame,
|
---|
| 1294 | Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
|
---|
[1163] | 1295 | {
|
---|
| 1296 | // test visibility
|
---|
| 1297 | if (cam->isVisible(node->mAABB))
|
---|
| 1298 | {
|
---|
| 1299 | #ifdef KDTREE_DEBUG
|
---|
| 1300 | WireBoundingBox * wbb = 0;
|
---|
| 1301 | if (showBoxes)
|
---|
| 1302 | wbb = node->getWireBoundingBox();
|
---|
| 1303 | #endif
|
---|
| 1304 |
|
---|
| 1305 | if (node->isLeaf())
|
---|
| 1306 | {
|
---|
[1170] | 1307 | KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
|
---|
[1163] | 1308 | KdRenderableList::iterator it = leaf->mKdRenderables.begin();
|
---|
| 1309 | KdRenderableList::iterator end = leaf->mKdRenderables.end();
|
---|
| 1310 | while (it != end)
|
---|
| 1311 | {
|
---|
| 1312 | if (!(*it)->isQueued(currentFrame, cam))
|
---|
| 1313 | {
|
---|
| 1314 | (*it)->queueObjects(cam, queue, onlyShadowCasters);
|
---|
| 1315 | }
|
---|
| 1316 | it++;
|
---|
| 1317 | }
|
---|
| 1318 | #ifdef KDTREE_DEBUG
|
---|
| 1319 | if (wbb)
|
---|
| 1320 | queue->addRenderable(wbb);
|
---|
| 1321 | #else
|
---|
| 1322 | if (showBoxes)
|
---|
| 1323 | queue->addRenderable(leaf->getWireBoundingBox());
|
---|
| 1324 | #endif
|
---|
| 1325 | }
|
---|
| 1326 | else
|
---|
| 1327 | {
|
---|
[1170] | 1328 | KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
|
---|
[1163] | 1329 | #ifdef KDTREE_DEBUG
|
---|
| 1330 | if (wbb)
|
---|
| 1331 | queue->addRenderable(wbb);
|
---|
| 1332 | #else
|
---|
| 1333 | if (showBoxes)
|
---|
| 1334 | queue->addRenderable(branch->getWireBoundingBox());
|
---|
| 1335 | #endif
|
---|
| 1336 |
|
---|
| 1337 | if (branch->mLeft)
|
---|
| 1338 | recQueueVisibleObjects(branch->mLeft, currentFrame, cam, queue, onlyShadowCasters, showBoxes);
|
---|
| 1339 | if (branch->mRight)
|
---|
| 1340 | recQueueVisibleObjects(branch->mRight, currentFrame, cam, queue, onlyShadowCasters, showBoxes);
|
---|
| 1341 | }
|
---|
| 1342 | }
|
---|
| 1343 | }
|
---|
| 1344 |
|
---|
[1170] | 1345 | void KdTree::stackQueueVisibleObjects(KdTree::Node * root, unsigned long currentFrame, Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
|
---|
| 1346 | {
|
---|
| 1347 | static NodeStack nodestack;
|
---|
| 1348 | if (!nodestack.empty()) OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
|
---|
| 1349 | "Stuff left in stack from previos frame", "KdTree::stackQueueVisibleObjects");
|
---|
| 1350 |
|
---|
| 1351 | nodestack.push(root);
|
---|
| 1352 |
|
---|
| 1353 | while (!nodestack.empty())
|
---|
| 1354 | {
|
---|
| 1355 | KdTree::Node * node = nodestack.top();
|
---|
| 1356 | nodestack.pop();
|
---|
| 1357 |
|
---|
| 1358 | // test visibility
|
---|
| 1359 | if (cam->isVisible(node->mAABB))
|
---|
| 1360 | {
|
---|
| 1361 | #ifdef KDTREE_DEBUG
|
---|
| 1362 | WireBoundingBox * wbb = 0;
|
---|
| 1363 | if (showBoxes)
|
---|
| 1364 | wbb = node->getWireBoundingBox();
|
---|
| 1365 | #endif
|
---|
| 1366 |
|
---|
| 1367 | if (node->isLeaf())
|
---|
| 1368 | {
|
---|
| 1369 | KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
|
---|
| 1370 | KdRenderableList::iterator it = leaf->mKdRenderables.begin();
|
---|
| 1371 | KdRenderableList::iterator end = leaf->mKdRenderables.end();
|
---|
| 1372 | while (it != end)
|
---|
| 1373 | {
|
---|
| 1374 | if (!(*it)->isQueued(currentFrame, cam))
|
---|
| 1375 | {
|
---|
| 1376 | (*it)->queueObjects(cam, queue, onlyShadowCasters);
|
---|
| 1377 | }
|
---|
| 1378 | it++;
|
---|
| 1379 | }
|
---|
| 1380 | #ifdef KDTREE_DEBUG
|
---|
| 1381 | if (wbb)
|
---|
| 1382 | queue->addRenderable(wbb);
|
---|
| 1383 | #else
|
---|
| 1384 | if (showBoxes)
|
---|
| 1385 | queue->addRenderable(leaf->getWireBoundingBox());
|
---|
| 1386 | #endif
|
---|
| 1387 | }
|
---|
| 1388 | else
|
---|
| 1389 | {
|
---|
| 1390 | KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
|
---|
| 1391 | #ifdef KDTREE_DEBUG
|
---|
| 1392 | if (wbb)
|
---|
| 1393 | queue->addRenderable(wbb);
|
---|
| 1394 | #else
|
---|
| 1395 | if (showBoxes)
|
---|
| 1396 | queue->addRenderable(branch->getWireBoundingBox());
|
---|
| 1397 | #endif
|
---|
| 1398 |
|
---|
| 1399 | if (branch->mLeft)
|
---|
| 1400 | nodestack.push(branch->mLeft);
|
---|
| 1401 | if (branch->mRight)
|
---|
| 1402 | nodestack.push(branch->mRight);
|
---|
| 1403 | }
|
---|
| 1404 | }
|
---|
| 1405 | }
|
---|
| 1406 | }
|
---|
| 1407 |
|
---|
[1163] | 1408 | void KdTree::dump()
|
---|
| 1409 | {
|
---|
| 1410 | LogManager::getSingleton().logMessage("#@#@#@#@ Dumping KdTree #@#@#@#@");
|
---|
| 1411 | if (mKdRoot)
|
---|
| 1412 | dump(mKdRoot);
|
---|
| 1413 | }
|
---|
| 1414 |
|
---|
| 1415 | void KdTree::dump(KdTree::Node * node)
|
---|
| 1416 | {
|
---|
| 1417 | LogManager * log = LogManager::getSingletonPtr();
|
---|
| 1418 | KdTreeSceneNode * scenenode;
|
---|
| 1419 | String pad;
|
---|
| 1420 | int p;
|
---|
| 1421 |
|
---|
| 1422 | pad = "";
|
---|
| 1423 | for (p = 0; p < node->mLevel; p++)
|
---|
| 1424 | {
|
---|
| 1425 | pad += " ";
|
---|
| 1426 | }
|
---|
| 1427 |
|
---|
| 1428 | if (node->isLeaf())
|
---|
| 1429 | {
|
---|
[1170] | 1430 | KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
|
---|
[1163] | 1431 | KdRenderableList::iterator it = leaf->mKdRenderables.begin();
|
---|
| 1432 | KdRenderableList::iterator end = leaf->mKdRenderables.end();
|
---|
| 1433 | while (it != end)
|
---|
| 1434 | {
|
---|
| 1435 | scenenode = dynamic_cast<KdTreeSceneNode *>(*it);
|
---|
| 1436 | log->logMessage(pad + "# Leaf level " + StringConverter::toString(node->mLevel) +
|
---|
| 1437 | " SceneNode " + scenenode->getName());
|
---|
| 1438 | log->logMessage(pad + "## Objects: " + scenenode->dumpToString());
|
---|
| 1439 | it++;
|
---|
| 1440 | }
|
---|
| 1441 | }
|
---|
| 1442 | else
|
---|
| 1443 | {
|
---|
[1170] | 1444 | KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
|
---|
[1163] | 1445 | if (branch->mLeft)
|
---|
| 1446 | {
|
---|
| 1447 | log->logMessage(pad + "# Branch level " + StringConverter::toString(node->mLevel) + " Left Child");
|
---|
| 1448 | dump(branch->mLeft);
|
---|
| 1449 | }
|
---|
| 1450 | if (branch->mRight)
|
---|
| 1451 | {
|
---|
| 1452 | log->logMessage(pad + "# Branch level " + StringConverter::toString(node->mLevel) + " Right Child");
|
---|
| 1453 | dump(branch->mRight);
|
---|
| 1454 | }
|
---|
| 1455 | }
|
---|
| 1456 | }
|
---|
| 1457 |
|
---|
| 1458 | void KdTree::calcCost()
|
---|
| 1459 | {
|
---|
| 1460 | Real cost = 0;
|
---|
| 1461 | if (mKdRoot)
|
---|
| 1462 | cost = calcCost(mKdRoot, PlaneEvent::surfaceArea(mKdRoot->mAABB));
|
---|
| 1463 |
|
---|
| 1464 | //LogManager::getSingleton().logMessage("#@#@#@ One KdTree: " + StringConverter::toString(cost));
|
---|
| 1465 | mBuildLog->logMessage("#@#@#@ One KdTree: " + StringConverter::toString(cost));
|
---|
| 1466 | }
|
---|
| 1467 |
|
---|
| 1468 | Real KdTree::calcCost(KdTree::Node * node, Real vs)
|
---|
| 1469 | {
|
---|
| 1470 | if (node == 0)
|
---|
| 1471 | return 0.0;
|
---|
| 1472 |
|
---|
| 1473 | if (node->isLeaf())
|
---|
| 1474 | {
|
---|
[1170] | 1475 | KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
|
---|
[1163] | 1476 | return (PlaneEvent::surfaceArea(node->mAABB)/vs)*PlaneEvent::KI*leaf->mKdRenderables.size();
|
---|
| 1477 | }
|
---|
| 1478 | else
|
---|
| 1479 | {
|
---|
[1170] | 1480 | KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
|
---|
[1163] | 1481 | return (PlaneEvent::surfaceArea(node->mAABB)/vs)*PlaneEvent::KT + calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
|
---|
| 1482 | }
|
---|
| 1483 | }
|
---|
| 1484 |
|
---|
| 1485 | KdTree::Leaf::~Leaf()
|
---|
| 1486 | {
|
---|
| 1487 | // detach all scene nodes in the case that we are rebuilding
|
---|
| 1488 | // the tree but not the scene
|
---|
| 1489 | KdRenderableList::iterator it = mKdRenderables.begin();
|
---|
| 1490 | KdRenderableList::iterator end = mKdRenderables.end();
|
---|
| 1491 | while (it != end)
|
---|
| 1492 | {
|
---|
| 1493 | (*it)->detachFrom(this);
|
---|
| 1494 | it++;
|
---|
| 1495 | }
|
---|
| 1496 | mKdRenderables.clear();
|
---|
| 1497 | }
|
---|
[1173] | 1498 |
|
---|
| 1499 | // update the world aabb based on the contained geometry
|
---|
| 1500 | void KdTree::Leaf::_updateBounds()
|
---|
| 1501 | {
|
---|
| 1502 | // reset box
|
---|
| 1503 | mWorldAABB.setNull();
|
---|
| 1504 |
|
---|
| 1505 | // merge boxes from attached geometry
|
---|
| 1506 | KdRenderableList::iterator it = mKdRenderables.begin();
|
---|
| 1507 | KdRenderableList::iterator end = mKdRenderables.end();
|
---|
| 1508 | while (it != end)
|
---|
| 1509 | {
|
---|
| 1510 | mWorldAABB.merge((*it)->getBoundingBox());
|
---|
| 1511 | it++;
|
---|
| 1512 | }
|
---|
| 1513 |
|
---|
| 1514 | // update parent recursively
|
---|
| 1515 | if (mParent)
|
---|
| 1516 | mParent->_updateBounds();
|
---|
| 1517 | }
|
---|
| 1518 | } // namespace Ogre |
---|