Stripe_w/bands.c

   1 /********************************************************************/
   2 /*   STRIPE: converting a polygonal model to triangle strips
   3      Francine Evans, 1996.
   4      SUNY @ Stony Brook
   5      Advisors: Steven Skiena and Amitabh Varshney
   6 */
   7 /********************************************************************/
   8
   9 /*---------------------------------------------------------------------*/
  10 /*   STRIPE: bands.c
  11      This file contains the main procedure code that will read in the
  12      object and then call the routines that produce the triangle strips.
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16
  17 #ifdef HAVE_CONFIG_H
  18 #  include <config.h>
  19 #endif
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <math.h>
  24 #include <string.h>
  25 #include "global.h"
  26 #include "polverts.h"
  27 #include "triangulate.h"
  28 #include "ties.h"
  29 #include "outputex.h"
  30 #include "options.h"
  31 #include "local.h"
  32 #include "init.h"
  33 #include "free.h"
  34 #include "add.h"
  35
  36 /*   TIMING for Windows */
  37 #ifdef WIN32
  38 #include <sys/timeb.h>
  39 #include <time.h>
  40 /*   TIMING for UNIX */
  41 #else
  42 #include <sys/types.h>
  43 #include <sys/param.h>
  44 #include <sys/times.h>
  45 extern long times( );
  46 long elapsed()
  47 {
  48   static long total = 0;
  49   long cpu_time, dummy;
  50   struct tms buffer;
  51   times(&buffer);
  52   dummy    = buffer.tms_utime  + buffer.tms_stime +
  53              buffer.tms_cutime + buffer.tms_cstime;
  54   cpu_time = ((dummy - total) * 1000) / HZ;
  55   total    = dummy;
  56   return(cpu_time);
  57 }
  58 #endif
  59
  60
  61 int     norms[STRIP_MAX];
  62 int     *vert_norms;
  63 int     *vert_texture;
  64
  65
  66 void get_time()
  67 {
  68   /*   For timing */
  69 #ifdef WIN32
  70   struct timeb timebuffer;
  71   char *timeline;
  72 #else
  73   long timer;
  74 #endif
  75
  76
  77 #ifdef WIN32
  78   ftime( &timebuffer );
  79   timeline = ctime( & ( timebuffer.time ) );
  80   printf( "The time is %.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20] );
  81 #else
  82   timer = elapsed();
  83   printf("The time is %ld\n",timer);
  84 #endif
  85 }
  86
  87 /*
  88 **
  89      Here the main program begins. It will start by loading in a .obj file
  90      then it will convert the polygonal model into triangle strips.
  91 **
  92 */
  93
  94 int main (int argc,char *argv[])
  95 {
  96   char  *fname, *oname, *all,buff[255], *ptr, *ptr2;
  97         FILE    *file, *bands;
  98         int face_id=0;
  99   int vert_count=0;
 100   int loop=0;
 101   int num=0;
 102   int num2=0;
 103
 104         float center[3];
 105   int temp[STRIP_MAX],vertex,strips, swaps,tempi,cost,triangles;
 106   int f,t,tr,g;
 107   char *file_open;
 108         int     num_vert        = 0,
 109                 num_faces       = 0,
 110                 num_nvert       = 0,
 111                 num_edges       = 0,
 112     num_texture = 0,
 113     num_tris = 0;
 114   double fra = 0.0;
 115   BOOL texture, normal, normal_and_texture,quads = FALSE;
 116
 117   /*   Options variables */
 118   double norm_difference;
 119
 120         /*   Structures for the object */
 121   struct vert_struct    *vertices       = NULL,
 122     *nvertices  = NULL,
 123                 *pvertices      = NULL,
 124                 *pnvertices     = NULL;
 125
 126   get_time();
 127
 128   /*
 129     Scan the file once to find out the number of vertices,
 130     vertice normals, and faces so we can set up some memory
 131     structures
 132     */
 133   /* Interpret the options specified */
 134   norm_difference = get_options(argc,argv,&f,&t,&tr,&g);
 135   if (f == BINARY)
 136       file_open = "rb";
 137   else
 138       file_open = "r";
 139
 140   fname = argv[argc-2];
 141   oname = argv[argc-1];
 142
 143   printf ("Input file: %s  Output file: %s\n", fname, oname);
 144   printf ("Scanning...%s ",file_open);
 145
 146
 147   /*   File that will contain the triangle strip data */
 148
 149   bands = fopen(oname, "w");
 150
 151   /*   File can be in binary for faster reading */
 152   if (file = fopen (fname,file_open))
 153         {
 154           while (!feof (file))
 155                 {
 156                         /*   Read a line */
 157       if (f == BINARY)
 158         fread (buff,sizeof(char) * 255,1, file);
 159                         else
 160         fgets (buff, sizeof(char) * 255, file);
 161       num++;
 162
 163       printf("%d\r",num);
 164
 165
 166       /*   At a vertex */
 167       if (*buff == 'v')
 168                         {
 169                                 /*   At a normal */
 170         if (*(buff+1)=='n')
 171                                         num_nvert++;
 172                                 else if (*(buff+1)=='t')
 173           num_texture++;
 174         /*   At a regular vertex */
 175         else
 176                                   num_vert++;
 177                         }
 178                         /*   At a face */
 179       else if (*buff == 'f')
 180                         {
 181         num_faces++;
 182                           strtok(buff, " ");
 183                           tempi = 0;
 184                           while (strtok(NULL, " ") != NULL) tempi++;
 185                           num_tris += tempi - 2;
 186       }
 187                 }
 188                 fclose (file);
 189   }
 190         else
 191   {
 192     printf("Error in the file name\n");
 193     exit(1);
 194   }
 195
 196   printf("%s pass 1\n",fname);
 197
 198         /* Allocate structures for the information */
 199         Start_Face_Struct(num_faces);
 200         vertices = (struct vert_struct *)
 201                         malloc (sizeof (struct vert_struct) * num_vert);
 202
 203         if (num_nvert > 0) {
 204     nvertices = (struct vert_struct *)
 205                 malloc (sizeof (struct vert_struct) * num_nvert);
 206     vert_norms = (int *) malloc (sizeof (int) * num_vert);
 207     /*
 208     Initialize entries to zero, in case there are 2 hits
 209     to the same vertex we will know it - used for determining
 210     the normal difference
 211     */
 212     init_vert_norms(num_vert);
 213   } else {
 214                 nvertices = NULL;
 215   }
 216
 217   if (num_texture > 0) {
 218     vert_texture = (int *) malloc (sizeof(int) * num_vert);
 219     init_vert_texture(num_vert);
 220   }
 221
 222         /*
 223   Set up the temporary 'p' pointers
 224   */
 225         pvertices = vertices;
 226         pnvertices = nvertices;
 227
 228         /* Load the object into memory */
 229         /*printf (" Loading...");*/
 230
 231    fprintf(bands,"#%s: a triangle strip representation created by STRIPE.\n#This is a .objf file\n#by Francine Evans\n",fname);
 232
 233   /*  File will be put in a list for faster execution if file is in binary */
 234   if (file = fopen(fname,file_open)) {
 235     if (f == BINARY) {
 236       all = (char *) malloc (sizeof(char) * 255 * num);
 237       fread(all,sizeof(char) * 255 * num, 1, file);
 238       ptr = all;
 239     } else {
 240       ptr = (char *) malloc (sizeof(char) * 255 * num);
 241     }
 242   }
 243
 244
 245   while (num > 0) {
 246     num--;
 247
 248     printf("%d\r",num);
 249
 250                 if (f == ASCII) {
 251       fgets (ptr, sizeof(char) * 255, file);
 252     } else {
 253       ptr = ptr + 255;
 254     }
 255
 256     /* Load in vertices/normals */
 257                 if (*ptr == 'v') {
 258                         if (*(ptr+1)=='n') {
 259                                 sscanf (ptr+3,"%lf%lf%lf",
 260                                         &(pnvertices->x),
 261                                         &(pnvertices->y),
 262                                         &(pnvertices->z));
 263                                 fprintf(bands,"vn %f %f %f\n",
 264                                         pnvertices->x,pnvertices->y,pnvertices->z);
 265                         ++pnvertices;
 266                         } else if (*(ptr+1)=='t') {
 267                                 sscanf (ptr+3,"%f%f%f",&center[0],&center[1],&center[2]);
 268                         fprintf(bands,"vt %f %f %f\n",center[0],center[1],center[2]);
 269       } else {
 270                                 sscanf (ptr+2,"%lf%lf%lf",
 271                                         &(pvertices->x),
 272                                         &(pvertices->y),
 273                                         &(pvertices->z));
 274                         fprintf(bands,"v %f %f %f\n",
 275                                         pvertices->x,pvertices->y,pvertices->z);
 276                                 ++pvertices;
 277       }
 278                 } else if (*ptr == 'f') {
 279                         /* Read in faces */
 280                         num2 = 0;
 281                         face_id++;
 282       ptr2 = ptr+1;
 283       normal = FALSE; texture = FALSE, normal_and_texture = FALSE;
 284       while (*ptr2) {
 285                           if (*ptr2 >='0' && *ptr2 <='9') {
 286                                   num2++;
 287                                   ++ptr2;
 288                                   while (*ptr2 && (*ptr2!=' ' && *ptr2!='/')) {
 289                                           ptr2++;
 290           }
 291           /*   There are normals in this line */
 292           if (*ptr2 == '/') {
 293             if (*(ptr2+1) == '/') {
 294               normal = TRUE;
 295             } else {
 296               texture = TRUE;
 297             }
 298                             } else if (*ptr2 == ' ') {
 299             if ((num2 == 3) && (texture)) {
 300               normal_and_texture = TRUE;
 301             }
 302           }
 303         } else {
 304                                   ++ptr2;
 305         }
 306                         }
 307
 308       ptr2 = ptr+1;
 309
 310       /*
 311       loop on the number of numbers in this line of face data
 312       */
 313                         vert_count = 0;
 314
 315                         for (loop=0;loop<num2;loop++) {
 316                                 /* skip the whitespace */
 317                                 while (*ptr2<'0' || *ptr2>'9') {
 318           if (*ptr2 == '-') {
 319             break;
 320           }
 321           ptr2++;
 322         }
 323                                 vertex = atoi(ptr2)-1;
 324         if (vertex < 0) {
 325           vertex = num_vert + vertex;
 326           *ptr2 = ' ';
 327           ptr2++;
 328         }
 329         /*
 330         If there are either normals or textures with the vertices
 331         in this file, the data alternates so we must read it this way
 332         */
 333                                 if ( (normal) && (!normal_and_texture)) {
 334                                         if (loop%2) {
 335             add_norm_id(vertex,vert_count);
 336             /*
 337             Test here to see if we added a new vertex, since the
 338             vertex has more than one normal and the 2 normals are greater
 339             than the threshold specified
 340             */
 341             if (norm_array(vertex,0,norm_difference,nvertices,num_vert)) {
 342               /*
 343               Add a new vertex and change the
 344               id of the vertex that we just read to the id of the new
 345               vertex that we just added
 346               */
 347               /*
 348               Put it in the output file, note the added vertices will
 349               be after the normals and separated from the rest of the
 350               vertices. Will not affect our viewer
 351               */
 352               fprintf(bands,"v %f %f %f\n",
 353                 (vertices + temp[vert_count - 1])->x,
 354                 (vertices + temp[vert_count - 1])->y,
 355                 (vertices + temp[vert_count - 1])->z);
 356               num_vert++;
 357               temp[vert_count - 1] = num_vert - 1;
 358               if (!(add_vert_id(num_vert - 1,vert_count))) {
 359                 vert_count--;
 360               }
 361             }
 362           } else {
 363                                           /* the vertex */
 364                                                 temp[vert_count] = vertex ;
 365                                                 vert_count++;
 366             if (!(add_vert_id(vertex,vert_count))) {
 367                 vert_count--;
 368             }
 369             norm_array(vertex,1,norm_difference,nvertices,num_vert);
 370                                         }
 371         } else if (normal_and_texture) {
 372           /* Else there are vertices and textures with the data */
 373           if( !((loop+1)%3)) {
 374             add_norm_id(vertex,vert_count);
 375             /*
 376             Test here to see if we added a new vertex, since the
 377             vertex has more than one normal and the 2 normals are greater
 378             than the threshold specified
 379             */
 380             if (norm_array(vertex,0,norm_difference,nvertices,num_vert)) {
 381               /*
 382               Add a new vertex and change the
 383               id of the vertex that we just read to the id of the new
 384               vertex that we just added
 385               */
 386               /*
 387               Put it in the output file, note the added vertices will
 388               be after the normals and separated from the rest of the
 389               vertices. Will not affect our viewer
 390               */
 391               fprintf(bands,"v %f %f %f\n",
 392                 (vertices + temp[vert_count - 1])->x,
 393                 (vertices + temp[vert_count - 1])->y,
 394                 (vertices + temp[vert_count - 1])->z);
 395               num_vert++;
 396               temp[vert_count - 1] = num_vert - 1;
 397               if (!(add_vert_id(num_vert - 1,vert_count))) {
 398                 vert_count--;
 399               }
 400             }
 401           } else if ((loop == 0) || (*(ptr2-1) == ' ')) {
 402             /*   the vertex */
 403             temp[vert_count] = vertex ;
 404             vert_count++;
 405             if (vert_count == 4) {
 406               quads = TRUE;
 407             }
 408             if (!(add_vert_id(vertex,vert_count))) {
 409               vert_count--;
 410             }
 411             add_texture(vertex,TRUE);
 412             norm_array(vertex,1,norm_difference,nvertices,num_vert);
 413                                         } else {
 414             /*   The texture */
 415             add_texture(vertex,FALSE);
 416           }
 417         } else if ( texture ) {
 418                                         /*   the vertex */
 419           if (!(loop%2)) {
 420                                                 temp[vert_count] = vertex ;
 421                                                 vert_count++;
 422             if (vert_count == 4)
 423               quads = TRUE;
 424             add_texture(vertex,TRUE);
 425             if (!(add_vert_id(vertex,vert_count)))
 426               vert_count--;
 427             norm_array(vertex,1,norm_difference,nvertices,num_vert);
 428                                         } else {
 429             /*   texture */
 430             add_texture(vertex,FALSE);
 431           }
 432         } else {
 433                                   /*** no nvertices ***/
 434                                         temp[vert_count] = vertex ;
 435                                         vert_count++;
 436           if (vert_count == 4)
 437             quads = TRUE;
 438           if (!(add_vert_id(vertex,vert_count)))
 439             vert_count--;
 440                                 }
 441                                 while (*ptr2>='0' && *ptr2<='9')
 442                                         ptr2++;
 443       }
 444                         /* Done with the polygon */
 445                         num_edges += vert_count;
 446                         /* add it to face structure */
 447                         if (vert_count >= 3)
 448         AddNewFace(ids,vert_count,face_id,norms);
 449       else
 450         face_id--;
 451       if (vert_count == 4)
 452         quads = TRUE;
 453     }
 454     else if ((g == TRUE) && (face_id > 0)
 455          && ((*ptr == 'g') || (*ptr  == 's') || (*ptr == 'm') || (*ptr == 'o')))
 456     {
 457       /*
 458       The user specified that the strips will be contained in each group
 459       from the data file, so we just finished a group and will find the
 460       triangle strips in it.
 461       */
 462       Start_Edge_Struct(num_vert);
 463             Find_Adjacencies(face_id);
 464             if (quads)
 465       {
 466         Init_Table_SGI();
 467               Build_SGI_Table(num_vert,face_id);
 468         /* Code for lengths of walks in each direction */
 469               /* Save_Walks(face_id,TRUE); */
 470               Save_Walks(face_id);
 471
 472         /* Code for finding the bands */
 473               Find_Bands(face_id,bands,&swaps,&strips,&cost,&triangles,num_nvert,vert_norms,num_texture,vert_texture);
 474
 475         /*
 476         Remove the faces that we did  so that we can
 477         run the strip code on the rest of the faces that are left
 478         */
 479         if (cost != 0)
 480         {
 481           printf("Total %d triangles with %d cost\n",triangles,cost);
 482           Save_Rest(&face_id);
 483           printf("We saved %d .... now doing the local algorithm\n",face_id);
 484           fprintf(bands,"\n#local\n");
 485                 End_Edge_Struct(num_vert);
 486           Start_Edge_Struct(num_vert);
 487                 Find_Adjacencies(face_id);
 488         }
 489       }
 490
 491       SGI_Strip(num_vert,face_id,bands,t,tr);
 492
 493       /* Get the total cost */
 494       Output_TriEx(-1,-2,-3,NULL,-1,-20,cost);
 495
 496       End_Face_Struct(num_faces);
 497       End_Edge_Struct(num_vert);
 498       cost = 0;
 499       face_id = 0;
 500       quads = FALSE;
 501       Start_Face_Struct(num_faces-face_id);
 502       num_faces = num_faces - face_id;
 503       Free_Strips();
 504     }
 505   }
 506
 507   /*   Done reading in all the information into data structures */
 508   num_faces = face_id;
 509   fclose (file);
 510
 511   printf("Input Done.\n\n");
 512
 513   free(vertices);
 514   free(nvertices);
 515
 516   printf ("Vertices:    %d\nNormals:    %d\nFaces:              %d\n",num_vert,num_nvert,num_faces);
 517
 518   Start_Edge_Struct(num_vert);
 519   Find_Adjacencies(num_faces);
 520
 521   /* Initialize it */
 522   Init_Table_SGI();
 523   /* Build it */
 524   Build_SGI_Table(num_vert,num_faces);
 525
 526   InitStripTable();
 527
 528   if (quads) {
 529     /* Code for lengths of walks in each direction */
 530           /* Save_Walks(num_faces,TRUE); */
 531           Save_Walks(num_faces);
 532
 533     /* Code for finding the bands */
 534           Find_Bands(num_faces,bands,&swaps,&strips,&cost,&triangles,num_nvert,vert_norms,num_texture,vert_texture);
 535     /*printf("Total %d triangles with %d cost\n",triangles,cost);*/
 536
 537     /*
 538     Remove the faces that we did  so that we can
 539     run the strip code on the rest of the faces that are left
 540     */
 541     Save_Rest(&num_faces);
 542     /*printf("We saved %d .... now doing the local algorithm\n",num_faces);*/
 543     fprintf(bands,"\n#local\n");
 544           End_Edge_Struct(num_vert);
 545     Start_Edge_Struct(num_vert);
 546           Find_Adjacencies(num_faces);
 547   }
 548
 549   SGI_Strip(num_vert,num_faces,bands,t,tr);
 550
 551   /*   Get the total cost */
 552   Output_TriEx(-1,-2,-3,NULL,-1,-20,cost);
 553
 554   End_Face_Struct(num_faces);
 555   End_Edge_Struct(num_vert);
 556   fclose(bands);
 557
 558   get_time();
 559
 560   return(0);
 561 }
 562