1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
11 This file will contain all the routines used to determine the next face if there
14 /*---------------------------------------------------------------------*/
19 #include "sturctsex.h"
20 #include "triangulatex.h"
31 /* Clear the buffer, because we do not have the tie
32 any more that we had before */
38 /* We have a tie to add to the buffer */
39 ties_array[last++] = id;
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
60 /* Randomly choose the next face with which
68 return (ties_array[num]);
71 int Look_Ahead(int id)
73 /* Look ahead at this face and save the minimum
74 adjacency of all the faces that are adjacent to
80 int Random_Look(int id[],int count)
82 /* We had a tie within a tie in the lookahead,
96 /* Look ahead and find the face to go to that
97 will give the least number of adjacencies
99 int id[60],t,x,f=0,min = 60;
101 for (x = 0; x < last; x++)
103 t = Look_Ahead(ties_array[x]);
106 id[f++] = ties_array[x];
111 id[f++] = ties_array[x];
114 /* No tie within the tie */
117 /* Or ties, but we are at the end of strips */
120 return (Random_Look(id,f));
124 int Sequential_Tri(int *index)
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
132 int reversed, e1,e2,e3,output1,output2,output3,output4;
134 /* e2 and e3 are the input edge to the triangle */
135 Last_Edge(&e1,&e2,&e3,0);
137 if ((e2 == 0) && (e3 == 0))
138 /* Starting the strip, don't need to do this */
139 return ties_array[0];
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);
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");
152 int Sequential_Quad(int *index, int triangulate)
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
157 int reversed,output1,output2,x,e1,e2,e3;
159 /* e2 and e3 are the input edge to the quad */
160 Last_Edge(&e1,&e2,&e3,0);
163 if ((e2 == 0) && (e3 == 0))
164 return ties_array[0];
166 /* Go through the ties and see if there is a sequential one */
167 for (x = 0; x < last; x++)
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];
177 /* There was not a tie that was sequential */
178 return Look_Ahead_Tie();
181 void Whole_Output(int in1,int in2, int *index, int size, int *out1, int *out2)
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.
190 /* Put the input edge first in the list */
191 Rearrange_IndexEx(index,size);
203 *out1 = *(index+half);
204 *out2 = *(index+half+1);
207 int Sequential_Poly(int size, int *index, int triangulate)
209 /* We have a polygon of greater than 4 sides and wish to break the
210 tie in the most sequential manner.
213 int x,reversed,output1,output2,e1,e2,e3,saved1=-1,saved2=-1,output3,output4;
215 /* e2 and e3 are the input edge to the quad */
216 Last_Edge(&e1,&e2,&e3,0);
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);
223 if ((e2 == 0) && (e3 == 0))
224 return ties_array[0];
226 for (x = 0; x < last ; x++)
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.
240 if (((output1 == output3) && (output2 == output4)) ||
241 ((output1 == output4) && (output2 == output3)) &&
242 (triangulate == WHOLE))
243 return ties_array[x];
251 /* There was not a tie that was sequential */
252 return Look_Ahead_Tie();
255 int Sequential_Tie(int face_id,int triangulate)
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
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.
271 /* Get the polygon with id face_id */
272 pListFace = PolFaces[face_id];
273 face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
275 if (face->nPolSize == 3)
276 return(Sequential_Tri(face->pPolygon));
277 if (face->nPolSize == 4)
278 return(Sequential_Quad(face->pPolygon,triangulate));
280 return(Sequential_Poly(face->nPolSize,face->pPolygon,triangulate));
284 int Get_Next_Face(int t, int face_id, int triangulate)
286 /* Get the next face depending on what
290 /* Did not have a tie, don't do anything */
292 return(ties_array[0]);
296 return Alternate_Tie();
298 return Look_Ahead_Tie();
300 return Sequential_Tie(face_id,triangulate);
302 printf("Illegal option specified for ties, using first \n");
303 return (ties_array[0]);