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