home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 23 / IOPROG_23.ISO / SOFT / RAYCAST.ZIP / BSPTREE.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-16  |  8.9 KB  |  301 lines
  1. #include "ray.h"
  2. #include "rayrend.h"
  3. #include "rayvb.h"
  4. #include "bspmove.h"
  5. #include "globals.h"
  6.  
  7. typedef long bsp_stack_node;
  8.  
  9. #define BSP_STACK_LENGTH  1024
  10. #define STOP_TRACE -2
  11. #define NODE_MASK 0x8000
  12.  
  13. #define BSP_LOW_HALF (0x0000FFFF)
  14. #define BSP_HIGH_HALF (0xFFFF0000)
  15.  
  16. #define BSP_START_SECTION (0x00000000)
  17. #define BSP_DO_RIGHT_LEAF (0x00010000)
  18. #define BSP_DO_LEFT_LEAF (0x00020000)
  19. #define BSP_END_SECTION (0x00030000)
  20. #define BSP_NULL_SECTION (0x7fff)
  21.  
  22. // There will be a stack used in the BSP drawing routine to simulate recursion,
  23. // because as we all know, real recursion is too slow to use in games
  24.  
  25. short bsp_stack_size;
  26. bsp_stack_node bsp_stack[BSP_STACK_LENGTH];
  27.  
  28. // Two routines to automate push and poping on BSP stack
  29.  
  30. inline BOOL PushBSPStack(bsp_stack_node push_value) {
  31.  
  32.    if (bsp_stack_size>=BSP_STACK_LENGTH) {
  33.       return TRUE;
  34.    } else {
  35.       bsp_stack[bsp_stack_size]=push_value;
  36.       bsp_stack_size++;
  37.       return FALSE;
  38.    }
  39.  
  40. }
  41.  
  42. inline BOOL PopBSPStack(bsp_stack_node & pop_value) {
  43.  
  44.    if (bsp_stack_size<=0) {
  45.       pop_value=STOP_TRACE;
  46.       return TRUE;
  47.    } else {
  48.       bsp_stack_size--;
  49.       pop_value=bsp_stack[bsp_stack_size];
  50.       return FALSE;
  51.    } /* endif */
  52.  
  53. }
  54.  
  55. inline BOOL On_Right(bsp_node * current_node)
  56. {
  57.    long x1, y1, x2, y2;
  58.    x1=current_node->x1;
  59.    x2=current_node->x2;
  60.    y1=current_node->y1;
  61.    y2=current_node->y2;
  62.    if ( fixedmult((x1-x2),(render_y-(y2<<SHIFT))) >= fixedmult((y1-y2),(render_x-(x2<<SHIFT))) ) {
  63.       return TRUE;
  64.    } else {
  65.       return FALSE;
  66.    } /* endif */
  67. }
  68.  
  69. inline BOOL On_Right(bsp_node * current_node, long base_x, long base_y)
  70. {
  71.    long x1, y1, x2, y2;
  72.    x1=current_node->x1;
  73.    x2=current_node->x2;
  74.    y1=current_node->y1;
  75.    y2=current_node->y2;
  76.    if ( ((x1-x2)*(base_y-y2)) >= ((y1-y2)*(base_x-x2)) ) {
  77.       return TRUE;
  78.    } else {
  79.       return FALSE;
  80.    } /* endif */
  81. }
  82.  
  83. /*
  84.    Visible_Rect
  85.    Tries to determine if a rectangle is in the view range
  86.    May return TRUE on some rects that are out of the cone
  87.    However, it is quick
  88. */
  89.  
  90. inline BOOL Visible_Rect(prectl current_bound)
  91. {
  92.    long left_angle=Get_Angle_Sum(render_view_angle, ANGLE_30);
  93.    if (left_angle < ANGLE_90) {
  94.       if (current_bound->right > (render_x>>SHIFT)) return TRUE;
  95.    } else if (left_angle < ANGLE_180) {
  96.       if (current_bound->top > (render_y>>SHIFT)) return TRUE;
  97.    } else if (left_angle < ANGLE_270) {
  98.       if (current_bound->left < (render_x>>SHIFT)) return TRUE;
  99.    } else {
  100.       if (current_bound->bottom < (render_y>>SHIFT)) return TRUE;
  101.    } /* endif */
  102.    return FALSE;
  103. }
  104.  
  105. // This routine examines the fifthteenth bit of the child node to determine whether they
  106. // are another recursive division, or a drawable subsector
  107.  
  108. inline BOOL IsChildSubSector(USHORT child_num) {
  109.    return (((child_num & NODE_MASK) > 0) ? TRUE : FALSE);
  110. }
  111.  
  112. inline USHORT GetSSIndex(long index) {
  113.     return (USHORT)(index ^ NODE_MASK);
  114. }
  115.  
  116. long Box_Smallest_Node(long x1, long x2, long y1, long y2)
  117. {
  118.    long cur_node_index=bsp_start_node;
  119.    BOOL cur_side, next_side, found_smallest;
  120.    bsp_node * cur_node;
  121.    found_smallest=FALSE;
  122.    while (!IsChildSubSector(cur_node_index)) {
  123.       cur_node=bsp_tree+cur_node_index;
  124.       cur_side=On_Right(cur_node, x1, y1);
  125.       next_side=On_Right(cur_node, x2, y1);
  126.       if (cur_side!=next_side)
  127.          found_smallest=TRUE;
  128.       next_side=On_Right(cur_node, x2, y2);
  129.       if (cur_side!=next_side)
  130.          found_smallest=TRUE;
  131.       next_side=On_Right(cur_node, x1, y2);
  132.       if (cur_side!=next_side)
  133.          found_smallest=TRUE;
  134.       if (found_smallest)
  135.          break;
  136.       else {
  137.          if (cur_side) {
  138.             cur_node_index=cur_node->right_child;
  139.          } else {
  140.             cur_node_index=cur_node->left_child;
  141.          } /* endif */
  142.       }
  143.    }
  144. return cur_node_index;
  145. }
  146.  
  147. ssector * Get_Object_SSector(pobject find_obj, long starting_node_index)
  148. {
  149. long obj_x=find_obj->x;
  150. long obj_y=find_obj->y;
  151. long cur_node_index=starting_node_index;
  152. long x1, y1, x2, y2;
  153. bsp_node * cur_node;
  154. while (!IsChildSubSector(cur_node_index)) {
  155.    cur_node=bsp_tree+cur_node_index;
  156.    x1=cur_node->x1;
  157.    x2=cur_node->x2;
  158.    y1=cur_node->y1;
  159.    y2=cur_node->y2;
  160.    if ( fixedmult((x1-x2),(obj_y-(y2<<SHIFT))) >= fixedmult((y1-y2),(obj_x-(x2<<SHIFT))) ) {
  161.       cur_node_index=cur_node->right_child;
  162.    } else {
  163.       cur_node_index=cur_node->left_child;
  164.    } /* endif */
  165. } /* endwhile */
  166. return (SS_List+GetSSIndex(cur_node_index));
  167. }
  168.  
  169. void BSP_Recursion_Draw()
  170. {
  171.  
  172. /*
  173. This the primary draw routine of the engine. Here's how it works:
  174.  
  175. Move down a recursive tree, which represents a series of divisions in the map.
  176. At each node (for our purposes "NODE X"), test first whether this division is even visible.
  177. If it is, test whether the part on the left side of the division is closer to you.
  178. If it is, then recurse down the left child tree. Other wise, recurse down the right.
  179. At the lowest level are subsectors, which are areas where no wall obscures another.
  180. If the child is one of these, draw and recurse back to NODE 1. 
  181. Then recurse down the to child who side of the division was farther away from you.
  182. When you get back to NODE X again, recurse back up to its parent node.
  183. Stop when you've recursed the whole tree, or when there is no more room on the viewing window
  184.  
  185. This allows for proper depth sorting, as well as efficient front to back drawing.
  186.  
  187. Since true recursion is too slow, we will fake recursion by using a static stack.
  188. The stack nodes will be long numbers. The lower sixteen bits will save the node number.
  189. The upper sixteen bits will save what processing we need to do with that node.
  190.  
  191. Phew! Everybody got that?
  192.  
  193. Revision: It should be noted that the recursor attempts to check whether the children's
  194. bounding boxes are visible, and also no longer uses angles in calculating which
  195. side is in front of you
  196.  
  197. */
  198.  
  199. bsp_stack_size=0;
  200.  
  201. long current_bsp_section=bsp_start_node;
  202. long next_bsp_section;
  203.  
  204. unsigned short low_half; long high_half;
  205. bsp_node * current_node;
  206. prectl front_bound, back_bound;
  207. pssector cur_ss;
  208.  
  209. while ( (current_bsp_section!=STOP_TRACE) && (!VB_EmptyList()) ) {
  210.  
  211.    low_half=(short)(current_bsp_section & BSP_LOW_HALF);
  212.    high_half=current_bsp_section & BSP_HIGH_HALF;
  213.    current_node=bsp_tree+low_half;
  214.  
  215.    switch (high_half) {
  216.       case BSP_DO_RIGHT_LEAF:
  217.  
  218.          current_bsp_section=low_half + BSP_END_SECTION;
  219.          next_bsp_section=(long)current_node->right_child;
  220.  
  221.          // Is child drawable subsector? If so, draw it. Otherwise, save current node on stack and
  222.          // down to child node
  223.  
  224.          if (IsChildSubSector(next_bsp_section)) {
  225.            cur_ss=SS_List+GetSSIndex(next_bsp_section);
  226.            Draw_Sub_Sector(cur_ss);
  227.          } else {
  228.             PushBSPStack((long)current_bsp_section);
  229.             current_bsp_section=next_bsp_section;
  230.          } /* endif */
  231.  
  232.       break;
  233.  
  234.       case BSP_DO_LEFT_LEAF:
  235.  
  236.          current_bsp_section=low_half + BSP_END_SECTION;
  237.          next_bsp_section=(long)current_node->left_child;
  238.  
  239.          // Is child drawable subsector? If so, draw it. Otherwise, save current node on stack and
  240.          // down to child node
  241.  
  242.          if (IsChildSubSector(next_bsp_section)) {
  243.             cur_ss=SS_List+GetSSIndex(next_bsp_section);
  244.             Draw_Sub_Sector(cur_ss);
  245.          } else {
  246.             PushBSPStack((long)current_bsp_section);
  247.             current_bsp_section=next_bsp_section;
  248.          } /* endif */
  249.  
  250.       break;
  251.  
  252.       case BSP_START_SECTION:
  253.  
  254.         if (low_half==BSP_NULL_SECTION) {
  255.            current_bsp_section=low_half + BSP_END_SECTION;
  256.            continue;
  257.            }
  258.  
  259.         if (On_Right(current_node)) {
  260.            front_bound=&(current_node->right_bound);
  261.            back_bound=&(current_node->left_bound);
  262.            next_bsp_section=current_node->right_child;
  263.            current_bsp_section=low_half+BSP_DO_LEFT_LEAF;
  264.         } else {
  265.            front_bound=&(current_node->left_bound);
  266.            back_bound=&(current_node->right_bound);
  267.            next_bsp_section=current_node->left_child;
  268.            current_bsp_section=low_half+BSP_DO_RIGHT_LEAF;
  269.         }
  270.  
  271.         if (!Visible_Rect(back_bound))
  272.            current_bsp_section=low_half+BSP_END_SECTION;
  273.  
  274.         if (!Visible_Rect(front_bound))
  275.            continue;
  276.  
  277.         // Is child drawable subsector? If so, draw it. Otherwise, save current node on stack and
  278.         // down to child node
  279.  
  280.         if (IsChildSubSector(next_bsp_section)) {
  281.            cur_ss=SS_List+GetSSIndex(next_bsp_section);
  282.            Draw_Sub_Sector(cur_ss);
  283.         } else {
  284.            PushBSPStack((long)current_bsp_section);
  285.            current_bsp_section=next_bsp_section;
  286.         } /* endif */
  287.  
  288.      break;
  289.  
  290.      case BSP_END_SECTION:
  291.         PopBSPStack(current_bsp_section);
  292.      break;
  293.  
  294.      default:
  295.         return;
  296.    } /* end switch */
  297.  
  298. } /* endwhile */
  299.  
  300. }
  301.