Back to index

radiance  4R0+20100331
rayopt.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: rayopt.c,v 1.4 2007/09/05 01:36:37 greg Exp $";
00003 #endif
00004 /*-------------------------------------------------------------------------
00005 
00006                Triangle Bounder/Smoother for POV-Ray
00007                   by Steve Anger 1993
00008 
00009     A number of C routines that can be used to generate POV-Ray ray tracer
00010  files from triangle data.  Supports generation of smooth triangles and an
00011  optimal set of bounding shapes for much faster traces.  Output files are
00012  compatible with POV-Ray v1.0.
00013 
00014 --------------------------------------------------------------------------*/
00015 
00016 #ifdef __TURBOC__
00017 #include <alloc.h>
00018 #endif
00019 
00020 #include <stdio.h>
00021 #include <stdlib.h>
00022 #include <string.h>
00023 #include <ctype.h>
00024 #include <math.h>
00025 #include "vect.h"
00026 #include "rayopt.h"
00027 
00028 #if defined(applec) || defined(THINK_C)
00029 #include "RAW2POV.mac.h"
00030 #else
00031 #define COOPERATE
00032 #endif
00033 
00034 #define HASHSIZE  1000          /* Size of hash table for vertex lookup */
00035 #define DEGEN_TOL (1e-8)        /* float comparison tolerance for checking */
00036                             /* for degenerate triangles */
00037 #define MAX_TEX   500           /* Maximum allowable number of texture */
00038                             /* declarations */
00039 
00040 #define POV10   0
00041 #define POV20   1
00042 #define VIVID   2
00043 #define POLYRAY 3
00044 #define MGF   4
00045 
00046 #ifndef MAXFLOAT
00047 #define MAXFLOAT (1e37)
00048 #endif
00049 
00050                             /* computed luminances for RGB */
00051 #define CIE_Y_r             0.265
00052 #define CIE_Y_g             0.670
00053 #define CIE_Y_b             0.065
00054 
00055 typedef struct {
00056     float red;
00057     float green;
00058     float blue;
00059 } Palette;
00060 
00061 typedef char *Texture;
00062 
00063 typedef struct {
00064     unsigned vert[3];
00065     unsigned text_index;
00066     char     text_type;
00067     char     flag;
00068 } Triangle;
00069 
00070 
00071 /* Linked list of triangles */
00072 typedef struct TList {
00073     Triangle     *tri;
00074     struct TList *next;
00075 } TriList;
00076 
00077 
00078 /* Double linked list of triangles */
00079 typedef struct TList2 {
00080     Triangle      *tri;
00081     struct TList2 *prev;
00082     struct TList2 *next;
00083 } TriList2;
00084 
00085 
00086 /* List of triangle vertices */
00087 typedef struct VList {
00088     unsigned     vert;
00089     struct VList *next;
00090 } VertList;
00091 
00092 
00093 /* List of triangle groups */
00094 typedef struct GTree {
00095     TriList2     *index[3];    /* Triangles indexed by x, y, and z coord */
00096     Vector       vmin;         /* min/max extents of triangle vertices */
00097     Vector       vmax;         /*    "       "     "     "        "     */
00098     float        area;         /* Total surface area of bounding region */
00099     unsigned     obj_cnt;      /* Total number of triangles in group */
00100     int          child_cnt;    /* Number of children */
00101     int          split_cnt;    /* Number of times this node has been split */
00102     struct GTree *parent;      /* Parent of this node */
00103     struct GTree *next;        /* Next node at this level */
00104     struct GTree *child;       /* First child of this ndoe */
00105 } GroupTree;
00106 
00107 static Palette   *ptable;      /* Palette table */
00108 static unsigned  pmax;         /* Maximum size of table */
00109 static unsigned  psize;        /* Current size */
00110 
00111 static Texture   *ttable;      /* Named texture table */
00112 static unsigned  tmax;         /* Maximum size of table */
00113 static unsigned  tsize;        /* Current size */
00114 
00115 static Vector    *vtable;      /* Vertice table */
00116 static unsigned  vmax;         /* Maximum size of table */
00117 static unsigned  vsize;        /* Current size */
00118 
00119 static Vector    gmin = {+MAXFLOAT, +MAXFLOAT, +MAXFLOAT};
00120 static Vector    gmax = {-MAXFLOAT, -MAXFLOAT, -MAXFLOAT};
00121 
00122 static Matrix    trans_matrix;
00123 static int       use_transform = 0;
00124 
00125 static VertList  **vert_hash;    /* Hash table for looking up vertices */
00126 static TriList   **tri_index;    /* Index for smooth triangle generation */
00127 
00128 static GroupTree *groot;         /* Tree representing the object hierarchy */
00129 
00130 static int       initialized  = 0;
00131 static int       quiet_mode   = 0;
00132 static int       bound_mode   = 0;
00133 static float     smooth_angle = 0.0;
00134 static unsigned  vert_init    = 0;
00135 static int       dec_point    = 4;
00136 static int       out_format   = POV10;
00137 
00138 static char      out_file[64] = "rayopt.pov";
00139 static char      inc_file[64] = "rayopt.inc";
00140 
00141 static unsigned  tot_bounds   = 0;
00142 static unsigned  object_cnt   = 0;
00143 
00144 static Vector    last_vmin = {0.0, 0.0, 0.0};
00145 static Vector    last_vmax = {0.0, 0.0, 0.0};
00146 static unsigned  last_vert_cnt = 0;
00147 static unsigned  last_tri_cnt = 0;
00148 static float     last_index = 0.0;
00149 static unsigned  last_bounds = 0;
00150 
00151 static Palette   last_pal;
00152 static char      last_texture[64] = "";
00153 static unsigned  texture_index;
00154 static char      texture_type;
00155 static char      object_name[64] = "";
00156 
00157 static float     orig_tpr;    /* Number of Tests Per Ray before optimization */
00158 static float     final_tpr;   /*    "   "    "    "   "  after optimization */
00159 static float     bound_cost;  /* Cost of testing a bound relative to testing */
00160                            /* a triangle */
00161 
00162 /* Function prototypes */
00163 void init_object (void);
00164 void cleanup_object (void);
00165 float calc_tpr (GroupTree *gnode);
00166 GroupTree *create_group (void);
00167 void delete_tree (GroupTree *gnode);
00168 void optimize_tree (GroupTree *gnode);
00169 void test_split (GroupTree *gnode, int axis, float *best_rtpr, TriList2 **
00170        best_loc);
00171 void split_group (GroupTree *gnode, int axis, TriList2 *split_loc, GroupTree *
00172        *group_a, GroupTree **group_b);
00173 void write_file (void);
00174 void write_box (Vector v1, Vector v2, Triangle *tri);
00175 void write_pov10_tree (FILE *f, GroupTree *gnode, int level);
00176 void write_pov10_texture (FILE *f, Triangle *tri);
00177 void write_pov10_transform (FILE *f, Matrix matrix);
00178 void write_pov10_header (FILE *f);
00179 void write_pov10_triangle (FILE *f, Triangle *tri, int one_texture);
00180 void write_pov10_bound (FILE *f, GroupTree *gnode);
00181 void write_pov20_tree (FILE *f, GroupTree *gnode, int level);
00182 void write_pov20_texture (FILE *f, Triangle *tri);
00183 void write_pov20_transform (FILE *f, Matrix matrix);
00184 void write_pov20_header (FILE *f);
00185 void write_pov20_triangle (FILE *f, Triangle *tri, int one_texture);
00186 void write_pov20_bound (FILE *f, GroupTree *gnode);
00187 void write_vivid_tree (FILE *f, GroupTree *gnode);
00188 void write_vivid_transform (FILE *f, Matrix matrix);
00189 void write_vivid_texture (FILE *f, Triangle *tri);
00190 void write_vivid_header (FILE *f);
00191 void write_vivid_triangle (FILE *f, Triangle *tri);
00192 void write_polyray_tree (FILE *f, GroupTree *gnode);
00193 void write_polyray_transform (FILE *f, Matrix matrix);
00194 void write_polyray_texture (FILE *f, Triangle *tri);
00195 void write_polyray_header (FILE *f);
00196 void write_polyray_triangle (FILE *f, Triangle *tri);
00197 void write_mgf_tree (FILE *f, GroupTree *gnode, int level);
00198 void write_mgf_texture (FILE *f, Triangle *tri);
00199 void write_mgf_transform (FILE *f, Matrix matrix);
00200 void write_mgf_header (FILE *f);
00201 void write_mgf_triangle (FILE *f, Triangle *tri);
00202 void update_node (GroupTree *gnode);
00203 void sort_indexes (GroupTree *gnode);
00204 void quick_sort (TriList2 *start, TriList2 *end, int axis);
00205 float surf_area (float a, float b, float c);
00206 float max_vertex (Triangle *tri, int axis);
00207 float min_vertex (Triangle *tri, int axis);
00208 float avg_vertex (Triangle *tri, int axis);
00209 void build_tri_index (void);
00210 void dump_tri_index (void);
00211 void vert_normal (Triangle *t, Vector *norm);
00212 void tri_normal (Triangle *t, Vector normal);
00213 unsigned pal_lookup (float red, float green, float blue);
00214 unsigned texture_lookup (char *texture_name);
00215 unsigned vert_lookup (float x, float y, float z);
00216 int degen_tri (float ax, float ay, float az, float bx, float by, float bz,
00217         float cx, float cy, float cz);
00218 void abortmsg (char *msg, int exit_code);
00219 float fltmin (float a, float b);
00220 float fltmax (float a, float b);
00221 void add_ext (char *fname, char *ext, int force);
00222 void cleanup_name (char *name);
00223 
00224 
00225 void opt_set_format (int format)
00226 {
00227     if (format != POV10 && format != POV20 && format != VIVID
00228               && format != POLYRAY && format != MGF)
00229        abortmsg ("ERROR: Invalid parameter passed to opt_set_format.", 1);
00230 
00231     out_format = format;
00232 }
00233 
00234 
00235 void opt_set_fname (char *out_name, char *inc_name)
00236 {
00237     FILE *f;
00238 
00239     strcpy (out_file, out_name);
00240 
00241     if (strlen(inc_name) > 0)
00242        strcpy (inc_file, inc_name);
00243     else {
00244        strcpy (inc_file, out_file);
00245 
00246        switch (out_format) {
00247            case POV10:
00248            case POV20:   add_ext (inc_file, "inc", 1);
00249                        break;
00250            case VIVID:   add_ext (inc_file, "vo", 1);
00251                        break;
00252            case POLYRAY: add_ext (inc_file, "inc", 1);
00253                        break;
00254            case MGF:     add_ext (inc_file, "inc", 1);
00255                        break;
00256        }
00257     }
00258 
00259     if (strcmp (out_file, inc_file) == 0)
00260        abortmsg ("Main file and include file cannot have the same name", 1);
00261 
00262     if ((f = fopen (out_file, "w")) == NULL) {
00263        printf ("Cannot open output file %s\n", out_file);
00264        exit (1);
00265     }
00266 
00267     fclose (f);
00268 
00269     if ((f = fopen (inc_file, "w")) == NULL) {
00270        printf ("Cannot open output file %s\n", inc_file);
00271        exit (1);
00272     }
00273 
00274     fclose (f);
00275 }
00276 
00277 
00278 void opt_set_quiet (int quiet)
00279 {
00280     if (quiet != 0 && quiet != 1)
00281        abortmsg ("ERROR: Invalid parameter passed to opt_set_quiet.", 1);
00282 
00283     quiet_mode = quiet;
00284 }
00285 
00286 
00287 void opt_set_bound (int bound)
00288 {
00289     if (bound != 0 && bound != 1 && bound != 2)
00290        abortmsg ("ERROR: Invalid parameter passed to opt_set_bound.", 1);
00291 
00292     bound_mode = bound;
00293 }
00294 
00295 
00296 void opt_set_smooth (float  smooth)
00297 {
00298     if (smooth < 0.0 || smooth > 180.0)
00299        abortmsg ("ERROR: Invalid parameter passed to opt_set_smooth.", 1);
00300 
00301     smooth_angle = smooth;
00302 }
00303 
00304 
00305 void opt_set_vert (unsigned vert)
00306 {
00307     vert_init = vert;
00308 }
00309 
00310 
00311 void opt_set_dec (int dec)
00312 {
00313     if (dec < 0 || dec > 9)
00314        abortmsg ("ERROR: Invalid parameter passed to opt_set_dec.", 1);
00315 
00316     dec_point = dec;
00317 }
00318 
00319 
00320 void opt_set_color (float  red, float  green, float  blue)
00321 {
00322     if (!initialized)
00323        init_object();
00324 
00325     if (last_pal.red != red || last_pal.green != green ||
00326                             last_pal.blue != blue || psize == 0)
00327     {
00328        last_pal.red   = red;
00329        last_pal.green = green;
00330        last_pal.blue  = blue;
00331 
00332        texture_index = pal_lookup (red, green, blue);
00333     }
00334 
00335     texture_type = 0;   /* An RGB texture */
00336 }
00337 
00338 
00339 void opt_set_texture (char *texture_name)
00340 {
00341     char new_texture[64];
00342 
00343     if (!initialized)
00344        init_object();
00345 
00346     strcpy (new_texture, texture_name);
00347     cleanup_name (new_texture);
00348 
00349     if (strcmp (last_texture, new_texture) != 0) {
00350        strcpy (last_texture, new_texture);
00351        texture_index = texture_lookup (new_texture);
00352     }
00353 
00354     texture_type = 1;   /* A named texture */
00355 }
00356 
00357 
00358 /* Set a transformation matrix for the next object */
00359 void opt_set_transform (Matrix mat)
00360 {
00361     int i, j;
00362 
00363     for (i = 0; i < 4; i++) {
00364        for (j = 0; j < 3; j++)
00365            trans_matrix[i][j] = mat[i][j];
00366     }
00367 
00368     use_transform = 1;
00369 }
00370 
00371 
00372 void opt_clear_transform()
00373 {
00374     use_transform = 0;
00375 }
00376 
00377 
00378 /* Add a new triangle to the database */
00379 int opt_add_tri (float  ax, float  ay, float  az,
00380                float  bx, float  by, float  bz,
00381                float  cx, float  cy, float  cz)
00382 {
00383     TriList2 *new_node;
00384     Triangle *new_tri;
00385     int      i;
00386 
00387     /* Check if the triangle is degenerate (zero area), if so return -1 */
00388     if (degen_tri (ax, ay, az, bx, by, bz, cx, cy, cz))
00389        return -1;
00390 
00391     if (!initialized)
00392        init_object();
00393 
00394     /* Allocate memory for the new triangle */
00395     new_tri = malloc (sizeof(Triangle));
00396     if (new_tri == NULL)
00397        abortmsg ("Insufficient memory for new triangles.", 1);
00398 
00399     /* Look up the vertex and texture indexes */
00400     new_tri->vert[0] = vert_lookup (ax, ay, az);
00401     new_tri->vert[1] = vert_lookup (bx, by, bz);
00402     new_tri->vert[2] = vert_lookup (cx, cy, cz);
00403 
00404     new_tri->text_index = texture_index;
00405     new_tri->text_type  = texture_type;
00406 
00407     new_tri->flag = 0;
00408 
00409     for (i = 0; i < 3; i++) {
00410        /* Create a new index node */
00411        new_node = malloc (sizeof(TriList2));
00412        if (new_node == NULL)
00413            abortmsg ("Insufficient memory for triangles.", 1);
00414 
00415        /* Point the index entry to the new triangle */
00416        new_node->tri = new_tri;
00417 
00418        /* Insert the new index node into the list */
00419        new_node->next = groot->index[i];
00420        new_node->prev = groot->index[i]->prev;
00421        groot->index[i]->prev->next = new_node;
00422        groot->index[i]->prev = new_node;
00423     }
00424 
00425     ++(groot->obj_cnt);
00426 
00427     return 0;
00428 }
00429 
00430 
00431 /* For compatability */
00432 void opt_write_pov (char *obj_name)
00433 {
00434     opt_write_file (obj_name);
00435 }
00436 
00437 
00438 /* Optimize and write file */
00439 void opt_write_file (char *obj_name)
00440 {
00441     VertList *temp;
00442     int      i;
00443 
00444     if (out_format != POV10 && out_format != POV20)
00445        bound_mode = 2;
00446 
00447     if (!initialized || groot->obj_cnt == 0) {
00448        orig_tpr = 1.0;
00449        final_tpr = 0.0;
00450        tot_bounds = 0;
00451        return;   /* No triangles where ever added, nothing to write */
00452     }
00453 
00454     strcpy (object_name, obj_name);
00455     cleanup_name (object_name);
00456 
00457     ++object_cnt;
00458 
00459     /* Dump the hash table, don't need it any more */
00460     for (i = 0; i < HASHSIZE; i++) {
00461        while (vert_hash[i] != NULL) {
00462            temp = vert_hash[i];
00463            vert_hash[i] = vert_hash[i]->next;
00464            free (temp);
00465        }
00466     }
00467 
00468     /* Build the vertice index */
00469     build_tri_index();
00470 
00471     if (bound_mode != 2) {
00472        if (!quiet_mode)
00473            printf ("Building indexes\n");
00474 
00475        sort_indexes (groot);
00476     }
00477 
00478     update_node (groot);
00479 
00480     if (!quiet_mode) {
00481        printf ("Adding bounds (1)\r");
00482        fflush(stdout);;
00483     }
00484 
00485     /* Optimize the tree */
00486     orig_tpr = calc_tpr (groot);
00487 
00488     if (bound_mode != 2)
00489        optimize_tree (groot);
00490 
00491     final_tpr = calc_tpr (groot);
00492 
00493     /* Write the file */
00494     write_file();
00495 
00496     /* Free up the vertex index */
00497     dump_tri_index();
00498 
00499     cleanup_object();
00500 }
00501 
00502 
00503 void opt_write_box (char *obj_name)
00504 {
00505     VertList *temp;
00506     int i;
00507 
00508     if (!initialized || groot->obj_cnt == 0) {
00509        orig_tpr = 1.0;
00510        final_tpr = 0.0;
00511        tot_bounds = 0;
00512        return;   /* No triangles where ever added, nothing to write */
00513     }
00514 
00515     strcpy (object_name, obj_name);
00516     cleanup_name (object_name);
00517 
00518     ++object_cnt;
00519 
00520     /* Dump the hash table, don't need it any more */
00521     for (i = 0; i < HASHSIZE; i++) {
00522        while (vert_hash[i] != NULL) {
00523            temp = vert_hash[i];
00524            vert_hash[i] = vert_hash[i]->next;
00525            free (temp);
00526        }
00527     }
00528 
00529     orig_tpr = final_tpr = 1.0;
00530 
00531     update_node (groot);
00532 
00533     write_box (groot->vmin, groot->vmax, groot->index[0]->next->tri);
00534 
00535     cleanup_object();
00536 }
00537 
00538 
00539 void opt_finish()
00540 {
00541     FILE *f;
00542 
00543     f = fopen (out_file, "a");
00544 
00545     switch (out_format) {
00546        case POV10:
00547             if (object_cnt > 2 && bound_mode == 0)
00548                fprintf (f, "composite {  /* All Objects */\n    ");
00549 
00550            fprintf (f, "#include \"%s\"\n", inc_file);
00551 
00552            if (object_cnt > 2 && bound_mode == 0) {
00553               fprintf (f, "\n");
00554               fprintf (f, "    bounded_by {\n");
00555               fprintf (f, "        box { <%.4f %.4f %.4f> <%.4f %.4f %.4f> }\n",
00556                                     gmin[X], gmin[Y], gmin[Z],
00557                                     gmax[X], gmax[Y], gmax[Z]);
00558               fprintf (f, "    }\n");
00559                fprintf (f, "}\n\n");
00560             }
00561            break;
00562 
00563        case POV20:
00564             if (object_cnt > 2 && bound_mode == 0)
00565                 fprintf (f, "union {\n    ");
00566 
00567            fprintf (f, "#include \"%s\"\n", inc_file);
00568 
00569            if (object_cnt > 2 && bound_mode == 0) {
00570               fprintf (f, "\n");
00571               fprintf (f, "    bounded_by {\n");
00572               fprintf (f, "        box { <%.4f, %.4f, %.4f>, <%.4f, %.4f, %.4f> }\n",
00573                                     gmin[X], gmin[Y], gmin[Z],
00574                                     gmax[X], gmax[Y], gmax[Z]);
00575               fprintf (f, "    }\n");
00576                 fprintf (f, "}\n\n");
00577             }
00578            break;
00579 
00580        case VIVID:
00581            fprintf (f, "#include %s\n\n", inc_file);
00582            break;
00583 
00584        case POLYRAY:
00585            fprintf (f, "include \"%s\"\n\n", inc_file);
00586            break;
00587 
00588        case MGF:
00589            fprintf (f, "i %s\n", inc_file);
00590            break;
00591     }
00592 
00593     fclose (f);
00594 }
00595 
00596 
00597 
00598 void opt_get_limits (float  *min_x, float  *min_y, float  *min_z,
00599                    float  *max_x, float  *max_y, float  *max_z)
00600 {
00601     *min_x = last_vmin[X];
00602     *min_y = last_vmin[Y];
00603     *min_z = last_vmin[Z];
00604 
00605     *max_x = last_vmax[X];
00606     *max_y = last_vmax[Y];
00607     *max_z = last_vmax[Z];
00608 }
00609 
00610 
00611 void opt_get_glimits (float  *min_x, float  *min_y, float  *min_z,
00612                     float  *max_x, float  *max_y, float  *max_z)
00613 {
00614     *min_x = gmin[X];
00615     *min_y = gmin[Y];
00616     *min_z = gmin[Z];
00617 
00618     *max_x = gmax[X];
00619     *max_y = gmax[Y];
00620     *max_z = gmax[Z];
00621 }
00622 
00623 
00624 unsigned opt_get_vert_cnt()
00625 {
00626     return last_vert_cnt;
00627 }
00628 
00629 
00630 unsigned opt_get_tri_cnt()
00631 {
00632     return last_tri_cnt;
00633 }
00634 
00635 
00636 float  opt_get_index()
00637 {
00638     return last_index;
00639 }
00640 
00641 
00642 unsigned opt_get_bounds()
00643 {
00644     return last_bounds;
00645 }
00646 
00647 
00648 void init_object()
00649 {
00650     int i;
00651 
00652     last_pal.red   = 0.0;
00653     last_pal.green = 0.0;
00654     last_pal.blue  = 0.0;
00655 
00656     strcpy (last_texture, "");
00657 
00658     bound_cost = 1.6;
00659 
00660     /* Allocate memory for palette lookup table */
00661     pmax   = 10;
00662     psize  = 0;
00663     ptable = malloc (pmax * sizeof(Palette));
00664     if (ptable == NULL)
00665        abortmsg ("Insufficient memory for palette.", 1);
00666 
00667     /* Allocate memory for texture table */
00668     tmax   = 10;
00669     tsize  = 0;
00670     ttable = malloc (tmax * sizeof(Texture));
00671     if (ttable == NULL)
00672        abortmsg ("Insufficient memory for textures.", 1);
00673 
00674     /* Allocate memory for vertex lookup table */
00675     vmax = (vert_init > 0) ? vert_init : 1000;
00676     vsize  = 0;
00677     vtable = malloc (vmax * sizeof(Vector));
00678     if (vtable == NULL)
00679        abortmsg ("Insufficient memory for vertices.", 1);
00680 
00681     /* Allocate memory for vertex hash table */
00682     vert_hash = malloc (sizeof(VertList*)*HASHSIZE);
00683     if (vert_hash == NULL)
00684        abortmsg ("Insufficient memory for vertex hash table.", 1);
00685 
00686     /* Initialize the vertex lookup hash table */
00687     for (i = 0; i < HASHSIZE; i++)
00688        vert_hash[i] = NULL;
00689 
00690     /* Start with an empty root node */
00691     groot = create_group();
00692 
00693     tot_bounds = 1;
00694     initialized = 1;
00695 }
00696 
00697 
00698 void cleanup_object()
00699 {
00700     int i;
00701     Vector corners[8];  /* Corners of box */
00702 
00703     last_vert_cnt = vsize;
00704     last_tri_cnt  = groot->obj_cnt;
00705     last_index    = orig_tpr/final_tpr;
00706     last_bounds   = tot_bounds;
00707 
00708     vect_copy (last_vmin, groot->vmin);
00709     vect_copy (last_vmax, groot->vmax);
00710 
00711     /* Calculate the corners of the bounding box */
00712     corners[0][X] =  groot->vmin[X];
00713     corners[0][Y] =  groot->vmin[Y];
00714     corners[0][Z] =  groot->vmin[Z];
00715 
00716     corners[1][X] =  groot->vmin[X];
00717     corners[1][Y] =  groot->vmin[Y];
00718     corners[1][Z] =  groot->vmax[Z];
00719 
00720     corners[2][X] =  groot->vmax[X];
00721     corners[2][Y] =  groot->vmin[Y];
00722     corners[2][Z] =  groot->vmin[Z];
00723 
00724     corners[3][X] =  groot->vmax[X];
00725     corners[3][Y] =  groot->vmin[Y];
00726     corners[3][Z] =  groot->vmax[Z];
00727 
00728     corners[4][X] =  groot->vmin[X];
00729     corners[4][Y] =  groot->vmax[Y];
00730     corners[4][Z] =  groot->vmin[Z];
00731 
00732     corners[5][X] =  groot->vmax[X];
00733     corners[5][Y] =  groot->vmax[Y];
00734     corners[5][Z] =  groot->vmin[Z];
00735 
00736     corners[6][X] =  groot->vmin[X];
00737     corners[6][Y] =  groot->vmax[Y];
00738     corners[6][Z] =  groot->vmax[Z];
00739 
00740     corners[7][X] =  groot->vmax[X];
00741     corners[7][Y] =  groot->vmax[Y];
00742     corners[7][Z] =  groot->vmax[Z];
00743 
00744     /* Include any transformation in the box calcs */
00745     if (use_transform) {
00746        for (i = 0; i < 8; i++)
00747            vect_transform (corners[i], corners[i], trans_matrix);
00748     }
00749 
00750     for (i = 0; i < 8; i++) {
00751        gmin[X] = (corners[i][X] < gmin[X]) ? corners[i][X] : gmin[X];
00752        gmin[Y] = (corners[i][Y] < gmin[Y]) ? corners[i][Y] : gmin[Y];
00753        gmin[Z] = (corners[i][Z] < gmin[Z]) ? corners[i][Z] : gmin[Z];
00754 
00755        gmax[X] = (corners[i][X] > gmax[X]) ? corners[i][X] : gmax[X];
00756        gmax[Y] = (corners[i][Y] > gmax[Y]) ? corners[i][Y] : gmax[Y];
00757        gmax[Z] = (corners[i][Z] > gmax[Z]) ? corners[i][Z] : gmax[Z];
00758     }
00759 
00760     free (ptable);
00761     free (vtable);
00762     free (vert_hash);
00763 
00764     for (i = 0; i < tsize; i++)
00765        free (ttable[i]);
00766 
00767     free (ttable);
00768 
00769     delete_tree (groot);
00770 
00771     initialized = 0;
00772 }
00773 
00774 
00775 /* Calculate the number of Tests Per Ray (tpr) required for this group */
00776 float  calc_tpr (GroupTree *gnode)
00777 {
00778     GroupTree *g;
00779     float     tpr;
00780 
00781     if (gnode->child_cnt == 0)
00782        return gnode->obj_cnt;
00783 
00784     tpr = bound_cost * gnode->child_cnt;
00785 
00786     for (g = gnode->child; g != NULL; g = g->next)
00787        tpr = tpr + (g->area/gnode->area) * calc_tpr(g);
00788 
00789     return tpr;
00790 }
00791 
00792 
00793 /* Create an empty group node */
00794 GroupTree *create_group()
00795 {
00796     GroupTree *new_group;
00797     int       i;
00798 
00799     new_group = malloc (sizeof(GroupTree));
00800     if (new_group == NULL)
00801        abortmsg ("Insufficient memory for group list.", 1);
00802 
00803     for (i = 0; i < 3; i++) {
00804        new_group->index[i] = malloc (sizeof(TriList2));
00805        if (new_group->index[i] == NULL)
00806            abortmsg ("Insufficient memory for tree.", 1);
00807 
00808        new_group->index[i]->tri = NULL;
00809        new_group->index[i]->prev = new_group->index[i];
00810        new_group->index[i]->next = new_group->index[i];
00811     }
00812 
00813     vect_init (new_group->vmin, +MAXFLOAT, +MAXFLOAT, +MAXFLOAT);
00814     vect_init (new_group->vmax, -MAXFLOAT, -MAXFLOAT, -MAXFLOAT);
00815     new_group->area      = 0.0;
00816     new_group->obj_cnt   = 0;
00817     new_group->child_cnt = 0;
00818     new_group->split_cnt = 0;
00819     new_group->parent    = NULL;
00820     new_group->next      = NULL;
00821     new_group->child     = NULL;
00822 
00823     return new_group;
00824 }
00825 
00826 
00827 /* Delete this node and all sub-nodes of tree */
00828 void delete_tree (GroupTree *gnode)
00829 {
00830     GroupTree *g, *g_temp;
00831     TriList2  *t, *t_temp;
00832     int       i;
00833 
00834     for (g = gnode->child; g != NULL; ) {
00835        g_temp = g->next;
00836        delete_tree (g);
00837        g = g_temp;
00838     }
00839 
00840     /* Free the indexes for this node (if any exist) */
00841     for (i = 0; i < 3; i++) {
00842        if ((gnode->index[i] != NULL) && (gnode->index[i]->prev != NULL)) {
00843            /* Drop a link so the list isn't circular any more */
00844            gnode->index[i]->prev->next = NULL;
00845 
00846            /* Delete the list */
00847            for (t = gnode->index[i]; t != NULL; ) {
00848               if (i == 0 && (t->tri != NULL))
00849                   free (t->tri);
00850 
00851               t_temp = t;
00852               t = t->next;
00853               free (t_temp);
00854            }
00855        }
00856     }
00857 
00858     /* And finally free the root node */
00859     free (gnode);
00860 }
00861 
00862 
00863 /* Optimize the bounds for this sub-tree */
00864 void optimize_tree (GroupTree *gnode)
00865 {
00866     GroupTree *group_a, *group_b;
00867     int axis, best_axis;
00868     float     best_rtpr, new_rtpr;
00869     TriList2  *best_loc, *new_loc;
00870 
00871     best_rtpr = 0.0;
00872     best_loc  = NULL;
00873     best_axis = -1;
00874 
00875     /* Try splitting the group in each of the three axis' (x,y,z) */
00876     for (axis = 0; axis < 3; axis++) {
00877        test_split (gnode, axis, &new_rtpr, &new_loc);
00878 
00879        if (new_rtpr < best_rtpr) {
00880            best_rtpr = new_rtpr;
00881            best_loc  = new_loc;
00882            best_axis = axis;
00883        }
00884     }
00885 
00886     if (best_axis != -1) {
00887        /* Split this node into two nodes */
00888        split_group (gnode, best_axis, best_loc, &group_a, &group_b);
00889 
00890        optimize_tree (group_a);
00891        optimize_tree (group_b);
00892     }
00893 }
00894 
00895 
00896 
00897 /* Test the effectiveness of splitting this group (but don't do it yet) */
00898 void test_split (GroupTree *gnode, int axis, float  *best_rtpr,
00899                TriList2 **best_loc)
00900 {
00901     float    dim1, dim2;
00902     float    area1, area2, p_area;
00903     float    new_min1, new_max1, new_min2, new_max2;
00904     float    best_index, new_index;
00905     TriList2 *t;
00906     int      cnt, best_cnt;
00907 
00908     *best_loc  = NULL;
00909     best_index = +MAXFLOAT ;
00910     best_cnt   = 0;
00911     cnt = 0;
00912 
00913     dim1 = gnode->vmax[(axis+1) % 3] - gnode->vmin[(axis+1) % 3];
00914     dim2 = gnode->vmax[(axis+2) % 3] - gnode->vmin[(axis+2) % 3];
00915 
00916     for (t = gnode->index[axis]->next; t != gnode->index[axis]; t = t->next) {
00917        if (t->next == gnode->index[axis])
00918            break;
00919 
00920        ++cnt;
00921 
00922        /* Make an estimate of the new min/max limits, doing the full */
00923        /* calculation is just tooooo slooowww. */
00924        new_min1 = gnode->vmin[axis];
00925        new_max1 = max_vertex (t->tri, axis);
00926        new_min2 = min_vertex (t->next->tri, axis);
00927        new_max2 = gnode->vmax[axis];
00928 
00929        /* Calculate the surface area of the new groups */
00930        area1 = surf_area (dim1, dim2, new_max1 - new_min1);
00931        area2 = surf_area (dim1, dim2, new_max2 - new_min2);
00932 
00933        new_index = (cnt * area1) + ((gnode->obj_cnt - cnt) * area2);
00934 
00935        /* Keep track of the best one */
00936        if (new_index < best_index) {
00937            best_index = new_index;
00938            *best_loc  = t->next;
00939            best_cnt   = cnt;
00940        }
00941     }
00942 
00943     /* The former was just an estimate, verify the numbers */
00944     if (*best_loc != NULL) {
00945        new_min1 = gnode->vmin[axis];
00946        new_max1 = -MAXFLOAT;
00947        new_min2 = +MAXFLOAT;
00948        new_max2 = gnode->vmax[axis];
00949 
00950        for (t = gnode->index[axis]->next; t != *best_loc; t = t->next)
00951            new_max1 = fltmax (new_max1, max_vertex (t->tri, axis));
00952 
00953        for (t = *best_loc; t != gnode->index[axis]; t = t->next)
00954            new_min2 = fltmin (new_min2, min_vertex (t->tri, axis));
00955 
00956        area1 = surf_area (dim1, dim2, new_max1 - new_min1);
00957        area2 = surf_area (dim1, dim2, new_max2 - new_min2);
00958 
00959        best_index = (best_cnt * area1) +
00960                    ((gnode->obj_cnt - best_cnt) * area2);
00961     }
00962 
00963     if (gnode->parent == NULL || gnode->split_cnt >= 2) {
00964        p_area = gnode->area;
00965 
00966        *best_rtpr = -1.0*((gnode->area/p_area) * gnode->obj_cnt) +
00967                    (gnode->area/p_area) * ((best_index/p_area) +
00968                    2.0*bound_cost);
00969     }
00970     else {
00971        p_area = gnode->parent->area;
00972 
00973        *best_rtpr = -1.0*((gnode->area/p_area) * gnode->obj_cnt) +
00974                    (best_index/p_area) + bound_cost;
00975     }
00976 }
00977 
00978 
00979 /* Split the group along the specified axis into two sub-groups */
00980 void split_group (GroupTree *gnode, int axis, TriList2 *split_loc,
00981                 GroupTree **group_a, GroupTree **group_b)
00982 {
00983     GroupTree *new_a, *new_b;
00984     TriList2  *t, *next_t, *new_index;
00985     char      new_flag;
00986     int       i;
00987 
00988     COOPERATE /* support multitasking */
00989 
00990     /* Mark the triangles as to which group they will belong */
00991     new_flag = 0;
00992     for (t = gnode->index[axis]->next; t != gnode->index[axis]; t = t->next) {
00993        if (t == split_loc)
00994            new_flag = 1;
00995 
00996        t->tri->flag = new_flag;
00997     }
00998 
00999     new_a = create_group();
01000     new_b = create_group();
01001 
01002     for (i = 0; i < 3; i++) {
01003        t = gnode->index[i]->next;
01004 
01005        while (t != gnode->index[i]) {
01006            next_t = t->next;
01007 
01008            if (t->tri->flag == 0)
01009               new_index = new_a->index[i];
01010            else
01011               new_index = new_b->index[i];
01012 
01013            /* Remove this node from the list */
01014            t->prev->next = t->next;
01015            t->next->prev = t->prev;
01016 
01017            /* Insert node into its new group */
01018            t->prev = new_index->prev;
01019            t->next = new_index;
01020            new_index->prev->next = t;
01021            new_index->prev = t;
01022 
01023            t = next_t;
01024        }
01025     }
01026 
01027     for (i = 0; i < 3; i++) {
01028        free (gnode->index[i]);
01029        gnode->index[i] = NULL;
01030     }
01031 
01032     if (gnode->parent == NULL || gnode->split_cnt >= 2) {
01033        /* Add the new groups as children of original */
01034        gnode->child  = new_a;
01035        new_a->parent = gnode;
01036        new_a->next   = new_b;
01037        new_b->parent = gnode;
01038 
01039        new_a->split_cnt = 0;
01040        new_b->split_cnt = 0;
01041 
01042        tot_bounds = tot_bounds + 2;
01043     }
01044     else {
01045        /* Remove the original group and replace with the new groups */
01046        for (i = 0; i < 3; i++)
01047            gnode->index[i] = new_a->index[i];
01048 
01049        free (new_a);
01050        new_a = gnode;
01051 
01052        new_b->next = new_a->next;
01053        new_a->next = new_b;
01054 
01055        new_a->parent = gnode->parent;
01056        new_b->parent = gnode->parent;
01057 
01058        new_a->split_cnt = gnode->split_cnt + 1;
01059        new_b->split_cnt = gnode->split_cnt + 1;
01060 
01061        tot_bounds = tot_bounds + 1;
01062     }
01063 
01064     update_node (new_a);
01065     update_node (new_b);
01066 
01067     if (new_a->parent != NULL)
01068        update_node (new_a->parent);
01069 
01070     if (!quiet_mode) {
01071        printf ("Adding bounds (%d)\r", tot_bounds);
01072        fflush(stdout);
01073     }
01074 
01075     *group_a = new_a;
01076     *group_b = new_b;
01077 }
01078 
01079 
01080 /* Write the optimized POV file */
01081 void write_file()
01082 {
01083     FILE  *f;
01084 
01085     if (!quiet_mode)
01086        printf ("\nWriting files %s and %s\n", out_file, inc_file);
01087 
01088     f = fopen (out_file, "a");
01089     if (f == NULL)
01090        abortmsg ("Error opening output file.", 1);
01091 
01092     switch (out_format) {
01093        case POV10:   write_pov10_header (f);
01094                     break;
01095        case POV20:   write_pov20_header (f);
01096                     break;
01097        case VIVID:   write_vivid_header (f);
01098                     break;
01099        case POLYRAY: write_polyray_header (f);
01100                     break;
01101        case MGF:     write_mgf_header (f);
01102                     break;
01103     }
01104 
01105     fclose (f);
01106 
01107     f = fopen (inc_file, "a");
01108     if (f == NULL)
01109        abortmsg ("Error opening output file.", 1);
01110 
01111     switch (out_format) {
01112        case POV10:   write_pov10_tree (f, groot, 1);
01113                     break;
01114        case POV20:   write_pov20_tree (f, groot, 1);
01115                     break;
01116        case VIVID:   write_vivid_tree (f, groot);
01117                     break;
01118        case POLYRAY: write_polyray_tree (f, groot);
01119                     break;
01120        case MGF:     write_mgf_tree (f, groot, 1);
01121                     break;
01122     }
01123 
01124     fclose (f);
01125 
01126     if (!quiet_mode) {
01127        printf ("Triangles: %u, ", groot->obj_cnt);
01128        printf ("Vertices: %u, ", vsize);
01129        printf ("Bounding index: %.2f\n\n", orig_tpr/final_tpr);
01130     }
01131 }
01132 
01133 
01134 void write_box (Vector v1, Vector v2, Triangle *tri)
01135 {
01136     FILE  *f;
01137 
01138     if (!quiet_mode)
01139        printf ("\nWriting files %s and %s\n", out_file, inc_file);
01140 
01141     f = fopen (inc_file, "a");
01142     if (f == NULL)
01143        abortmsg ("Error opening output file.", 1);
01144 
01145     switch (out_format) {
01146        case POV10:
01147            fprintf (f, "\n/* Object '%s' */\n", object_name);
01148            fprintf (f, "object {\n");
01149            fprintf (f, "\tbox { <%.4f %.4f %.4f> <%.4f %.4f %.4f> }\n",
01150                      v1[X], v1[Y], v1[Z], v2[X], v2[Y], v2[Z]);
01151            fprintf (f, "\t");
01152            write_pov10_texture (f, tri);
01153            fprintf (f, "\n");
01154 
01155            if (use_transform)
01156               write_pov10_transform (f, trans_matrix);
01157 
01158            fprintf (f, "}\n\n");
01159            break;
01160 
01161        case POV20:
01162            fprintf (f, "\n/* Object '%s' */\n", object_name);
01163            fprintf (f, "box {\n");
01164            fprintf (f, "\t<%.4f, %.4f, %.4f>, <%.4f, %.4f, %.4f>\n",
01165                      v1[X], v1[Y], v1[Z], v2[X], v2[Y], v2[Z]);
01166            fprintf (f, "\t");
01167            write_pov20_texture (f, tri);
01168            fprintf (f, "\n");
01169 
01170            if (use_transform)
01171               write_pov20_transform (f, trans_matrix);
01172 
01173            fprintf (f, "}\n\n");
01174            break;
01175 
01176        case VIVID:
01177            fprintf (f, "\n/* Object '%s' */\n", object_name);
01178 
01179            if (use_transform)
01180               write_vivid_transform (f, trans_matrix);
01181 
01182            write_vivid_texture (f, tri);
01183 
01184            fprintf (f, "polygon { points 4 vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f }\n",
01185                       v1[X], v1[Y], v1[Z], v2[X], v1[Y], v1[Z], v2[X], v2[Y], v1[Z], v1[X], v2[Y], v1[Z]);
01186            fprintf (f, "polygon { points 4 vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f }\n",
01187                       v1[X], v1[Y], v1[Z], v1[X], v2[Y], v1[Z], v1[X], v2[Y], v2[Z], v1[X], v1[Y], v2[Z]);
01188            fprintf (f, "polygon { points 4 vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f }\n",
01189                       v1[X], v2[Y], v1[Z], v2[X], v2[Y], v1[Z], v2[X], v2[Y], v2[Z], v1[X], v2[Y], v2[Z]);
01190            fprintf (f, "polygon { points 4 vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f }\n",
01191                       v2[X], v2[Y], v1[Z], v2[X], v1[Y], v1[Z], v2[X], v1[Y], v2[Z], v2[X], v2[Y], v2[Z]);
01192            fprintf (f, "polygon { points 4 vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f }\n",
01193                       v2[X], v1[Y], v1[Z], v1[X], v1[Y], v1[Z], v1[X], v1[Y], v2[Z], v2[X], v1[Y], v2[Z]);
01194            fprintf (f, "polygon { points 4 vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f vertex %.4f %.4f %.4f }\n",
01195                       v1[X], v1[Y], v2[Z], v1[X], v2[Y], v2[Z], v2[X], v2[Y], v2[Z], v2[X], v1[Y], v2[Z]);
01196 
01197            if (use_transform)
01198               fprintf (f, "transform_pop\n\n");
01199            break;
01200 
01201        case POLYRAY:
01202            fprintf (f, "\n// Object '%s'\n", object_name);
01203            fprintf (f, "object {\n");
01204            fprintf (f, "\tbox <%.4f, %.4f, %.4f>, <%.4f, %.4f, %.4f>\n",
01205                      v1[X], v1[Y], v1[Z], v2[X], v2[Y], v2[Z]);
01206            fprintf (f, "\t");
01207            write_polyray_texture (f, tri);
01208            fprintf (f, "\n");
01209 
01210            if (use_transform)
01211               write_polyray_transform (f, trans_matrix);
01212 
01213            fprintf (f, "}\n\n");
01214            break;
01215 
01216        case MGF:
01217            if (object_name[0]) fprintf (f, "o %s\n", object_name);
01218            write_mgf_texture (f, tri);
01219            fprintf (f, "v v1 =\n\tp %.4f %.4f %.4f\n", v1[X], v1[Y], v1[Z]);
01220            fprintf (f, "v v2 =\n\tp %.4f %.4f %.4f\n", v1[X], v2[Y], v1[Z]);
01221            fprintf (f, "v v3 =\n\tp %.4f %.4f %.4f\n", v2[X], v2[Y], v1[Z]);
01222            fprintf (f, "v v4 =\n\tp %.4f %.4f %.4f\n", v2[X], v1[Y], v1[Z]);
01223            fprintf (f, "prism v1 v2 v3 v4 %.4f\n", v2[Z]-v1[Z]);
01224            if (object_name[0]) fprintf (f, "o\n");
01225            fprintf (f, "\n");
01226     }
01227 
01228     fclose (f);
01229 }
01230 
01231 
01232 /* Write a sub-tree to file */
01233 void write_pov10_tree (FILE *f, GroupTree *gnode, int level)
01234 {
01235     GroupTree *g;
01236     TriList2  *t;
01237     Triangle  *first_tri;
01238     int       one_texture;
01239 
01240     if (level == 1)
01241        fprintf (f, "\n/* Object '%s' */\n", object_name);
01242 
01243     fprintf (f, "composite {\n");
01244 
01245     if (gnode->child != NULL) {
01246        for (g = gnode->child; g != NULL; g = g->next)
01247            write_pov10_tree (f, g, level+1);
01248     }
01249     else {
01250        first_tri = gnode->index[0]->next->tri;
01251        one_texture = 1;
01252 
01253        for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
01254            if (t->tri->text_index != first_tri->text_index ||
01255               t->tri->text_type  != first_tri->text_type) {
01256                  one_texture = 0;
01257                  break;
01258            }
01259        }
01260 
01261        if (one_texture) {
01262            fprintf (f, "\tobject {\n");
01263            fprintf (f, "\t\tunion {\n");
01264        }
01265 
01266        for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next)
01267            write_pov10_triangle (f, t->tri, one_texture);
01268 
01269        if (one_texture) {
01270            fprintf (f, "\t\t}\n\n\t\t");
01271            write_pov10_texture (f, first_tri);
01272            fprintf (f, "\n\t}\n");
01273        }
01274     }
01275 
01276     if (bound_mode == 0)
01277         write_pov10_bound (f, gnode);
01278 
01279     if (level == 1 && use_transform)
01280        write_pov10_transform (f, trans_matrix);
01281 
01282     fprintf (f, "}\n");
01283 }
01284 
01285 
01286 void write_pov10_texture (FILE *f, Triangle *tri)
01287 {
01288     if (tri->text_type == 1)
01289        fprintf (f, "texture { %s }", ttable[tri->text_index]);
01290     else if (psize < MAX_TEX)
01291        fprintf (f, "texture { %s_%u }",
01292                object_name, tri->text_index + 1);
01293     else
01294        fprintf (f, "texture { %s color red %.3f green %.3f blue %.3f }",
01295                object_name, ptable[tri->text_index].red,
01296                ptable[tri->text_index].green, ptable[tri->text_index].blue);
01297 }
01298 
01299 
01300 /*
01301    Writes a transformation matrix as separate POV-Ray scale< >,
01302    rotate< >, and translate< > commands
01303 */
01304 void write_pov10_transform (FILE *f, Matrix matrix)
01305 {
01306     Vector scale, shear, rotate, transl;
01307 
01308     /* Decode the matrix into separate operations */
01309     mat_decode (matrix, scale, shear, rotate, transl);
01310 
01311     fprintf (f, "\n\t/* Object transformation */\n");
01312 
01313     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
01314        fprintf (f, "\tscale <%.3f %.3f %.3f>\n", scale[X], scale[Y], scale[Z]);
01315 
01316     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
01317        fprintf (f, "\trotate <%.2f %.2f %.2f>\n", rotate[X], rotate[Y], rotate[Z]);
01318 
01319     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
01320        fprintf (f, "\ttranslate <%.4f %.4f %.4f>\n", transl[X], transl[Y], transl[Z]);
01321 
01322     /* Can't handle shear but warn if it's there */
01323     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
01324        printf ("Warning: Significant shear in transformation (ignored)\n");
01325 }
01326 
01327 
01328 /* Write the POV file header */
01329 void write_pov10_header (FILE *f)
01330 {
01331     int i;
01332 
01333     if (psize >= MAX_TEX) {
01334        fprintf (f, "/* Too many textures, textures generated in-line */\n\n");
01335        fprintf (f, "#declare %s = texture {\n", object_name);
01336        fprintf (f, "    ambient 0.1\n");
01337        fprintf (f, "    diffuse 0.7\n");
01338        fprintf (f, "    phong 1.0\n");
01339        fprintf (f, "    phong_size 70.0\n");
01340        fprintf (f, "}\n\n");
01341     }
01342     else {
01343        if (psize > 0)
01344            fprintf (f, "/* Texture declarations for object '%s' */\n", object_name);
01345 
01346        for (i = 0; i < psize; i++) {
01347            fprintf (f, "#declare %s_%u = texture {\n", object_name, i + 1);
01348            fprintf (f, "    ambient 0.1\n");
01349            fprintf (f, "    diffuse 0.7\n");
01350            fprintf (f, "    phong 1.0\n");
01351            fprintf (f, "    phong_size 70.0\n");
01352            fprintf (f, "    color red %.3f green %.3f blue %.3f\n",
01353                    ptable[i].red, ptable[i].green, ptable[i].blue);
01354            fprintf (f, "}\n\n");
01355        }
01356     }
01357 }
01358 
01359 
01360 /* Write a triangle (smooth or regular) */
01361 void write_pov10_triangle (FILE *f, Triangle *tri, int one_texture)
01362 {
01363     Vector norm[3];
01364     int    no_smooth = 0;
01365 
01366     COOPERATE /* support multitasking */
01367 
01368     if (one_texture)
01369        fprintf (f, "\t\t");
01370     else
01371        fprintf (f, "\tobject { ");
01372 
01373     if (smooth_angle > 0.0) {
01374        vert_normal (tri, norm);
01375 
01376        if (vect_equal (norm[0], norm[1]) && vect_equal (norm[1], norm[2]))
01377            no_smooth = 1;
01378     }
01379 
01380     if (smooth_angle > 0.0 && !no_smooth) {
01381        fprintf (f, "smooth_triangle { <");
01382        vect_print (f, vtable[tri->vert[0]], dec_point, ' ');
01383        fprintf (f, "> <");
01384        vect_print (f, norm[0], 3, ' ');
01385        fprintf (f, "> <");
01386        vect_print (f, vtable[tri->vert[1]], dec_point, ' ');
01387        fprintf (f, "> <");
01388        vect_print (f, norm[1], 3, ' ');
01389        fprintf (f, "> <");
01390        vect_print (f, vtable[tri->vert[2]], dec_point, ' ');
01391        fprintf (f, "> <");
01392        vect_print (f, norm[2], 3, ' ');
01393        fprintf (f, "> }");
01394     }
01395     else {
01396        fprintf (f, "triangle { <");
01397        vect_print (f, vtable[tri->vert[0]], dec_point, ' ');
01398        fprintf (f, "> <");
01399        vect_print (f, vtable[tri->vert[1]], dec_point, ' ');
01400        fprintf (f, "> <");
01401        vect_print (f, vtable[tri->vert[2]], dec_point, ' ');
01402        fprintf (f, "> }");
01403     }
01404 
01405     if (!one_texture) {
01406        fprintf (f, " ");
01407        write_pov10_texture (f, tri);
01408        fprintf (f, " }");
01409     }
01410 
01411     fprintf (f, "\n");
01412 }
01413 
01414 
01415 /* Write a bounding shape */
01416 void write_pov10_bound (FILE *f, GroupTree *gnode)
01417 {
01418     if (gnode->obj_cnt > 1) {
01419        fprintf (f, "\n\tbounded_by { box { <");
01420        vect_print (f, gnode->vmin, dec_point + 1, ' ');
01421        fprintf (f, "> <");
01422        vect_print (f, gnode->vmax, dec_point + 1, ' ');
01423        fprintf (f, "> } }\n");
01424     }
01425 }
01426 
01427 
01428 /* Write a sub-tree to file */
01429 void write_pov20_tree (FILE *f, GroupTree *gnode, int level)
01430 {
01431     GroupTree *g;
01432     TriList2  *t;
01433     Triangle  *first_tri;
01434     int       one_texture;
01435 
01436     if (level == 1)
01437        fprintf (f, "\n/* Object '%s' */\n", object_name);
01438 
01439     if (gnode->obj_cnt > 1)
01440         fprintf (f, "union {\n");
01441     else
01442         fprintf (f, "object {\n");
01443 
01444     if (gnode->child != NULL) {
01445        for (g = gnode->child; g != NULL; g = g->next)
01446            write_pov20_tree (f, g, level+1);
01447     }
01448     else {
01449        first_tri = gnode->index[0]->next->tri;
01450        one_texture = 1;
01451 
01452        for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
01453            if (t->tri->text_index != first_tri->text_index ||
01454               t->tri->text_type  != first_tri->text_type) {
01455                  one_texture = 0;
01456                  break;
01457            }
01458        }
01459 
01460        for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
01461             fprintf (f, "\t");
01462            write_pov20_triangle (f, t->tri, one_texture);
01463         }
01464 
01465        if (one_texture) {
01466            fprintf (f, "\n\t");
01467            write_pov20_texture (f, first_tri);
01468        }
01469     }
01470 
01471     fprintf (f, "\n");
01472 
01473     if (bound_mode == 0)
01474        write_pov20_bound (f, gnode);
01475 
01476     if (level == 1 && use_transform)
01477        write_pov20_transform (f, trans_matrix);
01478 
01479     fprintf (f, "}\n");
01480 }
01481 
01482 
01483 void write_pov20_texture (FILE *f, Triangle *tri)
01484 {
01485     if (tri->text_type == 1)
01486        fprintf (f, "texture { %s }", ttable[tri->text_index]);
01487     else if (psize < MAX_TEX)
01488        fprintf (f, "texture { %s_%u }",
01489                object_name, tri->text_index + 1);
01490     else
01491        fprintf (f, "texture { %s pigment { color red %.3f green %.3f blue %.3f } }",
01492                object_name, ptable[tri->text_index].red,
01493                ptable[tri->text_index].green, ptable[tri->text_index].blue);
01494 }
01495 
01496 
01497 /*
01498    Writes a transformation matrix as separate POV-Ray scale< >,
01499    rotate< >, and translate< > commands
01500 */
01501 void write_pov20_transform (FILE *f, Matrix matrix)
01502 {
01503     Vector scale, shear, rotate, transl;
01504 
01505     /* Decode the matrix into separate operations */
01506     mat_decode (matrix, scale, shear, rotate, transl);
01507 
01508     fprintf (f, "\n\t/* Object transformation */\n");
01509 
01510     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
01511        fprintf (f, "\tscale <%.3f, %.3f, %.3f>\n", scale[X], scale[Y], scale[Z]);
01512 
01513     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
01514        fprintf (f, "\trotate <%.2f, %.2f, %.2f>\n", rotate[X], rotate[Y], rotate[Z]);
01515 
01516     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
01517        fprintf (f, "\ttranslate <%.4f, %.4f, %.4f>\n", transl[X], transl[Y], transl[Z]);
01518 
01519     /* Can't handle shear but warn if it's there */
01520     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
01521        printf ("Warning: Significant shear in transformation (ignored)\n");
01522 }
01523 
01524 
01525 /* Write the POV file header */
01526 void write_pov20_header (FILE *f)
01527 {
01528     int i;
01529 
01530     if (psize >= MAX_TEX) {
01531        fprintf (f, "/* Too many textures, textures generated in-line */\n\n");
01532        fprintf (f, "#declare %s = texture {\n", object_name);
01533        fprintf (f, "    finish { Shiny }\n");
01534        fprintf (f, "    pigment { White }\n");
01535        fprintf (f, "}\n\n");
01536     }
01537     else {
01538        if (psize > 0)
01539            fprintf (f, "/* Texture declarations for object '%s' */\n", object_name);
01540 
01541        for (i = 0; i < psize; i++) {
01542            fprintf (f, "#declare %s_%u = texture {\n", object_name, i + 1);
01543            fprintf (f, "    finish { Shiny }\n");
01544            fprintf (f, "    pigment { color red %.3f green %.3f blue %.3f }\n",
01545                    ptable[i].red, ptable[i].green, ptable[i].blue);
01546            fprintf (f, "}\n\n");
01547        }
01548     }
01549 }
01550 
01551 
01552 /* Write a triangle (smooth or regular) */
01553 void write_pov20_triangle (FILE *f, Triangle *tri, int one_texture)
01554 {
01555     Vector norm[3];
01556     int    no_smooth = 0;
01557 
01558     COOPERATE /* support multitasking */
01559 
01560     if (smooth_angle > 0.0) {
01561        vert_normal (tri, norm);
01562 
01563        if (vect_equal (norm[0], norm[1]) && vect_equal (norm[1], norm[2]))
01564            no_smooth = 1;
01565     }
01566 
01567     if (smooth_angle > 0.0 && !no_smooth) {
01568        fprintf (f, "smooth_triangle { <");
01569        vect_print (f, vtable[tri->vert[0]], dec_point, ',');
01570        fprintf (f, ">, <");
01571        vect_print (f, norm[0], 3, ',');
01572        fprintf (f, ">, <");
01573        vect_print (f, vtable[tri->vert[1]], dec_point, ',');
01574        fprintf (f, ">, <");
01575        vect_print (f, norm[1], 3, ',');
01576        fprintf (f, ">, <");
01577        vect_print (f, vtable[tri->vert[2]], dec_point, ',');
01578        fprintf (f, ">, <");
01579        vect_print (f, norm[2], 3, ',');
01580        fprintf (f, "> ");
01581     }
01582     else {
01583        fprintf (f, "triangle { <");
01584        vect_print (f, vtable[tri->vert[0]], dec_point, ',');
01585        fprintf (f, ">, <");
01586        vect_print (f, vtable[tri->vert[1]], dec_point, ',');
01587        fprintf (f, ">, <");
01588        vect_print (f, vtable[tri->vert[2]], dec_point, ',');
01589        fprintf (f, "> ");
01590     }
01591 
01592     if (!one_texture)
01593        write_pov20_texture (f, tri);
01594 
01595     fprintf (f, "}\n");
01596 }
01597 
01598 
01599 /* Write a bounding shape */
01600 void write_pov20_bound (FILE *f, GroupTree *gnode)
01601 {
01602     if (gnode->obj_cnt > 1) {
01603        fprintf (f, "\tbounded_by { box { <");
01604        vect_print (f, gnode->vmin, dec_point + 1, ',');
01605        fprintf (f, ">, <");
01606        vect_print (f, gnode->vmax, dec_point + 1, ',');
01607        fprintf (f, "> } }\n");
01608     }
01609 }
01610 
01611 
01612 /* Write a sub-tree to file */
01613 void write_vivid_tree (FILE *f, GroupTree *gnode)
01614 {
01615     TriList2  *t;
01616     int       last_index, last_type;
01617 
01618     last_index = -1;
01619     last_type  = -1;
01620 
01621     fprintf (f, "\n/* Object '%s' */\n", object_name);
01622 
01623     if (use_transform)
01624        write_vivid_transform (f, trans_matrix);
01625 
01626     if (gnode->child != NULL)
01627        abortmsg ("Internal error", 1);
01628 
01629     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
01630        if (t->tri->text_index != last_index ||
01631            t->tri->text_type != last_type)
01632        {
01633            write_vivid_texture (f, t->tri);
01634            last_index = t->tri->text_index;
01635            last_type  = t->tri->text_type;
01636        }
01637 
01638        write_vivid_triangle (f, t->tri);
01639     }
01640 
01641     if (use_transform)
01642        fprintf (f, "transform_pop\n\n");
01643 }
01644 
01645 
01646 /*
01647    Writes a transformation matrix as separate Vivid scale,
01648    rotate, and translate commands
01649 */
01650 void write_vivid_transform (FILE *f, Matrix matrix)
01651 {
01652     Vector scale, shear, rotate, transl;
01653 
01654     /* Decode the matrix into separate operations */
01655     mat_decode (matrix, scale, shear, rotate, transl);
01656 
01657     fprintf (f, "\n/* Object transformation */\n");
01658 
01659     fprintf (f, "transform {\n");
01660 
01661     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
01662        fprintf (f, "\tscale %.3f %.3f %.3f\n", scale[X], scale[Y], scale[Z]);
01663 
01664     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
01665        fprintf (f, "\trotate %.2f %.2f %.2f\n", rotate[X], rotate[Y], rotate[Z]);
01666 
01667     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
01668        fprintf (f, "\ttranslate %.4f %.4f %.4f\n", transl[X], transl[Y], transl[Z]);
01669     else
01670        fprintf (f, "\ttranslate 0 0 0 // Null transformation\n");
01671 
01672     /* Can't handle shear but warn if it's there */
01673     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
01674        printf ("Warning: Significant shear in transformation (ignored)\n");
01675 
01676     fprintf (f, "}\n\n");
01677 }
01678 
01679 
01680 void write_vivid_texture (FILE *f, Triangle *tri)
01681 {
01682     if (tri->text_type == 1)
01683        fprintf (f, "\n%s /* New texture */\n\n", ttable[tri->text_index]);
01684     else
01685        fprintf (f, "\n%s_%u /* New texture */\n\n",
01686                object_name, tri->text_index + 1);
01687 }
01688 
01689 
01690 /* Write the Vivid file header */
01691 void write_vivid_header (FILE *f)
01692 {
01693     int i;
01694 
01695     if (psize > 0)
01696        fprintf (f, "/* Texture declarations for object '%s' */\n", object_name);
01697 
01698     for (i = 0; i < psize; i++) {
01699        fprintf (f, "#define %s_%u \\ \n", object_name, i + 1);
01700        fprintf (f, "    surface {           \\ \n");
01701        fprintf (f, "        diffuse %.3f %.3f %.3f \\ \n",
01702                   ptable[i].red, ptable[i].green, ptable[i].blue);
01703        fprintf (f, "        shine 70 white  \\ \n");
01704        fprintf (f, "    }\n\n");
01705     }
01706 }
01707 
01708 
01709 /* Write a Vivid triangle patch */
01710 void write_vivid_triangle (FILE *f, Triangle *tri)
01711 {
01712     Vector norm[3];
01713 
01714     COOPERATE /* support multitasking */
01715 
01716     vert_normal (tri, norm);
01717 
01718     fprintf (f, "patch {\n");
01719     fprintf (f, "\tvertex ");
01720     vect_print (f, vtable[tri->vert[0]], dec_point, ' ');
01721     fprintf (f, " normal ");
01722     vect_print (f, norm[0], 3, ' ');
01723     fprintf (f, "\n");
01724 
01725     fprintf (f, "\tvertex ");
01726     vect_print (f, vtable[tri->vert[1]], dec_point, ' ');
01727     fprintf (f, " normal ");
01728     vect_print (f, norm[1], 3, ' ');
01729     fprintf (f, "\n");
01730 
01731     fprintf (f, "\tvertex ");
01732     vect_print (f, vtable[tri->vert[2]], dec_point, ' ');
01733     fprintf (f, " normal ");
01734     vect_print (f, norm[2], 3, ' ');
01735     fprintf (f, "\n");
01736 
01737     fprintf (f, "}\n\n");
01738 }
01739 
01740 
01741 /* Write a sub-tree to file */
01742 void write_polyray_tree (FILE *f, GroupTree *gnode)
01743 {
01744     TriList2  *t;
01745 
01746     fprintf (f, "\n// Object '%s'\n\n", object_name);
01747 
01748     fprintf (f, "object {\n");
01749 
01750     if (gnode->child != NULL)
01751        abortmsg ("Internal error", 1);
01752 
01753     for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
01754        if (t != gnode->index[0]->next)
01755            fprintf (f, "\t+\n");
01756 
01757        write_polyray_triangle (f, t->tri);
01758 
01759        fprintf (f, "\t\t");
01760        write_polyray_texture (f, t->tri);
01761        fprintf (f, "\n\t}\n\n");
01762     }
01763 
01764     if (use_transform)
01765        write_polyray_transform (f, trans_matrix);
01766 
01767     fprintf (f, "}\n\n");
01768 }
01769 
01770 
01771 /*
01772    Writes a transformation matrix as separate Polyray scale< >,
01773    rotate< >, and translate< > commands
01774 */
01775 void write_polyray_transform (FILE *f, Matrix matrix)
01776 {
01777     Vector scale, shear, rotate, transl;
01778 
01779     /* Decode the matrix into separate operations */
01780     mat_decode (matrix, scale, shear, rotate, transl);
01781 
01782     fprintf (f, "\n\t// Object transformation\n");
01783 
01784     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 || fabs(scale[Z] - 1.0) > 0.001)
01785        fprintf (f, "\tscale <%.3f, %.3f, %.3f>\n", scale[X], scale[Y], scale[Z]);
01786 
01787     if (fabs(rotate[X]) > 0.01 || fabs(rotate[Y]) > 0.01 || fabs(rotate[Z]) > 0.01)
01788        fprintf (f, "\trotate <%.2f, %.2f, %.2f>\n", rotate[X], rotate[Y], rotate[Z]);
01789 
01790     if (fabs(transl[X]) > 0.0001 || fabs(transl[Y]) > 0.0001 || fabs(transl[Z]) > 0.0001)
01791        fprintf (f, "\ttranslate <%.4f, %.4f, %.4f>\n", transl[X], transl[Y], transl[Z]);
01792 
01793     /* Can't handle shear but warn if it's there */
01794     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
01795        printf ("Warning: Significant shear in transformation (ignored)\n");
01796 }
01797 
01798 
01799 void write_polyray_texture (FILE *f, Triangle *tri)
01800 {
01801     if (tri->text_type == 1)
01802        fprintf (f, "%s", ttable[tri->text_index]);
01803     else
01804        fprintf (f, "%s_%u",
01805                object_name, tri->text_index + 1);
01806 }
01807 
01808 
01809 /* Write the Polyray file header */
01810 void write_polyray_header (FILE *f)
01811 {
01812     int i;
01813 
01814     if (psize > 0)
01815        fprintf (f, "// Texture declarations for object '%s'\n", object_name);
01816 
01817     for (i = 0; i < psize; i++) {
01818        fprintf (f, "define %s_%u\n", object_name, i + 1);
01819        fprintf (f, "texture {\n");
01820        fprintf (f, "    surface {\n");
01821        fprintf (f, "        ambient <%.3f, %.3f, %.3f>, 0.1\n",
01822                   ptable[i].red, ptable[i].green, ptable[i].blue);
01823        fprintf (f, "        diffuse <%.3f, %.3f, %.3f>, 0.7\n",
01824                   ptable[i].red, ptable[i].green, ptable[i].blue);
01825        fprintf (f, "        specular white, 1.0\n");
01826        fprintf (f, "        microfacet Reitz 10\n");
01827        fprintf (f, "    }\n");
01828        fprintf (f, "}\n\n");
01829     }
01830 }
01831 
01832 
01833 /* Write a Polyray triangle patch */
01834 void write_polyray_triangle (FILE *f, Triangle *tri)
01835 {
01836     Vector norm[3];
01837 
01838     COOPERATE /* support multitasking */
01839 
01840     vert_normal (tri, norm);
01841 
01842     fprintf (f, "\tobject {\n");
01843 
01844     fprintf (f, "\t\tpatch\t <");
01845     vect_print (f, vtable[tri->vert[0]], dec_point, ',');
01846     fprintf (f, ">, <");
01847     vect_print (f, norm[0], 3, ',');
01848     fprintf (f, ">,\n");
01849 
01850     fprintf (f, "\t\t\t <");
01851     vect_print (f, vtable[tri->vert[1]], dec_point, ',');
01852     fprintf (f, ">, <");
01853     vect_print (f, norm[1], 3, ',');
01854     fprintf (f, ">,\n");
01855 
01856     fprintf (f, "\t\t\t <");
01857     vect_print (f, vtable[tri->vert[2]], dec_point, ',');
01858     fprintf (f, ">, <");
01859     vect_print (f, norm[2], 3, ',');
01860     fprintf (f, ">\n");
01861 }
01862 
01863 
01864 /* Write a sub-tree to file */
01865 void write_mgf_tree (FILE *f, GroupTree *gnode, int level)
01866 {
01867     GroupTree *g;
01868     TriList2  *t;
01869 
01870     if (level == 1) {
01871        fprintf (f, "\no %s\n", object_name);
01872        if (use_transform)
01873            write_mgf_transform (f, trans_matrix);
01874     }
01875 
01876     if (gnode->child != NULL) {
01877        for (g = gnode->child; g != NULL; g = g->next)
01878            write_mgf_tree (f, g, level+1);
01879     }
01880     else {
01881        for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next)
01882            write_mgf_triangle (f, t->tri);
01883     }
01884 
01885     fprintf (f, "\n");
01886 
01887     if (level == 1) {
01888        if (use_transform)
01889            fprintf (f, "xf\n");
01890        fprintf (f, "\no\n");
01891     }
01892     fprintf (f, "\n");
01893 }
01894 
01895 
01896 void write_mgf_texture (FILE *f, Triangle *tri)
01897 {
01898     if (tri->text_type == 1)
01899        fprintf (f, "m %s\n", ttable[tri->text_index]);
01900     else if (psize < MAX_TEX)
01901        fprintf (f, "m %s_%u\n", object_name, tri->text_index + 1);
01902     else
01903        fprintf (f, "m\n\tc\n\t\tcmix %.3f R %.3f G %.3f B\n\trd %.3f\n",
01904                CIE_Y_r*ptable[tri->text_index].red,
01905                CIE_Y_g*ptable[tri->text_index].green,
01906                CIE_Y_b*ptable[tri->text_index].blue,
01907                CIE_Y_r*ptable[tri->text_index].red +
01908                CIE_Y_g*ptable[tri->text_index].green +
01909                CIE_Y_b*ptable[tri->text_index].blue);
01910 }
01911 
01912 
01913 /*
01914    Writes a transformation matrix as MGF transform entity
01915 */
01916 void write_mgf_transform (FILE *f, Matrix matrix)
01917 {
01918     Vector scale, shear, rotate, transl;
01919     float ascale;
01920 
01921     /* Decode the matrix into separate operations */
01922     mat_decode (matrix, scale, shear, rotate, transl);
01923 
01924     fprintf (f, "xf");
01925                                           /* print scaling */
01926     if (fabs(scale[X] - 1.0) > 0.001 || fabs(scale[Y] - 1.0) > 0.001 ||
01927               fabs(scale[Z] - 1.0) > 0.001) {
01928        if (fabs(scale[X] - scale[Y]) > 0.001 ||
01929                      fabs(scale[Y] - scale[Z]) > 0.001)
01930            printf("Warning: Non-linear scaling in transformation (ignored)\n");
01931        ascale = sqrt((scale[X]*scale[X] + scale[Y]*scale[Y] +
01932                      scale[Z]*scale[Z])/3.0);
01933        fprintf (f, " -s %.3f\n", ascale);
01934     }
01935                                           /* add rotation */
01936     if (fabs(rotate[X]) > 0.01)
01937        fprintf (f, " -rx %.2f", rotate[X]);
01938     if (fabs(rotate[Y]) > 0.01)
01939        fprintf (f, " -ry %.2f", rotate[Y]);
01940     if (fabs(rotate[Z]) > 0.01)
01941        fprintf (f, " -rz %.2f", rotate[Z]);
01942                                           /* final translation */
01943     fprintf (f, " -t %.4f, %.4f, %.4f\n", transl[X], transl[Y], transl[Z]);
01944 
01945     /* Can't handle shear but warn if it's there */
01946     if (fabs(shear[X]) > 0.01 || fabs(shear[Y]) > 0.01 || fabs(shear[Z]) > 0.01)
01947        printf ("Warning: Significant shear in transformation (ignored)\n");
01948 }
01949 
01950 
01951 /* Write the MGF file header */
01952 void write_mgf_header (FILE *f)
01953 {
01954     int i;
01955 
01956     if (psize >= MAX_TEX) {
01957        fprintf (f, "# Too many materials, materials generated in-line\n\n");
01958     }
01959     else {
01960        if (psize > 0)
01961            fprintf (f, "# Material definitions for object '%s'\n", object_name);
01962 
01963        for (i = 0; i < psize; i++) {
01964            fprintf (f, "m %s_%u =\n", object_name, i + 1);
01965            fprintf (f, "\tc\n\t\tcmix %.3f R %.3f G %.3f B\n\trd %.3f\n",
01966                    CIE_Y_r*ptable[i].red,
01967                    CIE_Y_g*ptable[i].green,
01968                    CIE_Y_b*ptable[i].blue,
01969                    CIE_Y_r*ptable[i].red +
01970                    CIE_Y_g*ptable[i].green +
01971                    CIE_Y_b*ptable[i].blue);
01972        }
01973     }
01974 }
01975 
01976 
01977 /* Write a triangle (smooth or regular) */
01978 void write_mgf_triangle (FILE *f, Triangle *tri)
01979 {
01980     Vector norm[3];
01981     int    i;
01982     int    smooth;
01983 
01984     COOPERATE /* support multitasking */
01985 
01986     write_mgf_texture (f, tri);
01987 
01988     if (smooth_angle > 0.0) {
01989        vert_normal (tri, norm);
01990 
01991        smooth = !vect_equal (norm[0], norm[1]) ||
01992                !vect_equal (norm[1], norm[2]);
01993     } else
01994        smooth = 0;
01995 
01996     for (i = 0; i < 3; i++) {
01997        fprintf (f, "v v%d =\n\tp ", i+1);
01998        vect_print (f, vtable[tri->vert[i]], dec_point, ' ');
01999        if (smooth) {
02000            fprintf (f, "\n\tn ");
02001            vect_print (f, norm[i], 3, ' ');
02002        }
02003        fprintf (f, "\n");
02004     }
02005     fprintf (f, "f v1 v2 v3\n");
02006 }
02007 
02008 
02009 /* Update the stats (area, vmin/vmax, child_cnt, etc.) for this node */
02010 void update_node (GroupTree *gnode)
02011 {
02012     GroupTree *g;
02013     TriList2  *t;
02014     int       i;
02015 
02016     vect_init (gnode->vmin, +MAXFLOAT, +MAXFLOAT, +MAXFLOAT);
02017     vect_init (gnode->vmax, -MAXFLOAT, -MAXFLOAT, -MAXFLOAT);
02018 
02019     gnode->obj_cnt   = 0;
02020     gnode->child_cnt = 0;
02021 
02022     if (gnode->index[0] == NULL) {
02023        /* Not a leaf node, calc the info from the child nodes */
02024 
02025        for (g = gnode->child; g != NULL; g = g->next) {
02026            ++(gnode->child_cnt);
02027 
02028            gnode->obj_cnt += g->obj_cnt;
02029 
02030            for (i = 0; i < 3; i++) {
02031               gnode->vmin[i] = fltmin (gnode->vmin[i], g->vmin[i]);
02032               gnode->vmax[i] = fltmax (gnode->vmax[i], g->vmax[i]);
02033            }
02034        }
02035     }
02036     else {
02037        /* A leaf node, calc the info from the triangle list */
02038 
02039        for (t = gnode->index[0]->next; t != gnode->index[0]; t = t->next) {
02040            ++(gnode->obj_cnt);
02041 
02042            for (i = 0; i < 3; i++) {
02043               gnode->vmin[i] = fltmin (gnode->vmin[i], min_vertex (t->tri, i));
02044               gnode->vmax[i] = fltmax (gnode->vmax[i], max_vertex (t->tri, i));
02045            }
02046        }
02047     }
02048 
02049     /* Update total surface area of region */
02050     gnode->area = surf_area (gnode->vmax[X] - gnode->vmin[X],
02051                           gnode->vmax[Y] - gnode->vmin[Y],
02052                           gnode->vmax[Z] - gnode->vmin[Z]);
02053 }
02054 
02055 
02056 void sort_indexes (GroupTree *gnode)
02057 {
02058     int i;
02059 
02060     for (i = 0; i < 3; i++)
02061        quick_sort (gnode->index[i]->next, gnode->index[i]->prev, i);
02062 }
02063 
02064 
02065 void quick_sort (TriList2 *start, TriList2 *end, int axis)
02066 {
02067     TriList2 *a, *b;
02068     Triangle *temp;
02069     float  middle;
02070 
02071     if (start == end)
02072        return;
02073 
02074     a = start;
02075     b = end;
02076     middle = avg_vertex (a->tri, axis);
02077 
02078     do {
02079        while (avg_vertex (b->tri, axis) >= middle && a != b)
02080            b = b->prev;
02081 
02082        if (a != b) {
02083            temp   = a->tri;
02084            a->tri = b->tri;
02085            b->tri = temp;
02086 
02087            while (avg_vertex (a->tri, axis) <= middle && a != b)
02088               a = a->next;
02089 
02090            if (a != b) {
02091               temp   = a->tri;
02092               a->tri = b->tri;
02093               b->tri = temp;
02094            }
02095        }
02096     } while (a != b);
02097 
02098     if (a != start)
02099        quick_sort (start, a->prev, axis);
02100 
02101     if (b != end)
02102        quick_sort (b->next, end, axis);
02103 }
02104 
02105 
02106 /* Calculate the surface area of a box */
02107 float surf_area (float  a, float  b, float  c)
02108 {
02109     return 2.0*(a*b + b*c + c*a);
02110 }
02111 
02112 
02113 float max_vertex (Triangle *tri, int axis)
02114 {
02115     float  max_v, val;
02116     int i;
02117 
02118     max_v = -MAXFLOAT;
02119 
02120     for (i = 0; i < 3; i++) {
02121        val = vtable[tri->vert[i]][axis];
02122 
02123        if (val > max_v)
02124            max_v = val;
02125     }
02126 
02127     return max_v;
02128 }
02129 
02130 
02131 float min_vertex (Triangle *tri, int axis)
02132 {
02133     float  min_v, val;
02134     int i;
02135 
02136     min_v = +MAXFLOAT;
02137 
02138     for (i = 0; i < 3; i++) {
02139        val = vtable[tri->vert[i]][axis];
02140 
02141        if (val < min_v)
02142            min_v = val;
02143     }
02144 
02145     return min_v;
02146 }
02147 
02148 
02149 float avg_vertex (Triangle *tri, int axis)
02150 {
02151     float  avg;
02152 
02153     avg = (vtable[tri->vert[0]][axis] + vtable[tri->vert[1]][axis] +
02154           vtable[tri->vert[2]][axis])/3.0;
02155 
02156     return avg;
02157 }
02158 
02159 
02160 /* Build an index of which triangles touch each vertex.  Used to */
02161 /* speed up smooth triangle normal calculations. */
02162 void build_tri_index()
02163 {
02164     GroupTree *g;
02165     TriList   *temp;
02166     TriList2  *t;
02167     unsigned  i, vert_no;
02168 
02169     if (vsize == 0)
02170        return;
02171 
02172     tri_index = malloc (vsize * sizeof(TriList));
02173     if (tri_index == NULL)
02174        abortmsg ("Insufficient memory for smooth triangles.", 1);
02175 
02176     for (i = 0; i < vsize; i++)
02177        tri_index[i] = NULL;
02178 
02179     for (g = groot; g != NULL; g = g->next) {
02180        for (t = g->index[0]->next; t != g->index[0]; t = t->next) {
02181            for (i = 0; i < 3; i++) {
02182               vert_no = t->tri->vert[i];
02183               temp = tri_index[vert_no];
02184               tri_index[vert_no] = malloc (sizeof(TriList));
02185               if (tri_index[vert_no] == NULL)
02186                   abortmsg ("Insufficient memory for smooth triangles.\n", 1);
02187 
02188               tri_index[vert_no]->tri = t->tri;
02189               tri_index[vert_no]->next = temp;
02190            }
02191        }
02192     }
02193 
02194 }
02195 
02196 
02197 void dump_tri_index()
02198 {
02199     TriList *temp;
02200     int     i;
02201 
02202     for (i = 0; i < vsize; i++) {
02203        while (tri_index[i] != NULL) {
02204            temp = tri_index[i];
02205            tri_index[i] = tri_index[i]->next;
02206            free (temp);
02207        }
02208     }
02209 
02210     free (tri_index);
02211 }
02212 
02213 
02214 /* Calculates the smooth triangle normal for this vertex */
02215 void vert_normal (Triangle *t, Vector *norm)
02216 {
02217     Vector  curr_norm, new_norm;
02218     TriList *p;
02219     int     i;
02220 
02221     tri_normal (t, curr_norm);
02222 
02223     if (smooth_angle <= 0.0) {
02224        for (i = 0; i < 3; i++)
02225            vect_copy (norm[i], curr_norm);
02226 
02227        return;
02228     }
02229 
02230     for (i = 0; i < 3; i++) {
02231        vect_init (norm[i], 0.0, 0.0, 0.0);
02232 
02233        for (p = tri_index[t->vert[i]]; p != NULL; p = p->next) {
02234            tri_normal (p->tri, new_norm);
02235            if (vect_angle (curr_norm, new_norm) < smooth_angle)
02236               vect_add (norm[i], norm[i], new_norm);
02237        }
02238 
02239        vect_normalize (norm[i]);
02240     }
02241 }
02242 
02243 
02244 /* Calculates the normal to the specified triangle */
02245 void tri_normal (Triangle *t, Vector normal)
02246 {
02247     Vector ab, ac;
02248 
02249     vect_sub (ab, vtable[t->vert[1]], vtable[t->vert[0]]);
02250     vect_sub (ac, vtable[t->vert[2]], vtable[t->vert[0]]);
02251     vect_cross (normal, ac, ab);
02252 
02253     vect_normalize (normal);
02254 }
02255 
02256 
02257 /* Find the specified rgb values in the palette table */
02258 unsigned pal_lookup (float  red, float  green, float  blue)
02259 {
02260     int i;
02261 
02262     /* The palette table is usually small so just do a simple linear search */
02263     for (i = psize-1; i >= 0; i--) {
02264        if (ptable[i].red   == red &&
02265            ptable[i].green == green &&
02266            ptable[i].blue  == blue)
02267          break;
02268     }
02269 
02270     if (i >= 0)
02271        return i;    /* found, return the table index */
02272 
02273     /* not found, insert the new palette into the table */
02274     ++psize;
02275     if (psize > pmax) {
02276        /* table not big enough, resize it */
02277        pmax = pmax + 10;
02278        ptable = realloc (ptable, pmax * sizeof(Palette));
02279        if (ptable == NULL)
02280            abortmsg ("Insufficient memory to expand palette table.", 1);
02281     }
02282 
02283     ptable[psize-1].red   = red;
02284     ptable[psize-1].green = green;
02285     ptable[psize-1].blue  = blue;
02286 
02287     return (psize-1);
02288 }
02289 
02290 
02291 /* Find the specified named texture in the texture table */
02292 unsigned texture_lookup (char *texture_name)
02293 {
02294     int i;
02295 
02296     /* The texture table is usually small so just do a simple linear search */
02297     for (i = tsize-1; i >= 0; i--) {
02298        if (strcmp (ttable[i], texture_name) == 0)
02299            break;
02300     }
02301 
02302     if (i >= 0)
02303        return i;    /* found, return the table index */
02304 
02305     /* not found, insert the new texture into the table */
02306     ++tsize;
02307     if (tsize > tmax) {
02308        /* table not big enough, resize it */
02309        tmax = tmax + 10;
02310        ttable = realloc (ttable, tmax * sizeof(Texture));
02311        if (ttable == NULL)
02312            abortmsg ("Insufficient memory to expand palette table.", 1);
02313     }
02314 
02315     ttable[tsize-1] = malloc (strlen(texture_name) + 1);
02316     if (ttable[tsize-1] == NULL)
02317        abortmsg ("Insufficient memory for texture name.", 1);
02318 
02319     strcpy (ttable[tsize-1], texture_name);
02320 
02321     return (tsize-1);
02322 }
02323 
02324 
02325 /* Find the specified vertex in the vertex table */
02326 unsigned vert_lookup (float  x, float  y, float  z)
02327 {
02328     VertList *p, *new_node;
02329     unsigned hash;
02330 
02331     /* Vertex table is usually very large, use hash lookup */
02332     hash = (unsigned)((int)(326.4*x) ^ (int)(694.7*y) ^ (int)(1423.6*z)) % HASHSIZE;
02333 
02334     for (p = vert_hash[hash]; p != NULL; p = p->next) {
02335        if (vtable[p->vert][0] == x && vtable[p->vert][1] == y &&
02336            vtable[p->vert][2] == z) break;
02337     }
02338 
02339     if (p != NULL)
02340        return (p->vert);   /* found, return the table index */
02341 
02342     /* not found, insert the new vertex into the table */
02343     ++vsize;
02344     if (vsize > vmax) {
02345        /* table not big enough, expand it */
02346        vmax = vmax + 100;
02347        vtable = realloc (vtable, vmax * sizeof(Vector));
02348        if (vtable == NULL)
02349            abortmsg ("Insufficient memory for vertices.\n", 1);
02350     }
02351 
02352     vect_init (vtable[vsize-1], x, y, z);
02353 
02354     new_node = malloc (sizeof(VertList));
02355     if (new_node == NULL)
02356        abortmsg ("Insufficient memory for hash table.", 1);
02357 
02358     new_node->vert  = vsize-1;
02359     new_node->next  = vert_hash[hash];
02360     vert_hash[hash] = new_node;
02361 
02362     return (vsize-1);
02363 }
02364 
02365 
02366 /* Checks if triangle is degenerate (zero area) */
02367 int  degen_tri (float  ax, float  ay, float  az,
02368               float  bx, float  by, float  bz,
02369               float  cx, float  cy, float  cz)
02370 {
02371     Vector  ab, ac, norm;
02372     double  mag, fact;
02373 
02374     fact = pow (10.0, dec_point);
02375 
02376     /* Round the coords off to the output precision before checking */
02377     ax = floor((ax*fact) + 0.5)/fact;
02378     ay = floor((ay*fact) + 0.5)/fact;
02379     az = floor((az*fact) + 0.5)/fact;
02380     bx = floor((bx*fact) + 0.5)/fact;
02381     by = floor((by*fact) + 0.5)/fact;
02382     bz = floor((bz*fact) + 0.5)/fact;
02383     cx = floor((cx*fact) + 0.5)/fact;
02384     cy = floor((cy*fact) + 0.5)/fact;
02385     cz = floor((cz*fact) + 0.5)/fact;
02386 
02387     vect_init (ab, ax-bx, ay-by, az-bz);
02388     vect_init (ac, ax-cx, ay-cy, az-cz);
02389     vect_cross (norm, ab, ac);
02390 
02391     mag = vect_mag(norm);
02392 
02393     return (mag < DEGEN_TOL);
02394 }
02395 
02396 
02397 void abortmsg (char *msg, int exit_code)
02398 {
02399     printf ("\n%s\n", msg);
02400     exit (exit_code);
02401 }
02402 
02403 
02404 float  fltmin (float  a, float  b)
02405 {
02406     if (a < b)
02407        return a;
02408     else
02409        return b;
02410 }
02411 
02412 
02413 float  fltmax (float  a, float  b)
02414 {
02415     if (a > b)
02416        return a;
02417     else
02418        return b;
02419 }
02420 
02421 
02422 void add_ext (char *fname, char *ext, int force)
02423 {
02424     int i;
02425 
02426     for (i = 0; i < strlen(fname); i++)
02427        if (fname[i] == '.') break;
02428 
02429     if (fname[i] == '\0' || force) {
02430        if (strlen(ext) > 0)
02431            fname[i++] = '.';
02432 
02433        strcpy (&fname[i], ext);
02434     }
02435 }
02436 
02437 
02438 void cleanup_name (char *name)
02439 {
02440     char *tmp = malloc (strlen(name)+1);
02441     int  i;
02442 
02443     /* Remove any leading blanks or quotes */
02444     i = 0;
02445     while ((name[i] == ' ' || name[i] == '"') && name[i] != '\0')
02446        i++;
02447 
02448     strcpy (tmp, &name[i]);
02449 
02450     /* Remove any trailing blanks or quotes */
02451     for (i = strlen(tmp)-1; i >= 0; i--) {
02452        if (isprint(tmp[i]) && !isspace(tmp[i]) && tmp[i] != '"')
02453            break;
02454        else
02455            tmp[i] = '\0';
02456     }
02457 
02458     strcpy (name, tmp);
02459 
02460     /* Prefix the letter 'N' to materials that begin with a digit */
02461     if (!isdigit (name[0]))
02462        strcpy (tmp, name);
02463     else {
02464        tmp[0] = 'N';
02465        strcpy (&tmp[1], name);
02466     }
02467 
02468     /* Replace all illegal charaters in name with underscores */
02469     for (i = 0; tmp[i] != '\0'; i++) {
02470        if (!isalnum(tmp[i]))
02471           tmp[i] = '_';
02472     }
02473 
02474     strcpy (name, tmp);
02475 
02476     free (tmp);
02477 }
02478 
02479