Stripe_w/struct.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: struct.c
  11      Contains routines that update structures, and micellaneous routines.
  12 */
  13 /*---------------------------------------------------------------------*/
  14
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include "polverts.h"
  18 #include "ties.h"
  19 #include "output.h"
  20 #include "triangulate.h"
  21 #include "sturcts.h"
  22 #include "options.h"
  23 #include "common.h"
  24 #include "util.h"
  25
  26 int out1 = -1;
  27 int out2 = -1;
  28
  29 int Get_Edge(int *edge1,int *edge2,int *index,int face_id,
  30                 int size, int id1, int id2)
  31 {
  32         /*      Put the edge that is adjacent to face_id into edge1
  33                 and edge2. For each edge see if it is adjacent to
  34                 face_id. Id1 and id2 is the input edge, so see if
  35                 the orientation is reversed, and save it in reversed.
  36         */
  37         register int x;
  38         int reversed = -1;
  39         BOOL set = FALSE;
  40
  41      for (x=0; x< size; x++)
  42         {
  43                 if (x == (size-1))
  44                 {
  45                         if ((*(index) == id1) && (*(index+size-1)==id2))
  46                         {
  47                                 if (set)
  48                          return 1;
  49                                 reversed = 1;
  50                         }
  51                         else if ((*(index) == id2) && (*(index+size-1)==id1))
  52                         {
  53                                 if (set)
  54                          return 0;
  55                                 reversed = 0;
  56                         }
  57
  58                         if (Look_Up(*(index),*(index+size-1),face_id))
  59                         {
  60                                 if ( (out1 != -1) && ( (out1 == *(index)) || (out1 == *(index+size-1)) ) &&
  61                        ( (out2 == *(index)) || (out2 == *(index+size-1)) ))
  62                     {
  63                          set = TRUE;
  64                          *edge1 = *(index);
  65                          *edge2 = *(index+size-1);
  66                     }
  67                                 else if (out1 == -1)
  68                     {
  69                          set = TRUE;
  70                          *edge1 = *(index);
  71                          *edge2 = *(index+size-1);
  72                     }
  73                                 if ((reversed != -1) && (set))
  74                                         return reversed;
  75                         }
  76                 }
  77                 else
  78                 {
  79                         if ((*(index+x) == id1) && (*(index+x+1)==id2))
  80                         {
  81                                 if (set)
  82                          return 0;
  83                                 reversed = 0;
  84                         }
  85                         else if ((*(index+x) == id2) && (*(index+x+1)==id1))
  86                         {
  87                                 if (set)
  88                                         return 1;
  89                                 reversed = 1;
  90                         }
  91
  92                         if (Look_Up(*(index+x),*(index+x+1),face_id))
  93                         {
  94                                 if ( (out1 != -1) && ( (out1 == *(index+x)) || (out1 == *(index+x+1)) ) &&
  95                          ((out2 == *(index+x)) || (out2 == *(index+x+1))))
  96                     {
  97                          set = TRUE;
  98                          *edge1 = *(index+x);
  99                          *edge2 = *(index+x+1);
 100                     }
 101                                 else if (out1 == -1)
 102                     {
 103                          set = TRUE;
 104                          *edge1 = *(index+x);
 105                                      *edge2 = *(index+x + 1);
 106                     }
 107                                 if ((reversed != -1) && (set))
 108                          return reversed;
 109                         }
 110                 }
 111         }
 112         if ((x == size) && (reversed != -1))
 113         {
 114                 /*      Could not find the output edge */
 115                 printf("Error in the Lookup %d %d %d %d %d %d %d %d\n",face_id,id1,id2,reversed,*edge1,*edge2,out1,out2);
 116                 exit(0);
 117         }
 118         return reversed;
 119 }
 120
 121
 122 void Update_Face(int *next_bucket, int *min_face, int face_id, int *e1,
 123                                  int *e2,int temp1,int temp2,int *ties)
 124 {
 125         /*      We have a face id that needs to be decremented.
 126                 We have to determine where it is in the structure,
 127                 so that we can decrement it.
 128         */
 129         /*      The number of adjacencies may have changed, so to locate
 130                 it may be a little tricky. However we know that the number
 131                 of adjacencies is less than or equal to the original number
 132                 of adjacencies,
 133         */
 134         int y,size;
 135         ListHead *pListHead;
 136         PF_FACES temp = NULL;
 137         PLISTINFO lpListInfo;
 138         static int each_poly = 0;
 139         BOOL there = FALSE;
 140
 141         pListHead = PolFaces[face_id];
 142         temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 143         /*      Check each edge of the face and tally the number of adjacent
 144                 polygons to this face.
 145         */
 146         if ( temp != NULL )
 147         {
 148                 /*      Size of the polygon */
 149         size = temp->nPolSize;
 150         /*  We did it already */
 151         if (size == 1)
 152             return;
 153         for (y = 0; y< size; y++)
 154            {
 155                         /*      If we are doing partial triangulation, we must check
 156                                 to see whether the edge is still there in the polygon,
 157                                 since we might have done a portion of the polygon
 158                                 and saved the rest for later.
 159                         */
 160             if (y != (size-1))
 161                   {
 162                                 if( ((temp1 == *(temp->pPolygon+y)) && (temp2 ==*(temp->pPolygon+y+1)))
 163                                         || ((temp2 == *(temp->pPolygon+y)) && (temp1 ==*(temp->pPolygon+y+1))))
 164                                         /*      edge is still there we are ok */
 165                                         there = TRUE;
 166                   }
 167                   else
 168                   {
 169                                 if( ((temp1 == *(temp->pPolygon)) && (temp2 == *(temp->pPolygon+size-1)))
 170                                         || ((temp2 == *(temp->pPolygon)) && (temp1 ==*(temp->pPolygon+size-1))))
 171                                         /*      edge is still there we are ok */
 172                                         there = TRUE;
 173                   }
 174          }
 175
 176       if (!there)
 177                 /*      Original edge was already used, we cannot use this polygon */
 178                         return;
 179
 180         /*      We have a starting point to start our search to locate
 181                 this polygon.
 182         */
 183
 184         /*      Check to see if this polygon was done */
 185         lpListInfo = Done(face_id,59,&y);
 186
 187         if (lpListInfo == NULL)
 188                 return;
 189
 190      /*  Was not done, but there is an error in the adjacency calculations */
 191      if (y == 0)
 192      {
 193             printf("There is an error in finding the adjacencies\n");
 194             exit(0);
 195      }
 196
 197      /* Now put the face in the proper bucket depending on tally. */
 198         /*      First add it to the new bucket, then remove it from the old */
 199         Add_Sgi_Adj(y-1,face_id);
 200         RemoveList(array[y],lpListInfo);
 201
 202      /* Save it if it was the smallest seen so far since then
 203                 it will be the next face
 204                 Here we will have different options depending on
 205                 what we want for resolving ties:
 206                         1) First one we see we will use
 207                         2) Random resolving
 208                         3) Look ahead
 209                         4) Alternating direction
 210         */
 211         /*      At a new strip */
 212         if (*next_bucket == 60)
 213                 *ties = *ties + each_poly;
 214         /*      Have a tie */
 215         if (*next_bucket == (y-1))
 216         {
 217                 Add_Ties(face_id);
 218                 each_poly++;
 219         }
 220         /*      At a new minimum */
 221         if (*next_bucket > (y-1))
 222         {
 223                 *next_bucket = y-1;
 224                 *min_face = face_id;
 225                 *e1 = temp1;
 226                 *e2 = temp2;
 227                 each_poly = 0;
 228                 Clear_Ties();
 229                 Add_Ties(face_id);
 230         }
 231      }
 232 }
 233
 234
 235 void Delete_Adj(int id1, int id2,int *next_bucket,int *min_face,
 236                          int current_face,int *e1,int *e2,int *ties)
 237 {
 238         /*      Find the face that is adjacent to the edge and is not the
 239                 current face. Delete one adjacency from it. Save the min
 240                 adjacency seen so far.
 241         */
 242         register int count=0;
 243         PF_EDGES temp = NULL;
 244         ListHead *pListHead;
 245         int next_face;
 246
 247         /*      Always want smaller id first */
 248         switch_lower(&id1,&id2);
 249
 250         pListHead = PolEdges[id1];
 251         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 252      if (temp == NULL)
 253         /*      It could be a new edge that we created. So we can
 254                 exit, since there is not a face adjacent to it.
 255         */
 256                 return;
 257         while (temp->edge[0] != id2)
 258      {
 259                 count++;
 260                 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 261           if (temp == NULL)
 262                         /*      Was a new edge that was created and therefore
 263                                 does not have anything adjacent to it
 264                         */
 265                         return;
 266      }
 267         /*      Was not adjacent to anything else except itself */
 268         if (temp->edge[2] == -1)
 269                 return;
 270
 271         /*      Was adjacent to something */
 272         else
 273         {
 274                 if (temp->edge[2] == current_face)
 275                         next_face =  temp->edge[1];
 276                 else
 277                         next_face = temp->edge[2];
 278         }
 279         /*      We have the other face adjacent to this edge, it is
 280                 next_face. Now we need to decrement this faces' adjacencies.
 281         */
 282         Update_Face(next_bucket, min_face, next_face,e1,e2,id1,id2,ties);
 283 }
 284
 285
 286 int Change_Face(int face_id,int in1,int in2,
 287                                  ListHead *pListHead, P_ADJACENCIES temp, BOOL no_check)
 288 {
 289         /*      We are doing a partial triangulation and we need to
 290                 put the new face of triangle into the correct bucket
 291         */
 292         int input_adj,y;
 293
 294         /*      Find the old number of adjacencies to this face,
 295                 so we know where to delete it from
 296         */
 297         y = Old_Adj(face_id);
 298
 299         /*      Do we need to change the adjacency? Maybe the edge on the triangle
 300                 that was outputted was not adjacent to anything. We know if we
 301                 have to check by "check". We came out on the output edge
 302                 that we needed, then we know that the adjacencies will decrease
 303                 by exactly one.
 304         */
 305         if (!no_check)
 306         {
 307                 input_adj = Number_Adj(in1,in2,face_id);
 308                 /*      If there weren't any then don't do anything */
 309                 if (input_adj == 0)
 310                         return y;
 311         }
 312
 313         RemoveList(pListHead,(PLISTINFO)temp);
 314         /*      Before we had a quad with y adjacencies. The in edge
 315                 did not have an adjacency, since it was just deleted,
 316                 since we came in on it. The outedge must have an adjacency
 317                 otherwise we would have a bucket 0, and would not be in this
 318                 routine. Therefore the new adjacency must be y-1
 319         */
 320
 321     Add_Sgi_Adj(y-1,face_id);
 322     return (y-1);
 323 }
 324
 325 int Update_Adjacencies(int face_id, int *next_bucket, int *e1, int *e2,
 326                                            int *ties)
 327 {
 328         /*      Give the face with id face_id, we want to decrement
 329                 all the faces that are adjacent to it, since we will
 330                 be deleting face_id from the data structure.
 331                 We will return the face that has the least number
 332                 of adjacencies.
 333         */
 334         PF_FACES temp = NULL;
 335         ListHead *pListHead;
 336         int size,y,min_face = -1;
 337
 338      *next_bucket = 60;
 339         pListHead = PolFaces[face_id];
 340         temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 341
 342         if ( temp == NULL )
 343         {
 344                 printf("The face was already deleted, there is an error\n");
 345                 exit(0);
 346         }
 347
 348         /*      Size of the polygon */
 349         size = temp->nPolSize;
 350         for (y = 0; y< size; y++)
 351         {
 352                 if (y != (size-1))
 353                         Delete_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
 354                                 next_bucket,&min_face,face_id,e1,e2,ties);
 355                 else
 356                         Delete_Adj(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
 357                                 next_bucket,&min_face,face_id,e1,e2,ties);
 358         }
 359         return (min_face);
 360 }
 361
 362
 363 void Find_Adj_Tally(int id1, int id2,int *next_bucket,int *min_face,
 364                                 int current_face,int *ties)
 365 {
 366         /*      Find the face that is adjacent to the edge and is not the
 367                 current face. Save the min adjacency seen so far.
 368         */
 369         int size,each_poly=0,y,count=0;
 370         PF_EDGES temp = NULL;
 371         PF_FACES temp2 = NULL;
 372         ListHead *pListHead;
 373         int next_face;
 374         BOOL there = FALSE;
 375
 376
 377     /*  Always want smaller id first */
 378         switch_lower(&id1,&id2);
 379
 380         pListHead = PolEdges[id1];
 381         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 382      if (temp == NULL)
 383      /* This was a new edge that was created, so it is
 384                 adjacent to nothing.
 385         */
 386                 return;
 387
 388         while (temp->edge[0] != id2)
 389      {
 390                 count++;
 391                 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 392           if (temp == NULL)
 393                         /*      This was a new edge that we created */
 394                         return;
 395      }
 396         /*      Was not adjacent to anything else except itself */
 397         if (temp->edge[2] == -1)
 398                 return;
 399         else
 400         {
 401                 if (temp->edge[2] == current_face)
 402                         next_face =  temp->edge[1];
 403                 else
 404                         next_face = temp->edge[2];
 405         }
 406         /*      We have the other face adjacent to this edge, it is
 407                 next_face. Find how many faces it is adjacent to.
 408         */
 409         pListHead = PolFaces[next_face];
 410         temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 411         /*      Check each edge of the face and tally the number of adjacent
 412                 polygons to this face. This will be the original number of
 413                 polygons adjacent to this polygon, we must then see if this
 414                 number has been decremented
 415         */
 416         if ( temp2 != NULL )
 417         {
 418                 /*      Size of the polygon */
 419                 size = temp2->nPolSize;
 420                 /*  We did it already */
 421           if (size == 1)
 422             return;
 423           for (y = 0; y< size; y++)
 424                 {
 425                         /*      Make sure that the edge is still in the
 426                                 polygon and was not deleted, because if the edge was
 427                                 deleted, then we used it already.
 428                         */
 429                         if (y != (size-1))
 430                         {
 431                                 if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
 432                                         || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
 433                                         /*      edge is still there we are ok */
 434                                         there = TRUE;
 435                         }
 436                         else
 437                         {
 438                                 if( ((id1 == *(temp2->pPolygon)) && (id2 ==*(temp2->pPolygon+size-1)))
 439                                         || ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
 440                                         /*      edge is still there we are ok */
 441                                         there = TRUE;
 442                         }
 443                 }
 444
 445                 if (!there)
 446                         /*      Edge already used and deleted from the polygon*/
 447                         return;
 448
 449                 /*      See if the face was already deleted, and where
 450                         it is if it was not
 451                 */
 452                 if (Done(next_face,size,&y) == NULL)
 453                         return;
 454
 455                 /*      Save it if it was the smallest seen so far since then
 456                         it will be the next face
 457                         Here we will have different options depending on
 458                         what we want for resolving ties:
 459                         1) First one we see we will use
 460                         2) Random resolving
 461                         3) Look ahead
 462                         4) Alternating direction
 463                 */
 464
 465                 /*      At a new strip */
 466                 if (*next_bucket == 60)
 467                         *ties = *ties + each_poly;
 468                 /*      Have a tie */
 469                 if (*next_bucket == (y-1))
 470                 {
 471                         Add_Ties(next_face);
 472                         each_poly++;
 473                 }
 474                 /*      At a new minimum */
 475                 if (*next_bucket > (y-1))
 476                 {
 477                         *next_bucket = y-1;
 478                         *min_face = next_face;
 479                         each_poly = 0;
 480                         Clear_Ties();
 481                         Add_Ties(next_face);
 482                 }
 483         }
 484 }
 485
 486
 487 int Min_Face_Adj(int face_id, int *next_bucket, int *ties)
 488 {
 489         /*      Used for the Partial triangulation to find the next
 490                 face. It will return the minimum adjacency face id
 491                 found at this face.
 492         */
 493         PF_FACES temp = NULL;
 494         ListHead *pListHead;
 495         int size,y,min_face,test_face;
 496
 497         *next_bucket = 60;
 498         pListHead = PolFaces[face_id];
 499         temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 500
 501         if ( temp == NULL )
 502         {
 503                 printf("The face was already deleted, there is an error\n");
 504                 exit(0);
 505         }
 506
 507         /*      Size of the polygon */
 508         size = temp->nPolSize;
 509         for (y = 0; y< size; y++)
 510         {
 511                 if (y != (size-1))
 512                         Find_Adj_Tally(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
 513                                 next_bucket,&min_face,face_id,ties);
 514                 else
 515                         Find_Adj_Tally(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
 516                                 next_bucket,&min_face,face_id,ties);
 517         }
 518         /*    Maybe we can do better by triangulating the face, because
 519           by triangulating the face we will go to a polygon of lesser
 520           adjacencies
 521     */
 522     if (size == 4)
 523     {
 524          /*    Checking for a quad whether to do the whole polygon will
 525                result in better performance because the triangles in the polygon
 526                have less adjacencies
 527          */
 528          Check_In_Quad(face_id,&test_face);
 529          if (*next_bucket > test_face)
 530               /*    We can do better by going through the polygon */
 531               min_face = face_id;
 532     }
 533
 534     /*  We have a polygon with greater than 4 sides, check to see if going
 535         inside is better than going outside the polygon for the output edge.
 536     */
 537     else
 538     {
 539         Check_In_Polygon(face_id,&test_face,size);
 540         if (*next_bucket > test_face)
 541             /*  We can do better by going through the polygon */
 542             min_face = face_id;
 543     }
 544
 545     return (min_face);
 546 }
 547
 548
 549