Subversion Repositories shark

Rev

Rev 55 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
55 pj 1
/* $Id: tesselat.c,v 1.1 2003-02-28 11:42:08 pj Exp $ */
2
 
3
/*
4
 * Mesa 3-D graphics library
5
 * Version:  3.3
6
 * Copyright (C) 1995-2000  Brian Paul
7
 *
8
 * This library is free software; you can redistribute it and/or
9
 * modify it under the terms of the GNU Library General Public
10
 * License as published by the Free Software Foundation; either
11
 * version 2 of the License, or (at your option) any later version.
12
 *
13
 * This library is distributed in the hope that it will be useful,
14
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16
 * Library General Public License for more details.
17
 *
18
 * You should have received a copy of the GNU Library General Public
19
 * License along with this library; if not, write to the Free
20
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21
 */
22
 
23
 
24
/*
25
 * This file is part of the polygon tesselation code contributed by
26
 * Bogdan Sikorski
27
 */
28
 
29
 
30
#ifdef PC_HEADER
31
#include "all.h"
32
#else
33
#include <stdlib.h>
34
#include <math.h>
35
#include "tess.h"
36
#endif
37
 
38
 
39
 
40
static GLboolean edge_flag;
41
 
42
static void emit_triangle(GLUtriangulatorObj *, tess_vertex *,
43
                          tess_vertex *, tess_vertex *);
44
 
45
static void emit_triangle_with_edge_flag(GLUtriangulatorObj *,
46
                                         tess_vertex *, GLboolean,
47
                                         tess_vertex *, GLboolean,
48
                                         tess_vertex *, GLboolean);
49
 
50
static GLdouble
51
twice_the_triangle_area(tess_vertex * va, tess_vertex * vb, tess_vertex * vc)
52
{
53
   return (vb->x - va->x) * (vc->y - va->y) - (vb->y - va->y) * (vc->x -
54
                                                                 va->x);
55
}
56
 
57
static GLboolean
58
left(GLdouble A, GLdouble B, GLdouble C, GLdouble x, GLdouble y)
59
{
60
   if (A * x + B * y + C > -EPSILON)
61
      return GL_TRUE;
62
   else
63
      return GL_FALSE;
64
}
65
 
66
static GLboolean
67
right(GLdouble A, GLdouble B, GLdouble C, GLdouble x, GLdouble y)
68
{
69
   if (A * x + B * y + C < EPSILON)
70
      return GL_TRUE;
71
   else
72
      return GL_FALSE;
73
}
74
 
75
static GLint
76
convex_ccw(tess_vertex * va,
77
           tess_vertex * vb, tess_vertex * vc, GLUtriangulatorObj * tobj)
78
{
79
   GLdouble d;
80
 
81
   d = twice_the_triangle_area(va, vb, vc);
82
 
83
   if (d > EPSILON) {
84
      return 1;
85
   }
86
   else if (d < -EPSILON) {
87
      return 0;
88
   }
89
   else {
90
      return -1;
91
   }
92
}
93
 
94
static GLint
95
convex_cw(tess_vertex * va,
96
          tess_vertex * vb, tess_vertex * vc, GLUtriangulatorObj * tobj)
97
{
98
   GLdouble d;
99
 
100
   d = twice_the_triangle_area(va, vb, vc);
101
 
102
   if (d < -EPSILON) {
103
      return 1;
104
   }
105
   else if (d > EPSILON) {
106
      return 0;
107
   }
108
   else {
109
      return -1;
110
   }
111
}
112
 
113
static GLboolean
114
diagonal_ccw(tess_vertex * va,
115
             tess_vertex * vb,
116
             GLUtriangulatorObj * tobj, tess_contour * contour)
