Ignore:
Timestamp:
10/05/06 11:15:50 (18 years ago)
Author:
mattausch
Message:
 
File:
1 edited

Legend:

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

    r1570 r1571  
    19751975void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter, 
    19761976                                                                                         const AxisAlignedBox3 *sceneBox, 
    1977                                                                                          const AxisAlignedPlane *clipPlane 
     1977                                                                                         const AxisAlignedPlane *clipPlane, 
     1978                                                                                         const bool colorCode 
    19781979                                                                                         ) const 
    19791980{ 
     
    19841985                if (!mOnlyValidViewCells || (*it)->GetValid()) 
    19851986                { 
    1986                         ExportColor(exporter, *it);      
     1987                        ExportColor(exporter, *it, colorCode);   
    19871988                        ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane); 
    19881989                } 
     
    23512352 
    23522353 
    2353 void ViewCellsManager::ExportColor(Exporter *exporter, ViewCell *vc) const 
     2354void ViewCellsManager::ExportColor(Exporter *exporter,  
     2355                                                                   ViewCell *vc,  
     2356                                                                   bool colorCode) const 
    23542357{ 
    23552358        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize); 
     
    28912894                mViewCellsTree->GetPvs(vc, pvs); 
    28922895 
     2896                char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i); 
     2897                Exporter *exporter = Exporter::GetExporter(s); 
     2898                 
     2899                cout << "view cell " << idx << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl; 
     2900 
     2901                if (exportRays) 
     2902                { 
     2903                        //////////// 
     2904                        //-- export rays piercing this view cell 
     2905 
     2906                        // use rays stored with the view cells 
     2907                        VssRayContainer vcRays, vcRays2, vcRays3; 
     2908            VssRayContainer collectRays; 
     2909 
     2910                        // collect initial view cells 
     2911                        ViewCellContainer leaves; 
     2912                        mViewCellsTree->CollectLeaves(vc, leaves); 
     2913 
     2914                        ViewCellContainer::const_iterator vit, vit_end = leaves.end(); 
     2915                for (vit = leaves.begin(); vit != vit_end; ++ vit) 
     2916                        {        
     2917                                // prepare some rays for output 
     2918                                VssRayContainer::const_iterator rit, rit_end = (*vit)->mVssRays.end(); 
     2919                                for (rit = (*vit)->mVssRays.begin(); rit != rit_end; ++ rit) 
     2920                                { 
     2921                                        collectRays.push_back(*rit); 
     2922                                } 
     2923                        } 
     2924 
     2925                        const int raysOut = min((int)collectRays.size(), maxRays); 
     2926 
     2927                        // prepare some rays for output 
     2928                        VssRayContainer::const_iterator rit, rit_end = collectRays.end(); 
     2929                        for (rit = collectRays.begin(); rit != rit_end; ++ rit) 
     2930                        { 
     2931                                const float p = RandomValue(0.0f, (float)collectRays.size()); 
     2932                                if (p < raysOut) 
     2933                                { 
     2934                                        cout << "here42 " << (int)(*rit)->mFlags << endl; 
     2935                                        if ((*rit)->mFlags & VssRay::BorderSample) 
     2936                                                vcRays.push_back(*rit); 
     2937                                        else if ((*rit)->mFlags & VssRay::ReverseSample) 
     2938                                                vcRays2.push_back(*rit); 
     2939                                        else 
     2940                                                vcRays3.push_back(*rit); 
     2941                                                 
     2942                                } 
     2943                        } 
     2944 
     2945                        exporter->ExportRays(vcRays, RgbColor(1, 0, 0)); 
     2946                        exporter->ExportRays(vcRays2, RgbColor(0, 1, 0)); 
     2947                        exporter->ExportRays(vcRays3, RgbColor(1, 1, 1)); 
     2948                } 
     2949                 
     2950                //////////////// 
     2951                //-- export view cell geometry 
     2952 
     2953                exporter->SetWireframe(); 
     2954 
     2955                Material m;//= RandomMaterial(); 
     2956                m.mDiffuseColor = RgbColor(0, 1, 0); 
     2957                exporter->SetForcedMaterial(m); 
     2958 
     2959                ExportViewCellGeometry(exporter, vc, NULL, NULL); 
     2960                exporter->SetFilled(); 
     2961 
     2962                if (exportPvs) 
     2963                { 
     2964                        Intersectable::NewMail(); 
     2965                        ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end(); 
     2966                         
     2967                        // output PVS of view cell 
     2968                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit) 
     2969                        {                
     2970                                Intersectable *intersect = (*oit).first; 
     2971                                 
     2972                                if (!intersect->Mailed()) 
     2973                                { 
     2974                                        intersect->Mail(); 
     2975 
     2976                                        m = RandomMaterial(); 
     2977                                        exporter->SetForcedMaterial(m); 
     2978                                        exporter->ExportIntersectable(intersect); 
     2979                                } 
     2980                        } 
     2981                        cout << endl; 
     2982                } 
     2983                 
     2984                DEL_PTR(exporter); 
     2985                cout << "finished" << endl; 
     2986        } 
     2987} 
     2988 
     2989 
     2990void BspViewCellsManager::TestSubdivision() 
     2991{ 
     2992        ViewCellContainer leaves; 
     2993        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves); 
     2994 
     2995        ViewCellContainer::const_iterator it, it_end = leaves.end(); 
     2996 
     2997        const float vol = mViewSpaceBox.GetVolume(); 
     2998        float subdivVol = 0; 
     2999        float newVol = 0; 
     3000 
     3001        for (it = leaves.begin(); it != it_end; ++ it) 
     3002        { 
     3003                BspNodeGeometry geom; 
     3004                mBspTree->ConstructGeometry(*it, geom); 
     3005 
     3006                const float lVol = geom.GetVolume(); 
     3007                newVol += lVol; 
     3008                subdivVol += (*it)->GetVolume(); 
     3009 
     3010                const float thres = 0.9f; 
     3011                if ((lVol < ((*it)->GetVolume() * thres)) || 
     3012                        (lVol * thres > ((*it)->GetVolume()))) 
     3013                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl; 
     3014        } 
     3015         
     3016        Debug << "exact volume: " << vol << endl; 
     3017        Debug << "subdivision volume: " << subdivVol << endl; 
     3018        Debug << "new volume: " << newVol << endl; 
     3019} 
     3020 
     3021 
     3022void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 
     3023                                                                                                 ViewCell *vc, 
     3024                                                                                                 const AxisAlignedBox3 *sceneBox, 
     3025                                                                                                 const AxisAlignedPlane *clipPlane 
     3026                                                                                                 ) const 
     3027{ 
     3028        if (clipPlane) 
     3029        { 
     3030                const Plane3 plane = clipPlane->GetPlane(); 
     3031 
     3032                ViewCellContainer leaves; 
     3033                mViewCellsTree->CollectLeaves(vc, leaves); 
     3034                ViewCellContainer::const_iterator it, it_end = leaves.end(); 
     3035 
     3036                for (it = leaves.begin(); it != it_end; ++ it) 
     3037                { 
     3038                        BspNodeGeometry geom; 
     3039                        BspNodeGeometry front; 
     3040                        BspNodeGeometry back; 
     3041 
     3042                        mBspTree->ConstructGeometry(*it, geom); 
     3043 
     3044                        const float eps = 0.0001f; 
     3045                        const int cf = geom.Side(plane, eps); 
     3046 
     3047                        if (cf == -1) 
     3048                        { 
     3049                                exporter->ExportPolygons(geom.GetPolys()); 
     3050                        } 
     3051                        else if (cf == 0) 
     3052                        { 
     3053                                geom.SplitGeometry(front, 
     3054                                                                   back, 
     3055                                                                   plane, 
     3056                                                                   mViewSpaceBox,  
     3057                                                                   eps); 
     3058 
     3059                                if (back.Valid()) 
     3060                                { 
     3061                                        exporter->ExportPolygons(back.GetPolys()); 
     3062                                }                        
     3063                        } 
     3064                } 
     3065        } 
     3066        else 
     3067        { 
     3068                // export mesh if available 
     3069                // TODO: some bug here? 
     3070                if (1 && vc->GetMesh()) 
     3071                { 
     3072                        exporter->ExportMesh(vc->GetMesh()); 
     3073                } 
     3074                else 
     3075                { 
     3076                        BspNodeGeometry geom; 
     3077                        mBspTree->ConstructGeometry(vc, geom); 
     3078                        exporter->ExportPolygons(geom.GetPolys()); 
     3079                } 
     3080        } 
     3081} 
     3082 
     3083 
     3084void BspViewCellsManager::CreateMesh(ViewCell *vc) 
     3085{ 
     3086        // note: should previous mesh be deleted (via mesh manager?) 
     3087        BspNodeGeometry geom; 
     3088        mBspTree->ConstructGeometry(vc, geom); 
     3089 
     3090        Mesh *mesh = MeshManager::GetSingleton()->CreateResource(); 
     3091 
     3092        IncludeNodeGeomInMesh(geom, *mesh); 
     3093        vc->SetMesh(mesh); 
     3094} 
     3095 
     3096 
     3097void BspViewCellsManager::Finalize(ViewCell *viewCell,  
     3098                                                                   const bool createMesh) 
     3099{ 
     3100        float area = 0; 
     3101        float volume = 0; 
     3102 
     3103        ViewCellContainer leaves; 
     3104        mViewCellsTree->CollectLeaves(viewCell, leaves); 
     3105 
     3106        ViewCellContainer::const_iterator it, it_end = leaves.end(); 
     3107 
     3108    for (it = leaves.begin(); it != it_end; ++ it) 
     3109        { 
     3110                BspNodeGeometry geom; 
     3111 
     3112                mBspTree->ConstructGeometry(*it, geom); 
     3113 
     3114                const float lVol = geom.GetVolume(); 
     3115                const float lArea = geom.GetArea(); 
     3116 
     3117                area += lArea; 
     3118                volume += lVol; 
     3119         
     3120                CreateMesh(*it); 
     3121        } 
     3122 
     3123        viewCell->SetVolume(volume); 
     3124        viewCell->SetArea(area); 
     3125} 
     3126 
     3127 
     3128ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const 
     3129{ 
     3130        if (!ViewCellsConstructed()) 
     3131        { 
     3132                return NULL; 
     3133        } 
     3134        if (!mViewSpaceBox.IsInside(point)) 
     3135        { 
     3136                return NULL; 
     3137        } 
     3138        return mBspTree->GetViewCell(point); 
     3139} 
     3140 
     3141 
     3142void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,  
     3143                                                                                                 vector<MergeCandidate> &candidates) 
     3144{ 
     3145        cout << "collecting merge candidates ... " << endl; 
     3146 
     3147        if (mUseRaysForMerge) 
     3148        { 
     3149                mBspTree->CollectMergeCandidates(rays, candidates); 
     3150        } 
     3151        else 
     3152        { 
     3153                vector<BspLeaf *> leaves; 
     3154                mBspTree->CollectLeaves(leaves); 
     3155                mBspTree->CollectMergeCandidates(leaves, candidates); 
     3156        } 
     3157 
     3158        cout << "fininshed collecting candidates" << endl; 
     3159} 
     3160 
     3161 
     3162 
     3163bool BspViewCellsManager::ExportViewCells(const string filename,  
     3164                                                                                  const bool exportPvs,  
     3165                                                                                  const ObjectContainer &objects) 
     3166{ 
     3167        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed()) 
     3168        { 
     3169                return false; 
     3170        } 
     3171 
     3172        cout << "exporting view cells to xml ... "; 
     3173 
     3174        OUT_STREAM stream(filename.c_str()); 
     3175 
     3176        // for output we need unique ids for each view cell 
     3177        CreateUniqueViewCellIds(); 
     3178 
     3179        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl; 
     3180        stream << "<VisibilitySolution>" << endl; 
     3181 
     3182        if (exportPvs)  
     3183        { 
     3184                ////////// 
     3185                //-- export bounding boxes: they are used to identify the objects from the pvs and 
     3186                //-- assign them to the entities in the rendering engine 
     3187 
     3188                stream << "<BoundingBoxes>" << endl; 
     3189                ObjectContainer::const_iterator oit, oit_end = objects.end(); 
     3190 
     3191                for (oit = objects.begin(); oit != oit_end; ++ oit) 
     3192                { 
     3193                        const AxisAlignedBox3 box = (*oit)->GetBox(); 
     3194                         
     3195                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\"" 
     3196                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\"" 
     3197                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl; 
     3198                } 
     3199 
     3200                stream << "</BoundingBoxes>" << endl; 
     3201        } 
     3202 
     3203        /////////// 
     3204        //-- export the view cells and the pvs 
     3205 
     3206        const int numViewCells = mCurrentViewCellsStats.viewCells; 
     3207        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl; 
     3208 
     3209        mViewCellsTree->Export(stream, exportPvs); 
     3210         
     3211        stream << "</ViewCells>" << endl; 
     3212 
     3213        ///////////// 
     3214        //-- export the view space hierarchy 
     3215        stream << "<ViewSpaceHierarchy type=\"bsp\"" 
     3216                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\"" 
     3217                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl; 
     3218 
     3219        mBspTree->Export(stream); 
     3220 
     3221        // end tags 
     3222        stream << "</ViewSpaceHierarchy>" << endl; 
     3223        stream << "</VisibilitySolution>" << endl; 
     3224 
     3225        stream.close(); 
     3226        cout << "finished" << endl; 
     3227 
     3228        return true; 
     3229} 
     3230 
     3231 
     3232ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root) 
     3233{ 
     3234        ViewCellInterior *vcRoot = new ViewCellInterior(); 
     3235                 
     3236        // evaluate merge cost for priority traversal 
     3237        const float mergeCost = 1.0f / (float)root->mTimeStamp; 
     3238        vcRoot->SetMergeCost(mergeCost); 
     3239 
     3240        float volume = 0; 
     3241        vector<BspLeaf *> leaves; 
     3242        mBspTree->CollectLeaves(leaves); 
     3243        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end(); 
     3244        ViewCell::NewMail(); 
     3245 
     3246        for (lit = leaves.begin(); lit != lit_end; ++ lit) 
     3247        { 
     3248                BspLeaf *leaf = *lit; 
     3249                ViewCell *vc = leaf->GetViewCell(); 
     3250 
     3251                if (!vc->Mailed()) 
     3252                { 
     3253                        vc->Mail(); 
     3254                        vc->SetMergeCost(0.0f); 
     3255                        vcRoot->SetupChildLink(vc); 
     3256 
     3257                        volume += vc->GetVolume(); 
     3258                        volume += vc->GetVolume();       
     3259                        vcRoot->SetVolume(volume); 
     3260                } 
     3261        } 
     3262         
     3263        return vcRoot; 
     3264} 
     3265 
     3266 
     3267ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root) 
     3268{ 
     3269        // terminate recursion 
     3270        if (root->IsLeaf()) 
     3271        { 
     3272                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root); 
     3273                leaf->GetViewCell()->SetMergeCost(0.0f); 
     3274                return leaf->GetViewCell(); 
     3275        } 
     3276         
     3277        BspInterior *interior = dynamic_cast<BspInterior *>(root); 
     3278        ViewCellInterior *viewCellInterior = new ViewCellInterior(); 
     3279                 
     3280        // evaluate merge cost for priority traversal 
     3281        float mergeCost = 1.0f / (float)root->mTimeStamp; 
     3282        viewCellInterior->SetMergeCost(mergeCost); 
     3283 
     3284        float volume = 0; 
     3285         
     3286        BspNode *front = interior->GetFront(); 
     3287        BspNode *back = interior->GetBack(); 
     3288 
     3289 
     3290        //////////// 
     3291        //-- recursivly compute child hierarchies 
     3292 
     3293        ViewCell *backVc = ConstructSpatialMergeTree(back); 
     3294        ViewCell *frontVc = ConstructSpatialMergeTree(front); 
     3295 
     3296        viewCellInterior->SetupChildLink(backVc); 
     3297        viewCellInterior->SetupChildLink(frontVc); 
     3298 
     3299        volume += backVc->GetVolume(); 
     3300        volume += frontVc->GetVolume();  
     3301 
     3302        viewCellInterior->SetVolume(volume); 
     3303 
     3304        return viewCellInterior; 
     3305} 
     3306 
     3307 
     3308/************************************************************************/ 
     3309/*                   KdViewCellsManager implementation                  */ 
     3310/************************************************************************/ 
     3311 
     3312 
     3313 
     3314KdViewCellsManager::KdViewCellsManager(ViewCellsTree *vcTree, KdTree *kdTree): 
     3315ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100) 
     3316{ 
     3317} 
     3318 
     3319 
     3320float KdViewCellsManager::GetProbability(ViewCell *viewCell) 
     3321{ 
     3322        // compute view cell area / volume as subsititute for probability 
     3323        if (0) 
     3324                return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea(); 
     3325        else 
     3326                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume(); 
     3327} 
     3328 
     3329 
     3330 
     3331 
     3332void KdViewCellsManager::CollectViewCells() 
     3333{ 
     3334        //mKdTree->CollectViewCells(mViewCells); TODO 
     3335} 
     3336 
     3337 
     3338int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects, 
     3339                                                                  const VssRayContainer &rays) 
     3340{ 
     3341        // if view cells already constructed 
     3342        if (ViewCellsConstructed()) 
     3343                return 0; 
     3344 
     3345        mKdTree->Construct(); 
     3346 
     3347        mTotalAreaValid = false; 
     3348        // create the view cells 
     3349        mKdTree->CreateAndCollectViewCells(mViewCells); 
     3350        // cast rays 
     3351        ComputeSampleContributions(rays, true, false); 
     3352 
     3353        EvaluateViewCellsStats(); 
     3354        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl; 
     3355 
     3356        return 0; 
     3357} 
     3358 
     3359 
     3360bool KdViewCellsManager::ViewCellsConstructed() const 
     3361{ 
     3362        return mKdTree->GetRoot() != NULL; 
     3363} 
     3364 
     3365 
     3366int KdViewCellsManager::PostProcess(const ObjectContainer &objects, 
     3367                                                                        const VssRayContainer &rays) 
     3368{ 
     3369        return 0; 
     3370} 
     3371 
     3372 
     3373void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects, 
     3374                                                                                           const int maxViewCells, 
     3375                                                                                           const bool sortViewCells, 
     3376                                                                                           const bool exportPvs, 
     3377                                                                                           const bool exportRays, 
     3378                                                                                           const int maxRays, 
     3379                                                                                           const string prefix, 
     3380                                                                                           VssRayContainer *visRays) 
     3381{ 
     3382        // TODO 
     3383} 
     3384 
     3385 
     3386void KdViewCellsManager::Visualize(const ObjectContainer &objects, 
     3387                                                                   const VssRayContainer &sampleRays) 
     3388{ 
     3389        if (!ViewCellsConstructed()) 
     3390                return; 
     3391 
     3392        // using view cells instead of the kd PVS of objects 
     3393        const bool useViewCells = true; 
     3394        bool exportRays = false; 
     3395 
     3396        int limit = min(mVisualizationSamples, (int)sampleRays.size()); 
     3397        const int pvsOut = min((int)objects.size(), 10); 
     3398        VssRayContainer *rays = new VssRayContainer[pvsOut]; 
     3399 
     3400        if (useViewCells) 
     3401        { 
     3402                const int leafOut = 10; 
     3403 
     3404                ViewCell::NewMail(); 
     3405 
     3406                //-- some rays for output 
     3407                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples); 
     3408                Debug << "visualization using " << raysOut << " samples" << endl; 
     3409 
     3410                //-- some random view cells and rays for output 
     3411                vector<KdLeaf *> kdLeaves; 
     3412 
     3413                for (int i = 0; i < leafOut; ++ i) 
     3414                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf())); 
     3415 
     3416                for (int i = 0; i < kdLeaves.size(); ++ i) 
     3417                { 
     3418                        KdLeaf *leaf = kdLeaves[i]; 
     3419                        RayContainer vcRays; 
     3420 
     3421                        cout << "creating output for view cell " << i << " ... "; 
     3422#if 0 
     3423                        // check whether we can add the current ray to the output rays 
     3424                        for (int k = 0; k < raysOut; ++ k) 
     3425                        { 
     3426                                Ray *ray = sampleRays[k]; 
     3427 
     3428                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j) 
     3429                                { 
     3430                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf; 
     3431 
     3432                                        if (leaf->GetViewCell() == leaf2->GetViewCell()) 
     3433                                        { 
     3434                                                vcRays.push_back(ray); 
     3435                                        } 
     3436                                } 
     3437                        } 
     3438#endif 
     3439                        Intersectable::NewMail(); 
     3440 
     3441                        ViewCell *vc = leaf->mViewCell; 
     3442                        char str[64]; sprintf(str, "viewcell%04d.wrl", i); 
     3443 
     3444                        Exporter *exporter = Exporter::GetExporter(str); 
     3445                        exporter->SetFilled(); 
     3446 
     3447                        exporter->SetWireframe(); 
     3448                        //exporter->SetFilled(); 
     3449 
     3450                        Material m;//= RandomMaterial(); 
     3451                        m.mDiffuseColor = RgbColor(1, 1, 0); 
     3452                        exporter->SetForcedMaterial(m); 
     3453 
     3454                        AxisAlignedBox3 box = mKdTree->GetBox(leaf); 
     3455                        exporter->ExportBox(box); 
     3456 
     3457                        // export rays piercing this view cell 
     3458                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0)); 
     3459 
     3460                        m.mDiffuseColor = RgbColor(1, 0, 0); 
     3461                        exporter->SetForcedMaterial(m); 
     3462 
     3463                        // exporter->SetWireframe(); 
     3464                        exporter->SetFilled(); 
     3465 
     3466                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end(); 
     3467                        // -- output PVS of view cell 
     3468                        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
     3469                        { 
     3470                                Intersectable *intersect = (*it).first; 
     3471                                if (!intersect->Mailed()) 
     3472                                { 
     3473                                        exporter->ExportIntersectable(intersect); 
     3474                                        intersect->Mail(); 
     3475                                } 
     3476                        } 
     3477 
     3478                        DEL_PTR(exporter); 
     3479                        cout << "finished" << endl; 
     3480                } 
     3481 
     3482                DEL_PTR(rays); 
     3483        } 
     3484        else // using kd PVS of objects 
     3485        { 
     3486                for (int i = 0; i < limit; ++ i) 
     3487                { 
     3488                        VssRay *ray = sampleRays[i]; 
     3489 
     3490                        // check whether we can add this to the rays 
     3491                        for (int j = 0; j < pvsOut; j++) 
     3492                        { 
     3493                                if (objects[j] == ray->mTerminationObject) 
     3494                                { 
     3495                                        rays[j].push_back(ray); 
     3496                                } 
     3497                        } 
     3498                } 
     3499 
     3500                if (exportRays) 
     3501                { 
     3502                        Exporter *exporter = NULL; 
     3503                        exporter = Exporter::GetExporter("sample-rays.x3d"); 
     3504                        exporter->SetWireframe(); 
     3505                        exporter->ExportKdTree(*mKdTree); 
     3506 
     3507                        for (i = 0; i < pvsOut; i++) 
     3508                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0)); 
     3509 
     3510                        exporter->SetFilled(); 
     3511                        delete exporter; 
     3512                } 
     3513 
     3514                for (int k=0; k < pvsOut; k++) 
     3515                { 
     3516                        Intersectable *object = objects[k]; 
     3517                        char str[64]; sprintf(str, "viewcell%04d.wrl", i); 
     3518 
     3519                        Exporter *exporter = Exporter::GetExporter(str); 
     3520                        exporter->SetWireframe(); 
     3521 
     3522                        KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin(); 
     3523                        Intersectable::NewMail(); 
     3524 
     3525                        // avoid adding the object to the list 
     3526                        object->Mail(); 
     3527                        ObjectContainer visibleObjects; 
     3528 
     3529                        for (; kit != object->mKdPvs.mEntries.end(); i++) 
     3530                        { 
     3531                                KdNode *node = (*kit).first; 
     3532                                exporter->ExportBox(mKdTree->GetBox(node)); 
     3533 
     3534                                mKdTree->CollectObjects(node, visibleObjects); 
     3535                        } 
     3536 
     3537                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0)); 
     3538                        exporter->SetFilled(); 
     3539 
     3540                        for (int j = 0; j < visibleObjects.size(); j++) 
     3541                                exporter->ExportIntersectable(visibleObjects[j]); 
     3542 
     3543                        Material m; 
     3544                        m.mDiffuseColor = RgbColor(1, 0, 0); 
     3545                        exporter->SetForcedMaterial(m); 
     3546                        exporter->ExportIntersectable(object); 
     3547 
     3548                        delete exporter; 
     3549                } 
     3550        } 
     3551} 
     3552 
     3553 
     3554ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const 
     3555{ 
     3556        return new KdViewCell(mesh); 
     3557} 
     3558 
     3559 
     3560void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 
     3561                                                                                                ViewCell *vc, 
     3562                                                                                                const AxisAlignedBox3 *sceneBox, 
     3563                                                                                                const AxisAlignedPlane *clipPlane 
     3564                                                                                                ) const 
     3565{ 
     3566        ViewCellContainer leaves; 
     3567        mViewCellsTree->CollectLeaves(vc, leaves); 
     3568        ViewCellContainer::const_iterator it, it_end = leaves.end(); 
     3569 
     3570        for (it = leaves.begin(); it != it_end; ++ it) 
     3571        { 
     3572                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it); 
     3573                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0])); 
     3574        } 
     3575} 
     3576 
     3577 
     3578int KdViewCellsManager::GetType() const 
     3579{ 
     3580        return ViewCellsManager::KD; 
     3581} 
     3582 
     3583 
     3584 
     3585KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf) 
     3586{ 
     3587        KdNode *node = leaf; 
     3588 
     3589        while (node->mParent && node->mDepth > mKdPvsDepth) 
     3590                node = node->mParent; 
     3591 
     3592        return node; 
     3593} 
     3594 
     3595int KdViewCellsManager::CastLineSegment(const Vector3 &origin, 
     3596                                                                                const Vector3 &termination, 
     3597                                                                                ViewCellContainer &viewcells) 
     3598{ 
     3599        return mKdTree->CastLineSegment(origin, termination, viewcells); 
     3600} 
     3601 
     3602 
     3603void KdViewCellsManager::CreateMesh(ViewCell *vc) 
     3604{ 
     3605        // TODO 
     3606} 
     3607 
     3608 
     3609 
     3610void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,  
     3611                                                                                                vector<MergeCandidate> &candidates) 
     3612{ 
     3613        // TODO 
     3614} 
     3615 
     3616 
     3617 
     3618/**************************************************************************/ 
     3619/*                   VspBspViewCellsManager implementation                */ 
     3620/**************************************************************************/ 
     3621 
     3622 
     3623VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree): 
     3624ViewCellsManager(vcTree), mVspBspTree(vspBspTree) 
     3625{ 
     3626        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples); 
     3627        mVspBspTree->SetViewCellsManager(this); 
     3628        mVspBspTree->mViewCellsTree = mViewCellsTree; 
     3629} 
     3630 
     3631 
     3632VspBspViewCellsManager::~VspBspViewCellsManager() 
     3633{ 
     3634} 
     3635 
     3636 
     3637float VspBspViewCellsManager::GetProbability(ViewCell *viewCell) 
     3638{ 
     3639        if (0 && mVspBspTree->mUseAreaForPvs) 
     3640                return GetArea(viewCell) / GetAccVcArea(); 
     3641        else 
     3642                return GetVolume(viewCell) / mViewSpaceBox.GetVolume(); 
     3643} 
     3644 
     3645 
     3646void VspBspViewCellsManager::CollectViewCells() 
     3647{ 
     3648        // view cells tree constructed? 
     3649        if (!ViewCellsTreeConstructed()) 
     3650        { 
     3651                mVspBspTree->CollectViewCells(mViewCells, false); 
     3652        } 
     3653        else  
     3654        {        
     3655                // we can use the view cells tree hierarchy to get the right set 
     3656                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells); 
     3657        } 
     3658} 
     3659 
     3660 
     3661void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,  
     3662                                                                                                        vector<MergeCandidate> &candidates) 
     3663{        
     3664        cout << "collecting merge candidates ... " << endl; 
     3665 
     3666        if (mUseRaysForMerge) 
     3667        { 
     3668                mVspBspTree->CollectMergeCandidates(rays, candidates); 
     3669        } 
     3670        else 
     3671        { 
     3672                vector<BspLeaf *> leaves; 
     3673                mVspBspTree->CollectLeaves(leaves); 
     3674         
     3675                mVspBspTree->CollectMergeCandidates(leaves, candidates); 
     3676        } 
     3677 
     3678        cout << "fininshed collecting candidates" << endl; 
     3679} 
     3680 
     3681 
     3682bool VspBspViewCellsManager::ViewCellsConstructed() const 
     3683{ 
     3684        return mVspBspTree->GetRoot() != NULL; 
     3685} 
     3686 
     3687 
     3688ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const 
     3689{ 
     3690        return new BspViewCell(mesh); 
     3691} 
     3692 
     3693 
     3694int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects, 
     3695                                                                                                 const VssRayContainer &rays) 
     3696{ 
     3697        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size()); 
     3698 
     3699        // if view cells were already constructed 
     3700        if (ViewCellsConstructed()) 
     3701        { 
     3702                return 0; 
     3703        } 
     3704 
     3705        int sampleContributions = 0; 
     3706        VssRayContainer sampleRays; 
     3707 
     3708        const int limit = min(mInitialSamples, (int)rays.size()); 
     3709 
     3710        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples  
     3711                  << ", actual rays: " << (int)rays.size() << endl; 
     3712 
     3713        VssRayContainer savedRays; 
     3714 
     3715        if (SAMPLE_AFTER_SUBDIVISION) 
     3716        { 
     3717                VssRayContainer constructionRays; 
     3718                 
     3719                GetRaySets(rays, mInitialSamples, constructionRays, &savedRays); 
     3720 
     3721                Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl; 
     3722                Debug << "rays saved for later use: " << (int)savedRays.size() << endl; 
     3723         
     3724                mVspBspTree->Construct(constructionRays, &mViewSpaceBox); 
     3725        } 
     3726        else 
     3727        { 
     3728                Debug << "rays used for initial construction: " << (int)rays.size() << endl; 
     3729                mVspBspTree->Construct(rays, &mViewSpaceBox); 
     3730        } 
     3731 
     3732        // collapse invalid regions 
     3733        cout << "collapsing invalid tree regions ... "; 
     3734        long startTime = GetTime(); 
     3735 
     3736        const int collapsedLeaves = mVspBspTree->CollapseTree(); 
     3737        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3  
     3738                  << " seconds" << endl; 
     3739 
     3740    cout << "finished" << endl; 
     3741 
     3742        ///////////////// 
     3743        //-- stats after construction 
     3744 
     3745        Debug << mVspBspTree->GetStatistics() << endl; 
     3746 
     3747        ResetViewCells(); 
     3748        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl; 
     3749 
     3750 
     3751        ////////////////////// 
     3752        //-- recast the rest of the rays 
     3753 
     3754        startTime = GetTime(); 
     3755 
     3756        cout << "Computing remaining ray contributions ... "; 
     3757 
     3758        if (SAMPLE_AFTER_SUBDIVISION) 
     3759                ComputeSampleContributions(savedRays, true, false); 
     3760 
     3761        cout << "finished" << endl; 
     3762 
     3763        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3 
     3764                  << " secs" << endl; 
     3765 
     3766        cout << "construction finished" << endl; 
     3767 
     3768        if (0) 
     3769        {       //////// 
     3770                //-- real meshes are contructed at this stage 
     3771                cout << "finalizing view cells ... "; 
     3772                FinalizeViewCells(true); 
     3773                cout << "finished" << endl; 
     3774        } 
     3775 
     3776        return sampleContributions; 
     3777} 
     3778 
     3779 
     3780void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays, 
     3781                                                                                        const ObjectContainer &objects) 
     3782{ 
     3783    int vcSize = 0; 
     3784        int pvsSize = 0; 
     3785 
     3786        //-- merge view cells 
     3787        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl; 
     3788        long startTime = GetTime(); 
     3789 
     3790 
     3791        if (mMergeViewCells) 
     3792        { 
     3793                // TODO: should be done BEFORE the ray casting 
     3794                // compute tree by merging the nodes based on cost heuristics 
     3795                mViewCellsTree->ConstructMergeTree(rays, objects); 
     3796        } 
     3797        else 
     3798        { 
     3799                // compute tree by merging the nodes of the spatial hierarchy 
     3800                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot()); 
     3801                mViewCellsTree->SetRoot(root); 
     3802 
     3803                // compute pvs 
     3804                ObjectPvs pvs; 
     3805                UpdatePvsForEvaluation(root, pvs); 
     3806        } 
     3807 
     3808        if (1) 
     3809        { 
     3810                char mstats[100]; 
     3811                ObjectPvs pvs; 
     3812 
     3813                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats); 
     3814                mViewCellsTree->ExportStats(mstats); 
     3815        } 
     3816 
     3817        cout << "merged view cells in " 
     3818                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl; 
     3819 
     3820        Debug << "Postprocessing: Merged view cells in " 
     3821                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl; 
     3822         
     3823 
     3824        ////////////////// 
     3825        //-- stats and visualizations 
     3826 
     3827        int savedColorCode = mColorCode; 
     3828         
     3829        // get currently active view cell set 
     3830        ResetViewCells(); 
     3831        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl; 
     3832         
     3833        if (1) // export merged view cells 
     3834        { 
     3835                mColorCode = 0; 
     3836                Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl"); 
     3837                 
     3838                cout << "exporting view cells after merge ... "; 
     3839 
     3840                if (exporter) 
     3841                { 
     3842                        if (0) 
     3843                                exporter->SetWireframe(); 
     3844                        else 
     3845                                exporter->SetFilled(); 
     3846 
     3847                        ExportViewCellsForViz(exporter, NULL, GetClipPlane()); 
     3848 
     3849                        if (mExportGeometry) 
     3850                        { 
     3851                                Material m; 
     3852                                m.mDiffuseColor = RgbColor(0, 1, 0); 
     3853                                exporter->SetForcedMaterial(m); 
     3854                                exporter->SetFilled(); 
     3855 
     3856                                exporter->ExportGeometry(objects); 
     3857                        } 
     3858 
     3859                        delete exporter; 
     3860                } 
     3861                cout << "finished" << endl; 
     3862        } 
     3863 
     3864        if (1)  
     3865        { 
     3866                // use pvs size for color coding 
     3867                mColorCode = 1; 
     3868                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl"); 
     3869 
     3870                cout << "exporting view cells after merge (pvs size) ... ";      
     3871 
     3872                if (exporter) 
     3873                { 
     3874                        exporter->SetFilled(); 
     3875 
     3876                        ExportViewCellsForViz(exporter, NULL, GetClipPlane()); 
     3877 
     3878                        if (mExportGeometry) 
     3879                        { 
     3880                                Material m; 
     3881                                m.mDiffuseColor = RgbColor(0, 1, 0); 
     3882                                exporter->SetForcedMaterial(m); 
     3883                                exporter->SetFilled(); 
     3884 
     3885                                exporter->ExportGeometry(objects); 
     3886                        } 
     3887 
     3888                        delete exporter; 
     3889                } 
     3890                cout << "finished" << endl; 
     3891        } 
     3892 
     3893        mColorCode = savedColorCode; 
     3894 
     3895} 
     3896 
     3897 
     3898bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const 
     3899{ 
     3900        return GetSpatialNode(viewCell) != NULL; 
     3901} 
     3902 
     3903 
     3904BspNode *VspBspViewCellsManager::GetSpatialNode(ViewCell *viewCell) const 
     3905{ 
     3906        if (!viewCell->IsLeaf()) 
     3907        { 
     3908                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(viewCell); 
     3909                return bspVc->mLeaves[0]; 
     3910        } 
     3911        else 
     3912        { 
     3913                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell); 
     3914 
     3915                // cannot be node of binary tree 
     3916                if (interior->mChildren.size() != 2) 
     3917                        return NULL; 
     3918 
     3919                ViewCell *left = interior->mChildren[0]; 
     3920                ViewCell *right = interior->mChildren[1]; 
     3921 
     3922                BspNode *leftNode = GetSpatialNode(left); 
     3923                BspNode *rightNode = GetSpatialNode(right); 
     3924 
     3925                if (leftNode && rightNode && leftNode->IsSibling(rightNode)) 
     3926                { 
     3927                        return leftNode->GetParent();  
     3928                } 
     3929        } 
     3930 
     3931        return NULL; 
     3932} 
     3933 
     3934 
     3935void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays, 
     3936                                                                                         const ObjectContainer &objects) 
     3937{ 
     3938        mRenderer->RenderScene(); 
     3939        SimulationStatistics ss; 
     3940        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss); 
     3941    Debug << "render time before refine\n\n" << ss << endl; 
     3942 
     3943        const long startTime = GetTime(); 
     3944        cout << "Refining the merged view cells ... "; 
     3945 
     3946        // refining the merged view cells 
     3947        const int refined = mViewCellsTree->RefineViewCells(rays, objects); 
     3948 
     3949        //-- stats and visualizations 
     3950        cout << "finished" << endl; 
     3951        cout << "refined " << refined << " view cells in " 
     3952                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl; 
     3953 
     3954        Debug << "Postprocessing: refined " << refined << " view cells in " 
     3955                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl; 
     3956} 
     3957 
     3958 
     3959int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects, 
     3960                                                                                const VssRayContainer &rays) 
     3961{ 
     3962        if (!ViewCellsConstructed()) 
     3963        { 
     3964                Debug << "postprocess error: no view cells constructed" << endl; 
     3965                return 0; 
     3966        } 
     3967 
     3968        // view cells already finished before post processing step  
     3969        // (i.e. because they were loaded) 
     3970        if (mViewCellsFinished) 
     3971        { 
     3972                FinalizeViewCells(true); 
     3973                EvaluateViewCellsStats(); 
     3974 
     3975                return 0; 
     3976        } 
     3977 
     3978        // check if new view cells turned invalid 
     3979        int minPvs, maxPvs; 
     3980 
     3981        if (0) 
     3982        { 
     3983                minPvs = mMinPvsSize; 
     3984                maxPvs = mMaxPvsSize; 
     3985        } 
     3986        else 
     3987        { 
     3988                // problem matt: why did I start here from zero? 
     3989                minPvs = 0; 
     3990                maxPvs = mMaxPvsSize; 
     3991        } 
     3992 
     3993        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl; 
     3994        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl; 
     3995         
     3996        SetValidity(minPvs, maxPvs);  
     3997 
     3998        // update valid view space according to valid view cells 
     3999        if (0) mVspBspTree->ValidateTree(); 
     4000 
     4001        // area has to be recomputed 
     4002        mTotalAreaValid = false; 
     4003        VssRayContainer postProcessRays; 
     4004        GetRaySets(rays, mPostProcessSamples, postProcessRays); 
     4005 
     4006        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl; 
     4007 
     4008        // should maybe be done here to allow merge working  
     4009        // with area or volume and to correct the rendering statistics 
     4010        if (0) FinalizeViewCells(false); 
     4011                 
     4012        ////////// 
     4013        //-- merge the individual view cells 
     4014        MergeViewCells(postProcessRays, objects); 
     4015         
     4016        // refines the merged view cells 
     4017        if (0) RefineViewCells(postProcessRays, objects); 
     4018 
     4019 
     4020        /////////// 
     4021        //-- render simulation after merge + refine 
     4022 
     4023        cout << "\nview cells partition render time before compress" << endl << endl;; 
     4024        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene(); 
     4025        SimulationStatistics ss; 
     4026        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss); 
     4027        cout << ss << endl; 
     4028         
     4029 
     4030        //////////// 
     4031        //-- compression 
     4032 
     4033        if (ViewCellsTreeConstructed() && mCompressViewCells) 
     4034        { 
     4035                int pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot()); 
     4036                Debug << "number of entries before compress: " << pvsEntries << endl; 
     4037 
     4038                mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED); 
     4039 
     4040                pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot()); 
     4041                Debug << "number of entries after compress: " << pvsEntries << endl; 
     4042        } 
     4043 
     4044 
     4045        // collapse sibling leaves that share the same view cell 
     4046        if (0) mVspBspTree->CollapseTree(); 
     4047 
     4048        // recompute view cell list and statistics 
     4049        ResetViewCells(); 
     4050 
     4051        // compute final meshes and volume / area 
     4052        if (1) FinalizeViewCells(true); 
     4053 
     4054        // write view cells to disc 
     4055        if (1 && mExportViewCells) 
     4056        { 
     4057                char filename[100]; 
     4058                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename); 
     4059                ExportViewCells(filename, mExportPvs, objects); 
     4060        } 
     4061 
     4062        return 0; 
     4063} 
     4064 
     4065 
     4066int VspBspViewCellsManager::GetType() const 
     4067{ 
     4068        return VSP_BSP; 
     4069} 
     4070 
     4071 
     4072ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root) 
     4073{ 
     4074        // terminate recursion 
     4075        if (root->IsLeaf()) 
     4076        { 
     4077                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root); 
     4078                leaf->GetViewCell()->SetMergeCost(0.0f); 
     4079                return leaf->GetViewCell(); 
     4080        } 
     4081         
     4082         
     4083        BspInterior *interior = dynamic_cast<BspInterior *>(root); 
     4084        ViewCellInterior *viewCellInterior = new ViewCellInterior(); 
     4085                 
     4086        // evaluate merge cost for priority traversal 
     4087        float mergeCost = 1.0f / (float)root->mTimeStamp; 
     4088        viewCellInterior->SetMergeCost(mergeCost); 
     4089 
     4090        float volume = 0; 
     4091         
     4092        BspNode *front = interior->GetFront(); 
     4093        BspNode *back = interior->GetBack(); 
     4094 
     4095 
     4096        ObjectPvs frontPvs, backPvs; 
     4097 
     4098        //-- recursivly compute child hierarchies 
     4099        ViewCell *backVc = ConstructSpatialMergeTree(back); 
     4100        ViewCell *frontVc = ConstructSpatialMergeTree(front); 
     4101 
     4102 
     4103        viewCellInterior->SetupChildLink(backVc); 
     4104        viewCellInterior->SetupChildLink(frontVc); 
     4105 
     4106        volume += backVc->GetVolume(); 
     4107        volume += frontVc->GetVolume();  
     4108 
     4109        viewCellInterior->SetVolume(volume); 
     4110 
     4111        return viewCellInterior; 
     4112} 
     4113 
     4114 
     4115bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const 
     4116{ 
     4117        if (!ViewCellsConstructed()) 
     4118                return ViewCellsManager::GetViewPoint(viewPoint); 
     4119 
     4120        // TODO: set reasonable limit 
     4121        const int limit = 20; 
     4122 
     4123        for (int i = 0; i < limit; ++ i) 
     4124        { 
     4125                viewPoint = mViewSpaceBox.GetRandomPoint(); 
     4126                if (mVspBspTree->ViewPointValid(viewPoint)) 
     4127                { 
     4128                        return true; 
     4129                } 
     4130        } 
     4131 
     4132        Debug << "failed to find valid view point, taking " << viewPoint << endl; 
     4133        return false; 
     4134} 
     4135 
     4136 
     4137bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const 
     4138{ 
     4139        // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic 
     4140        // validy update in preprocessor for all managers) 
     4141        return ViewCellsManager::ViewPointValid(viewPoint); 
     4142 
     4143        //      return mViewSpaceBox.IsInside(viewPoint) && 
     4144        //                 mVspBspTree->ViewPointValid(viewPoint); 
     4145} 
     4146 
     4147 
     4148void VspBspViewCellsManager::Visualize(const ObjectContainer &objects, 
     4149                                                                           const VssRayContainer &sampleRays) 
     4150{ 
     4151        if (!ViewCellsConstructed()) 
     4152                return; 
     4153 
     4154        VssRayContainer visRays; 
     4155        GetRaySets(sampleRays, mVisualizationSamples, visRays); 
     4156         
     4157        if (1)  
     4158        {        
     4159                ////////////////// 
     4160                //-- export final view cell partition 
     4161 
     4162                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl"); 
     4163                 
     4164                if (exporter) 
     4165                { 
     4166                        cout << "exporting view cells after post process ... "; 
     4167                        if (0) 
     4168                        {       // export view space box 
     4169                                exporter->SetWireframe(); 
     4170                                exporter->ExportBox(mViewSpaceBox); 
     4171                                exporter->SetFilled(); 
     4172                        } 
     4173 
     4174                        Material m;  
     4175                        m.mDiffuseColor.r = 0.0f; 
     4176                        m.mDiffuseColor.g = 0.5f; 
     4177                        m.mDiffuseColor.b = 0.5f; 
     4178 
     4179            exporter->SetForcedMaterial(m); 
     4180 
     4181                        if (1 && mExportGeometry) 
     4182                        { 
     4183                                exporter->ExportGeometry(objects); 
     4184                        } 
     4185 
     4186                        if (0 && mExportRays) 
     4187                        { 
     4188                                exporter->ExportRays(visRays, RgbColor(1, 0, 0)); 
     4189                        } 
     4190                        ExportViewCellsForViz(exporter, NULL, GetClipPlane()); 
     4191 
     4192                        delete exporter; 
     4193                        cout << "finished" << endl; 
     4194                } 
     4195        } 
     4196 
     4197        //////////////// 
     4198        //-- visualization of the BSP splits 
     4199 
     4200        bool exportSplits = false; 
     4201        Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits); 
     4202 
     4203        if (exportSplits) 
     4204        { 
     4205                cout << "exporting splits ... "; 
     4206                ExportSplits(objects, visRays); 
     4207                cout << "finished" << endl; 
     4208        } 
     4209 
     4210        //////// 
     4211        //-- export single view cells 
     4212         
     4213        int leafOut; 
     4214        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut); 
     4215        const int raysOut = 100; 
     4216         
     4217        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, ""); 
     4218} 
     4219 
     4220 
     4221void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects, 
     4222                                                                                  const VssRayContainer &rays) 
     4223{ 
     4224        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d"); 
     4225 
     4226        if (exporter) 
     4227        { 
     4228                Material m; 
     4229                m.mDiffuseColor = RgbColor(1, 0, 0); 
     4230                exporter->SetForcedMaterial(m); 
     4231                exporter->SetWireframe(); 
     4232 
     4233                exporter->ExportBspSplits(*mVspBspTree, true); 
     4234 
     4235                // take forced material, else big scenes cannot be viewed 
     4236                m.mDiffuseColor = RgbColor(0, 1, 0); 
     4237                exporter->SetForcedMaterial(m); 
     4238                exporter->SetFilled(); 
     4239 
     4240                exporter->ResetForcedMaterial(); 
     4241 
     4242                // export rays 
     4243                if (mExportRays) 
     4244                { 
     4245                        exporter->ExportRays(rays, RgbColor(1, 1, 0)); 
     4246                } 
     4247 
     4248                if (mExportGeometry) 
     4249                { 
     4250                        exporter->ExportGeometry(objects); 
     4251                } 
     4252                delete exporter; 
     4253        } 
     4254} 
     4255 
     4256 
     4257void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects, 
     4258                                                                                                   const int maxViewCells, 
     4259                                                                                                   const bool sortViewCells, 
     4260                                                                                                   const bool exportPvs, 
     4261                                                                                                   const bool exportRays, 
     4262                                                                                                   const int maxRays, 
     4263                                                                                                   const string prefix, 
     4264                                                                                                   VssRayContainer *visRays) 
     4265{        
     4266        if (sortViewCells) 
     4267        { 
     4268                // sort view cells to visualize the largest view cells 
     4269                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost); 
     4270        } 
     4271 
     4272        ////////// 
     4273        //-- some view cells for output 
     4274 
     4275        ViewCell::NewMail(); 
     4276        const int limit = min(maxViewCells, (int)mViewCells.size()); 
     4277         
     4278        for (int i = 0; i < limit; ++ i) 
     4279        { 
     4280                cout << "creating output for view cell " << i << " ... "; 
     4281 
     4282                ViewCell *vc = sortViewCells ? // largest view cell pvs first? 
     4283                        mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i]; 
     4284 
     4285                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID) 
     4286                        continue; 
     4287 
     4288                vc->Mail(); 
     4289 
     4290                ObjectPvs pvs; 
     4291                mViewCellsTree->GetPvs(vc, pvs); 
     4292 
    28934293                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i); 
    28944294                Exporter *exporter = Exporter::GetExporter(s); 
    28954295                 
    2896                 cout << "view cell " << idx << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl; 
     4296                const int pvsSize = (int)mViewCellsTree->GetPvsSize(vc); 
     4297                cout << "view cell " << vc->GetId() << ": pvs size=" << pvsSize << endl; 
    28974298 
    28984299                if (exportRays) 
     
    29224323 
    29234324                        const int raysOut = min((int)collectRays.size(), maxRays); 
    2924 cout << "here500 " << raysOut << endl; 
     4325                 
    29254326                        // prepare some rays for output 
    29264327                        VssRayContainer::const_iterator rit, rit_end = collectRays.end(); 
     
    29344335                                } 
    29354336                        } 
     4337 
    29364338                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1)); 
    29374339                } 
     
    29634365                                { 
    29644366                                        intersect->Mail(); 
     4367 
    29654368                                        m = RandomMaterial(); 
    29664369                                        exporter->SetForcedMaterial(m); 
    29674370                                        exporter->ExportIntersectable(intersect); 
    2968                                         cout << " i: " << intersect; 
    2969                                 } 
    2970                         } 
    2971                         cout << endl; 
    2972                 } 
    2973                  
    2974                 DEL_PTR(exporter); 
    2975                 cout << "finished" << endl; 
    2976         } 
    2977 } 
    2978  
    2979  
    2980 void BspViewCellsManager::TestSubdivision() 
    2981 { 
    2982         ViewCellContainer leaves; 
    2983         mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves); 
    2984  
    2985         ViewCellContainer::const_iterator it, it_end = leaves.end(); 
    2986  
    2987         const float vol = mViewSpaceBox.GetVolume(); 
    2988         float subdivVol = 0; 
    2989         float newVol = 0; 
    2990  
    2991         for (it = leaves.begin(); it != it_end; ++ it) 
    2992         { 
    2993                 BspNodeGeometry geom; 
    2994                 mBspTree->ConstructGeometry(*it, geom); 
    2995  
    2996                 const float lVol = geom.GetVolume(); 
    2997                 newVol += lVol; 
    2998                 subdivVol += (*it)->GetVolume(); 
    2999  
    3000                 const float thres = 0.9f; 
    3001                 if ((lVol < ((*it)->GetVolume() * thres)) || 
    3002                         (lVol * thres > ((*it)->GetVolume()))) 
    3003                         Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl; 
    3004         } 
    3005          
    3006         Debug << "exact volume: " << vol << endl; 
    3007         Debug << "subdivision volume: " << subdivVol << endl; 
    3008         Debug << "new volume: " << newVol << endl; 
    3009 } 
    3010  
    3011  
    3012 void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 
    3013                                                                                                  ViewCell *vc, 
    3014                                                                                                  const AxisAlignedBox3 *sceneBox, 
    3015                                                                                                  const AxisAlignedPlane *clipPlane 
    3016                                                                                                  ) const 
    3017 { 
    3018         if (clipPlane) 
    3019         { 
    3020                 const Plane3 plane = clipPlane->GetPlane(); 
    3021  
    3022                 ViewCellContainer leaves; 
    3023                 mViewCellsTree->CollectLeaves(vc, leaves); 
    3024                 ViewCellContainer::const_iterator it, it_end = leaves.end(); 
    3025  
    3026                 for (it = leaves.begin(); it != it_end; ++ it) 
    3027                 { 
    3028                         BspNodeGeometry geom; 
    3029                         BspNodeGeometry front; 
    3030                         BspNodeGeometry back; 
    3031  
    3032                         mBspTree->ConstructGeometry(*it, geom); 
    3033  
    3034                         const float eps = 0.0001f; 
    3035                         const int cf = geom.Side(plane, eps); 
    3036  
    3037                         if (cf == -1) 
    3038                         { 
    3039                                 exporter->ExportPolygons(geom.GetPolys()); 
    3040                         } 
    3041                         else if (cf == 0) 
    3042                         { 
    3043                                 geom.SplitGeometry(front, 
    3044                                                                    back, 
    3045                                                                    plane, 
    3046                                                                    mViewSpaceBox,  
    3047                                                                    eps); 
    3048  
    3049                                 if (back.Valid()) 
    3050                                 { 
    3051                                         exporter->ExportPolygons(back.GetPolys()); 
    3052                                 }                        
    3053                         } 
    3054                 } 
    3055         } 
    3056         else 
    3057         { 
    3058                 // export mesh if available 
    3059                 // TODO: some bug here? 
    3060                 if (1 && vc->GetMesh()) 
    3061                 { 
    3062                         exporter->ExportMesh(vc->GetMesh()); 
    3063                 } 
    3064                 else 
    3065                 { 
    3066                         BspNodeGeometry geom; 
    3067                         mBspTree->ConstructGeometry(vc, geom); 
    3068                         exporter->ExportPolygons(geom.GetPolys()); 
    3069                 } 
    3070         } 
    3071 } 
    3072  
    3073  
    3074 void BspViewCellsManager::CreateMesh(ViewCell *vc) 
    3075 { 
    3076         // note: should previous mesh be deleted (via mesh manager?) 
    3077         BspNodeGeometry geom; 
    3078         mBspTree->ConstructGeometry(vc, geom); 
    3079  
    3080         Mesh *mesh = MeshManager::GetSingleton()->CreateResource(); 
    3081  
    3082         IncludeNodeGeomInMesh(geom, *mesh); 
    3083         vc->SetMesh(mesh); 
    3084 } 
    3085  
    3086  
    3087 void BspViewCellsManager::Finalize(ViewCell *viewCell,  
    3088                                                                    const bool createMesh) 
    3089 { 
    3090         float area = 0; 
    3091         float volume = 0; 
    3092  
    3093         ViewCellContainer leaves; 
    3094         mViewCellsTree->CollectLeaves(viewCell, leaves); 
    3095  
    3096         ViewCellContainer::const_iterator it, it_end = leaves.end(); 
    3097  
    3098     for (it = leaves.begin(); it != it_end; ++ it) 
    3099         { 
    3100                 BspNodeGeometry geom; 
    3101  
    3102                 mBspTree->ConstructGeometry(*it, geom); 
    3103  
    3104                 const float lVol = geom.GetVolume(); 
    3105                 const float lArea = geom.GetArea(); 
    3106  
    3107                 area += lArea; 
    3108                 volume += lVol; 
    3109          
    3110                 CreateMesh(*it); 
    3111         } 
    3112  
    3113         viewCell->SetVolume(volume); 
    3114         viewCell->SetArea(area); 
    3115 } 
    3116  
    3117  
    3118 ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const 
    3119 { 
    3120         if (!ViewCellsConstructed()) 
    3121         { 
    3122                 return NULL; 
    3123         } 
    3124         if (!mViewSpaceBox.IsInside(point)) 
    3125         { 
    3126                 return NULL; 
    3127         } 
    3128         return mBspTree->GetViewCell(point); 
    3129 } 
    3130  
    3131  
    3132 void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,  
    3133                                                                                                  vector<MergeCandidate> &candidates) 
    3134 { 
    3135         cout << "collecting merge candidates ... " << endl; 
    3136  
    3137         if (mUseRaysForMerge) 
    3138         { 
    3139                 mBspTree->CollectMergeCandidates(rays, candidates); 
    3140         } 
    3141         else 
    3142         { 
    3143                 vector<BspLeaf *> leaves; 
    3144                 mBspTree->CollectLeaves(leaves); 
    3145                 mBspTree->CollectMergeCandidates(leaves, candidates); 
    3146         } 
    3147  
    3148         cout << "fininshed collecting candidates" << endl; 
    3149 } 
    3150  
    3151  
    3152  
    3153 bool BspViewCellsManager::ExportViewCells(const string filename,  
    3154                                                                                   const bool exportPvs,  
    3155                                                                                   const ObjectContainer &objects) 
    3156 { 
    3157         if (!ViewCellsConstructed() || !ViewCellsTreeConstructed()) 
    3158         { 
    3159                 return false; 
    3160         } 
    3161  
    3162         cout << "exporting view cells to xml ... "; 
    3163  
    3164         OUT_STREAM stream(filename.c_str()); 
    3165  
    3166         // for output we need unique ids for each view cell 
    3167         CreateUniqueViewCellIds(); 
    3168  
    3169         stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl; 
    3170         stream << "<VisibilitySolution>" << endl; 
    3171  
    3172         if (exportPvs)  
    3173         { 
    3174                 ////////// 
    3175                 //-- export bounding boxes: they are used to identify the objects from the pvs and 
    3176                 //-- assign them to the entities in the rendering engine 
    3177  
    3178                 stream << "<BoundingBoxes>" << endl; 
    3179                 ObjectContainer::const_iterator oit, oit_end = objects.end(); 
    3180  
    3181                 for (oit = objects.begin(); oit != oit_end; ++ oit) 
    3182                 { 
    3183                         const AxisAlignedBox3 box = (*oit)->GetBox(); 
    3184                          
    3185                         stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\"" 
    3186                                    << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\"" 
    3187                                    << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl; 
    3188                 } 
    3189  
    3190                 stream << "</BoundingBoxes>" << endl; 
    3191         } 
    3192  
    3193         /////////// 
    3194         //-- export the view cells and the pvs 
    3195  
    3196         const int numViewCells = mCurrentViewCellsStats.viewCells; 
    3197         stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl; 
    3198  
    3199         mViewCellsTree->Export(stream, exportPvs); 
    3200          
    3201         stream << "</ViewCells>" << endl; 
    3202  
    3203         ///////////// 
    3204         //-- export the view space hierarchy 
    3205         stream << "<ViewSpaceHierarchy type=\"bsp\"" 
    3206                    << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\"" 
    3207                    << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl; 
    3208  
    3209         mBspTree->Export(stream); 
    3210  
    3211         // end tags 
    3212         stream << "</ViewSpaceHierarchy>" << endl; 
    3213         stream << "</VisibilitySolution>" << endl; 
    3214  
    3215         stream.close(); 
    3216         cout << "finished" << endl; 
    3217  
    3218         return true; 
    3219 } 
    3220  
    3221  
    3222 ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root) 
    3223 { 
    3224         ViewCellInterior *vcRoot = new ViewCellInterior(); 
    3225                  
    3226         // evaluate merge cost for priority traversal 
    3227         const float mergeCost = 1.0f / (float)root->mTimeStamp; 
    3228         vcRoot->SetMergeCost(mergeCost); 
    3229  
    3230         float volume = 0; 
    3231         vector<BspLeaf *> leaves; 
    3232         mBspTree->CollectLeaves(leaves); 
    3233         vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end(); 
    3234         ViewCell::NewMail(); 
    3235  
    3236         for (lit = leaves.begin(); lit != lit_end; ++ lit) 
    3237         { 
    3238                 BspLeaf *leaf = *lit; 
    3239                 ViewCell *vc = leaf->GetViewCell(); 
    3240  
    3241                 if (!vc->Mailed()) 
    3242                 { 
    3243                         vc->Mail(); 
    3244                         vc->SetMergeCost(0.0f); 
    3245                         vcRoot->SetupChildLink(vc); 
    3246  
    3247                         volume += vc->GetVolume(); 
    3248                         volume += vc->GetVolume();       
    3249                         vcRoot->SetVolume(volume); 
    3250                 } 
    3251         } 
    3252          
    3253         return vcRoot; 
    3254 } 
    3255  
    3256  
    3257 ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root) 
    3258 { 
    3259         // terminate recursion 
    3260         if (root->IsLeaf()) 
    3261         { 
    3262                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(root); 
    3263                 leaf->GetViewCell()->SetMergeCost(0.0f); 
    3264                 return leaf->GetViewCell(); 
    3265         } 
    3266          
    3267         BspInterior *interior = dynamic_cast<BspInterior *>(root); 
    3268         ViewCellInterior *viewCellInterior = new ViewCellInterior(); 
    3269                  
    3270         // evaluate merge cost for priority traversal 
    3271         float mergeCost = 1.0f / (float)root->mTimeStamp; 
    3272         viewCellInterior->SetMergeCost(mergeCost); 
    3273  
    3274         float volume = 0; 
    3275          
    3276         BspNode *front = interior->GetFront(); 
    3277         BspNode *back = interior->GetBack(); 
    3278  
    3279  
    3280         //////////// 
    3281         //-- recursivly compute child hierarchies 
    3282  
    3283         ViewCell *backVc = ConstructSpatialMergeTree(back); 
    3284         ViewCell *frontVc = ConstructSpatialMergeTree(front); 
    3285  
    3286         viewCellInterior->SetupChildLink(backVc); 
    3287         viewCellInterior->SetupChildLink(frontVc); 
    3288  
    3289         volume += backVc->GetVolume(); 
    3290         volume += frontVc->GetVolume();  
    3291  
    3292         viewCellInterior->SetVolume(volume); 
    3293  
    3294         return viewCellInterior; 
    3295 } 
    3296  
    3297  
    3298 /************************************************************************/ 
    3299 /*                   KdViewCellsManager implementation                  */ 
    3300 /************************************************************************/ 
    3301  
    3302  
    3303  
    3304 KdViewCellsManager::KdViewCellsManager(ViewCellsTree *vcTree, KdTree *kdTree): 
    3305 ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100) 
    3306 { 
    3307 } 
    3308  
    3309  
    3310 float KdViewCellsManager::GetProbability(ViewCell *viewCell) 
    3311 { 
    3312         // compute view cell area / volume as subsititute for probability 
    3313         if (0) 
    3314                 return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea(); 
    3315         else 
    3316                 return GetVolume(viewCell) / GetViewSpaceBox().GetVolume(); 
    3317 } 
    3318  
    3319  
    3320  
    3321  
    3322 void KdViewCellsManager::CollectViewCells() 
    3323 { 
    3324         //mKdTree->CollectViewCells(mViewCells); TODO 
    3325 } 
    3326  
    3327  
    3328 int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects, 
    3329                                                                   const VssRayContainer &rays) 
    3330 { 
    3331         // if view cells already constructed 
    3332         if (ViewCellsConstructed()) 
    3333                 return 0; 
    3334  
    3335         mKdTree->Construct(); 
    3336  
    3337         mTotalAreaValid = false; 
    3338         // create the view cells 
    3339         mKdTree->CreateAndCollectViewCells(mViewCells); 
    3340         // cast rays 
    3341         ComputeSampleContributions(rays, true, false); 
    3342  
    3343         EvaluateViewCellsStats(); 
    3344         Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl; 
    3345  
    3346         return 0; 
    3347 } 
    3348  
    3349  
    3350 bool KdViewCellsManager::ViewCellsConstructed() const 
    3351 { 
    3352         return mKdTree->GetRoot() != NULL; 
    3353 } 
    3354  
    3355  
    3356 int KdViewCellsManager::PostProcess(const ObjectContainer &objects, 
    3357                                                                         const VssRayContainer &rays) 
    3358 { 
    3359         return 0; 
    3360 } 
    3361  
    3362  
    3363 void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects, 
    3364                                                                                            const int maxViewCells, 
    3365                                                                                            const bool sortViewCells, 
    3366                                                                                            const bool exportPvs, 
    3367                                                                                            const bool exportRays, 
    3368                                                                                            const int maxRays, 
    3369                                                                                            const string prefix, 
    3370                                                                                            VssRayContainer *visRays) 
    3371 { 
    3372         // TODO 
    3373 } 
    3374  
    3375  
    3376 void KdViewCellsManager::Visualize(const ObjectContainer &objects, 
    3377                                                                    const VssRayContainer &sampleRays) 
    3378 { 
    3379         if (!ViewCellsConstructed()) 
    3380                 return; 
    3381  
    3382         // using view cells instead of the kd PVS of objects 
    3383         const bool useViewCells = true; 
    3384         bool exportRays = false; 
    3385  
    3386         int limit = min(mVisualizationSamples, (int)sampleRays.size()); 
    3387         const int pvsOut = min((int)objects.size(), 10); 
    3388         VssRayContainer *rays = new VssRayContainer[pvsOut]; 
    3389  
    3390         if (useViewCells) 
    3391         { 
    3392                 const int leafOut = 10; 
    3393  
    3394                 ViewCell::NewMail(); 
    3395  
    3396                 //-- some rays for output 
    3397                 const int raysOut = min((int)sampleRays.size(), mVisualizationSamples); 
    3398                 Debug << "visualization using " << raysOut << " samples" << endl; 
    3399  
    3400                 //-- some random view cells and rays for output 
    3401                 vector<KdLeaf *> kdLeaves; 
    3402  
    3403                 for (int i = 0; i < leafOut; ++ i) 
    3404                         kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf())); 
    3405  
    3406                 for (int i = 0; i < kdLeaves.size(); ++ i) 
    3407                 { 
    3408                         KdLeaf *leaf = kdLeaves[i]; 
    3409                         RayContainer vcRays; 
    3410  
    3411                         cout << "creating output for view cell " << i << " ... "; 
    3412 #if 0 
    3413                         // check whether we can add the current ray to the output rays 
    3414                         for (int k = 0; k < raysOut; ++ k) 
    3415                         { 
    3416                                 Ray *ray = sampleRays[k]; 
    3417  
    3418                                 for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j) 
    3419                                 { 
    3420                                         BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf; 
    3421  
    3422                                         if (leaf->GetViewCell() == leaf2->GetViewCell()) 
    3423                                         { 
    3424                                                 vcRays.push_back(ray); 
    3425                                         } 
    3426                                 } 
    3427                         } 
    3428 #endif 
    3429                         Intersectable::NewMail(); 
    3430  
    3431                         ViewCell *vc = leaf->mViewCell; 
    3432                         char str[64]; sprintf(str, "viewcell%04d.wrl", i); 
    3433  
    3434                         Exporter *exporter = Exporter::GetExporter(str); 
    3435                         exporter->SetFilled(); 
    3436  
    3437                         exporter->SetWireframe(); 
    3438                         //exporter->SetFilled(); 
    3439  
    3440                         Material m;//= RandomMaterial(); 
    3441                         m.mDiffuseColor = RgbColor(1, 1, 0); 
    3442                         exporter->SetForcedMaterial(m); 
    3443  
    3444                         AxisAlignedBox3 box = mKdTree->GetBox(leaf); 
    3445                         exporter->ExportBox(box); 
    3446  
    3447                         // export rays piercing this view cell 
    3448                         exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0)); 
    3449  
    3450                         m.mDiffuseColor = RgbColor(1, 0, 0); 
    3451                         exporter->SetForcedMaterial(m); 
    3452  
    3453                         // exporter->SetWireframe(); 
    3454                         exporter->SetFilled(); 
    3455  
    3456                         ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end(); 
    3457                         // -- output PVS of view cell 
    3458                         for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
    3459                         { 
    3460                                 Intersectable *intersect = (*it).first; 
    3461                                 if (!intersect->Mailed()) 
    3462                                 { 
    3463                                         exporter->ExportIntersectable(intersect); 
    3464                                         intersect->Mail(); 
    3465                                 } 
    3466                         } 
    3467  
    3468                         DEL_PTR(exporter); 
    3469                         cout << "finished" << endl; 
    3470                 } 
    3471  
    3472                 DEL_PTR(rays); 
    3473         } 
    3474         else // using kd PVS of objects 
    3475         { 
    3476                 for (int i = 0; i < limit; ++ i) 
    3477                 { 
    3478                         VssRay *ray = sampleRays[i]; 
    3479  
    3480                         // check whether we can add this to the rays 
    3481                         for (int j = 0; j < pvsOut; j++) 
    3482                         { 
    3483                                 if (objects[j] == ray->mTerminationObject) 
    3484                                 { 
    3485                                         rays[j].push_back(ray); 
    3486                                 } 
    3487                         } 
    3488                 } 
    3489  
    3490                 if (exportRays) 
    3491                 { 
    3492                         Exporter *exporter = NULL; 
    3493                         exporter = Exporter::GetExporter("sample-rays.x3d"); 
    3494                         exporter->SetWireframe(); 
    3495                         exporter->ExportKdTree(*mKdTree); 
    3496  
    3497                         for (i = 0; i < pvsOut; i++) 
    3498                                 exporter->ExportRays(rays[i], RgbColor(1, 0, 0)); 
    3499  
    3500                         exporter->SetFilled(); 
    3501                         delete exporter; 
    3502                 } 
    3503  
    3504                 for (int k=0; k < pvsOut; k++) 
    3505                 { 
    3506                         Intersectable *object = objects[k]; 
    3507                         char str[64]; sprintf(str, "viewcell%04d.wrl", i); 
    3508  
    3509                         Exporter *exporter = Exporter::GetExporter(str); 
    3510                         exporter->SetWireframe(); 
    3511  
    3512                         KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin(); 
    3513                         Intersectable::NewMail(); 
    3514  
    3515                         // avoid adding the object to the list 
    3516                         object->Mail(); 
    3517                         ObjectContainer visibleObjects; 
    3518  
    3519                         for (; kit != object->mKdPvs.mEntries.end(); i++) 
    3520                         { 
    3521                                 KdNode *node = (*kit).first; 
    3522                                 exporter->ExportBox(mKdTree->GetBox(node)); 
    3523  
    3524                                 mKdTree->CollectObjects(node, visibleObjects); 
    3525                         } 
    3526  
    3527                         exporter->ExportRays(rays[k],  RgbColor(0, 1, 0)); 
    3528                         exporter->SetFilled(); 
    3529  
    3530                         for (int j = 0; j < visibleObjects.size(); j++) 
    3531                                 exporter->ExportIntersectable(visibleObjects[j]); 
    3532  
    3533                         Material m; 
    3534                         m.mDiffuseColor = RgbColor(1, 0, 0); 
    3535                         exporter->SetForcedMaterial(m); 
    3536                         exporter->ExportIntersectable(object); 
    3537  
    3538                         delete exporter; 
    3539                 } 
    3540         } 
    3541 } 
    3542  
    3543  
    3544 ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const 
    3545 { 
    3546         return new KdViewCell(mesh); 
    3547 } 
    3548  
    3549  
    3550 void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 
    3551                                                                                                 ViewCell *vc, 
    3552                                                                                                 const AxisAlignedBox3 *sceneBox, 
    3553                                                                                                 const AxisAlignedPlane *clipPlane 
    3554                                                                                                 ) const 
    3555 { 
    3556         ViewCellContainer leaves; 
    3557         mViewCellsTree->CollectLeaves(vc, leaves); 
    3558         ViewCellContainer::const_iterator it, it_end = leaves.end(); 
    3559  
    3560         for (it = leaves.begin(); it != it_end; ++ it) 
    3561         { 
    3562                 KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it); 
    3563                 exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0])); 
    3564         } 
    3565 } 
    3566  
    3567  
    3568 int KdViewCellsManager::GetType() const 
    3569 { 
    3570         return ViewCellsManager::KD; 
    3571 } 
    3572  
    3573  
    3574  
    3575 KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf) 
    3576 { 
    3577         KdNode *node = leaf; 
    3578  
    3579         while (node->mParent && node->mDepth > mKdPvsDepth) 
    3580                 node = node->mParent; 
    3581  
    3582         return node; 
    3583 } 
    3584  
    3585 int KdViewCellsManager::CastLineSegment(const Vector3 &origin, 
    3586                                                                                 const Vector3 &termination, 
    3587                                                                                 ViewCellContainer &viewcells) 
    3588 { 
    3589         return mKdTree->CastLineSegment(origin, termination, viewcells); 
    3590 } 
    3591  
    3592  
    3593 void KdViewCellsManager::CreateMesh(ViewCell *vc) 
    3594 { 
    3595         // TODO 
    3596 } 
    3597  
    3598  
    3599  
    3600 void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,  
    3601                                                                                                 vector<MergeCandidate> &candidates) 
    3602 { 
    3603         // TODO 
    3604 } 
    3605  
    3606  
    3607  
    3608 /**************************************************************************/ 
    3609 /*                   VspBspViewCellsManager implementation                */ 
    3610 /**************************************************************************/ 
    3611  
    3612  
    3613 VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree): 
    3614 ViewCellsManager(vcTree), mVspBspTree(vspBspTree) 
    3615 { 
    3616         Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples); 
    3617         mVspBspTree->SetViewCellsManager(this); 
    3618         mVspBspTree->mViewCellsTree = mViewCellsTree; 
    3619 } 
    3620  
    3621  
    3622 VspBspViewCellsManager::~VspBspViewCellsManager() 
    3623 { 
    3624 } 
    3625  
    3626  
    3627 float VspBspViewCellsManager::GetProbability(ViewCell *viewCell) 
    3628 { 
    3629         if (0 && mVspBspTree->mUseAreaForPvs) 
    3630                 return GetArea(viewCell) / GetAccVcArea(); 
    3631         else 
    3632                 return GetVolume(viewCell) / mViewSpaceBox.GetVolume(); 
    3633 } 
    3634  
    3635  
    3636 void VspBspViewCellsManager::CollectViewCells() 
    3637 { 
    3638         // view cells tree constructed? 
    3639         if (!ViewCellsTreeConstructed()) 
    3640         { 
    3641                 mVspBspTree->CollectViewCells(mViewCells, false); 
    3642         } 
    3643         else  
    3644         {        
    3645                 // we can use the view cells tree hierarchy to get the right set 
    3646                 mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells); 
    3647         } 
    3648 } 
    3649  
    3650  
    3651 void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,  
    3652                                                                                                         vector<MergeCandidate> &candidates) 
    3653 {        
    3654         cout << "collecting merge candidates ... " << endl; 
    3655  
    3656         if (mUseRaysForMerge) 
    3657         { 
    3658                 mVspBspTree->CollectMergeCandidates(rays, candidates); 
    3659         } 
    3660         else 
    3661         { 
    3662                 vector<BspLeaf *> leaves; 
    3663                 mVspBspTree->CollectLeaves(leaves); 
    3664          
    3665                 mVspBspTree->CollectMergeCandidates(leaves, candidates); 
    3666         } 
    3667  
    3668         cout << "fininshed collecting candidates" << endl; 
    3669 } 
    3670  
    3671  
    3672 bool VspBspViewCellsManager::ViewCellsConstructed() const 
    3673 { 
    3674         return mVspBspTree->GetRoot() != NULL; 
    3675 } 
    3676  
    3677  
    3678 ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const 
    3679 { 
    3680         return new BspViewCell(mesh); 
    3681 } 
    3682  
    3683  
    3684 int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects, 
    3685                                                                                                  const VssRayContainer &rays) 
    3686 { 
    3687         mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size()); 
    3688  
    3689         // if view cells were already constructed 
    3690         if (ViewCellsConstructed()) 
    3691         { 
    3692                 return 0; 
    3693         } 
    3694  
    3695         int sampleContributions = 0; 
    3696         VssRayContainer sampleRays; 
    3697  
    3698         const int limit = min(mInitialSamples, (int)rays.size()); 
    3699  
    3700         Debug << "samples used for vsp bsp subdivision: " << mInitialSamples  
    3701                   << ", actual rays: " << (int)rays.size() << endl; 
    3702  
    3703         VssRayContainer savedRays; 
    3704  
    3705         if (SAMPLE_AFTER_SUBDIVISION) 
    3706         { 
    3707                 VssRayContainer constructionRays; 
    3708                  
    3709                 GetRaySets(rays, mInitialSamples, constructionRays, &savedRays); 
    3710  
    3711                 Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl; 
    3712                 Debug << "rays saved for later use: " << (int)savedRays.size() << endl; 
    3713          
    3714                 mVspBspTree->Construct(constructionRays, &mViewSpaceBox); 
    3715         } 
    3716         else 
    3717         { 
    3718                 Debug << "rays used for initial construction: " << (int)rays.size() << endl; 
    3719                 mVspBspTree->Construct(rays, &mViewSpaceBox); 
    3720         } 
    3721  
    3722         // collapse invalid regions 
    3723         cout << "collapsing invalid tree regions ... "; 
    3724         long startTime = GetTime(); 
    3725  
    3726         const int collapsedLeaves = mVspBspTree->CollapseTree(); 
    3727         Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3  
    3728                   << " seconds" << endl; 
    3729  
    3730     cout << "finished" << endl; 
    3731  
    3732         ///////////////// 
    3733         //-- stats after construction 
    3734  
    3735         Debug << mVspBspTree->GetStatistics() << endl; 
    3736  
    3737         ResetViewCells(); 
    3738         Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl; 
    3739  
    3740  
    3741         ////////////////////// 
    3742         //-- recast the rest of the rays 
    3743  
    3744         startTime = GetTime(); 
    3745  
    3746         cout << "Computing remaining ray contributions ... "; 
    3747  
    3748         if (SAMPLE_AFTER_SUBDIVISION) 
    3749                 ComputeSampleContributions(savedRays, true, false); 
    3750  
    3751         cout << "finished" << endl; 
    3752  
    3753         Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3 
    3754                   << " secs" << endl; 
    3755  
    3756         cout << "construction finished" << endl; 
    3757  
    3758         if (0) 
    3759         {       //////// 
    3760                 //-- real meshes are contructed at this stage 
    3761                 cout << "finalizing view cells ... "; 
    3762                 FinalizeViewCells(true); 
    3763                 cout << "finished" << endl; 
    3764         } 
    3765  
    3766         return sampleContributions; 
    3767 } 
    3768  
    3769  
    3770 void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays, 
    3771                                                                                         const ObjectContainer &objects) 
    3772 { 
    3773     int vcSize = 0; 
    3774         int pvsSize = 0; 
    3775  
    3776         //-- merge view cells 
    3777         cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl; 
    3778         long startTime = GetTime(); 
    3779  
    3780  
    3781         if (mMergeViewCells) 
    3782         { 
    3783                 // TODO: should be done BEFORE the ray casting 
    3784                 // compute tree by merging the nodes based on cost heuristics 
    3785                 mViewCellsTree->ConstructMergeTree(rays, objects); 
    3786         } 
    3787         else 
    3788         { 
    3789                 // compute tree by merging the nodes of the spatial hierarchy 
    3790                 ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot()); 
    3791                 mViewCellsTree->SetRoot(root); 
    3792  
    3793                 // compute pvs 
    3794                 ObjectPvs pvs; 
    3795                 UpdatePvsForEvaluation(root, pvs); 
    3796         } 
    3797  
    3798         if (1) 
    3799         { 
    3800                 char mstats[100]; 
    3801                 ObjectPvs pvs; 
    3802  
    3803                 Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats); 
    3804                 mViewCellsTree->ExportStats(mstats); 
    3805         } 
    3806  
    3807         cout << "merged view cells in " 
    3808                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl; 
    3809  
    3810         Debug << "Postprocessing: Merged view cells in " 
    3811                   << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl; 
    3812          
    3813  
    3814         ////////////////// 
    3815         //-- stats and visualizations 
    3816  
    3817         int savedColorCode = mColorCode; 
    3818          
    3819         // get currently active view cell set 
    3820         ResetViewCells(); 
    3821         Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl; 
    3822          
    3823         if (1) // export merged view cells 
    3824         { 
    3825                 mColorCode = 0; 
    3826                 Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl"); 
    3827                  
    3828                 cout << "exporting view cells after merge ... "; 
    3829  
    3830                 if (exporter) 
    3831                 { 
    3832                         if (0) 
    3833                                 exporter->SetWireframe(); 
    3834                         else 
    3835                                 exporter->SetFilled(); 
    3836  
    3837                         ExportViewCellsForViz(exporter, NULL, GetClipPlane()); 
    3838  
    3839                         if (mExportGeometry) 
    3840                         { 
    3841                                 Material m; 
    3842                                 m.mDiffuseColor = RgbColor(0, 1, 0); 
    3843                                 exporter->SetForcedMaterial(m); 
    3844                                 exporter->SetFilled(); 
    3845  
    3846                                 exporter->ExportGeometry(objects); 
    3847                         } 
    3848  
    3849                         delete exporter; 
    3850                 } 
    3851                 cout << "finished" << endl; 
    3852         } 
    3853  
    3854         if (1)  
    3855         { 
    3856                 // use pvs size for color coding 
    3857                 mColorCode = 1; 
    3858                 Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl"); 
    3859  
    3860                 cout << "exporting view cells after merge (pvs size) ... ";      
    3861  
    3862                 if (exporter) 
    3863                 { 
    3864                         exporter->SetFilled(); 
    3865  
    3866                         ExportViewCellsForViz(exporter, NULL, GetClipPlane()); 
    3867  
    3868                         if (mExportGeometry) 
    3869                         { 
    3870                                 Material m; 
    3871                                 m.mDiffuseColor = RgbColor(0, 1, 0); 
    3872                                 exporter->SetForcedMaterial(m); 
    3873                                 exporter->SetFilled(); 
    3874  
    3875                                 exporter->ExportGeometry(objects); 
    3876                         } 
    3877  
    3878                         delete exporter; 
    3879                 } 
    3880                 cout << "finished" << endl; 
    3881         } 
    3882  
    3883         mColorCode = savedColorCode; 
    3884  
    3885 } 
    3886  
    3887  
    3888 bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const 
    3889 { 
    3890         return GetSpatialNode(viewCell) != NULL; 
    3891 } 
    3892  
    3893  
    3894 BspNode *VspBspViewCellsManager::GetSpatialNode(ViewCell *viewCell) const 
    3895 { 
    3896         if (!viewCell->IsLeaf()) 
    3897         { 
    3898                 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(viewCell); 
    3899                 return bspVc->mLeaves[0]; 
    3900         } 
    3901         else 
    3902         { 
    3903                 ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell); 
    3904  
    3905                 // cannot be node of binary tree 
    3906                 if (interior->mChildren.size() != 2) 
    3907                         return NULL; 
    3908  
    3909                 ViewCell *left = interior->mChildren[0]; 
    3910                 ViewCell *right = interior->mChildren[1]; 
    3911  
    3912                 BspNode *leftNode = GetSpatialNode(left); 
    3913                 BspNode *rightNode = GetSpatialNode(right); 
    3914  
    3915                 if (leftNode && rightNode && leftNode->IsSibling(rightNode)) 
    3916                 { 
    3917                         return leftNode->GetParent();  
    3918                 } 
    3919         } 
    3920  
    3921         return NULL; 
    3922 } 
    3923  
    3924  
    3925 void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays, 
    3926                                                                                          const ObjectContainer &objects) 
    3927 { 
    3928         mRenderer->RenderScene(); 
    3929         SimulationStatistics ss; 
    3930         dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss); 
    3931     Debug << "render time before refine\n\n" << ss << endl; 
    3932  
    3933         const long startTime = GetTime(); 
    3934         cout << "Refining the merged view cells ... "; 
    3935  
    3936         // refining the merged view cells 
    3937         const int refined = mViewCellsTree->RefineViewCells(rays, objects); 
    3938  
    3939         //-- stats and visualizations 
    3940         cout << "finished" << endl; 
    3941         cout << "refined " << refined << " view cells in " 
    3942                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl; 
    3943  
    3944         Debug << "Postprocessing: refined " << refined << " view cells in " 
    3945                   << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl; 
    3946 } 
    3947  
    3948  
    3949 int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects, 
    3950                                                                                 const VssRayContainer &rays) 
    3951 { 
    3952         if (!ViewCellsConstructed()) 
    3953         { 
    3954                 Debug << "postprocess error: no view cells constructed" << endl; 
    3955                 return 0; 
    3956         } 
    3957  
    3958         // view cells already finished before post processing step  
    3959         // (i.e. because they were loaded) 
    3960         if (mViewCellsFinished) 
    3961         { 
    3962                 FinalizeViewCells(true); 
    3963                 EvaluateViewCellsStats(); 
    3964  
    3965                 return 0; 
    3966         } 
    3967  
    3968         // check if new view cells turned invalid 
    3969         int minPvs, maxPvs; 
    3970  
    3971         if (0) 
    3972         { 
    3973                 minPvs = mMinPvsSize; 
    3974                 maxPvs = mMaxPvsSize; 
    3975         } 
    3976         else 
    3977         { 
    3978                 // problem matt: why did I start here from zero? 
    3979                 minPvs = 0; 
    3980                 maxPvs = mMaxPvsSize; 
    3981         } 
    3982  
    3983         Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl; 
    3984         cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl; 
    3985          
    3986         SetValidity(minPvs, maxPvs);  
    3987  
    3988         // update valid view space according to valid view cells 
    3989         if (0) mVspBspTree->ValidateTree(); 
    3990  
    3991         // area has to be recomputed 
    3992         mTotalAreaValid = false; 
    3993         VssRayContainer postProcessRays; 
    3994         GetRaySets(rays, mPostProcessSamples, postProcessRays); 
    3995  
    3996         Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl; 
    3997  
    3998         // should maybe be done here to allow merge working  
    3999         // with area or volume and to correct the rendering statistics 
    4000         if (0) FinalizeViewCells(false); 
    4001                  
    4002         ////////// 
    4003         //-- merge the individual view cells 
    4004         MergeViewCells(postProcessRays, objects); 
    4005          
    4006         // refines the merged view cells 
    4007         if (0) RefineViewCells(postProcessRays, objects); 
    4008  
    4009  
    4010         /////////// 
    4011         //-- render simulation after merge + refine 
    4012  
    4013         cout << "\nview cells partition render time before compress" << endl << endl;; 
    4014         dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene(); 
    4015         SimulationStatistics ss; 
    4016         dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss); 
    4017         cout << ss << endl; 
    4018          
    4019  
    4020         //////////// 
    4021         //-- compression 
    4022  
    4023         if (ViewCellsTreeConstructed() && mCompressViewCells) 
    4024         { 
    4025                 int pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot()); 
    4026                 Debug << "number of entries before compress: " << pvsEntries << endl; 
    4027  
    4028                 mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED); 
    4029  
    4030                 pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot()); 
    4031                 Debug << "number of entries after compress: " << pvsEntries << endl; 
    4032         } 
    4033  
    4034  
    4035         // collapse sibling leaves that share the same view cell 
    4036         if (0) mVspBspTree->CollapseTree(); 
    4037  
    4038         // recompute view cell list and statistics 
    4039         ResetViewCells(); 
    4040  
    4041         // compute final meshes and volume / area 
    4042         if (1) FinalizeViewCells(true); 
    4043  
    4044         // write view cells to disc 
    4045         if (1 && mExportViewCells) 
    4046         { 
    4047                 char filename[100]; 
    4048                 Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename); 
    4049                 ExportViewCells(filename, mExportPvs, objects); 
    4050         } 
    4051  
    4052         return 0; 
    4053 } 
    4054  
    4055  
    4056 int VspBspViewCellsManager::GetType() const 
    4057 { 
    4058         return VSP_BSP; 
    4059 } 
    4060  
    4061  
    4062 ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root) 
    4063 { 
    4064         // terminate recursion 
    4065         if (root->IsLeaf()) 
    4066         { 
    4067                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(root); 
    4068                 leaf->GetViewCell()->SetMergeCost(0.0f); 
    4069                 return leaf->GetViewCell(); 
    4070         } 
    4071          
    4072          
    4073         BspInterior *interior = dynamic_cast<BspInterior *>(root); 
    4074         ViewCellInterior *viewCellInterior = new ViewCellInterior(); 
    4075                  
    4076         // evaluate merge cost for priority traversal 
    4077         float mergeCost = 1.0f / (float)root->mTimeStamp; 
    4078         viewCellInterior->SetMergeCost(mergeCost); 
    4079  
    4080         float volume = 0; 
    4081          
    4082         BspNode *front = interior->GetFront(); 
    4083         BspNode *back = interior->GetBack(); 
    4084  
    4085  
    4086         ObjectPvs frontPvs, backPvs; 
    4087  
    4088         //-- recursivly compute child hierarchies 
    4089         ViewCell *backVc = ConstructSpatialMergeTree(back); 
    4090         ViewCell *frontVc = ConstructSpatialMergeTree(front); 
    4091  
    4092  
    4093         viewCellInterior->SetupChildLink(backVc); 
    4094         viewCellInterior->SetupChildLink(frontVc); 
    4095  
    4096         volume += backVc->GetVolume(); 
    4097         volume += frontVc->GetVolume();  
    4098  
    4099         viewCellInterior->SetVolume(volume); 
    4100  
    4101         return viewCellInterior; 
    4102 } 
    4103  
    4104  
    4105 bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const 
    4106 { 
    4107         if (!ViewCellsConstructed()) 
    4108                 return ViewCellsManager::GetViewPoint(viewPoint); 
    4109  
    4110         // TODO: set reasonable limit 
    4111         const int limit = 20; 
    4112  
    4113         for (int i = 0; i < limit; ++ i) 
    4114         { 
    4115                 viewPoint = mViewSpaceBox.GetRandomPoint(); 
    4116                 if (mVspBspTree->ViewPointValid(viewPoint)) 
    4117                 { 
    4118                         return true; 
    4119                 } 
    4120         } 
    4121  
    4122         Debug << "failed to find valid view point, taking " << viewPoint << endl; 
    4123         return false; 
    4124 } 
    4125  
    4126  
    4127 bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const 
    4128 { 
    4129         // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic 
    4130         // validy update in preprocessor for all managers) 
    4131         return ViewCellsManager::ViewPointValid(viewPoint); 
    4132  
    4133         //      return mViewSpaceBox.IsInside(viewPoint) && 
    4134         //                 mVspBspTree->ViewPointValid(viewPoint); 
    4135 } 
    4136  
    4137  
    4138 void VspBspViewCellsManager::Visualize(const ObjectContainer &objects, 
    4139                                                                            const VssRayContainer &sampleRays) 
    4140 { 
    4141         if (!ViewCellsConstructed()) 
    4142                 return; 
    4143  
    4144         VssRayContainer visRays; 
    4145         GetRaySets(sampleRays, mVisualizationSamples, visRays); 
    4146          
    4147         if (1)  
    4148         {        
    4149                 ////////////////// 
    4150                 //-- export final view cell partition 
    4151  
    4152                 Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl"); 
    4153                  
    4154                 if (exporter) 
    4155                 { 
    4156                         cout << "exporting view cells after post process ... "; 
    4157                         if (0) 
    4158                         {       // export view space box 
    4159                                 exporter->SetWireframe(); 
    4160                                 exporter->ExportBox(mViewSpaceBox); 
    4161                                 exporter->SetFilled(); 
    4162                         } 
    4163  
    4164                         Material m;  
    4165                         m.mDiffuseColor.r = 0.0f; 
    4166                         m.mDiffuseColor.g = 0.5f; 
    4167                         m.mDiffuseColor.b = 0.5f; 
    4168  
    4169             exporter->SetForcedMaterial(m); 
    4170  
    4171                         if (1 && mExportGeometry) 
    4172                         { 
    4173                                 exporter->ExportGeometry(objects); 
    4174                         } 
    4175  
    4176                         if (0 && mExportRays) 
    4177                         { 
    4178                                 exporter->ExportRays(visRays, RgbColor(1, 0, 0)); 
    4179                         } 
    4180                         ExportViewCellsForViz(exporter, NULL, GetClipPlane()); 
    4181  
    4182                         delete exporter; 
    4183                         cout << "finished" << endl; 
    4184                 } 
    4185         } 
    4186  
    4187         //////////////// 
    4188         //-- visualization of the BSP splits 
    4189  
    4190         bool exportSplits = false; 
    4191         Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits); 
    4192  
    4193         if (exportSplits) 
    4194         { 
    4195                 cout << "exporting splits ... "; 
    4196                 ExportSplits(objects, visRays); 
    4197                 cout << "finished" << endl; 
    4198         } 
    4199  
    4200         //////// 
    4201         //-- export single view cells 
    4202          
    4203         int leafOut; 
    4204         Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut); 
    4205         const int raysOut = 100; 
    4206          
    4207         ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, ""); 
    4208 } 
    4209  
    4210  
    4211 void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects, 
    4212                                                                                   const VssRayContainer &rays) 
    4213 { 
    4214         Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d"); 
    4215  
    4216         if (exporter) 
    4217         { 
    4218                 Material m; 
    4219                 m.mDiffuseColor = RgbColor(1, 0, 0); 
    4220                 exporter->SetForcedMaterial(m); 
    4221                 exporter->SetWireframe(); 
    4222  
    4223                 exporter->ExportBspSplits(*mVspBspTree, true); 
    4224  
    4225                 // take forced material, else big scenes cannot be viewed 
    4226                 m.mDiffuseColor = RgbColor(0, 1, 0); 
    4227                 exporter->SetForcedMaterial(m); 
    4228                 exporter->SetFilled(); 
    4229  
    4230                 exporter->ResetForcedMaterial(); 
    4231  
    4232                 // export rays 
    4233                 if (mExportRays) 
    4234                 { 
    4235                         exporter->ExportRays(rays, RgbColor(1, 1, 0)); 
    4236                 } 
    4237  
    4238                 if (mExportGeometry) 
    4239                 { 
    4240                         exporter->ExportGeometry(objects); 
    4241                 } 
    4242                 delete exporter; 
    4243         } 
    4244 } 
    4245  
    4246  
    4247 void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects, 
    4248                                                                                                    const int maxViewCells, 
    4249                                                                                                    const bool sortViewCells, 
    4250                                                                                                    const bool exportPvs, 
    4251                                                                                                    const bool exportRays, 
    4252                                                                                                    const int maxRays, 
    4253                                                                                                    const string prefix, 
    4254                                                                                                    VssRayContainer *visRays) 
    4255 {        
    4256         if (sortViewCells) 
    4257         { 
    4258                 // sort view cells to visualize the largest view cells 
    4259                 stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost); 
    4260         } 
    4261  
    4262         ////////// 
    4263         //-- some view cells for output 
    4264  
    4265         ViewCell::NewMail(); 
    4266         const int limit = min(maxViewCells, (int)mViewCells.size()); 
    4267          
    4268         for (int i = 0; i < limit; ++ i) 
    4269         { 
    4270                 cout << "creating output for view cell " << i << " ... "; 
    4271  
    4272                 ViewCell *vc = sortViewCells ? // largest view cell pvs first? 
    4273                         mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i]; 
    4274  
    4275                 if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID) 
    4276                         continue; 
    4277  
    4278                 vc->Mail(); 
    4279  
    4280                 ObjectPvs pvs; 
    4281                 mViewCellsTree->GetPvs(vc, pvs); 
    4282  
    4283                 char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i); 
    4284                 Exporter *exporter = Exporter::GetExporter(s); 
    4285                  
    4286                 cout << "view cell " << vc->GetId() << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl; 
    4287  
    4288                 if (exportRays) 
    4289                 { 
    4290                         //////////// 
    4291                         //-- export rays piercing this view cell 
    4292  
    4293                         // take rays stored with the view cells during subdivision 
    4294                         VssRayContainer vcRays; 
    4295             VssRayContainer collectRays; 
    4296  
    4297                         // collect initial view cells 
    4298                         ViewCellContainer leaves; 
    4299                         mViewCellsTree->CollectLeaves(vc, leaves); 
    4300  
    4301                         ViewCellContainer::const_iterator vit, vit_end = leaves.end(); 
    4302                 for (vit = leaves.begin(); vit != vit_end; ++ vit) 
    4303                         {        
    4304                                 BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaves[0]; 
    4305                                 VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end(); 
    4306  
    4307                                 for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit) 
    4308                                 { 
    4309                                         collectRays.push_back(*rit); 
    4310                                 } 
    4311                         } 
    4312  
    4313                         const int raysOut = min((int)collectRays.size(), maxRays); 
    4314                         cout << "here500 " << raysOut << endl; 
    4315                         // prepare some rays for output 
    4316                         VssRayContainer::const_iterator rit, rit_end = collectRays.end(); 
    4317                         for (rit = collectRays.begin(); rit != rit_end; ++ rit) 
    4318                         { 
    4319                                 const float p = RandomValue(0.0f, (float)collectRays.size()); 
    4320                          
    4321                                 if (p < raysOut) 
    4322                                 { 
    4323                                         vcRays.push_back(*rit); 
    4324                                 } 
    4325                         } 
    4326  
    4327                         exporter->ExportRays(vcRays, RgbColor(1, 1, 1)); 
    4328                 } 
    4329                  
    4330                 //////////////// 
    4331                 //-- export view cell geometry 
    4332  
    4333                 exporter->SetWireframe(); 
    4334  
    4335                 Material m;//= RandomMaterial(); 
    4336                 m.mDiffuseColor = RgbColor(0, 1, 0); 
    4337                 exporter->SetForcedMaterial(m); 
    4338  
    4339                 ExportViewCellGeometry(exporter, vc, NULL, NULL); 
    4340                 exporter->SetFilled(); 
    4341  
    4342                 if (exportPvs) 
    4343                 { 
    4344                         Intersectable::NewMail(); 
    4345  
    4346                         ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end(); 
    4347                         cout << endl; 
    4348                         // output PVS of view cell 
    4349                         for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit) 
    4350                         {                
    4351                                 Intersectable *intersect = (*oit).first; 
    4352                                  
    4353                                 if (!intersect->Mailed()) 
    4354                                 { 
    4355                                         intersect->Mail(); 
    4356                                         m = RandomMaterial(); 
    4357                                         exporter->SetForcedMaterial(m); 
    4358                                         exporter->ExportIntersectable(intersect); 
    4359                                         cout << " i: " << intersect; 
    43604371                                } 
    43614372                        } 
     
    55625573} 
    55635574 
     5575//#define TEST_EVALUATION 
    55645576 
    55655577#if TEST_EVALUATION 
Note: See TracChangeset for help on using the changeset viewer.