Ignore:
Timestamp:
01/04/06 10:02:28 (19 years ago)
Author:
mattausch
Message:

fixed bug in tree collapse

Location:
trunk/VUT/GtpVisibilityPreprocessor/src
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r492 r495  
    13401340        } 
    13411341         
    1342         // choose candidate planes extracted from rays 
     1342        //-- choose candidate planes extracted from rays 
    13431343        for (int i = 0; i < mMaxRayCandidates; ++ i) 
    13441344        { 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

    r492 r495  
    13871387 
    13881388        // collapse siblings belonging to the same view cell 
    1389         mVspKdTree->CollapseTree(mVspKdTree->GetRoot()); 
    1390          
     1389        mVspKdTree->CollapseTree(); 
     1390 
    13911391        // collapse siblings belonging to the same view cell 
    13921392        mVspKdTree->RefineViewCells(rays); 
     
    17631763        // collapse invalid regions 
    17641764        cout << "collapsing invalid tree regions ... "; 
    1765         mVspBspTree->CollapseTree(mVspBspTree->GetRoot());  
    1766         cout << "finished" << endl; 
     1765        long startTime = GetTime(); 
     1766        mVspBspTree->CollapseTree();  
     1767        Debug << "tree collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 << " seconds" << endl; 
     1768    cout << "finished" << endl; 
     1769         
    17671770        cout << "reseting view cell stats ... "; 
    17681771        ResetViewCells(); 
     
    17821785                        ExportViewCells(exporter); 
    17831786 
    1784                         //if (mExportRays) 
    1785                         //      exporter->ExportRays(postProcessRays, RgbColor(1, 1, 0)); 
     1787                        if (0 && mExportRays) 
     1788                                exporter->ExportRays(rays, RgbColor(1, 1, 1)); 
    17861789                         
    17871790                        if (mExportGeometry) 
     
    17931796        } 
    17941797 
    1795         long startTime = GetTime(); 
     1798        startTime = GetTime(); 
    17961799        cout << "Computing remaining ray contributions ... "; 
    17971800        // recast rest of rays 
     
    19421945         
    19431946        // collapse sibling leaves that share the same view cell 
    1944         mVspBspTree->CollapseTree(mVspBspTree->GetRoot()); 
     1947        mVspBspTree->CollapseTree(); 
     1948 
    19451949        // reset view cells and stats 
    19461950        ResetViewCells(); 
     
    21322136                //-- export rays piercing this view cell 
    21332137#if 1 
    2134                 exporter->ExportRays(vcRays, RgbColor(0, 1, 0)); 
     2138                exporter->ExportRays(vcRays, RgbColor(1, 1, 1)); 
    21352139#endif 
    21362140#if 0 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

    r492 r495  
    3535float BspMergeCandidate::sOverallCost = 0; 
    3636 
    37  
    38 /// Adds object to the pvs of the front and back node 
    39 inline void AddObject2Pvs(Intersectable *object, 
    40                                                   const int side, 
    41                                                   int &pvsBack, 
    42                                                   int &pvsFront) 
    43 { 
    44         if (!object) 
    45                 return; 
    46  
    47         if (side <= 0) 
    48         { 
    49                 if (!object->Mailed() && !object->Mailed(2)) 
    50                 { 
    51                         ++ pvsBack; 
    52  
    53                         if (object->Mailed(1)) 
    54                                 object->Mail(2); 
    55                         else 
    56                                 object->Mail(); 
    57                 } 
    58         } 
    59  
    60         if (side >= 0) 
    61         { 
    62                 if (!object->Mailed(1) && !object->Mailed(2)) 
    63                 { 
    64                         ++ pvsFront; 
    65  
    66                         if (object->Mailed()) 
    67                                 object->Mail(2); 
    68                         else 
    69                                 object->Mail(1); 
    70                 } 
    71         } 
    72 } 
    73  
    74  
    7537/****************************************************************/ 
    7638/*                  class VspBspTree implementation             */ 
     
    8345mViewCellsManager(NULL), 
    8446mStoreRays(false), 
    85 mOnlyDrivingAxis(false), 
    8647mOutOfBoundsCell(NULL) 
    8748{ 
     
    794755float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane, 
    795756                                                                                 const VspBspTraversalData &tData, 
    796                                                                                  int &bestAxis) 
     757                                                                                 int &axis, 
     758                                                                                 float &position, 
     759                                                                                 int &raysBack, 
     760                                                                                 int &raysFront, 
     761                                                                                 int &pvsBack, 
     762                                                                                 int &pvsFront) 
    797763{ 
    798764        AxisAlignedBox3 box; 
     
    810776        float nPosition[3]; 
    811777        float nCostRatio[3]; 
    812         bestAxis = -1; 
     778        int bestAxis = -1; 
    813779 
    814780        const int sAxis = box.Size().DrivingAxis(); 
    815781 
    816         for (int axis = 0; axis < 3; ++ axis) 
     782        for (axis = 0; axis < 3; ++ axis) 
    817783        { 
    818784                if (!mOnlyDrivingAxis || axis == sAxis) 
     
    851817        } 
    852818 
    853         //-- assign best axis 
     819        //-- assign values 
     820        axis = bestAxis; 
     821        position = nPosition[bestAxis]; 
     822 
     823        raysBack = 0;//nRaysBack[bestAxis]; 
     824        raysFront = 0;//nRaysFront[bestAxis]; 
     825 
     826        pvsBack = 0;//nPvsBack[bestAxis]; 
     827        pvsFront = 0;//nPvsFront[bestAxis]; 
     828 
    854829        Vector3 normal(0,0,0); normal[bestAxis] = 1; 
    855830        plane = Plane3(normal, nPosition[bestAxis]); 
     
    10701045} 
    10711046 
     1047 
    10721048bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane, 
    10731049                                                                           BspLeaf *leaf, 
     
    10861062        for (int i = 0; i < limit; ++ i) 
    10871063        { 
    1088                 // assure that no index is taken twice 
     1064                //-- assure that no index is taken twice 
    10891065                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx)); 
    1090                 //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl; 
    1091  
    10921066                Polygon3 *poly = (*data.mPolygons)[candidateIdx]; 
    10931067 
     
    11091083        //-- axis aligned splits 
    11101084        int axis; 
    1111         candidateCost = SelectAxisAlignedPlane(plane, data, axis); 
     1085        float position; 
     1086        int raysBack; 
     1087        int raysFront; 
     1088        int pvsFront; 
     1089        int pvsBack; 
     1090 
     1091        candidateCost = SelectAxisAlignedPlane(plane,  
     1092                                                                                   data,  
     1093                                                                                   axis, 
     1094                                                                                   position, 
     1095                                                                                   raysBack, 
     1096                                                                                   raysFront, 
     1097                                                                                   pvsFront, 
     1098                                                                                   pvsBack); 
    11121099 
    11131100        if (candidateCost < lowestCost) 
     
    11161103                { 
    11171104                        useAxisAlignedPlane = true; 
     1105                        //if (data.mPolygons->size() > 0) 
     1106                        //      Debug << "haha" << endl; 
    11181107                        //! error also computed if cost ratio is missed 
    11191108                        ++ mStat.splits[axis]; 
     
    11421131        Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId; 
    11431132} 
     1133 
    11441134 
    11451135float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
     
    11591149        float pBack = 0; 
    11601150 
    1161         const bool pvsUseLen = false; 
    1162  
    11631151        if (mSplitPlaneStrategy & PVS) 
    11641152        { 
    1165 // matt: change back!! 
    1166 Intersectable::NewMail(3); 
    11671153                // create unique ids for pvs heuristics 
    1168                 //GenerateUniqueIdsForPvs(); 
     1154                GenerateUniqueIdsForPvs(); 
    11691155 
    11701156                if (mPvsUseArea) // use front and back cell areas to approximate volume 
     
    12271213                        // assure that we only count the object 
    12281214                        // once for the front and once for the back side of the plane 
    1229  
    1230                         // add the termination object 
    1231                         //AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs); 
    1232                         AddObject2Pvs(ray->mTerminationObject, cf, frontPvs, backPvs); 
    1233                         // add the source object 
    1234                         //AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs); 
     1215                        AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs); 
     1216                        AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs); 
    12351217 
    12361218                        // use number of rays to approximate volume 
    12371219                        if (!mPvsUseArea) 
    12381220                        { 
    1239                                 ++ pOverall; 
     1221                                pOverall = (float)data.mRays->size(); 
    12401222 
    12411223                                if (cf >= 0) 
     
    12531235 
    12541236        if (mSplitPlaneStrategy & BALANCED_RAYS) 
    1255                 cost += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize; 
     1237                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize; 
    12561238 
    12571239        // pvs criterium 
     
    21252107BspNode *VspBspTree::CollapseTree(BspNode *node) 
    21262108{ 
    2127     if (node->IsLeaf()) 
     2109        if (node->IsLeaf()) 
    21282110                return node; 
    21292111 
     
    21562138        } 
    21572139 
     2140        return node; 
     2141} 
     2142 
     2143 
     2144void VspBspTree::CollapseTree() 
     2145{ 
     2146        CollapseTree(mRoot); 
    21582147        // revalidate leaves 
    21592148        RepairVcLeafLists(); 
    2160  
    2161         return node; 
    21622149} 
    21632150 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

    r492 r495  
    257257        int RefineViewCells(const VssRayContainer &rays); 
    258258 
    259         /** Collapses the tree with respect to the view cell partition, 
    260                 i.e. leaves having the same view cell are collapsed. 
    261                 @returns node of type leaf if the node could be collapsed,  
    262                 this node otherwise 
    263         */ 
    264         BspNode *CollapseTree(BspNode *node); 
     259        /** Collapses the tree with respect to the view cell partition. 
     260        */ 
     261        void CollapseTree(); 
    265262 
    266263  ViewCell * 
     
    315312        }; 
    316313 
     314        /** Collapses the tree with respect to the view cell partition, 
     315                i.e. leaves having the same view cell are collapsed. 
     316                @returns node of type leaf if the node could be collapsed,  
     317                this node otherwise 
     318        */ 
     319        BspNode *CollapseTree(BspNode *node); 
    317320        /** Shuffles the leaves, i.e., tests if exchanging 
    318321                the leaves helps in improving the view cells. 
     
    421424        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent); 
    422425 
    423         /** Selects a plane axis aligned. 
     426        /** Selects an axis aligned for the next split. 
     427                @returns cost for this split 
    424428        */ 
    425429        float SelectAxisAlignedPlane(Plane3 &plane,  
    426430                                                                 const VspBspTraversalData &tData, 
    427                                                                  int &bestAxis); 
     431                                                                 int &axis, 
     432                                                                 float &position, 
     433                                                                 int &raysBack, 
     434                                                                 int &raysFront, 
     435                                                                 int &pvsBack, 
     436                                                                 int &pvsFront); 
    428437 
    429438        /** Sorts split candidates for surface area heuristics for axis aligned splits. 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

    r491 r495  
    188188                                         const int maxCostMisses): 
    189189VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL), 
    190 mMaxCostMisses(maxCostMisses) 
     190mMaxCostMisses(maxCostMisses), mPvs(NULL), mVolume(0) 
    191191{ 
    192192        mRays.reserve(nRays); 
     
    195195VspKdLeaf::~VspKdLeaf() 
    196196{ 
     197        DEL_PTR(mPvs); 
    197198} 
    198199 
     
    785786        if (1) //-- area substitute for probability 
    786787        { 
    787                  
     788                pOverall = box.SurfaceArea(); 
     789 
    788790                const bool useMidSplit = true; 
    789                 //const bool useMidSplit = false; 
    790                          
    791                 pOverall = box.SurfaceArea(); 
    792                          
     791                //const bool useMidSplit = false;        
     792                                         
    793793                if (!useMidSplit) 
    794794                { 
     
    892892        pvsFront = nPvsFront[bestAxis]; 
    893893 
     894        if (bestAxis == 1) 
     895                Debug << "y axis!" << endl; 
    894896        return nCostRatio[bestAxis]; 
    895897} 
     
    18871889        RayInfoContainer::const_iterator it, it_end = globalRays.end(); 
    18881890 
    1889         // TODO 
     1891        Intersectable::NewMail(); 
    18901892 
    18911893        // warning: implicit conversion from VssRay to Ray 
    18921894        for (it = globalRays.begin(); it != globalRays.end(); ++ it) 
    1893                 pvsSize += box.GetMinMaxT(*(*it).mRay, NULL, NULL); 
    1894  
     1895        { 
     1896                VssRay *ray = (*it).mRay; 
     1897 
     1898                // ray intersects node bounding box 
     1899                if (box.GetMinMaxT(*ray, NULL, NULL)) 
     1900                { 
     1901                        if (ray->mTerminationObject && !ray->mTerminationObject->Mailed()) 
     1902                        { 
     1903                                ray->mTerminationObject->Mail(); 
     1904                                ++ pvsSize; 
     1905                        } 
     1906                } 
     1907        } 
    18951908        return pvsSize; 
    18961909} 
     
    23452358        } 
    23462359 
     2360        return node; 
     2361} 
     2362 
     2363 
     2364void VspKdTree::CollapseTree() 
     2365{ 
     2366        CollapseTree(mRoot); 
    23472367        // revalidate leaves 
    23482368        RepairVcLeafLists(); 
    2349  
    2350         return node; 
    2351 } 
    2352  
     2369} 
    23532370 
    23542371int VspKdTree::RefineViewCells(const VssRayContainer &rays) 
     
    23792396                const bool wasShuffled = false; 
    23802397                        //ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2()); 
    2381                  
     2398                        // matt: restore 
    23822399                //-- stats 
    23832400                if (wasShuffled) 
     
    24032420float GetShuffledVcCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2) 
    24042421{ 
    2405 #if 0 // TODO 
    24062422        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs); 
    24072423        const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs); 
    24082424 
    2409         const float area1 = vc1->GetArea() - leaf->mArea; 
    2410         const float area2 = vc2->GetArea() + leaf->mArea; 
    2411  
    2412         const float cost1 = pvs1 * area1; 
    2413         const float cost2 = pvs2 * area2; 
     2425        const float vol1 = vc1->GetVolume() - leaf->mVolume; 
     2426        const float vol2 = vc2->GetVolume() + leaf->mVolume; 
     2427 
     2428        const float cost1 = pvs1 * vol1; 
     2429        const float cost2 = pvs2 * vol2; 
    24142430 
    24152431        return cost1 + cost2; 
    2416 #else 
    2417         return -1; 
    2418 #endif 
    24192432} 
    24202433 
     
    24242437                                                        VspKdViewCell *vc2) const 
    24252438{ 
    2426 #if 0 // TODO 
    24272439        // compute new pvs and area 
    24282440        vc1->GetPvs().SubtractPvs(*leaf->mPvs); 
    24292441        vc2->GetPvs().AddPvs(*leaf->mPvs); 
    24302442         
    2431         vc1->SetArea(vc1->GetArea() - leaf->mArea); 
    2432         vc2->SetArea(vc2->GetArea() + leaf->mArea); 
     2443        vc1->SetArea(vc1->GetVolume() - leaf->mVolume); 
     2444        vc2->SetArea(vc2->GetVolume() + leaf->mVolume); 
    24332445 
    24342446        /// add to second view cell 
     
    24422454 
    24432455        leaf->SetViewCell(vc2);  // finally change view cell 
    2444 #endif 
    24452456} 
    24462457 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

    r486 r495  
    390390         
    391391        static void NewMail(); 
    392  
    393392        static int sMailId; 
    394393 
    395          
     394        ObjectPvs *mPvs; 
     395        float mVolume; 
     396 
    396397protected: 
    397398 
     
    616617 
    617618        /** Collapses the tree with respect to the view cell partition. 
    618                 @returns node of type leaf if the node could be collapsed, this node otherwise 
     619        */ 
     620        void CollapseTree(); 
     621 
     622protected: 
     623 
     624        /** Collapses the tree with respect to the view cell partition. 
     625                @returns node of type leaf if the node could be collapsed,  
     626                this node otherwise 
    619627        */ 
    620628        VspKdNode *CollapseTree(VspKdNode *node); 
    621  
    622 protected: 
    623  
    624629        // incremental construction 
    625630        virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add); 
Note: See TracChangeset for help on using the changeset viewer.