Stripe_u/common.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: common.c
  11      This file contains common code used in both the local and global algorithm
  12 */
  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 "util.h"
  22 #include "add.h"
  23
  24 int  Old_Adj(int face_id)
  25 {
  26         /*      Find the bucket that the face_id is currently in,
  27                 because maybe we will be deleting it.
  28         */
  29         PF_FACES temp = NULL;
  30         ListHead *pListHead;
  31         int size,y;
  32
  33         pListHead = PolFaces[face_id];
  34         temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  35         if ( temp == NULL )
  36         {
  37                 printf("The face was already deleted, there is an error\n");
  38                 exit(0);
  39         }
  40
  41         size = temp->nPolSize;
  42         if (Done(face_id,size,&y) == NULL)
  43         {
  44                 printf("There is an error in finding the face\n");
  45                 exit(0);
  46         }
  47         return y;
  48 }
  49
  50 int Number_Adj(int id1, int id2, int curr_id)
  51 {
  52         /*      Given edge whose endpoints are specified by id1 and id2,
  53                 determine how many polygons share this edge and return that
  54                 number minus one (since we do not want to include the polygon
  55                 that the caller has already).
  56         */
  57
  58         int size,y,count=0;
  59         PF_EDGES temp = NULL;
  60         PF_FACES temp2 = NULL;
  61         ListHead *pListHead;
  62         BOOL there= FALSE;
  63
  64         /*      Always want smaller id first */
  65         switch_lower(&id1,&id2);
  66
  67         pListHead = PolEdges[id1];
  68         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  69      if (temp == NULL)
  70      /* new edge that was created might not be here */
  71                 return 0;
  72         while (temp->edge[0] != id2)
  73      {
  74                 count++;
  75                 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  76           if (temp == NULL)
  77                         /*      This edge was not there in the original, which
  78                                 mean that we created it in the partial triangulation.
  79                                 So it is adjacent to nothing.
  80                         */
  81                         return 0;
  82         }
  83         /*      Was not adjacent to anything else except itself */
  84         if (temp->edge[2] == -1)
  85                 return 0;
  86         else
  87         {
  88                 /*      It was adjacent to another polygon, but maybe we did this
  89                         polygon already, and it was done partially so that this edge
  90                         could have been done
  91                 */
  92                 if (curr_id != temp->edge[1])
  93                 {
  94                         /*      Did we use this polygon already?and it was deleted
  95                                 completely from the structure
  96                         */
  97                         pListHead = PolFaces[temp->edge[1]];
  98                         temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  99                         if (Done(temp->edge[1],temp2->nPolSize,&size) == NULL)
 100                                 return 0;
 101                 }
 102                 else
 103                 {
 104                         pListHead = PolFaces[temp->edge[2]];
 105                         temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 106                         if (Done(temp->edge[2],temp2->nPolSize,&size)== NULL)
 107                                 return 0;
 108                 }
 109
 110                 /*      Now we have to check whether it was partially done, before
 111                         we can say definitely if it is adjacent.
 112                         Check each edge of the face and tally the number of adjacent
 113                         polygons to this face.
 114                 */
 115                 if ( temp2 != NULL )
 116                 {
 117                         /*      Size of the polygon */
 118                         size = temp2->nPolSize;
 119                         for (y = 0; y< size; y++)
 120                         {
 121                                 /*      If we are doing partial triangulation, we must check
 122                                         to see whether the edge is still there in the polygon,
 123                                         since we might have done a portion of the polygon
 124                                         and saved the rest for later.
 125                                 */
 126                                 if (y != (size-1))
 127                                 {
 128                                         if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
 129                                                 || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
 130                                                 /*      edge is still there we are ok */
 131                                                 there = TRUE;
 132                                 }
 133                                 else
 134                                 {
 135                                         if( ((id1 == *(temp2->pPolygon)) && (id2 == *(temp2->pPolygon+size-1)))
 136                                         || ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
 137                                         /*      edge is still there we are ok */
 138                                                 there = TRUE;
 139                                 }
 140                         }
 141                 }
 142
 143                 if (there )
 144                         return 1;
 145                 return 0;
 146         }
 147 }
 148
 149 int Min_Adj(int id)
 150 {
 151         /*      Used for the lookahead to break ties. It will
 152                 return the minimum adjacency found at this face.
 153         */
 154         int y,numverts,t,x=60;
 155         PF_FACES temp=NULL;
 156         ListHead *pListHead;
 157
 158         /*      If polygon was used then we can't use this face */
 159         if (Done(id,59,&y) == NULL)
 160                 return 60;
 161
 162         /*      It was not used already */
 163         pListHead = PolFaces[id];
 164         temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 165      if ( temp != NULL )
 166         {
 167                 numverts = temp->nPolSize;
 168                 for (y = 0; y< numverts; y++)
 169                 {
 170                         if (y != (numverts-1))
 171                                 t = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),id);
 172                         else
 173                                 t = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+(numverts-1)),id);
 174                         if (t < x)
 175                                 x = t;
 176                 }
 177         }
 178         if (x == -1)
 179         {
 180                 printf("Error in the look\n");
 181                 exit(0);
 182         }
 183         return x;
 184 }
 185
 186
 187
 188 void Edge_Least(int *index,int *new1,int *new2,int face_id,int size)
 189 {
 190     /*   We had a polygon without an input edge and now we re going to pick one
 191          of the edges with the least number of adjacencies to be the input
 192          edge
 193     */
 194     register int x,value,smallest=60;
 195
 196     for (x = 0; x<size; x++)
 197     {
 198         if (x != (size -1) )
 199             value = Number_Adj(*(index+x),*(index+x+1),face_id);
 200         else
 201             value = Number_Adj(*(index),*(index+size-1),face_id);
 202         if (value < smallest)
 203         {
 204             smallest = value;
 205             if (x != (size -1))
 206             {
 207                 *new1 = *(index+x);
 208                 *new2 = *(index+x+1);
 209             }
 210             else
 211             {
 212                 *new1 = *(index);
 213                 *new2 = *(index+size-1);
 214             }
 215         }
 216     }
 217     if ((smallest == 60) || (smallest < 0))
 218     {
 219         printf("There is an error in getting the least edge\n");
 220         exit(0);
 221     }
 222 }
 223
 224
 225 void Check_In_Polygon(int face_id, int *min, int size)
 226 {
 227     /*  Check to see the adjacencies by going into a polygon that has
 228         greater than 4 sides.
 229     */
 230
 231     ListHead *pListHead;
 232     PF_FACES temp;
 233     int y,id1,id2,id3,x=0,z=0;
 234     int saved[2];
 235     int big_saved[60];
 236
 237     pListHead = PolFaces[face_id];
 238     temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 239
 240     /*   Get the input edge that we came in on */
 241     Last_Edge(&id1,&id2,&id3,0);
 242
 243     /*  Find the number of adjacencies to the edges that are adjacent
 244         to the input edge.
 245     */
 246     for (y=0; y< size; y++)
 247     {
 248         if (y != (size-1))
 249         {
 250             if (((*(temp->pPolygon+y) == id2) && (*(temp->pPolygon+y+1) != id3))
 251                 || ((*(temp->pPolygon+y) == id3) && (*(temp->pPolygon+y+1) != id2)))
 252             {
 253                 saved[x++] = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),face_id);
 254                 big_saved[z++] = saved[x-1];
 255             }
 256             else
 257                 big_saved[z++] = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),face_id);
 258         }
 259         else
 260         {
 261             if (((*(temp->pPolygon) == id2) && (*(temp->pPolygon+size-1) != id3))
 262                 || ((*(temp->pPolygon) == id3) && (*(temp->pPolygon+size-1) != id2)))
 263             {
 264                 saved[x++] = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+size-1),face_id);
 265                 big_saved[z++] = saved[x-1];
 266             }
 267             else
 268                 big_saved[z++] = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+size-1),face_id);
 269         }
 270     }
 271     /*  There was an input edge */
 272     if (x == 2)
 273     {
 274         if (saved[0] < saved[1])
 275             /*  Count the polygon that we will be cutting as another adjacency*/
 276             *min = saved[0] + 1;
 277         else
 278             *min = saved[1] + 1;
 279     }
 280     /*  There was not an input edge */
 281     else
 282     {
 283         if (z != size)
 284         {
 285             printf("There is an error with the z %d %d\n",size,z);
 286             exit(0);
 287         }
 288         *min = 60;
 289         for (x = 0; x < size; x++)
 290         {
 291             if (*min > big_saved[x])
 292                 *min = big_saved[x];
 293         }
 294     }
 295 }
 296
 297
 298 void New_Face (int face_id, int v1, int v2, int v3)
 299 {
 300         /*      We want to change the face that was face_id, we will
 301                 change it to a triangle, since the rest of the polygon
 302                 was already outputtted
 303         */
 304         ListHead *pListHead;
 305         PF_FACES temp = NULL;
 306
 307         pListHead = PolFaces[face_id];
 308      temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0);
 309         /*      Check each edge of the face and tally the number of adjacent
 310                 polygons to this face.
 311         */
 312         if ( temp != NULL )
 313         {
 314                 /*      Size of the polygon */
 315                 if (temp->nPolSize != 4)
 316                 {
 317                         printf("There is a miscalculation in the partial\n");
 318                         exit (0);
 319                 }
 320                 temp->nPolSize = 3;
 321                 *(temp->pPolygon) = v1;
 322                 *(temp->pPolygon+1) = v2;
 323                 *(temp->pPolygon+2) = v3;
 324         }
 325 }
 326
 327 void New_Size_Face (int face_id)
 328 {
 329         /*      We want to change the face that was face_id, we will
 330                 change it to a triangle, since the rest of the polygon
 331                 was already outputtted
 332         */
 333         ListHead *pListHead;
 334         PF_FACES temp = NULL;
 335
 336         pListHead = PolFaces[face_id];
 337         temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 338         /*      Check each edge of the face and tally the number of adjacent
 339                 polygons to this face.
 340         */
 341         if ( temp != NULL )
 342                 (temp->nPolSize)--;
 343         else
 344                 printf("There is an error in updating the size\n");
 345 }
 346
 347
 348
 349 void  Check_In_Quad(int face_id,int *min)
 350 {
 351      /*   Check to see what the adjacencies are for the polygons that
 352           are inside the quad, ie the 2 triangles that we can form.
 353      */
 354     ListHead *pListHead;
 355     int y,id1,id2,id3,x=0;
 356     int saved[4];
 357     PF_FACES temp;
 358     register int size = 4;
 359
 360     pListHead = PolFaces[face_id];
 361     temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 362
 363      /*   Get the input edge that we came in on */
 364     Last_Edge(&id1,&id2,&id3,0);
 365
 366     /*    Now find the adjacencies for the inside triangles */
 367     for (y = 0; y< size; y++)
 368         {
 369          /*     Will not do this if the edge is the input edge */
 370          if (y != (size-1))
 371          {
 372               if ((((*(temp->pPolygon+y) == id2) && (*(temp->pPolygon+y+1) == id3))) ||
 373              (((*(temp->pPolygon+y) == id3) && (*(temp->pPolygon+y+1) == id2))))
 374                     saved[x++] = -1;
 375               else
 376               {
 377                    if (x == 4)
 378                    {
 379                         printf("There is an error in the check in quad \n");
 380                         exit(0);
 381                    }
 382                    /*    Save the number of Adjacent Polygons to this edge */
 383                    saved[x++] = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),face_id);
 384               }
 385          }
 386                 else if ((((*(temp->pPolygon) == id2) && (*(temp->pPolygon+size-1) == id3))) ||
 387              (((*(temp->pPolygon) == id3) && (*(temp->pPolygon+size-1) == id2))) )
 388              saved[x++] = -1;
 389         else
 390         {
 391                if (x == 4)
 392                {
 393                     printf("There is an error in the check in quad \n");
 394                     exit(0);
 395                }
 396                /*    Save the number of Adjacent Polygons to this edge */
 397                saved[x++] = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+size-1),face_id);
 398
 399         }
 400     }
 401     if (x != 4)
 402     {
 403          printf("Did not enter all the values %d \n",x);
 404          exit(0);
 405     }
 406
 407     *min = 10;
 408     for (x=0; x<4; x++)
 409     {
 410          if (x!= 3)
 411          {
 412               if ((saved[x] != -1) && (saved[x+1] != -1) &&
 413                    ((saved[x] + saved[x+1]) < *min))
 414                    *min = saved[x] + saved[x+1];
 415          }
 416          else
 417          {
 418               if ((saved[0] != -1) && (saved[x] != -1) &&
 419                    ((saved[x] + saved[0]) < *min))
 420                    *min = saved[0] + saved[x];
 421          }
 422     }
 423 }
 424
 425
 426
 427 int Get_Output_Edge(int face_id, int size, int *index,int id2,int id3)
 428 {
 429     /*  Return the vertex adjacent to either input1 or input2 that
 430         is adjacent to the least number of polygons on the edge that
 431         is shared with either input1 or input2.
 432     */
 433     register int x=0,y;
 434     int saved[2];
 435     int edges[2][1];
 436
 437     for (y = 0; y < size; y++)
 438     {
 439         if (y != (size-1))
 440         {
 441             if (((*(index+y) == id2) && (*(index+y+1) != id3))
 442                 || ((*(index+y) == id3) && (*(index+y+1) != id2)))
 443             {
 444                 saved[x++] = Number_Adj(*(index+y),*(index+y+1),face_id);
 445                 edges[x-1][0] = *(index+y+1);
 446             }
 447             else if (y != 0)
 448             {
 449                 if (( (*(index+y) == id2) && (*(index+y-1) != id3) ) ||
 450                     ( (*(index+y) == id3) && (*(index+y-1) != id2)) )
 451                 {
 452                     saved[x++] = Number_Adj(*(index+y),*(index+y-1),face_id);
 453                     edges[x-1][0] = *(index+y-1);
 454                 }
 455             }
 456             else if (y == 0)
 457             {
 458                 if (( (*(index) == id2) && (*(index+size-1) != id3) ) ||
 459                     ( (*(index) == id3) && (*(index+size-1) != id2)) )
 460                 {
 461                     saved[x++] = Number_Adj(*(index),*(index+size-1),face_id);
 462                     edges[x-1][0] = *(index+size-1);
 463                 }
 464             }
 465
 466         }
 467         else
 468         {
 469             if (((*(index+size-1) == id2) && (*(index) != id3))
 470                 || ((*(index+size-1) == id3) && (*(index) != id2)))
 471             {
 472                 saved[x++] = Number_Adj(*(index),*(index+size-1),face_id);
 473                 edges[x-1][0] = *(index);
 474             }
 475
 476             if (( (*(index+size-1) == id2) && (*(index+y-1) != id3) ) ||
 477                     ( (*(index+size-1) == id3) && (*(index+y-1) != id2)) )
 478                 {
 479                     saved[x++] = Number_Adj(*(index+size-1),*(index+y-1),face_id);
 480                     edges[x-1][0] = *(index+y-1);
 481                 }
 482         }
 483     }
 484     if ((x != 2))
 485     {
 486         printf("There is an error in getting the input edge %d \n",x);
 487         exit(0);
 488     }
 489     if (saved[0] < saved[1])
 490         return edges[0][0];
 491     else
 492         return edges[1][0];
 493
 494 }
 495
 496 void Get_Input_Edge(int *index,int id1,int id2,int id3,int *new1,int *new2,int size,
 497                     int face_id)
 498 {
 499     /*  We had a polygon without an input edge and now we are going to pick one
 500         as the input edge. The last triangle was id1,id2,id3, we will try to
 501         get an edge to have something in common with one of those vertices, otherwise
 502         we will pick the edge with the least number of adjacencies.
 503     */
 504
 505     register int x;
 506     int saved[3];
 507
 508     saved[0] = -1;
 509     saved[1] = -1;
 510     saved[2] = -1;
 511
 512     /*  Go through the edges to see if there is one in common with one
 513         of the vertices of the last triangle that we had, preferably id2 or
 514         id3 since those are the last 2 things in the stack of size 2.
 515     */
 516     for (x=0; x< size; x++)
 517     {
 518         if (*(index+x) == id1)
 519         {
 520             if (x != (size-1))
 521                 saved[0] = *(index+x+1);
 522             else
 523                 saved[0] = *(index);
 524         }
 525
 526         if (*(index+x) == id2)
 527         {
 528             if (x != (size-1))
 529                 saved[1] = *(index+x+1);
 530             else
 531                 saved[1] = *(index);
 532         }
 533
 534         if (*(index+x) == id3)
 535         {
 536             if (x != (size -1))
 537                 saved[2] = *(index+x+1);
 538             else
 539                 saved[2] = *(index);
 540         }
 541     }
 542     /*  Now see what we saved */
 543     if (saved[2] != -1)
 544     {
 545         *new1 = id3;
 546         *new2 = saved[2];
 547         return;
 548     }
 549     else if (saved[1] != -1)
 550     {
 551         *new1 = id2;
 552         *new2 = saved[1];
 553         return;
 554     }
 555     else if (saved[0] != -1)
 556     {
 557         *new1 = id1;
 558         *new2 = saved[0];
 559         return;
 560     }
 561     /*  We did not find anything so get the edge with the least number of adjacencies */
 562     Edge_Least(index,new1,new2,face_id,size);
 563
 564 }
 565
 566 int Find_Face(int current_face, int id1, int id2, int *bucket)
 567 {
 568         /*      Find the face that is adjacent to the edge and is not the
 569                 current face.
 570         */
 571         register int size,each_poly=0,y,tally=0,count=0;
 572         PF_EDGES temp = NULL;
 573         PF_FACES temp2 = NULL;
 574         ListHead *pListHead;
 575         int next_face;
 576         BOOL there = FALSE;
 577
 578
 579     /*  Always want smaller id first */
 580         switch_lower(&id1,&id2);
 581
 582         pListHead = PolEdges[id1];
 583         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 584      /*  The input edge was a new edge */
 585      if (temp == NULL)
 586         return -1;
 587
 588      while (temp->edge[0] != id2)
 589      {
 590                 count++;
 591                 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 592           /*  The input edge was a new edge */
 593           if (temp == NULL)
 594             return -1;
 595      }
 596         /*      Was not adjacent to anything else except itself */
 597         if (temp->edge[2] == -1)
 598                 return -1;
 599         else
 600         {
 601                 if (temp->edge[2] == current_face)
 602                         next_face =  temp->edge[1];
 603                 else
 604                         next_face = temp->edge[2];
 605         }
 606         /*      We have the other face adjacent to this edge, it is
 607                 next_face.
 608         */
 609         pListHead = PolFaces[next_face];
 610         temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 611
 612      /* See if the face was already deleted, and where
 613               it is if it was not
 614      */
 615
 616      if (Done(next_face,59,bucket) == NULL)
 617         return -1;
 618
 619      /*  Make sure the edge is still in this polygon, and that it is not
 620          done
 621      */
 622                 /*      Size of the polygon */
 623                 size = temp2->nPolSize;
 624                 for (y = 0; y< size; y++)
 625                 {
 626                         /*      Make sure that the edge is still in the
 627                                 polygon and was not deleted, because if the edge was
 628                                 deleted, then we used it already.
 629                         */
 630                         if (y != (size-1))
 631                         {
 632                                 if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
 633                                         || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
 634                                         /*      edge is still there we are ok */
 635                                         there = TRUE;
 636                         }
 637                         else
 638                         {
 639                                 if( ((id1 == *(temp2->pPolygon)) && (id2 ==*(temp2->pPolygon+size-1)))
 640                                         || ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
 641                                         /*      edge is still there we are ok */
 642                                         there = TRUE;
 643                         }
 644                 }
 645
 646                 if (!there)
 647                         /*      Edge already used and deleted from the polygon*/
 648                         return -1;
 649          else
 650             return next_face;
 651 }
 652
 653 BOOL Look_Up(int id1,int id2,int face_id)
 654 {
 655         /*      See if the endpoints of the edge specified by id1 and id2
 656                 are adjacent to the face with face_id
 657         */
 658         register int count = 0;
 659         PF_EDGES temp  = NULL;
 660         ListHead *pListHead;
 661         PF_FACES temp2 = NULL;
 662
 663         /*      Always want smaller id first */
 664         switch_lower(&id1,&id2);
 665
 666         pListHead = PolEdges[id1];
 667         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 668      if (temp == NULL)
 669      /* Was a new edge that we created */
 670                 return 0;
 671
 672         while (temp->edge[0] != id2)
 673      {
 674                 count++;
 675                 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 676           if (temp == NULL)
 677                         /*      Was a new edge that we created */
 678                         return 0;
 679      }
 680         /*      Was not adjacent to anything else except itself */
 681         if ((temp->edge[2] == face_id) || (temp->edge[1] == face_id))
 682         {
 683                 /*      Edge was adjacent to face, make sure that edge is
 684                         still there
 685                 */
 686                 if (Exist(face_id,id1,id2))
 687                         return 1;
 688                 else
 689                         return 0;
 690         }
 691         else
 692                 return 0;
 693 }
 694
 695
 696 void Add_Id_Strips(int id, int where)
 697 {
 698      /*    Just save the triangle for later  */
 699      P_STRIPS pfNode;
 700
 701         pfNode = (P_STRIPS) malloc(sizeof(Strips) );
 702         if ( pfNode )
 703         {
 704              pfNode->face_id = id;
 705              if (where == 1)
 706                  AddTail(strips[0],(PLISTINFO) pfNode);
 707              /* We are backtracking in the strip */
 708              else
 709                  AddHead(strips[0],(PLISTINFO) pfNode);
 710         }
 711         else
 712         {
 713              printf("There is not enough memory to allocate for the strips\n");
 714              exit(0);
 715         }
 716 }
 717
 718
 719 int Num_Adj(int id1, int id2)
 720 {
 721         /*   Given edge whose endpoints are specified by id1 and id2,
 722                 determine how many polygons share this edge and return that
 723                 number minus one (since we do not want to include the polygon
 724                 that the caller has already).
 725         */
 726
 727         PF_EDGES temp = NULL;
 728         ListHead *pListHead;
 729         register count=-1;
 730
 731         /*      Always want smaller id first */
 732         switch_lower(&id1,&id2);
 733
 734         pListHead = PolEdges[id1];
 735         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 736      if (temp == NULL)
 737         {
 738                 printf("There is an error in the creation of the table \n");
 739                 exit(0);
 740         }
 741         while (temp->edge[0] != id2)
 742      {
 743                 count++;
 744                 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 745              if (temp == NULL)
 746                 {
 747                         printf("There is an error in the creation of the table\n");
 748                         exit(0);
 749                 }
 750         }
 751         /*      Was not adjacent to anything else except itself */
 752         if (temp->edge[2] == -1)
 753                 return 0;
 754         return 1;
 755 }
 756
 757
 758 void Add_Sgi_Adj(int bucket,int face_id)
 759 {
 760         /*   This routine will add the face to the proper bucket,
 761                 depending on how many faces are adjacent to it (what the
 762                 value bucket should be).
 763         */
 764         P_ADJACENCIES pfNode;
 765
 766         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 767      if ( pfNode )
 768      {
 769                 pfNode->face_id = face_id;
 770              AddHead(array[bucket],(PLISTINFO) pfNode);
 771         }
 772         else
 773         {
 774                 printf("Out of memory for the SGI adj list!\n");
 775                 exit(0);
 776         }
 777 }
 778
 779 void Find_Adjacencies(int num_faces)
 780 {
 781      register int       x,y;
 782      register int       numverts;
 783      PF_FACES temp=NULL;
 784      ListHead *pListHead;
 785
 786         /*   Fill in the adjacencies data structure for all the faces */
 787      for (x=0;x<num_faces;x++)
 788         {
 789                 pListHead = PolFaces[x];
 790                 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 791         if ( temp != NULL )
 792                 {
 793                         numverts = temp->nPolSize;
 794                         if (numverts != 1)
 795                {
 796                     for (y = 0; y< numverts; y++)
 797                              {
 798                                      if (y != (numverts-1))
 799                                              Add_AdjEdge(*(temp->pPolygon+y),*(temp->pPolygon+y+1),x,y);
 800
 801                                      else
 802                                              Add_AdjEdge(*(temp->pPolygon),*(temp->pPolygon+(numverts-1)),x,numverts-1);
 803
 804                     }
 805                }
 806                         temp = NULL;
 807                 }
 808         }
 809 }
 810
 811