![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
- Timestamp:
- 07/07/06 16:14:33 (18 years ago)
- Location:
- GTP/trunk/Lib/Vis/Preprocessing
- Files:
-
- 1 added
- 3 edited
- 2 moved
-
scripts/Preprocessor.vcproj (modified) (3 diffs)
-
src/FlexibleHeap.h (added)
-
src/MyHeap.cpp (moved) (moved from GTP/trunk/Lib/Vis/Preprocessing/src/MxHeap.cxx) (1 diff)
-
src/MyHeap.h (moved) (moved from GTP/trunk/Lib/Vis/Preprocessing/src/MxHeap.h) (1 diff)
-
src/VspOspTree.cpp (modified) (14 diffs)
-
src/VspOspTree.h (modified) (10 diffs)
Legend:
- Unmodified
- Added
- Removed
-
GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj
r1097 r1099 158 158 </File> 159 159 <File 160 RelativePath="..\src\FlexibleHeap.h"> 161 </File> 162 <File 160 163 RelativePath="..\src\glInterface.h"> 161 164 </File> … … 502 505 RelativePath="..\src\X3dParserXerces.h"> 503 506 </File> 504 <Filter505 Name="mixkit"506 Filter="">507 <File508 RelativePath="..\src\mixkit\getopt.c">509 </File>510 <File511 RelativePath="..\src\mixkit\getopt.h">512 </File>513 <File514 RelativePath="..\src\mixkit\getopt1.c">515 </File>516 <File517 RelativePath="..\src\mixkit\mixio.h">518 </File>519 <File520 RelativePath="..\src\mixkit\mixmops.cxx">521 </File>522 <File523 RelativePath="..\src\mixkit\mixmops.h">524 </File>525 <File526 RelativePath="..\src\mixkit\mixmsg.cxx">527 </File>528 <File529 RelativePath="..\src\mixkit\mixmsg.h">530 </File>531 <File532 RelativePath="..\src\mixkit\mixvops.h">533 </File>534 <File535 RelativePath="..\src\mixkit\MxArcball.cxx">536 </File>537 <File538 RelativePath="..\src\mixkit\MxArcball.h">539 </File>540 <File541 RelativePath="..\src\mixkit\MxAsp.cxx">542 </File>543 <File544 RelativePath="..\src\mixkit\MxAsp.h">545 </File>546 <File547 RelativePath="..\src\mixkit\MxBlock.h">548 </File>549 <File550 RelativePath="..\src\mixkit\MxBlock2.h">551 </File>552 <File553 RelativePath="..\src\mixkit\MxBlock3.h">554 </File>555 <File556 RelativePath="..\src\mixkit\MxBlockModel.cxx">557 </File>558 <File559 RelativePath="..\src\mixkit\MxBlockModel.h">560 </File>561 <File562 RelativePath="..\src\mixkit\MxCamera.cxx">563 </File>564 <File565 RelativePath="..\src\mixkit\MxCamera.h">566 </File>567 <File568 RelativePath="..\src\mixkit\MxCmdParser.cxx">569 </File>570 <File571 RelativePath="..\src\mixkit\MxCmdParser.h">572 </File>573 <File574 RelativePath="..\src\mixkit\MxDynBlock.h">575 </File>576 <File577 RelativePath="..\src\mixkit\MxEdgeFilter.cxx">578 </File>579 <File580 RelativePath="..\src\mixkit\MxEdgeFilter.h">581 </File>582 <File583 RelativePath="..\src\mixkit\MxGeom3D.cxx">584 </File>585 <File586 RelativePath="..\src\mixkit\MxGeom3D.h">587 </File>588 <File589 RelativePath="..\src\mixkit\MxGeoPrims.h">590 </File>591 <File592 RelativePath="..\src\mixkit\MxGL.h">593 </File>594 <File595 RelativePath="..\src\mixkit\MxGLDebug.cxx">596 </File>597 <File598 RelativePath="..\src\mixkit\MxGLPane.cxx">599 </File>600 <File601 RelativePath="..\src\mixkit\MxGLPane.h">602 </File>603 <File604 RelativePath="..\src\mixkit\MxGLUtils.cxx">605 </File>606 <File607 RelativePath="..\src\mixkit\MxGLUtils.h">608 </File>609 <File610 RelativePath="..\src\mixkit\MxHeap.cxx">611 <FileConfiguration612 Name="Debug|Win32">613 <Tool614 Name="VCCLCompilerTool"615 ObjectFile="$(IntDir)/$(InputName)1.obj"/>616 </FileConfiguration>617 <FileConfiguration618 Name="Release|Win32">619 <Tool620 Name="VCCLCompilerTool"621 ObjectFile="$(IntDir)/$(InputName)1.obj"/>622 </FileConfiguration>623 </File>624 <File625 RelativePath="..\src\mixkit\MxHeap.h">626 </File>627 <File628 RelativePath="..\src\mixkit\MxLineModel.cxx">629 </File>630 <File631 RelativePath="..\src\mixkit\MxManipulator.h">632 </File>633 <File634 RelativePath="..\src\mixkit\MxMat2.cxx">635 </File>636 <File637 RelativePath="..\src\mixkit\MxMat2.h">638 </File>639 <File640 RelativePath="..\src\mixkit\MxMat3-jacobi.cxx">641 </File>642 <File643 RelativePath="..\src\mixkit\MxMat3.cxx">644 </File>645 <File646 RelativePath="..\src\mixkit\MxMat3.h">647 </File>648 <File649 RelativePath="..\src\mixkit\MxMat4-jacobi.cxx">650 </File>651 <File652 RelativePath="..\src\mixkit\MxMat4.cxx">653 </File>654 <File655 RelativePath="..\src\mixkit\MxMat4.h">656 </File>657 <File658 RelativePath="..\src\mixkit\MxMath.h">659 </File>660 <File661 RelativePath="..\src\mixkit\MxMatrix.cxx">662 </File>663 <File664 RelativePath="..\src\mixkit\MxMatrix.h">665 </File>666 <File667 RelativePath="..\src\mixkit\MxPropSlim.cxx">668 </File>669 <File670 RelativePath="..\src\mixkit\MxPropSlim.h">671 </File>672 <File673 RelativePath="..\src\mixkit\MxQMetric.cxx">674 </File>675 <File676 RelativePath="..\src\mixkit\MxQMetric.h">677 </File>678 <File679 RelativePath="..\src\mixkit\MxQMetric2.cxx">680 </File>681 <File682 RelativePath="..\src\mixkit\MxQMetric2.h">683 </File>684 <File685 RelativePath="..\src\mixkit\MxQMetric3.cxx">686 </File>687 <File688 RelativePath="..\src\mixkit\MxQMetric3.h">689 </File>690 <File691 RelativePath="..\src\mixkit\MxQSlim.cxx">692 </File>693 <File694 RelativePath="..\src\mixkit\MxQSlim.h">695 </File>696 <File697 RelativePath="..\src\mixkit\MxQVis3.cxx">698 </File>699 <File700 RelativePath="..\src\mixkit\MxRaster-tiff.cxx">701 </File>702 <File703 RelativePath="..\src\mixkit\MxRaster.cxx">704 </File>705 <File706 RelativePath="..\src\mixkit\MxRaster.h">707 </File>708 <File709 RelativePath="..\src\mixkit\MxSMF.cxx">710 </File>711 <File712 RelativePath="..\src\mixkit\MxSMF.h">713 </File>714 <File715 RelativePath="..\src\mixkit\MxStack.h">716 </File>717 <File718 RelativePath="..\src\mixkit\MxStdModel.cxx">719 </File>720 <File721 RelativePath="..\src\mixkit\MxStdModel.h">722 </File>723 <File724 RelativePath="..\src\mixkit\MxStdPane.cxx">725 </File>726 <File727 RelativePath="..\src\mixkit\MxStdPane.h">728 </File>729 <File730 RelativePath="..\src\mixkit\MxStdRender.cxx">731 </File>732 <File733 RelativePath="..\src\mixkit\MxStdSlim.cxx">734 </File>735 <File736 RelativePath="..\src\mixkit\MxStdSlim.h">737 </File>738 <File739 RelativePath="..\src\mixkit\MxTimer.cxx">740 </File>741 <File742 RelativePath="..\src\mixkit\MxTimer.h">743 </File>744 <File745 RelativePath="..\src\mixkit\MxTriProject.cxx">746 </File>747 <File748 RelativePath="..\src\mixkit\MxVec2.h">749 </File>750 <File751 RelativePath="..\src\mixkit\MxVec3.h">752 </File>753 <File754 RelativePath="..\src\mixkit\MxVec4.h">755 </File>756 <File757 RelativePath="..\src\mixkit\MxVector.h">758 </File>759 <File760 RelativePath="..\src\mixkit\stdmix.h">761 </File>762 </Filter>763 507 </Filter> 764 508 <Filter … … 798 542 <File 799 543 RelativePath="..\include\ViewCell.h"> 544 </File> 545 </Filter> 546 <Filter 547 Name="mixkit" 548 Filter=""> 549 <File 550 RelativePath="..\src\mixkit\getopt.c"> 551 </File> 552 <File 553 RelativePath="..\src\mixkit\getopt.h"> 554 </File> 555 <File 556 RelativePath="..\src\mixkit\getopt1.c"> 557 </File> 558 <File 559 RelativePath="..\src\mixkit\mixio.h"> 560 </File> 561 <File 562 RelativePath="..\src\mixkit\mixmops.cxx"> 563 </File> 564 <File 565 RelativePath="..\src\mixkit\mixmops.h"> 566 </File> 567 <File 568 RelativePath="..\src\mixkit\mixmsg.cxx"> 569 </File> 570 <File 571 RelativePath="..\src\mixkit\mixmsg.h"> 572 </File> 573 <File 574 RelativePath="..\src\mixkit\mixvops.h"> 575 </File> 576 <File 577 RelativePath="..\src\mixkit\MxArcball.cxx"> 578 </File> 579 <File 580 RelativePath="..\src\mixkit\MxArcball.h"> 581 </File> 582 <File 583 RelativePath="..\src\mixkit\MxAsp.cxx"> 584 </File> 585 <File 586 RelativePath="..\src\mixkit\MxAsp.h"> 587 </File> 588 <File 589 RelativePath="..\src\mixkit\MxBlock.h"> 590 </File> 591 <File 592 RelativePath="..\src\mixkit\MxBlock2.h"> 593 </File> 594 <File 595 RelativePath="..\src\mixkit\MxBlock3.h"> 596 </File> 597 <File 598 RelativePath="..\src\mixkit\MxBlockModel.cxx"> 599 </File> 600 <File 601 RelativePath="..\src\mixkit\MxBlockModel.h"> 602 </File> 603 <File 604 RelativePath="..\src\mixkit\MxCamera.cxx"> 605 </File> 606 <File 607 RelativePath="..\src\mixkit\MxCamera.h"> 608 </File> 609 <File 610 RelativePath="..\src\mixkit\MxCmdParser.cxx"> 611 </File> 612 <File 613 RelativePath="..\src\mixkit\MxCmdParser.h"> 614 </File> 615 <File 616 RelativePath="..\src\mixkit\MxDynBlock.h"> 617 </File> 618 <File 619 RelativePath="..\src\mixkit\MxEdgeFilter.cxx"> 620 </File> 621 <File 622 RelativePath="..\src\mixkit\MxEdgeFilter.h"> 623 </File> 624 <File 625 RelativePath="..\src\mixkit\MxGeom3D.cxx"> 626 </File> 627 <File 628 RelativePath="..\src\mixkit\MxGeom3D.h"> 629 </File> 630 <File 631 RelativePath="..\src\mixkit\MxGeoPrims.h"> 632 </File> 633 <File 634 RelativePath="..\src\mixkit\MxGL.h"> 635 </File> 636 <File 637 RelativePath="..\src\mixkit\MxGLDebug.cxx"> 638 </File> 639 <File 640 RelativePath="..\src\mixkit\MxGLPane.cxx"> 641 </File> 642 <File 643 RelativePath="..\src\mixkit\MxGLPane.h"> 644 </File> 645 <File 646 RelativePath="..\src\mixkit\MxGLUtils.cxx"> 647 </File> 648 <File 649 RelativePath="..\src\mixkit\MxGLUtils.h"> 650 </File> 651 <File 652 RelativePath="..\src\mixkit\MxHeap.cxx"> 653 <FileConfiguration 654 Name="Debug|Win32"> 655 <Tool 656 Name="VCCLCompilerTool" 657 ObjectFile="$(IntDir)/$(InputName)1.obj"/> 658 </FileConfiguration> 659 <FileConfiguration 660 Name="Release|Win32"> 661 <Tool 662 Name="VCCLCompilerTool" 663 ObjectFile="$(IntDir)/$(InputName)1.obj"/> 664 </FileConfiguration> 665 </File> 666 <File 667 RelativePath="..\src\mixkit\MxHeap.h"> 668 </File> 669 <File 670 RelativePath="..\src\mixkit\MxLineModel.cxx"> 671 </File> 672 <File 673 RelativePath="..\src\mixkit\MxManipulator.h"> 674 </File> 675 <File 676 RelativePath="..\src\mixkit\MxMat2.cxx"> 677 </File> 678 <File 679 RelativePath="..\src\mixkit\MxMat2.h"> 680 </File> 681 <File 682 RelativePath="..\src\mixkit\MxMat3-jacobi.cxx"> 683 </File> 684 <File 685 RelativePath="..\src\mixkit\MxMat3.cxx"> 686 </File> 687 <File 688 RelativePath="..\src\mixkit\MxMat3.h"> 689 </File> 690 <File 691 RelativePath="..\src\mixkit\MxMat4-jacobi.cxx"> 692 </File> 693 <File 694 RelativePath="..\src\mixkit\MxMat4.cxx"> 695 </File> 696 <File 697 RelativePath="..\src\mixkit\MxMat4.h"> 698 </File> 699 <File 700 RelativePath="..\src\mixkit\MxMath.h"> 701 </File> 702 <File 703 RelativePath="..\src\mixkit\MxMatrix.cxx"> 704 </File> 705 <File 706 RelativePath="..\src\mixkit\MxMatrix.h"> 707 </File> 708 <File 709 RelativePath="..\src\mixkit\MxPropSlim.cxx"> 710 </File> 711 <File 712 RelativePath="..\src\mixkit\MxPropSlim.h"> 713 </File> 714 <File 715 RelativePath="..\src\mixkit\MxQMetric.cxx"> 716 </File> 717 <File 718 RelativePath="..\src\mixkit\MxQMetric.h"> 719 </File> 720 <File 721 RelativePath="..\src\mixkit\MxQMetric2.cxx"> 722 </File> 723 <File 724 RelativePath="..\src\mixkit\MxQMetric2.h"> 725 </File> 726 <File 727 RelativePath="..\src\mixkit\MxQMetric3.cxx"> 728 </File> 729 <File 730 RelativePath="..\src\mixkit\MxQMetric3.h"> 731 </File> 732 <File 733 RelativePath="..\src\mixkit\MxQSlim.cxx"> 734 </File> 735 <File 736 RelativePath="..\src\mixkit\MxQSlim.h"> 737 </File> 738 <File 739 RelativePath="..\src\mixkit\MxQVis3.cxx"> 740 </File> 741 <File 742 RelativePath="..\src\mixkit\MxRaster-tiff.cxx"> 743 </File> 744 <File 745 RelativePath="..\src\mixkit\MxRaster.cxx"> 746 </File> 747 <File 748 RelativePath="..\src\mixkit\MxRaster.h"> 749 </File> 750 <File 751 RelativePath="..\src\mixkit\MxSMF.cxx"> 752 </File> 753 <File 754 RelativePath="..\src\mixkit\MxSMF.h"> 755 </File> 756 <File 757 RelativePath="..\src\mixkit\MxStack.h"> 758 </File> 759 <File 760 RelativePath="..\src\mixkit\MxStdModel.cxx"> 761 </File> 762 <File 763 RelativePath="..\src\mixkit\MxStdModel.h"> 764 </File> 765 <File 766 RelativePath="..\src\mixkit\MxStdPane.cxx"> 767 </File> 768 <File 769 RelativePath="..\src\mixkit\MxStdPane.h"> 770 </File> 771 <File 772 RelativePath="..\src\mixkit\MxStdRender.cxx"> 773 </File> 774 <File 775 RelativePath="..\src\mixkit\MxStdSlim.cxx"> 776 </File> 777 <File 778 RelativePath="..\src\mixkit\MxStdSlim.h"> 779 </File> 780 <File 781 RelativePath="..\src\mixkit\MxTimer.cxx"> 782 </File> 783 <File 784 RelativePath="..\src\mixkit\MxTimer.h"> 785 </File> 786 <File 787 RelativePath="..\src\mixkit\MxTriProject.cxx"> 788 </File> 789 <File 790 RelativePath="..\src\mixkit\MxVec2.h"> 791 </File> 792 <File 793 RelativePath="..\src\mixkit\MxVec3.h"> 794 </File> 795 <File 796 RelativePath="..\src\mixkit\MxVec4.h"> 797 </File> 798 <File 799 RelativePath="..\src\mixkit\MxVector.h"> 800 </File> 801 <File 802 RelativePath="..\src\mixkit\stdmix.h"> 800 803 </File> 801 804 </Filter> -
GTP/trunk/Lib/Vis/Preprocessing/src/MyHeap.cpp
r1097 r1099 1 /************************************************************************ 2 3 Heap data structure 4 5 Copyright (C) 1998 Michael Garland. See "COPYING.txt" for details. 6 7 $Id: MxHeap.cxx,v 1.1 2002/09/24 16:53:54 wimmer Exp $ 8 9 ************************************************************************/ 10 11 //#include "stdmix.h" 12 #include "MxHeap.h" 1 #include "MyHeap.h" 13 2 14 3 15 //////////////////////////////////////////////////////////////////////// 16 // 17 // Internal functions for manipulating the heap 4 namespace GtpVisibilityPreprocessor { 18 5 19 inline void MxHeap::place(MxHeapable *x, unsigned int i) 6 7 /*****************************************************************************/ 8 /* MyHeap implementation * 9 /*****************************************************************************/ 10 11 12 13 inline void MyHeap::Place(Heapable *x, unsigned int i) 20 14 { 21 ref(i)= x;22 x-> set_heap_pos(i);15 mBuffer[i] = x; 16 x->SetHeapPos(i); 23 17 } 24 18 25 void MxHeap::swap(unsigned int i, unsigned int j) 19 20 void MyHeap::Swap(unsigned int i, unsigned int j) 26 21 { 27 MxHeapable *tmp = ref(i);22 Heapable *tmp = mBuffer[i]; 28 23 29 place(ref(j), i);30 place(tmp, j);24 Place(mBuffer[j], i); 25 Place(tmp, j); 31 26 } 32 27 33 void MxHeap::upheap(unsigned int i) 28 29 void MyHeap::UpHeap(unsigned int i) 34 30 { 35 MxHeapable *moving = ref(i);36 u int index = i;37 u int p = parent(i);31 Heapable *moving = mBuffer[i]; 32 unsigned int index = i; 33 unsigned int p = Parent(i); 38 34 39 while ( index>0 && moving->heap_key() > ref(p)->heap_key())35 while ((index > 0) && (moving->SetPriority() > mBuffer[p]->SetPriority())) 40 36 { 41 place(ref(p), index);42 index = p;43 p = parent(p);37 Place(mBuffer[p], index); 38 index = p; 39 p = Parent(p); 44 40 } 45 41 46 if( index != i ) 47 place(moving, index); 42 if (index != i) 43 { 44 Place(moving, index); 45 } 48 46 } 49 47 50 void MxHeap::downheap(unsigned int i) 48 49 void MyHeap::DownHeap(unsigned int i) 51 50 { 52 MxHeapable *moving = ref(i); 53 uint index = i; 54 uint l = left(i); 55 uint r = right(i); 56 uint largest; 51 Heapable *moving = mBuffer[i]; 57 52 58 while( l<length() ) 59 { 60 if( r<length() && ref(l)->heap_key() < ref(r)->heap_key() ) 61 largest = r; 62 else 63 largest = l; 53 unsigned int index = i; 54 unsigned int l = Left(i); 55 unsigned int r = Right(i); 56 unsigned int largest; 64 57 65 if( moving->heap_key() < ref(largest)->heap_key())58 while (l < (int)mBuffer.size()) 66 59 { 67 place(ref(largest), index); 68 index = largest; 69 l = left(index); 70 r = right(index); 60 if ((r < (unsigned int)mBuffer.size()) && (mBuffer[l]->SetPriority() < mBuffer[r]->SetPriority())) 61 largest = r; 62 else 63 largest = l; 64 65 if (moving->SetPriority() < mBuffer[largest]->SetPriority()) 66 { 67 Place(mBuffer[largest], index); 68 index = largest; 69 l = Left(index); 70 r = Right(index); 71 } 72 else 73 { 74 break; 75 } 71 76 } 72 else73 break;74 }75 77 76 if( index != i ) 77 place(moving, index); 78 if (index != i) 79 { 80 Place(moving, index); 81 } 78 82 } 79 83 80 ////////////////////////////////////////////////////////////////////////81 //82 // Exported interface to the heap83 //84 84 85 void M xHeap::insert(MxHeapable *t, float v)85 void MyHeap::Push(Heapable *t, float v) 86 86 { 87 t-> heap_key(v);87 t->SetPriority(v); 88 88 89 unsigned int i = add(t); 90 t->set_heap_pos(i); 89 unsigned int i = (unsigned int)mBuffer.size(); 91 90 92 upheap(i); 91 t->SetHeapPos(i); 92 mBuffer.push_back(t); 93 94 UpHeap(i); 93 95 } 94 96 95 void MxHeap::update(MxHeapable *t, float v) 97 98 bool MyHeap::Update(Heapable *t, float v) 96 99 { 97 SanityCheck( t->is_in_heap() );98 t->heap_key(v);100 if (t->IsInHeap()) 101 return false; 99 102 100 unsigned int i = t->get_heap_pos();103 t->SetPriority(v); 101 104 102 if( i>0 && v>ref(parent(i))->heap_key() ) 103 upheap(i); 105 unsigned int i = t->GetHeapPos(); 106 107 if ((i > 0) && (v > mBuffer[Parent(i)]->SetPriority())) 108 UpHeap(i); 104 109 else 105 downheap(i); 110 DownHeap(i); 111 112 return true; 106 113 } 107 114 108 MxHeapable *MxHeap::extract() 115 116 Heapable *MyHeap::Pop() 109 117 { 110 if( length() < 1 ) return NULL; 118 if (mBuffer.empty()) 119 return NULL; 111 120 112 swap(0, length()-1); 113 MxHeapable *dead=drop(); 121 Swap(0, mBuffer.size() - 1); 122 123 Heapable *dead = mBuffer.back(); 124 mBuffer.pop_back(); 114 125 115 downheap(0); 116 dead->not_in_heap(); 126 DownHeap(0); 127 dead->NotInHeap(); 128 117 129 return dead; 118 130 } 119 131 120 MxHeapable *MxHeap::remove(MxHeapable *t) 132 133 Heapable *MyHeap::Erase(Heapable *t) 121 134 { 122 if( !t->is_in_heap() ) return NULL; 135 if (!t->IsInHeap()) 136 return NULL; 123 137 124 int i = t->get_heap_pos(); 125 swap(i, length()-1); 126 drop(); 127 t->not_in_heap(); 138 int i = t->GetHeapPos(); 128 139 129 if( ref(i)->heap_key() < t->heap_key() ) 130 downheap(i); 131 else 132 upheap(i); 140 Swap(i, mBuffer.size() - 1); 141 142 mBuffer.pop_back(); 143 t->NotInHeap(); 144 145 if (mBuffer[i]->SetPriority() < t->SetPriority()) 146 DownHeap(i); 147 else 148 UpHeap(i); 133 149 134 150 return t; 135 151 } 152 } -
GTP/trunk/Lib/Vis/Preprocessing/src/MyHeap.h
r1097 r1099 1 #ifndef MXHEAP_INCLUDED // -*- C++ -*- 2 #define MXHEAP_INCLUDED 3 #if !defined(__GNUC__) 4 # pragma once 5 #endif 1 #ifndef MYHEAP_H 2 #define MYHEAP_H 6 3 7 /************************************************************************ 4 #include <vector> 8 5 9 Heap 6 /** This class implementas a heap for 7 use as a priority queue. 10 8 11 Copyright (C) 1998 Michael Garland. See "COPYING.txt" for details. 12 13 $Id: MxHeap.h,v 1.1 2002/09/24 16:53:54 wimmer Exp $ 9 The class aditionally implements efficient remove 10 of arbitrary elements. 11 */ 14 12 15 ************************************************************************/ 13 namespace GtpVisibilityPreprocessor { 16 14 17 //#include "MxDynBlock.h" 18 typedef unsigned int uint; 15 const static int NOT_IN_HEAP = -100; 19 16 20 class MxHeapable17 class Heapable 21 18 { 22 private: 23 float import; 24 int token; 19 public: 20 Heapable() { NotInHeap(); HeapKey(0.0f); } 25 21 26 public: 27 MxHeapable() { not_in_heap(); heap_key(0.0f); } 22 inline bool IsInHeap() { return mPosition != NOT_IN_HEAP; } 23 inline void NotInHeap() { mPosition = NOT_IN_HEAP; } 24 inline int GetHeapPos() { return mPosition; } 25 inline void SetHeapPos(int t) { mPosition = t; } 28 26 29 inline bool is_in_heap() { return token != -47; } 30 inline void not_in_heap() { token = -47; } 31 inline int get_heap_pos() { return token; } 32 inline void set_heap_pos(int t) { token=t; } 27 inline void HeapKey(float k) { mPriority = k; } 28 inline float HeapKey() const { return mPriority; } 33 29 34 inline void heap_key(float k) { import=k; } 35 inline float heap_key() const { return import; } 30 protected: 31 32 float mPriority; 33 int mPosition; 36 34 }; 37 35 38 36 39 class M xHeap// : private MxDynBlock<MxHeapable *>37 class MyHeap 40 38 { 41 p rivate:42 void place(MxHeapable *x, unsigned int i);43 void swap(unsigned int i, unsigned int j);39 public: 40 MyHeap() { } 41 MyHeap(unsigned int n) : mBuffer(n) { } 44 42 45 unsigned int parent(unsigned int i) { return (i-1)/2; } 46 unsigned int left(unsigned int i) { return 2*i+1; } 47 unsigned int right(unsigned int i) { return 2*i+2; } 43 void Push(Heapable *t) { Push(t, t->HeapKey()); } 44 void Push(Heapable *, float); 45 bool Update(Heapable *t) { return Update(t, t->HeapKey()); } 46 bool Update(Heapable *, float); 48 47 49 void upheap(unsigned int i); 50 void downheap(unsigned int i); 48 unsigned int Size() const { return (unsigned int)mBuffer.size(); } 49 bool Empty() const {return mBuffer.empty(); } 50 Heapable *Item(unsigned int i) { return mBuffer[i]; } 51 const Heapable *Item(unsigned int i) const { return mBuffer[i]; } 52 Heapable *Pop(); 53 Heapable *Top() { return (mBuffer.empty() ? (Heapable *)NULL : mBuffer.front()); } 54 Heapable *Erase(Heapable *); 51 55 52 public: 53 MxHeap()/* : MxDynBlock<MxHeapable *>(8)*/ { } 54 // MxHeap(unsigned int n) : MxDynBlock<MxHeapable *>(n) { } 56 protected: 55 57 56 void insert(MxHeapable *t) { insert(t, t->heap_key()); } 57 void insert(MxHeapable *, float); 58 void update(MxHeapable *t) { update(t, t->heap_key()); } 59 void update(MxHeapable *, float); 58 void Place(Heapable *x, unsigned int i); 59 void Swap(unsigned int i, unsigned int j); 60 60 61 unsigned int size() const { return length(); } 62 MxHeapable *item(uint i) { return ref(i); } 63 const MxHeapable *item(uint i) const { return ref(i); } 64 MxHeapable *extract(); 65 MxHeapable *top() { return (length()<1 ? (MxHeapable *)NULL : raw(0)); } 66 MxHeapable *remove(MxHeapable *); 61 unsigned int Parent(unsigned int i) { return (i-1)/2; } 62 unsigned int Left(unsigned int i) { return 2*i+1; } 63 unsigned int Right(unsigned int i) { return 2*i+2; } 64 65 void UpHeap(unsigned int i); 66 void DownHeap(unsigned int i); 67 68 std::vector<Heapable* > mBuffer; 67 69 }; 68 70 69 // MXHEAP_INCLUDED 71 } 72 73 // MYHEAP_H 70 74 #endif -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
r1097 r1099 30 30 int VspTree::sFrontAndBackId = 0; 31 31 32 32 VspTree *VspTree::VspSplitCandidate::sVspTree = NULL; 33 OspTree *OspTree::OspSplitCandidate::sOspTree = NULL; 33 34 34 35 // pvs penalty can be different from pvs size … … 442 443 AxisAlignedBox3 *forcedBoundingBox) 443 444 { 445 // store pointer to this tree 446 VspSplitCandidate::sVspTree = this; 447 444 448 mVspStats.nodes = 1; 445 449 … … 574 578 575 579 //-- push the new split candidates on the queue 576 VspSplitCandidate *frontCandidate = new VspSplitCandidate( );577 VspSplitCandidate *backCandidate = new VspSplitCandidate( );578 579 EvalSplitCandidate( tFrontData,*frontCandidate);580 EvalSplitCandidate( tBackData,*backCandidate);581 582 tQueue. push(frontCandidate);583 tQueue. push(backCandidate);580 VspSplitCandidate *frontCandidate = new VspSplitCandidate(tFrontData); 581 VspSplitCandidate *backCandidate = new VspSplitCandidate(tBackData); 582 583 EvalSplitCandidate(*frontCandidate); 584 EvalSplitCandidate(*backCandidate); 585 586 tQueue.Push(frontCandidate); 587 tQueue.Push(backCandidate); 584 588 585 589 // delete old leaf node … … 634 638 635 639 636 void VspTree::EvalSplitCandidate(VspTraversalData &tData, 637 VspSplitCandidate &splitCandidate) 640 void VspTree::EvalSplitCandidate(VspSplitCandidate &splitCandidate) 638 641 { 639 642 float frontProb; 640 643 float backProb; 641 644 642 VspLeaf *leaf = dynamic_cast<VspLeaf *>( tData.mNode);645 VspLeaf *leaf = dynamic_cast<VspLeaf *>(splitCandidate.mParentData.mNode); 643 646 644 647 // compute locally best split plane 645 648 const bool success = 646 SelectSplitPlane( tData, splitCandidate.mSplitPlane,frontProb, backProb);649 SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb); 647 650 648 651 // compute global decrease in render cost 649 splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane,tData);650 splitCandidate. mParentData = tData;651 splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses :tData.mMaxCostMisses + 1;652 const float priority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData); 653 splitCandidate.SetPriority(priority); 654 splitCandidate.mMaxCostMisses = success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1; 652 655 653 656 //Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl; … … 2539 2542 2540 2543 OspTree::OspTree(): 2541 mRoot(NULL) 2542 #if TODO 2543 mOutOfBoundsCell(NULL), 2544 mStoreRays(false), 2545 mUseRandomAxis(false), 2544 mRoot(NULL), 2546 2545 mTimeStamp(1) 2547 #endif2548 2546 { 2549 2547 #if TODO … … 2751 2749 2752 2750 //-- push the new split candidates on the queue 2753 OspSplitCandidate *frontCandidate = new OspSplitCandidate( );2754 OspSplitCandidate *backCandidate = new OspSplitCandidate( );2755 2756 EvalSplitCandidate( tFrontData,*frontCandidate);2757 EvalSplitCandidate( tBackData,*backCandidate);2758 2759 tQueue. push(frontCandidate);2760 tQueue. push(backCandidate);2751 OspSplitCandidate *frontCandidate = new OspSplitCandidate(tFrontData); 2752 OspSplitCandidate *backCandidate = new OspSplitCandidate(tBackData); 2753 2754 EvalSplitCandidate(*frontCandidate); 2755 EvalSplitCandidate(*backCandidate); 2756 2757 tQueue.Push(frontCandidate); 2758 tQueue.Push(backCandidate); 2761 2759 2762 2760 // delete old leaf node … … 2779 2777 2780 2778 2781 void OspTree::EvalSplitCandidate(OspTraversalData &tData, 2782 OspSplitCandidate &splitCandidate) 2779 void OspTree::EvalSplitCandidate(OspSplitCandidate &splitCandidate) 2783 2780 { 2784 2781 float frontProb; 2785 2782 float backProb; 2786 2783 2787 KdLeaf *leaf = dynamic_cast<KdLeaf *>( tData.mNode);2784 KdLeaf *leaf = dynamic_cast<KdLeaf *>(splitCandidate.mParentData.mNode); 2788 2785 2789 2786 // compute locally best split plane 2790 2787 const bool success = 2791 SelectSplitPlane( tData, splitCandidate.mSplitPlane,frontProb, backProb);2788 SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb); 2792 2789 2793 2790 //TODO 2794 2791 // compute global decrease in render cost 2795 splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, tData); 2796 splitCandidate.mParentData = tData; 2797 splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 2792 splitCandidate.SetPriority(EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData)); 2793 splitCandidate.mMaxCostMisses = success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1; 2798 2794 } 2799 2795 … … 3263 3259 AxisAlignedBox3 *forcedBoundingBox) 3264 3260 { 3261 // store pointer to this tree 3262 OspSplitCandidate::sOspTree = this; 3263 3265 3264 mOspStats.nodes = 1; 3266 3265 … … 3331 3330 SplitCandidate *HierarchyManager::NextSplitCandidate() 3332 3331 { 3333 SplitCandidate *splitCandidate = mTQueue.top();3332 SplitCandidate *splitCandidate = static_cast<SplitCandidate *>(mTQueue.Top()); 3334 3333 //Debug << "priority: " << splitCandidate->GetPriority() << endl; 3335 mTQueue. pop();3334 mTQueue.Pop(); 3336 3335 3337 3336 return splitCandidate; … … 3398 3397 3399 3398 // compute first split candidate 3400 VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate( );3401 mVspTree.EvalSplitCandidate( vData,*splitCandidate);3402 3403 mTQueue. push(splitCandidate);3399 VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate(vData); 3400 mVspTree.EvalSplitCandidate(*splitCandidate); 3401 3402 mTQueue.Push(splitCandidate); 3404 3403 3405 3404 … … 3427 3426 3428 3427 // compute first split candidate 3429 OspTree::OspSplitCandidate *oSplitCandidate = new OspTree::OspSplitCandidate( );3430 mOspTree.EvalSplitCandidate( oData,*oSplitCandidate);3431 3432 mTQueue. push(splitCandidate);3428 OspTree::OspSplitCandidate *oSplitCandidate = new OspTree::OspSplitCandidate(oData); 3429 mOspTree.EvalSplitCandidate(*oSplitCandidate); 3430 3431 mTQueue.Push(splitCandidate); 3433 3432 } 3434 3433 … … 3488 3487 3489 3488 //-- subdivide leaf node 3490 //-- either a object space or view space split3489 //-- we have either a object space or view space split 3491 3490 if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE) 3492 3491 { … … 3515 3514 bool HierarchyManager::FinishedConstruction() 3516 3515 { 3517 return mTQueue. empty();3518 } 3519 3520 3521 void HierarchyManager::RepairQueue( )3516 return mTQueue.Empty(); 3517 } 3518 3519 3520 void HierarchyManager::RepairQueue(const vector<SplitCandidate *> &dirtyList) 3522 3521 { 3523 3522 // TODO … … 3535 3534 // (explicit data structure, binary tree) 3536 3535 // *) inserting and removal is efficient 3537 // *) search is not efficient => store pointer to queue elementwith each3536 // *) search is not efficient => store queue position with each 3538 3537 // split candidate 3539 3538 3540 vector<SplitCandidate *> candidates; 3541 3542 while (!mTQueue.empty()) 3543 { 3544 SplitCandidate *candidate = mTQueue.top(); 3545 mTQueue.pop(); 3546 3547 candidates.push_back(candidate); 3548 } 3549 3550 // Reinsert 3551 3552 } 3553 3554 } 3539 vector<SplitCandidate *>::const_iterator sit, sit_end = dirtyList.end(); 3540 3541 for (sit = dirtyList.begin(); sit != sit_end; ++ sit) 3542 { 3543 SplitCandidate* sc = *sit; 3544 3545 mTQueue.Erase(sc); 3546 3547 // reevaluate 3548 sc->EvalPriority(); 3549 3550 // reinsert 3551 mTQueue.Push(sc); 3552 } 3553 } 3554 3555 } -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
r1097 r1099 10 10 #include "RayInfo.h" 11 11 #include "gzstream.h" 12 #include " mixkit/MxHeap.h"12 #include "FlexibleHeap.h" 13 13 14 14 … … 48 48 /** Candidate for a view space / object space split. 49 49 */ 50 class SplitCandidate: public MxHeapable50 class SplitCandidate: public Heapable 51 51 { 52 52 public: … … 62 62 63 63 /// priority of this split 64 float mPriority; 65 66 /// pointers used for building up heap 67 SplitCandidate *mParent; 68 SplitCandidate *mLeft; 69 SplitCandidate *mRight; 70 71 SplitCandidate(): mPriority(0) 64 //float mPriority; 65 66 SplitCandidate() 72 67 {}; 73 68 … … 75 70 {} 76 71 72 virtual void EvalPriority() = 0; 77 73 virtual int Type() const = 0; 78 79 /** Returns cost of the traversal data.80 */81 float GetPriority() const82 {83 return mPriority;84 }85 86 /*friend bool operator<(const SplitCandidate &a, const SplitCandidate &b)87 {88 return a.GetPriority() < b.GetPriority();89 }*/90 74 }; 91 75 … … 462 446 463 447 448 #if 0 464 449 typedef std::priority_queue<SplitCandidate *, 465 450 std::vector<SplitCandidate *>, 466 451 GtPriority<std::vector<SplitCandidate *>::value_type> > SplitQueue; 467 468 #if TODO469 /** candidate for a view space split470 */471 class OspSplitCandidate: public SplitCandidate472 {473 /// parent data474 OspTraversalData mParentData;475 476 VspOspSplitCandidate(): mRenderCost(0)477 {};478 479 int Type() const { return OSP_CANDIDATE; }480 481 VspOspSplitCandidate(const AxisAlignedPlane &plane, const VspOspTraversalData &tData):482 mSplitPlane(plane), mParentData(tData), mRenderCost(0)483 {}484 };485 452 #endif 453 454 typedef FlexibleHeap<SplitCandidate *> SplitQueue; 486 455 487 456 /** View Space Partitioning tree. … … 588 557 { 589 558 public: 559 static VspTree* sVspTree; 590 560 /// parent data 591 561 VspTraversalData mParentData; 592 562 593 VspSplitCandidate( )563 VspSplitCandidate(const VspTraversalData &tData): mParentData(tData) 594 564 {}; 595 565 596 566 int Type() const { return VIEW_SPACE; } 567 568 void EvalPriority() 569 { 570 sVspTree->EvalSplitCandidate(*this); 571 } 597 572 598 573 VspSplitCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData): … … 796 771 /** Evaluates candidate for splitting. 797 772 */ 798 void EvalSplitCandidate(Vsp TraversalData &tData, VspSplitCandidate &splitData);773 void EvalSplitCandidate(VspSplitCandidate &splitData); 799 774 800 775 /** Evaluates render cost decrease of next split. … … 1206 1181 { 1207 1182 public: 1183 static OspTree* sOspTree; 1184 1208 1185 /// parent data 1209 1186 OspTraversalData mParentData; 1210 1187 1211 OspSplitCandidate( )1188 OspSplitCandidate(const OspTraversalData &tData): mParentData(tData) 1212 1189 {}; 1213 1190 1214 1191 int Type() const { return VIEW_SPACE; } 1192 1193 void EvalPriority() 1194 { 1195 sOspTree->EvalSplitCandidate(*this); 1196 } 1215 1197 1216 1198 OspSplitCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData): … … 1376 1358 /** Evaluates candidate for splitting. 1377 1359 */ 1378 void EvalSplitCandidate(Osp TraversalData &tData, OspSplitCandidate &splitData);1360 void EvalSplitCandidate(OspSplitCandidate &splitData); 1379 1361 1380 1362 /** Computes priority of the traversal data and stores it in tData. … … 1706 1688 SplitCandidate *NextSplitCandidate(); 1707 1689 1708 void RepairQueue( );1690 void RepairQueue(const vector<SplitCandidate *> &dirtyList); 1709 1691 1710 1692 AxisAlignedBox3 mBoundingBox;
Note: See TracChangeset
for help on using the changeset viewer.