117
{
118
   tess_vertex *vc = va->next, *vertex, *shadow_vertex;
119
   struct
120
   {
121
      GLdouble A, B, C;
122
   }
123
   ac, cb, ba;
124
   GLdouble x, y;
125
 
126
   GLint res = convex_ccw(va, vc, vb, tobj);
127
   if (res == 0)
128
      return GL_FALSE;
129
   if (res == -1)
130
      return GL_TRUE;
131
 
132
   ba.A = vb->y - va->y;
133
   ba.B = va->x - vb->x;
134
   ba.C = -ba.A * va->x - ba.B * va->y;
135
   ac.A = va->y - vc->y;
136
   ac.B = vc->x - va->x;
137
   ac.C = -ac.A * vc->x - ac.B * vc->y;
138
   cb.A = vc->y - vb->y;
139
   cb.B = vb->x - vc->x;
140
   cb.C = -cb.A * vb->x - cb.B * vb->y;
141
   for (vertex = vb->next; vertex != va; vertex = vertex->next) {
142
      shadow_vertex = vertex->shadow_vertex;
143
      if (shadow_vertex != NULL &&
144
          (shadow_vertex == va || shadow_vertex == vb || shadow_vertex == vc))
145
         continue;
146
      x = vertex->x;
147
      y = vertex->y;
148
      if (left(ba.A, ba.B, ba.C, x, y) &&
149
          left(ac.A, ac.B, ac.C, x, y) && left(cb.A, cb.B, cb.C, x, y))
150
         return GL_FALSE;
151
   }
152
   return GL_TRUE;
153
}
154
 
155
static GLboolean
156
diagonal_cw(tess_vertex * va,
157
            tess_vertex * vb,
158
            GLUtriangulatorObj * tobj, tess_contour * contour)
159
{
160
   tess_vertex *vc = va->next, *vertex, *shadow_vertex;
161
   struct
162
   {
163
      GLdouble A, B, C;
164
   }
165
   ac, cb, ba;
166
   GLdouble x, y;
167
 
168
   GLint res = convex_cw(va, vc, vb, tobj);
169
   if (res == 0)
170
      return GL_FALSE;
171
   if (res == -1)
172
      return GL_TRUE;
173
 
174
   ba.A = vb->y - va->y;
175
   ba.B = va->x - vb->x;
176
   ba.C = -ba.A * va->x - ba.B * va->y;
177
   ac.A = va->y - vc->y;
178
   ac.B = vc->x - va->x;
179
   ac.C = -ac.A * vc->x - ac.B * vc->y;
180
   cb.A = vc->y - vb->y;
181
   cb.B = vb->x - vc->x;
182
   cb.C = -cb.A * vb->x - cb.B * vb->y;
183
   for (vertex = vb->next; vertex != va; vertex = vertex->next) {
184
      shadow_vertex = vertex->shadow_vertex;
185
      if (shadow_vertex != NULL &&
186
          (shadow_vertex == va || shadow_vertex == vb || shadow_vertex == vc))
187
         continue;
188
      x = vertex->x;
189
      y = vertex->y;
190
      if (right(ba.A, ba.B, ba.C, x, y) &&
191
          right(ac.A, ac.B, ac.C, x, y) && right(cb.A, cb.B, cb.C, x, y))
192
         return GL_FALSE;
193
   }
194
   return GL_TRUE;
195
}
196
 
197
static void
198
clip_ear(GLUtriangulatorObj * tobj, tess_vertex * v, tess_contour * contour)
199
{
200
   emit_triangle(tobj, v->previous, v, v->next);
201
   /* the first in the list */
202
   if (contour->vertices == v) {
203
      contour->vertices = v->next;
204
      contour->last_vertex->next = v->next;
205
      v->next->previous = contour->last_vertex;
206
   }
207
   else
208
      /* the last ? */
209
   if (contour->last_vertex == v) {
210
      contour->vertices->previous = v->previous;
211
      v->previous->next = v->next;
212
      contour->last_vertex = v->previous;
213
   }
214
   else {
215
      v->next->previous = v->previous;
216
      v->previous->next = v->next;
217
   }
218
   free(v);
219
   --(contour->vertex_cnt);
220
}
221
 
