File indexing completed on 2024-03-24 15:17:35

0001 #include "glu.h"
0002 #include "tess.h"
0003 #include "tessellate.h"
0004 #include <stdio.h>
0005 #include <stdlib.h>
0006 
0007 /******************************************************************************/
0008 
0009 typedef struct Triangle
0010 {
0011     int v[3];
0012     struct Triangle *prev;
0013 } Triangle;
0014 
0015 typedef struct Vertex
0016 {
0017     double pt[3];
0018     int index;
0019     struct Vertex *prev;
0020 } Vertex;
0021 
0022 typedef struct TessContext
0023 {
0024     Triangle *latest_t;
0025     int n_tris;
0026 
0027     Vertex *v_prev;
0028     Vertex *v_prevprev;
0029     Vertex *latest_v;
0030     GLenum current_mode;
0031     int odd_even_strip;
0032 
0033     void (*vertex_cb)(Vertex *, struct TessContext *);
0034 } TessContext;
0035 
0036 void skip_vertex(Vertex *v, TessContext *ctx);
0037 
0038 /******************************************************************************/
0039 
0040 TessContext *new_tess_context()
0041 {
0042     TessContext *result    = (TessContext *)malloc(sizeof(struct TessContext));
0043     result->latest_t       = NULL;
0044     result->latest_v       = NULL;
0045     result->n_tris         = 0;
0046     result->v_prev         = NULL;
0047     result->v_prevprev     = NULL;
0048     result->v_prev         = NULL;
0049     result->v_prev         = NULL;
0050     result->vertex_cb      = &skip_vertex;
0051     result->odd_even_strip = 0;
0052     return result;
0053 }
0054 
0055 void destroy_tess_context(TessContext *ctx)
0056 {
0057     free(ctx);
0058 }
0059 
0060 Vertex *new_vertex(TessContext *ctx, double x, double y)
0061 {
0062     Vertex *result = (Vertex *)malloc(sizeof(Vertex));
0063     result->prev   = ctx->latest_v;
0064     result->pt[0]  = x;
0065     result->pt[1]  = y;
0066     result->pt[2]  = 0;
0067 
0068     if (ctx->latest_v == NULL)
0069     {
0070         result->index = 0;
0071     }
0072     else
0073     {
0074         result->index = ctx->latest_v->index + 1;
0075     }
0076     return ctx->latest_v = result;
0077 }
0078 
0079 Triangle *new_triangle(TessContext *ctx, int v1, int v2, int v3)
0080 {
0081     Triangle *result = (Triangle *)malloc(sizeof(Triangle));
0082     result->prev     = ctx->latest_t;
0083     result->v[0]     = v1;
0084     result->v[1]     = v2;
0085     result->v[2]     = v3;
0086     ctx->n_tris++;
0087     return ctx->latest_t = result;
0088 }
0089 
0090 /******************************************************************************/
0091 
0092 void skip_vertex(Vertex *v, TessContext *ctx){};
0093 
0094 void fan_vertex(Vertex *v, TessContext *ctx)
0095 {
0096     if (ctx->v_prevprev == NULL)
0097     {
0098         ctx->v_prevprev = v;
0099         return;
0100     }
0101     if (ctx->v_prev == NULL)
0102     {
0103         ctx->v_prev = v;
0104         return;
0105     }
0106     new_triangle(ctx, ctx->v_prevprev->index, ctx->v_prev->index, v->index);
0107     ctx->v_prev = v;
0108 }
0109 
0110 void strip_vertex(Vertex *v, TessContext *ctx)
0111 {
0112     if (ctx->v_prev == NULL)
0113     {
0114         ctx->v_prev = v;
0115         return;
0116     }
0117     if (ctx->v_prevprev == NULL)
0118     {
0119         ctx->v_prevprev = v;
0120         return;
0121     }
0122     if (ctx->odd_even_strip)
0123     {
0124         new_triangle(ctx, ctx->v_prevprev->index, ctx->v_prev->index, v->index);
0125     }
0126     else
0127     {
0128         new_triangle(ctx, ctx->v_prev->index, ctx->v_prevprev->index, v->index);
0129     }
0130     ctx->odd_even_strip = !ctx->odd_even_strip;
0131 
0132     ctx->v_prev     = ctx->v_prevprev;
0133     ctx->v_prevprev = v;
0134 }
0135 
0136 void triangle_vertex(Vertex *v, TessContext *ctx)
0137 {
0138     if (ctx->v_prevprev == NULL)
0139     {
0140         ctx->v_prevprev = v;
0141         return;
0142     }
0143     if (ctx->v_prev == NULL)
0144     {
0145         ctx->v_prev = v;
0146         return;
0147     }
0148     new_triangle(ctx, ctx->v_prevprev->index, ctx->v_prev->index, v->index);
0149     ctx->v_prev = ctx->v_prevprev = NULL;
0150 }
0151 
0152 void vertex(void *vertex_data, void *poly_data)
0153 {
0154     Vertex *ptr      = (Vertex *)vertex_data;
0155     TessContext *ctx = (TessContext *)poly_data;
0156     ctx->vertex_cb(ptr, ctx);
0157 }
0158 
0159 void begin(GLenum which, void *poly_data)
0160 {
0161     TessContext *ctx = (TessContext *)poly_data;
0162     ctx->v_prev = ctx->v_prevprev = NULL;
0163     ctx->odd_even_strip           = 0;
0164     switch (which)
0165     {
0166         case GL_TRIANGLES:
0167             ctx->vertex_cb = &triangle_vertex;
0168             break;
0169         case GL_TRIANGLE_STRIP:
0170             ctx->vertex_cb = &strip_vertex;
0171             break;
0172         case GL_TRIANGLE_FAN:
0173             ctx->vertex_cb = &fan_vertex;
0174             break;
0175         default:
0176             fprintf(stderr, "ERROR, can't handle %d\n", (int)which);
0177             ctx->vertex_cb = &skip_vertex;
0178     }
0179 }
0180 
0181 void combine(const GLdouble newVertex[3], const void *neighborVertex[4], const GLfloat neighborWeight[4],
0182              void **outData, void *polyData)
0183 {
0184     TessContext *ctx = (TessContext *)polyData;
0185     Vertex *result   = new_vertex(ctx, newVertex[0], newVertex[1]);
0186     *outData         = result;
0187 }
0188 
0189 void write_output(TessContext *ctx, double **coordinates_out, int **tris_out, int *vc, int *tc)
0190 {
0191     int n_verts      = 1 + ctx->latest_v->index;
0192     *vc              = n_verts;
0193     int n_tris_copy  = ctx->n_tris;
0194     *tc              = ctx->n_tris;
0195     *coordinates_out = malloc(n_verts * sizeof(double) * 2);
0196     *tris_out        = (ctx->n_tris ? malloc(ctx->n_tris * sizeof(int) * 3) : NULL);
0197 
0198     while (ctx->latest_v)
0199     {
0200         (*coordinates_out)[2 * ctx->latest_v->index]     = ctx->latest_v->pt[0];
0201         (*coordinates_out)[2 * ctx->latest_v->index + 1] = ctx->latest_v->pt[1];
0202         Vertex *prev                                     = ctx->latest_v->prev;
0203         free(ctx->latest_v);
0204         ctx->latest_v = prev;
0205     }
0206 
0207     while (ctx->latest_t)
0208     {
0209         (*tris_out)[3 * (n_tris_copy - 1)]     = ctx->latest_t->v[0];
0210         (*tris_out)[3 * (n_tris_copy - 1) + 1] = ctx->latest_t->v[1];
0211         (*tris_out)[3 * (n_tris_copy - 1) + 2] = ctx->latest_t->v[2];
0212         Triangle *prev                         = ctx->latest_t->prev;
0213         free(ctx->latest_t);
0214         ctx->latest_t = prev;
0215         n_tris_copy--;
0216     }
0217 }
0218 
0219 void tessellate(double **verts, int *nverts, int **tris, int *ntris, const double **contoursbegin,
0220                 const double **contoursend)
0221 {
0222     const double *contourbegin, *contourend;
0223     Vertex *current_vertex;
0224     GLUtesselator *tess;
0225     TessContext *ctx;
0226 
0227     tess = gluNewTess();
0228     ctx  = new_tess_context();
0229     gluTessProperty(tess, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_NONZERO);
0230     gluTessCallback(tess, GLU_TESS_VERTEX_DATA, (GLvoid(*)()) & vertex);
0231     gluTessCallback(tess, GLU_TESS_BEGIN_DATA, (GLvoid(*)()) & begin);
0232     gluTessCallback(tess, GLU_TESS_COMBINE_DATA, (GLvoid(*)()) & combine);
0233 
0234     gluTessBeginPolygon(tess, ctx);
0235     do
0236     {
0237         contourbegin = *contoursbegin++;
0238         contourend   = *contoursbegin;
0239         gluTessBeginContour(tess);
0240         while (contourbegin != contourend)
0241         {
0242             current_vertex = new_vertex(ctx, contourbegin[0], contourbegin[1]);
0243             contourbegin += 2;
0244             gluTessVertex(tess, current_vertex->pt, current_vertex);
0245         }
0246         gluTessEndContour(tess);
0247     } while (contoursbegin != (contoursend - 1));
0248     gluTessEndPolygon(tess);
0249 
0250     write_output(ctx, verts, tris, nverts, ntris);
0251     destroy_tess_context(ctx);
0252     gluDeleteTess(tess);
0253 }