Ignore:
Timestamp:
07/05/06 08:43:09 (18 years ago)
Author:
mattausch
Message:

wked on view space object space partition

Location:
GTP/trunk/Lib/Vis/Preprocessing/src
Files:
11 edited

Legend:

Unmodified
Added
Removed
  • GTP/trunk/Lib/Vis/Preprocessing/src/Environment.cpp

    r1027 r1074  
    19901990                                        optFloat, 
    19911991                                        "vsp_bsp_construction_min_band=", 
    1992                                         "0.1"); 
     1992                                        "0.01"); 
    19931993 
    19941994        RegisterOption("VspBspTree.Construction.maxBand", 
    19951995                                        optFloat, 
    19961996                                        "vsp_bsp_construction_min_band=", 
    1997                                         "0.9"); 
     1997                                        "0.99"); 
    19981998 
    19991999        RegisterOption("VspBspTree.Construction.useDrivingAxisForMaxCost", 
     
    21202120                                        "0.001"); 
    21212121 
    2122          
    21232122        RegisterOption("VspTree.Termination.maxRayContribution", 
    21242123                        optFloat, 
     
    21472146                                        "0.0001"); 
    21482147 
    2149         RegisterOption("VspTree.useSplitCostQueue", 
    2150                 optBool, 
    2151                 "vsp_use_split_cost_queue=", 
    2152                 "true"); 
    2153  
    21542148        RegisterOption("VspTree.Termination.globalCostMissTolerance", 
    21552149                                        optInt, 
     
    22002194                                        optFloat, 
    22012195                                        "vsp_construction_min_band=", 
    2202                                         "0.1"); 
     2196                                        "0.01"); 
    22032197 
    22042198        RegisterOption("VspTree.Construction.maxBand", 
    22052199                                        optFloat, 
    2206                                         "vsp_construction_min_band=", 
    2207                                         "0.9"); 
     2200                                        "vsp_construction_max_band=", 
     2201                                        "0.99"); 
     2202 
     2203        RegisterOption("VspTree.pvsCountMethod", 
     2204                                        optInt, 
     2205                                        "vsp_pvs_count_method=", 
     2206                                        "1"); 
     2207 
    22082208 
    22092209        ////////////////////////////////////////////////////////////////////////////////// 
  • GTP/trunk/Lib/Vis/Preprocessing/src/Intersectable.h

    r1072 r1074  
    44#include "AxisAlignedBox3.h" 
    55#include "Pvs.h" 
     6#include <set> 
    67 
    78namespace GtpVisibilityPreprocessor { 
     
    2829   
    2930  /// kd leaves that this intersectable belongs to 
    30   std::vector<KdLeaf *> mKdLeaves; 
     31  set<KdLeaf *> mKdLeaves; 
    3132 
    3233  enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEW_CELL, OGRE_MESH_INSTANCE }; 
  • GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.cpp

    r1004 r1074  
    9090        mBox.Include((*mi)->GetBox()); 
    9191  } 
     92 
     93        ProcessLeafObjects(leaf, NULL); 
    9294 
    9395  cout <<"KdTree Root Box:"<<mBox<<endl; 
     
    281283  KdLeaf *front = new KdLeaf(node, objectsFront); 
    282284 
     285  
    283286  // replace a link from node's parent 
    284287  if (  leaf->mParent ) 
     
    304307  } 
    305308   
     309   ProcessLeafObjects(back, leaf); 
     310    ProcessLeafObjects(front, leaf); 
     311 
    306312  delete leaf; 
    307313  return node; 
     
    10871093} 
    10881094 
    1089 } 
     1095 
     1096void KdTree::ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const 
     1097{ 
     1098        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end(); 
     1099 
     1100        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit) 
     1101        { 
     1102                Intersectable *object = *oit; 
     1103 
     1104                if (parent) 
     1105                { 
     1106                        set<KdLeaf *>::iterator kdit = object->mKdLeaves.find(parent); 
     1107 
     1108                        // remove parent leaf 
     1109                        if (kdit != object->mKdLeaves.end()) 
     1110                                object->mKdLeaves.erase(kdit); 
     1111                } 
     1112 
     1113                object->mKdLeaves.insert(leaf); 
     1114 
     1115                if (object->mKdLeaves.size() > 1) 
     1116                        leaf->mMultipleObjects.push_back(object); 
     1117        } 
     1118} 
     1119 
     1120 
     1121} 
  • GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.h

    r1073 r1074  
    191191  /** Objects that are part of several leaves. 
    192192  */ 
    193   ObjectMap mMultipleObjects; 
     193  ObjectContainer mMultipleObjects; 
    194194 
    195195  /// universal counter 
     
    530530              ); 
    531531 
     532 
     533  /** does some post processing on the objects that are contained 
     534  in this leaf. 
     535  */ 
     536  void ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const; 
    532537 
    533538  int mTermMaxNodes; 
  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

    r1072 r1074  
    454454        bool dirSamples = (mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION); 
    455455 
    456         // -- the main loop 
     456        //-- do some more sampling 
    457457        while (numSamples < n) 
    458458        { 
     
    490490        } 
    491491 
    492          
    493492        //-- post processing 
    494493        VssRayContainer postProcessSamples; 
    495494 
    496         //-- construction rays  
     495        cout << "casting " << mPostProcessSamples << " post processing samples ... "; 
     496 
     497        // cast post processing samples rays  (storing the view cells if wanted) 
    497498        CastPassSamples(mPostProcessSamples, 
    498499                                        mSamplingType,  
    499500                                        postProcessSamples); 
    500501 
     502        cout << "finished" << endl; 
    501503 
    502504        // stats before post processing (i.e., merge) 
     
    542544 
    543545        //-- visualization 
     546 
    544547        if (mShowVisualization) 
    545548        { 
     
    17271730{ 
    17281731        mViewSpaceBox = box; 
    1729         Debug << "here111 " << mViewSpaceBox << endl; 
     1732         
    17301733        // hack: create clip plane relative to new view space box 
    17311734        CreateClipPlane(); 
     
    48534856        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size()); 
    48544857 
    4855         Debug << "here125 view space box " << mViewSpaceBox << endl; 
    4856  
    4857         // if view cells were already constructed 
     4858        // skip rest if view cells were already constructed 
    48584859        if (ViewCellsConstructed()) 
    48594860                return 0; 
     
    52775278 
    52785279        //-- export single view cells 
    5279         ExportBspPvs(objects, visRays); 
    5280 } 
    5281  
    5282  
    5283 void VspOspViewCellsManager::ExportBspPvs(const ObjectContainer &objects, 
    5284                                                                                   const VssRayContainer &rays) 
     5280        ExportPvs(objects, visRays); 
     5281} 
     5282 
     5283 
     5284void VspOspViewCellsManager::ExportPvs(const ObjectContainer &objects, 
     5285                                                                           const VssRayContainer &rays) 
    52855286{ 
    52865287        int leafOut; 
     
    53155316                if (sortViewCells) // largest view cell pvs first 
    53165317                        vc = mViewCells[i]; 
    5317                 else 
     5318                else // random view cell 
    53185319                        vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)]; 
    53195320 
     
    53285329 
    53295330                //-- export the sample rays 
    5330                 if (mExportRays) 
     5331                if (1 || mExportRays) 
    53315332                { 
    53325333                        // output rays stored with the view cells during subdivision 
     
    54085409 
    54095410 
    5410                 //-- export pvs 
    54115411                if (1) 
    5412                 { 
     5412                {       //-- export pvs 
    54135413                        ObjectPvsMap::const_iterator oit, 
    54145414                                oit_end = pvs.mEntries.end(); 
     
    54165416                        Intersectable::NewMail(); 
    54175417 
    5418                         // output PVS of view cell 
     5418                        vector<KdLeaf *> kdLeaves; 
     5419 
     5420                        KdLeaf::NewMail(); 
     5421 
     5422                        m.mDiffuseColor = RgbColor(1, 0, 0); 
     5423                        exporter->SetForcedMaterial(m); 
     5424 
     5425                        // find kd nodes 
    54195426                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit) 
    5420                         {                
    5421                                 Intersectable *intersect = (*oit).first; 
    5422  
    5423                                 if (!intersect->Mailed()) 
     5427                        {        
     5428                                // "original" pvs 
     5429                                Intersectable *obj = (*oit).first; 
     5430 
     5431                                if (1 && !obj->Mailed()) 
    54245432                                { 
    5425                                         m = RandomMaterial(); 
    5426                                         exporter->SetForcedMaterial(m); 
    5427  
    5428                                         exporter->ExportIntersectable(intersect); 
    5429                                         intersect->Mail(); 
     5433                                        exporter->ExportIntersectable(obj); 
     5434                                        obj->Mail(); 
     5435                                }                                        
     5436 
     5437                                // collect kd leaves 
     5438                                set<KdLeaf *>::const_iterator kdit, kdit_end = obj->mKdLeaves.end(); 
     5439 
     5440                                for (kdit = obj->mKdLeaves.begin(); kdit != kdit_end; ++ kdit) 
     5441                                { 
     5442                                        KdLeaf *kdleaf = *kdit; 
     5443 
     5444                                        if (!kdleaf->Mailed()) 
     5445                                        { 
     5446                                                kdleaf->Mail(); 
     5447                                                kdLeaves.push_back(kdleaf); 
     5448                                        } 
    54305449                                } 
    54315450                        } 
    5432                 } 
    5433                  
    5434                 if (0) 
    5435                 {   // export scene geometry 
    5436                         m.mDiffuseColor = RgbColor(1, 0, 0); 
     5451 
     5452                        m.mDiffuseColor = RgbColor(0, 0, 1); 
    54375453                        exporter->SetForcedMaterial(m); 
    54385454 
    5439                         exporter->ExportGeometry(objects); 
    5440                 } 
    5441  
     5455                        // export kd node pvs 
     5456                        Intersectable::NewMail(); 
     5457 
     5458                        vector<KdLeaf *>::const_iterator kdit, kdit_end = kdLeaves.end(); 
     5459 
     5460                        for (kdit = kdLeaves.begin(); kdit != kdit_end; ++ kdit) 
     5461                        { 
     5462                                KdLeaf *kdleaf = *kdit; 
     5463 
     5464                                //-- export kd node 
     5465                                /*exporter->SetWireframe(); 
     5466                                exporter->ExportBox(mKdTree->GetBox(kdleaf)); 
     5467                                exporter->SetFilled();*/ 
     5468 
     5469                                ObjectContainer::const_iterator oit, oit_end = kdleaf->mObjects.end(); 
     5470 
     5471                for (oit = kdleaf->mObjects.begin(); oit != oit_end; ++ oit) 
     5472                                {        
     5473                                        Intersectable *obj = *oit; 
     5474 
     5475                                        if (!obj->Mailed()) 
     5476                                        { 
     5477                                                exporter->ExportIntersectable(obj); 
     5478                                                obj->Mail();                                     
     5479                                        }                                
     5480                                } 
     5481                        } 
     5482                } 
     5483         
    54425484                DEL_PTR(exporter); 
    54435485                cout << "finished" << endl; 
  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h

    r1047 r1074  
    10011001        */ 
    10021002        void ExportViewCellGeometry(Exporter *exporter,  
    1003                                                                 ViewCell *vc, 
    1004                                                                 const AxisAlignedPlane *clipPlane = NULL) const; 
    1005  
    1006         int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const; 
     1003                ViewCell *vc, 
     1004                const AxisAlignedPlane *clipPlane = NULL) const; 
     1005 
     1006        int ComputeBoxIntersections(const AxisAlignedBox3 &box,  
     1007                ViewCellContainer &viewCells) const; 
    10071008         
    10081009        void CollectViewCells(); 
     
    10191020        void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs); 
    10201021 
    1021         /** Exports visualization of the BSP PVS. 
    1022         */ 
    1023         void ExportBspPvs(const ObjectContainer &objects, 
    1024                                           const VssRayContainer &rays); 
     1022        /** Exports visualization of the PVS. 
     1023        */ 
     1024        void ExportPvs(const ObjectContainer &objects, 
     1025                const VssRayContainer &rays); 
    10251026 
    10261027 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VrmlExporter.cpp

    r1052 r1074  
    101101  stream << "}" << endl; // end material 
    102102  stream << "}" << endl; // end appearance 
    103   Debug << "here8" << endl; 
     103  
    104104  stream << "geometry IndexedLineSet { coordIndex [" << endl; 
    105105 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp

    r1072 r1074  
    13211321         
    13221322        // the relative cost ratio 
    1323         float ratio = /*Limits::Infinity;*/99999999.0f; 
     1323        float ratio = 99999999.0f; 
    13241324        bool splitPlaneFound = false; 
    13251325 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

    r1073 r1074  
    274274{ 
    275275        DEL_PTR(mPvs); 
     276        CLEAR_CONTAINER(mVssRays); 
    276277} 
    277278 
     
    349350        Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance); 
    350351 
    351         // HACK//mTermMinPolygons = 25; 
    352  
    353352        //-- factors for bsp tree split plane heuristics 
    354353        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi); 
     
    366365        Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis); 
    367366         
     367        Environment::GetSingleton()->GetIntValue("VspTree.pvsCountMethod", mPvsCountMethod); 
    368368 
    369369        char subdivisionStatsLog[100]; 
     
    398398        Debug << "minband: " << mMinBand << endl; 
    399399        Debug << "maxband: " << mMaxBand << endl; 
     400        Debug << "pvs count method: " << mPvsCountMethod << endl; 
    400401         
    401402 
     
    650651        splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 
    651652 
    652         Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl; 
     653        //Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl; 
    653654} 
    654655 
     
    674675                          *backData.mRays); 
    675676 
    676         Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl; 
     677        //Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl; 
    677678        //-- compute pvs 
    678679        frontData.mPvs = ComputePvsSize(*frontData.mRays); 
     
    778779                 
    779780                // warning: rays get never deleted! 
    780                 if (0) leaf->mVssRays.push_back(new VssRay(*ray)); 
     781                if (1) leaf->mVssRays.push_back(new VssRay(*ray)); 
    781782        } 
    782783} 
     
    804805        float pos; 
    805806 
    806         if (0) 
    807         { 
    808                 // float values => don't compare with exact values 
    809                 minBand += Limits::Small; 
    810                 maxBand -= Limits::Small; 
    811         } 
    812  
    813807        // insert all queries 
    814808        for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri) 
     
    818812                pos = (*ri).ExtrapOrigin(axis); 
    819813                 
    820                 if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band 
    821814                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,  
    822815                                                                        pos, (*ri).mRay)); 
    823816 
    824817                pos = (*ri).ExtrapTermination(axis); 
    825  
    826                 if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band 
    827818 
    828819                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,  
     
    860851 
    861852 
    862 void VspTree::PrepareHeuristics(const RayInfoContainer &rays) 
     853int VspTree::PrepareHeuristics(Intersectable *object) 
     854{ 
     855        set<KdLeaf *>::const_iterator kit, kit_end = object->mKdLeaves.end(); 
     856         
     857        int pvsSize = 0; 
     858 
     859        for (kit = object->mKdLeaves.begin(); kit != kit_end; ++ kit) 
     860        { 
     861                KdLeaf *node = dynamic_cast<KdLeaf *>(*kit); 
     862 
     863                if (!node->Mailed()) 
     864                { 
     865                        node->Mail(); 
     866                        node->mCounter = 1; 
     867 
     868                        //Debug << "here5 "<<(int)node->mObjects.size() <<" "<< node->mMultipleObjects.size()<< " " <<(int)node->mObjects.size() - node->mMultipleObjects.size()<<endl; 
     869                        // add objects without the objects which are in several kd leaves 
     870                        pvsSize += (int)(node->mObjects.size() - node->mMultipleObjects.size()); 
     871                } 
     872                else 
     873                { 
     874                        ++ node->mCounter; 
     875                } 
     876 
     877                //-- the objects belonging to several leaves must be handled seperately 
     878                ObjectContainer::const_iterator oit, oit_end = node->mMultipleObjects.end(); 
     879 
     880                for (oit = node->mMultipleObjects.begin(); oit != oit_end; ++ oit) 
     881                { 
     882                        Intersectable *object = *oit; 
     883                                                 
     884                        if (!object->Mailed()) 
     885                        { 
     886                                //Debug << "here233: " << object->mKdLeaves.size() << endl; 
     887                                object->Mail(); 
     888                                object->mCounter = 1; 
     889 
     890                                ++ pvsSize; 
     891                        } 
     892                        else 
     893                        { 
     894                                ++ object->mCounter; 
     895                        } 
     896                } 
     897        } 
     898 
     899        return pvsSize; 
     900} 
     901 
     902 
     903int VspTree::PrepareHeuristics(const RayInfoContainer &rays) 
    863904{        
    864         ObjectContainer objects; 
    865  
    866         // Collect all pvs that can be seen from the view cell 
    867         CollectPvs(rays, objects); 
    868  
    869         // adjust kd node info table 
    870         // for each object the entry must be updated  
    871         // which belongs to the same kd nodes 
    872         ObjectContainer::const_iterator oit, oit_end = objects.end(); 
    873  
    874         for (oit = objects.begin(); oit != oit_end; ++ oit) 
    875         { 
    876                 Intersectable *obj = *oit; 
    877                 // TODO 
    878                 //UpdateKdNodeInfo(obj); 
    879         } 
     905        Intersectable::NewMail(); 
     906        KdNode::NewMail(); 
     907 
     908        int pvsSize = 0; 
     909 
     910        RayInfoContainer::const_iterator ri, ri_end = rays.end(); 
     911 
     912        //-- set all kd nodes as belonging to the front pvs 
     913 
     914        for (ri = rays.begin(); ri != ri_end; ++ ri) 
     915        { 
     916                Intersectable *oObject = (*ri).mRay->mOriginObject; 
     917 
     918                if (oObject) 
     919                { 
     920                        if (mPvsCountMethod == PER_OBJECT) 
     921                        { 
     922                                if (!oObject->Mailed()) 
     923                                { 
     924                                        oObject->Mail(); 
     925                                        oObject->mCounter = 1; 
     926                                        ++ pvsSize; 
     927                                } 
     928                                else 
     929                                { 
     930                                        ++ oObject->mCounter; 
     931                                } 
     932                        } 
     933                        else 
     934                        { 
     935                                pvsSize += PrepareHeuristics(oObject);   
     936                        }        
     937                } 
     938 
     939                Intersectable *tObject = (*ri).mRay->mTerminationObject; 
     940 
     941                if (tObject) 
     942                { 
     943                        if (mPvsCountMethod == PER_OBJECT) 
     944                        { 
     945                                if (!tObject->Mailed()) 
     946                                { 
     947                                        tObject->Mail(); 
     948                                        tObject->mCounter = 1; 
     949                                        ++ pvsSize; 
     950                                } 
     951                                else 
     952                                { 
     953                                        ++ tObject->mCounter; 
     954                                } 
     955                        } 
     956                        else 
     957                        { 
     958                                pvsSize += PrepareHeuristics(tObject);   
     959                        }        
     960                } 
     961        } 
     962 
     963        return pvsSize; 
    880964} 
    881965 
     
    910994float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays, 
    911995                                                                           const AxisAlignedBox3 &box, 
    912                                                                            const int pvsSize, 
     996                                                                           int pvsSize, 
    913997                                                                           const int axis, 
    914998                                                                           float &position) 
     
    9421026         
    9431027        // the relative cost ratio 
    944         float ratio = /*Limits::Infinity;*/99999999.0f; 
     1028        float ratio = 99999999.0f; 
    9451029        bool splitPlaneFound = false; 
    9461030 
     
    10611145        const float pFront = maxBox - position; 
    10621146 
    1063         /*const float pOverall = box.GetVolume(); 
    1064  
    1065         AxisAlignedBox3 bbox; 
    1066         AxisAlignedBox3 fbox; 
    1067  
    1068         box.Split(axis, position, bbox, fbox); 
    1069  
    1070         const float pBack = fbox.GetVolume(); 
    1071         const float pFront = bbox.GetVolume();*/ 
    1072  
     1147         
    10731148        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit); 
    10741149    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 
     
    10901165 
    10911166 
    1092 void VspTree::EvalPvsIncr(ObjectMap &multipleObjects, 
    1093                                                   KdLeaf *leaf,  
    1094                                                   const SortableEntry &ci, 
     1167void VspTree::RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const 
     1168{ 
     1169        // leaf falls out of right pvs 
     1170        if (-- leaf->mCounter == 0) 
     1171        { 
     1172                pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size()); 
     1173        } 
     1174 
     1175        //-- handle objects which are in several kd leaves separately  
     1176        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end(); 
     1177 
     1178        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit) 
     1179        { 
     1180                Intersectable *object = *oit; 
     1181 
     1182                if (-- object->mCounter == 0) 
     1183                { 
     1184                        -- pvs; 
     1185                } 
     1186        } 
     1187} 
     1188 
     1189 
     1190void VspTree::AddContriToPvs(KdLeaf *leaf, int &pvs) const 
     1191{ 
     1192        if (!leaf->Mailed()) 
     1193        { 
     1194                leaf->Mail(); 
     1195 
     1196                // add objects without objects which are part of several kd leaves 
     1197                pvs += ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size()); 
     1198 
     1199                //-- handle objects of several kd leaves separately 
     1200                ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end(); 
     1201 
     1202                for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit) 
     1203                { 
     1204                        Intersectable *object = *oit; 
     1205 
     1206                        // object not previously in left pvs 
     1207                        if (!object->Mailed()) 
     1208                        { 
     1209                                object->Mail(); 
     1210                                ++ pvs; 
     1211                        } 
     1212                } 
     1213        }                                        
     1214} 
     1215 
     1216 
     1217void VspTree::EvalPvsIncr(const SortableEntry &ci, 
    10951218                                                  int &pvsLeft, 
    10961219                                                  int &pvsRight) const 
    10971220{ 
    1098         int pvsSize = 0; 
    1099  
    1100         if (ci.type == SortableEntry::ERayMin) 
    1101         { 
    1102                 if (!leaf->Mailed()) 
    1103                 { 
    1104                         leaf->Mail(); 
    1105                         pvsLeft += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size(); 
    1106  
    1107                         // add duplicates 
    1108                         ObjectMap::const_iterator oit, oit_end = leaf->mMultipleObjects.end(); 
    1109  
    1110                         for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit) 
    1111                         { 
    1112                                 const int id = (*oit).first; 
    1113                                 Intersectable *object = (*oit).second; 
    1114  
    1115                                 if (multipleObjects[id] != object) // object not previously in pvs 
     1221        VssRay *ray = ci.ray; 
     1222 
     1223        Intersectable *oObject = ray->mOriginObject; 
     1224        Intersectable *tObject = ray->mTerminationObject; 
     1225 
     1226        if (oObject) 
     1227        {        
     1228                if (mPvsCountMethod == PER_OBJECT) 
     1229                { 
     1230                        if (ci.type == SortableEntry::ERayMin) 
     1231                        { 
     1232                                if (!oObject->Mailed()) 
    11161233                                { 
    1117                                         multipleObjects[id] = object; 
     1234                                        oObject->Mail(); 
    11181235                                        ++ pvsLeft; 
    11191236                                } 
    1120  
    1121                         } 
    1122                 }                                        
    1123         } 
    1124         else if (ci.type == SortableEntry::ERayMax) 
    1125         { 
    1126                 if (-- leaf->mCounter == 0) 
    1127                         pvsRight += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size(); 
    1128         } 
    1129 } 
    1130  
    1131  
    1132 float VspTree::EvalKdCostHeuristics(const RayInfoContainer &rays, 
    1133                                                                         const AxisAlignedBox3 &box, 
    1134                                                                         const int pvsSize, 
    1135                                                                         const int axis, 
    1136                                                                         float &position) 
     1237                        } 
     1238                        else if (ci.type == SortableEntry::ERayMax) 
     1239                        { 
     1240                                if (-- oObject->mCounter == 0) 
     1241                                        -- pvsRight; 
     1242                        } 
     1243                } 
     1244                else // per kd node 
     1245                { 
     1246                        set<KdLeaf *>::const_iterator kit, kit_end = oObject->mKdLeaves.end(); 
     1247 
     1248                        for (kit = oObject->mKdLeaves.begin(); kit != kit_end; ++ kit) 
     1249                        { 
     1250                                KdLeaf *node = dynamic_cast<KdLeaf *>(*kit); 
     1251 
     1252                                // add contributions of the kd nodes 
     1253                                if (ci.type == SortableEntry::ERayMin) 
     1254                                { 
     1255                                        AddContriToPvs(node, pvsLeft); 
     1256                                } 
     1257                                else if (ci.type == SortableEntry::ERayMax) 
     1258                                { 
     1259                                        RemoveContriFromPvs(node, pvsRight); 
     1260                                } 
     1261                        } 
     1262                } 
     1263                         
     1264 
     1265        } 
     1266         
     1267        if (tObject) 
     1268        {        
     1269                if (mPvsCountMethod == PER_OBJECT) 
     1270                { 
     1271                        if (ci.type == SortableEntry::ERayMin) 
     1272                        { 
     1273                                if (!tObject->Mailed()) 
     1274                                { 
     1275                                        tObject->Mail(); 
     1276                                        ++ pvsLeft; 
     1277                                } 
     1278                        } 
     1279                        else if (ci.type == SortableEntry::ERayMax) 
     1280                        { 
     1281                                if (-- tObject->mCounter == 0) 
     1282                                        -- pvsRight; 
     1283                        } 
     1284                } 
     1285                else // per kd node 
     1286                { 
     1287                        set<KdLeaf *>::const_iterator kit, kit_end = tObject->mKdLeaves.end(); 
     1288 
     1289                        for (kit = tObject->mKdLeaves.begin(); kit != kit_end; ++ kit) 
     1290                        { 
     1291                                KdLeaf *node = dynamic_cast<KdLeaf *>(*kit); 
     1292 
     1293                                if (ci.type == SortableEntry::ERayMin) 
     1294                                { 
     1295                                        AddContriToPvs(node, pvsLeft); 
     1296                                } 
     1297                                else if (ci.type == SortableEntry::ERayMax) 
     1298                                { 
     1299                                        RemoveContriFromPvs(node, pvsRight); 
     1300                                } 
     1301                        } 
     1302                } 
     1303        } 
     1304} 
     1305 
     1306 
     1307/* 
     1308float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays, 
     1309                                                                           const AxisAlignedBox3 &box, 
     1310                                                                           int pvsSize, 
     1311                                                                           const int axis, 
     1312                                                                           float &position) 
    11371313{ 
    11381314        const float minBox = box.Min(axis); 
     
    11451321 
    11461322        SortSplitCandidates(rays, axis, minBand, maxBand); 
     1323 
     1324        // prepare the heuristics sweep  
     1325        // (note: returns pvs size, so there would be no need  
     1326        // to give pvs size as argument) 
     1327        pvsSize = PrepareHeuristics(rays); 
     1328 
     1329        Debug << "here45 pvs: " << pvsSize << endl; 
    11471330 
    11481331        // go through the lists, count the number of objects left and right 
     
    11641347         
    11651348        // the relative cost ratio 
    1166         float ratio = /*Limits::Infinity;*/99999999.0f; 
     1349        float ratio = 99999999.0f; 
    11671350        bool splitPlaneFound = false; 
    11681351 
    11691352        Intersectable::NewMail(); 
    1170         KdNode::NewMail(); 
    1171  
    1172         RayInfoContainer::const_iterator ri, ri_end = rays.end(); 
    1173  
    1174         //-- set all kd nodes as belonging to the front pvs 
    1175  
    1176         for (ri = rays.begin(); ri != ri_end; ++ ri) 
    1177         { 
    1178                 Intersectable *oObject = (*ri).mRay->mOriginObject; 
    1179  
    1180                 if (oObject) 
    1181                 { 
    1182                         KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end(); 
    1183                  
    1184                         for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 
    1185                         { 
    1186                                 KdNode *node = (*kit).first; 
    1187  
    1188                                 if (!node->Mailed()) 
    1189                                 { 
    1190                                         node->Mail(); 
    1191                                         //node->mCounter = 1; 
    1192                                 } 
    1193                                 else 
    1194                                 { 
    1195                                         //++ node->mCounter; 
    1196                                 } 
    1197                         }        
    1198                 } 
    1199  
    1200                 Intersectable *tObject = (*ri).mRay->mTerminationObject; 
    1201  
    1202                 if (tObject) 
    1203                 { 
    1204                         KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end(); 
    1205                  
    1206                         for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 
    1207                         { 
    1208                                 KdNode *node = (*kit).first; 
    1209  
    1210                                 if (!node->Mailed()) 
    1211                                 { 
    1212                                         node->Mail(); 
    1213                                         //node->mCounter = 1; 
    1214                                 } 
    1215                                 else 
    1216                                 { 
    1217                                         //++ node->mCounter; 
    1218                                 } 
    1219                         }        
    1220                 } 
    1221         } 
    1222  
    1223         Intersectable::NewMail(); 
     1353        KdLeaf::NewMail(); 
     1354 
    12241355 
    12251356        vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end(); 
    12261357 
    1227         ObjectMap multipleObjectsLeft, multipleObjectsRight; 
    1228  
    1229  
    1230         // -- traverse through visibility events 
     1358Debug << "****************" << endl; 
     1359        //-- traverse through visibility events 
    12311360 
    12321361        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci) 
    12331362        { 
    1234                 VssRay *ray; 
    1235                 ray = (*ci).ray; 
    1236                  
    1237                 Intersectable *oObject = ray->mOriginObject; 
    1238                  
    1239                 KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end(); 
    1240  
    1241                 if (oObject) 
    1242                 {        
    1243                         for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 
    1244                         { 
    1245                 KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first); 
    1246  
    1247                                 EvalPvsIncr(multipleObjectsLeft, node, *ci, pvsl, pvsr); 
    1248                         } 
    1249                 } 
    1250  
    1251                 Intersectable *tObject = ray->mOriginObject; 
    1252  
    1253                 if (tObject) 
    1254                 {        
    1255                         for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 
    1256                         { 
    1257                                 KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first); 
    1258  
    1259                                 EvalPvsIncr(multipleObjectsRight, node, *ci, pvsl, pvsr); 
    1260                         } 
    1261                 } 
    1262  
     1363                EvalPvsIncr(*ci, pvsl, pvsr); 
    12631364 
    12641365                // Note: sufficient to compare size of bounding boxes of front and back side? 
     
    12671368                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value); 
    12681369 
    1269                         //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl; 
    1270                         //Debug << "cost= " << sum << endl; 
     1370                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << "\t cost= " << sum << endl; 
    12711371 
    12721372                        if (sum < minSum) 
     
    13041404                ratio = newRenderCost / oldRenderCost; 
    13051405        } 
     1406         
    13061407        //if (axis != 1) 
    1307         //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 
    1308          //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl; 
     1408        Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 
     1409              <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl; 
    13091410 
    13101411        return ratio; 
    1311 } 
    1312  
    1313  
    1314 #if TODO 
    1315  
    1316 float VspTree::EvalLocalCostHeuristicsNonIncremential(const RayInfoContainer &rays, 
    1317                                                                                                           const AxisAlignedBox3 &box, 
    1318                                                                                                           const int pvsSize, 
    1319                                                                                                           const int axis, 
    1320                                                                                                           float &position) 
    1321 { 
    1322         const float minBox = box.Min(axis); 
    1323         const float maxBox = box.Max(axis); 
    1324  
    1325         const float sizeBox = maxBox - minBox; 
    1326  
    1327         const float minBand = minBox + mMinBand * sizeBox; 
    1328         const float maxBand = minBox + mMaxBand * sizeBox; 
    1329  
    1330         SortSplitCandidates(rays, axis, minBand, maxBand); 
    1331  
    1332         // go through the lists, count the number of objects left and right 
    1333         // and evaluate the following cost funcion: 
    1334         // C = ct_div_ci  + (ql*rl + qr*rr)/queries 
    1335  
    1336         int pvsl = 0; 
    1337         int pvsr = pvsSize; 
    1338  
    1339         int pvsBack = pvsl; 
    1340         int pvsFront = pvsr; 
    1341  
    1342         float sum = (float)pvsSize * sizeBox; 
    1343         float minSum = 1e20f; 
    1344  
    1345          
    1346         // if no good split can be found, take mid split 
    1347         position = minBox + 0.5f * sizeBox; 
    1348          
    1349         // the relative cost ratio 
    1350         float ratio = /*Limits::Infinity;*/99999999.0f; 
    1351         bool splitPlaneFound = false; 
    1352  
    1353         Intersectable::NewMail(); 
    1354  
    1355         RayInfoContainer::const_iterator ri, ri_end = rays.end(); 
    1356  
    1357         //-- set all object as belonging to the front pvs 
    1358  
    1359         for(ri = rays.begin(); ri != ri_end; ++ ri) 
    1360         { 
    1361                 // Note: sufficient to compare size of bounding boxes of front and back side? 
    1362                 if (((*ci).value >= minBand) && ((*ci).value <= maxBand)) 
    1363                 { 
    1364                         sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value); 
    1365  
    1366                         //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl; 
    1367                         //Debug << "cost= " << sum << endl; 
    1368  
    1369                         if (sum < minSum) 
    1370                         { 
    1371                                 splitPlaneFound = true; 
    1372  
    1373                                 minSum = sum; 
    1374                                 position = (*ci).value; 
    1375                                  
    1376                                 pvsBack = pvsl; 
    1377                                 pvsFront = pvsr; 
    1378                         } 
    1379                 } 
    1380         } 
    1381  
    1382          
    1383         // -- compute cost 
    1384  
    1385         const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 
    1386         const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 
    1387  
    1388         const float pOverall = sizeBox; 
    1389         const float pBack = position - minBox; 
    1390         const float pFront = maxBox - position; 
    1391  
    1392          
    1393         const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit); 
    1394     const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 
    1395         const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 
    1396          
    1397         const float oldRenderCost = penaltyOld * pOverall + Limits::Small; 
    1398         const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack; 
    1399  
    1400         if (splitPlaneFound) 
    1401         { 
    1402                 ratio = newRenderCost / oldRenderCost; 
    1403         } 
    1404         //if (axis != 1) 
    1405         //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 
    1406          //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl; 
    1407  
    1408         return ratio; 
    1409 } 
    1410 #endif 
     1412}*/ 
    14111413 
    14121414 
     
    14271429        int bestAxis = -1; 
    14281430 
    1429         //mOnlyDrivingAxis = true; 
    1430  
    14311431        // if we use some kind of specialised fixed axis 
    14321432    const bool useSpecialAxis =  
    14331433                mOnlyDrivingAxis || mCirculatingAxis; 
    1434         Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl; 
     1434        //Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl; 
    14351435        if (mCirculatingAxis) 
    14361436        { 
     
    14811481                        else if (nCostRatio[axis] < nCostRatio[bestAxis]) 
    14821482                        { 
    1483                                 Debug << "old: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl; 
    14841483                                bestAxis = axis; 
    1485                                  
    1486                                 Debug << "new: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl; 
    14871484                        }  
    14881485                } 
     
    14991496        pBack = nProbBack[bestAxis]; 
    15001497 
    1501  
    1502         Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl; 
     1498        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl; 
    15031499        return nCostRatio[bestAxis]; 
    15041500} 
     
    17791775        ++ mCreatedViewCells; 
    17801776 
    1781 //#ifdef _DEBUG 
     1777#ifdef _DEBUG 
    17821778        Debug << "BSP stats: " 
    17831779                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), " 
     
    17861782                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), " 
    17871783                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl; 
    1788 //#endif 
     1784#endif 
    17891785} 
    17901786 
     
    30353031{ 
    30363032        SplitCandidate *splitCandidate = mTQueue.top(); 
    3037         Debug << "priority: " << splitCandidate->GetPriority() << endl; 
     3033        //Debug << "priority: " << splitCandidate->GetPriority() << endl; 
    30383034        mTQueue.pop(); 
    30393035 
     
    30893085                                                                        0, 
    30903086                                                                        &rays, 
    3091                                                                         (int)objects.size(), 
    3092                                                                         //mVspTree.ComputePvsSize(rays), 
     3087                                                                        //(int)objects.size(), 
     3088                                                                        mVspTree.ComputePvsSize(rays), 
    30933089                                                                        prop, 
    30943090                                                                        mVspTree.mBoundingBox); 
     
    31323128        cout << "Constructing view space / object space tree ... \n"; 
    31333129        const long startTime = GetTime();        
    3134  
     3130         
     3131        int i = 0; 
    31353132        while (!FinishedConstruction()) 
    31363133        { 
     
    31403137                        GlobalTerminationCriteriaMet(splitCandidate); 
    31413138 
    3142                 Debug << "cost: " << splitCandidate->GetPriority(); 
     3139                cout << "view cells: " << i ++ << endl; 
    31433140 
    31443141                // cost ratio of cost decrease / totalCost 
     
    31683165        } 
    31693166 
    3170         cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl; 
     3167        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl; 
    31713168 
    31723169        mVspTree.mVspStats.Stop(); 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

    r1072 r1074  
    883883 
    884884        /** Prepares objects for SAH. 
    885         */ 
    886         void PrepareHeuristics(const RayInfoContainer &rays); 
     885                @returns pvs size of the ray container 
     886        */ 
     887        int PrepareHeuristics(const RayInfoContainer &rays); 
     888 
     889        int PrepareHeuristics(Intersectable *object); 
    887890 
    888891        /** Computes pvs increase with respect to the previous pvs for SAH. 
     
    898901        float EvalLocalCostHeuristics(const RayInfoContainer &rays, 
    899902                                                                  const AxisAlignedBox3 &box, 
    900                                                                   const int pvsSize, 
     903                                                                  int pvsSize, 
    901904                                                                  const int axis, 
    902905                                                                  float &position); 
    903906 
    904         float EvalKdCostHeuristics(const RayInfoContainer &rays, 
    905                                                            const AxisAlignedBox3 &box, 
    906                                                            const int pvsSize, 
    907                                                            const int axis, 
    908                                                            float &position); 
    909          void EvalPvsIncr(ObjectMap &multipleObjects, 
    910                                           KdLeaf *leaf,  
    911                                           const SortableEntry &ci, 
     907        /** Evaluates the influence on the pvs of the visibility event ve. 
     908                @param ve the visibility event 
     909                @param pvsLeft updates the left pvs 
     910                @param rightPvs updates the right pvs 
     911        */ 
     912        void EvalPvsIncr(const SortableEntry &ve, 
    912913                                          int &pvsLeft, 
    913914                                          int &pvsRight) const; 
    914915 
     916        void RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const; 
     917        void AddContriToPvs(KdLeaf *leaf, int &pvs) const; 
    915918 
    916919        /** Subdivides the rays into front and back rays according to the split plane. 
     
    989992 
    990993protected: 
     994 
     995        int mPvsCountMethod; 
     996        enum {PER_OBJECT, PER_KDLEAF}; 
    991997 
    992998        ViewCellsManager *mViewCellsManager; 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VssPreprocessor.cpp

    r1052 r1074  
    314314  Exporter *exporter = NULL; 
    315315  exporter = Exporter::GetExporter(filename); 
    316   //    exporter->SetWireframe(); 
    317   //    exporter->ExportKdTree(*mKdTree); 
     316  exporter->SetWireframe(); 
     317  exporter->ExportKdTree(*mKdTree); 
    318318  exporter->SetFilled(); 
    319319  exporter->ExportScene(mSceneGraph->mRoot); 
     
    623623  if (!mLoadViewCells) 
    624624  { 
    625            Debug << "here923 " << vbox << endl; 
    626625          mViewCellsManager->SetViewSpaceBox(vbox); 
    627626          // construct view cells using it's own set of samples 
     
    746745  vssTree->Construct(mVssRays, mViewSpaceBox); 
    747746  cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl; 
     747 
     748  ExportRays("kdtree.x3d", mVssRays, 10); 
    748749 
    749750  if (0) 
Note: See TracChangeset for help on using the changeset viewer.