1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
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.
14 /*---------------------------------------------------------------------*/
23 #include "triangulate.h"
33 /* TIMING for Windows */
35 #include <sys/timeb.h>
39 #include <sys/types.h>
40 #include <sys/param.h>
41 #include <sys/times.h>
46 #define START gettimeofday(&tm,&tz);\
47 et = (tm.tv_sec)+ (0.000001* (tm.tv_usec));
49 #define STOP gettimeofday(&tm,&tz);\
50 et = (tm.tv_sec)+(0.000001*(tm.tv_usec)) - et;
58 struct _timeb timebuffer;
66 _ftime( &timebuffer );
67 timeline = ctime( & ( timebuffer.time ) );
68 printf( "The time is %.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20] );
70 printf("Time for last frame = %lf seconds\n", et);
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.
81 void main (int argc,char *argv[])
83 char *fname,*all,buff[255], *ptr, *ptr2;
85 int face_id=0, vert_count, loop, num=0,num2;
87 int temp[MAX1],vertex,strips, swaps,tempi,cost,triangles;
97 BOOL texture, normal, normal_and_texture,quads = FALSE;
99 /* Options variables */
100 float norm_difference;
102 /* Structures for the object */
103 struct vert_struct *vertices = NULL,
111 /* File that will contain the triangle strip data */
112 bands = fopen("bands.d","w");
115 Scan the file once to find out the number of vertices,
116 vertice normals, and faces so we can set up some memory
119 /* Interpret the options specified */
120 norm_difference = get_options(argc,argv,&f,&t,&tr,&g);
126 fname = argv[argc-1];
127 printf ("File: %s\n",fname);
128 /*printf ("Scanning...%s ",file_open);*/
131 /* File can be in binary for faster reading */
132 if (file = fopen (fname,file_open))
138 fread (buff,sizeof(char) * 255,1, file);
140 fgets (buff, sizeof(char) * 255, file);
148 else if (*(buff+1)=='t')
150 /* At a regular vertex */
155 else if (*buff == 'f')
160 while (strtok(NULL, " ") != NULL) tempi++;
161 num_tris += tempi - 2;
169 printf("Error in the file name\n");
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);
181 nvertices = (struct vert_struct *)
182 malloc (sizeof (struct vert_struct) * num_nvert);
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
189 init_vert_norms(num_vert);
196 vert_texture = (int *) malloc (sizeof(int) * num_vert);
197 init_vert_texture(num_vert);
200 /* Set up the temporary 'p' pointers
202 pvertices = vertices;
203 pnvertices = nvertices;
205 /* Load the object into memory */
206 /*printf (" Loading...");*/
208 fprintf(bands,"#%s: a triangle strip representation created by STRIPE.\n#This is a .objf file\n#by Francine Evans\n",fname);
210 /* File will be put in a list for faster execution if file is in binary */
211 if (file = fopen(fname,file_open))
215 all = (char *) malloc (sizeof(char) * 255 * num);
216 fread(all,sizeof(char) * 255 * num, 1, file);
220 ptr = (char *) malloc (sizeof(char) * 255 * num);
228 fgets (ptr, sizeof(char) * 255, file);
232 /* Load in vertices/normals */
237 sscanf (ptr+3,"%lf%lf%lf",
241 fprintf(bands,"vn %lf %lf %lf\n",
242 pnvertices->x,pnvertices->y,pnvertices->z);
245 else if (*(ptr+1)=='t')
247 sscanf (ptr+3,"%f%f%f",¢er[0],¢er[1],¢er[2]);
248 fprintf(bands,"vt %f %f %f\n",center[0],center[1],center[2]);
252 sscanf (ptr+2,"%lf%lf%lf",
256 fprintf(bands,"v %lf %lf %lf\n",
257 pvertices->x,pvertices->y,pvertices->z);
262 else if (*ptr == 'f')
268 normal = FALSE; texture = FALSE, normal_and_texture = FALSE;
271 if (*ptr2 >='0' && *ptr2 <='9')
275 while (*ptr2 && (*ptr2!=' ' && *ptr2!='/'))
277 /* There are normals in this line */
280 if (*(ptr2+1) == '/')
285 else if (*ptr2 == ' ')
287 if ((num2 == 3) && (texture))
288 normal_and_texture = TRUE;
297 /* loop on the number of numbers in this line of face data
301 for (loop=0;loop<num2;loop++)
303 /* skip the whitespace */
304 while (*ptr2<'0' || *ptr2>'9')
310 vertex = atoi(ptr2)-1;
313 vertex = num_vert + vertex;
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
320 if ( (normal) && (!normal_and_texture))
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
329 if (norm_array(vertex,0,norm_difference,nvertices,num_vert))
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
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
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);
344 temp[vert_count - 1] = num_vert - 1;
345 if (!(add_vert_id(num_vert - 1,vert_count)))
352 temp[vert_count] = vertex ;
354 if (!(add_vert_id(vertex,vert_count)))
356 norm_array(vertex,1,norm_difference,nvertices,num_vert);
360 /* Else there are vertices and textures with the data */
361 else if (normal_and_texture)
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
370 if (norm_array(vertex,0,norm_difference,nvertices,num_vert))
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
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
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);
385 temp[vert_count - 1] = num_vert - 1;
386 if (!(add_vert_id(num_vert - 1,vert_count)))
391 else if ((loop == 0) || (*(ptr2-1) == ' '))
393 temp[vert_count] = vertex ;
397 if (!(add_vert_id(vertex,vert_count)))
399 add_texture(vertex,TRUE);
400 norm_array(vertex,1,norm_difference,nvertices,num_vert);
402 else /* The texture */
403 add_texture(vertex,FALSE);
411 temp[vert_count] = vertex ;
415 add_texture(vertex,TRUE);
416 if (!(add_vert_id(vertex,vert_count)))
418 norm_array(vertex,1,norm_difference,nvertices,num_vert);
421 add_texture(vertex,FALSE);
426 /*** no nvertices ***/
427 temp[vert_count] = vertex ;
431 if (!(add_vert_id(vertex,vert_count)))
434 while (*ptr2>='0' && *ptr2<='9')
437 /* Done with the polygon */
438 num_edges += vert_count;
439 /* add it to face structure */
441 AddNewFace(ids,vert_count,face_id,norms);
447 else if ((g == TRUE) && (face_id > 0)
448 && ((*ptr == 'g') || (*ptr == 's') || (*ptr == 'm') || (*ptr == 'o')))
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.
454 Start_Edge_Struct(num_vert);
455 Find_Adjacencies(face_id);
459 Build_SGI_Table(num_vert,face_id);
460 /* Code for lengths of walks in each direction */
461 Save_Walks(face_id,TRUE);
463 /* Code for finding the bands */
464 Find_Bands(face_id,bands,&swaps,&strips,&cost,&triangles,num_nvert,vert_norms,num_texture,vert_texture);
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
471 printf("Total %d triangles with %d cost\n",triangles,cost);
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);
481 SGI_Strip(num_vert,face_id,bands,t,tr);
483 /* Get the total cost */
484 Output_TriEx(-1,-2,-3,NULL,-1,-20,cost);
486 End_Face_Struct(num_faces);
487 End_Edge_Struct(num_vert);
491 Start_Face_Struct(num_faces-face_id);
492 num_faces = num_faces - face_id;
497 /* Done reading in all the information into data structures */
500 /*printf(" Done.\n\n");*/
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);
511 Build_SGI_Table(num_vert,num_faces);
518 /* Code for lengths of walks in each direction */
519 Save_Walks(num_faces,TRUE);
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);*/
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
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);
536 SGI_Strip(num_vert,num_faces,bands,t,tr);
538 /* Get the total cost */
539 Output_TriEx(-1,-2,-3,NULL,-1,-20,cost);
541 End_Face_Struct(num_faces);
542 End_Edge_Struct(num_vert);