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"
22 #include "sturctsex.h"
30 int Get_EdgeEx(int *edge1,int *edge2,int *index,int face_id,
31 int size, int id1, int id2)
33 /* Put the edge that is adjacent to face_id into edge1
34 and edge2. For each edge see if it is adjacent to
35 face_id. Id1 and id2 is the input edge, so see if
36 the orientation is reversed, and save it in reversed.
42 for (x=0; x< size; x++)
46 if ((*(index) == id1) && (*(index+size-1)==id2))
52 else if ((*(index) == id2) && (*(index+size-1)==id1))
59 if (Look_Up(*(index),*(index+size-1),face_id))
61 if ( (out1Ex != -1) && ( (out1Ex == *(index)) || (out1Ex == *(index+size-1)) ) &&
62 ( (out2Ex == *(index)) || (out2Ex == *(index+size-1)) ))
66 *edge2 = *(index+size-1);
68 else if (out1Ex == -1)
72 *edge2 = *(index+size-1);
74 if ((reversed != -1) && (set))
80 if ((*(index+x) == id1) && (*(index+x+1)==id2))
86 else if ((*(index+x) == id2) && (*(index+x+1)==id1))
93 if (Look_Up(*(index+x),*(index+x+1),face_id))
95 if ( (out1Ex != -1) && ( (out1Ex == *(index+x)) || (out1Ex == *(index+x+1)) ) &&
96 ((out2Ex == *(index+x)) || (out2Ex == *(index+x+1))))
100 *edge2 = *(index+x+1);
102 else if (out1Ex == -1)
106 *edge2 = *(index+x + 1);
108 if ((reversed != -1) && (set))
113 if ((x == size) && (reversed != -1))
115 /* Could not find the output edge */
116 printf("Error in the Lookup %d %d %d %d %d %d %d %d\n",face_id,id1,id2,reversed,*edge1,*edge2,out1Ex,out2Ex);
123 void Update_FaceEx(int *next_bucket, int *min_face, int face_id, int *e1,
124 int *e2,int temp1,int temp2,int *ties)
126 /* We have a face id that needs to be decremented.
127 We have to determine where it is in the structure,
128 so that we can decrement it.
130 /* The number of adjacencies may have changed, so to locate
131 it may be a little tricky. However we know that the number
132 of adjacencies is less than or equal to the original number
137 PF_FACES temp = NULL;
138 PLISTINFO lpListInfo;
139 static int each_poly = 0;
142 pListHead = PolFaces[face_id];
143 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
144 /* Check each edge of the face and tally the number of adjacent
145 polygons to this face.
149 /* Size of the polygon */
150 size = temp->nPolSize;
151 for (y = 0; y< size; y++)
153 /* If we are doing partial triangulation, we must check
154 to see whether the edge is still there in the polygon,
155 since we might have done a portion of the polygon
156 and saved the rest for later.
160 if( ((temp1 == *(temp->pPolygon+y)) && (temp2 ==*(temp->pPolygon+y+1)))
161 || ((temp2 == *(temp->pPolygon+y)) && (temp1 ==*(temp->pPolygon+y+1))))
162 /* edge is still there we are ok */
167 if( ((temp1 == *(temp->pPolygon)) && (temp2 == *(temp->pPolygon+size-1)))
168 || ((temp2 == *(temp->pPolygon)) && (temp1 ==*(temp->pPolygon+size-1))))
169 /* edge is still there we are ok */
175 /* Original edge was already used, we cannot use this polygon */
178 /* We have a starting point to start our search to locate
182 /* Check to see if this polygon was done */
183 lpListInfo = Done(face_id,59,&y);
185 if (lpListInfo == NULL)
188 /* Was not done, but there is an error in the adjacency calculations */
189 /* If more than one edge is adj to it then maybe it was not updated */
193 /* Now put the face in the proper bucket depending on tally. */
194 /* First add it to the new bucket, then remove it from the old */
195 Add_Sgi_Adj(y-1,face_id);
196 RemoveList(array[y],lpListInfo);
198 /* Save it if it was the smallest seen so far since then
199 it will be the next face
200 Here we will have different options depending on
201 what we want for resolving ties:
202 1) First one we see we will use
205 4) Alternating direction
208 if (*next_bucket == 60)
209 *ties = *ties + each_poly;
211 if (*next_bucket == (y-1))
216 /* At a new minimum */
217 if (*next_bucket > (y-1))
231 void Delete_AdjEx(int id1, int id2,int *next_bucket,int *min_face,
232 int current_face,int *e1,int *e2,int *ties)
234 /* Find the face that is adjacent to the edge and is not the
235 current face. Delete one adjacency from it. Save the min
236 adjacency seen so far.
238 register int count=0;
239 PF_EDGES temp = NULL;
243 /* Always want smaller id first */
244 switch_lower(&id1,&id2);
246 pListHead = PolEdges[id1];
247 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
249 /* It could be a new edge that we created. So we can
250 exit, since there is not a face adjacent to it.
253 while (temp->edge[0] != id2)
256 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
258 /* Was a new edge that was created and therefore
259 does not have anything adjacent to it
263 /* Was not adjacent to anything else except itself */
264 if (temp->edge[2] == -1)
267 /* Was adjacent to something */
270 if (temp->edge[2] == current_face)
271 next_face = temp->edge[1];
273 next_face = temp->edge[2];
275 /* We have the other face adjacent to this edge, it is
276 next_face. Now we need to decrement this faces' adjacencies.
278 Update_FaceEx(next_bucket, min_face, next_face,e1,e2,id1,id2,ties);
281 int Change_FaceEx(int face_id,int in1,int in2,
282 ListHead *pListHead, P_ADJACENCIES temp, BOOL no_check)
284 /* We are doing a partial triangulation and we need to
285 put the new face of triangle into the correct bucket
288 P_ADJACENCIES pfNode,lpListInfo;
290 /* Find the old number of adjacencies to this face,
291 so we know where to delete it from
293 y = Old_Adj(face_id);
294 pListHead = array[y];
296 pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
298 pfNode->face_id = face_id;
299 lpListInfo = (P_ADJACENCIES) (SearchList(array[y], pfNode,
300 (int (*)(void *,void *)) (Compare)));
301 if (lpListInfo == NULL)
303 printf("There is an error finding the next polygon3 %d\n",face_id);
307 /* Do we need to change the adjacency? Maybe the edge on the triangle
308 that was outputted was not adjacent to anything. We know if we
309 have to check by "check". We came out on the output edge
310 that we needed, then we know that the adjacencies will decrease
315 input_adj = Number_Adj(in1,in2,face_id);
316 /* If there weren't any then don't do anything */
321 RemoveList(pListHead,(PLISTINFO)/*(temp*/lpListInfo);
322 /* Before we had a quad with y adjacencies. The in edge
323 did not have an adjacency, since it was just deleted,
324 since we came in on it. The outedge must have an adjacency
325 otherwise we would have a bucket 0, and would not be in this
326 routine. Therefore the new adjacency must be y-1
329 Add_Sgi_Adj(y-1,face_id);
333 int Update_AdjacenciesEx(int face_id, int *next_bucket, int *e1, int *e2,
336 /* Give the face with id face_id, we want to decrement
337 all the faces that are adjacent to it, since we will
338 be deleting face_id from the data structure.
339 We will return the face that has the least number
342 PF_FACES temp = NULL;
344 int size,y,min_face = -1;
347 pListHead = PolFaces[face_id];
348 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
352 printf("The face was already deleted, there is an error\n");
356 /* Size of the polygon */
357 size = temp->nPolSize;
358 for (y = 0; y< size; y++)
361 Delete_AdjEx(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
362 next_bucket,&min_face,face_id,e1,e2,ties);
364 Delete_AdjEx(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
365 next_bucket,&min_face,face_id,e1,e2,ties);
372 void Find_Adj_TallyEx(int id1, int id2,int *next_bucket,int *min_face,
373 int current_face,int *ties)
375 /* Find the face that is adjacent to the edge and is not the
376 current face. Save the min adjacency seen so far.
378 int size,each_poly=0,y,tally=0,count=0;
379 PF_EDGES temp = NULL;
380 PF_FACES temp2 = NULL;
386 /* Always want smaller id first */
387 switch_lower(&id1,&id2);
389 pListHead = PolEdges[id1];
390 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
392 /* This was a new edge that was created, so it is
396 while (temp->edge[0] != id2)
399 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
401 /* This was a new edge that we created */
404 /* Was not adjacent to anything else except itself */
405 if (temp->edge[2] == -1)
409 if (temp->edge[2] == current_face)
410 next_face = temp->edge[1];
412 next_face = temp->edge[2];
414 /* We have the other face adjacent to this edge, it is
415 next_face. Find how many faces it is adjacent to.
417 pListHead = PolFaces[next_face];
418 temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
419 /* Check each edge of the face and tally the number of adjacent
420 polygons to this face. This will be the original number of
421 polygons adjacent to this polygon, we must then see if this
422 number has been decremented
426 /* Size of the polygon */
427 size = temp2->nPolSize;
428 for (y = 0; y< size; y++)
430 /* Make sure that the edge is still in the
431 polygon and was not deleted, because if the edge was
432 deleted, then we used it already.
436 if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
437 || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
438 /* edge is still there we are ok */
443 if( ((id1 == *(temp2->pPolygon)) && (id2 ==*(temp2->pPolygon+size-1)))
444 || ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
445 /* edge is still there we are ok */
451 /* Edge already used and deleted from the polygon*/
454 /* See if the face was already deleted, and where
457 if (Done(next_face,size,&y) == NULL)
460 /* Save it if it was the smallest seen so far since then
461 it will be the next face
462 Here we will have different options depending on
463 what we want for resolving ties:
464 1) First one we see we will use
467 4) Alternating direction
471 if (*next_bucket == 60)
472 *ties = *ties + each_poly;
474 if (*next_bucket == (y-1))
479 /* At a new minimum */
480 if (*next_bucket > (y-1))
483 *min_face = next_face;
492 int Min_Face_AdjEx(int face_id, int *next_bucket, int *ties)
494 /* Used for the Partial triangulation to find the next
495 face. It will return the minimum adjacency face id
498 PF_FACES temp = NULL;
500 int size,y,min_face,test_face;
503 pListHead = PolFaces[face_id];
504 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
508 printf("The face was already deleted, there is an error\n");
512 /* Size of the polygon */
513 size = temp->nPolSize;
514 for (y = 0; y< size; y++)
517 Find_Adj_TallyEx(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
518 next_bucket,&min_face,face_id,ties);
520 Find_Adj_TallyEx(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
521 next_bucket,&min_face,face_id,ties);
523 /* Maybe we can do better by triangulating the face, because
524 by triangulating the face we will go to a polygon of lesser
529 /* Checking for a quad whether to do the whole polygon will
530 result in better performance because the triangles in the polygon
531 have less adjacencies
533 Check_In_Quad(face_id,&test_face);
534 if (*next_bucket > test_face)
535 /* We can do better by going through the polygon */
539 /* We have a polygon with greater than 4 sides, check to see if going
540 inside is better than going outside the polygon for the output edge.
544 Check_In_Polygon(face_id,&test_face,size);
545 if (*next_bucket > test_face)
546 /* We can do better by going through the polygon */