Changeset 434 for trunk/VUT


Ignore:
Timestamp:
11/25/05 14:45:50 (19 years ago)
Author:
bittner
Message:

vssbsp merge, tab change

Location:
trunk/VUT/GtpVisibilityPreprocessor/src
Files:
12 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

    r427 r434  
    14491449  RegisterOption("VssTree.randomize", optBool, "randomize", "false"); 
    14501450  RegisterOption("VssTree.splitType", optString, "split=", "queries"); 
     1451  RegisterOption("VssTree.splitUseOnlyDrivingAxis", optBool, "splitdriving=", "false"); 
     1452 
     1453  RegisterOption("VssTree.useRss", optBool, "rss=", "false"); 
     1454 
     1455 
     1456 
    14511457  RegisterOption("VssTree.numberOfEndPointDomains", optInt, "endpoints=", "10000"); 
    14521458 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h

    r428 r434  
    1919class BspLeaf; 
    2020class Polygon3; 
     21class VssTree; 
    2122 
    2223class Exporter 
    … …  
    4748  virtual bool 
    4849  ExportKdTree(const KdTree &tree) = 0; 
     50 
     51        virtual bool 
     52  ExportVssTree(const VssTree &tree) = 0; 
    4953 
    5054  virtual bool 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Makefile

    r427 r434  
    11############################################################################# 
    22# Makefile for building: preprocessor 
    3 # Generated by qmake (1.07a) (Qt 3.3.2) on: Tue Nov 22 12:10:40 2005 
     3# Generated by qmake (1.07a) (Qt 3.3.2) on: Wed Nov 23 09:47:01 2005 
    44# Project:  preprocessor.pro 
    55# Template: app 
    … …  
    369369                VssRay.h \ 
    370370                VspKdTree.h \ 
     371                VssTree.h \ 
    371372                Containers.h \ 
    372373                AxisAlignedBox3.h \ 
    … …  
    439440                Ray.h \ 
    440441                Plane3.h \ 
     442                VssRay.h \ 
    441443                Matrix4x4.h \ 
    442444                Vector3.h \ 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

    r433 r434  
    1111 
    1212 
    13 bool useViewSpaceBox = false;//true; 
     13bool useViewSpaceBox = true;//true; 
    1414bool use2dSampling = false; 
    15 bool useViewspacePlane = false;//true; 
     15bool useViewspacePlane = true;//true; 
    1616 
    1717VssPreprocessor::VssPreprocessor(): 
    18         mPass(0), 
    19         mVssRays() 
     18  mPass(0), 
     19  mVssRays() 
    2020{ 
    2121  // this should increase coherence of the samples 
    … …  
    3232VssPreprocessor::~VssPreprocessor() 
    3333{ 
    34         CLEAR_CONTAINER(mVssRays); 
     34  CLEAR_CONTAINER(mVssRays); 
    3535} 
    3636 
    3737void 
    3838VssPreprocessor::SetupRay(Ray &ray,  
    39                                                                                                         const Vector3 &point,  
    40                                                                                                         const Vector3 &direction 
    41                                                                                                         ) 
     39                                                  const Vector3 &point,  
     40                                                  const Vector3 &direction 
     41                                                  ) 
    4242{ 
    4343  ray.intersections.clear(); 
    44         // do not store anything else then intersections at the ray 
     44  // do not store anything else then intersections at the ray 
    4545  ray.Init(point, direction, Ray::LOCAL_RAY); 
    4646} 
    … …  
    4848int 
    4949VssPreprocessor::CastRay( 
    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; 
     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; 
    141141} 
    142142 
    … …  
    145145VssPreprocessor::GetViewpoint(AxisAlignedBox3 *viewSpaceBox) 
    146146{ 
    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(); 
     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(); 
    156156} 
    157157 
    158158Vector3 
    159159VssPreprocessor::GetDirection(const Vector3 &viewpoint, 
    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; 
     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; 
    182182} 
    183183 
    184184int 
    185185VssPreprocessor::GenerateImportanceRays(VssTree *vssTree, 
    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; 
     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; 
    215215} 
    216216 
    … …  
    218218bool 
    219219VssPreprocessor::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 
     257bool 
     258VssPreprocessor::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} 
    256269 
    257270bool 
    258271VssPreprocessor::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); 
    275283        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; 
    294307} 
    295308 
    … …  
    297310VssPreprocessor::ExportVssTreeLeaves(VssTree *tree, const int number) 
    298311{ 
    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 
     331float 
     332VssPreprocessor::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(); 
    315343} 
    316344 
    … …  
    326354 
    327355 
    328         AxisAlignedBox3 *box = new AxisAlignedBox3(mKdTree->GetBox()); 
    329  
    330         if (!useViewspacePlane) { 
    331                 float size = 0.01f; 
    332                 float s = 0.5f - size; 
    333                 float olds = Magnitude(box->Size()); 
    334                 box->Enlarge(box->Size()*Vector3(-s)); 
    335                 Vector3 translation = Vector3(-olds*0.1f, 0, 0); 
    336                 box->SetMin(box->Min() + translation); 
    337                 box->SetMax(box->Max() + translation); 
    338         } else { 
    339                  
    340                 // sample city like heights 
    341                 box->SetMin(1, box->Min(1) + box->Size(1)*0.1); 
    342                 box->SetMax(1, box->Min(1) + box->Size(1)*0.2); 
    343         } 
    344  
    345         if (use2dSampling) 
    346                 box->SetMax(1, box->Min(1)); 
    347          
    348         if (useViewSpaceBox) 
    349                 mViewSpaceBox = box; 
    350         else 
    351                 mViewSpaceBox = NULL; 
    352                  
    353  
    354         VssTree *vssTree = NULL; 
    355  
    356         RayContainer bspRays; 
     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; 
    357385 
    358386  while (totalSamples < mInitialSamples) { 
    359                 int passContributingSamples = 0; 
    360                 int passSampleContributions = 0; 
    361                 int passSamples = 0; 
    362                 int index = 0; 
    363                  
    364                 int sampleContributions; 
    365                  
    366                 int s = Min(mSamplesPerPass, mInitialSamples); 
    367                 for (int k=0; k < s; k++) { 
     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++) { 
    368396                         
    369                         Vector3 viewpoint = GetViewpoint(mViewSpaceBox); 
    370                         Vector3 direction = GetDirection(viewpoint, mViewSpaceBox); 
     397          Vector3 viewpoint = GetViewpoint(mViewSpaceBox); 
     398          Vector3 direction = GetDirection(viewpoint, mViewSpaceBox); 
    371399                         
    372                         sampleContributions = CastRay(viewpoint, direction, mVssRays); 
     400          sampleContributions = CastRay(viewpoint, direction, mVssRays); 
    373401                         
    374402                         
    375                         //-- CORR matt: put block inside loop 
    376                         if (sampleContributions) { 
    377                                 passContributingSamples ++; 
    378                                 passSampleContributions += sampleContributions; 
    379                         } 
    380                         passSamples++; 
    381                         totalSamples++; 
    382                 } 
     403          //-- CORR matt: put block inside loop 
     404          if (sampleContributions) { 
     405                passContributingSamples ++; 
     406                passSampleContributions += sampleContributions; 
     407          } 
     408          passSamples++; 
     409          totalSamples++; 
     410        } 
    383411     
    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; 
    417533 
    418534        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 
    425545        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)  
    426567        { 
    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 
     585void 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); 
    439601                         
    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 
    517603        { 
    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        } 
    557607} 
    558608 
    559609int VssPreprocessor::AddObjectSamples(Intersectable *obj, const Ray &ray) 
    560610{ 
    561         int contributingSamples = 0; 
    562         int j; 
     611  int contributingSamples = 0; 
     612  int j; 
    563613  
    564         // object can be seen from the view cell => add to view cell pvs 
    565         for (j=0; j < ray.bspIntersections.size(); ++ j) 
     614  // object can be seen from the view cell => add to view cell pvs 
     615  for (j=0; j < ray.bspIntersections.size(); ++ j) 
    566616        {        
     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          { 
    567628                BspLeaf *leaf = ray.bspIntersections[j].mLeaf; 
    568                 // if ray not in unbounded space 
     629                 
    569630                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  
    1414class VssPreprocessor : public Preprocessor { 
    1515public: 
    16         int mPass; 
     16  int mPass; 
    1717  int mSamplesPerPass; 
    1818  int mVssSamplesPerPass; 
    1919  int mInitialSamples; 
    2020  int mVssSamples; 
    21         bool mUseImportanceSampling; 
     21  bool mUseImportanceSampling; 
    2222 
    23         AxisAlignedBox3 *mViewSpaceBox; 
     23  AxisAlignedBox3 *mViewSpaceBox; 
    2424 
    25         ofstream mStats; 
     25  ofstream mStats; 
    2626         
    2727  ObjectContainer mObjects; 
    2828 
    29         // rays cast during the processing 
     29  // rays cast during the processing 
    3030  VssRayContainer mVssRays; 
    3131         
    … …  
    3535  virtual bool ComputeVisibility(); 
    3636 
    37         Vector3 
    38         GetViewpoint(AxisAlignedBox3 *viewSpaceBox); 
     37  Vector3 
     38  GetViewpoint(AxisAlignedBox3 *viewSpaceBox); 
    3939 
    40         Vector3 
    41         GetDirection(const Vector3 &viewpoint, 
    42                                                         AxisAlignedBox3 *viewSpaceBox 
    43                                                         ); 
     40  Vector3 
     41  GetDirection(const Vector3 &viewpoint, 
     42                          AxisAlignedBox3 *viewSpaceBox 
     43                          ); 
    4444         
    4545  void 
    4646  SetupRay(Ray &ray,  
    47                                         const Vector3 &point,  
    48                                         const Vector3 &direction 
    49                                         ); 
     47                  const Vector3 &point,  
     48                  const Vector3 &direction 
     49                  ); 
    5050 
    5151 
    5252         
    53         int 
    54         CastRay( 
    55                                         Vector3 &viewPoint, 
    56                                         Vector3 &direction, 
    57                                         VssRayContainer &vssRays 
     53  int 
     54  CastRay( 
     55                  Vector3 &viewPoint, 
     56                  Vector3 &direction, 
     57                  VssRayContainer &vssRays 
    5858 
    59                                         ); 
     59                  ); 
    6060                 
    6161 
    6262         
    63         virtual bool BuildBspTree() { return false; } 
     63  virtual bool BuildBspTree() { return false; } 
    6464 
    6565 
    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 
    7076                                                 ); 
    7177 
    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); 
    7791 
    7892 
    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); 
    8699         
    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); 
    90101}; 
    91102 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VssRay.h

    r431 r434  
    136136  Vector3 GetNormalizedDir() const { return (mTermination - mOrigin)*mInvSize; } 
    137137 
     138        Vector3 Extrap(const float t) const { 
     139                return GetOrigin() + t * GetDir(); 
     140        } 
     141         
    138142        float GetDirParametrization(const int axis) const; 
    139143         
    … …  
    200204      } 
    201205  } 
     206 
     207        static Vector3 
     208        GetDirection(const float a, const float b) { 
     209                return Vector3(sin(a), sin(b), cos(a)); 
     210        } 
     211 
    202212}; 
    203213 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp

    r433 r434  
    2626 
    2727 
    28 #define DEBUG_DIR_SPLIT 0 
    29  
    30  
    31  
    3228// Static variables 
    3329int 
    … …  
    3632inline void 
    3733AddObject2Pvs(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} 
    6762 
    6863// Constructor 
    … …  
    7065{ 
    7166  environment->GetIntValue("VssTree.maxDepth", termMaxDepth); 
    72         environment->GetIntValue("VssTree.minPvs", termMinPvs); 
    73         environment->GetIntValue("VssTree.minRays", termMinRays); 
    74         environment->GetFloatValue("VssTree.maxRayContribution", termMaxRayContribution); 
     67  environment->GetIntValue("VssTree.minPvs", termMinPvs); 
     68  environment->GetIntValue("VssTree.minRays", termMinRays); 
     69  environment->GetFloatValue("VssTree.maxRayContribution", termMaxRayContribution); 
    7570  environment->GetFloatValue("VssTree.maxCostRatio", termMaxCostRatio); 
    7671 
    … …  
    9287  float refDirAngle; 
    9388  environment->GetFloatValue("VssTree.refDirAngle", refDirAngle); 
    94  
     89   
    9590  environment->GetIntValue("VssTree.accessTimeThreshold", accessTimeThreshold); 
    9691  //= 1000; 
    … …  
    9994 
    10095  //  pRefDirThresh = cos(0.5*M_PI - M_PI*refDirAngle/180.0); 
    101         //  cosRefDir = cos(M_PI*refDirAngle/180.0); 
    102         //  sinRefDir = sin(M_PI*refDirAngle/180.0); 
     96  //  cosRefDir = cos(M_PI*refDirAngle/180.0); 
     97  //  sinRefDir = sin(M_PI*refDirAngle/180.0); 
    10398   
    10499   
    105100  // split type 
    106         char sname[128]; 
    107         environment->GetStringValue("VssTree.splitType", sname); 
     101  char sname[128]; 
     102  environment->GetStringValue("VssTree.splitType", sname); 
    108103  string name(sname); 
    109104         
    … …  
    113108    if (name.compare("heuristic") == 0) 
    114109      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          } 
    119117         
    120118  environment->GetBoolValue("VssTree.randomize", randomize); 
    121  
     119  environment->GetBoolValue("VssTree.splitUseOnlyDrivingAxis", mSplitUseOnlyDrivingAxis); 
     120  environment->GetBoolValue("VssTree.useRss", mUseRss); 
     121         
    122122  root = NULL; 
    123123   
    … …  
    143143      << rays <<endl; 
    144144 
    145         app << "#N_INITPVS ( Initial PVS size )\n" 
     145  app << "#N_INITPVS ( Initial PVS size )\n" 
    146146      << initialPvsSize <<endl; 
    147147   
    … …  
    179179    minRaysNodes*100/(double)Leaves()<<endl; 
    180180         
    181         app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<< 
     181  app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<< 
    182182    minSizeNodes*100/(double)Leaves()<<endl; 
    183183 
    184         app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"<< 
     184  app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"<< 
    185185    maxRayContribNodes*100/(double)Leaves()<<endl; 
    186186 
    187         app << "#N_PMAXCOSTRATIOLEAVES  ( Percentage of leaves with max cost ratio )\n"<< 
     187  app << "#N_PMAXCOSTRATIOLEAVES  ( Percentage of leaves with max cost ratio )\n"<< 
    188188    maxCostRatioNodes*100/(double)Leaves()<<endl; 
    189189 
    … …  
    207207VssTreeLeaf::UpdatePvsSize() 
    208208{ 
    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; 
     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; 
    217217#if BIDIRECTIONAL_RAY 
    218                                 object = (*ri).mRay->mOriginObject; 
    219                                 if (object && !object->Mailed()) { 
    220                                         pvsSize++; 
    221                                         object->Mail(); 
    222                                 } 
     218                object = (*ri).mRay->mOriginObject; 
     219                if (object && !object->Mailed()) { 
     220                  pvsSize++; 
     221                  object->Mail(); 
     222                } 
    223223#endif 
    224                                 object = (*ri).mRay->mTerminationObject; 
    225                                 if (object && !object->Mailed()) { 
    226                                         pvsSize++; 
    227                                         object->Mail(); 
    228                                 } 
    229                         } 
    230                 mPvsSize = pvsSize; 
    231                 mValidPvs = true; 
    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  } 
    233233} 
    234234 
    235235bool 
    236236VssTree::ClipRay( 
    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; 
     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; 
    259259} 
    260260 
    … …  
    262262void 
    263263VssTree::Construct( 
    264                                                                         VssRayContainer &rays, 
    265                                                                         AxisAlignedBox3 *forcedBoundingBox 
    266                                                                         ) 
     264                                  VssRayContainer &rays, 
     265                                  AxisAlignedBox3 *forcedBoundingBox 
     266                                  ) 
    267267{ 
    268268  stat.Start(); 
    269269   
    270         maxMemory = maxStaticMemory; 
     270  maxMemory = maxStaticMemory; 
    271271 
    272272  if (root) 
    273273    delete root; 
    274  
     274         
    275275  root = new VssTreeLeaf(NULL, rays.size()); 
    276276  // first construct a leaf that will get subdivide 
    … …  
    281281  bbox.Initialize(); 
    282282  dirBBox.Initialize(); 
    283    
     283 
     284  if (mUseRss) 
     285        forcedBoundingBox = NULL; 
     286         
    284287  for(VssRayContainer::const_iterator ri = rays.begin(); 
    285288      ri != rays.end(); 
    286289      ri++) { 
    287  
    288                 VssTreeNode::RayInfo info(*ri); 
    289                 if (forcedBoundingBox) 
    290                         if (!ClipRay(info, *forcedBoundingBox)) 
    291                                 continue; 
    292                 leaf->AddRay(info); 
     290                 
     291        VssTreeNode::RayInfo info(*ri); 
     292        if (forcedBoundingBox) 
     293          if (!ClipRay(info, *forcedBoundingBox)) 
     294                continue; 
     295        leaf->AddRay(info); 
    293296                 
    294297    bbox.Include((*ri)->GetOrigin()); 
    … …  
    296299     
    297300                 
    298                 dirBBox.Include(Vector3( 
    299                                                                                                                 (*ri)->GetDirParametrization(0), 
    300                                                                                                                 (*ri)->GetDirParametrization(1), 
    301                                                                                                                 0 
    302                                                                                                                 ) 
    303                                                                                 ); 
    304         } 
    305          
    306          
    307         if ( forcedBoundingBox )  
    308                 bbox = *forcedBoundingBox; 
    309          
    310         cout<<"Bbox = "<<bbox<<endl; 
    311         cout<<"Dirr Bbox = "<<dirBBox<<endl; 
     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; 
    312315 
    313316  stat.rays = leaf->rays.size(); 
    314         leaf->UpdatePvsSize(); 
     317  leaf->UpdatePvsSize(); 
    315318  stat.initialPvsSize = leaf->GetPvsSize(); 
    316319  // Subdivide(); 
    … …  
    325328  stat.Stop(); 
    326329 
    327         stat.Print(cout); 
    328         cout<<"#Total memory="<<GetMemUsage()<<endl; 
     330  stat.Print(cout); 
     331  cout<<"#Total memory="<<GetMemUsage()<<endl; 
    329332 
    330333} 
    … …  
    333336VssTree::UpdateSubdivision() 
    334337{ 
    335         priority_queue<TraversalData> tStack; 
     338  priority_queue<TraversalData> tStack; 
    336339  //  stack<TraversalData> tStack; 
    337340   
    338         tStack.push(TraversalData(root, bbox, 0)); 
     341  tStack.push(TraversalData(root, bbox, 0)); 
    339342         
    340343  AxisAlignedBox3 backBox; 
    341344  AxisAlignedBox3 frontBox; 
    342345 
    343         maxMemory = maxTotalMemory; 
    344         int subdivided = 0; 
    345         int lastMem = 0; 
     346  maxMemory = maxTotalMemory; 
     347  int subdivided = 0; 
     348  int lastMem = 0; 
    346349  while (!tStack.empty()) { 
    347350                 
    348                 float mem = GetMemUsage(); 
    349                  
    350                 if ( lastMem/10 != ((int)mem)/10) { 
    351                         cout<<mem<<" MB"<<endl; 
    352                 } 
    353                 lastMem = (int)mem; 
    354                  
    355                 if (  mem > maxMemory ) { 
     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 ) { 
    356359      // count statistics on unprocessed leafs 
    357360      while (!tStack.empty()) { 
    358                                 //                              EvaluateLeafStats(tStack.top()); 
    359                                 tStack.pop(); 
     361                //                              EvaluateLeafStats(tStack.top()); 
     362                tStack.pop(); 
    360363      } 
    361364      break; 
    … …  
    365368    tStack.pop(); 
    366369 
    367                 if (data.node->IsLeaf()) { 
    368                         VssTreeNode *node = SubdivideNode((VssTreeLeaf *) data.node, 
    369                                                                                                                                                                 data.bbox, 
    370                                                                                                                                                                 backBox, 
    371                                                                                                                                                                 frontBox 
    372                                                                                                                                                                 ); 
    373                         if (!node->IsLeaf()) { 
    374                                 subdivided++; 
    375                                 VssTreeInterior *interior = (VssTreeInterior *) node; 
    376                                 // push the children on the stack 
    377                                 tStack.push(TraversalData(interior->back, backBox, data.depth+1)); 
    378                                 tStack.push(TraversalData(interior->front, frontBox, data.depth+1)); 
    379                         } else { 
    380                                 //      EvaluateLeafStats(data); 
    381                         } 
    382                 } else { 
    383                         VssTreeInterior *interior = (VssTreeInterior *) data.node; 
    384                         tStack.push(TraversalData(interior->back, GetBBox(interior->back), data.depth+1)); 
    385                         tStack.push(TraversalData(interior->front, GetBBox(interior->front), data.depth+1)); 
    386                 } 
    387   } 
    388         return subdivided; 
     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; 
    389392} 
    390393 
    … …  
    404407 
    405408   
    406         int lastMem = 0; 
     409  int lastMem = 0; 
    407410  while (!tStack.empty()) { 
    408411 
    409                 float mem = GetMemUsage(); 
    410                  
    411                 if ( lastMem/10 != ((int)mem)/10) { 
    412                         cout<<mem<<" MB"<<endl; 
    413                 } 
    414                 lastMem = (int)mem; 
    415                  
    416                 if (  mem > maxMemory ) { 
     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 ) { 
    417420      // count statistics on unprocessed leafs 
    418421      while (!tStack.empty()) { 
    419                                 EvaluateLeafStats(tStack.top()); 
    420                                 tStack.pop(); 
     422                EvaluateLeafStats(tStack.top()); 
     423                tStack.pop(); 
    421424      } 
    422425      break; 
    … …  
    427430     
    428431    VssTreeNode *node = SubdivideNode((VssTreeLeaf *) data.node, 
    429                                                                                                                                                         data.bbox, 
    430                                                                                                                                                         backBox, 
    431                                                                                                                                                         frontBox 
    432                                                                                                                                                         ); 
     432                                                                          data.bbox, 
     433                                                                          backBox, 
     434                                                                          frontBox 
     435                                                                          ); 
    433436    if (result == NULL) 
    434437      result = node; 
    … …  
    453456int 
    454457VssTree::SelectPlane( 
    455                                                                                 VssTreeLeaf *leaf, 
    456                                                                                 const AxisAlignedBox3 &box, 
    457                                                                                 float &position, 
    458                                                                                 int &raysBack, 
    459                                                                                 int &raysFront, 
    460                                                                                 int &pvsBack, 
    461                                                                                 int &pvsFront 
    462                                                                                 ) 
     458                                        VssTreeLeaf *leaf, 
     459                                        const AxisAlignedBox3 &box, 
     460                                        float &position, 
     461                                        int &raysBack, 
     462                                        int &raysFront, 
     463                                        int &pvsBack, 
     464                                        int &pvsFront 
     465                                        ) 
    463466{ 
    464467 
    465468  int minDirDepth = 6; 
    466469  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 
     501float 
     502VssTree::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 
     567float 
     568VssTree::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 
     650float 
     651VssTree::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 { 
    490733                        cerr<<"VssTree: Unknown split heuristics\n"; 
    491734                        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         
    515759float 
    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) { 
     760VssTree::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) { 
    567846                         
    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); 
    625855                         
    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 0 
    635                         float directionalPenalty = 0.7f; 
    636                         // importance based cost 
    637                         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 #else 
    643                         float newCost = raysBack*pvsBack  + raysFront*pvsFront; 
    644                         float oldCost = leaf->rays.size()*pvsSize; 
    645                         ratio = newCost/oldCost; 
    646 #endif 
    647                 } 
    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 float 
    657 VssTree::BestCostRatioRegular( 
    658                                                                                                                         VssTreeLeaf *leaf, 
    659                                                                                                                         int &axis, 
    660                                                                                                                         float &position, 
    661                                                                                                                         int &raysBack, 
    662                                                                                                                         int &raysFront, 
    663                                                                                                                         int &pvsBack, 
    664                                                                                                                         int &pvsFront 
    665                                                                                                                         ) 
    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                         else 
    690                                 nPosition[axis] = (dBox.Min()[axis-3] + dBox.Max()[axis-3])*0.5f; 
    691856                         
    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; 
    700859                         
    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; 
    814869                                 
    815870      } 
    816871    } 
    817872  } 
    818    
    819   float oldCost = leaf->GetPvsSize(); 
    820   float newCost = ct_div_ci + minSum/sizeBox; 
    821   float ratio = newCost/oldCost; 
     873 
    822874   
    823875  //  cout<<"===================="<<endl; 
    824876  //  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox) 
    825877  //      <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl; 
    826         return ratio; 
     878  return minRatio; 
    827879} 
    828880 
    829881void 
    830882VssTree::SortSplitCandidates( 
    831                                                                                                                 VssTreeLeaf *node, 
    832                                                                                                                 const int axis 
    833                                                                                                                 ) 
     883                                                        VssTreeLeaf *node, 
     884                                                        const int axis 
     885                                                        ) 
    834886{ 
    835887   
    … …  
    851903      ri < node->rays.end(); 
    852904      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 
    867934  stable_sort(splitCandidates->begin(), splitCandidates->end()); 
    868935} 
    … …  
    879946    stat.maxDepthNodes++; 
    880947   
    881         //  if ( (int)(leaf->rays.size()) < termMinCost) 
    882         //    stat.minCostNodes++; 
    883         if ( leaf->GetPvsSize() < termMinPvs) 
    884                 stat.minPvsNodes++; 
    885  
    886         if ( leaf->GetPvsSize() < termMinRays) 
    887                 stat.minRaysNodes++; 
    888  
    889         if (0 && leaf->GetAvgRayContribution() > termMaxRayContribution ) 
    890                 stat.maxRayContribNodes++; 
    891          
    892         if (SqrMagnitude(data.bbox.Size()) <= termMinSize) { 
    893                 stat.minSizeNodes++; 
    894         } 
    895  
    896         if ( (int)(leaf->rays.size()) > stat.maxRayRefs) 
     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) 
    897964    stat.maxRayRefs = leaf->rays.size(); 
    898965 
    … …  
    902969VssTree::TerminationCriteriaSatisfied(VssTreeLeaf *leaf) 
    903970{ 
    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                   ); 
    909978} 
    910979 
    … …  
    912981VssTreeNode * 
    913982VssTree::SubdivideNode( 
    914                                                                                         VssTreeLeaf *leaf, 
    915                                                                                         const AxisAlignedBox3 &box, 
    916                                                                                         AxisAlignedBox3 &backBBox, 
    917                                                                                         AxisAlignedBox3 &frontBBox 
    918                                                                                         ) 
    919 { 
    920    
    921         if (TerminationCriteriaSatisfied(leaf)) { 
     983                                          VssTreeLeaf *leaf, 
     984                                          const AxisAlignedBox3 &box, 
     985                                          AxisAlignedBox3 &backBBox, 
     986                                          AxisAlignedBox3 &frontBBox 
     987                                          ) 
     988{ 
     989   
     990  if (TerminationCriteriaSatisfied(leaf)) { 
    922991#if 0 
    923                 if (leaf->depth >= termMaxDepth) { 
    924                         cout<<"Warning: max depth reached depth="<<(int)leaf->depth<<" rays="<<leaf->rays.size()<<endl; 
    925                         cout<<"Bbox: "<<GetBBox(leaf)<<" dirbbox:"<<GetDirBBox(leaf)<<endl; 
    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        } 
    927996#endif 
    928997                 
    929                 return leaf; 
    930         } 
    931          
    932         float position; 
    933          
    934         // first count ray sides 
     998        return leaf; 
     999  } 
     1000         
     1001  float position; 
     1002         
     1003  // first count ray sides 
    9351004  int raysBack; 
    9361005  int raysFront; 
    937         int pvsBack; 
    938         int pvsFront; 
     1006  int pvsBack; 
     1007  int pvsFront; 
    9391008         
    9401009  // select subdivision axis 
    9411010  int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront); 
    942         //      cout<<axis<<" "; 
    943          
    944         //      cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<< 
    945         //              pvsFront<<endl; 
     1011  //    cout<<axis<<" "; 
     1012         
     1013  //    cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<< 
     1014  //            pvsFront<<endl; 
    9461015 
    9471016  if (axis == -1) { 
    … …  
    9641033 
    9651034  VssTreeLeaf *back = new VssTreeLeaf(node, raysBack); 
    966         back->SetPvsSize(pvsBack); 
    9671035  VssTreeLeaf *front = new VssTreeLeaf(node, raysFront); 
    968         front->SetPvsSize(pvsFront); 
    9691036 
    9701037  // replace a link from node's parent 
    … …  
    9751042         
    9761043  if (axis <= VssTreeNode::SPLIT_Z) { 
    977                 backBBox.SetMax(axis, position); 
     1044        backBBox.SetMax(axis, position); 
    9781045    frontBBox.SetMin(axis, position); 
    9791046                 
    980                 for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 
    981                                 ri != leaf->rays.end(); 
    982                                 ri++) { 
     1047        for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 
     1048                ri != leaf->rays.end(); 
     1049                ri++) { 
    9831050      if ((*ri).mRay->IsActive()) { 
    9841051                                 
    985                                 // first unref ray from the former leaf 
    986                                 (*ri).mRay->Unref(); 
    987  
    988                                 Debug << "computed t: " << (*ri).mRay->mT << endl; 
    989                                 // determine the side of this ray with respect to the plane 
    990                                 int side = node->ComputeRayIntersection(*ri, (*ri).mRay->mT); 
    991  
    992                                 if (side == 0) { 
    993                                         if ((*ri).mRay->HasPosDir(axis)) { 
    994                                                 back->AddRay(VssTreeNode::RayInfo((*ri).mRay, 
    995                                                                                                                                                                                         (*ri).mMinT, 
    996                                                                                                                                                                                         (*ri).mRay->mT) 
    997                                                                                                 ); 
    998                                                 front->AddRay(VssTreeNode::RayInfo((*ri).mRay, 
    999                                                                                                                                                                                         (*ri).mRay->mT, 
    1000                                                                                                                                                                                         (*ri).mMaxT)); 
    1001                                         } else { 
    1002                                                 back->AddRay(VssTreeNode::RayInfo((*ri).mRay, 
    1003                                                                                                                                                                                         (*ri).mRay->mT, 
    1004                                                                                                                                                                                         (*ri).mMaxT)); 
    1005                                                 front->AddRay(VssTreeNode::RayInfo((*ri).mRay, 
    1006                                                                                                                                                                                         (*ri).mMinT, 
    1007                                                                                                                                                                                         (*ri).mRay->mT)); 
    1008                                         } 
    1009                                 } else 
    1010                                         if (side == 1)  
    1011                                                 front->AddRay(*ri); 
    1012                                         else 
    1013                                                 back->AddRay(*ri); 
     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); 
    10141081      } else 
    1015                                 (*ri).mRay->Unref(); 
     1082                (*ri).mRay->Unref(); 
    10161083    } 
    10171084  } else { 
    … …  
    10201087     
    10211088    for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 
    1022                                 ri != leaf->rays.end(); 
    1023                                 ri++) { 
     1089                ri != leaf->rays.end(); 
     1090                ri++) { 
    10241091      if ((*ri).mRay->IsActive()) { 
    1025                                 // first unref ray from the former leaf 
    1026                                 (*ri).mRay->Unref(); 
    1027  
    1028                                 int side; 
    1029                                 if ((*ri).mRay->GetDirParametrization(axis - 3) > position) 
    1030                                         side = 1; 
    1031                                 else 
    1032                                         side = -1; 
    1033                                  
    1034                                 if (side == 1) 
    1035                                         front->AddRay(*ri); 
    1036                                 else 
    1037                                         back->AddRay(*ri); 
     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); 
    10381105                                 
    10391106      } else 
    1040                                 (*ri).mRay->Unref(); 
     1107                (*ri).mRay->Unref(); 
    10411108    } 
    10421109  } 
    1043          
     1110 
     1111  front->SetPvsSize(pvsFront); 
     1112  back->SetPvsSize(pvsBack); 
     1113 
    10441114  // update stats 
    10451115  stat.rayRefs -= leaf->rays.size(); 
    … …  
    10761146      //      cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl; 
    10771147      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; 
    10811151      } 
    10821152       
    10831153      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); 
    10871157      } else { 
    1088         tstack.push(in->back); 
    1089         tstack.push(in->front); 
     1158                tstack.push(in->back); 
     1159                tstack.push(in->front); 
    10901160      } 
    10911161    } 
    … …  
    11061176VssTreeNode * 
    11071177VssTree::SubdivideLeaf( 
    1108                                                                                         VssTreeLeaf *leaf 
    1109                                                                                         ) 
     1178                                          VssTreeLeaf *leaf 
     1179                                          ) 
    11101180{ 
    11111181  VssTreeNode *node = leaf; 
    … …  
    11131183  AxisAlignedBox3 leafBBox = GetBBox(leaf); 
    11141184 
    1115         static int pass = 0; 
    1116         pass ++; 
     1185  static int pass = 0; 
     1186  pass ++; 
    11171187         
    11181188  // check if we should perform a dynamic subdivision of the leaf 
    1119         if (!TerminationCriteriaSatisfied(leaf)) { 
     1189  if (!TerminationCriteriaSatisfied(leaf)) { 
    11201190     
    1121                 // memory check and realese... 
     1191        // memory check and realese... 
    11221192    if (GetMemUsage() > maxTotalMemory) { 
    11231193      ReleaseMemory( pass ); 
    … …  
    11291199    node = 
    11301200      SubdivideNode(leaf, 
    1131                                                                                 leafBBox, 
    1132                                                                                 backBBox, 
    1133                                                                                 frontBBox 
    1134                                                                                 ); 
     1201                                        leafBBox, 
     1202                                        backBBox, 
     1203                                        frontBBox 
     1204                                        ); 
    11351205  } 
    11361206         
    … …  
    11421212void 
    11431213VssTree::UpdateRays(VssRayContainer &remove, 
    1144                                                                                 VssRayContainer &add 
    1145                                                                                 ) 
     1214                                        VssRayContainer &add 
     1215                                        ) 
    11461216{ 
    11471217  VssTreeLeaf::NewMail(); 
    … …  
    11601230      ri++) { 
    11611231    if ((*ri)->ScheduledForRemoval()) 
    1162 //      RemoveRay(*ri, NULL, false); 
    1163 // !!! BUG - with true it does not work correctly - aggreated delete 
     1232          //      RemoveRay(*ri, NULL, false); 
     1233          // !!! BUG - with true it does not work correctly - aggreated delete 
    11641234      RemoveRay(*ri, NULL, true); 
    11651235    else 
    … …  
    11731243      ri != add.end(); 
    11741244      ri++) { 
    1175                 VssTreeNode::RayInfo info(*ri); 
    1176                 if (ClipRay(info, bbox)) 
    1177                         AddRay(info); 
     1245        VssTreeNode::RayInfo info(*ri); 
     1246        if (ClipRay(info, bbox)) 
     1247          AddRay(info); 
    11781248  } 
    11791249} 
    … …  
    11821252void 
    11831253VssTree::RemoveRay(VssRay *ray, 
    1184                                                                         vector<VssTreeLeaf *> *affectedLeaves, 
    1185                                                                         const bool removeAllScheduledRays 
    1186                                                                         ) 
     1254                                  vector<VssTreeLeaf *> *affectedLeaves, 
     1255                                  const bool removeAllScheduledRays 
     1256                                  ) 
    11871257{ 
    11881258         
    … …  
    12111281       
    12121282      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             if (leaf->rays[i].mRay->ScheduledForRemoval()) { 
    1222               // find a ray to replace it with 
    1223               while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) { 
    1224                 stat.removedRayRefs++; 
    1225                 leaf->rays[tail].mRay->Unref(); 
    1226                 leaf->rays.pop_back(); 
    1227                 tail--; 
    1228               } 
    1229  
    1230               if (tail < i) 
    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; 
    12321302               
    1233               stat.removedRayRefs++; 
    1234               leaf->rays[i].mRay->Unref(); 
    1235               leaf->rays[i] = leaf->rays[tail]; 
    1236               leaf->rays.pop_back(); 
    1237               tail--; 
    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                } 
    12411311      } 
    12421312       
    12431313      if (!removeAllScheduledRays) 
    1244         for (int i=0; i < (int)leaf->rays.size(); i++) { 
    1245           if (leaf->rays[i].mRay == ray) { 
    1246             stat.removedRayRefs++; 
    1247             ray->Unref(); 
    1248             leaf->rays[i] = leaf->rays[leaf->rays.size()-1]; 
    1249             leaf->rays.pop_back(); 
    1250             // check this ray again 
    1251             break; 
    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                } 
    12541324       
    12551325    } 
    … …  
    12921362void 
    12931363VssTree::TraverseInternalNode( 
    1294                                                                                                                         RayTraversalData &data, 
    1295                                                                                                                         stack<RayTraversalData> &tstack) 
     1364                                                          RayTraversalData &data, 
     1365                                                          stack<RayTraversalData> &tstack) 
    12961366{ 
    12971367  VssTreeInterior *in =  (VssTreeInterior *) data.node; 
    … …  
    13011371    // determine the side of this ray with respect to the plane 
    13021372    int side = in->ComputeRayIntersection(data.rayData, 
    1303                                                                                                                                                                         data.rayData.mRay->mT); 
     1373                                                                                  data.rayData.mRay->mT); 
    13041374     
    13051375   
    13061376    if (side == 0) { 
    13071377      if (data.rayData.mRay->HasPosDir(in->axis)) { 
    1308                                 tstack.push(RayTraversalData(in->back, 
    1309                                                                                                                                                 VssTreeNode::RayInfo(data.rayData.mRay, 
    1310                                                                                                                                                                                                                                         data.rayData.mMinT, 
    1311                                                                                                                                                                                                                                         data.rayData.mRay->mT)) 
    1312                                                                                 ); 
    1313                                  
    1314                                 tstack.push(RayTraversalData(in->front, 
    1315                                                                                                                                                 VssTreeNode::RayInfo(data.rayData.mRay, 
    1316                                                                                                                                                                                                                                         data.rayData.mRay->mT, 
    1317                                                                                                                                                                                                                                         data.rayData.mMaxT 
    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                                        ); 
    13201390         
    13211391      } else { 
    1322                                 tstack.push(RayTraversalData(in->back, 
    1323                                                                                                                                                 VssTreeNode::RayInfo(data.rayData.mRay, 
    1324                                                                                                                                                                                                                                         data.rayData.mRay->mT, 
    1325                                                                                                                                                                                                                                         data.rayData.mMaxT 
    1326                                                                                                                                                                                                                                         )) 
    1327                                                                                 ); 
    1328                                  
    1329                                 tstack.push(RayTraversalData(in->front, 
    1330                                                                                                                                                 VssTreeNode::RayInfo(data.rayData.mRay, 
    1331                                                                                                                                                                                                                                         data.rayData.mMinT, 
    1332                                                                                                                                                                                                                                         data.rayData.mRay->mT)) 
    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                                        ); 
    13341404                                 
    13351405                                 
    … …  
    13371407    } else 
    13381408      if (side == 1) 
    1339                                 tstack.push(RayTraversalData(in->front, data.rayData)); 
     1409                tstack.push(RayTraversalData(in->front, data.rayData)); 
    13401410      else 
    1341                                 tstack.push(RayTraversalData(in->back, data.rayData)); 
     1411                tstack.push(RayTraversalData(in->back, data.rayData)); 
    13421412  }  
    13431413  else { 
    13441414    // directional split 
    1345                 if (data.rayData.mRay->GetDirParametrization(in->axis - 3) > in->position) 
    1346                         tstack.push(RayTraversalData(in->front, data.rayData)); 
    1347                 else 
    1348                         tstack.push(RayTraversalData(in->back, data.rayData)); 
     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)); 
    13491419  } 
    13501420} 
    … …  
    13671437#endif 
    13681438 
    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(); 
    13721442   
    13731443  tstack.push(sroot); 
    … …  
    13821452      VssTreeLeaf *leaf = (VssTreeLeaf *) node; 
    13831453      for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 
    1384                                         ri != leaf->rays.end(); 
    1385                                         ri++) { 
    1386                                  
    1387                                 totalRayCount++; 
    1388                                 if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed()) { 
    1389                                         (*ri).mRay->Mail(); 
    1390                                         rayCount++; 
    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                } 
    13921462      } 
    13931463    } else { 
    … …  
    14161486       
    14171487      for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 
    1418                                         ri != leaf->rays.end(); 
    1419                                         ri++) { 
    1420                                  
    1421                                 // unref this ray from the old node 
    1422                                  
    1423                                 if ((*ri).mRay->IsActive()) { 
    1424                                         (*ri).mRay->Unref(); 
    1425                                         if (!(*ri).mRay->Mailed()) { 
    1426                                                 (*ri).mRay->Mail(); 
    1427                                                 newLeaf->AddRay(*ri); 
    1428                                         } 
    1429                                 } else 
    1430                                         (*ri).mRay->Unref(); 
     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(); 
    14311501                                 
    14321502      } 
    … …  
    14401510  delete sroot; 
    14411511   
    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); 
    14461516 
    14471517 
    … …  
    14601530#endif 
    14611531 
    1462         //  tstat.collapsedNodes += collapsedNodes; 
    1463         //  tstat.collapsedRays += totalRayCount - rayCount; 
     1532  //  tstat.collapsedNodes += collapsedNodes; 
     1533  //  tstat.collapsedRays += totalRayCount - rayCount; 
    14641534     
    14651535  return totalRayCount - rayCount; 
    … …  
    14681538 
    14691539int 
    1470 VssTree::GetPvsSize(VssTreeNode *node, const AxisAlignedBox3 &box) const 
    1471 { 
    1472         stack<VssTreeNode *> tstack; 
     1540VssTree::GetPvsSize(const AxisAlignedBox3 &box) const 
     1541{ 
     1542  stack<VssTreeNode *> tstack; 
    14731543  tstack.push(root); 
    14741544 
    1475         Intersectable::NewMail(); 
    1476         int pvsSize = 0; 
     1545  Intersectable::NewMail(); 
     1546  int pvsSize = 0; 
    14771547         
    14781548  while (!tstack.empty()) { 
    … …  
    14821552  
    14831553    if (node->IsLeaf()) { 
    1484                         VssTreeLeaf *leaf = (VssTreeLeaf *)node; 
    1485                         for(VssTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin(); 
    1486                                         ri != leaf->rays.end(); 
    1487                                         ri++) 
    1488                                 if ((*ri).mRay->IsActive()) { 
    1489                                         Intersectable *object; 
     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; 
    14901560#if BIDIRECTIONAL_RAY 
    1491                                         object = (*ri).mRay->mOriginObject; 
    1492                                         if (object && !object->Mailed()) { 
    1493                                                 pvsSize++; 
    1494                                                 object->Mail(); 
    1495                                         } 
     1561                  object = (*ri).mRay->mOriginObject; 
     1562                  if (object && !object->Mailed()) { 
     1563                        pvsSize++; 
     1564                        object->Mail(); 
     1565                  } 
    14961566#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                  } 
    15161572                } 
    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; 
    15191589} 
    15201590 
    15211591void 
    15221592VssTree::GetRayContributionStatistics( 
    1523                                                                                                                                                         float &minRayContribution, 
    1524                                                                                                                                                         float &maxRayContribution, 
    1525                                                                                                                                                         float &avgRayContribution 
    1526                                                                                                                                                         ) 
    1527 { 
    1528         stack<VssTreeNode *> tstack; 
     1593                                                                          float &minRayContribution, 
     1594                                                                          float &maxRayContribution, 
     1595                                                                          float &avgRayContribution 
     1596                                                                          ) 
     1597{ 
     1598  stack<VssTreeNode *> tstack; 
    15291599  tstack.push(root); 
    15301600         
    1531         minRayContribution = 1.0f; 
    1532         maxRayContribution = 0.0f; 
    1533         float sumRayContribution = 0.0f; 
    1534         int leaves = 0; 
     1601  minRayContribution = 1.0f; 
     1602  maxRayContribution = 0.0f; 
     1603  float sumRayContribution = 0.0f; 
     1604  int leaves = 0; 
    15351605 
    15361606  while (!tstack.empty()) { 
    … …  
    15391609                 
    15401610    if (node->IsLeaf()) { 
    1541                         leaves++; 
    1542                         VssTreeLeaf *leaf = (VssTreeLeaf *)node; 
    1543                         float c = leaf->GetAvgRayContribution(); 
    1544                         if (c > maxRayContribution) 
    1545                                 maxRayContribution = c; 
    1546                         if (c < minRayContribution) 
    1547                                 minRayContribution = c; 
    1548                         sumRayContribution += c; 
     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; 
    15491619                         
    1550                 } else { 
    1551                         VssTreeInterior *in = (VssTreeInterior *)node; 
    1552                         // both nodes for directional splits 
    1553                         tstack.push(in->front); 
    1554                         tstack.push(in->back); 
    1555                 } 
    1556         } 
    1557          
    1558         cout<<"sum="<<sumRayContribution<<endl; 
    1559         cout<<"leaves="<<leaves<<endl; 
    1560         avgRayContribution = sumRayContribution/(float)leaves; 
     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; 
    15611631} 
    15621632 
    … …  
    15641634int 
    15651635VssTree::GenerateRays(const float ratioPerLeaf, 
    1566                                                                                         SimpleRayContainer &rays) 
    1567 { 
    1568         stack<VssTreeNode *> tstack; 
     1636                                          SimpleRayContainer &rays) 
     1637{ 
     1638  stack<VssTreeNode *> tstack; 
    15691639  tstack.push(root); 
    15701640         
    … …  
    15741644                 
    15751645    if (node->IsLeaf()) { 
    1576                         VssTreeLeaf *leaf = (VssTreeLeaf *)node; 
    1577                         float c = leaf->GetAvgRayContribution(); 
    1578                         int num = (c*ratioPerLeaf + 0.5); 
    1579                         //                      cout<<num<<" "; 
    1580  
    1581                         for (int i=0; i < num; i++) { 
    1582                                 Vector3 origin = GetBBox(leaf).GetRandomPoint(); 
    1583                                 Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint(); 
    1584                                 Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x)); 
    1585                                 //cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl; 
    1586                                 rays.push_back(SimpleRay(origin, direction)); 
    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          } 
    15881658                         
    1589                 } else { 
    1590                         VssTreeInterior *in = (VssTreeInterior *)node; 
    1591                         // both nodes for directional splits 
    1592                         tstack.push(in->front); 
    1593                         tstack.push(in->back); 
    1594                 } 
    1595         } 
    1596  
    1597         return rays.size(); 
     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(); 
    15981668} 
    15991669 
    … …  
    16011671VssTree::CollectLeaves(vector<VssTreeLeaf *> &leaves) 
    16021672{ 
    1603         stack<VssTreeNode *> tstack; 
     1673  stack<VssTreeNode *> tstack; 
    16041674  tstack.push(root); 
    16051675         
    … …  
    16091679                 
    16101680    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 
     1692bool 
     1693VssTree::ValidLeaf(VssTreeLeaf *leaf) const 
     1694{ 
     1695  return leaf->rays.size() > termMinRays/4; 
     1696} 
     1697 
     1698void 
     1699GenerateExtendedConvexCombinationWeights(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 
     1715void 
     1716VssTree::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  } 
    16201756} 
    16211757 
    16221758int 
    16231759VssTree::GenerateRays(const int numberOfRays, 
    1624                                                                                         const int numberOfLeaves, 
    1625                                                                                         SimpleRayContainer &rays) 
    1626 { 
    1627  
    1628         vector<VssTreeLeaf *> leaves; 
    1629          
    1630         CollectLeaves(leaves); 
    1631          
    1632         sort(leaves.begin(), 
    1633                         leaves.end(), 
    1634                         GreaterContribution); 
     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); 
    16351771                          
    16361772 
    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(); 
    16631797} 
    16641798 
    … …  
    16671801VssTree::GetAvgPvsSize() 
    16681802{ 
    1669         stack<VssTreeNode *> tstack; 
     1803  stack<VssTreeNode *> tstack; 
    16701804  tstack.push(root); 
    16711805 
    1672         int sumPvs = 0; 
    1673         int leaves = 0; 
     1806  int sumPvs = 0; 
     1807  int leaves = 0; 
    16741808  while (!tstack.empty()) { 
    16751809    VssTreeNode *node = tstack.top(); 
    … …  
    16771811                 
    16781812    if (node->IsLeaf()) { 
    1679                         VssTreeLeaf *leaf = (VssTreeLeaf *)node; 
    1680                         // update pvs size 
    1681                         leaf->UpdatePvsSize(); 
    1682                         sumPvs += leaf->GetPvsSize(); 
    1683                         leaves++; 
    1684                 } else { 
    1685                         VssTreeInterior *in = (VssTreeInterior *)node; 
    1686                         // both nodes for directional splits 
    1687                         tstack.push(in->front); 
    1688                         tstack.push(in->back); 
    1689                 } 
    1690         } 
    1691  
    1692  
    1693         return sumPvs/(float)leaves; 
    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  
    226226                return mRay->GetOrigin(axis) + GetMaxT()*mRay->GetDir(axis); 
    227227        } 
     228 
     229        Vector3 Extrap(const float t) const { 
     230                return mRay->Extrap(t); 
     231        } 
    228232         
    229233#if USE_FIXEDPOINT_T 
    … …  
    411415   
    412416  RayInfoContainer rays; 
     417        int mPassingRays; 
     418         
    413419        bool mValidPvs; 
     420         
     421         
    414422         
    415423  VssTreeLeaf(VssTreeInterior *p, 
    416424                                                        const int nRays 
    417                                                         ):VssTreeNode(p), rays(), mPvsSize(0), mValidPvs(false) { 
     425                                                        ):VssTreeNode(p), rays(), mPvsSize(0), mPassingRays(0), mValidPvs(false) { 
    418426    rays.reserve(nRays); 
    419427  } 
    … …  
    431439    rays.push_back(data); 
    432440    data.mRay->Ref(); 
     441                if (data.GetRayClass() == RayInfo::PASSING_RAY) 
     442                        mPassingRays++; 
    433443  } 
    434444         
    … …  
    438448        void SetPvsSize(const int s) { 
    439449                mPvsSize = s; 
     450                mValidPvs = true; 
    440451        } 
    441452 
    … …  
    537548                                leafb->rays.size()*b.bbox.GetVolume(); 
    538549#endif 
    539 #if 1 
     550#if 0 
    540551                        return 
    541552                                leafa->GetPvsSize()*a.bbox.GetVolume() 
    … …  
    555566                                leafb->GetPvsSize()/(leafb->rays.size()+1); 
    556567#endif 
    557 #if 0 
     568#if 1 
    558569                        return 
    559570                                leafa->GetPvsSize()*leafa->rays.size() 
    … …  
    623634 
    624635  // type of the splitting to use fo rthe tree construction 
    625   enum {ESplitRegular, ESplitHeuristic }; 
     636  enum {ESplitRegular, ESplitHeuristic, ESplitHybrid }; 
    626637  int splitType; 
     638 
     639        bool mSplitUseOnlyDrivingAxis; 
     640 
     641        // use ray space subdivision instead of view space subdivision 
     642        bool mUseRss; 
    627643         
    628644  // maximal size of the box on which the refdir splitting can be performed 
    … …  
    723739  } 
    724740   
     741 
    725742        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                                                                ); 
    747752         
    748753        float 
    … …  
    757762                                                                ); 
    758763 
    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 { 
    760787    if (node->parent == NULL) 
    761788      return bbox; 
    … …  
    775802  } 
    776803 
    777   AxisAlignedBox3 GetDirBBox(const VssTreeNode *node) { 
     804  AxisAlignedBox3 GetDirBBox(const VssTreeNode *node) const { 
    778805 
    779806    if (node->parent == NULL) 
    … …  
    834861        int 
    835862        GetRootPvsSize() const { 
    836                 return GetPvsSize(root, bbox); 
     863                return GetPvsSize(bbox); 
    837864        } 
    838865         
    839866        int 
    840         GetPvsSize(VssTreeNode *node, const AxisAlignedBox3 &box) const; 
     867        GetPvsSize(const AxisAlignedBox3 &box) const; 
    841868 
    842869        void 
    … …  
    874901                                        ); 
    875902 
    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 
    877914}; 
    878915 

  • trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

    r427 r434  
    1010#include "VssRay.h" 
    1111#include "VspKdTree.h" 
     12#include "VssTree.h" 
    1213 
    1314X3dExporter::X3dExporter(const string filename):Exporter(filename) 
    … …  
    154155  for (; ri != rays.end(); ri++) { 
    155156    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); 
    157158         
    158159    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"; 
    160161  } 
    161162   
    … …  
    699700} 
    700701 
     702 
     703void 
     704X3dExporter::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 
     726bool 
     727X3dExporter::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} 
    701782 
    702783bool 

  • trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

    r425 r434  
    3838  bool 
    3939  ExportKdTree(const KdTree &tree); 
    40    
     40 
     41        bool 
     42  ExportVssTree(const VssTree &tree); 
     43 
    4144  bool  
    4245  ExportVspKdTree(const VspKdTree &tree, const int maxPvs); 
    … …  
    108111 
    109112  bool 
    110   ExportBspTreeRayDensity(const BspTree &tree);   
     113  ExportBspTreeRayDensity(const BspTree &tree); 
     114 
     115        void 
     116        AddBoxToMesh(const AxisAlignedBox3 &box, 
     117                                                         Mesh *mesh); 
     118                 
    111119}; 
    112120  

  • trunk/VUT/GtpVisibilityPreprocessor/src/common.h

    r372 r434  
    238238 
    239239 
     240 
    240241inline Real sqr(Real a) 
    241242{ 

  • trunk/VUT/GtpVisibilityPreprocessor/src/default.env

    r430 r434  
    1313#;../data/vienna/vienna-plane.x3d 
    1414# filename ../data/vienna/viewcells-25-sel.x3d 
    15 filename ../data/atlanta/atlanta2.x3d 
     15# filename ../data/atlanta/atlanta2.x3d 
    1616# filename ../data/soda/soda.dat 
    17 # filename ../data/soda/soda5.dat 
     17 filename ../data/soda/soda5.dat 
    1818} 
    1919 
    … …  
    2525VssPreprocessor { 
    2626        samplesPerPass  100000 
    27         initialSamples 2000000 
     27        initialSamples 200000 
    2828        vssSamples 1000000 
    29         vssSamplesPerPass 100000 
     29        vssSamplesPerPass 50000 
    3030        useImportanceSampling true 
    3131} 
    3232 
    3333VssTree { 
     34        useRss    true 
    3435        epsilon         1e-6 
    3536 
    … …  
    3839        minRays         100 
    3940        minSize         0.001 
    40   maxCostRatio  0.98 
     41  maxCostRatio  1.1 
    4142        maxRayContribution 0.05 
    4243         
    … …  
    4445        maxStaticMemory 50 
    4546 
    46         splitType regular 
    47 #       splitType heuristics 
     47#       splitType regular 
     48#       splitType heuristic 
     49        splitType hybrid 
     50        splitUseOnlyDrivingAxis true 
    4851 
    4952        numberOfEndPointDomains 10000 
Note: See TracChangeset for help on using the changeset viewer.