home *** CD-ROM | disk | FTP | other *** search
/ Enter 2005 March / ENTER.ISO / files / fwp-0.0.6-win32-installer.exe / SpacePartitioningTree.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2004-12-18  |  16.6 KB  |  679 lines
  1. /*!
  2. \file SpacePartitioningTree.cpp
  3. \author Karsten Schwenk
  4.  
  5. See header for description (sptree.h).
  6. */
  7.  
  8. #include "SpacePartitioningTree.h"
  9. #include "intersection.h"
  10. #include "matrixmath.h"
  11. #include "log.h"
  12. #include "Renderer.h"
  13. #include "RendererInfo.h"
  14. #include "Game.h"
  15.  
  16. #include "Q3bspLoader.h"
  17.  
  18. SpacePartitioningTree::SpacePartitioningTree(Model* model){
  19.     this->model=model;
  20.     vectorCopy3d(model->min, this->min);
  21.     vectorCopy3d(model->max, this->max);
  22.     /*
  23. #define EPS 0.01f
  24.     vectorInit3d(model->min[0]-EPS, model->min[1]-EPS, model->min[2]-EPS, min);
  25.     vectorInit3d(model->max[0]+EPS, model->max[1]+EPS, model->max[2]+EPS, max);
  26. #undef EPS
  27.     */
  28.  
  29.     numNodes=0;
  30.     numLevels=0;
  31.     numFaces=0;
  32.  
  33.     facesDrawn=NULL;
  34.     pvs=NULL;
  35.     q3bspExtension=NULL;
  36.  
  37.     root=NULL;
  38.  
  39. }
  40.  
  41. SpacePartitioningTree::~SpacePartitioningTree(){
  42.     if(facesDrawn!=NULL)
  43.         delete facesDrawn;
  44.  
  45.     if(root!=NULL)
  46.         delete root;    // this destroys recursively all nodes
  47.  
  48.     delete[] nodes;        // this is empty now
  49.  
  50.     if(pvs!=NULL)
  51.         delete pvs;
  52.  
  53.     if(q3bspExtension!=NULL)
  54.         delete q3bspExtension;
  55. }
  56.  
  57. SpacePartitioningTreeNode* SpacePartitioningTree::getLeafNodeContainingPoint(vec3_t point){
  58.     int i;
  59.     SpacePartitioningTreeNode* current=root;
  60.     SpacePartitioningTreeNode* child;
  61.  
  62.     // check if point is in root node
  63.     if(!pointIntersectsAABB(point, min, max)){
  64.         return NULL;
  65.     }
  66.  
  67.     // decend into tree
  68.     while(current!=NULL && !current->leafNode){
  69.         for(i=0;i<current->numChilds;i++){
  70.             child=current->childs[i];
  71.             if(pointIntersectsAABB(point, child->min, child->max)){
  72.                 current=child;
  73.                 break;
  74.             }
  75.         }
  76.         if(i==current->numChilds){    // no suitable child found -> return NULL
  77.             return NULL;
  78.         }
  79.     }
  80.  
  81.     return current;
  82. }
  83.  
  84. SpacePartitioningTreeNode* SpacePartitioningTree::getNodeContainingPoint(vec3_t point, int maxLevel){
  85.     int i;
  86.     SpacePartitioningTreeNode* current=root;
  87.     SpacePartitioningTreeNode* child;
  88.  
  89.     // check if point is in root node
  90.     if(!pointIntersectsAABB(point, min, max)){
  91.         return NULL;
  92.     }
  93.  
  94.     // decend into tree
  95.     while(current!=NULL && !current->leafNode && current->level<maxLevel){
  96.         for(i=0;i<current->numChilds;i++){
  97.             child=current->childs[i];
  98.             if(pointIntersectsAABB(point, child->min, child->max)){
  99.                 current=child;
  100.                 break;
  101.             }
  102.         }
  103.         if(i==current->numChilds){    // THINKABOUTME: was tun, wenn kein nachbar AUF GLEICHEM LEVEL da ist??
  104.             break;
  105.         }
  106.     }
  107.  
  108.     return current;
  109. }
  110.  
  111.  
  112. vector<SpacePartitioningTreeNode*> SpacePartitioningTree::getLeafNodesIntersectingAABB(vec3_t min, vec3_t max){
  113.     vector<SpacePartitioningTreeNode*> ret;
  114.  
  115.     root->collectLeafNodesIntersectingAABB(min, max, ret);
  116.  
  117.     return ret;
  118. }
  119.  
  120. void SpacePartitioningTree::traceRay(/*vec3_t startPos, vec3_t dir,*/ trace_t* trace){
  121. //    vectorCopy3d(startPos, trace->startPos);
  122. //    vectorCopy3d(dir, trace->dir);
  123. //    trace->traceType=TRACE_TYPE_RAY;
  124.  
  125. //    trace->hits.clear();
  126. /*    
  127.     vector<Face*> faces;
  128.     if( trace->ignoreFlags & COLLISION_FLAG_BACKFACES ){    // ignore backfaces
  129.         root->collectFrontFacingFacesIntersectingRay(trace->startPos, trace->dir, faces);
  130.     }else{
  131.         root->collectFacesIntersectingRay(trace->startPos, trace->dir, faces);
  132.     }
  133.  
  134.     // sortieren und fertisch
  135.     // TODO: calc hits Positions and sort stuff
  136.     for(int i=0;i<faces.size();i++){
  137.         if( !(trace->ignoreFlags & faces[i]->material->collisionFlags) ){
  138.             trace->hitFaces.push_back(faces[i]);
  139.         }
  140.     }
  141. */
  142.     root->traceRay(trace);
  143. }
  144.  
  145. void SpacePartitioningTree::traceLinesegment(/*vec3_t pos1, vec3_t pos2,*/ trace_t* trace){
  146. //    vectorCopy3d(pos1, trace->startPos);
  147. //    vectorCopy3d(pos2, trace->endPos);
  148. //    vectorSub3d(pos2, pos1, trace->dir);
  149. //    trace->traceType=TRACE_TYPE_LINE_SEGMENT;
  150.  
  151. //    trace->hits.clear();
  152.  
  153.     SpacePartitioningTreeNode* pos1Node = getLeafNodeContainingPoint(trace->startPos);
  154.     SpacePartitioningTreeNode* pos2Node = getLeafNodeContainingPoint(trace->endPos);
  155.     if(pos1Node!=pos2Node || pos1Node==NULL || pos2Node==NULL)
  156.         root->traceLinesegment(trace);
  157.     else    // start and end in the same node -> test only this node
  158.         pos1Node->traceLinesegment(trace);
  159.  
  160. //    if(trace->hitDistance==FLT_MAX)
  161. //        trace->hitDistance=-1.0f;
  162. }
  163.  
  164. void SpacePartitioningTree::traceAABB(/*vec3_t pos1, vec3_t pos2, vec3_t min, vec3_t max, */trace_t* trace){
  165.     unsigned int i;
  166.     bool noHitsHere = true;
  167.  
  168. //    vectorCopy3d(pos1, trace->startPos);
  169. //    vectorCopy3d(pos2, trace->endPos);
  170. //    vectorSub3d(pos2, pos1, trace->dir);
  171.     float hitDistance = vectorLength3d(trace->dir);
  172. //    vectorCopy3d(min, trace->min);
  173. //    vectorCopy3d(max, trace->max);
  174. //    trace->traceType=TRACE_TYPE_AABB;
  175.  
  176. //    trace->hits.clear();
  177.  
  178.     vec3_t minAbs, maxAbs;
  179.     vectorAdd3d(trace->endPos, trace->min, minAbs);
  180.     vectorAdd3d(trace->endPos, trace->max, maxAbs);
  181.  
  182.     if( trace->ignoreFlags & COLLISION_FLAG_SUBSEQUENT_HITS ){    // we want only ONE hit
  183.  
  184.         vector<SpacePartitioningTreeNode*> intersectedLeafNodes;
  185.         root->collectLeafNodesIntersectingAABB(minAbs, maxAbs, intersectedLeafNodes);
  186.  
  187.         // check
  188.         for(i=0;i<intersectedLeafNodes.size();i++){
  189.             Face* f;
  190.             if(trace->ignoreFlags & COLLISION_FLAG_BACKFACES){    // ignore backfaces
  191.                 f = intersectedLeafNodes[i]->getFrontFacingFaceIntersectingAABB(minAbs, maxAbs, trace->dir);
  192.             }else{
  193.                 f = intersectedLeafNodes[i]->getFaceIntersectingAABB(minAbs, maxAbs);
  194.             }
  195.  
  196.             if(f != NULL && !(trace->ignoreFlags & f->material->collisionFlags)){
  197.                 hit_t hit;
  198.                 hit.distance = hitDistance;
  199.                 vectorCopy3d(trace->endPos, hit.pos);
  200.                 hit.node = intersectedLeafNodes[i];
  201.                 hit.face = f;
  202.                 hit.vehicle = NULL;
  203.  
  204.                 trace->hits.push_back(hit);
  205.                 noHitsHere = false;
  206.                 return;
  207.             }
  208.         }
  209.  
  210.     }else{    // collect all hits
  211.         vector<Face*> faces;
  212.         if(trace->ignoreFlags & COLLISION_FLAG_BACKFACES){    // ignore backfaces
  213.             root->collectFrontFacingFacesIntersectingAABB(minAbs, maxAbs, trace->dir, faces);
  214.         }else{
  215.             root->collectFacesIntersectingAABB(minAbs, maxAbs, faces);
  216.         }
  217.  
  218.         for(unsigned int i=0;i<faces.size();i++){
  219.             if( !(trace->ignoreFlags & faces[i]->material->collisionFlags) ){
  220.                 hit_t hit;
  221.                 hit.distance = hitDistance;
  222.                 vectorCopy3d(trace->endPos, hit.pos);
  223.                 hit.node = root;    // FIXME: WRONG!!
  224.                 hit.face = faces[i];
  225.                 hit.vehicle = NULL;
  226.  
  227.                 trace->hits.push_back(hit);
  228.                 noHitsHere = false;
  229.             }
  230.         }
  231.     }
  232.  
  233.     if( noHitsHere ){    // maybe we "tunneled" a wall...
  234.         root->traceLinesegment(trace);
  235.     }
  236.  
  237. //    if(trace->hitDistance == FLT_MAX)
  238. //        trace->hitDistance=-1.0f;
  239. }
  240.  
  241. void SpacePartitioningTree::render(){
  242.     if(Renderer::info.var.renderSPTreeBorders)
  243.         drawBorders();
  244.  
  245.     if(q3bspExtension!=NULL){
  246.         Renderer::renderQ3bspExtension(q3bspExtension);
  247.         return;
  248.     }
  249.  
  250.     if(facesDrawn!=NULL)
  251.         facesDrawn->clearAll();
  252.  
  253.     if(pvs!=NULL){
  254.         SpacePartitioningTreeNode* camNode=getLeafNodeContainingPoint(Game::cam.pos);
  255.         if(camNode!=NULL){
  256.             pvs->setCurrentCluster(camNode->nodeId);
  257.             pvs->enabled=true;
  258.             if(Renderer::info.var.renderPVSBorders)
  259.                 pvs->drawClusterBorders();
  260.         }else{
  261.             pvs->enabled=false;
  262.         }
  263.     }
  264.  
  265.     root->render();
  266. }
  267.  
  268. void SpacePartitioningTree::drawBorders(){
  269.     Renderer::disableLighting();
  270.     glColor4f(1.0f, 1.0f, 0.0f, 1.0f);
  271.     Renderer::debug_renderAABB(min, max);
  272.     Renderer::enableLighting();
  273.  
  274.     root->drawBorders();
  275. }
  276.  
  277.  
  278. void SpacePartitioningTree::importPVS(PotentialVisibilitySet* pvs){
  279.     if(this->pvs!=NULL){
  280.         delete this->pvs;
  281.     }
  282.     this->pvs=new PotentialVisibilitySet(numNodes);
  283.  
  284.     unsigned int i,j,k,l;
  285.     unsigned int import_numClusters=pvs->getNumClusters();
  286.     PVSCluster_t** import_clusters=pvs->getClusters();
  287.     PVSCluster_t** this_clusters=this->pvs->getClusters();
  288.     int* a=new int[numNodes*(import_numClusters+1)];
  289.  
  290.     log("SPTree::importPVS: importing pvs...\n");
  291.  
  292.     for(i=0;i<(unsigned int)numNodes;i++){
  293.         vectorCopy3d(nodes[i]->min, this_clusters[i]->min);
  294.         vectorCopy3d(nodes[i]->max, this_clusters[i]->max);
  295.  
  296.         int counter=0;
  297.         for(j=0;j<import_numClusters;j++){
  298.             if(AABBIntersectsAABB(nodes[i]->min, nodes[i]->max, import_clusters[j]->min, import_clusters[j]->max)){ 
  299.                 a[counter*numNodes + i]=j;
  300.                 counter++;
  301.                 //break;
  302.             }
  303.         }
  304.         a[counter*numNodes + i]=-1;
  305.     }
  306.  
  307.  
  308.     for(i=0;i<(unsigned int)numNodes;i++){
  309.         for(j=0;j<(unsigned int)numNodes;j++){
  310.             for(k=0;a[k*numNodes + i]!=-1;k++){
  311.                 for(l=0;a[l*numNodes + j]!=-1;l++){
  312.                     if(pvs->clusterIsVisible(a[k*numNodes + i], a[l*numNodes + j])){
  313.                         this_clusters[i]->visibleClusters->set(j);
  314.                         //this_clusters[j]->visibleClusters->set(i);
  315.                         goto nextNode;
  316.                     }
  317.                 }
  318.             }
  319. nextNode:    ;
  320.         }
  321.     }
  322.  
  323.     log("SPTree::importPVS: pvs imported: %i clusters converted to %i clusters.\n", import_numClusters, numNodes);
  324.  
  325.     delete[] a;
  326. }
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333. SpacePartitioningTreeNode::SpacePartitioningTreeNode(SpacePartitioningTree* tree){
  334.  
  335.     this->tree=tree;
  336.  
  337.     parent=NULL;
  338.  
  339.     childs=NULL;
  340.     numChilds=0;
  341.  
  342.     neighbours=NULL;
  343.     numNeighbours=0;
  344.  
  345.     vectorInit3d(0.0f, 0.0f, 0.0f, min);
  346.     vectorInit3d(0.0f, 0.0f, 0.0f, max);
  347.  
  348.     level=0;
  349.  
  350.     mesh=NULL;
  351.     leafNode=false;
  352.  
  353.     faceIds=NULL;
  354. }
  355.  
  356. SpacePartitioningTreeNode::~SpacePartitioningTreeNode(){
  357.     int i;
  358.  
  359.     for(i=0;i<numChilds;i++){    // THINKABOUTME: wirklich alle childs l÷schen?
  360.         if(childs[i]!=NULL){
  361.             delete childs[i];
  362.         }
  363.     }
  364.  
  365.     if(childs!=NULL)
  366.         delete[] childs;
  367.  
  368.     if(neighbours!=NULL)
  369.         delete[] neighbours;
  370.  
  371.     if(mesh!=NULL)
  372.         delete mesh;
  373.  
  374.     if(faceIds!=NULL)
  375.         delete faceIds;
  376.  
  377. }
  378.  
  379. Face* SpacePartitioningTreeNode::getFaceIntersectingAABB(vec3_t min, vec3_t max){
  380.     int i;
  381.     Face* f;
  382.  
  383.     if(!AABBIntersectsAABB(min, max, this->min, this->max))
  384.         return NULL;
  385.  
  386.     if(leafNode){
  387.         for(i=0;i<mesh->numFaces;i++){
  388.             f=mesh->faces[i];
  389.             if(triangleIntersectsAABB(&f->vertices[0],&f->vertices[3],&f->vertices[6], min, max)){
  390.                 return f;
  391.             }
  392.         }
  393.     }else{
  394.         for(i=0;i<numChilds;i++){
  395.             f=childs[i]->getFaceIntersectingAABB(min, max);
  396.             if(f!=NULL){
  397.                 return f;
  398.             }
  399.         }
  400.     }
  401.  
  402.     return NULL;
  403. }
  404.  
  405. Face* SpacePartitioningTreeNode::getFrontFacingFaceIntersectingAABB(vec3_t min, vec3_t max, vec3_t dir){
  406.     int i;
  407.     Face* f;
  408.  
  409.     if(!AABBIntersectsAABB(min, max, this->min, this->max))
  410.         return NULL;
  411.  
  412.     if(leafNode){
  413.         for(i=0;i<mesh->numFaces;i++){
  414.             f=mesh->faces[i];
  415.             if(DOT_PRODUCT_3D(f->normal, dir)<0.0f
  416.                 && triangleIntersectsAABB(&f->vertices[0],&f->vertices[3],&f->vertices[6], min, max)){
  417.                 return f;
  418.             }
  419.         }
  420.     }else{
  421.         for(i=0;i<numChilds;i++){
  422.             f=childs[i]->getFrontFacingFaceIntersectingAABB(min, max, dir);
  423.             if(f!=NULL){
  424.                 return f;
  425.             }
  426.         }
  427.     }
  428.  
  429.     return NULL;
  430. }
  431.  
  432. void SpacePartitioningTreeNode::collectFacesIntersectingAABB(vec3_t min, vec3_t max, vector<Face*>& ret){
  433.     int i;
  434.     Face* f;
  435.  
  436.     if(!AABBIntersectsAABB(min, max, this->min, this->max))    // aabb not in node
  437.         return;
  438.  
  439.     if(leafNode){
  440.         for(i=0;i<mesh->numFaces;i++){
  441.             f = mesh->faces[i];
  442.             if(triangleIntersectsAABB(&f->vertices[0],&f->vertices[3],&f->vertices[6], min, max)){
  443.                 ret.push_back(f);
  444.             }
  445.         }
  446.     }else{
  447.         for(i=0;i<numChilds;i++){
  448.             if( AABBIntersectsAABB(min, max, childs[i]->min, childs[i]->max) ){
  449.                 childs[i]->collectFacesIntersectingAABB(min, max, ret);
  450.             }
  451.         }
  452.     }
  453. }
  454.  
  455. void SpacePartitioningTreeNode::collectFrontFacingFacesIntersectingAABB(vec3_t min, vec3_t max, vec3_t dir, vector<Face*>& ret){
  456.     int i;
  457.     Face* f;
  458.  
  459.     if( !AABBIntersectsAABB(min, max, this->min, this->max) )
  460.         return;
  461.  
  462.     if(leafNode){
  463.         for(i=0;i<mesh->numFaces;i++){
  464.             f = mesh->faces[i];
  465.             if( DOT_PRODUCT_3D(f->normal, dir) < 0.0f
  466.                 && triangleIntersectsAABB(&f->vertices[0],&f->vertices[3],&f->vertices[6], min, max) ){
  467.                 ret.push_back(f);
  468.             }
  469.         }
  470.     }else{
  471.         for(i=0;i<numChilds;i++){
  472.             if( AABBIntersectsAABB(min, max, childs[i]->min, childs[i]->max) ){
  473.                 childs[i]->collectFrontFacingFacesIntersectingAABB(min, max, dir, ret);
  474.             }
  475.         }
  476.     }
  477. }
  478.  
  479.  
  480. void SpacePartitioningTreeNode::collectFacesIntersectingRay(vec3_t startPos, vec3_t dir, vector<Face*>& ret){
  481.     int i;
  482.  
  483.     Face* f;
  484.  
  485.     if( !rayIntersectsAABB(startPos, dir, this->min, this->max) )    // ray not in node
  486.         return;
  487.  
  488.     if(leafNode){
  489.         for(i=0;i<mesh->numFaces;i++){
  490.             f = mesh->faces[i];
  491.             if( rayIntersectsTriangle(startPos, dir, &f->vertices[0],&f->vertices[3],&f->vertices[6]) ){
  492.                 ret.push_back(f);
  493.             }
  494.         }
  495.     }else{
  496.         for(i=0;i<numChilds;i++){
  497.             if( rayIntersectsAABB(startPos, dir, childs[i]->min, childs[i]->max) ){
  498.                 childs[i]->collectFacesIntersectingRay(startPos, dir, ret);
  499.             }
  500.         }
  501.     }
  502. }
  503.  
  504. void SpacePartitioningTreeNode::collectFrontFacingFacesIntersectingRay(vec3_t startPos, vec3_t dir, vector<Face*>& ret){
  505.     int i;
  506.     Face* f;
  507.  
  508.     if( !rayIntersectsAABB(startPos, dir, this->min, this->max) )    // ray not in node
  509.         return;
  510.  
  511.     if(leafNode){
  512.         for(i=0;i<mesh->numFaces;i++){
  513.             f = mesh->faces[i];
  514.             if( rayIntersectsTriangle(startPos, dir, &f->vertices[0],&f->vertices[3],&f->vertices[6]) 
  515.                     && DOT_PRODUCT_3D(f->normal, dir) >= 0.0f ){
  516.                 ret.push_back(f);
  517.             }
  518.         }
  519.     }else{
  520.         for(i=0;i<numChilds;i++){
  521.             if( rayIntersectsAABB(startPos, dir, childs[i]->min, childs[i]->max) ){
  522.                 childs[i]->collectFacesIntersectingRay(startPos, dir, ret);
  523.             }
  524.         }
  525.     }
  526. }
  527.  
  528.  
  529.  
  530. void SpacePartitioningTreeNode::collectLeafNodesIntersectingAABB(vec3_t min, vec3_t max, vector<SpacePartitioningTreeNode*>& ret){
  531.     int i;
  532.  
  533.     if(!AABBIntersectsAABB(min, max, this->min, this->max))
  534.         return;
  535.  
  536.     if(leafNode){
  537.         ret.push_back(this);
  538.     }else{
  539.         for(i=0;i<numChilds;i++){
  540.             childs[i]->collectLeafNodesIntersectingAABB(min, max, ret);
  541.         }
  542.     }
  543. }
  544.  
  545.  
  546. void SpacePartitioningTreeNode::traceRay(trace_t* trace){
  547.     int i;
  548.     Face* f;
  549.  
  550.     if(leafNode){
  551.         float dist;
  552.         vec3_t hp;
  553.         for(i=0;i<mesh->numFaces;i++){
  554.             if( ((trace->ignoreFlags & COLLISION_FLAG_BACKFACES) && DOT_PRODUCT_3D(mesh->faces[i]->normal, trace->dir) >= 0.0f)
  555.                 || (trace->ignoreFlags & mesh->faces[i]->material->collisionFlags) )
  556.                 continue;
  557.  
  558.             f = mesh->faces[i];
  559.             if( rayIntersectsFace(trace->startPos, trace->dir, f, &dist, hp) ){
  560.                 vector<hit_t>::iterator hits_iter;
  561.                 for (hits_iter = trace->hits.begin(); hits_iter != trace->hits.end(); hits_iter++){
  562. //                    if( (*node_iter)->faceIds[i] == this->faceIds[i] ){
  563. //                        printf("DOUBLE!\n");
  564. //                        f = NULL;
  565. //                    }
  566.                     if( dist < hits_iter->distance ){
  567.                         break;
  568.                     }
  569.  
  570.                 }
  571.  
  572.                 if( f != NULL ){
  573.                     hit_t hit;
  574.                     hit.distance = dist;
  575.                     vectorCopy3d(hp, hit.pos);
  576.                     hit.node = this;
  577.                     hit.face = f;
  578.                     hit.vehicle = NULL;
  579.  
  580.                     hits_iter = trace->hits.insert(hits_iter, hit);
  581.                 }
  582.             }
  583.         }
  584.  
  585.     }else{
  586.         for(i=0;i<numChilds;i++){
  587.             if(rayIntersectsAABB(trace->startPos, trace->dir, childs[i]->min, childs[i]->max)){
  588.                 childs[i]->traceRay(trace);
  589.             }
  590.         }
  591.     }
  592.  
  593. }
  594.  
  595. void SpacePartitioningTreeNode::traceLinesegment(trace_t* trace){
  596.     int i;
  597.     Face* f;
  598.  
  599.     if(leafNode){
  600.         float dist;
  601.         vec3_t hp;
  602.         for(i=0;i<mesh->numFaces;i++){
  603.             if( ((trace->ignoreFlags & COLLISION_FLAG_BACKFACES) && DOT_PRODUCT_3D(mesh->faces[i]->normal, trace->dir) >= 0.0f)
  604.                 || (trace->ignoreFlags & mesh->faces[i]->material->collisionFlags) )
  605.                 continue;
  606.  
  607.             f = mesh->faces[i];
  608.             if( linesegmentIntersectsFace(trace->startPos, trace->endPos, f, &dist, hp) ){
  609.                 vector<hit_t>::iterator hits_iter;
  610.                 for (hits_iter = trace->hits.begin(); hits_iter != trace->hits.end(); hits_iter++){
  611. //                    if( (*node_iter)->faceIds[i] == this->faceIds[i] ){
  612. //                        printf("DOUBLE!\n");
  613. //                        f = NULL;
  614. //                    }
  615.                     if( dist < hits_iter->distance ){
  616.                         break;
  617.                     }
  618.                 }
  619.  
  620.                 if( f != NULL ){
  621.                     hit_t hit;
  622.                     hit.distance = dist;
  623.                     vectorCopy3d(hp, hit.pos);
  624.                     hit.node = this;
  625.                     hit.face = f;
  626.                     hit.vehicle = NULL;
  627.  
  628.                     hits_iter = trace->hits.insert(hits_iter, hit);
  629.                 }
  630.             }
  631.         }
  632.     }else{
  633.         for(i=0;i<numChilds;i++){
  634.             if(linesegmentIntersectsAABB(trace->startPos, trace->endPos, childs[i]->min, childs[i]->max)){
  635.                 childs[i]->traceLinesegment(trace);
  636.             }
  637.         }
  638.     }
  639. }
  640.  
  641. void SpacePartitioningTreeNode::render(){
  642.     //printf("rendering node %i\n", nodeId);
  643.  
  644.     if(Renderer::info.var.useFrustrumCulling && !Game::cam.AABBInFrustum(min, max))
  645.         return;
  646.  
  647.     if(tree->pvs!=NULL && tree->pvs->enabled && !tree->pvs->clusterIsVisible(nodeId)){
  648.         //printf("JUHU!!\n");
  649.         return;
  650.     }
  651.  
  652.     if(!leafNode){
  653.         for(int i=0;i<numChilds;i++){
  654.             childs[i]->render();
  655.         }
  656.     }else{
  657.         Renderer::renderMesh(mesh, this);
  658.         Renderer::info.var.nodeCount++;
  659.     }
  660. }
  661.  
  662. void SpacePartitioningTreeNode::drawBorders(){
  663.     if(!(Renderer::info.var.renderSPTreeBorders==2) || leafNode){
  664.         float red=1.0f - level/(float)tree->numLevels;
  665.         Renderer::disableLighting();
  666.         glColor4f(red, 1.0f, 0.0f, 1.0f);
  667.         Renderer::debug_renderAABB(min, max);
  668.         Renderer::enableLighting();
  669.     }
  670.  
  671.     if(leafNode)
  672.         return;
  673.  
  674.     for(int i=0;i<numChilds;i++){
  675.         childs[i]->drawBorders();
  676.     }
  677. }
  678.  
  679.