diff options
author | Julien Cristau <[email protected]> | 2007-02-01 11:50:36 +0100 |
---|---|---|
committer | Julien Cristau <[email protected]> | 2007-02-01 11:50:36 +0100 |
commit | 2634f06c2095b79d4252bb81c0b0272139dad890 (patch) | |
tree | 855ba634812939982daa999dc44365a4d889d11e /src/glu/mini/tesselat.c | |
parent | 7549426a168f3803d6023622dd9e630a5fa2faf6 (diff) | |
parent | eb667b979bc941f05b8f40a2fc39af6fac960ac5 (diff) |
Merge branch 'upstream-experimental' into debian-experimental
Conflicts:
progs/util/README
progs/util/glstate.c
progs/util/glstate.h
progs/util/sampleMakefile
src/glu/sgi/libnurbs/interface/bezierEval.h
src/glu/sgi/libnurbs/interface/bezierPatch.cc
src/glu/sgi/libnurbs/interface/bezierPatch.h
src/glu/sgi/libnurbs/interface/bezierPatchMesh.cc
src/glu/sgi/libnurbs/interface/bezierPatchMesh.h
src/glu/sgi/libnurbs/interface/glcurveval.cc
src/glu/sgi/libnurbs/interface/glimports.h
src/glu/sgi/libnurbs/interface/glinterface.cc
src/glu/sgi/libnurbs/interface/glrenderer.h
src/glu/sgi/libnurbs/interface/incurveeval.cc
src/glu/sgi/libnurbs/interface/insurfeval.cc
src/glu/sgi/libnurbs/interface/mystdio.h
src/glu/sgi/libnurbs/interface/mystdlib.h
src/glu/sgi/libnurbs/internals/arc.h
src/glu/sgi/libnurbs/internals/arcsorter.cc
src/glu/sgi/libnurbs/internals/arcsorter.h
src/glu/sgi/libnurbs/internals/arctess.h
src/glu/sgi/libnurbs/internals/backend.cc
src/glu/sgi/libnurbs/internals/backend.h
src/glu/sgi/libnurbs/internals/basiccrveval.h
src/glu/sgi/libnurbs/internals/basicsurfeval.h
src/glu/sgi/libnurbs/internals/bezierarc.h
src/glu/sgi/libnurbs/internals/bin.cc
src/glu/sgi/libnurbs/internals/bin.h
src/glu/sgi/libnurbs/internals/bufpool.cc
src/glu/sgi/libnurbs/internals/bufpool.h
src/glu/sgi/libnurbs/internals/cachingeval.cc
src/glu/sgi/libnurbs/internals/cachingeval.h
src/glu/sgi/libnurbs/internals/ccw.cc
src/glu/sgi/libnurbs/internals/coveandtiler.h
src/glu/sgi/libnurbs/internals/curve.cc
src/glu/sgi/libnurbs/internals/curve.h
src/glu/sgi/libnurbs/internals/curvelist.cc
src/glu/sgi/libnurbs/internals/curvelist.h
src/glu/sgi/libnurbs/internals/curvesub.cc
src/glu/sgi/libnurbs/internals/dataTransform.cc
src/glu/sgi/libnurbs/internals/dataTransform.h
src/glu/sgi/libnurbs/internals/defines.h
src/glu/sgi/libnurbs/internals/displaylist.cc
src/glu/sgi/libnurbs/internals/displaylist.h
src/glu/sgi/libnurbs/internals/displaymode.h
src/glu/sgi/libnurbs/internals/flist.cc
src/glu/sgi/libnurbs/internals/flist.h
src/glu/sgi/libnurbs/internals/flistsorter.cc
src/glu/sgi/libnurbs/internals/flistsorter.h
src/glu/sgi/libnurbs/internals/gridline.h
src/glu/sgi/libnurbs/internals/gridtrimvertex.h
src/glu/sgi/libnurbs/internals/gridvertex.h
src/glu/sgi/libnurbs/internals/hull.cc
src/glu/sgi/libnurbs/internals/hull.h
src/glu/sgi/libnurbs/internals/intersect.cc
src/glu/sgi/libnurbs/internals/jarcloc.h
src/glu/sgi/libnurbs/internals/knotvector.h
src/glu/sgi/libnurbs/internals/mapdesc.cc
src/glu/sgi/libnurbs/internals/mapdesc.h
src/glu/sgi/libnurbs/internals/mapdescv.cc
src/glu/sgi/libnurbs/internals/maplist.cc
src/glu/sgi/libnurbs/internals/maplist.h
src/glu/sgi/libnurbs/internals/mesher.cc
src/glu/sgi/libnurbs/internals/mesher.h
src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc
src/glu/sgi/libnurbs/internals/monotonizer.cc
src/glu/sgi/libnurbs/internals/monotonizer.h
src/glu/sgi/libnurbs/internals/myassert.h
src/glu/sgi/libnurbs/internals/mycode.cc
src/glu/sgi/libnurbs/internals/mystring.h
src/glu/sgi/libnurbs/internals/nurbsconsts.h
src/glu/sgi/libnurbs/internals/nurbstess.cc
src/glu/sgi/libnurbs/internals/patch.cc
src/glu/sgi/libnurbs/internals/patch.h
src/glu/sgi/libnurbs/internals/patchlist.cc
src/glu/sgi/libnurbs/internals/patchlist.h
src/glu/sgi/libnurbs/internals/pwlarc.h
src/glu/sgi/libnurbs/internals/quilt.cc
src/glu/sgi/libnurbs/internals/quilt.h
src/glu/sgi/libnurbs/internals/reader.cc
src/glu/sgi/libnurbs/internals/reader.h
src/glu/sgi/libnurbs/internals/renderhints.cc
src/glu/sgi/libnurbs/internals/renderhints.h
src/glu/sgi/libnurbs/internals/simplemath.h
src/glu/sgi/libnurbs/internals/slicer.cc
src/glu/sgi/libnurbs/internals/slicer.h
src/glu/sgi/libnurbs/internals/sorter.cc
src/glu/sgi/libnurbs/internals/sorter.h
src/glu/sgi/libnurbs/internals/splitarcs.cc
src/glu/sgi/libnurbs/internals/subdivider.h
src/glu/sgi/libnurbs/internals/tobezier.cc
src/glu/sgi/libnurbs/internals/trimline.cc
src/glu/sgi/libnurbs/internals/trimline.h
src/glu/sgi/libnurbs/internals/trimregion.cc
src/glu/sgi/libnurbs/internals/trimregion.h
src/glu/sgi/libnurbs/internals/trimvertex.h
src/glu/sgi/libnurbs/internals/trimvertpool.cc
src/glu/sgi/libnurbs/internals/trimvertpool.h
src/glu/sgi/libnurbs/internals/types.h
src/glu/sgi/libnurbs/internals/uarray.cc
src/glu/sgi/libnurbs/internals/uarray.h
src/glu/sgi/libnurbs/internals/varray.cc
src/glu/sgi/libnurbs/internals/varray.h
src/glu/sgi/libnurbs/nurbtess/definitions.h
src/glu/sgi/libnurbs/nurbtess/directedLine.h
src/glu/sgi/libnurbs/nurbtess/glimports.h
src/glu/sgi/libnurbs/nurbtess/gridWrap.cc
src/glu/sgi/libnurbs/nurbtess/gridWrap.h
src/glu/sgi/libnurbs/nurbtess/monoChain.cc
src/glu/sgi/libnurbs/nurbtess/monoChain.h
src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc
src/glu/sgi/libnurbs/nurbtess/monoTriangulation.h
src/glu/sgi/libnurbs/nurbtess/mystdio.h
src/glu/sgi/libnurbs/nurbtess/mystdlib.h
src/glu/sgi/libnurbs/nurbtess/partitionX.cc
src/glu/sgi/libnurbs/nurbtess/partitionX.h
src/glu/sgi/libnurbs/nurbtess/partitionY.cc
src/glu/sgi/libnurbs/nurbtess/partitionY.h
src/glu/sgi/libnurbs/nurbtess/polyDBG.h
src/glu/sgi/libnurbs/nurbtess/polyUtil.cc
src/glu/sgi/libnurbs/nurbtess/polyUtil.h
src/glu/sgi/libnurbs/nurbtess/primitiveStream.cc
src/glu/sgi/libnurbs/nurbtess/primitiveStream.h
src/glu/sgi/libnurbs/nurbtess/quicksort.cc
src/glu/sgi/libnurbs/nurbtess/quicksort.h
src/glu/sgi/libnurbs/nurbtess/rectBlock.cc
src/glu/sgi/libnurbs/nurbtess/rectBlock.h
src/glu/sgi/libnurbs/nurbtess/sampleComp.cc
src/glu/sgi/libnurbs/nurbtess/sampleComp.h
src/glu/sgi/libnurbs/nurbtess/sampleCompBot.cc
src/glu/sgi/libnurbs/nurbtess/sampleCompBot.h
src/glu/sgi/libnurbs/nurbtess/sampleCompRight.cc
src/glu/sgi/libnurbs/nurbtess/sampleCompRight.h
src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc
src/glu/sgi/libnurbs/nurbtess/sampleCompTop.h
src/glu/sgi/libnurbs/nurbtess/sampleMonoPoly.cc
src/glu/sgi/libnurbs/nurbtess/sampleMonoPoly.h
src/glu/sgi/libnurbs/nurbtess/sampledLine.cc
src/glu/sgi/libnurbs/nurbtess/sampledLine.h
src/glu/sgi/libnurbs/nurbtess/searchTree.cc
src/glu/sgi/libnurbs/nurbtess/searchTree.h
src/glu/sgi/libnurbs/nurbtess/zlassert.h
src/glu/sgi/libtess/README
src/glu/sgi/libtess/alg-outline
src/glu/sgi/libtess/dict-list.h
src/glu/sgi/libtess/dict.c
src/glu/sgi/libtess/dict.h
src/glu/sgi/libtess/geom.c
src/glu/sgi/libtess/memalloc.c
src/glu/sgi/libtess/memalloc.h
src/glu/sgi/libtess/mesh.c
src/glu/sgi/libtess/mesh.h
src/glu/sgi/libtess/normal.h
src/glu/sgi/libtess/priorityq-heap.c
src/glu/sgi/libtess/priorityq-heap.h
src/glu/sgi/libtess/priorityq-sort.h
src/glu/sgi/libtess/priorityq.c
src/glu/sgi/libtess/priorityq.h
src/glu/sgi/libtess/render.c
src/glu/sgi/libtess/render.h
src/glu/sgi/libtess/sweep.h
src/glu/sgi/libtess/tess.h
src/glu/sgi/libtess/tessmono.c
src/glu/sgi/libtess/tessmono.h
src/glu/sgi/libutil/error.c
src/glu/sgi/libutil/glue.c
src/glu/sgi/libutil/gluint.h
src/glu/sgi/libutil/project.c
src/glu/sgi/libutil/registry.c
Diffstat (limited to 'src/glu/mini/tesselat.c')
-rw-r--r-- | src/glu/mini/tesselat.c | 407 |
1 files changed, 407 insertions, 0 deletions
diff --git a/src/glu/mini/tesselat.c b/src/glu/mini/tesselat.c new file mode 100644 index 00000000000..a1102e6e5a6 --- /dev/null +++ b/src/glu/mini/tesselat.c @@ -0,0 +1,407 @@ +/* $Id: tesselat.c,v 1.2 2003/08/22 20:11:43 brianp Exp $ */ + +/* + * Mesa 3-D graphics library + * Version: 3.3 + * Copyright (C) 1995-2000 Brian Paul + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library; if not, write to the Free + * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + + +/* + * This file is part of the polygon tesselation code contributed by + * Bogdan Sikorski + */ + + +#ifdef PC_HEADER +#include "all.h" +#else +#include <stdlib.h> +#include <math.h> +#include "tess.h" +#endif + + + +static GLboolean edge_flag; + +static void emit_triangle(GLUtriangulatorObj *, tess_vertex *, + tess_vertex *, tess_vertex *); + +static void emit_triangle_with_edge_flag(GLUtriangulatorObj *, + tess_vertex *, GLboolean, + tess_vertex *, GLboolean, + tess_vertex *, GLboolean); + +static GLdouble +twice_the_triangle_area(tess_vertex * va, tess_vertex * vb, tess_vertex * vc) +{ + return (vb->x - va->x) * (vc->y - va->y) - (vb->y - va->y) * (vc->x - + va->x); +} + +static GLboolean +left(GLdouble A, GLdouble B, GLdouble C, GLdouble x, GLdouble y) +{ + if (A * x + B * y + C > -EPSILON) + return GL_TRUE; + else + return GL_FALSE; +} + +static GLboolean +right(GLdouble A, GLdouble B, GLdouble C, GLdouble x, GLdouble y) +{ + if (A * x + B * y + C < EPSILON) + return GL_TRUE; + else + return GL_FALSE; +} + +static GLint +convex_ccw(tess_vertex * va, + tess_vertex * vb, tess_vertex * vc, GLUtriangulatorObj * tobj) +{ + GLdouble d; + + d = twice_the_triangle_area(va, vb, vc); + + if (d > EPSILON) { + return 1; + } + else if (d < -EPSILON) { + return 0; + } + else { + return -1; + } +} + +static GLint +convex_cw(tess_vertex * va, + tess_vertex * vb, tess_vertex * vc, GLUtriangulatorObj * tobj) +{ + GLdouble d; + + d = twice_the_triangle_area(va, vb, vc); + + if (d < -EPSILON) { + return 1; + } + else if (d > EPSILON) { + return 0; + } + else { + return -1; + } +} + +static GLboolean +diagonal_ccw(tess_vertex * va, + tess_vertex * vb, + GLUtriangulatorObj * tobj, tess_contour * contour) +{ + tess_vertex *vc = va->next, *vertex, *shadow_vertex; + struct + { + GLdouble A, B, C; + } + ac, cb, ba; + GLdouble x, y; + + GLint res = convex_ccw(va, vc, vb, tobj); + if (res == 0) + return GL_FALSE; + if (res == -1) + return GL_TRUE; + + ba.A = vb->y - va->y; + ba.B = va->x - vb->x; + ba.C = -ba.A * va->x - ba.B * va->y; + ac.A = va->y - vc->y; + ac.B = vc->x - va->x; + ac.C = -ac.A * vc->x - ac.B * vc->y; + cb.A = vc->y - vb->y; + cb.B = vb->x - vc->x; + cb.C = -cb.A * vb->x - cb.B * vb->y; + for (vertex = vb->next; vertex != va; vertex = vertex->next) { + shadow_vertex = vertex->shadow_vertex; + if (shadow_vertex != NULL && + (shadow_vertex == va || shadow_vertex == vb || shadow_vertex == vc)) + continue; + x = vertex->x; + y = vertex->y; + if (left(ba.A, ba.B, ba.C, x, y) && + left(ac.A, ac.B, ac.C, x, y) && left(cb.A, cb.B, cb.C, x, y)) + return GL_FALSE; + } + return GL_TRUE; +} + +static GLboolean +diagonal_cw(tess_vertex * va, + tess_vertex * vb, + GLUtriangulatorObj * tobj, tess_contour * contour) +{ + tess_vertex *vc = va->next, *vertex, *shadow_vertex; + struct + { + GLdouble A, B, C; + } + ac, cb, ba; + GLdouble x, y; + + GLint res = convex_cw(va, vc, vb, tobj); + if (res == 0) + return GL_FALSE; + if (res == -1) + return GL_TRUE; + + ba.A = vb->y - va->y; + ba.B = va->x - vb->x; + ba.C = -ba.A * va->x - ba.B * va->y; + ac.A = va->y - vc->y; + ac.B = vc->x - va->x; + ac.C = -ac.A * vc->x - ac.B * vc->y; + cb.A = vc->y - vb->y; + cb.B = vb->x - vc->x; + cb.C = -cb.A * vb->x - cb.B * vb->y; + for (vertex = vb->next; vertex != va; vertex = vertex->next) { + shadow_vertex = vertex->shadow_vertex; + if (shadow_vertex != NULL && + (shadow_vertex == va || shadow_vertex == vb || shadow_vertex == vc)) + continue; + x = vertex->x; + y = vertex->y; + if (right(ba.A, ba.B, ba.C, x, y) && + right(ac.A, ac.B, ac.C, x, y) && right(cb.A, cb.B, cb.C, x, y)) + return GL_FALSE; + } + return GL_TRUE; +} + +static void +clip_ear(GLUtriangulatorObj * tobj, tess_vertex * v, tess_contour * contour) +{ + emit_triangle(tobj, v->previous, v, v->next); + /* the first in the list */ + if (contour->vertices == v) { + contour->vertices = v->next; + contour->last_vertex->next = v->next; + v->next->previous = contour->last_vertex; + } + else + /* the last ? */ + if (contour->last_vertex == v) { + contour->vertices->previous = v->previous; + v->previous->next = v->next; + contour->last_vertex = v->previous; + } + else { + v->next->previous = v->previous; + v->previous->next = v->next; + } + free(v); + --(contour->vertex_cnt); +} + +static void +clip_ear_with_edge_flag(GLUtriangulatorObj * tobj, + tess_vertex * v, tess_contour * contour) +{ + emit_triangle_with_edge_flag(tobj, v->previous, v->previous->edge_flag, + v, v->edge_flag, v->next, GL_FALSE); + v->previous->edge_flag = GL_FALSE; + /* the first in the list */ + if (contour->vertices == v) { + contour->vertices = v->next; + contour->last_vertex->next = v->next; + v->next->previous = contour->last_vertex; + } + else + /* the last ? */ + if (contour->last_vertex == v) { + contour->vertices->previous = v->previous; + v->previous->next = v->next; + contour->last_vertex = v->previous; + } + else { + v->next->previous = v->previous; + v->previous->next = v->next; + } + free(v); + --(contour->vertex_cnt); +} + +static void +triangulate_ccw(GLUtriangulatorObj * tobj, tess_contour * contour) +{ + tess_vertex *vertex; + GLuint vertex_cnt = contour->vertex_cnt; + + while (vertex_cnt > 3) { + vertex = contour->vertices; + while (diagonal_ccw(vertex, vertex->next->next, tobj, contour) == + GL_FALSE && tobj->error == GLU_NO_ERROR) + vertex = vertex->next; + if (tobj->error != GLU_NO_ERROR) + return; + clip_ear(tobj, vertex->next, contour); + --vertex_cnt; + } +} + +static void +triangulate_cw(GLUtriangulatorObj * tobj, tess_contour * contour) +{ + tess_vertex *vertex; + GLuint vertex_cnt = contour->vertex_cnt; + + while (vertex_cnt > 3) { + vertex = contour->vertices; + while (diagonal_cw(vertex, vertex->next->next, tobj, contour) == + GL_FALSE && tobj->error == GLU_NO_ERROR) + vertex = vertex->next; + if (tobj->error != GLU_NO_ERROR) + return; + clip_ear(tobj, vertex->next, contour); + --vertex_cnt; + } +} + +static void +triangulate_ccw_with_edge_flag(GLUtriangulatorObj * tobj, + tess_contour * contour) +{ + tess_vertex *vertex; + GLuint vertex_cnt = contour->vertex_cnt; + + while (vertex_cnt > 3) { + vertex = contour->vertices; + while (diagonal_ccw(vertex, vertex->next->next, tobj, contour) == + GL_FALSE && tobj->error == GLU_NO_ERROR) + vertex = vertex->next; + if (tobj->error != GLU_NO_ERROR) + return; + clip_ear_with_edge_flag(tobj, vertex->next, contour); + --vertex_cnt; + } +} + +static void +triangulate_cw_with_edge_flag(GLUtriangulatorObj * tobj, + tess_contour * contour) +{ + tess_vertex *vertex; + GLuint vertex_cnt = contour->vertex_cnt; + + while (vertex_cnt > 3) { + vertex = contour->vertices; + while (diagonal_cw(vertex, vertex->next->next, tobj, contour) == + GL_FALSE && tobj->error == GLU_NO_ERROR) + vertex = vertex->next; + if (tobj->error != GLU_NO_ERROR) + return; + clip_ear_with_edge_flag(tobj, vertex->next, contour); + --vertex_cnt; + } +} + +void +tess_tesselate(GLUtriangulatorObj * tobj) +{ + tess_contour *contour; + + for (contour = tobj->contours; contour != NULL; contour = contour->next) { + if (contour->orientation == GLU_CCW) { + triangulate_ccw(tobj, contour); + } + else { + triangulate_cw(tobj, contour); + } + if (tobj->error != GLU_NO_ERROR) + return; + + /* emit the last triangle */ + emit_triangle(tobj, contour->vertices, contour->vertices->next, + contour->vertices->next->next); + } +} + +void +tess_tesselate_with_edge_flag(GLUtriangulatorObj * tobj) +{ + tess_contour *contour; + + edge_flag = GL_TRUE; + /* first callback with edgeFlag set to GL_TRUE */ + (tobj->callbacks.edgeFlag) (GL_TRUE); + + for (contour = tobj->contours; contour != NULL; contour = contour->next) { + if (contour->orientation == GLU_CCW) + triangulate_ccw_with_edge_flag(tobj, contour); + else + triangulate_cw_with_edge_flag(tobj, contour); + if (tobj->error != GLU_NO_ERROR) + return; + /* emit the last triangle */ + emit_triangle_with_edge_flag(tobj, contour->vertices, + contour->vertices->edge_flag, + contour->vertices->next, + contour->vertices->next->edge_flag, + contour->vertices->next->next, + contour->vertices->next->next->edge_flag); + } +} + +static void +emit_triangle(GLUtriangulatorObj * tobj, + tess_vertex * v1, tess_vertex * v2, tess_vertex * v3) +{ + (tobj->callbacks.begin) (GL_TRIANGLES); + (tobj->callbacks.vertex) (v1->data); + (tobj->callbacks.vertex) (v2->data); + (tobj->callbacks.vertex) (v3->data); + (tobj->callbacks.end) (); +} + +static void +emit_triangle_with_edge_flag(GLUtriangulatorObj * tobj, + tess_vertex * v1, + GLboolean edge_flag1, + tess_vertex * v2, + GLboolean edge_flag2, + tess_vertex * v3, GLboolean edge_flag3) +{ + (tobj->callbacks.begin) (GL_TRIANGLES); + if (edge_flag1 != edge_flag) { + edge_flag = (edge_flag == GL_TRUE ? GL_FALSE : GL_TRUE); + (tobj->callbacks.edgeFlag) (edge_flag); + } + (tobj->callbacks.vertex) (v1->data); + if (edge_flag2 != edge_flag) { + edge_flag = (edge_flag == GL_TRUE ? GL_FALSE : GL_TRUE); + (tobj->callbacks.edgeFlag) (edge_flag); + } + (tobj->callbacks.vertex) (v2->data); + if (edge_flag3 != edge_flag) { + edge_flag = (edge_flag == GL_TRUE ? GL_FALSE : GL_TRUE); + (tobj->callbacks.edgeFlag) (edge_flag); + } + (tobj->callbacks.vertex) (v3->data); + (tobj->callbacks.end) (); +} |