home *** CD-ROM | disk | FTP | other *** search
/ Virtual Reality Zone / VRZONE.ISO / mac / PC / REND386 / DEVEL5 / SPLITS.C < prev    next >
C/C++ Source or Header  |  1992-09-17  |  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.  
  14. #include <stdio.h>
  15. #include <alloc.h>  /* malloc() */
  16.  
  17. #include "../include/rend386.h"
  18. #include "../include/intmath.h"
  19. #include "../include/splitdef.h"
  20.  
  21. /* from intsplit.c */
  22.  
  23. extern int _which_side(SPLIT *s, long tx,long ty,long tz);
  24. extern void *_fast_split_descent(SPLIT *tree, long x, long y, long z, char *type);
  25.  
  26. static AREA *create_area()
  27. {
  28.     AREA *a;
  29.     if ((a = malloc(sizeof(AREA))) == NULL) return NULL;
  30.     a->floor_a = 0;
  31.     a->floor_b = 1;
  32.     a->floor_c = 0;
  33.     a->floor_d = 0;
  34.     a->ceiling_a = 0;
  35.     a->ceiling_b = 1;
  36.     a->ceiling_c = 0;
  37.     a->ceiling_d = 0;
  38.     a->fn = NULL;
  39.     a->visfrom = NULL;
  40.     a->ptr = new_objlist();
  41.     a->has_tree = 0;
  42.     return a;
  43. }
  44.  
  45. SPLIT *add_split(SPLIT **tree, long x, long y, long z,
  46.     long nx, long ny, long nz, unsigned flags)
  47. {
  48.     if (*tree == NULL) {
  49.         if ((*tree = malloc(sizeof(SPLIT))) == NULL) return NULL;
  50.         (*tree)->x = x; 
  51.         (*tree)->y = y; 
  52.         (*tree)->z = z;
  53.         (*tree)->nx = nx; 
  54.         (*tree)->ny = ny; 
  55.         (*tree)->nz = nz;
  56.         (*tree)->olist = new_objlist();
  57.         (*tree)->left_type = (*tree)->right_type = ISAREA;
  58.         (*tree)->left = create_area();
  59.         (*tree)->right = create_area();
  60.         (*tree)->flags = flags;
  61.         return (*tree);
  62.     }
  63.     if (_which_side(*tree, x, y, z) < 0) {
  64.         if ((*tree)->left_type == ISAREA) {
  65.             free((*tree)->left);
  66.             (*tree)->left = NULL;
  67.         }
  68.         (*tree)->left_type = ISSPLIT;
  69.         return add_split(&((SPLIT *)(*tree)->left), x, y, z, nx, ny, nz, flags);
  70.     }
  71.     if ((*tree)->right_type == ISAREA) {
  72.         free((*tree)->right);
  73.         (*tree)->right = NULL;
  74.     }
  75.     (*tree)->right_type = ISSPLIT;
  76.     return add_split(&((SPLIT *)(*tree)->right), x, y, z, nx, ny, nz, flags);
  77. }
  78.  
  79. static SPLIT *what_split(SPLIT *tree, long x, long y, long z)
  80. {
  81.     int n;
  82.     while (tree) {
  83.         n = _which_side(tree, x, y, z);
  84.         if (n == 0) break;
  85.         if (n < 0) {
  86.             if (tree->left_type != ISSPLIT) return NULL;
  87.             else tree = tree->left;
  88.         }
  89.         else {
  90.             if (tree->right_type != ISSPLIT) return NULL;
  91.             else tree = tree->right;
  92.         }
  93.     }
  94.     return tree;
  95. }
  96.  
  97. AREA *what_area(SPLIT *tree, long x, long y, long z)
  98. {
  99.     char n;
  100.     return _fast_split_descent(tree,x,y,z,&n);
  101. }
  102.  
  103. void add_obj_to_area(AREA *a, OBJECT *obj)
  104. {
  105.     if (a) add_to_objlist(a->ptr, obj);
  106. }
  107.  
  108. void add_obj_to_split_center(SPLIT *s, OBJECT *obj)
  109. {
  110.     if (s) add_to_objlist(s->olist, obj);
  111. }
  112.  
  113. void add_obj_to_split(SPLIT *tree, OBJECT *obj)
  114. { /* area OR on split */
  115.     SPLIT *s;
  116.     long x, y, z;
  117.     char t;
  118.     get_object_bounds(obj, &x, &y, &z);
  119.     if ((s = what_split(tree, x, y, z)) != NULL)
  120.         add_to_objlist(s->olist, obj);
  121.     else
  122.         add_obj_to_area(_fast_split_descent(tree, x, y, z, &t), obj);
  123. }
  124.  
  125. void add_obj_to_split_area(SPLIT *tree, OBJECT *obj)
  126. {
  127.     SPLIT *s; /* in area only */
  128.     long x, y, z; /* use during move */
  129.     char t;
  130.     get_object_bounds(obj, &x, &y, &z);
  131.     add_obj_to_area(_fast_split_descent(tree, x, y, z, &t), obj);
  132. }
  133.  
  134. OBJLIST *which_area_objlist(SPLIT *tree, long x, long y, long z)
  135. {
  136.     char t;
  137.     AREA *a;
  138.  
  139.     if (tree == NULL) return NULL;
  140.     a = _fast_split_descent(tree, x, y, z, &t);
  141.     if (a == NULL || t!=ISAREA) return NULL;
  142.     return a->ptr;
  143. }
  144.  
  145. OBJLIST *which_objlist(SPLIT *tree, long x, long y, long z)
  146. {
  147.     int n;
  148.  
  149.     if (tree == NULL) return NULL;
  150.  
  151.     while (tree)
  152.     {
  153.         n = _which_side(tree, x, y, z);
  154.         if (n == 0) return tree->olist; /* center of split */
  155.         if (n < 0)
  156.         { /* area left of split */
  157.             if (tree->left_type == ISSPLIT) tree = tree->left;
  158.             else return ((AREA *)(tree->left))->ptr;
  159.         }
  160.         else
  161.             { /* area right of split */
  162.             if (tree->right_type == ISSPLIT) tree = tree->right;
  163.             else return ((AREA *)(tree->right))->ptr;
  164.         }
  165.     }
  166.     return NULL;
  167. }
  168.  
  169.  
  170. SPLIT **global_split_root = NULL;
  171.  
  172. void set_global_split_root(SPLIT **split_tree)
  173. {
  174.     global_split_root = split_tree;
  175. }
  176.  
  177.  
  178. void initial_world_split(SPLIT **split_ptr)
  179. {
  180.     set_global_split_root(split_ptr);
  181.     add_split(split_ptr, 0x3FFFFFFF, 0, 0, 1, 0, 0, 0);
  182. }
  183.  
  184.  
  185. void split_move_handler(OBJECT *obj)
  186. { /* split tree move */
  187.     if (global_split_root)
  188.     {
  189.         remove_from_objlist(obj);
  190.         add_obj_to_split_area(*global_split_root, obj);
  191.     }
  192. }
  193.  
  194.  
  195. static OBJECT *objhit = NULL;
  196. static int polyhit = 0;
  197. static int verthit = 0;
  198. static int checkflag = 0;
  199.  
  200. void render_monitor_point(int x, int y)
  201. {
  202.     checkflag = 1;
  203.     objhit = NULL;
  204.     set_screen_monitor(x, y);
  205. }
  206.  
  207. OBJECT *render_check_monitor(int *poly, int *vert)
  208. {
  209.     if (objhit)
  210.     {
  211.         if (poly) *poly = polyhit;
  212.         if (vert) *vert = verthit;
  213.     }
  214.     checkflag = 0;
  215.     clear_screen_monitor();
  216.     return objhit;
  217. }
  218.  
  219. void render_objlist(OBJLIST *objlist)
  220. {
  221.     if (objlist == NULL) return;
  222.     subrender(objlist);
  223.     if (checkflag)
  224.     {
  225.         OBJECT *t = locate_screen_pt(&polyhit, &verthit);
  226.         if (t) objhit = t;
  227.     }
  228. }
  229.  
  230. void render_area(AREA *a)
  231. {
  232.     if (a == NULL) return;
  233.     subrender(a->ptr);
  234.     if (checkflag)
  235.     {
  236.         OBJECT *t = locate_screen_pt(&polyhit, &verthit);
  237.         if (t) objhit = t;
  238.     }
  239. }
  240.  
  241. void render_subtree(int type, void *ptr, VIEW *view)
  242. {
  243.     void render_split();
  244.     switch (type) {
  245.         case ISAREA:
  246.             render_area(ptr); 
  247.             break;
  248.         case ISOBJLIST:
  249.             subrender(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(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)())
  295. {
  296.     if (a) walk_objlist(a->ptr, fn);
  297. }
  298.  
  299. void walk_split_tree(SPLIT *tree, void (*fn)())
  300. {
  301.     if (tree == NULL) return;
  302.     switch (tree->left_type) {
  303.         case ISSPLIT:
  304.             walk_split_tree(tree->left, fn); 
  305.             break;
  306.         case ISAREA:
  307.             walk_area(tree->left, fn); 
  308.             break;
  309.         case ISOBJLIST:
  310.             walk_objlist(tree->left, fn); 
  311.             break;
  312.     }
  313.     switch (tree->right_type) {
  314.         case ISSPLIT:
  315.             walk_split_tree(tree->right, fn); 
  316.             break;
  317.         case ISAREA:
  318.             walk_area(tree->right, fn); 
  319.             break;
  320.         case ISOBJLIST:
  321.             walk_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)())
  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 = 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(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.