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 used for various functions in
14 /*---------------------------------------------------------------------*/
21 #include "triangulatex.h"
25 #include "sturctsex.h"
32 void Output_TriEx(int id1, int id2, int id3, FILE *output, int next_face, int flag,
35 /* We will save everything into a list, rather than output at once,
36 as was done in the old routine. This way for future modifications
37 we can change the strips later on if we want to.
40 int swap,temp1,temp2,temp3;
43 static int strips = 0;
48 cost = cost + where+total+tri+strips+strips;
49 printf("We will need to send %d vertices to the renderer\n",cost);
58 /* We are finished, now is time to output the triangle list
61 fprintf(output,"\nt ");
62 tri = tri + Finished(&swap,output,FALSE);
65 /*printf("There are %d swaps %d tri %d strips\n",total,tri,strips);*/
70 Last_Edge(&temp1,&temp2,&temp3,0);
71 Add_Id_Strips(id1,where);
72 Add_Id_Strips(id2,where);
73 Add_Id_Strips(id3,where);
74 Last_Edge(&id1,&id2,&id3,1);
81 void Extend_BackwardsEx(int face_id, FILE *output, FILE *strip, int *ties,
82 int tie, int triangulate,
83 int swaps,int *next_id)
85 /* We just made a strip, now we are going to see if we can extend
86 backwards from the starting face, which had 2 or more adjacencies
89 int bucket,next_face,num,x,y,z,c,d=1,max,f;
94 /* Get the first triangle that we have saved the the strip data
95 structure, so we can see if there are any polygons adjacent
96 to this edge or a neighboring one
100 pListFace = PolFaces[face_id];
101 face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
103 num = face->nPolSize;
105 /* Go through the edges to see if there is an adjacency
106 with a vertex in common to the first triangle that was
107 outputted in the strip. (maybe edge was deleted....)
109 for (c=0; c<num ; c++)
112 if ( (c != (num-1)) &&
113 (( (*(face->pPolygon+c) == x) && (*(face->pPolygon+c+1) == y)) ||
114 (*(face->pPolygon+c) == y) && (*(face->pPolygon+c+1) == x)))
116 /* Input edge is still there see if there is an adjacency */
117 next_face = Find_Face(face_id, x, y, &bucket);
119 /* Could not find a face adjacent to the edge */
121 pListFace = array[bucket];
122 max = NumOnList(pListFace);
125 temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);
126 if (temp->face_id == next_face)
128 Last_Edge(&z,&y,&x,1);
129 Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
130 output,strip,ties,tie,triangulate,swaps,next_id,0);
136 printf("Error in the new buckets%d %d %d\n",bucket,max,0);
142 else if ( (c == (num -1)) &&
143 ( ((*(face->pPolygon) == x) && (*(face->pPolygon+num-1) == y)) ||
144 (*(face->pPolygon) == y) && (*(face->pPolygon+num-1) == x)))
146 next_face = Find_Face(face_id,x,y,&bucket);
148 /* Could not find a face adjacent to the edge */
150 pListFace = array[bucket];
151 max = NumOnList(pListFace);
154 temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);
155 if (temp->face_id == next_face)
157 Last_Edge(&z,&y,&x,1);
158 Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
159 output,strip,ties,tie,triangulate,swaps,next_id,0);
165 printf("Error in the new buckets%d %d %d\n",bucket,max,0);
175 void Polygon_OutputEx(P_ADJACENCIES temp,int face_id,int bucket,
176 ListHead *pListHead, FILE *output, FILE *strips,
178 int triangulate, int swaps,
179 int *next_id, int where)
183 P_ADJACENCIES pfNode;
184 static BOOL begin = TRUE;
185 int old_face,next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
186 P_ADJACENCIES lpListInfo;
188 /* We have a polygon to output, the id is face id, and the number
189 of adjacent polygons to it is bucket.
192 Last_Edge(&e1,&e2,&e3,0);
194 /* Get the polygon with id face_id */
195 pListFace = PolFaces[face_id];
196 face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
198 if (face->nPolSize == 3)
200 /* It is already a triangle */
203 /* It is not adjacent to anything so we do not have to
204 worry about the order of the sides or updating adjacencies
207 Last_Edge(&e1,&e2,&e3,0);
208 next_face_id = Different(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),
209 e1,e2,e3,&other1,&other2);
210 /* No input edge, at the start */
211 if ((e2 ==0) && (e3 == 0))
217 Output_TriEx(e2,e3,next_face_id,strips,-1,begin,where);
218 RemoveList(pListHead,(PLISTINFO) temp);
219 /* We will be at the beginning of the next strip. */
222 /* It is a triangle with adjacencies. This means that we
224 1. Update the adjacencies in the list, because we are
225 using this polygon and it will be deleted.
226 2. Get the next polygon.
230 /* Return the face_id of the next polygon we will be using,
231 while updating the adjacency list by decrementing the
232 adjacencies of everything adjacent to the current triangle.
235 next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
236 old_face = next_face_id;
238 /* Break the tie, if there was one */
240 old_face = Get_Next_Face(tie,face_id,triangulate);
242 if (next_face_id == -1)
244 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
245 triangulate,swaps,next_id,where);
250 /* We are using a different face */
251 if ((tie != FIRST) && (old_face != next_face_id) && (swaps == ON))
253 next_face_id = old_face;
254 /* Get the new output edge, since e1 and e2 are for the
255 original next face that we got.
257 e3 = Get_EdgeEx(&e1,&e2,face->pPolygon,next_face_id,face->nPolSize,0,0);
260 /* Find the other vertex to transmit in the triangle */
261 e3 = Return_Other(face->pPolygon,e1,e2);
262 Last_Edge(&other1,&other2,&other3,0);
264 if ((other1 != 0) && (other2 != 0))
266 /* See which vertex in the output edge is not in the input edge */
267 if ((e1 != other2) && (e1 != other3))
269 else if ((e2 != other2) && (e2 != other3))
271 /* can happen with > 2 polys on an edge but won't form a good strip so stop
276 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
277 triangulate,swaps,next_id,where);
281 /* See which vertex of the input edge is not in the output edge */
282 if ((other2 != e1) && (other2 != e2))
287 else if ((other3 != e1) && (other3 != e2))
291 /* Degenerate triangle just return*/
292 Output_TriEx(other1,other2,e3,strips,next_face_id,begin,where);
293 RemoveList(pListHead,(PLISTINFO) temp);
300 /* There was not an input edge, we are the first triangle in a strip */
303 /* Find the correct order to transmit the triangle, what is
304 the output edge that we want ?
311 /* At this point the adjacencies have been updated and we
312 have the next polygon id
314 Output_TriEx(other1,other2,e3,strips,next_face_id,begin,where);
315 RemoveList(pListHead,(PLISTINFO) temp);
318 if (Done(next_face_id,59,&next_bucket) == NULL)
321 pListHead = array[next_bucket];
322 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
324 pfNode->face_id = next_face_id;
325 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
326 (int (*)(void *,void *)) (Compare)));
327 if (lpListInfo == NULL)
329 printf("There is an error finding the next polygon3 %d\n",next_face_id);
332 Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
333 pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
340 /* It is not a triangle, we have to triangulate it .
341 Since it is not adjacent to anything we can triangulate it
346 /* Check to see if there is not an input edge */
347 Last_Edge(&other1,&other2,&other3,0);
348 if ((other1 == 0) && (other2 ==0))
349 Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
352 Blind_TriangulateEx(face->nPolSize,face->pPolygon,strips,
355 RemoveList(pListHead,(PLISTINFO) temp);
356 /* We will be at the beginning of the next strip. */
360 /* If we have specified PARTIAL triangulation then
361 we will go to special routines that will break the
362 polygon and update the data structure. Else everything
363 below will simply triangulate the whole polygon
365 else if (triangulate == PARTIAL)
368 /* Return the face_id of the next polygon we will be using,
370 next_face_id = Min_Face_AdjEx(face_id,&next_bucket,ties);
373 /* Don't do it partially, because we can go inside and get
374 less adjacencies, for a quad we can do the whole thing.
376 if ((face_id == next_face_id) && (face->nPolSize == 4) && (swaps == ON))
378 next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
379 if (next_face_id == -1)
381 /* There is no sequential face to go to, end the strip */
382 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
383 triangulate,swaps,next_id,where);
387 /* Break the tie, if there was one */
389 next_face_id = Get_Next_Face(tie,face_id,triangulate);
390 Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
391 output,next_face_id,face_id,where);
392 RemoveList(pListHead,(PLISTINFO) temp);
395 /* Was not a quad but we still do not want to do it partially for
396 now, since we want to only do one triangle at a time
398 else if ((face_id == next_face_id) && (swaps == ON))
399 Inside_Polygon(face->nPolSize,face->pPolygon,strips,output,
400 next_face_id,face_id,next_id,pListHead,temp,where);
404 if ((tie != FIRST) && (swaps == ON))
405 next_face_id = Get_Next_Face(tie,face_id,triangulate);
406 Partial_Triangulate(face->nPolSize,face->pPolygon,strips,
407 output,next_face_id,face_id,next_id,pListHead,temp,where);
408 /* Check the next bucket again ,maybe it changed
409 We calculated one less, but that might not be the case
413 if (Done(next_face_id,59,&next_bucket) == NULL)
415 /* Check to see if there is not an input edge */
416 Last_Edge(&other1,&other2,&other3,0);
417 if ((other1 == 0) && (other2 ==0))
418 Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
421 Blind_TriangulateEx(face->nPolSize,face->pPolygon,strips,
424 if (Done(face_id,59,&bucket) != NULL)
426 pListHead = array[bucket];
427 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
429 pfNode->face_id = face_id;
430 lpListInfo = (P_ADJACENCIES) (SearchList(array[bucket], pfNode,
431 (int (*)(void *,void *)) (Compare)));
432 RemoveList(pListHead,(PLISTINFO)lpListInfo);
439 pListHead = array[next_bucket];
440 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
442 pfNode->face_id = next_face_id;
443 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
444 (int (*)(void *,void *)) (Compare)));
445 if (lpListInfo == NULL)
447 printf("There is an error finding the next polygon1 %d %d\n",next_face_id,next_bucket);
450 Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
451 pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
457 /* WHOLE triangulation */
458 /* It is not a triangle and has adjacencies.
459 This means that we have to:
460 1. TriangulateEx this polygon, not blindly because
461 we have an edge that we want to come out on, that
462 is the edge that is adjacent to a polygon with the
463 least number of adjacencies. Also we must come in
464 on the last seen edge.
465 2. Update the adjacencies in the list, because we are
467 3. Get the next polygon.
469 /* Return the face_id of the next polygon we will be using,
470 while updating the adjacency list by decrementing the
471 adjacencies of everything adjacent to the current polygon.
474 next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
476 if (Done(next_face_id,59,&next_bucket) == NULL)
478 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
479 triangulate,swaps,next_id,where);
480 /* Because maybe there was more than 2 polygons on the edge */
484 /* Break the tie, if there was one */
485 else if (tie != FIRST)
486 next_face_id = Get_Next_Face(tie,face_id,triangulate);
488 Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
489 output,next_face_id,face_id,where);
490 RemoveList(pListHead,(PLISTINFO) temp);
492 pListHead = array[next_bucket];
493 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
495 pfNode->face_id = next_face_id;
496 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
497 (int (*)(void *,void *)) (Compare)));
498 if (lpListInfo == NULL)
500 printf("There is an error finding the next polygon2 %d %d\n",next_face_id,next_bucket);
503 Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
504 pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
508 Last_Edge(&e1,&e2,&e3,0);