home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Applications / RTrace 1.0 / source / enclose.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-04  |  14.8 KB  |  516 lines  |  [TEXT/KAHL]
  1. /*
  2.  * Copyright (c) 1988, 1992 Antonio Costa, INESC-Norte.
  3.  * All rights reserved.
  4.  *
  5.  * This code received contributions from the following people:
  6.  *
  7.  *  Roman Kuchkuda      - basic ray tracer
  8.  *  Mark VandeWettering - MTV ray tracer
  9.  *  Augusto Sousa       - overall, shading model
  10.  *  Reid Judd        - corrections
  11.  *
  12.  * Redistribution and use in source and binary forms are permitted
  13.  * provided that the above copyright notice and this paragraph are
  14.  * duplicated in all such forms and that any documentation,
  15.  * advertising materials, and other materials related to such
  16.  * distribution and use acknowledge that the software was developed
  17.  * by Antonio Costa, at INESC-Norte. The name of the author and
  18.  * INESC-Norte may not be used to endorse or promote products derived
  19.  * from this software without specific prior written permission.
  20.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  21.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  22.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  23.  */
  24. #include "defs.h"
  25. #include "extern.h"
  26.  
  27. /**********************************************************************
  28.  *    RAY TRACING - Enclose - Version 7.3.1                           *
  29.  *                                                                    *
  30.  *    MADE BY    : Antonio Costa, INESC-Norte, October 1988           *
  31.  *    ADAPTED BY : Antonio Costa, INESC-Norte, June 1989              *
  32.  *    MODIFIED BY: Antonio Costa, INESC-Norte, July 1992              *
  33.  **********************************************************************/
  34.  
  35. /***** Enclosing box *****/
  36. static int
  37. find_axis(first, last)
  38.   int             first, last;
  39. {
  40.   REG int         i, axis;
  41.   REG real        delta;
  42.   xyz_struct      min, max;
  43.  
  44.   STRUCT_ASSIGN(min, *(object[first]->min));
  45.   STRUCT_ASSIGN(max, *(object[first]->max));
  46.   for (i = SUCC(first); i <= last; POSINC(i))
  47.   {
  48.     if (object[i]->min->x < min.x)
  49.       min.x = object[i]->min->x;
  50.     if (object[i]->max->x > max.x)
  51.       max.x = object[i]->max->x;
  52.     if (object[i]->min->y < min.y)
  53.       min.y = object[i]->min->y;
  54.     if (object[i]->max->y > max.y)
  55.       max.y = object[i]->max->y;
  56.     if (object[i]->min->z < min.z)
  57.       min.z = object[i]->min->z;
  58.     if (object[i]->max->z > max.z)
  59.       max.z = object[i]->max->z;
  60.   }
  61.   delta = max.x - min.x;
  62.   axis = X_AXIS;
  63.   if (max.y - min.y > delta)
  64.   {
  65.     delta = max.y - min.y;
  66.     axis = Y_AXIS;
  67.   }
  68.   if (max.z - min.z > delta)
  69.     return Z_AXIS;
  70.   return axis;
  71. }
  72. static boolean
  73. compare(axis, first, second)
  74.   int             axis, first, second;
  75. {
  76.   REG real        sum1, sum2;
  77.  
  78.   switch (axis)
  79.   {
  80.   case X_AXIS:
  81.     sum1 = object[first]->min->x + object[first]->max->x;
  82.     sum2 = object[second]->min->x + object[second]->max->x;
  83.     break;
  84.   case Y_AXIS:
  85.     sum1 = object[first]->min->y + object[first]->max->y;
  86.     sum2 = object[second]->min->y + object[second]->max->y;
  87.     break;
  88.   case Z_AXIS:
  89.     sum1 = object[first]->min->z + object[first]->max->z;
  90.     sum2 = object[second]->min->z + object[second]->max->z;
  91.     break;
  92.   }
  93.   return (boolean) (sum1 <= sum2);
  94. }
  95. static void
  96. sort(axis, first, size)
  97.   int             axis, first, size;
  98. /***** Shell Sort *****/
  99. {
  100.   REG int         step, i, j, first0;
  101.   object_ptr      temp;
  102.  
  103.   step = size DIV 2;
  104.   POSDEC(size);
  105.   while (step > 0)
  106.   {
  107.     for (i = step; i <= size; POSINC(i))
  108.     {
  109.       j = i - step;
  110.       while (j >= 0)
  111.         if (compare(axis, first + j, first + j + step))
  112.           break;                /* already in order */
  113.         else
  114.         {
  115.           /* Out of order, so exchange */
  116.           first0 = first + j;
  117.           temp = object[first0];
  118.           object[first0] = object[first0 + step];
  119.           object[first0 + step] = temp;
  120.           /* Check previous */
  121.           j = j - step;
  122.         }
  123.     }
  124.     step = step DIV 2;
  125.   }
  126. }
  127. static void
  128. sort_and_split(first, last)
  129.   REG int         first, last;
  130. {
  131.   REG int         i, size, axis;
  132.   xyz_struct      min, max;
  133.   cluster_ptr     cluster;
  134.  
  135.   /* Find axis to sort */
  136.   axis = find_axis(first, last);
  137.   size = SUCC(last - first);
  138.   /* Sort objects according to axis */
  139.   sort(axis, first, size);
  140.   if (size <= cluster_size)
  141.   {
  142.     /* Put objects in Cluster */
  143.     ALLOCATE(cluster, cluster_struct, 1);
  144.     ALLOCATE(cluster->object, void_ptr, size);
  145.     cluster->size = size;
  146.     for (i = 0; i < size; POSINC(i))
  147.       cluster->object[i] = (void_ptr) (object[first + i]);
  148.     POSINC(objects);
  149.     if (objects >= OBJECTS_MAX)
  150.       runtime_abort("too many OBJECTS and CLUSTERS");
  151.     ALLOCATE(object[objects], object_struct, 1);
  152.     object[objects]->id = objects;
  153.     object[objects]->object_type = CLUSTER_TYPE;
  154.     object[objects]->transf = NULL;
  155.     object[objects]->inv_transf = NULL;
  156.     object[objects]->texture = NULL;
  157.     object[objects]->data = (void_ptr) cluster;
  158.     ALLOCATE(object[objects]->min, xyz_struct, 1);
  159.     ALLOCATE(object[objects]->max, xyz_struct, 1);
  160.     STRUCT_ASSIGN(min, *(((object_ptr) (cluster->object[0]))->min));
  161.     STRUCT_ASSIGN(max, *(((object_ptr) (cluster->object[0]))->max));
  162.     for (i = 1; i < size; POSINC(i))
  163.     {
  164.     
  165.         PROCESS_MAC_EVENT
  166.  
  167.       if (((object_ptr) (cluster->object[i]))->min->x < min.x)
  168.         min.x = ((object_ptr) (cluster->object[i]))->min->x;
  169.       if (((object_ptr) (cluster->object[i]))->max->x > max.x)
  170.         max.x = ((object_ptr) (cluster->object[i]))->max->x;
  171.       if (((object_ptr) (cluster->object[i]))->min->y < min.y)
  172.         min.y = ((object_ptr) (cluster->object[i]))->min->y;
  173.       if (((object_ptr) (cluster->object[i]))->max->y > max.y)
  174.         max.y = ((object_ptr) (cluster->object[i]))->max->y;
  175.       if (((object_ptr) (cluster->object[i]))->min->z < min.z)
  176.         min.z = ((object_ptr) (cluster->object[i]))->min->z;
  177.       if (((object_ptr) (cluster->object[i]))->max->z > max.z)
  178.         max.z = ((object_ptr) (cluster->object[i]))->max->z;
  179.     }
  180.     STRUCT_ASSIGN(*(object[objects]->min), min);
  181.     STRUCT_ASSIGN(*(object[objects]->max), max);
  182.     ROOT_OBJECT = object[objects];
  183.   } else
  184.   {
  185.     i = (first + last) DIV 2;
  186.     sort_and_split(first, i);
  187.     sort_and_split(SUCC(i), last);
  188.   }
  189. }
  190.  
  191. #define CSG_LEVEL1_MAX (OBJECTS_MAX / 3)
  192. #define CSG_LEVEL2_MAX (OBJECTS_MAX - 1)
  193.  
  194. static void
  195. csg_copy(csg_object, csg_objects_ptr, node)
  196.   object_ptr     *csg_object;
  197.   int            *csg_objects_ptr, node;
  198. {
  199.   csg_ptr         csg;
  200.  
  201.   if (object[node] == NULL)
  202.     runtime_abort("invalid CSG TREE (empty NODE)");
  203.   if (*csg_objects_ptr >= CSG_LEVEL2_MAX)
  204.     runtime_abort("too many CSG secondary NODES");
  205.   csg_object[*csg_objects_ptr] = object[node];
  206.   POSINC(*csg_objects_ptr);
  207.   if (object[node]->object_type != CSG_TYPE)
  208.   {
  209.     object[node] = NULL;
  210.     return;
  211.   }
  212.   csg = (csg_ptr) object[node]->data;
  213.   object[node] = NULL;
  214.   node = csg->left;
  215.   csg->left = *csg_objects_ptr;
  216.   csg_copy(csg_object, csg_objects_ptr, node);
  217.   node = csg->right;
  218.   csg->right = *csg_objects_ptr;
  219.   csg_copy(csg_object, csg_objects_ptr, node);
  220. }
  221. void
  222. validate_object(object, id)
  223.   object_ptr      object;
  224.   int             id;
  225. {
  226.   object->id = id;
  227.   if ((object->transf == NULL) AND(object->inv_transf != NULL))
  228.   {
  229.     FREE(object->inv_transf);
  230.     object->inv_transf = NULL;
  231.   }
  232.   if (object->transf != NULL)
  233.     normalize_transform(object->transf);
  234.   if (object->inv_transf != NULL)
  235.     normalize_transform(object->inv_transf);
  236. }
  237. void
  238. enclose_all()
  239. {
  240.   REG int         i, j, total, first, last;
  241.   int             main_objects, csg_created;
  242.   int             csg_removed, non_csg_removed, csg_union_removed;
  243.   int             csg_prim_objects, csg_sec_objects;
  244.   csg_ptr         csg;
  245.   texture_ptr     texture, old_texture;
  246.  
  247. #ifdef THINK_C
  248.     
  249.     /* The macintosh dynamically determines OBJECTS_MAX, which determines
  250.         CSG_LEVELn_MAX.  So we must dynamically allocate the arrays */
  251.  
  252.     object_ptr    *csg_prim_object;
  253.     object_ptr    *csg_sec_object;
  254.       
  255.     ALLOCATE (csg_prim_object, object_ptr, CSG_LEVEL1_MAX);
  256.     ALLOCATE (csg_sec_object, object_ptr, CSG_LEVEL1_MAX);
  257.  
  258.  
  259.     /* Also update the status window to say we're enclosing */
  260.     if (status_dialog_visible) set_status_text("\pEnclosing Objects…");
  261.     
  262.     /* Set the maximum value of the progress bar to be the number of objects */
  263.     set_progress_bar_max(objects);
  264.  
  265. #else
  266.  
  267.   object_ptr      csg_prim_object[CSG_LEVEL1_MAX];
  268.   object_ptr      csg_sec_object[CSG_LEVEL2_MAX];
  269.  
  270. #endif
  271.  
  272.   total = 0;
  273.   for (i = 1; i <= objects; POSINC(i))
  274.   {
  275.   
  276. #ifdef THINK_C
  277.  
  278.     /* On the mac, we update the progress bar periodically to show the number
  279.         of objects read */
  280.     if (status_dialog_visible) set_progress_bar_value(i);
  281.  
  282.     PROCESS_MAC_EVENT
  283.  
  284. #endif
  285.  
  286.     OBJECT_ENCLOSE(object[i]);
  287.     if (CHECK_BOUNDS(object[i]->object_type))
  288.       POSINC(total);
  289.     if (object[i]->texture != NULL)
  290.     {
  291.       for(texture = object[i]->texture; texture != NULL;
  292.           texture = (texture_ptr) texture->next)
  293.         if (MODIFY_NORMAL(texture->type))
  294.         {
  295.           object[i]->texture_modify_normal = TRUE;
  296.           break;
  297.         }
  298.     }
  299.   }
  300.   /* Enclose CSG objects; must be from last to first */
  301.   csg_created = 0;
  302.   csg_removed = 0;
  303.   non_csg_removed = 0;
  304.   for (i = objects; i > 0; POSDEC(i))
  305.     if (object[i]->object_type == CSG_TYPE)
  306.     {
  307.       POSINC(csg_created);
  308.       csg_enclose(i, &csg_removed, &non_csg_removed);
  309.  
  310.     PROCESS_MAC_EVENT
  311.  
  312.     }
  313.   if (verbose_mode > 1)
  314.   {
  315.     if (total > 0)
  316.       WRITE(results, "%d Object bounding volume(s) computed\n", total);
  317.     if (csg_created > 0)
  318.       WRITE(results, "%d CSG object(s) created\n", csg_created);
  319.     if (csg_removed > 0)
  320.       WRITE(results, "%d CSG object(s) removed\n", csg_removed);
  321.     if (non_csg_removed > 0)
  322.       WRITE(results, "%d Primitive object(s) removed\n", non_csg_removed);
  323.     FLUSH(results);
  324.   }
  325.   main_objects = objects;
  326.   if (csg_created > 0)
  327.   {
  328.     /* Rearrange object list; CSG objects are not processed */
  329.     csg_prim_objects = 0;
  330.     csg_sec_objects = 0;
  331.     csg_union_removed = 0;
  332.     if (csg_created > csg_removed)
  333.       for (i = 1; i <= objects; POSINC(i))
  334.       {
  335.  
  336.         PROCESS_MAC_EVENT
  337.  
  338.         if ((object[i] == NULL) OR(object[i]->object_type != CSG_TYPE))
  339.           continue;
  340.         csg = (csg_ptr) object[i]->data;
  341.         /* Convert CSG union objects to normal objects */
  342.         if ((csg->op == CSG_UNION)
  343.             AND(object[i]->surface_id < 0)
  344.         AND(object[i]->refraction < 0.0)
  345.         AND(object[i]->texture == NULL)
  346.         AND(object[i]->transf == NULL))
  347.         {
  348.           /* Remove this CSG object */
  349.           FREE(object[i]->min);
  350.           FREE(object[i]->max);
  351.           if (object[i]->transf != NULL)
  352.             FREE(object[i]->transf);
  353.           if (object[i]->inv_transf != NULL)
  354.             FREE(object[i]->inv_transf);
  355.           texture = object[i]->texture;
  356.           while (texture != NULL)
  357.           {
  358.             if (texture->transf != NULL)
  359.               FREE(texture->transf);
  360.             if (texture->data != NULL)
  361.               FREE(texture->data);
  362.             old_texture = texture;
  363.             texture = texture->next;
  364.             FREE(old_texture);
  365.           }
  366.           if (csg->position != NULL)
  367.             FREE(csg->position);
  368.           texture = csg->texture;
  369.           while (texture != NULL)
  370.           {
  371.             if (texture->transf != NULL)
  372.               FREE(texture->transf);
  373.             if (texture->data != NULL)
  374.               FREE(texture->data);
  375.             old_texture = texture;
  376.             texture = texture->next;
  377.             FREE(old_texture);
  378.           }
  379.           FREE(object[i]->data);
  380.           FREE(object[i]);
  381.           object[i] = NULL;
  382.       POSINC(csg_union_removed);
  383.       POSDEC(csg_created);
  384.       POSINC(csg_removed);
  385.       continue;
  386.         }
  387.         if (csg_prim_objects >= CSG_LEVEL1_MAX)
  388.           runtime_abort("too many CSG primary NODES");
  389.         csg_prim_object[csg_prim_objects] = object[i];
  390.         POSINC(csg_prim_objects);
  391.         j = csg->left;
  392.         csg->left = csg_sec_objects;
  393.         csg_copy(csg_sec_object, &csg_sec_objects, j);
  394.         j = csg->right;
  395.         csg->right = csg_sec_objects;
  396.         csg_copy(csg_sec_object, &csg_sec_objects, j);
  397.         object[i] = NULL;
  398.       }
  399.     for (i = objects; i > 0; POSDEC(i))
  400.       if (object[i] == NULL)
  401.       {
  402.     for (j = i + 1; j <= main_objects; POSINC(j))
  403.       object[j - 1] = object[j];
  404.     POSDEC(main_objects);
  405.       }
  406.     if ((verbose_mode > 1) AND(csg_union_removed > 0))
  407.     {
  408.       WRITE(results, "%d CSG UNION object(s) removed\n", csg_union_removed);
  409.       if (csg_created > 0)
  410.         WRITE(results, "%d CSG object(s) created (total)\n", csg_created);
  411.       if (csg_removed > 0)
  412.         WRITE(results, "%d CSG object(s) removed (total)\n", csg_removed);
  413.     }
  414.     j = main_objects + 1 + csg_prim_objects;
  415.     for (i = 0; i < csg_prim_objects; POSINC(i))
  416.     {
  417.       POSINC(main_objects);
  418.       object[main_objects] = csg_prim_object[i];
  419.       csg = (csg_ptr) object[main_objects]->data;
  420.       csg->left += j;
  421.       csg->right += j;
  422.     }
  423.     if (main_objects == 0)
  424.       runtime_abort("no OBJECTS (after CSG sorting)");
  425.   }
  426.   /* Create cluster hierarchy */
  427.  
  428. #ifdef THINK_C
  429.  
  430.     /* On the mac, we change the status text to show we're creating the
  431.         cluster hierarchy */
  432.     if (status_dialog_visible) set_status_text("\pCreating Cluster Hierarchy…Please Wait…");
  433.  
  434. #endif
  435.  
  436.   objects = main_objects;
  437.   i = objects;
  438.   last = objects;
  439.   sort_and_split(1, last);
  440.  
  441.   while (objects - last > 1)
  442.   {
  443.     first = SUCC(last);
  444.     last = objects;
  445.     sort_and_split(first, last);
  446.  
  447.     PROCESS_MAC_EVENT
  448.  
  449.   }
  450.   if (verbose_mode > 1)
  451.     WRITE(results, "%d Cluster object(s) created\n", objects - i);
  452.   if (csg_created > 0)
  453.   {
  454.     /* Adjust CSG primary objects */
  455.     j = objects - i;
  456.     for (i = 1; i <= main_objects; POSINC(i))
  457.     {
  458.       if (object[i]->object_type != CSG_TYPE)
  459.     continue;
  460.       csg = (csg_ptr) object[i]->data;
  461.       csg->left += j;
  462.       csg->right += j;
  463.     }
  464.     /* Insert CSG secondary objects */
  465.     j = objects + 1;
  466.     for (i = 0; i < csg_sec_objects; POSINC(i))
  467.     {
  468.       POSINC(objects);
  469.       if (objects >= OBJECTS_MAX)
  470.         runtime_abort("too many OBJECTS");
  471.       object[objects] = csg_sec_object[i];
  472.       if (object[objects]->object_type != CSG_TYPE)
  473.     continue;
  474.       csg = (csg_ptr) object[objects]->data;
  475.       csg->left += j;
  476.       csg->right += j;
  477.     }
  478.   }
  479.   if (verbose_mode > 1)
  480.   {
  481.     WRITE(results, "%d Total object(s)\n", objects);
  482.     FLUSH(results);
  483.   }
  484.   /* Clean objects */
  485.   for (i = 1; i <= objects; POSINC(i))
  486.   {
  487.     /* Sanity check */
  488.     validate_object(object[i], i);
  489.     if (object[i]->object_type == CSG_TYPE)
  490.     {
  491.       csg = (csg_ptr) object[i]->data;
  492.       if ((csg->left < 1) OR(csg->left > objects))
  493.       {
  494.         WRITE(ERROR, "Incorrect CSG LEFT NODE pointer (%d) at OBJECT %d\n",
  495.               csg->left, i);
  496.         runtime_abort("invalid CSG NODE");
  497.       }
  498.       if ((csg->right < 1) OR(csg->right > objects))
  499.       {
  500.         WRITE(ERROR, "Incorrect CSG RIGHT pointer (%d) at OBJECT %d\n",
  501.               csg->right, i);
  502.         runtime_abort("invalid CSG NODE");
  503.       }
  504.     }
  505.   }
  506.   
  507. #ifdef THINK_C
  508.     
  509.     /* Free the arrays we dynamically allocated */
  510.     FREE (csg_prim_object);
  511.     FREE (csg_sec_object);
  512.  
  513. #endif
  514.  
  515. }
  516.