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