src/glu/mini/tesselat.c

   1 /* $Id: tesselat.c,v 1.2 2003/08/22 20:11:43 brianp 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 }