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