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