1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
11 This routine contains the bulk of the code that will find the
12 patches of quads in the data model
14 /*---------------------------------------------------------------------*/
20 #include "triangulate.h"
31 BOOL resetting = FALSE;
34 BOOL reversed = FALSE;
39 int Calculate_Walks(int lastvert,int y, PF_FACES temp2)
41 /* Find the length of the walk */
43 int previous_edge1, previous_edge2;
44 register int nextvert,numverts,counter,walk=0;
50 /* Find the edge that we are currently on */
53 previous_edge1 = *(temp2->pPolygon +y);
54 previous_edge2 = *(temp2->pPolygon + y + 1);
58 previous_edge1 = *(temp2->pPolygon +y);
59 previous_edge2 = *(temp2->pPolygon);
65 /*Find the adjacent face to this edge */
66 node = *(temp2->VertandId+y);
67 if (node->edge[2] != lastvert)
68 nextvert = node->edge[2];
70 nextvert = node->edge[1];
72 /* Keep walking in this direction until we cannot do so */
73 while ((nextvert != lastvert) && (nextvert != -1))
76 pListHead = PolFaces[nextvert];
77 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
78 numverts = temp2->nPolSize;
79 if ((numverts != 4) || (temp2->seen == seen))
87 /* Find edge that is not adjacent to the previous one */
90 while ((counter < 3) && (flag))
92 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
93 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
94 ((*(temp2->pPolygon+counter) == previous_edge2) ||
95 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
100 /* Get the IDs of the next edge */
103 previous_edge1 = *(temp2->pPolygon + counter);
104 previous_edge2 = *(temp2->pPolygon + counter + 1);
108 previous_edge1 = *(temp2->pPolygon + counter);
109 previous_edge2 = *(temp2->pPolygon);
112 node = *(temp2->VertandId + counter);
113 if (node->edge[1] == nextvert)
114 nextvert = node->edge[2];
116 nextvert = node->edge[1];
124 BOOL Check_Right(int last_seen,PF_FACES temp2,int y,int face_id)
126 /* Check when we last saw the face to the right of the current
127 one. We want to have seen it just before we started this strip
132 register int nextvert,oldy;
140 node = *(temp2->VertandId + y);
141 if (face_id == node->edge[1])
142 nextvert = node->edge[2];
144 nextvert = node->edge[1];
149 pListHead = PolFaces[nextvert];
150 t = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
151 if (t->seen != (last_seen - 1))
153 /* maybe because of the numbering, we are not
154 on the right orientation, so we have to check the
155 opposite one to be sure
161 node = *(temp2->VertandId + y);
162 if (face_id == node->edge[1])
163 nextvert = node->edge[2];
165 nextvert = node->edge[1];
168 pListHead = PolFaces[nextvert];
169 t = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
170 if (t->seen != (last_seen - 1))
177 int Update_and_Test(PF_FACES temp2,int y,BOOL first,int distance,int lastvert, int val)
180 static int last_seen = 17;
181 int previous_edge1, previous_edge2;
182 register int original_distance,nextvert,numverts,counter;
187 original_distance = distance;
188 /* Find the edge that we are currently on */
191 previous_edge1 = *(temp2->pPolygon +y);
192 previous_edge2 = *(temp2->pPolygon + y + 1);
196 previous_edge1 = *(temp2->pPolygon +y);
197 previous_edge2 = *(temp2->pPolygon);
203 node = *(temp2->VertandId+y);
204 if (lastvert != node->edge[2])
205 nextvert = node->edge[2];
207 nextvert = node->edge[1];
209 /* Keep walking in this direction until we cannot do so or
211 while ((distance > 0) && (nextvert != lastvert) && (nextvert != -1))
215 pListHead = PolFaces[nextvert];
216 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
219 if (temp2->seen2 == val)
222 return (original_distance - distance);
227 numverts = temp2->nPolSize;
232 else if ((!first) && (!(Check_Right(last_seen,temp2,y,nextvert))))
235 return (original_distance - distance);
239 /* Find edge that is not adjacent to the previous one */
242 while ((counter < 3) && (flag))
244 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
245 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
246 ((*(temp2->pPolygon+counter) == previous_edge2) ||
247 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
252 /* Get the IDs of the next edge */
255 previous_edge1 = *(temp2->pPolygon + counter);
256 previous_edge2 = *(temp2->pPolygon + counter + 1);
260 previous_edge1 = *(temp2->pPolygon + counter);
261 previous_edge2 = *(temp2->pPolygon);
263 if ( ((*(temp2->walked+counter) == -1) &&
264 (*(temp2->walked+counter+2) == -1)))
266 printf("There is an error in the walks!\n");
267 printf("1Code %d %d \n",*(temp2->walked+counter),*(temp2->walked+counter+2));
272 if ((*(temp2->walked+counter) == -1) &&
273 (*(temp2->walked+counter-2) == -1))
275 printf("There is an error in the walks!\n");
276 printf("2Code %d %d \n",*(temp2->walked+counter),*(temp2->walked+counter-2));
280 node = *(temp2->VertandId + counter);
282 if (node->edge[1] == nextvert)
283 nextvert = node->edge[2];
285 nextvert = node->edge[1];
293 if (((nextvert == -1) || (nextvert == lastvert)) && (distance != 1))
294 return (original_distance - distance);
296 return original_distance;
300 int Test_Adj(PF_FACES temp2,int x,int north,int distance,int lastvert, int value)
302 /* if first time, then just update the last seen field */
304 return(Update_and_Test(temp2,north,TRUE,distance,lastvert,value));
305 /* else we have to check if we are adjacent to the last strip */
307 return(Update_and_Test(temp2,north,FALSE,distance,lastvert,value));
310 void Get_Band_Walk(PF_FACES temp2,int face_id,int *dir1,int *dir2,
311 int orientation,int cutoff_length)
313 int previous_edge1, previous_edge2;
316 register int walk = 0, nextvert,numverts,counter;
319 /* Get the largest band that will include this face, starting
320 from orientation. Save the values of the largest band
321 (either north and south together, or east and west together)
322 in the direction variables.
324 /* Find the edge that we are currently on */
325 if (orientation != 3)
327 previous_edge1 = *(temp2->pPolygon + orientation);
328 previous_edge2 = *(temp2->pPolygon + orientation + 1);
332 previous_edge1 = *(temp2->pPolygon + orientation );
333 previous_edge2 = *(temp2->pPolygon);
336 if (orientation == 0)
338 if (*dir1 > *(temp2->walked + 1))
339 *dir1 = *(temp2->walked + 1);
340 if (*dir2 > *(temp2->walked + 3))
341 *dir2 = *(temp2->walked + 3);
343 else if (orientation == 3)
345 if (*dir1 > *(temp2->walked + orientation - 3))
346 *dir1 = *(temp2->walked + orientation - 3) ;
347 if (*dir2 > *(temp2->walked + orientation -1 ))
348 *dir2 = *(temp2->walked + orientation - 1);
352 if (*dir1 > *(temp2->walked + orientation - 1))
353 *dir1 = *(temp2->walked + orientation -1) ;
354 if (*dir2 > *(temp2->walked+ orientation + 1))
355 *dir2 = *(temp2->walked + orientation + 1);
358 /* if we know already that we can't extend the
359 band from this face, we do not need to do the walk
361 if ((*dir1 != 0) && (*dir2 != 0))
363 /* Find the adjacent face to this edge */
364 node = *(temp2->VertandId+orientation);
365 if (face_id == node->edge[1])
366 nextvert = node->edge[2];
368 nextvert = node->edge[1];
371 nextvert = -1; /* leave w/o walking */
373 /* Keep walking in this direction until we cannot do so */
374 while ((nextvert != face_id) && (nextvert != -1))
377 pListHead = PolFaces[nextvert];
378 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
379 numverts = temp2->nPolSize;
380 if ((numverts != 4) || (walk > cutoff_length))
384 /* Find edge that is not adjacent to the previous one */
387 while ((counter < 3) && (flag))
389 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
390 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
391 ((*(temp2->pPolygon+counter) == previous_edge2) ||
392 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
397 /* Get the IDs of the next edge */
400 previous_edge1 = *(temp2->pPolygon + counter);
401 previous_edge2 = *(temp2->pPolygon + counter + 1);
405 previous_edge1 = *(temp2->pPolygon + counter);
406 previous_edge2 = *(temp2->pPolygon);
409 /* find out how far we can extend in the 2 directions
410 along this new face in the walk
414 if (*dir1 > *(temp2->walked + 1))
415 *dir1 = *(temp2->walked + 1);
416 if (*dir2 > *(temp2->walked + 3))
417 *dir2 = *(temp2->walked + 3);
419 else if (counter == 3)
421 if (*dir1 > *(temp2->walked + counter - 3))
422 *dir1 = *(temp2->walked + counter - 3) ;
423 if (*dir2 > *(temp2->walked + counter -1 ))
424 *dir2 = *(temp2->walked + counter -1);
428 if (*dir1 > *(temp2->walked + counter - 1))
429 *dir1 = *(temp2->walked + counter -1) ;
430 if (*dir2 > *(temp2->walked + counter + 1))
431 *dir2 = *(temp2->walked + counter + 1);
434 /* if we know already that we can't extend the
435 band from this face, we do not need to do the walk
437 if ((*dir1 == 0) || (*dir2 == 0))
441 node = *(temp2->VertandId + counter);
442 if (node->edge[1] == nextvert)
443 nextvert = node->edge[2];
445 nextvert = node->edge[1];
455 int Find_Max(PF_FACES temp2,int lastvert,int north,int left,
456 int *lastminup,int *lastminleft)
458 int temp,walk,counter,minup,x,band_value;
459 int previous_edge1, previous_edge2;
463 static int last_seen = 0;
464 register int smallest_so_far,nextvert,max=-1;
466 *lastminup = MAX_BAND;
471 previous_edge1 = *(temp2->pPolygon + left);
472 previous_edge2 = *(temp2->pPolygon);
477 previous_edge1 = *(temp2->pPolygon + left + 1);
478 previous_edge2 = *(temp2->pPolygon + left);
481 temp2->seen = last_seen;
482 walk = *(temp2->walked + left);
484 for (x=1;x<=(walk+1); x++)
486 /* test to see if we have a true band
487 that is, are they adjacent to each other
490 minup = *(temp2->walked + north) + 1;
492 /* if we are at the very first face, then we do not
493 have to check the adjacent faces going up
494 and our north distance is the distance of this face's
500 minup = Test_Adj(temp2,x,north,*lastminup,lastvert,last_seen);
502 smallest_so_far = minup;
506 /* find the largest band that we can have */
507 if (minup < (*lastminup))
509 /* see if we really can go up all the way
510 temp should by less than our equal to minup
511 if it is less, then one of the faces was not
512 adjacent to those next to it and the band height
515 temp = Test_Adj(temp2,x,north,minup,lastvert,last_seen);
518 printf("There is an error in the test adj\n");
522 band_value = x * minup;
523 if (minup < smallest_so_far)
525 if (band_value > max)
527 smallest_so_far = minup;
533 smallest_so_far = minup;
537 band_value = x * smallest_so_far;
538 if (band_value > max)
540 *lastminup = smallest_so_far;
550 temp = Test_Adj(temp2,x,north,smallest_so_far,lastvert,last_seen);
551 if (temp > smallest_so_far)
553 printf("There is an error in the test adj\n");
556 smallest_so_far = temp;
558 band_value = x * smallest_so_far;
559 if (band_value > max)
561 *lastminup = smallest_so_far;
566 if ( x != (walk + 1))
568 node = *(temp2->VertandId+left);
569 if (lastvert == node->edge[1])
570 nextvert = node->edge[2];
572 nextvert = node->edge[1];
579 pListHead = PolFaces[nextvert];
580 temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
582 /* if we have visited this face before, then there is an error */
583 if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
584 (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
585 || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
588 if (lastvert == node->edge[1])
589 nextvert = node->edge[2];
591 nextvert = node->edge[1];
595 /* Last attempt to get the face ... */
596 pListHead = PolFaces[nextvert];
597 temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
598 if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
599 (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
600 || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
601 return max; /* The polygon was not saved with the edge, not
602 enough room. We will get the walk when we come
603 to that polygon later.
610 temp2->seen = last_seen;
612 while ((counter < 3) && (flag))
615 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
616 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
617 ((*(temp2->pPolygon+counter) == previous_edge2) ||
618 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
625 /* Get the IDs of the next edge */
632 previous_edge1 = *(temp2->pPolygon + counter + 1);
633 previous_edge2 = *(temp2->pPolygon + counter);
637 previous_edge1 = *(temp2->pPolygon + counter);
638 previous_edge2 = *(temp2->pPolygon);
648 void Mark_Face(PF_FACES temp2, int color1, int color2,
649 int color3, FILE *output_file, BOOL end, int *edge1, int *edge2,
650 int *face_id, int norms, int texture)
652 static int last_quad[4];
655 static int output1, output2,last_id;
656 BOOL cptexture = FALSE;
658 /* Are we done with the patch? If so return the last edge that
659 we will come out on, and that will be the edge that we will
660 start to extend upon.
673 *(temp2->walked) = -1;
674 *(temp2->walked+1) = -1;
675 *(temp2->walked+2) = -1;
676 *(temp2->walked+3) = -1;
682 /* At the first quad in the strip -- save it */
683 last_quad[0] = *(temp2->pPolygon);
684 last_quad[1] = *(temp2->pPolygon+1);
685 last_quad[2] = *(temp2->pPolygon+2);
686 last_quad[3] = *(temp2->pPolygon+3);
691 /* Now we have a triangle to output, find the edge in common */
692 for (x=0; x < 4 ;x++)
696 if (last_quad[x] == *(temp2->pPolygon+y))
698 saved[z++] = last_quad[x];
701 /* This means that there was a non convex or
702 an overlapping polygon
713 printf("Z is not 2 %d \n",patch);
714 printf("4 %d %d %d %d %d %d %d\n",*(temp2->pPolygon),
715 *(temp2->pPolygon+1),*(temp2->pPolygon+2),*(temp2->pPolygon+3),
716 color1,color2,color3);
717 printf("%d %d %d %d\n",last_quad[0],last_quad[1],last_quad[2],last_quad[3]);
723 /* First one to output, there was no output edge */
725 x = Adjacent(saved[0],saved[1],last_quad,4);
726 y = Adjacent(saved[1],saved[0],last_quad,4);
728 /* Data might be mixed and we do not have textures for some of the vertices */
729 if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) || ((vt[saved[1]])==0)))
732 if ((!norms) && (!cptexture))
734 fprintf(output_file,"\nt %d %d %d ",x+1,y+1,saved[1]+1);
735 fprintf(output_file,"%d ",saved[0]+1);
737 else if ((norms) && (!cptexture))
739 fprintf(output_file,"\nt %d//%d %d//%d %d//%d ",x+1,vn[x] +1,
741 saved[1]+1,vn[saved[1]]+1);
742 fprintf(output_file,"%d//%d ",saved[0]+1,vn[saved[0]]+1);
744 else if ((cptexture) && (!norms))
746 fprintf(output_file,"\nt %d/%d %d/%d %d/%d ",x+1,vt[x] +1,
748 saved[1]+1,vt[saved[1]]+1);
749 fprintf(output_file,"%d//%d ",saved[0]+1,vt[saved[0]]+1);
753 fprintf(output_file,"\nt %d/%d/%d %d/%d/%d %d/%d/%d ",x+1,vt[x]+1,vn[x] +1,
754 y+1,vt[y]+1,vn[y] +1,
755 saved[1]+1,vt[saved[1]]+1,vn[saved[1]]+1);
756 fprintf(output_file,"%d/%d/%d ",saved[0]+1,vt[saved[0]]+1,vn[saved[0]]+1);
759 x = Adjacent(saved[0],saved[1],temp2->pPolygon,4);
760 y = Adjacent(saved[1],saved[0],temp2->pPolygon,4);
762 /* Data might be mixed and we do not have textures for some of the vertices */
763 if ((texture) && ( (vt[x] == 0) || (vt[y]==0)))
766 fprintf(output_file,"\nq ");
769 if ((!norms) && (!cptexture))
771 fprintf(output_file,"%d ",x+1);
772 fprintf(output_file,"%d ",y+1);
774 else if ((norms) && (!cptexture))
776 fprintf(output_file,"%d//%d ",x+1,vn[x]+1);
777 fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
779 else if ((cptexture) && (!norms))
781 fprintf(output_file,"%d/%d ",x+1,vt[x]+1);
782 fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
786 fprintf(output_file,"%d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
787 fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
796 x = Adjacent(output2,output1,temp2->pPolygon,4);
797 y = Adjacent(output1,output2,temp2->pPolygon,4);
798 /* Data might be mixed and we do not have textures for some of the vertices */
799 if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) ))
802 if ((!norms) && (!texture))
804 fprintf(output_file,"\nq %d ",x+1);
805 fprintf(output_file,"%d ",y+1);
807 else if ((norms) && (!texture))
809 fprintf(output_file,"\nq %d//%d ",x+1,vn[x]+1);
810 fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
812 else if ((texture) && (!norms))
814 fprintf(output_file,"\nq %d/%d ",x+1,vt[x]+1);
815 fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
819 fprintf(output_file,"\nq %d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
820 fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
827 last_quad[0] = *(temp2->pPolygon);
828 last_quad[1] = *(temp2->pPolygon+1);
829 last_quad[2] = *(temp2->pPolygon+2);
830 last_quad[3] = *(temp2->pPolygon+3);
834 void Fast_Reset(int x)
836 register int y,numverts;
837 register int front_walk, back_walk;
839 PF_FACES temp = NULL;
841 pListHead = PolFaces[x];
842 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
843 numverts = temp->nPolSize;
849 /* we are doing this only for quads */
852 /* for each face not seen yet, do North and South together
853 and East and West together
857 /* Check if the opposite sides were seen already */
858 /* Find walk for the first edge */
859 front_walk = Calculate_Walks(x,y,temp);
860 /* Find walk in the opposite direction */
861 back_walk = Calculate_Walks(x,y+2,temp);
862 /* Now put into the data structure the numbers that
865 Assign_Walk(x,temp,front_walk,y,back_walk);
866 Assign_Walk(x,temp,back_walk,y+2,front_walk);
873 void Reset_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
874 int last_left,FILE *output_file,int color1,int color2,int color3,
877 int previous_edge1,previous_edge2;
880 int f,t,nextvert,counter;
884 /* Reset walks on faces, since we just found a patch */
887 previous_edge1 = *(temp2->pPolygon + orientation+1);
888 previous_edge2 = *(temp2->pPolygon + orientation );
892 previous_edge1 = *(temp2->pPolygon + orientation );
893 previous_edge2 = *(temp2->pPolygon);
896 /* only if we are going left, otherwise there will be -1 there */
897 /*Find the adjacent face to this edge */
899 for (t = 0; t <=3 ; t++)
901 node = *(temp2->VertandId+t);
903 if (face_id == node->edge[1])
912 node = *(temp2->VertandId+orientation);
913 if (face_id == node->edge[1])
914 nextvert = node->edge[2];
916 nextvert = node->edge[1];
918 while ((last_left--) > 1)
922 Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
925 pListHead = PolFaces[nextvert];
926 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
927 if ((temp2->nPolSize != 4) && (temp2->nPolSize != 1))
929 /* There is more than 2 polygons on the edge, and we could have
932 if (nextvert != node->edge[1])
933 nextvert = node->edge[1];
935 nextvert = node->edge[2];
936 pListHead = PolFaces[nextvert];
937 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
938 node = *(temp2->VertandId+orientation);
944 for (t = 0; t <=3 ; t++)
946 node = *(temp2->VertandId+t);
948 if (face_id == node->edge[1])
961 while ((counter < 3) && (flag))
963 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
964 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
965 ((*(temp2->pPolygon+counter) == previous_edge2) ||
966 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
972 /* Get the IDs of the next edge */
975 previous_edge1 = *(temp2->pPolygon + counter+1);
976 previous_edge2 = *(temp2->pPolygon + counter);
980 previous_edge1 = *(temp2->pPolygon + counter);
981 previous_edge2 = *(temp2->pPolygon);
983 orientation = counter;
985 node = *(temp2->VertandId + counter);
986 if (node->edge[1] == nextvert)
987 nextvert = node->edge[2];
989 nextvert = node->edge[1];
1008 Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
1009 else if (nextvert != -1)
1010 Fast_Reset(nextvert);
1015 int Peel_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
1016 int last_left,FILE *output_file,int color1,int color2,int color3,
1017 BOOL start, int *swaps_added, int norms, int texture)
1019 int end1,end2,last_id,s=0,walk = 0;
1020 int previous_edge1,previous_edge2;
1021 static int last_seen = 1000;
1023 ListHead *pListHead;
1024 int nextvert,numverts,counter,dummy,tris=0;
1027 /* Peel the patch from the model.
1028 We will try and extend off the end of each strip in the patch. We will return the
1029 number of triangles completed by this extension only, and the number of swaps
1030 in the extension only.
1034 if (orientation !=3)
1036 previous_edge1 = *(temp2->pPolygon + orientation+1);
1037 previous_edge2 = *(temp2->pPolygon + orientation );
1041 previous_edge1 = *(temp2->pPolygon + orientation );
1042 previous_edge2 = *(temp2->pPolygon);
1046 walk = *(temp2->walked + orientation);
1048 /* only if we are going left, otherwise there will be -1 there */
1049 if ((start) && ((walk+1) < last_left))
1051 printf("There is an error in the left %d %d\n",walk,last_left);
1055 /* Find the adjacent face to this edge */
1056 node = *(temp2->VertandId+orientation);
1057 if (face_id == node->edge[1])
1058 nextvert = node->edge[2];
1060 nextvert = node->edge[1];
1061 temp2->seen = last_seen;
1064 while ((last_left--) > 1)
1067 tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1068 color1,color2,color3,FALSE,swaps_added,norms,texture);
1070 Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);
1073 pListHead = PolFaces[nextvert];
1074 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1075 numverts = temp2->nPolSize;
1077 if ((numverts != 4) || (temp2->seen == last_seen)
1078 || (nextvert == -1))
1081 /* There is more than 2 polygons on the edge, and we could have
1082 gotten the wrong one
1084 if (nextvert != node->edge[1])
1085 nextvert = node->edge[1];
1087 nextvert = node->edge[2];
1088 pListHead = PolFaces[nextvert];
1089 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1090 numverts = temp2->nPolSize;
1091 if ((numverts != 4) || (temp2->seen == last_seen) )
1093 printf("Peel 2 %d\n",numverts);
1099 temp2->seen = last_seen;
1103 while ((counter < 3) && (flag))
1105 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1106 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1107 ((*(temp2->pPolygon+counter) == previous_edge2) ||
1108 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1113 /* Get the IDs of the next edge */
1116 previous_edge1 = *(temp2->pPolygon + counter+1);
1117 previous_edge2 = *(temp2->pPolygon + counter);
1121 previous_edge1 = *(temp2->pPolygon + counter);
1122 previous_edge2 = *(temp2->pPolygon);
1124 orientation = counter;
1126 node = *(temp2->VertandId + counter);
1127 if (node->edge[1] == nextvert)
1128 nextvert = node->edge[2];
1130 nextvert = node->edge[1];
1149 tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1150 color1,color2,color3,FALSE,swaps_added,norms,texture);
1152 Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);/* do the last face */
1156 /* Get the edge that we came out on the last strip of the patch */
1157 Mark_Face(NULL,0,0,0,output_file,TRUE,&end1,&end2,&last_id,norms,texture);
1158 tris += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1159 *swaps_added = *swaps_added + s;
1165 void Find_Bands(int numfaces, FILE *output_file, int *swaps, int *bands,
1166 int *cost, int *tri, int norms, int *vert_norms, int texture, int *vert_texture)
1169 register int x,y,max1,max2,numverts,face_id,flag,maximum = 25;
1170 ListHead *pListHead;
1171 PF_FACES temp = NULL;
1172 int color1 = 0, color2 = 100, color3 = 255;
1174 int north_length1,last_north,left_length1,last_left,north_length2,left_length2;
1175 int total_tri = 0, total_swaps = 0,last_id;
1177 register int cutoff = 20;
1179 /* Code that will find the patches. "Cutoff" will be
1180 the cutoff of the area of the patches that we will be allowing. After
1181 we reach this cutoff length, then we will run the local algorithm on the
1185 /* For each faces that is left find the largest possible band that we can
1186 have with the remaining faces. Note that we will only be finding patches
1187 consisting of quads.
1195 while ((maximum >= cutoff))
1199 for (x=0; x<numfaces; x++)
1201 /* Used to produce the triangle strips */
1203 /* for each face, get the face */
1204 pListHead = PolFaces[x];
1205 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1206 numverts = temp->nPolSize;
1208 /* we are doing this only for quads */
1211 /* We want a face that is has not been used yet,
1212 since we know that that face must be part of
1213 a band. Then we will find the largest band that
1214 the face may be contained in
1217 /* Doing the north and the left */
1218 if ((*(temp->walked) != -1) && (*(temp->walked+3) != -1))
1219 max1 = Find_Max(temp,x,0,3,&north_length1,&left_length1);
1220 if ((*(temp->walked+1) != -1) && (*(temp->walked+2) != -1))
1221 max2 = Find_Max(temp,x,2,1,&north_length2,&left_length2);
1222 if ((max1 != (north_length1 * left_length1)) ||
1223 (max2 != (north_length2 * left_length2)))
1225 printf("Max1 %d, %d %d Max2 %d, %d %d\n",max1,north_length1,left_length1,max2,north_length2,left_length2);
1230 if ((max1 > max2) && (max1 > maximum))
1235 last_north = north_length1;
1236 last_left = left_length1;
1237 /* so we know we saved max1 */
1239 else if ((max2 > maximum) )
1244 last_north = north_length2;
1245 last_left = left_length2;
1246 /* so we know we saved max2 */
1250 if ((maximum < cutoff) && (*bands == 0))
1252 pListHead = PolFaces[face_id];
1253 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1254 /* There are no patches that we found in this pass */
1257 printf("The maximum is face %d area %d: lengths %d %d\n",face_id,maximum,last_north,last_left);
1261 if (last_north > last_left)
1263 larger = last_north;
1264 smaller = last_left;
1269 smaller = last_north;
1276 if (last_north > last_left) /* go north sequentially */
1278 total_tri += Peel_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1279 Reset_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE);
1285 total_tri += Peel_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1286 Reset_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE);
1292 /* Get the edge that we came out on the last strip of the patch */
1293 Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1294 total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1300 if (last_north > last_left)
1302 total_tri += Peel_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1303 Reset_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE);
1309 total_tri += Peel_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1310 Reset_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE);
1315 /* Get the edge that we came out on on the patch */
1316 Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1317 total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1321 /* Now compute the cost of transmitting this band, is equal to
1322 going across the larger portion sequentially,
1323 and swapping 3 times per other dimension
1326 total_tri += (maximum * 2);
1327 *bands = *bands + smaller;
1330 printf("We transmitted %d triangles,using %d swaps and %d strips\n",total_tri,total_swaps, *bands);
1331 printf("COST %d\n",total_tri + total_swaps + *bands + *bands);
1333 *cost = total_tri + total_swaps + *bands + *bands;
1335 added_quad = added_quad * 4;
1336 *swaps = total_swaps;
1340 void Save_Rest(int *numfaces)
1342 /* Put the polygons that are left into a data structure so that we can run the
1343 stripping code on it.
1345 register int x,y=0,numverts;
1346 ListHead *pListHead;
1349 for (x=0; x<*numfaces; x++)
1351 /* for each face, get the face */
1352 pListHead = PolFaces[x];
1353 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1354 numverts = temp->nPolSize;
1355 /* If we did not do the face before add it to data structure with new
1360 CopyFace(temp->pPolygon,numverts,y+1,temp->pNorms);
1363 /* Used it, so remove it */
1365 RemoveList(pListHead,(PLISTINFO) temp);
1371 void Assign_Walk(int lastvert,PF_FACES temp2, int front_walk,int y,
1374 /* Go back and do the walk again, but this time save the lengths inside
1376 y was the starting edge number for the front_walk length
1377 back_walk is the length of the walk along the opposite edge
1379 int previous_edge1, previous_edge2;
1380 register int walk = 0,nextvert,numverts,counter;
1383 ListHead *pListHead;
1384 static int seen = 0;
1385 static BOOL first = TRUE;
1386 BOOL wrap = FALSE, set = FALSE;
1388 /* In the "Fast_Reset" resetting will be true */
1389 if ((resetting) && (first))
1396 /* Had a band who could be a cycle */
1397 if (front_walk == back_walk)
1400 /* Find the edge that we are currently on */
1403 previous_edge1 = *(temp2->pPolygon +y);
1404 previous_edge2 = *(temp2->pPolygon + y + 1);
1408 previous_edge1 = *(temp2->pPolygon +y);
1409 previous_edge2 = *(temp2->pPolygon);
1412 /* Assign the lengths */
1415 *(temp2->walked+y) = front_walk--;
1416 *(temp2->walked+y+2) = back_walk++;
1420 *(temp2->walked+y) = front_walk--;
1421 *(temp2->walked+y-2) = back_walk++;
1424 /*Find the adjacent face to this edge */
1425 node = *(temp2->VertandId+y);
1427 if (node->edge[2] != lastvert)
1428 nextvert = node->edge[2];
1430 nextvert = node->edge[1];
1432 temp2->seen3 = seen;
1434 /* Keep walking in this direction until we cannot do so */
1435 while ((nextvert != lastvert) && (nextvert != -1) && (front_walk >= 0))
1438 pListHead = PolFaces[nextvert];
1440 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1441 numverts = temp2->nPolSize;
1442 if ((numverts != 4))
1445 /* Don't include this face in the walk */
1450 /* Find edge that is not adjacent to the previous one */
1453 while ((counter < 3) && (flag))
1455 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1456 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1457 ((*(temp2->pPolygon+counter) == previous_edge2) ||
1458 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1463 /* Get the IDs of the next edge */
1466 previous_edge1 = *(temp2->pPolygon + counter);
1467 previous_edge2 = *(temp2->pPolygon + counter + 1);
1471 previous_edge1 = *(temp2->pPolygon + counter);
1472 previous_edge2 = *(temp2->pPolygon);
1476 /* Put in the walk lengths */
1479 if (((*(temp2->walked + counter) >= 0)
1480 || (*(temp2->walked +counter + 2) >= 0)))
1482 if ((resetting == FALSE) && ((temp2->seen3) != (seen-1)))
1484 /* If there are more than 2 polygons adjacent
1485 to an edge then we can be trying to assign more than
1486 once. We will save the smaller one
1488 temp2->seen3 = seen;
1489 if ( (*(temp2->walked+counter) <= front_walk) &&
1490 (*(temp2->walked+counter+2) <= back_walk) )
1492 if (*(temp2->walked+counter) > front_walk)
1493 *(temp2->walked+counter) = front_walk--;
1496 if (*(temp2->walked+counter+2) > back_walk)
1497 *(temp2->walked+counter+2) = back_walk++;
1501 else if (resetting == FALSE)
1503 /* if there was a cycle then all lengths are the same */
1507 temp2->seen3 = seen;
1508 *(temp2->walked+counter) = front_walk--;
1509 *(temp2->walked+counter+2) = back_walk++;
1511 else if (((temp2->seen3 == (seen-1))
1512 && (wrap) && (walk == 1)) || (set))
1514 /* if there was a cycle then all lengths are the same */
1519 temp2->seen3 = seen;
1520 *(temp2->walked+counter) = front_walk--;
1521 *(temp2->walked+counter+2) = back_walk++;
1525 temp2->seen3 = seen;
1526 *(temp2->walked+counter) = front_walk--;
1527 *(temp2->walked+counter+2) = back_walk++;
1532 temp2->seen3 = seen;
1533 *(temp2->walked+counter) = front_walk--;
1534 *(temp2->walked+counter+2) = back_walk++;
1540 if (((*(temp2->walked + counter) >= 0 )
1541 || (*(temp2->walked +counter - 2) >= 0)) )
1543 if ((temp2->seen3 != (seen-1)) && (resetting == FALSE))
1545 /* If there are more than 2 polygons adjacent
1546 to an edge then we can be trying to assign more than
1547 once. We will save the smaller one
1549 temp2->seen3 = seen;
1550 if ( (*(temp2->walked+counter) <= front_walk) &&
1551 (*(temp2->walked+counter-2) <= back_walk) )
1553 if (*(temp2->walked+counter) > front_walk)
1554 *(temp2->walked+counter) = front_walk--;
1557 if (*(temp2->walked+counter-2) > back_walk)
1558 *(temp2->walked+counter-2) = back_walk++;
1562 else if (resetting == FALSE)
1567 temp2->seen3 = seen;
1568 *(temp2->walked+counter) = front_walk--;
1569 *(temp2->walked+counter-2) = back_walk++;
1571 else if (((temp2->seen3 == (seen-1)) && (walk == 1) && (wrap))
1574 /* if there was a cycle then all lengths are the same */
1579 temp2->seen3 = seen;
1580 *(temp2->walked+counter) = front_walk--;
1581 *(temp2->walked+counter-2) = back_walk++;
1585 temp2->seen3 = seen;
1586 *(temp2->walked+counter) = front_walk--;
1587 *(temp2->walked+counter-2) = back_walk++;
1592 temp2->seen3 = seen;
1593 *(temp2->walked+counter) = front_walk--;
1594 *(temp2->walked+counter-2) = back_walk++;
1600 node = *(temp2->VertandId + counter);
1601 if (node->edge[1] == nextvert)
1602 nextvert = node->edge[2];
1604 nextvert = node->edge[1];
1613 void Save_Walks(int numfaces)
1616 int front_walk, back_walk;
1617 ListHead *pListHead;
1618 PF_FACES temp = NULL;
1620 for (x=0; x<numfaces; x++)
1622 /* for each face, get the face */
1623 pListHead = PolFaces[x];
1624 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1625 numverts = temp->nPolSize;
1629 /* we are finding patches only for quads */
1632 /* for each face not seen yet, do North and South together
1633 and East and West together
1637 /* Check if the opposite sides were seen already from another
1638 starting face, if they were then there is no need to do the walk again
1641 if ( ((*(temp->walked+y) == -1) &&
1642 (*(temp->walked+y+2) == -1) ))
1644 /* Find walk for the first edge */
1645 front_walk = Calculate_Walks(x,y,temp);
1646 /* Find walk in the opposite direction */
1647 back_walk = Calculate_Walks(x,y+2,temp);
1648 /* Now put into the data structure the numbers that
1651 Assign_Walk(x,temp,front_walk,y,back_walk);
1652 Assign_Walk(x,temp,back_walk,y+2,front_walk);