Advertisement
Guest User

Untitled

a guest
Aug 3rd, 2014
333
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. // Traverse the tree left node first
  2. // Bitfield, a bit set at position n means that the traversal at this level has to continue with its sibling node
  3. uint levelindex = 0;
  4. // Start with root
  5. int node = 0;
  6. bool setlca = true;
  7.  
  8. do
  9. {
  10.     // Process leafnodes
  11.     if (node >= LightCount) ++count;
  12.     //if (texelFetch (Light_BVHNodes, node).r >= LightCount) ++count;
  13.  
  14.     // Test child nodes
  15.     else
  16.     {
  17.         ivec2 children = ivec2 (texelFetch (Light_BVHChildrenNodes, node).rg);
  18.         bvec2 overlap = bvec2 (IsOverlapping (children.x, depths, tilerect), IsOverlapping (children.y, depths, tilerect));
  19.  
  20.         if (any (overlap))
  21.         {
  22.             // Shift levelindex because we descended on level in the tree
  23.             levelindex <<= 1;
  24.  
  25.             // If both children need to be processed set the rightmost bit of levelindex to 1
  26.             if (!all (overlap)) ++levelindex;
  27.             else if (setlca)
  28.             {
  29.                 lca = node;
  30.                 setlca = false;
  31.             }
  32.  
  33.             // Continue with the left child if posible
  34.             node = (overlap.x) ? children.x : children.y;
  35.             continue;
  36.         }
  37.     }
  38.  
  39.     // Find the first ancestor, that has a sibling that needs to be processed
  40.     ++levelindex;
  41.     while ((levelindex & 1) == 0)
  42.     {
  43.         // Continue with the parent
  44.         node = (node >= LightCount) ? int (texelFetch (Light_BVHParentLeafs, node - LightCount).r) : int (texelFetch (Light_BVHParentNodes, node).r);
  45.         levelindex >>= 1;
  46.     }
  47.  
  48.     // Continue with the sibling of the current node
  49.     if (node != 0)
  50.     {
  51.         node = (node >= LightCount) ? int (texelFetch (Light_BVHParentLeafs, node - LightCount).r) : int (texelFetch (Light_BVHParentNodes, node).r);
  52.         node = int (texelFetch (Light_BVHChildrenNodes, node).g);
  53.     }
  54. } while (node != 0);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement