home *** CD-ROM | disk | FTP | other *** search
/ Virtual Reality Homebrewer's Handbook / vr.iso / vr386 / splits.c < prev    next >
C/C++ Source or Header  |  1996-03-19  |  12KB  |  536 lines
  1. /* Splitting-tree routines:  */
  2.  
  3. /* Original implementation written by Bernie Roehl, June 1992 */
  4.  
  5. /* Substantially upgraded by Dave Stampe, August '92 */
  6. // The theory of splits is to use splitting planes to divide the
  7. // world into "areas", and for visibility sorting.  Objects are
  8. // sorted into areas when they move by descending the split tree
  9. // Fast assembler for descent is in SPLITS.ASM.  The theoretical
  10. // basis for splits was worked out by Dave, and there are a lot
  11. // of unimplemented uses for collision detection and world pruning
  12. // not yet explored.
  13.  
  14. // WORLD-WALKING AND vr-386 api PORT BY dAVE stAMPE, 9/1/94
  15.  
  16. /*
  17.  This code is part of the VR-386 project, created by Dave Stampe.
  18.  VR-386 is a desendent of REND386, created by Dave Stampe and
  19.  Bernie Roehl.  Almost all the code has been rewritten by Dave
  20.  Stampre for VR-386.
  21.  
  22.  Copyright (c) 1994 by Dave Stampe:
  23.  May be freely used to write software for release into the public domain
  24.  or for educational use; all commercial endeavours MUST contact Dave Stampe
  25.  (dstampe@psych.toronto.edu) for permission to incorporate any part of
  26.  this software or source code into their products!  Usually there is no
  27.  charge for under 50-100 items for low-cost or shareware products, and terms
  28.  are reasonable.  Any royalties are used for development, so equipment is
  29.  often acceptable payment.
  30.  
  31.  ATTRIBUTION:  If you use any part of this source code or the libraries
  32.  in your projects, you must give attribution to VR-386 and Dave Stampe,
  33.  and any other authors in your documentation, source code, and at startup
  34.  of your program.  Let's keep the freeware ball rolling!
  35.  
  36.  DEVELOPMENT: VR-386 is a effort to develop the process started by
  37.  REND386, improving programmer access by rewriting the code and supplying
  38.  a standard API.  If you write improvements, add new functions rather
  39.  than rewriting current functions.  This will make it possible to
  40.  include you improved code in the next API release.  YOU can help advance
  41.  VR-386.  Comments on the API are welcome.
  42.  
  43.  CONTACT: dstampe@psych.toronto.edu
  44. */
  45.  
  46.  
  47.  
  48. #include <stdio.h>
  49. #include <alloc.h>  /* malloc() */
  50. #include <string.h>
  51.  
  52. #define SPLDEF 1
  53. #define SPLIT void
  54.  
  55. #include "vr_api.h"
  56. #include "segment.h"
  57. #include "intmath.h"
  58.  
  59. #undef SPLIT
  60. #include "splitdef.h"
  61.  
  62. /* from intsplit.c */
  63.  
  64. extern int _which_side(SPLIT *s, long tx,long ty,long tz);
  65. extern void *_fast_split_descent(SPLIT *tree, long x, long y, long z, char *type);
  66.  
  67. static AREA *create_area(void)
  68. {
  69.   AREA *a;
  70.   if ((a = malloc(sizeof(AREA))) == NULL) return NULL;
  71.   a->floor_a = 0x7FFFFFFFL;
  72.   a->floor_b = 1;
  73.   a->floor_c = 0;
  74.   a->floor_d = 0;
  75.   a->ceiling_a = 0;
  76.   a->ceiling_b = 1;
  77.   a->ceiling_c = 0;
  78.   a->ceiling_d = 0;
  79.   a->fn = NULL;
  80.   a->visfrom = NULL;
  81.   a->ptr = new_objlist();
  82.   a->has_tree = 0;
  83.   a->name = NULL;
  84.   return a;
  85. }
  86.  
  87. SPLIT *add_split(SPLIT **tree, long x, long y, long z,
  88.     long nx, long ny, long nz, unsigned flags)
  89. {
  90.   if (*tree == NULL)  // new split if needed
  91.     {
  92.       if ((*tree = malloc(sizeof(SPLIT))) == NULL) return NULL;
  93.       (*tree)->x = x;
  94.       (*tree)->y = y;
  95.       (*tree)->z = z;
  96.       (*tree)->nx = nx;
  97.       (*tree)->ny = ny;
  98.       (*tree)->nz = nz;
  99.       (*tree)->olist = new_objlist();
  100.       (*tree)->left_type = (*tree)->right_type = ISAREA;
  101.       (*tree)->left = create_area();
  102.       (*tree)->right = create_area();
  103.       (*tree)->flags = flags;
  104.       return (*tree);
  105.     }
  106.   if (_which_side(*tree, x, y, z) < 0)  // left side add
  107.     {
  108.       if ((*tree)->left_type == ISAREA) // replace area
  109.     {
  110.       free((*tree)->left);
  111.       (*tree)->left = NULL;
  112.     }
  113.       (*tree)->left_type = ISSPLIT;
  114.       return add_split(&((SPLIT *)(*tree)->left), x, y, z, nx, ny, nz, flags);
  115.     }
  116.   if ((*tree)->right_type == ISAREA)    // right side add
  117.     {
  118.       free((*tree)->right);
  119.       (*tree)->right = NULL;
  120.     }
  121.   (*tree)->right_type = ISSPLIT;
  122.   return add_split(&((SPLIT *)(*tree)->right), x, y, z, nx, ny, nz, flags);
  123. }
  124.  
  125. static SPLIT *what_split(SPLIT *tree, long x, long y, long z)
  126. {
  127.     int n;
  128.     while (tree) {
  129.         n = _which_side(tree, x, y, z);
  130.         if (n == 0) break;
  131.         if (n < 0) {
  132.             if (tree->left_type != ISSPLIT) return NULL;
  133.             else tree = tree->left;
  134.         }
  135.         else {
  136.             if (tree->right_type != ISSPLIT) return NULL;
  137.             else tree = tree->right;
  138.         }
  139.     }
  140.     return tree;
  141. }
  142.  
  143. AREA *what_area(SPLIT *tree, long x, long y, long z)
  144. {
  145.     char n;
  146.     return _fast_split_descent(tree,x,y,z,&n);
  147. }
  148.  
  149. void add_obj_to_area(AREA *a, OBJECT *obj)
  150. {
  151.     if (a) add_to_objlist(a->ptr, obj);
  152. }
  153.  
  154. void add_obj_to_split_center(SPLIT *s, OBJECT *obj)
  155. {
  156.     if (s) add_to_objlist(s->olist, obj);
  157. }
  158.  
  159. void add_obj_to_split(SPLIT *tree, OBJECT *obj)
  160. { /* area OR on split */
  161.     SPLIT *s;
  162.     long x, y, z;
  163.     char t;
  164.     get_object_bounds(obj, &x, &y, &z);
  165.     if ((s = what_split(tree, x, y, z)) != NULL)
  166.         add_to_objlist(s->olist, obj);
  167.     else
  168.         add_obj_to_area(_fast_split_descent(tree, x, y, z, &t), obj);
  169. }
  170.  
  171. void add_obj_to_split_area(SPLIT *tree, OBJECT *obj)
  172. {
  173.     SPLIT *s; /* in area only */
  174.     long x, y, z; /* use during move */
  175.     char t;
  176.     get_object_bounds(obj, &x, &y, &z);
  177.     add_obj_to_area(_fast_split_descent(tree, x, y, z, &t), obj);
  178. }
  179.  
  180. OBJLIST *which_area_objlist(SPLIT *tree, long x, long y, long z)
  181. {
  182.     char t;
  183.     AREA *a;
  184.  
  185.     if (tree == NULL) return NULL;
  186.     a = _fast_split_descent(tree, x, y, z, &t);
  187.     if (a == NULL || t!=ISAREA) return NULL;
  188.     return a->ptr;
  189. }
  190.  
  191. OBJLIST *which_split_objlist(SPLIT *tree, long x, long y, long z)
  192. {
  193.     int n;
  194.  
  195.     if (tree == NULL) return NULL;
  196.  
  197.     while (tree)
  198.     {
  199.         n = _which_side(tree, x, y, z);
  200.         if (n == 0) return tree->olist; /* center of split */
  201.         if (n < 0)
  202.         { /* area left of split */
  203.             if (tree->left_type == ISSPLIT) tree = tree->left;
  204.             else return ((AREA *)(tree->left))->ptr;
  205.         }
  206.         else
  207.             { /* area right of split */
  208.             if (tree->right_type == ISSPLIT) tree = tree->right;
  209.             else return ((AREA *)(tree->right))->ptr;
  210.         }
  211.     }
  212.     return NULL;
  213. }
  214.  
  215.  
  216. SPLIT *create_initial_world_split()
  217. {
  218.  SPLIT * tree = NULL;
  219.  add_split(&tree, 0x3FFFFFFF, 0, 0, 1, 0, 0, 0);
  220.  return tree;
  221. }
  222.  
  223.  
  224.     // move object in or into split tree
  225.     // ignored if object marked as not
  226.     // part of world or invisible
  227. void split_move_handler(OBJECT *obj)
  228. {
  229.   if (global_world_root)
  230.     if (is_object_visible(obj))
  231.       add_obj_to_split_area(global_world_root, obj);
  232. }
  233.  
  234.  
  235. void render_objlist(OBJLIST *objlist)
  236. {
  237.     if (objlist == NULL) return;
  238.     subrender(objlist);
  239. }
  240.  
  241. void render_area(AREA *a)
  242. {
  243.     if (a == NULL) return;
  244.     subrender(a->ptr);
  245. }
  246.  
  247. void render_subtree(int type, void *ptr, VIEW *view)
  248. {
  249.     void render_split(SPLIT *, VIEW *);
  250.     switch (type)
  251.     {
  252.     case ISAREA:
  253.         render_area(ptr);
  254.         break;
  255.     case ISOBJLIST:
  256.         subrender(ptr);
  257.         break;
  258.     case ISSPLIT:
  259.     default:
  260.         render_split(ptr, view);
  261.         break;
  262.     }
  263. }
  264.  
  265. void render_split(SPLIT *tree, VIEW *view)
  266. {
  267.     long x, y, z;
  268.     if (tree == NULL) return;
  269.     real_viewpoint(view, &x, &y, &z);
  270.     if (_which_side(tree, x, y, z) < 0)
  271.     {
  272.         render_subtree(tree->right_type, tree->right, view);
  273.         subrender(tree->olist);
  274.         render_subtree(tree->left_type, tree->left, view);
  275.     }
  276.     else
  277.         {
  278.         render_subtree(tree->left_type, tree->left, view);
  279.         subrender(tree->olist);
  280.         render_subtree(tree->right_type, tree->right, view);
  281.     }
  282. }
  283.  
  284.  
  285. void render_visareas(AREA *area)
  286. {
  287.     AREA_REF *a;
  288.     for (a = area->visfrom; a; a = a->next)
  289.         render_area(a->area);
  290.     render_area(area);
  291. }
  292.  
  293. ///////// WORLD WALKING
  294.  
  295. void walk_area(AREA *a, void (*fn)())
  296. {
  297.     if (a) walk_objlist(a->ptr, fn);
  298. }
  299.  
  300. void walk_split_tree(SPLIT *tree, void (*fn)())
  301. {
  302.     if (tree == NULL) return;
  303.     switch (tree->left_type) {
  304.     case ISSPLIT:
  305.         walk_split_tree(tree->left, fn);
  306.         break;
  307.     case ISAREA:
  308.         walk_area(tree->left, fn);
  309.         break;
  310.     case ISOBJLIST:
  311.         walk_objlist(tree->left, fn);
  312.         break;
  313.     }
  314.     switch (tree->right_type) {
  315.     case ISSPLIT:
  316.         walk_split_tree(tree->right, fn);
  317.         break;
  318.     case ISAREA:
  319.         walk_area(tree->right, fn);
  320.         break;
  321.     case ISOBJLIST:
  322.         walk_objlist(tree->right, fn);
  323.         break;
  324.     }
  325.     if (tree->olist) walk_objlist(tree->olist, fn);
  326. }
  327.  
  328.  
  329. /// TESTS
  330.  
  331.  
  332. static void (*walkfn)() = NULL;
  333.  
  334. static void selwalk(OBJECT *obj)
  335. {
  336.   if(is_object_selected(obj)) walkfn(obj);
  337. }
  338.  
  339. static void movwalk(OBJECT *obj)
  340. {
  341.   if(is_object_moveable(obj)) walkfn(obj);
  342. }
  343.  
  344. static void fixedwalk(OBJECT *obj)
  345. {
  346.   if(!is_object_moveable(obj)) walkfn(obj);
  347. }
  348.  
  349. static void movselwalk(OBJECT *obj)
  350. {
  351.   if(is_object_moveable(obj)&&is_object_selected(obj)) walkfn(obj);
  352. }
  353.  
  354.  
  355. //////// WORLD TRAVERSALS
  356.  
  357. void do_for_all_not_in_world(void (*fn)())
  358. {
  359.   walk_objlist(inactive_object_list, fn);
  360. }
  361.  
  362. void do_for_all_objects(void (*fn)())
  363. {
  364.   walkfn = fn;
  365.   walk_split_tree(global_world_root, fn);
  366. }
  367.  
  368. void do_for_all_selected(void (*fn)())
  369. {
  370.   walkfn = fn;
  371.   walk_split_tree(global_world_root, selwalk);
  372. }
  373.  
  374. void do_for_all_moveable(void (*fn)())
  375. {
  376.   walkfn = fn;
  377.   walk_split_tree(global_world_root, movwalk);
  378. }
  379.  
  380. void do_for_all_fixed(void (*fn)())
  381. {
  382.   walkfn = fn;
  383.   walk_split_tree(global_world_root, fixedwalk);
  384. }
  385.  
  386. void do_for_all_selected_moveable(void (*fn)())
  387. {
  388.   walkfn = fn;
  389.   walk_split_tree(global_world_root, movselwalk);
  390. }
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398. /* Area-related functions */
  399.  
  400. void set_area_function(AREA *a, void (*fn)())
  401. {
  402.     if (a) a->fn = fn;
  403. }
  404.  
  405. void call_area_fn(AREA *a)
  406. {
  407.     if (a) if (a->fn) a->fn(a);
  408. }
  409.  
  410.  
  411. char *area_name(AREA *a)
  412. {
  413.     if (a) return a->name;
  414.     else return NULL;
  415. }
  416.  
  417.  
  418. char *set_area_name(AREA *a, char *name)
  419. {
  420.     if (a) return a->name = strdup(name);
  421.     return NULL;
  422. }
  423.  
  424. int add_visfrom(AREA *from, AREA *to)
  425. {
  426.     AREA_REF *p;
  427.     if (from == NULL || to == NULL) return -2;
  428.     if ((p = malloc(sizeof(AREA_REF))) == NULL) return -1;
  429.     p->next = from->visfrom;
  430.     from->visfrom = p;
  431.     p->area = to;
  432.     return 0;
  433. }
  434.  
  435. void add_floor(AREA *area, long a, long b, long c, long d)
  436. {
  437.     if (area == NULL) return;
  438.     if (b == 0) b = 1;
  439.     area->floor_a = a; 
  440.     area->floor_b = b; 
  441.     area->floor_c = c; 
  442.     area->floor_d = d;
  443. }
  444.  
  445. void add_ceiling(AREA *area, long a, long b, long c, long d)
  446. {
  447.     if (area == NULL) return;
  448.     if (b == 0) b = 1;
  449.     area->ceiling_a = a; 
  450.     area->ceiling_b = b; 
  451.     area->ceiling_c = c; 
  452.     area->ceiling_d = d;
  453. }
  454.  
  455. long floor_at(AREA *a, long x, long z)
  456. {
  457.     if (a == NULL || a->floor_a==0x7FFFFFFFL) return 0x7FFFFFFFL;
  458.     /*    return a->floor_a * x + a->floor_c * z + a->floor_d; */
  459.     /*    return dot_prod_29(a->floor_a, a->floor_c, a->floor_d, x, z, 1L); */
  460.     return plane_y(a->floor_a, a->floor_b, a->floor_c, a->floor_d, x, z);
  461. }
  462.  
  463. long ceiling_at(AREA *a, long x, long z)
  464. {
  465.     if (a == NULL) return 0;
  466.     /*    return a->ceiling_a * x + a->ceiling_c * z + a->ceiling_d; */
  467.     /*    return dot_prod_29(a->ceiling_a, a->ceiling_c, a->ceiling_d, x, z); */
  468.     return plane_y(a->ceiling_a, a->ceiling_b, a->ceiling_c, a->ceiling_d, x, z);
  469. }
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477. /* DEBUGGING ONLY: */
  478.  
  479. static int count_objlist(OBJLIST *o)
  480. {
  481.     OBJECT *obj;
  482.     int i = 0;
  483.     if (o == NULL) return 0;
  484.     for (obj = first_in_objlist(o); obj; obj = next_in_objlist(obj))
  485.         ++i;
  486.     return i;
  487. }
  488.  
  489. void dump_area(AREA *a, int level)
  490. {
  491.     int i;
  492.     if (a == NULL) return;
  493.     for (i = 0; i < level; ++i) printf("  ");
  494.     printf("Area %c (%d objects)\n", (char) a->floor_a, count_objlist(a->ptr));
  495. }
  496.  
  497. void dump_objlist(OBJLIST *o, int level)
  498. {
  499.     int i;
  500.     if (o == NULL) return;
  501.     for (i = 0; i < level; ++i) printf("  ");
  502.     printf("Objlist with %d objects in it\n", count_objlist(o));
  503. }
  504.  
  505. void dump_split_tree(SPLIT *tree, int level)
  506. {
  507.     int i;
  508.     if (tree == NULL) return;
  509.     for (i = 0; i < level; ++i) printf("  ");
  510.     printf("Split %u: %ld,%ld,%ld %ld,%ld,%ld\n", tree->flags,
  511.     tree->x, tree->y, tree->z, tree->nx, tree->ny, tree->nz);
  512.     switch (tree->left_type) {
  513.     case ISSPLIT:
  514.         dump_split_tree((SPLIT *) tree->left, level + 1); 
  515.         break;
  516.     case ISAREA:
  517.         dump_area((AREA *) tree->left, level + 1); 
  518.         break;
  519.     case ISOBJLIST:
  520.         dump_objlist((OBJLIST *) tree->left, level + 1); 
  521.         break;
  522.     }
  523.     switch (tree->right_type) {
  524.     case ISSPLIT:
  525.         dump_split_tree((SPLIT *) tree->right, level + 1); 
  526.         break;
  527.     case ISAREA:
  528.         dump_area((AREA *) tree->right, level + 1); 
  529.         break;
  530.     case ISOBJLIST:
  531.         dump_objlist((OBJLIST *) tree->right, level + 1); 
  532.         break;
  533.     }
  534. }
  535.  
  536.