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