src/glu/mesa/tesselat.c

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