libtess/src/tessellate.c

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