home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / Mesa-1.2.1 / src-glu / tesselat.c < prev   
Encoding:
C/C++ Source or Header  |  1995-07-05  |  9.4 KB  |  432 lines
  1. /* tesselat.c */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  1.2
  6.  * Copyright (C) 1995  Brian Paul  (brianp@ssec.wisc.edu)
  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. $Id: tesselat.c,v 1.4 1995/06/09 16:42:31 brianp Exp $
  26.  
  27. $Log: tesselat.c,v $
  28.  * Revision 1.4  1995/06/09  16:42:31  brianp
  29.  * renamed as tesselat.c
  30.  *
  31.  * Revision 1.3  1995/05/23  17:37:48  brianp
  32.  * added #ifndef NULL ...
  33.  *
  34.  * Revision 1.2  1995/05/22  16:56:20  brianp
  35.  * Release 1.2
  36.  *
  37.  * Revision 1.1  1995/04/28  16:21:08  brianp
  38.  * Initial revision
  39.  *
  40.  */
  41.  
  42.  
  43. /*
  44.  * This file is part of the polygon tesselation code contributed by
  45.  * Bogdan Sikorski
  46.  */
  47.  
  48.  
  49. #include "tess.h"
  50. #include <stdlib.h>
  51. #include <math.h>
  52.  
  53. #ifndef NULL
  54. #  define NULL 0
  55. #endif
  56.  
  57.  
  58. static GLboolean edge_flag;
  59.  
  60. static void emit_triangle(GLUtriangulatorObj *, tess_vertex *,
  61.     tess_vertex *,tess_vertex *);
  62.  
  63. static void emit_triangle_with_edge_flag(GLUtriangulatorObj *,
  64.      tess_vertex *,GLboolean,tess_vertex *,GLboolean,
  65.      tess_vertex *,GLboolean);
  66.  
  67. static GLdouble twice_the_triangle_area(
  68.     tess_vertex *va,
  69.     tess_vertex *vb,
  70.     tess_vertex *vc)
  71. {
  72.     return     (vb->x - va->x)*(vc->y - va->y) - (vb->y - va->y)*(vc->x - va->x);
  73. }
  74.  
  75. static GLboolean left(
  76.     GLdouble A,
  77.     GLdouble B,
  78.     GLdouble C,
  79.     GLdouble x,
  80.     GLdouble y)
  81. {
  82.     if(A*x+B*y+C > -EPSILON)
  83.         return GL_TRUE;
  84.     else
  85.         return GL_FALSE;
  86. }
  87.  
  88. static GLboolean right(
  89.     GLdouble A,
  90.     GLdouble B,
  91.     GLdouble C,
  92.     GLdouble x,
  93.     GLdouble y)
  94. {
  95.     if(A*x+B*y+C < EPSILON)
  96.         return GL_TRUE;
  97.     else
  98.         return GL_FALSE;
  99. }
  100.  
  101. static GLboolean convex_ccw(
  102.     tess_vertex *va,
  103.     tess_vertex *vb,
  104.     tess_vertex *vc,
  105.     GLUtriangulatorObj *tobj)
  106. {
  107.     if(twice_the_triangle_area(va,vb,vc) > EPSILON)
  108.         return GL_TRUE;
  109.     else
  110.         return GL_FALSE;
  111. }
  112.  
  113. static GLboolean convex_cw(
  114.     tess_vertex *va,
  115.     tess_vertex *vb,
  116.     tess_vertex *vc,
  117.     GLUtriangulatorObj *tobj)
  118. {
  119.     if(twice_the_triangle_area(va,vb,vc) < -EPSILON)
  120.         return GL_TRUE;
  121.     else
  122.         return GL_FALSE;
  123. }
  124.  
  125. static GLboolean diagonal_ccw(
  126.     tess_vertex *va,
  127.     tess_vertex *vb,
  128.     GLUtriangulatorObj *tobj,
  129.     tess_contour *contour)
  130. {
  131.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  132.     struct
  133.     {
  134.         GLdouble A,B,C;
  135.     } ac,cb,ba;
  136.     GLdouble x,y;
  137.  
  138.     if(convex_ccw(va,vc,vb,tobj)==GL_FALSE)
  139.         return GL_FALSE;
  140.     ba.A=vb->y - va->y;
  141.     ba.B=va->x - vb->x;
  142.     ba.C= -ba.A*va->x - ba.B*va->y;
  143.     ac.A=va->y - vc->y;
  144.     ac.B=vc->x - va->x;
  145.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  146.     cb.A=vc->y - vb->y;
  147.     cb.B=vb->x - vc->x;
  148.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  149.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  150.     {
  151.         shadow_vertex=vertex->shadow_vertex;
  152.         if(shadow_vertex!=NULL && 
  153.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  154.             continue;
  155.         x=vertex->x;
  156.         y=vertex->y;
  157.         if(left(ba.A,ba.B,ba.C,x,y) &&
  158.             left(ac.A,ac.B,ac.C,x,y) &&
  159.             left(cb.A,cb.B,cb.C,x,y))
  160.             return GL_FALSE;
  161.     }
  162.     return GL_TRUE;
  163. }
  164.  
  165. static GLboolean diagonal_cw(
  166.     tess_vertex *va,
  167.     tess_vertex *vb,
  168.     GLUtriangulatorObj *tobj,
  169.     tess_contour *contour)
  170. {
  171.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  172.     struct
  173.     {
  174.         GLdouble A,B,C;
  175.     } ac,cb,ba;
  176.     GLdouble x,y;
  177.  
  178.     if(convex_cw(va,vc,vb,tobj)==GL_FALSE)
  179.         return GL_FALSE;
  180.     ba.A=vb->y - va->y;
  181.     ba.B=va->x - vb->x;
  182.     ba.C= -ba.A*va->x - ba.B*va->y;
  183.     ac.A=va->y - vc->y;
  184.     ac.B=vc->x - va->x;
  185.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  186.     cb.A=vc->y - vb->y;
  187.     cb.B=vb->x - vc->x;
  188.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  189.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  190.     {
  191.         shadow_vertex=vertex->shadow_vertex;
  192.         if(shadow_vertex!=NULL && 
  193.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  194.             continue;
  195.         x=vertex->x;
  196.         y=vertex->y;
  197.         if(right(ba.A,ba.B,ba.C,x,y) &&
  198.             right(ac.A,ac.B,ac.C,x,y) &&
  199.             right(cb.A,cb.B,cb.C,x,y))
  200.             return GL_FALSE;
  201.     }
  202.     return GL_TRUE;
  203. }
  204.  
  205. static void clip_ear(
  206.     GLUtriangulatorObj *tobj,
  207.     tess_vertex *v,
  208.     tess_contour *contour)
  209. {
  210.     emit_triangle(tobj,v->previous,v,v->next);
  211.     /* the first in the list */
  212.     if(contour->vertices==v)
  213.     {
  214.         contour->vertices=v->next;
  215.         contour->last_vertex->next=v->next;
  216.         v->next->previous=contour->last_vertex;
  217.     }
  218.     else
  219.     /* the last ? */
  220.     if(contour->last_vertex==v)
  221.     {
  222.         contour->vertices->previous=v->previous;
  223.         v->previous->next=v->next;
  224.         contour->last_vertex=v->previous;
  225.     }
  226.     else
  227.     {
  228.         v->next->previous=v->previous;
  229.         v->previous->next=v->next;
  230.     }
  231.     free(v);
  232.     --(contour->vertex_cnt);
  233. }
  234.  
  235. static void clip_ear_with_edge_flag(
  236.     GLUtriangulatorObj *tobj,
  237.     tess_vertex *v,
  238.     tess_contour *contour)
  239. {
  240.     emit_triangle_with_edge_flag(tobj,v->previous,v->previous->edge_flag,
  241.         v,v->edge_flag,v->next,GL_FALSE);
  242.     v->previous->edge_flag=GL_FALSE;
  243.     /* the first in the list */
  244.     if(contour->vertices==v)
  245.     {
  246.         contour->vertices=v->next;
  247.         contour->last_vertex->next=v->next;
  248.         v->next->previous=contour->last_vertex;
  249.     }
  250.     else
  251.     /* the last ? */
  252.     if(contour->last_vertex==v)
  253.     {
  254.         contour->vertices->previous=v->previous;
  255.         v->previous->next=v->next;
  256.         contour->last_vertex=v->previous;
  257.     }
  258.     else
  259.     {
  260.         v->next->previous=v->previous;
  261.         v->previous->next=v->next;
  262.     }
  263.     free(v);
  264.     --(contour->vertex_cnt);
  265. }
  266.  
  267. static void triangulate_ccw(
  268.     GLUtriangulatorObj *tobj,
  269.     tess_contour *contour)
  270. {
  271.     tess_vertex *vertex;
  272.     GLuint vertex_cnt=contour->vertex_cnt;
  273.  
  274.     while(vertex_cnt > 3)
  275.     {
  276.         vertex=contour->vertices;
  277.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  278.             tobj->error==GLU_NO_ERROR)
  279.             vertex=vertex->next;
  280.         if(tobj->error!=GLU_NO_ERROR)
  281.             return;
  282.         clip_ear(tobj,vertex->next,contour);
  283.         --vertex_cnt;
  284.     }
  285. }
  286.  
  287. static void triangulate_cw(
  288.     GLUtriangulatorObj *tobj,
  289.     tess_contour *contour)
  290. {
  291.     tess_vertex *vertex;
  292.     GLuint vertex_cnt=contour->vertex_cnt;
  293.  
  294.     while(vertex_cnt > 3)
  295.     {
  296.         vertex=contour->vertices;
  297.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  298.             tobj->error==GLU_NO_ERROR)
  299.             vertex=vertex->next;
  300.         if(tobj->error!=GLU_NO_ERROR)
  301.             return;
  302.         clip_ear(tobj,vertex->next,contour);
  303.         --vertex_cnt;
  304.     }
  305. }
  306.  
  307. static void triangulate_ccw_with_edge_flag(
  308.     GLUtriangulatorObj *tobj,
  309.     tess_contour *contour)
  310. {
  311.     tess_vertex *vertex;
  312.     GLuint vertex_cnt=contour->vertex_cnt;
  313.  
  314.     while(vertex_cnt > 3)
  315.     {
  316.         vertex=contour->vertices;
  317.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  318.             tobj->error==GLU_NO_ERROR)
  319.             vertex=vertex->next;
  320.         if(tobj->error!=GLU_NO_ERROR)
  321.             return;
  322.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  323.         --vertex_cnt;
  324.     }
  325. }
  326.  
  327. static void triangulate_cw_with_edge_flag(
  328.     GLUtriangulatorObj *tobj,
  329.     tess_contour *contour)
  330. {
  331.     tess_vertex *vertex;
  332.     GLuint vertex_cnt=contour->vertex_cnt;
  333.  
  334.     while(vertex_cnt > 3)
  335.     {
  336.         vertex=contour->vertices;
  337.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  338.             tobj->error==GLU_NO_ERROR)
  339.             vertex=vertex->next;
  340.         if(tobj->error!=GLU_NO_ERROR)
  341.             return;
  342.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  343.         --vertex_cnt;
  344.     }
  345. }
  346.  
  347. void tess_tesselate(GLUtriangulatorObj *tobj)
  348. {
  349.     tess_contour *contour;
  350.  
  351.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  352.     {
  353.         if(contour->orientation==GLU_CCW)
  354.             triangulate_ccw(tobj,contour);
  355.         else
  356.             triangulate_cw(tobj,contour);
  357.         if(tobj->error!=GLU_NO_ERROR)
  358.             return;
  359.         /* emit the last triangle */
  360.         emit_triangle(tobj,contour->vertices,contour->vertices->next,
  361.             contour->vertices->next->next);
  362.     }
  363. }
  364.  
  365. void tess_tesselate_with_edge_flag(GLUtriangulatorObj *tobj)
  366. {
  367.     tess_contour *contour;
  368.  
  369.     edge_flag=GL_TRUE;
  370.     /* first callback with edgeFlag set to GL_TRUE */
  371.     (tobj->callbacks.edgeFlag)(GL_TRUE);
  372.  
  373.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  374.     {
  375.         if(contour->orientation==GLU_CCW)
  376.             triangulate_ccw_with_edge_flag(tobj,contour);
  377.         else
  378.             triangulate_cw_with_edge_flag(tobj,contour);
  379.         if(tobj->error!=GLU_NO_ERROR)
  380.             return;
  381.         /* emit the last triangle */
  382.         emit_triangle_with_edge_flag(tobj,contour->vertices,
  383.             contour->vertices->edge_flag,contour->vertices->next,
  384.             contour->vertices->next->edge_flag,contour->vertices->next->next,
  385.             contour->vertices->next->next->edge_flag);
  386.     }
  387. }
  388.  
  389. static void emit_triangle(
  390.     GLUtriangulatorObj *tobj,
  391.     tess_vertex *v1,
  392.     tess_vertex *v2,
  393.     tess_vertex *v3)
  394. {
  395.     (tobj->callbacks.begin)(GL_TRIANGLES);
  396.     (tobj->callbacks.vertex)(v1->data);
  397.     (tobj->callbacks.vertex)(v2->data);
  398.     (tobj->callbacks.vertex)(v3->data);
  399.     (tobj->callbacks.end)();
  400. }
  401.  
  402. static void emit_triangle_with_edge_flag(
  403.     GLUtriangulatorObj *tobj,
  404.     tess_vertex *v1,
  405.     GLboolean edge_flag1,
  406.     tess_vertex *v2,
  407.     GLboolean edge_flag2,
  408.     tess_vertex *v3,
  409.     GLboolean edge_flag3)
  410. {
  411.     (tobj->callbacks.begin)(GL_TRIANGLES);
  412.     if(edge_flag1!=edge_flag)
  413.     {
  414.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  415.         (tobj->callbacks.edgeFlag)(edge_flag);
  416.     }
  417.     (tobj->callbacks.vertex)(v1->data);
  418.     if(edge_flag2!=edge_flag)
  419.     {
  420.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  421.         (tobj->callbacks.edgeFlag)(edge_flag);
  422.     }
  423.     (tobj->callbacks.vertex)(v2->data);
  424.     if(edge_flag3!=edge_flag)
  425.     {
  426.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  427.         (tobj->callbacks.edgeFlag)(edge_flag);
  428.     }
  429.     (tobj->callbacks.vertex)(v3->data);
  430.     (tobj->callbacks.end)();
  431. }
  432.