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 /*---------------------------------------------------------------------*/
27 #include "triangulate.h"
36 /* TIMING for Windows */
38 # include <sys/timeb.h>
42 # include <sys/types.h>
43 # include <sys/param.h>
44 # include <sys/times.h>
45 # if defined(__FreeBSD__)
52 # endif /* __FreeBSD__ */
55 static long total = 0;
59 dummy = buffer.tms_utime + buffer.tms_stime +
60 buffer.tms_cutime + buffer.tms_cstime;
61 cpu_time = ((dummy - total) * 1000) / HZ;
77 struct timeb timebuffer;
86 timeline = ctime( & ( timebuffer.time ) );
87 printf( "The time is %.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20] );
90 printf("The time is %ld\n",timer);
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.
101 int main (int argc,char *argv[])
103 char *fname, *oname, *all,buff[255], *ptr, *ptr2;
112 int temp[STRIP_MAX],vertex,strips, swaps,tempi,cost,triangles;
122 BOOL texture, normal, normal_and_texture,quads = FALSE;
124 /* Options variables */
125 double norm_difference;
127 /* Structures for the object */
128 struct vert_struct *vertices = NULL,
136 Scan the file once to find out the number of vertices,
137 vertice normals, and faces so we can set up some memory
140 /* Interpret the options specified */
141 norm_difference = get_options(argc,argv,&f,&t,&tr,&g);
147 fname = argv[argc-2];
148 oname = argv[argc-1];
150 printf ("Input file: %s Output file: %s\n", fname, oname);
151 printf ("Scanning...%s ",file_open);
154 /* File that will contain the triangle strip data */
156 bands = fopen(oname, "w");
158 /* File can be in binary for faster reading */
159 if (file = fopen (fname,file_open))
165 fread (buff,sizeof(char) * 255,1, file);
167 fgets (buff, sizeof(char) * 255, file);
179 else if (*(buff+1)=='t')
181 /* At a regular vertex */
186 else if (*buff == 'f')
191 while (strtok(NULL, " ") != NULL) tempi++;
192 num_tris += tempi - 2;
199 printf("Error in the file name\n");
203 printf("%s pass 1\n",fname);
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);
211 nvertices = (struct vert_struct *)
212 malloc (sizeof (struct vert_struct) * num_nvert);
213 vert_norms = (int *) malloc (sizeof (int) * num_vert);
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
219 init_vert_norms(num_vert);
224 if (num_texture > 0) {
225 vert_texture = (int *) malloc (sizeof(int) * num_vert);
226 init_vert_texture(num_vert);
230 Set up the temporary 'p' pointers
232 pvertices = vertices;
233 pnvertices = nvertices;
235 /* Load the object into memory */
236 /*printf (" Loading...");*/
238 fprintf(bands,"#%s: a triangle strip representation created by STRIPE.\n#This is a .objf file\n#by Francine Evans\n",fname);
240 /* File will be put in a list for faster execution if file is in binary */
241 if (file = fopen(fname,file_open)) {
243 all = (char *) malloc (sizeof(char) * 255 * num);
244 fread(all,sizeof(char) * 255 * num, 1, file);
247 ptr = (char *) malloc (sizeof(char) * 255 * num);
258 fgets (ptr, sizeof(char) * 255, file);
263 /* Load in vertices/normals */
266 sscanf (ptr+3,"%lf%lf%lf",
270 fprintf(bands,"vn %f %f %f\n",
271 pnvertices->x,pnvertices->y,pnvertices->z);
273 } else if (*(ptr+1)=='t') {
274 sscanf (ptr+3,"%f%f%f",¢er[0],¢er[1],¢er[2]);
275 fprintf(bands,"vt %f %f %f\n",center[0],center[1],center[2]);
277 sscanf (ptr+2,"%lf%lf%lf",
281 fprintf(bands,"v %f %f %f\n",
282 pvertices->x,pvertices->y,pvertices->z);
285 } else if (*ptr == 'f') {
290 normal = FALSE; texture = FALSE, normal_and_texture = FALSE;
292 if (*ptr2 >='0' && *ptr2 <='9') {
295 while (*ptr2 && (*ptr2!=' ' && *ptr2!='/')) {
298 /* There are normals in this line */
300 if (*(ptr2+1) == '/') {
305 } else if (*ptr2 == ' ') {
306 if ((num2 == 3) && (texture)) {
307 normal_and_texture = TRUE;
318 loop on the number of numbers in this line of face data
322 for (loop=0;loop<num2;loop++) {
323 /* skip the whitespace */
324 while (*ptr2<'0' || *ptr2>'9') {
330 vertex = atoi(ptr2)-1;
332 vertex = num_vert + vertex;
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
340 if ( (normal) && (!normal_and_texture)) {
342 add_norm_id(vertex,vert_count);
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
348 if (norm_array(vertex,0,norm_difference,nvertices,num_vert)) {
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
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
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);
364 temp[vert_count - 1] = num_vert - 1;
365 if (!(add_vert_id(num_vert - 1,vert_count))) {
371 temp[vert_count] = vertex ;
373 if (!(add_vert_id(vertex,vert_count))) {
376 norm_array(vertex,1,norm_difference,nvertices,num_vert);
378 } else if (normal_and_texture) {
379 /* Else there are vertices and textures with the data */
381 add_norm_id(vertex,vert_count);
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
387 if (norm_array(vertex,0,norm_difference,nvertices,num_vert)) {
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
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
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);
403 temp[vert_count - 1] = num_vert - 1;
404 if (!(add_vert_id(num_vert - 1,vert_count))) {
408 } else if ((loop == 0) || (*(ptr2-1) == ' ')) {
410 temp[vert_count] = vertex ;
412 if (vert_count == 4) {
415 if (!(add_vert_id(vertex,vert_count))) {
418 add_texture(vertex,TRUE);
419 norm_array(vertex,1,norm_difference,nvertices,num_vert);
422 add_texture(vertex,FALSE);
424 } else if ( texture ) {
427 temp[vert_count] = vertex ;
431 add_texture(vertex,TRUE);
432 if (!(add_vert_id(vertex,vert_count)))
434 norm_array(vertex,1,norm_difference,nvertices,num_vert);
437 add_texture(vertex,FALSE);
440 /*** no nvertices ***/
441 temp[vert_count] = vertex ;
445 if (!(add_vert_id(vertex,vert_count)))
448 while (*ptr2>='0' && *ptr2<='9')
451 /* Done with the polygon */
452 num_edges += vert_count;
453 /* add it to face structure */
455 AddNewFace(ids,vert_count,face_id,norms);
461 else if ((g == TRUE) && (face_id > 0)
462 && ((*ptr == 'g') || (*ptr == 's') || (*ptr == 'm') || (*ptr == 'o')))
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.
469 Start_Edge_Struct(num_vert);
470 Find_Adjacencies(face_id);
474 Build_SGI_Table(num_vert,face_id);
475 /* Code for lengths of walks in each direction */
476 /* Save_Walks(face_id,TRUE); */
479 /* Code for finding the bands */
480 Find_Bands(face_id,bands,&swaps,&strips,&cost,&triangles,num_nvert,vert_norms,num_texture,vert_texture);
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
488 printf("Total %d triangles with %d cost\n",triangles,cost);
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);
498 SGI_Strip(num_vert,face_id,bands,t,tr);
500 /* Get the total cost */
501 Output_TriEx(-1,-2,-3,NULL,-1,-20,cost);
503 End_Face_Struct(num_faces);
504 End_Edge_Struct(num_vert);
508 Start_Face_Struct(num_faces-face_id);
509 num_faces = num_faces - face_id;
514 /* Done reading in all the information into data structures */
518 printf("Input Done.\n\n");
523 printf ("Vertices: %d\nNormals: %d\nFaces: %d\n",num_vert,num_nvert,num_faces);
525 Start_Edge_Struct(num_vert);
526 Find_Adjacencies(num_faces);
531 Build_SGI_Table(num_vert,num_faces);
536 /* Code for lengths of walks in each direction */
537 /* Save_Walks(num_faces,TRUE); */
538 Save_Walks(num_faces);
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);*/
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
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);
556 SGI_Strip(num_vert,num_faces,bands,t,tr);
558 /* Get the total cost */
559 Output_TriEx(-1,-2,-3,NULL,-1,-20,cost);
561 End_Face_Struct(num_faces);
562 End_Edge_Struct(num_vert);