API tools faq
paste
Guest User

Quadtree Terrain Code

a guest
Aug 17th, 2013
382
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.16 KB | None | 0 0
raw download clone embed print report
  1. #include "Quadtree.hpp"
  2. #include "Object.hpp"
  3. #include <thread>
  4. #include <stdio.h>
  5. #include <string>
  6. #include <future>
  7. #include <SFML\System.hpp>
  8.  
  9. sf::Mutex mutex;
  10. Quadtree::Quadtree() :
  11. left( 0 ),
  12. right( 0 ),
  13. top( 0 ),
  14. down( 0 ),
  15. numObjectsToGrow( 1 ),
  16. nodes( 0 ),
  17. isLeaf( true ),
  18. isReady(false)
  19. {
  20.  
  21. }
  22.  
  23. Quadtree::Quadtree( double _left, double _right, double _top, double _down, unsigned int _numObjectsToGrow ) :
  24. left( _left ),
  25. right( _right ),
  26. top( _top ),
  27. down( _down ),
  28. numObjectsToGrow( _numObjectsToGrow ),
  29. nodes( 0 ),
  30. isLeaf( true ),
  31. isReady(false)
  32. {
  33.  
  34.  
  35.  
  36.  
  37. }
  38.  
  39. Quadtree::~Quadtree()
  40. {
  41.     if ( !isLeaf )
  42.         delete [] nodes;
  43. }
  44.  
  45. void Quadtree::Setup()
  46. {
  47.     center = glm::vec3((left+right)/2, 1, (top+down)/2);
  48.     float iValue;
  49.     float jValue;
  50. //  ID = engine->getGraphicsManager()->getId();
  51.     std::cout << "Setup: " << ID  << std::endl;
  52.     size = 400;
  53.     w = 1 ;
  54.     h = 1 ;
  55.     float ID2 = ID *0.1;
  56.     ID2 = 0;
  57.     for(int i = 0; i < w; i++)
  58.       {
  59.           for(int j = 0; j < h; j++)
  60.           {
  61.               iValue = i;
  62.               jValue = j;
  63.               vertices.push_back(glm::vec3(0.0+iValue, 1.0+ID2, 0.0+jValue));
  64.               vertices.push_back(glm::vec3(0.0+iValue, 1.0+ID2, 1.0+jValue));
  65.               vertices.push_back(glm::vec3(1.0+iValue, 1.0+ID2, 0.0+jValue));
  66.  
  67.               vertices.push_back(glm::vec3(1.0+iValue, 1.0+ID2, 1.0+jValue));
  68.               vertices.push_back(glm::vec3(1.0+iValue, 1.0+ID2, 0.0+jValue));
  69.               vertices.push_back(glm::vec3(0.0+iValue, 1.0+ID2, 1.0+jValue));
  70.           }
  71.       }
  72.  
  73.     for(int i = 0; i < vertices.size(); i++)
  74.     {
  75.         uvs.push_back(glm::vec2(vertices[i].x, vertices[i].z));
  76.         normals.push_back(vertices[i]);
  77.         glm::vec3 oldVec = vertices[i];
  78.     //  glm::vec3 newVec = glm::normalize(oldVec);
  79.         glm::vec3 newVec = oldVec;
  80.     //  vertices[i] = newVec * glm::vec3(size, size, size);
  81.         //vertices[i] = newVec + (glm::vec3(center.x - (100 * (1/(pow(level-1,2)))), 1, center.z - (100 * (1/(pow(level-1,2)))) ));
  82.         //glm::vec3 newVec = oldVec * glm::vec3(size*(pow(0.5, level)), size, size*(pow(0.5, level)));
  83.         vertices[i] = newVec + (glm::vec3(center.x - (100 * (1/(pow(level-1,2)))), 1, center.z - (100 * (1/(pow(level-1,2)))) ));
  84.     }
  85.  
  86.     for(int i = 0; i < vertices.size(); i+=3)
  87.     {
  88.  
  89.           // get the three vertices that make the faces
  90.           glm::vec3 p1 = vertices[i+0];
  91.           glm::vec3 p2 = vertices[i+1];
  92.           glm::vec3 p3 = vertices[i+2];
  93.  
  94.           glm::vec3 v1 = p2 - p1;
  95.           glm::vec3 v2 = p3 - p1;
  96.           glm::vec3 normal = glm::cross( v1,v2 );
  97.  
  98.           normal = glm::normalize(normal);
  99.  
  100.           normals[i+0] = normal;
  101.           normals[i+1] = normal;
  102.           normals[i+2] = normal;
  103.        
  104.     }
  105.  
  106.      std::cout << "Terrain has: " << vertices.size() * 3 << " vertices!" << std::endl;
  107.      
  108.     glGenBuffers(1, &vertexbuffer);
  109.     glGenBuffers(1, &uvbuffer);
  110.     glGenBuffers(1, &normalbuffer);
  111.  
  112.     glBindBuffer(GL_ARRAY_BUFFER, vertexbuffer);
  113.     glBufferData(GL_ARRAY_BUFFER, vertices.size() * sizeof(glm::vec3), &vertices[0], GL_STATIC_DRAW);
  114.  
  115.     glBindBuffer(GL_ARRAY_BUFFER, normalbuffer);
  116.     glBufferData(GL_ARRAY_BUFFER, normals.size() * sizeof(glm::vec3), &normals[0], GL_STATIC_DRAW);
  117.  
  118.     glBindBuffer(GL_ARRAY_BUFFER, uvbuffer);
  119.     glBufferData(GL_ARRAY_BUFFER, uvs.size() * sizeof(glm::vec2), &uvs[0], GL_STATIC_DRAW);
  120.  
  121.     level = 0;
  122. }
  123.  
  124. void Quadtree::Setup( int width, int height)
  125. {
  126.  
  127.   center = glm::vec3((left+right)/2, 1, (top+down)/2);
  128.   float prevIValue;
  129.   float prevJValue;
  130.   float iValue;
  131.   float jValue;
  132.  // size = 25;
  133. //  w = 160 ;
  134.  // h = 160 ;
  135.   size = 100;
  136.   w = 41 ;
  137.   h = 41 ;
  138. //  ID = engine->getGraphicsManager()->getId();
  139.   ID = 0;
  140.  
  141.   vertices.empty();
  142.     //std::cout << "Setup: " << ID  << std::endl;
  143.      for(int i = 0; i < w; i++)
  144.       {
  145.           for(int j = 0; j < h; j++)
  146.           {
  147.               iValue = i;
  148.               jValue = j;
  149.               //iValue = i * (pow(0.5, 2));
  150.              // jValue = j * (pow(0.5, 2));
  151.        
  152.  
  153. //            std::cout << "Level: " <<  level << std::endl;
  154.  
  155.               vertices.push_back(glm::vec3(0.0+iValue, 1.0+ID, 0.0+jValue)); //top left
  156.               vertices.push_back(glm::vec3(0.0+iValue, 1.0+ID, 1.0+jValue)); // bottom left
  157.               vertices.push_back(glm::vec3(1.0+iValue, 1.0+ID, 0.0+jValue)); // top right
  158.  
  159.               vertices.push_back(glm::vec3(1.0+iValue, 1.0+ID, 1.0+jValue));
  160.               vertices.push_back(glm::vec3(1.0+iValue, 1.0+ID, 0.0+jValue));
  161.               vertices.push_back(glm::vec3(0.0+iValue, 1.0+ID, 1.0+jValue));
  162.  
  163.           }
  164.       }
  165.  
  166.     for(int i = 0; i < vertices.size(); i++)
  167.     {
  168.        
  169.         uvs.push_back(glm::vec2(vertices[i].x, vertices[i].z));
  170.         normals.push_back(vertices[i]);
  171.         glm::vec3 oldVec = vertices[i];
  172.         //glm::vec3 newVec = glm::normalize(oldVec);
  173.         //glm::vec3 newVec = oldVec * glm::vec3(size*(pow(0.5, level)), size, size*(pow(0.5, level)));
  174.        
  175.         //newVec = newVec - glm::vec3(size*(pow(0.5, level)), size, size*(pow(0.5, level)));
  176.         /*
  177.         if(level != 1)
  178.         {
  179.             glm::vec3 translate = glm::vec3(50/(level-1), 0, 50/(level-1));
  180.             newVec = newVec - translate;
  181.         }else{
  182.             glm::vec3 translate = glm::vec3(50, 0, 50);
  183.             newVec = newVec - translate;
  184.         }
  185.         */
  186.         //glm::vec3 newVec = oldVec /  glm::vec3(2 ^ level, 1, 2 ^ level);  
  187.         glm::vec3 newVec = oldVec * glm::vec3(size*(pow(0.5001, level)), size, size*(pow(0.5001, level)));
  188.         vertices[i] = newVec + glm::vec3(left, 0, top); //+ (glm::vec3(center.x - (100 * (1/(pow(abs(level-1),2)))), 1, center.z - (100 * (1/(pow(abs(level-1),2)))) ));
  189.        
  190.            
  191.        
  192.         //std::cout << " X = " << (glm::vec3(center.x - (100 * (1/(pow(abs(level-1),2)))), 1, center.z - (100 * (1/(pow(abs(level-1),2)))) )).x << " Z = " << (glm::vec3(center.x - (100 * (1/(pow(abs(level-1),2)))), 1, center.z - (100 * (1/(pow(abs(level-1),2)))) )).z << std::endl;
  193.  
  194.     }
  195.          std::cout << normals.size() << std::endl;
  196.     for(int i = 0; i < vertices.size(); i+=3)
  197.     {
  198.  
  199.           // get the three vertices that make the faces
  200.           glm::vec3 p1 = vertices[i+0];
  201.           glm::vec3 p2 = vertices[i+1];
  202.           glm::vec3 p3 = vertices[i+2];
  203.  
  204.           glm::vec3 v1 = p2 - p1;
  205.           glm::vec3 v2 = p3 - p1;
  206.           glm::vec3 normal = glm::cross( v1,v2 );
  207.  
  208.           normal = glm::normalize(normal);
  209.  
  210.           normals[i+0] = normal;
  211.           normals[i+1] = normal;
  212.           normals[i+2] = normal;
  213.        
  214.     }
  215.  
  216.     // std::cout << "Terrain has: " << vertices.size() * 3 << " vertices!" << std::endl;
  217.  
  218.    
  219.    
  220.    
  221.     glGenBuffers(1, &vertexbuffer);
  222.     glGenBuffers(1, &uvbuffer);
  223.     glGenBuffers(1, &normalbuffer);
  224.  
  225.  
  226.     glBindBuffer(GL_ARRAY_BUFFER, vertexbuffer);
  227.     glBufferData(GL_ARRAY_BUFFER, vertices.size() * sizeof(glm::vec3), &vertices[0], GL_STATIC_DRAW);
  228.  
  229.     glBindBuffer(GL_ARRAY_BUFFER, normalbuffer);
  230.     glBufferData(GL_ARRAY_BUFFER, normals.size() * sizeof(glm::vec3), &normals[0], GL_STATIC_DRAW);
  231.  
  232.     glBindBuffer(GL_ARRAY_BUFFER, uvbuffer);
  233.     glBufferData(GL_ARRAY_BUFFER, uvs.size() * sizeof(glm::vec2), &uvs[0], GL_STATIC_DRAW);
  234.  
  235.     mutex.lock();
  236.     isReady = true;
  237.     mutex.unlock();
  238.     //isReady = true;
  239.    
  240.     }
  241.     int ia = 0;
  242. void Quadtree::Render()
  243. {
  244.         glBindBuffer(GL_ARRAY_BUFFER, vertexbuffer);
  245.         glBufferData(GL_ARRAY_BUFFER, vertices.size() * sizeof(glm::vec3), &vertices[0], GL_STATIC_DRAW);
  246.  
  247.         glBindBuffer(GL_ARRAY_BUFFER, normalbuffer);
  248.         glBufferData(GL_ARRAY_BUFFER, normals.size() * sizeof(glm::vec3), &normals[0], GL_STATIC_DRAW);
  249.  
  250.         glBindBuffer(GL_ARRAY_BUFFER, uvbuffer);
  251.         glBufferData(GL_ARRAY_BUFFER, uvs.size() * sizeof(glm::vec2), &uvs[0], GL_STATIC_DRAW);
  252.    
  253.     if(isLeaf) 
  254.     {
  255.        
  256.     //  std::cout << "Rendering: " << ID << std::endl;
  257.         //vertices
  258.        
  259.         glEnableVertexAttribArray(0);
  260.         glBindBuffer(GL_ARRAY_BUFFER, vertexbuffer);
  261.         glVertexAttribPointer(
  262.            0,                  
  263.            3,                  
  264.            GL_FLOAT,          
  265.            GL_FALSE,          
  266.            0,                  
  267.            (char*)0          
  268.         );
  269.          
  270.          //UVs
  271.          glEnableVertexAttribArray(1);
  272.          glBindBuffer(GL_ARRAY_BUFFER, uvbuffer);
  273.          glVertexAttribPointer(
  274.            1,                                // attribute
  275.            2,                                // size
  276.            GL_FLOAT,                         // type
  277.            GL_FALSE,                         // normalized?
  278.            0,                                // stride
  279.            (char*)0                          // array buffer offset
  280.          );
  281.      
  282.          //Normal
  283.          glEnableVertexAttribArray(2);
  284.          glBindBuffer(GL_ARRAY_BUFFER, normalbuffer);
  285.          glVertexAttribPointer(
  286.            2,                                // attribute
  287.            3,                                // size
  288.            GL_FLOAT,                         // type
  289.            GL_FALSE,                         // normalized?
  290.            0,                                // stride
  291.            (void*)0                          // array buffer offset
  292.          );
  293.      
  294.        
  295.         glDrawArrays(GL_TRIANGLES, 0, vertices.size() );
  296.    
  297.         glDisableVertexAttribArray(0);
  298.         glDisableVertexAttribArray(1);
  299.         glDisableVertexAttribArray(2);
  300.        
  301.     }else{
  302.         for ( int n = 0; n < NodeCount; ++n ) {
  303.                 nodes[n].Render();
  304.         }
  305.    
  306.     }
  307.    
  308.    
  309. }
  310.  
  311. void Quadtree::AddObject( Object *object )
  312. {
  313.    
  314.     if ( isLeaf ) {
  315.         objects.push_back( object );
  316.         bool reachedMaxObjects = ( objects.size() == numObjectsToGrow );
  317.         if ( reachedMaxObjects ) {
  318.            
  319.             if(level < 5)
  320.             {
  321.                 createLeaves();
  322.                 moveObjectsToLeaves();
  323.                 isLeaf = false;
  324.             }
  325.         }
  326.         return;
  327.     }
  328.     for ( int n = 0; n < NodeCount; ++n ) {
  329.         if ( nodes[n].contains( object ) ) {
  330.             nodes[n].AddObject( object );
  331.    
  332.             return;
  333.         }
  334.     }
  335.  
  336.     objects.push_back( object );
  337. }
  338.  
  339. void Quadtree::Clear()
  340. {
  341.     objects.clear();
  342.  
  343.     if ( !isLeaf ) {
  344.         for ( int n = 0; n < NodeCount; ++n ) {
  345.             nodes[n].Clear();
  346.         }
  347.     }
  348. }
  349.  
  350. vector<Object*> Quadtree::GetObjectsAt( double x, double y )
  351. {
  352.  
  353.     if ( isLeaf ) {
  354.         return objects;
  355.     }
  356.  
  357.     vector<Object*> returnedObjects;
  358.     vector<Object*> childObjects;
  359.  
  360.     if ( !objects.empty() )
  361.         returnedObjects.insert( returnedObjects.end(), objects.begin(), objects.end() );
  362.  
  363.     for ( int n = 0; n < NodeCount; ++n ) {
  364.         if ( nodes[n].contains( x, y ) ) {
  365.             childObjects = nodes[n].GetObjectsAt( x, y );
  366.             returnedObjects.insert( returnedObjects.end(), childObjects.begin(), childObjects.end() );
  367.             break;
  368.         }
  369.     }
  370.    
  371.     return returnedObjects;
  372. }
  373.  
  374. bool Quadtree::contains( Object *object )
  375. {
  376.     return  object->left > left &&
  377.         object->right < right &&
  378.         object->top > top &&
  379.         object->down < down;
  380. }
  381.  
  382. bool Quadtree::contains( double x, double y )
  383. {
  384.     return  ( x >= left && x <= right ) &&
  385.         ( y >= top && y <= down );
  386. }
  387.  
  388. void Quadtree::CheckDistance(glm::vec3 camera)
  389. {
  390.     if(!camera.null){
  391.         float xd = camera.x - center.x;
  392.         float yd = camera.y - center.y;
  393.         float zd = camera.z - center.z;
  394.         float distance = sqrt(xd*xd + yd*yd + zd*zd);
  395.         //std::cout << distance << std::endl;
  396.  
  397.        
  398.        
  399.         if(distance > 200)
  400.         {
  401.             if(!isLeaf)
  402.             {
  403.                 if(nodes != NULL)
  404.                 {
  405.                     if(level > 0)
  406.                     {
  407.                         deleteLeaves();
  408.                     }
  409.                 }
  410.             }
  411.         }
  412.    
  413.         if(distance < 100){
  414.             if(level < 5)
  415.             {
  416.             if(nodes == NULL){
  417.                     if(isLeaf)
  418.                     {
  419.                         //std::cout << "hello" << std::endl;
  420.                         createLeaves();
  421.                         moveObjectsToLeaves();
  422.                         isLeaf = false;
  423.                     }
  424.                 }
  425.             }
  426.         }
  427.        
  428.         /*
  429.         if(distance > 100){
  430.             if(!isLeaf)
  431.             {
  432.                 if(nodes != NULL)
  433.                 {
  434.                     if(level > 0)
  435.                     {
  436.                         deleteLeaves();
  437.                     }
  438.                 }
  439.             }
  440.         }
  441.         */
  442.         if(nodes != NULL)
  443.             {
  444.                 nodes[NW].CheckDistance(camera);   
  445.                 nodes[NE].CheckDistance(camera);   
  446.                 nodes[SW].CheckDistance(camera);   
  447.                 nodes[SE].CheckDistance(camera);
  448.             }
  449.        
  450.        
  451.    
  452.        
  453.        
  454.    
  455.        
  456.     }
  457. }
  458.  
  459. void Quadtree::createLeaves()
  460. {
  461.  
  462.     nodes = new Quadtree[4];
  463.     //std::cout << "left = " << left << " right = " << right << " top = " << top <<  "down = " << down << std::endl;
  464.     nodes[NW] = Quadtree( left, (left+right)/2, top, (top+down)/2, numObjectsToGrow );
  465.     nodes[NE] = Quadtree( (left+right)/2, right, top, (top+down)/2, numObjectsToGrow );
  466.     nodes[SW] = Quadtree( left, (left+right)/2, (top+down)/2, down, numObjectsToGrow );
  467.     nodes[SE] = Quadtree( (left+right)/2, right, (top+down)/2, down, numObjectsToGrow );
  468.  
  469.    
  470. /*  nodes[NW].center.z = center.z ;
  471.     nodes[NW].center.x = center.x ;
  472.  
  473.     nodes[NE].level = (level+1);
  474.     nodes[NE].center.z = center.z ;
  475.     nodes[NE].center.x = center.x + 34;
  476.  
  477.     nodes[SW].level = (level+1);
  478.     nodes[SW].center.z = center.z + 34 ;
  479.     nodes[SW].center.x = center.x + 34;
  480.  
  481.     nodes[SE].level = (level+1);
  482.     nodes[SE].center.z = center.z + 34 ;
  483.     nodes[SE].center.x = center.x ;*/
  484.  
  485.     /*
  486.     nodes[NW].level = (level+1);
  487.     nodes[NW].center.z = center.z / 2;
  488.     nodes[NW].center.x = center.x / 2;
  489.     nodes[NW].center.y = center.y;
  490.  
  491.     nodes[NE].level = (level+1);
  492.     nodes[NE].center.z = center.z / 2;
  493.     nodes[NE].center.x = center.x + (center.x / 2);
  494.     nodes[NE].center.y = center.y;
  495.  
  496.     nodes[SW].level = (level+1);
  497.     nodes[SW].center.z = center.z + (center.z / 2);
  498.     nodes[SW].center.x = center.x / 2;
  499.     nodes[SW].center.y = center.y;
  500.  
  501.     nodes[SE].level = (level+1);
  502.     nodes[SE].center.z = center.z + (center.z / 2);
  503.     nodes[SE].center.x = center.x + (center.x / 2);
  504.     nodes[SE].center.y = center.y;
  505.     */
  506.  
  507.     float value = 0;
  508.  
  509.     nodes[NW].level = (level+1);
  510.     //nodes[NW].center.z = center.z;
  511.     //nodes[NW].center.x = center.x;
  512.     //nodes[NW].center.y = center.y;
  513.  
  514. //  std::cout << "NW: " << nodes[NW].center.x << " " <<  nodes[NW].center.y << " " <<  nodes[NW].center.z << " " << std::endl;
  515.  
  516.     nodes[NE].level = (level+1);
  517.     //nodes[NE].center.z = center.z ;
  518.     //nodes[NE].center.x = center.x + (left+right)/2;
  519.     //nodes[NE].center.y = center.y;
  520.  
  521. //  std::cout << "LEFT: " << left << std::endl;
  522.  
  523.     //std::cout << "NE: " << nodes[NE].center.x << " " <<  nodes[NE].center.y << " " <<  nodes[NE].center.z << " " << std::endl;
  524.  
  525.     nodes[SW].level = (level+1);
  526.     //nodes[SW].center.z = center.z +  (top+down)/2;
  527.     //nodes[SW].center.x = center.x;
  528.     //nodes[SW].center.y = center.y;
  529.  
  530.     nodes[SE].level = (level+1);
  531.     /*nodes[SE].center.z = center.z +  (top+down)/2;
  532.     nodes[SE].center.x = center.x +  (left+right)/2;
  533.     nodes[SE].center.y = center.y;
  534.     */
  535.  
  536.     nodes[NW].Setup( w, h);
  537.     nodes[NE].Setup( w, h);
  538.     nodes[SW].Setup( w, h);
  539.     nodes[SE].Setup( w, h);
  540.    
  541.  
  542. }
  543. void Quadtree::deleteLeaves()
  544. {
  545.  
  546.     nodes = NULL;
  547.     isLeaf = true;
  548. }
  549.  
  550. void Quadtree::deleteSelf()
  551. {
  552.    
  553.     //nodes = NULL;
  554.     isLeaf = true;
  555. }
  556.  
  557. void Quadtree::moveObjectsToLeaves()
  558. {
  559.     for ( int n = 0; n < NodeCount; ++n ) {
  560.         for ( unsigned int m = 0; m < objects.size(); ++m ) {
  561.             if ( nodes[n].contains( objects[m] ) ) {
  562.                 nodes[n].AddObject( objects[m] );
  563.                 objects.erase( objects.begin() + m );
  564.                 --m;
  565.             }
  566.         }
  567.     }
  568. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!