Stripe_w/local.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: local.c
  11      This file contains the code that initializes the data structures for
  12      the local algorithm, and starts the local algorithm going.
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include "polverts.h"
  19 #include "local.h"
  20 #include "triangulatex.h"
  21 #include "sturctsex.h"
  22 #include "common.h"
  23 #include "outputex.h"
  24 #include "util.h"
  25 #include "init.h"
  26
  27 void Find_StripsEx(FILE *output, FILE *strip,int *ties, int tie,
  28                    int triangulate, int swaps, int *next_id)
  29 {
  30         /*      This routine will peel off the strips from the model */
  31
  32         ListHead *pListHead;
  33         P_ADJACENCIES temp = NULL;
  34         register int max,bucket=0;
  35         BOOL whole_flag = TRUE;
  36      int dummy = 0;
  37
  38         /* Set the last known input edge to be null */
  39   Last_Edge(&dummy,&dummy,&dummy,1);
  40
  41   /* Search for lowest adjacency polygon and output strips */
  42         while (whole_flag)
  43         {
  44                 bucket = -1;
  45                 /* Search for polygons in increasing number of adjacencies */
  46                 while (bucket < 59)
  47                 {
  48                         bucket++;
  49                         pListHead = array[bucket];
  50                         max = NumOnList(pListHead);
  51                         if (max > 0)
  52                         {
  53                                 temp = (P_ADJACENCIES) PeekList(pListHead,LISTHEAD,0);
  54                                 if (temp == NULL)
  55                                 {
  56                                         printf("Error in the buckets%d %d %d\n",bucket,max,0);
  57                                         exit(0);
  58                                 }
  59                                 Polygon_OutputEx(temp,temp->face_id,bucket,pListHead,
  60                                                output,strip,ties,tie,triangulate,swaps,next_id,1);
  61                                 /* Try to extend backwards, if the starting polygon in the
  62            strip had 2 or more adjacencies to begin with
  63         */
  64         if (bucket >= 2)
  65           Extend_BackwardsEx(temp->face_id,output,strip,ties,tie,triangulate,swaps,next_id);
  66         break;
  67                         }
  68                 }
  69                 /*      Went through the whole structure, it is empty and we are done.
  70                 */
  71                 if ((bucket == 59) && (max == 0))
  72                         whole_flag = FALSE;
  73
  74     /*  We just finished a strip, send dummy data to signal the end
  75         of the strip so that we can output it.
  76     */
  77     else
  78     {
  79       Output_TriEx(-1,-2,-3,output,-1,-10,1);
  80       Last_Edge(&dummy,&dummy,&dummy,1);
  81     }
  82   }
  83 }
  84
  85
  86 void SGI_Strip(int num_verts,int num_faces,FILE *output,
  87                            int ties,int triangulate)
  88
  89 {
  90         FILE *strip;
  91   int next_id = -1,t=0;
  92
  93   strip = fopen("output.d","w");
  94   /* We are going to output and find triangle strips
  95          according the the method that SGI uses, ie always
  96                  choosing as the next triangle in our strip the triangle
  97                  that has the least number of adjacencies. We do not have
  98                  all triangles and will be triangulating on the fly those
  99                  polygons that have more than 3 sides.
 100         */
 101
 102         /*      Build a table that has all the polygons sorted by the number
 103                 of polygons adjacent to it.
 104         */
 105         /*      Initialize it */
 106         Init_Table_SGI();
 107         /*      Build it */
 108         Build_SGI_Table(num_verts,num_faces);
 109
 110         /*    We will have a structure to hold all the strips, until
 111         outputted.
 112   */
 113   InitStripTable();
 114   /* Now we have the structure built to find the polygons according
 115                  to the number of adjacencies. Now use the SGI Method to find
 116                  strips according to the adjacencies
 117         */
 118   Find_StripsEx(output,strip,&t,ties,triangulate,ON,&next_id);
 119 }