Stripe_u/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[MAX1], int vert_count, int face_id, int norms[MAX1])
 200 {
 201 PF_FACES pfNode;
 202 int     *pTempInt;
 203 int *pnorms;
 204 F_EDGES **pTempVertptr;
 205 int     *pTempmarked, *pTempwalked;
 206 register int    y,count = 0,sum = 0;
 207
 208         /*   Add a new face into our face data structure */
 209
 210      pfNode = (PF_FACES) malloc(sizeof(F_FACES) );
 211      if ( pfNode )
 212      {
 213           pfNode->pPolygon = (int*) malloc(sizeof(int) * (vert_count) );
 214         pfNode->pNorms = (int*) malloc(sizeof(int) * (vert_count) );
 215           pfNode->VertandId = (F_EDGES**)malloc(sizeof(F_EDGES*) * (vert_count));
 216                 pfNode->marked  = (int*)malloc(sizeof(int) * (vert_count));
 217                 pfNode->walked = (int*)malloc(sizeof(int) * (vert_count));
 218         }
 219         pTempInt =pfNode->pPolygon;
 220         pnorms = pfNode->pNorms;
 221      pTempmarked = pfNode->marked;
 222         pTempwalked = pfNode->walked;
 223         pTempVertptr = pfNode->VertandId;
 224         pfNode->nPolSize = vert_count;
 225         pfNode->seen = -1;
 226      pfNode->seen2 = -1;
 227         for (y=1;y<=vert_count;y++)
 228         {
 229                 *(pTempInt + count) = ids[y];
 230                 *(pnorms + count) = norms[y];
 231           *(pTempmarked + count) = FALSE;
 232                 *(pTempwalked + count) =  -1;
 233                 *(pTempVertptr+count) = NULL;
 234                 count++;
 235         }
 236         AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
 237 }
 238
 239
 240 void CopyFace(int ids[MAX1], int vert_count, int face_id, int norms[MAX1])
 241 {
 242 PF_FACES pfNode;
 243 int     *pTempInt;
 244 int *pnorms;
 245 F_EDGES **pTempVertptr;
 246 int     *pTempmarked, *pTempwalked;
 247 register int    y,count = 0,sum = 0;
 248
 249         /*   Copy a face node into a new node, used after the global algorithm
 250           is run, so that we can save whatever is left into a new structure
 251      */
 252
 253      pfNode = (PF_FACES) malloc(sizeof(F_FACES) );
 254      if ( pfNode )
 255      {
 256           pfNode->pPolygon = (int*) malloc(sizeof(int) * (vert_count) );
 257         pfNode->pNorms = (int*) malloc(sizeof(int) * (vert_count) );
 258           pfNode->VertandId = (F_EDGES**)malloc(sizeof(F_EDGES*) * (vert_count));
 259                 pfNode->marked  = (int*)malloc(sizeof(int) * (vert_count));
 260                 pfNode->walked = (int*)malloc(sizeof(int) * (vert_count));
 261         }
 262         pTempInt =pfNode->pPolygon;
 263         pnorms = pfNode->pNorms;
 264      pTempmarked = pfNode->marked;
 265         pTempwalked = pfNode->walked;
 266         pTempVertptr = pfNode->VertandId;
 267         pfNode->nPolSize = vert_count;
 268         pfNode->seen = -1;
 269      pfNode->seen2 = -1;
 270         for (y=0;y<vert_count;y++)
 271         {
 272                 *(pTempInt + count) = ids[y];
 273                 *(pnorms + count) = norms[y];
 274           *(pTempmarked + count) = FALSE;
 275                 *(pTempwalked + count) =  -1;
 276                 *(pTempVertptr+count) = NULL;
 277                 count++;
 278         }
 279         AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
 280 }
 281
 282 void Add_Edge(int v1,int v2)
 283 {
 284 PF_EDGES temp  = NULL;
 285 ListHead *pListHead;
 286 BOOL flag = TRUE;
 287 register int t,count = 0;
 288
 289         /*   Add a new edge into the edge data structure */
 290      if (v1 > v2)
 291         {
 292                 t  = v1;
 293                 v1 = v2;
 294                 v2 = t;
 295         }
 296
 297      pListHead = PolEdges[v1];
 298         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 299         if (temp == NULL)
 300      {
 301           printf("Have the wrong edge \n:");
 302           exit(1);
 303      }
 304
 305         while (flag)
 306         {
 307                 if (v2 == temp->edge[0])
 308                return;
 309           else
 310                 temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,++count);
 311
 312         }
 313 }
 314
 315 void Add_AdjEdge(int v1,int v2,int fnum,int index1 )
 316 {
 317      PF_EDGES temp  = NULL;
 318      PF_FACES temp2 = NULL;
 319      PF_EDGES pfNode;
 320      ListHead *pListHead;
 321      ListHead *pListFace;
 322      BOOL       flag = TRUE;
 323      register int       count = 0;
 324      register int       t,v3 = -1;
 325
 326         if (v1 > v2)
 327         {
 328                 t  = v1;
 329                 v1 = v2;
 330                 v2 = t;
 331         }
 332         pListFace  = PolFaces[fnum];
 333         temp2 = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
 334         pListHead = PolEdges[v1];
 335         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 336         if (temp == NULL)
 337                 flag = FALSE;
 338         count++;
 339         while (flag)
 340         {
 341                 if (v2 == temp->edge[0])
 342                 {
 343                /*   If greater than 2 polygons adjacent to an edge, then we will
 344                     only save the first 2 that we found. We will have a small performance
 345                     hit, but this does not happen often.
 346                */
 347                if (temp->edge[2] == -1)
 348                     temp->edge[2] = fnum;
 349                else
 350                     v3 = temp->edge[2];
 351                         flag = FALSE;
 352                 }
 353                 else
 354                 {
 355                         temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
 356                         count++;
 357                         if (temp == NULL)
 358                                 flag = FALSE;
 359                 }
 360         }
 361
 362         /*   Did not find it */
 363      if (temp == NULL)
 364         {
 365                 pfNode = (PF_EDGES) malloc(sizeof(F_EDGES) );
 366           if ( pfNode )
 367           {
 368                pfNode->edge[0] = v2;
 369                         pfNode->edge[1] = fnum;
 370                   pfNode->edge[2] =  v3;
 371                         AddTail( PolEdges[v1], (PLISTINFO) pfNode );
 372           }
 373                 else
 374           {
 375                printf("Out of memory!\n");
 376                exit(1);
 377           }
 378
 379           *(temp2->VertandId+index1) = pfNode;
 380         }
 381         else
 382                 *(temp2->VertandId+index1) =  temp;
 383
 384 }
 385
 386