home *** CD-ROM | disk | FTP | other *** search
/ Enter 2005 March / ENTER.ISO / files / fwp-0.0.6-win32-installer.exe / Quadtree.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2004-12-18  |  9.3 KB  |  279 lines
  1. /*!
  2. \file Quadtree.cpp
  3. \author Karsten Schwenk
  4.  
  5. See header for description (quadtree.h).
  6. */
  7.  
  8.  
  9. #include "Quadtree.h"
  10. #include "intersection.h"
  11. #include "matrixmath.h"
  12. #include "log.h"
  13. #include "Camera.h"
  14. //#include "Light.h"
  15.  
  16. #include "Renderer.h"
  17. #include "RendererInfo.h"
  18.  
  19. #define QUADTREE_MIN_EDGELENGTH    5.0f
  20. #define QUADTREE_MAX_LEVEL        10
  21. #define QUADTREE_MIN_FACES_PER_LEAF_NODE 200
  22.  
  23. Quadtree::Quadtree(Model* model):SpacePartitioningTree(model){
  24.     log("Building quadtree (min=(%.2f, %.2f, %.2f) max=(%.2f, %.2f, %.2f))...\n", min[0],min[1],min[2], max[0], max[1], max[2]);
  25.     root=new QuadtreeNode(this);
  26.     vectorCopy3d(min, root->min);
  27.     vectorCopy3d(max, root->max);
  28.     root->buildNode();
  29.  
  30.     nodes=new SpacePartitioningTreeNode*[numNodes];
  31.  
  32.     log("building neightbourhood info...\n");
  33.     root->buildNeighbourhoodInfo();
  34.  
  35.     for(int i=0;i<model->numMeshes;i++){
  36.         numFaces+=model->meshes[i]->numFaces;
  37.     }
  38.     facesDrawn=new BitSet(numFaces);
  39.  
  40.     log("Quadtree constructed: %i nodes in %i levels having a minEdgelength of %.2f.\n", numNodes, numLevels, QUADTREE_MIN_EDGELENGTH);
  41. }
  42.  
  43. Quadtree::~Quadtree(){
  44. }
  45.  
  46.  
  47.  
  48.  
  49. QuadtreeNode::QuadtreeNode(Quadtree* tree):SpacePartitioningTreeNode(tree){
  50.     int i;
  51.  
  52. //    this->tree=tree;
  53.  
  54.     parent=NULL;
  55.  
  56.     numChilds=QUADTREE_NUM_CHILDS;
  57.     childs=new SpacePartitioningTreeNode*[numChilds];
  58.     for(i=0;i<numChilds;i++)
  59.         childs[i]=NULL;
  60.  
  61.     numNeighbours=QUADTREE_NUM_NEIGHBOURS;
  62.     neighbours=new SpacePartitioningTreeNode*[numNeighbours];
  63.     for(i=0;i<numNeighbours;i++)
  64.         neighbours[i]=NULL;
  65.  
  66. }
  67.  
  68. QuadtreeNode::~QuadtreeNode(){
  69. }
  70.  
  71. void QuadtreeNode::buildNode(){
  72.     int i,j;
  73.     Model* m=tree->model;
  74.     vec4_t p1, p2, p3;
  75.     vec4_t n1, n2, n3, n;
  76.  
  77.     if(parent==NULL){
  78.         level=0;
  79.     }else{
  80.         level=parent->level+1;
  81.     }
  82.     if(tree->numLevels<level)
  83.         tree->numLevels=level;
  84.  
  85.     nodeId=tree->numNodes;
  86.     tree->numNodes++;
  87.  
  88.     // count faces that COULD be in node
  89.     int faceCount=0;
  90.         for(i=0;i<m->numMeshes;i++){
  91.             for(j=0;j<m->meshes[i]->numFaces;j++){
  92.                 vectorInit4d(m->meshes[i]->faces[j]->vertices[0], m->meshes[i]->faces[j]->vertices[1], m->meshes[i]->faces[j]->vertices[2], 1.0f, p1);
  93.                 vectorInit4d(m->meshes[i]->faces[j]->vertices[3], m->meshes[i]->faces[j]->vertices[4], m->meshes[i]->faces[j]->vertices[5], 1.0f, p2);
  94.                 vectorInit4d(m->meshes[i]->faces[j]->vertices[6], m->meshes[i]->faces[j]->vertices[7], m->meshes[i]->faces[j]->vertices[8], 1.0f, p3);
  95.                 matrixMultVector(m->matrices[0][i], p1, 4, p1);
  96.                 matrixMultVector(m->matrices[0][i], p2, 4, p2);
  97.                 matrixMultVector(m->matrices[0][i], p3, 4, p3);
  98.  
  99.                 if(triangleIntersectsAABB(p1, p2, p3, min, max)){
  100.                     faceCount++;
  101.                 }
  102.             }
  103.         }
  104.  
  105.  
  106.     if(max[0]-min[0] < QUADTREE_MIN_EDGELENGTH || max[2]-min[2] < QUADTREE_MIN_EDGELENGTH
  107.             || level>=QUADTREE_MAX_LEVEL
  108.             || faceCount<QUADTREE_MIN_FACES_PER_LEAF_NODE){    // make it a leaf node
  109.         
  110.         faceIds=new unsigned int[faceCount];
  111.  
  112.         mesh=new Mesh();
  113.  
  114.         int faceIdInModel=-1;    // id in model
  115.         int faceIdInMesh=0;        // id in mesh
  116.         for(i=0;i<m->numMeshes;i++){
  117.             for(j=0;j<m->meshes[i]->numFaces;j++){
  118.                 faceIdInModel++;
  119.  
  120.                 vectorInit4d(m->meshes[i]->faces[j]->vertices[0], m->meshes[i]->faces[j]->vertices[1], m->meshes[i]->faces[j]->vertices[2], 1.0f, p1);
  121.                 vectorInit4d(m->meshes[i]->faces[j]->vertices[3], m->meshes[i]->faces[j]->vertices[4], m->meshes[i]->faces[j]->vertices[5], 1.0f, p2);
  122.                 vectorInit4d(m->meshes[i]->faces[j]->vertices[6], m->meshes[i]->faces[j]->vertices[7], m->meshes[i]->faces[j]->vertices[8], 1.0f, p3);
  123.                 matrixMultVector(m->matrices[0][i], p1, 4, p1);
  124.                 matrixMultVector(m->matrices[0][i], p2, 4, p2);
  125.                 matrixMultVector(m->matrices[0][i], p3, 4, p3);
  126.  
  127.                 if(!triangleIntersectsAABB(p1, p2, p3, min, max)){
  128.                     continue;
  129.                 }
  130.  
  131.                 Face* face=new Face();
  132.  
  133.                 face->numVertices=3;
  134.                 face->vertices=new GLfloat[3*3];
  135.                 vectorCopy3d(p1, &face->vertices[0]);
  136.                 vectorCopy3d(p2, &face->vertices[3]);
  137.                 vectorCopy3d(p3, &face->vertices[6]);
  138.     
  139.                 vectorInit4d(m->meshes[i]->faces[j]->normals[0], m->meshes[i]->faces[j]->normals[1], m->meshes[i]->faces[j]->normals[2], 0.0f, n1);
  140.                 vectorInit4d(m->meshes[i]->faces[j]->normals[3], m->meshes[i]->faces[j]->normals[4], m->meshes[i]->faces[j]->normals[5], 0.0f, n2);
  141.                 vectorInit4d(m->meshes[i]->faces[j]->normals[6], m->meshes[i]->faces[j]->normals[7], m->meshes[i]->faces[j]->normals[8], 0.0f, n3);
  142.                 matrixMultVector(m->matrices[0][i], n1, 4, n1);
  143.                 matrixMultVector(m->matrices[0][i], n2, 4, n2);
  144.                 matrixMultVector(m->matrices[0][i], n3, 4, n3);
  145.  
  146.                 face->numNormals=3;
  147.                 face->normals=new GLfloat[3*3];
  148.                 vectorCopy3d(n1, &face->normals[0]);
  149.                 vectorCopy3d(n2, &face->normals[3]);
  150.                 vectorCopy3d(n3, &face->normals[6]);
  151.  
  152.                 face->numColors=3;
  153.                 face->colors=new GLfloat[3*3];
  154.                 vectorCopy3d(&m->meshes[i]->faces[j]->colors[0], &face->colors[0]);
  155.                 vectorCopy3d(&m->meshes[i]->faces[j]->colors[3], &face->colors[3]);
  156.                 vectorCopy3d(&m->meshes[i]->faces[j]->colors[6], &face->colors[6]);
  157.  
  158.                 face->numTexCoords=3;
  159.                 face->texCoords1=new GLfloat[3*2];
  160.                 vectorCopy2d(&m->meshes[i]->faces[j]->texCoords1[0], &face->texCoords1[0]);
  161.                 vectorCopy2d(&m->meshes[i]->faces[j]->texCoords1[2], &face->texCoords1[2]);
  162.                 vectorCopy2d(&m->meshes[i]->faces[j]->texCoords1[4], &face->texCoords1[4]);
  163.  
  164.                 face->texCoords2=new GLfloat[3*2];
  165.                 vectorCopy2d(&m->meshes[i]->faces[j]->texCoords2[0], &face->texCoords2[0]);
  166.                 vectorCopy2d(&m->meshes[i]->faces[j]->texCoords2[2], &face->texCoords2[2]);
  167.                 vectorCopy2d(&m->meshes[i]->faces[j]->texCoords2[4], &face->texCoords2[4]);
  168.  
  169. //                vectorCopy3d(m->meshes[i]->faces[j]->normal, face->normal);
  170.                 vectorInit4d(m->meshes[i]->faces[j]->normal[0], m->meshes[i]->faces[j]->normal[1], m->meshes[i]->faces[j]->normal[2], 0.0f, n);
  171.                 matrixMultVector(m->matrices[0][i], n, 4, n);
  172.                 vectorNormalize3d(n, n);
  173.                 vectorCopy3d(n, face->normal);
  174.                 
  175.                 face->material=m->meshes[i]->faces[j]->material;
  176.  
  177.                 mesh->addFace(face);
  178.  
  179.                 faceIds[faceIdInMesh]=faceIdInModel;
  180.                 faceIdInMesh++;
  181.             }
  182.         }
  183.  
  184.         mesh->name="<name destroyed by quadtree>";
  185.         mesh->createSecondaryColors();
  186.         mesh->setRenderMode();
  187.         if(_glGenBuffersARB!=NULL && Renderer::info.var.useVBOs==true){
  188.             mesh->createVBOs();
  189.             mesh->updateSecondaryColorVBO();
  190.         }
  191. //        mesh->sortFacesByMaterial();
  192.         
  193.         if(mesh->numVertices==0){
  194.         //    printf("min: %f %f %f ;  max: %f %f %f\n", min[0], min[1], min[2], max[0],max[1],max[2]);
  195.             vectorInit3d(0.0f, 0.0f, 0.0f, min);
  196.             vectorInit3d(0.0f, 0.0f, 0.0f, max);
  197.         }
  198.  
  199.         min[1]=FLT_MAX;
  200.         max[1]=-FLT_MAX;
  201.         for(i=0;i<mesh->numVertices;i++){    // THINKABOUTME: numV==0???
  202.             if(mesh->vertices[i*3+1] < min[1])
  203.                 min[1]=mesh->vertices[i*3+1];
  204.  
  205.             if(mesh->vertices[i*3+1] > max[1])
  206.                 max[1]=mesh->vertices[i*3+1];
  207.  
  208.         }
  209.         min[1]-=0.1f;    // THINKABOUTME
  210.         max[1]+=0.1f;
  211.         leafNode=true;
  212.  
  213.  
  214.     }else{    // divide it further
  215.         childs[QUADTREE_CHILD_LOWER_RIGHT]=new QuadtreeNode((Quadtree*)tree);
  216.         childs[QUADTREE_CHILD_LOWER_RIGHT]->parent=this;
  217.         vectorInit3d(min[0], min[1], min[2], childs[QUADTREE_CHILD_LOWER_RIGHT]->min);
  218.         vectorInit3d((max[0]+min[0])*0.5f, max[1], (max[2]+min[2])*0.5f, childs[QUADTREE_CHILD_LOWER_RIGHT]->max);
  219.  
  220.         childs[QUADTREE_CHILD_LOWER_LEFT]=new QuadtreeNode((Quadtree*)tree);
  221.         childs[QUADTREE_CHILD_LOWER_LEFT]->parent=this;
  222.         vectorInit3d((max[0]+min[0])*0.5f, min[1], min[2], childs[QUADTREE_CHILD_LOWER_LEFT]->min);
  223.         vectorInit3d(max[0], max[1], (max[2]+min[2])*0.5f, childs[QUADTREE_CHILD_LOWER_LEFT]->max);
  224.  
  225.         childs[QUADTREE_CHILD_UPPER_RIGHT]=new QuadtreeNode((Quadtree*)tree);
  226.         childs[QUADTREE_CHILD_UPPER_RIGHT]->parent=this;
  227.         vectorInit3d(min[0], min[1], (max[2]+min[2])*0.5f, childs[QUADTREE_CHILD_UPPER_RIGHT]->min);
  228.         vectorInit3d((max[0]+min[0])*0.5f, max[1], max[2], childs[QUADTREE_CHILD_UPPER_RIGHT]->max);
  229.  
  230.         childs[QUADTREE_CHILD_UPPER_LEFT]=new QuadtreeNode((Quadtree*)tree);
  231.         childs[QUADTREE_CHILD_UPPER_LEFT]->parent=this;
  232.         vectorInit3d((max[0]+min[0])*0.5f, min[1], (max[2]+min[2])*0.5f, childs[QUADTREE_CHILD_UPPER_LEFT]->min);
  233.         vectorInit3d(max[0], max[1], max[2], childs[QUADTREE_CHILD_UPPER_LEFT]->max);
  234.  
  235.         leafNode=false;
  236.  
  237.         min[1]=FLT_MAX;
  238.         max[1]=-FLT_MAX;
  239.         for(i=0;i<QUADTREE_NUM_CHILDS;i++){
  240.             childs[i]->buildNode();
  241.  
  242.             if(childs[i]->min[1]<min[1])
  243.                 min[1]=childs[i]->min[1];
  244.  
  245.             if(childs[i]->max[1]>max[1])
  246.                 max[1]=childs[i]->max[1];
  247.         }
  248.     }
  249. }
  250.  
  251. void QuadtreeNode::buildNeighbourhoodInfo(){
  252.     vec3_t point, mid;
  253.     float xSize=max[0]-min[0];
  254.     float zSize=max[2]-min[2];
  255.     vectorLinCombi3d(0.5, min, 0.5, max, mid);
  256.  
  257.     vectorInit3d(mid[0]-xSize, mid[1], mid[2], point);
  258.     neighbours[QUADTREE_NEIGHBOUR_RIGHT]=(QuadtreeNode*)tree->getNodeContainingPoint(point, level);
  259.  
  260.     vectorInit3d(mid[0]+xSize, mid[1], mid[2], point);
  261.     neighbours[QUADTREE_NEIGHBOUR_LEFT]=(QuadtreeNode*)tree->getNodeContainingPoint(point, level);
  262.  
  263.     vectorInit3d(mid[0], mid[1], mid[2]+zSize, point);
  264.     neighbours[QUADTREE_NEIGHBOUR_UP]=(QuadtreeNode*)tree->getNodeContainingPoint(point, level);
  265.  
  266.     vectorInit3d(mid[0], mid[1], mid[2]-zSize, point);
  267.     neighbours[QUADTREE_NEIGHBOUR_DOWN]=(QuadtreeNode*)tree->getNodeContainingPoint(point, level);
  268.  
  269.     tree->nodes[nodeId]=this;
  270.  
  271.     if(leafNode)
  272.         return;
  273.  
  274.     for(int i=0;i<QUADTREE_NUM_CHILDS;i++){
  275.         childs[i]->buildNeighbourhoodInfo();
  276.     }
  277.  
  278. }
  279.