Stripe_u/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[MAX1];
  33 int     added_quad = 0;
  34 BOOL reversed = FALSE;
  35 int patch = 0;
  36 int *vn;
  37 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 t,smallest_so_far,nextvert,max=-1;
 465
 466      t= lastvert;
 467      *lastminup = MAX_BAND;
 468         *lastminleft = 1;
 469
 470      if (left == 3)
 471         {
 472           previous_edge1 = *(temp2->pPolygon + left);
 473           previous_edge2 = *(temp2->pPolygon);
 474         }
 475
 476         else
 477         {
 478           previous_edge1 = *(temp2->pPolygon + left + 1);
 479           previous_edge2 = *(temp2->pPolygon + left);
 480         }
 481
 482         temp2->seen = last_seen;
 483      walk = *(temp2->walked + left);
 484
 485      for (x=1;x<=(walk+1); x++)
 486         {
 487                 /*   test to see if we have a true band
 488                      that is, are they adjacent to each other
 489                 */
 490
 491          minup = *(temp2->walked + north) + 1;
 492
 493             /*  if we are at the very first face, then we do not
 494                      have to check the adjacent faces going up
 495                      and our north distance is the distance of this face's
 496                         north direction.
 497             */
 498          if (x == 1)
 499             {
 500                         *lastminup = minup;
 501                         minup = Test_Adj(temp2,x,north,*lastminup,lastvert,last_seen);
 502                         *lastminup = minup;
 503                smallest_so_far = minup;
 504          }
 505
 506
 507             /* find the largest band that we can have */
 508             if (minup < (*lastminup))
 509             {
 510                         /*      see if we really can go up all the way
 511                                 temp should by less than our equal to minup
 512                                 if it is less, then one of the faces was not
 513                                 adjacent to those next to it and the band height
 514                                 will be smaller
 515                         */
 516                         temp = Test_Adj(temp2,x,north,minup,lastvert,last_seen);
 517                         if (temp > minup)
 518                         {
 519                                 printf("There is an error in the test adj\n");
 520                                 exit(0);
 521                         }
 522                         minup = temp;
 523                         band_value = x * minup;
 524                         if (minup < smallest_so_far)
 525                         {
 526                                 if (band_value > max)
 527                 {
 528                                         smallest_so_far = minup;
 529                                         *lastminup = minup;
 530                                         *lastminleft = x;
 531                          max = band_value;
 532                     }
 533                                 else
 534                                         smallest_so_far = minup;
 535                         }
 536                         else
 537                         {
 538                                 band_value = x * smallest_so_far;
 539                   if (band_value > max)
 540                     {
 541                              *lastminup = smallest_so_far;
 542                          *lastminleft = x;
 543                          max = band_value;
 544                     }
 545                         }
 546                 }
 547                 else
 548                 {
 549                         if (x != 1)
 550                {
 551                     temp = Test_Adj(temp2,x,north,smallest_so_far,lastvert,last_seen);
 552                              if (temp > smallest_so_far)
 553                              {
 554                                     printf("There is an error in the test adj\n");
 555                                     exit(0);
 556                              }
 557                             smallest_so_far = temp;
 558                }
 559                band_value = x * smallest_so_far;
 560                         if (band_value > max)
 561                         {
 562                                 *lastminup = smallest_so_far;
 563                                 *lastminleft = x;
 564                                 max = band_value;
 565                         }
 566                 }
 567                 if ( x != (walk + 1))
 568                 {
 569                         node = *(temp2->VertandId+left);
 570                         if (lastvert == node->edge[1])
 571                                 nextvert = node->edge[2];
 572                         else
 573                                 nextvert = node->edge[1];
 574
 575                lastvert = nextvert;
 576
 577                if (nextvert == -1)
 578                     return max;
 579
 580                pListHead = PolFaces[nextvert];
 581                         temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
 582
 583                /* if we have visited this face before, then there is an error */
 584                if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
 585                                 (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
 586                                 || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
 587                         {
 588
 589                     if (lastvert == node->edge[1])
 590                          nextvert = node->edge[2];
 591                     else
 592                          nextvert = node->edge[1];
 593                     if (nextvert == -1)
 594                          return max;
 595                     lastvert = nextvert;
 596                     /*   Last attempt to get the face ... */
 597                     pListHead = PolFaces[nextvert];
 598                         temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
 599                     if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
 600                                      (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
 601                                      || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
 602                          return max;    /*   The polygon was not saved with the edge, not
 603                                              enough room. We will get the walk when we come
 604                                              to that polygon later.
 605                                         */
 606                         }
 607                         else
 608                         {
 609                                 counter = 0;
 610                                 flag = TRUE;
 611                                 temp2->seen = last_seen;
 612
 613                     while ((counter < 3) && (flag))
 614                              {
 615
 616                          if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
 617                                         (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
 618                                         ((*(temp2->pPolygon+counter) == previous_edge2) ||
 619                                         (*(temp2->pPolygon+counter+1) == previous_edge1)) )
 620                                         counter++;
 621                                      else
 622                                         flag = FALSE;
 623                     }
 624                }
 625
 626                /* Get the IDs of the next edge */
 627                left = counter;
 628                      north = left+1;
 629                if (left ==3)
 630                              north = 0;
 631                      if (counter < 3)
 632                {
 633                         previous_edge1 = *(temp2->pPolygon + counter + 1);
 634                         previous_edge2 = *(temp2->pPolygon + counter);
 635                }
 636                else
 637                {
 638                         previous_edge1 = *(temp2->pPolygon + counter);
 639                         previous_edge2 = *(temp2->pPolygon);
 640                }
 641
 642           }
 643
 644 }
 645 last_seen++;
 646 return max;
 647 }
 648
 649 void Mark_Face(PF_FACES temp2, int color1, int color2,
 650                                 int color3, FILE *output_file, BOOL end, int *edge1, int *edge2,
 651                     int *face_id, int norms, int texture)
 652 {
 653      static int last_quad[4];
 654      register int x,y,z=0;
 655      int saved[2];
 656      static int output1, output2,last_id;
 657      BOOL cptexture;
 658
 659      /*   Are we done with the patch? If so return the last edge that
 660           we will come out on, and that will be the edge that we will
 661           start to extend upon.
 662      */
 663
 664      cptexture = texture;
 665      if (end)
 666      {
 667           *edge1 = output1;
 668           *edge2 = output2;
 669           *face_id = last_id;
 670           return;
 671      }
 672
 673      last_id = *face_id;
 674         *(temp2->walked) = -1;
 675         *(temp2->walked+1) = -1;
 676         *(temp2->walked+2) = -1;
 677         *(temp2->walked+3) = -1;
 678         added_quad++;
 679         temp2->nPolSize = 1;
 680
 681      if (patch == 0)
 682      {
 683           /*   At the first quad in the strip -- save it */
 684           last_quad[0] = *(temp2->pPolygon);
 685           last_quad[1] = *(temp2->pPolygon+1);
 686           last_quad[2] = *(temp2->pPolygon+2);
 687           last_quad[3] = *(temp2->pPolygon+3);
 688           patch++;
 689      }
 690      else
 691      {
 692           /*   Now we have a triangle to output, find the edge in common */
 693           for (x=0; x < 4 ;x++)
 694           {
 695               for (y=0; y< 4; y++)
 696               {
 697                    if (last_quad[x] == *(temp2->pPolygon+y))
 698                    {
 699                         saved[z++] = last_quad[x];
 700                         if (z > 2)
 701                         {
 702                              /*    This means that there was a non convex or
 703                                    an overlapping polygon
 704                              */
 705                              z--;
 706                              break;
 707                         }
 708                    }
 709               }
 710           }
 711
 712           if (z != 2)
 713           {
 714                printf("Z is not 2 %d \n",patch);
 715                printf("4 %d %d %d %d %d %d %d\n",*(temp2->pPolygon),
 716                                 *(temp2->pPolygon+1),*(temp2->pPolygon+2),*(temp2->pPolygon+3),
 717                                 color1,color2,color3);
 718                printf("%d %d %d %d\n",last_quad[0],last_quad[1],last_quad[2],last_quad[3]);
 719                exit(1);
 720           }
 721
 722           if (patch == 1)
 723           {
 724                /*   First one to output, there was no output edge */
 725                patch++;
 726                x = Adjacent(saved[0],saved[1],last_quad,4);
 727                y = Adjacent(saved[1],saved[0],last_quad,4);
 728
 729                /*   Data might be mixed and we do not have textures for some of the vertices */
 730                if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) || ((vt[saved[1]])==0)))
 731                     cptexture = FALSE;
 732
 733                if ((!norms) && (!cptexture))
 734                {
 735                     fprintf(output_file,"\nt %d %d %d ",x+1,y+1,saved[1]+1);
 736                     fprintf(output_file,"%d ",saved[0]+1);
 737                }
 738                else if ((norms) && (!cptexture))
 739                {
 740                     fprintf(output_file,"\nt %d//%d %d//%d %d//%d ",x+1,vn[x] +1,
 741                                                                     y+1,vn[y] +1,
 742                                                                     saved[1]+1,vn[saved[1]]+1);
 743                     fprintf(output_file,"%d//%d ",saved[0]+1,vn[saved[0]]+1);
 744                }
 745                else if ((cptexture) && (!norms))
 746                {
 747                     fprintf(output_file,"\nt %d/%d %d/%d %d/%d ",x+1,vt[x] +1,
 748                                                                     y+1,vt[y] +1,
 749                                                                     saved[1]+1,vt[saved[1]]+1);
 750                     fprintf(output_file,"%d//%d ",saved[0]+1,vt[saved[0]]+1);
 751                }
 752                else
 753                {
 754                     fprintf(output_file,"\nt %d/%d/%d %d/%d/%d %d/%d/%d ",x+1,vt[x]+1,vn[x] +1,
 755                                                                     y+1,vt[y]+1,vn[y] +1,
 756                                                                     saved[1]+1,vt[saved[1]]+1,vn[saved[1]]+1);
 757                     fprintf(output_file,"%d/%d/%d ",saved[0]+1,vt[saved[0]]+1,vn[saved[0]]+1);
 758                }
 759
 760                x = Adjacent(saved[0],saved[1],temp2->pPolygon,4);
 761                y = Adjacent(saved[1],saved[0],temp2->pPolygon,4);
 762
 763                /*   Data might be mixed and we do not have textures for some of the vertices */
 764                if ((texture) && ( (vt[x] == 0) || (vt[y]==0)))
 765                {
 766                     if (cptexture)
 767                          fprintf(output_file,"\nq ");
 768                     cptexture = FALSE;
 769                }
 770                if ((!norms) && (!cptexture))
 771                {
 772                     fprintf(output_file,"%d ",x+1);
 773                     fprintf(output_file,"%d ",y+1);
 774                }
 775                else if ((norms) && (!cptexture))
 776                {
 777                     fprintf(output_file,"%d//%d ",x+1,vn[x]+1);
 778                     fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
 779                }
 780                else if ((cptexture) && (!norms))
 781                {
 782                     fprintf(output_file,"%d/%d ",x+1,vt[x]+1);
 783                     fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
 784                }
 785                else
 786                {
 787                     fprintf(output_file,"%d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
 788                     fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
 789                }
 790
 791                output1 = x;
 792                output2 = y;
 793           }
 794
 795           else
 796           {
 797                x = Adjacent(output2,output1,temp2->pPolygon,4);
 798                y = Adjacent(output1,output2,temp2->pPolygon,4);
 799                /*   Data might be mixed and we do not have textures for some of the vertices */
 800                if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) ))
 801                     texture = FALSE;
 802
 803                if ((!norms) && (!texture))
 804                {
 805                     fprintf(output_file,"\nq %d ",x+1);
 806                     fprintf(output_file,"%d ",y+1);
 807                }
 808                else if ((norms) && (!texture))
 809                {
 810                     fprintf(output_file,"\nq %d//%d ",x+1,vn[x]+1);
 811                     fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
 812                }
 813                else if ((texture) && (!norms))
 814                {
 815                     fprintf(output_file,"\nq %d/%d ",x+1,vt[x]+1);
 816                     fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
 817                }
 818                else
 819                {
 820                     fprintf(output_file,"\nq %d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
 821                     fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
 822                }
 823
 824                output1 = x;
 825                output2 = y;
 826           }
 827
 828           last_quad[0] = *(temp2->pPolygon);
 829           last_quad[1] = *(temp2->pPolygon+1);
 830           last_quad[2] = *(temp2->pPolygon+2);
 831           last_quad[3] = *(temp2->pPolygon+3);
 832      }
 833 }
 834
 835 void Fast_Reset(int x)
 836 {
 837         register int y,numverts;
 838         register int front_walk, back_walk;
 839         ListHead *pListHead;
 840         PF_FACES temp = NULL;
 841
 842      pListHead = PolFaces[x];
 843         temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 844         numverts = temp->nPolSize;
 845
 846      front_walk = 0;
 847      back_walk = 0;
 848      resetting = TRUE;
 849
 850      /* we are doing this only for quads */
 851         if (numverts == 4)
 852         {
 853                         /*      for each face not seen yet, do North and South together
 854                                 and East and West together
 855                         */
 856                         for (y=0;y<2;y++)
 857                         {
 858                                 /* Check if the opposite sides were seen already */
 859                         /* Find walk for the first edge */
 860                                 front_walk = Calculate_Walks(x,y,temp);
 861                                 /* Find walk in the opposite direction */
 862                                 back_walk = Calculate_Walks(x,y+2,temp);
 863                                 /*      Now put into the data structure the numbers that
 864                                 we have found
 865                                 */
 866                     Assign_Walk(x,temp,front_walk,y,back_walk);
 867                                 Assign_Walk(x,temp,back_walk,y+2,front_walk);
 868                         }
 869         }
 870      resetting = FALSE;
 871 }
 872
 873
 874 void Reset_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
 875                 int last_left,FILE *output_file,int color1,int color2,int color3,
 876                 BOOL start)
 877 {
 878         register int walk = 0,count = 0;
 879         int previous_edge1,previous_edge2;
 880         int static last_seen = 1000;
 881         F_EDGES *node;
 882         ListHead *pListHead;
 883         int f,t,nextvert,counter;
 884      BOOL flag;
 885
 886
 887      /*   Reset walks on faces, since we just found a patch */
 888      if (orientation !=3)
 889      {
 890                 previous_edge1 = *(temp2->pPolygon + orientation+1);
 891                 previous_edge2 = *(temp2->pPolygon + orientation );
 892      }
 893      else
 894      {
 895                 previous_edge1 = *(temp2->pPolygon + orientation );
 896                 previous_edge2 = *(temp2->pPolygon);
 897      }
 898
 899         /* only if we are going left, otherwise there will be -1 there */
 900         /*Find the adjacent face to this edge */
 901
 902      for (t = 0; t <=3 ; t++)
 903      {
 904              node = *(temp2->VertandId+t);
 905
 906              if (face_id == node->edge[1])
 907                 f = node->edge[2];
 908              else
 909                f = node->edge[1];
 910
 911              if (f != -1)
 912                   Fast_Reset(f);
 913         }
 914
 915         node = *(temp2->VertandId+orientation);
 916         if (face_id == node->edge[1])
 917              nextvert = node->edge[2];
 918         else
 919              nextvert = node->edge[1];
 920
 921         while ((last_left--) > 1)
 922         {
 923
 924           if (start)
 925                Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
 926
 927           face_id = nextvert;
 928           pListHead = PolFaces[nextvert];
 929           temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 930           if ((temp2->nPolSize != 4) && (temp2->nPolSize != 1))
 931           {
 932              /*   There is more than 2 polygons on the edge, and we could have
 933                   gotten the wrong one
 934              */
 935              if (nextvert != node->edge[1])
 936                   nextvert = node->edge[1];
 937              else
 938                   nextvert = node->edge[2];
 939              pListHead = PolFaces[nextvert];
 940              temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
 941              node = *(temp2->VertandId+orientation);
 942           }
 943
 944
 945          if (!start)
 946          {
 947              for (t = 0; t <=3 ; t++)
 948              {
 949                     node = *(temp2->VertandId+t);
 950
 951                     if (face_id == node->edge[1])
 952                          f = node->edge[2];
 953                     else
 954                          f = node->edge[1];
 955
 956                     if (f != -1)
 957                          Fast_Reset(f);
 958              }
 959         }
 960
 961
 962         counter = 0;
 963            flag = TRUE;
 964            while ((counter < 3) && (flag))
 965         {
 966              if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
 967                    (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
 968                   ((*(temp2->pPolygon+counter) == previous_edge2) ||
 969                    (*(temp2->pPolygon+counter+1) == previous_edge1)) )
 970                    counter++;
 971              else
 972                   flag = FALSE;
 973         }
 974
 975         /* Get the IDs of the next edge */
 976         if (counter < 3)
 977         {
 978              previous_edge1 = *(temp2->pPolygon + counter+1);
 979              previous_edge2 = *(temp2->pPolygon + counter);
 980         }
 981         else
 982         {
 983              previous_edge1 = *(temp2->pPolygon + counter);
 984              previous_edge2 = *(temp2->pPolygon);
 985         }
 986         orientation = counter;
 987
 988         node = *(temp2->VertandId + counter);
 989            if (node->edge[1] == nextvert)
 990                         nextvert = node->edge[2];
 991            else
 992                         nextvert = node->edge[1];
 993
 994         if (!reversed)
 995         {
 996                if (counter != 3)
 997                              north = counter +1;
 998                      else
 999                              north = 0;
1000         }
1001         else
1002         {
1003                if (counter != 0)
1004                     north = counter -1;
1005                else
1006                     north = 3;
1007
1008         }
1009      }
1010 if (start)
1011         Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
1012 else if (nextvert != -1)
1013      Fast_Reset(nextvert);
1014
1015 }
1016
1017
1018 int Peel_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
1019                 int last_left,FILE *output_file,int color1,int color2,int color3,
1020                 BOOL start, int *swaps_added, int norms, int texture)
1021 {
1022         int end1,end2,last_id,s=0,walk = 0,count = 0;
1023         int previous_edge1,previous_edge2;
1024         int static last_seen = 1000;
1025         F_EDGES *node;
1026         ListHead *pListHead;
1027         int nextvert,numverts,counter,dummy,tris=0;
1028      BOOL flag;
1029
1030      /*   Peel the patch from the model.
1031           We will try and extend off the end of each strip in the patch. We will return the
1032           number of triangles completed by this extension only, and the number of swaps
1033           in the extension only.
1034      */
1035      patch = 0;
1036
1037      if (orientation !=3)
1038      {
1039                 previous_edge1 = *(temp2->pPolygon + orientation+1);
1040                 previous_edge2 = *(temp2->pPolygon + orientation );
1041      }
1042      else
1043      {
1044                 previous_edge1 = *(temp2->pPolygon + orientation );
1045                 previous_edge2 = *(temp2->pPolygon);
1046      }
1047
1048
1049      walk = *(temp2->walked + orientation);
1050
1051      /* only if we are going left, otherwise there will be -1 there */
1052         if ((start) && ((walk+1) < last_left))
1053         {
1054                 printf("There is an error in the left %d %d\n",walk,last_left);
1055                 exit(0);
1056         }
1057
1058      /* Find the adjacent face to this edge */
1059      node = *(temp2->VertandId+orientation);
1060      if (face_id == node->edge[1])
1061           nextvert = node->edge[2];
1062      else
1063           nextvert = node->edge[1];
1064         temp2->seen = last_seen;
1065
1066
1067         while ((last_left--) > 1)
1068         {
1069                 if (start)
1070              tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1071                               color1,color2,color3,FALSE,swaps_added,norms,texture);
1072           else
1073              Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);
1074
1075
1076           pListHead = PolFaces[nextvert];
1077           temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1078           numverts = temp2->nPolSize;
1079
1080           if ((numverts != 4) || (temp2->seen == last_seen)
1081                         ||  (nextvert == -1))
1082           {
1083
1084              /*   There is more than 2 polygons on the edge, and we could have
1085                   gotten the wrong one
1086              */
1087              if (nextvert != node->edge[1])
1088                   nextvert = node->edge[1];
1089              else
1090                   nextvert = node->edge[2];
1091              pListHead = PolFaces[nextvert];
1092              temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1093              numverts = temp2->nPolSize;
1094              if ((numverts != 4) || (temp2->seen == last_seen) )
1095              {
1096                   printf("Peel 2 %d\n",numverts);
1097                   exit(1);
1098              }
1099         }
1100
1101         face_id = nextvert;
1102         temp2->seen = last_seen;
1103
1104         counter = 0;
1105         flag = TRUE;
1106            while ((counter < 3) && (flag))
1107         {
1108              if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1109                    (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1110                   ((*(temp2->pPolygon+counter) == previous_edge2) ||
1111                    (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1112                    counter++;
1113              else
1114                   flag = FALSE;
1115         }
1116         /* Get the IDs of the next edge */
1117         if (counter < 3)
1118         {
1119              previous_edge1 = *(temp2->pPolygon + counter+1);
1120              previous_edge2 = *(temp2->pPolygon + counter);
1121         }
1122         else
1123         {
1124              previous_edge1 = *(temp2->pPolygon + counter);
1125              previous_edge2 = *(temp2->pPolygon);
1126         }
1127         orientation = counter;
1128
1129            node = *(temp2->VertandId + counter);
1130            if (node->edge[1] == nextvert)
1131                         nextvert = node->edge[2];
1132            else
1133                         nextvert = node->edge[1];
1134
1135            if (!reversed)
1136         {
1137                if (counter != 3)
1138                              north = counter +1;
1139                      else
1140                              north = 0;
1141         }
1142         else
1143         {
1144                if (counter != 0)
1145                     north = counter -1;
1146                else
1147                     north = 3;
1148         }
1149 }
1150
1151 if (start)
1152         tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1153                         color1,color2,color3,FALSE,swaps_added,norms,texture);
1154 else
1155      Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);/* do the last face */
1156
1157 last_seen++;
1158
1159 /*    Get the edge that we came out on the last strip of the patch */
1160 Mark_Face(NULL,0,0,0,output_file,TRUE,&end1,&end2,&last_id,norms,texture);
1161 tris += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1162 *swaps_added = *swaps_added + s;
1163 return tris;
1164 }
1165
1166
1167
1168 void Find_Bands(int numfaces, FILE *output_file, int *swaps, int *bands,
1169                 int *cost, int *tri, int norms, int *vert_norms, int texture, int *vert_texture)
1170 {
1171
1172         register int x,y,max1,max2,numverts,face_id,flag,maximum = 25;
1173         ListHead *pListHead;
1174         PF_FACES temp = NULL;
1175         int color1 = 0, color2 = 100, color3 = 255;
1176         int color = 0,larger,smaller;
1177         int north_length1,last_north,left_length1,last_left,north_length2,left_length2;
1178      int total_tri = 0, total_swaps = 0,last_id;
1179      int end1, end2,s=0;
1180      register int cutoff = 20;
1181
1182      /*   Code that will find the patches. "Cutoff" will be
1183           the cutoff of the area of the patches that we will be allowing. After
1184           we reach this cutoff length, then we will run the local algorithm on the
1185           remaining faces.
1186      */
1187
1188         /*      For each faces that is left find the largest possible band that we can
1189                 have with the remaining faces. Note that we will only be finding patches
1190           consisting of quads.
1191         */
1192
1193 vn = vert_norms;
1194 vt = vert_texture;
1195 y=1;
1196 *bands = 0;
1197
1198 while ((maximum >= cutoff))
1199 {
1200         y++;
1201      maximum = -1;
1202         for (x=0; x<numfaces; x++)
1203         {
1204
1205           /*   Used to produce the triangle strips */
1206
1207           /* for each face, get the face */
1208                 pListHead = PolFaces[x];
1209                 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1210                 numverts = temp->nPolSize;
1211
1212           /* we are doing this only for quads */
1213                 if (numverts == 4)
1214                 {
1215                         /*   We want a face that is has not been used yet,
1216                     since we know that that face must be part of
1217                                 a band. Then we will find the largest band that
1218                                 the face may be contained in
1219                         */
1220
1221                /*  Doing the north and the left */
1222                         if ((*(temp->walked) != -1) && (*(temp->walked+3) != -1))
1223                                 max1 = Find_Max(temp,x,0,3,&north_length1,&left_length1);
1224                         if ((*(temp->walked+1) != -1) && (*(temp->walked+2) != -1))
1225                                 max2 = Find_Max(temp,x,2,1,&north_length2,&left_length2);
1226                         if ((max1 != (north_length1 * left_length1)) ||
1227                             (max2 != (north_length2 * left_length2)))
1228                         {
1229                                 printf("Max1 %d, %d %d  Max2 %d, %d %d\n",max1,north_length1,left_length1,max2,north_length2,left_length2);
1230                                 exit(0);
1231                         }
1232
1233
1234                if ((max1 > max2) && (max1 > maximum))
1235                         {
1236                     maximum = max1;
1237                     face_id = x;
1238                     flag = 1;
1239                     last_north = north_length1;
1240                     last_left = left_length1;
1241                     /* so we know we saved max1 */
1242                         }
1243                         else if ((max2 > maximum) )
1244                         {
1245                     maximum = max2;
1246                     face_id = x;
1247                     flag = 2;
1248                     last_north = north_length2;
1249                     last_left = left_length2;
1250                     /* so we know we saved max2 */
1251                }
1252           }
1253      }
1254      if ((maximum < cutoff) && (*bands == 0))
1255           return;
1256      pListHead = PolFaces[face_id];
1257      temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1258      /*   There are no patches that we found in this pass */
1259      if (maximum == -1)
1260           break;
1261      /*printf("The maximum is  face %d area %d: lengths %d %d\n",face_id,maximum,last_north,last_left);*/
1262
1263      if (last_north > last_left)
1264      {
1265           larger = last_north;
1266           smaller = last_left;
1267      }
1268      else
1269      {
1270           larger = last_left;
1271           smaller = last_north;
1272      }
1273
1274      length = larger;
1275
1276 if (flag == 1)
1277 {
1278         if (last_north > last_left) /*     go north sequentially */
1279      {
1280           total_tri += Peel_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1281           Reset_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE);
1282           total_swaps += s;
1283      }
1284     else
1285     {
1286          reversed = TRUE;
1287          total_tri += Peel_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1288          Reset_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE);
1289          reversed = FALSE;
1290          total_swaps += s;
1291     }
1292
1293
1294     /*    Get the edge that we came out on the last strip of the patch */
1295     Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1296     total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1297     total_swaps += s;
1298
1299 }
1300 else
1301 {
1302      if (last_north > last_left)
1303      {
1304           total_tri += Peel_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1305           Reset_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE);
1306           total_swaps += s;
1307      }
1308      else
1309      {
1310           reversed = TRUE;
1311           total_tri += Peel_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1312           Reset_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE);
1313           reversed = FALSE;
1314           total_swaps += s;
1315      }
1316
1317      /*    Get the edge that we came out on on the patch */
1318     Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1319     total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1320     total_swaps += s;
1321 }
1322
1323     /*  Now compute the cost of transmitting this band, is equal to
1324         going across the larger portion sequentially,
1325         and swapping 3 times per other dimension
1326     */
1327
1328 total_tri += (maximum * 2);
1329 *bands = *bands + smaller;
1330
1331 }
1332
1333 /*printf("We transmitted %d triangles,using %d swaps and %d strips\n",total_tri,
1334         total_swaps, *bands);
1335 printf("COST %d\n",total_tri + total_swaps + *bands + *bands);*/
1336 *cost = total_tri + total_swaps + *bands + *bands;
1337 *tri = total_tri;
1338 added_quad = added_quad * 4;
1339 *swaps = total_swaps;
1340 }
1341
1342
1343 void Save_Rest(int *numfaces)
1344 {
1345     /*  Put the polygons that are left into a data structure so that we can run the
1346         stripping code on it.
1347     */
1348     register int x,y=0,numverts;
1349     ListHead *pListHead;
1350     PF_FACES temp=NULL;
1351
1352     for (x=0; x<*numfaces; x++)
1353     {
1354                         /* for each face, get the face */
1355                         pListHead = PolFaces[x];
1356                         temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1357                         numverts = temp->nPolSize;
1358                /*  If we did not do the face before add it to data structure with new
1359                    face id number
1360                */
1361                if (numverts != 1)
1362                {
1363                    CopyFace(temp->pPolygon,numverts,y+1,temp->pNorms);
1364                    y++;
1365                }
1366                /*   Used it, so remove it */
1367                else
1368                     RemoveList(pListHead,(PLISTINFO) temp);
1369
1370     }
1371     *numfaces = y;
1372 }
1373
1374 void Assign_Walk(int lastvert,PF_FACES temp2, int front_walk,int y,
1375                                 int back_walk)
1376 {
1377 /*      Go back and do the walk again, but this time save the lengths inside
1378         the data structure.
1379         y was the starting edge number for the front_walk length
1380         back_walk is the length of the walk along the opposite edge
1381  */
1382         int previous_edge1, previous_edge2;
1383         register int walk = 0,nextvert,numverts,counter;
1384         BOOL flag;
1385         F_EDGES *node;
1386         ListHead *pListHead;
1387         register int total_walk, start_back_walk;
1388         static int seen = 0;
1389         static BOOL first = TRUE;
1390         int test;
1391         BOOL f = TRUE, wrap = FALSE, set = FALSE;
1392              test = lastvert;
1393
1394         /*     In the "Fast_Reset" resetting will be true */
1395         if ((resetting) && (first))
1396         {
1397              seen = 0;
1398              first = FALSE;
1399         }
1400
1401         seen++;
1402         total_walk = front_walk + back_walk;
1403         start_back_walk = back_walk;
1404         /*     Had a band who could be a cycle  */
1405         if (front_walk == back_walk)
1406              wrap = TRUE;
1407
1408         /* Find the edge that we are currently on */
1409         if (y != 3)
1410         {
1411                 previous_edge1 = *(temp2->pPolygon +y);
1412                 previous_edge2 = *(temp2->pPolygon + y + 1);
1413         }
1414         else
1415         {
1416                 previous_edge1 = *(temp2->pPolygon +y);
1417                 previous_edge2 = *(temp2->pPolygon);
1418         }
1419
1420         /* Assign the lengths */
1421            if (y < 2)
1422            {
1423                 *(temp2->walked+y) = front_walk--;
1424                          *(temp2->walked+y+2) = back_walk++;
1425            }
1426            else
1427            {
1428                *(temp2->walked+y) = front_walk--;
1429                 *(temp2->walked+y-2) = back_walk++;
1430            }
1431
1432            /*Find the adjacent face to this edge */
1433         node = *(temp2->VertandId+y);
1434
1435         if (node->edge[2] != lastvert)
1436           nextvert = node->edge[2];
1437         else
1438           nextvert = node->edge[1];
1439
1440         temp2->seen3 = seen;
1441
1442         /* Keep walking in this direction until we cannot do so */
1443         while ((nextvert != lastvert) && (nextvert != -1) && (front_walk >= 0))
1444         {
1445                      walk++;
1446                pListHead = PolFaces[nextvert];
1447
1448                temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1449                numverts = temp2->nPolSize;
1450                if ((numverts != 4))
1451                {
1452                     nextvert = -1;
1453                     /* Don't include this face in the walk */
1454                     walk--;
1455                }
1456                else
1457                {
1458                     /* Find edge that is not adjacent to the previous one */
1459                     counter = 0;
1460                     flag = TRUE;
1461                     while ((counter < 3) && (flag))
1462                     {
1463                          if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1464                                (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1465                               ((*(temp2->pPolygon+counter) == previous_edge2) ||
1466                                (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1467                               counter++;
1468                          else
1469                               flag = FALSE;
1470                     }
1471                     /* Get the IDs of the next edge */
1472                     if (counter < 3)
1473                     {
1474                          previous_edge1 = *(temp2->pPolygon + counter);
1475                          previous_edge2 = *(temp2->pPolygon + counter + 1);
1476                     }
1477                     else
1478                     {
1479                          previous_edge1 = *(temp2->pPolygon + counter);
1480                          previous_edge2 = *(temp2->pPolygon);
1481                     }
1482
1483
1484                           /*      Put in the walk lengths */
1485                           if (counter < 2)
1486                           {
1487                         if (((*(temp2->walked + counter) >= 0)
1488                                   || (*(temp2->walked +counter + 2) >= 0)))
1489                                   {
1490                                           if ((resetting == FALSE) && ((temp2->seen3) != (seen-1)))
1491                                           {
1492                                                   /*   If there are more than 2 polygons adjacent
1493                                         to an edge then we can be trying to assign more than
1494                                         once. We will save the smaller one
1495                                    */
1496                                    temp2->seen3 = seen;
1497                                    if ( (*(temp2->walked+counter) <= front_walk) &&
1498                                         (*(temp2->walked+counter+2) <= back_walk) )
1499                                         return;
1500                                    if (*(temp2->walked+counter) > front_walk)
1501                                        *(temp2->walked+counter) = front_walk--;
1502                                    else
1503                                         front_walk--;
1504                                    if (*(temp2->walked+counter+2) > back_walk)
1505                                        *(temp2->walked+counter+2) = back_walk++;
1506                                    else
1507                                         back_walk++;
1508                                           }
1509                                           else if (resetting == FALSE)
1510                                           {
1511                                                   /* if there was a cycle then all lengths are the same */
1512                                                   walk--;
1513                                                   back_walk--;
1514                                                   front_walk++;
1515                                    temp2->seen3 = seen;
1516                                    *(temp2->walked+counter) = front_walk--;
1517                                    *(temp2->walked+counter+2) = back_walk++;
1518                               }
1519                               else if (((temp2->seen3 == (seen-1))
1520                                    && (wrap) && (walk == 1)) || (set))
1521                               {
1522                                                   /* if there was a cycle then all lengths are the same */
1523                                                   set = TRUE;
1524                                    walk--;
1525                                                   back_walk--;
1526                                                   front_walk++;
1527                                    temp2->seen3 = seen;
1528                                    *(temp2->walked+counter) = front_walk--;
1529                                    *(temp2->walked+counter+2) = back_walk++;
1530                               }
1531                               else
1532                               {
1533                                    temp2->seen3 = seen;
1534                                    *(temp2->walked+counter) = front_walk--;
1535                                    *(temp2->walked+counter+2) = back_walk++;
1536                               }
1537                         } /* if was > 0 */
1538                         else
1539                         {
1540                              temp2->seen3 = seen;
1541                              *(temp2->walked+counter) = front_walk--;
1542                              *(temp2->walked+counter+2) = back_walk++;
1543                         }
1544                     }
1545
1546                else
1547                {
1548                     if (((*(temp2->walked + counter) >= 0 )
1549                         || (*(temp2->walked +counter - 2) >= 0)) )
1550                     {
1551                          if ((temp2->seen3 != (seen-1))  && (resetting == FALSE))
1552                          {
1553                               /*   If there are more than 2 polygons adjacent
1554                                    to an edge then we can be trying to assign more than
1555                                    once. We will save the smaller one
1556                               */
1557                               temp2->seen3 = seen;
1558                               if ( (*(temp2->walked+counter) <= front_walk) &&
1559                                    (*(temp2->walked+counter-2) <= back_walk) )
1560                                    return;
1561                               if (*(temp2->walked+counter) > front_walk)
1562                                    *(temp2->walked+counter) = front_walk--;
1563                               else
1564                                    front_walk--;
1565                               if (*(temp2->walked+counter-2) > back_walk)
1566                                    *(temp2->walked+counter-2) = back_walk++;
1567                               else
1568                                    back_walk++;
1569                                 }
1570                                      else if (resetting == FALSE)
1571                                 {
1572                                         walk--;
1573                                         back_walk--;
1574                                         front_walk++;
1575                                  temp2->seen3 = seen;
1576                               *(temp2->walked+counter) = front_walk--;
1577                               *(temp2->walked+counter-2) = back_walk++;
1578                          }
1579                          else if (((temp2->seen3 == (seen-1)) && (walk == 1) && (wrap))
1580                               || (set))
1581                          {
1582                                              /* if there was a cycle then all lengths are the same */
1583                                              set = TRUE;
1584                               walk--;
1585                                              back_walk--;
1586                                              front_walk++;
1587                               temp2->seen3 = seen;
1588                               *(temp2->walked+counter) = front_walk--;
1589                               *(temp2->walked+counter-2) = back_walk++;
1590                          }
1591                          else
1592                          {
1593                               temp2->seen3 = seen;
1594                               *(temp2->walked+counter) = front_walk--;
1595                               *(temp2->walked+counter-2) = back_walk++;
1596                          }
1597                         }
1598                     else
1599                     {
1600                          temp2->seen3 = seen;
1601                          *(temp2->walked+counter) = front_walk--;
1602                          *(temp2->walked+counter-2) = back_walk++;
1603                     }
1604
1605                      }
1606                      if (nextvert != -1)
1607                      {
1608                              node = *(temp2->VertandId + counter);
1609                         if (node->edge[1] == nextvert)
1610                                 nextvert = node->edge[2];
1611                         else
1612                                 nextvert = node->edge[1];
1613                }
1614
1615      }
1616 }
1617 if ((EVEN(seen)) )
1618      seen+=2;
1619 }
1620
1621 void Save_Walks(int numfaces)
1622 {
1623         int x,y,numverts;
1624         int front_walk, back_walk;
1625         ListHead *pListHead;
1626         PF_FACES temp = NULL;
1627
1628         for (x=0; x<numfaces; x++)
1629         {
1630                 /* for each face, get the face */
1631                 pListHead = PolFaces[x];
1632                 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1633                 numverts = temp->nPolSize;
1634                 front_walk = 0;
1635           back_walk = 0;
1636
1637           /* we are finding patches only for quads */
1638                 if (numverts == 4)
1639                 {
1640                         /*      for each face not seen yet, do North and South together
1641                                 and East and West together
1642                         */
1643                         for (y=0;y<2;y++)
1644                         {
1645                                 /*   Check if the opposite sides were seen already from another
1646                          starting face, if they were then there is no need to do the walk again
1647                     */
1648
1649                                 if      ( ((*(temp->walked+y) == -1) &&
1650                                         (*(temp->walked+y+2) == -1) ))
1651                                 {
1652                                         /* Find walk for the first edge */
1653                                         front_walk = Calculate_Walks(x,y,temp);
1654                                         /* Find walk in the opposite direction */
1655                                         back_walk = Calculate_Walks(x,y+2,temp);
1656                                         /*      Now put into the data structure the numbers that
1657                                                 we have found
1658                                         */
1659                          Assign_Walk(x,temp,front_walk,y,back_walk);
1660                                         Assign_Walk(x,temp,back_walk,y+2,front_walk);
1661                         }
1662                         }
1663                 }
1664         }
1665 }
1666
1667