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