[162] | 1 | #ifndef _KdTree_H__ |
---|
| 2 | #define _KdTree_H__ |
---|
| 3 | |
---|
| 4 | #include <functional> |
---|
| 5 | using namespace std; |
---|
| 6 | |
---|
| 7 | #include "Containers.h" |
---|
| 8 | #include "AxisAlignedBox3.h" |
---|
| 9 | #include "Ray.h" |
---|
[191] | 10 | #include "Pvs.h" |
---|
[162] | 11 | |
---|
| 12 | |
---|
| 13 | class KdNode; |
---|
| 14 | class KdLeaf; |
---|
| 15 | class KdInterior; |
---|
[176] | 16 | class Intersectable; |
---|
[162] | 17 | |
---|
| 18 | |
---|
| 19 | // -------------------------------------------------------------- |
---|
| 20 | // Static statistics for kd-tree search |
---|
| 21 | // -------------------------------------------------------------- |
---|
| 22 | class KdTreeStatistics |
---|
| 23 | { |
---|
| 24 | public: |
---|
| 25 | // total number of nodes |
---|
| 26 | int nodes; |
---|
| 27 | // number of splits along each of the axes |
---|
| 28 | int splits[7]; |
---|
| 29 | // totals number of rays |
---|
| 30 | int rays; |
---|
| 31 | // total number of query domains |
---|
| 32 | int queryDomains; |
---|
| 33 | // total number of ray references |
---|
| 34 | int rayRefs; |
---|
| 35 | // refs in non empty leafs |
---|
| 36 | int rayRefsNonZeroQuery; |
---|
| 37 | // total number of query references |
---|
| 38 | int objectRefs; |
---|
| 39 | // nodes with zero queries |
---|
| 40 | int zeroQueryNodes; |
---|
| 41 | // max depth nodes |
---|
| 42 | int maxDepthNodes; |
---|
| 43 | // max depth nodes |
---|
| 44 | int minCostNodes; |
---|
| 45 | // max number of rays per node |
---|
| 46 | int maxObjectRefs; |
---|
| 47 | // number of dynamically added ray refs |
---|
| 48 | int addedRayRefs; |
---|
| 49 | // number of dynamically removed ray refs |
---|
| 50 | int removedRayRefs; |
---|
| 51 | |
---|
| 52 | // Constructor |
---|
| 53 | KdTreeStatistics() { |
---|
| 54 | Reset(); |
---|
| 55 | } |
---|
| 56 | |
---|
| 57 | int Nodes() const {return nodes;} |
---|
| 58 | int Interior() const { return nodes/2; } |
---|
| 59 | int Leaves() const { return (nodes/2) + 1; } |
---|
| 60 | |
---|
| 61 | void Reset() { |
---|
| 62 | nodes = 0; |
---|
| 63 | for (int i=0; i<7; i++) |
---|
| 64 | splits[i] = 0; |
---|
| 65 | rays = queryDomains = 0; |
---|
| 66 | rayRefs = rayRefsNonZeroQuery = objectRefs = 0; |
---|
| 67 | zeroQueryNodes = 0; |
---|
| 68 | maxDepthNodes = 0; |
---|
| 69 | minCostNodes = 0; |
---|
| 70 | maxObjectRefs = 0; |
---|
| 71 | addedRayRefs = removedRayRefs = 0; |
---|
| 72 | } |
---|
| 73 | |
---|
| 74 | void |
---|
| 75 | Print(ostream &app) const; |
---|
| 76 | |
---|
| 77 | friend ostream &operator<<(ostream &s, const KdTreeStatistics &stat) { |
---|
| 78 | stat.Print(s); |
---|
| 79 | return s; |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | }; |
---|
| 83 | |
---|
| 84 | |
---|
| 85 | class KdInterior; |
---|
| 86 | /** Abstract class for kd-tree node */ |
---|
| 87 | class KdNode { |
---|
| 88 | public: |
---|
[177] | 89 | static int mailID; |
---|
| 90 | int mailbox; |
---|
| 91 | |
---|
| 92 | void Mail() { mailbox = mailID; } |
---|
| 93 | static void NewMail() { mailID++; } |
---|
| 94 | bool Mailed() const { return mailbox == mailID; } |
---|
| 95 | |
---|
| 96 | |
---|
[162] | 97 | KdNode(KdInterior *parent); |
---|
| 98 | |
---|
| 99 | /** Determines whether this node is a leaf or interior node |
---|
| 100 | @return true if leaf |
---|
| 101 | */ |
---|
| 102 | virtual bool IsLeaf() const = 0; |
---|
| 103 | |
---|
| 104 | /** Determines whether this node is the root of the tree |
---|
| 105 | @return true if root |
---|
| 106 | */ |
---|
| 107 | virtual bool IsRoot() const { |
---|
| 108 | return mParent == NULL; |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | /** Parent of the node - the parent is a little overhead for maintanance of the tree, |
---|
| 112 | but allows various optimizations of tree traversal algorithms */ |
---|
| 113 | KdInterior *mParent; |
---|
| 114 | int mDepth; |
---|
| 115 | }; |
---|
| 116 | |
---|
| 117 | /** Implementation of the kd-tree interior node */ |
---|
| 118 | class KdInterior : public KdNode { |
---|
| 119 | |
---|
| 120 | public: |
---|
| 121 | |
---|
| 122 | KdInterior(KdInterior *parent):KdNode(parent), mBack(NULL), mFront(NULL) {} |
---|
| 123 | |
---|
| 124 | /** \sa KdNode::IsLeaf() */ |
---|
| 125 | virtual bool IsLeaf() const { return false; } |
---|
| 126 | |
---|
| 127 | /** splitting axis */ |
---|
| 128 | int mAxis; |
---|
| 129 | /** splitting position, absolute position within the bounding box of this node */ |
---|
| 130 | float mPosition; |
---|
| 131 | /** bounding box of interior node */ |
---|
| 132 | AxisAlignedBox3 mBox; |
---|
| 133 | |
---|
| 134 | /** back node */ |
---|
| 135 | KdNode *mBack; |
---|
| 136 | /** front node */ |
---|
| 137 | KdNode *mFront; |
---|
| 138 | |
---|
| 139 | void SetupChildLinks(KdNode *b, KdNode *f) { |
---|
| 140 | mBack = b; |
---|
| 141 | mFront = f; |
---|
| 142 | b->mParent = f->mParent = this; |
---|
| 143 | } |
---|
| 144 | |
---|
| 145 | void ReplaceChildLink(KdNode *oldChild, KdNode *newChild) { |
---|
| 146 | if (mBack == oldChild) |
---|
| 147 | mBack = newChild; |
---|
| 148 | else |
---|
| 149 | mFront = newChild; |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | |
---|
| 153 | }; |
---|
| 154 | |
---|
| 155 | |
---|
| 156 | /** Implementation of the kd-tree leaf node */ |
---|
| 157 | class KdLeaf : public KdNode { |
---|
| 158 | public: |
---|
| 159 | KdLeaf(KdInterior *parent, const int objects):KdNode(parent) { |
---|
| 160 | mObjects.reserve(objects); |
---|
| 161 | } |
---|
| 162 | |
---|
[191] | 163 | void AddPassingRay(const Ray &ray, const int contributions) { |
---|
| 164 | mPassingRays.AddRay(ray, contributions); |
---|
[365] | 165 | // Debug << "adding passing ray" << endl; |
---|
[191] | 166 | } |
---|
| 167 | |
---|
[162] | 168 | /** \sa KdNode::IsLeaf() */ |
---|
| 169 | virtual bool IsLeaf() const { return true; } |
---|
[191] | 170 | |
---|
[162] | 171 | |
---|
[191] | 172 | |
---|
| 173 | |
---|
[162] | 174 | /** pointers to occluders contained in this node */ |
---|
[176] | 175 | ObjectContainer mObjects; |
---|
[162] | 176 | |
---|
| 177 | /** pointers to viewcells contained in this node */ |
---|
| 178 | // ViewCellContainer mViewCells; |
---|
[191] | 179 | |
---|
| 180 | /** Ray set description of the rays passing through this node */ |
---|
| 181 | PassingRaySet mPassingRays; |
---|
| 182 | |
---|
| 183 | /** PVS consisting of visible KdTree nodes */ |
---|
| 184 | KdPvs mKdPvs; |
---|
| 185 | |
---|
[162] | 186 | }; |
---|
| 187 | |
---|
| 188 | |
---|
| 189 | |
---|
| 190 | /** KdTree for indexing scene entities - occluders/occludees/viewcells */ |
---|
| 191 | class KdTree { |
---|
| 192 | |
---|
| 193 | protected: |
---|
| 194 | struct TraversalData |
---|
| 195 | { |
---|
| 196 | KdNode *mNode; |
---|
| 197 | AxisAlignedBox3 mBox; |
---|
| 198 | int mDepth; |
---|
| 199 | float mPriority; |
---|
| 200 | |
---|
| 201 | TraversalData() {} |
---|
| 202 | |
---|
| 203 | TraversalData(KdNode *n, const float p): |
---|
| 204 | mNode(n), mPriority(p) |
---|
| 205 | {} |
---|
| 206 | |
---|
| 207 | TraversalData(KdNode *n, |
---|
| 208 | const AxisAlignedBox3 &b, |
---|
| 209 | const int d): |
---|
| 210 | mNode(n), mBox(b), mDepth(d) {} |
---|
| 211 | |
---|
| 212 | |
---|
| 213 | bool operator<( |
---|
| 214 | const TraversalData &b) const { |
---|
| 215 | KdLeaf *leafa = (KdLeaf *) mNode; |
---|
| 216 | KdLeaf *leafb = (KdLeaf *) b.mNode; |
---|
| 217 | return |
---|
| 218 | leafa->mObjects.size()*mBox.SurfaceArea() |
---|
| 219 | < |
---|
| 220 | leafb->mObjects.size()*b.mBox.SurfaceArea(); |
---|
| 221 | } |
---|
| 222 | |
---|
| 223 | |
---|
| 224 | // comparator for the |
---|
| 225 | struct less_priority : public |
---|
| 226 | binary_function<const TraversalData, const TraversalData, bool> { |
---|
| 227 | |
---|
| 228 | bool operator()(const TraversalData a, const TraversalData b) { |
---|
| 229 | return a.mPriority < b.mPriority; |
---|
| 230 | } |
---|
| 231 | |
---|
| 232 | }; |
---|
| 233 | |
---|
| 234 | }; |
---|
| 235 | |
---|
| 236 | |
---|
| 237 | |
---|
| 238 | public: |
---|
| 239 | |
---|
| 240 | enum {SPLIT_OBJECT_MEDIAN, |
---|
| 241 | SPLIT_SPATIAL_MEDIAN, |
---|
| 242 | SPLIT_SAH}; |
---|
| 243 | |
---|
| 244 | KdTree(); |
---|
| 245 | |
---|
| 246 | |
---|
| 247 | /** Insert view cell into the tree */ |
---|
| 248 | virtual void InsertViewCell(ViewCell *viewCell) { |
---|
| 249 | // mRoot->mViewcells.push_back(viewCell); |
---|
| 250 | } |
---|
| 251 | |
---|
| 252 | virtual bool Construct(); |
---|
| 253 | |
---|
| 254 | /** Check whether subdivision criteria are met for the given subtree. |
---|
| 255 | If not subdivide the leafs of the subtree. The criteria are specified in |
---|
| 256 | the environment as well as the subdivision method. By default surface area |
---|
| 257 | heuristics is used. |
---|
| 258 | |
---|
| 259 | @param subtree root of the subtree |
---|
| 260 | |
---|
| 261 | @return true if subdivision was performed, false if subdivision criteria |
---|
| 262 | were already met |
---|
| 263 | */ |
---|
| 264 | virtual KdNode *Subdivide(const TraversalData &tdata); |
---|
| 265 | |
---|
| 266 | /** Get the root of the tree */ |
---|
| 267 | KdNode *GetRoot() const { |
---|
| 268 | return mRoot; |
---|
| 269 | } |
---|
| 270 | |
---|
| 271 | |
---|
| 272 | AxisAlignedBox3 GetBox() const { return mBox; } |
---|
| 273 | |
---|
| 274 | int |
---|
| 275 | CastRay( |
---|
| 276 | Ray &ray |
---|
| 277 | ); |
---|
| 278 | |
---|
| 279 | const KdTreeStatistics &GetStatistics() const { |
---|
| 280 | return mStat; |
---|
| 281 | } |
---|
| 282 | |
---|
[176] | 283 | void |
---|
| 284 | CollectObjects(KdNode *n, ObjectContainer &objects); |
---|
[191] | 285 | |
---|
| 286 | void |
---|
| 287 | CollectLeaves(vector<KdLeaf *> &leaves); |
---|
| 288 | |
---|
| 289 | AxisAlignedBox3 GetBox(const KdNode *node) const { |
---|
[162] | 290 | KdInterior *parent = node->mParent; |
---|
| 291 | if (parent == NULL) |
---|
| 292 | return mBox; |
---|
| 293 | |
---|
| 294 | if (!node->IsLeaf()) |
---|
| 295 | return ((KdInterior *)node)->mBox; |
---|
| 296 | |
---|
| 297 | AxisAlignedBox3 box(parent->mBox); |
---|
| 298 | if (parent->mFront == node) |
---|
| 299 | box.SetMin(parent->mAxis, parent->mPosition); |
---|
| 300 | else |
---|
| 301 | box.SetMax(parent->mAxis, parent->mPosition); |
---|
| 302 | return box; |
---|
| 303 | } |
---|
| 304 | |
---|
[177] | 305 | KdNode * |
---|
| 306 | FindRandomNeighbor(KdNode *n, |
---|
[354] | 307 | bool onlyUnmailed |
---|
| 308 | ); |
---|
| 309 | |
---|
[245] | 310 | |
---|
| 311 | KdNode * |
---|
| 312 | KdTree::GetRandomLeaf(const Plane3 &halfspace); |
---|
[354] | 313 | |
---|
| 314 | KdNode * |
---|
| 315 | GetRandomLeaf(const bool onlyUnmailed = false); |
---|
| 316 | |
---|
[177] | 317 | int |
---|
| 318 | FindNeighbors(KdNode *n, |
---|
| 319 | vector<KdNode *> &neighbors, |
---|
| 320 | bool onlyUnmailed |
---|
| 321 | ); |
---|
[191] | 322 | |
---|
| 323 | int |
---|
| 324 | CollectLeafPvs(); |
---|
| 325 | |
---|
[162] | 326 | protected: |
---|
| 327 | |
---|
| 328 | struct RayData { |
---|
| 329 | // pointer to the actual ray |
---|
| 330 | Ray *ray; |
---|
| 331 | |
---|
| 332 | // endpoints - do we need them? |
---|
| 333 | #if USE_FIXEDPOINT_T |
---|
| 334 | short tmin, tmax; |
---|
| 335 | #else |
---|
| 336 | float tmin, tmax; |
---|
| 337 | #endif |
---|
| 338 | |
---|
| 339 | RayData():ray(NULL) {} |
---|
| 340 | RayData(Ray *r):ray(r), tmin(0), |
---|
| 341 | |
---|
| 342 | #if USE_FIXEDPOINT_T |
---|
| 343 | #define FIXEDPOINT_ONE 0x7FFE |
---|
| 344 | // tmax(0xFFFF) |
---|
| 345 | tmax(FIXEDPOINT_ONE) |
---|
| 346 | #else |
---|
| 347 | tmax(1.0f) |
---|
| 348 | #endif |
---|
| 349 | {} |
---|
| 350 | |
---|
| 351 | RayData(Ray *r, |
---|
| 352 | const float _min, |
---|
| 353 | const float _max |
---|
| 354 | ):ray(r) { |
---|
| 355 | SetTMin(_min); |
---|
| 356 | SetTMax(_max); |
---|
| 357 | } |
---|
| 358 | |
---|
| 359 | RayData(Ray *r, |
---|
| 360 | const short _min, |
---|
| 361 | const float _max |
---|
| 362 | ):ray(r), tmin(_min) { |
---|
| 363 | SetTMax(_max); |
---|
| 364 | } |
---|
| 365 | |
---|
| 366 | RayData(Ray *r, |
---|
| 367 | const float _min, |
---|
| 368 | const short _max |
---|
| 369 | ):ray(r), tmax(_max) { |
---|
| 370 | SetTMin(_min); |
---|
| 371 | } |
---|
| 372 | |
---|
| 373 | friend bool operator<(const RayData &a, const RayData &b) { |
---|
| 374 | return a.ray < b.ray; |
---|
| 375 | } |
---|
| 376 | |
---|
| 377 | |
---|
| 378 | float ExtrapOrigin(const int axis) const { |
---|
| 379 | return ray->GetLoc(axis) + GetTMin()*ray->GetDir(axis); |
---|
| 380 | } |
---|
| 381 | |
---|
| 382 | float ExtrapTermination(const int axis) const { |
---|
| 383 | return ray->GetLoc(axis) + GetTMax()*ray->GetDir(axis); |
---|
| 384 | } |
---|
| 385 | |
---|
| 386 | #if USE_FIXEDPOINT_T |
---|
| 387 | float GetTMin () const { return tmin/(float)(FIXEDPOINT_ONE); } |
---|
| 388 | float GetTMax () const { return tmax/(float)(FIXEDPOINT_ONE); } |
---|
| 389 | |
---|
| 390 | void SetTMin (const float t) { |
---|
| 391 | tmin = (short) (t*(float)(FIXEDPOINT_ONE)); |
---|
| 392 | } |
---|
| 393 | |
---|
| 394 | void SetTMax (const float t) { |
---|
| 395 | tmax = (short) (t*(float)(FIXEDPOINT_ONE)); |
---|
| 396 | tmax++; |
---|
| 397 | // if (tmax!=0xFFFF) |
---|
| 398 | // tmax++; |
---|
| 399 | } |
---|
| 400 | #else |
---|
| 401 | float GetTMin () const { return tmin; } |
---|
| 402 | float GetTMax () const { return tmax; } |
---|
| 403 | |
---|
| 404 | void SetTMin (const float t) { tmin = t; } |
---|
| 405 | void SetTMax (const float t) { tmax = t; } |
---|
| 406 | #endif |
---|
| 407 | }; |
---|
| 408 | |
---|
| 409 | struct RayTraversalData { |
---|
| 410 | KdNode *mNode; |
---|
| 411 | Vector3 mExitPoint; |
---|
| 412 | float mMaxT; |
---|
| 413 | |
---|
| 414 | RayTraversalData() {} |
---|
| 415 | RayTraversalData(KdNode *n, |
---|
| 416 | const Vector3 &p, |
---|
| 417 | const float maxt): |
---|
| 418 | mNode(n), mExitPoint(p), mMaxT(maxt) {} |
---|
| 419 | }; |
---|
| 420 | |
---|
| 421 | // -------------------------------------------------------------- |
---|
| 422 | // For sorting objects |
---|
| 423 | // -------------------------------------------------------------- |
---|
| 424 | struct SortableEntry |
---|
| 425 | { |
---|
| 426 | enum { |
---|
[176] | 427 | BOX_MIN, |
---|
| 428 | BOX_MAX |
---|
[162] | 429 | }; |
---|
| 430 | |
---|
| 431 | int type; |
---|
| 432 | float value; |
---|
[176] | 433 | Intersectable *intersectable; |
---|
[162] | 434 | |
---|
| 435 | SortableEntry() {} |
---|
[176] | 436 | SortableEntry(const int t, const float v, Intersectable *i):type(t), |
---|
| 437 | value(v), |
---|
| 438 | intersectable(i) {} |
---|
[162] | 439 | |
---|
| 440 | bool operator<(const SortableEntry &b) const { |
---|
| 441 | return value < b.value; |
---|
| 442 | } |
---|
| 443 | |
---|
| 444 | }; |
---|
| 445 | |
---|
| 446 | // reusable array of split candidates |
---|
| 447 | vector<SortableEntry> *splitCandidates; |
---|
| 448 | |
---|
| 449 | float |
---|
| 450 | BestCostRatio( |
---|
| 451 | KdLeaf *node, |
---|
| 452 | const AxisAlignedBox3 &box, |
---|
| 453 | const int axis, |
---|
| 454 | float &position, |
---|
| 455 | int &objectsBack, |
---|
| 456 | int &objectsFront |
---|
| 457 | ); |
---|
| 458 | |
---|
| 459 | void |
---|
| 460 | SortSplitCandidates( |
---|
| 461 | KdLeaf *node, |
---|
| 462 | const int axis |
---|
| 463 | ); |
---|
| 464 | |
---|
| 465 | void |
---|
| 466 | EvaluateLeafStats(const TraversalData &data); |
---|
| 467 | |
---|
| 468 | KdNode * |
---|
| 469 | SubdivideNode( |
---|
| 470 | KdLeaf *leaf, |
---|
| 471 | const AxisAlignedBox3 &box, |
---|
| 472 | AxisAlignedBox3 &backBBox, |
---|
| 473 | AxisAlignedBox3 &frontBBox |
---|
| 474 | ); |
---|
| 475 | |
---|
| 476 | bool |
---|
| 477 | TerminationCriteriaMet(const KdLeaf *leaf); |
---|
| 478 | |
---|
| 479 | int |
---|
| 480 | SelectPlane(KdLeaf *leaf, |
---|
| 481 | const AxisAlignedBox3 &box, |
---|
| 482 | float &position |
---|
| 483 | ); |
---|
| 484 | |
---|
| 485 | |
---|
| 486 | |
---|
| 487 | float mSplitBorder; |
---|
| 488 | int mTermMaxDepth; |
---|
| 489 | int mTermMinCost; |
---|
| 490 | float mMaxCostRatio; |
---|
| 491 | float mCt_div_ci; |
---|
| 492 | int mSplitMethod; |
---|
[170] | 493 | bool mSahUseFaces; |
---|
[162] | 494 | /// root of the tree |
---|
| 495 | KdNode *mRoot; |
---|
| 496 | /// bounding box of the tree root |
---|
| 497 | AxisAlignedBox3 mBox; |
---|
| 498 | KdTreeStatistics mStat; |
---|
[191] | 499 | |
---|
[162] | 500 | }; |
---|
| 501 | |
---|
| 502 | |
---|
| 503 | |
---|
| 504 | |
---|
| 505 | |
---|
| 506 | |
---|
| 507 | #endif |
---|