Stripe_u/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
 361         /*      Since we are calling this recursively, we have to check whether
 362                 we are down to the case of the quad.
 363         */
 364
 365     if (size == 4)
 366         {
 367                 Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
 368                                                         index,output,reversed,face_id,where,color1,color2,color3);
 369                 return;
 370         }
 371
 372
 373
 374         /*      We do not have a specified input edge, and therefore we
 375                 can make it anything we like, as long as we still come out
 376                 the output edge that we want.
 377         */
 378         if (reversed  == -1)
 379         {
 380                 /*      Get the vertex for the last triangle, which is
 381                         the one coming out the output edge, before we do
 382                         any deletions to the list. We will be doing this
 383                         bottom up.
 384                 */
 385                 vertex4 = Adjacent(out_edge1,out_edge2,index,size);
 386                 temp = (int *) malloc(sizeof(int) * size);
 387                 memcpy(temp,index,sizeof(int)*size);
 388                 Delete_From_List(out_edge2,index,&size);
 389                 Triangulate_Polygon(out_edge1,vertex4,in_edge2,
 390                                                  vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 391                 memcpy(index,temp,sizeof(int)*size);
 392                 /*      Lastly do the triangle that comes out the output
 393                         edge.
 394                 */
 395                 Output_Tri(vertex4,out_edge1,out_edge2,output,color1,color2,color3,where,where);
 396                 return;
 397         }
 398
 399         /*      These are the 5 cases that we can have for the output edge */
 400
 401         /*  Are they consecutive so that we form a triangle to
 402                 peel off that comes out the correct output edge,
 403                 but we cannot use the whole polygon?
 404         */
 405         if (in_edge2 == out_edge1)
 406         {
 407                 /*      Output the triangle that comes out the correct
 408                         edge last. First recursively do the rest of the
 409                         polygon.
 410                 */
 411                 /*      Do the rest of the polygon without the triangle.
 412                         We will be doing a fan triangulation.
 413                 */
 414                 /*      Get the vertex adjacent to in_edge1, but is not
 415                         in_edge2.
 416                 */
 417                 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
 418                 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
 419                 /*      Create a new edgelist without the triangle that
 420                         was just outputted.
 421                 */
 422                 temp = (int *) malloc(sizeof(int) * size);
 423                 memcpy(temp,index,sizeof(int)*size);
 424           Delete_From_List(in_edge1,index,&size);
 425                 Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
 426                                                 vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
 427                 memcpy(index,temp,sizeof(int)*size);
 428                 return;
 429         }
 430
 431         /*      Next case is where it is again consecutive, but the triangle
 432                 formed by the consecutive edges do not come out of the
 433                 correct output edge. For this case, we can not do much to
 434                 keep it sequential. Try and do the fan.
 435         */
 436         else if (in_edge1 == out_edge1)
 437         {
 438                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 439                 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
 440                 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where,where);
 441                 /*      Since that triangle goes out of the polygon (the
 442                         output edge of it), we can make our new input edge
 443                         anything we like, so we will try to make it good for
 444                         the strip. (This will be like starting a new strip,
 445                         all so that we can go out the correct output edge.)
 446                 */
 447                 temp = (int *) malloc(sizeof(int) * size);
 448                 memcpy(temp,index,sizeof(int)*size);
 449                 Delete_From_List(in_edge2,index,&size);
 450                 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
 451                                                 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 452                 memcpy(index,temp,sizeof(int)*size);
 453                 return;
 454         }
 455         /*      Consecutive cases again, but with the output edge reversed */
 456         else if (in_edge1 == out_edge2)
 457         {
 458                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 459                 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
 460                 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where,where);
 461                 temp = (int *) malloc(sizeof(int) * size);
 462                 memcpy(temp,index,sizeof(int)*size);
 463                 Delete_From_List(in_edge2,index,&size);
 464           Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
 465                                                 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 466                 memcpy(index,temp,sizeof(int)*size);
 467                 return;
 468         }
 469         else if (in_edge2 == out_edge2)
 470         {
 471                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 472                 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
 473                 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where,where);
 474                 temp = (int *) malloc(sizeof(int) * size);
 475                 memcpy(temp,index,sizeof(int)*size);
 476                 Delete_From_List(in_edge1,index,&size);
 477           Triangulate_Polygon(out_edge1,out_edge2,vertex4,
 478                                                 in_edge2,size-1,index,output,reversed,face_id,where,color1,color2,color3);
 479                 memcpy(index,temp,sizeof(int)*size);
 480                 return;
 481         }
 482
 483         /*      Else the edge is not consecutive, and it is sufficiently
 484                 far away, for us not to make a conclusion at this time.
 485                 So we can take off a triangle and recursively call this
 486                 function.
 487         */
 488         else
 489         {
 490                         vertex4 = Adjacent(in_edge2,in_edge1,index,size);
 491                         Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where,where);
 492                         temp = (int *) malloc(sizeof(int) * size);
 493                         memcpy(temp,index,sizeof(int)*size);
 494                         Delete_From_List(in_edge1,index,&size);
 495                Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
 496                                                      vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
 497                         memcpy(index,temp,sizeof(int)*size);
 498                      return;
 499         }
 500 }
 501
 502 void Triangulate(int out_edge1,int out_edge2,int in_edge1,
 503                                  int in_edge2,int size,int *index,
 504                                  FILE *output,int reversed,int face_id, int where,
 505                      int color1, int color2,int color3)
 506 {
 507         /*      We have the info we need to triangulate a polygon */
 508
 509         if (size == 4)
 510                 Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
 511                                     index,output,reversed,face_id,where,color1,color2,color3);
 512         else
 513                 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
 514                                        index,output,reversed,face_id,where,color1,color2,color3);
 515 }
 516
 517 void Non_Blind_Triangulate(int size,int *index,
 518                                           FILE *output,int next_face_id,int face_id,int where,
 519                            int color1,int color2,int color3)
 520 {
 521         int id1,id2,id3;
 522         int nedge1,nedge2;
 523         int reversed;
 524         /*      We have a polygon that has to be triangulated and we cannot
 525                 do it blindly, ie we will try to come out on the edge that
 526                 has the least number of adjacencies
 527         */
 528
 529         Last_Edge(&id1,&id2,&id3,0);
 530         /*      Find the edge that is adjacent to the new face ,
 531                 also return whether the orientation is reversed in the
 532                 face of the input edge, which is id2 and id3.
 533         */
 534         if (next_face_id == -1)
 535      {
 536         printf("The face is -1 and the size is %d\n",size);
 537         exit(0);
 538      }
 539
 540      reversed = Get_Edge(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
 541         /*      Do the triangulation */
 542
 543         /*      If reversed is -1, the input edge is not in the polygon, therefore we can have the
 544                 input edge to be anything we like, since we are at the beginning
 545                 of a strip
 546         */
 547         Triangulate(nedge1,nedge2,id2,id3,size,index,output,reversed,
 548                        face_id, where,color1,color2,color3);
 549 }
 550
 551
 552
 553 void Blind_Triangulate(int size, int *index, FILE *output,
 554                                    BOOL begin, int where ,int color1,int color2,
 555                        int color3)
 556 {
 557         /*      save sides in temp array, we need it so we know
 558                 about swaps.
 559         */
 560         int mode, decreasing,increasing,e1,e2,e3;
 561         int x = 0;
 562         BOOL flag = FALSE;
 563
 564         /*      Rearrange the index list so that the input edge is first
 565         */
 566         if (!begin)
 567                 Rearrange_Index(index,size);
 568
 569         /*      We are given a polygon of more than 3 sides
 570                 and want to triangulate it. We will output the
 571                 triangles to the output file.
 572         */
 573
 574     /*  Find where the input edge is in the input list */
 575         Last_Edge(&e1,&e2,&e3,0);
 576      if (( (!begin) && (*(index) == e2) ) || (begin))
 577      {
 578             Output_Tri(*(index+0),*(index+1),*(index+size-1),output,color1,color2,color3,where,where);
 579         /*      If we have a quad, (chances are yes), then we know that
 580                      we can just add one diagonal and be done. (divide the
 581                      quad into 2 triangles.
 582         */
 583         if (size == 4)
 584         {
 585                     Output_Tri(*(index+1),*(index+size-1),*(index+2),output,color1,color2,color3,where,where);
 586               return;
 587         }
 588         increasing = 1;
 589         mode = 1;
 590
 591     }
 592     else if (!begin)
 593     {
 594         Output_Tri(*(index+1),*(index+0),*(index+size-1),output,color1,color2,color3,where,where);
 595         if (size == 4)
 596         {
 597             Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where,where);
 598             return;
 599         }
 600         Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where,where);
 601         increasing = 2;
 602         mode = 0;
 603     }
 604     if (size != 4)
 605     {
 606                 /*      We do not have a quad, we have something bigger. */
 607                 decreasing = size - 1;
 608                 do
 609                 {
 610                         /*      Will be alternating diagonals, so we will be increasing
 611                                 and decreasing around the polygon.
 612                         */
 613                         if (mode)
 614                         {
 615                                 Output_Tri(*(index+increasing),*(index+decreasing),*(index+increasing+1),output,color1,color2,color3,where,where);
 616                                 increasing++;
 617                         }
 618                         else
 619                         {
 620                                 Output_Tri(*(index+decreasing),*(index+increasing),*(index+decreasing-1),output,color1,color2,color3,where,where);
 621                     decreasing--;
 622                }
 623                         mode = !mode;
 624                 } while ((decreasing - increasing) >= 2);
 625
 626         }
 627 }
 628
 629
 630
 631