Stripe_w/partial.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: partial.c
  11      This file contains routines that are used partial triangulation of polygons
  12 */
  13 /*---------------------------------------------------------------------*/
  14
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include "global.h"
  19 #include "outputex.h"
  20 #include "polyvertsex.h"
  21 #include "triangulatex.h"
  22 #include "sturctsex.h"
  23 #include "polverts.h"
  24 #include "common.h"
  25 #include "util.h"
  26
  27 void P_Triangulate_Quad(int out_edge1,int out_edge2,int in_edge1,
  28                                           int in_edge2,int size,int *index,
  29                                           FILE *output,FILE *fp,int reversed,int face_id,
  30                                           int *next_id,ListHead *pListHead,
  31                                           P_ADJACENCIES temp,
  32                       int where)
  33 {
  34     int vertex4,vertex5,dummy=60;
  35
  36     /*  This routine will nonblindly triangulate a quad, meaning
  37                 that there is a definite input and a definite output
  38                 edge that we must adhere to. Reversed will tell the orientation
  39                 of the input edge. (Reversed is -1 is we do not have an input
  40                 edge, in other words we are at the beginning of a strip.)
  41                 Out_edge* is the output edge, and in_edge* is the input edge.
  42                 Index are the edges of the polygon
  43                 and size is the size of the polygon. Begin is whether we are
  44                 at the start of a new strip.
  45                 Note that we will not necessarily triangulate the whole quad;
  46                 maybe we will do half and leave the other half (a triangle)
  47                 for later.
  48         */
  49
  50
  51     /*  If we do not have an input edge, then we can make our input
  52                 edge whatever we like, therefore it will be easier to come
  53                 out on the output edge. In this case the whole quad is done.
  54         */
  55         if (reversed == -1)
  56         {
  57                 vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
  58                 vertex5 = Get_Other_Vertex(vertex4,out_edge1,out_edge2,index);
  59                 Output_TriEx(vertex5,vertex4,out_edge1,output,-1,-1,where);
  60                 Output_TriEx(vertex4,out_edge1,out_edge2,output,-1,-1,where);
  61                 dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
  62                 RemoveList(pListHead,(PLISTINFO) temp);
  63                 return;
  64         }
  65
  66         /*      These are the 5 cases that we can have for the output edge */
  67
  68         /*  Are they consecutive so that we form a triangle to
  69                 peel off, but cannot use the whole quad?
  70         */
  71
  72         if (in_edge2 == out_edge1)
  73         {
  74                 /*      Output the triangle that comes out the correct
  75                         edge. Save the other half for later.
  76                 */
  77                 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
  78           Output_TriEx(in_edge1,in_edge2,out_edge2,output,-1,-1,where);
  79                 /*      Now we have a triangle used, and a triangle that is
  80                         left for later.
  81                 */
  82
  83                 /*      Now delete the adjacencies by one for all the faces
  84                         that are adjacent to the triangle that we just outputted.
  85                 */
  86                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,
  87                                 face_id,&dummy,&dummy,&dummy);
  88                 Delete_AdjEx(out_edge2,in_edge2,&dummy,&dummy,
  89                                 face_id,&dummy,&dummy,&dummy);
  90                 /*      Put the new face in the proper bucket of adjacencies
  91                         There are 2 edges that need to be checked for the triangle
  92                         that was just outputted. For the output edge we definitely
  93                         will be decreasing the adjacency, but we must check for the
  94                         input edge.
  95                 */
  96
  97                 dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp,FALSE);
  98                 dummy = Change_FaceEx(face_id,in_edge2,out_edge2,pListHead,temp,TRUE);
  99
 100                 /*      Update the face data structure, by deleting the old
 101                         face and putting in the triangle as the new face
 102                 */
 103                 New_Face(face_id,in_edge1,out_edge2,vertex4);
 104                 return;
 105         }
 106         else if (in_edge1 == out_edge1)
 107         {
 108                 /*      We want to output the first triangle (whose output
 109                         edge is not the one that we want.
 110                         We have to find the vertex that we need, which is
 111                         the other vertex which we do not have.
 112                 */
 113                 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
 114                 Output_TriEx(in_edge2,in_edge1,out_edge2,output,-1,-1,where);
 115                 /*      Now we have a triangle used, and a triangle that is
 116                         left for later.
 117                 */
 118
 119                 /*      Now delete the adjacencies by one for all the faces
 120                         that are adjacent to the triangle that we just outputted.
 121                 */
 122                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 123                                 &dummy,&dummy,&dummy);
 124                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 125                                 face_id,&dummy,&dummy,&dummy);
 126
 127                 /*      Put the new face in the proper bucket of adjacencies */
 128                 dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp,FALSE);
 129                 dummy = Change_FaceEx(face_id,in_edge1,out_edge2,pListHead,temp,TRUE);
 130
 131                 /*      Update the face data structure, by deleting the old
 132                         face and putting in the triangle as the new face
 133                 */
 134                 New_Face(face_id,in_edge2,out_edge2,vertex4);
 135                 return;
 136         }
 137
 138         /*      Consecutive cases again, but with the output edge reversed */
 139         else if (in_edge1 == out_edge2)
 140         {
 141                 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
 142                 Output_TriEx(in_edge2,in_edge1,out_edge1,output,-1,-1,where);
 143                 /*      Now we have a triangle used, and a triangle that is
 144                         left for later.
 145                 */
 146
 147                 /*      Now delete the adjacencies by one for all the faces
 148                         that are adjacent to the triangle that we just outputted.
 149                 */
 150                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 151                                 &dummy,&dummy,&dummy);
 152                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 153                                 face_id,&dummy,&dummy,&dummy);
 154
 155                 /*      Put the new face in the proper bucket of adjacencies */
 156                 dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp,FALSE);
 157                 dummy = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp,TRUE);
 158
 159                 /*      Update the face data structure, by deleting the old
 160                         face and putting in the triangle as the new face
 161                 */
 162                 New_Face(face_id,in_edge2,out_edge1,vertex4);
 163           return;
 164         }
 165         else if (in_edge2 == out_edge2)
 166         {
 167                 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
 168                 Output_TriEx(in_edge1,in_edge2,out_edge1,output,-1,-1,where);
 169                 /*      Now we have a triangle used, and a triangle that is
 170                         left for later.
 171                 */
 172                 /*      Now delete the adjacencies by one for all the faces
 173                         that are adjacent to the triangle that we just outputted.
 174                 */
 175                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 176                                 &dummy,&dummy,&dummy);
 177                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 178                                 face_id,&dummy,&dummy,&dummy);
 179
 180                 /*      Put the new face in the proper bucket of adjacencies */
 181                 dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp,FALSE);
 182                 dummy = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp,TRUE);
 183
 184                 /*      Update the face data structure, by deleting the old
 185                         face and putting in the triangle as the new face
 186                 */
 187                 New_Face(face_id,in_edge1,out_edge1,vertex4);
 188                 return;
 189         }
 190
 191         /*      The final case is where we want to come out the opposite
 192                 edge.
 193         */
 194         else
 195         {
 196         if( ((!reversed) && (out_edge1 == (AdjacentEx(in_edge1,in_edge2,index,size)))) ||
 197                     ((reversed) && (out_edge2 == (AdjacentEx(in_edge2,in_edge1,index,size)))))
 198                 {
 199                         /*      We need to know the orientation of the input
 200                                 edge, so we know which way to put the diagonal.
 201                 And also the output edge, so that we triangulate
 202                 correctly. Does not need partial.
 203              */
 204                         Output_TriEx(in_edge1,in_edge2,out_edge2,output,-1,-1,where);
 205                         Output_TriEx(in_edge2,out_edge2,out_edge1,output,-1,-1,where);
 206                         dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
 207                         RemoveList(pListHead,(PLISTINFO) temp);
 208                 }
 209                 else
 210                 {
 211                         /*      Input and output orientation was reversed, so diagonal will
 212                                         be reversed from above.
 213                         */
 214                         Output_TriEx(in_edge1,in_edge2,out_edge1,output,-1,-1,where);
 215                         Output_TriEx(in_edge2,out_edge1,out_edge2,output,-1,-1,where);
 216                         dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
 217                         RemoveList(pListHead,(PLISTINFO) temp);
 218                 }
 219                 return;
 220         }
 221 }
 222
 223 void P_Triangulate_Polygon(int out_edge1,int out_edge2,int in_edge1,
 224                                                    int in_edge2,int size,
 225                                                   int *index,FILE *output,FILE *fp,
 226                                                   int reversed,int face_id,int *next_id,
 227                                                   ListHead *pListHead, P_ADJACENCIES temp2,
 228                           int where)
 229 {
 230         /*      We have a polygon greater than 4 sides, which we wish
 231                 to partially triangulate
 232         */
 233         int next_bucket,vertex4,dummy = 60;
 234         int *temp;
 235         P_ADJACENCIES pfNode;
 236
 237
 238     /*  Since we are calling this recursively, we have to check whether
 239                 we are down to the case of the quad.
 240         */
 241         if (size == 4)
 242         {
 243                 P_Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
 244                                                         index,output,fp,reversed,face_id,next_id,
 245                                                         pListHead,temp2,where);
 246                 return;
 247         }
 248
 249         /*      We do not have a specified input edge, and therefore we
 250                 can make it anything we like, as long as we still come out
 251                 the output edge that we want.
 252         */
 253         if (reversed  == -1)
 254         {
 255                 /*      Get the vertex for the last triangle, which is
 256                         the one coming out the output edge, before we do
 257                         any deletions to the list. We will be doing this
 258                         bottom up.
 259                 */
 260                 vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
 261                 temp = (int *) malloc(sizeof(int) * size);
 262                 memcpy(temp,index,sizeof(int)*size);
 263                 Delete_From_ListEx(out_edge2,index,size);
 264                 /*      We do not have to partially triangulate, since
 265                         we will do the whole thing, so use the whole routine
 266                 */
 267                 /* Triangulate_PolygonEx(vertex4,out_edge1,in_edge2,
 268                                       vertex4,size-1,index,output,fp,reversed,
 269                                       face_id,next_id,pListHead,temp2,where); */
 270                 Triangulate_PolygonEx(vertex4,out_edge1,in_edge2,
 271                                       vertex4,size-1,index,output,fp,reversed,
 272                                       face_id,where);
 273                 memcpy(index,temp,sizeof(int)*size);
 274                 /*      Lastly do the triangle that comes out the output
 275                         edge.
 276                 */
 277                 Output_TriEx(vertex4,out_edge1,out_edge2,output,-1,-1,where);
 278                 /*      We were able to do the whole polygon, now we
 279                         can delete the whole thing from our data structure.
 280                 */
 281                 dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
 282                 RemoveList(pListHead,(PLISTINFO) temp2);
 283                 return;
 284         }
 285
 286         /*      These are the 5 cases that we can have for the output edge */
 287
 288         /*  Are they consecutive so that we form a triangle to
 289                 peel off that comes out the correct output edge,
 290                 but we cannot use the whole polygon?
 291         */
 292         if (in_edge2 == out_edge1)
 293         {
 294                 Output_TriEx(in_edge1,out_edge1,out_edge2,output,-1,-1,where);
 295
 296                 /*      Now delete the adjacencies by one for all the faces
 297                         that are adjacent to the triangle that we just outputted.
 298                 */
 299                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 300                                 &dummy,&dummy,&dummy);
 301                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 302                                 face_id,&dummy,&dummy,&dummy);
 303
 304                 /*      Put the new face in the proper bucket of adjacencies */
 305                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 306                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 307
 308                 /*      Create a new edgelist without the triangle that
 309                         was just outputted.
 310                 */
 311           Delete_From_ListEx(in_edge2,index,size);
 312                 /*      Update the face data structure, by deleting the old
 313                         face and putting in the polygon minus the triangle
 314                         as the new face, here we will be decrementing the size
 315                         by one.
 316                 */
 317                 New_Size_Face(face_id);
 318                 return;
 319         }
 320
 321         /*      Next case is where it is again consecutive, but the triangle
 322                 formed by the consecutive edges do not come out of the
 323                 correct output edge. (the input edge will be reversed in
 324                 the next triangle)
 325         */
 326         else if (in_edge1 == out_edge1)
 327         {
 328                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 329                 Output_TriEx(in_edge2,in_edge1,out_edge2,output,-1,-1,where);
 330
 331                 /*      Now delete the adjacencies by one for all the faces
 332                         that are adjacent to the triangle that we just outputted.
 333                 */
 334                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 335                                 &dummy,&dummy,&dummy);
 336                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 337                                 face_id,&dummy,&dummy,&dummy);
 338
 339                 /*      Put the new face in the proper bucket of adjacencies */
 340                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 341                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 342
 343                 /*      Create a new edgelist without the triangle that
 344                         was just outputted.
 345                 */
 346           Delete_From_ListEx(in_edge1,index,size);
 347                 /*      Update the face data structure, by deleting the old
 348                         face and putting in the polygon minus the triangle
 349                         as the new face, here we will be decrementing the size
 350                         by one.
 351                 */
 352                 New_Size_Face(face_id);
 353                 return;
 354         }
 355
 356         /*      Consecutive cases again, but with the output edge reversed */
 357         else if (in_edge1 == out_edge2)
 358         {
 359                 Output_TriEx(in_edge2,in_edge1,out_edge1,output,-1,-1,where);
 360
 361                 /*      Now delete the adjacencies by one for all the faces
 362                         that are adjacent to the triangle that we just outputted.
 363                 */
 364                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 365                                 &dummy,&dummy,&dummy);
 366                 Delete_AdjEx(out_edge1,out_edge2,&dummy,&dummy,
 367                                 face_id,&dummy,&dummy,&dummy);
 368
 369                 /*      Put the new face in the proper bucket of adjacencies */
 370                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 371                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 372
 373                 /*      Create a new edgelist without the triangle that
 374                         was just outputted.
 375                 */
 376         Delete_From_ListEx(in_edge1,index,size);
 377                 /*      Update the face data structure, by deleting the old
 378                         face and putting in the polygon minus the triangle
 379                         as the new face, here we will be decrementing the size
 380                         by one.
 381                 */
 382                 New_Size_Face(face_id);
 383                 return;
 384         }
 385         else if (in_edge2 == out_edge2)
 386         {
 387                 Output_TriEx(in_edge1,in_edge2,out_edge1,output,-1,-1,where);
 388
 389                 /*      Now delete the adjacencies by one for all the faces
 390                         that are adjacent to the triangle that we just outputted.
 391                 */
 392                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 393                                 &dummy,&dummy,&dummy);
 394                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 395                                 face_id,&dummy,&dummy,&dummy);
 396
 397                 /*      Put the new face in the proper bucket of adjacencies */
 398                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 399                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 400
 401                 /*      Create a new edgelist without the triangle that
 402                         was just outputted.
 403                 */
 404           Delete_From_ListEx(in_edge2,index,size);
 405                 /*      Update the face data structure, by deleting the old
 406                         face and putting in the polygon minus the triangle
 407                         as the new face, here we will be decrementing the size
 408                         by one.
 409                 */
 410                 New_Size_Face(face_id);
 411                 return;
 412         }
 413
 414         /*      Else the edge is not consecutive, and it is sufficiently
 415                 far away, for us not to make a conclusion at this time.
 416                 So we can take off a triangle and recursively call this
 417                 function.
 418         */
 419         else
 420         {
 421           if (!reversed)
 422                 {
 423                         vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
 424                         Output_TriEx(in_edge1,in_edge2,vertex4,output,-1,-1,where);
 425
 426                         /*      Now delete the adjacencies by one for all the faces
 427                                 that are adjacent to the triangle that we just outputted.
 428                         */
 429                         Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 430                                 &dummy,&dummy,&dummy);
 431                         Delete_AdjEx(in_edge1,vertex4,&dummy,&dummy,
 432                                 face_id,&dummy,&dummy,&dummy);
 433
 434                         /*      Put the new face in the proper bucket of adjacencies */
 435                         next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 436                         next_bucket = Change_FaceEx(face_id,in_edge1,vertex4,pListHead,temp2,FALSE);
 437
 438                         /*      Create a new edgelist without the triangle that
 439                                 was just outputted.
 440                         */
 441                         Delete_From_ListEx(in_edge1,index,size);
 442                         /*      Update the face data structure, by deleting the old
 443                                 face and putting in the polygon minus the triangle
 444                                 as the new face, here we will be decrementing the size
 445                                 by one.
 446                         */
 447                         New_Size_Face(face_id);
 448
 449                         /*      Save the info for the new bucket, we will need it on
 450                                 the next pass for the variables, pListHead and temp
 451                         */
 452                         pListHead = array[next_bucket];
 453                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 454                         if ( pfNode )
 455                                 pfNode->face_id = face_id;
 456                         temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 457                                 (int (*)(void *,void *)) (Compare)));
 458                         if (temp2 == NULL)
 459                         {
 460                                 printf("There is an error finding the next polygon10 %d %d\n",next_bucket,face_id);
 461                                 exit(0);
 462                         }
 463
 464                         P_Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
 465                                                  vertex4,size-1,index,output,fp,!reversed,
 466                                                  face_id,next_id,pListHead,temp2,where);
 467                 }
 468                 else
 469                 {
 470                         vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
 471                         Output_TriEx(in_edge2,in_edge1,vertex4,output,-1,-1,where);
 472
 473                         /*      Now delete the adjacencies by one for all the faces
 474                                 that are adjacent to the triangle that we just outputted.
 475                         */
 476                         Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 477                                 &dummy,&dummy,&dummy);
 478                         Delete_AdjEx(in_edge2,vertex4,&dummy,&dummy,
 479                                 face_id,&dummy,&dummy,&dummy);
 480
 481                         /*      Put the new face in the proper bucket of adjacencies */
 482                         next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 483                         next_bucket = Change_FaceEx(face_id,in_edge2,vertex4,pListHead,temp2,FALSE);
 484
 485                         /*      Create a new edgelist without the triangle that
 486                                 was just outputted.
 487                         */
 488                         Delete_From_ListEx(in_edge2,index,size);
 489
 490                         /*      Update the face data structure, by deleting the old
 491                                 face and putting in the polygon minus the triangle
 492                                 as the new face, here we will be decrementing the size
 493                                 by one.
 494                         */
 495                         New_Size_Face(face_id);
 496
 497                         /*      Save the info for the new bucket, we will need it on
 498                                 the next pass for the variables, pListHead and temp
 499                         */
 500                         pListHead = array[next_bucket];
 501                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 502                         if ( pfNode )
 503                                 pfNode->face_id = face_id;
 504                         temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 505                                 (int (*)(void *,void *)) (Compare)));
 506                         if (temp2 == NULL)
 507                         {
 508                                 printf("There is an error finding the next polygon11 %d %d\n",face_id,next_bucket);
 509                                 exit(0);
 510                         }
 511
 512                         P_Triangulate_Polygon(out_edge1,out_edge2,vertex4,
 513                                                        in_edge1,size-1,index,output,fp,!reversed,
 514                                                        face_id,next_id,pListHead,temp2,where);
 515                 }
 516                 return;
 517         }
 518 }
 519
 520 void P_Triangulate(int out_edge1,int out_edge2,int in_edge1,
 521                                  int in_edge2,int size,int *index,
 522                                  FILE *fp,FILE *output,int reversed,int face_id,
 523                                  int *next_id,ListHead *pListHead,
 524                                  P_ADJACENCIES temp,int where)
 525 {
 526
 527         if (size == 4)
 528                 P_Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
 529                                       index,fp,output,reversed,face_id,next_id,pListHead, temp,where);
 530         else
 531                 P_Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
 532                                          index,fp,output,reversed,face_id,next_id,pListHead,temp,where);
 533 }
 534
 535  void Partial_Triangulate(int size,int *index, FILE *fp,
 536                                                  FILE *output,int next_face_id,int face_id,
 537                                                  int *next_id,ListHead *pListHead,
 538                                                  P_ADJACENCIES temp, int where)
 539 {
 540         int id1,id2,id3;
 541         int nedge1,nedge2;
 542         int reversed;
 543
 544         /*      We have a polygon that has to be triangulated and we cannot
 545                 do it blindly, ie we will try to come out on the edge that
 546                 has the least number of adjacencies, But also we do not
 547                 want to triangulate the whole polygon now, so that means
 548                 we will output the least number of triangles that we can
 549                 and then update the data structures, with the polygon
 550                 that is left after we are done.
 551         */
 552         Last_Edge(&id1,&id2,&id3,0);
 553
 554         /*      Find the edge that is adjacent to the new face ,
 555                 also return whether the orientation is reversed in the
 556                 face of the input edge, which is id2 and id3.
 557         */
 558         reversed = Get_EdgeEx(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
 559
 560         /*   Input edge and output edge can be the same if there are more than
 561           one polygon on an edge
 562      */
 563      if ( ((nedge1 == id2) && (nedge2 == id3)) ||
 564           ((nedge1 == id3) && (nedge2 == id2)) )
 565           /*   Set output edge arbitrarily but when come out of here the
 566                next face will be on the old output edge (identical one)
 567           */
 568           nedge2 = Return_Other(index,id2,id3);
 569
 570           /*    Do the triangulation */
 571         P_Triangulate(nedge1,nedge2,id2,id3,size,index,fp,output,reversed,
 572                          face_id,next_id,pListHead,temp,where);
 573 }
 574
 575  void Input_Edge(int face_id, int *index, int size, int in_edge1, int in_edge2,
 576                 FILE *fp, FILE *output,ListHead *pListHead, P_ADJACENCIES temp2,
 577                 int where)
 578  {
 579      /* The polygon had an input edge, specified by input1 and input2 */
 580
 581      int output1;
 582      int vertex4, vertex5,dummy=60;
 583
 584      output1 = Get_Output_Edge(face_id,size,index,in_edge1,in_edge2);
 585         vertex5 = AdjacentEx(in_edge2,in_edge1,index,size);
 586      vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
 587
 588      if (vertex4 == output1)
 589      {
 590                 Output_TriEx(in_edge2,in_edge1,output1,output,-1,-1,where);
 591                 /*      Now delete the adjacencies by one for all the faces
 592                         that are adjacent to the triangle that we just outputted.
 593                 */
 594                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 595                                 &dummy,&dummy,&dummy);
 596                 Delete_AdjEx(in_edge2,output1,&dummy,&dummy,
 597                                 face_id,&dummy,&dummy,&dummy);
 598                 /*      Put the new face in the proper bucket of adjacencies */
 599                 Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 600                 Change_FaceEx(face_id,in_edge2,output1,pListHead,temp2,FALSE);
 601
 602                 /*      Create a new edgelist without the triangle that
 603                         was just outputted.
 604                 */
 605           Delete_From_ListEx(in_edge2,index,size);
 606
 607     }
 608     else if (vertex5 == output1)
 609     {
 610           Output_TriEx(in_edge1,in_edge2,vertex5,output,-1,-1,where);
 611                 /*      Now delete the adjacencies by one for all the faces
 612                         that are adjacent to the triangle that we just outputted.
 613                 */
 614                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 615                                 &dummy,&dummy,&dummy);
 616                 Delete_AdjEx(in_edge1,vertex5,&dummy,&dummy,
 617                                 face_id,&dummy,&dummy,&dummy);
 618                 /*      Put the new face in the proper bucket of adjacencies */
 619                 Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 620                 Change_FaceEx(face_id,in_edge1,vertex5,pListHead,temp2,FALSE);
 621
 622                 /*      Create a new edgelist without the triangle that
 623                         was just outputted.
 624                 */
 625           Delete_From_ListEx(in_edge1,index,size);
 626     }
 627
 628     /*  Update the face data structure, by deleting the old
 629                 face and putting in the polygon minus the triangle
 630                 as the new face, here we will be decrementing the size
 631                 by one.
 632     */
 633     New_Size_Face(face_id);
 634     return;
 635  }
 636
 637  void Inside_Polygon(int size,int *index,FILE *fp,FILE *output,
 638                    int next_face_id,int face_id,int *next_id,
 639                    ListHead *pListHead,P_ADJACENCIES temp, int where)
 640  {
 641      /* We know that we have a polygon that is greater than 4 sides, and
 642         that it is better for us to go inside the polygon for the next
 643         one, since inside will have less adjacencies than going outside.
 644         So, we are not doing partial for a part of the polygon.
 645       */
 646     int id1,id2,id3;
 647     int new1,new2;
 648
 649     Last_Edge(&id1,&id2,&id3,0);
 650
 651     /*  See if the input edge existed in the polygon, that will help us */
 652         if (Exist(face_id,id2,id3))
 653         Input_Edge(face_id,index,size,id2,id3,output,fp,pListHead,temp,where);
 654     else
 655     {
 656         /*  Make one of the input edges
 657             We will choose it by trying to get an edge that has something
 658             in common with the last triangle, or by getting the edge that
 659             is adjacent to the least number of thigs, with preference given
 660             to the first option
 661         */
 662
 663         Get_Input_Edge(index,id1,id2,id3,&new1,&new2,size,face_id);
 664         Input_Edge(face_id,index,size,new1,new2,output,fp,pListHead,temp,where);
 665     }
 666  }
 667
 668