Stripe_w/sgi_triang.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: sgi_triang.c
  11      File contains the routines that do the whole triangulation
  12      of polygons.
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <string.h>
  19 #include "global.h"
  20 #include "output.h"
  21 #include "polverts.h"
  22 #include "sturcts.h"
  23 #include "common.h"
  24 #include "util.h"
  25 #include "init.h"
  26
  27 int Adjacent(int id2,int id1, int *list, int size)
  28 {
  29         /*      Return the vertex that is adjacent to id1,
  30                 but is not id2, in the list of integers.
  31         */
  32
  33         register int x=0;
  34
  35         while (x < size)
  36         {
  37                 if (*(list+x) == id1)
  38                 {
  39                         if ((x != (size -1)) && (x != 0))
  40                         {
  41                                 if ( *(list+x+1) != id2)
  42                                         return *(list+x+1);
  43                                 else
  44                                         return *(list+x-1);
  45                         }
  46                         else if (x == (size -1))
  47                         {
  48                                 if (*(list) != id2)
  49                                         return *(list);
  50                                 else
  51                                         return *(list+x-1);
  52                         }
  53                         else
  54                         {
  55                                 if (*(list+size-1) != id2)
  56                                         return *(list+size-1);
  57                                 else
  58                                         return *(list+x+1);
  59                         }
  60                 }
  61                 x++;
  62         }
  63         /*   if there are degeneracies */
  64      return id1;
  65 }
  66
  67
  68 void Rearrange_Index(int *index, int size)
  69 {
  70         /*      If we are in the middle of a strip we must find the
  71                 edge to start on, which is the last edge that we had
  72                 transmitted.
  73         */
  74         int x,f,y,e1,e2,e3;
  75         register int increment = 1;
  76      int *temp;
  77
  78         /*      Find where the input edge is in the input list */
  79         Last_Edge(&e1,&e2,&e3,0);
  80         for (y = 0; y < size; y++)
  81         {
  82                 if (*(index+y) == e2)
  83                 {
  84                         if ((y != (size - 1)) && (*(index+y+1) == e3))
  85                                 break;
  86                         else if ((y == (size - 1)) && (*(index) == e3))
  87                                 break;
  88                else if ((y != 0) && (*(index+y-1) == e3))
  89                {
  90                     increment = -1;
  91                     break;
  92                }
  93                else if ((y==0) && (*(index+size-1) == e3))
  94                {
  95                     increment = -1;
  96                     break;
  97                }
  98                 }
  99                 if (*(index+y) == e3)
 100                 {
 101                         if ((y != (size - 1)) && (*(index+y+1) == e2))
 102                                 break;
 103                         else if ((y == (size - 1)) && (*(index) == e2))
 104                                 break;
 105             else if ((y != 0) && (*(index+y-1) == e2))
 106             {
 107                 increment = -1;
 108                 break;
 109             }
 110             else if ((y==0) && (*(index+size-1) == e2))
 111             {
 112                 increment = -1;
 113                 break;
 114             }
 115                 }
 116                 /*      Edge is not here, we are at the beginning */
 117                 if ((y == (size-1)) && (increment != -1))
 118                         return;
 119         }
 120
 121         /*      Now put the list into a new list, starting with the
 122                 input edge. Increment tells us whether we have to go
 123                 forward or backward.
 124         */
 125         /*      Was in good position already */
 126         if ((y == 0) && (increment == 1))
 127                 return;
 128
 129      temp = (int *) malloc(sizeof(int) * size);
 130      memcpy(temp,index,sizeof(int)*size);
 131
 132         if (increment == 1)
 133         {
 134                 x=0;
 135                 for (f = y ; f< size; f++)
 136                 {
 137                         *(index+x) = *(temp+f);
 138                         x++;
 139                 }
 140                 /*      Finish the rest of the list */
 141                 for(f = 0; f < y ; f++)
 142                 {
 143                         *(index+x) = *(temp+f);
 144                         x++;
 145                 }
 146         }
 147         else
 148         {
 149                 x=0;
 150                 for (f = y ; f >= 0; f--)
 151                 {
 152                         *(index+x) = *(temp+f);
 153                         x++;
 154                 }
 155                 /*      Finish the rest of the list */
 156                 for(f = (size - 1); f > y ; f--)
 157                 {
 158                         *(index+x) = *(temp+f);
 159                         x++;
 160                 }
 161         }
 162 }
 163
 164 void Delete_From_List(int id,int *list, int *size)
 165 {
 166         /*      Delete the occurence of id in the list.
 167                 (list has size size)
 168         */
 169
 170         int *temp;
 171         register int x,y=0;
 172
 173         temp = (int *) malloc(sizeof(int) * (*size));
 174         for (x=0; x<(*size); x++)
 175         {
 176                 if (*(list+x) != id)
 177                 {
 178                         *(temp+y) = *(list+x);
 179                         y++;
 180                 }
 181         }
 182         *(temp+y) = -1;
 183      *size = *size - (*size - y - 1);
 184         memcpy(list,temp,sizeof(int)*(*size));
 185 }
 186
 187
 188 void Build_SGI_Table(int num_verts,int num_faces)
 189 {
 190         /*      Build a table that has the polygons sorted by the
 191                 number of adjacent polygons.
 192         */
 193         int x,y,size,tally=0;
 194         ListHead *pListHead;
 195         PF_FACES temp = NULL;
 196
 197         /* For each face....*/
 198         for (x=0;x < num_faces;x++)
 199         {
 200                 pListHead = PolFaces[x];
 201                 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
 202                 /*   Check each edge of the face and tally the number of adjacent
 203                         polygons to this face.
 204                 */
 205                 if ( temp != NULL )
 206                 {
 207                         /*      Size of the polygon */
 208                         size = temp->nPolSize;
 209                         if (size != 1)
 210       {
 211         for (y = 0; y< size; y++)
 212                           {
 213                                   if (y != (size-1))
 214                                           tally += Num_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1));
 215                                   else
 216                                           tally += Num_Adj(*(temp->pPolygon),*(temp->pPolygon+(size-1)));
 217         }
 218
 219                           /* Tally is the number of polygons that is adjacent to
 220                                    the current polygon.
 221                           */
 222                           /* Now put the face in the proper bucket depending on tally. */
 223                           Add_Sgi_Adj(tally,x);
 224                           temp = NULL;
 225                           tally=0;
 226       }
 227                 }
 228         }
 229 }
 230
 231
 232 void Triangulate_Quad(int out_edge1,int out_edge2,int in_edge1,
 233                                           int in_edge2,int size,int *index,
 234                                           FILE *output,int reversed,int face_id,
 235                       int where,int color1,int color2,int color3)
 236 {
 237         int vertex4,vertex5;
 238
 239         /*      This routine will nonblindly triangulate a quad, meaning
 240                 that there is a definite input and a definite output
 241                 edge that we must adhere to. Reversed will tell the orientation
 242                 of the input edge. (Reversed is -1 is we do not have an input
 243                 edge, in other words we are at the beginning of a strip.)
 244                 Out_edge* is the output edge, and in_edge* is the input edge.
 245                 Index are the edges of the polygon
 246                 and size is the size of the polygon. Begin is whether we are
 247                 at the start of a new strip.
 248         */
 249
 250         /*      If we do not have an input edge, then we can make our input
 251                 edge whatever we like, therefore it will be easier to come
 252                 out on the output edge.
 253         */
 254         if (reversed == -1)
 255         {
 256                 vertex4 = Adjacent(out_edge1,out_edge2,index,size);
 257                 vertex5 = Get_Other_Vertex(vertex4,out_edge1,out_edge2,index);
 258                 Output_Tri(vertex5,vertex4,out_edge1,output,color1,color2,color3,where);
 259                 Output_Tri(vertex4,out_edge1,out_edge2,output,color1,color2,color3,where);
 260                 return;
 261         }
 262
 263         /*      These are the 5 cases that we can have for the output edge */
 264
 265         /*  Are they consecutive so that we form a triangle to
 266                 peel off, but cannot use the whole quad?
 267         */
 268
 269         if (in_edge2 == out_edge1)
 270         {
 271                 /* Output the triangle that comes out the correct
 272                          edge last. First output the triangle that comes out
 273                          the wrong edge.
 274                 */
 275                 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
 276     Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
 277     Output_Tri(vertex4,in_edge2,out_edge2,output,color1,color2,color3,where);
 278                 return;
 279         }
 280         /* The next case is where it is impossible to come out the
 281                  edge that we want. So we will have to start a new strip to
 282                  come out on that edge. We will output the one triangle
 283                  that we can, and then start the new strip with the triangle
 284                  that comes out on the edge that we want to come out on.
 285         */
 286         else if (in_edge1 == out_edge1)
 287         {
 288                 /* We want to output the first triangle (whose output
 289                          edge is not the one that we want.
 290                          We have to find the vertex that we need, which is
 291                          the other vertex which we do not have.
 292                 */
 293                 vertex4 = Get_Other_Vertex(in_edge2,in_edge1,out_edge2,index);
 294                 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where);
 295                 Output_Tri(vertex4,in_edge1,out_edge2,output,color1,color2,color3,where);
 296                 return;
 297         }
 298
 299         /*      Consecutive cases again, but with the output edge reversed */
 300         else if (in_edge1 == out_edge2)
 301         {
 302                 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
 303                 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where);
 304                 Output_Tri(vertex4,in_edge1,out_edge1,output,color1,color2,color3,where);
 305                 return;
 306         }
 307         else if (in_edge2 == out_edge2)
 308         {
 309                 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
 310                 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
 311                 Output_Tri(vertex4,in_edge2,out_edge1,output,color1,color2,color3,where);
 312                 return;
 313         }
 314
 315         /*      The final case is where we want to come out the opposite
 316                 edge.
 317         */
 318         else
 319         {
 320     if( ((!reversed) && (out_edge1 == (Adjacent(in_edge1,in_edge2,index,size)))) ||
 321         ((reversed) && (out_edge2 == (Adjacent(in_edge2,in_edge1,index,size)))))
 322                 {
 323                   /* We need to know the orientation of the input
 324                                  edge, so we know which way to put the diagonal.
 325          And also the output edge, so that we triangulate
 326          correctly.
 327       */
 328                         Output_Tri(in_edge1,in_edge2,out_edge2,output,color1,color2,color3,where);
 329                         Output_Tri(in_edge2,out_edge2,out_edge1,output,color1,color2,color3,where);
 330                 }
 331                 else
 332                 {
 333                         /* Input and output orientation was reversed, so diagonal will
 334                                  be reversed from above.
 335                         */
 336                         Output_Tri(in_edge1,in_edge2,out_edge1,output,color1,color2,color3,where);
 337                         Output_Tri(in_edge2,out_edge1,out_edge2,output,color1,color2,color3,where);
 338                 }
 339                 return;
 340         }
 341 }
 342
 343 void Triangulate_Polygon(int out_edge1, int out_edge2, int in_edge1,
 344                                            int in_edge2, int size, int *index,
 345                                                              FILE *output, int reversed, int face_id,
 346                          int where, int color1, int color2, int color3)
 347 {
 348         /* We have a polygon that we need to nonblindly triangulate.
 349                  We will recursively try to triangulate it, until we are left
 350                  with a polygon of size 4, which can use the quad routine
 351                  from above. We will be taking off a triangle at a time
 352                  and outputting it. We will have 3 cases similar to the
 353                  cases for the quad above. The inputs to this routine
 354                  are the same as for the quad routine.
 355         */
 356
 357         int vertex4;
 358         int *temp;
 359
 360         /* Since we are calling this recursively, we have to check whether
 361                  we are down to the case of the quad.
 362         */
 363
 364   if (size == 4)
 365         {
 366           Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
 367                                 index,output,reversed,face_id,where,color1,color2,color3);
 368                 return;
 369         }
 370
 371
 372
 373         /*      We do not have a specified input edge, and therefore we
 374                 can make it anything we like, as long as we still come out
 375                 the output edge that we want.
 376         */
 377         if (reversed  == -1)
 378         {
 379                 /*      Get the vertex for the last triangle, which is
 380                         the one coming out the output edge, before we do
 381                         any deletions to the list. We will be doing this
 382                         bottom up.
 383                 */
 384                 vertex4 = Adjacent(out_edge1,out_edge2,index,size);
 385                 temp = (int *) malloc(sizeof(int) * size);
 386                 memcpy(temp,index,sizeof(int)*size);
 387                 Delete_From_List(out_edge2,index,&size);
 388                 Triangulate_Polygon(out_edge1,vertex4,in_edge2,
 389                                                  vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 390                 memcpy(index,temp,sizeof(int)*size);
 391                 /*      Lastly do the triangle that comes out the output
 392                         edge.
 393                 */
 394                 Output_Tri(vertex4,out_edge1,out_edge2,output,color1,color2,color3,where);
 395                 return;
 396         }
 397
 398         /*      These are the 5 cases that we can have for the output edge */
 399
 400         /*  Are they consecutive so that we form a triangle to
 401                 peel off that comes out the correct output edge,
 402                 but we cannot use the whole polygon?
 403         */
 404         if (in_edge2 == out_edge1)
 405         {
 406                 /*      Output the triangle that comes out the correct
 407                         edge last. First recursively do the rest of the
 408                         polygon.
 409                 */
 410                 /*      Do the rest of the polygon without the triangle.
 411                         We will be doing a fan triangulation.
 412                 */
 413                 /*      Get the vertex adjacent to in_edge1, but is not
 414                         in_edge2.
 415                 */
 416                 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
 417                 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
 418                 /*      Create a new edgelist without the triangle that
 419                         was just outputted.
 420                 */
 421                 temp = (int *) malloc(sizeof(int) * size);
 422                 memcpy(temp,index,sizeof(int)*size);
 423           Delete_From_List(in_edge1,index,&size);
 424                 Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
 425                                                 vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
 426                 memcpy(index,temp,sizeof(int)*size);
 427                 return;
 428         }
 429
 430         /*      Next case is where it is again consecutive, but the triangle
 431                 formed by the consecutive edges do not come out of the
 432                 correct output edge. For this case, we can not do much to
 433                 keep it sequential. Try and do the fan.
 434         */
 435         else if (in_edge1 == out_edge1)
 436         {
 437                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 438                 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
 439                 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
 440                 /*      Since that triangle goes out of the polygon (the
 441                         output edge of it), we can make our new input edge
 442                         anything we like, so we will try to make it good for
 443                         the strip. (This will be like starting a new strip,
 444                         all so that we can go out the correct output edge.)
 445                 */
 446                 temp = (int *) malloc(sizeof(int) * size);
 447                 memcpy(temp,index,sizeof(int)*size);
 448                 Delete_From_List(in_edge2,index,&size);
 449                 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
 450                                                 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 451                 memcpy(index,temp,sizeof(int)*size);
 452                 return;
 453         }
 454         /*      Consecutive cases again, but with the output edge reversed */
 455         else if (in_edge1 == out_edge2)
 456         {
 457                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 458                 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
 459                 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where);
 460                 temp = (int *) malloc(sizeof(int) * size);
 461                 memcpy(temp,index,sizeof(int)*size);
 462                 Delete_From_List(in_edge2,index,&size);
 463           Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
 464                                                 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 465                 memcpy(index,temp,sizeof(int)*size);
 466                 return;
 467         }
 468         else if (in_edge2 == out_edge2)
 469         {
 470                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 471                 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
 472                 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
 473                 temp = (int *) malloc(sizeof(int) * size);
 474                 memcpy(temp,index,sizeof(int)*size);
 475                 Delete_From_List(in_edge1,index,&size);
 476           Triangulate_Polygon(out_edge1,out_edge2,vertex4,
 477                                                 in_edge2,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 478                 memcpy(index,temp,sizeof(int)*size);
 479                 return;
 480         }
 481
 482         /*      Else the edge is not consecutive, and it is sufficiently
 483                 far away, for us not to make a conclusion at this time.
 484                 So we can take off a triangle and recursively call this
 485                 function.
 486         */
 487         else
 488         {
 489                         vertex4 = Adjacent(in_edge2,in_edge1,index,size);
 490                         Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
 491                         temp = (int *) malloc(sizeof(int) * size);
 492                         memcpy(temp,index,sizeof(int)*size);
 493                         Delete_From_List(in_edge1,index,&size);
 494                Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
 495                                                      vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
 496                         memcpy(index,temp,sizeof(int)*size);
 497                      return;
 498         }
 499 }
 500
 501 void Triangulate(int out_edge1,int out_edge2,int in_edge1,
 502                                  int in_edge2,int size,int *index,
 503                                  FILE *output,int reversed,int face_id, int where,
 504                      int color1, int color2,int color3)
 505 {
 506         /*      We have the info we need to triangulate a polygon */
 507
 508         if (size == 4)
 509                 Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
 510                                     index,output,reversed,face_id,where,color1,color2,color3);
 511         else
 512                 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
 513                                        index,output,reversed,face_id,where,color1,color2,color3);
 514 }
 515
 516 void Non_Blind_Triangulate(int size,int *index,
 517                                           FILE *output,int next_face_id,int face_id,int where,
 518                            int color1,int color2,int color3)
 519 {
 520         int id1,id2,id3;
 521         int nedge1,nedge2;
 522         int reversed;
 523         /*      We have a polygon that has to be triangulated and we cannot
 524                 do it blindly, ie we will try to come out on the edge that
 525                 has the least number of adjacencies
 526         */
 527
 528         Last_Edge(&id1,&id2,&id3,0);
 529         /*      Find the edge that is adjacent to the new face ,
 530                 also return whether the orientation is reversed in the
 531                 face of the input edge, which is id2 and id3.
 532         */
 533         if (next_face_id == -1)
 534      {
 535         printf("The face is -1 and the size is %d\n",size);
 536         exit(0);
 537      }
 538
 539      reversed = Get_Edge(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
 540         /*      Do the triangulation */
 541
 542         /*      If reversed is -1, the input edge is not in the polygon, therefore we can have the
 543                 input edge to be anything we like, since we are at the beginning
 544                 of a strip
 545         */
 546         Triangulate(nedge1,nedge2,id2,id3,size,index,output,reversed,
 547                        face_id, where,color1,color2,color3);
 548 }
 549
 550
 551
 552 void Blind_Triangulate(int size, int *index, FILE *output,
 553                                    BOOL begin, int where ,int color1,int color2,
 554                        int color3)
 555 {
 556         /*      save sides in temp array, we need it so we know
 557                 about swaps.
 558         */
 559         int mode, decreasing,increasing,e1,e2,e3;
 560
 561         /*      Rearrange the index list so that the input edge is first
 562         */
 563         if (!begin)
 564                 Rearrange_Index(index,size);
 565
 566         /*      We are given a polygon of more than 3 sides
 567                 and want to triangulate it. We will output the
 568                 triangles to the output file.
 569         */
 570
 571     /*  Find where the input edge is in the input list */
 572         Last_Edge(&e1,&e2,&e3,0);
 573      if (( (!begin) && (*(index) == e2) ) || (begin))
 574      {
 575             Output_Tri(*(index+0),*(index+1),*(index+size-1),output,color1,color2,color3,where);
 576         /*      If we have a quad, (chances are yes), then we know that
 577                      we can just add one diagonal and be done. (divide the
 578                      quad into 2 triangles.
 579         */
 580         if (size == 4)
 581         {
 582                     Output_Tri(*(index+1),*(index+size-1),*(index+2),output,color1,color2,color3,where);
 583               return;
 584         }
 585         increasing = 1;
 586         mode = 1;
 587
 588     }
 589     else if (!begin)
 590     {
 591         Output_Tri(*(index+1),*(index+0),*(index+size-1),output,color1,color2,color3,where);
 592         if (size == 4)
 593         {
 594             Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where);
 595             return;
 596         }
 597         Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where);
 598         increasing = 2;
 599         mode = 0;
 600     }
 601     if (size != 4)
 602     {
 603                 /*      We do not have a quad, we have something bigger. */
 604                 decreasing = size - 1;
 605                 do
 606                 {
 607                         /*      Will be alternating diagonals, so we will be increasing
 608                                 and decreasing around the polygon.
 609                         */
 610                         if (mode)
 611                         {
 612                                 Output_Tri(*(index+increasing),*(index+decreasing),*(index+increasing+1),output,color1,color2,color3,where);
 613                                 increasing++;
 614                         }
 615                         else
 616                         {
 617                                 Output_Tri(*(index+decreasing),*(index+increasing),*(index+decreasing-1),output,color1,color2,color3,where);
 618                     decreasing--;
 619                }
 620                         mode = !mode;
 621                 } while ((decreasing - increasing) >= 2);
 622
 623         }
 624 }
 625
 626
 627
 628