![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
Changeset 1545 for GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h
- Timestamp:
- 09/29/06 22:42:25 (18 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h
r1449 r1545 27 27 { 28 28 public: 29 /** Default constructor. 30 */ 29 31 BspNodeGeometry() 30 32 {}; … … 343 345 { 344 346 friend class BspTree; 347 345 348 public: 346 349 /** Standard contructor taking split plane as argument. … … 438 441 } 439 442 440 441 443 /// Rays piercing this leaf. 442 444 VssRayContainer mVssRays; … … 444 446 /// leaf pvs 445 447 ObjectPvs *mPvs; 446 448 447 449 /// Probability that the view point lies in this leaf 448 450 float mProbability; … … 607 609 BspNode *GetRoot() const; 608 610 609 610 //bool Export(const string filename);611 612 611 /** Collects the leaf view cells of the tree 613 612 @param viewCells returns the view cells … … 629 628 630 629 /// bsp tree construction types 631 enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};630 //enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES}; 632 631 633 632 /** Returns statistics. … … 678 677 bool Export(ofstream &stream); 679 678 680 681 /** Returns view cell corresponding to 682 the invalid view space. If it does not exist, it is created. 683 */ 684 BspViewCell *GetOutOfBoundsCell(); 685 686 ViewCellsTree *mViewCellsTree; 687 679 /** Pointer to the view cells tree. 680 */ 681 void SetViewCellsTree(ViewCellsTree *vct); 682 688 683 protected: 689 690 // --------------------------------------------------------------691 // For sorting objects692 // --------------------------------------------------------------693 struct SortableEntry694 {695 enum {POLY_MIN, POLY_MAX};696 697 int type;698 float value;699 Polygon3 *poly;700 SortableEntry() {}701 SortableEntry(const int t, const float v, Polygon3 *poly):702 type(t), value(v), poly(poly) {}703 704 bool operator<(const SortableEntry &b) const705 {706 return value < b.value;707 }708 };709 710 void ExportNode(BspNode *node, ofstream &stream);711 712 /** Evaluates tree stats in the BSP tree leafs.713 */714 void EvaluateLeafStats(const BspTraversalData &data);715 716 /** Subdivides node with respect to the traversal data.717 @param tStack current traversal stack718 @param tData traversal data also holding node to be subdivided719 @returns new root of the subtree720 */721 BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData);722 723 /** Constructs the tree from the given list of polygons and rays.724 @param polys stores set of polygons on which subdivision may be based725 @param rays storesset of rays on which subdivision may be based726 */727 void Construct(PolygonContainer *polys, BoundedRayContainer *rays);728 729 /** Selects the best possible splitting plane.730 @param leaf the leaf to be split731 @param polys the polygon list on which the split decition is based732 @param rays ray container on which selection may be based733 @note the polygons can be reordered in the process734 @returns the split plane735 */736 Plane3 SelectPlane(BspLeaf *leaf,737 BspTraversalData &data);738 739 /** Evaluates the contribution of the candidate split plane.740 741 @param candidatePlane the candidate split plane742 @param polys the polygons the split can be based on743 @param rays the rays the split can be based on744 745 @returns the cost of the candidate split plane746 */747 float SplitPlaneCost(const Plane3 &candidatePlane,748 BspTraversalData &data) const;749 750 /** Strategies where the effect of the split plane is tested751 on all input rays.752 @returns the cost of the candidate split plane753 */754 float SplitPlaneCost(const Plane3 &candidatePlane,755 const PolygonContainer &polys) const;756 757 /** Strategies where the effect of the split plane is tested758 on all input rays.759 760 @returns the cost of the candidate split plane761 */762 float SplitPlaneCost(const Plane3 &candidatePlane,763 const BoundedRayContainer &rays,764 const int pvs,765 const float probability,766 const BspNodeGeometry &cell) const;767 768 /** Filters next view cell down the tree and inserts it into the appropriate leaves769 (i.e., possibly more than one leaf).770 */771 void InsertViewCell(ViewCellLeaf *viewCell);772 /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,773 then further subdivided.774 */775 void InsertPolygons(PolygonContainer *polys);776 777 /** Subdivide leaf.778 @param leaf the leaf to be subdivided779 780 @param polys the polygons to be split781 @param frontPolys returns the polygons in front of the split plane782 @param backPolys returns the polygons in the back of the split plane783 784 @param rays the polygons to be filtered785 @param frontRays returns the polygons in front of the split plane786 @param backRays returns the polygons in the back of the split plane787 788 @returns the root of the subdivision789 */790 791 BspInterior *SubdivideNode(BspTraversalData &tData,792 BspTraversalData &frontData,793 BspTraversalData &backData,794 PolygonContainer &coincident);795 796 /** Filters polygons down the tree.797 @param node the current BSP node798 @param polys the polygons to be filtered799 @param frontPolys returns the polygons in front of the split plane800 @param backPolys returns the polygons in the back of the split plane801 */802 void FilterPolygons(BspInterior *node,803 PolygonContainer *polys,804 PolygonContainer *frontPolys,805 PolygonContainer *backPolys);806 807 /** Take 3 ray endpoints, where two are minimum and one a maximum808 point or the other way round.809 */810 Plane3 ChooseCandidatePlane(const BoundedRayContainer &rays) const;811 812 /** Take plane normal as plane normal and the midpoint of the ray.813 PROBLEM: does not resemble any point where visibility is likely to change814 */815 Plane3 ChooseCandidatePlane2(const BoundedRayContainer &rays) const;816 817 /** Fit the plane between the two lines so that the plane has equal shortest818 distance to both lines.819 */820 Plane3 ChooseCandidatePlane3(const BoundedRayContainer &rays) const;821 822 /** Selects the split plane in order to construct a tree with823 certain characteristics (e.g., balanced tree, least splits,824 2.5d aligned)825 @param polygons container of polygons826 @param rays bundle of rays on which the split can be based827 */828 Plane3 SelectPlaneHeuristics(BspLeaf *leaf,829 BspTraversalData &data);830 831 /** Extracts the meshes of the objects and adds them to polygons.832 Adds object aabb to the aabb of the tree.833 @param maxPolys the maximal number of objects to be stored as polygons834 @returns the number of polygons835 */836 int AddToPolygonSoup(const ObjectContainer &objects,837 PolygonContainer &polys,838 int maxObjects = 0,839 bool addToBbox = true);840 841 /** Extracts the meshes of the view cells and and adds them to polygons.842 Adds view cell aabb to the aabb of the tree.843 @param maxPolys the maximal number of objects to be stored as polygons844 @returns the number of polygons845 */846 int AddToPolygonSoup(const ViewCellContainer &viewCells,847 PolygonContainer &polys,848 int maxObjects = 0);849 850 /** Extract polygons of this mesh and add to polygon container.851 @param mesh the mesh that drives the polygon construction852 @param parent the parent intersectable this polygon is constructed from853 @returns number of polygons854 */855 int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);856 857 /** Helper function which extracts a view cell on the front and the back858 of the split plane.859 @param backViewCell returns view cell on the back of the split plane860 @param frontViewCell returns a view cell on the front of the split plane861 @param coincident container of polygons coincident to the split plane862 @param splitPlane the split plane which decides about back and front863 @param extractBack if a back view cell is extracted864 @param extractFront if a front view cell is extracted865 */866 void ExtractViewCells(BspTraversalData &frontData,867 BspTraversalData &backData,868 const PolygonContainer &coincident,869 const Plane3 &splitPlane) const;870 871 /** Computes best cost ratio for the suface area heuristics for axis aligned872 splits. This heuristics minimizes the cost for ray traversal.873 @param polys the polygons guiding the ratio computation874 @param box the bounding box of the leaf875 @param axis the current split axis876 @param position returns the split position877 @param objectsBack the number of objects in the back of the split plane878 @param objectsFront the number of objects in the front of the split plane879 */880 float BestCostRatio(const PolygonContainer &polys,881 const AxisAlignedBox3 &box,882 const int axis,883 float &position,884 int &objectsBack,885 int &objectsFront) const;886 887 /** Sorts split candidates for cost heuristics using axis aligned splits.888 @param polys the input for choosing split candidates889 @param axis the current split axis890 @param splitCandidates returns sorted list of split candidates891 */892 void SortSubdivisionCandidates(const PolygonContainer &polys,893 const int axis,894 vector<SortableEntry> &splitCandidates) const;895 896 /** Selects an axis aligned split plane.897 Returns true if split is valied898 */899 bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;900 901 /** Subdivides the rays into front and back rays according to the split plane.902 903 @param plane the split plane904 @param rays contains the rays to be split. The rays are905 distributed into front and back rays.906 @param frontRays returns rays on the front side of the plane907 @param backRays returns rays on the back side of the plane908 909 @returns the number of splits910 */911 int SplitRays(const Plane3 &plane,912 BoundedRayContainer &rays,913 BoundedRayContainer &frontRays,914 BoundedRayContainer &backRays);915 916 917 /** Extracts the split planes representing the space bounded by node n.918 */919 void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;920 921 /** Adds the object to the pvs of the front and back leaf with a given classification.922 923 @param obj the object to be added924 @param cf the ray classification regarding the split plane925 @param frontPvs returns the PVS of the front partition926 @param backPvs returns the PVS of the back partition927 928 */929 void AddObjToPvs(Intersectable *obj, const int cf, int &frontPvs, int &backPvs) const;930 931 /** Computes PVS size induced by the rays.932 */933 int ComputePvsSize(const BoundedRayContainer &rays) const;934 935 /** Returns true if tree can be terminated.936 */937 inline bool TerminationCriteriaMet(const BspTraversalData &data) const;938 939 /** Computes accumulated ray lenght of this rays.940 */941 float AccumulatedRayLength(BoundedRayContainer &rays) const;942 943 /** Splits polygons with respect to the split plane.944 @param polys the polygons to be split. the polygons are consumed and945 distributed to the containers frontPolys, backPolys, coincident.946 @param frontPolys returns the polygons in the front of the split plane947 @param backPolys returns the polygons in the back of the split plane948 @param coincident returns the polygons coincident to the split plane949 950 @returns the number of splits951 */952 int SplitPolygons(const Plane3 &plane,953 PolygonContainer &polys,954 PolygonContainer &frontPolys,955 PolygonContainer &backPolys,956 PolygonContainer &coincident) const;957 958 /** Adds ray sample contributions to the PVS.959 @param sampleContributions the number contributions of the samples960 @param contributingSampels the number of contributing rays961 962 */963 void AddToPvs(BspLeaf *leaf,964 const BoundedRayContainer &rays,965 int &sampleContributions,966 int &contributingSamples);967 968 /** Preprocesses polygons and throws out all polygons which969 are coincident to the view space box faces:970 These polygons can can be problematic for bsp because they create971 bad view cells.972 */973 void PreprocessPolygons(PolygonContainer &polys);974 975 /** Returns view cell corresponding to the invalid view space.976 If it does not exist, it is created.977 */978 BspViewCell *GetOrCreateOutOfBoundsCell();979 980 /// Pointer to the root of the tree.981 BspNode *mRoot;982 983 /// Stores statistics during traversal.984 BspTreeStatistics mStat;985 684 986 685 /// Strategies for choosing next split plane. … … 999 698 }; 1000 699 700 /** 701 For sorting polygons 702 */ 703 struct SortableEntry 704 { 705 enum {POLY_MIN, POLY_MAX}; 706 707 int type; 708 float value; 709 Polygon3 *poly; 710 SortableEntry() {} 711 SortableEntry(const int t, const float v, Polygon3 *poly): 712 type(t), value(v), poly(poly) {} 713 714 bool operator<(const SortableEntry &b) const 715 { 716 return value < b.value; 717 } 718 }; 719 720 void ExportNode(BspNode *node, ofstream &stream); 721 722 /** Evaluates tree stats in the BSP tree leafs. 723 */ 724 void EvaluateLeafStats(const BspTraversalData &data); 725 726 /** Subdivides node with respect to the traversal data. 727 @param tStack current traversal stack 728 @param tData traversal data also holding node to be subdivided 729 @returns new root of the subtree 730 */ 731 BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData); 732 733 /** Constructs the tree from the given list of polygons and rays. 734 @param polys stores set of polygons on which subdivision may be based 735 @param rays storesset of rays on which subdivision may be based 736 */ 737 void Construct(PolygonContainer *polys, BoundedRayContainer *rays); 738 739 /** Selects the best possible splitting plane. 740 @param leaf the leaf to be split 741 @param polys the polygon list on which the split decition is based 742 @param rays ray container on which selection may be based 743 @note the polygons can be reordered in the process 744 @returns the split plane 745 */ 746 Plane3 SelectPlane(BspLeaf *leaf, 747 BspTraversalData &data); 748 749 /** Evaluates the contribution of the candidate split plane. 750 751 @param candidatePlane the candidate split plane 752 @param polys the polygons the split can be based on 753 @param rays the rays the split can be based on 754 755 @returns the cost of the candidate split plane 756 */ 757 float SplitPlaneCost(const Plane3 &candidatePlane, 758 BspTraversalData &data) const; 759 760 /** Strategies where the effect of the split plane is tested 761 on all input rays. 762 @returns the cost of the candidate split plane 763 */ 764 float SplitPlaneCost(const Plane3 &candidatePlane, 765 const PolygonContainer &polys) const; 766 767 /** Strategies where the effect of the split plane is tested 768 on all input rays. 769 770 @returns the cost of the candidate split plane 771 */ 772 float SplitPlaneCost(const Plane3 &candidatePlane, 773 const BoundedRayContainer &rays, 774 const int pvs, 775 const float probability, 776 const BspNodeGeometry &cell) const; 777 778 /** Filters next view cell down the tree and inserts it into the appropriate leaves 779 (i.e., possibly more than one leaf). 780 */ 781 void InsertViewCell(ViewCellLeaf *viewCell); 782 /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached, 783 then further subdivided. 784 */ 785 void InsertPolygons(PolygonContainer *polys); 786 787 /** Subdivide leaf. 788 @param leaf the leaf to be subdivided 789 790 @param polys the polygons to be split 791 @param frontPolys returns the polygons in front of the split plane 792 @param backPolys returns the polygons in the back of the split plane 793 794 @param rays the polygons to be filtered 795 @param frontRays returns the polygons in front of the split plane 796 @param backRays returns the polygons in the back of the split plane 797 798 @returns the root of the subdivision 799 */ 800 801 BspInterior *SubdivideNode(BspTraversalData &tData, 802 BspTraversalData &frontData, 803 BspTraversalData &backData, 804 PolygonContainer &coincident); 805 806 /** Filters polygons down the tree. 807 @param node the current BSP node 808 @param polys the polygons to be filtered 809 @param frontPolys returns the polygons in front of the split plane 810 @param backPolys returns the polygons in the back of the split plane 811 */ 812 void FilterPolygons(BspInterior *node, 813 PolygonContainer *polys, 814 PolygonContainer *frontPolys, 815 PolygonContainer *backPolys); 816 817 /** Take 3 ray endpoints, where two are minimum and one a maximum 818 point or the other way round. 819 */ 820 Plane3 ChooseCandidatePlane(const BoundedRayContainer &rays) const; 821 822 /** Take plane normal as plane normal and the midpoint of the ray. 823 PROBLEM: does not resemble any point where visibility is likely to change 824 */ 825 Plane3 ChooseCandidatePlane2(const BoundedRayContainer &rays) const; 826 827 /** Fit the plane between the two lines so that the plane has equal shortest 828 distance to both lines. 829 */ 830 Plane3 ChooseCandidatePlane3(const BoundedRayContainer &rays) const; 831 832 /** Selects the split plane in order to construct a tree with 833 certain characteristics (e.g., balanced tree, least splits, 834 2.5d aligned) 835 @param polygons container of polygons 836 @param rays bundle of rays on which the split can be based 837 */ 838 Plane3 SelectPlaneHeuristics(BspLeaf *leaf, 839 BspTraversalData &data); 840 841 /** Extracts the meshes of the objects and adds them to polygons. 842 Adds object aabb to the aabb of the tree. 843 @param maxPolys the maximal number of objects to be stored as polygons 844 @returns the number of polygons 845 */ 846 int AddToPolygonSoup(const ObjectContainer &objects, 847 PolygonContainer &polys, 848 int maxObjects = 0, 849 bool addToBbox = true); 850 851 /** Extracts the meshes of the view cells and and adds them to polygons. 852 Adds view cell aabb to the aabb of the tree. 853 @param maxPolys the maximal number of objects to be stored as polygons 854 @returns the number of polygons 855 */ 856 int AddToPolygonSoup(const ViewCellContainer &viewCells, 857 PolygonContainer &polys, 858 int maxObjects = 0); 859 860 /** Extract polygons of this mesh and add to polygon container. 861 @param mesh the mesh that drives the polygon construction 862 @param parent the parent intersectable this polygon is constructed from 863 @returns number of polygons 864 */ 865 int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent); 866 867 /** Helper function which extracts a view cell on the front and the back 868 of the split plane. 869 @param backViewCell returns view cell on the back of the split plane 870 @param frontViewCell returns a view cell on the front of the split plane 871 @param coincident container of polygons coincident to the split plane 872 @param splitPlane the split plane which decides about back and front 873 @param extractBack if a back view cell is extracted 874 @param extractFront if a front view cell is extracted 875 */ 876 void ExtractViewCells(BspTraversalData &frontData, 877 BspTraversalData &backData, 878 const PolygonContainer &coincident, 879 const Plane3 &splitPlane) const; 880 881 /** Computes best cost ratio for the suface area heuristics for axis aligned 882 splits. This heuristics minimizes the cost for ray traversal. 883 @param polys the polygons guiding the ratio computation 884 @param box the bounding box of the leaf 885 @param axis the current split axis 886 @param position returns the split position 887 @param objectsBack the number of objects in the back of the split plane 888 @param objectsFront the number of objects in the front of the split plane 889 */ 890 float BestCostRatio(const PolygonContainer &polys, 891 const AxisAlignedBox3 &box, 892 const int axis, 893 float &position, 894 int &objectsBack, 895 int &objectsFront) const; 896 897 /** Sorts split candidates for cost heuristics using axis aligned splits. 898 @param polys the input for choosing split candidates 899 @param axis the current split axis 900 @param splitCandidates returns sorted list of split candidates 901 */ 902 void SortSubdivisionCandidates(const PolygonContainer &polys, 903 const int axis, 904 vector<SortableEntry> &splitCandidates) const; 905 906 /** Selects an axis aligned split plane. 907 Returns true if split is valied 908 */ 909 bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const; 910 911 /** Subdivides the rays into front and back rays according to the split plane. 912 913 @param plane the split plane 914 @param rays contains the rays to be split. The rays are 915 distributed into front and back rays. 916 @param frontRays returns rays on the front side of the plane 917 @param backRays returns rays on the back side of the plane 918 919 @returns the number of splits 920 */ 921 int SplitRays(const Plane3 &plane, 922 BoundedRayContainer &rays, 923 BoundedRayContainer &frontRays, 924 BoundedRayContainer &backRays); 925 926 927 /** Extracts the split planes representing the space bounded by node n. 928 */ 929 void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const; 930 931 /** Adds the object to the pvs of the front and back leaf with a given classification. 932 933 @param obj the object to be added 934 @param cf the ray classification regarding the split plane 935 @param frontPvs returns the PVS of the front partition 936 @param backPvs returns the PVS of the back partition 937 938 */ 939 void AddObjToPvs(Intersectable *obj, const int cf, int &frontPvs, int &backPvs) const; 940 941 /** Computes PVS size induced by the rays. 942 */ 943 int ComputePvsSize(const BoundedRayContainer &rays) const; 944 945 /** Returns true if tree can be terminated. 946 */ 947 inline bool TerminationCriteriaMet(const BspTraversalData &data) const; 948 949 /** Computes accumulated ray lenght of this rays. 950 */ 951 float AccumulatedRayLength(BoundedRayContainer &rays) const; 952 953 /** Splits polygons with respect to the split plane. 954 @param polys the polygons to be split. the polygons are consumed and 955 distributed to the containers frontPolys, backPolys, coincident. 956 @param frontPolys returns the polygons in the front of the split plane 957 @param backPolys returns the polygons in the back of the split plane 958 @param coincident returns the polygons coincident to the split plane 959 960 @returns the number of splits 961 */ 962 int SplitPolygons(const Plane3 &plane, 963 PolygonContainer &polys, 964 PolygonContainer &frontPolys, 965 PolygonContainer &backPolys, 966 PolygonContainer &coincident) const; 967 968 /** Adds ray sample contributions to the PVS. 969 @param sampleContributions the number contributions of the samples 970 @param contributingSampels the number of contributing rays 971 972 */ 973 void AddToPvs(BspLeaf *leaf, 974 const BoundedRayContainer &rays, 975 int &sampleContributions, 976 int &contributingSamples); 977 978 /** Preprocesses polygons and throws out all polygons which 979 are coincident to the view space box faces: 980 These polygons can can be problematic for bsp because they create 981 bad view cells. 982 */ 983 void PreprocessPolygons(PolygonContainer &polys); 984 985 986 /////////////////////////////////// 987 988 /// Pointer to the root of the tree. 989 BspNode *mRoot; 990 991 /// Stores statistics during traversal. 992 BspTreeStatistics mStat; 993 1001 994 /// box around the whole view domain 1002 AxisAlignedBox3 mB ox;995 AxisAlignedBox3 mBbox; 1003 996 1004 997 /// view cell corresponding to unbounded space … … 1006 999 1007 1000 /// if view cells should be generated or the given view cells should be used. 1008 bool m GenerateViewCells;1001 bool mUsePredefinedViewCells; 1009 1002 1010 1003 /// maximal number of polygons before subdivision termination … … 1076 1069 ofstream mSubdivisionStats; 1077 1070 1071 ViewCellsTree *mViewCellsTree; 1072 1073 bool mOutOfBoundsCellPartOfTree; 1078 1074 private: 1079 1075
Note: See TracChangeset
for help on using the changeset viewer.
