Stripe_u/outputex.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: outputex.c
  11      This file contains routines that are used for various functions in
  12      the local algorithm.
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include "global.h"
  20 #include "outputex.h"
  21 #include "triangulatex.h"
  22 #include "polverts.h"
  23 #include "ties.h"
  24 #include "partial.h"
  25 #include "sturctsex.h"
  26 #include "options.h"
  27 #include "output.h"
  28 #include "common.h"
  29 #include "util.h"
  30
  31
  32 void Output_TriEx(int id1, int id2, int id3, FILE *output, int next_face, int flag,
  33                 int where)
  34 {
  35      /*   We will save everything into a list, rather than output at once,
  36           as was done in the old routine. This way for future modifications
  37           we can change the strips later on if we want to.
  38      */
  39
  40     int swap,temp1,temp2,temp3;
  41     static int total=0;
  42     static int tri=0;
  43     static int strips = 0;
  44     static int cost = 0;
  45
  46     if (flag == -20)
  47     {
  48          cost = cost + where+total+tri+strips+strips;
  49          printf("We will need to send %d vertices to the renderer\n",cost);
  50          total = 0;
  51          tri = 0;
  52          strips = 0;
  53          return ;
  54     }
  55
  56
  57     if (flag == -10)
  58          /*    We are finished, now is time to output the triangle list
  59          */
  60     {
  61           fprintf(output,"\nt ");
  62           tri = tri + Finished(&swap,output,FALSE);
  63           total = total + swap;
  64           strips++;
  65           /*printf("There are %d swaps %d tri %d strips\n",total,tri,strips);*/
  66     }
  67
  68     else
  69     {
  70          Last_Edge(&temp1,&temp2,&temp3,0);
  71          Add_Id_Strips(id1,where);
  72          Add_Id_Strips(id2,where);
  73          Add_Id_Strips(id3,where);
  74          Last_Edge(&id1,&id2,&id3,1);
  75     }
  76 }
  77
  78
  79
  80
  81 void Extend_BackwardsEx(int face_id, FILE *output, FILE *strip, int *ties,
  82                       int tie, int triangulate,
  83                       int swaps,int *next_id)
  84 {
  85     /*  We just made a strip, now we are going to see if we can extend
  86            backwards from the starting face, which had 2 or more adjacencies
  87            to start with.
  88     */
  89     int bucket,next_face,num,x,y,z,c,d=1,max,f;
  90     ListHead *pListFace;
  91     PF_FACES face;
  92     P_ADJACENCIES temp;
  93
  94     /*  Get the first triangle that we have saved the the strip data
  95            structure, so we can see if there are any polygons adjacent
  96            to this edge or a neighboring one
  97     */
  98     First_Edge(&x,&y,&z);
  99
 100     pListFace  = PolFaces[face_id];
 101     face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
 102
 103     num = face->nPolSize;
 104
 105     /*  Go through the edges to see if there is an adjacency
 106            with a vertex in common to the first triangle that was
 107            outputted in the strip. (maybe edge was deleted....)
 108     */
 109     for (c=0; c<num ; c++)
 110     {
 111
 112         if ( (c != (num-1)) &&
 113              (( (*(face->pPolygon+c) == x) && (*(face->pPolygon+c+1) == y)) ||
 114                 (*(face->pPolygon+c) == y) && (*(face->pPolygon+c+1) == x)))
 115         {
 116             /*  Input edge is still there see if there is an adjacency */
 117             next_face = Find_Face(face_id, x, y, &bucket);
 118             if (next_face == -1)
 119                 /*  Could not find a face adjacent to the edge */
 120                 break;
 121             pListFace = array[bucket];
 122             max = NumOnList(pListFace);
 123             for (f=0;;f++)
 124             {
 125                         temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);
 126                      if (temp->face_id == next_face)
 127                      {
 128                           Last_Edge(&z,&y,&x,1);
 129                           Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
 130                                                        output,strip,ties,tie,triangulate,swaps,next_id,0);
 131                           return;
 132                      }
 133
 134                         if (temp == NULL)
 135                         {
 136                                         printf("Error in the new buckets%d %d %d\n",bucket,max,0);
 137                                         exit(0);
 138                         }
 139             }
 140
 141         }
 142         else if ( (c == (num -1)) &&
 143            ( ((*(face->pPolygon) == x) && (*(face->pPolygon+num-1) == y)) ||
 144               (*(face->pPolygon) == y) && (*(face->pPolygon+num-1) == x)))
 145         {
 146              next_face = Find_Face(face_id,x,y,&bucket);
 147              if (next_face == -1)
 148                 /*  Could not find a face adjacent to the edge */
 149                      break;
 150                 pListFace = array[bucket];
 151                 max = NumOnList(pListFace);
 152                 for (f=0;;f++)
 153                 {
 154                         temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);
 155                      if (temp->face_id == next_face)
 156                      {
 157                           Last_Edge(&z,&y,&x,1);
 158                           Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
 159                                                     output,strip,ties,tie,triangulate,swaps,next_id,0);
 160                           return;
 161                      }
 162
 163                         if (temp == NULL)
 164                         {
 165                                         printf("Error in the new buckets%d %d %d\n",bucket,max,0);
 166                                         exit(0);
 167                         }
 168             }
 169         }
 170
 171     }
 172
 173 }
 174
 175 void Polygon_OutputEx(P_ADJACENCIES temp,int face_id,int bucket,
 176                                         ListHead *pListHead, FILE *output, FILE *strips,
 177                                         int *ties, int tie,
 178                                         int triangulate, int swaps,
 179                                         int *next_id, int where)
 180 {
 181         ListHead *pListFace;
 182         PF_FACES face;
 183         P_ADJACENCIES pfNode;
 184         static BOOL begin = TRUE;
 185         int old_face,next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
 186         P_ADJACENCIES lpListInfo;
 187
 188         /*      We have a polygon to output, the id is face id, and the number
 189                    of adjacent polygons to it is bucket.
 190         */
 191
 192      Last_Edge(&e1,&e2,&e3,0);
 193
 194      /*  Get the polygon with id face_id */
 195         pListFace  = PolFaces[face_id];
 196         face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
 197
 198      if (face->nPolSize == 3)
 199         {
 200                 /*      It is already a triangle */
 201                 if (bucket == 0)
 202                 {
 203                         /*      It is not adjacent to anything so we do not have to
 204                                    worry about the order of the sides or updating adjacencies
 205                         */
 206
 207                   Last_Edge(&e1,&e2,&e3,0);
 208                   next_face_id = Different(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),
 209                                               e1,e2,e3,&other1,&other2);
 210                   /*  No input edge, at the start */
 211                   if ((e2 ==0) && (e3 == 0))
 212                   {
 213                           e2 = other1;
 214                           e3 = other2;
 215                   }
 216
 217                         Output_TriEx(e2,e3,next_face_id,strips,-1,begin,where);
 218                         RemoveList(pListHead,(PLISTINFO) temp);
 219                         /*      We will be at the beginning of the next strip. */
 220                         begin = TRUE;
 221                 }
 222                 /*      It is a triangle with adjacencies. This means that we
 223                            have to:
 224                                 1. Update the adjacencies in the list, because we are
 225                                         using this polygon and it will be deleted.
 226                                 2. Get the next polygon.
 227                 */
 228                 else
 229                 {
 230                         /*   Return the face_id of the next polygon we will be using,
 231                                 while updating the adjacency list by decrementing the
 232                                 adjacencies of everything adjacent to the current triangle.
 233                         */
 234
 235                next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
 236                         old_face = next_face_id;
 237
 238               /*  Break the tie,  if there was one */
 239                     if (tie != FIRST)
 240                                 old_face = Get_Next_Face(tie,face_id,triangulate);
 241
 242               if (next_face_id == -1)
 243               {
 244                     Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
 245                             triangulate,swaps,next_id,where);
 246                     return;
 247               }
 248
 249
 250                 /*  We are using a different face */
 251                 if ((tie != FIRST) && (old_face != next_face_id) && (swaps == ON))
 252              {
 253                         next_face_id = old_face;
 254                         /*  Get the new output edge, since e1 and e2 are for the
 255                             original next face that we got.
 256                         */
 257                   e3 = Get_EdgeEx(&e1,&e2,face->pPolygon,next_face_id,face->nPolSize,0,0);
 258                 }
 259
 260                    /*      Find the other vertex to transmit in the triangle */
 261                    e3 = Return_Other(face->pPolygon,e1,e2);
 262                 Last_Edge(&other1,&other2,&other3,0);
 263
 264                 if ((other1 != 0) && (other2 != 0))
 265                 {
 266                        /*   See which vertex in the output edge is not in the input edge */
 267                        if ((e1 != other2) && (e1 != other3))
 268                                e3 = e1;
 269                        else if ((e2 != other2) && (e2 != other3))
 270                                e3 = e2;
 271                        /* can happen with > 2 polys on an edge  but won't form a good strip so stop
 272                        the strip here
 273                     */
 274                     else
 275                        {
 276                          Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
 277                                                    triangulate,swaps,next_id,where);
 278                          return;
 279                }
 280
 281                /*   See which vertex of the input edge is not in the output edge */
 282                if ((other2 != e1) && (other2 != e2))
 283                {
 284                           other1 = other2;
 285                           other2 = other3;
 286                }
 287                else if ((other3 != e1) && (other3 != e2))
 288                           other1 = other3;
 289                else
 290                {
 291                  /* Degenerate triangle just return*/
 292                Output_TriEx(other1,other2,e3,strips,next_face_id,begin,where);
 293                         RemoveList(pListHead,(PLISTINFO) temp);
 294                         begin = FALSE;
 295                return;
 296                }
 297
 298            }
 299
 300            /*   There was not an input edge, we are the first triangle in a strip */
 301            else
 302            {
 303                /*   Find the correct order to transmit the triangle, what is
 304                        the output edge that we want ?
 305                */
 306                other1 = e3;
 307                e3 = e2;
 308                other2 = e1;
 309            }
 310
 311            /*   At this point the adjacencies have been updated  and we
 312                    have the next polygon id
 313            */
 314         Output_TriEx(other1,other2,e3,strips,next_face_id,begin,where);
 315            RemoveList(pListHead,(PLISTINFO) temp);
 316            begin = FALSE;
 317
 318            if (Done(next_face_id,59,&next_bucket) == NULL)
 319                 return;
 320
 321         pListHead = array[next_bucket];
 322            pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 323            if ( pfNode )
 324                 pfNode->face_id = next_face_id;
 325            lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 326                                  (int (*)(void *,void *)) (Compare)));
 327            if (lpListInfo == NULL)
 328            {
 329                                 printf("There is an error finding the next polygon3 %d\n",next_face_id);
 330                                 exit(0);
 331            }
 332            Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
 333                                         pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
 334
 335         }
 336 }
 337
 338         else
 339         {
 340                 /*      It is not a triangle, we have to triangulate it .
 341                            Since it is not adjacent to anything we can triangulate it
 342                            blindly
 343                 */
 344                 if (bucket == 0)
 345                 {
 346                         /*  Check to see if there is not an input edge */
 347                   Last_Edge(&other1,&other2,&other3,0);
 348                   if ((other1 == 0) && (other2 ==0))
 349                           Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
 350                                                           output,TRUE,where);
 351                   else
 352                           Blind_TriangulateEx(face->nPolSize,face->pPolygon,strips,
 353                                                  output,FALSE,where);
 354
 355                         RemoveList(pListHead,(PLISTINFO) temp);
 356                         /*      We will be at the beginning of the next strip. */
 357                         begin = TRUE;
 358                 }
 359
 360                  /*  If we have specified PARTIAL triangulation then
 361                         we will go to special routines that will break the
 362                         polygon and update the data structure. Else everything
 363                         below will simply triangulate the whole polygon
 364                 */
 365                 else if (triangulate == PARTIAL)
 366                 {
 367
 368                   /*  Return the face_id of the next polygon we will be using,
 369                         */
 370                         next_face_id = Min_Face_AdjEx(face_id,&next_bucket,ties);
 371
 372
 373                         /* Don't do it partially, because we can go inside and get
 374                         less adjacencies, for a quad we can do the whole thing.
 375                   */
 376                   if ((face_id == next_face_id) && (face->nPolSize == 4)  && (swaps == ON))
 377                   {
 378                     next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
 379                           if (next_face_id == -1)
 380                           {
 381                                /*  There is no sequential face to go to, end the strip */
 382                                Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
 383                                                          triangulate,swaps,next_id,where);
 384                                return;
 385                           }
 386
 387                     /* Break the tie,  if there was one */
 388                           if (tie != FIRST)
 389                                   next_face_id = Get_Next_Face(tie,face_id,triangulate);
 390                           Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
 391                                                               output,next_face_id,face_id,where);
 392                              RemoveList(pListHead,(PLISTINFO) temp);
 393                   }
 394
 395                   /*   Was not a quad but we still do not want to do it partially for
 396                           now, since we want to only do one triangle at a time
 397                   */
 398                   else if ((face_id == next_face_id) && (swaps == ON))
 399                        Inside_Polygon(face->nPolSize,face->pPolygon,strips,output,
 400                                          next_face_id,face_id,next_id,pListHead,temp,where);
 401
 402                   else
 403                   {
 404                                          if ((tie != FIRST) && (swaps == ON))
 405                                                  next_face_id = Get_Next_Face(tie,face_id,triangulate);
 406                                          Partial_Triangulate(face->nPolSize,face->pPolygon,strips,
 407                                                                 output,next_face_id,face_id,next_id,pListHead,temp,where);
 408                                         /*    Check the next bucket again ,maybe it changed
 409                                                  We calculated one less, but that might not be the case
 410                                         */
 411                }
 412
 413                         if (Done(next_face_id,59,&next_bucket) == NULL)
 414                         {
 415                         /*  Check to see if there is not an input edge */
 416                        Last_Edge(&other1,&other2,&other3,0);
 417                        if ((other1 == 0) && (other2 ==0))
 418                                Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
 419                                                                output,TRUE,where);
 420                        else
 421                                Blind_TriangulateEx(face->nPolSize,face->pPolygon,strips,
 422                                                       output,FALSE,where);
 423
 424                     if (Done(face_id,59,&bucket) != NULL)
 425                     {
 426                          pListHead = array[bucket];
 427                                   pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 428                                   if ( pfNode )
 429                                           pfNode->face_id = face_id;
 430                                   lpListInfo = (P_ADJACENCIES) (SearchList(array[bucket], pfNode,
 431                                                   (int (*)(void *,void *)) (Compare)));
 432                                   RemoveList(pListHead,(PLISTINFO)lpListInfo);
 433                     }
 434                     begin = TRUE;
 435                                 return;
 436                         }
 437
 438                         begin = FALSE;
 439                         pListHead = array[next_bucket];
 440                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 441                         if ( pfNode )
 442                                 pfNode->face_id = next_face_id;
 443                         lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 444                                         (int (*)(void *,void *)) (Compare)));
 445                         if (lpListInfo == NULL)
 446                         {
 447                                 printf("There is an error finding the next polygon1 %d %d\n",next_face_id,next_bucket);
 448                                 exit(0);
 449                         }
 450                         Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
 451                                             pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
 452                 }
 453
 454
 455                 else
 456                 {
 457                         /*  WHOLE triangulation */
 458                   /*  It is not a triangle and has adjacencies.
 459                                 This means that we have to:
 460                                 1. TriangulateEx this polygon, not blindly because
 461                                         we have an edge that we want to come out on, that
 462                                         is the edge that is adjacent to a polygon with the
 463                                         least number of adjacencies. Also we must come in
 464                                         on the last seen edge.
 465                                 2. Update the adjacencies in the list, because we are
 466                                         using this polygon .
 467                                 3. Get the next polygon.
 468                         */
 469                         /*   Return the face_id of the next polygon we will be using,
 470                                 while updating the adjacency list by decrementing the
 471                                 adjacencies of everything adjacent to the current polygon.
 472                         */
 473
 474                next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
 475
 476                if (Done(next_face_id,59,&next_bucket) == NULL)
 477                {
 478                     Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
 479                                               triangulate,swaps,next_id,where);
 480                     /*    Because maybe there was more than 2 polygons on the edge */
 481                     return;
 482                      }
 483
 484                      /*      Break the tie,  if there was one */
 485                         else if (tie != FIRST)
 486                                 next_face_id = Get_Next_Face(tie,face_id,triangulate);
 487
 488                         Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
 489                                                          output,next_face_id,face_id,where);
 490                         RemoveList(pListHead,(PLISTINFO) temp);
 491                         begin = FALSE;
 492                         pListHead = array[next_bucket];
 493                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 494                         if ( pfNode )
 495                                 pfNode->face_id = next_face_id;
 496                         lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 497                                            (int (*)(void *,void *)) (Compare)));
 498                         if (lpListInfo == NULL)
 499                      {
 500                                         printf("There is an error finding the next polygon2 %d %d\n",next_face_id,next_bucket);
 501                                         exit(0);
 502                }
 503                         Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
 504                                                pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
 505                 }
 506
 507         }
 508     Last_Edge(&e1,&e2,&e3,0);
 509
 510 }
 511
 512
 513
 514
 515
 516
 517
 518