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 finding and outputting the
12 strips from the local algorithm
14 /*---------------------------------------------------------------------*/
20 #include "triangulate.h"
34 int Finished(int *swap, FILE *output, BOOL global)
36 /* We have finished all the triangles, now is time to output to
37 the data file. In the strips data structure, every three ids
38 is a triangle. Now we see whether we can swap, or make a new strip
39 or continue the strip, and output the data accordingly to the
42 register int start_swap = 0;
43 int num,x,vertex1,vertex2;
45 int id[2],other1,other2,index = 0,a,b,c;
46 P_STRIPS temp1,temp2,temp3,temp4,temp5,temp6;
51 pListHead = strips[0];
52 if (pListHead == NULL)
55 num = NumOnList(pListHead);
56 /*printf ("There are %d triangles in the extend\n",num/3);*/
58 /* Go through the list triangle by triangle */
59 temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 0);
60 temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 1);
61 temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 2);
63 /* Next triangle for lookahead */
64 temp4 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 3);
67 /* There is only one polygon in the strip */
70 /* Data might be mixed and we do not have textures for some of the vertices */
71 if ((text) && (vt[temp3->face_id] == 0))
73 if ((norm) && (!cptexture))
74 fprintf(output,"%d//%d %d//%d %d//%d",temp3->face_id+1,vn[temp3->face_id]+1,
75 temp2->face_id+1,vn[temp2->face_id]+1,
76 temp1->face_id+1,vn[temp1->face_id]+1);
77 else if ((cptexture) && (!norm))
78 fprintf(output,"%d/%d %d/%d %d/%d",temp3->face_id+1,vt[temp3->face_id]+1,
79 temp2->face_id+1,vt[temp2->face_id]+1,
80 temp1->face_id+1,vt[temp1->face_id]+1);
81 else if ((cptexture)&& (norm))
82 fprintf(output,"%d/%d/%d %d/%d/%d %d/%d/%d",temp3->face_id+1,vt[temp3->face_id]+1,vn[temp3->face_id]+1,
83 temp2->face_id+1,vt[temp2->face_id]+1,vn[temp2->face_id]+1,
84 temp1->face_id+1,vt[temp1->face_id]+1,vn[temp1->face_id]+1);
86 fprintf(output,"%d %d %d",temp3->face_id+1,temp2->face_id+1,temp1->face_id+1);
91 /* We have a real strip */
92 temp5 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 4);
93 temp6 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 5);
95 if ((temp1 == NULL) || (temp2 == NULL) || (temp3 == NULL) || (temp5 == NULL) || (temp6 == NULL))
97 printf("There is an error in the output of the triangles\n");
101 /* Find the vertex in the first triangle that is not in the second */
102 vertex1 = Different(temp1->face_id,temp2->face_id,temp3->face_id,temp4->face_id,temp5->face_id,temp6->face_id,&other1,&other2);
103 /* Find the vertex in the second triangle that is not in the first */
104 vertex2 = Different(temp4->face_id,temp5->face_id,temp6->face_id,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&other2);
106 /* Lookahead for the correct order of the 2nd and 3rd vertex of the first triangle */
107 temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 6);
108 temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 7);
109 temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 8);
112 other1 = Different(temp3->face_id,temp4->face_id,temp5->face_id,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&a);
114 id[index] = vertex1; index = !index;
115 id[index] = other1; index = !index;
116 id[index] = other2; index = !index;
122 /* If we need to rearrange the first sequence because otherwise
123 there would have been a swap.
126 if ((temp3 != NULL) && (text) && ( vt[temp3->face_id]==0))
128 if ((norm) && (!cptexture))
129 fprintf(output,"%d//%d %d//%d %d//%d ",vertex1+1,vn[vertex1]+1,other1+1,vn[other1]+1,
130 other2+1,vn[other2]+1);
131 else if ((cptexture) && (!norm))
132 fprintf(output,"%d/%d %d/%d %d/%d ",vertex1+1,vt[vertex1]+1,other1+1,vt[other1]+1,
133 other2+1,vt[other2]+1);
134 else if ((cptexture) && (norm))
135 fprintf(output,"%d/%d/%d %d/%d/%d %d/%d/%d ",vertex1+1,vt[vertex1]+1,vn[vertex1]+1,
136 other1+1,vt[other1]+1,vn[other1]+1,
137 other2+1,vt[other2]+1,vn[other2]+1);
139 fprintf(output,"%d %d %d ",vertex1+1,other1+1,other2+1);
142 for (x = 6; x < num ; x = x+3)
145 /* Get the next triangle */
146 temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x);
147 temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+1);
148 temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+2);
151 if (!(member(id[0],a,b,c)) || !(member(id[1],a,b,c)) || !(member(vertex2,a,b,c)))
153 /* If we used partial we might have a break in the middle of a strip */
154 fprintf(output,"\nt ");
155 /* Find the vertex in the first triangle that is not in the second */
156 vertex1 = Different(a,b,c,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&other2);
157 /* Find the vertex in the second triangle that is not in the first */
158 vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
160 id[index] = vertex1; index = !index;
161 id[index] = other1; index = !index;
162 id[index] = other2; index = !index;
165 if ((temp1 == NULL ) || (temp2 == NULL) || (temp3 == NULL))
167 printf("There is an error in the triangle list \n");
171 if ((id[0] == id[1]) || (id[0] == vertex2))
174 if ((member(id[index],temp1->face_id,temp2->face_id,temp3->face_id)))
176 if ((text) && ( vt[id[index]]==0))
178 if ((!norm) && (!cptexture))
179 fprintf(output,"%d ",id[index]+1);
180 else if ((norm) && (!cptexture))
181 fprintf(output,"%d//%d ",id[index]+1,vn[id[index]]+1);
182 else if ((!norm) && (cptexture))
183 fprintf(output,"%d/%d ",id[index]+1,vt[id[index]]+1);
185 fprintf(output,"%d/%d/%d ",id[index]+1,vt[id[index]]+1,vn[id[index]]+1);
190 if ((text) && ( vt[vertex2]==0))
192 if ((!norm) && (!cptexture))
193 fprintf(output,"\nq %d ",vertex2+1);
194 else if ((norm) && (!cptexture))
195 fprintf(output,"\nq %d//%d ",vertex2+1,vn[vertex2]+1);
196 else if ((!norm) && (cptexture))
197 fprintf(output,"\nq %d/%d ",vertex2+1,vt[vertex2]+1);
199 fprintf(output,"\nq %d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
201 id[index] = vertex2; index = !index;
203 /* Get the next vertex not in common */
204 vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
209 /* Do the last vertex */
210 if ((text) && (vt[vertex2]==0))
213 fprintf(output,"\nq ");
216 if ((!norm) && (!cptexture))
217 fprintf(output,"%d ",vertex2+1);
218 else if ((norm) && (!cptexture))
219 fprintf(output,"%d//%d ",vertex2+1,vn[vertex2]+1);
220 else if ((!norm) && (cptexture))
221 fprintf(output,"%d/%d ",vertex2+1,vt[vertex2]+1);
223 fprintf(output,"%d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
230 void Output_Tri(int id1, int id2, int id3,FILE *bands, int color1, int color2, int color3,BOOL end)
232 /* We will save everything into a list, rather than output at once,
233 as was done in the old routine. This way for future modifications
234 we can change the strips later on if we want to.
237 int temp1,temp2,temp3;
239 /* Make sure we do not have an error */
240 /* There are degeneracies in some of the files */
241 if ( (id1 == id2) || (id1 == id3) || (id2 == id3))
243 printf("Degenerate triangle %d %d %d\n",id1,id2,id3);
248 Last_Edge(&temp1,&temp2,&temp3,0);
249 Add_Id_Strips(id1,end);
250 Add_Id_Strips(id2,end);
251 Add_Id_Strips(id3,end);
252 Last_Edge(&id1,&id2,&id3,1);
257 int Polygon_Output(P_ADJACENCIES temp,int face_id,int bucket,
258 ListHead *pListHead, BOOL first, int *swaps,
259 FILE *bands,int color1,int color2,int color3,BOOL global, BOOL end)
263 P_ADJACENCIES pfNode;
264 static BOOL begin = TRUE;
265 int old_face,next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
266 P_ADJACENCIES lpListInfo;
268 int tie = SEQUENTIAL;
270 /* We have a polygon to output, the id is face id, and the number
271 of adjacent polygons to it is bucket. This routine extends the patches from
272 either end to make longer triangle strips.
276 /* Now get the edge */
277 Last_Edge(&e1,&e2,&e3,0);
279 /* Get the polygon with id face_id */
280 pListFace = PolFaces[face_id];
281 face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
283 /* We can't go any more */
284 if ((face->nPolSize == 1) || ((face->nPolSize == 4) && (global))) /* if global, then we are still doing patches */
286 /* Remove it from the list so we do not have to waste
287 time visiting it in the future, or winding up in an infinite loop
288 if it is the first on that we are looking at for a possible strip
290 if (face->nPolSize == 1)
291 RemoveList(pListHead,(PLISTINFO) temp);
295 return (Finished(swaps,bands,global));
298 if (face->nPolSize == 3)
300 /* It is already a triangle */
303 /* It is not adjacent to anything so we do not have to
304 worry about the order of the sides or updating adjacencies
307 next_face_id = Different(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),
308 e1,e2,e3,&other1,&other2);
311 /* If this is the first triangle in the strip */
312 if ((e2 == 0) && (e3 ==0))
318 Output_Tri(e2,e3,next_face_id,bands,color1,color2,color3,end);
319 RemoveList(pListHead,(PLISTINFO) temp);
320 return (Finished(swaps,bands,global));
324 /* It is a triangle with adjacencies. This means that we
326 1. Update the adjacencies in the list, because we are
327 using this polygon and it will be deleted.
328 2. Get the next polygon.
332 /* Return the face_id of the next polygon we will be using,
333 while updating the adjacency list by decrementing the
334 adjacencies of everything adjacent to the current triangle.
337 next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
338 /* Maybe we deleted something in a patch and could not find an adj polygon */
339 if (next_face_id == -1)
341 Output_Tri(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),bands,color1,
344 RemoveList(pListHead,(PLISTINFO) temp);
345 return (Finished(swaps,bands,global));
348 old_face = next_face_id;
349 /* Find the other vertex to transmit in the triangle */
350 e3 = Return_Other(face->pPolygon,e1,e2);
351 Last_Edge(&other1,&other2,&other3,0);
353 if ((other2 != 0) && (other3 != 0))
355 /* See which vertex in the output edge is not in the input edge */
356 if ((e1 != other2) && (e1 != other3))
358 else if ((e2 != other2) && (e2 != other3))
362 printf("There is an error in the tri with adj\n");
366 /* See which vertex of the input edge is not in the output edge */
367 if ((other2 != e1) && (other2 != e2))
372 else if ((other3 != e1) && (other3 != e2))
376 printf("There is an error in getting the tri with adj\n");
383 /* We are the first triangle in the strip and the starting edge
386 /* Maybe we deleted something in a patch and could not find an adj polygon */
387 if (next_face_id == -1)
389 Output_Tri(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),bands,color1,
392 RemoveList(pListHead,(PLISTINFO) temp);
393 return (Finished(swaps,bands,global));
401 /* At this point the adjacencies have been updated and we
402 have the next polygon id
405 Output_Tri(other1,other2,e3,bands,color1,color2,color3,end);
407 RemoveList(pListHead,(PLISTINFO) temp);
410 /* Maybe we deleted something in a patch and could not find an adj polygon */
411 if (next_face_id == -1)
412 return (Finished(swaps,bands,global));
414 if (Done(next_face_id,59,&next_bucket) == NULL)
416 printf("We deleted the next face 4%d\n",next_face_id);
420 pListHead = array[next_bucket];
421 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
423 pfNode->face_id = next_face_id;
424 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
425 (int (*)(void *,void *)) (Compare)));
426 if (lpListInfo == NULL)
428 printf("There is an error finding the next polygon3 %d\n",next_face_id);
431 return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
432 pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
439 /* It is not a triangle, we have to triangulate it .
440 Since it is not adjacent to anything we can triangulate it
445 /* It is the first polygon in the strip, therefore there is no
446 input edge to start with.
448 if ((e2 == 0) && (e3 ==0))
449 Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
450 TRUE,1,color1,color2,color3);
453 Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
454 FALSE,1,color1,color2,color3);
456 RemoveList(pListHead,(PLISTINFO) temp);
458 /* We will be at the beginning of the next strip. */
460 return (Finished(swaps,bands,global));
468 /* WHOLE triangulation */
469 /* It is not a triangle and has adjacencies.
470 This means that we have to:
471 1. Triangulate this polygon, not blindly because
472 we have an edge that we want to come out on, that
473 is the edge that is adjacent to a polygon with the
474 least number of adjacencies. Also we must come in
475 on the last seen edge.
476 2. Update the adjacencies in the list, because we are
478 3. Get the next polygon.
480 /* Return the face_id of the next polygon we will be using,
481 while updating the adjacency list by decrementing the
482 adjacencies of everything adjacent to the current polygon.
485 next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
487 /* Maybe we deleted something in a patch and could not find an adj polygon */
488 if (next_face_id == -1)
491 /* If we are at the first polygon in the strip and there is no input
492 edge, then begin is TRUE
494 if ((e2 == 0) && (e3 == 0))
495 Blind_Triangulate(face->nPolSize,face->pPolygon,
496 bands,TRUE,1,color1,color2,color3);
499 Blind_Triangulate(face->nPolSize,face->pPolygon,
500 bands,FALSE,1,color1,color2,color3);
502 RemoveList(pListHead,(PLISTINFO) temp);
504 /* We will be at the beginning of the next strip. */
506 return (Finished(swaps,bands,global));
509 if (Done(next_face_id,59,&next_bucket) == NULL)
511 printf("We deleted the next face 6 %d %d\n",next_face_id,face_id);
515 Non_Blind_Triangulate(face->nPolSize,face->pPolygon,
516 bands,next_face_id,face_id,1,color1,color2,color3);
518 RemoveList(pListHead,(PLISTINFO) temp);
521 pListHead = array[next_bucket];
522 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
524 pfNode->face_id = next_face_id;
525 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
526 (int (*)(void *,void *)) (Compare)));
527 if (lpListInfo == NULL)
529 printf("There is an error finding the next polygon2 %d %d\n",next_face_id,next_bucket);
532 return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
533 pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
537 Last_Edge(&e1,&e2,&e3,0);
542 int Extend_Face(int face_id,int e1,int e2,int *swaps,FILE *bands,
543 int color1,int color2,int color3,int *vert_norm, int normals,
544 int *vert_texture, int texture)
546 int dummy=0,next_bucket;
547 P_ADJACENCIES pfNode,lpListInfo;
550 /* Try to extend backwards off of the local strip that we just found */
558 /* Find the face that is adjacent to the edge and is not the
561 face_id = Find_Face(face_id, e1, e2,&next_bucket);
565 pListHead = array[next_bucket];
566 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
568 pfNode->face_id = face_id;
569 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
570 (int (*)(void *,void *)) (Compare)));
571 if (lpListInfo == NULL)
573 printf("There is an error finding the next polygon3 %d\n",face_id);
576 Last_Edge(&dummy,&e1,&e2,1);
578 /* Find a strip extending from the patch and return the cost */
579 return (Polygon_Output(lpListInfo,face_id,next_bucket,pListHead,TRUE,swaps,bands,color1,color2,color3,TRUE,TRUE));