[2073] | 1 | #include <stack>
|
---|
| 2 | #include <algorithm>
|
---|
| 3 | #include <queue>
|
---|
| 4 | #include "Environment.h"
|
---|
| 5 | #include "Mesh.h"
|
---|
| 6 | #include "TraversalTree.h"
|
---|
| 7 | #include "ViewCell.h"
|
---|
| 8 | #include "Beam.h"
|
---|
[2124] | 9 | #include "Exporter.h"
|
---|
[2073] | 10 |
|
---|
| 11 |
|
---|
| 12 | // $$JB HACK
|
---|
| 13 | #define KD_PVS_AREA (1e-5f)
|
---|
| 14 |
|
---|
| 15 | namespace GtpVisibilityPreprocessor {
|
---|
| 16 |
|
---|
| 17 | int TraversalNode::sMailId = 1;
|
---|
| 18 | int TraversalNode::sReservedMailboxes = 1;
|
---|
| 19 |
|
---|
| 20 |
|
---|
| 21 | inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
|
---|
| 22 | {
|
---|
| 23 | return obj1->mId < obj2->mId;
|
---|
| 24 | }
|
---|
| 25 |
|
---|
| 26 |
|
---|
[2093] | 27 | TraversalNode::TraversalNode(TraversalInterior *parent):
|
---|
| 28 | mParent(parent), mMailbox(0)
|
---|
| 29 | {
|
---|
| 30 | }
|
---|
[2073] | 31 |
|
---|
[2093] | 32 |
|
---|
| 33 | TraversalInterior::TraversalInterior(TraversalInterior *parent):
|
---|
| 34 | TraversalNode(parent), mBack(NULL), mFront(NULL)
|
---|
[2073] | 35 | {
|
---|
| 36 | }
|
---|
| 37 |
|
---|
| 38 |
|
---|
| 39 | TraversalInterior::~TraversalInterior()
|
---|
| 40 | {
|
---|
| 41 | // recursivly destroy children
|
---|
| 42 | DEL_PTR(mFront);
|
---|
| 43 | DEL_PTR(mBack);
|
---|
| 44 | }
|
---|
| 45 |
|
---|
| 46 |
|
---|
[2093] | 47 | bool TraversalInterior::IsLeaf() const
|
---|
| 48 | {
|
---|
| 49 | return false;
|
---|
| 50 | }
|
---|
| 51 |
|
---|
| 52 |
|
---|
| 53 | void TraversalInterior::SetupChildLinks(TraversalNode *b, TraversalNode *f)
|
---|
| 54 | {
|
---|
| 55 | mBack = b;
|
---|
| 56 | mFront = f;
|
---|
| 57 |
|
---|
| 58 | b->mParent = f->mParent = this;
|
---|
| 59 | }
|
---|
| 60 |
|
---|
| 61 |
|
---|
[2124] | 62 | void TraversalInterior::ReplaceChildLink(TraversalNode *oldChild,
|
---|
| 63 | TraversalNode *newChild)
|
---|
[2093] | 64 | {
|
---|
| 65 | if (mBack == oldChild)
|
---|
| 66 | mBack = newChild;
|
---|
| 67 | else
|
---|
| 68 | mFront = newChild;
|
---|
| 69 | }
|
---|
| 70 |
|
---|
| 71 |
|
---|
| 72 | TraversalLeaf::TraversalLeaf(TraversalInterior *parent, const int objects):
|
---|
| 73 | TraversalNode(parent)
|
---|
| 74 | {
|
---|
[2124] | 75 | mViewCells.reserve(objects);
|
---|
[2093] | 76 | }
|
---|
| 77 |
|
---|
| 78 |
|
---|
| 79 | bool TraversalLeaf::IsLeaf() const
|
---|
| 80 | {
|
---|
| 81 | return true;
|
---|
| 82 | }
|
---|
| 83 |
|
---|
| 84 |
|
---|
[2073] | 85 | TraversalLeaf::~TraversalLeaf()
|
---|
| 86 | {
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 |
|
---|
| 90 | TraversalTree::TraversalTree()
|
---|
[2093] | 91 | {
|
---|
[2124] | 92 | TraversalLeaf *leaf = new TraversalLeaf(NULL, 0);
|
---|
| 93 | leaf->mDepth = 0;
|
---|
| 94 | mRoot = leaf;
|
---|
[2073] | 95 |
|
---|
[2093] | 96 | Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxNodes", mTermMaxNodes);
|
---|
| 97 | Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxDepth", mTermMaxDepth);
|
---|
| 98 | Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.minCost", mTermMinCost);
|
---|
| 99 | Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.maxCostRatio", mMaxCostRatio);
|
---|
| 100 | Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.ct_div_ci", mCt_div_ci);
|
---|
| 101 | Environment::GetSingleton()->GetFloatValue("TraversalTree.splitBorder", mSplitBorder);
|
---|
[2073] | 102 |
|
---|
[2093] | 103 | Environment::GetSingleton()->GetBoolValue("TraversalTree.sahUseFaces", mSahUseFaces);
|
---|
[2073] | 104 |
|
---|
[2093] | 105 | char splitType[64];
|
---|
| 106 | Environment::GetSingleton()->GetStringValue("TraversalTree.splitMethod", splitType);
|
---|
| 107 |
|
---|
[2124] | 108 | splitCandidates = NULL;
|
---|
[2093] | 109 | mSplitMethod = SPLIT_SPATIAL_MEDIAN;
|
---|
[2124] | 110 |
|
---|
[2093] | 111 | if (strcmp(splitType, "spatialMedian") == 0)
|
---|
| 112 | {
|
---|
| 113 | mSplitMethod = SPLIT_SPATIAL_MEDIAN;
|
---|
| 114 | }
|
---|
| 115 | else
|
---|
| 116 | {
|
---|
| 117 | if (strcmp(splitType, "objectMedian") == 0)
|
---|
| 118 | {
|
---|
| 119 | mSplitMethod = SPLIT_OBJECT_MEDIAN;
|
---|
| 120 | }
|
---|
| 121 | else
|
---|
| 122 | {
|
---|
| 123 | if (strcmp(splitType, "SAH") == 0)
|
---|
| 124 | {
|
---|
| 125 | mSplitMethod = SPLIT_SAH;
|
---|
| 126 | }
|
---|
| 127 | else
|
---|
| 128 | {
|
---|
[2124] | 129 | cerr << "Wrong kd split type " << splitType << endl;
|
---|
[2093] | 130 | exit(1);
|
---|
| 131 | }
|
---|
| 132 | }
|
---|
| 133 | }
|
---|
[2124] | 134 | cout << "Traversal Tree Split method: " << mSplitMethod << endl;
|
---|
[2073] | 135 | }
|
---|
| 136 |
|
---|
| 137 |
|
---|
| 138 | TraversalTree::~TraversalTree()
|
---|
| 139 | {
|
---|
| 140 | DEL_PTR(mRoot);
|
---|
| 141 | }
|
---|
| 142 |
|
---|
| 143 |
|
---|
[2124] | 144 | bool TraversalTree::Construct(const ViewCellContainer &viewCells)
|
---|
[2073] | 145 | {
|
---|
[2093] | 146 | if (!splitCandidates)
|
---|
| 147 | {
|
---|
| 148 | splitCandidates = new vector<SortableEntry *>;
|
---|
| 149 | }
|
---|
[2073] | 150 |
|
---|
[2093] | 151 | // first construct a leaf that will get subdivide
|
---|
| 152 | TraversalLeaf *leaf = static_cast<TraversalLeaf *>(mRoot);
|
---|
[2073] | 153 |
|
---|
[2124] | 154 | leaf->mViewCells = viewCells;
|
---|
[2093] | 155 | mStat.nodes = 1;
|
---|
| 156 | mBox.Initialize();
|
---|
[2094] | 157 |
|
---|
[2124] | 158 | ViewCellContainer::const_iterator mi;
|
---|
| 159 |
|
---|
| 160 | for ( mi = leaf->mViewCells.begin(); mi != leaf->mViewCells.end(); ++ mi)
|
---|
[2093] | 161 | {
|
---|
| 162 | mBox.Include((*mi)->GetBox());
|
---|
| 163 | }
|
---|
[2073] | 164 |
|
---|
[2093] | 165 | cout << "TraversalTree Root Box:" << mBox << endl;
|
---|
| 166 | mRoot = Subdivide(TraversalData(leaf, mBox, 0));
|
---|
| 167 |
|
---|
| 168 | // remove the allocated array
|
---|
[2124] | 169 | if (splitCandidates)
|
---|
| 170 | {
|
---|
| 171 | CLEAR_CONTAINER(*splitCandidates);
|
---|
| 172 | delete splitCandidates;
|
---|
| 173 | }
|
---|
| 174 |
|
---|
[2093] | 175 | return true;
|
---|
| 176 | }
|
---|
[2073] | 177 |
|
---|
| 178 |
|
---|
[2093] | 179 | TraversalNode *TraversalTree::Subdivide(const TraversalData &tdata)
|
---|
[2073] | 180 | {
|
---|
[2093] | 181 | TraversalNode *result = NULL;
|
---|
[2073] | 182 |
|
---|
[2093] | 183 | //priority_queue<TraversalData> tStack;
|
---|
| 184 | stack<TraversalData> tStack;
|
---|
[2073] | 185 |
|
---|
[2093] | 186 | tStack.push(tdata);
|
---|
| 187 | AxisAlignedBox3 backBox, frontBox;
|
---|
[2073] | 188 |
|
---|
[2093] | 189 | while (!tStack.empty())
|
---|
| 190 | {
|
---|
| 191 | if (mStat.Nodes() > mTermMaxNodes)
|
---|
| 192 | {
|
---|
| 193 | while (!tStack.empty())
|
---|
| 194 | {
|
---|
| 195 | EvaluateLeafStats(tStack.top());
|
---|
| 196 | tStack.pop();
|
---|
| 197 | }
|
---|
| 198 | break;
|
---|
| 199 | }
|
---|
| 200 |
|
---|
| 201 | TraversalData data = tStack.top();
|
---|
[2073] | 202 | tStack.pop();
|
---|
| 203 |
|
---|
[2093] | 204 | TraversalLeaf *tLeaf = static_cast<TraversalLeaf *> (data.mNode);
|
---|
| 205 | TraversalNode *node = SubdivideNode(tLeaf,
|
---|
| 206 | data.mBox,
|
---|
| 207 | backBox,
|
---|
| 208 | frontBox);
|
---|
[2073] | 209 |
|
---|
[2093] | 210 | if (result == NULL)
|
---|
| 211 | result = node;
|
---|
[2073] | 212 |
|
---|
[2093] | 213 | if (!node->IsLeaf())
|
---|
| 214 | {
|
---|
| 215 | TraversalInterior *interior = static_cast<TraversalInterior *>(node);
|
---|
| 216 |
|
---|
| 217 | // push the children on the stack
|
---|
| 218 | tStack.push(TraversalData(interior->mBack, backBox, data.mDepth + 1));
|
---|
| 219 | tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth + 1));
|
---|
| 220 |
|
---|
| 221 | }
|
---|
| 222 | else
|
---|
| 223 | {
|
---|
| 224 | EvaluateLeafStats(data);
|
---|
| 225 | }
|
---|
| 226 | }
|
---|
| 227 |
|
---|
| 228 | return result;
|
---|
[2073] | 229 | }
|
---|
| 230 |
|
---|
| 231 |
|
---|
[2093] | 232 | bool TraversalTree::TerminationCriteriaMet(const TraversalLeaf *leaf)
|
---|
[2073] | 233 | {
|
---|
[2124] | 234 | const bool criteriaMet = (
|
---|
| 235 | ((int)leaf->mViewCells.size() <= mTermMinCost) ||
|
---|
| 236 | (leaf->mDepth >= mTermMaxDepth)
|
---|
| 237 | || (GetBox(leaf).SurfaceArea() < 0.00001f)
|
---|
| 238 | );
|
---|
[2093] | 239 |
|
---|
[2073] | 240 | if (criteriaMet)
|
---|
[2124] | 241 | {
|
---|
| 242 | cerr << "\nOBJECTS=" << (int)leaf->mViewCells.size() << endl;
|
---|
| 243 | cerr << "\nDEPTH=" << (int)leaf->mDepth << endl;
|
---|
| 244 | }
|
---|
[2073] | 245 |
|
---|
| 246 | return criteriaMet;
|
---|
| 247 | }
|
---|
| 248 |
|
---|
| 249 |
|
---|
[2093] | 250 | int TraversalTree::SelectPlane(TraversalLeaf *leaf,
|
---|
| 251 | const AxisAlignedBox3 &box,
|
---|
| 252 | float &position)
|
---|
[2073] | 253 | {
|
---|
[2093] | 254 | int axis = -1;
|
---|
[2073] | 255 |
|
---|
[2093] | 256 | switch (mSplitMethod)
|
---|
| 257 | {
|
---|
| 258 | case SPLIT_SPATIAL_MEDIAN:
|
---|
| 259 | {
|
---|
| 260 | axis = box.Size().DrivingAxis();
|
---|
[2124] | 261 | position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
|
---|
[2093] | 262 | break;
|
---|
[2073] | 263 | }
|
---|
[2093] | 264 | case SPLIT_SAH:
|
---|
| 265 | {
|
---|
| 266 | int objectsBack, objectsFront;
|
---|
[2124] | 267 | float costRatio = 99999;//MAX_FLOAT;
|
---|
[2093] | 268 |
|
---|
[2124] | 269 | for (int i=0; i < 3; ++ i)
|
---|
[2093] | 270 | {
|
---|
[2124] | 271 | float p;
|
---|
| 272 | float r = BestCostRatio(leaf,
|
---|
| 273 | box,
|
---|
| 274 | i,
|
---|
| 275 | p,
|
---|
| 276 | objectsBack,
|
---|
| 277 | objectsFront);
|
---|
| 278 |
|
---|
| 279 | if (r < costRatio)
|
---|
[2093] | 280 | {
|
---|
[2124] | 281 | costRatio = r;
|
---|
| 282 | axis = i;
|
---|
| 283 | position = p;
|
---|
[2093] | 284 | }
|
---|
| 285 | }
|
---|
| 286 |
|
---|
| 287 | if (costRatio > mMaxCostRatio)
|
---|
| 288 | {
|
---|
[2124] | 289 | cout << "Too big cost ratio " << costRatio << endl;
|
---|
[2093] | 290 | axis = -1;
|
---|
| 291 | }
|
---|
| 292 | break;
|
---|
| 293 | }
|
---|
| 294 | }
|
---|
| 295 |
|
---|
| 296 | return axis;
|
---|
[2073] | 297 | }
|
---|
| 298 |
|
---|
[2093] | 299 |
|
---|
[2073] | 300 | TraversalNode *TraversalTree::SubdivideNode(TraversalLeaf *leaf,
|
---|
| 301 | const AxisAlignedBox3 &box,
|
---|
| 302 | AxisAlignedBox3 &backBBox,
|
---|
[2093] | 303 | AxisAlignedBox3 &frontBBox)
|
---|
[2073] | 304 | {
|
---|
| 305 |
|
---|
| 306 | if (TerminationCriteriaMet(leaf))
|
---|
| 307 | return leaf;
|
---|
| 308 |
|
---|
| 309 | float position;
|
---|
| 310 |
|
---|
| 311 | // select subdivision axis
|
---|
| 312 | int axis = SelectPlane( leaf, box, position );
|
---|
| 313 |
|
---|
| 314 | if (axis == -1) {
|
---|
[2124] | 315 | cout << "terminate on cost ratio" << endl;
|
---|
[2149] | 316 | ++ mStat.costRatioNodes;
|
---|
[2073] | 317 | return leaf;
|
---|
| 318 | }
|
---|
| 319 |
|
---|
| 320 | mStat.nodes+=2;
|
---|
| 321 | mStat.splits[axis]++;
|
---|
| 322 |
|
---|
| 323 | // add the new nodes to the tree
|
---|
| 324 | TraversalInterior *node = new TraversalInterior(leaf->mParent);
|
---|
| 325 |
|
---|
| 326 | node->mAxis = axis;
|
---|
| 327 | node->mPosition = position;
|
---|
| 328 | node->mBox = box;
|
---|
| 329 |
|
---|
| 330 | backBBox = box;
|
---|
| 331 | frontBBox = box;
|
---|
| 332 |
|
---|
| 333 | // first count ray sides
|
---|
| 334 | int objectsBack = 0;
|
---|
| 335 | int objectsFront = 0;
|
---|
| 336 |
|
---|
| 337 | backBBox.SetMax(axis, position);
|
---|
| 338 | frontBBox.SetMin(axis, position);
|
---|
| 339 |
|
---|
[2124] | 340 | ViewCellContainer::const_iterator mi, mi_end = leaf->mViewCells.end();
|
---|
[2073] | 341 |
|
---|
[2124] | 342 | for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi)
|
---|
[2073] | 343 | {
|
---|
| 344 | // determine the side of this ray with respect to the plane
|
---|
| 345 | AxisAlignedBox3 box = (*mi)->GetBox();
|
---|
[2124] | 346 | if (box.Max(axis) > position)
|
---|
| 347 | ++ objectsFront;
|
---|
[2073] | 348 |
|
---|
[2124] | 349 | if (box.Min(axis) < position)
|
---|
[2093] | 350 | ++ objectsBack;
|
---|
[2073] | 351 | }
|
---|
| 352 |
|
---|
| 353 | TraversalLeaf *back = new TraversalLeaf(node, objectsBack);
|
---|
| 354 | TraversalLeaf *front = new TraversalLeaf(node, objectsFront);
|
---|
| 355 |
|
---|
[2124] | 356 | back->mDepth = front->mDepth = leaf->mDepth + 1;
|
---|
[2073] | 357 |
|
---|
| 358 | // replace a link from node's parent
|
---|
[2093] | 359 | if (leaf->mParent)
|
---|
| 360 | {
|
---|
[2073] | 361 | leaf->mParent->ReplaceChildLink(leaf, node);
|
---|
[2093] | 362 | }
|
---|
[2073] | 363 |
|
---|
| 364 | // and setup child links
|
---|
| 365 | node->SetupChildLinks(back, front);
|
---|
| 366 |
|
---|
[2124] | 367 | for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi)
|
---|
[2073] | 368 | {
|
---|
| 369 | // determine the side of this ray with respect to the plane
|
---|
| 370 | AxisAlignedBox3 box = (*mi)->GetBox();
|
---|
| 371 |
|
---|
| 372 | if (box.Max(axis) >= position )
|
---|
| 373 | {
|
---|
[2124] | 374 | front->mViewCells.push_back(*mi);
|
---|
[2073] | 375 | }
|
---|
| 376 |
|
---|
| 377 | if (box.Min(axis) < position )
|
---|
| 378 | {
|
---|
[2124] | 379 | back->mViewCells.push_back(*mi);
|
---|
[2073] | 380 | }
|
---|
| 381 |
|
---|
[2124] | 382 | mStat.objectRefs -= (int)leaf->mViewCells.size();
|
---|
[2073] | 383 | mStat.objectRefs += objectsBack + objectsFront;
|
---|
| 384 | }
|
---|
| 385 |
|
---|
[2093] | 386 | delete leaf;
|
---|
[2073] | 387 |
|
---|
| 388 | return node;
|
---|
| 389 | }
|
---|
| 390 |
|
---|
| 391 |
|
---|
[2093] | 392 | void TraversalTreeStatistics::Print(ostream &app) const
|
---|
[2073] | 393 | {
|
---|
[2093] | 394 | app << "===== TraversalTree statistics ===============\n";
|
---|
[2073] | 395 |
|
---|
[2093] | 396 | app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
|
---|
[2073] | 397 |
|
---|
[2093] | 398 | app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
|
---|
[2073] | 399 |
|
---|
[2093] | 400 | app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz)\n";
|
---|
[2073] | 401 |
|
---|
[2124] | 402 | for (int i = 0; i < 7; ++ i)
|
---|
| 403 | app << splits[i] << " ";
|
---|
| 404 | app << endl;
|
---|
[2073] | 405 |
|
---|
[2093] | 406 | app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" <<
|
---|
| 407 | maxObjectRefs << "\n";
|
---|
[2073] | 408 |
|
---|
[2124] | 409 | app << "#N_AVGOBJECTREFS ( Avg number of object refs / leaf )\n" <<
|
---|
| 410 | totalObjectRefs / (double)Leaves() << "\n";
|
---|
[2073] | 411 |
|
---|
[2093] | 412 | app << "#N_LEAFDOMAINREFS ( Number of query domain Refs / leaf )\n" <<
|
---|
[2124] | 413 | objectRefs / (double)Leaves() << "\n";
|
---|
[2073] | 414 |
|
---|
[2093] | 415 | app << "#N_PEMPTYLEAVES ( Percentage of leaves with zero query domains )\n"<<
|
---|
[2124] | 416 | zeroQueryNodes * 100 / (double)Leaves() << endl;
|
---|
[2073] | 417 |
|
---|
[2093] | 418 | app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
|
---|
[2124] | 419 | maxDepthNodes * 100 / (double)Leaves() << endl;
|
---|
[2073] | 420 |
|
---|
[2093] | 421 | app << "#N_PMINCOSTLEAVES ( Percentage of leaves with minCost )\n"<<
|
---|
[2124] | 422 | minCostNodes * 100 / (double)Leaves() << endl;
|
---|
[2073] | 423 |
|
---|
[2149] | 424 | app << "#N_COSTRATIOLEAVES ( Percentage of leaves with cost ratio termination )\n"<<
|
---|
| 425 | costRatioNodes * 100 / (double)Leaves() << endl;
|
---|
| 426 |
|
---|
[2093] | 427 | // app << setprecision(4);
|
---|
| 428 | // app << "#N_CTIME ( Construction time [s] )\n"
|
---|
| 429 | // << Time() << " \n";
|
---|
[2073] | 430 |
|
---|
[2124] | 431 | app << "======= END OF TraversalTree statistics ========\n";
|
---|
[2073] | 432 | }
|
---|
| 433 |
|
---|
| 434 |
|
---|
[2093] | 435 | void TraversalTree::EvaluateLeafStats(const TraversalData &data)
|
---|
[2073] | 436 | {
|
---|
[2124] | 437 | // the node became a leaf -> evaluate stats for leafs
|
---|
| 438 | TraversalLeaf *leaf = (TraversalLeaf *)data.mNode;
|
---|
[2073] | 439 |
|
---|
[2149] | 440 | if (data.mDepth >= mTermMaxDepth)
|
---|
[2124] | 441 | ++ mStat.maxDepthNodes;
|
---|
[2073] | 442 |
|
---|
[2149] | 443 | if ((int)(leaf->mViewCells.size()) <= mTermMinCost)
|
---|
[2124] | 444 | ++ mStat.minCostNodes;
|
---|
| 445 |
|
---|
| 446 | mStat.totalObjectRefs += (int)leaf->mViewCells.size();
|
---|
| 447 |
|
---|
| 448 | if ((int)(leaf->mViewCells.size()) > mStat.maxObjectRefs)
|
---|
| 449 | mStat.maxObjectRefs = (int)leaf->mViewCells.size();
|
---|
[2073] | 450 | }
|
---|
| 451 |
|
---|
| 452 |
|
---|
| 453 | void
|
---|
[2093] | 454 | TraversalTree::SortSubdivisionCandidates(TraversalLeaf *node,
|
---|
| 455 | const int axis)
|
---|
[2073] | 456 | {
|
---|
| 457 | CLEAR_CONTAINER(*splitCandidates);
|
---|
| 458 | //splitCandidates->clear();
|
---|
| 459 |
|
---|
[2124] | 460 | int requestedSize = 2 * (int)node->mViewCells.size();
|
---|
[2073] | 461 |
|
---|
| 462 | // creates a sorted split candidates array
|
---|
| 463 | if (splitCandidates->capacity() > 500000 &&
|
---|
[2124] | 464 | requestedSize < (int)(splitCandidates->capacity() / 10) )
|
---|
[2093] | 465 | {
|
---|
| 466 | delete splitCandidates;
|
---|
| 467 | splitCandidates = new vector<SortableEntry *>;
|
---|
| 468 | }
|
---|
[2073] | 469 |
|
---|
[2093] | 470 | splitCandidates->reserve(requestedSize);
|
---|
[2073] | 471 |
|
---|
[2124] | 472 |
|
---|
[2093] | 473 | // insert all queries
|
---|
[2124] | 474 | for(ViewCellContainer::const_iterator mi = node->mViewCells.begin();
|
---|
| 475 | mi != node->mViewCells.end();
|
---|
[2093] | 476 | mi++)
|
---|
| 477 | {
|
---|
| 478 | AxisAlignedBox3 box = (*mi)->GetBox();
|
---|
| 479 |
|
---|
[2149] | 480 | //cout << "box: " << box << endl;
|
---|
[2124] | 481 | splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
|
---|
| 482 | box.Max(axis),
|
---|
| 483 | *mi)
|
---|
| 484 | );
|
---|
| 485 | }
|
---|
| 486 |
|
---|
| 487 | // insert all queries
|
---|
| 488 | for(ViewCellContainer::const_iterator mi = node->mViewCells.begin();
|
---|
| 489 | mi != node->mViewCells.end();
|
---|
| 490 | mi++)
|
---|
| 491 | {
|
---|
| 492 | AxisAlignedBox3 box = (*mi)->GetBox();
|
---|
| 493 |
|
---|
[2093] | 494 | splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN,
|
---|
| 495 | box.Min(axis),
|
---|
| 496 | *mi)
|
---|
| 497 | );
|
---|
[2124] | 498 | /*splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
|
---|
[2093] | 499 | box.Max(axis),
|
---|
| 500 | *mi)
|
---|
[2124] | 501 | );*/
|
---|
[2093] | 502 | }
|
---|
| 503 |
|
---|
| 504 | stable_sort(splitCandidates->begin(), splitCandidates->end(), iltS);
|
---|
[2073] | 505 | }
|
---|
| 506 |
|
---|
| 507 |
|
---|
| 508 | float
|
---|
[2093] | 509 | TraversalTree::BestCostRatio(TraversalLeaf *node,
|
---|
| 510 | const AxisAlignedBox3 &box,
|
---|
| 511 | const int axis,
|
---|
| 512 | float &position,
|
---|
| 513 | int &objectsBack,
|
---|
| 514 | int &objectsFront
|
---|
| 515 | )
|
---|
[2073] | 516 | {
|
---|
| 517 |
|
---|
[2149] | 518 | #define DEBUG_COST 1
|
---|
[2073] | 519 |
|
---|
| 520 | #if DEBUG_COST
|
---|
[2093] | 521 | static int nodeId = -1;
|
---|
| 522 | char filename[256];
|
---|
[2073] | 523 |
|
---|
[2093] | 524 | static int lastAxis = 100;
|
---|
[2149] | 525 |
|
---|
[2093] | 526 | if (axis <= lastAxis)
|
---|
[2149] | 527 | ++ nodeId;
|
---|
[2073] | 528 |
|
---|
[2093] | 529 | lastAxis = axis;
|
---|
| 530 |
|
---|
| 531 | sprintf(filename, "sah-cost%d-%d.log", nodeId, axis);
|
---|
| 532 | ofstream costStream;
|
---|
| 533 |
|
---|
| 534 | if (nodeId < 100)
|
---|
| 535 | costStream.open(filename);
|
---|
| 536 |
|
---|
[2073] | 537 | #endif
|
---|
| 538 |
|
---|
[2093] | 539 | SortSubdivisionCandidates(node, axis);
|
---|
[2073] | 540 |
|
---|
[2093] | 541 | // go through the lists, count the number of objects left and right
|
---|
| 542 | // and evaluate the following cost funcion:
|
---|
| 543 | // C = ct_div_ci + (ol + or)/queries
|
---|
[2073] | 544 |
|
---|
[2093] | 545 | vector<SortableEntry *>::const_iterator ci;
|
---|
[2073] | 546 |
|
---|
[2124] | 547 | int objectsLeft = 0, objectsRight = (int)node->mViewCells.size();
|
---|
[2073] | 548 |
|
---|
[2124] | 549 | int dummy1 = objectsLeft, dummy2 = objectsRight;
|
---|
[2093] | 550 |
|
---|
| 551 | float minBox = box.Min(axis);
|
---|
| 552 | float maxBox = box.Max(axis);
|
---|
| 553 | float boxArea = box.SurfaceArea();
|
---|
| 554 |
|
---|
| 555 | float minBand = minBox + mSplitBorder*(maxBox - minBox);
|
---|
| 556 | float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
|
---|
| 557 |
|
---|
| 558 | float minSum = 1e20f;
|
---|
| 559 |
|
---|
[2149] | 560 | int openBoxes = 0;
|
---|
| 561 |
|
---|
[2093] | 562 | for(ci = splitCandidates->begin(); ci < splitCandidates->end(); ++ ci)
|
---|
| 563 | {
|
---|
| 564 | switch ((*ci)->type)
|
---|
| 565 | {
|
---|
| 566 | case SortableEntry::BOX_MIN:
|
---|
[2124] | 567 | ++ objectsLeft;
|
---|
[2149] | 568 | ++ openBoxes;
|
---|
[2093] | 569 | break;
|
---|
| 570 | case SortableEntry::BOX_MAX:
|
---|
[2124] | 571 | -- objectsRight;
|
---|
[2149] | 572 | -- openBoxes;
|
---|
[2093] | 573 | break;
|
---|
| 574 | }
|
---|
| 575 |
|
---|
[2124] | 576 | if ((*ci)->value >= minBand && (*ci)->value <= maxBand)
|
---|
[2093] | 577 | {
|
---|
| 578 | AxisAlignedBox3 lbox = box;
|
---|
| 579 | AxisAlignedBox3 rbox = box;
|
---|
[2124] | 580 |
|
---|
[2093] | 581 | lbox.SetMax(axis, (*ci)->value);
|
---|
| 582 | rbox.SetMin(axis, (*ci)->value);
|
---|
| 583 |
|
---|
[2124] | 584 | const float sum = objectsLeft * lbox.SurfaceArea() + objectsRight * rbox.SurfaceArea();
|
---|
[2093] | 585 |
|
---|
[2124] | 586 | // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
|
---|
| 587 | // cout<<"cost= "<<sum<<endl;
|
---|
[2093] | 588 |
|
---|
[2073] | 589 | #if DEBUG_COST
|
---|
[2093] | 590 | if (nodeId < 100)
|
---|
| 591 | {
|
---|
[2124] | 592 | float oldCost = (float)node->mViewCells.size();
|
---|
[2149] | 593 | float newCost = mCt_div_ci + sum / boxArea;
|
---|
[2124] | 594 | float ratio = newCost / oldCost;
|
---|
[2149] | 595 |
|
---|
| 596 | costStream << (*ci)->value << " " << ratio << " open: " << openBoxes;
|
---|
| 597 |
|
---|
| 598 | if ((*ci)->type == SortableEntry::BOX_MAX)
|
---|
| 599 | costStream << " max event" << endl;
|
---|
| 600 | else
|
---|
| 601 | costStream << " min event" << endl;
|
---|
[2093] | 602 | }
|
---|
[2073] | 603 | #endif
|
---|
[2093] | 604 |
|
---|
| 605 | if (sum < minSum)
|
---|
| 606 | {
|
---|
| 607 | minSum = sum;
|
---|
| 608 | position = (*ci)->value;
|
---|
| 609 |
|
---|
| 610 | objectsBack = objectsLeft;
|
---|
| 611 | objectsFront = objectsRight;
|
---|
| 612 | }
|
---|
| 613 | }
|
---|
| 614 | }
|
---|
| 615 |
|
---|
[2124] | 616 | const float oldCost = (float)node->mViewCells.size();
|
---|
| 617 | const float newCost = mCt_div_ci + minSum / boxArea;
|
---|
| 618 | const float ratio = newCost / oldCost;
|
---|
[2093] | 619 |
|
---|
[2124] | 620 | //if (boxArea == 0)
|
---|
| 621 | // cout << "error: " << boxArea << endl;
|
---|
| 622 | if (ratio > 2)
|
---|
| 623 | {
|
---|
| 624 | cout << "costratio: " << ratio << " oldcost: " << oldCost << " box area: " << boxArea << " new: " << newCost << endl;
|
---|
| 625 | cout << "obj left: " <<objectsBack<< " obj right: " << objectsFront << endl;
|
---|
| 626 | cout << "dummy1: " << dummy1 << " dummy2: " << dummy2 << endl;
|
---|
| 627 | }
|
---|
[2073] | 628 | #if 0
|
---|
[2093] | 629 | cout<<"===================="<<endl;
|
---|
| 630 | cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
|
---|
| 631 | <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
|
---|
[2073] | 632 | #endif
|
---|
[2124] | 633 |
|
---|
[2093] | 634 | return ratio;
|
---|
[2073] | 635 | }
|
---|
| 636 |
|
---|
| 637 |
|
---|
[2124] | 638 | int TraversalTree::FindViewCellIntersections(const Vector3 &lStart,
|
---|
| 639 | const Vector3 &lEnd,
|
---|
| 640 | const ViewCellContainer &viewCells,
|
---|
| 641 | ViewCellContainer &hitViewCells,
|
---|
| 642 | const bool useMailboxing)
|
---|
| 643 | {
|
---|
| 644 | int hits = 0;
|
---|
| 645 | ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
|
---|
| 646 |
|
---|
| 647 | for (vit = viewCells.begin(); vit != vit_end; ++ vit)
|
---|
| 648 | {
|
---|
| 649 | ViewCell *viewCell = *vit;
|
---|
| 650 | // don't have to mail if each view cell belongs to exactly one leaf
|
---|
| 651 | if (!useMailboxing || !viewCell->Mailed())
|
---|
| 652 | {
|
---|
| 653 | if (useMailboxing)
|
---|
| 654 | viewCell->Mail();
|
---|
| 655 |
|
---|
| 656 | // hack: assume that we use vsp tree,
|
---|
| 657 | //P so we can just test intersection with bounding boxes
|
---|
[2130] | 658 | if (viewCell->GetBox().Intersects(lStart, lEnd))
|
---|
[2124] | 659 | {
|
---|
| 660 | hitViewCells.push_back(viewCell);
|
---|
| 661 | ++ hits;
|
---|
| 662 | }
|
---|
| 663 | }
|
---|
| 664 | }
|
---|
| 665 |
|
---|
| 666 | return hits;
|
---|
| 667 | }
|
---|
| 668 |
|
---|
| 669 |
|
---|
[2073] | 670 | int TraversalTree::CastLineSegment(const Vector3 &origin,
|
---|
[2093] | 671 | const Vector3 &termination,
|
---|
[2124] | 672 | ViewCellContainer &viewCells,
|
---|
[2093] | 673 | const bool useMailboxing)
|
---|
[2073] | 674 | {
|
---|
| 675 | int hits = 0;
|
---|
| 676 |
|
---|
| 677 | float mint = 0.0f, maxt = 1.0f;
|
---|
| 678 | const Vector3 dir = termination - origin;
|
---|
| 679 |
|
---|
[2093] | 680 | stack<LineTraversalData> tStack;
|
---|
[2073] | 681 |
|
---|
| 682 | Vector3 entp = origin;
|
---|
| 683 | Vector3 extp = termination;
|
---|
| 684 |
|
---|
| 685 | TraversalNode *node = mRoot;
|
---|
| 686 | TraversalNode *farChild;
|
---|
| 687 |
|
---|
| 688 | float position;
|
---|
| 689 | int axis;
|
---|
| 690 |
|
---|
| 691 | while (1)
|
---|
| 692 | {
|
---|
| 693 | if (!node->IsLeaf())
|
---|
| 694 | {
|
---|
| 695 | TraversalInterior *in = static_cast<TraversalInterior *>(node);
|
---|
| 696 | position = in->mPosition;
|
---|
| 697 | axis = in->mAxis;
|
---|
| 698 |
|
---|
| 699 | if (entp[axis] <= position)
|
---|
| 700 | {
|
---|
| 701 | if (extp[axis] <= position)
|
---|
| 702 | {
|
---|
| 703 | node = in->mBack;
|
---|
| 704 | // cases N1,N2,N3,P5,Z2,Z3
|
---|
| 705 | continue;
|
---|
[2093] | 706 | } else
|
---|
[2073] | 707 | {
|
---|
| 708 | // case N4
|
---|
| 709 | node = in->mBack;
|
---|
| 710 | farChild = in->mFront;
|
---|
| 711 | }
|
---|
| 712 | }
|
---|
| 713 | else
|
---|
| 714 | {
|
---|
| 715 | if (position <= extp[axis])
|
---|
| 716 | {
|
---|
| 717 | node = in->mFront;
|
---|
| 718 | // cases P1,P2,P3,N5,Z1
|
---|
| 719 | continue;
|
---|
| 720 | }
|
---|
| 721 | else
|
---|
| 722 | {
|
---|
| 723 | node = in->mFront;
|
---|
| 724 | farChild = in->mBack;
|
---|
| 725 | // case P4
|
---|
| 726 | }
|
---|
| 727 | }
|
---|
| 728 |
|
---|
| 729 | // $$ modification 3.5.2004 - hints from Kamil Ghais
|
---|
| 730 | // case N4 or P4
|
---|
[2093] | 731 | const float tdist = (position - origin[axis]) / dir[axis];
|
---|
| 732 | tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
|
---|
| 733 |
|
---|
[2073] | 734 | extp = origin + dir * tdist;
|
---|
| 735 | maxt = tdist;
|
---|
| 736 | }
|
---|
| 737 | else
|
---|
| 738 | {
|
---|
| 739 | // compute intersection with all objects in this leaf
|
---|
| 740 | TraversalLeaf *leaf = static_cast<TraversalLeaf *>(node);
|
---|
| 741 |
|
---|
[2124] | 742 | hits += FindViewCellIntersections(origin,
|
---|
| 743 | termination,
|
---|
| 744 | leaf->mViewCells,
|
---|
| 745 | viewCells,
|
---|
| 746 | useMailboxing);
|
---|
| 747 |
|
---|
[2073] | 748 | // get the next node from the stack
|
---|
| 749 | if (tStack.empty())
|
---|
| 750 | break;
|
---|
| 751 |
|
---|
| 752 | entp = extp;
|
---|
| 753 | mint = maxt;
|
---|
| 754 |
|
---|
[2093] | 755 | LineTraversalData &s = tStack.top();
|
---|
[2073] | 756 | node = s.mNode;
|
---|
| 757 | extp = s.mExitPoint;
|
---|
| 758 | maxt = s.mMaxT;
|
---|
[2093] | 759 |
|
---|
[2073] | 760 | tStack.pop();
|
---|
| 761 | }
|
---|
| 762 | }
|
---|
| 763 |
|
---|
| 764 | return hits;
|
---|
| 765 | }
|
---|
| 766 |
|
---|
| 767 |
|
---|
[2093] | 768 | void TraversalTree::CollectLeaves(vector<TraversalLeaf *> &leaves)
|
---|
[2073] | 769 | {
|
---|
[2093] | 770 | stack<TraversalNode *> nodeStack;
|
---|
| 771 | nodeStack.push(mRoot);
|
---|
[2073] | 772 |
|
---|
[2093] | 773 | while (!nodeStack.empty())
|
---|
| 774 | {
|
---|
| 775 | TraversalNode *node = nodeStack.top();
|
---|
| 776 | nodeStack.pop();
|
---|
| 777 |
|
---|
| 778 | if (node->IsLeaf())
|
---|
| 779 | {
|
---|
| 780 | TraversalLeaf *leaf = (TraversalLeaf *)node;
|
---|
| 781 | leaves.push_back(leaf);
|
---|
| 782 | }
|
---|
| 783 | else
|
---|
| 784 | {
|
---|
| 785 | TraversalInterior *interior = (TraversalInterior *)node;
|
---|
| 786 | nodeStack.push(interior->mBack);
|
---|
| 787 | nodeStack.push(interior->mFront);
|
---|
| 788 | }
|
---|
| 789 | }
|
---|
[2073] | 790 | }
|
---|
| 791 |
|
---|
| 792 |
|
---|
[2093] | 793 | AxisAlignedBox3 TraversalTree::GetBox(const TraversalNode *node) const
|
---|
| 794 | {
|
---|
| 795 | TraversalInterior *parent = node->mParent;
|
---|
| 796 |
|
---|
| 797 | if (parent == NULL)
|
---|
| 798 | return mBox;
|
---|
| 799 |
|
---|
| 800 | if (!node->IsLeaf())
|
---|
| 801 | return ((TraversalInterior *)node)->mBox;
|
---|
| 802 |
|
---|
| 803 | AxisAlignedBox3 box(parent->mBox);
|
---|
| 804 |
|
---|
| 805 | if (parent->mFront == node)
|
---|
| 806 | box.SetMin(parent->mAxis, parent->mPosition);
|
---|
| 807 | else
|
---|
| 808 | box.SetMax(parent->mAxis, parent->mPosition);
|
---|
| 809 | return box;
|
---|
[2073] | 810 | }
|
---|
[2093] | 811 |
|
---|
| 812 | }
|
---|