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 int num,x,vertex1,vertex2;
44 int id[2],other1,other2,index = 0,a,b,c;
45 P_STRIPS temp1,temp2,temp3,temp4,temp5,temp6;
50 pListHead = strips[0];
51 if (pListHead == NULL)
54 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,
130 other1+1,vn[other1]+1,other2+1,vn[other2]+1);
131 else if ((cptexture) && (!norm))
132 fprintf(output,"%d/%d %d/%d %d/%d ",vertex1+1,vt[vertex1]+1,
133 other1+1,vt[other1]+1,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,other2+1,vt[other2]+1,vn[other2]+1);
138 fprintf(output,"%d %d %d ",vertex1+1,other1+1,other2+1);
142 // for (x = 6; x < num ; x = x+3)
143 // Wilbur modified line
144 for (x = 6; x < num ; x = x+3)
146 /* Get the next triangle */
147 temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x);
148 temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+1);
149 temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x+2);
152 if (!(member(id[0],a,b,c)) || !(member(id[1],a,b,c)) || !(member(vertex2,a,b,c)))
154 /* If we used partial we might have a break in the middle of a strip */
155 fprintf(output,"\nt ");
156 /* Find the vertex in the first triangle that is not in the second */
157 vertex1 = Different(a,b,c,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&other2);
158 /* Find the vertex in the second triangle that is not in the first */
159 vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
161 id[index] = vertex1; index = !index;
162 id[index] = other1; index = !index;
163 id[index] = other2; index = !index;
166 if ((temp1 == NULL ) || (temp2 == NULL) || (temp3 == NULL))
168 printf("There is an error in the triangle list \n");
172 if ((id[0] == id[1]) || (id[0] == vertex2))
175 if ( (member(id[index],temp1->face_id,temp2->face_id,temp3->face_id)) )
177 if ((text) && ( vt[id[index]]==0)) {
180 if ((!norm) && (!cptexture)) {
181 fprintf(output,"%d ",id[index]+1);
182 } else if ((norm) && (!cptexture)) {
183 fprintf(output,"%d//%d ",id[index]+1,vn[id[index]]+1);
184 } else if ((!norm) && (cptexture)) {
185 fprintf(output,"%d/%d ",id[index]+1,vt[id[index]]+1);
187 fprintf(output,"%d/%d/%d ",id[index]+1,vt[id[index]]+1,vn[id[index]]+1);
194 if ((text) && ( vt[vertex2]==0))
196 if ((!norm) && (!cptexture))
197 fprintf(output,"\nq %d ",vertex2+1);
198 else if ((norm) && (!cptexture))
199 fprintf(output,"\nq %d//%d ",vertex2+1,vn[vertex2]+1);
200 else if ((!norm) && (cptexture))
201 fprintf(output,"\nq %d/%d ",vertex2+1,vt[vertex2]+1);
203 fprintf(output,"\nq %d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
205 id[index] = vertex2; index = !index;
207 /* Get the next vertex not in common */
208 vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id,a,b,c,&other1,&other2);
214 /* Do the last vertex */
215 if ((!norm) && (!cptexture))
216 fprintf(output,"\nq %d ",vertex2+1);
217 else if ((norm) && (!cptexture))
218 fprintf(output,"\nq %d//%d ",vertex2+1,vn[vertex2]+1);
219 else if ((!norm) && (cptexture))
220 fprintf(output,"\nq %d/%d ",vertex2+1,vt[vertex2]+1);
222 fprintf(output,"\nq %d/%d/%d ",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
232 void Output_Tri(int id1, int id2, int id3,FILE *bands, int color1, int color2, int color3,BOOL end)
234 /* We will save everything into a list, rather than output at once,
235 as was done in the old routine. This way for future modifications
236 we can change the strips later on if we want to.
239 int temp1,temp2,temp3;
241 /* Make sure we do not have an error */
242 /* There are degeneracies in some of the files */
243 if ( (id1 == id2) || (id1 == id3) || (id2 == id3))
245 printf("Degenerate triangle %d %d %d\n",id1,id2,id3);
250 Last_Edge(&temp1,&temp2,&temp3,0);
251 Add_Id_Strips(id1,end);
252 Add_Id_Strips(id2,end);
253 Add_Id_Strips(id3,end);
254 Last_Edge(&id1,&id2,&id3,1);
259 int Polygon_Output(P_ADJACENCIES temp,int face_id,int bucket,
260 ListHead *pListHead, BOOL first, int *swaps,
261 FILE *bands,int color1,int color2,int color3,BOOL global, BOOL end)
265 P_ADJACENCIES pfNode;
266 int next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
267 P_ADJACENCIES lpListInfo;
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 /* Find the other vertex to transmit in the triangle */
349 e3 = Return_Other(face->pPolygon,e1,e2);
350 Last_Edge(&other1,&other2,&other3,0);
352 if ((other2 != 0) && (other3 != 0))
354 /* See which vertex in the output edge is not in the input edge */
355 if ((e1 != other2) && (e1 != other3))
357 else if ((e2 != other2) && (e2 != other3))
361 printf("There is an error in the tri with adj\n");
365 /* See which vertex of the input edge is not in the output edge */
366 if ((other2 != e1) && (other2 != e2))
371 else if ((other3 != e1) && (other3 != e2))
375 printf("There is an error in getting the tri with adj\n");
382 /* We are the first triangle in the strip and the starting edge
385 /* Maybe we deleted something in a patch and could not find an adj polygon */
386 if (next_face_id == -1)
388 Output_Tri(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),bands,color1,
391 RemoveList(pListHead,(PLISTINFO) temp);
392 return (Finished(swaps,bands,global));
400 /* At this point the adjacencies have been updated and we
401 have the next polygon id
404 Output_Tri(other1,other2,e3,bands,color1,color2,color3,end);
406 RemoveList(pListHead,(PLISTINFO) temp);
408 /* Maybe we deleted something in a patch and could not find an adj polygon */
409 if (next_face_id == -1)
410 return (Finished(swaps,bands,global));
412 if (Done(next_face_id,59,&next_bucket) == NULL)
414 printf("We deleted the next face 4%d\n",next_face_id);
418 pListHead = array[next_bucket];
419 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
421 pfNode->face_id = next_face_id;
422 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
423 (int (*)(void *,void *)) (Compare)));
424 if (lpListInfo == NULL)
426 printf("There is an error finding the next polygon3 %d\n",next_face_id);
429 return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
430 pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
437 /* It is not a triangle, we have to triangulate it .
438 Since it is not adjacent to anything we can triangulate it
443 /* It is the first polygon in the strip, therefore there is no
444 input edge to start with.
446 if ((e2 == 0) && (e3 ==0))
447 Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
448 TRUE,1,color1,color2,color3);
451 Blind_Triangulate(face->nPolSize,face->pPolygon,bands,
452 FALSE,1,color1,color2,color3);
454 RemoveList(pListHead,(PLISTINFO) temp);
456 /* We will be at the beginning of the next strip. */
458 return (Finished(swaps,bands,global));
466 /* WHOLE triangulation */
467 /* It is not a triangle and has adjacencies.
468 This means that we have to:
469 1. Triangulate this polygon, not blindly because
470 we have an edge that we want to come out on, that
471 is the edge that is adjacent to a polygon with the
472 least number of adjacencies. Also we must come in
473 on the last seen edge.
474 2. Update the adjacencies in the list, because we are
476 3. Get the next polygon.
478 /* Return the face_id of the next polygon we will be using,
479 while updating the adjacency list by decrementing the
480 adjacencies of everything adjacent to the current polygon.
483 next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
485 /* Maybe we deleted something in a patch and could not find an adj polygon */
486 if (next_face_id == -1)
489 /* If we are at the first polygon in the strip and there is no input
490 edge, then begin is TRUE
492 if ((e2 == 0) && (e3 == 0))
493 Blind_Triangulate(face->nPolSize,face->pPolygon,
494 bands,TRUE,1,color1,color2,color3);
497 Blind_Triangulate(face->nPolSize,face->pPolygon,
498 bands,FALSE,1,color1,color2,color3);
500 RemoveList(pListHead,(PLISTINFO) temp);
502 /* We will be at the beginning of the next strip. */
504 return (Finished(swaps,bands,global));
507 if (Done(next_face_id,59,&next_bucket) == NULL)
509 printf("We deleted the next face 6 %d %d\n",next_face_id,face_id);
513 Non_Blind_Triangulate(face->nPolSize,face->pPolygon,
514 bands,next_face_id,face_id,1,color1,color2,color3);
516 RemoveList(pListHead,(PLISTINFO) temp);
518 pListHead = array[next_bucket];
519 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
521 pfNode->face_id = next_face_id;
522 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
523 (int (*)(void *,void *)) (Compare)));
524 if (lpListInfo == NULL)
526 printf("There is an error finding the next polygon2 %d %d\n",next_face_id,next_bucket);
529 return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
530 pListHead, FALSE, swaps,bands,color1,color2,color3,global,end));
534 Last_Edge(&e1,&e2,&e3,0);
539 int Extend_Face(int face_id,int e1,int e2,int *swaps,FILE *bands,
540 int color1,int color2,int color3,int *vert_norm, int normals,
541 int *vert_texture, int texture)
543 int dummy=0,next_bucket;
544 P_ADJACENCIES pfNode,lpListInfo;
547 /* Try to extend backwards off of the local strip that we just found */
555 /* Find the face that is adjacent to the edge and is not the
558 face_id = Find_Face(face_id, e1, e2,&next_bucket);
562 pListHead = array[next_bucket];
563 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
565 pfNode->face_id = face_id;
566 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
567 (int (*)(void *,void *)) (Compare)));
568 if (lpListInfo == NULL)
570 printf("There is an error finding the next polygon3 %d\n",face_id);
573 Last_Edge(&dummy,&e1,&e2,1);
575 /* Find a strip extending from the patch and return the cost */
576 return (Polygon_Output(lpListInfo,face_id,next_bucket,pListHead,TRUE,swaps,bands,color1,color2,color3,TRUE,TRUE));