[727] | 1 | #include <stack>
|
---|
| 2 | #include <time.h>
|
---|
| 3 | #include <iomanip>
|
---|
| 4 |
|
---|
| 5 | #include "Plane3.h"
|
---|
| 6 | #include "VspBspTree.h"
|
---|
| 7 | #include "Mesh.h"
|
---|
| 8 | #include "common.h"
|
---|
| 9 | #include "ViewCell.h"
|
---|
| 10 | #include "Environment.h"
|
---|
| 11 | #include "Polygon3.h"
|
---|
| 12 | #include "Ray.h"
|
---|
| 13 | #include "AxisAlignedBox3.h"
|
---|
| 14 | #include "Exporter.h"
|
---|
| 15 | #include "Plane3.h"
|
---|
| 16 | #include "ViewCellBsp.h"
|
---|
| 17 | #include "ViewCellsManager.h"
|
---|
| 18 | #include "Beam.h"
|
---|
| 19 |
|
---|
| 20 | #define USE_FIXEDPOINT_T 0
|
---|
| 21 |
|
---|
| 22 |
|
---|
| 23 | //-- static members
|
---|
| 24 |
|
---|
| 25 |
|
---|
| 26 | int VspBspTree::sFrontId = 0;
|
---|
| 27 | int VspBspTree::sBackId = 0;
|
---|
| 28 | int VspBspTree::sFrontAndBackId = 0;
|
---|
| 29 |
|
---|
| 30 | typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
|
---|
| 31 |
|
---|
| 32 |
|
---|
| 33 | // pvs penalty can be different from pvs size
|
---|
| 34 | inline float EvalPvsPenalty(const int pvs,
|
---|
| 35 | const int lower,
|
---|
| 36 | const int upper)
|
---|
| 37 | {
|
---|
| 38 | // clamp to minmax values
|
---|
| 39 | if (pvs < lower)
|
---|
| 40 | return (float)lower;
|
---|
| 41 | if (pvs > upper)
|
---|
| 42 | return (float)upper;
|
---|
| 43 |
|
---|
| 44 | return (float)pvs;
|
---|
| 45 | }
|
---|
| 46 |
|
---|
| 47 |
|
---|
| 48 |
|
---|
| 49 |
|
---|
| 50 | /******************************************************************************/
|
---|
| 51 | /* class ViewCellBspTree implementation */
|
---|
| 52 | /******************************************************************************/
|
---|
| 53 |
|
---|
| 54 |
|
---|
| 55 | BspViewCell *VspBspTree::GetOutOfBoundsCell()
|
---|
| 56 | {
|
---|
| 57 | return mOutOfBoundsCell;
|
---|
| 58 | }
|
---|
| 59 |
|
---|
| 60 | VspBspTree::~VspBspTree()
|
---|
| 61 | {
|
---|
| 62 | DEL_PTR(mRoot);
|
---|
| 63 | }
|
---|
| 64 |
|
---|
| 65 | void VspBspTree::CollectViewCells(BspNode *root,
|
---|
| 66 | bool onlyValid,
|
---|
| 67 | ViewCellContainer &viewCells,
|
---|
| 68 | bool onlyUnmailed) const
|
---|
| 69 | {
|
---|
| 70 | stack<BspNode *> nodeStack;
|
---|
| 71 |
|
---|
| 72 | if (!root)
|
---|
| 73 | return;
|
---|
| 74 |
|
---|
| 75 | nodeStack.push(root);
|
---|
| 76 |
|
---|
| 77 | while (!nodeStack.empty())
|
---|
| 78 | {
|
---|
| 79 | BspNode *node = nodeStack.top();
|
---|
| 80 | nodeStack.pop();
|
---|
| 81 |
|
---|
| 82 | if (node->IsLeaf())
|
---|
| 83 | {
|
---|
| 84 | if (!onlyValid || node->TreeValid())
|
---|
| 85 | {
|
---|
| 86 | ViewCell *leafVc = dynamic_cast<BspLeaf *>(node)->GetViewCell();
|
---|
| 87 |
|
---|
| 88 | ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
|
---|
| 89 |
|
---|
| 90 | if (!onlyUnmailed || !viewCell->Mailed())
|
---|
| 91 | {
|
---|
| 92 | viewCell->Mail();
|
---|
| 93 | viewCells.push_back(viewCell);
|
---|
| 94 | }
|
---|
| 95 | }
|
---|
| 96 | }
|
---|
| 97 | else
|
---|
| 98 | {
|
---|
| 99 | BspInterior *interior = dynamic_cast<BspInterior *>(node);
|
---|
| 100 |
|
---|
| 101 | nodeStack.push(interior->GetFront());
|
---|
| 102 | nodeStack.push(interior->GetBack());
|
---|
| 103 | }
|
---|
| 104 | }
|
---|
| 105 |
|
---|
| 106 | }
|
---|
| 107 |
|
---|
| 108 |
|
---|
| 109 | int ViewCellBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
|
---|
| 110 | const bool onlyUnmailed) const
|
---|
| 111 | {
|
---|
| 112 | stack<bspNodePair> nodeStack;
|
---|
| 113 |
|
---|
| 114 | BspNodeGeometry nodeGeom;
|
---|
| 115 | ConstructGeometry(n, nodeGeom);
|
---|
| 116 |
|
---|
| 117 | // split planes from the root to this node
|
---|
| 118 | // needed to verify that we found neighbor leaf
|
---|
| 119 | // TODO: really needed?
|
---|
| 120 | vector<Plane3> halfSpaces;
|
---|
| 121 | ExtractHalfSpaces(n, halfSpaces);
|
---|
| 122 |
|
---|
| 123 |
|
---|
| 124 | BspNodeGeometry *rgeom = new BspNodeGeometry();
|
---|
| 125 | ConstructGeometry(mRoot, *rgeom);
|
---|
| 126 |
|
---|
| 127 | nodeStack.push(bspNodePair(mRoot, rgeom));
|
---|
| 128 |
|
---|
| 129 | while (!nodeStack.empty())
|
---|
| 130 | {
|
---|
| 131 | BspNode *node = nodeStack.top().first;
|
---|
| 132 | BspNodeGeometry *geom = nodeStack.top().second;
|
---|
| 133 |
|
---|
| 134 | nodeStack.pop();
|
---|
| 135 |
|
---|
| 136 | if (node->IsLeaf())
|
---|
| 137 | {
|
---|
| 138 | // test if this leaf is in valid view space
|
---|
| 139 | if (node->TreeValid() &&
|
---|
| 140 | (node != n) &&
|
---|
| 141 | (!onlyUnmailed || !node->Mailed()))
|
---|
| 142 | {
|
---|
| 143 | bool isAdjacent = true;
|
---|
| 144 |
|
---|
| 145 | if (1)
|
---|
| 146 | {
|
---|
| 147 | // test all planes of current node if still adjacent
|
---|
| 148 | for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
|
---|
| 149 | {
|
---|
| 150 | const int cf =
|
---|
| 151 | Polygon3::ClassifyPlane(geom->GetPolys(),
|
---|
| 152 | halfSpaces[i],
|
---|
| 153 | mEpsilon);
|
---|
| 154 |
|
---|
| 155 | if (cf == Polygon3::FRONT_SIDE)
|
---|
| 156 | {
|
---|
| 157 | isAdjacent = false;
|
---|
| 158 | }
|
---|
| 159 | }
|
---|
| 160 | }
|
---|
| 161 | else
|
---|
| 162 | {
|
---|
| 163 | // TODO: why is this wrong??
|
---|
| 164 | // test all planes of current node if still adjacent
|
---|
| 165 | for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i)
|
---|
| 166 | {
|
---|
| 167 | Polygon3 *poly = nodeGeom.GetPolys()[i];
|
---|
| 168 |
|
---|
| 169 | const int cf =
|
---|
| 170 | Polygon3::ClassifyPlane(geom->GetPolys(),
|
---|
| 171 | poly->GetSupportingPlane(),
|
---|
| 172 | mEpsilon);
|
---|
| 173 |
|
---|
| 174 | if (cf == Polygon3::FRONT_SIDE)
|
---|
| 175 | {
|
---|
| 176 | isAdjacent = false;
|
---|
| 177 | }
|
---|
| 178 | }
|
---|
| 179 | }
|
---|
| 180 | // neighbor was found
|
---|
| 181 | if (isAdjacent)
|
---|
| 182 | {
|
---|
| 183 | neighbors.push_back(dynamic_cast<BspLeaf *>(node));
|
---|
| 184 | }
|
---|
| 185 | }
|
---|
| 186 | }
|
---|
| 187 | else
|
---|
| 188 | {
|
---|
| 189 | BspInterior *interior = dynamic_cast<BspInterior *>(node);
|
---|
| 190 |
|
---|
| 191 | const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
|
---|
| 192 | interior->GetPlane(),
|
---|
| 193 | mEpsilon);
|
---|
| 194 |
|
---|
| 195 | BspNode *front = interior->GetFront();
|
---|
| 196 | BspNode *back = interior->GetBack();
|
---|
| 197 |
|
---|
| 198 | BspNodeGeometry *fGeom = new BspNodeGeometry();
|
---|
| 199 | BspNodeGeometry *bGeom = new BspNodeGeometry();
|
---|
| 200 |
|
---|
| 201 | geom->SplitGeometry(*fGeom,
|
---|
| 202 | *bGeom,
|
---|
| 203 | interior->GetPlane(),
|
---|
| 204 | mBox,
|
---|
| 205 | //0.0000001f);
|
---|
| 206 | mEpsilon);
|
---|
| 207 |
|
---|
| 208 | if (cf == Polygon3::BACK_SIDE)
|
---|
| 209 | {
|
---|
| 210 | nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
|
---|
| 211 | DEL_PTR(fGeom);
|
---|
| 212 | }
|
---|
| 213 | else
|
---|
| 214 | {
|
---|
| 215 | if (cf == Polygon3::FRONT_SIDE)
|
---|
| 216 | {
|
---|
| 217 | nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
|
---|
| 218 | DEL_PTR(bGeom);
|
---|
| 219 | }
|
---|
| 220 | else
|
---|
| 221 | { // random decision
|
---|
| 222 | nodeStack.push(bspNodePair(front, fGeom));
|
---|
| 223 | nodeStack.push(bspNodePair(back, bGeom));
|
---|
| 224 | }
|
---|
| 225 | }
|
---|
| 226 | }
|
---|
| 227 |
|
---|
| 228 | DEL_PTR(geom);
|
---|
| 229 | }
|
---|
| 230 |
|
---|
| 231 | return (int)neighbors.size();
|
---|
| 232 | }
|
---|
| 233 |
|
---|
| 234 |
|
---|
| 235 |
|
---|
| 236 | BspLeaf *ViewCellBspTree::GetRandomLeaf(const Plane3 &halfspace)
|
---|
| 237 | {
|
---|
| 238 | stack<BspNode *> nodeStack;
|
---|
| 239 | nodeStack.push(mRoot);
|
---|
| 240 |
|
---|
| 241 | int mask = rand();
|
---|
| 242 |
|
---|
| 243 | while (!nodeStack.empty())
|
---|
| 244 | {
|
---|
| 245 | BspNode *node = nodeStack.top();
|
---|
| 246 | nodeStack.pop();
|
---|
| 247 |
|
---|
| 248 | if (node->IsLeaf())
|
---|
| 249 | {
|
---|
| 250 | return dynamic_cast<BspLeaf *>(node);
|
---|
| 251 | }
|
---|
| 252 | else
|
---|
| 253 | {
|
---|
| 254 | BspInterior *interior = dynamic_cast<BspInterior *>(node);
|
---|
| 255 | BspNode *next;
|
---|
| 256 | BspNodeGeometry geom;
|
---|
| 257 |
|
---|
| 258 | // todo: not very efficient: constructs full cell everytime
|
---|
| 259 | ConstructGeometry(interior, geom);
|
---|
| 260 |
|
---|
| 261 | const int cf =
|
---|
| 262 | Polygon3::ClassifyPlane(geom.GetPolys(), halfspace, mEpsilon);
|
---|
| 263 |
|
---|
| 264 | if (cf == Polygon3::BACK_SIDE)
|
---|
| 265 | next = interior->GetFront();
|
---|
| 266 | else
|
---|
| 267 | if (cf == Polygon3::FRONT_SIDE)
|
---|
| 268 | next = interior->GetFront();
|
---|
| 269 | else
|
---|
| 270 | {
|
---|
| 271 | // random decision
|
---|
| 272 | if (mask & 1)
|
---|
| 273 | next = interior->GetBack();
|
---|
| 274 | else
|
---|
| 275 | next = interior->GetFront();
|
---|
| 276 | mask = mask >> 1;
|
---|
| 277 | }
|
---|
| 278 |
|
---|
| 279 | nodeStack.push(next);
|
---|
| 280 | }
|
---|
| 281 | }
|
---|
| 282 |
|
---|
| 283 | return NULL;
|
---|
| 284 | }
|
---|
| 285 |
|
---|
| 286 |
|
---|
| 287 | BspLeaf *ViewCellBspTree::GetRandomLeaf(const bool onlyUnmailed)
|
---|
| 288 | {
|
---|
| 289 | stack<BspNode *> nodeStack;
|
---|
| 290 |
|
---|
| 291 | nodeStack.push(mRoot);
|
---|
| 292 |
|
---|
| 293 | int mask = rand();
|
---|
| 294 |
|
---|
| 295 | while (!nodeStack.empty())
|
---|
| 296 | {
|
---|
| 297 | BspNode *node = nodeStack.top();
|
---|
| 298 | nodeStack.pop();
|
---|
| 299 |
|
---|
| 300 | if (node->IsLeaf())
|
---|
| 301 | {
|
---|
| 302 | if ( (!onlyUnmailed || !node->Mailed()) )
|
---|
| 303 | return dynamic_cast<BspLeaf *>(node);
|
---|
| 304 | }
|
---|
| 305 | else
|
---|
| 306 | {
|
---|
| 307 | BspInterior *interior = dynamic_cast<BspInterior *>(node);
|
---|
| 308 |
|
---|
| 309 | // random decision
|
---|
| 310 | if (mask & 1)
|
---|
| 311 | nodeStack.push(interior->GetBack());
|
---|
| 312 | else
|
---|
| 313 | nodeStack.push(interior->GetFront());
|
---|
| 314 |
|
---|
| 315 | mask = mask >> 1;
|
---|
| 316 | }
|
---|
| 317 | }
|
---|
| 318 |
|
---|
| 319 | return NULL;
|
---|
| 320 | }
|
---|
| 321 |
|
---|
| 322 |
|
---|
| 323 | float ViewCellBspTree::GetEpsilon() const
|
---|
| 324 | {
|
---|
| 325 | return mEpsilon;
|
---|
| 326 | }
|
---|
| 327 |
|
---|
| 328 |
|
---|
| 329 | int ViewCellBspTree::CastLineSegment(const Vector3 &origin,
|
---|
| 330 | const Vector3 &termination,
|
---|
| 331 | vector<ViewCell *> &viewcells)
|
---|
| 332 | {
|
---|
| 333 | int hits = 0;
|
---|
| 334 | stack<BspRayTraversalData> tQueue;
|
---|
| 335 |
|
---|
| 336 | float mint = 0.0f, maxt = 1.0f;
|
---|
| 337 |
|
---|
| 338 | Intersectable::NewMail();
|
---|
| 339 | ViewCell::NewMail();
|
---|
| 340 |
|
---|
| 341 | Vector3 entp = origin;
|
---|
| 342 | Vector3 extp = termination;
|
---|
| 343 |
|
---|
| 344 | BspNode *node = mRoot;
|
---|
| 345 | BspNode *farChild = NULL;
|
---|
| 346 |
|
---|
| 347 | float t;
|
---|
| 348 | const float thresh = 1e-6f; // matt: change this
|
---|
| 349 |
|
---|
| 350 | while (1)
|
---|
| 351 | {
|
---|
| 352 | if (!node->IsLeaf())
|
---|
| 353 | {
|
---|
| 354 | BspInterior *in = dynamic_cast<BspInterior *>(node);
|
---|
| 355 |
|
---|
| 356 | Plane3 splitPlane = in->GetPlane();
|
---|
| 357 |
|
---|
| 358 | const int entSide = splitPlane.Side(entp, thresh);
|
---|
| 359 | const int extSide = splitPlane.Side(extp, thresh);
|
---|
| 360 |
|
---|
| 361 | if (entSide < 0)
|
---|
| 362 | {
|
---|
| 363 | node = in->GetBack();
|
---|
| 364 |
|
---|
| 365 | // plane does not split ray => no far child
|
---|
| 366 | if (extSide <= 0)
|
---|
| 367 | continue;
|
---|
| 368 |
|
---|
| 369 | farChild = in->GetFront(); // plane splits ray
|
---|
| 370 | }
|
---|
| 371 | else if (entSide > 0)
|
---|
| 372 | {
|
---|
| 373 | node = in->GetFront();
|
---|
| 374 |
|
---|
| 375 | if (extSide >= 0) // plane does not split ray => no far child
|
---|
| 376 | continue;
|
---|
| 377 |
|
---|
| 378 | farChild = in->GetBack(); // plane splits ray
|
---|
| 379 | }
|
---|
| 380 | else // one of the ray end points is on the plane
|
---|
| 381 | { // NOTE: what to do if ray is coincident with plane?
|
---|
| 382 | if (extSide < 0)
|
---|
| 383 | node = in->GetBack();
|
---|
| 384 | else //if (extSide > 0)
|
---|
| 385 | node = in->GetFront();
|
---|
| 386 | //else break; // coincident => count no intersections
|
---|
| 387 |
|
---|
| 388 | continue; // no far child
|
---|
| 389 | }
|
---|
| 390 |
|
---|
| 391 | // push data for far child
|
---|
| 392 | tQueue.push(BspRayTraversalData(farChild, extp));
|
---|
| 393 |
|
---|
| 394 | // find intersection of ray segment with plane
|
---|
| 395 | extp = splitPlane.FindIntersection(origin, extp, &t);
|
---|
| 396 | }
|
---|
| 397 | else
|
---|
| 398 | {
|
---|
| 399 | // reached leaf => intersection with view cell
|
---|
| 400 | BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
|
---|
| 401 | ViewCell *viewCell;
|
---|
| 402 |
|
---|
| 403 | if (0)
|
---|
| 404 | viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
|
---|
| 405 | else
|
---|
| 406 | viewCell = leaf->GetViewCell();
|
---|
| 407 |
|
---|
| 408 | if (!viewCell->Mailed())
|
---|
| 409 | {
|
---|
| 410 | viewcells.push_back(viewCell);
|
---|
| 411 | viewCell->Mail();
|
---|
| 412 | ++ hits;
|
---|
| 413 | }
|
---|
| 414 |
|
---|
| 415 | //-- fetch the next far child from the stack
|
---|
| 416 | if (tQueue.empty())
|
---|
| 417 | break;
|
---|
| 418 |
|
---|
| 419 | entp = extp;
|
---|
| 420 |
|
---|
| 421 | BspRayTraversalData &s = tQueue.top();
|
---|
| 422 |
|
---|
| 423 | node = s.mNode;
|
---|
| 424 | extp = s.mExitPoint;
|
---|
| 425 |
|
---|
| 426 | tQueue.pop();
|
---|
| 427 | }
|
---|
| 428 | }
|
---|
| 429 |
|
---|
| 430 | return hits;
|
---|
| 431 | }
|
---|
| 432 |
|
---|
| 433 |
|
---|
| 434 | bool ViewCellBspTree::ViewPointValid(const Vector3 &viewPoint) const
|
---|
| 435 | {
|
---|
| 436 | BspNode *node = mRoot;
|
---|
| 437 |
|
---|
| 438 | while (1)
|
---|
| 439 | {
|
---|
| 440 | // early exit
|
---|
| 441 | if (node->TreeValid())
|
---|
| 442 | return true;
|
---|
| 443 |
|
---|
| 444 | if (node->IsLeaf())
|
---|
| 445 | return false;
|
---|
| 446 |
|
---|
| 447 | BspInterior *in = dynamic_cast<BspInterior *>(node);
|
---|
| 448 |
|
---|
| 449 | if (in->GetPlane().Side(viewPoint) <= 0)
|
---|
| 450 | {
|
---|
| 451 | node = in->GetBack();
|
---|
| 452 | }
|
---|
| 453 | else
|
---|
| 454 | {
|
---|
| 455 | node = in->GetFront();
|
---|
| 456 | }
|
---|
| 457 | }
|
---|
| 458 |
|
---|
| 459 | // should never come here
|
---|
| 460 | return false;
|
---|
| 461 | } |
---|