home *** CD-ROM | disk | FTP | other *** search
/ Virtual Reality Zone / VRZONE.ISO / mac / PC / PCGLOVE / GLOVE / OBJGLV.ZIP / SRC / DEMO4B / SUPP / SPLITS.CPP < prev    next >
C/C++ Source or Header  |  1993-04-07  |  10KB  |  445 lines

  1. /* Splitting-tree routines */
  2.  
  3. /* Written by Bernie Roehl, June 1992 */
  4. /* Substantially upgraded by Dave Stampe, August '92 */
  5.  
  6. /* Copyright 1992 by Dave Stampe and Bernie Roehl.
  7.    May be freely used to write software for release into the public domain;
  8.    all commercial endeavours MUST contact Bernie Roehl and Dave Stampe
  9.    for permission to incorporate any part of this software into their
  10.    products!
  11.  */
  12.  
  13. #include <stdio.h>
  14. #include <alloc.h>  /* malloc() */
  15.  
  16. #include "rend386.hpp"
  17. #include "intmath.h"
  18. #include "splitdef.h"
  19.  
  20. /* from intsplit.c */
  21.  
  22. extern int _which_side(SPLIT *s, long tx,long ty,long tz);
  23. extern void *_fast_split_descent(SPLIT *tree, long x, long y, long z, char *type);
  24.  
  25. static AREA *create_area()
  26. {
  27.     AREA *a;
  28.     if ((a = (AREA *)malloc(sizeof(AREA))) == NULL) return NULL;
  29.     a->floor_a = 0;
  30.     a->floor_b = 1;
  31.     a->floor_c = 0;
  32.     a->floor_d = 0;
  33.     a->ceiling_a = 0;
  34.     a->ceiling_b = 1;
  35.     a->ceiling_c = 0;
  36.     a->ceiling_d = 0;
  37.     a->fn = NULL;
  38.     a->visfrom = NULL;
  39.     a->ptr = new_objlist();
  40.     a->has_tree = 0;
  41.     return a;
  42. }
  43.  
  44. SPLIT *add_split(SPLIT **tree, long x, long y, long z,
  45.     long nx, long ny, long nz, unsigned flags)
  46. {
  47.     if (*tree == NULL) {
  48.         if ((*tree = (SPLIT *)malloc(sizeof(SPLIT))) == NULL) return NULL;
  49.         (*tree)->x = x; 
  50.         (*tree)->y = y; 
  51.         (*tree)->z = z;
  52.         (*tree)->nx = nx; 
  53.         (*tree)->ny = ny; 
  54.         (*tree)->nz = nz;
  55.         (*tree)->olist = new_objlist();
  56.         (*tree)->left_type = (*tree)->right_type = ISAREA;
  57.         (*tree)->left = create_area();
  58.         (*tree)->right = create_area();
  59.         (*tree)->flags = flags;
  60.         return (*tree);
  61.     }
  62.     if (_which_side(*tree, x, y, z) < 0) {
  63.         if ((*tree)->left_type == ISAREA) {
  64.             free((*tree)->left);
  65.             (*tree)->left = NULL;
  66.         }
  67.         (*tree)->left_type = ISSPLIT;
  68.         return add_split(&((SPLIT *)(*tree)->left), x, y, z, nx, ny, nz, flags);
  69.     }
  70.     if ((*tree)->right_type == ISAREA) {
  71.         free((*tree)->right);
  72.         (*tree)->right = NULL;
  73.     }
  74.     (*tree)->right_type = ISSPLIT;
  75.     return add_split(&((SPLIT *)(*tree)->right), x, y, z, nx, ny, nz, flags);
  76. }
  77.  
  78. static SPLIT *what_split(SPLIT *tree, long x, long y, long z)
  79. {
  80.     int n;
  81.     while (tree) {
  82.         n = _which_side(tree, x, y, z);
  83.         if (n == 0) break;
  84.         if (n < 0) {
  85.             if (tree->left_type != ISSPLIT) return NULL;
  86.             else tree = (SPLIT *)tree->left;
  87.         }
  88.         else {
  89.             if (tree->right_type != ISSPLIT) return NULL;
  90.             else tree = (SPLIT *)tree->right;
  91.         }
  92.     }
  93.     return tree;
  94. }
  95.  
  96. AREA *what_area(SPLIT *tree, long x, long y, long z)
  97. {
  98.     char n;
  99.     return ((AREA *)(_fast_split_descent(tree,x,y,z,&n)));
  100. }
  101.  
  102. void add_obj_to_area(AREA *a, OBJECT *obj)
  103. {
  104.     if (a) add_to_objlist((OBJLIST *)a->ptr, obj);
  105. }
  106.  
  107. void add_obj_to_split_center(SPLIT *s, OBJECT *obj)
  108. {
  109.     if (s) add_to_objlist(s->olist, obj);
  110. }
  111.  
  112. void add_obj_to_split(SPLIT *tree, OBJECT *obj)
  113. { /* area OR on split */
  114.     SPLIT *s;
  115.     long x, y, z;
  116.     char t;
  117.     get_object_bounds(obj, &x, &y, &z);
  118.     if ((s = what_split(tree, x, y, z)) != NULL)
  119.         add_to_objlist(s->olist, obj);
  120.     else
  121.         add_obj_to_area((AREA *)_fast_split_descent(tree, x, y, z, &t), obj);
  122. }
  123.  
  124. void add_obj_to_split_area(SPLIT *tree, OBJECT *obj)
  125. {
  126.     SPLIT *s; /* in area only */
  127.     long x, y, z; /* use during move */
  128.     char t;
  129.     get_object_bounds(obj, &x, &y, &z);
  130.     add_obj_to_area((AREA *)_fast_split_descent(tree, x, y, z, &t), obj);
  131. }
  132.  
  133. OBJLIST *which_area_objlist(SPLIT *tree, long x, long y, long z)
  134. {
  135.     char t;
  136.     AREA *a;
  137.  
  138.     if (tree == NULL) return NULL;
  139.     a = (AREA *)_fast_split_descent(tree, x, y, z, &t);
  140.     if (a == NULL || t!=ISAREA) return NULL;
  141.     return ((OBJLIST *)(a->ptr));
  142. }
  143.  
  144. OBJLIST *which_objlist(SPLIT *tree, long x, long y, long z)
  145. {
  146.     int n;
  147.  
  148.     if (tree == NULL) return NULL;
  149.  
  150.     while (tree)
  151.     {
  152.         n = _which_side(tree, x, y, z);
  153.         if (n == 0) return tree->olist; /* center of split */
  154.         if (n < 0)
  155.         { /* area left of split */
  156.             if (tree->left_type == ISSPLIT) tree = (SPLIT *)(tree->left);
  157.             else return ((OBJLIST *)(((AREA *)(tree->left))->ptr));
  158.         }
  159.         else
  160.             { /* area right of split */
  161.             if (tree->right_type == ISSPLIT) tree = (SPLIT *)tree->right;
  162.             else return ((OBJLIST *)(((AREA *)(tree->right))->ptr));
  163.         }
  164.     }
  165.     return NULL;
  166. }
  167.  
  168.  
  169. SPLIT **global_split_root = NULL;
  170.  
  171. void set_global_split_root(SPLIT **split_tree)
  172. {
  173.     global_split_root = split_tree;
  174. }
  175.  
  176.  
  177. void initial_world_split(SPLIT **split_ptr)
  178. {
  179.     set_global_split_root(split_ptr);
  180.     add_split(split_ptr, 0x3FFFFFFF, 0, 0, 1, 0, 0, 0);
  181. }
  182.  
  183.  
  184. void split_move_handler(OBJECT *obj)
  185. { /* split tree move */
  186.     if (global_split_root)
  187.     {
  188.         remove_from_objlist(obj);
  189.         add_obj_to_split_area(*global_split_root, obj);
  190.     }
  191. }
  192.  
  193.  
  194. static OBJECT *objhit = NULL;
  195. static int polyhit = 0;
  196. static int verthit = 0;
  197. static int checkflag = 0;
  198.  
  199. void render_monitor_point(int x, int y)
  200. {
  201.     checkflag = 1;
  202.     objhit = NULL;
  203.     set_screen_monitor(x, y);
  204. }
  205.  
  206. OBJECT *render_check_monitor(int *poly, int *vert)
  207. {
  208.     if (objhit)
  209.     {
  210.         if (poly) *poly = polyhit;
  211.         if (vert) *vert = verthit;
  212.     }
  213.     checkflag = 0;
  214.     clear_screen_monitor();
  215.     return objhit;
  216. }
  217.  
  218. void render_objlist(OBJLIST *objlist)
  219. {
  220.     if (objlist == NULL) return;
  221.     subrender(objlist);
  222.     if (checkflag)
  223.     {
  224.         OBJECT *t = locate_screen_pt(&polyhit, &verthit);
  225.         if (t) objhit = t;
  226.     }
  227. }
  228.  
  229. void render_area(AREA *a)
  230. {
  231.     if (a == NULL) return;
  232.     subrender((OBJLIST *)a->ptr);
  233.     if (checkflag)
  234.     {
  235.         OBJECT *t = locate_screen_pt(&polyhit, &verthit);
  236.         if (t) objhit = t;
  237.     }
  238. }
  239.  
  240. void render_split(SPLIT *tree, VIEW *view);
  241.  
  242. void render_subtree(int type, void *ptr, VIEW *view)
  243. {
  244.     switch (type) {
  245.         case ISAREA:
  246.             render_area((AREA *)ptr); 
  247.             break;
  248.         case ISOBJLIST:
  249.             subrender((OBJLIST *)ptr);
  250.             if (checkflag) {
  251.                 OBJECT *t = locate_screen_pt(&polyhit, &verthit);
  252.                 if (t) objhit = t;
  253.             }
  254.             break;
  255.         case ISSPLIT:
  256.         default:
  257.             render_split((SPLIT *)ptr, view);
  258.             break;
  259.     }
  260. }
  261.  
  262. void render_split(SPLIT *tree, VIEW *view)
  263. {
  264.     if (tree == NULL) return;
  265.     if (_which_side(tree, view->ex, view->ey, view->ez) < 0)
  266.     {
  267.         render_subtree(tree->right_type, tree->right, view);
  268.         subrender(tree->olist);
  269.         if (checkflag) {
  270.             OBJECT *t = locate_screen_pt(&polyhit, &verthit);
  271.             if (t) objhit = t;
  272.         }
  273.         render_subtree(tree->left_type, tree->left, view);
  274.     }
  275.     else {
  276.         render_subtree(tree->left_type, tree->left, view);
  277.         subrender(tree->olist);
  278.         if (checkflag) {
  279.             OBJECT *t = locate_screen_pt(&polyhit, &verthit);
  280.             if (t) objhit = t;
  281.         }
  282.         render_subtree(tree->right_type, tree->right, view);
  283.     }
  284. }
  285.  
  286. void render_visareas(AREA *area)
  287. {
  288.     AREA_REF *a;
  289.     for (a = area->visfrom; a; a = a->next)
  290.         render_area(a->area);
  291.     render_area(area);
  292. }
  293.  
  294. void walk_area(AREA *a, void (*fn)(OBJECT *))
  295. {
  296.     if (a) walk_objlist((OBJLIST *)a->ptr, fn);
  297. }
  298.  
  299. void walk_split_tree(SPLIT *tree, void (*fn)(OBJECT *))
  300. {
  301.     if (tree == NULL) return;
  302.     switch (tree->left_type) {
  303.         case ISSPLIT:
  304.             walk_split_tree((SPLIT *)tree->left, fn);
  305.             break;
  306.         case ISAREA:
  307.             walk_area((AREA *)tree->left, fn); 
  308.             break;
  309.         case ISOBJLIST:
  310.             walk_objlist((OBJLIST *)tree->left, fn); 
  311.             break;
  312.     }
  313.     switch (tree->right_type) {
  314.         case ISSPLIT:
  315.             walk_split_tree((SPLIT *)tree->right, fn); 
  316.             break;
  317.         case ISAREA:
  318.             walk_area((AREA *)tree->right, fn); 
  319.             break;
  320.         case ISOBJLIST:
  321.             walk_objlist((OBJLIST *)tree->right, fn); 
  322.             break;
  323.     }
  324.     if (tree->olist) walk_objlist(tree->olist, fn);
  325. }
  326.  
  327. /* Area-related functions */
  328.  
  329. void set_area_function(AREA *a, void (*fn)(AREA *))
  330. {
  331.     if (a) a->fn = fn;
  332. }
  333.  
  334. void call_area_fn(AREA *a)
  335. {
  336.     if (a) if (a->fn) a->fn(a);
  337. }
  338.  
  339. int add_visfrom(AREA *from, AREA *to)
  340. {
  341.     AREA_REF *p;
  342.     if (from == NULL || to == NULL) return -2;
  343.     if ((p = (AREA_REF *)malloc(sizeof(AREA_REF))) == NULL) return -1;
  344.     p->next = from->visfrom;
  345.     from->visfrom = p;
  346.     p->area = to;
  347.     return 0;
  348. }
  349.  
  350. void add_floor(AREA *area, long a, long b, long c, long d)
  351. {
  352.     if (area == NULL) return;
  353.     if (b == 0) b = 1;
  354.     area->floor_a = a; 
  355.     area->floor_b = b; 
  356.     area->floor_c = c; 
  357.     area->floor_d = d;
  358. }
  359.  
  360. void add_ceiling(AREA *area, long a, long b, long c, long d)
  361. {
  362.     if (area == NULL) return;
  363.     if (b == 0) b = 1;
  364.     area->ceiling_a = a; 
  365.     area->ceiling_b = b; 
  366.     area->ceiling_c = c; 
  367.     area->ceiling_d = d;
  368. }
  369.  
  370. long floor_at(AREA *a, long x, long z)
  371. {
  372.     if (a == NULL) return 0;
  373.     /*    return a->floor_a * x + a->floor_c * z + a->floor_d; */
  374.     /*    return dot_prod_29(a->floor_a, a->floor_c, a->floor_d, x, z, 1L); */
  375.     return plane_y(a->floor_a, a->floor_b, a->floor_c, a->floor_d, x, z);
  376. }
  377.  
  378. long ceiling_at(AREA *a, long x, long z)
  379. {
  380.     if (a == NULL) return 0;
  381.     /*    return a->ceiling_a * x + a->ceiling_c * z + a->ceiling_d; */
  382.     /*    return dot_prod_29(a->ceiling_a, a->ceiling_c, a->ceiling_d, x, z); */
  383.     return plane_y(a->ceiling_a, a->ceiling_b, a->ceiling_c, a->ceiling_d, x, z);
  384. }
  385.  
  386. /* DEBUGGING ONLY: */
  387.  
  388. static int count_objlist(OBJLIST *o)
  389. {
  390.     OBJECT *obj;
  391.     int i = 0;
  392.     if (o == NULL) return 0;
  393.     for (obj = first_in_objlist(o); obj; obj = next_in_objlist(obj))
  394.         ++i;
  395.     return i;
  396. }
  397.  
  398. void dump_area(AREA *a, int level)
  399. {
  400.     int i;
  401.     if (a == NULL) return;
  402.     for (i = 0; i < level; ++i) printf("  ");
  403.     printf("Area %c (%d objects)\n", (char) a->floor_a, count_objlist((OBJLIST *)a->ptr));
  404. }
  405.  
  406. void dump_objlist(OBJLIST *o, int level)
  407. {
  408.     int i;
  409.     if (o == NULL) return;
  410.     for (i = 0; i < level; ++i) printf("  ");
  411.     printf("Objlist with %d objects in it\n", count_objlist(o));
  412. }
  413.  
  414. void dump_split_tree(SPLIT *tree, int level)
  415. {
  416.     int i;
  417.     if (tree == NULL) return;
  418.     for (i = 0; i < level; ++i) printf("  ");
  419.     printf("Split %u: %ld,%ld,%ld %ld,%ld,%ld\n", tree->flags,
  420.     tree->x, tree->y, tree->z, tree->nx, tree->ny, tree->nz);
  421.     switch (tree->left_type) {
  422.         case ISSPLIT:
  423.             dump_split_tree((SPLIT *) tree->left, level + 1); 
  424.             break;
  425.         case ISAREA:
  426.             dump_area((AREA *) tree->left, level + 1); 
  427.             break;
  428.         case ISOBJLIST:
  429.             dump_objlist((OBJLIST *) tree->left, level + 1); 
  430.             break;
  431.     }
  432.     switch (tree->right_type) {
  433.         case ISSPLIT:
  434.             dump_split_tree((SPLIT *) tree->right, level + 1); 
  435.             break;
  436.         case ISAREA:
  437.             dump_area((AREA *) tree->right, level + 1); 
  438.             break;
  439.         case ISOBJLIST:
  440.             dump_objlist((OBJLIST *) tree->right, level + 1); 
  441.             break;
  442.     }
  443. }
  444.  
  445.