Ignore:
Timestamp:
01/03/08 15:53:44 (17 years ago)
Author:
bittner
Message:

big merge: preparation for havran ray caster, check if everything works

File:
1 edited

Legend:

Unmodified
Added
Removed

  • GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.cpp

    r2571 r2575  
    2626inline static bool ilt(Intersectable *obj1, Intersectable *obj2) 
    2727{ 
    28         return obj1->mId < obj2->mId; 
     28  return obj1->mId < obj2->mId; 
    2929} 
    3030 
    … …  
    3333mParent(parent), mMailbox(0), mIntersectable(NULL) 
    3434{ 
    35         if (parent) 
    36                 mDepth = parent->mDepth+1; 
    37         else 
    38                 mDepth = 0; 
     35  if (parent) 
     36    mDepth = parent->mDepth+1; 
     37  else 
     38    mDepth = 0; 
    3939} 
    4040 
    … …  
    4242KdInterior::~KdInterior() 
    4343{ 
    44         // recursivly destroy children 
    45         DEL_PTR(mFront); 
    46         DEL_PTR(mBack); 
     44  // recursivly destroy children 
     45  DEL_PTR(mFront); 
     46  DEL_PTR(mBack); 
    4747} 
    4848 
    … …  
    5050KdLeaf::~KdLeaf() 
    5151{ 
    52         DEL_PTR(mViewCell);   
     52  DEL_PTR(mViewCell);   
    5353} 
    5454 
    … …  
    5757{  
    5858  mRoot = new KdLeaf(NULL, 0); 
    59   Environment::GetSingleton()->GetIntValue("KdTree.Termination.maxNodes", mTermMaxNodes); 
    60   Environment::GetSingleton()->GetIntValue("KdTree.Termination.maxDepth", mTermMaxDepth); 
    61   Environment::GetSingleton()->GetIntValue("KdTree.Termination.minCost", mTermMinCost); 
    62   Environment::GetSingleton()->GetFloatValue("KdTree.Termination.maxCostRatio", mMaxCostRatio); 
    63   Environment::GetSingleton()->GetFloatValue("KdTree.Termination.ct_div_ci", mCt_div_ci); 
    64   Environment::GetSingleton()->GetFloatValue("KdTree.splitBorder", mSplitBorder); 
    65   Environment::GetSingleton()->GetFloatValue("KdTree.pvsArea", mKdPvsArea); 
    66  
    67   Environment::GetSingleton()->GetBoolValue("KdTree.sahUseFaces", mSahUseFaces); 
     59  Environment::GetSingleton()->GetIntValue("KdTree.Termination.maxNodes", 
     60                                           mTermMaxNodes); 
     61  Environment::GetSingleton()->GetIntValue("KdTree.Termination.maxDepth", 
     62                                           mTermMaxDepth); 
     63  Environment::GetSingleton()->GetIntValue("KdTree.Termination.minCost", 
     64                                           mTermMinCost); 
     65  Environment::GetSingleton()->GetFloatValue("KdTree.Termination.maxCostRatio", 
     66                                             mMaxCostRatio); 
     67  Environment::GetSingleton()->GetFloatValue("KdTree.Termination.ct_div_ci", 
     68                                             mCt_div_ci); 
     69  Environment::GetSingleton()->GetFloatValue("KdTree.splitBorder", 
     70                                             mSplitBorder); 
     71  Environment::GetSingleton()->GetFloatValue("KdTree.pvsArea", 
     72                                             mKdPvsArea); 
     73 
     74  Environment::GetSingleton()->GetBoolValue("KdTree.sahUseFaces", 
     75                                            mSahUseFaces); 
    6876 
    6977  char splitType[64]; 
    … …  
    97105KdTree::Construct() 
    98106{ 
    99  
    100107  if (!splitCandidates) 
    101108    splitCandidates = new vector<SortableEntry *>; 
    … …  
    158165     
    159166    KdNode *node = SubdivideNode((KdLeaf *) data.mNode, 
    160                                                                 data.mBox, 
    161                                                                 backBox, 
    162                                                                 frontBox 
    163                                                                 ); 
    164  
    165         if (result == NULL) 
     167                                data.mBox, 
     168                                backBox, 
     169                                frontBox 
     170                                ); 
     171 
     172    if (result == NULL) 
    166173      result = node; 
    167174     
    168175    if (!node->IsLeaf()) { 
    169  
    170176      KdInterior *interior = (KdInterior *) node; 
    171177      // push the children on the stack 
    … …  
    173179      tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth+1)); 
    174180       
    175     } else { 
     181    } 
     182    else { 
    176183      EvaluateLeafStats(data); 
    177184    } 
    … …  
    186193KdTree::TerminationCriteriaMet(const KdLeaf *leaf) 
    187194{ 
    188         const bool criteriaMet = 
    189                 ((int)leaf->mObjects.size() <= mTermMinCost) || 
    190                 (leaf->mDepth >= mTermMaxDepth); 
    191   
    192         if (0 && criteriaMet) 
    193                 cerr<<"\n OBJECTS="<<(int)leaf->mObjects.size()<<endl; 
    194  
    195         return criteriaMet; 
     195  const bool criteriaMet = 
     196    ((int)leaf->mObjects.size() <= mTermMinCost) || 
     197    (leaf->mDepth >= mTermMaxDepth); 
     198   
     199  if (0 && criteriaMet) 
     200    cerr<<"\n OBJECTS="<<(int)leaf->mObjects.size()<<endl; 
     201   
     202  return criteriaMet; 
    196203} 
    197204 
    … …  
    199206int 
    200207KdTree::SelectPlane(KdLeaf *leaf, 
    201                                         const AxisAlignedBox3 &box, 
    202                                         float &position 
    203                                         ) 
     208                    const AxisAlignedBox3 &box, 
     209                    float &position 
     210                    ) 
    204211{ 
    205212  int axis = -1; 
    … …  
    217224      bool mOnlyDrivingAxis = true; 
    218225 
    219           if (mOnlyDrivingAxis) { 
    220                 axis = box.Size().DrivingAxis(); 
    221                 costRatio = BestCostRatio(leaf, 
    222                                                                   box, 
    223                                                                   axis, 
    224                                                                   position, 
    225                                                                   objectsBack, 
    226                                                                   objectsFront); 
    227       } else { 
    228                 costRatio = MAX_FLOAT; 
    229                 for (int i=0; i < 3; i++) { 
    230                   float p; 
    231                   float r = BestCostRatio(leaf, 
    232                                                                   box, 
    233                                                                   i, 
    234                                                                   p, 
    235                                                                   objectsBack, 
    236                                                                   objectsFront); 
    237                   if (r < costRatio) { 
    238                         costRatio = r; 
    239                         axis = i; 
    240                         position = p; 
    241                   } 
    242                 } 
     226      if (mOnlyDrivingAxis) { 
     227        axis = box.Size().DrivingAxis(); 
     228        costRatio = BestCostRatio(leaf, 
     229                                  box, 
     230                                  axis, 
     231                                  position, 
     232                                  objectsBack, 
     233                                  objectsFront); 
     234      } 
     235      else { 
     236        // for all 3 axes 
     237        costRatio = MAX_FLOAT; 
     238        for (int i=0; i < 3; i++) { 
     239          float p; 
     240          float r = BestCostRatio(leaf, 
     241                                  box, 
     242                                  i, 
     243                                  p, 
     244                                  objectsBack, 
     245                                  objectsFront); 
     246          if (r < costRatio) { 
     247            costRatio = r; 
     248            axis = i; 
     249            position = p; 
     250          } 
     251        } 
    243252      } 
    244253       
    245254      if (costRatio > mMaxCostRatio) { 
    246                 //cout<<"Too big cost ratio "<<costRatio<<endl; 
    247                 axis = -1; 
     255        //cout<<"Too big cost ratio "<<costRatio<<endl; 
     256        axis = -1; 
    248257      } 
    249258      break; 
    … …  
    254263} 
    255264 
    256 KdNode * 
     265KdNode* 
    257266KdTree::SubdivideNode( 
    258267                      KdLeaf *leaf, 
    … …  
    261270                      AxisAlignedBox3 &frontBBox 
    262271                      ) 
    263 { 
    264    
     272{   
    265273  if (TerminationCriteriaMet(leaf)) 
    266           return leaf; 
     274    return leaf; 
    267275 
    268276  float position; 
    … …  
    275283  } 
    276284   
    277   mStat.nodes+=2; 
     285  mStat.nodes += 2; 
    278286  mStat.splits[axis]++; 
    279287   
    … …  
    309317  } 
    310318 
    311    
    312319  KdLeaf *back = new KdLeaf(node, objectsBack); 
    313320  KdLeaf *front = new KdLeaf(node, objectsFront); 
    314  
    315321  
    316322  // replace a link from node's parent 
    … …  
    336342 
    337343 
    338         if (box.Max(axis) >= position ) 
    339         { 
     344    if (box.Max(axis) >= position ) 
     345    { 
    340346      front->mObjects.push_back(*mi); 
    341           //++ (*mi)->mReferences; 
    342         } 
     347      //++ (*mi)->mReferences; 
     348    } 
    343349         
    344350    if (box.Min(axis) < position ) 
    345         { 
     351    { 
    346352      back->mObjects.push_back(*mi); 
    347         // matt: no more ref 
    348         //  ++ (*mi)->mReferences; 
    349         } 
     353      // matt: no more ref 
     354      //  ++ (*mi)->mReferences; 
     355    } 
    350356 
    351357    mStat.objectRefs -= (int)leaf->mObjects.size(); 
    … …  
    353359  } 
    354360 
    355         // store objects referenced in more than one leaf 
    356         // for easy access 
    357         ProcessMultipleRefs(back); 
    358         ProcessMultipleRefs(front); 
    359  
    360         delete leaf; 
    361         return node; 
     361  // store objects referenced in more than one leaf 
     362  // for easy access 
     363  ProcessMultipleRefs(back); 
     364  ProcessMultipleRefs(front); 
     365   
     366  delete leaf; 
     367  return node; 
    362368} 
    363369 
    … …  
    365371void KdTree::ProcessMultipleRefs(KdLeaf *leaf) const 
    366372{ 
    367         // find objects from multiple kd-leaves 
    368         ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end(); 
    369  
    370         for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit) 
    371         { 
    372                 Intersectable *object = *oit; 
     373  // find objects from multiple kd-leaves 
     374  ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end(); 
     375 
     376  for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit) 
     377  { 
     378    Intersectable *object = *oit; 
    373379                 
    374                 // matt: no more ref 
    375                 /*if (object->mReferences > 1) 
    376                 { 
    377                         leaf->mMultipleObjects.push_back(object); 
    378                 }*/ 
    379         } 
     380    // matt: no more ref 
     381    /* 
     382      if (object->mReferences > 1) { 
     383        leaf->mMultipleObjects.push_back(object); 
     384      } 
     385    */ 
     386  } 
    380387} 
    381388 
    … …  
    464471void 
    465472KdTree::SortSubdivisionCandidates( 
    466                             KdLeaf *node, 
    467                             const int axis 
    468                             ) 
    469 { 
    470         CLEAR_CONTAINER(*splitCandidates); 
    471         //splitCandidates->clear(); 
    472  
    473     int requestedSize = 2*(int)node->mObjects.size(); 
    474          
    475         // creates a sorted split candidates array 
    476         if (splitCandidates->capacity() > 500000 && 
    477                 requestedSize < (int)(splitCandidates->capacity()/10) ) {                
    478                         delete splitCandidates; 
    479                         splitCandidates = new vector<SortableEntry *>; 
     473                                  KdLeaf *node, 
     474                                  const int axis 
     475                                  ) 
     476{ 
     477  CLEAR_CONTAINER(*splitCandidates); 
     478  //splitCandidates->clear(); 
     479   
     480  int requestedSize = 2*(int)node->mObjects.size(); 
     481   
     482  // creates a sorted split candidates array 
     483  if (splitCandidates->capacity() > 500000 && 
     484      requestedSize < (int)(splitCandidates->capacity()/10) ) {          
     485    delete splitCandidates; 
     486    splitCandidates = new vector<SortableEntry *>; 
    480487  } 
    481488   
    … …  
    487494      mi++)  
    488495  { 
    489           AxisAlignedBox3 box = (*mi)->GetBox(); 
    490  
    491           splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN, 
    492                                                                 box.Min(axis), 
    493                                                                 *mi) 
    494                                                                 ); 
     496    AxisAlignedBox3 box = (*mi)->GetBox(); 
     497 
     498    splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN, 
     499                                                box.Min(axis), 
     500                                                *mi) 
     501                              ); 
    495502     
    496       splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX, 
    497                                                                 box.Max(axis), 
    498                                                                 *mi) 
    499                                                                 ); 
     503    splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX, 
     504                                                box.Max(axis), 
     505                                                *mi) 
     506                              ); 
    500507  } 
    501508   
    … …  
    506513float 
    507514KdTree::BestCostRatio( 
    508                                           KdLeaf *node, 
    509                                           const AxisAlignedBox3 &box, 
    510                                           const int axis, 
    511                                           float &position, 
    512                                           int &objectsBack, 
    513                                           int &objectsFront 
    514                                           ) 
     515                      KdLeaf *node, 
     516                      const AxisAlignedBox3 &box, 
     517                      const int axis, 
     518                      float &position, 
     519                      int &objectsBack, 
     520                      int &objectsFront 
     521                      ) 
    515522{ 
    516523 
    … …  
    531538   
    532539  if (nodeId < 100) 
    533         costStream.open(filename); 
     540    costStream.open(filename); 
    534541 
    535542#endif 
    … …  
    577584      intersectionsRight -= (*ci)->intersectable->IntersectionComplexity(); 
    578585      break; 
    579     } 
     586    } // switch 
    580587 
    581588    if ((*ci)->value > minBand && (*ci)->value < maxBand) { 
    … …  
    587594      float sum; 
    588595      if (mSahUseFaces) 
    589                 sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea(); 
     596        sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea(); 
    590597      else 
    591                 sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea(); 
     598        sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea(); 
    592599       
    593600      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 
    … …  
    595602 
    596603#if DEBUG_COST 
    597   if (nodeId < 100) { 
     604      if (nodeId < 100) { 
    598605        float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size(); 
    599606        float newCost = mCt_div_ci + sum/boxArea; 
    600607        float ratio = newCost/oldCost; 
    601608        costStream<<(*ci)->value<<" "<<ratio<<endl; 
    602   } 
     609      } 
    603610#endif 
    604            
     611       
    605612      if (sum < minSum) { 
    606                 minSum = sum; 
    607                 position = (*ci)->value; 
    608                  
    609                 objectsBack = objectsLeft; 
    610                 objectsFront = objectsRight; 
    611       } 
    612     } 
    613   } 
     613        minSum = sum; 
     614        position = (*ci)->value; 
     615         
     616        objectsBack = objectsLeft; 
     617        objectsFront = objectsRight; 
     618      } 
     619    } 
     620  } // for ci 
    614621   
    615622  float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size(); 
    … …  
    627634int 
    628635KdTree::CastRay( 
    629                                 Ray &ray 
    630                                 ) 
     636                Ray &ray 
     637                ) 
    631638{ 
    632639   
    … …  
    666673 
    667674      if (entp[axis] <= position) { 
    668                 if (extp[axis] <= position) { 
    669                   node = in->mBack; 
    670                   // cases N1,N2,N3,P5,Z2,Z3 
    671                   continue; 
    672                 } else { 
    673                   // case N4 
    674                   node = in->mBack; 
    675                   farChild = in->mFront; 
    676                 } 
     675        if (extp[axis] <= position) { 
     676          node = in->mBack; 
     677          // cases N1,N2,N3,P5,Z2,Z3 
     678          continue; 
     679        } 
     680        else { 
     681          // case N4 
     682          node = in->mBack; 
     683          farChild = in->mFront; 
     684        } 
    677685      } 
    678686      else { 
    679                 if (position <= extp[axis]) { 
    680                   node = in->mFront; 
    681                   // cases P1,P2,P3,N5,Z1 
    682                   continue; 
    683                 } else { 
    684                   node = in->mFront; 
    685                   farChild = in->mBack; 
    686                   // case P4 
    687                 } 
    688           } 
     687        if (position <= extp[axis]) { 
     688          node = in->mFront; 
     689          // cases P1,P2,P3,N5,Z1 
     690          continue; 
     691        } 
     692        else { 
     693          node = in->mFront; 
     694          farChild = in->mBack; 
     695          // case P4 
     696        } 
     697      } 
    689698      // $$ modification 3.5.2004 - hints from Kamil Ghais 
    690699      // case N4 or P4 
    … …  
    693702      extp = ray.GetLoc() + ray.GetDir()*tdist; 
    694703      maxt = tdist; 
    695         } else { 
    696           // compute intersection with all objects in this leaf 
    697           KdLeaf *leaf = (KdLeaf *) node; 
    698           if (ray.mFlags & Ray::STORE_KDLEAVES) 
    699                 ray.kdLeaves.push_back(leaf); 
     704    } 
     705    else { 
     706      // compute intersection with all objects in this leaf 
     707      KdLeaf *leaf = (KdLeaf *) node; 
     708      if (ray.mFlags & Ray::STORE_KDLEAVES) 
     709        ray.kdLeaves.push_back(leaf); 
    700710           
    701           ObjectContainer::const_iterator mi; 
    702           for ( mi = leaf->mObjects.begin(); 
    703                         mi != leaf->mObjects.end(); 
    704                         mi++) { 
    705                 Intersectable *object = *mi; 
    706                 if (!object->Mailed() ) { 
    707                   object->Mail(); 
    708                   if (ray.mFlags & Ray::STORE_TESTED_OBJECTS) 
     711      ObjectContainer::const_iterator mi; 
     712      for ( mi = leaf->mObjects.begin(); 
     713            mi != leaf->mObjects.end(); 
     714            mi++) { 
     715        Intersectable *object = *mi; 
     716        if (!object->Mailed() ) { 
     717          object->Mail(); 
     718          if (ray.mFlags & Ray::STORE_TESTED_OBJECTS) 
    709719                        ray.testedObjects.push_back(object); 
    710720                   
    711                   static int oi=1; 
    712                   if (MeshDebug)  
    713                         cout<<"Object "<<oi++; 
    714                    
    715                   hits += object->CastRay(ray); 
    716                    
    717                   if (MeshDebug) { 
    718                         if (!ray.intersections.empty())  
    719                           cout<<"nearest t="<<ray.intersections[0].mT<<endl; 
    720                         else 
    721                           cout<<"nearest t=-INF"<<endl; 
    722                   }        
    723                 } 
    724           } 
     721          static int oi=1; 
     722          if (MeshDebug)  
     723            cout<<"Object "<<oi++; 
    725724           
    726           if (hits && ray.GetType() == Ray::LOCAL_RAY) 
    727                 if (ray.intersections[0].mT <= maxt) 
    728                   break; 
     725          hits += object->CastRay(ray); 
    729726           
    730           // get the next node from the stack 
    731           if (tStack.empty()) 
    732                 break; 
     727          if (MeshDebug) { 
     728            if (!ray.intersections.empty())  
     729              cout<<"nearest t="<<ray.intersections[0].mT<<endl; 
     730            else 
     731              cout<<"nearest t=-INF"<<endl; 
     732          }        
     733        } 
     734      } 
    733735           
    734           entp = extp; 
    735           mint = maxt; 
    736           if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f) 
    737                 break; 
    738            
    739           RayTraversalData &s  = tStack.top(); 
    740           node = s.mNode; 
    741           extp = s.mExitPoint; 
    742           maxt = s.mMaxT; 
    743           tStack.pop(); 
    744         } 
     736      if (hits && ray.GetType() == Ray::LOCAL_RAY) 
     737        if (ray.intersections[0].mT <= maxt) 
     738          break; 
     739       
     740      // get the next node from the stack 
     741      if (tStack.empty()) 
     742        break; 
     743       
     744      entp = extp; 
     745      mint = maxt; 
     746      if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f) 
     747        break; 
     748       
     749      RayTraversalData &s  = tStack.top(); 
     750      node = s.mNode; 
     751      extp = s.mExitPoint; 
     752      maxt = s.mMaxT; 
     753      tStack.pop(); 
     754    } 
    745755  } 
    746756  return hits; 
    … …  
    748758 
    749759int KdTree::CastLineSegment(const Vector3 &origin, 
    750                                                         const Vector3 &termination, 
    751                                                         ViewCellContainer &viewcells) 
    752 { 
    753         int hits = 0; 
    754  
    755         float mint = 0.0f, maxt = 1.0f; 
    756         const Vector3 dir = termination - origin; 
    757  
    758         stack<RayTraversalData> tStack; 
    759  
    760         Intersectable::NewMail(); 
    761  
    762         //maxt += Limits::Threshold; 
    763  
    764         Vector3 entp = origin; 
    765         Vector3 extp = termination; 
    766  
    767         KdNode *node = mRoot; 
    768         KdNode *farChild; 
    769  
    770         float position; 
    771         int axis; 
    772  
    773         while (1) 
     760                            const Vector3 &termination, 
     761                            ViewCellContainer &viewcells) 
     762{ 
     763  int hits = 0; 
     764 
     765  float mint = 0.0f, maxt = 1.0f; 
     766  const Vector3 dir = termination - origin; 
     767   
     768  stack<RayTraversalData> tStack; 
     769   
     770  Intersectable::NewMail(); 
     771   
     772  //maxt += Limits::Threshold; 
     773   
     774  Vector3 entp = origin; 
     775  Vector3 extp = termination; 
     776   
     777  KdNode *node = mRoot; 
     778  KdNode *farChild; 
     779   
     780  float position; 
     781  int axis; 
     782 
     783  while (1) 
     784  { 
     785    if (!node->IsLeaf()) 
     786    { 
     787      KdInterior *in = static_cast<KdInterior *>(node); 
     788      position = in->mPosition; 
     789      axis = in->mAxis; 
     790       
     791      if (entp[axis] <= position) 
     792      { 
     793        if (extp[axis] <= position) 
    774794        { 
    775                 if (!node->IsLeaf()) 
    776                 { 
    777                         KdInterior *in = static_cast<KdInterior *>(node); 
    778                         position = in->mPosition; 
    779                         axis = in->mAxis; 
    780  
    781                         if (entp[axis] <= position) 
    782                         { 
    783                                 if (extp[axis] <= position) 
    784                                 { 
    785                                         node = in->mBack; 
    786                                         // cases N1,N2,N3,P5,Z2,Z3 
    787                                         continue; 
    788                                 }  
    789                                 else 
    790                                 { 
    791                                         // case N4 
    792                                         node = in->mBack; 
    793                                         farChild = in->mFront; 
    794                                 } 
    795                         } 
    796                         else 
    797                         { 
    798                                 if (position <= extp[axis]) 
    799                                 { 
    800                                         node = in->mFront; 
    801                                         // cases P1,P2,P3,N5,Z1 
    802                                         continue; 
    803                                 } 
    804                                 else 
    805                                 { 
    806                                         node = in->mFront; 
    807                                         farChild = in->mBack; 
    808                                         // case P4 
    809                                 } 
    810                         } 
    811  
    812                         // $$ modification 3.5.2004 - hints from Kamil Ghais 
    813                         // case N4 or P4 
    814                         float tdist = (position - origin[axis]) / dir[axis]; 
    815                         //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO 
    816                         extp = origin + dir * tdist; 
    817                         maxt = tdist; 
    818                 } 
    819                 else 
    820                 { 
    821                         // compute intersection with all objects in this leaf 
    822                         KdLeaf *leaf = static_cast<KdLeaf *>(node); 
    823  
    824                         // add view cell to intersections 
    825                         ViewCell *vc = leaf->mViewCell; 
    826  
    827                         if (!vc->Mailed()) 
    828                         { 
    829                                 vc->Mail(); 
    830                                 viewcells.push_back(vc); 
    831                                 ++ hits; 
    832                         } 
    833  
    834                         // get the next node from the stack 
    835                         if (tStack.empty()) 
    836                                 break; 
    837  
    838                         entp = extp; 
    839                         mint = maxt; 
    840                          
    841                         RayTraversalData &s  = tStack.top(); 
    842                         node = s.mNode; 
    843                         extp = s.mExitPoint; 
    844                         maxt = s.mMaxT; 
    845                         tStack.pop(); 
    846                 } 
    847         } 
    848  
    849         return hits; 
     795          node = in->mBack; 
     796          // cases N1,N2,N3,P5,Z2,Z3 
     797          continue; 
     798        }  
     799        else 
     800        { 
     801          // case N4 
     802          node = in->mBack; 
     803          farChild = in->mFront; 
     804        } 
     805      } 
     806      else 
     807      { 
     808        if (position <= extp[axis]) 
     809        { 
     810          node = in->mFront; 
     811          // cases P1,P2,P3,N5,Z1 
     812          continue; 
     813        } 
     814        else 
     815        { 
     816          node = in->mFront; 
     817          farChild = in->mBack; 
     818          // case P4 
     819        } 
     820      } 
     821       
     822      // $$ modification 3.5.2004 - hints from Kamil Ghais 
     823      // case N4 or P4 
     824      float tdist = (position - origin[axis]) / dir[axis]; 
     825      //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO 
     826      extp = origin + dir * tdist; 
     827      maxt = tdist; 
     828    } 
     829    else 
     830    { 
     831      // compute intersection with all objects in this leaf 
     832      KdLeaf *leaf = static_cast<KdLeaf *>(node); 
     833       
     834      // add view cell to intersections 
     835      ViewCell *vc = leaf->mViewCell; 
     836       
     837      if (!vc->Mailed()) 
     838      { 
     839        vc->Mail(); 
     840        viewcells.push_back(vc); 
     841        ++ hits; 
     842      } 
     843       
     844      // get the next node from the stack 
     845      if (tStack.empty()) 
     846        break; 
     847       
     848      entp = extp; 
     849      mint = maxt; 
     850       
     851      RayTraversalData &s  = tStack.top(); 
     852      node = s.mNode; 
     853      extp = s.mExitPoint; 
     854      maxt = s.mMaxT; 
     855      tStack.pop(); 
     856    } 
     857  } 
     858  return hits; 
    850859} 
    851860 
    852861void 
    853862KdTree::CollectKdObjects(const AxisAlignedBox3 &box, 
    854                                                 ObjectContainer &objects 
    855                                                  ) 
     863                        ObjectContainer &objects 
     864                        ) 
    856865{ 
    857866  stack<KdNode *> nodeStack; 
    … …  
    862871    KdNode *node = nodeStack.top(); 
    863872    nodeStack.pop(); 
    864         if (node->IsLeaf() || node->mPvsTermination == 1)  { 
    865           Intersectable *object = GetOrCreateKdIntersectable(node); 
    866           if (!node->Mailed()) { 
    867                 node->Mail(); 
    868                 objects.push_back(object); 
    869           } 
    870         } else { 
     873    if (node->IsLeaf() || node->mPvsTermination == 1)  { 
     874      Intersectable *object = GetOrCreateKdIntersectable(node); 
     875      if (!node->Mailed()) { 
     876        node->Mail(); 
     877        objects.push_back(object); 
     878      } 
     879    } 
     880    else { 
    871881      KdInterior *interior = (KdInterior *)node; 
    872882           
    873           if ( box.Max()[interior->mAxis] > interior->mPosition ) 
    874                 nodeStack.push(interior->mFront); 
    875            
    876           if (box.Min()[interior->mAxis] < interior->mPosition) 
    877                 nodeStack.push(interior->mBack); 
    878     } 
    879   } 
     883      if ( box.Max()[interior->mAxis] > interior->mPosition ) 
     884        nodeStack.push(interior->mFront); 
     885       
     886      if (box.Min()[interior->mAxis] < interior->mPosition) 
     887        nodeStack.push(interior->mBack); 
     888    } 
     889  } // while 
    880890} 
    881891 
    882892void 
    883893KdTree::CollectObjects(const AxisAlignedBox3 &box, 
    884                                            ObjectContainer &objects) 
     894                       ObjectContainer &objects) 
    885895{ 
    886896  stack<KdNode *> nodeStack; 
    … …  
    894904      KdLeaf *leaf = (KdLeaf *)node; 
    895905      for (int j=0; j < leaf->mObjects.size(); j++) { 
    896                 Intersectable *object = leaf->mObjects[j]; 
    897                 if (!object->Mailed() && Overlap(box, object->GetBox())) { 
    898                   object->Mail(); 
    899                   objects.push_back(object); 
    900                 } 
     906        Intersectable *object = leaf->mObjects[j]; 
     907        if (!object->Mailed() && Overlap(box, object->GetBox())) { 
     908          object->Mail(); 
     909          objects.push_back(object); 
     910        } 
    901911      } 
    902912    } else { 
    903913      KdInterior *interior = (KdInterior *)node; 
    904914 
    905           if ( box.Max()[interior->mAxis] > interior->mPosition ) 
    906                 nodeStack.push(interior->mFront); 
    907   
    908           if (box.Min()[interior->mAxis] < interior->mPosition) 
    909                 nodeStack.push(interior->mBack); 
     915      if ( box.Max()[interior->mAxis] > interior->mPosition ) 
     916        nodeStack.push(interior->mFront); 
     917       
     918      if (box.Min()[interior->mAxis] < interior->mPosition) 
     919        nodeStack.push(interior->mBack); 
    910920    } 
    911921  } 
    … …  
    925935      KdLeaf *leaf = (KdLeaf *)node; 
    926936      for (int j=0; j < leaf->mObjects.size(); j++) { 
    927                                 Intersectable *object = leaf->mObjects[j]; 
    928                                 if (!object->Mailed()) { 
    929                                         object->Mail(); 
    930                                         objects.push_back(object); 
    931                                 } 
     937        Intersectable *object = leaf->mObjects[j]; 
     938        if (!object->Mailed()) { 
     939          object->Mail(); 
     940          objects.push_back(object); 
     941        } 
    932942      } 
    933943    } else { 
    … …  
    942952KdNode * 
    943953KdTree::FindRandomNeighbor(KdNode *n, 
    944                                                    bool onlyUnmailed 
    945                                                    ) 
     954                           bool onlyUnmailed 
     955                           ) 
    946956{ 
    947957  stack<KdNode *> nodeStack; 
    … …  
    9971007      if ( node != n && (!onlyUnmailed || !node->Mailed()) )  
    9981008        neighbors.push_back(node); 
    999     } else { 
     1009    } 
     1010    else { 
    10001011      KdInterior *interior = (KdInterior *)node; 
    10011012      if (interior->mPosition > box.Max(interior->mAxis)) 
    1002                                 nodeStack.push(interior->mBack); 
    1003       else 
    1004                                 if (interior->mPosition < box.Min(interior->mAxis)) 
    1005                                         nodeStack.push(interior->mFront); 
    1006                                 else { 
    1007                                         // random decision 
    1008                                         nodeStack.push(interior->mBack); 
    1009                                         nodeStack.push(interior->mFront); 
    1010                                 } 
     1013        nodeStack.push(interior->mBack); 
     1014      else { 
     1015        if (interior->mPosition < box.Min(interior->mAxis)) 
     1016          nodeStack.push(interior->mFront); 
     1017        else { 
     1018          // random decision 
     1019          nodeStack.push(interior->mBack); 
     1020          nodeStack.push(interior->mFront); 
     1021        } 
     1022      } 
    10111023    } 
    10121024  } 
    … …  
    11811193void KdTree::ExportBinLeaf(OUT_STREAM &stream, KdLeaf *leaf) 
    11821194{ 
    1183         ObjectContainer::const_iterator it, it_end = leaf->mObjects.end(); 
     1195  ObjectContainer::const_iterator it, it_end = leaf->mObjects.end(); 
     1196   
     1197  int type = TYPE_LEAF; 
     1198  int size = (int)leaf->mObjects.size(); 
     1199   
     1200  stream.write(reinterpret_cast<char *>(&type), sizeof(int)); 
     1201  stream.write(reinterpret_cast<char *>(&size), sizeof(int)); 
     1202   
     1203  for (it = leaf->mObjects.begin(); it != it_end; ++ it) 
     1204    {    
     1205      Intersectable *obj = *it; 
     1206      int id = obj->mId;                 
     1207       
     1208      //stream.write(reinterpret_cast<char *>(&origin), sizeof(Vector3)); 
     1209      stream.write(reinterpret_cast<char *>(&id), sizeof(int)); 
     1210    } 
     1211} 
     1212 
     1213 
     1214KdLeaf *KdTree::ImportBinLeaf(IN_STREAM &stream,  
     1215                              KdInterior *parent, 
     1216                              const ObjectContainer &objects) 
     1217{ 
     1218  int leafId = TYPE_LEAF; 
     1219  int objId = leafId; 
     1220  int size; 
     1221   
     1222  stream.read(reinterpret_cast<char *>(&size), sizeof(int)); 
     1223  KdLeaf *leaf = new KdLeaf(parent, size); 
     1224 
     1225  MeshInstance dummyInst(NULL); 
    11841226         
    1185         int type = TYPE_LEAF; 
    1186         int size = (int)leaf->mObjects.size(); 
    1187  
    1188         stream.write(reinterpret_cast<char *>(&type), sizeof(int)); 
    1189         stream.write(reinterpret_cast<char *>(&size), sizeof(int)); 
    1190  
    1191         for (it = leaf->mObjects.begin(); it != it_end; ++ it) 
    1192         {        
    1193                 Intersectable *obj = *it; 
    1194                 int id = obj->mId;               
    1195          
    1196                 //stream.write(reinterpret_cast<char *>(&origin), sizeof(Vector3)); 
    1197                 stream.write(reinterpret_cast<char *>(&id), sizeof(int)); 
    1198     } 
    1199 } 
    1200  
    1201  
    1202 KdLeaf *KdTree::ImportBinLeaf(IN_STREAM &stream,  
    1203                                                           KdInterior *parent, 
    1204                                                           const ObjectContainer &objects) 
    1205 { 
    1206         int leafId = TYPE_LEAF; 
    1207         int objId = leafId; 
    1208         int size; 
    1209  
    1210         stream.read(reinterpret_cast<char *>(&size), sizeof(int)); 
    1211         KdLeaf *leaf = new KdLeaf(parent, size); 
    1212  
    1213         MeshInstance dummyInst(NULL); 
    1214          
    1215         // read object ids 
    1216         // note: this can also be done geometrically 
    1217         for (int i = 0; i < size; ++ i) 
    1218         {        
    1219                 stream.read(reinterpret_cast<char *>(&objId), sizeof(int)); 
    1220                 dummyInst.SetId(objId); 
    1221  
    1222                 ObjectContainer::const_iterator oit = 
    1223                         lower_bound(objects.begin(), objects.end(), (Intersectable *)&dummyInst, ilt); 
    1224                                                                  
    1225                 if ((oit != objects.end()) && ((*oit)->GetId() == objId)) 
    1226                         leaf->mObjects.push_back(*oit); 
    1227                 else 
    1228                         Debug << "error: object with id " << objId << " does not exist" << endl; 
    1229         } 
    1230  
    1231         return leaf; 
     1227  // read object ids 
     1228  // note: this can also be done geometrically 
     1229  for (int i = 0; i < size; ++ i) 
     1230    {    
     1231      stream.read(reinterpret_cast<char *>(&objId), sizeof(int)); 
     1232      dummyInst.SetId(objId); 
     1233       
     1234      ObjectContainer::const_iterator oit = 
     1235        lower_bound(objects.begin(), objects.end(), (Intersectable *)&dummyInst, ilt); 
     1236       
     1237      if ((oit != objects.end()) && ((*oit)->GetId() == objId)) 
     1238        leaf->mObjects.push_back(*oit); 
     1239      else 
     1240        Debug << "error: object with id " << objId << " does not exist" << endl; 
     1241    } 
     1242   
     1243  return leaf; 
    12321244} 
    12331245 
    … …  
    13191331bool KdTree::ImportBinTree(const string &filename, ObjectContainer &objects) 
    13201332{ 
    1321         // export binary version of mesh 
    1322         queue<TraversalData> tStack; 
    1323         IN_STREAM stream(filename.c_str(), IN_BIN_MODE); 
    1324  
    1325         if (!stream.is_open()) return false; 
    1326  
    1327         // sort objects by their id 
    1328 //      if (!is_sorted(objects.begin(), objects.end(), ilt)) 
    1329                 sort(objects.begin(), objects.end(), ilt); 
    1330  
    1331         mBox.Initialize(); 
    1332         ObjectContainer::const_iterator oit, oit_end = objects.end(); 
    1333  
    1334         /////////////////////////// 
    1335         //-- compute bounding box of object space 
    1336  
    1337     for (oit = objects.begin(); oit != oit_end; ++ oit) 
    1338         { 
    1339                 const AxisAlignedBox3 box = (*oit)->GetBox(); 
    1340                 mBox.Include(box); 
    1341         } 
    1342  
    1343         // hack: we make a new root 
    1344         DEL_PTR(mRoot); 
    1345    
    1346         mRoot = ImportNextNode(stream, NULL, objects); 
    1347  
    1348         tStack.push(TraversalData(mRoot, mBox, 0)); 
    1349         mStat.Reset(); 
    1350         mStat.nodes = 1; 
    1351  
    1352         while(!tStack.empty()) 
    1353         { 
    1354                 TraversalData tData = tStack.front(); 
    1355                 tStack.pop(); 
    1356  
    1357                 KdNode *node = tData.mNode; 
    1358  
    1359                 if (!node->IsLeaf()) 
    1360                 { 
    1361                         mStat.nodes += 2; 
    1362  
    1363                         //Debug << "i" ; 
    1364                         KdInterior *interior = static_cast<KdInterior *>(node); 
    1365                         interior->mBox = tData.mBox; 
    1366  
    1367             KdNode *front = ImportNextNode(stream, interior, objects); 
    1368                         KdNode *back = ImportNextNode(stream, interior, objects); 
    1369          
    1370                         interior->SetupChildLinks(back, front); 
    1371  
    1372                         ++ mStat.splits[interior->mAxis]; 
    1373  
    1374                         // compute new bounding box 
    1375                         AxisAlignedBox3 frontBox, backBox; 
    1376                          
    1377                         tData.mBox.Split(interior->mAxis,  
    1378                                                         interior->mPosition,  
    1379                                                         frontBox,  
    1380                                                         backBox); 
    1381  
    1382                         tStack.push(TraversalData(front, frontBox, tData.mDepth + 1));                   
    1383                         tStack.push(TraversalData(back, backBox, tData.mDepth + 1)); 
    1384                 } 
    1385                 else 
    1386                 { 
    1387                         EvaluateLeafStats(tData); 
    1388                         //cout << "l"; 
    1389                 } 
    1390         } 
    1391  
    1392         float area = GetBox().SurfaceArea()*mKdPvsArea; 
    1393          
    1394         SetPvsTerminationNodes(area); 
    1395  
    1396         Debug << mStat << endl; 
    1397  
    1398         return true; 
     1333  // export binary version of mesh 
     1334  queue<TraversalData> tStack; 
     1335  IN_STREAM stream(filename.c_str(), IN_BIN_MODE); 
     1336   
     1337  if (!stream.is_open()) return false; 
     1338   
     1339  // sort objects by their id 
     1340  //    if (!is_sorted(objects.begin(), objects.end(), ilt)) 
     1341  sort(objects.begin(), objects.end(), ilt); 
     1342   
     1343  mBox.Initialize(); 
     1344  ObjectContainer::const_iterator oit, oit_end = objects.end(); 
     1345   
     1346  /////////////////////////// 
     1347  //-- compute bounding box of object space 
     1348   
     1349  for (oit = objects.begin(); oit != oit_end; ++ oit) 
     1350  { 
     1351    const AxisAlignedBox3 box = (*oit)->GetBox(); 
     1352    mBox.Include(box); 
     1353  } 
     1354   
     1355  // hack: we make a new root 
     1356  DEL_PTR(mRoot); 
     1357   
     1358  mRoot = ImportNextNode(stream, NULL, objects); 
     1359   
     1360  tStack.push(TraversalData(mRoot, mBox, 0)); 
     1361  mStat.Reset(); 
     1362  mStat.nodes = 1; 
     1363   
     1364  while(!tStack.empty()) 
     1365  { 
     1366    TraversalData tData = tStack.front(); 
     1367    tStack.pop(); 
     1368     
     1369    KdNode *node = tData.mNode; 
     1370     
     1371    if (!node->IsLeaf()) 
     1372    { 
     1373      mStat.nodes += 2; 
     1374       
     1375      //Debug << "i" ; 
     1376      KdInterior *interior = static_cast<KdInterior *>(node); 
     1377      interior->mBox = tData.mBox; 
     1378       
     1379      KdNode *front = ImportNextNode(stream, interior, objects); 
     1380      KdNode *back = ImportNextNode(stream, interior, objects); 
     1381       
     1382      interior->SetupChildLinks(back, front); 
     1383       
     1384      ++ mStat.splits[interior->mAxis]; 
     1385       
     1386      // compute new bounding box 
     1387      AxisAlignedBox3 frontBox, backBox; 
     1388       
     1389      tData.mBox.Split(interior->mAxis,  
     1390                      interior->mPosition,  
     1391                      frontBox,  
     1392                      backBox); 
     1393       
     1394      tStack.push(TraversalData(front, frontBox, tData.mDepth + 1));                     
     1395      tStack.push(TraversalData(back, backBox, tData.mDepth + 1)); 
     1396    } 
     1397    else 
     1398    { 
     1399      EvaluateLeafStats(tData); 
     1400      //cout << "l"; 
     1401    } 
     1402  } 
     1403 
     1404  float area = GetBox().SurfaceArea()*mKdPvsArea; 
     1405   
     1406  SetPvsTerminationNodes(area); 
     1407   
     1408  Debug << mStat << endl; 
     1409   
     1410  return true; 
    13991411} 
    14001412 
    … …  
    14031415KdTree::GetOrCreateKdIntersectable(KdNode *node) 
    14041416{ 
    1405         if (node == NULL) 
    1406                 return NULL; 
     1417  if (node == NULL) 
     1418    return NULL; 
    14071419 
    14081420        if (node->mIntersectable == NULL)  
    … …  
    14151427                mKdIntersectables.push_back(kdObj); 
    14161428                kdObj->SetId(id); 
    1417  
    14181429#ifdef USE_BIT_PVS 
    1419                 // hack: for kd pvs the kd intersecables are the pvs objects 
    1420                 ObjectPvsIterator::sObjects.push_back(kdObj); 
     1430    // hack: for kd pvs the kd intersecables are the pvs objects 
     1431    ObjectPvsIterator::sObjects.push_back(kdObj); 
    14211432#endif 
    1422         } 
    1423  
    1424         return node->mIntersectable; 
     1433  } 
     1434 
     1435  return node->mIntersectable; 
    14251436} 
    14261437 
    14271438 
    14281439void 
    1429 KdTree::SetPvsTerminationNodes( 
    1430                                                            const float maxArea) 
     1440KdTree::SetPvsTerminationNodes(const float maxArea) 
    14311441{ 
    14321442  stack<KdNode *> nodeStack; 
    … …  
    14401450  while (!nodeStack.empty()) { 
    14411451    KdNode *node = nodeStack.top(); 
    1442         nodeStack.pop(); 
    1443  
    1444         node->mPvsTermination = 0; 
    1445         if (node->IsLeaf() || (GetSurfaceArea(node) <= maxArea) ) { 
    1446           area += GetSurfaceArea(node); 
    1447           radius += GetBox(node).Radius(); 
    1448           nodes++; 
    1449           node->mPvsTermination = 1; 
    1450           // create dummy kd intersectable 
    1451           Intersectable *object = GetOrCreateKdIntersectable(node); 
    1452         } else { 
    1453           KdInterior *interior = (KdInterior *)node; 
    1454           nodeStack.push(interior->mFront); 
    1455           nodeStack.push(interior->mBack); 
    1456     } 
    1457   } 
    1458  
     1452    nodeStack.pop(); 
     1453 
     1454    node->mPvsTermination = 0; 
     1455    if (node->IsLeaf() || (GetSurfaceArea(node) <= maxArea) ) { 
     1456      area += GetSurfaceArea(node); 
     1457      radius += GetBox(node).Radius(); 
     1458      nodes++; 
     1459      node->mPvsTermination = 1; 
     1460      // create dummy kd intersectable 
     1461      Intersectable *object = GetOrCreateKdIntersectable(node); 
     1462    } else { 
     1463      KdInterior *interior = (KdInterior *)node; 
     1464      nodeStack.push(interior->mFront); 
     1465      nodeStack.push(interior->mBack); 
     1466    } 
     1467  } 
     1468   
    14591469  if (nodes) { 
    1460         area /= nodes; 
    1461         radius /= nodes; 
    1462         cout<<"Number of nodes for storing in the PVS = "<<nodes<<endl; 
    1463         cout<<"Average rel. node area = "<<area/GetSurfaceArea(mRoot)<<endl; 
    1464         cout<<"Average rel. node radius = "<<radius/GetBox(mRoot).Radius()<<endl; 
    1465         cout<<"Avg node radius = "<<radius<<endl; 
     1470    area /= nodes; 
     1471    radius /= nodes; 
     1472    cout<<"Number of nodes for storing in the PVS = "<<nodes<<endl; 
     1473    cout<<"Average rel. node area = "<<area/GetSurfaceArea(mRoot)<<endl; 
     1474    cout<<"Average rel. node radius = "<<radius/GetBox(mRoot).Radius()<<endl; 
     1475    cout<<"Avg node radius = "<<radius<<endl; 
    14661476  } 
    14671477   
    … …  
    14741484   
    14751485  while (node->mPvsTermination == 0 ) { 
    1476         KdInterior *inter = (KdInterior *)node; 
    1477         if (point[inter->mAxis] < inter->mPosition) 
    1478           node = inter->mBack; 
    1479         else 
    1480           node = inter->mFront; 
     1486    KdInterior *inter = (KdInterior *)node; 
     1487    if (point[inter->mAxis] < inter->mPosition) 
     1488      node = inter->mBack; 
     1489    else 
     1490      node = inter->mFront; 
    14811491  } 
    14821492   
    … …  
    14911501   
    14921502  while (!node->IsLeaf() && (GetSurfaceArea(node) > maxArea) ) { 
    1493         KdInterior *inter = (KdInterior *)node; 
    1494         if (point[inter->mAxis] < inter->mPosition) 
    1495           node = inter->mBack; 
    1496         else 
    1497           node = inter->mFront; 
     1503    KdInterior *inter = (KdInterior *)node; 
     1504    if (point[inter->mAxis] < inter->mPosition) 
     1505      node = inter->mBack; 
     1506    else 
     1507      node = inter->mFront; 
    14981508  } 
    14991509   
    … …  
    15031513 
    15041514void KdTree::GetBoxIntersections(const AxisAlignedBox3 &box, 
    1505                                                                  vector<KdLeaf *> &leaves) 
    1506 { 
    1507         stack<KdNode *> tStack; 
    1508  
    1509         tStack.push(mRoot); 
    1510  
    1511         while (!tStack.empty()) 
     1515                                 vector<KdLeaf *> &leaves) 
     1516{ 
     1517  stack<KdNode *> tStack; 
     1518   
     1519  tStack.push(mRoot); 
     1520   
     1521  while (!tStack.empty()) 
     1522    { 
     1523      KdNode *node = tStack.top(); 
     1524      tStack.pop(); 
     1525       
     1526      if (node->IsLeaf()) 
    15121527        { 
    1513                 KdNode *node = tStack.top(); 
    1514                 tStack.pop(); 
    1515                  
    1516                 if (node->IsLeaf()) 
    1517                 { 
    1518                         leaves.push_back(static_cast<KdLeaf *>(node)); 
    1519                 } 
    1520                 else // interior 
    1521                 { 
    1522                         KdInterior *interior = static_cast<KdInterior *>(node); 
    1523  
    1524                         if (box.Max(interior->mAxis) >= interior->mPosition) 
    1525                         { 
    1526                                 tStack.push(interior->mFront); 
    1527                         } 
    1528  
    1529                         if (box.Min(interior->mAxis) < interior->mPosition) 
    1530                         { 
    1531                                 tStack.push(interior->mBack); 
    1532                         } 
    1533                 } 
    1534         } 
    1535 } 
    1536  
    1537  
    1538  
    1539 } 
     1528          leaves.push_back(static_cast<KdLeaf *>(node)); 
     1529        } 
     1530      else // interior 
     1531        { 
     1532          KdInterior *interior = static_cast<KdInterior *>(node); 
     1533           
     1534          if (box.Max(interior->mAxis) >= interior->mPosition) 
     1535            { 
     1536              tStack.push(interior->mFront); 
     1537            } 
     1538           
     1539          if (box.Min(interior->mAxis) < interior->mPosition) 
     1540            { 
     1541              tStack.push(interior->mBack); 
     1542            } 
     1543        } 
     1544    } 
     1545} 
     1546 
     1547 
     1548 
     1549} 
Note: See TracChangeset for help on using the changeset viewer.