Stripe_w/newpolve.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: newpolve.c
  11      This routine contains the bulk of the code that will find the
  12      patches of quads in the data model
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16 #include <stdlib.h>
  17 #include "polverts.h"
  18 #include "extend.h"
  19 #include "output.h"
  20 #include "triangulate.h"
  21 #include "common.h"
  22 #include "util.h"
  23 #include "global.h"
  24 #include "init.h"
  25 #include "add.h"
  26
  27 ListHead **PolVerts;
  28 ListHead **PolFaces;
  29 ListHead **PolEdges;
  30 int length;
  31 BOOL resetting = FALSE;
  32 int     ids[STRIP_MAX];
  33 int     added_quad = 0;
  34 BOOL reversed = FALSE;
  35 int patch = 0;
  36 extern int *vn;
  37 extern int *vt;
  38
  39 int Calculate_Walks(int lastvert,int y, PF_FACES temp2)
  40 {
  41         /* Find the length of the walk */
  42
  43         int previous_edge1, previous_edge2;
  44         register int nextvert,numverts,counter,walk=0;
  45         BOOL flag;
  46         F_EDGES *node;
  47      ListHead *pListHead;
  48      static int seen = 0;
  49
  50         /* Find the edge that we are currently on */
  51         if (y != 3)
  52         {
  53                 previous_edge1 = *(temp2->pPolygon +y);
  54                 previous_edge2 = *(temp2->pPolygon + y + 1);
  55         }
  56         else
  57         {
  58                 previous_edge1 = *(temp2->pPolygon +y);
  59                 previous_edge2 = *(temp2->pPolygon);
  60         }
  61
  62         temp2->seen = seen;
  63      counter = y;
  64
  65      /*Find the adjacent face to this edge */
  66         node = *(temp2->VertandId+y);
  67         if (node->edge[2] != lastvert)
  68         nextvert = node->edge[2];
  69      else
  70         nextvert = node->edge[1];
  71
  72         /* Keep walking in this direction until we cannot do so */
  73         while ((nextvert != lastvert) && (nextvert != -1))
  74         {
  75                 walk++;
  76                 pListHead = PolFaces[nextvert];
  77                 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
  78                 numverts = temp2->nPolSize;
  79                 if ((numverts != 4) || (temp2->seen == seen))
  80                 {
  81                         walk--;
  82                         nextvert = -1;
  83                 }
  84                 else
  85                 {
  86                         temp2->seen = seen;
  87                /* Find edge that is not adjacent to the previous one */
  88                         counter = 0;
  89                         flag = TRUE;
  90                         while ((counter < 3) && (flag))
  91                         {
  92                                 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
  93                                         (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
  94                                         ((*(temp2->pPolygon+counter) == previous_edge2) ||
  95                                         (*(temp2->pPolygon+counter+1) == previous_edge1)) )
  96                                         counter++;
  97                                 else
  98                                         flag = FALSE;
  99                         }
 100                 /* Get the IDs of the next edge */
 101                      if (counter < 3)
 102                      {
 103                              previous_edge1 = *(temp2->pPolygon + counter);
 104                              previous_edge2 = *(temp2->pPolygon + counter + 1);
 105                      }
 106                      else
 107                      {
 108                     previous_edge1 = *(temp2->pPolygon + counter);
 109                     previous_edge2 = *(temp2->pPolygon);
 110                      }
 111
 112                      node = *(temp2->VertandId + counter);
 113                      if (node->edge[1] == nextvert)
 114                              nextvert = node->edge[2];
 115                      else
 116                              nextvert = node->edge[1];
 117                 }
 118         }
 119      seen++;
 120         return walk;
 121 }
 122
 123
 124 BOOL Check_Right(int last_seen,PF_FACES temp2,int y,int face_id)
 125 {
 126         /* Check when we last saw the face to the right of the current
 127            one. We want to have seen it just before we started this strip
 128         */
 129
 130         F_EDGES *node;
 131         ListHead *pListHead;
 132         register int nextvert,oldy;
 133         PF_FACES t;
 134
 135      oldy = y;
 136         if (y != 3)
 137                 y = y+1;
 138         else
 139                 y = 0;
 140         node = *(temp2->VertandId + y);
 141         if (face_id == node->edge[1])
 142                 nextvert = node->edge[2];
 143         else
 144                 nextvert = node->edge[1];
 145
 146      if (nextvert == -1)
 147           return FALSE;
 148
 149      pListHead = PolFaces[nextvert];
 150         t = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 151         if (t->seen != (last_seen - 1))
 152         {
 153                  /* maybe because of the numbering, we are not
 154                     on the right orientation, so we have to check the
 155                     opposite one to be sure
 156            */
 157                 if (oldy != 0)
 158                         y = oldy-1;
 159                 else
 160                         y = 3;
 161                 node = *(temp2->VertandId + y);
 162                 if (face_id == node->edge[1])
 163                         nextvert = node->edge[2];
 164                 else
 165                         nextvert = node->edge[1];
 166                 if (nextvert == -1)
 167                return FALSE;
 168           pListHead = PolFaces[nextvert];
 169                 t = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 170                 if (t->seen != (last_seen - 1))
 171                         return FALSE;
 172         }
 173         return TRUE;
 174 }
 175
 176
 177 int Update_and_Test(PF_FACES temp2,int y,BOOL first,int distance,int lastvert, int val)
 178 {
 179
 180         static int last_seen = 17;
 181         int previous_edge1, previous_edge2;
 182         register int original_distance,nextvert,numverts,counter;
 183         BOOL flag;
 184         F_EDGES *node;
 185         ListHead *pListHead;
 186
 187         original_distance = distance;
 188         /* Find the edge that we are currently on */
 189         if (y != 3)
 190         {
 191                 previous_edge1 = *(temp2->pPolygon +y);
 192                 previous_edge2 = *(temp2->pPolygon + y + 1);
 193         }
 194         else
 195         {
 196                 previous_edge1 = *(temp2->pPolygon +y);
 197                 previous_edge2 = *(temp2->pPolygon);
 198         }
 199
 200         temp2->seen = val;
 201         temp2->seen2 = val;
 202
 203         node = *(temp2->VertandId+y);
 204         if (lastvert != node->edge[2])
 205                         nextvert = node->edge[2];
 206            else
 207                         nextvert = node->edge[1];
 208
 209         /* Keep walking in this direction until we cannot do so  or
 210                 we go to distance */
 211         while ((distance > 0)  && (nextvert != lastvert) && (nextvert != -1))
 212         {
 213                 distance--;
 214
 215                 pListHead = PolFaces[nextvert];
 216                 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 217                 temp2->seen = val;
 218
 219                 if (temp2->seen2 == val)
 220                 {
 221                      last_seen++;
 222                      return (original_distance - distance);
 223                 }
 224
 225                 temp2->seen2 = val;
 226
 227                 numverts = temp2->nPolSize;
 228
 229                  if (numverts != 4)
 230                      nextvert = -1;
 231
 232                 else if ((!first) && (!(Check_Right(last_seen,temp2,y,nextvert))))
 233                 {
 234                     last_seen++;
 235                     return (original_distance - distance);
 236                 }
 237                       else
 238                 {
 239                         /* Find edge that is not adjacent to the previous one */
 240                         counter = 0;
 241                         flag = TRUE;
 242                         while ((counter < 3) && (flag))
 243                         {
 244                                 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
 245                                         (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
 246                                         ((*(temp2->pPolygon+counter) == previous_edge2) ||
 247                                         (*(temp2->pPolygon+counter+1) == previous_edge1)) )
 248                                         counter++;
 249                                 else
 250                                         flag = FALSE;
 251                         }
 252                         /* Get the IDs of the next edge */
 253                         if (counter < 3)
 254                         {
 255                               previous_edge1 = *(temp2->pPolygon + counter);
 256                               previous_edge2 = *(temp2->pPolygon + counter + 1);
 257                         }
 258                         else
 259                         {
 260                               previous_edge1 = *(temp2->pPolygon + counter);
 261                               previous_edge2 = *(temp2->pPolygon);
 262                         }
 263                         if      ( ((*(temp2->walked+counter) == -1) &&
 264                                 (*(temp2->walked+counter+2) == -1)))
 265                         {
 266                                 printf("There is an error in the walks!\n");
 267                                 printf("1Code %d %d \n",*(temp2->walked+counter),*(temp2->walked+counter+2));
 268                                 exit(0);
 269                         }
 270                         else
 271                         {
 272                                 if      ((*(temp2->walked+counter) == -1) &&
 273                                         (*(temp2->walked+counter-2) ==  -1))
 274                                 {
 275                                         printf("There is an error in the walks!\n");
 276                                         printf("2Code %d %d \n",*(temp2->walked+counter),*(temp2->walked+counter-2));
 277                                         exit(0);
 278                                 }
 279                         }
 280                         node = *(temp2->VertandId + counter);
 281                         y = counter;
 282                               if (node->edge[1] == nextvert)
 283                               nextvert = node->edge[2];
 284                         else
 285                               nextvert = node->edge[1];
 286              }
 287     }
 288
 289     last_seen++;
 290
 291     if  (distance != 0)
 292     {
 293                 if (((nextvert == -1) || (nextvert == lastvert)) && (distance != 1))
 294                         return (original_distance - distance);
 295     }
 296     return original_distance;
 297 }
 298
 299
 300 int Test_Adj(PF_FACES temp2,int x,int north,int distance,int lastvert, int value)
 301 {
 302         /* if first time, then just update the last seen field */
 303         if (x==1)
 304                 return(Update_and_Test(temp2,north,TRUE,distance,lastvert,value));
 305         /* else we have to check if we are adjacent to the last strip */
 306         else
 307                 return(Update_and_Test(temp2,north,FALSE,distance,lastvert,value));
 308 }
 309
 310 void Get_Band_Walk(PF_FACES temp2,int face_id,int *dir1,int *dir2,
 311                                         int orientation,int cutoff_length)
 312 {
 313         int previous_edge1, previous_edge2;
 314         F_EDGES *node;
 315         ListHead *pListHead;
 316         register int walk = 0, nextvert,numverts,counter;
 317         BOOL flag;
 318
 319         /*      Get the largest band that will include this face, starting
 320                 from orientation. Save the values of the largest band
 321                 (either north and south together, or east and west together)
 322                 in the direction variables.
 323         */
 324         /* Find the edge that we are currently on */
 325      if (orientation != 3)
 326      {
 327                 previous_edge1 = *(temp2->pPolygon + orientation);
 328                 previous_edge2 = *(temp2->pPolygon + orientation + 1);
 329      }
 330      else
 331      {
 332                 previous_edge1 = *(temp2->pPolygon + orientation );
 333                 previous_edge2 = *(temp2->pPolygon);
 334      }
 335
 336      if (orientation == 0)
 337      {
 338                          if (*dir1 > *(temp2->walked + 1))
 339                                 *dir1 = *(temp2->walked + 1);
 340                          if (*dir2 > *(temp2->walked + 3))
 341                                 *dir2 = *(temp2->walked + 3);
 342         }
 343         else if (orientation == 3)
 344         {
 345                         if (*dir1 > *(temp2->walked + orientation - 3))
 346                              *dir1 = *(temp2->walked + orientation - 3) ;
 347                         if (*dir2 > *(temp2->walked + orientation -1 ))
 348                                 *dir2 = *(temp2->walked + orientation - 1);
 349         }
 350         else
 351         {
 352                         if (*dir1 > *(temp2->walked + orientation - 1))
 353                                 *dir1 = *(temp2->walked + orientation -1) ;
 354                         if (*dir2 > *(temp2->walked+ orientation + 1))
 355                                 *dir2 = *(temp2->walked + orientation + 1);
 356         }
 357
 358      /* if we know already that we can't extend the
 359                 band from this face, we do not need to do the walk
 360      */
 361      if ((*dir1 != 0) && (*dir2 != 0))
 362      {
 363                 /* Find the adjacent face to this edge */
 364                 node = *(temp2->VertandId+orientation);
 365                 if (face_id == node->edge[1])
 366                         nextvert = node->edge[2];
 367                 else
 368                         nextvert = node->edge[1];
 369         }
 370      else
 371                 nextvert = -1; /* leave w/o walking */
 372
 373         /* Keep walking in this direction until we cannot do so */
 374      while ((nextvert != face_id) && (nextvert != -1))
 375      {
 376             walk++;
 377             pListHead = PolFaces[nextvert];
 378             temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 379             numverts = temp2->nPolSize;
 380             if ((numverts != 4) || (walk > cutoff_length))
 381                    nextvert = -1;
 382             else
 383             {
 384                           /* Find edge that is not adjacent to the previous one */
 385                  counter = 0;
 386                  flag = TRUE;
 387                  while ((counter < 3) && (flag))
 388                  {
 389                            if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
 390                                 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
 391                                 ((*(temp2->pPolygon+counter) == previous_edge2) ||
 392                                 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
 393                                      counter++;
 394                            else
 395                                 flag = FALSE;
 396                  }
 397                  /* Get the IDs of the next edge */
 398                  if (counter < 3)
 399                  {
 400                         previous_edge1 = *(temp2->pPolygon + counter);
 401                         previous_edge2 = *(temp2->pPolygon + counter + 1);
 402                  }
 403                  else
 404                  {
 405                         previous_edge1 = *(temp2->pPolygon + counter);
 406                         previous_edge2 = *(temp2->pPolygon);
 407                  }
 408
 409                           /*    find out how far we can extend in the 2 directions
 410                                         along this new face in the walk
 411                           */
 412                           if (counter == 0)
 413                           {
 414                                         if (*dir1 > *(temp2->walked + 1))
 415                                                 *dir1 = *(temp2->walked + 1);
 416                                         if (*dir2 > *(temp2->walked + 3))
 417                                                 *dir2 = *(temp2->walked + 3);
 418                           }
 419                           else if (counter == 3)
 420                           {
 421                                         if (*dir1 > *(temp2->walked + counter - 3))
 422                                                 *dir1 = *(temp2->walked + counter - 3) ;
 423                                         if (*dir2 > *(temp2->walked + counter -1 ))
 424                                                 *dir2 = *(temp2->walked + counter -1);
 425                           }
 426                           else
 427                           {
 428                                         if (*dir1 > *(temp2->walked + counter - 1))
 429                                                 *dir1 = *(temp2->walked + counter -1) ;
 430                                         if (*dir2 > *(temp2->walked + counter + 1))
 431                                                 *dir2 = *(temp2->walked + counter + 1);
 432                           }
 433
 434                       /*        if we know already that we can't extend the
 435                         band from this face, we do not need to do the walk
 436                       */
 437                          if ((*dir1 == 0) || (*dir2 == 0))
 438                         nextvert = -1;
 439                 if (nextvert != -1)
 440                 {
 441                         node = *(temp2->VertandId + counter);
 442                         if (node->edge[1] == nextvert)
 443                         nextvert = node->edge[2];
 444                         else
 445                         nextvert = node->edge[1];
 446                 }
 447
 448            }
 449         }
 450 }
 451
 452
 453
 454
 455 int Find_Max(PF_FACES temp2,int lastvert,int north,int left,
 456                         int *lastminup,int *lastminleft)
 457 {
 458         int temp,walk,counter,minup,x,band_value;
 459         int previous_edge1, previous_edge2;
 460         F_EDGES *node;
 461         ListHead *pListHead;
 462         BOOL flag;
 463         static int last_seen = 0;
 464         register int smallest_so_far,nextvert,max=-1;
 465
 466      *lastminup = MAX_BAND;
 467         *lastminleft = 1;
 468
 469      if (left == 3)
 470         {
 471           previous_edge1 = *(temp2->pPolygon + left);
 472           previous_edge2 = *(temp2->pPolygon);
 473         }
 474
 475         else
 476         {
 477           previous_edge1 = *(temp2->pPolygon + left + 1);
 478           previous_edge2 = *(temp2->pPolygon + left);
 479         }
 480
 481         temp2->seen = last_seen;
 482      walk = *(temp2->walked + left);
 483
 484      for (x=1;x<=(walk+1); x++)
 485         {
 486                 /*   test to see if we have a true band
 487                      that is, are they adjacent to each other
 488                 */
 489
 490          minup = *(temp2->walked + north) + 1;
 491
 492             /*  if we are at the very first face, then we do not
 493                      have to check the adjacent faces going up
 494                      and our north distance is the distance of this face's
 495                         north direction.
 496             */
 497          if (x == 1)
 498             {
 499                         *lastminup = minup;
 500                         minup = Test_Adj(temp2,x,north,*lastminup,lastvert,last_seen);
 501                         *lastminup = minup;
 502                smallest_so_far = minup;
 503          }
 504
 505
 506             /* find the largest band that we can have */
 507             if (minup < (*lastminup))
 508             {
 509                         /*      see if we really can go up all the way
 510                                 temp should by less than our equal to minup
 511                                 if it is less, then one of the faces was not
 512                                 adjacent to those next to it and the band height
 513                                 will be smaller
 514                         */
 515                         temp = Test_Adj(temp2,x,north,minup,lastvert,last_seen);
 516                         if (temp > minup)
 517                         {
 518                                 printf("There is an error in the test adj\n");
 519                                 exit(0);
 520                         }
 521                         minup = temp;
 522                         band_value = x * minup;
 523                         if (minup < smallest_so_far)
 524                         {
 525                                 if (band_value > max)
 526                 {
 527                                         smallest_so_far = minup;
 528                                         *lastminup = minup;
 529                                         *lastminleft = x;
 530                          max = band_value;
 531                     }
 532                                 else
 533                                         smallest_so_far = minup;
 534                         }
 535                         else
 536                         {
 537                                 band_value = x * smallest_so_far;
 538                   if (band_value > max)
 539                     {
 540                              *lastminup = smallest_so_far;
 541                          *lastminleft = x;
 542                          max = band_value;
 543                     }
 544                         }
 545                 }
 546                 else
 547                 {
 548                         if (x != 1)
 549                {
 550                     temp = Test_Adj(temp2,x,north,smallest_so_far,lastvert,last_seen);
 551                              if (temp > smallest_so_far)
 552                              {
 553                                     printf("There is an error in the test adj\n");
 554                                     exit(0);
 555                              }
 556                             smallest_so_far = temp;
 557                }
 558                band_value = x * smallest_so_far;
 559                         if (band_value > max)
 560                         {
 561                                 *lastminup = smallest_so_far;
 562                                 *lastminleft = x;
 563                                 max = band_value;
 564                         }
 565                 }
 566                 if ( x != (walk + 1))
 567                 {
 568                         node = *(temp2->VertandId+left);
 569                         if (lastvert == node->edge[1])
 570                                 nextvert = node->edge[2];
 571                         else
 572                                 nextvert = node->edge[1];
 573
 574                lastvert = nextvert;
 575
 576                if (nextvert == -1)
 577                     return max;
 578
 579                pListHead = PolFaces[nextvert];
 580                         temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
 581
 582                /* if we have visited this face before, then there is an error */
 583                if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
 584                                 (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
 585                                 || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
 586                         {
 587
 588                     if (lastvert == node->edge[1])
 589                          nextvert = node->edge[2];
 590                     else
 591                          nextvert = node->edge[1];
 592                     if (nextvert == -1)
 593                          return max;
 594                     lastvert = nextvert;
 595                     /*   Last attempt to get the face ... */
 596                     pListHead = PolFaces[nextvert];
 597                         temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
 598                     if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
 599                                      (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
 600                                      || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
 601                          return max;    /*   The polygon was not saved with the edge, not
 602                                              enough room. We will get the walk when we come
 603                                              to that polygon later.
 604                                         */
 605                         }
 606                         /*else
 607                         {*/
 608                                 counter = 0;
 609                                 flag = TRUE;
 610                                 temp2->seen = last_seen;
 611
 612                     while ((counter < 3) && (flag))
 613                              {
 614
 615                          if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
 616                                         (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
 617                                         ((*(temp2->pPolygon+counter) == previous_edge2) ||
 618                                         (*(temp2->pPolygon+counter+1) == previous_edge1)) )
 619                                         counter++;
 620                                      else
 621                                         flag = FALSE;
 622                     }
 623                /*}*/
 624
 625                /* Get the IDs of the next edge */
 626                left = counter;
 627                      north = left+1;
 628                if (left ==3)
 629                              north = 0;
 630                      if (counter < 3)
 631                {
 632                         previous_edge1 = *(temp2->pPolygon + counter + 1);
 633                         previous_edge2 = *(temp2->pPolygon + counter);
 634                }
 635                else
 636                {
 637                         previous_edge1 = *(temp2->pPolygon + counter);
 638                         previous_edge2 = *(temp2->pPolygon);
 639                }
 640
 641           }
 642
 643 }
 644 last_seen++;
 645 return max;
 646 }
 647
 648 void Mark_Face(PF_FACES temp2, int color1, int color2,
 649                                 int color3, FILE *output_file, BOOL end, int *edge1, int *edge2,
 650                     int *face_id, int norms, int texture)
 651 {
 652      static int last_quad[4];
 653      int x,y,z=0;
 654      int saved[2];
 655      static int output1, output2,last_id;
 656      BOOL cptexture = FALSE;
 657
 658      /*   Are we done with the patch? If so return the last edge that
 659           we will come out on, and that will be the edge that we will
 660           start to extend upon.
 661      */
 662
 663      if (end)
 664      {
 665           *edge1 = output1;
 666           *edge2 = output2;
 667           *face_id = last_id;
 668           return;
 669      }
 670
 671      cptexture = texture;
 672      last_id = *face_id;
 673         *(temp2->walked) = -1;
 674         *(temp2->walked+1) = -1;
 675         *(temp2->walked+2) = -1;
 676         *(temp2->walked+3) = -1;
 677         added_quad++;
 678         temp2->nPolSize = 1;
 679
 680      if (patch == 0)
 681      {
 682           /*   At the first quad in the strip -- save it */
 683           last_quad[0] = *(temp2->pPolygon);
 684           last_quad[1] = *(temp2->pPolygon+1);
 685           last_quad[2] = *(temp2->pPolygon+2);
 686           last_quad[3] = *(temp2->pPolygon+3);
 687           patch++;
 688      }
 689      else
 690      {
 691           /*   Now we have a triangle to output, find the edge in common */
 692           for (x=0; x < 4 ;x++)
 693           {
 694               for (y=0; y< 4; y++)
 695               {
 696                    if (last_quad[x] == *(temp2->pPolygon+y))
 697                    {
 698                         saved[z++] = last_quad[x];
 699                         if (z > 2)
 700                         {
 701                              /*    This means that there was a non convex or
 702                                    an overlapping polygon
 703                              */
 704                              z--;
 705                              break;
 706                         }
 707                    }
 708               }
 709           }
 710
 711           if (z != 2)
 712           {
 713                printf("Z is not 2 %d \n",patch);
 714                printf("4 %d %d %d %d %d %d %d\n",*(temp2->pPolygon),
 715                                 *(temp2->pPolygon+1),*(temp2->pPolygon+2),*(temp2->pPolygon+3),
 716                                 color1,color2,color3);
 717                printf("%d %d %d %d\n",last_quad[0],last_quad[1],last_quad[2],last_quad[3]);
 718                exit(1);
 719           }
 720
 721           if (patch == 1)
 722           {
 723                /*   First one to output, there was no output edge */
 724                patch++;
 725                x = Adjacent(saved[0],saved[1],last_quad,4);
 726                y = Adjacent(saved[1],saved[0],last_quad,4);
 727
 728                /*   Data might be mixed and we do not have textures for some of the vertices */
 729                if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) || ((vt[saved[1]])==0)))
 730                     cptexture = FALSE;
 731
 732                if ((!norms) && (!cptexture))
 733                {
 734                     fprintf(output_file,"\nt %d %d %d ",x+1,y+1,saved[1]+1);
 735                     fprintf(output_file,"%d ",saved[0]+1);
 736                }
 737                else if ((norms) && (!cptexture))
 738                {
 739                     fprintf(output_file,"\nt %d//%d %d//%d %d//%d ",x+1,vn[x] +1,
 740                                                                     y+1,vn[y] +1,
 741                                                                     saved[1]+1,vn[saved[1]]+1);
 742                     fprintf(output_file,"%d//%d ",saved[0]+1,vn[saved[0]]+1);
 743                }
 744                else if ((cptexture) && (!norms))
 745                {
 746                     fprintf(output_file,"\nt %d/%d %d/%d %d/%d ",x+1,vt[x] +1,
 747                                                                     y+1,vt[y] +1,
 748                                                                     saved[1]+1,vt[saved[1]]+1);
 749                     fprintf(output_file,"%d//%d ",saved[0]+1,vt[saved[0]]+1);
 750                }
 751                else
 752                {
 753                     fprintf(output_file,"\nt %d/%d/%d %d/%d/%d %d/%d/%d ",x+1,vt[x]+1,vn[x] +1,
 754                                                                     y+1,vt[y]+1,vn[y] +1,
 755                                                                     saved[1]+1,vt[saved[1]]+1,vn[saved[1]]+1);
 756                     fprintf(output_file,"%d/%d/%d ",saved[0]+1,vt[saved[0]]+1,vn[saved[0]]+1);
 757                }
 758
 759                x = Adjacent(saved[0],saved[1],temp2->pPolygon,4);
 760                y = Adjacent(saved[1],saved[0],temp2->pPolygon,4);
 761
 762                /*   Data might be mixed and we do not have textures for some of the vertices */
 763                if ((texture) && ( (vt[x] == 0) || (vt[y]==0)))
 764                {
 765                     if (cptexture)
 766                          fprintf(output_file,"\nq ");
 767                     cptexture = FALSE;
 768                }
 769                if ((!norms) && (!cptexture))
 770                {
 771                     fprintf(output_file,"%d ",x+1);
 772                     fprintf(output_file,"%d ",y+1);
 773                }
 774                else if ((norms) && (!cptexture))
 775                {
 776                     fprintf(output_file,"%d//%d ",x+1,vn[x]+1);
 777                     fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
 778                }
 779                else if ((cptexture) && (!norms))
 780                {
 781                     fprintf(output_file,"%d/%d ",x+1,vt[x]+1);
 782                     fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
 783                }
 784                else
 785                {
 786                     fprintf(output_file,"%d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
 787                     fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
 788                }
 789
 790                output1 = x;
 791                output2 = y;
 792           }
 793
 794           else
 795           {
 796                x = Adjacent(output2,output1,temp2->pPolygon,4);
 797                y = Adjacent(output1,output2,temp2->pPolygon,4);
 798                /*   Data might be mixed and we do not have textures for some of the vertices */
 799                if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) ))
 800                     texture = FALSE;
 801
 802                if ((!norms) && (!texture))
 803                {
 804                     fprintf(output_file,"\nq %d ",x+1);
 805                     fprintf(output_file,"%d ",y+1);
 806                }
 807                else if ((norms) && (!texture))
 808                {
 809                     fprintf(output_file,"\nq %d//%d ",x+1,vn[x]+1);
 810                     fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
 811                }
 812                else if ((texture) && (!norms))
 813                {
 814                     fprintf(output_file,"\nq %d/%d ",x+1,vt[x]+1);
 815                     fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
 816                }
 817                else
 818                {
 819                     fprintf(output_file,"\nq %d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
 820                     fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
 821                }
 822
 823                output1 = x;
 824                output2 = y;
 825           }
 826
 827           last_quad[0] = *(temp2->pPolygon);
 828           last_quad[1] = *(temp2->pPolygon+1);
 829           last_quad[2] = *(temp2->pPolygon+2);
 830           last_quad[3] = *(temp2->pPolygon+3);
 831      }
 832 }
 833
 834 void Fast_Reset(int x)
 835 {
 836         register int y,numverts;
 837         register int front_walk, back_walk;
 838         ListHead *pListHead;
 839         PF_FACES temp = NULL;
 840
 841      pListHead = PolFaces[x];
 842         temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 843         numverts = temp->nPolSize;
 844
 845      front_walk = 0;
 846      back_walk = 0;
 847      resetting = TRUE;
 848
 849      /* we are doing this only for quads */
 850         if (numverts == 4)
 851         {
 852                         /*      for each face not seen yet, do North and South together
 853                                 and East and West together
 854                         */
 855                         for (y=0;y<2;y++)
 856                         {
 857                                 /* Check if the opposite sides were seen already */
 858                         /* Find walk for the first edge */
 859                                 front_walk = Calculate_Walks(x,y,temp);
 860                                 /* Find walk in the opposite direction */
 861                                 back_walk = Calculate_Walks(x,y+2,temp);
 862                                 /*      Now put into the data structure the numbers that
 863                                 we have found
 864                                 */
 865                     Assign_Walk(x,temp,front_walk,y,back_walk);
 866                                 Assign_Walk(x,temp,back_walk,y+2,front_walk);
 867                         }
 868         }
 869      resetting = FALSE;
 870 }
 871
 872
 873 void Reset_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
 874                 int last_left,FILE *output_file,int color1,int color2,int color3,
 875                 BOOL start)
 876 {
 877         int previous_edge1,previous_edge2;
 878         F_EDGES *node;
 879         ListHead *pListHead;
 880         int f,t,nextvert,counter;
 881      BOOL flag;
 882
 883
 884      /*   Reset walks on faces, since we just found a patch */
 885      if (orientation !=3)
 886      {
 887                 previous_edge1 = *(temp2->pPolygon + orientation+1);
 888                 previous_edge2 = *(temp2->pPolygon + orientation );
 889      }
 890      else
 891      {
 892                 previous_edge1 = *(temp2->pPolygon + orientation );
 893                 previous_edge2 = *(temp2->pPolygon);
 894      }
 895
 896         /* only if we are going left, otherwise there will be -1 there */
 897         /*Find the adjacent face to this edge */
 898
 899      for (t = 0; t <=3 ; t++)
 900      {
 901              node = *(temp2->VertandId+t);
 902
 903              if (face_id == node->edge[1])
 904                 f = node->edge[2];
 905              else
 906                f = node->edge[1];
 907
 908              if (f != -1)
 909                   Fast_Reset(f);
 910         }
 911
 912         node = *(temp2->VertandId+orientation);
 913         if (face_id == node->edge[1])
 914              nextvert = node->edge[2];
 915         else
 916              nextvert = node->edge[1];
 917
 918         while ((last_left--) > 1)
 919         {
 920
 921           if (start)
 922                Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
 923
 924           face_id = nextvert;
 925           pListHead = PolFaces[nextvert];
 926           temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 927           if ((temp2->nPolSize != 4) && (temp2->nPolSize != 1))
 928           {
 929              /*   There is more than 2 polygons on the edge, and we could have
 930                   gotten the wrong one
 931              */
 932              if (nextvert != node->edge[1])
 933                   nextvert = node->edge[1];
 934              else
 935                   nextvert = node->edge[2];
 936              pListHead = PolFaces[nextvert];
 937              temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 938              node = *(temp2->VertandId+orientation);
 939           }
 940
 941
 942          if (!start)
 943          {
 944              for (t = 0; t <=3 ; t++)
 945              {
 946                     node = *(temp2->VertandId+t);
 947
 948                     if (face_id == node->edge[1])
 949                          f = node->edge[2];
 950                     else
 951                          f = node->edge[1];
 952
 953                     if (f != -1)
 954                          Fast_Reset(f);
 955              }
 956         }
 957
 958
 959         counter = 0;
 960            flag = TRUE;
 961            while ((counter < 3) && (flag))
 962         {
 963              if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
 964                    (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
 965                   ((*(temp2->pPolygon+counter) == previous_edge2) ||
 966                    (*(temp2->pPolygon+counter+1) == previous_edge1)) )
 967                    counter++;
 968              else
 969                   flag = FALSE;
 970         }
 971
 972         /* Get the IDs of the next edge */
 973         if (counter < 3)
 974         {
 975              previous_edge1 = *(temp2->pPolygon + counter+1);
 976              previous_edge2 = *(temp2->pPolygon + counter);
 977         }
 978         else
 979         {
 980              previous_edge1 = *(temp2->pPolygon + counter);
 981              previous_edge2 = *(temp2->pPolygon);
 982         }
 983         orientation = counter;
 984
 985         node = *(temp2->VertandId + counter);
 986            if (node->edge[1] == nextvert)
 987                         nextvert = node->edge[2];
 988            else
 989                         nextvert = node->edge[1];
 990
 991         if (!reversed)
 992         {
 993                if (counter != 3)
 994                              north = counter +1;
 995                      else
 996                              north = 0;
 997         }
 998         else
 999         {
1000                if (counter != 0)
1001                     north = counter -1;
1002                else
1003                     north = 3;
1004
1005         }
1006      }
1007 if (start)
1008         Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
1009 else if (nextvert != -1)
1010      Fast_Reset(nextvert);
1011
1012 }
1013
1014
1015 int Peel_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
1016                 int last_left,FILE *output_file,int color1,int color2,int color3,
1017                 BOOL start, int *swaps_added, int norms, int texture)
1018 {
1019         int end1,end2,last_id,s=0,walk = 0;
1020         int previous_edge1,previous_edge2;
1021         static int last_seen = 1000;
1022         F_EDGES *node;
1023         ListHead *pListHead;
1024         int nextvert,numverts,counter,dummy,tris=0;
1025      BOOL flag;
1026
1027      /*   Peel the patch from the model.
1028           We will try and extend off the end of each strip in the patch. We will return the
1029           number of triangles completed by this extension only, and the number of swaps
1030           in the extension only.
1031      */
1032      patch = 0;
1033
1034      if (orientation !=3)
1035      {
1036                 previous_edge1 = *(temp2->pPolygon + orientation+1);
1037                 previous_edge2 = *(temp2->pPolygon + orientation );
1038      }
1039      else
1040      {
1041                 previous_edge1 = *(temp2->pPolygon + orientation );
1042                 previous_edge2 = *(temp2->pPolygon);
1043      }
1044
1045
1046      walk = *(temp2->walked + orientation);
1047
1048      /* only if we are going left, otherwise there will be -1 there */
1049         if ((start) && ((walk+1) < last_left))
1050         {
1051                 printf("There is an error in the left %d %d\n",walk,last_left);
1052                 exit(0);
1053         }
1054
1055      /* Find the adjacent face to this edge */
1056      node = *(temp2->VertandId+orientation);
1057      if (face_id == node->edge[1])
1058           nextvert = node->edge[2];
1059      else
1060           nextvert = node->edge[1];
1061         temp2->seen = last_seen;
1062
1063
1064         while ((last_left--) > 1)
1065         {
1066                 if (start)
1067              tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1068                               color1,color2,color3,FALSE,swaps_added,norms,texture);
1069           else
1070              Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);
1071
1072
1073           pListHead = PolFaces[nextvert];
1074           temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1075           numverts = temp2->nPolSize;
1076
1077           if ((numverts != 4) || (temp2->seen == last_seen)
1078                         ||  (nextvert == -1))
1079           {
1080
1081              /*   There is more than 2 polygons on the edge, and we could have
1082                   gotten the wrong one
1083              */
1084              if (nextvert != node->edge[1])
1085                   nextvert = node->edge[1];
1086              else
1087                   nextvert = node->edge[2];
1088              pListHead = PolFaces[nextvert];
1089              temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1090              numverts = temp2->nPolSize;
1091              if ((numverts != 4) || (temp2->seen == last_seen) )
1092              {
1093                   printf("Peel 2 %d\n",numverts);
1094                   exit(1);
1095              }
1096         }
1097
1098         face_id = nextvert;
1099         temp2->seen = last_seen;
1100
1101         counter = 0;
1102         flag = TRUE;
1103            while ((counter < 3) && (flag))
1104         {
1105              if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1106                    (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1107                   ((*(temp2->pPolygon+counter) == previous_edge2) ||
1108                    (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1109                    counter++;
1110              else
1111                   flag = FALSE;
1112         }
1113         /* Get the IDs of the next edge */
1114         if (counter < 3)
1115         {
1116              previous_edge1 = *(temp2->pPolygon + counter+1);
1117              previous_edge2 = *(temp2->pPolygon + counter);
1118         }
1119         else
1120         {
1121              previous_edge1 = *(temp2->pPolygon + counter);
1122              previous_edge2 = *(temp2->pPolygon);
1123         }
1124         orientation = counter;
1125
1126            node = *(temp2->VertandId + counter);
1127            if (node->edge[1] == nextvert)
1128                         nextvert = node->edge[2];
1129            else
1130                         nextvert = node->edge[1];
1131
1132            if (!reversed)
1133         {
1134                if (counter != 3)
1135                              north = counter +1;
1136                      else
1137                              north = 0;
1138         }
1139         else
1140         {
1141                if (counter != 0)
1142                     north = counter -1;
1143                else
1144                     north = 3;
1145         }
1146 }
1147
1148 if (start)
1149         tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1150                         color1,color2,color3,FALSE,swaps_added,norms,texture);
1151 else
1152      Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);/* do the last face */
1153
1154 last_seen++;
1155
1156 /*    Get the edge that we came out on the last strip of the patch */
1157 Mark_Face(NULL,0,0,0,output_file,TRUE,&end1,&end2,&last_id,norms,texture);
1158 tris += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1159 *swaps_added = *swaps_added + s;
1160 return tris;
1161 }
1162
1163
1164
1165 void Find_Bands(int numfaces, FILE *output_file, int *swaps, int *bands,
1166                 int *cost, int *tri, int norms, int *vert_norms, int texture, int *vert_texture)
1167 {
1168
1169         register int x,y,max1,max2,numverts,face_id,flag,maximum = 25;
1170         ListHead *pListHead;
1171         PF_FACES temp = NULL;
1172         int color1 = 0, color2 = 100, color3 = 255;
1173         int larger,smaller;
1174         int north_length1,last_north,left_length1,last_left,north_length2,left_length2;
1175   int total_tri = 0, total_swaps = 0,last_id;
1176   int end1, end2,s=0;
1177   register int cutoff = 20;
1178
1179   /* Code that will find the patches. "Cutoff" will be
1180      the cutoff of the area of the patches that we will be allowing. After
1181      we reach this cutoff length, then we will run the local algorithm on the
1182      remaining faces.
1183   */
1184
1185         /* For each faces that is left find the largest possible band that we can
1186                  have with the remaining faces. Note that we will only be finding patches
1187      consisting of quads.
1188         */
1189
1190   vn = vert_norms;
1191   vt = vert_texture;
1192   y=1;
1193   *bands = 0;
1194
1195   while ((maximum >= cutoff))
1196   {
1197           y++;
1198     maximum = -1;
1199           for (x=0; x<numfaces; x++)
1200           {
1201       /*   Used to produce the triangle strips */
1202
1203       /* for each face, get the face */
1204                   pListHead = PolFaces[x];
1205                   temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1206                   numverts = temp->nPolSize;
1207
1208       /* we are doing this only for quads */
1209                   if (numverts == 4)
1210                   {
1211                           /* We want a face that is has not been used yet,
1212            since we know that that face must be part of
1213                                    a band. Then we will find the largest band that
1214                                    the face may be contained in
1215                           */
1216
1217         /*  Doing the north and the left */
1218                           if ((*(temp->walked) != -1) && (*(temp->walked+3) != -1))
1219                                   max1 = Find_Max(temp,x,0,3,&north_length1,&left_length1);
1220                           if ((*(temp->walked+1) != -1) && (*(temp->walked+2) != -1))
1221                                   max2 = Find_Max(temp,x,2,1,&north_length2,&left_length2);
1222                           if ((max1 != (north_length1 * left_length1)) ||
1223                               (max2 != (north_length2 * left_length2)))
1224                           {
1225                                   printf("Max1 %d, %d %d        Max2 %d, %d %d\n",max1,north_length1,left_length1,max2,north_length2,left_length2);
1226                                   exit(0);
1227                           }
1228
1229
1230         if ((max1 > max2) && (max1 > maximum))
1231                           {
1232           maximum = max1;
1233           face_id = x;
1234           flag = 1;
1235           last_north = north_length1;
1236           last_left = left_length1;
1237           /* so we know we saved max1 */
1238                           }
1239                           else if ((max2 > maximum) )
1240                           {
1241           maximum = max2;
1242           face_id = x;
1243           flag = 2;
1244           last_north = north_length2;
1245           last_left = left_length2;
1246           /* so we know we saved max2 */
1247         }
1248       }
1249     }
1250     if ((maximum < cutoff) && (*bands == 0))
1251       return;
1252     pListHead = PolFaces[face_id];
1253     temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1254     /*   There are no patches that we found in this pass */
1255     if (maximum == -1)
1256       break;
1257     printf("The maximum is  face %d area %d: lengths %d %d\n",face_id,maximum,last_north,last_left);
1258     if (maximum == 16)
1259       printf("Fran");
1260
1261     if (last_north > last_left)
1262     {
1263       larger = last_north;
1264       smaller = last_left;
1265     }
1266     else
1267     {
1268       larger = last_left;
1269       smaller = last_north;
1270     }
1271
1272     length = larger;
1273
1274     if (flag == 1)
1275     {
1276             if (last_north > last_left) /*     go north sequentially */
1277       {
1278         total_tri += Peel_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1279         Reset_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE);
1280         total_swaps += s;
1281       }
1282       else
1283       {
1284         reversed = TRUE;
1285         total_tri += Peel_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1286         Reset_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE);
1287         reversed = FALSE;
1288         total_swaps += s;
1289       }
1290
1291
1292       /*    Get the edge that we came out on the last strip of the patch */
1293       Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1294       total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1295       total_swaps += s;
1296
1297     }
1298     else
1299     {
1300        if (last_north > last_left)
1301        {
1302             total_tri += Peel_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1303             Reset_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE);
1304             total_swaps += s;
1305        }
1306        else
1307        {
1308             reversed = TRUE;
1309             total_tri += Peel_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1310             Reset_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE);
1311             reversed = FALSE;
1312             total_swaps += s;
1313        }
1314
1315        /*    Get the edge that we came out on on the patch */
1316       Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1317       total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1318       total_swaps += s;
1319     }
1320
1321     /* Now compute the cost of transmitting this band, is equal to
1322        going across the larger portion sequentially,
1323        and swapping 3 times per other dimension
1324     */
1325
1326     total_tri += (maximum * 2);
1327     *bands = *bands + smaller;
1328   }
1329
1330   printf("We transmitted %d triangles,using %d swaps and %d strips\n",total_tri,total_swaps, *bands);
1331   printf("COST %d\n",total_tri + total_swaps + *bands + *bands);
1332
1333   *cost = total_tri + total_swaps + *bands + *bands;
1334   *tri = total_tri;
1335   added_quad = added_quad * 4;
1336   *swaps = total_swaps;
1337 }
1338
1339
1340 void Save_Rest(int *numfaces)
1341 {
1342     /*  Put the polygons that are left into a data structure so that we can run the
1343         stripping code on it.
1344     */
1345     register int x,y=0,numverts;
1346     ListHead *pListHead;
1347     PF_FACES temp=NULL;
1348
1349     for (x=0; x<*numfaces; x++)
1350     {
1351                         /* for each face, get the face */
1352                         pListHead = PolFaces[x];
1353                         temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1354                         numverts = temp->nPolSize;
1355                /*  If we did not do the face before add it to data structure with new
1356                    face id number
1357                */
1358                if (numverts != 1)
1359                {
1360                    CopyFace(temp->pPolygon,numverts,y+1,temp->pNorms);
1361                    y++;
1362                }
1363                /*   Used it, so remove it */
1364                else
1365                     RemoveList(pListHead,(PLISTINFO) temp);
1366
1367     }
1368     *numfaces = y;
1369 }
1370
1371 void Assign_Walk(int lastvert,PF_FACES temp2, int front_walk,int y,
1372                                 int back_walk)
1373 {
1374 /*      Go back and do the walk again, but this time save the lengths inside
1375         the data structure.
1376         y was the starting edge number for the front_walk length
1377         back_walk is the length of the walk along the opposite edge
1378  */
1379         int previous_edge1, previous_edge2;
1380         register int walk = 0,nextvert,numverts,counter;
1381         BOOL flag;
1382         F_EDGES *node;
1383         ListHead *pListHead;
1384         static int seen = 0;
1385         static BOOL first = TRUE;
1386         BOOL wrap = FALSE, set = FALSE;
1387
1388         /*     In the "Fast_Reset" resetting will be true */
1389         if ((resetting) && (first))
1390         {
1391              seen = 0;
1392              first = FALSE;
1393         }
1394
1395         seen++;
1396         /*     Had a band who could be a cycle  */
1397         if (front_walk == back_walk)
1398              wrap = TRUE;
1399
1400         /* Find the edge that we are currently on */
1401         if (y != 3)
1402         {
1403                 previous_edge1 = *(temp2->pPolygon +y);
1404                 previous_edge2 = *(temp2->pPolygon + y + 1);
1405         }
1406         else
1407         {
1408                 previous_edge1 = *(temp2->pPolygon +y);
1409                 previous_edge2 = *(temp2->pPolygon);
1410         }
1411
1412         /* Assign the lengths */
1413            if (y < 2)
1414            {
1415                 *(temp2->walked+y) = front_walk--;
1416                          *(temp2->walked+y+2) = back_walk++;
1417            }
1418            else
1419            {
1420                *(temp2->walked+y) = front_walk--;
1421                 *(temp2->walked+y-2) = back_walk++;
1422            }
1423
1424            /*Find the adjacent face to this edge */
1425         node = *(temp2->VertandId+y);
1426
1427         if (node->edge[2] != lastvert)
1428           nextvert = node->edge[2];
1429         else
1430           nextvert = node->edge[1];
1431
1432         temp2->seen3 = seen;
1433
1434         /* Keep walking in this direction until we cannot do so */
1435         while ((nextvert != lastvert) && (nextvert != -1) && (front_walk >= 0))
1436         {
1437                      walk++;
1438                pListHead = PolFaces[nextvert];
1439
1440                temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1441                numverts = temp2->nPolSize;
1442                if ((numverts != 4))
1443                {
1444                     nextvert = -1;
1445                     /* Don't include this face in the walk */
1446                     walk--;
1447                }
1448                else
1449                {
1450                     /* Find edge that is not adjacent to the previous one */
1451                     counter = 0;
1452                     flag = TRUE;
1453                     while ((counter < 3) && (flag))
1454                     {
1455                          if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1456                                (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1457                               ((*(temp2->pPolygon+counter) == previous_edge2) ||
1458                                (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1459                               counter++;
1460                          else
1461                               flag = FALSE;
1462                     }
1463                     /* Get the IDs of the next edge */
1464                     if (counter < 3)
1465                     {
1466                          previous_edge1 = *(temp2->pPolygon + counter);
1467                          previous_edge2 = *(temp2->pPolygon + counter + 1);
1468                     }
1469                     else
1470                     {
1471                          previous_edge1 = *(temp2->pPolygon + counter);
1472                          previous_edge2 = *(temp2->pPolygon);
1473                     }
1474
1475
1476                           /*      Put in the walk lengths */
1477                           if (counter < 2)
1478                           {
1479                         if (((*(temp2->walked + counter) >= 0)
1480                                   || (*(temp2->walked +counter + 2) >= 0)))
1481                                   {
1482                                           if ((resetting == FALSE) && ((temp2->seen3) != (seen-1)))
1483                                           {
1484                                                   /*   If there are more than 2 polygons adjacent
1485                                         to an edge then we can be trying to assign more than
1486                                         once. We will save the smaller one
1487                                    */
1488                                    temp2->seen3 = seen;
1489                                    if ( (*(temp2->walked+counter) <= front_walk) &&
1490                                         (*(temp2->walked+counter+2) <= back_walk) )
1491                                         return;
1492                                    if (*(temp2->walked+counter) > front_walk)
1493                                        *(temp2->walked+counter) = front_walk--;
1494                                    else
1495                                         front_walk--;
1496                                    if (*(temp2->walked+counter+2) > back_walk)
1497                                        *(temp2->walked+counter+2) = back_walk++;
1498                                    else
1499                                         back_walk++;
1500                                           }
1501                                           else if (resetting == FALSE)
1502                                           {
1503                                                   /* if there was a cycle then all lengths are the same */
1504                                                   walk--;
1505                                                   back_walk--;
1506                                                   front_walk++;
1507                                    temp2->seen3 = seen;
1508                                    *(temp2->walked+counter) = front_walk--;
1509                                    *(temp2->walked+counter+2) = back_walk++;
1510                               }
1511                               else if (((temp2->seen3 == (seen-1))
1512                                    && (wrap) && (walk == 1)) || (set))
1513                               {
1514                                                   /* if there was a cycle then all lengths are the same */
1515                                                   set = TRUE;
1516                                    walk--;
1517                                                   back_walk--;
1518                                                   front_walk++;
1519                                    temp2->seen3 = seen;
1520                                    *(temp2->walked+counter) = front_walk--;
1521                                    *(temp2->walked+counter+2) = back_walk++;
1522                               }
1523                               else
1524                               {
1525                                    temp2->seen3 = seen;
1526                                    *(temp2->walked+counter) = front_walk--;
1527                                    *(temp2->walked+counter+2) = back_walk++;
1528                               }
1529                         } /* if was > 0 */
1530                         else
1531                         {
1532                              temp2->seen3 = seen;
1533                              *(temp2->walked+counter) = front_walk--;
1534                              *(temp2->walked+counter+2) = back_walk++;
1535                         }
1536                     }
1537
1538                else
1539                {
1540                     if (((*(temp2->walked + counter) >= 0 )
1541                         || (*(temp2->walked +counter - 2) >= 0)) )
1542                     {
1543                          if ((temp2->seen3 != (seen-1))  && (resetting == FALSE))
1544                          {
1545                               /*   If there are more than 2 polygons adjacent
1546                                    to an edge then we can be trying to assign more than
1547                                    once. We will save the smaller one
1548                               */
1549                               temp2->seen3 = seen;
1550                               if ( (*(temp2->walked+counter) <= front_walk) &&
1551                                    (*(temp2->walked+counter-2) <= back_walk) )
1552                                    return;
1553                               if (*(temp2->walked+counter) > front_walk)
1554                                    *(temp2->walked+counter) = front_walk--;
1555                               else
1556                                    front_walk--;
1557                               if (*(temp2->walked+counter-2) > back_walk)
1558                                    *(temp2->walked+counter-2) = back_walk++;
1559                               else
1560                                    back_walk++;
1561                                 }
1562                                      else if (resetting == FALSE)
1563                                 {
1564                                         walk--;
1565                                         back_walk--;
1566                                         front_walk++;
1567                                  temp2->seen3 = seen;
1568                               *(temp2->walked+counter) = front_walk--;
1569                               *(temp2->walked+counter-2) = back_walk++;
1570                          }
1571                          else if (((temp2->seen3 == (seen-1)) && (walk == 1) && (wrap))
1572                               || (set))
1573                          {
1574                                              /* if there was a cycle then all lengths are the same */
1575                                              set = TRUE;
1576                               walk--;
1577                                              back_walk--;
1578                                              front_walk++;
1579                               temp2->seen3 = seen;
1580                               *(temp2->walked+counter) = front_walk--;
1581                               *(temp2->walked+counter-2) = back_walk++;
1582                          }
1583                          else
1584                          {
1585                               temp2->seen3 = seen;
1586                               *(temp2->walked+counter) = front_walk--;
1587                               *(temp2->walked+counter-2) = back_walk++;
1588                          }
1589                         }
1590                     else
1591                     {
1592                          temp2->seen3 = seen;
1593                          *(temp2->walked+counter) = front_walk--;
1594                          *(temp2->walked+counter-2) = back_walk++;
1595                     }
1596
1597                      }
1598                      if (nextvert != -1)
1599                      {
1600                              node = *(temp2->VertandId + counter);
1601                         if (node->edge[1] == nextvert)
1602                                 nextvert = node->edge[2];
1603                         else
1604                                 nextvert = node->edge[1];
1605                }
1606
1607      }
1608 }
1609 if ((EVEN(seen)) )
1610      seen+=2;
1611 }
1612
1613 void Save_Walks(int numfaces)
1614 {
1615         int x,y,numverts;
1616         int front_walk, back_walk;
1617         ListHead *pListHead;
1618         PF_FACES temp = NULL;
1619
1620         for (x=0; x<numfaces; x++)
1621         {
1622                 /* for each face, get the face */
1623                 pListHead = PolFaces[x];
1624                 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1625                 numverts = temp->nPolSize;
1626                 front_walk = 0;
1627           back_walk = 0;
1628
1629           /* we are finding patches only for quads */
1630                 if (numverts == 4)
1631                 {
1632                         /*      for each face not seen yet, do North and South together
1633                                 and East and West together
1634                         */
1635                         for (y=0;y<2;y++)
1636                         {
1637                                 /*   Check if the opposite sides were seen already from another
1638                          starting face, if they were then there is no need to do the walk again
1639                     */
1640
1641                                 if      ( ((*(temp->walked+y) == -1) &&
1642                                         (*(temp->walked+y+2) == -1) ))
1643                                 {
1644                                         /* Find walk for the first edge */
1645                                         front_walk = Calculate_Walks(x,y,temp);
1646                                         /* Find walk in the opposite direction */
1647                                         back_walk = Calculate_Walks(x,y+2,temp);
1648                                         /*      Now put into the data structure the numbers that
1649                                                 we have found
1650                                         */
1651                          Assign_Walk(x,temp,front_walk,y,back_walk);
1652                                         Assign_Walk(x,temp,back_walk,y+2,front_walk);
1653                         }
1654                         }
1655                 }
1656         }
1657 }
1658
1659