diff options
Diffstat (limited to 'src/glu/mesa/tesselat.c')
| -rw-r--r-- | src/glu/mesa/tesselat.c | 456 |
1 files changed, 456 insertions, 0 deletions
diff --git a/src/glu/mesa/tesselat.c b/src/glu/mesa/tesselat.c new file mode 100644 index 00000000000..1e424c17ca7 --- /dev/null +++ b/src/glu/mesa/tesselat.c @@ -0,0 +1,456 @@ +/* $Id: tesselat.c,v 1.1 1999/08/19 00:55:42 jtg Exp $ */ + +/* + * Mesa 3-D graphics library + * Version: 2.4 + * Copyright (C) 1995-1997 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. + */ + + +/* + * $Log: tesselat.c,v $ + * Revision 1.1 1999/08/19 00:55:42 jtg + * Initial revision + * + * Revision 1.5 1997/07/24 01:28:44 brianp + * changed precompiled header symbol from PCH to PC_HEADER + * + * Revision 1.4 1997/05/28 02:29:38 brianp + * added support for precompiled headers (PCH), inserted APIENTRY keyword + * + * Revision 1.3 1997/02/17 17:24:58 brianp + * more tesselation changes (Randy Frank) + * + * Revision 1.2 1997/02/13 18:31:57 brianp + * fixed some numerical precision problems (Randy Frank) + * + * Revision 1.1 1996/09/27 01:19:39 brianp + * Initial revision + * + */ + + +/* + * 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)(); +} |