home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 22 / PCPP #22.iso / Quake2 / q2source_12_11 / utils3 / bsp / qrad3 / trace.c < prev   
Encoding:
C/C++ Source or Header  |  1997-08-09  |  5.2 KB  |  276 lines
  1. // trace.c
  2.  
  3. #include "cmdlib.h"
  4. #include "mathlib.h"
  5. #include "bspfile.h"
  6.  
  7. #define    ON_EPSILON    0.1
  8.  
  9. typedef struct tnode_s
  10. {
  11.     int        type;
  12.     vec3_t    normal;
  13.     float    dist;
  14.     int        children[2];
  15.     int        pad;
  16. } tnode_t;
  17.  
  18. tnode_t        *tnodes, *tnode_p;
  19.  
  20. /*
  21. ==============
  22. MakeTnode
  23.  
  24. Converts the disk node structure into the efficient tracing structure
  25. ==============
  26. */
  27. void MakeTnode (int nodenum)
  28. {
  29.     tnode_t            *t;
  30.     dplane_t        *plane;
  31.     int                i;
  32.     dnode_t         *node;
  33.     
  34.     t = tnode_p++;
  35.  
  36.     node = dnodes + nodenum;
  37.     plane = dplanes + node->planenum;
  38.  
  39.     t->type = plane->type;
  40.     VectorCopy (plane->normal, t->normal);
  41.     t->dist = plane->dist;
  42.     
  43.     for (i=0 ; i<2 ; i++)
  44.     {
  45.         if (node->children[i] < 0)
  46.             t->children[i] = (dleafs[-node->children[i] - 1].contents & CONTENTS_SOLID) | (1<<31);
  47.         else
  48.         {
  49.             t->children[i] = tnode_p - tnodes;
  50.             MakeTnode (node->children[i]);
  51.         }
  52.     }
  53.             
  54. }
  55.  
  56.  
  57. /*
  58. =============
  59. MakeTnodes
  60.  
  61. Loads the node structure out of a .bsp file to be used for light occlusion
  62. =============
  63. */
  64. void MakeTnodes (dmodel_t *bm)
  65. {
  66.     // 32 byte align the structs
  67.     tnodes = malloc( (numnodes+1) * sizeof(tnode_t));
  68.     tnodes = (tnode_t *)(((int)tnodes + 31)&~31);
  69.     tnode_p = tnodes;
  70.  
  71.     MakeTnode (0);
  72. }
  73.  
  74.  
  75. //==========================================================
  76.  
  77.  
  78. int TestLine_r (int node, vec3_t start, vec3_t stop)
  79. {
  80.     tnode_t    *tnode;
  81.     float    front, back;
  82.     vec3_t    mid;
  83.     float    frac;
  84.     int        side;
  85.     int        r;
  86.  
  87.     if (node & (1<<31))
  88.         return node & ~(1<<31);    // leaf node
  89.  
  90.     tnode = &tnodes[node];
  91.     switch (tnode->type)
  92.     {
  93.     case PLANE_X:
  94.         front = start[0] - tnode->dist;
  95.         back = stop[0] - tnode->dist;
  96.         break;
  97.     case PLANE_Y:
  98.         front = start[1] - tnode->dist;
  99.         back = stop[1] - tnode->dist;
  100.         break;
  101.     case PLANE_Z:
  102.         front = start[2] - tnode->dist;
  103.         back = stop[2] - tnode->dist;
  104.         break;
  105.     default:
  106.         front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
  107.         back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist;
  108.         break;
  109.     }
  110.  
  111.     if (front >= -ON_EPSILON && back >= -ON_EPSILON)
  112.         return TestLine_r (tnode->children[0], start, stop);
  113.     
  114.     if (front < ON_EPSILON && back < ON_EPSILON)
  115.         return TestLine_r (tnode->children[1], start, stop);
  116.  
  117.     side = front < 0;
  118.     
  119.     frac = front / (front-back);
  120.  
  121.     mid[0] = start[0] + (stop[0] - start[0])*frac;
  122.     mid[1] = start[1] + (stop[1] - start[1])*frac;
  123.     mid[2] = start[2] + (stop[2] - start[2])*frac;
  124.  
  125.     r = TestLine_r (tnode->children[side], start, mid);
  126.     if (r)
  127.         return r;
  128.     return TestLine_r (tnode->children[!side], mid, stop);
  129. }
  130.  
  131. int TestLine (vec3_t start, vec3_t stop)
  132. {
  133.     return TestLine_r (0, start, stop);
  134. }
  135.  
  136. /*
  137. ==============================================================================
  138.  
  139. LINE TRACING
  140.  
  141. The major lighting operation is a point to point visibility test, performed
  142. by recursive subdivision of the line by the BSP tree.
  143.  
  144. ==============================================================================
  145. */
  146.  
  147. typedef struct
  148. {
  149.     vec3_t    backpt;
  150.     int        side;
  151.     int        node;
  152. } tracestack_t;
  153.  
  154.  
  155. /*
  156. ==============
  157. TestLine
  158. ==============
  159. */
  160. qboolean _TestLine (vec3_t start, vec3_t stop)
  161. {
  162.     int                node;
  163.     float            front, back;
  164.     tracestack_t    *tstack_p;
  165.     int                side;
  166.     float             frontx,fronty, frontz, backx, backy, backz;
  167.     tracestack_t    tracestack[64];
  168.     tnode_t            *tnode;
  169.     
  170.     frontx = start[0];
  171.     fronty = start[1];
  172.     frontz = start[2];
  173.     backx = stop[0];
  174.     backy = stop[1];
  175.     backz = stop[2];
  176.     
  177.     tstack_p = tracestack;
  178.     node = 0;
  179.     
  180.     while (1)
  181.     {
  182.         if (node == CONTENTS_SOLID)
  183.         {
  184. #if 0
  185.             float    d1, d2, d3;
  186.  
  187.             d1 = backx - frontx;
  188.             d2 = backy - fronty;
  189.             d3 = backz - frontz;
  190.  
  191.             if (d1*d1 + d2*d2 + d3*d3 > 1)
  192. #endif
  193.                 return false;    // DONE!
  194.         }
  195.         
  196.         while (node < 0)
  197.         {
  198.         // pop up the stack for a back side
  199.             tstack_p--;
  200.             if (tstack_p < tracestack)
  201.                 return true;
  202.             node = tstack_p->node;
  203.             
  204.         // set the hit point for this plane
  205.             
  206.             frontx = backx;
  207.             fronty = backy;
  208.             frontz = backz;
  209.             
  210.         // go down the back side
  211.  
  212.             backx = tstack_p->backpt[0];
  213.             backy = tstack_p->backpt[1];
  214.             backz = tstack_p->backpt[2];
  215.             
  216.             node = tnodes[tstack_p->node].children[!tstack_p->side];
  217.         }
  218.  
  219.         tnode = &tnodes[node];
  220.         
  221.         switch (tnode->type)
  222.         {
  223.         case PLANE_X:
  224.             front = frontx - tnode->dist;
  225.             back = backx - tnode->dist;
  226.             break;
  227.         case PLANE_Y:
  228.             front = fronty - tnode->dist;
  229.             back = backy - tnode->dist;
  230.             break;
  231.         case PLANE_Z:
  232.             front = frontz - tnode->dist;
  233.             back = backz - tnode->dist;
  234.             break;
  235.         default:
  236.             front = (frontx*tnode->normal[0] + fronty*tnode->normal[1] + frontz*tnode->normal[2]) - tnode->dist;
  237.             back = (backx*tnode->normal[0] + backy*tnode->normal[1] + backz*tnode->normal[2]) - tnode->dist;
  238.             break;
  239.         }
  240.  
  241.         if (front > -ON_EPSILON && back > -ON_EPSILON)
  242. //        if (front > 0 && back > 0)
  243.         {
  244.             node = tnode->children[0];
  245.             continue;
  246.         }
  247.         
  248.         if (front < ON_EPSILON && back < ON_EPSILON)
  249. //        if (front <= 0 && back <= 0)
  250.         {
  251.             node = tnode->children[1];
  252.             continue;
  253.         }
  254.  
  255.         side = front < 0;
  256.         
  257.         front = front / (front-back);
  258.     
  259.         tstack_p->node = node;
  260.         tstack_p->side = side;
  261.         tstack_p->backpt[0] = backx;
  262.         tstack_p->backpt[1] = backy;
  263.         tstack_p->backpt[2] = backz;
  264.         
  265.         tstack_p++;
  266.         
  267.         backx = frontx + front*(backx-frontx);
  268.         backy = fronty + front*(backy-fronty);
  269.         backz = frontz + front*(backz-frontz);
  270.         
  271.         node = tnode->children[side];        
  272.     }    
  273. }
  274.  
  275.  
  276.