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);
57 if (flag == -10) /* We are finished, now is time to output the triangle list */
59 fprintf(output,"\nt ");
60 tri = tri + Finished(&swap,output,FALSE);
63 /*printf("There are %d swaps %d tri %d strips\n",total,tri,strips);*/
68 Last_Edge(&temp1,&temp2,&temp3,0);
69 Add_Id_Strips(id1,where);
70 Add_Id_Strips(id2,where);
71 Add_Id_Strips(id3,where);
72 Last_Edge(&id1,&id2,&id3,1);
79 void Extend_BackwardsEx(int face_id, FILE *output, FILE *strip, int *ties,
80 int tie, int triangulate, int swaps, int *next_id)
82 /* We just made a strip, now we are going to see if we can extend
83 backwards from the starting face, which had 2 or more adjacencies
86 int bucket,next_face,num,x,y,z,c,max,f;
91 /* Get the first triangle that we have saved the the strip data
92 structure, so we can see if there are any polygons adjacent
93 to this edge or a neighboring one
97 pListFace = PolFaces[face_id];
98 face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
100 num = face->nPolSize;
102 /* Go through the edges to see if there is an adjacency
103 with a vertex in common to the first triangle that was
104 outputted in the strip. (maybe edge was deleted....)
106 for (c=0; c<num ; c++)
109 if ( (c != (num-1)) &&
110 (( (*(face->pPolygon+c) == x) && (*(face->pPolygon+c+1) == y)) ||
111 (*(face->pPolygon+c) == y) && (*(face->pPolygon+c+1) == x)))
113 /* Input edge is still there see if there is an adjacency */
114 next_face = Find_Face(face_id, x, y, &bucket);
116 /* Could not find a face adjacent to the edge */
118 pListFace = array[bucket];
119 max = NumOnList(pListFace);
122 temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);
123 if (temp->face_id == next_face)
125 Last_Edge(&z,&y,&x,1);
126 Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
127 output,strip,ties,tie,triangulate,swaps,next_id,0);
133 printf("Error in the new buckets%d %d %d\n",bucket,max,0);
139 else if ( (c == (num -1)) &&
140 ( ((*(face->pPolygon) == x) && (*(face->pPolygon+num-1) == y)) ||
141 (*(face->pPolygon) == y) && (*(face->pPolygon+num-1) == x)))
143 next_face = Find_Face(face_id,x,y,&bucket);
145 /* Could not find a face adjacent to the edge */
147 pListFace = array[bucket];
148 max = NumOnList(pListFace);
151 temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);
152 if (temp->face_id == next_face)
154 Last_Edge(&z,&y,&x,1);
155 Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
156 output,strip,ties,tie,triangulate,swaps,next_id,0);
162 printf("Error in the new buckets%d %d %d\n",bucket,max,0);
172 void Polygon_OutputEx(P_ADJACENCIES temp,int face_id,int bucket,
173 ListHead *pListHead, FILE *output, FILE *strips,
174 int *ties, int tie, int triangulate, int swaps,
175 int *next_id, int where)
179 P_ADJACENCIES pfNode;
180 static BOOL begin = TRUE;
181 int old_face,next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
182 P_ADJACENCIES lpListInfo;
184 /* We have a polygon to output, the id is face id, and the number
185 of adjacent polygons to it is bucket.
188 Last_Edge(&e1,&e2,&e3,0);
190 /* Get the polygon with id face_id */
191 pListFace = PolFaces[face_id];
192 face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
194 if (face->nPolSize == 3)
196 /* It is already a triangle */
199 /* It is not adjacent to anything so we do not have to
200 worry about the order of the sides or updating adjacencies
203 Last_Edge(&e1,&e2,&e3,0);
204 next_face_id = Different(*(face->pPolygon),*(face->pPolygon+1),*(face->pPolygon+2),
205 e1,e2,e3,&other1,&other2);
206 /* No input edge, at the start */
207 if ((e2 ==0) && (e3 == 0))
213 Output_TriEx(e2,e3,next_face_id,strips,-1,begin,where);
214 RemoveList(pListHead,(PLISTINFO) temp);
215 /* We will be at the beginning of the next strip. */
218 /* It is a triangle with adjacencies. This means that we
220 1. Update the adjacencies in the list, because we are
221 using this polygon and it will be deleted.
222 2. Get the next polygon.
226 /* Return the face_id of the next polygon we will be using,
227 while updating the adjacency list by decrementing the
228 adjacencies of everything adjacent to the current triangle.
231 next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
232 old_face = next_face_id;
234 /* Break the tie, if there was one */
236 old_face = Get_Next_Face(tie,face_id,triangulate);
238 if (next_face_id == -1)
240 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
241 triangulate,swaps,next_id,where);
246 /* We are using a different face */
247 if ((tie != FIRST) && (old_face != next_face_id) && (swaps == ON))
249 next_face_id = old_face;
250 /* Get the new output edge, since e1 and e2 are for the
251 original next face that we got.
253 e3 = Get_EdgeEx(&e1,&e2,face->pPolygon,next_face_id,face->nPolSize,0,0);
256 /* Find the other vertex to transmit in the triangle */
257 e3 = Return_Other(face->pPolygon,e1,e2);
258 Last_Edge(&other1,&other2,&other3,0);
260 if ((other1 != 0) && (other2 != 0))
262 /* See which vertex in the output edge is not in the input edge */
263 if ((e1 != other2) && (e1 != other3))
265 else if ((e2 != other2) && (e2 != other3))
267 /* can happen with > 2 polys on an edge but won't form a good strip so stop
272 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
273 triangulate,swaps,next_id,where);
277 /* See which vertex of the input edge is not in the output edge */
278 if ((other2 != e1) && (other2 != e2))
283 else if ((other3 != e1) && (other3 != e2))
287 /* Degenerate triangle just return*/
288 Output_TriEx(other1,other2,e3,strips,next_face_id,begin,where);
289 RemoveList(pListHead,(PLISTINFO) temp);
296 /* There was not an input edge, we are the first triangle in a strip */
299 /* Find the correct order to transmit the triangle, what is
300 the output edge that we want ?
307 /* At this point the adjacencies have been updated and we
308 have the next polygon id
310 Output_TriEx(other1,other2,e3,strips,next_face_id,begin,where);
311 RemoveList(pListHead,(PLISTINFO) temp);
314 if (Done(next_face_id,59,&next_bucket) == NULL)
317 pListHead = array[next_bucket];
318 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
320 pfNode->face_id = next_face_id;
321 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
322 (int (*)(void *,void *)) (Compare)));
323 if (lpListInfo == NULL)
325 printf("There is an error finding the next polygon3 %d\n",next_face_id);
328 Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
329 pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
336 /* It is not a triangle, we have to triangulate it .
337 Since it is not adjacent to anything we can triangulate it
342 /* Check to see if there is not an input edge */
343 Last_Edge(&other1,&other2,&other3,0);
344 if ((other1 == 0) && (other2 ==0))
345 Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
348 Blind_TriangulateEx(face->nPolSize,face->pPolygon,strips,
351 RemoveList(pListHead,(PLISTINFO) temp);
352 /* We will be at the beginning of the next strip. */
356 /* If we have specified PARTIAL triangulation then
357 we will go to special routines that will break the
358 polygon and update the data structure. Else everything
359 below will simply triangulate the whole polygon
361 else if (triangulate == PARTIAL)
364 /* Return the face_id of the next polygon we will be using,
366 next_face_id = Min_Face_AdjEx(face_id,&next_bucket,ties);
369 /* Don't do it partially, because we can go inside and get
370 less adjacencies, for a quad we can do the whole thing.
372 if ((face_id == next_face_id) && (face->nPolSize == 4) && (swaps == ON))
374 next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
375 if (next_face_id == -1)
377 /* There is no sequential face to go to, end the strip */
378 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
379 triangulate,swaps,next_id,where);
383 /* Break the tie, if there was one */
385 next_face_id = Get_Next_Face(tie,face_id,triangulate);
386 Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
387 output,next_face_id,face_id,where);
388 RemoveList(pListHead,(PLISTINFO) temp);
391 /* Was not a quad but we still do not want to do it partially for
392 now, since we want to only do one triangle at a time
394 else if ((face_id == next_face_id) && (swaps == ON))
395 Inside_Polygon(face->nPolSize,face->pPolygon,strips,output,
396 next_face_id,face_id,next_id,pListHead,temp,where);
400 if ((tie != FIRST) && (swaps == ON))
401 next_face_id = Get_Next_Face(tie,face_id,triangulate);
402 Partial_Triangulate(face->nPolSize,face->pPolygon,strips,
403 output,next_face_id,face_id,next_id,pListHead,temp,where);
404 /* Check the next bucket again ,maybe it changed
405 We calculated one less, but that might not be the case
409 if (Done(next_face_id,59,&next_bucket) == NULL)
411 /* Check to see if there is not an input edge */
412 Last_Edge(&other1,&other2,&other3,0);
413 if ((other1 == 0) && (other2 ==0))
414 Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
417 Blind_TriangulateEx(face->nPolSize,face->pPolygon,strips,
420 if (Done(face_id,59,&bucket) != NULL)
422 pListHead = array[bucket];
423 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
425 pfNode->face_id = face_id;
426 lpListInfo = (P_ADJACENCIES) (SearchList(array[bucket], pfNode,
427 (int (*)(void *,void *)) (Compare)));
428 RemoveList(pListHead,(PLISTINFO)lpListInfo);
435 pListHead = array[next_bucket];
436 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
438 pfNode->face_id = next_face_id;
439 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
440 (int (*)(void *,void *)) (Compare)));
441 if (lpListInfo == NULL)
443 printf("There is an error finding the next polygon1 %d %d\n",next_face_id,next_bucket);
446 Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
447 pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
453 /* WHOLE triangulation */
454 /* It is not a triangle and has adjacencies.
455 This means that we have to:
456 1. TriangulateEx this polygon, not blindly because
457 we have an edge that we want to come out on, that
458 is the edge that is adjacent to a polygon with the
459 least number of adjacencies. Also we must come in
460 on the last seen edge.
461 2. Update the adjacencies in the list, because we are
463 3. Get the next polygon.
465 /* Return the face_id of the next polygon we will be using,
466 while updating the adjacency list by decrementing the
467 adjacencies of everything adjacent to the current polygon.
470 next_face_id = Update_AdjacenciesEx(face_id, &next_bucket, &e1,&e2,ties);
472 if (Done(next_face_id,59,&next_bucket) == NULL)
474 Polygon_OutputEx(temp,face_id,0,pListHead,output,strips,ties,tie,
475 triangulate,swaps,next_id,where);
476 /* Because maybe there was more than 2 polygons on the edge */
480 /* Break the tie, if there was one */
481 else if (tie != FIRST)
482 next_face_id = Get_Next_Face(tie,face_id,triangulate);
484 Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon, strips,
485 output,next_face_id,face_id,where);
486 RemoveList(pListHead,(PLISTINFO) temp);
488 pListHead = array[next_bucket];
489 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
491 pfNode->face_id = next_face_id;
492 lpListInfo = (P_ADJACENCIES) (SearchList(array[next_bucket], pfNode,
493 (int (*)(void *,void *)) (Compare)));
494 if (lpListInfo == NULL)
496 printf("There is an error finding the next polygon2 %d %d\n",next_face_id,next_bucket);
499 Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
500 pListHead, output, strips,ties,tie,triangulate,swaps,next_id,where);
504 Last_Edge(&e1,&e2,&e3,0);