Stripe_u/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 "polvertsex.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,face_id,
 269                                                  next_id,pListHead,temp2,where);
 270                 memcpy(index,temp,sizeof(int)*size);
 271                 /*      Lastly do the triangle that comes out the output
 272                         edge.
 273                 */
 274                 Output_TriEx(vertex4,out_edge1,out_edge2,output,-1,-1,where);
 275                 /*      We were able to do the whole polygon, now we
 276                         can delete the whole thing from our data structure.
 277                 */
 278                 dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
 279                 RemoveList(pListHead,(PLISTINFO) temp2);
 280                 return;
 281         }
 282
 283         /*      These are the 5 cases that we can have for the output edge */
 284
 285         /*  Are they consecutive so that we form a triangle to
 286                 peel off that comes out the correct output edge,
 287                 but we cannot use the whole polygon?
 288         */
 289         if (in_edge2 == out_edge1)
 290         {
 291                 Output_TriEx(in_edge1,out_edge1,out_edge2,output,-1,-1,where);
 292
 293                 /*      Now delete the adjacencies by one for all the faces
 294                         that are adjacent to the triangle that we just outputted.
 295                 */
 296                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 297                                 &dummy,&dummy,&dummy);
 298                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 299                                 face_id,&dummy,&dummy,&dummy);
 300
 301                 /*      Put the new face in the proper bucket of adjacencies */
 302                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 303                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 304
 305                 /*      Create a new edgelist without the triangle that
 306                         was just outputted.
 307                 */
 308           Delete_From_ListEx(in_edge2,index,size);
 309                 /*      Update the face data structure, by deleting the old
 310                         face and putting in the polygon minus the triangle
 311                         as the new face, here we will be decrementing the size
 312                         by one.
 313                 */
 314                 New_Size_Face(face_id);
 315                 return;
 316         }
 317
 318         /*      Next case is where it is again consecutive, but the triangle
 319                 formed by the consecutive edges do not come out of the
 320                 correct output edge. (the input edge will be reversed in
 321                 the next triangle)
 322         */
 323         else if (in_edge1 == out_edge1)
 324         {
 325                 /*      Get vertex adjacent to in_edge2, but is not in_edge1 */
 326                 Output_TriEx(in_edge2,in_edge1,out_edge2,output,-1,-1,where);
 327
 328                 /*      Now delete the adjacencies by one for all the faces
 329                         that are adjacent to the triangle that we just outputted.
 330                 */
 331                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 332                                 &dummy,&dummy,&dummy);
 333                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 334                                 face_id,&dummy,&dummy,&dummy);
 335
 336                 /*      Put the new face in the proper bucket of adjacencies */
 337                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 338                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 339
 340                 /*      Create a new edgelist without the triangle that
 341                         was just outputted.
 342                 */
 343           Delete_From_ListEx(in_edge1,index,size);
 344                 /*      Update the face data structure, by deleting the old
 345                         face and putting in the polygon minus the triangle
 346                         as the new face, here we will be decrementing the size
 347                         by one.
 348                 */
 349                 New_Size_Face(face_id);
 350                 return;
 351         }
 352
 353         /*      Consecutive cases again, but with the output edge reversed */
 354         else if (in_edge1 == out_edge2)
 355         {
 356                 Output_TriEx(in_edge2,in_edge1,out_edge1,output,-1,-1,where);
 357
 358                 /*      Now delete the adjacencies by one for all the faces
 359                         that are adjacent to the triangle that we just outputted.
 360                 */
 361                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 362                                 &dummy,&dummy,&dummy);
 363                 Delete_AdjEx(out_edge1,out_edge2,&dummy,&dummy,
 364                                 face_id,&dummy,&dummy,&dummy);
 365
 366                 /*      Put the new face in the proper bucket of adjacencies */
 367                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 368                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 369
 370                 /*      Create a new edgelist without the triangle that
 371                         was just outputted.
 372                 */
 373         Delete_From_ListEx(in_edge1,index,size);
 374                 /*      Update the face data structure, by deleting the old
 375                         face and putting in the polygon minus the triangle
 376                         as the new face, here we will be decrementing the size
 377                         by one.
 378                 */
 379                 New_Size_Face(face_id);
 380                 return;
 381         }
 382         else if (in_edge2 == out_edge2)
 383         {
 384                 Output_TriEx(in_edge1,in_edge2,out_edge1,output,-1,-1,where);
 385
 386                 /*      Now delete the adjacencies by one for all the faces
 387                         that are adjacent to the triangle that we just outputted.
 388                 */
 389                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 390                                 &dummy,&dummy,&dummy);
 391                 Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy,
 392                                 face_id,&dummy,&dummy,&dummy);
 393
 394                 /*      Put the new face in the proper bucket of adjacencies */
 395                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 396                 next_bucket = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,temp2,TRUE);
 397
 398                 /*      Create a new edgelist without the triangle that
 399                         was just outputted.
 400                 */
 401           Delete_From_ListEx(in_edge2,index,size);
 402                 /*      Update the face data structure, by deleting the old
 403                         face and putting in the polygon minus the triangle
 404                         as the new face, here we will be decrementing the size
 405                         by one.
 406                 */
 407                 New_Size_Face(face_id);
 408                 return;
 409         }
 410
 411         /*      Else the edge is not consecutive, and it is sufficiently
 412                 far away, for us not to make a conclusion at this time.
 413                 So we can take off a triangle and recursively call this
 414                 function.
 415         */
 416         else
 417         {
 418           if (!reversed)
 419                 {
 420                         vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
 421                         Output_TriEx(in_edge1,in_edge2,vertex4,output,-1,-1,where);
 422
 423                         /*      Now delete the adjacencies by one for all the faces
 424                                 that are adjacent to the triangle that we just outputted.
 425                         */
 426                         Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 427                                 &dummy,&dummy,&dummy);
 428                         Delete_AdjEx(in_edge1,vertex4,&dummy,&dummy,
 429                                 face_id,&dummy,&dummy,&dummy);
 430
 431                         /*      Put the new face in the proper bucket of adjacencies */
 432                         next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 433                         next_bucket = Change_FaceEx(face_id,in_edge1,vertex4,pListHead,temp2,FALSE);
 434
 435                         /*      Create a new edgelist without the triangle that
 436                                 was just outputted.
 437                         */
 438                         Delete_From_ListEx(in_edge1,index,size);
 439                         /*      Update the face data structure, by deleting the old
 440                                 face and putting in the polygon minus the triangle
 441                                 as the new face, here we will be decrementing the size
 442                                 by one.
 443                         */
 444                         New_Size_Face(face_id);
 445
 446                         /*      Save the info for the new bucket, we will need it on
 447                                 the next pass for the variables, pListHead and temp
 448                         */
 449                         pListHead = array[next_bucket];
 450                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 451                         if ( pfNode )
 452                                 pfNode->face_id = face_id;
 453                         temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 454                                 (int (*)(void *,void *)) (Compare)));
 455                         if (temp2 == NULL)
 456                         {
 457                                 printf("There is an error finding the next polygon10\n",next_bucket,face_id);
 458                                 exit(0);
 459                         }
 460
 461                         P_Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
 462                                                  vertex4,size-1,index,output,fp,!reversed,
 463                                                  face_id,next_id,pListHead,temp2,where);
 464                 }
 465                 else
 466                 {
 467                         vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
 468                         Output_TriEx(in_edge2,in_edge1,vertex4,output,-1,-1,where);
 469
 470                         /*      Now delete the adjacencies by one for all the faces
 471                                 that are adjacent to the triangle that we just outputted.
 472                         */
 473                         Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 474                                 &dummy,&dummy,&dummy);
 475                         Delete_AdjEx(in_edge2,vertex4,&dummy,&dummy,
 476                                 face_id,&dummy,&dummy,&dummy);
 477
 478                         /*      Put the new face in the proper bucket of adjacencies */
 479                         next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 480                         next_bucket = Change_FaceEx(face_id,in_edge2,vertex4,pListHead,temp2,FALSE);
 481
 482                         /*      Create a new edgelist without the triangle that
 483                                 was just outputted.
 484                         */
 485                         Delete_From_ListEx(in_edge2,index,size);
 486
 487                         /*      Update the face data structure, by deleting the old
 488                                 face and putting in the polygon minus the triangle
 489                                 as the new face, here we will be decrementing the size
 490                                 by one.
 491                         */
 492                         New_Size_Face(face_id);
 493
 494                         /*      Save the info for the new bucket, we will need it on
 495                                 the next pass for the variables, pListHead and temp
 496                         */
 497                         pListHead = array[next_bucket];
 498                         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 499                         if ( pfNode )
 500                                 pfNode->face_id = face_id;
 501                         temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
 502                                 (int (*)(void *,void *)) (Compare)));
 503                         if (temp2 == NULL)
 504                         {
 505                                 printf("There is an error finding the next polygon11 %d %d\n",face_id,next_bucket);
 506                                 exit(0);
 507                         }
 508
 509                         P_Triangulate_Polygon(out_edge1,out_edge2,vertex4,
 510                                                        in_edge1,size-1,index,output,fp,!reversed,
 511                                                        face_id,next_id,pListHead,temp2,where);
 512                 }
 513                 return;
 514         }
 515 }
 516
 517 void P_Triangulate(int out_edge1,int out_edge2,int in_edge1,
 518                                  int in_edge2,int size,int *index,
 519                                  FILE *fp,FILE *output,int reversed,int face_id,
 520                                  int *next_id,ListHead *pListHead,
 521                                  P_ADJACENCIES temp,int where)
 522 {
 523
 524         if (size == 4)
 525                 P_Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
 526                                       index,fp,output,reversed,face_id,next_id,pListHead, temp,where);
 527         else
 528                 P_Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
 529                                          index,fp,output,reversed,face_id,next_id,pListHead,temp,where);
 530 }
 531
 532  void Partial_Triangulate(int size,int *index, FILE *fp,
 533                                                  FILE *output,int next_face_id,int face_id,
 534                                                  int *next_id,ListHead *pListHead,
 535                                                  P_ADJACENCIES temp, int where)
 536 {
 537         int id1,id2,id3;
 538         int nedge1,nedge2;
 539         int reversed;
 540
 541         /*      We have a polygon that has to be triangulated and we cannot
 542                 do it blindly, ie we will try to come out on the edge that
 543                 has the least number of adjacencies, But also we do not
 544                 want to triangulate the whole polygon now, so that means
 545                 we will output the least number of triangles that we can
 546                 and then update the data structures, with the polygon
 547                 that is left after we are done.
 548         */
 549         Last_Edge(&id1,&id2,&id3,0);
 550
 551         /*      Find the edge that is adjacent to the new face ,
 552                 also return whether the orientation is reversed in the
 553                 face of the input edge, which is id2 and id3.
 554         */
 555         reversed = Get_EdgeEx(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
 556
 557         /*   Input edge and output edge can be the same if there are more than
 558           one polygon on an edge
 559      */
 560      if ( ((nedge1 == id2) && (nedge2 == id3)) ||
 561           ((nedge1 == id3) && (nedge2 == id2)) )
 562           /*   Set output edge arbitrarily but when come out of here the
 563                next face will be on the old output edge (identical one)
 564           */
 565           nedge2 = Return_Other(index,id2,id3);
 566
 567           /*    Do the triangulation */
 568         P_Triangulate(nedge1,nedge2,id2,id3,size,index,fp,output,reversed,
 569                          face_id,next_id,pListHead,temp,where);
 570 }
 571
 572  void Input_Edge(int face_id, int *index, int size, int in_edge1, int in_edge2,
 573                 FILE *fp, FILE *output,ListHead *pListHead, P_ADJACENCIES temp2,
 574                 int where)
 575  {
 576      /* The polygon had an input edge, specified by input1 and input2 */
 577
 578      int output1,next_bucket;
 579      int vertex4, vertex5,dummy=60;
 580
 581      output1 = Get_Output_Edge(face_id,size,index,in_edge1,in_edge2);
 582         vertex5 = AdjacentEx(in_edge2,in_edge1,index,size);
 583      vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
 584
 585      if (vertex4 == output1)
 586      {
 587                 Output_TriEx(in_edge2,in_edge1,output1,output,-1,-1,where);
 588                 /*      Now delete the adjacencies by one for all the faces
 589                         that are adjacent to the triangle that we just outputted.
 590                 */
 591                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 592                                 &dummy,&dummy,&dummy);
 593                 Delete_AdjEx(in_edge2,output1,&dummy,&dummy,
 594                                 face_id,&dummy,&dummy,&dummy);
 595                 /*      Put the new face in the proper bucket of adjacencies */
 596                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 597                 next_bucket = Change_FaceEx(face_id,in_edge2,output1,pListHead,temp2,FALSE);
 598
 599                 /*      Create a new edgelist without the triangle that
 600                         was just outputted.
 601                 */
 602           Delete_From_ListEx(in_edge2,index,size);
 603
 604     }
 605     else if (vertex5 == output1)
 606     {
 607           Output_TriEx(in_edge1,in_edge2,vertex5,output,-1,-1,where);
 608                 /*      Now delete the adjacencies by one for all the faces
 609                         that are adjacent to the triangle that we just outputted.
 610                 */
 611                 Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
 612                                 &dummy,&dummy,&dummy);
 613                 Delete_AdjEx(in_edge1,vertex5,&dummy,&dummy,
 614                                 face_id,&dummy,&dummy,&dummy);
 615                 /*      Put the new face in the proper bucket of adjacencies */
 616                 next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,temp2,FALSE);
 617                 next_bucket = Change_FaceEx(face_id,in_edge1,vertex5,pListHead,temp2,FALSE);
 618
 619                 /*      Create a new edgelist without the triangle that
 620                         was just outputted.
 621                 */
 622           Delete_From_ListEx(in_edge1,index,size);
 623     }
 624
 625     /*  Update the face data structure, by deleting the old
 626                 face and putting in the polygon minus the triangle
 627                 as the new face, here we will be decrementing the size
 628                 by one.
 629     */
 630     New_Size_Face(face_id);
 631     return;
 632  }
 633
 634  void Inside_Polygon(int size,int *index,FILE *fp,FILE *output,
 635                    int next_face_id,int face_id,int *next_id,
 636                    ListHead *pListHead,P_ADJACENCIES temp, int where)
 637  {
 638      /* We know that we have a polygon that is greater than 4 sides, and
 639         that it is better for us to go inside the polygon for the next
 640         one, since inside will have less adjacencies than going outside.
 641         So, we are not doing partial for a part of the polygon.
 642       */
 643     int id1,id2,id3;
 644     int new1,new2;
 645
 646     Last_Edge(&id1,&id2,&id3,0);
 647
 648     /*  See if the input edge existed in the polygon, that will help us */
 649         if (Exist(face_id,id2,id3))
 650         Input_Edge(face_id,index,size,id2,id3,output,fp,pListHead,temp,where);
 651     else
 652     {
 653         /*  Make one of the input edges
 654             We will choose it by trying to get an edge that has something
 655             in common with the last triangle, or by getting the edge that
 656             is adjacent to the least number of thigs, with preference given
 657             to the first option
 658         */
 659
 660         Get_Input_Edge(index,id1,id2,id3,&new1,&new2,size,face_id);
 661         Input_Edge(face_id,index,size,new1,new2,output,fp,pListHead,temp,where);
 662     }
 663  }
 664
 665