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 t,smallest_so_far,nextvert,max=-1;
467 *lastminup = MAX_BAND;
472 previous_edge1 = *(temp2->pPolygon + left);
473 previous_edge2 = *(temp2->pPolygon);
478 previous_edge1 = *(temp2->pPolygon + left + 1);
479 previous_edge2 = *(temp2->pPolygon + left);
482 temp2->seen = last_seen;
483 walk = *(temp2->walked + left);
485 for (x=1;x<=(walk+1); x++)
487 /* test to see if we have a true band
488 that is, are they adjacent to each other
491 minup = *(temp2->walked + north) + 1;
493 /* if we are at the very first face, then we do not
494 have to check the adjacent faces going up
495 and our north distance is the distance of this face's
501 minup = Test_Adj(temp2,x,north,*lastminup,lastvert,last_seen);
503 smallest_so_far = minup;
507 /* find the largest band that we can have */
508 if (minup < (*lastminup))
510 /* see if we really can go up all the way
511 temp should by less than our equal to minup
512 if it is less, then one of the faces was not
513 adjacent to those next to it and the band height
516 temp = Test_Adj(temp2,x,north,minup,lastvert,last_seen);
519 printf("There is an error in the test adj\n");
523 band_value = x * minup;
524 if (minup < smallest_so_far)
526 if (band_value > max)
528 smallest_so_far = minup;
534 smallest_so_far = minup;
538 band_value = x * smallest_so_far;
539 if (band_value > max)
541 *lastminup = smallest_so_far;
551 temp = Test_Adj(temp2,x,north,smallest_so_far,lastvert,last_seen);
552 if (temp > smallest_so_far)
554 printf("There is an error in the test adj\n");
557 smallest_so_far = temp;
559 band_value = x * smallest_so_far;
560 if (band_value > max)
562 *lastminup = smallest_so_far;
567 if ( x != (walk + 1))
569 node = *(temp2->VertandId+left);
570 if (lastvert == node->edge[1])
571 nextvert = node->edge[2];
573 nextvert = node->edge[1];
580 pListHead = PolFaces[nextvert];
581 temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
583 /* if we have visited this face before, then there is an error */
584 if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
585 (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
586 || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
589 if (lastvert == node->edge[1])
590 nextvert = node->edge[2];
592 nextvert = node->edge[1];
596 /* Last attempt to get the face ... */
597 pListHead = PolFaces[nextvert];
598 temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
599 if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
600 (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
601 || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
602 return max; /* The polygon was not saved with the edge, not
603 enough room. We will get the walk when we come
604 to that polygon later.
611 temp2->seen = last_seen;
613 while ((counter < 3) && (flag))
616 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
617 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
618 ((*(temp2->pPolygon+counter) == previous_edge2) ||
619 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
626 /* Get the IDs of the next edge */
633 previous_edge1 = *(temp2->pPolygon + counter + 1);
634 previous_edge2 = *(temp2->pPolygon + counter);
638 previous_edge1 = *(temp2->pPolygon + counter);
639 previous_edge2 = *(temp2->pPolygon);
649 void Mark_Face(PF_FACES temp2, int color1, int color2,
650 int color3, FILE *output_file, BOOL end, int *edge1, int *edge2,
651 int *face_id, int norms, int texture)
653 static int last_quad[4];
654 register int x,y,z=0;
656 static int output1, output2,last_id;
659 /* Are we done with the patch? If so return the last edge that
660 we will come out on, and that will be the edge that we will
661 start to extend upon.
674 *(temp2->walked) = -1;
675 *(temp2->walked+1) = -1;
676 *(temp2->walked+2) = -1;
677 *(temp2->walked+3) = -1;
683 /* At the first quad in the strip -- save it */
684 last_quad[0] = *(temp2->pPolygon);
685 last_quad[1] = *(temp2->pPolygon+1);
686 last_quad[2] = *(temp2->pPolygon+2);
687 last_quad[3] = *(temp2->pPolygon+3);
692 /* Now we have a triangle to output, find the edge in common */
693 for (x=0; x < 4 ;x++)
697 if (last_quad[x] == *(temp2->pPolygon+y))
699 saved[z++] = last_quad[x];
702 /* This means that there was a non convex or
703 an overlapping polygon
714 printf("Z is not 2 %d \n",patch);
715 printf("4 %d %d %d %d %d %d %d\n",*(temp2->pPolygon),
716 *(temp2->pPolygon+1),*(temp2->pPolygon+2),*(temp2->pPolygon+3),
717 color1,color2,color3);
718 printf("%d %d %d %d\n",last_quad[0],last_quad[1],last_quad[2],last_quad[3]);
724 /* First one to output, there was no output edge */
726 x = Adjacent(saved[0],saved[1],last_quad,4);
727 y = Adjacent(saved[1],saved[0],last_quad,4);
729 /* Data might be mixed and we do not have textures for some of the vertices */
730 if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) || ((vt[saved[1]])==0)))
733 if ((!norms) && (!cptexture))
735 fprintf(output_file,"\nt %d %d %d ",x+1,y+1,saved[1]+1);
736 fprintf(output_file,"%d ",saved[0]+1);
738 else if ((norms) && (!cptexture))
740 fprintf(output_file,"\nt %d//%d %d//%d %d//%d ",x+1,vn[x] +1,
742 saved[1]+1,vn[saved[1]]+1);
743 fprintf(output_file,"%d//%d ",saved[0]+1,vn[saved[0]]+1);
745 else if ((cptexture) && (!norms))
747 fprintf(output_file,"\nt %d/%d %d/%d %d/%d ",x+1,vt[x] +1,
749 saved[1]+1,vt[saved[1]]+1);
750 fprintf(output_file,"%d//%d ",saved[0]+1,vt[saved[0]]+1);
754 fprintf(output_file,"\nt %d/%d/%d %d/%d/%d %d/%d/%d ",x+1,vt[x]+1,vn[x] +1,
755 y+1,vt[y]+1,vn[y] +1,
756 saved[1]+1,vt[saved[1]]+1,vn[saved[1]]+1);
757 fprintf(output_file,"%d/%d/%d ",saved[0]+1,vt[saved[0]]+1,vn[saved[0]]+1);
760 x = Adjacent(saved[0],saved[1],temp2->pPolygon,4);
761 y = Adjacent(saved[1],saved[0],temp2->pPolygon,4);
763 /* Data might be mixed and we do not have textures for some of the vertices */
764 if ((texture) && ( (vt[x] == 0) || (vt[y]==0)))
767 fprintf(output_file,"\nq ");
770 if ((!norms) && (!cptexture))
772 fprintf(output_file,"%d ",x+1);
773 fprintf(output_file,"%d ",y+1);
775 else if ((norms) && (!cptexture))
777 fprintf(output_file,"%d//%d ",x+1,vn[x]+1);
778 fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
780 else if ((cptexture) && (!norms))
782 fprintf(output_file,"%d/%d ",x+1,vt[x]+1);
783 fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
787 fprintf(output_file,"%d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
788 fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
797 x = Adjacent(output2,output1,temp2->pPolygon,4);
798 y = Adjacent(output1,output2,temp2->pPolygon,4);
799 /* Data might be mixed and we do not have textures for some of the vertices */
800 if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) ))
803 if ((!norms) && (!texture))
805 fprintf(output_file,"\nq %d ",x+1);
806 fprintf(output_file,"%d ",y+1);
808 else if ((norms) && (!texture))
810 fprintf(output_file,"\nq %d//%d ",x+1,vn[x]+1);
811 fprintf(output_file,"%d//%d ",y+1,vn[y]+1);
813 else if ((texture) && (!norms))
815 fprintf(output_file,"\nq %d/%d ",x+1,vt[x]+1);
816 fprintf(output_file,"%d/%d ",y+1,vt[y]+1);
820 fprintf(output_file,"\nq %d/%d/%d ",x+1,vt[x]+1,vn[x]+1);
821 fprintf(output_file,"%d/%d/%d ",y+1,vt[y]+1,vn[y]+1);
828 last_quad[0] = *(temp2->pPolygon);
829 last_quad[1] = *(temp2->pPolygon+1);
830 last_quad[2] = *(temp2->pPolygon+2);
831 last_quad[3] = *(temp2->pPolygon+3);
835 void Fast_Reset(int x)
837 register int y,numverts;
838 register int front_walk, back_walk;
840 PF_FACES temp = NULL;
842 pListHead = PolFaces[x];
843 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
844 numverts = temp->nPolSize;
850 /* we are doing this only for quads */
853 /* for each face not seen yet, do North and South together
854 and East and West together
858 /* Check if the opposite sides were seen already */
859 /* Find walk for the first edge */
860 front_walk = Calculate_Walks(x,y,temp);
861 /* Find walk in the opposite direction */
862 back_walk = Calculate_Walks(x,y+2,temp);
863 /* Now put into the data structure the numbers that
866 Assign_Walk(x,temp,front_walk,y,back_walk);
867 Assign_Walk(x,temp,back_walk,y+2,front_walk);
874 void Reset_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
875 int last_left,FILE *output_file,int color1,int color2,int color3,
878 register int walk = 0,count = 0;
879 int previous_edge1,previous_edge2;
880 int static last_seen = 1000;
883 int f,t,nextvert,counter;
887 /* Reset walks on faces, since we just found a patch */
890 previous_edge1 = *(temp2->pPolygon + orientation+1);
891 previous_edge2 = *(temp2->pPolygon + orientation );
895 previous_edge1 = *(temp2->pPolygon + orientation );
896 previous_edge2 = *(temp2->pPolygon);
899 /* only if we are going left, otherwise there will be -1 there */
900 /*Find the adjacent face to this edge */
902 for (t = 0; t <=3 ; t++)
904 node = *(temp2->VertandId+t);
906 if (face_id == node->edge[1])
915 node = *(temp2->VertandId+orientation);
916 if (face_id == node->edge[1])
917 nextvert = node->edge[2];
919 nextvert = node->edge[1];
921 while ((last_left--) > 1)
925 Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
928 pListHead = PolFaces[nextvert];
929 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
930 if ((temp2->nPolSize != 4) && (temp2->nPolSize != 1))
932 /* There is more than 2 polygons on the edge, and we could have
935 if (nextvert != node->edge[1])
936 nextvert = node->edge[1];
938 nextvert = node->edge[2];
939 pListHead = PolFaces[nextvert];
940 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
941 node = *(temp2->VertandId+orientation);
947 for (t = 0; t <=3 ; t++)
949 node = *(temp2->VertandId+t);
951 if (face_id == node->edge[1])
964 while ((counter < 3) && (flag))
966 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
967 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
968 ((*(temp2->pPolygon+counter) == previous_edge2) ||
969 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
975 /* Get the IDs of the next edge */
978 previous_edge1 = *(temp2->pPolygon + counter+1);
979 previous_edge2 = *(temp2->pPolygon + counter);
983 previous_edge1 = *(temp2->pPolygon + counter);
984 previous_edge2 = *(temp2->pPolygon);
986 orientation = counter;
988 node = *(temp2->VertandId + counter);
989 if (node->edge[1] == nextvert)
990 nextvert = node->edge[2];
992 nextvert = node->edge[1];
1011 Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,color1,color2,color3,FALSE);
1012 else if (nextvert != -1)
1013 Fast_Reset(nextvert);
1018 int Peel_Max(PF_FACES temp2,int face_id,int north,int last_north, int orientation,
1019 int last_left,FILE *output_file,int color1,int color2,int color3,
1020 BOOL start, int *swaps_added, int norms, int texture)
1022 int end1,end2,last_id,s=0,walk = 0,count = 0;
1023 int previous_edge1,previous_edge2;
1024 int static last_seen = 1000;
1026 ListHead *pListHead;
1027 int nextvert,numverts,counter,dummy,tris=0;
1030 /* Peel the patch from the model.
1031 We will try and extend off the end of each strip in the patch. We will return the
1032 number of triangles completed by this extension only, and the number of swaps
1033 in the extension only.
1037 if (orientation !=3)
1039 previous_edge1 = *(temp2->pPolygon + orientation+1);
1040 previous_edge2 = *(temp2->pPolygon + orientation );
1044 previous_edge1 = *(temp2->pPolygon + orientation );
1045 previous_edge2 = *(temp2->pPolygon);
1049 walk = *(temp2->walked + orientation);
1051 /* only if we are going left, otherwise there will be -1 there */
1052 if ((start) && ((walk+1) < last_left))
1054 printf("There is an error in the left %d %d\n",walk,last_left);
1058 /* Find the adjacent face to this edge */
1059 node = *(temp2->VertandId+orientation);
1060 if (face_id == node->edge[1])
1061 nextvert = node->edge[2];
1063 nextvert = node->edge[1];
1064 temp2->seen = last_seen;
1067 while ((last_left--) > 1)
1070 tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1071 color1,color2,color3,FALSE,swaps_added,norms,texture);
1073 Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);
1076 pListHead = PolFaces[nextvert];
1077 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1078 numverts = temp2->nPolSize;
1080 if ((numverts != 4) || (temp2->seen == last_seen)
1081 || (nextvert == -1))
1084 /* There is more than 2 polygons on the edge, and we could have
1085 gotten the wrong one
1087 if (nextvert != node->edge[1])
1088 nextvert = node->edge[1];
1090 nextvert = node->edge[2];
1091 pListHead = PolFaces[nextvert];
1092 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1093 numverts = temp2->nPolSize;
1094 if ((numverts != 4) || (temp2->seen == last_seen) )
1096 printf("Peel 2 %d\n",numverts);
1102 temp2->seen = last_seen;
1106 while ((counter < 3) && (flag))
1108 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1109 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1110 ((*(temp2->pPolygon+counter) == previous_edge2) ||
1111 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1116 /* Get the IDs of the next edge */
1119 previous_edge1 = *(temp2->pPolygon + counter+1);
1120 previous_edge2 = *(temp2->pPolygon + counter);
1124 previous_edge1 = *(temp2->pPolygon + counter);
1125 previous_edge2 = *(temp2->pPolygon);
1127 orientation = counter;
1129 node = *(temp2->VertandId + counter);
1130 if (node->edge[1] == nextvert)
1131 nextvert = node->edge[2];
1133 nextvert = node->edge[1];
1152 tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
1153 color1,color2,color3,FALSE,swaps_added,norms,texture);
1155 Mark_Face(temp2,color1,color2,color3,output_file,FALSE,&dummy,&dummy,&face_id,norms,texture);/* do the last face */
1159 /* Get the edge that we came out on the last strip of the patch */
1160 Mark_Face(NULL,0,0,0,output_file,TRUE,&end1,&end2,&last_id,norms,texture);
1161 tris += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1162 *swaps_added = *swaps_added + s;
1168 void Find_Bands(int numfaces, FILE *output_file, int *swaps, int *bands,
1169 int *cost, int *tri, int norms, int *vert_norms, int texture, int *vert_texture)
1172 register int x,y,max1,max2,numverts,face_id,flag,maximum = 25;
1173 ListHead *pListHead;
1174 PF_FACES temp = NULL;
1175 int color1 = 0, color2 = 100, color3 = 255;
1176 int color = 0,larger,smaller;
1177 int north_length1,last_north,left_length1,last_left,north_length2,left_length2;
1178 int total_tri = 0, total_swaps = 0,last_id;
1180 register int cutoff = 20;
1182 /* Code that will find the patches. "Cutoff" will be
1183 the cutoff of the area of the patches that we will be allowing. After
1184 we reach this cutoff length, then we will run the local algorithm on the
1188 /* For each faces that is left find the largest possible band that we can
1189 have with the remaining faces. Note that we will only be finding patches
1190 consisting of quads.
1198 while ((maximum >= cutoff))
1202 for (x=0; x<numfaces; x++)
1205 /* Used to produce the triangle strips */
1207 /* for each face, get the face */
1208 pListHead = PolFaces[x];
1209 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1210 numverts = temp->nPolSize;
1212 /* we are doing this only for quads */
1215 /* We want a face that is has not been used yet,
1216 since we know that that face must be part of
1217 a band. Then we will find the largest band that
1218 the face may be contained in
1221 /* Doing the north and the left */
1222 if ((*(temp->walked) != -1) && (*(temp->walked+3) != -1))
1223 max1 = Find_Max(temp,x,0,3,&north_length1,&left_length1);
1224 if ((*(temp->walked+1) != -1) && (*(temp->walked+2) != -1))
1225 max2 = Find_Max(temp,x,2,1,&north_length2,&left_length2);
1226 if ((max1 != (north_length1 * left_length1)) ||
1227 (max2 != (north_length2 * left_length2)))
1229 printf("Max1 %d, %d %d Max2 %d, %d %d\n",max1,north_length1,left_length1,max2,north_length2,left_length2);
1234 if ((max1 > max2) && (max1 > maximum))
1239 last_north = north_length1;
1240 last_left = left_length1;
1241 /* so we know we saved max1 */
1243 else if ((max2 > maximum) )
1248 last_north = north_length2;
1249 last_left = left_length2;
1250 /* so we know we saved max2 */
1254 if ((maximum < cutoff) && (*bands == 0))
1256 pListHead = PolFaces[face_id];
1257 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1258 /* There are no patches that we found in this pass */
1261 /*printf("The maximum is face %d area %d: lengths %d %d\n",face_id,maximum,last_north,last_left);*/
1263 if (last_north > last_left)
1265 larger = last_north;
1266 smaller = last_left;
1271 smaller = last_north;
1278 if (last_north > last_left) /* go north sequentially */
1280 total_tri += Peel_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1281 Reset_Max(temp,face_id,0,last_north,3,last_left,output_file,color1,color2,color3,TRUE);
1287 total_tri += Peel_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1288 Reset_Max(temp,face_id,3,last_left,0,last_north,output_file,color1,color2,color3,TRUE);
1294 /* Get the edge that we came out on the last strip of the patch */
1295 Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1296 total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1302 if (last_north > last_left)
1304 total_tri += Peel_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1305 Reset_Max(temp,face_id,2,last_north,1,last_left,output_file,color1,color2,color3,TRUE);
1311 total_tri += Peel_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE,&s,norms,texture);
1312 Reset_Max(temp,face_id,1,last_left,2,last_north,output_file,color1,color2,color3,TRUE);
1317 /* Get the edge that we came out on on the patch */
1318 Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
1319 total_tri += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,vn,norms,vt,texture);
1323 /* Now compute the cost of transmitting this band, is equal to
1324 going across the larger portion sequentially,
1325 and swapping 3 times per other dimension
1328 total_tri += (maximum * 2);
1329 *bands = *bands + smaller;
1333 /*printf("We transmitted %d triangles,using %d swaps and %d strips\n",total_tri,
1334 total_swaps, *bands);
1335 printf("COST %d\n",total_tri + total_swaps + *bands + *bands);*/
1336 *cost = total_tri + total_swaps + *bands + *bands;
1338 added_quad = added_quad * 4;
1339 *swaps = total_swaps;
1343 void Save_Rest(int *numfaces)
1345 /* Put the polygons that are left into a data structure so that we can run the
1346 stripping code on it.
1348 register int x,y=0,numverts;
1349 ListHead *pListHead;
1352 for (x=0; x<*numfaces; x++)
1354 /* for each face, get the face */
1355 pListHead = PolFaces[x];
1356 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1357 numverts = temp->nPolSize;
1358 /* If we did not do the face before add it to data structure with new
1363 CopyFace(temp->pPolygon,numverts,y+1,temp->pNorms);
1366 /* Used it, so remove it */
1368 RemoveList(pListHead,(PLISTINFO) temp);
1374 void Assign_Walk(int lastvert,PF_FACES temp2, int front_walk,int y,
1377 /* Go back and do the walk again, but this time save the lengths inside
1379 y was the starting edge number for the front_walk length
1380 back_walk is the length of the walk along the opposite edge
1382 int previous_edge1, previous_edge2;
1383 register int walk = 0,nextvert,numverts,counter;
1386 ListHead *pListHead;
1387 register int total_walk, start_back_walk;
1388 static int seen = 0;
1389 static BOOL first = TRUE;
1391 BOOL f = TRUE, wrap = FALSE, set = FALSE;
1394 /* In the "Fast_Reset" resetting will be true */
1395 if ((resetting) && (first))
1402 total_walk = front_walk + back_walk;
1403 start_back_walk = back_walk;
1404 /* Had a band who could be a cycle */
1405 if (front_walk == back_walk)
1408 /* Find the edge that we are currently on */
1411 previous_edge1 = *(temp2->pPolygon +y);
1412 previous_edge2 = *(temp2->pPolygon + y + 1);
1416 previous_edge1 = *(temp2->pPolygon +y);
1417 previous_edge2 = *(temp2->pPolygon);
1420 /* Assign the lengths */
1423 *(temp2->walked+y) = front_walk--;
1424 *(temp2->walked+y+2) = back_walk++;
1428 *(temp2->walked+y) = front_walk--;
1429 *(temp2->walked+y-2) = back_walk++;
1432 /*Find the adjacent face to this edge */
1433 node = *(temp2->VertandId+y);
1435 if (node->edge[2] != lastvert)
1436 nextvert = node->edge[2];
1438 nextvert = node->edge[1];
1440 temp2->seen3 = seen;
1442 /* Keep walking in this direction until we cannot do so */
1443 while ((nextvert != lastvert) && (nextvert != -1) && (front_walk >= 0))
1446 pListHead = PolFaces[nextvert];
1448 temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1449 numverts = temp2->nPolSize;
1450 if ((numverts != 4))
1453 /* Don't include this face in the walk */
1458 /* Find edge that is not adjacent to the previous one */
1461 while ((counter < 3) && (flag))
1463 if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
1464 (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
1465 ((*(temp2->pPolygon+counter) == previous_edge2) ||
1466 (*(temp2->pPolygon+counter+1) == previous_edge1)) )
1471 /* Get the IDs of the next edge */
1474 previous_edge1 = *(temp2->pPolygon + counter);
1475 previous_edge2 = *(temp2->pPolygon + counter + 1);
1479 previous_edge1 = *(temp2->pPolygon + counter);
1480 previous_edge2 = *(temp2->pPolygon);
1484 /* Put in the walk lengths */
1487 if (((*(temp2->walked + counter) >= 0)
1488 || (*(temp2->walked +counter + 2) >= 0)))
1490 if ((resetting == FALSE) && ((temp2->seen3) != (seen-1)))
1492 /* If there are more than 2 polygons adjacent
1493 to an edge then we can be trying to assign more than
1494 once. We will save the smaller one
1496 temp2->seen3 = seen;
1497 if ( (*(temp2->walked+counter) <= front_walk) &&
1498 (*(temp2->walked+counter+2) <= back_walk) )
1500 if (*(temp2->walked+counter) > front_walk)
1501 *(temp2->walked+counter) = front_walk--;
1504 if (*(temp2->walked+counter+2) > back_walk)
1505 *(temp2->walked+counter+2) = back_walk++;
1509 else if (resetting == FALSE)
1511 /* if there was a cycle then all lengths are the same */
1515 temp2->seen3 = seen;
1516 *(temp2->walked+counter) = front_walk--;
1517 *(temp2->walked+counter+2) = back_walk++;
1519 else if (((temp2->seen3 == (seen-1))
1520 && (wrap) && (walk == 1)) || (set))
1522 /* if there was a cycle then all lengths are the same */
1527 temp2->seen3 = seen;
1528 *(temp2->walked+counter) = front_walk--;
1529 *(temp2->walked+counter+2) = back_walk++;
1533 temp2->seen3 = seen;
1534 *(temp2->walked+counter) = front_walk--;
1535 *(temp2->walked+counter+2) = back_walk++;
1540 temp2->seen3 = seen;
1541 *(temp2->walked+counter) = front_walk--;
1542 *(temp2->walked+counter+2) = back_walk++;
1548 if (((*(temp2->walked + counter) >= 0 )
1549 || (*(temp2->walked +counter - 2) >= 0)) )
1551 if ((temp2->seen3 != (seen-1)) && (resetting == FALSE))
1553 /* If there are more than 2 polygons adjacent
1554 to an edge then we can be trying to assign more than
1555 once. We will save the smaller one
1557 temp2->seen3 = seen;
1558 if ( (*(temp2->walked+counter) <= front_walk) &&
1559 (*(temp2->walked+counter-2) <= back_walk) )
1561 if (*(temp2->walked+counter) > front_walk)
1562 *(temp2->walked+counter) = front_walk--;
1565 if (*(temp2->walked+counter-2) > back_walk)
1566 *(temp2->walked+counter-2) = back_walk++;
1570 else if (resetting == FALSE)
1575 temp2->seen3 = seen;
1576 *(temp2->walked+counter) = front_walk--;
1577 *(temp2->walked+counter-2) = back_walk++;
1579 else if (((temp2->seen3 == (seen-1)) && (walk == 1) && (wrap))
1582 /* if there was a cycle then all lengths are the same */
1587 temp2->seen3 = seen;
1588 *(temp2->walked+counter) = front_walk--;
1589 *(temp2->walked+counter-2) = back_walk++;
1593 temp2->seen3 = seen;
1594 *(temp2->walked+counter) = front_walk--;
1595 *(temp2->walked+counter-2) = back_walk++;
1600 temp2->seen3 = seen;
1601 *(temp2->walked+counter) = front_walk--;
1602 *(temp2->walked+counter-2) = back_walk++;
1608 node = *(temp2->VertandId + counter);
1609 if (node->edge[1] == nextvert)
1610 nextvert = node->edge[2];
1612 nextvert = node->edge[1];
1621 void Save_Walks(int numfaces)
1624 int front_walk, back_walk;
1625 ListHead *pListHead;
1626 PF_FACES temp = NULL;
1628 for (x=0; x<numfaces; x++)
1630 /* for each face, get the face */
1631 pListHead = PolFaces[x];
1632 temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
1633 numverts = temp->nPolSize;
1637 /* we are finding patches only for quads */
1640 /* for each face not seen yet, do North and South together
1641 and East and West together
1645 /* Check if the opposite sides were seen already from another
1646 starting face, if they were then there is no need to do the walk again
1649 if ( ((*(temp->walked+y) == -1) &&
1650 (*(temp->walked+y+2) == -1) ))
1652 /* Find walk for the first edge */
1653 front_walk = Calculate_Walks(x,y,temp);
1654 /* Find walk in the opposite direction */
1655 back_walk = Calculate_Walks(x,y+2,temp);
1656 /* Now put into the data structure the numbers that
1659 Assign_Walk(x,temp,front_walk,y,back_walk);
1660 Assign_Walk(x,temp,back_walk,y+2,front_walk);