home *** CD-ROM | disk | FTP | other *** search
/ World of Graphics / WOGRAPH.BIN / 729.SOURCE.ZIP / RAYOPT.C < prev    next >
C/C++ Source or Header  |  1993-04-29  |  55KB  |  2,166 lines
  1. /*-------------------------------------------------------------------------
  2.  
  3.          Triangle Bounder/Smoother for POV-Ray
  4.             Copyright (c) 1993 Steve Anger
  5.  
  6.     A number of C routines that can be used to generate POV-Ray ray tracer
  7.  files from triangle data.  Supports generation of smooth triangles and an
  8.  optimal set of bounding shapes for much faster traces.  Output files are
  9.  compatible with POV-Ray v1.0.  This program may be freely modified and
  10.  distributed.
  11.                        Compuserve: 70714,3113
  12.                         YCCMR BBS: (708)358-5611
  13.  
  14. --------------------------------------------------------------------------*/
  15.  
  16. #ifdef __TURBOC__
  17. #include <alloc.h>
  18. #endif
  19.  
  20. #include <stdio.h>
  21. #include <stdlib.h>
  22. #include <string.h>
  23. #include <ctype.h>
  24. #include <math.h>
  25. #include "vect.h"
  26. #include "rayopt.h"
  27.  
  28. #if defined(applec) || defined(THINK_C)
  29. #include "RAW2POV.mac.h"
  30. #else
  31. #define COOPERATE
  32. #endif
  33.  
  34. #define HASHSIZE  1000          /* Size of hash table for vertex lookup */
  35. #define DEGEN_TOL (1e-8)        /* float comparison tolerance for checking */
  36.                 /* for degenerate triangles */
  37. #define MAX_TEX   500           /* Maximum allowable number of texture */
  38.                 /* declarations */
  39.  
  40. #define POV10   0
  41. #define POV20   1
  42. #define VIVID   2
  43. #define POLYRAY 3
  44.  
  45. #ifndef MAXFLOAT
  46. #define MAXFLOAT (1e37)
  47. #endif
  48.  
  49. typedef struct {
  50.     float red;
  51.     float green;
  52.     float blue;
  53. } Palette;
  54.  
  55. typedef char *Texture;
  56.  
  57. typedef struct {
  58.     unsigned vert[3];
  59.     unsigned text_index;
  60.     char     text_type;
  61.     char     flag;
  62. } Triangle;
  63.  
  64.  
  65. /* Linked list of triangles */
  66. typedef struct TList {
  67.     Triangle     *tri;
  68.     struct TList *next;
  69. } TriList;
  70.  
  71.  
  72. /* Double linked list of triangles */
  73. typedef struct TList2 {
  74.     Triangle      *tri;
  75.     struct TList2 *prev;
  76.     struct TList2 *next;
  77. } TriList2;
  78.  
  79.  
  80. /* List of triangle vertices */
  81. typedef struct VList {
  82.     unsigned     vert;
  83.     struct VList *next;
  84. } VertList;
  85.  
  86.  
  87. /* List of triangle groups */
  88. typedef struct GTree {
  89.     TriList2     *index[3];    /* Triangles indexed by x, y, and z coord */
  90.     Vector       vmin;         /* min/max extents of triangle vertices */
  91.     Vector       vmax;         /*    "       "     "     "        "     */
  92.     float        area;         /* Total surface area of bounding region */
  93.     unsigned     obj_cnt;      /* Total number of triangles in group */
  94.     int          child_cnt;    /* Number of children */
  95.     int          split_cnt;    /* Number of times this node has been split */
  96.     struct GTree *parent;      /* Parent of this node */
  97.     struct GTree *next;        /* Next node at this level */
  98.     struct GTree *child;       /* First child of this ndoe */
  99. } GroupTree;
  100.  
  101. static Palette   *ptable;      /* Palette table */
  102. static unsigned  pmax;         /* Maximum size of table */
  103. static unsigned  psize;        /* Current size */
  104.  
  105. static Texture   *ttable;      /* Named texture table */
  106. static unsigned  tmax;         /* Maximum size of table */
  107. static unsigned  tsize;        /* Current size */
  108.  
  109. static Vector    *vtable;      /* Vertice table */
  110. static unsigned  vmax;         /* Maximum size of table */
  111. static unsigned  vsize;        /* Current size */
  112.  
  113. static Vector    gmin = {+MAXFLOAT, +MAXFLOAT, +MAXFLOAT};
  114. static Vector    gmax = {-MAXFLOAT, -MAXFLOAT, -MAXFLOAT};
  115.  
  116. static Matrix    trans_matrix;
  117. static int       use_transform = 0;
  118.  
  119. static VertList  **vert_hash;    /* Hash table for looking up vertices */
  120. static TriList   **tri_index;    /* Index for smooth triangle generation */
  121.  
  122. static GroupTree *groot;         /* Tree representing the object hierarchy */
  123.  
  124. static int       initialized  = 0;
  125. static int       quiet_mode   = 0;
  126. static int       bound_mode   = 0;
  127. static float     smooth_angle = 0.0;
  128. static unsigned  vert_init    = 0;
  129. static int       dec_point    = 4;
  130. static int       out_format   = POV10;
  131.  
  132. static char      out_file[64] = "rayopt.pov";
  133. static char      inc_file[64] = "rayopt.inc";
  134.  
  135. static unsigned  tot_bounds   = 0;
  136. static unsigned  object_cnt   = 0;
  137.  
  138. static Vector    last_vmin = {0.0, 0.0, 0.0};
  139. static Vector    last_vmax = {0.0, 0.0, 0.0};
  140. static unsigned  last_vert_cnt = 0;
  141. static unsigned  last_tri_cnt = 0;
  142. static float     last_index = 0.0;
  143. static unsigned  last_bounds = 0;
  144.  
  145. static Palette   last_pal;
  146. static char      last_texture[64] = "";
  147. static unsigned  texture_index;
  148. static char      texture_type;
  149. static char      object_name[64] = "";
  150.  
  151. static float     orig_tpr;    /* Number of Tests Per Ray before optimization */
  152. static float     final_tpr;   /*    "   "    "    "   "  after optimization */
  153. static float     bound_cost;  /* Cost of testing a bound relative to testing */
  154.                   /* a triangle */
  155.  
  156. /* Function prototypes */
  157. void init_object (void);
  158. void cleanup_object (void);
  159. float calc_tpr (GroupTree *gnode);
  160. GroupTree *create_group (void);
  161. void delete_tree (GroupTree *gnode);
  162. void optimize_tree (GroupTree *gnode);
  163. void test_split (GroupTree *gnode, int axis, float *best_rtpr, TriList2 **
  164.     best_loc);
  165. void split_group (GroupTree *gnode, int axis, TriList2 *split_loc, GroupTree *
  166.     *group_a, GroupTree **group_b);
  167. void write_file (void);
  168. void write_pov10_tree (FILE *f, GroupTree *gnode, int level);
  169. void write_pov10_texture (FILE *f, Triangle *tri);
  170. void write_pov10_transform (FILE *f, Matrix matrix);
  171. void write_pov10_header (FILE *f);
  172. void write_pov10_triangle (FILE *f, Triangle *tri, int one_texture);
  173. void write_pov10_bound (FILE *f, GroupTree *gnode);
  174. void write_pov20_tree (FILE *f, GroupTree *gnode, int level);
  175. void write_pov20_texture (FILE *f, Triangle *tri);
  176. void write_pov20_transform (FILE *f, Matrix matrix);
  177. void write_pov20_header (FILE *f);
  178. void write_pov20_triangle (FILE *f, Triangle *tri, int one_texture);
  179. void write_pov20_bound (FILE *f, GroupTree *gnode);
  180. void write_vivid_tree (FILE *f, GroupTree *gnode);
  181. void write_vivid_transform (FILE *f, Matrix matrix);
  182. void write_vivid_texture (FILE *f, Triangle *tri);
  183. void write_vivid_header (FILE *f);
  184. void write_vivid_triangle (FILE *f, Triangle *tri);
  185. void write_polyray_tree (FILE *f, GroupTree *gnode);
  186. void write_polyray_transform (FILE *f, Matrix matrix);
  187. void write_polyray_texture (FILE *f, Triangle *tri);
  188. void write_polyray_header (FILE *f);
  189. void write_polyray_triangle (FILE *f, Triangle *tri);
  190. void update_node (GroupTree *gnode);
  191. void sort_indexes (GroupTree *gnode);
  192. void quick_sort (TriList2 *start, TriList2 *end, int axis);
  193. float surf_area (float a, float b, float c);
  194. float max_vertex (Triangle *tri, int axis);
  195. float min_vertex (Triangle *tri, int axis);
  196. float avg_vertex (Triangle *tri, int axis);
  197. void build_tri_index (void);
  198. void dump_tri_index (void);
  199. void vert_normal (Triangle *t, Vector *norm);
  200. void tri_normal (Triangle *t, Vector normal);
  201. unsigned pal_lookup (float red, float green, float blue);
  202. unsigned texture_lookup (char *texture_name);
  203. unsigned vert_lookup (float x, float y, float z);
  204. int degen_tri (float ax, float ay, float az, float bx, float by, float bz,
  205.      float cx, float cy, float cz);
  206. void abortmsg (char *msg, int exit_code);
  207. float fmin (float a, float b);
  208. float fmax (float a, float b);
  209. void add_ext (char *fname, char *ext, int force);
  210. void cleanup_name (char *name);
  211.  
  212.  
  213. void opt_set_format (int format)
  214. {
  215.     if (format != POV10 && format != POV20 && format != VIVID && format != POLYRAY)
  216.     abortmsg ("ERROR: Invalid parameter passed to opt_set_format.", 1);
  217.  
  218.     out_format = format;
  219. }
  220.  
  221.  
  222. void opt_set_fname (char *out_name, char *inc_name)
  223. {
  224.     FILE *f;
  225.  
  226.     strcpy (out_file, out_name);
  227.  
  228.     if (strlen(inc_name) > 0)
  229.     strcpy (inc_file, inc_name);
  230.     else {
  231.     strcpy (inc_file, out_file);
  232.  
  233.     switch (out_format) {
  234.         case POV10:
  235.         case POV20:   add_ext (inc_file, "inc", 1);
  236.               break;
  237.         case VIVID:   add_ext (inc_file, "vo", 1);
  238.               break;
  239.         case POLYRAY: add_ext (inc_file, "inc", 1);
  240.               break;
  241.     }
  242.     }
  243.  
  244.     if (strcmp (out_file, inc_file) == 0)
  245.     abortmsg ("Main file and include file cannot have the same name", 1);
  246.  
  247.     if ((f = fopen (out_file, "w")) == NULL) {
  248.     printf ("Cannot open output file %s\n", out_file);
  249.     exit (1);
  250.     }
  251.  
  252.     fclose (f);
  253.  
  254.     if ((f = fopen (inc_file, "w")) == NULL) {
  255.     printf ("Cannot open output file %s\n", inc_file);
  256.     exit (1);
  257.     }
  258.  
  259.     fclose (f);
  260. }
  261.  
  262.  
  263. void opt_set_quiet (int quiet)
  264. {
  265.     if (quiet != 0 && quiet != 1)
  266.     abortmsg ("ERROR: Invalid parameter passed to opt_set_quiet.", 1);
  267.  
  268.     quiet_mode = quiet;
  269. }
  270.  
  271.  
  272. void opt_set_bound (int bound)
  273. {
  274.     if (bound != 0 && bound != 1 && bound != 2)
  275.     abortmsg ("ERROR: Invalid parameter passed to opt_set_bound.", 1);
  276.  
  277.     bound_mode = bound;
  278. }
  279.  
  280.  
  281. void opt_set_smooth (float  smooth)
  282. {
  283.     if (smooth < 0.0 || smooth > 180.0)
  284.     abortmsg ("ERROR: Invalid parameter passed to opt_set_smooth.", 1);
  285.  
  286.     smooth_angle = smooth;
  287. }
  288.  
  289.  
  290. void opt_set_vert (unsigned vert)
  291. {
  292.     vert_init = vert;
  293. }
  294.  
  295.  
  296. void opt_set_dec (int dec)
  297. {
  298.     if (dec < 0 || dec > 9)
  299.     abortmsg ("ERROR: Invalid parameter passed to opt_set_dec.", 1);
  300.  
  301.     dec_point = dec;
  302. }
  303.  
  304.  
  305. void opt_set_color (float  red, float  green, float  blue)
  306. {
  307.     if (!initialized)
  308.     init_object();
  309.  
  310.     if (last_pal.red != red || last_pal.green != green ||
  311.                    last_pal.blue != blue || psize == 0)
  312.     {
  313.     last_pal.red   = red;
  314.     last_pal.green = green;
  315.     last_pal.blue  = blue;
  316.  
  317.     texture_index = pal_lookup (red, green, blue);
  318.     }
  319.  
  320.     texture_type = 0;   /* An RGB texture */
  321. }
  322.  
  323.  
  324. void opt_set_texture (char *texture_name)
  325. {
  326.     char new_texture[64];
  327.  
  328.     if (!initialized)
  329.     init_object();
  330.  
  331.     strcpy (new_texture, texture_name);
  332.     cleanup_name (new_texture);
  333.  
  334.     if (strcmp (last_texture, new_texture) != 0) {
  335.     strcpy (last_texture, new_texture);
  336.     texture_index = texture_lookup (new_texture);
  337.     }
  338.  
  339.     texture_type = 1;   /* A named texture */
  340. }
  341.  
  342.  
  343. /* Set a transformation matrix for the next object */
  344. void opt_set_transform (Matrix mat)
  345. {
  346.     int i, j;
  347.  
  348.     for (i = 0; i < 4; i++) {
  349.     for (j = 0; j < 3; j++)
  350.         trans_matrix[i][j] = mat[i][j];
  351.     }
  352.  
  353.     use_transform = 1;
  354. }
  355.  
  356.  
  357. void opt_clear_transform()
  358. {
  359.     use_transform = 0;
  360. }
  361.  
  362.  
  363. /* Add a new triangle to the database */
  364. int opt_add_tri (float  ax, float  ay, float  az,
  365.          float  bx, float  by, float  bz,
  366.          float  cx, float  cy, float  cz)
  367. {
  368.     TriList2 *new_node;
  369.     Triangle *new_tri;
  370.     int      i;
  371.  
  372.     /* Check if the triangle is degenerate (zero area), if so return -1 */
  373.     if (degen_tri (ax, ay, az, bx, by, bz, cx, cy, cz))
  374.     return -1;
  375.  
  376.     if (!initialized)
  377.     init_object();
  378.  
  379.     /* Allocate memory for the new triangle */
  380.     new_tri = malloc (sizeof(Triangle));
  381.     if (new_tri == NULL)
  382.     abortmsg ("Insufficient memory for new triangles.", 1);
  383.  
  384.     /* Look up the vertex and texture indexes */
  385.     new_tri->vert[0] = vert_lookup (ax, ay, az);
  386.     new_tri->vert[1] = vert_lookup (bx, by, bz);
  387.     new_tri->vert[2] = vert_lookup (cx, cy, cz);
  388.  
  389.     new_tri->text_index = texture_index;
  390.     new_tri->text_type  = texture_type;
  391.  
  392.     new_tri->flag = 0;
  393.  
  394.     for (i = 0; i < 3; i++) {
  395.     /* Create a new index node */
  396.     new_node = malloc (sizeof(TriList2));
  397.     if (new_node == NULL)
  398.         abortmsg ("Insufficient memory for triangles.", 1);
  399.  
  400.     /* Point the index entry to the new triangle */
  401.     new_node->tri = new_tri;
  402.  
  403.     /* Insert the new index node into the list */
  404.     new_node->next = groot->index[i];
  405.     new_node->prev = groot->index[i]->prev;
  406.     groot->index[i]->prev->next = new_node;
  407.     groot->index[i]->prev = new_node;
  408.     }
  409.  
  410.     ++(groot->obj_cnt);
  411.  
  412.     return 0;
  413. }
  414.  
  415.  
  416. /* For compatability */
  417. void opt_write_pov (char *obj_name)
  418. {
  419.     opt_write_file (obj_name);
  420. }
  421.  
  422.  
  423. /* Optimize and write file */
  424. void opt_write_file (char *obj_name)
  425. {
  426.     VertList *temp;
  427.     int      i;
  428.  
  429.     if (out_format != POV10 && out_format != POV20)
  430.     bound_mode = 2;
  431.  
  432.     if (!initialized || groot->obj_cnt == 0) {
  433.     orig_tpr = 1.0;
  434.     final_tpr = 0.0;
  435.     tot_bounds = 0;
  436.     return;   /* No triangles where ever added, nothing to write */
  437.     }
  438.  
  439.     strcpy (object_name, obj_name);
  440.     cleanup_name (object_name);
  441.  
  442.     ++object_cnt;
  443.  
  444.     /* Dump the hash table, don't need it any more */
  445.     for (i = 0; i < HASHSIZE; i++) {
  446.     while (vert_hash[i] != NULL) {
  447.         temp = vert_hash[i];
  448.         vert_hash[i] = vert_hash[i]->next;
  449.         free (temp);
  450.     }
  451.     }
  452.  
  453.     /* Build the vertice index */
  454.     build_tri_index();
  455.  
  456.     if (bound_mode != 2) {
  457.     if (!quiet_mode)
  458.         printf ("Building indexes\n");
  459.  
  460.     sort_indexes (groot);
  461.     }
  462.  
  463.     update_node (groot);
  464.  
  465.     if (!quiet_mode) {
  466.     printf ("Adding bounds (1)\r");
  467.     fflush(stdout);;
  468.     }
  469.  
  470.     /* Optimize the tree */
  471.     orig_tpr = calc_tpr (groot);
  472.  
  473.     if (bound_mode != 2)
  474.     optimize_tree (groot);
  475.  
  476.     final_tpr = calc_tpr (groot);
  477.  
  478.     /* Write the file */
  479.     write_file();
  480.  
  481.     /* Free up the vertex index */
  482.     dump_tri_index();
  483.  
  484.     cleanup_object();
  485. }
  486.  
  487.  
  488. void opt_finish()
  489. {
  490.     FILE *f;
  491.  
  492.     f = fopen (out_file, "a");
  493.  
  494.     switch (out_format) {
  495.     case POV10:
  496.             if (object_cnt > 2 && bound_mode == 0)
  497.             fprintf (f, "composite {  /* All Objects */\n    ");
  498.  
  499.         fprintf (f, "#include \"%s\"\n", inc_file);
  500.  
  501.         if (object_cnt > 2 && bound_mode == 0) {
  502.         fprintf (f, "\n");
  503.         fprintf (f, "    bounded_by {\n");
  504.         fprintf (f, "        box { <%.4f %.4f %.4f> <%.4f %.4f %.4f> }\n",
  505.                      gmin[X], gmin[Y], gmin[Z],
  506.                      gmax[X], gmax[Y], gmax[Z]);
  507.         fprintf (f, "    }\n");
  508.             fprintf (f, "}\n\n");
  509.             }
  510.         break;
  511.  
  512.     case POV20:
  513.             if (object_cnt > 2 && bound_mode == 0)
  514.                 fprintf (f, "union {\n    ");
  515.  
  516.         fprintf (f, "#include \"%s\"\n", inc_file);
  517.  
  518.         if (object_cnt > 2 && bound_mode == 0) {
  519.         fprintf (f, "\n");
  520.         fprintf (f, "    bounded_by {\n");
  521.         fprintf (f, "        box { <%.4f, %.4f, %.4f>, <%.4f, %.4f, %.4f> }\n",
  522.                      gmin[X], gmin[Y], gmin[Z],
  523.                      gmax[X], gmax[Y], gmax[Z]);
  524.         fprintf (f, "    }\n");
  525.                 fprintf (f, "}\n\n");
  526.             }
  527.         break;
  528.  
  529.     case VIVID:
  530.         fprintf (f, "#include %s\n\n", inc_file);
  531.         break;
  532.  
  533.     case POLYRAY:
  534.         fprintf (f, "include \"%s\"\n\n", inc_file);
  535.         break;
  536.     }
  537.  
  538.     fclose (f);
  539. }
  540.  
  541.  
  542.  
  543. void opt_get_limits (float  *min_x, float  *min_y, float  *min_z,
  544.              float  *max_x, float  *max_y, float  *max_z)
  545. {
  546.     *min_x = last_vmin[X];
  547.     *min_y = last_vmin[Y];
  548.     *min_z = last_vmin[Z];
  549.  
  550.     *max_x = last_vmax[X];
  551.     *max_y = last_vmax[Y];
  552.     *max_z = last_vmax[Z];
  553. }
  554.  
  555.  
  556. void opt_get_glimits (float  *min_x, float  *min_y, float  *min_z,
  557.               float  *max_x, float  *max_y, float  *max_z)
  558. {
  559.     *min_x = gmin[X];
  560.     *min_y = gmin[Y];
  561.     *min_z = gmin[Z];
  562.  
  563.     *max_x = gmax[X];
  564.     *max_y = gmax[Y];
  565.     *max_z = gmax[Z];
  566. }
  567.  
  568.  
  569. unsigned opt_get_vert_cnt()
  570. {
  571.     return last_vert_cnt;
  572. }
  573.  
  574.  
  575. unsigned opt_get_tri_cnt()
  576. {
  577.     return last_tri_cnt;
  578. }
  579.  
  580.  
  581. float  opt_get_index()
  582. {
  583.     return last_index;
  584. }
  585.  
  586.  
  587. unsigned opt_get_bounds()
  588. {
  589.     return last_bounds;
  590. }
  591.  
  592.  
  593. void init_object()
  594. {
  595.     int i;
  596.  
  597.     last_pal.red   = 0.0;
  598.     last_pal.green = 0.0;
  599.     last_pal.blue  = 0.0;
  600.  
  601.     strcpy (last_texture, "");
  602.  
  603.     bound_cost = 1.6;
  604.  
  605.     /* Allocate memory for palette lookup table */
  606.     pmax   = 10;
  607.     psize  = 0;
  608.     ptable = malloc (pmax * sizeof(Palette));
  609.     if (ptable == NULL)
  610.     abortmsg ("Insufficient memory for palette.", 1);
  611.  
  612.     /* Allocate memory for texture table */
  613.     tmax   = 10;
  614.     tsize  = 0;
  615.     ttable = malloc (tmax * sizeof(Texture));
  616.     if (ttable == NULL)
  617.     abortmsg ("Insufficient memory for textures.", 1);
  618.  
  619.     /* Allocate memory for vertex lookup table */
  620.     vmax = (vert_init > 0) ? vert_init : 1000;
  621.     vsize  = 0;
  622.     vtable = malloc (vmax * sizeof(Vector));
  623.     if (vtable == NULL)
  624.     abortmsg ("Insufficient memory for vertices.", 1);
  625.  
  626.     /* Allocate memory for vertex hash table */
  627.     vert_hash = malloc (sizeof(VertList*)*HASHSIZE);
  628.     if (vert_hash == NULL)
  629.     abortmsg ("Insufficient memory for vertex hash table.", 1);
  630.  
  631.     /* Initialize the vertex lookup hash table */
  632.     for (i = 0; i < HASHSIZE; i++)
  633.     vert_hash[i] = NULL;
  634.  
  635.     /* Start with an empty root node */
  636.     groot = create_group();
  637.  
  638.     tot_bounds = 1;
  639.     initialized = 1;
  640. }
  641.  
  642.  
  643. void cleanup_object()
  644. {
  645.     int i;
  646.     Vector corners[8];  /* Corners of box */
  647.  
  648.     last_vert_cnt = vsize;
  649.     last_tri_cnt  = groot->obj_cnt;
  650.     last_index    = orig_tpr/final_tpr;
  651.     last_bounds   = tot_bounds;
  652.  
  653.     vect_copy (last_vmin, groot->vmin);
  654.     vect_copy (last_vmax, groot->vmax);
  655.  
  656.     /* Calculate the corners of the bounding box */
  657.     corners[0][X] =  groot->vmin[X];
  658.     corners[0][Y] =  groot->vmin[Y];
  659.     corners[0][Z] =  groot->vmin[Z];
  660.  
  661.     corners[1][X] =  groot->vmin[X];
  662.     corners[1][Y] =  groot->vmin[Y];
  663.     corners[1][Z] =  groot->vmax[Z];
  664.  
  665.     corners[2][X] =  groot->vmax[X];
  666.     corners[2][Y] =  groot->vmin[Y];
  667.     corners[2][Z] =  groot->vmin[Z];
  668.  
  669.     corners[3][X] =  groot->vmax[X];
  670.     corners[3][Y] =  groot->vmin[Y];
  671.     corners[3][Z] =  groot->vmax[Z];
  672.  
  673.     corners[4][X] =  groot->vmin[X];
  674.     corners[4][Y] =  groot->vmax[Y];
  675.     corners[4][Z] =  groot->vmin[Z];
  676.  
  677.     corners[5][X] =  groot->vmax[X];
  678.     corners[5][Y] =  groot->vmax[Y];
  679.     corners[5][Z] =  groot->vmin[Z];
  680.  
  681.     corners[6][X] =  groot->vmin[X];
  682.     corners[6][Y] =  groot->vmax[Y];
  683.     corners[6][Z] =  groot->vmax[Z];
  684.  
  685.     corners[7][X] =  groot->vmax[X];
  686.     corners[7][Y] =  groot->vmax[Y];
  687.     corners[7][Z] =  groot->vmax[Z];
  688.  
  689.     /* Include any transformation in the box calcs */
  690.     if (use_transform) {
  691.     for (i = 0; i < 8; i++)
  692.         vect_transform (corners[i], corners[i], trans_matrix);
  693.     }
  694.  
  695.     for (i = 0; i < 8; i++) {
  696.     gmin[X] = (corners[i][X] < gmin[X]) ? corners[i][X] : gmin[X];
  697.     gmin[Y] = (corners[i][Y] < gmin[Y]) ? corners[i][Y] : gmin[Y];
  698.     gmin[Z] = (corners[i][Z] < gmin[Z]) ? corners[i][Z] : gmin[Z];
  699.  
  700.     gmax[X] = (corners[i][X] > gmax[X]) ? corners[i][X] : gmax[X];
  701.     gmax[Y] = (corners[i][Y] > gmax[Y]) ? corners[i][Y] : gmax[Y];
  702.     gmax[Z] = (corners[i][Z] > gmax[Z]) ? corners[i][Z] : gmax[Z];
  703.     }
  704.  
  705.     free (ptable);
  706.     free (vtable);
  707.     free (vert_hash);
  708.  
  709.     for (i = 0; i < tsize; i++)
  710.     free (ttable[i]);
  711.  
  712.     free (ttable);
  713.  
  714.     delete_tree (groot);
  715.  
  716.     initialized = 0;
  717. }
  718.  
  719.  
  720. /* Calculate the number of Tests Per Ray (tpr) required for this group */
  721. float  calc_tpr (GroupTree *gnode)
  722. {
  723.     GroupTree *g;
  724.     float     tpr;
  725.  
  726.     if (gnode->child_cnt == 0)
  727.     return gnode->obj_cnt;
  728.  
  729.     tpr = bound_cost * gnode->child_cnt;
  730.  
  731.     for (g = gnode->child; g != NULL; g = g->next)
  732.     tpr = tpr + (g->area/gnode->area) * calc_tpr(g);
  733.  
  734.     return tpr;
  735. }
  736.  
  737.  
  738. /* Create an empty group node */
  739. GroupTree *create_group()
  740. {
  741.     GroupTree *new_group;
  742.     int       i;
  743.  
  744.     new_group = malloc (sizeof(GroupTree));
  745.     if (new_group == NULL)
  746.     abortmsg ("Insufficient memory for group list.", 1);
  747.  
  748.     for (i = 0; i < 3; i++) {
  749.     new_group->index[i] = malloc (sizeof(TriList2));
  750.     if (new_group->index[i] == NULL)
  751.         abortmsg ("Insufficient memory for tree.", 1);
  752.  
  753.     new_group->index[i]->tri = NULL;
  754.     new_group->index[i]->prev = new_group->index[i];
  755.     new_group->index[i]->next = new_group->index[i];
  756.     }
  757.  
  758.     vect_init (new_group->vmin, +MAXFLOAT, +MAXFLOAT, +MAXFLOAT);
  759.     vect_init (new_group->vmax, -MAXFLOAT, -MAXFLOAT, -MAXFLOAT);
  760.     new_group->area      = 0.0;
  761.     new_group->obj_cnt   = 0;
  762.     new_group->child_cnt = 0;
  763.     new_group->split_cnt = 0;
  764.     new_group->parent    = NULL;
  765.     new_group->next      = NULL;
  766.     new_group->child     = NULL;
  767.  
  768.     return new_group;
  769. }
  770.  
  771.  
  772. /* Delete this node and all sub-nodes of tree */
  773. void delete_tree (GroupTree *gnode)
  774. {
  775.     GroupTree *g, *g_temp;
  776.     TriList2  *t, *t_temp;
  777.     int       i;
  778.  
  779.     for (g = gnode->child; g != NULL; ) {
  780.     g_temp = g->next;
  781.     delete_tree (g);
  782.     g = g_temp;
  783.     }
  784.  
  785.     /* Free the indexes for this node (if any exist) */
  786.     for (i = 0; i < 3; i++) {
  787.     if ((gnode->index[i] != NULL) && (gnode->index[i]->prev != NULL)) {
  788.         /* Drop a link so the list isn't circular any more */
  789.         gnode->index[i]->prev->next = NULL;
  790.  
  791.         /* Delete the list */
  792.         for (t = gnode->index[i]; t != NULL; ) {
  793.         if (i == 0 && (t->tri != NULL))
  794.             free (t->tri);
  795.  
  796.         t_temp = t;
  797.         t = t->next;
  798.         free (t_temp);
  799.         }
  800.     }
  801.     }
  802.  
  803.     /* And finally free the root node */
  804.     free (gnode);
  805. }
  806.  
  807.  
  808. /* Optimize the bounds for this sub-tree */
  809. void optimize_tree (GroupTree *gnode)
  810. {
  811.     GroupTree *group_a, *group_b;
  812.     int axis, best_axis;
  813.     float     best_rtpr, new_rtpr;
  814.     TriList2  *best_loc, *new_loc;
  815.  
  816.     best_rtpr = 0.0;
  817.     best_loc  = NULL;
  818.     best_axis = -1;
  819.  
  820.     /* Try splitting the group in each of the three axis' (x,y,z) */
  821.     for (axis = 0; axis < 3; axis++) {
  822.     test_split (gnode, axis, &new_rtpr, &new_loc);
  823.  
  824.     if (new_rtpr < best_rtpr) {
  825.         best_rtpr = new_rtpr;
  826.         best_loc  = new_loc;
  827.         best_axis = axis;
  828.     }
  829.     }
  830.  
  831.     if (best_axis != -1) {
  832.     /* Split this node into two nodes */
  833.     split_group (gnode, best_axis, best_loc, &group_a, &group_b);
  834.  
  835.     optimize_tree (group_a);
  836.     optimize_tree (group_b);
  837.     }
  838. }
  839.  
  840.  
  841.  
  842. /* Test the effectiveness of splitting this group (but don't do it yet) */
  843. void test_split (GroupTree *gnode, int axis, float  *best_rtpr,
  844.          TriList2 **best_loc)
  845. {
  846.     float    dim1, dim2;
  847.     float    area1, area2, p_area;
  848.     float    new_min1, new_max1, new_min2, new_max2;
  849.     float    best_index, new_index;
  850.     TriList2 *t;
  851.     int      cnt, best_cnt;
  852.  
  853.     *best_loc  = NULL;
  854.     best_index = +MAXFLOAT ;
  855.     best_cnt   = 0;
  856.     cnt = 0;
  857.  
  858.     dim1 = gnode->vmax[(axis+1) % 3] - gnode->vmin[(axis+1) % 3];
  859.     dim2 = gnode->vmax[(axis+2) % 3] - gnode->vmin[(axis+2) % 3];
  860.  
  861.     for (t = gnode->index[axis]->next; t != gnode->index[axis]; t = t->next) {
  862.     if (t->next == gnode->index[axis])
  863.         break;
  864.  
  865.     ++cnt;
  866.  
  867.     /* Make an estimate of the new min/max limits, doing the full */
  868.     /* calculation is just tooooo slooowww. */
  869.     new_min1 = gnode->vmin[axis];
  870.     new_max1 = max_vertex (t->tri, axis);
  871.     new_min2 = min_vertex (t->next->tri, axis);
  872.     new_max2 = gnode->vmax[axis];
  873.  
  874.     /* Calculate the surface area of the new groups */
  875.     area1 = surf_area (dim1, dim2, new_max1 - new_min1);
  876.     area2 = surf_area (dim1, dim2, new_max2 - new_min2);
  877.  
  878.     new_index = (cnt * area1) + ((gnode->obj_cnt - cnt) * area2);
  879.  
  880.     /* Keep track of the best one */
  881.     if (new_index < best_index) {
  882.         best_index = new_index;
  883.         *best_loc  = t->next;
  884.         best_cnt   = cnt;
  885.     }
  886.     }
  887.  
  888.     /* The former was just an estimate, verify the numbers */
  889.     if (*best_loc != NULL) {
  890.     new_min1 = gnode->vmin[axis];
  891.     new_max1 = -MAXFLOAT;
  892.     new_min2 = +MAXFLOAT;
  893.     new_max2 = gnode->vmax[axis];
  894.  
  895.     for (t = gnode->index[axis]->next; t != *best_loc; t = t->next)
  896.         new_max1 = fmax (new_max1, max_vertex (t->tri, axis));
  897.  
  898.     for (t = *best_loc; t != gnode->index[axis]; t = t->next)
  899.         new_min2 = fmin (new_min2, min_vertex (t->tri, axis));
  900.  
  901.     area1 = surf_area (dim1, dim2, new_max1 - new_min1);
  902.     area2 = surf_area (dim1, dim2, new_max2 - new_min2);
  903.  
  904.     best_index = (best_cnt * area1) +
  905.              ((gnode->obj_cnt - best_cnt) * area2);
  906.     }
  907.  
  908.     if (gnode->parent == NULL || gnode->split_cnt >= 2) {
  909.     p_area = gnode->area;
  910.  
  911.     *best_rtpr = -1.0*((gnode->area/p_area) * gnode->obj_cnt) +
  912.              (gnode->area/p_area) * ((best_index/p_area) +
  913.              2.0*bound_cost);
  914.     }
  915.     else {
  916.     p_area = gnode->parent->area;
  917.  
  918.     *best_rtpr = -1.0*((gnode->area/p_area) * gnode->obj_cnt) +
  919.              (best_index/p_area) + bound_cost;
  920.     }
  921. }
  922.  
  923.  
  924. /* Split the group along the specified axis into two sub-groups */
  925. void split_group (GroupTree *gnode, int axis, TriList2 *split_loc,
  926.           GroupTree **group_a, GroupTree **group_b)
  927. {
  928.     GroupTree *new_a, *new_b;
  929.     TriList2  *t, *next_t, *new_index;
  930.     char      new_flag;
  931.     int       i;
  932.  
  933.     COOPERATE    /* support multitasking */
  934.  
  935.     /* Mark the triangles as to which group they will belong */
  936.     new_flag = 0;
  937.     for (t = gnode->index[axis]->next; t != gnode->index[axis]; t = t->next) {
  938.     if (t == split_loc)
  939.         new_flag = 1;
  940.  
  941.     t->tri->flag = new_flag;
  942.     }
  943.  
  944.     new_a = create_group();
  945.     new_b = create_group();
  946.  
  947.     for (i = 0; i < 3; i++) {
  948.     t = gnode->index[i]->next;
  949.  
  950.     while (t != gnode->index[i]) {
  951.         next_t = t->next;
  952.  
  953.         if (t->tri->flag == 0)
  954.         new_index = new_a->index[i];
  955.         else
  956.         new_index = new_b->index[i];
  957.  
  958.         /* Remove this node from the list */
  959.         t->prev->next = t->next;
  960.         t->next->prev = t->prev;
  961.  
  962.         /* Insert node into its new group */
  963.         t->prev = new_index->prev;
  964.         t->next = new_index;
  965.         new_index->prev->next = t;
  966.         new_index->prev = t;
  967.  
  968.         t = next_t;
  969.     }
  970.     }
  971.  
  972.     for (i = 0; i < 3; i++) {
  973.     free (gnode->index[i]);
  974.     gnode->index[i] = NULL;
  975.     }
  976.  
  977.     if (gnode->parent == NULL || gnode->split_cnt >= 2) {
  978.     /* Add the new groups as children of original */
  979.     gnode->child  = new_a;
  980.     new_a->parent = gnode;
  981.     new_a->next   = new_b;
  982.     new_b->parent = gnode;
  983.  
  984.     new_a->split_cnt = 0;
  985.     new_b->split_cnt = 0;
  986.  
  987.     tot_bounds = tot_bounds + 2;
  988.     }
  989.     else {
  990.     /* Remove the original group and replace with the new groups */
  991.     for (i = 0; i < 3; i++)
  992.         gnode->index[i] = new_a->index[i];
  993.  
  994.     free (new_a);
  995.     new_a = gnode;
  996.  
  997.     new_b->next = new_a->next;
  998.     new_a->next = new_b;
  999.  
  1000.     new_a->parent = gnode->parent;
  1001.     new_b->parent = gnode->parent;
  1002.  
  1003.     new_a->split_cnt = gnode->split_cnt + 1;
  1004.     new_b->split_cnt = gnode->split_cnt + 1;
  1005.  
  1006.     tot_bounds = tot_bounds + 1;
  1007.     }
  1008.  
  1009.     update_node (new_a);
  1010.     update_node (new_b);
  1011.  
  1012.     if (new_a->parent != NULL)
  1013.     update_node (new_a->parent);
  1014.  
  1015.     if (!quiet_mode) {
  1016.     printf ("Adding bounds (%d)\r", tot_bounds);
  1017.     fflush(stdout);
  1018.     }
  1019.  
  1020.     *group_a = new_a;
  1021.     *group_b = new_b;
  1022. }
  1023.  
  1024.  
  1025. /* Write the optimized POV file */
  1026. void write_file()
  1027. {
  1028.     FILE  *f;
  1029.  
  1030.     if (!quiet_mode)
  1031.     printf ("\nWriting files %s and %s\n", out_file, inc_file);
  1032.  
  1033.     f = fopen (out_file, "a");
  1034.     if (f == NULL)
  1035.     abortmsg ("Error opening output file.", 1);
  1036.  
  1037.     switch (out_format) {
  1038.     case POV10:   write_pov10_header (f);
  1039.               break;
  1040.     case POV20:   write_pov20_header (f);
  1041.               break;
  1042.     case VIVID:   write_vivid_header (f);
  1043.               break;
  1044.     case POLYRAY: write_polyray_header (f);
  1045.               break;
  1046.     }
  1047.  
  1048.     fclose (f);
  1049.  
  1050.     f = fopen (inc_file, "a");
  1051.     if (f == NULL)
  1052.     abortmsg ("Error opening output file.", 1);
  1053.  
  1054.     switch (out_format) {
  1055.     case POV10:   write_pov10_tree (f, groot, 1);
  1056.               break;
  1057.     case POV20:   write_pov20_tree (f, groot, 1);
  1058.               break;
  1059.     case VIVID:   write_vivid_tree (f, groot);
  1060.               break;
  1061.     case POLYRAY: write_polyray_tree (f, groot);
  1062.               break;
  1063.     }
  1064.  
  1065.     fclose (f);
  1066.  
  1067.     if (!quiet_mode) {
  1068.     printf ("Triangles: %u, ", groot->obj_cnt);
  1069.     printf ("Vertices: %u, ", vsize);
  1070.     printf ("Bounding index: %.2f\n\n", orig_tpr/final_tpr);
  1071.     }
  1072. }
  1073.  
  1074.  
  1075. /* Write a sub-tree to file */
  1076. void write_pov10_tree (FILE *f, GroupTree *gnode, int level)
  1077. {
  1078.     GroupTree *g;
  1079.     TriList2  *t;
  1080.     Triangle  *first_tri;
  1081.     int       one_texture;
  1082.  
  1083.     if (level == 1)
  1084.     fprintf (f, "\n/* Object '%s' */\n", object_name);
  1085.  
  1086.     fprintf (f, "composite {\n");
  1087.  
  1088.     if (gnode->child != NULL) {
  1089.     for (g = gnode->child; g != NULL; g = g->next)
  1090.         write_pov10_tree (f, g, level+1);
  1091.     }
  1092.     else {
  1093.     first_tri = gnode->index[0]->next->tri;
  1094.     one_texture = 1;
  1095.  
  1096.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1097.         if (t->tri->text_index != first_tri->text_index ||
  1098.         t->tri->text_type  != first_tri->text_type) {
  1099.            one_texture = 0;
  1100.            break;
  1101.         }
  1102.     }
  1103.  
  1104.     if (one_texture) {
  1105.         fprintf (f, "\tobject {\n");
  1106.         fprintf (f, "\t\tunion {\n");
  1107.     }
  1108.  
  1109.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next)
  1110.         write_pov10_triangle (f, t->tri, one_texture);
  1111.  
  1112.     if (one_texture) {
  1113.         fprintf (f, "\t\t}\n\n\t\t");
  1114.         write_pov10_texture (f, first_tri);
  1115.         fprintf (f, "\n\t}\n");
  1116.     }
  1117.     }
  1118.  
  1119.     if (bound_mode == 0)
  1120.         write_pov10_bound (f, gnode);
  1121.  
  1122.     if (level == 1 && use_transform)
  1123.     write_pov10_transform (f, trans_matrix);
  1124.  
  1125.     fprintf (f, "}\n");
  1126. }
  1127.  
  1128.  
  1129. void write_pov10_texture (FILE *f, Triangle *tri)
  1130. {
  1131.     if (tri->text_type == 1)
  1132.     fprintf (f, "texture { %s }", ttable[tri->text_index]);
  1133.     else if (psize < MAX_TEX)
  1134.     fprintf (f, "texture { %s_%u }",
  1135.          object_name, tri->text_index + 1);
  1136.     else
  1137.     fprintf (f, "texture { %s color red %.3f green %.3f blue %.3f }",
  1138.          object_name, ptable[tri->text_index].red,
  1139.          ptable[tri->text_index].green, ptable[tri->text_index].blue);
  1140. }
  1141.  
  1142.  
  1143. /*
  1144.    Writes a transformation matrix as separate POV-Ray scale< >,
  1145.    rotate< >, and translate< > commands
  1146. */
  1147. void write_pov10_transform (FILE *f, Matrix matrix)
  1148. {
  1149.     Vector scale, shear, rotate, transl;
  1150.  
  1151.     /* Decode the matrix into separate operations */
  1152.     mat_decode (matrix, scale, shear, rotate, transl);
  1153.  
  1154.     fprintf (f, "\n\t/* Object transformation */\n");
  1155.  
  1156.     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
  1157.     fprintf (f, "\tscale <%.3f %.3f %.3f>\n", scale[X], scale[Y], scale[Z]);
  1158.  
  1159.     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
  1160.     fprintf (f, "\trotate <%.2f %.2f %.2f>\n", rotate[X], rotate[Y], rotate[Z]);
  1161.  
  1162.     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
  1163.     fprintf (f, "\ttranslate <%.4f %.4f %.4f>\n", transl[X], transl[Y], transl[Z]);
  1164.  
  1165.     /* Can't handle shear but warn if it's there */
  1166.     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
  1167.     printf ("Warning: Significant shear in transformation (ignored)\n");
  1168. }
  1169.  
  1170.  
  1171. /* Write the POV file header */
  1172. void write_pov10_header (FILE *f)
  1173. {
  1174.     int i;
  1175.  
  1176.     if (psize >= MAX_TEX) {
  1177.     fprintf (f, "/* Too many textures, textures generated in-line */\n\n");
  1178.     fprintf (f, "#declare %s = texture {\n", object_name);
  1179.     fprintf (f, "    ambient 0.1\n");
  1180.     fprintf (f, "    diffuse 0.7\n");
  1181.     fprintf (f, "    phong 1.0\n");
  1182.     fprintf (f, "    phong_size 70.0\n");
  1183.     fprintf (f, "}\n\n");
  1184.     }
  1185.     else {
  1186.     if (psize > 0)
  1187.         fprintf (f, "/* Texture declarations for object '%s' */\n", object_name);
  1188.  
  1189.     for (i = 0; i < psize; i++) {
  1190.         fprintf (f, "#declare %s_%u = texture {\n", object_name, i + 1);
  1191.         fprintf (f, "    ambient 0.1\n");
  1192.         fprintf (f, "    diffuse 0.7\n");
  1193.         fprintf (f, "    phong 1.0\n");
  1194.         fprintf (f, "    phong_size 70.0\n");
  1195.         fprintf (f, "    color red %.3f green %.3f blue %.3f\n",
  1196.              ptable[i].red, ptable[i].green, ptable[i].blue);
  1197.         fprintf (f, "}\n\n");
  1198.     }
  1199.     }
  1200. }
  1201.  
  1202.  
  1203. /* Write a triangle (smooth or regular) */
  1204. void write_pov10_triangle (FILE *f, Triangle *tri, int one_texture)
  1205. {
  1206.     Vector norm[3];
  1207.     int    no_smooth = 0;
  1208.  
  1209.     COOPERATE    /* support multitasking */
  1210.  
  1211.     if (one_texture)
  1212.     fprintf (f, "\t\t");
  1213.     else
  1214.     fprintf (f, "\tobject { ");
  1215.  
  1216.     if (smooth_angle > 0.0) {
  1217.     vert_normal (tri, norm);
  1218.  
  1219.     if (vect_equal (norm[0], norm[1]) && vect_equal (norm[1], norm[2]))
  1220.         no_smooth = 1;
  1221.     }
  1222.  
  1223.     if (smooth_angle > 0.0 && !no_smooth) {
  1224.     fprintf (f, "smooth_triangle { <");
  1225.     vect_print (f, vtable[tri->vert[0]], dec_point, ' ');
  1226.     fprintf (f, "> <");
  1227.     vect_print (f, norm[0], 3, ' ');
  1228.     fprintf (f, "> <");
  1229.     vect_print (f, vtable[tri->vert[1]], dec_point, ' ');
  1230.     fprintf (f, "> <");
  1231.     vect_print (f, norm[1], 3, ' ');
  1232.     fprintf (f, "> <");
  1233.     vect_print (f, vtable[tri->vert[2]], dec_point, ' ');
  1234.     fprintf (f, "> <");
  1235.     vect_print (f, norm[2], 3, ' ');
  1236.     fprintf (f, "> }");
  1237.     }
  1238.     else {
  1239.     fprintf (f, "triangle { <");
  1240.     vect_print (f, vtable[tri->vert[0]], dec_point, ' ');
  1241.     fprintf (f, "> <");
  1242.     vect_print (f, vtable[tri->vert[1]], dec_point, ' ');
  1243.     fprintf (f, "> <");
  1244.     vect_print (f, vtable[tri->vert[2]], dec_point, ' ');
  1245.     fprintf (f, "> }");
  1246.     }
  1247.  
  1248.     if (!one_texture) {
  1249.     fprintf (f, " ");
  1250.     write_pov10_texture (f, tri);
  1251.     fprintf (f, " }");
  1252.     }
  1253.  
  1254.     fprintf (f, "\n");
  1255. }
  1256.  
  1257.  
  1258. /* Write a bounding shape */
  1259. void write_pov10_bound (FILE *f, GroupTree *gnode)
  1260. {
  1261.     if (gnode->obj_cnt > 1) {
  1262.     fprintf (f, "\n\tbounded_by { box { <");
  1263.     vect_print (f, gnode->vmin, dec_point + 1, ' ');
  1264.     fprintf (f, "> <");
  1265.     vect_print (f, gnode->vmax, dec_point + 1, ' ');
  1266.     fprintf (f, "> } }\n");
  1267.     }
  1268. }
  1269.  
  1270.  
  1271. /* Write a sub-tree to file */
  1272. void write_pov20_tree (FILE *f, GroupTree *gnode, int level)
  1273. {
  1274.     GroupTree *g;
  1275.     TriList2  *t;
  1276.     Triangle  *first_tri;
  1277.     int       one_texture;
  1278.  
  1279.     if (level == 1)
  1280.     fprintf (f, "\n/* Object '%s' */\n", object_name);
  1281.  
  1282.     if (gnode->obj_cnt > 1)
  1283.         fprintf (f, "union {\n");
  1284.     else
  1285.         fprintf (f, "object {\n");
  1286.  
  1287.     if (gnode->child != NULL) {
  1288.     for (g = gnode->child; g != NULL; g = g->next)
  1289.         write_pov20_tree (f, g, level+1);
  1290.     }
  1291.     else {
  1292.     first_tri = gnode->index[0]->next->tri;
  1293.     one_texture = 1;
  1294.  
  1295.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1296.         if (t->tri->text_index != first_tri->text_index ||
  1297.         t->tri->text_type  != first_tri->text_type) {
  1298.            one_texture = 0;
  1299.            break;
  1300.         }
  1301.     }
  1302.  
  1303.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1304.             fprintf (f, "\t");
  1305.         write_pov20_triangle (f, t->tri, one_texture);
  1306.         }
  1307.  
  1308.     if (one_texture) {
  1309.         fprintf (f, "\n\t");
  1310.         write_pov20_texture (f, first_tri);
  1311.     }
  1312.     }
  1313.  
  1314.     fprintf (f, "\n");
  1315.  
  1316.     if (bound_mode == 0)
  1317.     write_pov20_bound (f, gnode);
  1318.  
  1319.     if (level == 1 && use_transform)
  1320.     write_pov20_transform (f, trans_matrix);
  1321.  
  1322.     fprintf (f, "}\n");
  1323. }
  1324.  
  1325.  
  1326. void write_pov20_texture (FILE *f, Triangle *tri)
  1327. {
  1328.     if (tri->text_type == 1)
  1329.     fprintf (f, "texture { %s }", ttable[tri->text_index]);
  1330.     else if (psize < MAX_TEX)
  1331.     fprintf (f, "texture { %s_%u }",
  1332.          object_name, tri->text_index + 1);
  1333.     else
  1334.     fprintf (f, "texture { %s color red %.3f green %.3f blue %.3f }",
  1335.          object_name, ptable[tri->text_index].red,
  1336.          ptable[tri->text_index].green, ptable[tri->text_index].blue);
  1337. }
  1338.  
  1339.  
  1340. /*
  1341.    Writes a transformation matrix as separate POV-Ray scale< >,
  1342.    rotate< >, and translate< > commands
  1343. */
  1344. void write_pov20_transform (FILE *f, Matrix matrix)
  1345. {
  1346.     Vector scale, shear, rotate, transl;
  1347.  
  1348.     /* Decode the matrix into separate operations */
  1349.     mat_decode (matrix, scale, shear, rotate, transl);
  1350.  
  1351.     fprintf (f, "\n\t/* Object transformation */\n");
  1352.  
  1353.     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
  1354.     fprintf (f, "\tscale <%.3f, %.3f, %.3f>\n", scale[X], scale[Y], scale[Z]);
  1355.  
  1356.     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
  1357.     fprintf (f, "\trotate <%.2f, %.2f, %.2f>\n", rotate[X], rotate[Y], rotate[Z]);
  1358.  
  1359.     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
  1360.     fprintf (f, "\ttranslate <%.4f, %.4f, %.4f>\n", transl[X], transl[Y], transl[Z]);
  1361.  
  1362.     /* Can't handle shear but warn if it's there */
  1363.     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
  1364.     printf ("Warning: Significant shear in transformation (ignored)\n");
  1365. }
  1366.  
  1367.  
  1368. /* Write the POV file header */
  1369. void write_pov20_header (FILE *f)
  1370. {
  1371.     int i;
  1372.  
  1373.     if (psize >= MAX_TEX) {
  1374.     fprintf (f, "/* Too many textures, textures generated in-line */\n\n");
  1375.     fprintf (f, "#declare %s = texture {\n", object_name);
  1376.     fprintf (f, "    finish { Shiny }\n");
  1377.     fprintf (f, "}\n\n");
  1378.     }
  1379.     else {
  1380.     if (psize > 0)
  1381.         fprintf (f, "/* Texture declarations for object '%s' */\n", object_name);
  1382.  
  1383.     for (i = 0; i < psize; i++) {
  1384.         fprintf (f, "#declare %s_%u = texture {\n", object_name, i + 1);
  1385.         fprintf (f, "    finish { Shiny }\n");
  1386.         fprintf (f, "    pigment { color red %.3f green %.3f blue %.3f }\n",
  1387.              ptable[i].red, ptable[i].green, ptable[i].blue);
  1388.         fprintf (f, "}\n\n");
  1389.     }
  1390.     }
  1391. }
  1392.  
  1393.  
  1394. /* Write a triangle (smooth or regular) */
  1395. void write_pov20_triangle (FILE *f, Triangle *tri, int one_texture)
  1396. {
  1397.     Vector norm[3];
  1398.     int    no_smooth = 0;
  1399.  
  1400.     COOPERATE    /* support multitasking */
  1401.  
  1402.     if (smooth_angle > 0.0) {
  1403.     vert_normal (tri, norm);
  1404.  
  1405.     if (vect_equal (norm[0], norm[1]) && vect_equal (norm[1], norm[2]))
  1406.         no_smooth = 1;
  1407.     }
  1408.  
  1409.     if (smooth_angle > 0.0 && !no_smooth) {
  1410.     fprintf (f, "smooth_triangle { <");
  1411.     vect_print (f, vtable[tri->vert[0]], dec_point, ',');
  1412.     fprintf (f, ">, <");
  1413.     vect_print (f, norm[0], 3, ',');
  1414.     fprintf (f, ">, <");
  1415.     vect_print (f, vtable[tri->vert[1]], dec_point, ',');
  1416.     fprintf (f, ">, <");
  1417.     vect_print (f, norm[1], 3, ',');
  1418.     fprintf (f, ">, <");
  1419.     vect_print (f, vtable[tri->vert[2]], dec_point, ',');
  1420.     fprintf (f, ">, <");
  1421.     vect_print (f, norm[2], 3, ',');
  1422.     fprintf (f, "> ");
  1423.     }
  1424.     else {
  1425.     fprintf (f, "triangle { <");
  1426.     vect_print (f, vtable[tri->vert[0]], dec_point, ',');
  1427.     fprintf (f, ">, <");
  1428.     vect_print (f, vtable[tri->vert[1]], dec_point, ',');
  1429.     fprintf (f, ">, <");
  1430.     vect_print (f, vtable[tri->vert[2]], dec_point, ',');
  1431.     fprintf (f, "> ");
  1432.     }
  1433.  
  1434.     if (!one_texture)
  1435.     write_pov20_texture (f, tri);
  1436.  
  1437.     fprintf (f, "}\n");
  1438. }
  1439.  
  1440.  
  1441. /* Write a bounding shape */
  1442. void write_pov20_bound (FILE *f, GroupTree *gnode)
  1443. {
  1444.     if (gnode->obj_cnt > 1) {
  1445.     fprintf (f, "\tbounded_by { box { <");
  1446.     vect_print (f, gnode->vmin, dec_point + 1, ',');
  1447.     fprintf (f, ">, <");
  1448.     vect_print (f, gnode->vmax, dec_point + 1, ',');
  1449.     fprintf (f, "> } }\n");
  1450.     }
  1451. }
  1452.  
  1453.  
  1454. /* Write a sub-tree to file */
  1455. void write_vivid_tree (FILE *f, GroupTree *gnode)
  1456. {
  1457.     TriList2  *t;
  1458.     int       last_index, last_type;
  1459.  
  1460.     last_index = -1;
  1461.     last_type  = -1;
  1462.  
  1463.     fprintf (f, "\n/* Object '%s' */\n", object_name);
  1464.  
  1465.     if (use_transform)
  1466.     write_vivid_transform (f, trans_matrix);
  1467.  
  1468.     if (gnode->child != NULL)
  1469.     abortmsg ("Internal error", 1);
  1470.  
  1471.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1472.     if (t->tri->text_index != last_index ||
  1473.         t->tri->text_type != last_type)
  1474.     {
  1475.         write_vivid_texture (f, t->tri);
  1476.         last_index = t->tri->text_index;
  1477.         last_type  = t->tri->text_type;
  1478.     }
  1479.  
  1480.     write_vivid_triangle (f, t->tri);
  1481.     }
  1482.  
  1483.     if (use_transform)
  1484.     fprintf (f, "transform_pop\n\n");
  1485. }
  1486.  
  1487.  
  1488. /*
  1489.    Writes a transformation matrix as separate Vivid scale,
  1490.    rotate, and translate commands
  1491. */
  1492. void write_vivid_transform (FILE *f, Matrix matrix)
  1493. {
  1494.     Vector scale, shear, rotate, transl;
  1495.  
  1496.     /* Decode the matrix into separate operations */
  1497.     mat_decode (matrix, scale, shear, rotate, transl);
  1498.  
  1499.     fprintf (f, "\n/* Object transformation */\n");
  1500.  
  1501.     fprintf (f, "transform {\n");
  1502.  
  1503.     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
  1504.     fprintf (f, "\tscale %.3f %.3f %.3f\n", scale[X], scale[Y], scale[Z]);
  1505.  
  1506.     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
  1507.     fprintf (f, "\trotate %.2f %.2f %.2f\n", rotate[X], rotate[Y], rotate[Z]);
  1508.  
  1509.     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
  1510.     fprintf (f, "\ttranslate %.4f %.4f %.4f\n", transl[X], transl[Y], transl[Z]);
  1511.  
  1512.     /* Can't handle shear but warn if it's there */
  1513.     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
  1514.     printf ("Warning: Significant shear in transformation (ignored)\n");
  1515.  
  1516.     fprintf (f, "}\n\n");
  1517. }
  1518.  
  1519.  
  1520. void write_vivid_texture (FILE *f, Triangle *tri)
  1521. {
  1522.     if (tri->text_type == 1)
  1523.     fprintf (f, "\n%s /* New texture */\n\n", ttable[tri->text_index]);
  1524.     else
  1525.     fprintf (f, "\n%s_%u /* New texture */\n\n",
  1526.          object_name, tri->text_index + 1);
  1527. }
  1528.  
  1529.  
  1530. /* Write the Vivid file header */
  1531. void write_vivid_header (FILE *f)
  1532. {
  1533.     int i;
  1534.  
  1535.     if (psize > 0)
  1536.     fprintf (f, "/* Texture declarations for object '%s' */\n", object_name);
  1537.  
  1538.     for (i = 0; i < psize; i++) {
  1539.     fprintf (f, "#define %s_%u \\ \n", object_name, i + 1);
  1540.     fprintf (f, "    surface {           \\ \n");
  1541.     fprintf (f, "        diffuse %.3f %.3f %.3f \\ \n",
  1542.             ptable[i].red, ptable[i].green, ptable[i].blue);
  1543.     fprintf (f, "        shine 70 white  \\ \n");
  1544.     fprintf (f, "    }\n\n");
  1545.     }
  1546. }
  1547.  
  1548.  
  1549. /* Write a Vivid triangle patch */
  1550. void write_vivid_triangle (FILE *f, Triangle *tri)
  1551. {
  1552.     Vector norm[3];
  1553.  
  1554.     COOPERATE    /* support multitasking */
  1555.  
  1556.     vert_normal (tri, norm);
  1557.  
  1558.     fprintf (f, "patch {\n");
  1559.     fprintf (f, "\tvertex ");
  1560.     vect_print (f, vtable[tri->vert[0]], dec_point, ' ');
  1561.     fprintf (f, " normal ");
  1562.     vect_print (f, norm[0], 3, ' ');
  1563.     fprintf (f, "\n");
  1564.  
  1565.     fprintf (f, "\tvertex ");
  1566.     vect_print (f, vtable[tri->vert[1]], dec_point, ' ');
  1567.     fprintf (f, " normal ");
  1568.     vect_print (f, norm[1], 3, ' ');
  1569.     fprintf (f, "\n");
  1570.  
  1571.     fprintf (f, "\tvertex ");
  1572.     vect_print (f, vtable[tri->vert[2]], dec_point, ' ');
  1573.     fprintf (f, " normal ");
  1574.     vect_print (f, norm[2], 3, ' ');
  1575.     fprintf (f, "\n");
  1576.  
  1577.     fprintf (f, "}\n\n");
  1578. }
  1579.  
  1580.  
  1581. /* Write a sub-tree to file */
  1582. void write_polyray_tree (FILE *f, GroupTree *gnode)
  1583. {
  1584.     TriList2  *t;
  1585.  
  1586.     fprintf (f, "\n// Object '%s'\n\n", object_name);
  1587.  
  1588.     fprintf (f, "object {\n");
  1589.  
  1590.     if (gnode->child != NULL)
  1591.     abortmsg ("Internal error", 1);
  1592.  
  1593.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1594.     if (t != gnode->index[0]->next)
  1595.         fprintf (f, "\t+\n");
  1596.  
  1597.     write_polyray_triangle (f, t->tri);
  1598.  
  1599.     write_polyray_texture (f, t->tri);
  1600.     }
  1601.  
  1602.     if (use_transform)
  1603.     write_polyray_transform (f, trans_matrix);
  1604.  
  1605.     fprintf (f, "}\n\n");
  1606. }
  1607.  
  1608.  
  1609. /*
  1610.    Writes a transformation matrix as separate Polyray scale< >,
  1611.    rotate< >, and translate< > commands
  1612. */
  1613. void write_polyray_transform (FILE *f, Matrix matrix)
  1614. {
  1615.     Vector scale, shear, rotate, transl;
  1616.  
  1617.     /* Decode the matrix into separate operations */
  1618.     mat_decode (matrix, scale, shear, rotate, transl);
  1619.  
  1620.     fprintf (f, "\n\t// Object transformation\n");
  1621.  
  1622.     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
  1623.     fprintf (f, "\tscale <%.3f, %.3f, %.3f>\n", scale[X], scale[Y], scale[Z]);
  1624.  
  1625.     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
  1626.     fprintf (f, "\trotate <%.2f, %.2f, %.2f>\n", rotate[X], rotate[Y], rotate[Z]);
  1627.  
  1628.     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
  1629.     fprintf (f, "\ttranslate <%.4f, %.4f, %.4f>\n", transl[X], transl[Y], transl[Z]);
  1630.  
  1631.     /* Can't handle shear but warn if it's there */
  1632.     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
  1633.     printf ("Warning: Significant shear in transformation (ignored)\n");
  1634. }
  1635.  
  1636.  
  1637. void write_polyray_texture (FILE *f, Triangle *tri)
  1638. {
  1639.     if (tri->text_type == 1)
  1640.     fprintf (f, "\t\t%s\n\t}\n\n", ttable[tri->text_index]);
  1641.     else
  1642.     fprintf (f, "\t\t%s_%u\n\t}\n\n",
  1643.          object_name, tri->text_index + 1);
  1644. }
  1645.  
  1646.  
  1647. /* Write the Polyray file header */
  1648. void write_polyray_header (FILE *f)
  1649. {
  1650.     int i;
  1651.  
  1652.     if (psize > 0)
  1653.     fprintf (f, "// Texture declarations for object '%s'\n", object_name);
  1654.  
  1655.     for (i = 0; i < psize; i++) {
  1656.     fprintf (f, "define %s_%u\n", object_name, i + 1);
  1657.     fprintf (f, "texture {\n");
  1658.     fprintf (f, "    surface {\n");
  1659.     fprintf (f, "        ambient <%.3f, %.3f, %.3f>, 0.1\n",
  1660.             ptable[i].red, ptable[i].green, ptable[i].blue);
  1661.     fprintf (f, "        diffuse <%.3f, %.3f, %.3f>, 0.7\n",
  1662.             ptable[i].red, ptable[i].green, ptable[i].blue);
  1663.     fprintf (f, "        specular white, 1.0\n");
  1664.     fprintf (f, "        microfacet Reitz 10\n");
  1665.     fprintf (f, "    }\n");
  1666.     fprintf (f, "}\n\n");
  1667.     }
  1668. }
  1669.  
  1670.  
  1671. /* Write a Polyray triangle patch */
  1672. void write_polyray_triangle (FILE *f, Triangle *tri)
  1673. {
  1674.     Vector norm[3];
  1675.  
  1676.     COOPERATE    /* support multitasking */
  1677.  
  1678.     vert_normal (tri, norm);
  1679.  
  1680.     fprintf (f, "\tobject {\n");
  1681.  
  1682.     fprintf (f, "\t\tpatch\t <");
  1683.     vect_print (f, vtable[tri->vert[0]], dec_point, ',');
  1684.     fprintf (f, ">, <");
  1685.     vect_print (f, norm[0], 3, ',');
  1686.     fprintf (f, ">,\n");
  1687.  
  1688.     fprintf (f, "\t\t\t <");
  1689.     vect_print (f, vtable[tri->vert[1]], dec_point, ',');
  1690.     fprintf (f, ">, <");
  1691.     vect_print (f, norm[1], 3, ',');
  1692.     fprintf (f, ">,\n");
  1693.  
  1694.     fprintf (f, "\t\t\t <");
  1695.     vect_print (f, vtable[tri->vert[2]], dec_point, ',');
  1696.     fprintf (f, ">, <");
  1697.     vect_print (f, norm[2], 3, ',');
  1698.     fprintf (f, ">\n");
  1699. }
  1700.  
  1701.  
  1702. /* Update the stats (area, vmin/vmax, child_cnt, etc.) for this node */
  1703. void update_node (GroupTree *gnode)
  1704. {
  1705.     GroupTree *g;
  1706.     TriList2  *t;
  1707.     int       i;
  1708.  
  1709.     vect_init (gnode->vmin, +MAXFLOAT, +MAXFLOAT, +MAXFLOAT);
  1710.     vect_init (gnode->vmax, -MAXFLOAT, -MAXFLOAT, -MAXFLOAT);
  1711.  
  1712.     gnode->obj_cnt   = 0;
  1713.     gnode->child_cnt = 0;
  1714.  
  1715.     if (gnode->index[0] == NULL) {
  1716.     /* Not a leaf node, calc the info from the child nodes */
  1717.  
  1718.     for (g = gnode->child; g != NULL; g = g->next) {
  1719.         ++(gnode->child_cnt);
  1720.  
  1721.         gnode->obj_cnt += g->obj_cnt;
  1722.  
  1723.         for (i = 0; i < 3; i++) {
  1724.         gnode->vmin[i] = fmin (gnode->vmin[i], g->vmin[i]);
  1725.         gnode->vmax[i] = fmax (gnode->vmax[i], g->vmax[i]);
  1726.         }
  1727.     }
  1728.     }
  1729.     else {
  1730.     /* A leaf node, calc the info from the triangle list */
  1731.  
  1732.     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
  1733.         ++(gnode->obj_cnt);
  1734.  
  1735.         for (i = 0; i < 3; i++) {
  1736.         gnode->vmin[i] = fmin (gnode->vmin[i], min_vertex (t->tri, i));
  1737.         gnode->vmax[i] = fmax (gnode->vmax[i], max_vertex (t->tri, i));
  1738.         }
  1739.     }
  1740.     }
  1741.  
  1742.     /* Update total surface area of region */
  1743.     gnode->area = surf_area (gnode->vmax[X] - gnode->vmin[X],
  1744.                  gnode->vmax[Y] - gnode->vmin[Y],
  1745.                  gnode->vmax[Z] - gnode->vmin[Z]);
  1746. }
  1747.  
  1748.  
  1749. void sort_indexes (GroupTree *gnode)
  1750. {
  1751.     int i;
  1752.  
  1753.     for (i = 0; i < 3; i++)
  1754.     quick_sort (gnode->index[i]->next, gnode->index[i]->prev, i);
  1755. }
  1756.  
  1757.  
  1758. void quick_sort (TriList2 *start, TriList2 *end, int axis)
  1759. {
  1760.     TriList2 *a, *b;
  1761.     Triangle *temp;
  1762.     float  middle;
  1763.  
  1764.     if (start == end)
  1765.     return;
  1766.  
  1767.     a = start;
  1768.     b = end;
  1769.     middle = avg_vertex (a->tri, axis);
  1770.  
  1771.     do {
  1772.     while (avg_vertex (b->tri, axis) >= middle && a != b)
  1773.         b = b->prev;
  1774.  
  1775.     if (a != b) {
  1776.         temp   = a->tri;
  1777.         a->tri = b->tri;
  1778.         b->tri = temp;
  1779.  
  1780.         while (avg_vertex (a->tri, axis) <= middle && a != b)
  1781.         a = a->next;
  1782.  
  1783.         if (a != b) {
  1784.         temp   = a->tri;
  1785.         a->tri = b->tri;
  1786.         b->tri = temp;
  1787.         }
  1788.     }
  1789.     } while (a != b);
  1790.  
  1791.     if (a != start)
  1792.     quick_sort (start, a->prev, axis);
  1793.  
  1794.     if (b != end)
  1795.     quick_sort (b->next, end, axis);
  1796. }
  1797.  
  1798.  
  1799. /* Calculate the surface area of a box */
  1800. float surf_area (float  a, float  b, float  c)
  1801. {
  1802.     return 2.0*(a*b + b*c + c*a);
  1803. }
  1804.  
  1805.  
  1806. float max_vertex (Triangle *tri, int axis)
  1807. {
  1808.     float  max_v, val;
  1809.     int i;
  1810.  
  1811.     max_v = -MAXFLOAT;
  1812.  
  1813.     for (i = 0; i < 3; i++) {
  1814.     val = vtable[tri->vert[i]][axis];
  1815.  
  1816.     if (val > max_v)
  1817.         max_v = val;
  1818.     }
  1819.  
  1820.     return max_v;
  1821. }
  1822.  
  1823.  
  1824. float min_vertex (Triangle *tri, int axis)
  1825. {
  1826.     float  min_v, val;
  1827.     int i;
  1828.  
  1829.     min_v = +MAXFLOAT;
  1830.  
  1831.     for (i = 0; i < 3; i++) {
  1832.     val = vtable[tri->vert[i]][axis];
  1833.  
  1834.     if (val < min_v)
  1835.         min_v = val;
  1836.     }
  1837.  
  1838.     return min_v;
  1839. }
  1840.  
  1841.  
  1842. float avg_vertex (Triangle *tri, int axis)
  1843. {
  1844.     float  avg;
  1845.  
  1846.     avg = (vtable[tri->vert[0]][axis] + vtable[tri->vert[1]][axis] +
  1847.        vtable[tri->vert[2]][axis])/3.0;
  1848.  
  1849.     return avg;
  1850. }
  1851.  
  1852.  
  1853. /* Build an index of which triangles touch each vertex.  Used to */
  1854. /* speed up smooth triangle normal calculations. */
  1855. void build_tri_index()
  1856. {
  1857.     GroupTree *g;
  1858.     TriList   *temp;
  1859.     TriList2  *t;
  1860.     unsigned  i, vert_no;
  1861.  
  1862.     if (vsize == 0)
  1863.     return;
  1864.  
  1865.     tri_index = malloc (vsize * sizeof(TriList));
  1866.     if (tri_index == NULL)
  1867.     abortmsg ("Insufficient memory for smooth triangles.", 1);
  1868.  
  1869.     for (i = 0; i < vsize; i++)
  1870.     tri_index[i] = NULL;
  1871.  
  1872.     for (g = groot; g != NULL; g = g->next) {
  1873.     for (t = g->index[0]->next; t != g->index[0]; t = t->next) {
  1874.         for (i = 0; i < 3; i++) {
  1875.         vert_no = t->tri->vert[i];
  1876.         temp = tri_index[vert_no];
  1877.         tri_index[vert_no] = malloc (sizeof(TriList));
  1878.         if (tri_index[vert_no] == NULL)
  1879.             abortmsg ("Insufficient memory for smooth triangles.\n", 1);
  1880.  
  1881.         tri_index[vert_no]->tri = t->tri;
  1882.         tri_index[vert_no]->next = temp;
  1883.         }
  1884.     }
  1885.     }
  1886.  
  1887. }
  1888.  
  1889.  
  1890. void dump_tri_index()
  1891. {
  1892.     TriList *temp;
  1893.     int     i;
  1894.  
  1895.     for (i = 0; i < vsize; i++) {
  1896.     while (tri_index[i] != NULL) {
  1897.         temp = tri_index[i];
  1898.         tri_index[i] = tri_index[i]->next;
  1899.         free (temp);
  1900.     }
  1901.     }
  1902.  
  1903.     free (tri_index);
  1904. }
  1905.  
  1906.  
  1907. /* Calculates the smooth triangle normal for this vertex */
  1908. void vert_normal (Triangle *t, Vector *norm)
  1909. {
  1910.     Vector  curr_norm, new_norm;
  1911.     TriList *p;
  1912.     int     i;
  1913.  
  1914.     tri_normal (t, curr_norm);
  1915.  
  1916.     for (i = 0; i < 3; i++) {
  1917.     vect_init (norm[i], 0.0, 0.0, 0.0);
  1918.  
  1919.     for (p = tri_index[t->vert[i]]; p != NULL; p = p->next) {
  1920.         tri_normal (p->tri, new_norm);
  1921.         if (vect_angle (curr_norm, new_norm) < smooth_angle)
  1922.         vect_add (norm[i], norm[i], new_norm);
  1923.     }
  1924.  
  1925.     vect_normalize (norm[i]);
  1926.     }
  1927. }
  1928.  
  1929.  
  1930. /* Calculates the normal to the specified triangle */
  1931. void tri_normal (Triangle *t, Vector normal)
  1932. {
  1933.     Vector ab, ac;
  1934.  
  1935.     vect_sub (ab, vtable[t->vert[1]], vtable[t->vert[0]]);
  1936.     vect_sub (ac, vtable[t->vert[2]], vtable[t->vert[0]]);
  1937.     vect_cross (normal, ac, ab);
  1938.  
  1939.     vect_normalize (normal);
  1940. }
  1941.  
  1942.  
  1943. /* Find the specified rgb values in the palette table */
  1944. unsigned pal_lookup (float  red, float  green, float  blue)
  1945. {
  1946.     int i;
  1947.  
  1948.     /* The palette table is usually small so just do a simple linear search */
  1949.     for (i = psize-1; i >= 0; i--) {
  1950.     if (ptable[i].red   == red &&
  1951.         ptable[i].green == green &&
  1952.         ptable[i].blue  == blue)
  1953.       break;
  1954.     }
  1955.  
  1956.     if (i >= 0)
  1957.     return i;    /* found, return the table index */
  1958.  
  1959.     /* not found, insert the new palette into the table */
  1960.     ++psize;
  1961.     if (psize > pmax) {
  1962.     /* table not big enough, resize it */
  1963.     pmax = pmax + 10;
  1964.     ptable = realloc (ptable, pmax * sizeof(Palette));
  1965.     if (ptable == NULL)
  1966.         abortmsg ("Insufficient memory to expand palette table.", 1);
  1967.     }
  1968.  
  1969.     ptable[psize-1].red   = red;
  1970.     ptable[psize-1].green = green;
  1971.     ptable[psize-1].blue  = blue;
  1972.  
  1973.     return (psize-1);
  1974. }
  1975.  
  1976.  
  1977. /* Find the specified named texture in the texture table */
  1978. unsigned texture_lookup (char *texture_name)
  1979. {
  1980.     int i;
  1981.  
  1982.     /* The texture table is usually small so just do a simple linear search */
  1983.     for (i = tsize-1; i >= 0; i--) {
  1984.     if (strcmp (ttable[i], texture_name) == 0)
  1985.         break;
  1986.     }
  1987.  
  1988.     if (i >= 0)
  1989.     return i;    /* found, return the table index */
  1990.  
  1991.     /* not found, insert the new texture into the table */
  1992.     ++tsize;
  1993.     if (tsize > tmax) {
  1994.     /* table not big enough, resize it */
  1995.     tmax = tmax + 10;
  1996.     ttable = realloc (ttable, tmax * sizeof(Texture));
  1997.     if (ttable == NULL)
  1998.         abortmsg ("Insufficient memory to expand palette table.", 1);
  1999.     }
  2000.  
  2001.     ttable[tsize-1] = malloc (strlen(texture_name) + 1);
  2002.     if (ttable[tsize-1] == NULL)
  2003.     abortmsg ("Insufficient memory for texture name.", 1);
  2004.  
  2005.     strcpy (ttable[tsize-1], texture_name);
  2006.  
  2007.     return (tsize-1);
  2008. }
  2009.  
  2010.  
  2011. /* Find the specified vertex in the vertex table */
  2012. unsigned vert_lookup (float  x, float  y, float  z)
  2013. {
  2014.     VertList *p, *new_node;
  2015.     unsigned hash;
  2016.  
  2017.     /* Vertex table is usually very large, use hash lookup */
  2018.     hash = (unsigned)((int)(326.4*x) ^ (int)(694.7*y) ^ (int)(1423.6*z)) % HASHSIZE;
  2019.  
  2020.     for (p = vert_hash[hash]; p != NULL; p = p->next) {
  2021.     if (vtable[p->vert][0] == x && vtable[p->vert][1] == y &&
  2022.         vtable[p->vert][2] == z) break;
  2023.     }
  2024.  
  2025.     if (p != NULL)
  2026.     return (p->vert);   /* found, return the table index */
  2027.  
  2028.     /* not found, insert the new vertex into the table */
  2029.     ++vsize;
  2030.     if (vsize > vmax) {
  2031.     /* table not big enough, expand it */
  2032.     vmax = vmax + 100;
  2033.     vtable = realloc (vtable, vmax * sizeof(Vector));
  2034.     if (vtable == NULL)
  2035.         abortmsg ("Insufficient memory for vertices.\n", 1);
  2036.     }
  2037.  
  2038.     vect_init (vtable[vsize-1], x, y, z);
  2039.  
  2040.     new_node = malloc (sizeof(VertList));
  2041.     if (new_node == NULL)
  2042.     abortmsg ("Insufficient memory for hash table.", 1);
  2043.  
  2044.     new_node->vert  = vsize-1;
  2045.     new_node->next  = vert_hash[hash];
  2046.     vert_hash[hash] = new_node;
  2047.  
  2048.     return (vsize-1);
  2049. }
  2050.  
  2051.  
  2052. /* Checks if triangle is degenerate (zero area) */
  2053. int  degen_tri (float  ax, float  ay, float  az,
  2054.         float  bx, float  by, float  bz,
  2055.         float  cx, float  cy, float  cz)
  2056. {
  2057.     Vector  ab, ac, norm;
  2058.     double  mag, fact;
  2059.  
  2060.     fact = pow (10.0, dec_point);
  2061.  
  2062.     /* Round the coords off to the output precision before checking */
  2063.     ax = floor((ax*fact) + 0.5)/fact;
  2064.     ay = floor((ay*fact) + 0.5)/fact;
  2065.     az = floor((az*fact) + 0.5)/fact;
  2066.     bx = floor((bx*fact) + 0.5)/fact;
  2067.     by = floor((by*fact) + 0.5)/fact;
  2068.     bz = floor((bz*fact) + 0.5)/fact;
  2069.     cx = floor((cx*fact) + 0.5)/fact;
  2070.     cy = floor((cy*fact) + 0.5)/fact;
  2071.     cz = floor((cz*fact) + 0.5)/fact;
  2072.  
  2073.     vect_init (ab, ax-bx, ay-by, az-bz);
  2074.     vect_init (ac, ax-cx, ay-cy, az-cz);
  2075.     vect_cross (norm, ab, ac);
  2076.  
  2077.     mag = vect_mag(norm);
  2078.  
  2079.     return (mag < DEGEN_TOL);
  2080. }
  2081.  
  2082.  
  2083. void abortmsg (char *msg, int exit_code)
  2084. {
  2085.     printf ("\n%s\n", msg);
  2086.     exit (exit_code);
  2087. }
  2088.  
  2089.  
  2090. float  fmin (float  a, float  b)
  2091. {
  2092.     if (a < b)
  2093.     return a;
  2094.     else
  2095.     return b;
  2096. }
  2097.  
  2098.  
  2099. float  fmax (float  a, float  b)
  2100. {
  2101.     if (a > b)
  2102.     return a;
  2103.     else
  2104.     return b;
  2105. }
  2106.  
  2107.  
  2108. void add_ext (char *fname, char *ext, int force)
  2109. {
  2110.     int i;
  2111.  
  2112.     for (i = 0; i < strlen(fname); i++)
  2113.     if (fname[i] == '.') break;
  2114.  
  2115.     if (fname[i] == '\0' || force) {
  2116.     if (strlen(ext) > 0)
  2117.         fname[i++] = '.';
  2118.  
  2119.     strcpy (&fname[i], ext);
  2120.     }
  2121. }
  2122.  
  2123.  
  2124. void cleanup_name (char *name)
  2125. {
  2126.     char *tmp = malloc (strlen(name)+1);
  2127.     int  i;
  2128.  
  2129.     /* Remove any leading blanks or quotes */
  2130.     i = 0;
  2131.     while ((name[i] == ' ' || name[i] == '"') && name[i] != '\0')
  2132.     i++;
  2133.  
  2134.     strcpy (tmp, &name[i]);
  2135.  
  2136.     /* Remove any trailing blanks or quotes */
  2137.     for (i = strlen(tmp)-1; i >= 0; i--) {
  2138.     if (isprint(tmp[i]) && !isspace(tmp[i]) && tmp[i] != '"')
  2139.         break;
  2140.     else
  2141.         tmp[i] = '\0';
  2142.     }
  2143.  
  2144.     strcpy (name, tmp);
  2145.  
  2146.     /* Prefix the letter 'N' to materials that begin with a digit */
  2147.     if (!isdigit (name[0]))
  2148.        strcpy (tmp, name);
  2149.     else {
  2150.        tmp[0] = 'N';
  2151.        strcpy (&tmp[1], name);
  2152.     }
  2153.  
  2154.     /* Replace all illegal charaters in name with underscores */
  2155.     for (i = 0; tmp[i] != '\0'; i++) {
  2156.        if (!isalnum(tmp[i]))
  2157.        tmp[i] = '_';
  2158.     }
  2159.  
  2160.     strcpy (name, tmp);
  2161.  
  2162.     free (tmp);
  2163. }
  2164.  
  2165.  
  2166.