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