222
static void
223
clip_ear_with_edge_flag(GLUtriangulatorObj * tobj,
224
                        tess_vertex * v, tess_contour * contour)
225
{
226
   emit_triangle_with_edge_flag(tobj, v->previous, v->previous->edge_flag,
227
                                v, v->edge_flag, v->next, GL_FALSE);
228
   v->previous->edge_flag = GL_FALSE;
229
   /* the first in the list */
230
   if (contour->vertices == v) {
231
      contour->vertices = v->next;
232
      contour->last_vertex->next = v->next;
233
      v->next->previous = contour->last_vertex;
234
   }
235
   else
236
      /* the last ? */
237
   if (contour->last_vertex == v) {
238
      contour->vertices->previous = v->previous;
239
      v->previous->next = v->next;
240
      contour->last_vertex = v->previous;
241
   }
242
   else {
243
      v->next->previous = v->previous;
244
      v->previous->next = v->next;
245
   }
246
   free(v);
247
   --(contour->vertex_cnt);
248
}
249
 
250
static void
251
triangulate_ccw(GLUtriangulatorObj * tobj, tess_contour * contour)
252
{
253
   tess_vertex *vertex;
254
   GLuint vertex_cnt = contour->vertex_cnt;
255
 
256
   while (vertex_cnt > 3) {
257
      vertex = contour->vertices;
258
      while (diagonal_ccw(vertex, vertex->next->next, tobj, contour) ==
259
             GL_FALSE && tobj->error == GLU_NO_ERROR)
260
         vertex = vertex->next;
261
      if (tobj->error != GLU_NO_ERROR)
262
         return;
263
      clip_ear(tobj, vertex->next, contour);
264
      --vertex_cnt;
265
   }
266
}
267
 
268
static void
269
triangulate_cw(GLUtriangulatorObj * tobj, tess_contour * contour)
270
{
271
   tess_vertex *vertex;
272
   GLuint vertex_cnt = contour->vertex_cnt;
273
 
274
   while (vertex_cnt > 3) {
275
      vertex = contour->vertices;
276
      while (diagonal_cw(vertex, vertex->next->next, tobj, contour) ==
277
             GL_FALSE && tobj->error == GLU_NO_ERROR)
278
         vertex = vertex->next;
279
      if (tobj->error != GLU_NO_ERROR)
280
         return;
281
      clip_ear(tobj, vertex->next, contour);
282
      --vertex_cnt;
283
   }
284
}
285
 
286
static void
287
triangulate_ccw_with_edge_flag(GLUtriangulatorObj * tobj,
288
                               tess_contour * contour)
289
{
290
   tess_vertex *vertex;
291
   GLuint vertex_cnt = contour->vertex_cnt;
292
 
293
   while (vertex_cnt > 3) {
294
      vertex = contour->vertices;
295
      while (diagonal_ccw(vertex, vertex->next->next, tobj, contour) ==
296
             GL_FALSE && tobj->error == GLU_NO_ERROR)
297
         vertex = vertex->next;
298
      if (tobj->error != GLU_NO_ERROR)
299
         return;
300
      clip_ear_with_edge_flag(tobj, vertex->next, contour);
301
      --vertex_cnt;
302
   }
303
}
304
 
305
static void
306
triangulate_cw_with_edge_flag(GLUtriangulatorObj * tobj,
307
                              tess_contour * contour)
308
{
309
   tess_vertex *vertex;
310
   GLuint vertex_cnt = contour->vertex_cnt;
311
 
312
   while (vertex_cnt > 3) {
313
      vertex = contour->vertices;
314
      while (diagonal_cw(vertex, vertex->next->next, tobj, contour) ==
315
             GL_FALSE && tobj->error == GLU_NO_ERROR)
316
         vertex = vertex->next;
317
      if (tobj->error != GLU_NO_ERROR)
318
         return;
319
      clip_ear_with_edge_flag(tobj, vertex->next, contour);
320
      --vertex_cnt;
321
   }
322
}
323
 
