Stripe_w/output.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: output.c
  11      This file contains routines that are finding and outputting the
  12      strips from the local algorithm
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include "global.h"
  19 #include "polverts.h"
  20 #include "triangulate.h"
  21 #include "partial.h"
  22 #include "sturcts.h"
  23 #include "ties.h"
  24 #include "options.h"
  25 #include "common.h"
  26 #include "util.h"
  27 #include "free.h"
  28
  29 int *vn;
  30 int *vt;
  31 int norm;
  32 int text;
  33
  34 int Finished(int *swap, FILE *output, BOOL global)
  35 {
  36   /* We have finished all the triangles, now is time to output to
  37      the data file. In the strips data structure, every three ids
  38      is a triangle. Now we see whether we can swap, or make a new strip
  39      or continue the strip, and output the data accordingly to the
  40      data file.
  41   */
  42   int num,x,vertex1,vertex2;
  43   ListHead *pListHead;
  44   int id[2],other1,other2,index = 0,a,b,c;
  45   P_STRIPS temp1,temp2,temp3,temp4,temp5,temp6;
  46   BOOL cptexture;
  47   *swap =0;
  48
  49   cptexture = text;
  50   pListHead = strips[0];
  51   if (pListHead == NULL)
  52     return 0;
  53
  54   num = NumOnList(pListHead);
  55   // WILBUR
  56   // printf ("There are %d triangles in the extend\n",num/3);
  57
  58   /* Go through the list triangle by triangle */
  59         temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 0);
  60         temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 1);
  61         temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 2);
  62
  63   /* Next triangle for lookahead */
  64   temp4 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 3);
  65
  66
  67   /*    There is only one polygon in the strip */
  68   if (temp4 == NULL)
  69   {
  70     /* Data might be mixed and we do not have textures for some of the vertices */
  71     if ((text) &&  (vt[temp3->face_id] == 0))
  72       cptexture = FALSE;
  73     if ((norm) && (!cptexture))
  74       fprintf(output,"%d//%d %d//%d %d//%d",temp3->face_id+1,vn[temp3->face_id]+1,
  75                 temp2->face_id+1,vn[temp2->face_id]+1,
  76                 temp1->face_id+1,vn[temp1->face_id]+1);
  77     else if ((cptexture) && (!norm))
  78       fprintf(output,"%d/%d %d/%d %d/%d",temp3->face_id+1,vt[temp3->face_id]+1,
  79                 temp2->face_id+1,vt[temp2->face_id]+1,
  80                 temp1->face_id+1,vt[temp1->face_id]+1);
  81     else if ((cptexture)&& (norm))
  82       fprintf(output,"%d/%d/%d %d/%d/%d %d/%d/%d",temp3->face_id+1,vt[temp3->face_id]+1,vn[temp3->face_id]+1,
  83                 temp2->face_id+1,vt[temp2->face_id]+1,vn[temp2->face_id]+1,
  84                 temp1->face_id+1,vt[temp1->face_id]+1,vn[temp1->face_id]+1);
  85     else
  86       fprintf(output,"%d %d %d",temp3->face_id+1,temp2->face_id+1,temp1->face_id+1);
  87     Free_Strips();
  88           return 1;
  89         }
  90
  91         /* We have a real strip */
  92         temp5 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 4);
  93         temp6 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 5);
  94
  95         if ((temp1 == NULL) || (temp2 == NULL) || (temp3 == NULL) || (temp5 == NULL) || (temp6 == NULL))
  96         {
  97           printf("There is an error in the output of the triangles\n");
  98           exit(0);
  99         }
 100
 101         /* Find the vertex in the first triangle that is not in the second */
 102         vertex1 = Different(temp1->face_id,temp2->face_id,temp3->face_id,temp4->face_id,temp5->face_id,temp6->face_id,&other1,&other2);
 103         /* Find the vertex in the second triangle that is not in the first */
 104         vertex2 = Different(temp4->face_id,temp5->face_id,temp6->face_id,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&other2);
 105
 106         /* Lookahead for the correct order of the 2nd and 3rd vertex of the first triangle */
 107   temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 6);
 108         temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 7);
 109         temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 8);
 110
 111   if (temp1 != NULL)
 112     other1 = Different(temp3->face_id,temp4->face_id,temp5->face_id,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&a);
 113
 114         id[index] = vertex1; index = !index;
 115         id[index] = other1; index = !index;
 116         id[index] = other2; index = !index;
 117
 118         a = temp4->face_id;
 119         b = temp5->face_id;
 120         c = temp6->face_id;
 121
 122   /* If we need to rearrange the first sequence because otherwise
 123      there would have been a swap.
 124   */
 125
 126   if ((temp3 != NULL) && (text) && ( vt[temp3->face_id]==0))
 127     cptexture = FALSE;
 128   if ((norm) && (!cptexture))
 129     fprintf(output,"%d//%d %d//%d %d//%d ",vertex1+1,vn[vertex1]+1,
 130                other1+1,vn[other1]+1,other2+1,vn[other2]+1);
 131   else if ((cptexture) && (!norm))
 132     fprintf(output,"%d/%d %d/%d %d/%d ",vertex1+1,vt[vertex1]+1,
 133                other1+1,vt[other1]+1,other2+1,vt[other2]+1);
 134   else if ((cptexture) && (norm))
 135     fprintf(output,"%d/%d/%d %d/%d/%d %d/%d/%d ",vertex1+1,vt[vertex1]+1,vn[vertex1]+1,
 136               other1+1,vt[other1]+1,vn[other1]+1,other2+1,vt[other2]+1,vn[other2]+1);
 137   else {
 138     fprintf(output,"%d %d %d ",vertex1+1,other1+1,other2+1);
 139   }
 140
 141   // original line
 142   // for (x = 6; x < num ; x = x+3)
 143   // Wilbur modified line
 144   for (x = 6; x < num ; x = x+3)
 145         {
 146     /* Get the next triangle */
 147           temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x);
 148           temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+1);
 149           temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+2);
 150
 151     /* Error checking */
 152           if (!(member(id[0],a,b,c)) || !(member(id[1],a,b,c)) || !(member(vertex2,a,b,c)))
 153           {
 154                   /* If we used partial we might have a break in the middle of a strip */
 155                   fprintf(output,"\nt ");
 156             /* Find the vertex in the first triangle that is not in the second */
 157             vertex1 = Different(a,b,c,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&other2);
 158             /* Find the vertex in the second triangle that is not in the first */
 159             vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
 160
 161             id[index] = vertex1; index = !index;
 162             id[index] = other1; index = !index;
 163             id[index] = other2; index = !index;
 164           }
 165
 166           if ((temp1 == NULL ) || (temp2 == NULL) || (temp3 == NULL))
 167           {
 168                   printf("There is an error in the triangle list \n");
 169                   exit(0);
 170           }
 171
 172     if ((id[0] == id[1]) || (id[0] == vertex2))
 173       continue;
 174
 175     if ( (member(id[index],temp1->face_id,temp2->face_id,temp3->face_id)) )
 176     {
 177       if ((text) && ( vt[id[index]]==0)) {
 178         cptexture = FALSE;
 179       }
 180       if ((!norm) && (!cptexture)) {
 181         fprintf(output,"%d ",id[index]+1);
 182       } else if ((norm) && (!cptexture)) {
 183         fprintf(output,"%d//%d ",id[index]+1,vn[id[index]]+1);
 184       } else if ((!norm) && (cptexture)) {
 185         fprintf(output,"%d/%d ",id[index]+1,vt[id[index]]+1);
 186       } else {
 187         fprintf(output,"%d/%d/%d ",id[index]+1,vt[id[index]]+1,vn[id[index]]+1);
 188       }
 189
 190       index = !index;
 191       *swap = *swap + 1;
 192     }
 193
 194     if ((text) && ( vt[vertex2]==0))
 195       cptexture = FALSE;
 196           if ((!norm) && (!cptexture))
 197       fprintf(output,"\nq %d ",vertex2+1);
 198     else if ((norm) && (!cptexture))
 199       fprintf(output,"\nq %d//%d ",vertex2+1,vn[vertex2]+1);
 200     else if ((!norm) && (cptexture))
 201       fprintf(output,"\nq %d/%d ",vertex2+1,vt[vertex2]+1);
 202     else
 203       fprintf(output,"\nq %d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
 204
 205     id[index] = vertex2; index = !index;
 206
 207           /* Get the next vertex not in common */
 208           vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
 209           a = temp1->face_id;
 210           b = temp2->face_id;
 211           c = temp3->face_id;
 212         }
 213
 214   /* Do the last vertex */
 215   if ((!norm) && (!cptexture))
 216     fprintf(output,"\nq %d ",vertex2+1);
 217   else if ((norm) && (!cptexture))
 218     fprintf(output,"\nq %d//%d ",vertex2+1,vn[vertex2]+1);
 219   else if ((!norm) && (cptexture))
 220     fprintf(output,"\nq %d/%d ",vertex2+1,vt[vertex2]+1);
 221   else
 222     fprintf(output,"\nq %d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
 223
 224   Free_Strips();
 225   return (num/3);
 226 }
 227
 228
 229
 230
 231
 232 void Output_Tri(int id1, int id2, int id3,FILE *bands, int color1, int color2, int color3,BOOL end)
 233 {
 234      /*   We will save everything into a list, rather than output at once,
 235              as was done in the old routine. This way for future modifications
 236              we can change the strips later on if we want to.
 237      */
 238
 239     int temp1,temp2,temp3;
 240
 241     /*  Make sure we do not have an error */
 242     /*    There are degeneracies in some of the files */
 243         if ( (id1 == id2) || (id1 == id3) || (id2 == id3))
 244         {
 245                 printf("Degenerate triangle %d %d %d\n",id1,id2,id3);
 246                 exit(0);
 247         }
 248      else
 249      {
 250           Last_Edge(&temp1,&temp2,&temp3,0);
 251              Add_Id_Strips(id1,end);
 252              Add_Id_Strips(id2,end);
 253              Add_Id_Strips(id3,end);
 254              Last_Edge(&id1,&id2,&id3,1);
 255      }
 256 }
 257
 258
 259 int Polygon_Output(P_ADJACENCIES temp,int face_id,int bucket,
 260                                         ListHead *pListHead, BOOL first, int *swaps,
 261                          FILE *bands,int color1,int color2,int color3,BOOL global, BOOL end)
 262 {
 263         ListHead *pListFace;
 264         PF_FACES face;
 265         P_ADJACENCIES pfNode;
 266         int next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
 267         P_ADJACENCIES lpListInfo;
 268      int ties=0;
 269
 270      /* We have a polygon to output, the id is face id, and the number
 271            of adjacent polygons to it is bucket. This routine extends the patches from
 272         either end to make longer triangle strips.
 273         */
 274
 275
 276      /*  Now get the edge */
 277      Last_Edge(&e1,&e2,&e3,0);
 278
 279      /*  Get the polygon with id face_id */
 280         pListFace  = PolFaces[face_id];
 281         face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
 282
 283      /*  We can't go any more */
 284      if ((face->nPolSize == 1) || ((face->nPolSize == 4) && (global))) /* if global, then we are still doing patches */
 285      {
 286         /*     Remove it from the list so we do not have to waste
 287                time visiting it in the future, or winding up in an infinite loop
 288                if it is the first on that we are looking at for a possible strip
 289         */
 290         if (face->nPolSize == 1)
 291              RemoveList(pListHead,(PLISTINFO) temp);
 292         if (first)
 293              return 0;
 294         else
 295              return (Finished(swaps,bands,global));
 296     }
 297
 298     if (face->nPolSize == 3)
 299     {
 300                 /*      It is already a triangle */
 301                 if (bucket == 0)
 302                 {
 303                         /*      It is not adjacent to anything so we do not have to
 304                                    worry about the order of the sides or updating adjacencies
 305                         */
 306
 307                   next_face_id = Different(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),
 308                                               e1,e2,e3,&other1,&other2);
 309                         face->nPolSize = 1;
 310
 311                /* If this is the first triangle in the strip */
 312                if ((e2 == 0) && (e3 ==0))
 313                {
 314                     e2 = other1;
 315                     e3 = other2;
 316                }
 317
 318                Output_Tri(e2,e3,next_face_id,bands,color1,color2,color3,end);
 319                RemoveList(pListHead,(PLISTINFO) temp);
 320                return (Finished(swaps,bands,global));
 321           }
 322
 323
 324           /*  It is a triangle with adjacencies. This means that we
 325                     have to:
 326                                 1. Update the adjacencies in the list, because we are
 327                                         using this polygon and it will be deleted.
 328                                 2. Get the next polygon.
 329                 */
 330                 else
 331                 {
 332                         /*   Return the face_id of the next polygon we will be using,
 333                                 while updating the adjacency list by decrementing the
 334                                 adjacencies of everything adjacent to the current triangle.
 335                         */
 336
 337                next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
 338                /*  Maybe we deleted something in a patch and could not find an adj polygon */
 339                if (next_face_id == -1)
 340                {
 341                        Output_Tri(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),bands,color1,
 342                                   color2,color3,end);
 343                        face->nPolSize = 1;
 344                        RemoveList(pListHead,(PLISTINFO) temp);
 345                        return (Finished(swaps,bands,global));
 346                }
 347
 348                      /*      Find the other vertex to transmit in the triangle */
 349                      e3 = Return_Other(face->pPolygon,e1,e2);
 350                   Last_Edge(&other1,&other2,&other3,0);
 351
 352                   if ((other2 != 0) && (other3 != 0))
 353                   {
 354                       /*   See which vertex in the output edge is not in the input edge */
 355                       if ((e1 != other2) && (e1 != other3))
 356                             e3 = e1;
 357                       else if ((e2 != other2) && (e2 != other3))
 358                              e3 = e2;
 359                       else
 360                       {
 361                             printf("There is an error in the tri with adj\n");
 362                             exit(0);
 363                       }
 364
 365                       /*   See which vertex of the input edge is not in the output edge */
 366                       if ((other2 != e1) && (other2 != e2))
 367                       {
 368                             other1 = other2;
 369                             other2 = other3;
 370                       }
 371                       else if ((other3 != e1) && (other3 != e2))
 372                             other1 = other3;
 373                       else
 374                       {
 375                             printf("There is an error in getting the tri with adj\n");
 376                             exit(0);
 377                       }
 378
 379                   }
 380                else
 381                {
 382                   /*     We are the first triangle in the strip and the starting edge
 383                          has not been set yet
 384                   */
 385                   /*  Maybe we deleted something in a patch and could not find an adj polygon */
 386                   if (next_face_id == -1)
 387                   {
 388                        Output_Tri(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),bands,color1,
 389                                   color2,color3,end);
 390                        face->nPolSize = 1;
 391                        RemoveList(pListHead,(PLISTINFO) temp);
 392                        return (Finished(swaps,bands,global));
 393                   }
 394
 395                   other1 = e3;
 396                   e3 = e2;
 397                   other2 = e1;
 398                }
 399
 400                   /*   At this point the adjacencies have been updated  and we
 401                                 have the next polygon id
 402                   */
 403
 404                Output_Tri(other1,other2,e3,bands,color1,color2,color3,end);
 405                face->nPolSize = 1;
 406                      RemoveList(pListHead,(PLISTINFO) temp);
 407
 408                /*  Maybe we deleted something in a patch and could not find an adj polygon */
 409                if (next_face_id == -1)
 410                     return (Finished(swaps,bands,global));
 411
 412                if (Done(next_face_id,59,&next_bucket) == NULL)
 413                      {
 414                              printf("We deleted the next face 4%d\n",next_face_id);
 415                              exit(0);
 416                   }
 417
 418                         pListHead = array[next_bucket];
 419                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 420                         if ( pfNode )
 421                                 pfNode->face_id = next_face_id;
 422                         lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 423                                 (int (*)(void *,void *)) (Compare)));
 424                         if (lpListInfo == NULL)
 425                         {
 426                                 printf("There is an error finding the next polygon3 %d\n",next_face_id);
 427                                 exit(0);
 428                         }
 429                         return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
 430                                                      pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
 431
 432                 }
 433         }
 434
 435         else
 436         {
 437                 /*   It is not a triangle, we have to triangulate it .
 438                         Since it is not adjacent to anything we can triangulate it
 439                         blindly
 440                 */
 441                 if (bucket == 0)
 442                 {
 443                           /*   It is the first polygon in the strip, therefore there is no
 444                          input edge to start with.
 445                     */
 446                     if ((e2 == 0) && (e3 ==0))
 447                        Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
 448                                                   TRUE,1,color1,color2,color3);
 449
 450                     else
 451                        Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
 452                                                   FALSE,1,color1,color2,color3);
 453
 454                              RemoveList(pListHead,(PLISTINFO) temp);
 455
 456                     /*      We will be at the beginning of the next strip. */
 457                     face->nPolSize = 1;
 458                     return (Finished(swaps,bands,global));
 459                 }
 460
 461
 462                 else
 463                 {
 464
 465
 466                /*  WHOLE triangulation */
 467                   /*  It is not a triangle and has adjacencies.
 468                                 This means that we have to:
 469                                 1. Triangulate this polygon, not blindly because
 470                                         we have an edge that we want to come out on, that
 471                                         is the edge that is adjacent to a polygon with the
 472                                         least number of adjacencies. Also we must come in
 473                                         on the last seen edge.
 474                                 2. Update the adjacencies in the list, because we are
 475                                         using this polygon .
 476                                 3. Get the next polygon.
 477                         */
 478                         /*      Return the face_id of the next polygon we will be using,
 479                                 while updating the adjacency list by decrementing the
 480                                 adjacencies of everything adjacent to the current polygon.
 481                         */
 482
 483                next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
 484
 485                /*  Maybe we deleted something in a patch and could not find an adj polygon */
 486                if (next_face_id == -1)
 487                {
 488
 489                     /*   If we are at the first polygon in the strip and there is no input
 490                          edge, then begin is TRUE
 491                     */
 492                     if ((e2 == 0) && (e3 == 0))
 493                          Blind_Triangulate(face->nPolSize,face->pPolygon,
 494                                                     bands,TRUE,1,color1,color2,color3);
 495
 496                     else
 497                          Blind_Triangulate(face->nPolSize,face->pPolygon,
 498                                                     bands,FALSE,1,color1,color2,color3);
 499
 500                           RemoveList(pListHead,(PLISTINFO) temp);
 501
 502                        /*      We will be at the beginning of the next strip. */
 503                     face->nPolSize = 1;
 504                     return (Finished(swaps,bands,global));
 505                }
 506
 507                if (Done(next_face_id,59,&next_bucket) == NULL)
 508                   {
 509                             printf("We deleted the next face 6 %d %d\n",next_face_id,face_id);
 510                             exit(0);
 511                      }
 512
 513                         Non_Blind_Triangulate(face->nPolSize,face->pPolygon,
 514                                                  bands,next_face_id,face_id,1,color1,color2,color3);
 515
 516                RemoveList(pListHead,(PLISTINFO) temp);
 517                face->nPolSize = 1;
 518                         pListHead = array[next_bucket];
 519                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 520                         if ( pfNode )
 521                                 pfNode->face_id = next_face_id;
 522                         lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 523                                            (int (*)(void *,void *)) (Compare)));
 524                         if (lpListInfo == NULL)
 525                      {
 526                                 printf("There is an error finding the next polygon2 %d %d\n",next_face_id,next_bucket);
 527                                 exit(0);
 528                         }
 529                         return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
 530                                                      pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
 531                 }
 532
 533         }
 534     Last_Edge(&e1,&e2,&e3,0);
 535
 536 }
 537
 538
 539 int Extend_Face(int face_id,int e1,int e2,int *swaps,FILE *bands,
 540                 int color1,int color2,int color3,int *vert_norm, int normals,
 541                 int *vert_texture, int texture)
 542 {
 543     int dummy=0,next_bucket;
 544     P_ADJACENCIES pfNode,lpListInfo;
 545     ListHead *pListHead;
 546
 547     /*    Try to extend backwards off of the local strip that we just found */
 548
 549     vn = vert_norm;
 550     vt = vert_texture;
 551     norm = normals;
 552     text = texture;
 553
 554     *swaps = 0;
 555     /*  Find the face that is adjacent to the edge and is not the
 556                 current face.
 557     */
 558     face_id = Find_Face(face_id, e1, e2,&next_bucket);
 559     if (face_id == -1)
 560           return 0;
 561
 562     pListHead = array[next_bucket];
 563     pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 564     if ( pfNode )
 565                 pfNode->face_id = face_id;
 566     lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 567                        (int (*)(void *,void *)) (Compare)));
 568     if (lpListInfo == NULL)
 569     {
 570                 printf("There is an error finding the next polygon3 %d\n",face_id);
 571                 exit(0);
 572     }
 573     Last_Edge(&dummy,&e1,&e2,1);
 574
 575     /*  Find a strip extending from the patch and return the cost */
 576     return (Polygon_Output(lpListInfo,face_id,next_bucket,pListHead,TRUE,swaps,bands,color1,color2,color3,TRUE,TRUE));
 577 }
 578
 579