Stripe_w/add.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: add.c
  11      This file contains the procedure code that will add information
  12      to our data structures.
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <math.h>
  19 #include <string.h>
  20 #include "global.h"
  21 #include "queue.h"
  22 #include "polverts.h"
  23 #include "triangulate.h"
  24 #include "ties.h"
  25 #include "outputex.h"
  26 #include "options.h"
  27 #include "local.h"
  28
  29 BOOL new_vertex(double difference, int id1,int id2,
  30                 struct vert_struct *n)
  31 {
  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?
  35   */
  36   struct vert_struct *pn1,*pn2;
  37   double dot_product;
  38   double distance1, distance2,distance;
  39   double rad;
  40   char arg1[100];
  41   char arg2[100];
  42
  43   pn1 = n + id1;
  44   pn2 = n + id2;
  45
  46   dot_product = ((pn1->x) * (pn2->x)) +
  47                 ((pn1->y) * (pn2->y)) +
  48                 ((pn1->z) * (pn2->z));
  49   /*   Get the absolute value */
  50   if (dot_product < 0)
  51     dot_product = dot_product * -1;
  52
  53   distance1 = sqrt( (pn1->x * pn1->x) +
  54                     (pn1->y * pn1->y) +
  55                     (pn1->z * pn1->z) );
  56   distance2 = sqrt( (pn2->x * pn2->x) +
  57                     (pn2->y * pn2->y) +
  58                     (pn2->z * pn2->z) );
  59   distance = distance1 * distance2;
  60
  61   rad = acos((double)dot_product/(double)distance);
  62   /* convert to degrees */
  63   rad = (180 * rad)/PI;
  64
  65   if ( rad <= difference)
  66     return FALSE;
  67
  68   /*   double checking because of imprecision with floating
  69        point acos function
  70   */
  71   sprintf( arg1,"%.5f", rad );
  72   sprintf( arg2,"%.5f", difference );
  73   if ( strcmp( arg1, arg2 ) <=0 )
  74     return( FALSE );
  75   if ( rad <= difference)
  76     return FALSE;
  77   else
  78     return TRUE;
  79 }
  80
  81 BOOL Check_VN(int vertex,int normal, struct vert_added *added)
  82 {
  83   /*   Check to see if we already added this vertex and normal */
  84   register int x,n;
  85
  86   n = (added+vertex)->num;
  87   for (x = 0; x < n; x++)
  88   {
  89     if (*((added+vertex)->normal+x) == normal)
  90       return TRUE;
  91   }
  92   return FALSE;
  93 }
  94
  95 BOOL norm_array(int id, int vertex, double normal_difference,
  96                 struct vert_struct *n, int num_vert)
  97 {
  98   static int last;
  99   static struct vert_added *added;
 100   register int x;
 101   static BOOL first = TRUE;
 102
 103   if (first)
 104   {
 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
 108     */
 109     first = FALSE;
 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
 112          zero
 113     */
 114     for (x = 0; x < num_vert; x++)
 115       (added+x)->num = 0;
 116   }
 117
 118   if (vertex)
 119     /*   Set the pointer to the vertex, we will be calling again with the
 120          normal to fill it with
 121     */
 122     last = id;
 123   else
 124   {
 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))
 129     {
 130       /*   difference is big enough, we need to create a new vertex */
 131       if (new_vertex(normal_difference,id,*(vert_norms + last),n))
 132       {
 133         /*   First check to see if we added this vertex and normal already */
 134         if (Check_VN(last,id,added))
 135           return FALSE;
 136         /*   OK, create the new vertex, and have its id = the number of vertices
 137              and its normal what we have here
 138         */
 139         vert_norms = realloc(vert_norms, sizeof(int) * (num_vert + 1));
 140         if (!vert_norms)
 141         {
 142           printf("Allocation error - aborting\n");
 143           exit(1);
 144         }
 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
 148         */
 149         (added+last)->num = (added+last)->num + 1;
 150         if ((added+last)->num == 1)
 151         {
 152           /*   First time */
 153           (added+last)->normal =  (int *) malloc (sizeof (int ) * 1);
 154           *((added+last)->normal) =  id;
 155         }
 156         else
 157         {
 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;
 161         }
 162         return TRUE;
 163       }
 164     }
 165   }
 166   return FALSE;
 167 }
 168
 169 void add_texture(int id,BOOL vertex)
 170 {
 171   /*   Save the texture with its vertex for future use when outputting */
 172   static int last;
 173
 174   if (vertex)
 175     last = id;
 176   else
 177     *(vert_texture+last) = id;
 178 }
 179
 180 int     add_vert_id(int id, int index_count)
 181 {
 182   register int x;
 183
 184   /*   Test if degenerate, if so do not add degenerate vertex */
 185   for (x = 1; x < index_count ; x++)
 186   {
 187     if (ids[x] == id)
 188       return 0;
 189   }
 190   ids[index_count] = id;
 191   return 1;
 192 }
 193
 194 void    add_norm_id(int id, int index_count)
 195 {
 196         norms[index_count] = id;
 197 }
 198
 199 void AddNewFace(int ids[STRIP_MAX], int vert_count, int face_id,
 200                 int norms[STRIP_MAX])
 201 {
 202   PF_FACES pfNode;
 203   int   *pTempInt;
 204   int *pnorms;
 205   F_EDGES **pTempVertptr;
 206   int   *pTempmarked, *pTempwalked;
 207   register int  y,count = 0;
 208
 209         /*   Add a new face into our face data structure */
 210
 211   pfNode = (PF_FACES) malloc(sizeof(F_FACES) );
 212   if ( pfNode )
 213   {
 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));
 219         }
 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;
 226         pfNode->seen = -1;
 227   pfNode->seen2 = -1;
 228         for (y=1;y<=vert_count;y++)
 229         {
 230                 *(pTempInt + count) = ids[y];
 231                 *(pnorms + count) = norms[y];
 232     *(pTempmarked + count) = FALSE;
 233           *(pTempwalked + count) =  -1;
 234                 *(pTempVertptr+count) = NULL;
 235                 count++;
 236         }
 237         AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
 238 }
 239
 240
 241 void CopyFace(int ids[STRIP_MAX], int vert_count, int face_id,
 242               int norms[STRIP_MAX])
 243 {
 244   PF_FACES pfNode;
 245   int   *pTempInt;
 246   int *pnorms;
 247   F_EDGES **pTempVertptr;
 248   int   *pTempmarked, *pTempwalked;
 249   register int  y,count = 0;
 250
 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
 253   */
 254
 255   pfNode = (PF_FACES) malloc(sizeof(F_FACES) );
 256   if ( pfNode )
 257   {
 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));
 263         }
 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;
 270         pfNode->seen = -1;
 271   pfNode->seen2 = -1;
 272         for (y=0;y<vert_count;y++)
 273         {
 274                 *(pTempInt + count) = ids[y];
 275                 *(pnorms + count) = norms[y];
 276     *(pTempmarked + count) = FALSE;
 277                 *(pTempwalked + count) =  -1;
 278                 *(pTempVertptr+count) = NULL;
 279                 count++;
 280         }
 281         AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
 282 }
 283
 284 void Add_Edge(int v1,int v2)
 285 {
 286   PF_EDGES temp  = NULL;
 287   ListHead *pListHead;
 288   BOOL flag = TRUE;
 289   register int t,count = 0;
 290
 291         /*   Add a new edge into the edge data structure */
 292   if (v1 > v2)
 293         {
 294                 t  = v1;
 295                 v1 = v2;
 296                 v2 = t;
 297         }
 298
 299   pListHead = PolEdges[v1];
 300         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 301         if (temp == NULL)
 302   {
 303     printf("Have the wrong edge \n:");
 304     exit(1);
 305   }
 306
 307         while (flag)
 308         {
 309                 if (v2 == temp->edge[0])
 310       return;
 311     else
 312         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,++count);
 313         }
 314 }
 315
 316 void Add_AdjEdge(int v1,int v2,int fnum,int index1 )
 317 {
 318   PF_EDGES temp  = NULL;
 319   PF_FACES temp2 = NULL;
 320   PF_EDGES pfNode;
 321   ListHead *pListHead;
 322   ListHead *pListFace;
 323   BOOL  flag = TRUE;
 324   register int  count = 0;
 325   register int  t,v3 = -1;
 326
 327         if (v1 > v2)
 328         {
 329                 t  = v1;
 330                 v1 = v2;
 331                 v2 = t;
 332         }
 333         pListFace  = PolFaces[fnum];
 334         temp2 = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
 335         pListHead = PolEdges[v1];
 336         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 337         if (temp == NULL)
 338                 flag = FALSE;
 339         count++;
 340         while (flag)
 341         {
 342                 if (v2 == temp->edge[0])
 343                 {
 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.
 347       */
 348       if (temp->edge[2] == -1)
 349         temp->edge[2] = fnum;
 350       else
 351         v3 = temp->edge[2];
 352       flag = FALSE;
 353                 }
 354                 else
 355                 {
 356                         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 357                         count++;
 358                         if (temp == NULL)
 359                                 flag = FALSE;
 360                 }
 361         }
 362
 363         /*   Did not find it */
 364   if (temp == NULL)
 365         {
 366                 pfNode = (PF_EDGES) malloc(sizeof(F_EDGES) );
 367     if ( pfNode )
 368     {
 369       pfNode->edge[0] = v2;
 370                         pfNode->edge[1] = fnum;
 371             pfNode->edge[2] =  v3;
 372                         AddTail( PolEdges[v1], (PLISTINFO) pfNode );
 373     }
 374                 else
 375     {
 376       printf("Out of memory!\n");
 377       exit(1);
 378     }
 379
 380     *(temp2->VertandId+index1) = pfNode;
 381         }
 382         else
 383           *(temp2->VertandId+index1) =  temp;
 384 }