1 /********************************************************************/
2 /* STRIPE: converting a polygonal model to triangle strips
5 Advisors: Steven Skiena and Amitabh Varshney
7 /********************************************************************/
9 /*---------------------------------------------------------------------*/
11 This file contains the procedure code that will add information
12 to our data structures.
14 /*---------------------------------------------------------------------*/
23 #include "triangulate.h"
29 BOOL new_vertex(double difference, int id1,int id2,
30 struct vert_struct *n)
32 /* Is the difference between id1 and id2 (2 normal vertices that
33 mapped to the same vertex) greater than the
34 threshold that was specified?
36 struct vert_struct *pn1,*pn2;
38 double distance1, distance2,distance;
46 dot_product = ((pn1->x) * (pn2->x)) +
47 ((pn1->y) * (pn2->y)) +
48 ((pn1->z) * (pn2->z));
49 /* Get the absolute value */
51 dot_product = dot_product * -1;
53 distance1 = sqrt( (pn1->x * pn1->x) +
56 distance2 = sqrt( (pn2->x * pn2->x) +
59 distance = distance1 * distance2;
61 rad = acos((double)dot_product/(double)distance);
62 /* convert to degrees */
65 if ( rad <= difference)
68 /* double checking because of imprecision with floating
71 sprintf( arg1,"%.5f", rad );
72 sprintf( arg2,"%.5f", difference );
73 if ( strcmp( arg1, arg2 ) <=0 )
75 if ( rad <= difference)
81 BOOL Check_VN(int vertex,int normal, struct vert_added *added)
83 /* Check to see if we already added this vertex and normal */
86 n = (added+vertex)->num;
87 for (x = 0; x < n; x++)
89 if (*((added+vertex)->normal+x) == normal)
95 BOOL norm_array(int id, int vertex, double normal_difference,
96 struct vert_struct *n, int num_vert)
99 static struct vert_added *added;
101 static BOOL first = TRUE;
105 /* This is the first time that we are in here, so we will allocate
106 a structure that will save the vertices that we added, so that we
107 do not add the same thing twice
110 added = (struct vert_added *) malloc (sizeof (struct vert_added ) * num_vert);
111 /* The number of vertices added for each vertex must be initialized to
114 for (x = 0; x < num_vert; x++)
119 /* Set the pointer to the vertex, we will be calling again with the
120 normal to fill it with
125 /* Fill the pointer with the id of the normal */
126 if (*(vert_norms + last) == 0)
127 *(vert_norms + last) = id;
128 else if ((*(vert_norms + last) != id) && ((int)normal_difference != 360))
130 /* difference is big enough, we need to create a new vertex */
131 if (new_vertex(normal_difference,id,*(vert_norms + last),n))
133 /* First check to see if we added this vertex and normal already */
134 if (Check_VN(last,id,added))
136 /* OK, create the new vertex, and have its id = the number of vertices
137 and its normal what we have here
139 vert_norms = realloc(vert_norms, sizeof(int) * (num_vert + 1));
142 printf("Allocation error - aborting\n");
145 *(vert_norms + num_vert) = id;
146 /* We created a new vertex, now put it in our added structure so
147 we do not add the same thing twice
149 (added+last)->num = (added+last)->num + 1;
150 if ((added+last)->num == 1)
153 (added+last)->normal = (int *) malloc (sizeof (int ) * 1);
154 *((added+last)->normal) = id;
158 /* Not the first time, reallocate space */
159 (added+last)->normal = realloc((added+last)->normal,sizeof(int) * (added+last)->num);
160 *((added+last)->normal+((added+last)->num-1)) = id;
169 void add_texture(int id,BOOL vertex)
171 /* Save the texture with its vertex for future use when outputting */
177 *(vert_texture+last) = id;
180 int add_vert_id(int id, int index_count)
184 /* Test if degenerate, if so do not add degenerate vertex */
185 for (x = 1; x < index_count ; x++)
190 ids[index_count] = id;
194 void add_norm_id(int id, int index_count)
196 norms[index_count] = id;
199 void AddNewFace(int ids[STRIP_MAX], int vert_count, int face_id,
200 int norms[STRIP_MAX])
205 F_EDGES **pTempVertptr;
206 int *pTempmarked, *pTempwalked;
207 register int y,count = 0;
209 /* Add a new face into our face data structure */
211 pfNode = (PF_FACES) malloc(sizeof(F_FACES) );
214 pfNode->pPolygon = (int*) malloc(sizeof(int) * (vert_count) );
215 pfNode->pNorms = (int*) malloc(sizeof(int) * (vert_count) );
216 pfNode->VertandId = (F_EDGES**)malloc(sizeof(F_EDGES*) * (vert_count));
217 pfNode->marked = (int*)malloc(sizeof(int) * (vert_count));
218 pfNode->walked = (int*)malloc(sizeof(int) * (vert_count));
220 pTempInt =pfNode->pPolygon;
221 pnorms = pfNode->pNorms;
222 pTempmarked = pfNode->marked;
223 pTempwalked = pfNode->walked;
224 pTempVertptr = pfNode->VertandId;
225 pfNode->nPolSize = vert_count;
228 for (y=1;y<=vert_count;y++)
230 *(pTempInt + count) = ids[y];
231 *(pnorms + count) = norms[y];
232 *(pTempmarked + count) = FALSE;
233 *(pTempwalked + count) = -1;
234 *(pTempVertptr+count) = NULL;
237 AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
241 void CopyFace(int ids[STRIP_MAX], int vert_count, int face_id,
242 int norms[STRIP_MAX])
247 F_EDGES **pTempVertptr;
248 int *pTempmarked, *pTempwalked;
249 register int y,count = 0;
251 /* Copy a face node into a new node, used after the global algorithm
252 is run, so that we can save whatever is left into a new structure
255 pfNode = (PF_FACES) malloc(sizeof(F_FACES) );
258 pfNode->pPolygon = (int*) malloc(sizeof(int) * (vert_count) );
259 pfNode->pNorms = (int*) malloc(sizeof(int) * (vert_count) );
260 pfNode->VertandId = (F_EDGES**)malloc(sizeof(F_EDGES*) * (vert_count));
261 pfNode->marked = (int*)malloc(sizeof(int) * (vert_count));
262 pfNode->walked = (int*)malloc(sizeof(int) * (vert_count));
264 pTempInt =pfNode->pPolygon;
265 pnorms = pfNode->pNorms;
266 pTempmarked = pfNode->marked;
267 pTempwalked = pfNode->walked;
268 pTempVertptr = pfNode->VertandId;
269 pfNode->nPolSize = vert_count;
272 for (y=0;y<vert_count;y++)
274 *(pTempInt + count) = ids[y];
275 *(pnorms + count) = norms[y];
276 *(pTempmarked + count) = FALSE;
277 *(pTempwalked + count) = -1;
278 *(pTempVertptr+count) = NULL;
281 AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
284 void Add_Edge(int v1,int v2)
286 PF_EDGES temp = NULL;
289 register int t,count = 0;
291 /* Add a new edge into the edge data structure */
299 pListHead = PolEdges[v1];
300 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
303 printf("Have the wrong edge \n:");
309 if (v2 == temp->edge[0])
312 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,++count);
316 void Add_AdjEdge(int v1,int v2,int fnum,int index1 )
318 PF_EDGES temp = NULL;
319 PF_FACES temp2 = NULL;
324 register int count = 0;
325 register int t,v3 = -1;
333 pListFace = PolFaces[fnum];
334 temp2 = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
335 pListHead = PolEdges[v1];
336 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
342 if (v2 == temp->edge[0])
344 /* If greater than 2 polygons adjacent to an edge, then we will
345 only save the first 2 that we found. We will have a small performance
346 hit, but this does not happen often.
348 if (temp->edge[2] == -1)
349 temp->edge[2] = fnum;
356 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
363 /* Did not find it */
366 pfNode = (PF_EDGES) malloc(sizeof(F_EDGES) );
369 pfNode->edge[0] = v2;
370 pfNode->edge[1] = fnum;
371 pfNode->edge[2] = v3;
372 AddTail( PolEdges[v1], (PLISTINFO) pfNode );
376 printf("Out of memory!\n");
380 *(temp2->VertandId+index1) = pfNode;
383 *(temp2->VertandId+index1) = temp;