![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
Changeset 410 for trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
- Timestamp:
- 11/14/05 21:29:57 (19 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
r408 r410 374 374 // KD-tree node - leaf node 375 375 // -------------------------------------------------------------- 376 class VspKdTreeLeaf : 377 public VspKdTreeNode 376 class VspKdTreeLeaf : public VspKdTreeNode 378 377 { 379 378 private: 380 379 int mPvsSize; 381 380 public: 382 383 384 385 381 static int mailID; 382 int mailbox; 383 384 RayInfoContainer rays; 386 385 bool mValidPvs; 387 386 388 VspKdTreeLeaf(VspKdTreeInterior *p, 389 const int nRays 390 ):VspKdTreeNode(p), rays(), mPvsSize(0), mValidPvs(false) { 391 rays.reserve(nRays); 392 } 393 394 virtual ~VspKdTreeLeaf() { } 395 396 virtual int Type() const { return ELeaf; } 397 398 virtual void Print(ostream &s) const { 399 s<<endl<<"L: r="<<rays.size()<<endl; 400 }; 401 402 void AddRay(const RayInfo &data) { 387 VspKdTreeLeaf(VspKdTreeInterior *p, const int nRays): 388 VspKdTreeNode(p), rays(), mPvsSize(0), mValidPvs(false) 389 { 390 rays.reserve(nRays); 391 } 392 393 virtual ~VspKdTreeLeaf() { } 394 395 virtual int Type() const 396 { 397 return ELeaf; 398 } 399 400 virtual void Print(ostream &s) const 401 { 402 s << endl << "L: r = " << rays.size() << endl; 403 }; 404 405 void AddRay(const RayInfo &data) 406 { 403 407 mValidPvs = false; 404 rays.push_back(data); 405 data.mRay->Ref(); 406 } 407 408 int GetPvsSize() const { 408 rays.push_back(data); 409 data.mRay->Ref(); 410 } 411 412 int GetPvsSize() const 413 { 409 414 return mPvsSize; 410 415 } 411 void SetPvsSize(const int s) { 416 void SetPvsSize(const int s) 417 { 412 418 mPvsSize = s; 413 419 } 414 420 415 void 416 UpdatePvsSize(); 417 418 void Mail() { mailbox = mailID; } 419 static void NewMail() { mailID++; } 420 bool Mailed() const { return mailbox == mailID; } 421 422 bool Mailed(const int mail) { 423 return mailbox >= mailID + mail; 424 } 425 426 float GetAvgRayContribution() const { 421 void UpdatePvsSize(); 422 423 void Mail() 424 { 425 mailbox = mailID; 426 } 427 428 static void NewMail() 429 { 430 ++ mailID; 431 } 432 433 bool Mailed() const 434 { 435 return mailbox == mailID; 436 } 437 438 bool Mailed(const int mail) 439 { 440 return mailbox >= mailID + mail; 441 } 442 443 float GetAvgRayContribution() const 444 { 427 445 return GetPvsSize()/((float)rays.size() + Limits::Small); 428 446 } 429 447 430 float GetSqrRayContribution() const { 448 float GetSqrRayContribution() const 449 { 431 450 return sqr(GetPvsSize()/((float)rays.size() + Limits::Small)); 432 451 } … … 435 454 436 455 // Inline functions 437 inline 438 VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p): 439 parent(p), axis(-1), depth(p ? p->depth + 1 : 0){}456 inline VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p): 457 parent(p), axis(-1), depth(p ? p->depth + 1 : 0) 458 {} 440 459 441 460 … … 446 465 class VspKdTree 447 466 { 448 struct TraversalData 449 { 450 VspKdTreeNode *node; 451 AxisAlignedBox3 bbox; 452 int depth; 453 float priority; 467 struct TraversalData 468 { 469 VspKdTreeNode *node; 470 AxisAlignedBox3 bbox; 471 int depth; 472 float priority; 473 474 TraversalData() {} 475 476 TraversalData(VspKdTreeNode *n, const float p): 477 node(n), priority(p) 478 {} 479 480 TraversalData(VspKdTreeNode *n, const AxisAlignedBox3 &b, const int d): 481 node(n), bbox(b), depth(d) {} 454 482 455 TraversalData() {} 456 457 TraversalData(VspKdTreeNode *n, const float p): 458 node(n), priority(p) 459 {} 460 461 TraversalData(VspKdTreeNode *n, 462 const AxisAlignedBox3 &b, 463 const int d): 464 node(n), bbox(b), depth(d) {} 483 // comparator for the 484 struct less_priority : public binary_function<const TraversalData, const TraversalData, bool> 485 { 486 bool operator()(const TraversalData a, const TraversalData b) 487 { 488 return a.priority < b.priority; 489 } 490 }; 491 492 // ~TraversalData() {} 493 // TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {} 465 494 466 467 // comparator for the 468 struct less_priority : public 469 binary_function<const TraversalData, const TraversalData, bool> { 470 471 bool operator()(const TraversalData a, const TraversalData b) { 472 return a.priority < b.priority; 473 } 474 475 }; 476 477 // ~TraversalData() {} 478 // TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {} 479 480 friend bool operator<(const TraversalData &a, 481 const TraversalData &b) { 482 // return a.node->queries.size() < b.node->queries.size(); 483 VspKdTreeLeaf *leafa = (VspKdTreeLeaf *) a.node; 484 VspKdTreeLeaf *leafb = (VspKdTreeLeaf *) b.node; 495 friend bool operator<(const TraversalData &a, const TraversalData &b) 496 { 497 // return a.node->queries.size() < b.node->queries.size(); 498 VspKdTreeLeaf *leafa = (VspKdTreeLeaf *) a.node; 499 VspKdTreeLeaf *leafb = (VspKdTreeLeaf *) b.node; 485 500 #if 0 486 501 return … … 503 518 #if 0 504 519 return 505 leafa->GetPvsSize() /(leafa->rays.size()+1)520 leafa->GetPvsSize() / (float)(leafa->rays.size() + 1) 506 521 > 507 leafb->GetPvsSize() /(leafb->rays.size()+1);522 leafb->GetPvsSize() / (float)(leafb->rays.size() + 1); 508 523 #endif 509 524 #if 0 510 525 return 511 leafa->GetPvsSize() *leafa->rays.size()526 leafa->GetPvsSize() * (float)leafa->rays.size() 512 527 < 513 leafb->GetPvsSize() *leafb->rays.size();528 leafb->GetPvsSize() * (float)leafb->rays.size(); 514 529 #endif 515 530 } … … 518 533 // simplified data for ray traversal only... 519 534 520 struct RayTraversalData {521 522 523 524 525 526 RayTraversalData(VspKdTreeNode *n, 527 528 535 struct RayTraversalData 536 { 537 VspKdTreeNode::RayInfo rayData; 538 VspKdTreeNode *node; 539 540 RayTraversalData() {} 541 542 RayTraversalData(VspKdTreeNode *n, const VspKdTreeNode::RayInfo &data): 543 rayData(data), node(n) {} 529 544 }; 530 545 531 546 public: 532 ///////////////////////////// 533 // The core pointer 534 VspKdTreeNode *root; 535 536 ///////////////////////////// 537 // Basic properties 538 539 // total number of nodes of the tree 540 int nodes; 541 // axis aligned bounding box of the scene 542 AxisAlignedBox3 bbox; 543 544 // axis aligned bounding box of directions 545 AxisAlignedBox3 dirBBox; 546 547 ///////////////////////////// 548 // Construction parameters 549 550 // epsilon used for the construction 551 float epsilon; 552 553 // ratio between traversal and intersection costs 554 float ct_div_ci; 555 // max depth of the tree 556 int termMaxDepth; 557 // minimal ratio of the volume of the cell and the query volume 558 float termMinSize; 547 548 ///////////////////////////// 549 // The core pointer 550 VspKdTreeNode *root; 551 552 ///////////////////////////// 553 // Basic properties 554 555 // total number of nodes of the tree 556 int nodes; 557 558 // axis aligned bounding box of the scene 559 AxisAlignedBox3 bbox; 560 561 // axis aligned bounding box of directions 562 AxisAlignedBox3 dirBBox; 563 564 ///////////////////////////// 565 // Construction parameters 566 567 // epsilon used for the construction 568 float epsilon; 569 570 // ratio between traversal and intersection costs 571 float ct_div_ci; 572 573 // max depth of the tree 574 int termMaxDepth; 575 // minimal ratio of the volume of the cell and the query volume 576 float termMinSize; 559 577 560 578 // minimal pvs per node to still get subdivided 561 579 int termMinPvs; 562 580 563 581 // minimal ray number per node to still get subdivided 564 565 566 567 582 int termMinRays; 583 584 // maximal cost ration to subdivide a node 585 float termMaxCostRatio; 568 586 569 587 // maximal contribution per ray to subdivide the node 570 588 float termMaxRayContribution; 571 589 572 573 // randomized construction 574 bool randomize; 575 576 // type of the splitting to use fo rthe tree construction 577 enum {ESplitRegular, ESplitHeuristic }; 578 int splitType; 579 580 // maximal size of the box on which the refdir splitting can be performed 581 // (relative to the scene bbox 582 float refDirBoxMaxSize; 583 584 // maximum alovable memory in MB 585 float maxTotalMemory; 586 587 // maximum alovable memory for static kd tree in MB 588 float maxStaticMemory; 589 590 // this is used during the construction depending 591 // on the type of the tree and queries... 592 float maxMemory; 593 594 595 // minimal acess time for collapse 596 int accessTimeThreshold; 590 // randomized construction 591 bool randomize; 592 593 // type of the splitting to use for the tree construction 594 enum {ESplitRegular, ESplitHeuristic }; 595 int splitType; 596 597 // maximal size of the box on which the refdir splitting can be performed 598 // (relative to the scene bbox 599 float refDirBoxMaxSize; 600 601 // maximum alovable memory in MB 602 float maxTotalMemory; 603 604 // maximum alovable memory for static kd tree in MB 605 float maxStaticMemory; 606 607 // this is used during the construction depending 608 // on the type of the tree and queries... 609 float maxMemory; 610 611 // minimal acess time for collapse 612 int accessTimeThreshold; 597 613 598 614 // minimal depth at which to perform collapse 599 int minCollapseDepth; 600 601 602 // reusable array of split candidates 603 vector<SortableEntry> *splitCandidates; 604 ///////////////////////////// 605 606 VspKdStatistics stat; 607 608 609 VspKdTree(); 610 virtual ~VspKdTree(); 611 612 virtual void 613 Construct( 614 VssRayContainer &rays, 615 AxisAlignedBox3 *forcedBoundingBox = NULL 616 ); 617 618 // incemental construction 619 virtual void UpdateRays(VssRayContainer &remove, 620 VssRayContainer &add 621 ); 622 623 virtual void AddRays( 624 VssRayContainer &add 625 ) 615 int minCollapseDepth; 616 617 // reusable array of split candidates 618 vector<SortableEntry> *splitCandidates; 619 620 ///////////////////////////// 621 VspKdStatistics stat; 622 623 VspKdTree(); 624 virtual ~VspKdTree(); 625 626 virtual void Construct(VssRayContainer &rays, 627 AxisAlignedBox3 *forcedBoundingBox = NULL); 628 629 // incemental construction 630 virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add); 631 632 virtual void AddRays(VssRayContainer &add) 626 633 { 627 634 VssRayContainer remove; … … 629 636 } 630 637 631 632 633 VspKdTreeNode * 634 Locate(const Vector3 &v); 635 636 VspKdTreeNode * 637 SubdivideNode(VspKdTreeLeaf *leaf, 638 const AxisAlignedBox3 &box, 639 AxisAlignedBox3 &backBox, 640 AxisAlignedBox3 &frontBox 641 ); 642 643 VspKdTreeNode * 644 Subdivide(const TraversalData &tdata); 645 646 int 647 SelectPlane(VspKdTreeLeaf *leaf, 648 const AxisAlignedBox3 &box, 649 float &position, 650 int &raysBack, 651 int &raysFront, 652 int &pvsBack, 653 int &pvsFront 654 ); 655 656 void 657 SortSplitCandidates( 658 VspKdTreeLeaf *node, 659 const int axis 660 ); 661 662 663 // return memory usage in MB 664 float GetMemUsage() const { 665 return 666 (sizeof(VspKdTree) + 667 stat.Leaves()*sizeof(VspKdTreeLeaf) + 668 stat.Interior()*sizeof(VspKdTreeInterior) + 669 stat.rayRefs*sizeof(VspKdTreeNode::RayInfo))/(1024.0f*1024.0f); 670 } 671 672 float GetRayMemUsage() const { 673 return 674 stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f); 675 } 676 677 float 678 BestCostRatioHeuristic( 679 VspKdTreeLeaf *node, 680 int &axis, 681 float &position, 682 int &raysBack, 683 int &raysFront, 684 int &pvsBack, 685 int &pvsFront 686 ); 687 688 float 689 BestCostRatioRegular( 690 VspKdTreeLeaf *node, 691 int &axis, 692 float &position, 693 int &raysBack, 694 int &raysFront, 695 int &pvsBack, 696 int &pvsFront 697 698 ); 699 700 float 701 EvalCostRatio( 702 VspKdTreeLeaf *node, 703 const int axis, 704 const float position, 705 int &raysBack, 706 int &raysFront, 707 int &pvsBack, 708 int &pvsFront 709 ); 710 711 AxisAlignedBox3 GetBBox(const VspKdTreeNode *node) { 712 if (node->parent == NULL) 713 return bbox; 714 715 if (!node->IsLeaf()) 716 return ((VspKdTreeInterior *)node)->bbox; 717 718 if (node->parent->axis >= 3) 719 return node->parent->bbox; 638 VspKdTreeNode *Locate(const Vector3 &v); 639 640 VspKdTreeNode *SubdivideNode(VspKdTreeLeaf *leaf, 641 const AxisAlignedBox3 &box, 642 AxisAlignedBox3 &backBox, 643 AxisAlignedBox3 &frontBox); 644 645 VspKdTreeNode *Subdivide(const TraversalData &tdata); 646 647 int SelectPlane(VspKdTreeLeaf *leaf, 648 const AxisAlignedBox3 &box, 649 float &position, 650 int &raysBack, 651 int &raysFront, 652 int &pvsBack, 653 int &pvsFront); 654 655 void SortSplitCandidates(VspKdTreeLeaf *node, 656 const int axis); 657 658 659 // return memory usage in MB 660 float GetMemUsage() const 661 { 662 return 663 (sizeof(VspKdTree) + 664 stat.Leaves() * sizeof(VspKdTreeLeaf) + 665 stat.Interior() * sizeof(VspKdTreeInterior) + 666 stat.rayRefs * sizeof(VspKdTreeNode::RayInfo)) / (1024.0f*1024.0f); 667 } 668 669 float GetRayMemUsage() const 670 { 671 return stat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f); 672 } 673 674 float BestCostRatioHeuristic(VspKdTreeLeaf *node, 675 int &axis, 676 float &position, 677 int &raysBack, 678 int &raysFront, 679 int &pvsBack, 680 int &pvsFront); 681 682 float BestCostRatioRegular(VspKdTreeLeaf *node, 683 int &axis, 684 float &position, 685 int &raysBack, 686 int &raysFront, 687 int &pvsBack, 688 int &pvsFront); 689 690 float EvalCostRatio(VspKdTreeLeaf *node, 691 const int axis, 692 const float position, 693 int &raysBack, 694 int &raysFront, 695 int &pvsBack, 696 int &pvsFront); 697 698 AxisAlignedBox3 GetBBox(const VspKdTreeNode *node) 699 { 700 if (node->parent == NULL) 701 return bbox; 702 703 if (!node->IsLeaf()) 704 return ((VspKdTreeInterior *)node)->bbox; 705 706 if (node->parent->axis >= 3) 707 return node->parent->bbox; 720 708 721 AxisAlignedBox3 box(node->parent->bbox); 722 if (node->parent->front == node) 723 box.SetMin(node->parent->axis, node->parent->position); 724 else 725 box.SetMax(node->parent->axis, node->parent->position); 726 return box; 727 } 728 729 AxisAlignedBox3 GetDirBBox(const VspKdTreeNode *node) { 730 731 if (node->parent == NULL) 732 return dirBBox; 709 AxisAlignedBox3 box(node->parent->bbox); 710 if (node->parent->front == node) 711 box.SetMin(node->parent->axis, node->parent->position); 712 else 713 box.SetMax(node->parent->axis, node->parent->position); 714 return box; 715 } 716 717 AxisAlignedBox3 GetDirBBox(const VspKdTreeNode *node) 718 { 719 if (node->parent == NULL) 720 return dirBBox; 721 if (!node->IsLeaf()) 722 return ((VspKdTreeInterior *)node)->dirBBox; 723 if (node->parent->axis < 3) 724 return node->parent->dirBBox; 733 725 734 if (!node->IsLeaf() ) 735 return ((VspKdTreeInterior *)node)->dirBBox; 736 737 if (node->parent->axis < 3) 738 return node->parent->dirBBox; 739 740 AxisAlignedBox3 dBBox(node->parent->dirBBox); 741 742 if (node->parent->front == node) 743 dBBox.SetMin(node->parent->axis - 3, node->parent->position); 744 else 745 dBBox.SetMax(node->parent->axis - 3, node->parent->position); 746 return dBBox; 747 } 748 749 int 750 ReleaseMemory(const int time); 751 752 int 753 CollapseSubtree(VspKdTreeNode *node, const int time); 754 755 void 756 CountAccess(VspKdTreeInterior *node, const long time) { 757 node->accesses++; 758 node->lastAccessTime = time; 759 } 760 761 VspKdTreeNode * 762 SubdivideLeaf( 763 VspKdTreeLeaf *leaf, 764 const float SAThreshold 765 ); 766 767 void 768 RemoveRay(VssRay *ray, 769 vector<VspKdTreeLeaf *> *affectedLeaves, 770 const bool removeAllScheduledRays 771 ); 772 773 void 774 AddRay(VssRay *ray); 775 776 void 777 TraverseInternalNode( 778 RayTraversalData &data, 779 stack<RayTraversalData> &tstack); 780 781 void 782 EvaluateLeafStats(const TraversalData &data); 783 784 785 int 786 GetRootPvsSize() const { 726 AxisAlignedBox3 dBBox(node->parent->dirBBox); 727 728 if (node->parent->front == node) 729 dBBox.SetMin(node->parent->axis - 3, node->parent->position); 730 else 731 dBBox.SetMax(node->parent->axis - 3, node->parent->position); 732 return dBBox; 733 } 734 735 int ReleaseMemory(const int time); 736 737 int CollapseSubtree(VspKdTreeNode *node, const int time); 738 739 void CountAccess(VspKdTreeInterior *node, const long time) 740 { 741 ++ node->accesses; 742 node->lastAccessTime = time; 743 } 744 745 VspKdTreeNode * SubdivideLeaf(VspKdTreeLeaf *leaf, 746 const float SAThreshold); 747 748 void RemoveRay(VssRay *ray, 749 vector<VspKdTreeLeaf *> *affectedLeaves, 750 const bool removeAllScheduledRays); 751 752 void AddRay(VssRay *ray); 753 754 void TraverseInternalNode(RayTraversalData &data, 755 stack<RayTraversalData> &tstack); 756 757 void EvaluateLeafStats(const TraversalData &data); 758 759 760 int GetRootPvsSize() const 761 { 787 762 return GetPvsSize(root, bbox); 788 763 } 789 764 790 int 791 GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const; 792 793 void 794 GetRayContributionStatistics( 795 float &minRayContribution, 796 float &maxRayContribution, 797 float &avgRayContribution 798 ); 799 800 int 801 GenerateRays(const float ratioPerLeaf, 802 SimpleRayContainer &rays); 803 804 float 805 GetAvgPvsSize(); 806 765 int GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const; 766 767 void GetRayContributionStatistics(float &minRayContribution, 768 float &maxRayContribution, 769 float &avgRayContribution); 770 771 int GenerateRays(const float ratioPerLeaf, 772 SimpleRayContainer &rays); 773 774 float GetAvgPvsSize(); 807 775 }; 808 776
Note: See TracChangeset
for help on using the changeset viewer.
