Ignore:
Timestamp:
12/22/05 18:32:39 (19 years ago)
Author:
mattausch
Message:
 
File:
1 edited

Legend:

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

    r475 r478  
     1#include <stack> 
     2#include <time.h> 
     3#include <iomanip> 
     4 
    15#include "Plane3.h" 
    26#include "VspBspTree.h" 
     
    812#include "Ray.h" 
    913#include "AxisAlignedBox3.h" 
    10 #include <stack> 
    11 #include <time.h> 
    12 #include <iomanip> 
    1314#include "Exporter.h" 
    1415#include "Plane3.h" 
    1516#include "ViewCellBsp.h" 
     17#include "ViewCellsManager.h" 
     18 
    1619 
    1720//-- static members 
     
    3033int VspBspTree::sFrontAndBackId = 0; 
    3134 
     35float BspMergeCandidate::sOverallCost = Limits::Small; 
    3236 
    3337/****************************************************************/ 
     
    3842mRoot(NULL), 
    3943mPvsUseArea(true), 
    40 mCostNormalizer(Limits::Small) 
     44mCostNormalizer(Limits::Small), 
     45mViewCellsManager(NULL), 
     46mStoreRays(true) 
    4147{ 
    4248        mRootCell = new BspViewCell(); 
     
    7581        environment->GetIntValue("VspBspTree.maxTests", mMaxTests); 
    7682 
    77         // maximum number of view cells 
    78         environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 
    79  
    80         //-- 
     83        // maximum and minimum number of view cells 
     84        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells); 
     85        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells); 
     86        environment->GetIntValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 
     87 
     88 
     89        //-- debug output 
    8190        Debug << "******* VSP BSP options ******** " << endl; 
    8291    Debug << "max depth: " << mTermMaxDepth << endl; 
     
    313322        long startTime = GetTime(); 
    314323         
    315         while (!tStack.empty())  
     324        while (!tStack.empty()) 
    316325        { 
    317326                tData = tStack.top(); 
    318327 
    319328            tStack.pop(); 
     329 
    320330                // subdivide leaf node 
    321331                BspNode *r = Subdivide(tStack, tData); 
     
    331341} 
    332342 
    333 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data,  
    334                                                                                 const int numLeaves) const 
     343bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const 
    335344{ 
    336345        return  
     
    338347                 (data.mPvs <= mTermMinPvs)   || 
    339348                 (data.mArea <= mTermMinArea) || 
    340                  ((mStat.nodes / 2 + 1) >= mMaxViewCells) || 
     349                 (mStat.nodes / 2 + 1 >= mMaxViewCells) || 
    341350                // (data.GetAvgRayContribution() >= mTermMaxRayContribution) || 
    342351                 (data.mDepth >= mTermMaxDepth)); 
     
    348357        BspNode *newNode = tData.mNode; 
    349358 
    350         if (!TerminationCriteriaMet(tData, (int)tStack.size())) 
     359        if (!TerminationCriteriaMet(tData)) 
    351360        { 
    352361                PolygonContainer coincident; 
     
    370379        } 
    371380         
    372         //-- terminate traversal   
     381        //-- terminate traversal and create new view cell 
    373382        if (newNode->IsLeaf()) 
    374383        { 
     
    378387                BspViewCell *viewCell = new BspViewCell(); 
    379388                leaf->SetViewCell(viewCell); 
     389                 
     390                if (mStoreRays) 
     391                { 
     392                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end(); 
     393                        for (it = tData.mRays->begin(); it != it_end; ++ it) 
     394                                leaf->mVssRays.push_back((*it).mRay); 
     395                } 
     396 
    380397                viewCell->mLeaves.push_back(leaf); 
     398                viewCell->SetArea(tData.mArea); 
    381399 
    382400                //-- update pvs 
     
    392410                 
    393411        //-- cleanup 
    394         DEL_PTR(tData.mPolygons); 
    395         DEL_PTR(tData.mRays); 
    396         DEL_PTR(tData.mGeometry); 
     412        tData.Clear(); 
    397413 
    398414        return newNode; 
     
    18721888        return hits; 
    18731889} 
     1890 
     1891int VspBspTree::MergeLeaves() 
     1892{ 
     1893        vector<BspLeaf *> leaves; 
     1894        priority_queue<BspMergeCandidate> mergeQueue; 
     1895 
     1896        // collect the leaves, e.g., the "voxels" that will build the view cells 
     1897        CollectLeaves(leaves); 
     1898 
     1899        int vcSize = (int)leaves.size(); 
     1900        int savedVcSize = vcSize; 
     1901 
     1902        BspLeaf::NewMail(); 
     1903 
     1904        vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 
     1905 
     1906        // find merge candidates and push them into queue 
     1907        for (it = leaves.begin(); it != it_end; ++ it) 
     1908        { 
     1909                BspLeaf *leaf = *it; 
     1910 
     1911                // no leaf is part of two merge candidates 
     1912                if (!leaf->Mailed()) 
     1913                { 
     1914                        leaf->Mail(); 
     1915 
     1916                        vector<BspLeaf *> neighbors; 
     1917                        FindNeighbors(leaf, neighbors, true); 
     1918 
     1919                        vector<BspLeaf *>::const_iterator nit, 
     1920                                nit_end = neighbors.end(); 
     1921 
     1922                        for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
     1923                        { 
     1924                                BspMergeCandidate mc = BspMergeCandidate(leaf, *nit); 
     1925                                mergeQueue.push(mc); 
     1926 
     1927                                BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost(); 
     1928                                BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost(); 
     1929                        } 
     1930                } 
     1931        } 
     1932 
     1933        int merged = 0; 
     1934 
     1935        Debug << "here234: " << mMergeMaxCostRatio << endl; 
     1936 
     1937        // use priority queue to merge leaves 
     1938        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) )//&& 
     1939                   //(mergeQueue.top().GetMergeCost() <  
     1940                    //mMergeMaxCostRatio / BspMergeCandidate::sOverallCost)) 
     1941        { 
     1942                Debug << "mergecost: " << mergeQueue.top().GetMergeCost() << " " << mMergeMaxCostRatio << endl; 
     1943                BspMergeCandidate mc = mergeQueue.top(); 
     1944                mergeQueue.pop(); 
     1945 
     1946                // both view cells equal! 
     1947                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) 
     1948                        continue; 
     1949 
     1950                if (mc.Valid()) 
     1951                { 
     1952                        ViewCell::NewMail(); 
     1953                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 
     1954 
     1955                        ++ merged; 
     1956                        -- vcSize; 
     1957                        // increase absolute merge cost 
     1958                        BspMergeCandidate::sOverallCost += mc.GetMergeCost(); 
     1959                } 
     1960                // merge candidate not valid, because one of the leaves was already 
     1961                // merged with another one 
     1962                else 
     1963                { 
     1964                        // validate and reinsert into queue 
     1965                        mc.SetValid(); 
     1966                        mergeQueue.push(mc); 
     1967                        //Debug << "validate " << mc.GetMergeCost() << endl; 
     1968                } 
     1969        } 
     1970 
     1971        // collapse tree according to view cell partition 
     1972        //CollapseTree(mRoot); 
     1973 
     1974        // revalidate leaves 
     1975        //ValidateViewCellLeaves(); 
     1976 
     1977        //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl; 
     1978 
     1979        //TODO: should return sample contributions 
     1980        return merged; 
     1981} 
     1982 
     1983 
     1984bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) 
     1985{ 
     1986        //-- change pointer to view cells of all leaves associated  
     1987        //-- with the previous view cells 
     1988        BspViewCell *fVc = l1->GetViewCell(); 
     1989        BspViewCell *bVc = l2->GetViewCell(); 
     1990 
     1991        BspViewCell *vc = dynamic_cast<BspViewCell *>( 
     1992                mViewCellsManager->MergeViewCells(*fVc, *bVc)); 
     1993 
     1994        // if merge was unsuccessful 
     1995        if (!vc) return false; 
     1996 
     1997        // set new size of view cell 
     1998        vc->SetArea(fVc->GetVolume() + bVc->GetVolume()); 
     1999 
     2000        vector<BspLeaf *> fLeaves = fVc->mLeaves; 
     2001        vector<BspLeaf *> bLeaves = bVc->mLeaves; 
     2002 
     2003        vector<BspLeaf *>::const_iterator it; 
     2004 
     2005        //-- change view cells of all the other leaves the view cell belongs to 
     2006        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it) 
     2007        { 
     2008                (*it)->SetViewCell(vc); 
     2009                vc->mLeaves.push_back(*it); 
     2010        } 
     2011 
     2012        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it) 
     2013        { 
     2014                (*it)->SetViewCell(vc); 
     2015                vc->mLeaves.push_back(*it); 
     2016        } 
     2017 
     2018        vc->Mail(); 
     2019 
     2020        // clean up old view cells 
     2021        DEL_PTR(fVc); 
     2022        DEL_PTR(bVc); 
     2023 
     2024        return true; 
     2025} 
     2026 
     2027 
     2028void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm) 
     2029{ 
     2030        mViewCellsManager = vcm; 
     2031} 
     2032 
     2033/************************************************************************/ 
     2034/*                BspMergeCandidate implementation                      */ 
     2035/************************************************************************/ 
     2036 
     2037 
     2038BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2): 
     2039mMergeCost(0), 
     2040mLeaf1(l1), 
     2041mLeaf2(l2), 
     2042mLeaf1Id(l1->GetViewCell()->mMailbox), 
     2043mLeaf2Id(l2->GetViewCell()->mMailbox) 
     2044{ 
     2045        EvalMergeCost(); 
     2046} 
     2047 
     2048float BspMergeCandidate::GetLeaf1Cost() const 
     2049{ 
     2050        BspViewCell *vc = mLeaf1->GetViewCell(); 
     2051        return vc->GetPvs().GetSize() * vc->GetArea(); 
     2052} 
     2053 
     2054float BspMergeCandidate::GetLeaf2Cost() const 
     2055{ 
     2056        BspViewCell *vc = mLeaf2->GetViewCell(); 
     2057        return vc->GetPvs().GetSize() * vc->GetVolume(); 
     2058} 
     2059 
     2060void BspMergeCandidate::EvalMergeCost() 
     2061{ 
     2062        //-- compute pvs difference 
     2063        BspViewCell *vc1 = mLeaf1->GetViewCell(); 
     2064        BspViewCell *vc2 = mLeaf2->GetViewCell(); 
     2065 
     2066        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs()); 
     2067        const int vcPvs = diff1 + vc1->GetPvs().GetSize(); 
     2068 
     2069        //-- compute ratio of old cost 
     2070        //-- (added size of left and right view cell times pvs size) 
     2071        //-- to new rendering cost (size of merged view cell times pvs size) 
     2072        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost(); 
     2073         
     2074        const float newCost = 
     2075                (float)vcPvs * (vc1->GetArea() + vc2->GetArea()); 
     2076 
     2077        mMergeCost = newCost - oldCost; 
     2078 
     2079//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large 
     2080//              mMergeCost += 1.0; 
     2081} 
     2082 
     2083void BspMergeCandidate::SetLeaf1(BspLeaf *l) 
     2084{ 
     2085        mLeaf1 = l; 
     2086} 
     2087 
     2088void BspMergeCandidate::SetLeaf2(BspLeaf *l) 
     2089{ 
     2090        mLeaf2 = l; 
     2091} 
     2092 
     2093BspLeaf *BspMergeCandidate::GetLeaf1() 
     2094{ 
     2095        return mLeaf1; 
     2096} 
     2097 
     2098BspLeaf *BspMergeCandidate::GetLeaf2() 
     2099{ 
     2100        return mLeaf2; 
     2101} 
     2102 
     2103bool BspMergeCandidate::Valid() const 
     2104{ 
     2105        return 
     2106                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 
     2107                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id); 
     2108} 
     2109 
     2110float BspMergeCandidate::GetMergeCost() const 
     2111{ 
     2112        return mMergeCost; 
     2113} 
     2114 
     2115void BspMergeCandidate::SetValid() 
     2116{ 
     2117        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox; 
     2118        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox; 
     2119 
     2120        EvalMergeCost(); 
     2121} 
Note: See TracChangeset for help on using the changeset viewer.