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 "polyvertsex.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,
269 face_id,next_id,pListHead,temp2,where); */
270 Triangulate_PolygonEx(vertex4,out_edge1,in_edge2,
271 vertex4,size-1,index,output,fp,reversed,
273 memcpy(index,temp,sizeof(int)*size);
274 /* Lastly do the triangle that comes out the output
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.
281 dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
282 RemoveList(pListHead,(PLISTINFO) temp2);
286 /* These are the 5 cases that we can have for the output edge */
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?
292 if (in_edge2 == out_edge1)
294 Output_TriEx(in_edge1,out_edge1,out_edge2,output,-1,-1,where);
296 /* Now delete the adjacencies by one for all the faces
297 that are adjacent to the triangle that we just outputted.
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);
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);
308 /* Create a new edgelist without the triangle that
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
317 New_Size_Face(face_id);
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
326 else if (in_edge1 == out_edge1)
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);
331 /* Now delete the adjacencies by one for all the faces
332 that are adjacent to the triangle that we just outputted.
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);
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);
343 /* Create a new edgelist without the triangle that
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
352 New_Size_Face(face_id);
356 /* Consecutive cases again, but with the output edge reversed */
357 else if (in_edge1 == out_edge2)
359 Output_TriEx(in_edge2,in_edge1,out_edge1,output,-1,-1,where);
361 /* Now delete the adjacencies by one for all the faces
362 that are adjacent to the triangle that we just outputted.
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);
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);
373 /* Create a new edgelist without the triangle that
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
382 New_Size_Face(face_id);
385 else if (in_edge2 == out_edge2)
387 Output_TriEx(in_edge1,in_edge2,out_edge1,output,-1,-1,where);
389 /* Now delete the adjacencies by one for all the faces
390 that are adjacent to the triangle that we just outputted.
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);
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);
401 /* Create a new edgelist without the triangle that
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
410 New_Size_Face(face_id);
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
423 vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
424 Output_TriEx(in_edge1,in_edge2,vertex4,output,-1,-1,where);
426 /* Now delete the adjacencies by one for all the faces
427 that are adjacent to the triangle that we just outputted.
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);
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);
438 /* Create a new edgelist without the triangle that
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
447 New_Size_Face(face_id);
449 /* Save the info for the new bucket, we will need it on
450 the next pass for the variables, pListHead and temp
452 pListHead = array[next_bucket];
453 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
455 pfNode->face_id = face_id;
456 temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
457 (int (*)(void *,void *)) (Compare)));
460 printf("There is an error finding the next polygon10 %d %d\n",next_bucket,face_id);
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);
470 vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
471 Output_TriEx(in_edge2,in_edge1,vertex4,output,-1,-1,where);
473 /* Now delete the adjacencies by one for all the faces
474 that are adjacent to the triangle that we just outputted.
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);
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);
485 /* Create a new edgelist without the triangle that
488 Delete_From_ListEx(in_edge2,index,size);
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
495 New_Size_Face(face_id);
497 /* Save the info for the new bucket, we will need it on
498 the next pass for the variables, pListHead and temp
500 pListHead = array[next_bucket];
501 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
503 pfNode->face_id = face_id;
504 temp2 = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
505 (int (*)(void *,void *)) (Compare)));
508 printf("There is an error finding the next polygon11 %d %d\n",face_id,next_bucket);
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);
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)
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);
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);
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)
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.
552 Last_Edge(&id1,&id2,&id3,0);
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.
558 reversed = Get_EdgeEx(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
560 /* Input edge and output edge can be the same if there are more than
561 one polygon on an edge
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)
568 nedge2 = Return_Other(index,id2,id3);
570 /* Do the triangulation */
571 P_Triangulate(nedge1,nedge2,id2,id3,size,index,fp,output,reversed,
572 face_id,next_id,pListHead,temp,where);
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,
579 /* The polygon had an input edge, specified by input1 and input2 */
582 int vertex4, vertex5,dummy=60;
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);
588 if (vertex4 == output1)
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.
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);
602 /* Create a new edgelist without the triangle that
605 Delete_From_ListEx(in_edge2,index,size);
608 else if (vertex5 == output1)
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.
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);
622 /* Create a new edgelist without the triangle that
625 Delete_From_ListEx(in_edge1,index,size);
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
633 New_Size_Face(face_id);
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)
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.
649 Last_Edge(&id1,&id2,&id3,0);
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);
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
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);