1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
10 /* STRIPE: sgi_triangex.c
11 This file contains routines that are used for various functions in
14 /*---------------------------------------------------------------------*/
22 #include "sturctsex.h"
27 int AdjacentEx(int id2,int id1, int *list, int size)
29 /* Return the vertex that is adjacent to id1,
30 but is not id2, in the list of integers.
39 if ((x != (size -1)) && (x != 0))
41 if ( *(list+x+1) != id2)
46 else if (x == (size -1))
55 if (*(list+size-1) != id2)
56 return *(list+size-1);
63 printf("Error in the list\n");
68 void Delete_From_ListEx(int id,int *list, int size)
70 /* Delete the occurence of id in the list.
77 temp = (int *) malloc(sizeof(int) * size);
78 for (x=0; x<size; x++)
82 *(temp+y) = *(list+x);
88 printf("There is an error in the delete\n");
92 memcpy(list,temp,sizeof(int)*size);
97 void Triangulate_QuadEx(int out_edge1,int out_edge2,int in_edge1,
98 int in_edge2,int size,int *index,
99 FILE *output,FILE *fp,int reversed,int face_id,
104 /* This routine will nonblindly triangulate a quad, meaning
105 that there is a definite input and a definite output
106 edge that we must adhere to. Reversed will tell the orientation
107 of the input edge. (Reversed is -1 is we do not have an input
108 edge, in other words we are at the beginning of a strip.)
109 Out_edge* is the output edge, and in_edge* is the input edge.
110 Index are the edges of the polygon
111 and size is the size of the polygon. Begin is whether we are
112 at the start of a new strip.
115 /* If we do not have an input edge, then we can make our input
116 edge whatever we like, therefore it will be easier to come
117 out on the output edge.
121 vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
122 vertex5 = Get_Other_Vertex(vertex4,out_edge1,out_edge2,index);
123 Output_TriEx(vertex5,vertex4,out_edge1,output,-1,-1,where);
124 Output_TriEx(vertex4,out_edge1,out_edge2,output,-1,-1,where);
128 /* These are the 5 cases that we can have for the output edge */
130 /* Are they consecutive so that we form a triangle to
131 peel off, but cannot use the whole quad?
134 if (in_edge2 == out_edge1)
136 /* Output the triangle that comes out the correct
137 edge last. First output the triangle that comes out
140 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
141 Output_TriEx(in_edge1,in_edge2,vertex4,output,-1,-1,where);
142 Output_TriEx(vertex4,in_edge2,out_edge2,output,-1,-1,where);
145 /* The next case is where it is impossible to come out the
146 edge that we want. So we will have to start a new strip to
147 come out on that edge. We will output the one triangle
148 that we can, and then start the new strip with the triangle
149 that comes out on the edge that we want to come out on.
151 else if (in_edge1 == out_edge1)
153 /* We want to output the first triangle (whose output
154 edge is not the one that we want.
155 We have to find the vertex that we need, which is
156 the other vertex which we do not have.
158 vertex4 = Get_Other_Vertex(in_edge2,in_edge1,out_edge2,index);
159 Output_TriEx(in_edge2,in_edge1,vertex4,output,-1,-1,where);
160 Output_TriEx(vertex4,in_edge1,out_edge2,output,-1,-1,where);
164 /* Consecutive cases again, but with the output edge reversed */
165 else if (in_edge1 == out_edge2)
167 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
168 Output_TriEx(in_edge2,in_edge1,vertex4,output,-1,-1,where);
169 Output_TriEx(vertex4,in_edge1,out_edge1,output,-1,-1,where);
172 else if (in_edge2 == out_edge2)
174 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
175 Output_TriEx(in_edge1,in_edge2,vertex4,output,-1,-1,where);
176 Output_TriEx(vertex4,in_edge2,out_edge1,output,-1,-1,where);
180 /* The final case is where we want to come out the opposite edge.*/
183 if( ((!reversed) && (out_edge1 == (AdjacentEx(in_edge1,in_edge2,index,size)))) ||
184 ((reversed) && (out_edge2 == (AdjacentEx(in_edge2,in_edge1,index,size)))))
186 /* We need to know the orientation of the input
187 edge, so we know which way to put the diagonal.
188 And also the output edge, so that we triangulate correctly.
190 Output_TriEx(in_edge1,in_edge2,out_edge2,output,-1,-1,where);
191 Output_TriEx(in_edge2,out_edge2,out_edge1,output,-1,-1,where);
195 /* Input and output orientation was reversed, so diagonal will
196 be reversed from above.
198 Output_TriEx(in_edge1,in_edge2,out_edge1,output,-1,-1,where);
199 Output_TriEx(in_edge2,out_edge1,out_edge2,output,-1,-1,where);
205 void Triangulate_PolygonEx(int out_edge1,int out_edge2,int in_edge1,
206 int in_edge2,int size,int *index,
207 FILE *output,FILE *fp,int reversed,int face_id,
210 /* We have a polygon that we need to nonblindly triangulate.
211 We will recursively try to triangulate it, until we are left
212 with a polygon of size 4, which can use the quad routine
213 from above. We will be taking off a triangle at a time
214 and outputting it. We will have 3 cases similar to the
215 cases for the quad above. The inputs to this routine
216 are the same as for the quad routine.
223 /* Since we are calling this recursively, we have to check whether
224 we are down to the case of the quad.
229 Triangulate_QuadEx(out_edge1,out_edge2,in_edge1,in_edge2,size,
230 index,output,fp,reversed,face_id,where);
236 /* We do not have a specified input edge, and therefore we
237 can make it anything we like, as long as we still come out
238 the output edge that we want.
242 /* Get the vertex for the last triangle, which is
243 the one coming out the output edge, before we do
244 any deletions to the list. We will be doing this
247 vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
248 temp = (int *) malloc(sizeof(int) * size);
249 memcpy(temp,index,sizeof(int)*size);
250 Delete_From_ListEx(out_edge2,index,size);
251 Triangulate_PolygonEx(out_edge1,vertex4,in_edge2,
252 vertex4,size-1,index,output,fp,reversed,face_id,where);
253 memcpy(index,temp,sizeof(int)*size);
254 /* Lastly do the triangle that comes out the output
257 Output_TriEx(vertex4,out_edge1,out_edge2,output,-1,-1,where);
261 /* These are the 5 cases that we can have for the output edge */
263 /* Are they consecutive so that we form a triangle to
264 peel off that comes out the correct output edge,
265 but we cannot use the whole polygon?
267 if (in_edge2 == out_edge1)
269 /* Output the triangle that comes out the correct
270 edge last. First recursively do the rest of the
273 /* Do the rest of the polygon without the triangle.
274 We will be doing a fan triangulation.
276 /* Get the vertex adjacent to in_edge1, but is not
279 vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
280 Output_TriEx(in_edge1,in_edge2,vertex4,output,-1,-1,where);
281 /* Create a new edgelist without the triangle that
284 temp = (int *) malloc(sizeof(int) * size);
285 memcpy(temp,index,sizeof(int)*size);
286 Delete_From_ListEx(in_edge1,index,size);
287 Triangulate_PolygonEx(out_edge1,out_edge2,in_edge2,
288 vertex4,size-1,index,output,fp,!reversed,face_id,where);
289 memcpy(index,temp,sizeof(int)*size);
293 /* Next case is where it is again consecutive, but the triangle
294 formed by the consecutive edges do not come out of the
295 correct output edge. For this case, we can not do much to
296 keep it sequential. Try and do the fan.
298 else if (in_edge1 == out_edge1)
300 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
301 vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
302 Output_TriEx(in_edge1,in_edge2,vertex4,fp,-1,-1,where);
303 /* Since that triangle goes out of the polygon (the
304 output edge of it), we can make our new input edge
305 anything we like, so we will try to make it good for
306 the strip. (This will be like starting a new strip,
307 all so that we can go out the correct output edge.)
309 temp = (int *) malloc(sizeof(int) * size);
310 memcpy(temp,index,sizeof(int)*size);
311 Delete_From_ListEx(in_edge2,index,size);
312 Triangulate_PolygonEx(out_edge1,out_edge2,in_edge1,
313 vertex4,size-1,index,output,fp,reversed,face_id,where);
314 memcpy(index,temp,sizeof(int)*size);
317 /* Consecutive cases again, but with the output edge reversed */
318 else if (in_edge1 == out_edge2)
320 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
321 vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
322 Output_TriEx(in_edge2,in_edge1,vertex4,fp,-1,-1,where);
323 temp = (int *) malloc(sizeof(int) * size);
324 memcpy(temp,index,sizeof(int)*size);
325 Delete_From_ListEx(in_edge2,index,size);
326 Triangulate_PolygonEx(out_edge1,out_edge2,in_edge1,
327 vertex4,size-1,index,output,fp,reversed,face_id,where);
328 memcpy(index,temp,sizeof(int)*size);
331 else if (in_edge2 == out_edge2)
333 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
334 vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
335 Output_TriEx(in_edge1,in_edge2,vertex4,fp,-1,-1,where);
336 temp = (int *) malloc(sizeof(int) * size);
337 memcpy(temp,index,sizeof(int)*size);
338 Delete_From_ListEx(in_edge1,index,size);
339 Triangulate_PolygonEx(out_edge1,out_edge2,vertex4,
340 in_edge2,size-1,index,output,fp,reversed,face_id,where);
341 memcpy(index,temp,sizeof(int)*size);
345 /* Else the edge is not consecutive, and it is sufficiently
346 far away, for us not to make a conclusion at this time.
347 So we can take off a triangle and recursively call this
352 vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
353 Output_TriEx(in_edge1,in_edge2,vertex4,fp,-1,-1,where);
354 temp = (int *) malloc(sizeof(int) * size);
355 memcpy(temp,index,sizeof(int)*size);
356 Delete_From_ListEx(in_edge1,index,size);
357 Triangulate_PolygonEx(out_edge1,out_edge2,in_edge2,
358 vertex4,size-1,index,output,fp,!reversed,face_id,where);
359 memcpy(index,temp,sizeof(int)*size);
364 void TriangulateEx(int out_edge1,int out_edge2,int in_edge1,
365 int in_edge2,int size,int *index,
366 FILE *fp,FILE *output,int reversed,int face_id, int where)
368 /* We have the info we need to triangulate a polygon */
371 Triangulate_QuadEx(out_edge1,out_edge2,in_edge1,in_edge2,size,
372 index,fp,output,reversed,face_id,where);
374 Triangulate_PolygonEx(out_edge1,out_edge2,in_edge1,in_edge2,size,
375 index,fp,output,reversed,face_id,where);
378 void Non_Blind_TriangulateEx(int size,int *index, FILE *fp,
379 FILE *output,int next_face_id,int face_id,int where)
384 /* We have a polygon that has to be triangulated and we cannot
385 do it blindly, ie we will try to come out on the edge that
386 has the least number of adjacencies
389 Last_Edge(&id1,&id2,&id3,0);
390 /* Find the edge that is adjacent to the new face ,
391 also return whether the orientation is reversed in the
392 face of the input edge, which is id2 and id3.
394 if (next_face_id == -1)
396 printf("The face is -1 and the size is %d\n",size);
400 reversed = Get_EdgeEx(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
401 /* Do the triangulation */
403 /* If reversed is -1, the input edge is not in the polygon, therefore we can have the
404 input edge to be anything we like, since we are at the beginning
407 TriangulateEx(nedge1,nedge2,id2,id3,size,index,fp,output,reversed,
411 void Rearrange_IndexEx(int *index, int size)
413 /* If we are in the middle of a strip we must find the
414 edge to start on, which is the last edge that we had
421 /* Find where the input edge is in the input list */
422 Last_Edge(&e1,&e2,&e3,0);
423 for (y = 0; y < size; y++)
425 if (*(index+y) == e2)
427 if ((y != (size - 1)) && (*(index+y+1) == e3))
429 else if ((y == (size - 1)) && (*(index) == e3))
431 else if ((y != 0) && (*(index+y-1) == e3))
436 else if ((y==0) && (*(index+size-1) == e3))
442 if (*(index+y) == e3)
444 if ((y != (size - 1)) && (*(index+y+1) == e2))
446 else if ((y == (size - 1)) && (*(index) == e2))
448 else if ((y != 0) && (*(index+y-1) == e2))
453 else if ((y==0) && (*(index+size-1) == e2))
459 /* Edge is not here, we are at the beginning */
460 if ((y == (size-1)) && (increment != -1))
464 /* Now put the list into a new list, starting with the
465 input edge. Increment tells us whether we have to go
468 /* Was in good position already */
469 if ((y == 0) && (increment == 1))
473 temp = (int *) malloc(sizeof(int) * size);
474 memcpy(temp,index,sizeof(int)*size);
479 for (f = y ; f< size; f++)
481 *(index+x) = *(temp+f);
484 /* Finish the rest of the list */
485 for(f = 0; f < y ; f++)
487 *(index+x) = *(temp+f);
494 for (f = y ; f >= 0; f--)
496 *(index+x) = *(temp+f);
499 /* Finish the rest of the list */
500 for(f = (size - 1); f > y ; f--)
502 *(index+x) = *(temp+f);
508 void Blind_TriangulateEx(int size, int *index, FILE *fp,
509 FILE *output, BOOL begin, int where )
511 /* save sides in temp array, we need it so we know
514 int mode, decreasing,increasing,e1,e2,e3;
516 /* Rearrange the index list so that the input edge is first
519 Rearrange_IndexEx(index,size);
521 /* We are given a polygon of more than 3 sides
522 and want to triangulate it. We will output the
523 triangles to the output file.
526 /* Find where the input edge is in the input list */
527 Last_Edge(&e1,&e2,&e3,0);
528 if (( (!begin) && (*(index) == e2) ) || (begin))
530 Output_TriEx(*(index+0),*(index+1),*(index+size-1),fp,-1,-1,where);
531 /* If we have a quad, (chances are yes), then we know that
532 we can just add one diagonal and be done. (divide the
533 quad into 2 triangles.
537 Output_TriEx(*(index+1),*(index+size-1),*(index+2),fp,-1,-1,where);
546 Output_TriEx(*(index+1),*(index+0),*(index+size-1),fp,-1,-1,where);
549 Output_TriEx(*(index+0),*(index+size-1),*(index+2),fp,-1,-1,where);
552 Output_TriEx(*(index+0),*(index+size-1),*(index+2),fp,-1,-1,where);
558 /* We do not have a quad, we have something bigger. */
559 decreasing = size - 1;
563 /* Will be alternating diagonals, so we will be increasing
564 and decreasing around the polygon.
568 Output_TriEx(*(index+increasing),*(index+decreasing),*(index+increasing+1),fp,-1,-1,where);
573 Output_TriEx(*(index+decreasing),*(index+increasing),*(index+decreasing-1),fp,-1,-1,where);
577 } while ((decreasing - increasing) >= 2);