Changeset 486 for trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
- Timestamp:
- 12/30/05 16:37:41 (19 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
r485 r486 179 179 180 180 181 /************************************************************** /182 /* class VspKdLeaf implementation*/183 /************************************************************** /181 /*******************************************************************/ 182 /* class VspKdLeaf implementation */ 183 /*******************************************************************/ 184 184 185 185 … … 2351 2351 2352 2352 2353 void VspKdTree::RefineViewCells() 2354 { 2355 //TODO 2356 } 2353 int 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 2390 inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 2391 { 2392 return pvs1.AddPvs(pvs2); 2393 } 2394 2395 2396 inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 2397 { 2398 return pvs1.SubtractPvs(pvs2); 2399 } 2400 2401 2402 float 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 2421 void 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 2447 bool 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 2357 2485 2358 2486
Note: See TracChangeset
for help on using the changeset viewer.