1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
11 Contains routines that update structures, and micellaneous routines.
13 /*---------------------------------------------------------------------*/
20 #include "triangulate.h"
29 int Get_Edge(int *edge1,int *edge2,int *index,int face_id,
30 int size, int id1, int id2)
32 /* Put the edge that is adjacent to face_id into edge1
33 and edge2. For each edge see if it is adjacent to
34 face_id. Id1 and id2 is the input edge, so see if
35 the orientation is reversed, and save it in reversed.
41 for (x=0; x< size; x++)
45 if ((*(index) == id1) && (*(index+size-1)==id2))
51 else if ((*(index) == id2) && (*(index+size-1)==id1))
58 if (Look_Up(*(index),*(index+size-1),face_id))
60 if ( (out1 != -1) && ( (out1 == *(index)) || (out1 == *(index+size-1)) ) &&
61 ( (out2 == *(index)) || (out2 == *(index+size-1)) ))
65 *edge2 = *(index+size-1);
71 *edge2 = *(index+size-1);
73 if ((reversed != -1) && (set))
79 if ((*(index+x) == id1) && (*(index+x+1)==id2))
85 else if ((*(index+x) == id2) && (*(index+x+1)==id1))
92 if (Look_Up(*(index+x),*(index+x+1),face_id))
94 if ( (out1 != -1) && ( (out1 == *(index+x)) || (out1 == *(index+x+1)) ) &&
95 ((out2 == *(index+x)) || (out2 == *(index+x+1))))
99 *edge2 = *(index+x+1);
105 *edge2 = *(index+x + 1);
107 if ((reversed != -1) && (set))
112 if ((x == size) && (reversed != -1))
114 /* Could not find the output edge */
115 printf("Error in the Lookup %d %d %d %d %d %d %d %d\n",face_id,id1,id2,reversed,*edge1,*edge2,out1,out2);
122 void Update_Face(int *next_bucket, int *min_face, int face_id, int *e1,
123 int *e2,int temp1,int temp2,int *ties)
125 /* We have a face id that needs to be decremented.
126 We have to determine where it is in the structure,
127 so that we can decrement it.
129 /* The number of adjacencies may have changed, so to locate
130 it may be a little tricky. However we know that the number
131 of adjacencies is less than or equal to the original number
136 PF_FACES temp = NULL;
137 PLISTINFO lpListInfo;
138 static int each_poly = 0;
141 pListHead = PolFaces[face_id];
142 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
143 /* Check each edge of the face and tally the number of adjacent
144 polygons to this face.
148 /* Size of the polygon */
149 size = temp->nPolSize;
150 /* We did it already */
153 for (y = 0; y< size; y++)
155 /* If we are doing partial triangulation, we must check
156 to see whether the edge is still there in the polygon,
157 since we might have done a portion of the polygon
158 and saved the rest for later.
162 if( ((temp1 == *(temp->pPolygon+y)) && (temp2 ==*(temp->pPolygon+y+1)))
163 || ((temp2 == *(temp->pPolygon+y)) && (temp1 ==*(temp->pPolygon+y+1))))
164 /* edge is still there we are ok */
169 if( ((temp1 == *(temp->pPolygon)) && (temp2 == *(temp->pPolygon+size-1)))
170 || ((temp2 == *(temp->pPolygon)) && (temp1 ==*(temp->pPolygon+size-1))))
171 /* edge is still there we are ok */
177 /* Original edge was already used, we cannot use this polygon */
180 /* We have a starting point to start our search to locate
184 /* Check to see if this polygon was done */
185 lpListInfo = Done(face_id,59,&y);
187 if (lpListInfo == NULL)
190 /* Was not done, but there is an error in the adjacency calculations */
193 printf("There is an error in finding the adjacencies\n");
197 /* Now put the face in the proper bucket depending on tally. */
198 /* First add it to the new bucket, then remove it from the old */
199 Add_Sgi_Adj(y-1,face_id);
200 RemoveList(array[y],lpListInfo);
202 /* Save it if it was the smallest seen so far since then
203 it will be the next face
204 Here we will have different options depending on
205 what we want for resolving ties:
206 1) First one we see we will use
209 4) Alternating direction
212 if (*next_bucket == 60)
213 *ties = *ties + each_poly;
215 if (*next_bucket == (y-1))
220 /* At a new minimum */
221 if (*next_bucket > (y-1))
235 void Delete_Adj(int id1, int id2,int *next_bucket,int *min_face,
236 int current_face,int *e1,int *e2,int *ties)
238 /* Find the face that is adjacent to the edge and is not the
239 current face. Delete one adjacency from it. Save the min
240 adjacency seen so far.
242 register int count=0;
243 PF_EDGES temp = NULL;
247 /* Always want smaller id first */
248 switch_lower(&id1,&id2);
250 pListHead = PolEdges[id1];
251 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
253 /* It could be a new edge that we created. So we can
254 exit, since there is not a face adjacent to it.
257 while (temp->edge[0] != id2)
260 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
262 /* Was a new edge that was created and therefore
263 does not have anything adjacent to it
267 /* Was not adjacent to anything else except itself */
268 if (temp->edge[2] == -1)
271 /* Was adjacent to something */
274 if (temp->edge[2] == current_face)
275 next_face = temp->edge[1];
277 next_face = temp->edge[2];
279 /* We have the other face adjacent to this edge, it is
280 next_face. Now we need to decrement this faces' adjacencies.
282 Update_Face(next_bucket, min_face, next_face,e1,e2,id1,id2,ties);
286 int Change_Face(int face_id,int in1,int in2,
287 ListHead *pListHead, P_ADJACENCIES temp, BOOL no_check)
289 /* We are doing a partial triangulation and we need to
290 put the new face of triangle into the correct bucket
294 /* Find the old number of adjacencies to this face,
295 so we know where to delete it from
297 y = Old_Adj(face_id);
299 /* Do we need to change the adjacency? Maybe the edge on the triangle
300 that was outputted was not adjacent to anything. We know if we
301 have to check by "check". We came out on the output edge
302 that we needed, then we know that the adjacencies will decrease
307 input_adj = Number_Adj(in1,in2,face_id);
308 /* If there weren't any then don't do anything */
313 RemoveList(pListHead,(PLISTINFO)temp);
314 /* Before we had a quad with y adjacencies. The in edge
315 did not have an adjacency, since it was just deleted,
316 since we came in on it. The outedge must have an adjacency
317 otherwise we would have a bucket 0, and would not be in this
318 routine. Therefore the new adjacency must be y-1
321 Add_Sgi_Adj(y-1,face_id);
325 int Update_Adjacencies(int face_id, int *next_bucket, int *e1, int *e2,
328 /* Give the face with id face_id, we want to decrement
329 all the faces that are adjacent to it, since we will
330 be deleting face_id from the data structure.
331 We will return the face that has the least number
334 PF_FACES temp = NULL;
336 int size,y,min_face = -1;
339 pListHead = PolFaces[face_id];
340 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
344 printf("The face was already deleted, there is an error\n");
348 /* Size of the polygon */
349 size = temp->nPolSize;
350 for (y = 0; y< size; y++)
353 Delete_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
354 next_bucket,&min_face,face_id,e1,e2,ties);
356 Delete_Adj(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
357 next_bucket,&min_face,face_id,e1,e2,ties);
363 void Find_Adj_Tally(int id1, int id2,int *next_bucket,int *min_face,
364 int current_face,int *ties)
366 /* Find the face that is adjacent to the edge and is not the
367 current face. Save the min adjacency seen so far.
369 int size,each_poly=0,y,tally=0,count=0;
370 PF_EDGES temp = NULL;
371 PF_FACES temp2 = NULL;
377 /* Always want smaller id first */
378 switch_lower(&id1,&id2);
380 pListHead = PolEdges[id1];
381 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
383 /* This was a new edge that was created, so it is
388 while (temp->edge[0] != id2)
391 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
393 /* This was a new edge that we created */
396 /* Was not adjacent to anything else except itself */
397 if (temp->edge[2] == -1)
401 if (temp->edge[2] == current_face)
402 next_face = temp->edge[1];
404 next_face = temp->edge[2];
406 /* We have the other face adjacent to this edge, it is
407 next_face. Find how many faces it is adjacent to.
409 pListHead = PolFaces[next_face];
410 temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
411 /* Check each edge of the face and tally the number of adjacent
412 polygons to this face. This will be the original number of
413 polygons adjacent to this polygon, we must then see if this
414 number has been decremented
418 /* Size of the polygon */
419 size = temp2->nPolSize;
420 /* We did it already */
423 for (y = 0; y< size; y++)
425 /* Make sure that the edge is still in the
426 polygon and was not deleted, because if the edge was
427 deleted, then we used it already.
431 if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
432 || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
433 /* edge is still there we are ok */
438 if( ((id1 == *(temp2->pPolygon)) && (id2 ==*(temp2->pPolygon+size-1)))
439 || ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
440 /* edge is still there we are ok */
446 /* Edge already used and deleted from the polygon*/
449 /* See if the face was already deleted, and where
452 if (Done(next_face,size,&y) == NULL)
455 /* Save it if it was the smallest seen so far since then
456 it will be the next face
457 Here we will have different options depending on
458 what we want for resolving ties:
459 1) First one we see we will use
462 4) Alternating direction
466 if (*next_bucket == 60)
467 *ties = *ties + each_poly;
469 if (*next_bucket == (y-1))
474 /* At a new minimum */
475 if (*next_bucket > (y-1))
478 *min_face = next_face;
487 int Min_Face_Adj(int face_id, int *next_bucket, int *ties)
489 /* Used for the Partial triangulation to find the next
490 face. It will return the minimum adjacency face id
493 PF_FACES temp = NULL;
495 int size,y,min_face,test_face;
498 pListHead = PolFaces[face_id];
499 temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
503 printf("The face was already deleted, there is an error\n");
507 /* Size of the polygon */
508 size = temp->nPolSize;
509 for (y = 0; y< size; y++)
512 Find_Adj_Tally(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
513 next_bucket,&min_face,face_id,ties);
515 Find_Adj_Tally(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
516 next_bucket,&min_face,face_id,ties);
518 /* Maybe we can do better by triangulating the face, because
519 by triangulating the face we will go to a polygon of lesser
524 /* Checking for a quad whether to do the whole polygon will
525 result in better performance because the triangles in the polygon
526 have less adjacencies
528 Check_In_Quad(face_id,&test_face);
529 if (*next_bucket > test_face)
530 /* We can do better by going through the polygon */
534 /* We have a polygon with greater than 4 sides, check to see if going
535 inside is better than going outside the polygon for the output edge.
539 Check_In_Polygon(face_id,&test_face,size);
540 if (*next_bucket > test_face)
541 /* We can do better by going through the polygon */