1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
11 This file contains routines that are used partial triangulation of polygons
13 /*---------------------------------------------------------------------*/
20 #include "polvertsex.h"
21 #include "triangulatex.h"
22 #include "sturctsex.h"
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,
34 int vertex4,vertex5,dummy=60;
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)
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.
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);
66 /* These are the 5 cases that we can have for the output edge */
68 /* Are they consecutive so that we form a triangle to
69 peel off, but cannot use the whole quad?
72 if (in_edge2 == out_edge1)
74 /* Output the triangle that comes out the correct
75 edge. Save the other half for later.
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
83 /* Now delete the adjacencies by one for all the faces
84 that are adjacent to the triangle that we just outputted.
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
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);
100 /* Update the face data structure, by deleting the old
101 face and putting in the triangle as the new face
103 New_Face(face_id,in_edge1,out_edge2,vertex4);
106 else if (in_edge1 == out_edge1)
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.
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
119 /* Now delete the adjacencies by one for all the faces
120 that are adjacent to the triangle that we just outputted.
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);
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);
131 /* Update the face data structure, by deleting the old
132 face and putting in the triangle as the new face
134 New_Face(face_id,in_edge2,out_edge2,vertex4);
138 /* Consecutive cases again, but with the output edge reversed */
139 else if (in_edge1 == out_edge2)
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
147 /* Now delete the adjacencies by one for all the faces
148 that are adjacent to the triangle that we just outputted.
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);
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);
159 /* Update the face data structure, by deleting the old
160 face and putting in the triangle as the new face
162 New_Face(face_id,in_edge2,out_edge1,vertex4);
165 else if (in_edge2 == out_edge2)
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
172 /* Now delete the adjacencies by one for all the faces
173 that are adjacent to the triangle that we just outputted.
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);
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);
184 /* Update the face data structure, by deleting the old
185 face and putting in the triangle as the new face
187 New_Face(face_id,in_edge1,out_edge1,vertex4);
191 /* The final case is where we want to come out the opposite
196 if( ((!reversed) && (out_edge1 == (AdjacentEx(in_edge1,in_edge2,index,size)))) ||
197 ((reversed) && (out_edge2 == (AdjacentEx(in_edge2,in_edge1,index,size)))))
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.
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);
211 /* Input and output orientation was reversed, so diagonal will
212 be reversed from above.
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);
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,
230 /* We have a polygon greater than 4 sides, which we wish
231 to partially triangulate
233 int next_bucket,vertex4,dummy = 60;
235 P_ADJACENCIES pfNode;
238 /* Since we are calling this recursively, we have to check whether
239 we are down to the case of the quad.
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);
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.
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
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
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
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.
278 dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
279 RemoveList(pListHead,(PLISTINFO) temp2);
283 /* These are the 5 cases that we can have for the output edge */
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?
289 if (in_edge2 == out_edge1)
291 Output_TriEx(in_edge1,out_edge1,out_edge2,output,-1,-1,where);
293 /* Now delete the adjacencies by one for all the faces
294 that are adjacent to the triangle that we just outputted.
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);
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);
305 /* Create a new edgelist without the triangle that
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
314 New_Size_Face(face_id);
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
323 else if (in_edge1 == out_edge1)
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);
328 /* Now delete the adjacencies by one for all the faces
329 that are adjacent to the triangle that we just outputted.
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);
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);
340 /* Create a new edgelist without the triangle that
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
349 New_Size_Face(face_id);
353 /* Consecutive cases again, but with the output edge reversed */
354 else if (in_edge1 == out_edge2)
356 Output_TriEx(in_edge2,in_edge1,out_edge1,output,-1,-1,where);
358 /* Now delete the adjacencies by one for all the faces
359 that are adjacent to the triangle that we just outputted.
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);
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);
370 /* Create a new edgelist without the triangle that
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
379 New_Size_Face(face_id);
382 else if (in_edge2 == out_edge2)
384 Output_TriEx(in_edge1,in_edge2,out_edge1,output,-1,-1,where);
386 /* Now delete the adjacencies by one for all the faces
387 that are adjacent to the triangle that we just outputted.
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);
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);
398 /* Create a new edgelist without the triangle that
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
407 New_Size_Face(face_id);
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
420 vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
421 Output_TriEx(in_edge1,in_edge2,vertex4,output,-1,-1,where);
423 /* Now delete the adjacencies by one for all the faces
424 that are adjacent to the triangle that we just outputted.
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);
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);
435 /* Create a new edgelist without the triangle that
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
444 New_Size_Face(face_id);
446 /* Save the info for the new bucket, we will need it on
447 the next pass for the variables, pListHead and temp
449 pListHead = array[next_bucket];
450 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
452 pfNode->face_id = face_id;
453 temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
454 (int (*)(void *,void *)) (Compare)));
457 printf("There is an error finding the next polygon10\n",next_bucket,face_id);
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);
467 vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
468 Output_TriEx(in_edge2,in_edge1,vertex4,output,-1,-1,where);
470 /* Now delete the adjacencies by one for all the faces
471 that are adjacent to the triangle that we just outputted.
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);
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);
482 /* Create a new edgelist without the triangle that
485 Delete_From_ListEx(in_edge2,index,size);
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
492 New_Size_Face(face_id);
494 /* Save the info for the new bucket, we will need it on
495 the next pass for the variables, pListHead and temp
497 pListHead = array[next_bucket];
498 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
500 pfNode->face_id = face_id;
501 temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
502 (int (*)(void *,void *)) (Compare)));
505 printf("There is an error finding the next polygon11 %d %d\n",face_id,next_bucket);
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);
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)
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);
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);
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)
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.
549 Last_Edge(&id1,&id2,&id3,0);
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.
555 reversed = Get_EdgeEx(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
557 /* Input edge and output edge can be the same if there are more than
558 one polygon on an edge
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)
565 nedge2 = Return_Other(index,id2,id3);
567 /* Do the triangulation */
568 P_Triangulate(nedge1,nedge2,id2,id3,size,index,fp,output,reversed,
569 face_id,next_id,pListHead,temp,where);
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,
576 /* The polygon had an input edge, specified by input1 and input2 */
578 int output1,next_bucket;
579 int vertex4, vertex5,dummy=60;
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);
585 if (vertex4 == output1)
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.
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);
599 /* Create a new edgelist without the triangle that
602 Delete_From_ListEx(in_edge2,index,size);
605 else if (vertex5 == output1)
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.
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);
619 /* Create a new edgelist without the triangle that
622 Delete_From_ListEx(in_edge1,index,size);
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
630 New_Size_Face(face_id);
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)
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.
646 Last_Edge(&id1,&id2,&id3,0);
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);
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
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);