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