324
void
325
tess_tesselate(GLUtriangulatorObj * tobj)
326
{
327
   tess_contour *contour;
328
 
329
   for (contour = tobj->contours; contour != NULL; contour = contour->next) {
330
      if (contour->orientation == GLU_CCW) {
331
         triangulate_ccw(tobj, contour);
332
      }
333
      else {
334
         triangulate_cw(tobj, contour);
335
      }
336
      if (tobj->error != GLU_NO_ERROR)
337
         return;
338
 
339
      /* emit the last triangle */
340
      emit_triangle(tobj, contour->vertices, contour->vertices->next,
341
                    contour->vertices->next->next);
342
   }
343
}
344
 
345
void
346
tess_tesselate_with_edge_flag(GLUtriangulatorObj * tobj)
347
{
348
   tess_contour *contour;
349
 
350
   edge_flag = GL_TRUE;
351
   /* first callback with edgeFlag set to GL_TRUE */
352
   (tobj->callbacks.edgeFlag) (GL_TRUE);
353
 
354
   for (contour = tobj->contours; contour != NULL; contour = contour->next) {
355
      if (contour->orientation == GLU_CCW)
356
         triangulate_ccw_with_edge_flag(tobj, contour);
357
      else
358
         triangulate_cw_with_edge_flag(tobj, contour);
359
      if (tobj->error != GLU_NO_ERROR)
360
         return;
361
      /* emit the last triangle */
362
      emit_triangle_with_edge_flag(tobj, contour->vertices,
363
                                   contour->vertices->edge_flag,
364
                                   contour->vertices->next,
365
                                   contour->vertices->next->edge_flag,
366
                                   contour->vertices->next->next,
367
                                   contour->vertices->next->next->edge_flag);
368
   }
369
}
370
 
371
static void
372
emit_triangle(GLUtriangulatorObj * tobj,
373
              tess_vertex * v1, tess_vertex * v2, tess_vertex * v3)
374
{
375
   (tobj->callbacks.begin) (GL_TRIANGLES);
376
   (tobj->callbacks.vertex) (v1->data);
377
   (tobj->callbacks.vertex) (v2->data);
378
   (tobj->callbacks.vertex) (v3->data);
379
   (tobj->callbacks.end) ();
380
}
381
 
382
static void
383
emit_triangle_with_edge_flag(GLUtriangulatorObj * tobj,
384
                             tess_vertex * v1,
385
                             GLboolean edge_flag1,
386
                             tess_vertex * v2,
387
                             GLboolean edge_flag2,
388
                             tess_vertex * v3, GLboolean edge_flag3)
389
{
390
   (tobj->callbacks.begin) (GL_TRIANGLES);
391
   if (edge_flag1 != edge_flag) {
392
      edge_flag = (edge_flag == GL_TRUE ? GL_FALSE : GL_TRUE);
393
      (tobj->callbacks.edgeFlag) (edge_flag);
394
   }
395
   (tobj->callbacks.vertex) (v1->data);
396
   if (edge_flag2 != edge_flag) {
397
      edge_flag = (edge_flag == GL_TRUE ? GL_FALSE : GL_TRUE);
398
      (tobj->callbacks.edgeFlag) (edge_flag);
399
   }
400
   (tobj->callbacks.vertex) (v2->data);
401
   if (edge_flag3 != edge_flag) {
402
      edge_flag = (edge_flag == GL_TRUE ? GL_FALSE : GL_TRUE);
403
      (tobj->callbacks.edgeFlag) (edge_flag);
404
   }
405
   (tobj->callbacks.vertex) (v3->data);
406
   (tobj->callbacks.end) ();
407
}