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