[408] | 1 | // ================================================================
|
---|
| 2 | // $Id$
|
---|
| 3 | // ****************************************************************
|
---|
| 4 | //
|
---|
| 5 | // Initial coding by
|
---|
| 6 | /**
|
---|
| 7 | @author Jiri Bittner
|
---|
| 8 | */
|
---|
[405] | 9 |
|
---|
[408] | 10 | #ifndef __VSPKDTREE_H__
|
---|
| 11 | #define __VSPKDTREE_H__
|
---|
| 12 |
|
---|
| 13 | // Standard headers
|
---|
| 14 | #include <iomanip>
|
---|
| 15 | #include <vector>
|
---|
[405] | 16 | #include <functional>
|
---|
[408] | 17 | #include <stack>
|
---|
[405] | 18 |
|
---|
[408] | 19 |
|
---|
| 20 | // User headers
|
---|
| 21 | #include "VssRay.h"
|
---|
[405] | 22 | #include "AxisAlignedBox3.h"
|
---|
| 23 |
|
---|
| 24 |
|
---|
[408] | 25 | #define USE_KDNODE_VECTORS 1
|
---|
| 26 | #define _RSS_STATISTICS
|
---|
| 27 | #define _RSS_TRAVERSAL_STATISTICS
|
---|
[405] | 28 |
|
---|
[408] | 29 |
|
---|
| 30 | #include "Statistics.h"
|
---|
| 31 | #include "Ray.h"
|
---|
| 32 |
|
---|
[420] | 33 | #include "RayInfo.h"
|
---|
[428] | 34 | #include "Containers.h"
|
---|
[420] | 35 |
|
---|
| 36 | /**
|
---|
| 37 | Static statistics for vsp kd-tree search
|
---|
| 38 | */
|
---|
[408] | 39 | class VspKdStatistics: public StatisticsBase
|
---|
[405] | 40 | {
|
---|
| 41 | public:
|
---|
[420] | 42 | // total number of nodes
|
---|
| 43 | int nodes;
|
---|
| 44 | // number of splits along each of the axes
|
---|
| 45 | int splits[7];
|
---|
| 46 | // totals number of rays
|
---|
| 47 | int rays;
|
---|
[408] | 48 | // initial size of the pvs
|
---|
[420] | 49 | int initialPvsSize;
|
---|
[408] | 50 | // total number of query domains
|
---|
[420] | 51 | int queryDomains;
|
---|
| 52 | // total number of ray references
|
---|
| 53 | int rayRefs;
|
---|
[408] | 54 |
|
---|
| 55 | // max depth nodes
|
---|
[420] | 56 | int maxDepthNodes;
|
---|
| 57 | // max depth nodes
|
---|
| 58 | int minPvsNodes;
|
---|
[426] | 59 | // nodes with minimum PVS
|
---|
[420] | 60 | int minRaysNodes;
|
---|
[408] | 61 | // max ray contribution nodes
|
---|
[420] | 62 | int maxRayContribNodes;
|
---|
[408] | 63 | // max depth nodes
|
---|
[420] | 64 | int minSizeNodes;
|
---|
[408] | 65 |
|
---|
[420] | 66 | // max number of rays per node
|
---|
| 67 | int maxRayRefs;
|
---|
[426] | 68 | // maximal PVS size / leaf
|
---|
| 69 | int maxPvsSize;
|
---|
| 70 |
|
---|
[420] | 71 | // number of dynamically added ray refs
|
---|
| 72 | int addedRayRefs;
|
---|
| 73 | // number of dynamically removed ray refs
|
---|
| 74 | int removedRayRefs;
|
---|
[405] | 75 |
|
---|
[420] | 76 | /** Default constructor.
|
---|
| 77 | */
|
---|
| 78 | VspKdStatistics() { Reset(); }
|
---|
| 79 | int Nodes() const { return nodes; }
|
---|
| 80 | int Interior() const { return nodes / 2; }
|
---|
| 81 | int Leaves() const { return (nodes / 2) + 1; }
|
---|
[405] | 82 |
|
---|
[420] | 83 | void Reset()
|
---|
| 84 | {
|
---|
| 85 | nodes = 0;
|
---|
[405] | 86 |
|
---|
[420] | 87 | for (int i=0; i<7; i++)
|
---|
| 88 | splits[i] = 0;
|
---|
[405] | 89 |
|
---|
[420] | 90 | rays = queryDomains = 0;
|
---|
| 91 | rayRefs = 0;
|
---|
[426] | 92 |
|
---|
[420] | 93 | maxDepthNodes = 0;
|
---|
| 94 | minPvsNodes = 0;
|
---|
[426] | 95 | minRaysNodes = 0;
|
---|
| 96 | maxRayContribNodes = 0;
|
---|
| 97 | minSizeNodes = 0;
|
---|
| 98 |
|
---|
[420] | 99 | maxRayRefs = 0;
|
---|
| 100 | addedRayRefs = removedRayRefs = 0;
|
---|
[426] | 101 |
|
---|
[420] | 102 | initialPvsSize = 0;
|
---|
[426] | 103 | maxPvsSize = 0;
|
---|
[420] | 104 | }
|
---|
| 105 |
|
---|
| 106 | void Print(ostream &app) const;
|
---|
| 107 | friend ostream &operator<<(ostream &s, const VspKdStatistics &stat)
|
---|
| 108 | {
|
---|
| 109 | stat.Print(s);
|
---|
| 110 | return s;
|
---|
| 111 | }
|
---|
[405] | 112 | };
|
---|
| 113 |
|
---|
[408] | 114 |
|
---|
| 115 | class VspKdTreeInterior;
|
---|
| 116 |
|
---|
| 117 |
|
---|
[420] | 118 | /** Abstract superclass of Vsp-Kd-Tree nodes.
|
---|
| 119 | */
|
---|
[408] | 120 | class VspKdTreeNode
|
---|
| 121 | {
|
---|
[405] | 122 | public:
|
---|
[408] | 123 |
|
---|
[419] | 124 | friend class VspKdTree;
|
---|
[408] | 125 |
|
---|
[420] | 126 | enum {EInterior, ELeaf};
|
---|
[405] | 127 |
|
---|
[420] | 128 | /** Constructs new interior node from the parent node.
|
---|
| 129 | */
|
---|
| 130 | inline VspKdTreeNode(VspKdTreeInterior *p);
|
---|
[405] | 131 |
|
---|
[420] | 132 | /** Destroys this node and the subtree.
|
---|
| 133 | */
|
---|
| 134 | virtual ~VspKdTreeNode();
|
---|
[405] | 135 |
|
---|
[420] | 136 | /** Type of the node (Einterior or ELeaf)
|
---|
| 137 | */
|
---|
| 138 | virtual int Type() const = 0;
|
---|
| 139 |
|
---|
| 140 | /** Returns true if this node is a leaf.
|
---|
| 141 | */
|
---|
| 142 | bool IsLeaf() const;
|
---|
| 143 |
|
---|
| 144 | /** Prints node stats.
|
---|
| 145 | */
|
---|
| 146 | virtual void Print(ostream &s) const = 0;
|
---|
[405] | 147 |
|
---|
[420] | 148 | /** Returns time needed to access this node.
|
---|
| 149 | */
|
---|
| 150 | virtual int GetAccessTime(); // NOTE: don't really know how it is used!
|
---|
[405] | 151 |
|
---|
[420] | 152 | /** Returns parent node.
|
---|
| 153 | */
|
---|
| 154 | VspKdTreeInterior *GetParent() const;
|
---|
[426] | 155 |
|
---|
[420] | 156 | /** Sets parent node.
|
---|
| 157 | */
|
---|
| 158 | void SetParent(VspKdTreeInterior *p);
|
---|
[408] | 159 |
|
---|
[420] | 160 | protected:
|
---|
| 161 | /////////////////////////////////
|
---|
| 162 | // The actual data goes here
|
---|
[408] | 163 |
|
---|
[420] | 164 | /// link to the parent
|
---|
| 165 | VspKdTreeInterior *mParent;
|
---|
[405] | 166 |
|
---|
[420] | 167 | enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ};
|
---|
[408] | 168 |
|
---|
[420] | 169 | /// splitting axis
|
---|
| 170 | char mAxis;
|
---|
[408] | 171 |
|
---|
[420] | 172 | /// depth
|
---|
| 173 | unsigned char mDepth;
|
---|
[405] | 174 | };
|
---|
[408] | 175 |
|
---|
| 176 | // --------------------------------------------------------------
|
---|
| 177 | // KD-tree node - interior node
|
---|
| 178 | // --------------------------------------------------------------
|
---|
[411] | 179 | class VspKdTreeInterior: public VspKdTreeNode
|
---|
[408] | 180 | {
|
---|
| 181 | public:
|
---|
[419] | 182 | friend class VspKdTree;
|
---|
| 183 |
|
---|
[420] | 184 | /** Constructs new interior node from parent node.
|
---|
| 185 | */
|
---|
[418] | 186 | VspKdTreeInterior(VspKdTreeInterior *p);
|
---|
| 187 |
|
---|
| 188 | virtual int GetAccessTime();
|
---|
| 189 |
|
---|
[419] | 190 | virtual int Type() const;
|
---|
[405] | 191 |
|
---|
[418] | 192 | virtual ~VspKdTreeInterior();
|
---|
| 193 |
|
---|
| 194 | virtual void Print(ostream &s) const;
|
---|
[408] | 195 |
|
---|
[420] | 196 | /** Returns back child.
|
---|
| 197 | */
|
---|
[419] | 198 | inline VspKdTreeNode *GetBack() const;
|
---|
[420] | 199 | /** Returns front child.
|
---|
| 200 | */
|
---|
[419] | 201 | inline VspKdTreeNode *GetFront() const;
|
---|
| 202 |
|
---|
[418] | 203 | protected:
|
---|
[408] | 204 |
|
---|
[420] | 205 | /** Sets pointers to back child and front child.
|
---|
| 206 | */
|
---|
[418] | 207 | void SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f);
|
---|
[420] | 208 |
|
---|
| 209 | /** Replaces the pointer to oldChild with a pointer to newChild.
|
---|
| 210 | */
|
---|
[418] | 211 | void ReplaceChildLink(VspKdTreeNode *oldChild, VspKdTreeNode *newChild);
|
---|
| 212 |
|
---|
[420] | 213 | /** Computes intersection of the ray with the node boundaries.
|
---|
| 214 | */
|
---|
[418] | 215 | int ComputeRayIntersection(const RayInfo &rayData, float &t);
|
---|
[408] | 216 |
|
---|
[418] | 217 | // plane in local modelling coordinates
|
---|
| 218 | float mPosition;
|
---|
[408] | 219 |
|
---|
[418] | 220 | // pointers to children
|
---|
| 221 | VspKdTreeNode *mBack;
|
---|
| 222 | VspKdTreeNode *mFront;
|
---|
[405] | 223 |
|
---|
[418] | 224 | // the bbox of the node
|
---|
[419] | 225 | AxisAlignedBox3 mBox;
|
---|
[418] | 226 |
|
---|
| 227 | // data for caching
|
---|
| 228 | long mAccesses;
|
---|
| 229 | long mLastAccessTime;
|
---|
[408] | 230 | };
|
---|
| 231 |
|
---|
| 232 |
|
---|
| 233 | // --------------------------------------------------------------
|
---|
| 234 | // KD-tree node - leaf node
|
---|
| 235 | // --------------------------------------------------------------
|
---|
[419] | 236 | class VspKdTreeLeaf: public VspKdTreeNode
|
---|
[408] | 237 | {
|
---|
| 238 | public:
|
---|
[419] | 239 | friend class VspKdTree;
|
---|
| 240 |
|
---|
[420] | 241 | /** Constructs leaf from parent node.
|
---|
| 242 | @param p the parent node
|
---|
| 243 | @param nRays preallocates memory to store this number of rays
|
---|
| 244 | */
|
---|
| 245 | VspKdTreeLeaf(VspKdTreeInterior *p, const int nRays);
|
---|
[408] | 246 |
|
---|
[420] | 247 | virtual ~VspKdTreeLeaf();
|
---|
[405] | 248 |
|
---|
[420] | 249 | virtual int Type() const;
|
---|
[408] | 250 |
|
---|
[420] | 251 | virtual void Print(ostream &s) const;
|
---|
[405] | 252 |
|
---|
[420] | 253 | /** Adds a ray to the leaf ray container.
|
---|
| 254 | */
|
---|
| 255 | void AddRay(const RayInfo &data);
|
---|
| 256 | /** Returns size of the leaf PVS as induced by the rays
|
---|
| 257 | @note returns precomputed PVS size, which may not be valid
|
---|
| 258 | anymore. Run UpdatePvsSize to get a valid PVS.
|
---|
| 259 | */
|
---|
| 260 | int GetPvsSize() const;
|
---|
[405] | 261 |
|
---|
[420] | 262 | /** If PVS is not valid, this function recomputes the leaf
|
---|
| 263 | PVS as induced by the rays.
|
---|
| 264 | */
|
---|
[410] | 265 | void UpdatePvsSize();
|
---|
[408] | 266 |
|
---|
[428] | 267 | /** Returns stored rays.
|
---|
| 268 | */
|
---|
[426] | 269 | RayInfoContainer &GetRays();
|
---|
| 270 |
|
---|
[428] | 271 | /** Returns rays into this ray container.
|
---|
| 272 | */
|
---|
| 273 | void GetRays(VssRayContainer &rays);
|
---|
[420] | 274 | /** Returns average contribution of a ray to the PVS
|
---|
| 275 | */
|
---|
| 276 | inline float GetAvgRayContribution() const;
|
---|
| 277 | /** Returns square of average contribution of a ray.
|
---|
| 278 | */
|
---|
| 279 | inline float GetSqrRayContribution() const;
|
---|
[408] | 280 |
|
---|
[428] | 281 | /** Extracts PVS from ray set.
|
---|
| 282 | */
|
---|
| 283 | void ExtractPvs(ObjectContainer &objects) const;
|
---|
| 284 |
|
---|
[422] | 285 | //-- mailing options
|
---|
| 286 | void Mail();
|
---|
| 287 |
|
---|
| 288 | bool Mailed() const;
|
---|
| 289 |
|
---|
| 290 | bool Mailed(const int mail);
|
---|
| 291 |
|
---|
[420] | 292 | static void NewMail();
|
---|
| 293 |
|
---|
| 294 | static int mailID;
|
---|
| 295 |
|
---|
[428] | 296 |
|
---|
[420] | 297 | protected:
|
---|
[426] | 298 |
|
---|
| 299 | /** Manually sets PVS size.
|
---|
| 300 | @param s the PVS size
|
---|
| 301 | */
|
---|
| 302 | void SetPvsSize(const int s);
|
---|
| 303 |
|
---|
[420] | 304 | int mMailbox;
|
---|
| 305 |
|
---|
| 306 | RayInfoContainer mRays;
|
---|
| 307 | bool mValidPvs;
|
---|
| 308 |
|
---|
[419] | 309 | private:
|
---|
| 310 | int mPvsSize;
|
---|
[405] | 311 | };
|
---|
| 312 |
|
---|
| 313 |
|
---|
| 314 |
|
---|
[408] | 315 | // ---------------------------------------------------------------
|
---|
| 316 | // Main LSDS search class
|
---|
| 317 | // ---------------------------------------------------------------
|
---|
| 318 | class VspKdTree
|
---|
| 319 | {
|
---|
[411] | 320 | // --------------------------------------------------------------
|
---|
| 321 | // For sorting rays
|
---|
| 322 | // -------------------------------------------------------------
|
---|
| 323 | struct SortableEntry
|
---|
| 324 | {
|
---|
| 325 | enum EType
|
---|
| 326 | {
|
---|
| 327 | ERayMin,
|
---|
| 328 | ERayMax
|
---|
| 329 | };
|
---|
| 330 |
|
---|
| 331 | int type;
|
---|
| 332 | float value;
|
---|
| 333 | void *data;
|
---|
| 334 |
|
---|
| 335 | SortableEntry() {}
|
---|
| 336 | SortableEntry(const int t, const float v, void *d):type(t),
|
---|
| 337 | value(v), data(d)
|
---|
| 338 | {
|
---|
| 339 | }
|
---|
| 340 |
|
---|
| 341 | friend bool operator<(const SortableEntry &a, const SortableEntry &b)
|
---|
| 342 | {
|
---|
| 343 | return a.value < b.value;
|
---|
| 344 | }
|
---|
| 345 | };
|
---|
| 346 |
|
---|
[410] | 347 | struct TraversalData
|
---|
| 348 | {
|
---|
[419] | 349 | VspKdTreeNode *mNode;
|
---|
| 350 | AxisAlignedBox3 mBox;
|
---|
| 351 | int mDepth;
|
---|
[423] | 352 | //float mPriority;
|
---|
[410] | 353 |
|
---|
| 354 | TraversalData() {}
|
---|
[405] | 355 |
|
---|
[410] | 356 | TraversalData(VspKdTreeNode *n, const float p):
|
---|
[423] | 357 | mNode(n)//, mPriority(p)
|
---|
[410] | 358 | {}
|
---|
[408] | 359 |
|
---|
[410] | 360 | TraversalData(VspKdTreeNode *n, const AxisAlignedBox3 &b, const int d):
|
---|
[419] | 361 | mNode(n), mBox(b), mDepth(d) {}
|
---|
[405] | 362 |
|
---|
[423] | 363 | // comparator for the priority queue
|
---|
| 364 | /*struct less_priority : public binary_function<const TraversalData, const TraversalData, bool>
|
---|
[410] | 365 | {
|
---|
[423] | 366 | bool operator()(const TraversalData a, const TraversalData b) {
|
---|
| 367 | return a.mPriority < b.mPriority; } };*/
|
---|
[405] | 368 |
|
---|
[410] | 369 | // ~TraversalData() {}
|
---|
| 370 | // TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
|
---|
[408] | 371 |
|
---|
[410] | 372 | friend bool operator<(const TraversalData &a, const TraversalData &b)
|
---|
| 373 | {
|
---|
| 374 | // return a.node->queries.size() < b.node->queries.size();
|
---|
[419] | 375 | VspKdTreeLeaf *leafa = (VspKdTreeLeaf *) a.mNode;
|
---|
| 376 | VspKdTreeLeaf *leafb = (VspKdTreeLeaf *) b.mNode;
|
---|
[408] | 377 | #if 0
|
---|
| 378 | return
|
---|
[419] | 379 | leafa->rays.size()*a.mBox.GetVolume()
|
---|
[408] | 380 | <
|
---|
[419] | 381 | leafb->rays.size()*b.mBox.GetVolume();
|
---|
[408] | 382 | #endif
|
---|
| 383 | #if 1
|
---|
| 384 | return
|
---|
[419] | 385 | leafa->GetPvsSize()*a.mBox.GetVolume()
|
---|
[408] | 386 | <
|
---|
[419] | 387 | leafb->GetPvsSize()*b.mBox.GetVolume();
|
---|
[408] | 388 | #endif
|
---|
| 389 | #if 0
|
---|
| 390 | return
|
---|
| 391 | leafa->GetPvsSize()
|
---|
| 392 | <
|
---|
| 393 | leafb->GetPvsSize();
|
---|
| 394 | #endif
|
---|
| 395 | #if 0
|
---|
| 396 | return
|
---|
[423] | 397 | leafa->GetPvsSize() / (float)(leafa->rays.size() + Limits::Small())
|
---|
[408] | 398 | >
|
---|
[423] | 399 | leafb->GetPvsSize() / (float)(leafb->rays.size() + Limits::Small());
|
---|
[408] | 400 | #endif
|
---|
| 401 | #if 0
|
---|
| 402 | return
|
---|
[410] | 403 | leafa->GetPvsSize() * (float)leafa->rays.size()
|
---|
[408] | 404 | <
|
---|
[410] | 405 | leafb->GetPvsSize() * (float)leafb->rays.size();
|
---|
[408] | 406 | #endif
|
---|
| 407 | }
|
---|
[405] | 408 | };
|
---|
| 409 |
|
---|
[420] | 410 | /** Simplified data for ray traversal only.
|
---|
| 411 | */
|
---|
[410] | 412 | struct RayTraversalData
|
---|
| 413 | {
|
---|
[420] | 414 | RayInfo mRayData;
|
---|
[419] | 415 | VspKdTreeNode *mNode;
|
---|
[410] | 416 |
|
---|
| 417 | RayTraversalData() {}
|
---|
| 418 |
|
---|
[420] | 419 | RayTraversalData(VspKdTreeNode *n, const RayInfo &data):
|
---|
[419] | 420 | mRayData(data), mNode(n) {}
|
---|
[408] | 421 | };
|
---|
| 422 |
|
---|
[405] | 423 | public:
|
---|
| 424 |
|
---|
[410] | 425 | VspKdTree();
|
---|
| 426 | virtual ~VspKdTree();
|
---|
[405] | 427 |
|
---|
[440] | 428 | virtual void Construct(const VssRayContainer &rays,
|
---|
[410] | 429 | AxisAlignedBox3 *forcedBoundingBox = NULL);
|
---|
[420] | 430 |
|
---|
| 431 | /** Returns bounding box of the specified node.
|
---|
| 432 | */
|
---|
| 433 | AxisAlignedBox3 GetBBox(VspKdTreeNode *node) const;
|
---|
| 434 |
|
---|
| 435 | const VspKdStatistics &GetStatistics() const;
|
---|
| 436 |
|
---|
| 437 | /** Get the root of the tree.
|
---|
| 438 | */
|
---|
| 439 | VspKdTreeNode *GetRoot() const;
|
---|
| 440 |
|
---|
| 441 | /** Returns average PVS size in tree.
|
---|
| 442 | */
|
---|
| 443 | float GetAvgPvsSize();
|
---|
| 444 |
|
---|
| 445 | /** Returns memory usage in MB.
|
---|
| 446 | */
|
---|
| 447 | float GetMemUsage() const;
|
---|
| 448 |
|
---|
| 449 | float GetRayMemUsage() const;
|
---|
| 450 |
|
---|
[428] | 451 | /** Collects leaves of this tree.
|
---|
| 452 | */
|
---|
| 453 | void CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const;
|
---|
| 454 |
|
---|
[420] | 455 | protected:
|
---|
[428] | 456 |
|
---|
[420] | 457 | // incremental construction
|
---|
[410] | 458 | virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add);
|
---|
[405] | 459 |
|
---|
[420] | 460 | virtual void AddRays(VssRayContainer &add);
|
---|
[405] | 461 |
|
---|
[410] | 462 | VspKdTreeNode *Locate(const Vector3 &v);
|
---|
[408] | 463 |
|
---|
[410] | 464 | VspKdTreeNode *SubdivideNode(VspKdTreeLeaf *leaf,
|
---|
| 465 | const AxisAlignedBox3 &box,
|
---|
| 466 | AxisAlignedBox3 &backBox,
|
---|
| 467 | AxisAlignedBox3 &frontBox);
|
---|
[408] | 468 |
|
---|
[410] | 469 | VspKdTreeNode *Subdivide(const TraversalData &tdata);
|
---|
[408] | 470 |
|
---|
[410] | 471 | int SelectPlane(VspKdTreeLeaf *leaf,
|
---|
| 472 | const AxisAlignedBox3 &box,
|
---|
| 473 | float &position,
|
---|
| 474 | int &raysBack,
|
---|
| 475 | int &raysFront,
|
---|
| 476 | int &pvsBack,
|
---|
| 477 | int &pvsFront);
|
---|
[405] | 478 |
|
---|
[410] | 479 | void SortSplitCandidates(VspKdTreeLeaf *node,
|
---|
[420] | 480 | const int axis);
|
---|
[408] | 481 |
|
---|
[410] | 482 | float BestCostRatioHeuristic(VspKdTreeLeaf *node,
|
---|
| 483 | int &axis,
|
---|
| 484 | float &position,
|
---|
| 485 | int &raysBack,
|
---|
| 486 | int &raysFront,
|
---|
| 487 | int &pvsBack,
|
---|
| 488 | int &pvsFront);
|
---|
[405] | 489 |
|
---|
[410] | 490 | float BestCostRatioRegular(VspKdTreeLeaf *node,
|
---|
| 491 | int &axis,
|
---|
| 492 | float &position,
|
---|
| 493 | int &raysBack,
|
---|
| 494 | int &raysFront,
|
---|
| 495 | int &pvsBack,
|
---|
| 496 | int &pvsFront);
|
---|
[408] | 497 |
|
---|
[410] | 498 | float EvalCostRatio(VspKdTreeLeaf *node,
|
---|
| 499 | const int axis,
|
---|
| 500 | const float position,
|
---|
| 501 | int &raysBack,
|
---|
| 502 | int &raysFront,
|
---|
| 503 | int &pvsBack,
|
---|
| 504 | int &pvsFront);
|
---|
[405] | 505 |
|
---|
| 506 |
|
---|
[410] | 507 | VspKdTreeNode * SubdivideLeaf(VspKdTreeLeaf *leaf,
|
---|
| 508 | const float SAThreshold);
|
---|
[405] | 509 |
|
---|
[410] | 510 | void RemoveRay(VssRay *ray,
|
---|
| 511 | vector<VspKdTreeLeaf *> *affectedLeaves,
|
---|
| 512 | const bool removeAllScheduledRays);
|
---|
[405] | 513 |
|
---|
[410] | 514 | void AddRay(VssRay *ray);
|
---|
[408] | 515 |
|
---|
[410] | 516 | void TraverseInternalNode(RayTraversalData &data,
|
---|
| 517 | stack<RayTraversalData> &tstack);
|
---|
[408] | 518 |
|
---|
[410] | 519 | void EvaluateLeafStats(const TraversalData &data);
|
---|
[405] | 520 |
|
---|
| 521 |
|
---|
[418] | 522 | int GetRootPvsSize() const;
|
---|
[408] | 523 |
|
---|
[410] | 524 | int GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const;
|
---|
[405] | 525 |
|
---|
[410] | 526 | void GetRayContributionStatistics(float &minRayContribution,
|
---|
| 527 | float &maxRayContribution,
|
---|
| 528 | float &avgRayContribution);
|
---|
[405] | 529 |
|
---|
[410] | 530 | int GenerateRays(const float ratioPerLeaf,
|
---|
| 531 | SimpleRayContainer &rays);
|
---|
[405] | 532 |
|
---|
[425] | 533 | /** Collapses this subtree and releases the memory.
|
---|
| 534 | @returns number of collapsed rays.
|
---|
| 535 | */
|
---|
[418] | 536 | int CollapseSubtree(VspKdTreeNode *sroot, const int time);
|
---|
| 537 |
|
---|
[419] | 538 | int ReleaseMemory(const int time);
|
---|
| 539 |
|
---|
[421] | 540 | bool TerminationCriteriaMet(const VspKdTreeLeaf *leaf,
|
---|
| 541 | const AxisAlignedBox3 &box) const;
|
---|
| 542 |
|
---|
[425] | 543 | /** Computes PVS size of this node given a global ray set.
|
---|
| 544 | @returns PVS size of the intersection of this node bounding box with the rays.
|
---|
| 545 | */
|
---|
| 546 | int ComputePvsSize(VspKdTreeNode *node, const RayInfoContainer &globalRays) const;
|
---|
| 547 |
|
---|
[418] | 548 | protected:
|
---|
| 549 | /////////////////////////////
|
---|
| 550 | // The core pointer
|
---|
| 551 | VspKdTreeNode *mRoot;
|
---|
| 552 |
|
---|
| 553 | /////////////////////////////
|
---|
| 554 | // Basic properties
|
---|
| 555 |
|
---|
| 556 | // total number of nodes of the tree
|
---|
[422] | 557 | int mNumNodes;
|
---|
[418] | 558 |
|
---|
| 559 | // axis aligned bounding box of the scene
|
---|
| 560 | AxisAlignedBox3 mBox;
|
---|
| 561 |
|
---|
| 562 | // epsilon used for the construction
|
---|
[422] | 563 | float mEpsilon;
|
---|
[418] | 564 |
|
---|
| 565 | // ratio between traversal and intersection costs
|
---|
[422] | 566 | float mCtDivCi;
|
---|
[418] | 567 |
|
---|
| 568 | // type of the splitting to use for the tree construction
|
---|
| 569 | enum {ESplitRegular, ESplitHeuristic };
|
---|
| 570 | int splitType;
|
---|
| 571 |
|
---|
| 572 | // maximum alovable memory in MB
|
---|
[422] | 573 | float mMaxTotalMemory;
|
---|
[418] | 574 |
|
---|
| 575 | // maximum alovable memory for static kd tree in MB
|
---|
[422] | 576 | float mMaxStaticMemory;
|
---|
[418] | 577 |
|
---|
| 578 | // this is used during the construction depending
|
---|
| 579 | // on the type of the tree and queries...
|
---|
[422] | 580 | float mMaxMemory;
|
---|
[418] | 581 |
|
---|
| 582 | // minimal acess time for collapse
|
---|
[422] | 583 | int mAccessTimeThreshold;
|
---|
[418] | 584 |
|
---|
| 585 | // minimal depth at which to perform collapse
|
---|
[422] | 586 | int mMinCollapseDepth;
|
---|
[418] | 587 |
|
---|
| 588 | // reusable array of split candidates
|
---|
[422] | 589 | vector<SortableEntry> *mSplitCandidates;
|
---|
[418] | 590 |
|
---|
| 591 | /////////////////////////////
|
---|
[421] | 592 | // Construction parameters
|
---|
| 593 |
|
---|
| 594 | /// max depth of the tree
|
---|
| 595 | int mTermMaxDepth;
|
---|
| 596 |
|
---|
| 597 | /// minimal ratio of the volume of the cell and the query volume
|
---|
| 598 | float mTermMinSize;
|
---|
| 599 |
|
---|
| 600 | /// minimal pvs per node to still get subdivided
|
---|
| 601 | int mTermMinPvs;
|
---|
| 602 |
|
---|
| 603 | /// minimal ray number per node to still get subdivided
|
---|
| 604 | int mTermMinRays;
|
---|
| 605 |
|
---|
| 606 | /// maximal cost ration to subdivide a node
|
---|
| 607 | float mTermMaxCostRatio;
|
---|
| 608 |
|
---|
| 609 | /// maximal contribution per ray to subdivide the node
|
---|
| 610 | float mTermMaxRayContribution;
|
---|
| 611 |
|
---|
| 612 |
|
---|
[422] | 613 | bool mOnlyDrivingAxis;
|
---|
[421] | 614 | /////////////////////////////
|
---|
[418] | 615 | VspKdStatistics mStat;
|
---|
[405] | 616 | };
|
---|
| 617 |
|
---|
[408] | 618 |
|
---|
| 619 | #endif // __LSDS_KDTREE_H__
|
---|
| 620 |
|
---|