1 #include "glu.h"
2 #include "tess.h"
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 /******************************************************************************/
7
8 typedef struct Triangle
9 {
10 int v[3];
11 struct Triangle *prev;
12 } Triangle;
13
14 typedef struct Vertex
15 {
16 double pt[3];
17 int index;
18 struct Vertex *prev;
19 } Vertex;
20
21 typedef struct TessContext
22 {
23 Triangle *latest_t;
24 int n_tris;
25
26 Vertex *v_prev;
27 Vertex *v_prevprev;
28 Vertex *latest_v;
29 GLenum current_mode;
30 int odd_even_strip;
31
32 void (*vertex_cb)(Vertex *, struct TessContext *);
33 } TessContext;
34
35 void skip_vertex(Vertex *v, TessContext *ctx);
36
37 /******************************************************************************/
38
new_tess_context()39 TessContext *new_tess_context()
40 {
41 TessContext *result = (TessContext *)malloc(sizeof(struct TessContext));
42 result->latest_t = NULL;
43 result->latest_v = NULL;
44 result->n_tris = 0;
45 result->v_prev = NULL;
46 result->v_prevprev = NULL;
47 result->v_prev = NULL;
48 result->v_prev = NULL;
49 result->vertex_cb = &skip_vertex;
50 result->odd_even_strip = 0;
51 return result;
52 }
53
destroy_tess_context(TessContext * ctx)54 void destroy_tess_context(TessContext *ctx)
55 {
56 free(ctx);
57 }
58
new_vertex(TessContext * ctx,double x,double y)59 Vertex *new_vertex(TessContext *ctx, double x, double y)
60 {
61 Vertex *result = (Vertex *)malloc(sizeof(Vertex));
62 result->prev = ctx->latest_v;
63 result->pt[0] = x;
64 result->pt[1] = y;
65 result->pt[2] = 0;
66
67 if (ctx->latest_v == NULL)
68 {
69 result->index = 0;
70 }
71 else
72 {
73 result->index = ctx->latest_v->index + 1;
74 }
75 return ctx->latest_v = result;
76 }
77
new_triangle(TessContext * ctx,int v1,int v2,int v3)78 Triangle *new_triangle(TessContext *ctx, int v1, int v2, int v3)
79 {
80 Triangle *result = (Triangle *)malloc(sizeof(Triangle));
81 result->prev = ctx->latest_t;
82 result->v[0] = v1;
83 result->v[1] = v2;
84 result->v[2] = v3;
85 ctx->n_tris++;
86 return ctx->latest_t = result;
87 }
88
89 /******************************************************************************/
90
skip_vertex(Vertex * v,TessContext * ctx)91 void skip_vertex(Vertex *v, TessContext *ctx){};
92
fan_vertex(Vertex * v,TessContext * ctx)93 void fan_vertex(Vertex *v, TessContext *ctx)
94 {
95 if (ctx->v_prevprev == NULL)
96 {
97 ctx->v_prevprev = v;
98 return;
99 }
100 if (ctx->v_prev == NULL)
101 {
102 ctx->v_prev = v;
103 return;
104 }
105 new_triangle(ctx, ctx->v_prevprev->index, ctx->v_prev->index, v->index);
106 ctx->v_prev = v;
107 }
108
strip_vertex(Vertex * v,TessContext * ctx)109 void strip_vertex(Vertex *v, TessContext *ctx)
110 {
111 if (ctx->v_prev == NULL)
112 {
113 ctx->v_prev = v;
114 return;
115 }
116 if (ctx->v_prevprev == NULL)
117 {
118 ctx->v_prevprev = v;
119 return;
120 }
121 if (ctx->odd_even_strip)
122 {
123 new_triangle(ctx, ctx->v_prevprev->index, ctx->v_prev->index, v->index);
124 }
125 else
126 {
127 new_triangle(ctx, ctx->v_prev->index, ctx->v_prevprev->index, v->index);
128 }
129 ctx->odd_even_strip = !ctx->odd_even_strip;
130
131 ctx->v_prev = ctx->v_prevprev;
132 ctx->v_prevprev = v;
133 }
134
triangle_vertex(Vertex * v,TessContext * ctx)135 void triangle_vertex(Vertex *v, TessContext *ctx)
136 {
137 if (ctx->v_prevprev == NULL)
138 {
139 ctx->v_prevprev = v;
140 return;
141 }
142 if (ctx->v_prev == NULL)
143 {
144 ctx->v_prev = v;
145 return;
146 }
147 new_triangle(ctx, ctx->v_prevprev->index, ctx->v_prev->index, v->index);
148 ctx->v_prev = ctx->v_prevprev = NULL;
149 }
150
vertex(void * vertex_data,void * poly_data)151 void vertex(void *vertex_data, void *poly_data)
152 {
153 Vertex *ptr = (Vertex *)vertex_data;
154 TessContext *ctx = (TessContext *)poly_data;
155 ctx->vertex_cb(ptr, ctx);
156 }
157
begin(GLenum which,void * poly_data)158 void begin(GLenum which, void *poly_data)
159 {
160 TessContext *ctx = (TessContext *)poly_data;
161 ctx->v_prev = ctx->v_prevprev = NULL;
162 ctx->odd_even_strip = 0;
163 switch (which)
164 {
165 case GL_TRIANGLES:
166 ctx->vertex_cb = &triangle_vertex;
167 break;
168 case GL_TRIANGLE_STRIP:
169 ctx->vertex_cb = &strip_vertex;
170 break;
171 case GL_TRIANGLE_FAN:
172 ctx->vertex_cb = &fan_vertex;
173 break;
174 default:
175 fprintf(stderr, "ERROR, can't handle %d\n", (int)which);
176 ctx->vertex_cb = &skip_vertex;
177 }
178 }
179
combine(const GLdouble newVertex[3],const void * neighborVertex[4],const GLfloat neighborWeight[4],void ** outData,void * polyData)180 void combine(const GLdouble newVertex[3], const void *neighborVertex[4], const GLfloat neighborWeight[4],
181 void **outData, void *polyData)
182 {
183 TessContext *ctx = (TessContext *)polyData;
184 Vertex *result = new_vertex(ctx, newVertex[0], newVertex[1]);
185 *outData = result;
186 }
187
write_output(TessContext * ctx,double ** coordinates_out,int ** tris_out,int * vc,int * tc)188 void write_output(TessContext *ctx, double **coordinates_out, int **tris_out, int *vc, int *tc)
189 {
190 int n_verts = 1 + ctx->latest_v->index;
191 *vc = n_verts;
192 int n_tris_copy = ctx->n_tris;
193 *tc = ctx->n_tris;
194 *coordinates_out = malloc(n_verts * sizeof(double) * 2);
195 *tris_out = (ctx->n_tris ? malloc(ctx->n_tris * sizeof(int) * 3) : NULL);
196
197 while (ctx->latest_v)
198 {
199 (*coordinates_out)[2 * ctx->latest_v->index] = ctx->latest_v->pt[0];
200 (*coordinates_out)[2 * ctx->latest_v->index + 1] = ctx->latest_v->pt[1];
201 Vertex *prev = ctx->latest_v->prev;
202 free(ctx->latest_v);
203 ctx->latest_v = prev;
204 }
205
206 while (ctx->latest_t)
207 {
208 (*tris_out)[3 * (n_tris_copy - 1)] = ctx->latest_t->v[0];
209 (*tris_out)[3 * (n_tris_copy - 1) + 1] = ctx->latest_t->v[1];
210 (*tris_out)[3 * (n_tris_copy - 1) + 2] = ctx->latest_t->v[2];
211 Triangle *prev = ctx->latest_t->prev;
212 free(ctx->latest_t);
213 ctx->latest_t = prev;
214 n_tris_copy--;
215 }
216 }
217
tessellate(double ** verts,int * nverts,int ** tris,int * ntris,const double ** contoursbegin,const double ** contoursend)218 void tessellate(double **verts, int *nverts, int **tris, int *ntris, const double **contoursbegin,
219 const double **contoursend)
220 {
221 const double *contourbegin, *contourend;
222 Vertex *current_vertex;
223 GLUtesselator *tess;
224 TessContext *ctx;
225
226 tess = gluNewTess();
227 ctx = new_tess_context();
228 gluTessProperty(tess, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_NONZERO);
229 gluTessCallback(tess, GLU_TESS_VERTEX_DATA, (GLvoid(*)()) & vertex);
230 gluTessCallback(tess, GLU_TESS_BEGIN_DATA, (GLvoid(*)()) & begin);
231 gluTessCallback(tess, GLU_TESS_COMBINE_DATA, (GLvoid(*)()) & combine);
232
233 gluTessBeginPolygon(tess, ctx);
234 do
235 {
236 contourbegin = *contoursbegin++;
237 contourend = *contoursbegin;
238 gluTessBeginContour(tess);
239 while (contourbegin != contourend)
240 {
241 current_vertex = new_vertex(ctx, contourbegin[0], contourbegin[1]);
242 contourbegin += 2;
243 gluTessVertex(tess, current_vertex->pt, current_vertex);
244 }
245 gluTessEndContour(tess);
246 } while (contoursbegin != (contoursend - 1));
247 gluTessEndPolygon(tess);
248
249 write_output(ctx, verts, tris, nverts, ntris);
250 destroy_tess_context(ctx);
251 gluDeleteTess(tess);
252 }
253