Stripe_u/ties.c

   1 /********************************************************************/
   2 /*   STRIPE: converting a polygonal model to triangle strips
   3      Francine Evans, 1996.
   4      SUNY @ Stony Brook
   5      Advisors: Steven Skiena and Amitabh Varshney
   6 */
   7 /********************************************************************/
   8
   9 /*---------------------------------------------------------------------*/
  10 /*      STRIPE: ties.c
  11      This file will contain all the routines used to determine the next face if there
  12         is a tie
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16 #include <stdlib.h>
  17 #include "polverts.h"
  18 #include "ties.h"
  19 #include "sturctsex.h"
  20 #include "triangulatex.h"
  21 #include "options.h"
  22 #include "common.h"
  23 #include "util.h"
  24
  25 #define MAX_TIE 60
  26 int ties_array[60];
  27 int last = 0;
  28
  29 void Clear_Ties()
  30 {
  31         /*      Clear the buffer, because we do not have the tie
  32                 any more that we had before */
  33         last = 0;
  34 }
  35
  36 void Add_Ties(int id)
  37 {
  38         /*      We have a tie to add to the buffer */
  39         ties_array[last++] = id;
  40 }
  41
  42 int Alternate_Tie()
  43 {
  44         /*      Alternate in what we choose to break the tie
  45                 We are just alternating between the first and
  46                 second thing that we found
  47         */
  48         static int x = 0;
  49         register int t;
  50
  51         t = ties_array[x];
  52         x++;
  53         if (x == 2)
  54                 x = 0;
  55         return t;
  56 }
  57
  58 int Random_Tie()
  59 {
  60         /*      Randomly choose the next face with which
  61                 to break the tie
  62         */
  63         register int num;
  64
  65         num = rand();
  66         while (num >= last)
  67                 num = num/20;
  68         return (ties_array[num]);
  69 }
  70
  71 int Look_Ahead(int id)
  72 {
  73         /*      Look ahead at this face and save the minimum
  74                 adjacency of all the faces that are adjacent to
  75                 this face.
  76         */
  77         return Min_Adj(id);
  78 }
  79
  80 int Random_Look(int id[],int count)
  81 {
  82         /*      We had a tie within a tie in the lookahead,
  83                 break it randomly
  84         */
  85         register int num;
  86
  87         num = rand();
  88         while (num >= count)
  89                 num = num/20;
  90         return (id[num]);
  91 }
  92
  93
  94 int Look_Ahead_Tie()
  95 {
  96         /*      Look ahead and find the face to go to that
  97                 will give the least number of adjacencies
  98         */
  99         int id[60],t,x,f=0,min = 60;
 100
 101         for (x = 0; x < last; x++)
 102         {
 103                 t = Look_Ahead(ties_array[x]);
 104                 /*      We have a tie */
 105                 if (t == min)
 106                         id[f++] = ties_array[x];
 107                 if (t < min)
 108                 {
 109                         f = 0;
 110                         min = t;
 111                         id[f++] = ties_array[x];
 112                 }
 113         }
 114         /*      No tie within the tie */
 115         if ( f == 1)
 116                 return id[0];
 117         /*      Or ties, but we are at the end of strips */
 118         if (min == 0)
 119                 return id[0];
 120         return (Random_Look(id,f));
 121 }
 122
 123
 124 int Sequential_Tri(int *index)
 125 {
 126     /*  We have a triangle and need to break the ties at it.
 127         We will choose the edge that is sequential. There
 128         is definitely one since we know we have a triangle
 129         and that there is a tie and there are only 2 edges
 130         for the tie.
 131     */
 132     int reversed, e1,e2,e3,output1,output2,output3,output4;
 133
 134     /*  e2 and e3 are the input edge to the triangle */
 135     Last_Edge(&e1,&e2,&e3,0);
 136
 137     if ((e2 == 0) && (e3 == 0))
 138         /*  Starting the strip, don't need to do this */
 139         return ties_array[0];
 140
 141     /*  For the 2 ties find the edge adjacent to face id */
 142     reversed = Get_EdgeEx(&output1,&output2,index,ties_array[0],3,0,0);
 143     reversed = Get_EdgeEx(&output3,&output4,index,ties_array[1],3,0,0);
 144
 145     if ((output1 == e3) || (output2 == e3))
 146         return ties_array[0];
 147     if ((output3 == e3) || (output4 == e3))
 148         return ties_array[1];
 149     printf("There is an error trying to break sequential triangle \n");
 150 }
 151
 152 int Sequential_Quad(int *index, int triangulate)
 153 {
 154     /*  We have a quad that need to break its ties, we will try
 155         and choose a side that is sequential, otherwise use lookahead
 156     */
 157     int reversed,output1,output2,x,e1,e2,e3;
 158
 159     /*  e2 and e3 are the input edge to the quad */
 160     Last_Edge(&e1,&e2,&e3,0);
 161
 162     /*  No input edge */
 163     if ((e2 == 0) && (e3 == 0))
 164         return ties_array[0];
 165
 166         /*  Go through the ties and see if there is a sequential one */
 167     for (x = 0; x < last; x++)
 168         {
 169         reversed = Get_EdgeEx(&output1,&output2,index,ties_array[x],4,0,0);
 170         /*  Partial and whole triangulation will have different requirements */
 171         if (((output1 == e3) || (output2 == e3)) && (triangulate == PARTIAL))
 172             return ties_array[x];
 173         if (((output1 != e3) && (output1 != e2) &&
 174                 (output2 != e3) && (output2 != e2)))
 175             return ties_array[x];
 176     }
 177     /*  There was not a tie that was sequential */
 178         return Look_Ahead_Tie();
 179 }
 180
 181 void Whole_Output(int in1,int in2, int *index, int size, int *out1, int *out2)
 182 {
 183     /*  Used to sequentially break ties in the whole triangulation for polygons
 184         greater than 4 sides. We will find the output edge that is good
 185         for sequential triangulation.
 186     */
 187
 188     int half;
 189
 190     /*  Put the input edge first in the list */
 191     Rearrange_IndexEx(index,size);
 192
 193     if (!(EVEN(size)))
 194     {
 195         if (*(index) == in1)
 196             half = size/2 ;
 197         else
 198             half = size/2 +1;
 199     }
 200     else
 201         half = size/2;
 202
 203     *out1 = *(index+half);
 204     *out2 = *(index+half+1);
 205 }
 206
 207 int Sequential_Poly(int size, int *index, int triangulate)
 208 {
 209     /*  We have a polygon of greater than 4 sides and wish to break the
 210         tie in the most sequential manner.
 211     */
 212
 213     int x,reversed,output1,output2,e1,e2,e3,saved1=-1,saved2=-1,output3,output4;
 214
 215     /*  e2 and e3 are the input edge to the quad */
 216     Last_Edge(&e1,&e2,&e3,0);
 217
 218     /*  If we are using whole, find the output edge that is sequential */
 219     if (triangulate == WHOLE)
 220         Whole_Output(e2,e3,index,size,&output3,&output4);
 221
 222     /*  No input edge */
 223     if ((e2 == 0) && (e3 == 0))
 224         return ties_array[0];
 225
 226     for (x = 0; x < last ; x++)
 227     {
 228         reversed = Get_EdgeEx(&output1,&output2,index,ties_array[x],size,0,0);
 229         /*  Partial that can be removed in just one triangle */
 230         if (((output1 == e3) || (output2 == e3)) && (triangulate == PARTIAL))
 231             saved1 = ties_array[x];
 232         /*  Partial removed in more than one triangle */
 233         if ((output1 != e3) && (output1 != e2) && (output2 != e3) && (output2 != e2) &&
 234             (triangulate == PARTIAL) && (saved2 != -1))
 235             saved2 = ties_array[x];
 236         /*  Whole is not so easy, since the whole polygon must be done. Given
 237             an input edge there is only one way to come out, approximately half
 238             way around the polygon.
 239         */
 240         if (((output1 == output3) && (output2 == output4)) ||
 241             ((output1 == output4) && (output2 == output3)) &&
 242             (triangulate == WHOLE))
 243             return ties_array[x];
 244     }
 245
 246     if (saved1 != -1)
 247         return saved1;
 248     if (saved2 != -1)
 249         return saved2;
 250
 251     /*  There was not a tie that was sequential */
 252     return Look_Ahead_Tie();
 253 }
 254
 255 int Sequential_Tie(int face_id,int triangulate)
 256 {
 257     /*  Break the tie by choosing the face that will
 258         not give us a swap and is sequential. If there
 259         is not one, then do the lookahead to break the
 260         tie.
 261     */
 262     /*  Separate into 3 cases for simplicity, if the current
 263         polygon has 3 sides, 4 sides or if the sides were
 264         greater. We can do the smaller cases faster, so that
 265         is why I separated the cases.
 266     */
 267
 268      ListHead *pListFace;
 269         PF_FACES face;
 270
 271     /*  Get the polygon with id face_id */
 272         pListFace  = PolFaces[face_id];
 273         face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
 274
 275      if (face->nPolSize == 3)
 276         return(Sequential_Tri(face->pPolygon));
 277      if (face->nPolSize == 4)
 278         return(Sequential_Quad(face->pPolygon,triangulate));
 279      else
 280         return(Sequential_Poly(face->nPolSize,face->pPolygon,triangulate));
 281
 282 }
 283
 284 int Get_Next_Face(int t, int face_id, int triangulate)
 285 {
 286         /*      Get the next face depending on what
 287                 the user specified
 288         */
 289
 290         /*      Did not have a tie, don't do anything */
 291         if (last == 1)
 292                 return(ties_array[0]);
 293         if (t == RANDOM)
 294                 return Random_Tie();
 295         if (t == ALTERNATE)
 296                 return Alternate_Tie();
 297         if (t == LOOK)
 298                 return Look_Ahead_Tie();
 299      if (t == SEQUENTIAL)
 300         return Sequential_Tie(face_id,triangulate);
 301
 302         printf("Illegal option specified for ties, using first \n");
 303      return (ties_array[0]);
 304 }