Stripe_w/util.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: util.c
  11      This file contains routines that are used for various functions
  12 */
  13 /*---------------------------------------------------------------------*/
  14
  15
  16 #include <stdlib.h>
  17 #include "polverts.h"
  18
  19 void switch_lower (int *x, int *y)
  20 {
  21         register int temp;
  22
  23         /*      Put lower value in x */
  24         if (*y < *x)
  25         {
  26                 temp = *x;
  27                 *x = *y;
  28                 *y = temp;
  29         }
  30 }
  31
  32 BOOL member(int x , int id1, int id2, int id3)
  33 {
  34     /*  Is x in the triangle specified by id1,id2,id3 */
  35     if ((x != id1) && (x != id2) && (x != id3))
  36         return FALSE;
  37     return TRUE;
  38 }
  39
  40
  41 int Compare (P_ADJACENCIES node1, P_ADJACENCIES node2)
  42 {
  43         /*      This will only return whether 2 adjacency nodes
  44                 are equivalent.
  45         */
  46         if (node1->face_id == node2->face_id)
  47                 return TRUE;
  48         else
  49                 return FALSE;
  50 }
  51
  52
  53 BOOL Exist(int face_id, int id1, int id2)
  54 {
  55         /*      Does the edge specified by id1 and id2 exist in this
  56                 face currently? Maybe we deleted in partial triangulation
  57         */
  58         ListHead *pListHead;
  59         PF_FACES temp;
  60         register int x,size;
  61         BOOL a=FALSE,b =FALSE;
  62
  63         pListHead = PolFaces[face_id];
  64         temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  65         size = temp->nPolSize;
  66         for (x=0; x<size; x++)
  67         {
  68                 if (*(temp->pPolygon+x) == id1)
  69                         a = TRUE;
  70                 if (*(temp->pPolygon+x) == id2)
  71                         b = TRUE;
  72                 if (a && b)
  73                         return TRUE;
  74         }
  75         return FALSE;
  76 }
  77
  78 int Get_Next_Id(int *index,int e3, int size)
  79 {
  80     /*  Return the id following e3 in the list of vertices */
  81
  82     register int x;
  83
  84     for (x = 0; x< size; x++)
  85     {
  86         if ((*(index+x) == e3) && (x != (size-1)))
  87             return *(index+x+1);
  88         else if (*(index+x) == e3)
  89             return *(index);
  90     }
  91     printf("There is an error in the next id\n");
  92     exit(0);
  93 }
  94
  95 int Different (int id1,int id2,int id3,int id4,int id5, int id6, int *x, int *y)
  96 {
  97     /*    Find the vertex in the first 3 numbers that does not exist in
  98              the last three numbers
  99     */
 100     if ((id1 != id4) && (id1 != id5) && (id1 != id6))
 101     {
 102         *x = id2;
 103         *y = id3;
 104         return id1;
 105     }
 106     if ((id2 != id4) && (id2 != id5) && (id2 != id6))
 107     {
 108         *x = id1;
 109         *y = id3;
 110         return id2;
 111     }
 112     if ((id3 != id4) && (id3 != id5) && (id3 != id6))
 113     {
 114         *x = id1;
 115         *y = id2;
 116         return id3;
 117     }
 118
 119     /*  Because there are degeneracies in the data, this might occur */
 120     *x = id5;
 121     *y = id6;
 122     return id4;
 123 }
 124
 125 int Return_Other(int *index,int e1,int e2)
 126 {
 127         /*   We have a triangle and want to know the third vertex of it */
 128         register int x;
 129
 130         for (x=0;x<3;x++)
 131         {
 132                 if ((*(index+x) != e1) && (*(index+x) != e2))
 133                         return *(index+x);
 134         }
 135      /*   If there is a degenerate triangle return arbitrary */
 136      return e1;
 137 }
 138
 139 int Get_Other_Vertex(int id1,int id2,int id3,int *index)
 140 {
 141         /*      We have a list index of 4 numbers and we wish to
 142           return the number that is not id1,id2 or id3
 143         */
 144         register int x;
 145
 146         for (x=0; x<4; x++)
 147         {
 148                 if ((*(index+x) != id1) && (*(index+x) != id2) &&
 149                         (*(index+x) != id3))
 150                         return *(index+x);
 151         }
 152         /*   If there is some sort of degeneracy this might occur,
 153           return arbitrary
 154      */
 155      if (x==4)
 156           return id1;
 157 }
 158
 159
 160 PLISTINFO Done(int face_id, int size, int *bucket)
 161 {
 162         /*      Check to see whether the polygon with face_id was used
 163                 already, return NULL if it was, otherwise return a pointer to the face.
 164         */
 165         P_ADJACENCIES pfNode;
 166         register int y;
 167         PLISTINFO lpListInfo;
 168
 169         pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
 170         if ( pfNode )
 171                 pfNode->face_id = face_id;
 172
 173         for (y=size; ; y--)
 174         {
 175                 lpListInfo = SearchList(array[y], pfNode,
 176                         (int (*)(void *,void *)) (Compare));
 177                 if (lpListInfo != NULL)
 178                 {
 179                         *bucket = y;
 180                         return lpListInfo;
 181                 }
 182                 if (y == 0)
 183                 /*      This adjacent face was done already */
 184                         return lpListInfo;
 185         }
 186         free (pfNode);
 187 }
 188
 189 void Output_Edge(int *index,int e2,int e3,int *output1,int *output2)
 190 {
 191     /*  Given a quad and an input edge return the other 2 vertices of the
 192         quad.
 193     */
 194
 195     *output1 = -1;
 196     *output2 = -1;
 197
 198     if ((*(index) != e2) && (*(index) != e3))
 199         *output1 = *(index);
 200
 201     if ((*(index+1) != e2) && (*(index+1) != e3))
 202     {
 203         if (*output1 == -1)
 204             *output1 = *(index+1);
 205         else
 206         {
 207             *output2 = *(index+1);
 208             return;
 209         }
 210     }
 211
 212     if ((*(index+2) != e2) && (*(index+2) != e3))
 213     {
 214         if (*output1 == -1)
 215             *output1 = *(index+2);
 216         else
 217         {
 218             *output2 = *(index+2);
 219             return;
 220         }
 221     }
 222
 223     *output2 = *(index+3);
 224 }
 225
 226
 227 void First_Edge(int *id1,int *id2, int *id3)
 228 {
 229     /*  Get the first triangle in the strip we just found, we will use this to
 230            try to extend backwards in the strip
 231     */
 232
 233     ListHead *pListHead;
 234     register int num;
 235     P_STRIPS temp1,temp2,temp3;
 236
 237     pListHead = strips[0];
 238     num = NumOnList(pListHead);
 239
 240     /*    Did not have a strip */
 241     if (num < 3)
 242          return;
 243
 244     temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 0);
 245     temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 1);
 246     temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 2);
 247     *id1 = temp1->face_id;
 248     *id2 = temp2->face_id;
 249     *id3 = temp3->face_id;
 250
 251 }
 252
 253 void Last_Edge(int *id1, int *id2, int *id3, BOOL save)
 254 {
 255         /*   We need the last edge that we had  */
 256         static int v1, v2, v3;
 257
 258         if (save)
 259         {
 260                 v1 = *id1;
 261                 v2 = *id2;
 262                 v3 = *id3;
 263         }
 264         else
 265         {
 266                 *id1 = v1;
 267                 *id2 = v2;
 268                 *id3 = v3;
 269         }
 270 }
 271
 272