1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
10 /* STRIPE: sgi_triang.c
11 File contains the routines that do the whole triangulation
14 /*---------------------------------------------------------------------*/
27 int Adjacent(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 /* if there are degeneracies */
68 void Rearrange_Index(int *index, int size)
70 /* If we are in the middle of a strip we must find the
71 edge to start on, which is the last edge that we had
75 register int increment = 1;
78 /* Find where the input edge is in the input list */
79 Last_Edge(&e1,&e2,&e3,0);
80 for (y = 0; y < size; y++)
84 if ((y != (size - 1)) && (*(index+y+1) == e3))
86 else if ((y == (size - 1)) && (*(index) == e3))
88 else if ((y != 0) && (*(index+y-1) == e3))
93 else if ((y==0) && (*(index+size-1) == e3))
101 if ((y != (size - 1)) && (*(index+y+1) == e2))
103 else if ((y == (size - 1)) && (*(index) == e2))
105 else if ((y != 0) && (*(index+y-1) == e2))
110 else if ((y==0) && (*(index+size-1) == e2))
116 /* Edge is not here, we are at the beginning */
117 if ((y == (size-1)) && (increment != -1))
121 /* Now put the list into a new list, starting with the
122 input edge. Increment tells us whether we have to go
125 /* Was in good position already */
126 if ((y == 0) && (increment == 1))
129 temp = (int *) malloc(sizeof(int) * size);
130 memcpy(temp,index,sizeof(int)*size);
135 for (f = y ; f< size; f++)
137 *(index+x) = *(temp+f);
140 /* Finish the rest of the list */
141 for(f = 0; f < y ; f++)
143 *(index+x) = *(temp+f);
150 for (f = y ; f >= 0; f--)
152 *(index+x) = *(temp+f);
155 /* Finish the rest of the list */
156 for(f = (size - 1); f > y ; f--)
158 *(index+x) = *(temp+f);
164 void Delete_From_List(int id,int *list, int *size)
166 /* Delete the occurence of id in the list.
173 temp = (int *) malloc(sizeof(int) * (*size));
174 for (x=0; x<(*size); x++)
178 *(temp+y) = *(list+x);
183 *size = *size - (*size - y - 1);
184 memcpy(list,temp,sizeof(int)*(*size));
188 void Build_SGI_Table(int num_verts,int num_faces)
190 /* Build a table that has the polygons sorted by the
191 number of adjacent polygons.
193 int x,y,size,tally=0;
195 PF_FACES temp = NULL;
197 /* For each face....*/
198 for (x=0;x < num_faces;x++)
200 pListHead = PolFaces[x];
201 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
202 /* Check each edge of the face and tally the number of adjacent
203 polygons to this face.
207 /* Size of the polygon */
208 size = temp->nPolSize;
211 for (y = 0; y< size; y++)
214 tally += Num_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1));
216 tally += Num_Adj(*(temp->pPolygon),*(temp->pPolygon+(size-1)));
219 /* Tally is the number of polygons that is adjacent to
222 /* Now put the face in the proper bucket depending on tally. */
223 Add_Sgi_Adj(tally,x);
232 void Triangulate_Quad(int out_edge1,int out_edge2,int in_edge1,
233 int in_edge2,int size,int *index,
234 FILE *output,int reversed,int face_id,
235 int where,int color1,int color2,int color3)
239 /* This routine will nonblindly triangulate a quad, meaning
240 that there is a definite input and a definite output
241 edge that we must adhere to. Reversed will tell the orientation
242 of the input edge. (Reversed is -1 is we do not have an input
243 edge, in other words we are at the beginning of a strip.)
244 Out_edge* is the output edge, and in_edge* is the input edge.
245 Index are the edges of the polygon
246 and size is the size of the polygon. Begin is whether we are
247 at the start of a new strip.
250 /* If we do not have an input edge, then we can make our input
251 edge whatever we like, therefore it will be easier to come
252 out on the output edge.
256 vertex4 = Adjacent(out_edge1,out_edge2,index,size);
257 vertex5 = Get_Other_Vertex(vertex4,out_edge1,out_edge2,index);
258 Output_Tri(vertex5,vertex4,out_edge1,output,color1,color2,color3,where);
259 Output_Tri(vertex4,out_edge1,out_edge2,output,color1,color2,color3,where);
263 /* These are the 5 cases that we can have for the output edge */
265 /* Are they consecutive so that we form a triangle to
266 peel off, but cannot use the whole quad?
269 if (in_edge2 == out_edge1)
271 /* Output the triangle that comes out the correct
272 edge last. First output the triangle that comes out
275 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
276 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
277 Output_Tri(vertex4,in_edge2,out_edge2,output,color1,color2,color3,where);
280 /* The next case is where it is impossible to come out the
281 edge that we want. So we will have to start a new strip to
282 come out on that edge. We will output the one triangle
283 that we can, and then start the new strip with the triangle
284 that comes out on the edge that we want to come out on.
286 else if (in_edge1 == out_edge1)
288 /* We want to output the first triangle (whose output
289 edge is not the one that we want.
290 We have to find the vertex that we need, which is
291 the other vertex which we do not have.
293 vertex4 = Get_Other_Vertex(in_edge2,in_edge1,out_edge2,index);
294 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where);
295 Output_Tri(vertex4,in_edge1,out_edge2,output,color1,color2,color3,where);
299 /* Consecutive cases again, but with the output edge reversed */
300 else if (in_edge1 == out_edge2)
302 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
303 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where);
304 Output_Tri(vertex4,in_edge1,out_edge1,output,color1,color2,color3,where);
307 else if (in_edge2 == out_edge2)
309 vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
310 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
311 Output_Tri(vertex4,in_edge2,out_edge1,output,color1,color2,color3,where);
315 /* The final case is where we want to come out the opposite
320 if( ((!reversed) && (out_edge1 == (Adjacent(in_edge1,in_edge2,index,size)))) ||
321 ((reversed) && (out_edge2 == (Adjacent(in_edge2,in_edge1,index,size)))))
323 /* We need to know the orientation of the input
324 edge, so we know which way to put the diagonal.
325 And also the output edge, so that we triangulate
328 Output_Tri(in_edge1,in_edge2,out_edge2,output,color1,color2,color3,where);
329 Output_Tri(in_edge2,out_edge2,out_edge1,output,color1,color2,color3,where);
333 /* Input and output orientation was reversed, so diagonal will
334 be reversed from above.
336 Output_Tri(in_edge1,in_edge2,out_edge1,output,color1,color2,color3,where);
337 Output_Tri(in_edge2,out_edge1,out_edge2,output,color1,color2,color3,where);
343 void Triangulate_Polygon(int out_edge1, int out_edge2, int in_edge1,
344 int in_edge2, int size, int *index,
345 FILE *output, int reversed, int face_id,
346 int where, int color1, int color2, int color3)
348 /* We have a polygon that we need to nonblindly triangulate.
349 We will recursively try to triangulate it, until we are left
350 with a polygon of size 4, which can use the quad routine
351 from above. We will be taking off a triangle at a time
352 and outputting it. We will have 3 cases similar to the
353 cases for the quad above. The inputs to this routine
354 are the same as for the quad routine.
360 /* Since we are calling this recursively, we have to check whether
361 we are down to the case of the quad.
366 Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
367 index,output,reversed,face_id,where,color1,color2,color3);
373 /* We do not have a specified input edge, and therefore we
374 can make it anything we like, as long as we still come out
375 the output edge that we want.
379 /* Get the vertex for the last triangle, which is
380 the one coming out the output edge, before we do
381 any deletions to the list. We will be doing this
384 vertex4 = Adjacent(out_edge1,out_edge2,index,size);
385 temp = (int *) malloc(sizeof(int) * size);
386 memcpy(temp,index,sizeof(int)*size);
387 Delete_From_List(out_edge2,index,&size);
388 Triangulate_Polygon(out_edge1,vertex4,in_edge2,
389 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
390 memcpy(index,temp,sizeof(int)*size);
391 /* Lastly do the triangle that comes out the output
394 Output_Tri(vertex4,out_edge1,out_edge2,output,color1,color2,color3,where);
398 /* These are the 5 cases that we can have for the output edge */
400 /* Are they consecutive so that we form a triangle to
401 peel off that comes out the correct output edge,
402 but we cannot use the whole polygon?
404 if (in_edge2 == out_edge1)
406 /* Output the triangle that comes out the correct
407 edge last. First recursively do the rest of the
410 /* Do the rest of the polygon without the triangle.
411 We will be doing a fan triangulation.
413 /* Get the vertex adjacent to in_edge1, but is not
416 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
417 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
418 /* Create a new edgelist without the triangle that
421 temp = (int *) malloc(sizeof(int) * size);
422 memcpy(temp,index,sizeof(int)*size);
423 Delete_From_List(in_edge1,index,&size);
424 Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
425 vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
426 memcpy(index,temp,sizeof(int)*size);
430 /* Next case is where it is again consecutive, but the triangle
431 formed by the consecutive edges do not come out of the
432 correct output edge. For this case, we can not do much to
433 keep it sequential. Try and do the fan.
435 else if (in_edge1 == out_edge1)
437 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
438 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
439 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
440 /* Since that triangle goes out of the polygon (the
441 output edge of it), we can make our new input edge
442 anything we like, so we will try to make it good for
443 the strip. (This will be like starting a new strip,
444 all so that we can go out the correct output edge.)
446 temp = (int *) malloc(sizeof(int) * size);
447 memcpy(temp,index,sizeof(int)*size);
448 Delete_From_List(in_edge2,index,&size);
449 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
450 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
451 memcpy(index,temp,sizeof(int)*size);
454 /* Consecutive cases again, but with the output edge reversed */
455 else if (in_edge1 == out_edge2)
457 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
458 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
459 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where);
460 temp = (int *) malloc(sizeof(int) * size);
461 memcpy(temp,index,sizeof(int)*size);
462 Delete_From_List(in_edge2,index,&size);
463 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
464 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
465 memcpy(index,temp,sizeof(int)*size);
468 else if (in_edge2 == out_edge2)
470 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
471 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
472 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
473 temp = (int *) malloc(sizeof(int) * size);
474 memcpy(temp,index,sizeof(int)*size);
475 Delete_From_List(in_edge1,index,&size);
476 Triangulate_Polygon(out_edge1,out_edge2,vertex4,
477 in_edge2,size-1,index,output,reversed,face_id,where,color1,color2,color3);
478 memcpy(index,temp,sizeof(int)*size);
482 /* Else the edge is not consecutive, and it is sufficiently
483 far away, for us not to make a conclusion at this time.
484 So we can take off a triangle and recursively call this
489 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
490 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
491 temp = (int *) malloc(sizeof(int) * size);
492 memcpy(temp,index,sizeof(int)*size);
493 Delete_From_List(in_edge1,index,&size);
494 Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
495 vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
496 memcpy(index,temp,sizeof(int)*size);
501 void Triangulate(int out_edge1,int out_edge2,int in_edge1,
502 int in_edge2,int size,int *index,
503 FILE *output,int reversed,int face_id, int where,
504 int color1, int color2,int color3)
506 /* We have the info we need to triangulate a polygon */
509 Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
510 index,output,reversed,face_id,where,color1,color2,color3);
512 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
513 index,output,reversed,face_id,where,color1,color2,color3);
516 void Non_Blind_Triangulate(int size,int *index,
517 FILE *output,int next_face_id,int face_id,int where,
518 int color1,int color2,int color3)
523 /* We have a polygon that has to be triangulated and we cannot
524 do it blindly, ie we will try to come out on the edge that
525 has the least number of adjacencies
528 Last_Edge(&id1,&id2,&id3,0);
529 /* Find the edge that is adjacent to the new face ,
530 also return whether the orientation is reversed in the
531 face of the input edge, which is id2 and id3.
533 if (next_face_id == -1)
535 printf("The face is -1 and the size is %d\n",size);
539 reversed = Get_Edge(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
540 /* Do the triangulation */
542 /* If reversed is -1, the input edge is not in the polygon, therefore we can have the
543 input edge to be anything we like, since we are at the beginning
546 Triangulate(nedge1,nedge2,id2,id3,size,index,output,reversed,
547 face_id, where,color1,color2,color3);
552 void Blind_Triangulate(int size, int *index, FILE *output,
553 BOOL begin, int where ,int color1,int color2,
556 /* save sides in temp array, we need it so we know
559 int mode, decreasing,increasing,e1,e2,e3;
561 /* Rearrange the index list so that the input edge is first
564 Rearrange_Index(index,size);
566 /* We are given a polygon of more than 3 sides
567 and want to triangulate it. We will output the
568 triangles to the output file.
571 /* Find where the input edge is in the input list */
572 Last_Edge(&e1,&e2,&e3,0);
573 if (( (!begin) && (*(index) == e2) ) || (begin))
575 Output_Tri(*(index+0),*(index+1),*(index+size-1),output,color1,color2,color3,where);
576 /* If we have a quad, (chances are yes), then we know that
577 we can just add one diagonal and be done. (divide the
578 quad into 2 triangles.
582 Output_Tri(*(index+1),*(index+size-1),*(index+2),output,color1,color2,color3,where);
591 Output_Tri(*(index+1),*(index+0),*(index+size-1),output,color1,color2,color3,where);
594 Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where);
597 Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where);
603 /* We do not have a quad, we have something bigger. */
604 decreasing = size - 1;
607 /* Will be alternating diagonals, so we will be increasing
608 and decreasing around the polygon.
612 Output_Tri(*(index+increasing),*(index+decreasing),*(index+increasing+1),output,color1,color2,color3,where);
617 Output_Tri(*(index+decreasing),*(index+increasing),*(index+decreasing-1),output,color1,color2,color3,where);
621 } while ((decreasing - increasing) >= 2);