Stripe_u/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      register int start_swap = 0;
  43      int num,x,vertex1,vertex2;
  44      ListHead *pListHead;
  45      int id[2],other1,other2,index = 0,a,b,c;
  46      P_STRIPS temp1,temp2,temp3,temp4,temp5,temp6;
  47      BOOL cptexture;
  48      *swap =0;
  49
  50      cptexture = text;
  51      pListHead = strips[0];
  52      if (pListHead == NULL)
  53          return 0;
  54
  55      num = NumOnList(pListHead);
  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,other1+1,vn[other1]+1,
 130                                                   other2+1,vn[other2]+1);
 131       else if ((cptexture) && (!norm))
 132            fprintf(output,"%d/%d %d/%d %d/%d ",vertex1+1,vt[vertex1]+1,other1+1,vt[other1]+1,
 133                                                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,
 137                                                         other2+1,vt[other2]+1,vn[other2]+1);
 138       else
 139            fprintf(output,"%d %d %d ",vertex1+1,other1+1,other2+1);
 140
 141
 142          for (x = 6; x < num ; x = x+3)
 143           {
 144
 145               /*    Get the next triangle */
 146               temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x);
 147               temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+1);
 148               temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+2);
 149
 150            /*    Error checking */
 151               if (!(member(id[0],a,b,c)) || !(member(id[1],a,b,c)) || !(member(vertex2,a,b,c)))
 152               {
 153                      /*   If we used partial we might have a break in the middle of a strip */
 154                      fprintf(output,"\nt ");
 155                   /*   Find the vertex in the first triangle that is not in the second */
 156                   vertex1 = Different(a,b,c,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&other2);
 157                   /*    Find the vertex in the second triangle that is not in the first */
 158                   vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
 159
 160                   id[index] = vertex1; index = !index;
 161                   id[index] = other1; index = !index;
 162                   id[index] = other2; index = !index;
 163               }
 164
 165               if ((temp1 == NULL ) || (temp2 == NULL) || (temp3 == NULL))
 166               {
 167                   printf("There is an error in the triangle list \n");
 168                   exit(0);
 169               }
 170
 171            if ((id[0] == id[1]) || (id[0] == vertex2))
 172                 continue;
 173
 174            if ((member(id[index],temp1->face_id,temp2->face_id,temp3->face_id)))
 175            {
 176                 if ((text) && ( vt[id[index]]==0))
 177                      cptexture = FALSE;
 178                 if ((!norm) && (!cptexture))
 179                      fprintf(output,"%d ",id[index]+1);
 180                 else if ((norm) && (!cptexture))
 181                      fprintf(output,"%d//%d ",id[index]+1,vn[id[index]]+1);
 182                 else if ((!norm) && (cptexture))
 183                      fprintf(output,"%d/%d ",id[index]+1,vt[id[index]]+1);
 184                 else
 185                      fprintf(output,"%d/%d/%d ",id[index]+1,vt[id[index]]+1,vn[id[index]]+1);
 186                 index = !index;
 187                 *swap = *swap + 1;
 188            }
 189
 190            if ((text) && ( vt[vertex2]==0))
 191                 cptexture = FALSE;
 192               if ((!norm) && (!cptexture))
 193                 fprintf(output,"\nq %d ",vertex2+1);
 194            else if ((norm) && (!cptexture))
 195                 fprintf(output,"\nq %d//%d ",vertex2+1,vn[vertex2]+1);
 196            else if ((!norm) && (cptexture))
 197                 fprintf(output,"\nq %d/%d ",vertex2+1,vt[vertex2]+1);
 198            else
 199                 fprintf(output,"\nq %d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
 200
 201               id[index] = vertex2; index = !index;
 202
 203               /*    Get the next vertex not in common */
 204               vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
 205               a = temp1->face_id;
 206               b = temp2->face_id;
 207               c = temp3->face_id;
 208           }
 209           /*    Do the last vertex */
 210        if ((text) && (vt[vertex2]==0))
 211        {
 212             if (cptexture)
 213                  fprintf(output,"\nq ");
 214             cptexture = FALSE;
 215        }
 216        if ((!norm) && (!cptexture))
 217             fprintf(output,"%d ",vertex2+1);
 218        else if ((norm) && (!cptexture))
 219             fprintf(output,"%d//%d ",vertex2+1,vn[vertex2]+1);
 220        else if ((!norm) && (cptexture))
 221             fprintf(output,"%d/%d ",vertex2+1,vt[vertex2]+1);
 222        else
 223             fprintf(output,"%d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
 224
 225
 226          Free_Strips();
 227       return (num/3);
 228 }
 229
 230 void Output_Tri(int id1, int id2, int id3,FILE *bands, int color1, int color2, int color3,BOOL end)
 231 {
 232      /*   We will save everything into a list, rather than output at once,
 233              as was done in the old routine. This way for future modifications
 234              we can change the strips later on if we want to.
 235      */
 236
 237     int temp1,temp2,temp3;
 238
 239     /*  Make sure we do not have an error */
 240     /*    There are degeneracies in some of the files */
 241         if ( (id1 == id2) || (id1 == id3) || (id2 == id3))
 242         {
 243                 printf("Degenerate triangle %d %d %d\n",id1,id2,id3);
 244                 exit(0);
 245         }
 246      else
 247      {
 248           Last_Edge(&temp1,&temp2,&temp3,0);
 249              Add_Id_Strips(id1,end);
 250              Add_Id_Strips(id2,end);
 251              Add_Id_Strips(id3,end);
 252              Last_Edge(&id1,&id2,&id3,1);
 253      }
 254 }
 255
 256
 257 int Polygon_Output(P_ADJACENCIES temp,int face_id,int bucket,
 258                                         ListHead *pListHead, BOOL first, int *swaps,
 259                          FILE *bands,int color1,int color2,int color3,BOOL global, BOOL end)
 260 {
 261         ListHead *pListFace;
 262         PF_FACES face;
 263         P_ADJACENCIES pfNode;
 264         static BOOL begin = TRUE;
 265         int old_face,next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
 266         P_ADJACENCIES lpListInfo;
 267      int ties=0;
 268      int  tie = SEQUENTIAL;
 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                old_face = next_face_id;
 349                      /*      Find the other vertex to transmit in the triangle */
 350                      e3 = Return_Other(face->pPolygon,e1,e2);
 351                   Last_Edge(&other1,&other2,&other3,0);
 352
 353                   if ((other2 != 0) && (other3 != 0))
 354                   {
 355                       /*   See which vertex in the output edge is not in the input edge */
 356                       if ((e1 != other2) && (e1 != other3))
 357                             e3 = e1;
 358                       else if ((e2 != other2) && (e2 != other3))
 359                              e3 = e2;
 360                       else
 361                       {
 362                             printf("There is an error in the tri with adj\n");
 363                             exit(0);
 364                       }
 365
 366                       /*   See which vertex of the input edge is not in the output edge */
 367                       if ((other2 != e1) && (other2 != e2))
 368                       {
 369                             other1 = other2;
 370                             other2 = other3;
 371                       }
 372                       else if ((other3 != e1) && (other3 != e2))
 373                             other1 = other3;
 374                       else
 375                       {
 376                             printf("There is an error in getting the tri with adj\n");
 377                             exit(0);
 378                       }
 379
 380                   }
 381                else
 382                {
 383                   /*     We are the first triangle in the strip and the starting edge
 384                          has not been set yet
 385                   */
 386                   /*  Maybe we deleted something in a patch and could not find an adj polygon */
 387                   if (next_face_id == -1)
 388                   {
 389                        Output_Tri(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),bands,color1,
 390                                   color2,color3,end);
 391                        face->nPolSize = 1;
 392                        RemoveList(pListHead,(PLISTINFO) temp);
 393                        return (Finished(swaps,bands,global));
 394                   }
 395
 396                   other1 = e3;
 397                   e3 = e2;
 398                   other2 = e1;
 399                }
 400
 401                   /*   At this point the adjacencies have been updated  and we
 402                                 have the next polygon id
 403                   */
 404
 405                Output_Tri(other1,other2,e3,bands,color1,color2,color3,end);
 406                face->nPolSize = 1;
 407                      RemoveList(pListHead,(PLISTINFO) temp);
 408                      begin = FALSE;
 409
 410                /*  Maybe we deleted something in a patch and could not find an adj polygon */
 411                if (next_face_id == -1)
 412                     return (Finished(swaps,bands,global));
 413
 414                if (Done(next_face_id,59,&next_bucket) == NULL)
 415                      {
 416                              printf("We deleted the next face 4%d\n",next_face_id);
 417                              exit(0);
 418                   }
 419
 420                         pListHead = array[next_bucket];
 421                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 422                         if ( pfNode )
 423                                 pfNode->face_id = next_face_id;
 424                         lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 425                                 (int (*)(void *,void *)) (Compare)));
 426                         if (lpListInfo == NULL)
 427                         {
 428                                 printf("There is an error finding the next polygon3 %d\n",next_face_id);
 429                                 exit(0);
 430                         }
 431                         return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
 432                                                      pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
 433
 434                 }
 435         }
 436
 437         else
 438         {
 439                 /*   It is not a triangle, we have to triangulate it .
 440                         Since it is not adjacent to anything we can triangulate it
 441                         blindly
 442                 */
 443                 if (bucket == 0)
 444                 {
 445                           /*   It is the first polygon in the strip, therefore there is no
 446                          input edge to start with.
 447                     */
 448                     if ((e2 == 0) && (e3 ==0))
 449                        Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
 450                                                   TRUE,1,color1,color2,color3);
 451
 452                     else
 453                        Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
 454                                                   FALSE,1,color1,color2,color3);
 455
 456                              RemoveList(pListHead,(PLISTINFO) temp);
 457
 458                     /*      We will be at the beginning of the next strip. */
 459                     face->nPolSize = 1;
 460                     return (Finished(swaps,bands,global));
 461                 }
 462
 463
 464                 else
 465                 {
 466
 467
 468                /*  WHOLE triangulation */
 469                   /*  It is not a triangle and has adjacencies.
 470                                 This means that we have to:
 471                                 1. Triangulate this polygon, not blindly because
 472                                         we have an edge that we want to come out on, that
 473                                         is the edge that is adjacent to a polygon with the
 474                                         least number of adjacencies. Also we must come in
 475                                         on the last seen edge.
 476                                 2. Update the adjacencies in the list, because we are
 477                                         using this polygon .
 478                                 3. Get the next polygon.
 479                         */
 480                         /*      Return the face_id of the next polygon we will be using,
 481                                 while updating the adjacency list by decrementing the
 482                                 adjacencies of everything adjacent to the current polygon.
 483                         */
 484
 485                next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
 486
 487                /*  Maybe we deleted something in a patch and could not find an adj polygon */
 488                if (next_face_id == -1)
 489                {
 490
 491                     /*   If we are at the first polygon in the strip and there is no input
 492                          edge, then begin is TRUE
 493                     */
 494                     if ((e2 == 0) && (e3 == 0))
 495                          Blind_Triangulate(face->nPolSize,face->pPolygon,
 496                                                     bands,TRUE,1,color1,color2,color3);
 497
 498                     else
 499                          Blind_Triangulate(face->nPolSize,face->pPolygon,
 500                                                     bands,FALSE,1,color1,color2,color3);
 501
 502                           RemoveList(pListHead,(PLISTINFO) temp);
 503
 504                        /*      We will be at the beginning of the next strip. */
 505                     face->nPolSize = 1;
 506                     return (Finished(swaps,bands,global));
 507                }
 508
 509                if (Done(next_face_id,59,&next_bucket) == NULL)
 510                   {
 511                             printf("We deleted the next face 6 %d %d\n",next_face_id,face_id);
 512                             exit(0);
 513                      }
 514
 515                         Non_Blind_Triangulate(face->nPolSize,face->pPolygon,
 516                                                  bands,next_face_id,face_id,1,color1,color2,color3);
 517
 518                RemoveList(pListHead,(PLISTINFO) temp);
 519                begin = FALSE;
 520                face->nPolSize = 1;
 521                         pListHead = array[next_bucket];
 522                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 523                         if ( pfNode )
 524                                 pfNode->face_id = next_face_id;
 525                         lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 526                                            (int (*)(void *,void *)) (Compare)));
 527                         if (lpListInfo == NULL)
 528                      {
 529                                 printf("There is an error finding the next polygon2 %d %d\n",next_face_id,next_bucket);
 530                                 exit(0);
 531                         }
 532                         return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
 533                                                      pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
 534                 }
 535
 536         }
 537     Last_Edge(&e1,&e2,&e3,0);
 538
 539 }
 540
 541
 542 int Extend_Face(int face_id,int e1,int e2,int *swaps,FILE *bands,
 543                 int color1,int color2,int color3,int *vert_norm, int normals,
 544                 int *vert_texture, int texture)
 545 {
 546     int dummy=0,next_bucket;
 547     P_ADJACENCIES pfNode,lpListInfo;
 548     ListHead *pListHead;
 549
 550     /*    Try to extend backwards off of the local strip that we just found */
 551
 552     vn = vert_norm;
 553     vt = vert_texture;
 554     norm = normals;
 555     text = texture;
 556
 557     *swaps = 0;
 558     /*  Find the face that is adjacent to the edge and is not the
 559                 current face.
 560     */
 561     face_id = Find_Face(face_id, e1, e2,&next_bucket);
 562     if (face_id == -1)
 563           return 0;
 564
 565     pListHead = array[next_bucket];
 566     pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 567     if ( pfNode )
 568                 pfNode->face_id = face_id;
 569     lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 570                        (int (*)(void *,void *)) (Compare)));
 571     if (lpListInfo == NULL)
 572     {
 573                 printf("There is an error finding the next polygon3 %d\n",face_id);
 574                 exit(0);
 575     }
 576     Last_Edge(&dummy,&e1,&e2,1);
 577
 578     /*  Find a strip extending from the patch and return the cost */
 579     return (Polygon_Output(lpListInfo,face_id,next_bucket,pListHead,TRUE,swaps,bands,color1,color2,color3,TRUE,TRUE));
 580 }
 581
 582