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