Changeset 434
- Timestamp:
- 11/25/05 14:45:50 (19 years ago)
- Location:
- trunk/VUT/GtpVisibilityPreprocessor/src
- Files:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
r427 r434 1449 1449 RegisterOption("VssTree.randomize", optBool, "randomize", "false"); 1450 1450 RegisterOption("VssTree.splitType", optString, "split=", "queries"); 1451 RegisterOption("VssTree.splitUseOnlyDrivingAxis", optBool, "splitdriving=", "false"); 1452 1453 RegisterOption("VssTree.useRss", optBool, "rss=", "false"); 1454 1455 1456 1451 1457 RegisterOption("VssTree.numberOfEndPointDomains", optInt, "endpoints=", "10000"); 1452 1458 -
trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h
r428 r434 19 19 class BspLeaf; 20 20 class Polygon3; 21 class VssTree; 21 22 22 23 class Exporter … … 47 48 virtual bool 48 49 ExportKdTree(const KdTree &tree) = 0; 50 51 virtual bool 52 ExportVssTree(const VssTree &tree) = 0; 49 53 50 54 virtual bool -
trunk/VUT/GtpVisibilityPreprocessor/src/Makefile
r427 r434 1 1 ############################################################################# 2 2 # Makefile for building: preprocessor 3 # Generated by qmake (1.07a) (Qt 3.3.2) on: Tue Nov 22 12:10:4020053 # Generated by qmake (1.07a) (Qt 3.3.2) on: Wed Nov 23 09:47:01 2005 4 4 # Project: preprocessor.pro 5 5 # Template: app … … 369 369 VssRay.h \ 370 370 VspKdTree.h \ 371 VssTree.h \ 371 372 Containers.h \ 372 373 AxisAlignedBox3.h \ … … 439 440 Ray.h \ 440 441 Plane3.h \ 442 VssRay.h \ 441 443 Matrix4x4.h \ 442 444 Vector3.h \ -
trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp
r433 r434 11 11 12 12 13 bool useViewSpaceBox = false;//true;13 bool useViewSpaceBox = true;//true; 14 14 bool use2dSampling = false; 15 bool useViewspacePlane = false;//true;15 bool useViewspacePlane = true;//true; 16 16 17 17 VssPreprocessor::VssPreprocessor(): 18 19 18 mPass(0), 19 mVssRays() 20 20 { 21 21 // this should increase coherence of the samples … … 32 32 VssPreprocessor::~VssPreprocessor() 33 33 { 34 34 CLEAR_CONTAINER(mVssRays); 35 35 } 36 36 37 37 void 38 38 VssPreprocessor::SetupRay(Ray &ray, 39 40 41 39 const Vector3 &point, 40 const Vector3 &direction 41 ) 42 42 { 43 43 ray.intersections.clear(); 44 44 // do not store anything else then intersections at the ray 45 45 ray.Init(point, direction, Ray::LOCAL_RAY); 46 46 } … … 48 48 int 49 49 VssPreprocessor::CastRay( 50 51 52 53 54 { 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 50 Vector3 &viewPoint, 51 Vector3 &direction, 52 VssRayContainer &vssRays 53 ) 54 { 55 int hits = 0; 56 static Ray ray; 57 AxisAlignedBox3 box = mKdTree->GetBox(); 58 59 AxisAlignedBox3 sbox = box; 60 sbox.Enlarge(Vector3(-Limits::Small)); 61 if (!sbox.IsInside(viewPoint)) 62 return 0; 63 64 SetupRay(ray, viewPoint, direction); 65 // cast ray to KD tree to find intersection with other objects 66 Intersectable *objectA, *objectB; 67 Vector3 pointA, pointB; 68 float bsize = Magnitude(box.Size()); 69 if (mKdTree->CastRay(ray)) { 70 objectA = ray.intersections[0].mObject; 71 pointA = ray.Extrap(ray.intersections[0].mT); 72 } else { 73 objectA = NULL; 74 // compute intersection with the scene bounding box 75 float tmin, tmax; 76 box.ComputeMinMaxT(ray, &tmin, &tmax); 77 if (tmax > bsize) { 78 // cerr<<"Warning: tmax > box size tmax="<<tmax<<" tmin="<<tmin<<" size="<<bsize<<endl; 79 // cerr<<"ray"<<ray<<endl; 80 } 81 pointA = ray.Extrap(tmax); 82 83 } 84 85 bool detectEmptyViewSpace = true; 86 87 if (detectEmptyViewSpace) { 88 SetupRay(ray, pointA, -direction); 89 } else 90 SetupRay(ray, viewPoint, -direction); 91 92 93 if (mKdTree->CastRay(ray)) { 94 95 objectB = ray.intersections[0].mObject; 96 pointB = ray.Extrap(ray.intersections[0].mT); 97 98 } else { 99 objectB = NULL; 100 float tmin, tmax; 101 box.ComputeMinMaxT(ray, &tmin, &tmax); 102 if (tmax > bsize) { 103 // cerr<<"Warning: tmax > box size tmax="<<tmax<<" tmin="<<tmin<<" size="<<bsize<<endl; 104 // cerr<<"ray"<<ray<<endl; 105 } 106 107 pointB = ray.Extrap(tmax); 108 } 109 110 VssRay *vssRay = NULL; 111 112 bool validSample = true; 113 if (detectEmptyViewSpace) { 114 if (Distance(pointA, pointB) < 115 Distance(viewPoint, pointA) + Distance(viewPoint, pointB) - Limits::Small) { 116 validSample = false; 117 } 118 } 119 120 if (validSample) { 121 if (objectA) { 122 vssRay = new VssRay(pointB, 123 pointA, 124 objectB, 125 objectA); 126 vssRays.push_back(vssRay); 127 hits ++; 128 } 129 130 if (objectB) { 131 vssRay = new VssRay(pointA, 132 pointB, 133 objectA, 134 objectB); 135 vssRays.push_back(vssRay); 136 hits ++; 137 } 138 } 139 140 return hits; 141 141 } 142 142 … … 145 145 VssPreprocessor::GetViewpoint(AxisAlignedBox3 *viewSpaceBox) 146 146 { 147 148 149 150 151 152 153 154 155 147 AxisAlignedBox3 box; 148 149 if (viewSpaceBox) 150 box =*viewSpaceBox; 151 else 152 box = mKdTree->GetBox(); 153 154 // shrink the box in the y direction 155 return box.GetRandomPoint(); 156 156 } 157 157 158 158 Vector3 159 159 VssPreprocessor::GetDirection(const Vector3 &viewpoint, 160 161 162 { 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 160 AxisAlignedBox3 *viewSpaceBox 161 ) 162 { 163 Vector3 point; 164 if (!use2dSampling) { 165 Vector3 normal; 166 int i = RandomValue(0, mObjects.size()-1); 167 Intersectable *object = mObjects[i]; 168 object->GetRandomSurfacePoint(point, normal); 169 } else { 170 AxisAlignedBox3 box; 171 172 if (viewSpaceBox) 173 box =*viewSpaceBox; 174 else 175 box = mKdTree->GetBox(); 176 177 point = box.GetRandomPoint(); 178 point.y = viewpoint.y; 179 } 180 181 return point - viewpoint; 182 182 } 183 183 184 184 int 185 185 VssPreprocessor::GenerateImportanceRays(VssTree *vssTree, 186 187 188 189 { 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 186 const int desiredSamples, 187 SimpleRayContainer &rays 188 ) 189 { 190 int num; 191 if (0) { 192 float minRayContribution; 193 float maxRayContribution; 194 float avgRayContribution; 195 196 vssTree->GetRayContributionStatistics(minRayContribution, 197 maxRayContribution, 198 avgRayContribution); 199 200 cout<< 201 "#MIN_RAY_CONTRIB\n"<<minRayContribution<<endl<< 202 "#MAX_RAY_CONTRIB\n"<<maxRayContribution<<endl<< 203 "#AVG_RAY_CONTRIB\n"<<avgRayContribution<<endl; 204 205 float p = desiredSamples/(float)(avgRayContribution*vssTree->stat.Leaves()); 206 num = vssTree->GenerateRays(p, rays); 207 } else { 208 int leaves = vssTree->stat.Leaves()/2; 209 num = vssTree->GenerateRays(desiredSamples, leaves, rays); 210 } 211 212 cout<<"Generated "<<num<<" rays."<<endl; 213 214 return num; 215 215 } 216 216 … … 218 218 bool 219 219 VssPreprocessor::ExportRays(const char *filename, 220 const VssRayContainer &vssRays, 221 const int number 222 ) 223 { 224 cout<<"Exporting vss rays..."<<endl<<flush; 225 226 float prob = number/(float)vssRays.size(); 227 228 229 Exporter *exporter = NULL; 230 exporter = Exporter::GetExporter(filename); 231 // exporter->SetWireframe(); 232 // exporter->ExportKdTree(*mKdTree); 233 exporter->SetFilled(); 234 exporter->ExportScene(mSceneGraph->mRoot); 235 exporter->SetWireframe(); 236 237 if (mViewSpaceBox) { 238 exporter->SetForcedMaterial(RgbColor(1,0,0)); 239 exporter->ExportBox(*mViewSpaceBox); 240 exporter->ResetForcedMaterial(); 241 } 242 243 VssRayContainer rays; for (int i=0; i < vssRays.size(); i++) 244 if (RandomValue(0,1) < prob) 245 rays.push_back(vssRays[i]); 246 247 exporter->ExportRays(rays, RgbColor(1, 0, 0)); 248 249 delete exporter; 250 251 cout<<"done."<<endl<<flush; 252 253 return true; 254 } 255 220 const VssRayContainer &vssRays, 221 const int number 222 ) 223 { 224 cout<<"Exporting vss rays..."<<endl<<flush; 225 226 float prob = number/(float)vssRays.size(); 227 228 229 Exporter *exporter = NULL; 230 exporter = Exporter::GetExporter(filename); 231 // exporter->SetWireframe(); 232 // exporter->ExportKdTree(*mKdTree); 233 exporter->SetFilled(); 234 exporter->ExportScene(mSceneGraph->mRoot); 235 exporter->SetWireframe(); 236 237 if (mViewSpaceBox) { 238 exporter->SetForcedMaterial(RgbColor(1,0,0)); 239 exporter->ExportBox(*mViewSpaceBox); 240 exporter->ResetForcedMaterial(); 241 } 242 243 VssRayContainer rays; for (int i=0; i < vssRays.size(); i++) 244 if (RandomValue(0,1) < prob) 245 rays.push_back(vssRays[i]); 246 247 exporter->ExportRays(rays, RgbColor(1, 0, 0)); 248 249 delete exporter; 250 251 cout<<"done."<<endl<<flush; 252 253 return true; 254 } 255 256 257 bool 258 VssPreprocessor::ExportVssTree(char *filename, 259 VssTree *tree) 260 { 261 Exporter *exporter = Exporter::GetExporter(filename); 262 exporter->SetFilled(); 263 exporter->ExportScene(mSceneGraph->mRoot); 264 exporter->SetWireframe(); 265 bool result = exporter->ExportVssTree(*tree); 266 delete exporter; 267 return result; 268 } 256 269 257 270 bool 258 271 VssPreprocessor::ExportVssTreeLeaf(char *filename, 259 VssTree *tree, 260 VssTreeLeaf *leaf) 261 { 262 Exporter *exporter = NULL; 263 exporter = Exporter::GetExporter(filename); 264 exporter->SetWireframe(); 265 exporter->ExportKdTree(*mKdTree); 266 267 if (mViewSpaceBox) { 268 exporter->SetForcedMaterial(RgbColor(1,0,0)); 269 exporter->ExportBox(*mViewSpaceBox); 270 exporter->ResetForcedMaterial(); 271 } 272 273 exporter->SetForcedMaterial(RgbColor(0,0,1)); 274 exporter->ExportBox(tree->GetBBox(leaf)); 272 VssTree *tree, 273 VssTreeLeaf *leaf) 274 { 275 Exporter *exporter = NULL; 276 exporter = Exporter::GetExporter(filename); 277 exporter->SetWireframe(); 278 exporter->ExportKdTree(*mKdTree); 279 280 if (mViewSpaceBox) { 281 exporter->SetForcedMaterial(RgbColor(1,0,0)); 282 exporter->ExportBox(*mViewSpaceBox); 275 283 exporter->ResetForcedMaterial(); 276 277 VssRayContainer rays[4]; 278 for (int i=0; i < leaf->rays.size(); i++) { 279 int k = leaf->rays[i].GetRayClass(); 280 rays[k].push_back(leaf->rays[i].mRay); 281 } 282 283 // SOURCE RAY 284 exporter->ExportRays(rays[0], RgbColor(1, 0, 0)); 285 // TERMINATION RAY 286 exporter->ExportRays(rays[1], RgbColor(1, 1, 1)); 287 // PASSING_RAY 288 exporter->ExportRays(rays[2], RgbColor(1, 1, 0)); 289 // CONTAINED_RAY 290 exporter->ExportRays(rays[3], RgbColor(0, 0, 1)); 291 292 delete exporter; 293 return true; 284 } 285 286 exporter->SetForcedMaterial(RgbColor(0,0,1)); 287 exporter->ExportBox(tree->GetBBox(leaf)); 288 exporter->ResetForcedMaterial(); 289 290 VssRayContainer rays[4]; 291 for (int i=0; i < leaf->rays.size(); i++) { 292 int k = leaf->rays[i].GetRayClass(); 293 rays[k].push_back(leaf->rays[i].mRay); 294 } 295 296 // SOURCE RAY 297 exporter->ExportRays(rays[0], RgbColor(1, 0, 0)); 298 // TERMINATION RAY 299 exporter->ExportRays(rays[1], RgbColor(1, 1, 1)); 300 // PASSING_RAY 301 exporter->ExportRays(rays[2], RgbColor(1, 1, 0)); 302 // CONTAINED_RAY 303 exporter->ExportRays(rays[3], RgbColor(0, 0, 1)); 304 305 delete exporter; 306 return true; 294 307 } 295 308 … … 297 310 VssPreprocessor::ExportVssTreeLeaves(VssTree *tree, const int number) 298 311 { 299 vector<VssTreeLeaf *> leaves; 300 tree->CollectLeaves(leaves); 301 302 int num = 0; 303 int i; 304 float p = number / (float)leaves.size(); 305 for (i=0; i < leaves.size(); i++) { 306 if (RandomValue(0,1) < p) { 307 char filename[64]; 308 sprintf(filename, "vss-leaf-%04d.x3d", num); 309 ExportVssTreeLeaf(filename, tree, leaves[i]); 310 num++; 311 } 312 if (num >= number) 313 break; 314 } 312 vector<VssTreeLeaf *> leaves; 313 tree->CollectLeaves(leaves); 314 315 int num = 0; 316 int i; 317 float p = number / (float)leaves.size(); 318 for (i=0; i < leaves.size(); i++) { 319 if (RandomValue(0,1) < p) { 320 char filename[64]; 321 sprintf(filename, "vss-leaf-%04d.x3d", num); 322 ExportVssTreeLeaf(filename, tree, leaves[i]); 323 num++; 324 } 325 if (num >= number) 326 break; 327 } 328 } 329 330 331 float 332 VssPreprocessor::GetAvgPvsSize(VssTree *tree, 333 const vector<AxisAlignedBox3> &viewcells 334 ) 335 { 336 vector<AxisAlignedBox3>::const_iterator it, it_end = viewcells.end(); 337 338 int sum = 0; 339 for (it = viewcells.begin(); it != it_end; ++ it) 340 sum += tree->GetPvsSize(*it); 341 342 return sum/(float)viewcells.size(); 315 343 } 316 344 … … 326 354 327 355 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 356 AxisAlignedBox3 *box = new AxisAlignedBox3(mKdTree->GetBox()); 357 358 if (!useViewspacePlane) { 359 float size = 0.01f; 360 float s = 0.5f - size; 361 float olds = Magnitude(box->Size()); 362 box->Enlarge(box->Size()*Vector3(-s)); 363 Vector3 translation = Vector3(-olds*0.1f, 0, 0); 364 box->SetMin(box->Min() + translation); 365 box->SetMax(box->Max() + translation); 366 } else { 367 368 // sample city like heights 369 box->SetMin(1, box->Min(1) + box->Size(1)*0.1); 370 box->SetMax(1, box->Min(1) + box->Size(1)*0.2); 371 } 372 373 if (use2dSampling) 374 box->SetMax(1, box->Min(1)); 375 376 if (useViewSpaceBox) 377 mViewSpaceBox = box; 378 else 379 mViewSpaceBox = NULL; 380 381 382 VssTree *vssTree = NULL; 383 384 RayContainer bspRays; 357 385 358 386 while (totalSamples < mInitialSamples) { 359 360 361 362 363 364 365 366 367 387 int passContributingSamples = 0; 388 int passSampleContributions = 0; 389 int passSamples = 0; 390 int index = 0; 391 392 int sampleContributions; 393 394 int s = Min(mSamplesPerPass, mInitialSamples); 395 for (int k=0; k < s; k++) { 368 396 369 370 397 Vector3 viewpoint = GetViewpoint(mViewSpaceBox); 398 Vector3 direction = GetDirection(viewpoint, mViewSpaceBox); 371 399 372 400 sampleContributions = CastRay(viewpoint, direction, mVssRays); 373 401 374 402 375 376 377 378 379 380 381 382 403 //-- CORR matt: put block inside loop 404 if (sampleContributions) { 405 passContributingSamples ++; 406 passSampleContributions += sampleContributions; 407 } 408 passSamples++; 409 totalSamples++; 410 } 383 411 384 mPass++; 385 386 int pvsSize = 0; 387 float avgRayContrib = (passContributingSamples > 0) ? 388 passSampleContributions/(float)passContributingSamples : 0; 389 390 cout << "#Pass " << mPass << " : t = " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 391 cout << "#TotalSamples=" << totalSamples/1000 392 << "k #SampleContributions=" << passSampleContributions << " (" 393 << 100*passContributingSamples/(float)passSamples<<"%)" << " avgPVS=" 394 << pvsSize/(float)mObjects.size() << endl 395 << "avg ray contrib=" << avgRayContrib << endl; 396 397 mStats << 398 "#Pass\n" <<mPass<<endl<< 399 "#Time\n" << TimeDiff(startTime, GetTime())*1e-3 << endl<< 400 "#TotalSamples\n" << totalSamples<< endl<< 401 "#SampleContributions\n" << passSampleContributions << endl << 402 "#PContributingSamples\n"<<100*passContributingSamples/(float)passSamples<<endl << 403 "#AvgPVS\n"<< pvsSize/(float)mObjects.size() << endl << 404 "#AvgRayContrib\n" << avgRayContrib << endl; 405 406 407 408 409 } 410 411 cout << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl; 412 cout << "#totalRayStackSize=" << mVssRays.size() << endl <<flush; 413 414 415 int numExportRays = 10000; 416 //int numExportRays = 0; 412 mPass++; 413 414 int pvsSize = 0; 415 float avgRayContrib = (passContributingSamples > 0) ? 416 passSampleContributions/(float)passContributingSamples : 0; 417 418 cout << "#Pass " << mPass << " : t = " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 419 cout << "#TotalSamples=" << totalSamples/1000 420 << "k #SampleContributions=" << passSampleContributions << " (" 421 << 100*passContributingSamples/(float)passSamples<<"%)" << " avgPVS=" 422 << pvsSize/(float)mObjects.size() << endl 423 << "avg ray contrib=" << avgRayContrib << endl; 424 425 mStats << 426 "#Pass\n" <<mPass<<endl<< 427 "#Time\n" << TimeDiff(startTime, GetTime())*1e-3 << endl<< 428 "#TotalSamples\n" << totalSamples<< endl<< 429 "#SampleContributions\n" << passSampleContributions << endl << 430 "#PContributingSamples\n"<<100*passContributingSamples/(float)passSamples<<endl << 431 "#AvgPVS\n"<< pvsSize/(float)mObjects.size() << endl << 432 "#AvgRayContrib\n" << avgRayContrib << endl; 433 434 435 436 437 } 438 439 cout << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl; 440 cout << "#totalRayStackSize=" << mVssRays.size() << endl <<flush; 441 442 int numExportRays = 10000; 443 //int numExportRays = 0; 444 445 if (numExportRays) { 446 char filename[64]; 447 sprintf(filename, "vss-rays-initial.x3d"); 448 ExportRays(filename, mVssRays, numExportRays); 449 } 450 451 //-- construct BSP view cells 452 if (ViewCell::sHierarchy == ViewCell::BSP) 453 { 454 const int bspSamples = min((int)mVssRays.size(), mBspConstructionSamples); 455 456 for (int i = 0; i < bspSamples; ++ i) 457 bspRays.push_back(new Ray(*mVssRays[i])); 458 459 //-- construct BSP tree using the samples 460 mBspTree = new BspTree(&mUnbounded); 461 462 mBspTree->SetGenerateViewCells(true); 463 mBspTree->Construct(bspRays); 464 465 Exporter *exporter = Exporter::GetExporter("vccbsprays.x3d"); 466 467 // export rays piercing this view cell 468 exporter->ExportRays(bspRays, 1000, RgbColor(0, 1, 0)); 469 470 // cast remaining initial rays into BSP tree 471 for (int i = bspSamples; i < (int)mVssRays.size(); ++ i) 472 CastRay(*mBspTree, *mVssRays[i]); 473 } 474 475 vssTree = new VssTree; 476 // viewcells = Construct(mVssRays); 477 478 vssTree->Construct(mVssRays, mViewSpaceBox); 479 cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl; 480 481 ExportVssTree("vss-tree.x3d", vssTree); 482 483 ExportVssTreeLeaves(vssTree, 10); 484 485 // viewcells->UpdatePVS(newVssRays); 486 // get viewcells as kd tree boxes 487 vector<AxisAlignedBox3> kdViewcells; 488 if (0) { 489 vector<KdLeaf *> leaves; 490 mKdTree->CollectLeaves(leaves); 491 vector<KdLeaf *>::const_iterator it; 492 int targetLeaves = 50; 493 float prob = targetLeaves/(float)leaves.size(); 494 for (it = leaves.begin(); it != leaves.end(); ++it) 495 if (RandomValue(0.0f,1.0f) < prob) 496 kdViewcells.push_back(mKdTree->GetBox(*it)); 497 498 float avgPvs = GetAvgPvsSize(vssTree, kdViewcells); 499 cout<<"Initial average PVS size = "<<avgPvs<<endl; 500 } 501 502 503 int samples = 0; 504 int pass = 0; 505 while (1) { 506 int num = mVssSamplesPerPass; 507 SimpleRayContainer rays; 508 VssRayContainer vssRays; 509 510 if (!mUseImportanceSampling) { 511 for (int j=0; j < num; j++) { 512 Vector3 viewpoint = GetViewpoint(mViewSpaceBox); 513 Vector3 direction = GetDirection(viewpoint, mViewSpaceBox); 514 rays.push_back(SimpleRay(viewpoint, direction)); 515 } 516 } else { 517 num = GenerateImportanceRays(vssTree, num, rays); 518 } 519 520 521 for (int i=0; i < rays.size(); i++) 522 CastRay(rays[i].mOrigin, rays[i].mDirection, vssRays); 523 524 vssTree->AddRays(vssRays); 525 526 if (0) { 527 int subdivided = vssTree->UpdateSubdivision(); 528 cout<<"subdivided leafs = "<<subdivided<<endl; 529 } 530 531 float avgPvs = GetAvgPvsSize(vssTree, kdViewcells); 532 cout<<"Average PVS size = "<<avgPvs<<endl; 417 533 418 534 if (numExportRays) { 419 char filename[64]; 420 sprintf(filename, "vss-rays-initial.x3d"); 421 ExportRays(filename, mVssRays, numExportRays); 422 } 423 424 //-- construct BSP view cells 535 char filename[64]; 536 if (mUseImportanceSampling) 537 sprintf(filename, "vss-rays-i%04d.x3d", pass); 538 else 539 sprintf(filename, "vss-rays-%04d.x3d", pass); 540 541 ExportRays(filename, vssRays, numExportRays); 542 } 543 544 // cast rays into BSP tree 425 545 if (ViewCell::sHierarchy == ViewCell::BSP) 546 { 547 for (int i = 0; i < (int)vssRays.size(); ++ i) 548 { 549 CastRay(*mBspTree, *vssRays[i]); 550 } 551 } 552 553 samples+=num; 554 float pvs = vssTree->GetAvgPvsSize(); 555 cout<<"*****************************\n"; 556 cout<<samples<<" avgPVS ="<<pvs<<endl; 557 cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl; 558 cout<<"*****************************\n"; 559 if (samples >= mVssSamples) 560 break; 561 pass++; 562 } 563 564 delete vssTree; 565 566 if (ViewCell::sHierarchy == ViewCell::BSP) 426 567 { 427 const int bspSamples = min((int)mVssRays.size(), mBspConstructionSamples); 428 429 for (int i = 0; i < bspSamples; ++ i) 430 bspRays.push_back(new Ray(*mVssRays[i])); 431 432 //-- construct BSP tree using the samples 433 mBspTree = new BspTree(&mUnbounded); 434 435 mBspTree->SetGenerateViewCells(true); 436 mBspTree->Construct(bspRays); 437 438 Exporter *exporter = Exporter::GetExporter("vccbsprays.x3d"); 568 Debug << mBspTree->GetStatistics(); 569 570 ObjectContainer objects; 571 ExportSplits(objects, bspRays, 10000); 572 ExportBspPvs(objects, bspRays, 10000); 573 574 BspViewCellsStatistics stat; 575 mBspTree->EvaluateViewCellsStats(stat); 576 Debug << "original view cell partition:\n" << stat << endl; 577 578 // clear BSP samples 579 CLEAR_CONTAINER(bspRays); 580 } 581 582 return true; 583 } 584 585 void VssPreprocessor::CastRay(const BspTree &tree, const VssRay & vssRay) 586 { 587 //-- cast ray to BSP tree to get intersection with view cells 588 Ray ray(vssRay); 589 590 Debug << ray << endl; 591 if (ray.intersections.empty()) 592 Debug << "empty ray" << endl; 593 else 594 Debug << "intersection: " << ray.intersections[0].mT << " " << ray.intersections[0].mObject << endl; 595 596 mBspTree->CastRay(ray); 597 598 //if (0 && ray.sourceObject.mObject) 599 //sampleContributions += 600 //AddObjectSamples(ray.sourceObject.mObject, ray); 439 601 440 // export rays piercing this view cell 441 exporter->ExportRays(bspRays, 1000, RgbColor(0, 1, 0)); 442 443 // cast remaining initial rays into BSP tree 444 for (int i = bspSamples; i < (int)mVssRays.size(); ++ i) 445 CastRay(*mBspTree, *mVssRays[i]); 446 } 447 448 vssTree = new VssTree; 449 450 vssTree->Construct(mVssRays, mViewSpaceBox); 451 452 cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl; 453 454 ExportVssTreeLeaves(vssTree, 10); 455 456 int samples = 0; 457 int pass = 0; 458 while (1) { 459 int num = mVssSamplesPerPass; 460 SimpleRayContainer rays; 461 VssRayContainer vssRays; 462 463 if (!mUseImportanceSampling) { 464 for (int j=0; j < num; j++) { 465 Vector3 viewpoint = GetViewpoint(mViewSpaceBox); 466 Vector3 direction = GetDirection(viewpoint, mViewSpaceBox); 467 rays.push_back(SimpleRay(viewpoint, direction)); 468 } 469 } else { 470 num = GenerateImportanceRays(vssTree, num, rays); 471 } 472 473 474 for (int i=0; i < rays.size(); i++) 475 CastRay(rays[i].mOrigin, rays[i].mDirection, vssRays); 476 477 vssTree->AddRays(vssRays); 478 479 if (1) { 480 int subdivided = vssTree->UpdateSubdivision(); 481 cout<<"subdivided leafs = "<<subdivided<<endl; 482 } 483 484 if (numExportRays) { 485 char filename[64]; 486 if (mUseImportanceSampling) 487 sprintf(filename, "vss-rays-i%04d.x3d", pass); 488 else 489 sprintf(filename, "vss-rays-%04d.x3d", pass); 490 491 ExportRays(filename, vssRays, numExportRays); 492 } 493 494 // cast rays into BSP tree 495 if (ViewCell::sHierarchy == ViewCell::BSP) 496 { 497 for (int i = 0; i < (int)vssRays.size(); ++ i) 498 { 499 CastRay(*mBspTree, *vssRays[i]); 500 } 501 } 502 503 samples+=num; 504 float pvs = vssTree->GetAvgPvsSize(); 505 cout<<"*****************************\n"; 506 cout<<samples<<" avgPVS ="<<pvs<<endl; 507 cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl; 508 cout<<"*****************************\n"; 509 if (samples >= mVssSamples) 510 break; 511 pass++; 512 } 513 514 delete vssTree; 515 516 if (ViewCell::sHierarchy == ViewCell::BSP) 602 if (!ray.intersections.empty()) // second intersection found 517 603 { 518 Debug << mBspTree->GetStatistics(); 519 520 ObjectContainer objects; 521 ExportSplits(objects, bspRays, 10000); 522 ExportBspPvs(objects, bspRays, 10000); 523 524 BspViewCellsStatistics stat; 525 mBspTree->EvaluateViewCellsStats(stat); 526 Debug << "original view cell partition:\n" << stat << endl; 527 528 // clear BSP samples 529 CLEAR_CONTAINER(bspRays); 530 } 531 532 return true; 533 } 534 535 void VssPreprocessor::CastRay(const BspTree &tree, const VssRay & vssRay) 536 { 537 //-- cast ray to BSP tree to get intersection with view cells 538 Ray ray(vssRay); 539 540 Debug << ray << endl; 541 if (ray.intersections.empty()) 542 Debug << "empty ray" << endl; 543 else 544 Debug << "intersection: " << ray.intersections[0].mT << " " << ray.intersections[0].mObject << endl; 545 546 mBspTree->CastRay(ray); 547 548 //if (0 && ray.sourceObject.mObject) 549 //sampleContributions += 550 //AddObjectSamples(ray.sourceObject.mObject, ray); 551 552 if (!ray.intersections.empty()) // second intersection found 553 { 554 //sampleContributions += 555 AddObjectSamples(ray.intersections[0].mObject, ray); 556 } 604 //sampleContributions += 605 AddObjectSamples(ray.intersections[0].mObject, ray); 606 } 557 607 } 558 608 559 609 int VssPreprocessor::AddObjectSamples(Intersectable *obj, const Ray &ray) 560 610 { 561 562 611 int contributingSamples = 0; 612 int j; 563 613 564 565 614 // object can be seen from the view cell => add to view cell pvs 615 for (j=0; j < ray.bspIntersections.size(); ++ j) 566 616 { 617 BspLeaf *leaf = ray.bspIntersections[j].mLeaf; 618 // if ray not in unbounded space 619 if (leaf->GetViewCell() != &mUnbounded) 620 contributingSamples += 621 leaf->GetViewCell()->GetPvs().AddSample(obj); 622 } 623 624 // rays passing through this viewcell 625 if (mPass > 1) 626 for (j=1; j < ((int)ray.bspIntersections.size() - 1); ++ j) 627 { 567 628 BspLeaf *leaf = ray.bspIntersections[j].mLeaf; 568 // if ray not in unbounded space629 569 630 if (leaf->GetViewCell() != &mUnbounded) 570 contributingSamples += 571 leaf->GetViewCell()->GetPvs().AddSample(obj); 572 } 573 574 // rays passing through this viewcell 575 if (mPass > 1) 576 for (j=1; j < ((int)ray.bspIntersections.size() - 1); ++ j) 577 { 578 BspLeaf *leaf = ray.bspIntersections[j].mLeaf; 579 580 if (leaf->GetViewCell() != &mUnbounded) 581 leaf->GetViewCell()-> 582 AddPassingRay(ray, contributingSamples ? 1 : 0); 583 } 584 585 return contributingSamples; 586 } 631 leaf->GetViewCell()-> 632 AddPassingRay(ray, contributingSamples ? 1 : 0); 633 } 634 635 return contributingSamples; 636 } -
trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.h
r429 r434 14 14 class VssPreprocessor : public Preprocessor { 15 15 public: 16 16 int mPass; 17 17 int mSamplesPerPass; 18 18 int mVssSamplesPerPass; 19 19 int mInitialSamples; 20 20 int mVssSamples; 21 21 bool mUseImportanceSampling; 22 22 23 23 AxisAlignedBox3 *mViewSpaceBox; 24 24 25 25 ofstream mStats; 26 26 27 27 ObjectContainer mObjects; 28 28 29 29 // rays cast during the processing 30 30 VssRayContainer mVssRays; 31 31 … … 35 35 virtual bool ComputeVisibility(); 36 36 37 38 37 Vector3 38 GetViewpoint(AxisAlignedBox3 *viewSpaceBox); 39 39 40 41 42 43 40 Vector3 41 GetDirection(const Vector3 &viewpoint, 42 AxisAlignedBox3 *viewSpaceBox 43 ); 44 44 45 45 void 46 46 SetupRay(Ray &ray, 47 48 49 47 const Vector3 &point, 48 const Vector3 &direction 49 ); 50 50 51 51 52 52 53 54 55 56 57 53 int 54 CastRay( 55 Vector3 &viewPoint, 56 Vector3 &direction, 57 VssRayContainer &vssRays 58 58 59 59 ); 60 60 61 61 62 62 63 63 virtual bool BuildBspTree() { return false; } 64 64 65 65 66 bool 67 ExportRays(const char *filename, 68 const VssRayContainer &vssRays, 69 const int number 66 bool 67 ExportRays(const char *filename, 68 const VssRayContainer &vssRays, 69 const int number 70 ); 71 72 int 73 GenerateImportanceRays(VssTree *vssTree, 74 const int desiredSamples, 75 SimpleRayContainer &rays 70 76 ); 71 77 72 int 73 GenerateImportanceRays(VssTree *vssTree, 74 const int desiredSamples, 75 SimpleRayContainer &rays 76 ); 78 79 bool 80 ExportVssTreeLeaf(char *filename, 81 VssTree *tree, 82 VssTreeLeaf *leaf); 83 84 void 85 ExportVssTreeLeaves(VssTree *tree, const int number); 86 87 88 bool 89 ExportVssTree(char *filename, 90 VssTree *tree); 77 91 78 92 79 bool 80 ExportVssTreeLeaf(char *filename, 81 VssTree *tree, 82 VssTreeLeaf *leaf); 83 84 void 85 ExportVssTreeLeaves(VssTree *tree, const int number); 93 float 94 GetAvgPvsSize(VssTree *tree, 95 const vector<AxisAlignedBox3> &viewcells 96 ); 97 98 void CastRay(const BspTree &tree, const VssRay & vssRay); 86 99 87 void CastRay(const BspTree &tree, const VssRay & vssRay); 88 89 int AddObjectSamples(Intersectable *obj, const Ray &ray); 100 int AddObjectSamples(Intersectable *obj, const Ray &ray); 90 101 }; 91 102 -
trunk/VUT/GtpVisibilityPreprocessor/src/VssRay.h
r431 r434 136 136 Vector3 GetNormalizedDir() const { return (mTermination - mOrigin)*mInvSize; } 137 137 138 Vector3 Extrap(const float t) const { 139 return GetOrigin() + t * GetDir(); 140 } 141 138 142 float GetDirParametrization(const int axis) const; 139 143 … … 200 204 } 201 205 } 206 207 static Vector3 208 GetDirection(const float a, const float b) { 209 return Vector3(sin(a), sin(b), cos(a)); 210 } 211 202 212 }; 203 213 -
trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp
r433 r434 26 26 27 27 28 #define DEBUG_DIR_SPLIT 029 30 31 32 28 // Static variables 33 29 int … … 36 32 inline void 37 33 AddObject2Pvs(Intersectable *object, 38 const int side, 39 int &pvsBack, 40 int &pvsFront) 41 { 42 43 if (!object) 44 return; 45 46 if (side <= 0) { 47 if (!object->Mailed() && !object->Mailed(2)) { 48 pvsBack++; 49 if (object->Mailed(1)) 50 object->Mail(2); 51 else 52 object->Mail(); 53 } 54 } 55 56 if (side >= 0) { 57 if (!object->Mailed(1) && !object->Mailed(2)) { 58 pvsFront++; 59 if (object->Mailed()) 60 object->Mail(2); 61 else 62 object->Mail(1); 63 } 64 } 65 } 66 34 const int side, 35 int &pvsBack, 36 int &pvsFront) 37 { 38 39 if (!object) 40 return; 41 42 if (side <= 0) { 43 if (!object->Mailed() && !object->Mailed(2)) { 44 pvsBack++; 45 if (object->Mailed(1)) 46 object->Mail(2); 47 else 48 object->Mail(); 49 } 50 } 51 52 if (side >= 0) { 53 if (!object->Mailed(1) && !object->Mailed(2)) { 54 pvsFront++; 55 if (object->Mailed()) 56 object->Mail(2); 57 else 58 object->Mail(1); 59 } 60 } 61 } 67 62 68 63 // Constructor … … 70 65 { 71 66 environment->GetIntValue("VssTree.maxDepth", termMaxDepth); 72 73 74 67 environment->GetIntValue("VssTree.minPvs", termMinPvs); 68 environment->GetIntValue("VssTree.minRays", termMinRays); 69 environment->GetFloatValue("VssTree.maxRayContribution", termMaxRayContribution); 75 70 environment->GetFloatValue("VssTree.maxCostRatio", termMaxCostRatio); 76 71 … … 92 87 float refDirAngle; 93 88 environment->GetFloatValue("VssTree.refDirAngle", refDirAngle); 94 89 95 90 environment->GetIntValue("VssTree.accessTimeThreshold", accessTimeThreshold); 96 91 //= 1000; … … 99 94 100 95 // pRefDirThresh = cos(0.5*M_PI - M_PI*refDirAngle/180.0); 101 102 96 // cosRefDir = cos(M_PI*refDirAngle/180.0); 97 // sinRefDir = sin(M_PI*refDirAngle/180.0); 103 98 104 99 105 100 // split type 106 107 101 char sname[128]; 102 environment->GetStringValue("VssTree.splitType", sname); 108 103 string name(sname); 109 104 … … 113 108 if (name.compare("heuristic") == 0) 114 109 splitType = ESplitHeuristic; 115 else { 116 cerr<<"Invalid VssTree split type "<<name<<endl; 117 exit(1); 118 } 110 else 111 if (name.compare("hybrid") == 0) 112 splitType = ESplitHybrid; 113 else { 114 cerr<<"Invalid VssTree split type "<<name<<endl; 115 exit(1); 116 } 119 117 120 118 environment->GetBoolValue("VssTree.randomize", randomize); 121 119 environment->GetBoolValue("VssTree.splitUseOnlyDrivingAxis", mSplitUseOnlyDrivingAxis); 120 environment->GetBoolValue("VssTree.useRss", mUseRss); 121 122 122 root = NULL; 123 123 … … 143 143 << rays <<endl; 144 144 145 145 app << "#N_INITPVS ( Initial PVS size )\n" 146 146 << initialPvsSize <<endl; 147 147 … … 179 179 minRaysNodes*100/(double)Leaves()<<endl; 180 180 181 181 app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<< 182 182 minSizeNodes*100/(double)Leaves()<<endl; 183 183 184 184 app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"<< 185 185 maxRayContribNodes*100/(double)Leaves()<<endl; 186 186 187 187 app << "#N_PMAXCOSTRATIOLEAVES ( Percentage of leaves with max cost ratio )\n"<< 188 188 maxCostRatioNodes*100/(double)Leaves()<<endl; 189 189 … … 207 207 VssTreeLeaf::UpdatePvsSize() 208 208 { 209 210 211 212 213 214 215 216 209 if (!mValidPvs) { 210 Intersectable::NewMail(); 211 int pvsSize = 0; 212 for(VssTreeNode::RayInfoContainer::iterator ri = rays.begin(); 213 ri != rays.end(); 214 ri++) 215 if ((*ri).mRay->IsActive()) { 216 Intersectable *object; 217 217 #if BIDIRECTIONAL_RAY 218 219 220 221 222 218 object = (*ri).mRay->mOriginObject; 219 if (object && !object->Mailed()) { 220 pvsSize++; 221 object->Mail(); 222 } 223 223 #endif 224 225 226 227 228 229 230 231 232 224 object = (*ri).mRay->mTerminationObject; 225 if (object && !object->Mailed()) { 226 pvsSize++; 227 object->Mail(); 228 } 229 } 230 mPvsSize = pvsSize; 231 mValidPvs = true; 232 } 233 233 } 234 234 235 235 bool 236 236 VssTree::ClipRay( 237 238 239 240 { 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 237 VssTreeNode::RayInfo &rayInfo, 238 const AxisAlignedBox3 &box 239 ) 240 { 241 float tmin, tmax; 242 static Ray ray; 243 ray.Init(rayInfo.mRay->GetOrigin(), rayInfo.mRay->GetDir(), Ray::LINE_SEGMENT); 244 box.ComputeMinMaxT(ray, &tmin, &tmax); 245 if (tmin >= tmax) 246 return false; 247 248 if (tmin > 0.0f) 249 rayInfo.SetMinT(tmin); 250 251 if (tmax < 1.0f) 252 rayInfo.SetMaxT(tmax); 253 254 // vssRay->SetupEndPoints( 255 // origin, 256 // termination 257 // ); 258 return true; 259 259 } 260 260 … … 262 262 void 263 263 VssTree::Construct( 264 265 266 264 VssRayContainer &rays, 265 AxisAlignedBox3 *forcedBoundingBox 266 ) 267 267 { 268 268 stat.Start(); 269 269 270 270 maxMemory = maxStaticMemory; 271 271 272 272 if (root) 273 273 delete root; 274 274 275 275 root = new VssTreeLeaf(NULL, rays.size()); 276 276 // first construct a leaf that will get subdivide … … 281 281 bbox.Initialize(); 282 282 dirBBox.Initialize(); 283 283 284 if (mUseRss) 285 forcedBoundingBox = NULL; 286 284 287 for(VssRayContainer::const_iterator ri = rays.begin(); 285 288 ri != rays.end(); 286 289 ri++) { 287 288 289 290 291 292 290 291 VssTreeNode::RayInfo info(*ri); 292 if (forcedBoundingBox) 293 if (!ClipRay(info, *forcedBoundingBox)) 294 continue; 295 leaf->AddRay(info); 293 296 294 297 bbox.Include((*ri)->GetOrigin()); … … 296 299 297 300 298 299 300 301 302 303 304 305 306 307 308 309 310 311 301 dirBBox.Include(Vector3( 302 (*ri)->GetDirParametrization(0), 303 (*ri)->GetDirParametrization(1), 304 0 305 ) 306 ); 307 } 308 309 310 if ( forcedBoundingBox ) 311 bbox = *forcedBoundingBox; 312 313 cout<<"Bbox = "<<bbox<<endl; 314 cout<<"Dirr Bbox = "<<dirBBox<<endl; 312 315 313 316 stat.rays = leaf->rays.size(); 314 317 leaf->UpdatePvsSize(); 315 318 stat.initialPvsSize = leaf->GetPvsSize(); 316 319 // Subdivide(); … … 325 328 stat.Stop(); 326 329 327 328 330 stat.Print(cout); 331 cout<<"#Total memory="<<GetMemUsage()<<endl; 329 332 330 333 } … … 333 336 VssTree::UpdateSubdivision() 334 337 { 335 338 priority_queue<TraversalData> tStack; 336 339 // stack<TraversalData> tStack; 337 340 338 341 tStack.push(TraversalData(root, bbox, 0)); 339 342 340 343 AxisAlignedBox3 backBox; 341 344 AxisAlignedBox3 frontBox; 342 345 343 344 345 346 maxMemory = maxTotalMemory; 347 int subdivided = 0; 348 int lastMem = 0; 346 349 while (!tStack.empty()) { 347 350 348 349 350 351 352 353 354 355 351 float mem = GetMemUsage(); 352 353 if ( lastMem/10 != ((int)mem)/10) { 354 cout<<mem<<" MB"<<endl; 355 } 356 lastMem = (int)mem; 357 358 if ( mem > maxMemory ) { 356 359 // count statistics on unprocessed leafs 357 360 while (!tStack.empty()) { 358 359 361 // EvaluateLeafStats(tStack.top()); 362 tStack.pop(); 360 363 } 361 364 break; … … 365 368 tStack.pop(); 366 369 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 } 388 370 if (data.node->IsLeaf()) { 371 VssTreeNode *node = SubdivideNode((VssTreeLeaf *) data.node, 372 data.bbox, 373 backBox, 374 frontBox 375 ); 376 if (!node->IsLeaf()) { 377 subdivided++; 378 VssTreeInterior *interior = (VssTreeInterior *) node; 379 // push the children on the stack 380 tStack.push(TraversalData(interior->back, backBox, data.depth+1)); 381 tStack.push(TraversalData(interior->front, frontBox, data.depth+1)); 382 } else { 383 // EvaluateLeafStats(data); 384 } 385 } else { 386 VssTreeInterior *interior = (VssTreeInterior *) data.node; 387 tStack.push(TraversalData(interior->back, GetBBox(interior->back), data.depth+1)); 388 tStack.push(TraversalData(interior->front, GetBBox(interior->front), data.depth+1)); 389 } 390 } 391 return subdivided; 389 392 } 390 393 … … 404 407 405 408 406 409 int lastMem = 0; 407 410 while (!tStack.empty()) { 408 411 409 410 411 412 413 414 415 416 412 float mem = GetMemUsage(); 413 414 if ( lastMem/10 != ((int)mem)/10) { 415 cout<<mem<<" MB"<<endl; 416 } 417 lastMem = (int)mem; 418 419 if ( mem > maxMemory ) { 417 420 // count statistics on unprocessed leafs 418 421 while (!tStack.empty()) { 419 420 422 EvaluateLeafStats(tStack.top()); 423 tStack.pop(); 421 424 } 422 425 break; … … 427 430 428 431 VssTreeNode *node = SubdivideNode((VssTreeLeaf *) data.node, 429 430 431 432 432 data.bbox, 433 backBox, 434 frontBox 435 ); 433 436 if (result == NULL) 434 437 result = node; … … 453 456 int 454 457 VssTree::SelectPlane( 455 456 457 458 459 460 461 462 458 VssTreeLeaf *leaf, 459 const AxisAlignedBox3 &box, 460 float &position, 461 int &raysBack, 462 int &raysFront, 463 int &pvsBack, 464 int &pvsFront 465 ) 463 466 { 464 467 465 468 int minDirDepth = 6; 466 469 int axis; 467 float costRatio; 468 469 if (splitType == ESplitRegular) { 470 costRatio = BestCostRatioRegular(leaf, 471 axis, 472 position, 473 raysBack, 474 raysFront, 475 pvsBack, 476 pvsFront 477 ); 478 479 } else { 480 if (splitType == ESplitHeuristic) 481 costRatio = BestCostRatioHeuristic(leaf, 482 axis, 483 position, 484 raysBack, 485 raysFront, 486 pvsBack, 487 pvsFront 488 ); 489 else { 470 float costRatio; 471 472 costRatio = BestCostRatio(leaf, 473 axis, 474 position, 475 raysBack, 476 raysFront, 477 pvsBack, 478 pvsFront 479 ); 480 481 // cout<<axis<<" r="<<costRatio<<endl; 482 483 if (costRatio > termMaxCostRatio) { 484 // cout<<"Too big cost ratio "<<costRatio<<endl; 485 stat.maxCostRatioNodes++; 486 return -1; 487 } 488 489 #if 0 490 cout<< 491 "pvs="<<leaf->mPvsSize<< 492 " rays="<<leaf->rays.size()<< 493 " rc="<<leaf->GetAvgRayContribution()<< 494 " axis="<<axis<<endl; 495 #endif 496 497 return axis; 498 } 499 500 501 float 502 VssTree::GetCostRatio( 503 VssTreeLeaf *leaf, 504 const int axis, 505 const float position, 506 const int raysBack, 507 const int raysFront, 508 const int pvsBack, 509 const int pvsFront 510 ) 511 { 512 bool costImportance = true; 513 514 float ratio; 515 AxisAlignedBox3 box; 516 float minBox, maxBox; 517 518 if (axis < 3) { 519 box = GetBBox(leaf); 520 minBox = box.Min(axis); 521 maxBox = box.Max(axis); 522 } else { 523 box = GetDirBBox(leaf); 524 minBox = box.Min(axis-3); 525 maxBox = box.Max(axis-3); 526 } 527 528 float sizeBox = maxBox - minBox; 529 530 int pvsSize = leaf->GetPvsSize(); 531 532 if (!costImportance) { 533 // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position); 534 float sum = pvsBack*(position - minBox) + pvsFront*(maxBox - position); 535 float newCost = ct_div_ci + sum/sizeBox; 536 float oldCost = pvsSize; 537 ratio = newCost/oldCost; 538 } else { 539 // importance based cost 540 #if 0 541 float newContrib = 542 ((position - minBox)*sqr(pvsBack/(raysBack + Limits::Small)) + 543 (maxBox - position)*sqr(pvsFront/(raysFront + Limits::Small)))/sizeBox; 544 545 // float newContrib = 546 // sqr(pvsBack/(raysBack + Limits::Small)) + 547 // sqr(pvsFront/(raysFront + Limits::Small)); 548 float oldContrib = sqr(leaf->GetAvgRayContribution()); 549 ratio = oldContrib/newContrib; 550 #else 551 #if 1 552 float newCost = raysBack*pvsBack + raysFront*pvsFront; 553 float oldCost = leaf->rays.size()*pvsSize; 554 ratio = newCost/oldCost; 555 #else 556 float newCost = (pvsBack + pvsFront)*0.5f; 557 float oldCost = pvsSize; 558 ratio = newCost/oldCost; 559 #endif 560 #endif 561 } 562 563 return ratio; 564 } 565 566 567 float 568 VssTree::EvalCostRatio( 569 VssTreeLeaf *leaf, 570 const int axis, 571 const float position, 572 int &raysBack, 573 int &raysFront, 574 int &pvsBack, 575 int &pvsFront 576 ) 577 { 578 raysBack = 0; 579 raysFront = 0; 580 pvsFront = 0; 581 pvsBack = 0; 582 583 584 Intersectable::NewMail(3); 585 586 if (axis <= VssTreeNode::SPLIT_Z) { 587 // this is the main ray classification loop! 588 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 589 ri != leaf->rays.end(); 590 ri++) 591 if ((*ri).mRay->IsActive()) { 592 593 // determine the side of this ray with respect to the plane 594 int side = (*ri).ComputeRayIntersection(axis, position, (*ri).mRay->mT); 595 // (*ri).mRay->mSide = side; 596 597 if (side <= 0) 598 raysBack++; 599 600 if (side >= 0) 601 raysFront++; 602 603 AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront); 604 } 605 606 } else { 607 608 // directional split 609 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 610 ri != leaf->rays.end(); 611 ri++) 612 if ((*ri).mRay->IsActive()) { 613 614 // determine the side of this ray with respect to the plane 615 int side; 616 if ((*ri).mRay->GetDirParametrization(axis - 3) > position) 617 side = 1; 618 else 619 side = -1; 620 621 if (side <= 0) 622 raysBack++; 623 624 if (side >= 0) 625 raysFront++; 626 627 // (*ri).mRay->mSide = side; 628 AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront); 629 630 } 631 } 632 633 float ratio = GetCostRatio( 634 leaf, 635 axis, 636 position, 637 raysBack, 638 raysFront, 639 pvsBack, 640 pvsFront); 641 642 // cout<<axis<<" "<<pvsSize<<" "<<pvsBack<<" "<<pvsFront<<endl; 643 // float oldCost = leaf->rays.size(); 644 645 // cout<<"ratio="<<ratio<<endl; 646 647 return ratio; 648 } 649 650 float 651 VssTree::BestCostRatio( 652 VssTreeLeaf *leaf, 653 int &axis, 654 float &position, 655 int &raysBack, 656 int &raysFront, 657 int &pvsBack, 658 int &pvsFront 659 ) 660 { 661 int nRaysBack[6], nRaysFront[6]; 662 int nPvsBack[6], nPvsFront[6]; 663 float nPosition[6]; 664 float nCostRatio[6]; 665 int bestAxis = -1; 666 667 AxisAlignedBox3 sBox = GetBBox(leaf); 668 AxisAlignedBox3 dBox = GetDirBBox(leaf); 669 // int sAxis = box.Size().DrivingAxis(); 670 int sAxis = sBox.Size().DrivingAxis(); 671 int dAxis = dBox.Size().DrivingAxis() + 3; 672 673 674 float dirSplitBoxSize = 0.01f; 675 bool allowDirSplit = Magnitude(sBox.Size())*dirSplitBoxSize < Magnitude(bbox.Size()); 676 677 678 for (axis = 0; axis < 5; axis++) { 679 if (!mSplitUseOnlyDrivingAxis || axis == sAxis || axis == dAxis) { 680 681 682 if (splitType == ESplitRegular) { 683 if (axis < 3) 684 nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis])*0.5f; 685 else 686 nPosition[axis] = (dBox.Min()[axis-3] + dBox.Max()[axis-3])*0.5f; 687 688 nCostRatio[axis] = EvalCostRatio(leaf, 689 axis, 690 nPosition[axis], 691 nRaysBack[axis], 692 nRaysFront[axis], 693 nPvsBack[axis], 694 nPvsFront[axis] 695 ); 696 } else 697 if (splitType == ESplitHeuristic) { 698 nCostRatio[axis] = EvalCostRatioHeuristic( 699 leaf, 700 axis, 701 nPosition[axis], 702 nRaysBack[axis], 703 nRaysFront[axis], 704 nPvsBack[axis], 705 nPvsFront[axis]); 706 } else 707 if (splitType == ESplitHybrid) { 708 if (leaf->depth > 7) 709 nCostRatio[axis] = EvalCostRatioHeuristic( 710 leaf, 711 axis, 712 nPosition[axis], 713 nRaysBack[axis], 714 nRaysFront[axis], 715 nPvsBack[axis], 716 nPvsFront[axis]); 717 else { 718 if (axis < 3) 719 nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis])*0.5f; 720 else 721 nPosition[axis] = (dBox.Min()[axis-3] + dBox.Max()[axis-3])*0.5f; 722 723 nCostRatio[axis] = EvalCostRatio(leaf, 724 axis, 725 nPosition[axis], 726 nRaysBack[axis], 727 nRaysFront[axis], 728 nPvsBack[axis], 729 nPvsFront[axis] 730 ); 731 } 732 } else { 490 733 cerr<<"VssTree: Unknown split heuristics\n"; 491 734 exit(1); 492 } 493 } 494 495 if (costRatio > termMaxCostRatio) { 496 // cout<<"Too big cost ratio "<<costRatio<<endl; 497 stat.maxCostRatioNodes++; 498 return -1; 499 } 500 501 #if 0 502 cout<< 503 "pvs="<<leaf->mPvsSize<< 504 " rays="<<leaf->rays.size()<< 505 " rc="<<leaf->GetAvgRayContribution()<< 506 " axis="<<axis<<endl; 507 #endif 508 509 return axis; 510 } 511 512 513 514 735 } 736 737 738 if ( bestAxis == -1) 739 bestAxis = axis; 740 else 741 if ( nCostRatio[axis] < nCostRatio[bestAxis] ) 742 bestAxis = axis; 743 } 744 } 745 746 axis = bestAxis; 747 position = nPosition[bestAxis]; 748 749 raysBack = nRaysBack[bestAxis]; 750 raysFront = nRaysFront[bestAxis]; 751 752 pvsBack = nPvsBack[bestAxis]; 753 pvsFront = nPvsFront[bestAxis]; 754 755 return nCostRatio[bestAxis]; 756 } 757 758 515 759 float 516 VssTree::EvalCostRatio( 517 VssTreeLeaf *leaf, 518 const int axis, 519 const float position, 520 int &raysBack, 521 int &raysFront, 522 int &pvsBack, 523 int &pvsFront 524 ) 525 { 526 raysBack = 0; 527 raysFront = 0; 528 pvsFront = 0; 529 pvsBack = 0; 530 531 532 Intersectable::NewMail(3); 533 bool costImportance = true; 534 // eval pvs size 535 int pvsSize = leaf->GetPvsSize(); 536 float ratio; 537 538 Intersectable::NewMail(3); 539 540 if (axis <= VssTreeNode::SPLIT_Z) { 541 // this is the main ray classification loop! 542 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 543 ri != leaf->rays.end(); 544 ri++) 545 if ((*ri).mRay->IsActive()) { 546 547 // determine the side of this ray with respect to the plane 548 int side = (*ri).ComputeRayIntersection(axis, position, (*ri).mRay->mT); 549 // (*ri).mRay->mSide = side; 550 551 if (side <= 0) 552 raysBack++; 553 554 if (side >= 0) 555 raysFront++; 556 557 AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront); 558 } 559 560 AxisAlignedBox3 box = GetBBox(leaf); 561 562 float minBox = box.Min(axis); 563 float maxBox = box.Max(axis); 564 float sizeBox = maxBox - minBox; 565 566 if (!costImportance) { 760 VssTree::EvalCostRatioHeuristic( 761 VssTreeLeaf *leaf, 762 const int axis, 763 float &bestPosition, 764 int &raysBack, 765 int &raysFront, 766 int &pvsBack, 767 int &pvsFront 768 ) 769 { 770 AxisAlignedBox3 box; 771 float minBox, maxBox; 772 773 if (axis < 3) { 774 box = GetBBox(leaf); 775 minBox = box.Min(axis); 776 maxBox = box.Max(axis); 777 } 778 else { 779 box = GetDirBBox(leaf); 780 minBox = box.Min(axis-3); 781 maxBox = box.Max(axis-3); 782 } 783 784 SortSplitCandidates(leaf, axis); 785 786 // go through the lists, count the number of objects left and right 787 // and evaluate the following cost funcion: 788 // C = ct_div_ci + (ql*rl + qr*rr)/queries 789 790 int rl=0, rr = leaf->rays.size(); 791 int pl=0, pr = leaf->GetPvsSize(); 792 float sizeBox = maxBox - minBox; 793 794 float minBand = minBox + 0.1*(maxBox - minBox); 795 float maxBand = minBox + 0.9*(maxBox - minBox); 796 797 float minRatio = 1e20; 798 799 Intersectable::NewMail(); 800 // set all object as belonging to the fron pvs 801 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 802 ri != leaf->rays.end(); 803 ri++) 804 if ((*ri).mRay->IsActive()) { 805 Intersectable *object = (*ri).mRay->mTerminationObject; 806 if (object) 807 if (!object->Mailed()) { 808 object->Mail(); 809 object->mCounter = 1; 810 } else 811 object->mCounter++; 812 } 813 814 Intersectable::NewMail(); 815 816 for(vector<SortableEntry>::const_iterator ci = splitCandidates->begin(); 817 ci < splitCandidates->end(); 818 ci++) { 819 VssRay *ray; 820 switch ((*ci).type) { 821 case SortableEntry::ERayMin: { 822 rl++; 823 ray = (VssRay *) (*ci).data; 824 Intersectable *object = ray->mTerminationObject; 825 if (object && !object->Mailed()) { 826 object->Mail(); 827 pl++; 828 } 829 break; 830 } 831 case SortableEntry::ERayMax: { 832 rr--; 833 ray = (VssRay *) (*ci).data; 834 Intersectable *object = ray->mTerminationObject; 835 if (object) { 836 if (--object->mCounter == 0) 837 pr--; 838 } 839 break; 840 } 841 } 842 843 float position = (*ci).value; 844 845 if (position > minBand && position < maxBand) { 567 846 568 // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position); 569 float sum = pvsBack*(position - minBox) + pvsFront*(maxBox - position); 570 float newCost = ct_div_ci + sum/sizeBox; 571 float oldCost = pvsSize; 572 ratio = newCost/oldCost; 573 } else { 574 // importance based cost 575 #if 0 576 float newContrib = 577 ((position - minBox)*sqr(pvsBack/(raysBack + Limits::Small)) + 578 (maxBox - position)*sqr(pvsFront/(raysFront + Limits::Small)))/sizeBox; 579 580 // float newContrib = 581 // sqr(pvsBack/(raysBack + Limits::Small)) + 582 // sqr(pvsFront/(raysFront + Limits::Small)); 583 float oldContrib = sqr(leaf->GetAvgRayContribution()); 584 ratio = oldContrib/newContrib; 585 #else 586 float newCost = raysBack*pvsBack + raysFront*pvsFront; 587 float oldCost = leaf->rays.size()*pvsSize; 588 ratio = newCost/oldCost; 589 #endif 590 } 591 592 } else { 593 594 // directional split 595 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 596 ri != leaf->rays.end(); 597 ri++) 598 if ((*ri).mRay->IsActive()) { 599 600 // determine the side of this ray with respect to the plane 601 int side; 602 if ((*ri).mRay->GetDirParametrization(axis - 3) > position) 603 side = 1; 604 else 605 side = -1; 606 607 if (side <= 0) 608 raysBack++; 609 610 if (side >= 0) 611 raysFront++; 612 613 // (*ri).mRay->mSide = side; 614 AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront); 615 616 } 617 618 AxisAlignedBox3 box = GetDirBBox(leaf); 619 620 float minBox = box.Min(axis-3); 621 float maxBox = box.Max(axis-3); 622 float sizeBox = maxBox - minBox; 623 624 if (!costImportance) { 847 float ratio = GetCostRatio( 848 leaf, 849 axis, 850 position, 851 rl, 852 rr, 853 pl, 854 pr); 625 855 626 float directionalPenalty = 1.0f;627 float sum =628 (pvsBack*(position - minBox) +629 pvsFront*(maxBox - position))*directionalPenalty;630 float newCost = ct_div_ci + sum/sizeBox;631 float oldCost = pvsSize;632 ratio = newCost/oldCost;633 } else {634 #if 0635 float directionalPenalty = 0.7f;636 // importance based cost637 float newContrib =638 directionalPenalty*((position - minBox)*sqr(pvsBack/(raysBack + Limits::Small)) +639 (maxBox - position)*sqr(pvsFront/(raysFront + Limits::Small)))/sizeBox;640 float oldContrib = sqr(leaf->GetAvgRayContribution());641 ratio = oldContrib/newContrib;642 #else643 float newCost = raysBack*pvsBack + raysFront*pvsFront;644 float oldCost = leaf->rays.size()*pvsSize;645 ratio = newCost/oldCost;646 #endif647 }648 }649 // cout<<axis<<" "<<pvsSize<<" "<<pvsBack<<" "<<pvsFront<<endl;650 // float oldCost = leaf->rays.size();651 652 // cout<<"ratio="<<ratio<<endl;653 return ratio;654 }655 656 float657 VssTree::BestCostRatioRegular(658 VssTreeLeaf *leaf,659 int &axis,660 float &position,661 int &raysBack,662 int &raysFront,663 int &pvsBack,664 int &pvsFront665 )666 {667 int nRaysBack[6], nRaysFront[6];668 int nPvsBack[6], nPvsFront[6];669 float nPosition[6];670 float nCostRatio[6];671 int bestAxis = -1;672 673 AxisAlignedBox3 sBox = GetBBox(leaf);674 AxisAlignedBox3 dBox = GetDirBBox(leaf);675 // int sAxis = box.Size().DrivingAxis();676 int sAxis = sBox.Size().DrivingAxis();677 int dAxis = dBox.Size().DrivingAxis() + 3;678 679 bool onlyDrivingAxis = false;680 681 float dirSplitBoxSize = 0.01f;682 bool allowDirSplit = Magnitude(sBox.Size())*dirSplitBoxSize < Magnitude(bbox.Size());683 684 685 for (axis = 0; axis < 5; axis++) {686 if (!onlyDrivingAxis || axis == sAxis || axis == dAxis) {687 if (axis < 3)688 nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis])*0.5f;689 else690 nPosition[axis] = (dBox.Min()[axis-3] + dBox.Max()[axis-3])*0.5f;691 856 692 nCostRatio[axis] = EvalCostRatio(leaf, 693 axis, 694 nPosition[axis], 695 nRaysBack[axis], 696 nRaysFront[axis], 697 nPvsBack[axis], 698 nPvsFront[axis] 699 ); 857 // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 858 // cout<<"cost= "<<sum<<endl; 700 859 701 if ( bestAxis == -1) 702 bestAxis = axis; 703 else 704 if ( nCostRatio[axis] < nCostRatio[bestAxis] ) 705 bestAxis = axis; 706 } 707 } 708 709 axis = bestAxis; 710 position = nPosition[bestAxis]; 711 712 raysBack = nRaysBack[bestAxis]; 713 raysFront = nRaysFront[bestAxis]; 714 715 pvsBack = nPvsBack[bestAxis]; 716 pvsFront = nPvsFront[bestAxis]; 717 718 return nCostRatio[bestAxis]; 719 } 720 721 float 722 VssTree::BestCostRatioHeuristic( 723 VssTreeLeaf *leaf, 724 int &axis, 725 float &position, 726 int &raysBack, 727 int &raysFront, 728 int &pvsBack, 729 int &pvsFront 730 ) 731 { 732 AxisAlignedBox3 box = GetBBox(leaf); 733 // AxisAlignedBox3 dirBox = GetDirBBox(node); 734 735 axis = box.Size().DrivingAxis(); 736 737 SortSplitCandidates(leaf, axis); 738 739 // go through the lists, count the number of objects left and right 740 // and evaluate the following cost funcion: 741 // C = ct_div_ci + (ql*rl + qr*rr)/queries 742 743 int rl=0, rr = leaf->rays.size(); 744 int pl=0, pr = leaf->GetPvsSize(); 745 float minBox = box.Min(axis); 746 float maxBox = box.Max(axis); 747 float sizeBox = maxBox - minBox; 748 749 float minBand = minBox + 0.1*(maxBox - minBox); 750 float maxBand = minBox + 0.9*(maxBox - minBox); 751 752 float sum = rr*sizeBox; 753 float minSum = 1e20; 754 755 Intersectable::NewMail(); 756 // set all object as belonging to the fron pvs 757 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 758 ri != leaf->rays.end(); 759 ri++) 760 if ((*ri).mRay->IsActive()) { 761 Intersectable *object = (*ri).mRay->mTerminationObject; 762 if (object) 763 if (!object->Mailed()) { 764 object->Mail(); 765 object->mCounter = 1; 766 } else 767 object->mCounter++; 768 } 769 770 Intersectable::NewMail(); 771 772 for(vector<SortableEntry>::const_iterator ci = splitCandidates->begin(); 773 ci < splitCandidates->end(); 774 ci++) { 775 VssRay *ray; 776 switch ((*ci).type) { 777 case SortableEntry::ERayMin: { 778 rl++; 779 ray = (VssRay *) (*ci).data; 780 Intersectable *object = ray->mTerminationObject; 781 if (object && !object->Mailed()) { 782 object->Mail(); 783 pl++; 784 } 785 break; 786 } 787 case SortableEntry::ERayMax: { 788 rr--; 789 ray = (VssRay *) (*ci).data; 790 Intersectable *object = ray->mTerminationObject; 791 if (object) { 792 if (--object->mCounter == 0) 793 pr--; 794 } 795 break; 796 } 797 } 798 if ((*ci).value > minBand && (*ci).value < maxBand) { 799 800 sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value); 801 802 // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 803 // cout<<"cost= "<<sum<<endl; 804 805 if (sum < minSum) { 806 minSum = sum; 807 position = (*ci).value; 808 809 raysBack = rl; 810 raysFront = rr; 811 812 pvsBack = pl; 813 pvsFront = pr; 860 if (ratio < minRatio) { 861 minRatio = ratio; 862 bestPosition = position; 863 864 raysBack = rl; 865 raysFront = rr; 866 867 pvsBack = pl; 868 pvsFront = pr; 814 869 815 870 } 816 871 } 817 872 } 818 819 float oldCost = leaf->GetPvsSize(); 820 float newCost = ct_div_ci + minSum/sizeBox; 821 float ratio = newCost/oldCost; 873 822 874 823 875 // cout<<"===================="<<endl; 824 876 // cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox) 825 877 // <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl; 826 return ratio;878 return minRatio; 827 879 } 828 880 829 881 void 830 882 VssTree::SortSplitCandidates( 831 832 833 883 VssTreeLeaf *node, 884 const int axis 885 ) 834 886 { 835 887 … … 851 903 ri < node->rays.end(); 852 904 ri++) { 853 bool positive = (*ri).mRay->HasPosDir(axis); 854 splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : 855 SortableEntry::ERayMax, 856 (*ri).ExtrapOrigin(axis), 857 (void *)&*ri) 858 ); 859 860 splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : 861 SortableEntry::ERayMin, 862 (*ri).ExtrapTermination(axis), 863 (void *)&*ri) 864 ); 865 } 866 905 if ((*ri).mRay->IsActive()) { 906 if (axis < 3) { 907 bool positive = (*ri).mRay->HasPosDir(axis); 908 splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : 909 SortableEntry::ERayMax, 910 (*ri).ExtrapOrigin(axis), 911 (void *)(*ri).mRay) 912 ); 913 914 splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : 915 SortableEntry::ERayMin, 916 (*ri).ExtrapTermination(axis), 917 (void *)(*ri).mRay) 918 ); 919 } else { 920 float pos = (*ri).mRay->GetDirParametrization(axis-3); 921 splitCandidates->push_back(SortableEntry(SortableEntry::ERayMin, 922 pos - Limits::Small, 923 (void *)(*ri).mRay) 924 ); 925 926 splitCandidates->push_back(SortableEntry(SortableEntry::ERayMax, 927 pos + Limits::Small, 928 (void *)(*ri).mRay) 929 ); 930 } 931 } 932 } 933 867 934 stable_sort(splitCandidates->begin(), splitCandidates->end()); 868 935 } … … 879 946 stat.maxDepthNodes++; 880 947 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 948 // if ( (int)(leaf->rays.size()) < termMinCost) 949 // stat.minCostNodes++; 950 if ( leaf->GetPvsSize() < termMinPvs) 951 stat.minPvsNodes++; 952 953 if ( leaf->GetPvsSize() < termMinRays) 954 stat.minRaysNodes++; 955 956 if (0 && leaf->GetAvgRayContribution() > termMaxRayContribution ) 957 stat.maxRayContribNodes++; 958 959 if (SqrMagnitude(data.bbox.Size()) <= termMinSize) { 960 stat.minSizeNodes++; 961 } 962 963 if ( (int)(leaf->rays.size()) > stat.maxRayRefs) 897 964 stat.maxRayRefs = leaf->rays.size(); 898 965 … … 902 969 VssTree::TerminationCriteriaSatisfied(VssTreeLeaf *leaf) 903 970 { 904 return ( (leaf->GetPvsSize() < termMinPvs) || 905 (leaf->rays.size() < termMinRays) || 906 // (leaf->GetAvgRayContribution() > termMaxRayContribution ) || 907 (leaf->depth >= termMaxDepth) || 908 SqrMagnitude(GetBBox(leaf).Size()) <= termMinSize ); 971 return ( (leaf->GetPvsSize() < termMinPvs) || 972 (leaf->rays.size() < termMinRays) || 973 // (leaf->GetAvgRayContribution() > termMaxRayContribution ) || 974 (leaf->depth >= termMaxDepth) || 975 (SqrMagnitude(GetBBox(leaf).Size()) <= termMinSize) || 976 (mUseRss && leaf->mPassingRays == leaf->rays.size()) 977 ); 909 978 } 910 979 … … 912 981 VssTreeNode * 913 982 VssTree::SubdivideNode( 914 915 916 917 918 919 { 920 921 983 VssTreeLeaf *leaf, 984 const AxisAlignedBox3 &box, 985 AxisAlignedBox3 &backBBox, 986 AxisAlignedBox3 &frontBBox 987 ) 988 { 989 990 if (TerminationCriteriaSatisfied(leaf)) { 922 991 #if 0 923 924 925 926 992 if (leaf->depth >= termMaxDepth) { 993 cout<<"Warning: max depth reached depth="<<(int)leaf->depth<<" rays="<<leaf->rays.size()<<endl; 994 cout<<"Bbox: "<<GetBBox(leaf)<<" dirbbox:"<<GetDirBBox(leaf)<<endl; 995 } 927 996 #endif 928 997 929 930 931 932 933 934 998 return leaf; 999 } 1000 1001 float position; 1002 1003 // first count ray sides 935 1004 int raysBack; 936 1005 int raysFront; 937 938 1006 int pvsBack; 1007 int pvsFront; 939 1008 940 1009 // select subdivision axis 941 1010 int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront); 942 943 944 945 1011 // cout<<axis<<" "; 1012 1013 // cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<< 1014 // pvsFront<<endl; 946 1015 947 1016 if (axis == -1) { … … 964 1033 965 1034 VssTreeLeaf *back = new VssTreeLeaf(node, raysBack); 966 back->SetPvsSize(pvsBack);967 1035 VssTreeLeaf *front = new VssTreeLeaf(node, raysFront); 968 front->SetPvsSize(pvsFront);969 1036 970 1037 // replace a link from node's parent … … 975 1042 976 1043 if (axis <= VssTreeNode::SPLIT_Z) { 977 1044 backBBox.SetMax(axis, position); 978 1045 frontBBox.SetMin(axis, position); 979 1046 980 981 982 1047 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 1048 ri != leaf->rays.end(); 1049 ri++) { 983 1050 if ((*ri).mRay->IsActive()) { 984 1051 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1052 // first unref ray from the former leaf 1053 (*ri).mRay->Unref(); 1054 1055 // Debug << "computed t: " << (*ri).mRay->mT << endl; 1056 // determine the side of this ray with respect to the plane 1057 int side = node->ComputeRayIntersection(*ri, (*ri).mRay->mT); 1058 1059 if (side == 0) { 1060 if ((*ri).mRay->HasPosDir(axis)) { 1061 back->AddRay(VssTreeNode::RayInfo((*ri).mRay, 1062 (*ri).mMinT, 1063 (*ri).mRay->mT) 1064 ); 1065 front->AddRay(VssTreeNode::RayInfo((*ri).mRay, 1066 (*ri).mRay->mT, 1067 (*ri).mMaxT)); 1068 } else { 1069 back->AddRay(VssTreeNode::RayInfo((*ri).mRay, 1070 (*ri).mRay->mT, 1071 (*ri).mMaxT)); 1072 front->AddRay(VssTreeNode::RayInfo((*ri).mRay, 1073 (*ri).mMinT, 1074 (*ri).mRay->mT)); 1075 } 1076 } else 1077 if (side == 1) 1078 front->AddRay(*ri); 1079 else 1080 back->AddRay(*ri); 1014 1081 } else 1015 1082 (*ri).mRay->Unref(); 1016 1083 } 1017 1084 } else { … … 1020 1087 1021 1088 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 1022 1023 1089 ri != leaf->rays.end(); 1090 ri++) { 1024 1091 if ((*ri).mRay->IsActive()) { 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1092 // first unref ray from the former leaf 1093 (*ri).mRay->Unref(); 1094 1095 int side; 1096 if ((*ri).mRay->GetDirParametrization(axis - 3) > position) 1097 side = 1; 1098 else 1099 side = -1; 1100 1101 if (side == 1) 1102 front->AddRay(*ri); 1103 else 1104 back->AddRay(*ri); 1038 1105 1039 1106 } else 1040 1107 (*ri).mRay->Unref(); 1041 1108 } 1042 1109 } 1043 1110 1111 front->SetPvsSize(pvsFront); 1112 back->SetPvsSize(pvsBack); 1113 1044 1114 // update stats 1045 1115 stat.rayRefs -= leaf->rays.size(); … … 1076 1146 // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl; 1077 1147 if (in->depth >= minCollapseDepth && 1078 in->lastAccessTime <= maxAccessTime) {1079 released = CollapseSubtree(node, time);1080 break;1148 in->lastAccessTime <= maxAccessTime) { 1149 released = CollapseSubtree(node, time); 1150 break; 1081 1151 } 1082 1152 1083 1153 if (in->back->GetAccessTime() < 1084 in->front->GetAccessTime()) {1085 tstack.push(in->front);1086 tstack.push(in->back);1154 in->front->GetAccessTime()) { 1155 tstack.push(in->front); 1156 tstack.push(in->back); 1087 1157 } else { 1088 tstack.push(in->back);1089 tstack.push(in->front);1158 tstack.push(in->back); 1159 tstack.push(in->front); 1090 1160 } 1091 1161 } … … 1106 1176 VssTreeNode * 1107 1177 VssTree::SubdivideLeaf( 1108 1109 1178 VssTreeLeaf *leaf 1179 ) 1110 1180 { 1111 1181 VssTreeNode *node = leaf; … … 1113 1183 AxisAlignedBox3 leafBBox = GetBBox(leaf); 1114 1184 1115 1116 1185 static int pass = 0; 1186 pass ++; 1117 1187 1118 1188 // check if we should perform a dynamic subdivision of the leaf 1119 1189 if (!TerminationCriteriaSatisfied(leaf)) { 1120 1190 1121 1191 // memory check and realese... 1122 1192 if (GetMemUsage() > maxTotalMemory) { 1123 1193 ReleaseMemory( pass ); … … 1129 1199 node = 1130 1200 SubdivideNode(leaf, 1131 1132 1133 1134 1201 leafBBox, 1202 backBBox, 1203 frontBBox 1204 ); 1135 1205 } 1136 1206 … … 1142 1212 void 1143 1213 VssTree::UpdateRays(VssRayContainer &remove, 1144 1145 1214 VssRayContainer &add 1215 ) 1146 1216 { 1147 1217 VssTreeLeaf::NewMail(); … … 1160 1230 ri++) { 1161 1231 if ((*ri)->ScheduledForRemoval()) 1162 // RemoveRay(*ri, NULL, false);1163 // !!! BUG - with true it does not work correctly - aggreated delete1232 // RemoveRay(*ri, NULL, false); 1233 // !!! BUG - with true it does not work correctly - aggreated delete 1164 1234 RemoveRay(*ri, NULL, true); 1165 1235 else … … 1173 1243 ri != add.end(); 1174 1244 ri++) { 1175 1176 1177 1245 VssTreeNode::RayInfo info(*ri); 1246 if (ClipRay(info, bbox)) 1247 AddRay(info); 1178 1248 } 1179 1249 } … … 1182 1252 void 1183 1253 VssTree::RemoveRay(VssRay *ray, 1184 1185 1186 1254 vector<VssTreeLeaf *> *affectedLeaves, 1255 const bool removeAllScheduledRays 1256 ) 1187 1257 { 1188 1258 … … 1211 1281 1212 1282 if (!leaf->Mailed()) { 1213 leaf->Mail();1214 if (affectedLeaves)1215 affectedLeaves->push_back(leaf);1216 1217 if (removeAllScheduledRays) {1218 int tail = leaf->rays.size()-1;1219 1220 for (int i=0; i < (int)(leaf->rays.size()); i++) {1221 1222 1223 1224 stat.removedRayRefs++;1225 leaf->rays[tail].mRay->Unref();1226 leaf->rays.pop_back();1227 tail--;1228 1229 1230 1231 break;1283 leaf->Mail(); 1284 if (affectedLeaves) 1285 affectedLeaves->push_back(leaf); 1286 1287 if (removeAllScheduledRays) { 1288 int tail = leaf->rays.size()-1; 1289 1290 for (int i=0; i < (int)(leaf->rays.size()); i++) { 1291 if (leaf->rays[i].mRay->ScheduledForRemoval()) { 1292 // find a ray to replace it with 1293 while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) { 1294 stat.removedRayRefs++; 1295 leaf->rays[tail].mRay->Unref(); 1296 leaf->rays.pop_back(); 1297 tail--; 1298 } 1299 1300 if (tail < i) 1301 break; 1232 1302 1233 1234 1235 1236 1237 1238 1239 }1240 }1303 stat.removedRayRefs++; 1304 leaf->rays[i].mRay->Unref(); 1305 leaf->rays[i] = leaf->rays[tail]; 1306 leaf->rays.pop_back(); 1307 tail--; 1308 } 1309 } 1310 } 1241 1311 } 1242 1312 1243 1313 if (!removeAllScheduledRays) 1244 for (int i=0; i < (int)leaf->rays.size(); i++) {1245 if (leaf->rays[i].mRay == ray) {1246 1247 1248 1249 1250 1251 1252 }1253 }1314 for (int i=0; i < (int)leaf->rays.size(); i++) { 1315 if (leaf->rays[i].mRay == ray) { 1316 stat.removedRayRefs++; 1317 ray->Unref(); 1318 leaf->rays[i] = leaf->rays[leaf->rays.size()-1]; 1319 leaf->rays.pop_back(); 1320 // check this ray again 1321 break; 1322 } 1323 } 1254 1324 1255 1325 } … … 1292 1362 void 1293 1363 VssTree::TraverseInternalNode( 1294 1295 1364 RayTraversalData &data, 1365 stack<RayTraversalData> &tstack) 1296 1366 { 1297 1367 VssTreeInterior *in = (VssTreeInterior *) data.node; … … 1301 1371 // determine the side of this ray with respect to the plane 1302 1372 int side = in->ComputeRayIntersection(data.rayData, 1303 1373 data.rayData.mRay->mT); 1304 1374 1305 1375 1306 1376 if (side == 0) { 1307 1377 if (data.rayData.mRay->HasPosDir(in->axis)) { 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1378 tstack.push(RayTraversalData(in->back, 1379 VssTreeNode::RayInfo(data.rayData.mRay, 1380 data.rayData.mMinT, 1381 data.rayData.mRay->mT)) 1382 ); 1383 1384 tstack.push(RayTraversalData(in->front, 1385 VssTreeNode::RayInfo(data.rayData.mRay, 1386 data.rayData.mRay->mT, 1387 data.rayData.mMaxT 1388 )) 1389 ); 1320 1390 1321 1391 } else { 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1392 tstack.push(RayTraversalData(in->back, 1393 VssTreeNode::RayInfo(data.rayData.mRay, 1394 data.rayData.mRay->mT, 1395 data.rayData.mMaxT 1396 )) 1397 ); 1398 1399 tstack.push(RayTraversalData(in->front, 1400 VssTreeNode::RayInfo(data.rayData.mRay, 1401 data.rayData.mMinT, 1402 data.rayData.mRay->mT)) 1403 ); 1334 1404 1335 1405 … … 1337 1407 } else 1338 1408 if (side == 1) 1339 1409 tstack.push(RayTraversalData(in->front, data.rayData)); 1340 1410 else 1341 1411 tstack.push(RayTraversalData(in->back, data.rayData)); 1342 1412 } 1343 1413 else { 1344 1414 // directional split 1345 1346 1347 1348 1415 if (data.rayData.mRay->GetDirParametrization(in->axis - 3) > in->position) 1416 tstack.push(RayTraversalData(in->front, data.rayData)); 1417 else 1418 tstack.push(RayTraversalData(in->back, data.rayData)); 1349 1419 } 1350 1420 } … … 1367 1437 #endif 1368 1438 1369 // tstat.collapsedSubtrees++;1370 // tstat.collapseDepths += (int)sroot->depth;1371 // tstat.collapseAccessTimes += time - sroot->GetAccessTime();1439 // tstat.collapsedSubtrees++; 1440 // tstat.collapseDepths += (int)sroot->depth; 1441 // tstat.collapseAccessTimes += time - sroot->GetAccessTime(); 1372 1442 1373 1443 tstack.push(sroot); … … 1382 1452 VssTreeLeaf *leaf = (VssTreeLeaf *) node; 1383 1453 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 1384 1385 1386 1387 1388 1389 1390 1391 1454 ri != leaf->rays.end(); 1455 ri++) { 1456 1457 totalRayCount++; 1458 if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed()) { 1459 (*ri).mRay->Mail(); 1460 rayCount++; 1461 } 1392 1462 } 1393 1463 } else { … … 1416 1486 1417 1487 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1488 ri != leaf->rays.end(); 1489 ri++) { 1490 1491 // unref this ray from the old node 1492 1493 if ((*ri).mRay->IsActive()) { 1494 (*ri).mRay->Unref(); 1495 if (!(*ri).mRay->Mailed()) { 1496 (*ri).mRay->Mail(); 1497 newLeaf->AddRay(*ri); 1498 } 1499 } else 1500 (*ri).mRay->Unref(); 1431 1501 1432 1502 } … … 1440 1510 delete sroot; 1441 1511 1442 // for(VssTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin();1443 // ri != newLeaf->rays.end();1444 // ri++)1445 // (*ri).ray->UnMail(2);1512 // for(VssTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin(); 1513 // ri != newLeaf->rays.end(); 1514 // ri++) 1515 // (*ri).ray->UnMail(2); 1446 1516 1447 1517 … … 1460 1530 #endif 1461 1531 1462 1463 1532 // tstat.collapsedNodes += collapsedNodes; 1533 // tstat.collapsedRays += totalRayCount - rayCount; 1464 1534 1465 1535 return totalRayCount - rayCount; … … 1468 1538 1469 1539 int 1470 VssTree::GetPvsSize( VssTreeNode *node,const AxisAlignedBox3 &box) const1471 { 1472 1540 VssTree::GetPvsSize(const AxisAlignedBox3 &box) const 1541 { 1542 stack<VssTreeNode *> tstack; 1473 1543 tstack.push(root); 1474 1544 1475 1476 1545 Intersectable::NewMail(); 1546 int pvsSize = 0; 1477 1547 1478 1548 while (!tstack.empty()) { … … 1482 1552 1483 1553 if (node->IsLeaf()) { 1484 1485 1486 1487 1488 1489 1554 VssTreeLeaf *leaf = (VssTreeLeaf *)node; 1555 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 1556 ri != leaf->rays.end(); 1557 ri++) 1558 if ((*ri).mRay->IsActive()) { 1559 Intersectable *object; 1490 1560 #if BIDIRECTIONAL_RAY 1491 1492 1493 1494 1495 1561 object = (*ri).mRay->mOriginObject; 1562 if (object && !object->Mailed()) { 1563 pvsSize++; 1564 object->Mail(); 1565 } 1496 1566 #endif 1497 object = (*ri).mRay->mTerminationObject; 1498 if (object && !object->Mailed()) { 1499 pvsSize++; 1500 object->Mail(); 1501 } 1502 } 1503 } else { 1504 VssTreeInterior *in = (VssTreeInterior *)node; 1505 if (in->axis < 3) { 1506 if (box.Max(in->axis) >= in->position ) 1507 tstack.push(in->front); 1508 1509 if (box.Min(in->axis) <= in->position ) 1510 tstack.push(in->back); 1511 } else { 1512 // both nodes for directional splits 1513 tstack.push(in->front); 1514 tstack.push(in->back); 1515 } 1567 object = (*ri).mRay->mTerminationObject; 1568 if (object && !object->Mailed()) { 1569 pvsSize++; 1570 object->Mail(); 1571 } 1516 1572 } 1517 } 1518 return pvsSize; 1573 } else { 1574 VssTreeInterior *in = (VssTreeInterior *)node; 1575 if (in->axis < 3) { 1576 if (box.Max(in->axis) >= in->position ) 1577 tstack.push(in->front); 1578 1579 if (box.Min(in->axis) <= in->position ) 1580 tstack.push(in->back); 1581 } else { 1582 // both nodes for directional splits 1583 tstack.push(in->front); 1584 tstack.push(in->back); 1585 } 1586 } 1587 } 1588 return pvsSize; 1519 1589 } 1520 1590 1521 1591 void 1522 1592 VssTree::GetRayContributionStatistics( 1523 1524 1525 1526 1527 { 1528 1593 float &minRayContribution, 1594 float &maxRayContribution, 1595 float &avgRayContribution 1596 ) 1597 { 1598 stack<VssTreeNode *> tstack; 1529 1599 tstack.push(root); 1530 1600 1531 1532 1533 1534 1601 minRayContribution = 1.0f; 1602 maxRayContribution = 0.0f; 1603 float sumRayContribution = 0.0f; 1604 int leaves = 0; 1535 1605 1536 1606 while (!tstack.empty()) { … … 1539 1609 1540 1610 if (node->IsLeaf()) { 1541 1542 1543 1544 1545 1546 1547 1548 1611 leaves++; 1612 VssTreeLeaf *leaf = (VssTreeLeaf *)node; 1613 float c = leaf->GetAvgRayContribution(); 1614 if (c > maxRayContribution) 1615 maxRayContribution = c; 1616 if (c < minRayContribution) 1617 minRayContribution = c; 1618 sumRayContribution += c; 1549 1619 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1620 } else { 1621 VssTreeInterior *in = (VssTreeInterior *)node; 1622 // both nodes for directional splits 1623 tstack.push(in->front); 1624 tstack.push(in->back); 1625 } 1626 } 1627 1628 cout<<"sum="<<sumRayContribution<<endl; 1629 cout<<"leaves="<<leaves<<endl; 1630 avgRayContribution = sumRayContribution/(float)leaves; 1561 1631 } 1562 1632 … … 1564 1634 int 1565 1635 VssTree::GenerateRays(const float ratioPerLeaf, 1566 1567 { 1568 1636 SimpleRayContainer &rays) 1637 { 1638 stack<VssTreeNode *> tstack; 1569 1639 tstack.push(root); 1570 1640 … … 1574 1644 1575 1645 if (node->IsLeaf()) { 1576 1577 1578 1579 1580 1581 1582 1583 1584 Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));1585 1586 1587 1646 VssTreeLeaf *leaf = (VssTreeLeaf *)node; 1647 float c = leaf->GetAvgRayContribution(); 1648 int num = (c*ratioPerLeaf + 0.5); 1649 // cout<<num<<" "; 1650 1651 for (int i=0; i < num; i++) { 1652 Vector3 origin = GetBBox(leaf).GetRandomPoint(); 1653 Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint(); 1654 Vector3 direction = VssRay::GetDirection(dirVector.x, dirVector.y); 1655 //cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl; 1656 rays.push_back(SimpleRay(origin, direction)); 1657 } 1588 1658 1589 1590 1591 1592 1593 1594 1595 1596 1597 1659 } else { 1660 VssTreeInterior *in = (VssTreeInterior *)node; 1661 // both nodes for directional splits 1662 tstack.push(in->front); 1663 tstack.push(in->back); 1664 } 1665 } 1666 1667 return rays.size(); 1598 1668 } 1599 1669 … … 1601 1671 VssTree::CollectLeaves(vector<VssTreeLeaf *> &leaves) 1602 1672 { 1603 1673 stack<VssTreeNode *> tstack; 1604 1674 tstack.push(root); 1605 1675 … … 1609 1679 1610 1680 if (node->IsLeaf()) { 1611 VssTreeLeaf *leaf = (VssTreeLeaf *)node; 1612 leaves.push_back(leaf); 1613 } else { 1614 VssTreeInterior *in = (VssTreeInterior *)node; 1615 // both nodes for directional splits 1616 tstack.push(in->front); 1617 tstack.push(in->back); 1618 } 1619 } 1681 VssTreeLeaf *leaf = (VssTreeLeaf *)node; 1682 leaves.push_back(leaf); 1683 } else { 1684 VssTreeInterior *in = (VssTreeInterior *)node; 1685 // both nodes for directional splits 1686 tstack.push(in->front); 1687 tstack.push(in->back); 1688 } 1689 } 1690 } 1691 1692 bool 1693 VssTree::ValidLeaf(VssTreeLeaf *leaf) const 1694 { 1695 return leaf->rays.size() > termMinRays/4; 1696 } 1697 1698 void 1699 GenerateExtendedConvexCombinationWeights(float &w1, 1700 float &w2, 1701 float &w3, 1702 const float overlap 1703 ) 1704 { 1705 w1 = RandomValue(-overlap, 1.0f + overlap); 1706 w2 = RandomValue(-overlap, 1.0f + overlap); 1707 w3 = RandomValue(-overlap, 1.0f + overlap); 1708 1709 float c = 1.0f/(w1 + w2 + w3); 1710 w1 *= c; 1711 w2 *= c; 1712 w3 *= c; 1713 } 1714 1715 void 1716 VssTree::GenerateLeafRays(VssTreeLeaf *leaf, 1717 const int numberOfRays, 1718 SimpleRayContainer &rays) 1719 { 1720 int nrays = leaf->rays.size(); 1721 for (int i=0; i < numberOfRays; i++) { 1722 // pickup 3 random rays 1723 int r1 = Random(nrays-1); 1724 int r2 = Random(nrays-1); 1725 int r3 = Random(nrays-1); 1726 1727 Vector3 o1 = leaf->rays[r1].Extrap(RandomValue(leaf->rays[r1].GetMinT(), 1728 leaf->rays[r1].GetMaxT())); 1729 1730 Vector3 o2 = leaf->rays[r2].Extrap(RandomValue(leaf->rays[r2].GetMinT(), 1731 leaf->rays[r2].GetMaxT())); 1732 1733 Vector3 o3 = leaf->rays[r3].Extrap(RandomValue(leaf->rays[r3].GetMinT(), 1734 leaf->rays[r3].GetMaxT())); 1735 1736 const float overlap = 0.1; 1737 1738 Vector3 origin, direction; 1739 bool useExtendedConvexCombination = true; 1740 if (useExtendedConvexCombination) { 1741 float w1, w2, w3; 1742 GenerateExtendedConvexCombinationWeights(w1, w2, w3, overlap); 1743 origin = w1*o1 + w2*o2 + w3*o3; 1744 direction = 1745 w1*leaf->rays[r1].mRay->GetDir() + 1746 w2*leaf->rays[r2].mRay->GetDir() + 1747 w3*leaf->rays[r3].mRay->GetDir(); 1748 } else { 1749 origin = GetBBox(leaf).GetRandomPoint(); 1750 Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint(); 1751 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x)); 1752 } 1753 //cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl; 1754 rays.push_back(SimpleRay(origin, direction)); 1755 } 1620 1756 } 1621 1757 1622 1758 int 1623 1759 VssTree::GenerateRays(const int numberOfRays, 1624 1625 1626 { 1627 1628 1629 1630 1631 1632 1633 1634 1760 const int numberOfLeaves, 1761 SimpleRayContainer &rays) 1762 { 1763 1764 vector<VssTreeLeaf *> leaves; 1765 1766 CollectLeaves(leaves); 1767 1768 sort(leaves.begin(), 1769 leaves.end(), 1770 GreaterContribution); 1635 1771 1636 1772 1637 float sumContrib = 0.0; 1638 int i; 1639 for (i=0; i < numberOfLeaves; i++) { 1640 float c = leaves[i]->GetAvgRayContribution(); 1641 sumContrib += c; 1642 // cout<<"ray contrib "<<i<<" : "<<c<<endl; 1643 } 1644 1645 float avgContrib = sumContrib/numberOfLeaves; 1646 float ratioPerLeaf = numberOfRays/(avgContrib*numberOfLeaves); 1647 1648 for (i=0; i < numberOfLeaves; i++) { 1649 VssTreeLeaf *leaf = leaves[i]; 1650 float c = leaf->GetAvgRayContribution(); 1651 int num = (c*ratioPerLeaf + 0.5); 1652 // cout<<num<<" "; 1653 1654 for (int i=0; i < num; i++) { 1655 Vector3 origin = GetBBox(leaf).GetRandomPoint(); 1656 Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint(); 1657 Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x)); 1658 //cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl; 1659 rays.push_back(SimpleRay(origin, direction)); 1660 } 1661 } 1662 return rays.size(); 1773 float sumContrib = 0.0; 1774 int i; 1775 int k = 0; 1776 for (i=0; i < leaves.size() && k < numberOfLeaves; i++) 1777 if (ValidLeaf(leaves[i])) { 1778 float c = leaves[i]->GetAvgRayContribution(); 1779 sumContrib += c; 1780 // cout<<"ray contrib "<<i<<" : "<<c<<endl; 1781 k++; 1782 } 1783 1784 float avgContrib = sumContrib/numberOfLeaves; 1785 float ratioPerLeaf = numberOfRays/(avgContrib*numberOfLeaves); 1786 k = 0; 1787 for (i=0; i < leaves.size() && k < numberOfLeaves; i++) 1788 if (ValidLeaf(leaves[i])) { 1789 k++; 1790 VssTreeLeaf *leaf = leaves[i]; 1791 float c = leaf->GetAvgRayContribution(); 1792 int num = (c*ratioPerLeaf + 0.5); 1793 GenerateLeafRays(leaf, num, rays); 1794 } 1795 1796 return rays.size(); 1663 1797 } 1664 1798 … … 1667 1801 VssTree::GetAvgPvsSize() 1668 1802 { 1669 1803 stack<VssTreeNode *> tstack; 1670 1804 tstack.push(root); 1671 1805 1672 1673 1806 int sumPvs = 0; 1807 int leaves = 0; 1674 1808 while (!tstack.empty()) { 1675 1809 VssTreeNode *node = tstack.top(); … … 1677 1811 1678 1812 if (node->IsLeaf()) { 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 } 1695 1696 1813 VssTreeLeaf *leaf = (VssTreeLeaf *)node; 1814 // update pvs size 1815 leaf->UpdatePvsSize(); 1816 sumPvs += leaf->GetPvsSize(); 1817 leaves++; 1818 } else { 1819 VssTreeInterior *in = (VssTreeInterior *)node; 1820 // both nodes for directional splits 1821 tstack.push(in->front); 1822 tstack.push(in->back); 1823 } 1824 } 1825 1826 1827 return sumPvs/(float)leaves; 1828 } 1829 1830 -
trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.h
r427 r434 226 226 return mRay->GetOrigin(axis) + GetMaxT()*mRay->GetDir(axis); 227 227 } 228 229 Vector3 Extrap(const float t) const { 230 return mRay->Extrap(t); 231 } 228 232 229 233 #if USE_FIXEDPOINT_T … … 411 415 412 416 RayInfoContainer rays; 417 int mPassingRays; 418 413 419 bool mValidPvs; 420 421 414 422 415 423 VssTreeLeaf(VssTreeInterior *p, 416 424 const int nRays 417 ):VssTreeNode(p), rays(), mPvsSize(0), m ValidPvs(false) {425 ):VssTreeNode(p), rays(), mPvsSize(0), mPassingRays(0), mValidPvs(false) { 418 426 rays.reserve(nRays); 419 427 } … … 431 439 rays.push_back(data); 432 440 data.mRay->Ref(); 441 if (data.GetRayClass() == RayInfo::PASSING_RAY) 442 mPassingRays++; 433 443 } 434 444 … … 438 448 void SetPvsSize(const int s) { 439 449 mPvsSize = s; 450 mValidPvs = true; 440 451 } 441 452 … … 537 548 leafb->rays.size()*b.bbox.GetVolume(); 538 549 #endif 539 #if 1550 #if 0 540 551 return 541 552 leafa->GetPvsSize()*a.bbox.GetVolume() … … 555 566 leafb->GetPvsSize()/(leafb->rays.size()+1); 556 567 #endif 557 #if 0568 #if 1 558 569 return 559 570 leafa->GetPvsSize()*leafa->rays.size() … … 623 634 624 635 // type of the splitting to use fo rthe tree construction 625 enum {ESplitRegular, ESplitHeuristic };636 enum {ESplitRegular, ESplitHeuristic, ESplitHybrid }; 626 637 int splitType; 638 639 bool mSplitUseOnlyDrivingAxis; 640 641 // use ray space subdivision instead of view space subdivision 642 bool mUseRss; 627 643 628 644 // maximal size of the box on which the refdir splitting can be performed … … 723 739 } 724 740 741 725 742 float 726 BestCostRatioHeuristic( 727 VssTreeLeaf *node, 728 int &axis, 729 float &position, 730 int &raysBack, 731 int &raysFront, 732 int &pvsBack, 733 int &pvsFront 734 ); 735 736 float 737 BestCostRatioRegular( 738 VssTreeLeaf *node, 739 int &axis, 740 float &position, 741 int &raysBack, 742 int &raysFront, 743 int &pvsBack, 744 int &pvsFront 745 746 ); 743 BestCostRatio( 744 VssTreeLeaf *node, 745 int &axis, 746 float &position, 747 int &raysBack, 748 int &raysFront, 749 int &pvsBack, 750 int &pvsFront 751 ); 747 752 748 753 float … … 757 762 ); 758 763 759 AxisAlignedBox3 GetBBox(const VssTreeNode *node) { 764 float 765 EvalCostRatioHeuristic( 766 VssTreeLeaf *node, 767 const int axis, 768 float &position, 769 int &raysBack, 770 int &raysFront, 771 int &pvsBack, 772 int &pvsFront 773 ); 774 775 float 776 GetCostRatio( 777 VssTreeLeaf *leaf, 778 const int axis, 779 const float position, 780 const int raysBack, 781 const int raysFront, 782 const int pvsBack, 783 const int pvsFront 784 ); 785 786 AxisAlignedBox3 GetBBox(const VssTreeNode *node) const { 760 787 if (node->parent == NULL) 761 788 return bbox; … … 775 802 } 776 803 777 AxisAlignedBox3 GetDirBBox(const VssTreeNode *node) {804 AxisAlignedBox3 GetDirBBox(const VssTreeNode *node) const { 778 805 779 806 if (node->parent == NULL) … … 834 861 int 835 862 GetRootPvsSize() const { 836 return GetPvsSize( root,bbox);863 return GetPvsSize(bbox); 837 864 } 838 865 839 866 int 840 GetPvsSize( VssTreeNode *node,const AxisAlignedBox3 &box) const;867 GetPvsSize(const AxisAlignedBox3 &box) const; 841 868 842 869 void … … 874 901 ); 875 902 876 903 VssTreeNode *GetRoot() const { return root; } 904 905 bool 906 ValidLeaf(VssTreeLeaf *leaf) const; 907 908 void 909 GenerateLeafRays(VssTreeLeaf *leaf, 910 const int numberOfRays, 911 SimpleRayContainer &rays); 912 913 877 914 }; 878 915 -
trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp
r427 r434 10 10 #include "VssRay.h" 11 11 #include "VspKdTree.h" 12 #include "VssTree.h" 12 13 13 14 X3dExporter::X3dExporter(const string filename):Exporter(filename) … … 154 155 for (; ri != rays.end(); ri++) { 155 156 Vector3 a = (*ri)->GetOrigin(); 156 Vector3 b = (*ri)->mTerminationObject ? (*ri)->GetTermination() : a + 1000 * Normalize(b - a);157 Vector3 b = (*ri)->mTerminationObject ? (*ri)->GetTermination() : a + 1000 * Normalize(b - a); 157 158 158 159 stream<<a.x<<" "<<a.y<<" "<<a.z<<" ,"; 159 stream<<b.x<<" "<<b.y<<" "<<b.z<<" ,\n";160 stream<<b.x<<" "<<b.y<<" "<<b.z<<" ,\n"; 160 161 } 161 162 … … 699 700 } 700 701 702 703 void 704 X3dExporter::AddBoxToMesh(const AxisAlignedBox3 &box, 705 Mesh *mesh) 706 { 707 // add 6 vertices of the box 708 int index = (int)mesh->mVertices.size(); 709 710 for (int i=0; i < 8; i++) { 711 Vector3 v; 712 box.GetVertex(i, v); 713 mesh->mVertices.push_back(v); 714 } 715 716 mesh->AddFace(new Face(index + 0, index + 1, index + 3, index + 2) ); 717 mesh->AddFace(new Face(index + 0, index + 2, index + 6, index + 4) ); 718 mesh->AddFace(new Face(index + 4, index + 6, index + 7, index + 5) ); 719 720 mesh->AddFace(new Face(index + 3, index + 1, index + 5, index + 7) ); 721 mesh->AddFace(new Face(index + 0, index + 4, index + 5, index + 1) ); 722 mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) ); 723 724 } 725 726 bool 727 X3dExporter::ExportVssTree(const VssTree &tree) 728 { 729 stack<VssTreeNode *> tStack; 730 731 tStack.push(tree.GetRoot()); 732 733 Mesh *mesh = new Mesh; 734 VssRayContainer rays; 735 736 while (!tStack.empty()) { 737 738 VssTreeNode *node = tStack.top(); 739 tStack.pop(); 740 741 742 if (!node->IsLeaf()) { 743 VssTreeInterior *interior = (VssTreeInterior *)node; 744 tStack.push(interior->front); 745 tStack.push(interior->back); 746 } else { 747 VssTreeLeaf *leaf = (VssTreeLeaf *)node; 748 AxisAlignedBox3 box; 749 box = tree.GetBBox(leaf); 750 AddBoxToMesh(box, mesh); 751 752 if (tree.ValidLeaf(leaf)) { 753 754 Vector3 origin = box.Center(); 755 box = tree.GetDirBBox(leaf); 756 VssRay *ray; 757 758 const indices[][2] = {{0,0}, {0,1}, {1,1}, {1,0}}; 759 MeshInstance dummy(mesh); 760 for (int i=0; i < 4; i++) { 761 // Vector3 v = box.GetVertex(indices[i][0], indices[i][1], 0); 762 Vector3 v = box.Center(); 763 764 Vector3 direction = VssRay::GetDirection(v.x, v.y); 765 direction.Normalize(); 766 float k = 100.0f*leaf->GetAvgRayContribution(); 767 // get 4 corners of the ray directions 768 769 ray = new VssRay(origin, origin + (direction*k), NULL, &dummy); 770 rays.push_back(ray); 771 } 772 } 773 } 774 } 775 776 ExportMesh(mesh); 777 ExportRays(rays); 778 CLEAR_CONTAINER(rays); 779 delete mesh; 780 return true; 781 } 701 782 702 783 bool -
trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h
r425 r434 38 38 bool 39 39 ExportKdTree(const KdTree &tree); 40 40 41 bool 42 ExportVssTree(const VssTree &tree); 43 41 44 bool 42 45 ExportVspKdTree(const VspKdTree &tree, const int maxPvs); … … 108 111 109 112 bool 110 ExportBspTreeRayDensity(const BspTree &tree); 113 ExportBspTreeRayDensity(const BspTree &tree); 114 115 void 116 AddBoxToMesh(const AxisAlignedBox3 &box, 117 Mesh *mesh); 118 111 119 }; 112 120 -
trunk/VUT/GtpVisibilityPreprocessor/src/common.h
r372 r434 238 238 239 239 240 240 241 inline Real sqr(Real a) 241 242 { -
trunk/VUT/GtpVisibilityPreprocessor/src/default.env
r430 r434 13 13 #;../data/vienna/vienna-plane.x3d 14 14 # filename ../data/vienna/viewcells-25-sel.x3d 15 filename ../data/atlanta/atlanta2.x3d15 # filename ../data/atlanta/atlanta2.x3d 16 16 # filename ../data/soda/soda.dat 17 #filename ../data/soda/soda5.dat17 filename ../data/soda/soda5.dat 18 18 } 19 19 … … 25 25 VssPreprocessor { 26 26 samplesPerPass 100000 27 initialSamples 200000 027 initialSamples 200000 28 28 vssSamples 1000000 29 vssSamplesPerPass 10000029 vssSamplesPerPass 50000 30 30 useImportanceSampling true 31 31 } 32 32 33 33 VssTree { 34 useRss true 34 35 epsilon 1e-6 35 36 … … 38 39 minRays 100 39 40 minSize 0.001 40 maxCostRatio 0.9841 maxCostRatio 1.1 41 42 maxRayContribution 0.05 42 43 … … 44 45 maxStaticMemory 50 45 46 46 splitType regular 47 # splitType heuristics 47 # splitType regular 48 # splitType heuristic 49 splitType hybrid 50 splitUseOnlyDrivingAxis true 48 51 49 52 numberOfEndPointDomains 10000
Note: See TracChangeset
for help on using the changeset viewer.