1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
11 This file contains common code used in both the local and global algorithm
13 /*---------------------------------------------------------------------*/
20 #include "triangulate.h"
24 int Old_Adj(int face_id)
26 /* Find the bucket that the face_id is currently in,
27 because maybe we will be deleting it.
33 pListHead = PolFaces[face_id];
34 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
37 printf("The face was already deleted, there is an error\n");
41 size = temp->nPolSize;
42 if (Done(face_id,size,&y) == NULL)
44 printf("There is an error in finding the face\n");
50 int Number_Adj(int id1, int id2, int curr_id)
52 /* Given edge whose endpoints are specified by id1 and id2,
53 determine how many polygons share this edge and return that
54 number minus one (since we do not want to include the polygon
55 that the caller has already).
60 PF_FACES temp2 = NULL;
64 /* Always want smaller id first */
65 switch_lower(&id1,&id2);
67 pListHead = PolEdges[id1];
68 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
70 /* new edge that was created might not be here */
72 while (temp->edge[0] != id2)
75 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
77 /* This edge was not there in the original, which
78 mean that we created it in the partial triangulation.
79 So it is adjacent to nothing.
83 /* Was not adjacent to anything else except itself */
84 if (temp->edge[2] == -1)
88 /* It was adjacent to another polygon, but maybe we did this
89 polygon already, and it was done partially so that this edge
92 if (curr_id != temp->edge[1])
94 /* Did we use this polygon already?and it was deleted
95 completely from the structure
97 pListHead = PolFaces[temp->edge[1]];
98 temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
99 if (Done(temp->edge[1],temp2->nPolSize,&size) == NULL)
104 pListHead = PolFaces[temp->edge[2]];
105 temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
106 if (Done(temp->edge[2],temp2->nPolSize,&size)== NULL)
110 /* Now we have to check whether it was partially done, before
111 we can say definitely if it is adjacent.
112 Check each edge of the face and tally the number of adjacent
113 polygons to this face.
117 /* Size of the polygon */
118 size = temp2->nPolSize;
119 for (y = 0; y< size; y++)
121 /* If we are doing partial triangulation, we must check
122 to see whether the edge is still there in the polygon,
123 since we might have done a portion of the polygon
124 and saved the rest for later.
128 if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
129 || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
130 /* edge is still there we are ok */
135 if( ((id1 == *(temp2->pPolygon)) && (id2 == *(temp2->pPolygon+size-1)))
136 || ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
137 /* edge is still there we are ok */
151 /* Used for the lookahead to break ties. It will
152 return the minimum adjacency found at this face.
154 int y,numverts,t,x=60;
158 /* If polygon was used then we can't use this face */
159 if (Done(id,59,&y) == NULL)
162 /* It was not used already */
163 pListHead = PolFaces[id];
164 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
167 numverts = temp->nPolSize;
168 for (y = 0; y< numverts; y++)
170 if (y != (numverts-1))
171 t = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),id);
173 t = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+(numverts-1)),id);
180 printf("Error in the look\n");
188 void Edge_Least(int *index,int *new1,int *new2,int face_id,int size)
190 /* We had a polygon without an input edge and now we re going to pick one
191 of the edges with the least number of adjacencies to be the input
194 register int x,value,smallest=60;
196 for (x = 0; x<size; x++)
199 value = Number_Adj(*(index+x),*(index+x+1),face_id);
201 value = Number_Adj(*(index),*(index+size-1),face_id);
202 if (value < smallest)
208 *new2 = *(index+x+1);
213 *new2 = *(index+size-1);
217 if ((smallest == 60) || (smallest < 0))
219 printf("There is an error in getting the least edge\n");
225 void Check_In_Polygon(int face_id, int *min, int size)
227 /* Check to see the adjacencies by going into a polygon that has
228 greater than 4 sides.
233 int y,id1,id2,id3,x=0,z=0;
237 pListHead = PolFaces[face_id];
238 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
240 /* Get the input edge that we came in on */
241 Last_Edge(&id1,&id2,&id3,0);
243 /* Find the number of adjacencies to the edges that are adjacent
246 for (y=0; y< size; y++)
250 if (((*(temp->pPolygon+y) == id2) && (*(temp->pPolygon+y+1) != id3))
251 || ((*(temp->pPolygon+y) == id3) && (*(temp->pPolygon+y+1) != id2)))
253 saved[x++] = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),face_id);
254 big_saved[z++] = saved[x-1];
257 big_saved[z++] = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),face_id);
261 if (((*(temp->pPolygon) == id2) && (*(temp->pPolygon+size-1) != id3))
262 || ((*(temp->pPolygon) == id3) && (*(temp->pPolygon+size-1) != id2)))
264 saved[x++] = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+size-1),face_id);
265 big_saved[z++] = saved[x-1];
268 big_saved[z++] = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+size-1),face_id);
271 /* There was an input edge */
274 if (saved[0] < saved[1])
275 /* Count the polygon that we will be cutting as another adjacency*/
280 /* There was not an input edge */
285 printf("There is an error with the z %d %d\n",size,z);
289 for (x = 0; x < size; x++)
291 if (*min > big_saved[x])
298 void New_Face (int face_id, int v1, int v2, int v3)
300 /* We want to change the face that was face_id, we will
301 change it to a triangle, since the rest of the polygon
302 was already outputtted
305 PF_FACES temp = NULL;
307 pListHead = PolFaces[face_id];
308 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0);
309 /* Check each edge of the face and tally the number of adjacent
310 polygons to this face.
314 /* Size of the polygon */
315 if (temp->nPolSize != 4)
317 printf("There is a miscalculation in the partial\n");
321 *(temp->pPolygon) = v1;
322 *(temp->pPolygon+1) = v2;
323 *(temp->pPolygon+2) = v3;
327 void New_Size_Face (int face_id)
329 /* We want to change the face that was face_id, we will
330 change it to a triangle, since the rest of the polygon
331 was already outputtted
334 PF_FACES temp = NULL;
336 pListHead = PolFaces[face_id];
337 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
338 /* Check each edge of the face and tally the number of adjacent
339 polygons to this face.
344 printf("There is an error in updating the size\n");
349 void Check_In_Quad(int face_id,int *min)
351 /* Check to see what the adjacencies are for the polygons that
352 are inside the quad, ie the 2 triangles that we can form.
355 int y,id1,id2,id3,x=0;
358 register int size = 4;
360 pListHead = PolFaces[face_id];
361 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
363 /* Get the input edge that we came in on */
364 Last_Edge(&id1,&id2,&id3,0);
366 /* Now find the adjacencies for the inside triangles */
367 for (y = 0; y< size; y++)
369 /* Will not do this if the edge is the input edge */
372 if ((((*(temp->pPolygon+y) == id2) && (*(temp->pPolygon+y+1) == id3))) ||
373 (((*(temp->pPolygon+y) == id3) && (*(temp->pPolygon+y+1) == id2))))
379 printf("There is an error in the check in quad \n");
382 /* Save the number of Adjacent Polygons to this edge */
383 saved[x++] = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),face_id);
386 else if ((((*(temp->pPolygon) == id2) && (*(temp->pPolygon+size-1) == id3))) ||
387 (((*(temp->pPolygon) == id3) && (*(temp->pPolygon+size-1) == id2))) )
393 printf("There is an error in the check in quad \n");
396 /* Save the number of Adjacent Polygons to this edge */
397 saved[x++] = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+size-1),face_id);
403 printf("Did not enter all the values %d \n",x);
412 if ((saved[x] != -1) && (saved[x+1] != -1) &&
413 ((saved[x] + saved[x+1]) < *min))
414 *min = saved[x] + saved[x+1];
418 if ((saved[0] != -1) && (saved[x] != -1) &&
419 ((saved[x] + saved[0]) < *min))
420 *min = saved[0] + saved[x];
427 int Get_Output_Edge(int face_id, int size, int *index,int id2,int id3)
429 /* Return the vertex adjacent to either input1 or input2 that
430 is adjacent to the least number of polygons on the edge that
431 is shared with either input1 or input2.
437 for (y = 0; y < size; y++)
441 if (((*(index+y) == id2) && (*(index+y+1) != id3))
442 || ((*(index+y) == id3) && (*(index+y+1) != id2)))
444 saved[x++] = Number_Adj(*(index+y),*(index+y+1),face_id);
445 edges[x-1][0] = *(index+y+1);
449 if (( (*(index+y) == id2) && (*(index+y-1) != id3) ) ||
450 ( (*(index+y) == id3) && (*(index+y-1) != id2)) )
452 saved[x++] = Number_Adj(*(index+y),*(index+y-1),face_id);
453 edges[x-1][0] = *(index+y-1);
458 if (( (*(index) == id2) && (*(index+size-1) != id3) ) ||
459 ( (*(index) == id3) && (*(index+size-1) != id2)) )
461 saved[x++] = Number_Adj(*(index),*(index+size-1),face_id);
462 edges[x-1][0] = *(index+size-1);
469 if (((*(index+size-1) == id2) && (*(index) != id3))
470 || ((*(index+size-1) == id3) && (*(index) != id2)))
472 saved[x++] = Number_Adj(*(index),*(index+size-1),face_id);
473 edges[x-1][0] = *(index);
476 if (( (*(index+size-1) == id2) && (*(index+y-1) != id3) ) ||
477 ( (*(index+size-1) == id3) && (*(index+y-1) != id2)) )
479 saved[x++] = Number_Adj(*(index+size-1),*(index+y-1),face_id);
480 edges[x-1][0] = *(index+y-1);
486 printf("There is an error in getting the input edge %d \n",x);
489 if (saved[0] < saved[1])
496 void Get_Input_Edge(int *index,int id1,int id2,int id3,int *new1,int *new2,int size,
499 /* We had a polygon without an input edge and now we are going to pick one
500 as the input edge. The last triangle was id1,id2,id3, we will try to
501 get an edge to have something in common with one of those vertices, otherwise
502 we will pick the edge with the least number of adjacencies.
512 /* Go through the edges to see if there is one in common with one
513 of the vertices of the last triangle that we had, preferably id2 or
514 id3 since those are the last 2 things in the stack of size 2.
516 for (x=0; x< size; x++)
518 if (*(index+x) == id1)
521 saved[0] = *(index+x+1);
526 if (*(index+x) == id2)
529 saved[1] = *(index+x+1);
534 if (*(index+x) == id3)
537 saved[2] = *(index+x+1);
542 /* Now see what we saved */
549 else if (saved[1] != -1)
555 else if (saved[0] != -1)
561 /* We did not find anything so get the edge with the least number of adjacencies */
562 Edge_Least(index,new1,new2,face_id,size);
566 int Find_Face(int current_face, int id1, int id2, int *bucket)
568 /* Find the face that is adjacent to the edge and is not the
571 register int size,each_poly=0,y,tally=0,count=0;
572 PF_EDGES temp = NULL;
573 PF_FACES temp2 = NULL;
579 /* Always want smaller id first */
580 switch_lower(&id1,&id2);
582 pListHead = PolEdges[id1];
583 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
584 /* The input edge was a new edge */
588 while (temp->edge[0] != id2)
591 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
592 /* The input edge was a new edge */
596 /* Was not adjacent to anything else except itself */
597 if (temp->edge[2] == -1)
601 if (temp->edge[2] == current_face)
602 next_face = temp->edge[1];
604 next_face = temp->edge[2];
606 /* We have the other face adjacent to this edge, it is
609 pListHead = PolFaces[next_face];
610 temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
612 /* See if the face was already deleted, and where
616 if (Done(next_face,59,bucket) == NULL)
619 /* Make sure the edge is still in this polygon, and that it is not
622 /* Size of the polygon */
623 size = temp2->nPolSize;
624 for (y = 0; y< size; y++)
626 /* Make sure that the edge is still in the
627 polygon and was not deleted, because if the edge was
628 deleted, then we used it already.
632 if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
633 || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
634 /* edge is still there we are ok */
639 if( ((id1 == *(temp2->pPolygon)) && (id2 ==*(temp2->pPolygon+size-1)))
640 || ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
641 /* edge is still there we are ok */
647 /* Edge already used and deleted from the polygon*/
653 BOOL Look_Up(int id1,int id2,int face_id)
655 /* See if the endpoints of the edge specified by id1 and id2
656 are adjacent to the face with face_id
658 register int count = 0;
659 PF_EDGES temp = NULL;
661 PF_FACES temp2 = NULL;
663 /* Always want smaller id first */
664 switch_lower(&id1,&id2);
666 pListHead = PolEdges[id1];
667 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
669 /* Was a new edge that we created */
672 while (temp->edge[0] != id2)
675 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
677 /* Was a new edge that we created */
680 /* Was not adjacent to anything else except itself */
681 if ((temp->edge[2] == face_id) || (temp->edge[1] == face_id))
683 /* Edge was adjacent to face, make sure that edge is
686 if (Exist(face_id,id1,id2))
696 void Add_Id_Strips(int id, int where)
698 /* Just save the triangle for later */
701 pfNode = (P_STRIPS) malloc(sizeof(Strips) );
704 pfNode->face_id = id;
706 AddTail(strips[0],(PLISTINFO) pfNode);
707 /* We are backtracking in the strip */
709 AddHead(strips[0],(PLISTINFO) pfNode);
713 printf("There is not enough memory to allocate for the strips\n");
719 int Num_Adj(int id1, int id2)
721 /* Given edge whose endpoints are specified by id1 and id2,
722 determine how many polygons share this edge and return that
723 number minus one (since we do not want to include the polygon
724 that the caller has already).
727 PF_EDGES temp = NULL;
731 /* Always want smaller id first */
732 switch_lower(&id1,&id2);
734 pListHead = PolEdges[id1];
735 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
738 printf("There is an error in the creation of the table \n");
741 while (temp->edge[0] != id2)
744 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
747 printf("There is an error in the creation of the table\n");
751 /* Was not adjacent to anything else except itself */
752 if (temp->edge[2] == -1)
758 void Add_Sgi_Adj(int bucket,int face_id)
760 /* This routine will add the face to the proper bucket,
761 depending on how many faces are adjacent to it (what the
762 value bucket should be).
764 P_ADJACENCIES pfNode;
766 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
769 pfNode->face_id = face_id;
770 AddHead(array[bucket],(PLISTINFO) pfNode);
774 printf("Out of memory for the SGI adj list!\n");
779 void Find_Adjacencies(int num_faces)
782 register int numverts;
786 /* Fill in the adjacencies data structure for all the faces */
787 for (x=0;x<num_faces;x++)
789 pListHead = PolFaces[x];
790 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
793 numverts = temp->nPolSize;
796 for (y = 0; y< numverts; y++)
798 if (y != (numverts-1))
799 Add_AdjEdge(*(temp->pPolygon+y),*(temp->pPolygon+y+1),x,y);
802 Add_AdjEdge(*(temp->pPolygon),*(temp->pPolygon+(numverts-1)),x,numverts-1);