Ignore:
Timestamp:
12/30/05 16:37:41 (19 years ago)
Author:
mattausch
Message:
 
File:
1 edited

Legend:

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

    r485 r486  
    179179 
    180180 
    181 /**************************************************************/ 
    182 /*              class VspKdLeaf implementation            */ 
    183 /**************************************************************/ 
     181/*******************************************************************/ 
     182/*                   class VspKdLeaf implementation                */ 
     183/*******************************************************************/ 
    184184 
    185185 
     
    23512351 
    23522352 
    2353 void VspKdTree::RefineViewCells() 
    2354 { 
    2355         //TODO 
    2356 } 
     2353int VspKdTree::RefineViewCells(const VssRayContainer &rays) 
     2354{ 
     2355        int shuffled = 0; 
     2356 
     2357        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl; 
     2358        BspLeaf::NewMail(); 
     2359 
     2360        // Use priority queue of remaining leaf pairs  
     2361        // These candidates either share the same view cells or 
     2362        // are border leaves which share a boundary. 
     2363        // We test if they can be shuffled, i.e., 
     2364        // either one leaf is made part of one view cell or the other 
     2365        // leaf is made part of the other view cell. It is tested if the 
     2366        // remaining view cells are "better" than the old ones. 
     2367        while (!mMergeQueue.empty()) 
     2368        { 
     2369                MergeCandidate mc = mMergeQueue.top(); 
     2370                mMergeQueue.pop(); 
     2371 
     2372                // both view cells equal or already shuffled 
     2373                if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) || 
     2374                        (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed())) 
     2375                        continue; 
     2376                 
     2377                // candidate for shuffling 
     2378                const bool wasShuffled = false; 
     2379                        //ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2()); 
     2380                 
     2381                //-- stats 
     2382                if (wasShuffled) 
     2383                        ++ shuffled; 
     2384        } 
     2385 
     2386        return shuffled; 
     2387} 
     2388 
     2389 
     2390inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 
     2391{ 
     2392        return pvs1.AddPvs(pvs2); 
     2393} 
     2394 
     2395 
     2396inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 
     2397{ 
     2398        return pvs1.SubtractPvs(pvs2); 
     2399} 
     2400 
     2401 
     2402float GetShuffledVcCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2) 
     2403{ 
     2404#if 0 // TODO 
     2405        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs); 
     2406        const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs); 
     2407 
     2408        const float area1 = vc1->GetArea() - leaf->mArea; 
     2409        const float area2 = vc2->GetArea() + leaf->mArea; 
     2410 
     2411        const float cost1 = pvs1 * area1; 
     2412        const float cost2 = pvs2 * area2; 
     2413 
     2414        return cost1 + cost2; 
     2415#else 
     2416        return -1; 
     2417#endif 
     2418} 
     2419 
     2420 
     2421void VspKdTree::ShuffleLeaf(VspKdLeaf *leaf,  
     2422                                                        VspKdViewCell *vc1,  
     2423                                                        VspKdViewCell *vc2) const 
     2424{ 
     2425#if 0 // TODO 
     2426        // compute new pvs and area 
     2427        vc1->GetPvs().SubtractPvs(*leaf->mPvs); 
     2428        vc2->GetPvs().AddPvs(*leaf->mPvs); 
     2429         
     2430        vc1->SetArea(vc1->GetArea() - leaf->mArea); 
     2431        vc2->SetArea(vc2->GetArea() + leaf->mArea); 
     2432 
     2433        /// add to second view cell 
     2434        vc2->mLeaves.push_back(leaf); 
     2435 
     2436        // erase leaf from old view cell 
     2437        vector<VspKdLeaf *>::iterator it = vc1->mLeaves.begin(); 
     2438 
     2439        for (; *it != leaf; ++ it); 
     2440        vc1->mLeaves.erase(it); 
     2441 
     2442        leaf->SetViewCell(vc2);  // finally change view cell 
     2443#endif 
     2444} 
     2445 
     2446 
     2447bool VspKdTree::ShuffleLeaves(VspKdLeaf *leaf1, VspKdLeaf *leaf2) const 
     2448{ 
     2449        VspKdViewCell *vc1 = leaf1->GetViewCell(); 
     2450        VspKdViewCell *vc2 = leaf2->GetViewCell(); 
     2451 
     2452        const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea(); 
     2453        const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea(); 
     2454 
     2455        const float oldCost = cost1 + cost2; 
     2456         
     2457        float shuffledCost1 = Limits::Infinity; 
     2458        float shuffledCost2 = Limits::Infinity; 
     2459 
     2460        // the view cell should not be empty after the shuffle 
     2461        if (vc1->mLeaves.size() > 1) 
     2462                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2); 
     2463        if (vc2->mLeaves.size() > 1) 
     2464                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1); 
     2465 
     2466        // shuffling unsuccessful 
     2467        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2)) 
     2468                return false; 
     2469         
     2470        if (shuffledCost1 < shuffledCost2) 
     2471        { 
     2472                ShuffleLeaf(leaf1, vc1, vc2); 
     2473                leaf1->Mail(); 
     2474        } 
     2475        else 
     2476        { 
     2477                ShuffleLeaf(leaf2, vc2, vc1); 
     2478                leaf2->Mail(); 
     2479        } 
     2480 
     2481        return true; 
     2482} 
     2483 
     2484 
    23572485 
    23582486 
Note: See TracChangeset for help on using the changeset viewer.