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.
361 /* Since we are calling this recursively, we have to check whether
362 we are down to the case of the quad.
367 Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
368 index,output,reversed,face_id,where,color1,color2,color3);
374 /* We do not have a specified input edge, and therefore we
375 can make it anything we like, as long as we still come out
376 the output edge that we want.
380 /* Get the vertex for the last triangle, which is
381 the one coming out the output edge, before we do
382 any deletions to the list. We will be doing this
385 vertex4 = Adjacent(out_edge1,out_edge2,index,size);
386 temp = (int *) malloc(sizeof(int) * size);
387 memcpy(temp,index,sizeof(int)*size);
388 Delete_From_List(out_edge2,index,&size);
389 Triangulate_Polygon(out_edge1,vertex4,in_edge2,
390 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
391 memcpy(index,temp,sizeof(int)*size);
392 /* Lastly do the triangle that comes out the output
395 Output_Tri(vertex4,out_edge1,out_edge2,output,color1,color2,color3,where,where);
399 /* These are the 5 cases that we can have for the output edge */
401 /* Are they consecutive so that we form a triangle to
402 peel off that comes out the correct output edge,
403 but we cannot use the whole polygon?
405 if (in_edge2 == out_edge1)
407 /* Output the triangle that comes out the correct
408 edge last. First recursively do the rest of the
411 /* Do the rest of the polygon without the triangle.
412 We will be doing a fan triangulation.
414 /* Get the vertex adjacent to in_edge1, but is not
417 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
418 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where);
419 /* Create a new edgelist without the triangle that
422 temp = (int *) malloc(sizeof(int) * size);
423 memcpy(temp,index,sizeof(int)*size);
424 Delete_From_List(in_edge1,index,&size);
425 Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
426 vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
427 memcpy(index,temp,sizeof(int)*size);
431 /* Next case is where it is again consecutive, but the triangle
432 formed by the consecutive edges do not come out of the
433 correct output edge. For this case, we can not do much to
434 keep it sequential. Try and do the fan.
436 else if (in_edge1 == out_edge1)
438 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
439 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
440 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where,where);
441 /* Since that triangle goes out of the polygon (the
442 output edge of it), we can make our new input edge
443 anything we like, so we will try to make it good for
444 the strip. (This will be like starting a new strip,
445 all so that we can go out the correct output edge.)
447 temp = (int *) malloc(sizeof(int) * size);
448 memcpy(temp,index,sizeof(int)*size);
449 Delete_From_List(in_edge2,index,&size);
450 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
451 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
452 memcpy(index,temp,sizeof(int)*size);
455 /* Consecutive cases again, but with the output edge reversed */
456 else if (in_edge1 == out_edge2)
458 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
459 vertex4 = Adjacent(in_edge1,in_edge2,index,size);
460 Output_Tri(in_edge2,in_edge1,vertex4,output,color1,color2,color3,where,where);
461 temp = (int *) malloc(sizeof(int) * size);
462 memcpy(temp,index,sizeof(int)*size);
463 Delete_From_List(in_edge2,index,&size);
464 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
465 vertex4,size-1,index,output,reversed,face_id,where,color1,color2,color3);
466 memcpy(index,temp,sizeof(int)*size);
469 else if (in_edge2 == out_edge2)
471 /* Get vertex adjacent to in_edge2, but is not in_edge1 */
472 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
473 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where,where);
474 temp = (int *) malloc(sizeof(int) * size);
475 memcpy(temp,index,sizeof(int)*size);
476 Delete_From_List(in_edge1,index,&size);
477 Triangulate_Polygon(out_edge1,out_edge2,vertex4,
478 in_edge2,size-1,index,output,reversed,face_id,where,color1,color2,color3);
479 memcpy(index,temp,sizeof(int)*size);
483 /* Else the edge is not consecutive, and it is sufficiently
484 far away, for us not to make a conclusion at this time.
485 So we can take off a triangle and recursively call this
490 vertex4 = Adjacent(in_edge2,in_edge1,index,size);
491 Output_Tri(in_edge1,in_edge2,vertex4,output,color1,color2,color3,where,where);
492 temp = (int *) malloc(sizeof(int) * size);
493 memcpy(temp,index,sizeof(int)*size);
494 Delete_From_List(in_edge1,index,&size);
495 Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
496 vertex4,size-1,index,output,!reversed,face_id,where,color1,color2,color3);
497 memcpy(index,temp,sizeof(int)*size);
502 void Triangulate(int out_edge1,int out_edge2,int in_edge1,
503 int in_edge2,int size,int *index,
504 FILE *output,int reversed,int face_id, int where,
505 int color1, int color2,int color3)
507 /* We have the info we need to triangulate a polygon */
510 Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
511 index,output,reversed,face_id,where,color1,color2,color3);
513 Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
514 index,output,reversed,face_id,where,color1,color2,color3);
517 void Non_Blind_Triangulate(int size,int *index,
518 FILE *output,int next_face_id,int face_id,int where,
519 int color1,int color2,int color3)
524 /* We have a polygon that has to be triangulated and we cannot
525 do it blindly, ie we will try to come out on the edge that
526 has the least number of adjacencies
529 Last_Edge(&id1,&id2,&id3,0);
530 /* Find the edge that is adjacent to the new face ,
531 also return whether the orientation is reversed in the
532 face of the input edge, which is id2 and id3.
534 if (next_face_id == -1)
536 printf("The face is -1 and the size is %d\n",size);
540 reversed = Get_Edge(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
541 /* Do the triangulation */
543 /* If reversed is -1, the input edge is not in the polygon, therefore we can have the
544 input edge to be anything we like, since we are at the beginning
547 Triangulate(nedge1,nedge2,id2,id3,size,index,output,reversed,
548 face_id, where,color1,color2,color3);
553 void Blind_Triangulate(int size, int *index, FILE *output,
554 BOOL begin, int where ,int color1,int color2,
557 /* save sides in temp array, we need it so we know
560 int mode, decreasing,increasing,e1,e2,e3;
564 /* Rearrange the index list so that the input edge is first
567 Rearrange_Index(index,size);
569 /* We are given a polygon of more than 3 sides
570 and want to triangulate it. We will output the
571 triangles to the output file.
574 /* Find where the input edge is in the input list */
575 Last_Edge(&e1,&e2,&e3,0);
576 if (( (!begin) && (*(index) == e2) ) || (begin))
578 Output_Tri(*(index+0),*(index+1),*(index+size-1),output,color1,color2,color3,where,where);
579 /* If we have a quad, (chances are yes), then we know that
580 we can just add one diagonal and be done. (divide the
581 quad into 2 triangles.
585 Output_Tri(*(index+1),*(index+size-1),*(index+2),output,color1,color2,color3,where,where);
594 Output_Tri(*(index+1),*(index+0),*(index+size-1),output,color1,color2,color3,where,where);
597 Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where,where);
600 Output_Tri(*(index+0),*(index+size-1),*(index+2),output,color1,color2,color3,where,where);
606 /* We do not have a quad, we have something bigger. */
607 decreasing = size - 1;
610 /* Will be alternating diagonals, so we will be increasing
611 and decreasing around the polygon.
615 Output_Tri(*(index+increasing),*(index+decreasing),*(index+increasing+1),output,color1,color2,color3,where,where);
620 Output_Tri(*(index+decreasing),*(index+increasing),*(index+decreasing-1),output,color1,color2,color3,where,where);
624 } while ((decreasing - increasing) >= 2);