home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 5 / MA_Cover_5.iso / ppc / mesa / src-glu / polytest.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-01-31  |  26.4 KB  |  1,041 lines
  1. /* $Id: polytest.c,v 1.5 1997/10/29 02:02:20 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.4
  6.  * Copyright (C) 1995-1997  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.  * $Log: polytest.c,v $
  26.  * Revision 1.5  1997/10/29 02:02:20  brianp
  27.  * various MS Windows compiler changes (David Bucciarelli, v20 3dfx driver)
  28.  *
  29.  * Revision 1.4  1997/07/24 01:28:44  brianp
  30.  * changed precompiled header symbol from PCH to PC_HEADER
  31.  *
  32.  * Revision 1.3  1997/05/28 02:29:38  brianp
  33.  * added support for precompiled headers (PCH), inserted APIENTRY keyword
  34.  *
  35.  * Revision 1.2  1997/05/08 01:53:21  brianp
  36.  * fixed memory leak in free_current_polygon() reported by Randy Frank
  37.  *
  38.  * Revision 1.1  1996/09/27 01:19:39  brianp
  39.  * Initial revision
  40.  *
  41.  */
  42.  
  43.  
  44. /*
  45.  * This file is part of the polygon tesselation code contributed by
  46.  * Bogdan Sikorski
  47.  */
  48.  
  49.  
  50. #ifdef PC_HEADER
  51. #include "all.h"
  52. #else
  53. #include <math.h>
  54. #include <stdlib.h>
  55. #include "gluP.h"
  56. #include "tess.h"
  57. #endif
  58.  
  59.  
  60.  
  61. static GLenum store_polygon_as_contour(GLUtriangulatorObj *);
  62. static void free_current_polygon(tess_polygon *);
  63. static void prepare_projection_info(GLUtriangulatorObj *);
  64. static GLdouble twice_the_polygon_area(tess_vertex *,tess_vertex *);
  65. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
  66. void tess_find_contour_hierarchies(GLUtriangulatorObj *);
  67. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *);
  68. static GLenum contours_overlap(tess_contour *, tess_polygon *);
  69. static GLenum is_contour_contained_in(tess_contour *,tess_contour *);
  70. static void add_new_exterior(GLUtriangulatorObj *,tess_contour *);
  71. static void add_new_interior(GLUtriangulatorObj *,tess_contour *,
  72.     tess_contour *);
  73. static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
  74.     tess_contour *,tess_contour *);
  75. static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
  76.     tess_contour *,tess_contour *);
  77. static GLboolean point_in_polygon(tess_contour *,GLdouble,GLdouble);
  78. static void shift_interior_to_exterior(GLUtriangulatorObj *,tess_contour *);
  79. static void add_exterior_with_check(GLUtriangulatorObj *,tess_contour *,
  80.     tess_contour *);
  81. static GLenum cut_out_hole(GLUtriangulatorObj *,tess_contour *,
  82.     tess_contour *);
  83. static GLenum merge_hole_with_contour(GLUtriangulatorObj *,
  84.     tess_contour *,tess_contour *,tess_vertex *,
  85.     tess_vertex *);
  86.  
  87. static GLenum
  88. find_normal(GLUtriangulatorObj *tobj)
  89. {
  90.     tess_polygon *polygon=tobj->current_polygon;
  91.     tess_vertex *va,*vb,*vc;
  92.     GLdouble A,B,C;
  93.     GLdouble A0,A1,A2,B0,B1,B2;
  94.  
  95.     va=polygon->vertices;
  96.     vb=va->next;
  97.     A0=vb->location[0]-va->location[0];
  98.     A1=vb->location[1]-va->location[1];
  99.     A2=vb->location[2]-va->location[2];
  100.     for(vc=vb->next;vc!=va;vc=vc->next)
  101.     {
  102.         B0=vc->location[0]-va->location[0];
  103.         B1=vc->location[1]-va->location[1];
  104.         B2=vc->location[2]-va->location[2];
  105.         A=A1*B2-A2*B1;
  106.         B=A2*B0-A0*B2;
  107.         C=A0*B1-A1*B0;
  108.         if(fabs(A)>EPSILON || fabs(B)>EPSILON || fabs(C)>EPSILON)
  109.         {
  110.             polygon->A=A;
  111.             polygon->B=B;
  112.             polygon->C=C;
  113.             polygon->D= -A*va->location[0]-B*va->location[1]-C*va->location[2];
  114.             return GLU_NO_ERROR;
  115.         }
  116.     }
  117.     tess_call_user_error(tobj,GLU_TESS_ERROR7);
  118.     return GLU_ERROR;
  119. }
  120.  
  121. void
  122. tess_test_polygon( GLUtriangulatorObj *tobj )
  123. {
  124.     tess_polygon *polygon=tobj->current_polygon;
  125.  
  126.     /* any vertices defined? */
  127.     if(polygon->vertex_cnt<3)
  128.     {
  129.         free_current_polygon(polygon);
  130.         return;
  131.     }
  132.     /* wrap pointers */
  133.     polygon->last_vertex->next=polygon->vertices;
  134.     polygon->vertices->previous=polygon->last_vertex;
  135.     /* determine the normal */
  136.     if(find_normal(tobj)==GLU_ERROR)
  137.         return;
  138.     /* compare the normals of previously defined contours and this one */
  139.     /* first contour define ? */
  140.     if(tobj->contours==NULL)
  141.     {
  142.         tobj->A=polygon->A;
  143.         tobj->B=polygon->B;
  144.         tobj->C=polygon->C;
  145.         tobj->D=polygon->D;
  146.         /* determine the best projection to use */
  147.         if(fabs(polygon->A) > fabs(polygon->B))
  148.             if(fabs(polygon->A) > fabs(polygon->C))
  149.                 tobj->projection=OYZ;
  150.             else
  151.                 tobj->projection=OXY;
  152.         else
  153.             if(fabs(polygon->B) > fabs(polygon->C))
  154.                 tobj->projection=OXZ;
  155.             else
  156.                 tobj->projection=OXY;
  157.     }
  158.     else
  159.     {
  160.         GLdouble a[3],b[3];
  161.         tess_vertex *vertex=polygon->vertices;
  162.  
  163.         a[0]=tobj->A;
  164.         a[1]=tobj->B;
  165.         a[2]=tobj->C;
  166.         b[0]=polygon->A;
  167.         b[1]=polygon->B;
  168.         b[2]=polygon->C;
  169.  
  170.         /* compare the normals */
  171.         if( fabs(a[1]*b[2]-a[2]*b[1]) > EPSILON ||
  172.             fabs(a[2]*b[0]-a[0]*b[2]) > EPSILON ||
  173.             fabs(a[0]*b[1]-a[1]*b[0]) > EPSILON)
  174.         {
  175.             /* not coplanar */
  176.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  177.             return;
  178.         }
  179.         /* the normals are parallel - test for plane equation */
  180.         if(fabs(a[0]*vertex->location[0]+a[1]*vertex->location[1]+
  181.             a[2]*vertex->location[2]+tobj->D) > EPSILON)
  182.         {
  183.             /* not the same plane */
  184.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  185.             return;
  186.         }
  187.     }
  188.     prepare_projection_info(tobj);
  189.     if(verify_edge_vertex_intersections(tobj)==GLU_ERROR)
  190.         return;
  191.     if(test_for_overlapping_contours(tobj)==GLU_ERROR)
  192.         return;
  193.     if(store_polygon_as_contour(tobj)==GLU_ERROR)
  194.         return;
  195. }
  196.  
  197. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *tobj)
  198. {
  199.     tess_contour *contour;
  200.     tess_polygon *polygon;
  201.  
  202.     polygon=tobj->current_polygon;
  203.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  204.         if(contours_overlap(contour,polygon)!=GLU_NO_ERROR)
  205.         {
  206.             tess_call_user_error(tobj,GLU_TESS_ERROR5);
  207.             return GLU_ERROR;
  208.         }
  209.     return GLU_NO_ERROR;
  210. }
  211.  
  212. static GLenum store_polygon_as_contour(GLUtriangulatorObj *tobj)
  213. {
  214.     tess_polygon *polygon=tobj->current_polygon;
  215.     tess_contour *contour=tobj->contours;
  216.  
  217.     /* the first contour defined */
  218.     if(contour==NULL)
  219.     {
  220.         if((contour=(tess_contour *)malloc(
  221.             sizeof(tess_contour)))==NULL)
  222.         {
  223.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  224.             free_current_polygon(polygon);
  225.             return GLU_ERROR;
  226.         }
  227.         tobj->contours=tobj->last_contour=contour;
  228.         contour->next=contour->previous=NULL;
  229.     }
  230.     else
  231.     {
  232.         if((contour=(tess_contour *)malloc(
  233.             sizeof(tess_contour)))==NULL)
  234.         {
  235.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  236.             free_current_polygon(polygon);
  237.             return GLU_ERROR;
  238.         }
  239.         contour->previous=tobj->last_contour;
  240.         tobj->last_contour->next=contour;
  241.         tobj->last_contour=contour;
  242.         contour->next=NULL;
  243.     }
  244.     /* mark all vertices in new contour as not special */
  245.     /* and all are boundary edges */
  246.     {
  247.         tess_vertex *vertex;
  248.         GLuint vertex_cnt,i;
  249.  
  250.         for(vertex=polygon->vertices , i=0 , vertex_cnt=polygon->vertex_cnt;
  251.             i<vertex_cnt;
  252.             vertex=vertex->next , i++)
  253.         {
  254.             vertex->shadow_vertex=NULL;
  255.             vertex->edge_flag=GL_TRUE;
  256.         }
  257.     }
  258.     contour->vertex_cnt=polygon->vertex_cnt;
  259.     contour->area=polygon->area;
  260.     contour->orientation=polygon->orientation;
  261.     contour->type=GLU_UNKNOWN;
  262.     contour->vertices=polygon->vertices;
  263.     contour->last_vertex=polygon->last_vertex;
  264.     polygon->vertices=polygon->last_vertex=NULL;
  265.     polygon->vertex_cnt=0;
  266.     ++(tobj->contour_cnt);
  267.     return GLU_NO_ERROR;
  268. }
  269.  
  270. static void free_current_polygon(tess_polygon *polygon)
  271. {
  272.     tess_vertex *vertex,*vertex_tmp;
  273.     GLuint    i;
  274.  
  275.     /* free current_polygon structures */
  276.     for(vertex=polygon->vertices,i=0;i<polygon->vertex_cnt;i++)
  277.     {
  278.         vertex_tmp=vertex->next;
  279.         free(vertex);
  280.         vertex=vertex_tmp;
  281.     }
  282.     polygon->vertices=polygon->last_vertex=NULL;
  283.     polygon->vertex_cnt=0;
  284. }
  285.  
  286. static void prepare_projection_info(GLUtriangulatorObj *tobj)
  287. {
  288.     tess_polygon *polygon=tobj->current_polygon;
  289.     tess_vertex *vertex,*last_vertex_ptr;
  290.     GLdouble area;
  291.  
  292.     last_vertex_ptr=polygon->last_vertex;
  293.     switch(tobj->projection)
  294.     {
  295.         case OXY:
  296.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  297.                 vertex=vertex->next)
  298.             {
  299.                 vertex->x=vertex->location[0];
  300.                 vertex->y=vertex->location[1];
  301.             }
  302.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  303.             last_vertex_ptr->y=last_vertex_ptr->location[1];
  304.             break;
  305.         case OXZ:
  306.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  307.                 vertex=vertex->next)
  308.             {
  309.                 vertex->x=vertex->location[0];
  310.                 vertex->y=vertex->location[2];
  311.             }
  312.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  313.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  314.             break;
  315.         case OYZ:
  316.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  317.                 vertex=vertex->next)
  318.             {
  319.                 vertex->x=vertex->location[1];
  320.                 vertex->y=vertex->location[2];
  321.             }
  322.             last_vertex_ptr->x=last_vertex_ptr->location[1];
  323.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  324.             break;
  325.     }
  326.     area=twice_the_polygon_area(polygon->vertices,polygon->last_vertex);
  327.     if(area >= 0.0)
  328.     {
  329.         polygon->orientation=GLU_CCW;
  330.         polygon->area=area;
  331.     }
  332.     else
  333.     {
  334.         polygon->orientation=GLU_CW;
  335.         polygon->area= -area;
  336.     }
  337. }
  338.  
  339. static GLdouble twice_the_polygon_area(tess_vertex *vertex,
  340.     tess_vertex *last_vertex)
  341. {
  342.     tess_vertex *next;
  343.     GLdouble area,x,y;
  344.  
  345.     area=0.0;
  346.     x=vertex->x;
  347.     y=vertex->y;
  348.     vertex=vertex->next;
  349.     for(; vertex!=last_vertex; vertex=vertex->next)
  350.     {
  351.         next=vertex->next;
  352.         area+=(vertex->x - x)*(next->y - y) - (vertex->y - y)*(next->x - x);
  353.     }
  354.     return area;
  355. }
  356.  
  357. /* test if edges ab and cd intersect */
  358. /* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
  359. /* else if adjacent return GLU_TESS_ERROR4 */
  360. static GLenum edge_edge_intersect(
  361.     tess_vertex *a,
  362.     tess_vertex *b,
  363.     tess_vertex *c,
  364.     tess_vertex *d)
  365. {
  366.     GLdouble denom,r,s;
  367.     GLdouble xba,ydc,yba,xdc,yac,xac;
  368.  
  369.     xba=b->x - a->x;
  370.     yba=b->y - a->y;
  371.     xdc=d->x - c->x;
  372.     ydc=d->y - c->y;
  373.     xac=a->x - c->x;
  374.     yac=a->y - c->y;
  375.     denom= xba*ydc - yba*xdc;
  376.     r = yac*xdc - xac*ydc;
  377.     /* parallel? */
  378.     if(fabs(denom) < EPSILON)
  379.     {
  380.         if(fabs(r) < EPSILON)
  381.         {
  382.             /* colinear */
  383.             if(fabs(xba) < EPSILON)
  384.             {
  385.                 /* compare the Y coordinate */
  386.                 if(yba > 0.0)
  387.                 {
  388.                     if((fabs(a->y - c->y)<EPSILON && fabs(c->y - b->y)<EPSILON)
  389.                         ||
  390.                         (fabs(a->y - d->y)<EPSILON && fabs(d->y - b->y)<EPSILON))
  391.                     return GLU_TESS_ERROR4;
  392.  
  393.                 }
  394.                 else
  395.                 {
  396.                     if((fabs(b->y - c->y)<EPSILON && fabs(c->y - a->y)<EPSILON)
  397.                         ||
  398.                         (fabs(b->y - d->y)<EPSILON && fabs(d->y - a->y)<EPSILON))
  399.                     return GLU_TESS_ERROR4;
  400.                 }
  401.             }
  402.             else
  403.             {
  404.                 /* compare the X coordinate */
  405.                 if(xba > 0.0)
  406.                 {
  407.                     if((fabs(a->x - c->x)<EPSILON && fabs(c->x - b->x)<EPSILON)
  408.                         ||
  409.                         (fabs(a->x - d->x)<EPSILON && fabs(d->x - b->x)<EPSILON))
  410.                     return GLU_TESS_ERROR4;
  411.                 }
  412.                 else
  413.                 {
  414.                     if((fabs(b->x - c->x)<EPSILON && fabs(c->x - a->x)<EPSILON)
  415.                         ||
  416.                         (fabs(b->x - d->x)<EPSILON && fabs(d->x - a->x)<EPSILON))
  417.                     return GLU_TESS_ERROR4;
  418.                 }
  419.             }
  420.         }
  421.         return GLU_NO_ERROR;
  422.     }
  423.     r /= denom;
  424.     s = (yac*xba - xac*yba) / denom;
  425.     /* test if one vertex lies on other edge */
  426.     if(((fabs(r) < EPSILON || (r < 1.0+EPSILON && r > 1.0-EPSILON)) &&
  427.         s > -EPSILON && s < 1.0+EPSILON) ||
  428.         ((fabs(s) < EPSILON || (s < 1.0+EPSILON && s > 1.0-EPSILON)) &&
  429.         r > -EPSILON && r < 1.0+EPSILON))
  430.     {
  431.         return GLU_TESS_ERROR4;
  432.     }
  433.     /* test for crossing */
  434.     if(r > -EPSILON && r < 1.0+EPSILON &&
  435.         s > -EPSILON && s < 1.0+EPSILON)
  436.     {
  437.         return GLU_TESS_ERROR8;
  438.     }
  439.     return GLU_NO_ERROR;
  440. }
  441.  
  442. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *tobj)
  443. {
  444.     tess_polygon *polygon=tobj->current_polygon;
  445.     tess_vertex *vertex1,*last_vertex,*vertex2;
  446.     GLenum test;
  447.  
  448.     last_vertex=polygon->last_vertex;
  449.     vertex1=last_vertex;
  450.     for(vertex2=vertex1->next->next;
  451.         vertex2->next!=last_vertex;
  452.         vertex2=vertex2->next)
  453.     {
  454.         test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  455.             vertex2->next);
  456.         if(test!=GLU_NO_ERROR)
  457.         {
  458.             tess_call_user_error(tobj,test);
  459.             return GLU_ERROR;
  460.         }
  461.     }
  462.     for(vertex1=polygon->vertices;
  463.         vertex1->next->next!=last_vertex;
  464.         vertex1=vertex1->next)
  465.     {
  466.         for(vertex2=vertex1->next->next;
  467.             vertex2!=last_vertex;
  468.             vertex2=vertex2->next)
  469.         {
  470.             test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  471.                 vertex2->next);
  472.             if(test!=GLU_NO_ERROR)
  473.             {
  474.                 tess_call_user_error(tobj,test);
  475.                 return GLU_ERROR;
  476.             }
  477.         }
  478.     }
  479.     return GLU_NO_ERROR;
  480. }
  481.  
  482. static int
  483. #if defined(FX) && defined(__WIN32__)
  484. _cdecl
  485. #endif
  486. area_compare(const void *a,const void *b)
  487. {
  488.     GLdouble area1,area2;
  489.  
  490.     area1=(*((tess_contour **)a))->area;
  491.     area2=(*((tess_contour **)b))->area;
  492.     if(area1 < area2)
  493.         return 1;
  494.     if(area1 > area2)
  495.         return -1;
  496.     return 0;
  497. }
  498.  
  499. void tess_find_contour_hierarchies(GLUtriangulatorObj *tobj)
  500. {
  501.     tess_contour **contours; /* dinamic array of pointers */
  502.     tess_contour *tmp_contour_ptr=tobj->contours;
  503.     GLuint cnt,i;
  504.     GLenum result;
  505.     GLboolean hierarchy_changed;
  506.  
  507.     /* any contours? */
  508.     if(tobj->contour_cnt < 2)
  509.     {
  510.         tobj->contours->type=GLU_EXTERIOR;
  511.         return;
  512.     }
  513.     if((contours=(tess_contour **)
  514.         malloc(sizeof(tess_contour *)*(tobj->contour_cnt)))==NULL)
  515.     {
  516.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  517.         return;
  518.     }
  519.     for(tmp_contour_ptr=tobj->contours , cnt=0;
  520.         tmp_contour_ptr!=NULL;
  521.         tmp_contour_ptr=tmp_contour_ptr->next)
  522.         contours[cnt++]=tmp_contour_ptr;
  523.     /* now sort the contours in decreasing area size order */
  524.     qsort((void *)contours,(size_t)cnt,(size_t)sizeof(tess_contour *),area_compare);
  525.     /* we leave just the first contour - remove others from list */
  526.     tobj->contours=contours[0];
  527.     tobj->contours->next=tobj->contours->previous=NULL;
  528.     tobj->last_contour=tobj->contours;
  529.     tobj->contour_cnt=1;
  530.     /* first contour is the one with greatest area */
  531.     /* must be EXTERIOR */
  532.     tobj->contours->type=GLU_EXTERIOR;
  533.     tmp_contour_ptr=tobj->contours;
  534.     /* now we play! */
  535.     for(i=1;i<cnt;i++)
  536.     {
  537.         hierarchy_changed=GL_FALSE;
  538.         for(tmp_contour_ptr=tobj->contours;
  539.             tmp_contour_ptr!=NULL;
  540.             tmp_contour_ptr=tmp_contour_ptr->next)
  541.         {
  542.             if(tmp_contour_ptr->type==GLU_EXTERIOR)
  543.             {
  544.                 /* check if contour completely contained in EXTERIOR */
  545.                 result=is_contour_contained_in(tmp_contour_ptr,contours[i]);
  546.                 switch(result)
  547.                 {
  548.                     case GLU_INTERIOR:
  549.                         /* now we have to check if contour is inside interiors */
  550.                         /* or not */
  551.                         /* any interiors? */
  552.                         if(tmp_contour_ptr->next!=NULL &&
  553.                             tmp_contour_ptr->next->type==GLU_INTERIOR)
  554.                         {
  555.                             /* for all interior, check if inside any of them */
  556.                             /* if not inside any of interiors, its another */
  557.                             /* interior */
  558.                             /* or it may contain some interiors, then change */
  559.                             /* the contained interiors to exterior ones */
  560.                             add_interior_with_hierarchy_check(tobj,
  561.                                 tmp_contour_ptr,contours[i]);
  562.                         }
  563.                         else
  564.                         {
  565.                             /* not in interior, add as new interior contour */
  566.                             add_new_interior(tobj,tmp_contour_ptr,contours[i]);
  567.                         }
  568.                         hierarchy_changed=GL_TRUE;
  569.                         break;
  570.                     case GLU_EXTERIOR:
  571.                         /* ooops, the marked as EXTERIOR (contours[i]) is */
  572.                         /* actually an interior of tmp_contour_ptr */
  573.                         /*  reverse the local hierarchy */
  574.                         reverse_hierarchy_and_add_exterior(tobj,tmp_contour_ptr,
  575.                             contours[i]);
  576.                         hierarchy_changed=GL_TRUE;
  577.                         break;
  578.                     case GLU_NO_ERROR:
  579.                         break;
  580.                     default:
  581.                         abort();
  582.                 }
  583.             }
  584.             if(hierarchy_changed)
  585.                 break; /* break from for loop */
  586.         }
  587.         if(hierarchy_changed==GL_FALSE)
  588.         {
  589.             /* disjoint with all contours, add to contour list */
  590.             add_new_exterior(tobj,contours[i]);
  591.         }
  592.     }
  593.     free(contours);
  594. }
  595.  
  596. /* returns GLU_INTERIOR if inner is completey enclosed within outer */
  597. /* returns GLU_EXTERIOR if outer is completely enclosed within inner */
  598. /* returns GLU_NO_ERROR if contours are disjoint */
  599. static GLenum is_contour_contained_in(
  600.     tess_contour *outer,
  601.     tess_contour *inner)
  602. {
  603.     GLenum relation_flag;
  604.  
  605.     /* set relation_flag to relation of containment of first inner vertex */
  606.     /* regarding outer contour */
  607.     if(point_in_polygon(outer,inner->vertices->x,inner->vertices->y))
  608.         relation_flag=GLU_INTERIOR;
  609.     else
  610.         relation_flag=GLU_EXTERIOR;
  611.     if(relation_flag==GLU_INTERIOR)
  612.         return GLU_INTERIOR;
  613.     if(point_in_polygon(inner,outer->vertices->x,outer->vertices->y))
  614.         return GLU_EXTERIOR;
  615.     return GLU_NO_ERROR;
  616. }
  617.  
  618. static GLboolean point_in_polygon(
  619.     tess_contour *contour,
  620.     GLdouble x,
  621.     GLdouble y)
  622. {
  623.     tess_vertex *v1,*v2;
  624.     GLuint i,vertex_cnt;
  625.     GLdouble xp1,yp1,xp2,yp2;
  626.     GLboolean tst;
  627.  
  628.     tst=GL_FALSE;
  629.     v1=contour->vertices;
  630.     v2=contour->vertices->previous;
  631.     for(i=0 , vertex_cnt=contour->vertex_cnt;
  632.         i < vertex_cnt;
  633.         i++)
  634.     {
  635.         xp1=v1->x;
  636.         yp1=v1->y;
  637.         xp2=v2->x;
  638.         yp2=v2->y;
  639.         if ((((yp1<=y) && (y<yp2)) || ((yp2<=y)  && (y<yp1))) &&
  640.             (x < (xp2 - xp1) * (y - yp1) /  (yp2 - yp1) + xp1))
  641.                 tst = (tst==GL_FALSE ? GL_TRUE : GL_FALSE);
  642.         v2=v1;
  643.         v1=v1->next;
  644.     }
  645.     return tst;
  646. }
  647.  
  648. static GLenum contours_overlap(
  649.     tess_contour *contour,
  650.     tess_polygon *polygon)
  651. {
  652.     tess_vertex *vertex1,*vertex2;
  653.     GLuint vertex1_cnt,vertex2_cnt,i,j;
  654.     GLenum test;
  655.  
  656.     vertex1=contour->vertices;
  657.     vertex2=polygon->vertices;
  658.     vertex1_cnt=contour->vertex_cnt;
  659.     vertex2_cnt=polygon->vertex_cnt;
  660.     for(i=0; i<vertex1_cnt; vertex1=vertex1->next , i++)
  661.     {
  662.         for(j=0; j<vertex2_cnt; vertex2=vertex2->next , j++)
  663.             if((test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  664.                 vertex2->next))!=GLU_NO_ERROR)
  665.                 return test;
  666.     }
  667.     return GLU_NO_ERROR;
  668. }
  669.  
  670. static void add_new_exterior(
  671.     GLUtriangulatorObj *tobj,
  672.     tess_contour *contour)
  673. {
  674.     contour->type=GLU_EXTERIOR;
  675.     contour->next=NULL;
  676.     contour->previous=tobj->last_contour;
  677.     tobj->last_contour->next=contour;
  678.     tobj->last_contour=contour;
  679. }
  680.  
  681. static void add_new_interior(
  682.     GLUtriangulatorObj *tobj,
  683.     tess_contour *outer,
  684.     tess_contour *contour)
  685. {
  686.     contour->type=GLU_INTERIOR;
  687.     contour->next=outer->next;
  688.     contour->previous=outer;
  689.     if(outer->next!=NULL)
  690.         outer->next->previous=contour;
  691.     outer->next=contour;
  692.     if(tobj->last_contour==outer)
  693.         tobj->last_contour=contour;
  694. }
  695.  
  696. static void add_interior_with_hierarchy_check(
  697.     GLUtriangulatorObj *tobj,
  698.     tess_contour *outer,
  699.     tess_contour *contour)
  700. {
  701.     tess_contour *ptr;
  702.  
  703.     /* for all interiors of outer check if they are interior of contour */
  704.     /* if so, change that interior to exterior and move it of of the */
  705.     /* interior sequence */
  706.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  707.     {
  708.         GLenum test;
  709.  
  710.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  711.         {
  712.             test=is_contour_contained_in(ptr,contour);
  713.             switch(test)
  714.             {
  715.                 case GLU_INTERIOR:
  716.                     /* contour is contained in one of the interiors */
  717.                     /* check if possibly contained in other exteriors */
  718.                     /* move ptr to first EXTERIOR */
  719.                     for(;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next);
  720.                     if(ptr==NULL)
  721.                         /* another exterior */
  722.                         add_new_exterior(tobj,contour);
  723.                     else
  724.                         add_exterior_with_check(tobj,ptr,contour);
  725.                     return;
  726.                 case GLU_EXTERIOR:
  727.                     /* one of the interiors is contained in the contour */
  728.                     /* change it to EXTERIOR, and shift it away from the */
  729.                     /* interior sequence */
  730.                     shift_interior_to_exterior(tobj,ptr);
  731.                     break;
  732.                 case GLU_NO_ERROR:
  733.                     /* disjoint */
  734.                     break;
  735.                 default:
  736.                     abort();
  737.             }
  738.         }
  739.     }
  740.     /* add contour to the interior sequence */
  741.     add_new_interior(tobj,outer,contour);
  742. }
  743.  
  744. static void reverse_hierarchy_and_add_exterior(
  745.     GLUtriangulatorObj *tobj,
  746.     tess_contour *outer,
  747.     tess_contour *contour)
  748. {
  749.     tess_contour *ptr;
  750.  
  751.     /* reverse INTERIORS to EXTERIORS */
  752.     /* any INTERIORS? */
  753.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  754.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  755.             ptr->type=GLU_EXTERIOR;
  756.     /* the outer now becomes inner */
  757.     outer->type=GLU_INTERIOR;
  758.     /* contour is the EXTERIOR */
  759.     contour->next=outer;
  760.     if(tobj->contours==outer)
  761.     {
  762.         /* first contour beeing reversed */
  763.         contour->previous=NULL;
  764.         tobj->contours=contour;
  765.     }
  766.     else
  767.     {
  768.         outer->previous->next=contour;
  769.         contour->previous=outer->previous;
  770.     }
  771.     outer->previous=contour;
  772. }
  773.  
  774. static void shift_interior_to_exterior(
  775.     GLUtriangulatorObj *tobj,
  776.     tess_contour *contour)
  777. {
  778.     contour->previous->next=contour->next;
  779.     if(contour->next!=NULL)
  780.         contour->next->previous=contour->previous;
  781.     else
  782.         tobj->last_contour=contour->previous;
  783. }
  784.  
  785. static void add_exterior_with_check(
  786.     GLUtriangulatorObj *tobj,
  787.     tess_contour *outer,
  788.     tess_contour *contour)
  789. {
  790.     GLenum test;
  791.  
  792.     /* this contour might be interior to further exteriors - check */
  793.     /* if not, just add as a new exterior */
  794.     for(;outer!=NULL && outer->type==GLU_EXTERIOR;outer=outer->next)
  795.     {
  796.         test=is_contour_contained_in(outer,contour);
  797.         switch(test)
  798.         {
  799.             case GLU_INTERIOR:
  800.                 /* now we have to check if contour is inside interiors */
  801.                 /* or not */
  802.                 /* any interiors? */
  803.                 if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  804.                 {
  805.                     /* for all interior, check if inside any of them */
  806.                     /* if not inside any of interiors, its another */
  807.                     /* interior */
  808.                     /* or it may contain some interiors, then change */
  809.                     /* the contained interiors to exterior ones */
  810.                     add_interior_with_hierarchy_check(tobj,
  811.                         outer,contour);
  812.                 }
  813.                 else
  814.                 {
  815.                     /* not in interior, add as new interior contour */
  816.                     add_new_interior(tobj,outer,contour);
  817.                 }
  818.                 return;
  819.             case GLU_NO_ERROR:
  820.                 /* disjoint */
  821.                 break;
  822.             default:
  823.                 abort();
  824.         }
  825.     }
  826.     /* add contour to the exterior sequence */
  827.     add_new_exterior(tobj,contour);
  828. }
  829.  
  830. void tess_handle_holes(GLUtriangulatorObj *tobj)
  831. {
  832.     tess_contour *contour,*hole;
  833.     GLenum exterior_orientation;
  834.  
  835.     /* verify hole orientation */
  836.     for(contour=tobj->contours;contour!=NULL;)
  837.     {
  838.         exterior_orientation=contour->orientation;
  839.         for(contour=contour->next;
  840.             contour!=NULL && contour->type==GLU_INTERIOR;
  841.             contour=contour->next)
  842.         {
  843.             if(contour->orientation==exterior_orientation)
  844.             {
  845.                 tess_call_user_error(tobj,GLU_TESS_ERROR5);
  846.                 return;
  847.             }
  848.         }
  849.     }
  850.     /* now cut-out holes */
  851.     for(contour=tobj->contours;contour!=NULL;)
  852.     {
  853.         hole=contour->next;
  854.         while(hole!=NULL && hole->type==GLU_INTERIOR)
  855.         {
  856.             if(cut_out_hole(tobj,contour,hole)==GLU_ERROR)
  857.                 return;
  858.             hole=contour->next;
  859.         }
  860.         contour=contour->next;
  861.     }
  862. }
  863.  
  864. static GLenum cut_out_hole(
  865.     GLUtriangulatorObj *tobj,
  866.     tess_contour *contour,
  867.     tess_contour *hole)
  868. {
  869.     tess_contour *tmp_hole;
  870.     tess_vertex *v1,*v2,*tmp_vertex;
  871.     GLuint vertex1_cnt,vertex2_cnt,tmp_vertex_cnt;
  872.     GLuint i,j,k;
  873.     GLenum test;
  874.  
  875.     /* find an edge connecting contour and hole not intersecting any other */
  876.     /* edge belonging to either the contour or any of the other holes */
  877.     for(v1=contour->vertices , vertex1_cnt=contour->vertex_cnt , i=0;
  878.         i<vertex1_cnt;
  879.         i++ , v1=v1->next)
  880.     {
  881.         for(v2=hole->vertices , vertex2_cnt=hole->vertex_cnt , j=0;
  882.             j<vertex2_cnt;
  883.             j++ , v2=v2->next)
  884.         {
  885.             /* does edge (v1,v2) intersect any edge of contour */
  886.             for(tmp_vertex=contour->vertices , tmp_vertex_cnt=contour->vertex_cnt ,
  887.                     k=0;
  888.                 k<tmp_vertex_cnt;
  889.                 tmp_vertex=tmp_vertex->next , k++)
  890.             {
  891.                 /* skip edge tests for edges directly connected */
  892.                 if(v1==tmp_vertex || v1==tmp_vertex->next)
  893.                     continue;
  894.                 test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  895.                 if(test!=GLU_NO_ERROR)
  896.                     break;
  897.             }
  898.             if(test==GLU_NO_ERROR)
  899.             {
  900.                 /* does edge (v1,v2) intersect any edge of hole */
  901.                 for(tmp_vertex=hole->vertices ,
  902.                         tmp_vertex_cnt=hole->vertex_cnt , k=0;
  903.                     k<tmp_vertex_cnt;
  904.                     tmp_vertex=tmp_vertex->next , k++)
  905.                 {
  906.                     /* skip edge tests for edges directly connected */
  907.                     if(v2==tmp_vertex || v2==tmp_vertex->next)
  908.                         continue;
  909.                     test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  910.                     if(test!=GLU_NO_ERROR)
  911.                         break;
  912.                 }
  913.                 if(test==GLU_NO_ERROR)
  914.                 {
  915.                     /* does edge (v1,v2) intersect any other hole? */
  916.                     for(tmp_hole=hole->next;
  917.                         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  918.                         tmp_hole=tmp_hole->next)
  919.                     {
  920.                         /* does edge (v1,v2) intersect any edge of hole */
  921.                         for(tmp_vertex=tmp_hole->vertices ,
  922.                                 tmp_vertex_cnt=tmp_hole->vertex_cnt , k=0;
  923.                             k<tmp_vertex_cnt;
  924.                             tmp_vertex=tmp_vertex->next , k++)
  925.                         {
  926.                             test=edge_edge_intersect(v1,v2,tmp_vertex,
  927.                                 tmp_vertex->next);
  928.                             if(test!=GLU_NO_ERROR)
  929.                                 break;
  930.                         }
  931.                         if(test!=GLU_NO_ERROR)
  932.                             break;
  933.                     }
  934.                 }
  935.             }
  936.             if(test==GLU_NO_ERROR)
  937.             {
  938.                 /* edge (v1,v2) is good for eliminating the hole */
  939.                 if(merge_hole_with_contour(tobj,contour,hole,v1,v2)
  940.                     ==GLU_NO_ERROR)
  941.                     return GLU_NO_ERROR;
  942.                 else
  943.                     return GLU_ERROR;
  944.             }
  945.         }
  946.     }
  947.     /* other holes are blocking all possible connections of hole */
  948.     /* with contour, we shift this hole as the last hole and retry */
  949.     for(tmp_hole=hole;
  950.         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  951.         tmp_hole=tmp_hole->next);
  952.     contour->next=hole->next;
  953.     hole->next->previous=contour;
  954.     if(tmp_hole==NULL)
  955.     {
  956.         /* last EXTERIOR contour, shift hole as last contour */
  957.         hole->next=NULL;
  958.         hole->previous=tobj->last_contour;
  959.         tobj->last_contour->next=hole;
  960.         tobj->last_contour=hole;
  961.     }
  962.     else
  963.     {
  964.         tmp_hole->previous->next=hole;
  965.         hole->previous=tmp_hole->previous;
  966.         tmp_hole->previous=hole;
  967.         hole->next=tmp_hole;
  968.     }
  969.     hole=contour->next;
  970.     /* try once again - recurse */
  971.     return cut_out_hole(tobj,contour,hole);
  972. }
  973.  
  974. static GLenum merge_hole_with_contour(
  975.     GLUtriangulatorObj *tobj,
  976.     tess_contour *contour,
  977.     tess_contour *hole,
  978.     tess_vertex *v1,
  979.     tess_vertex *v2)
  980. {
  981.     tess_vertex *v1_new,*v2_new;
  982.  
  983.     /* make copies of v1 and v2, place them respectively after their originals */
  984.     if((v1_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  985.     {
  986.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  987.         return GLU_ERROR;
  988.     }
  989.     if((v2_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  990.     {
  991.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  992.         return GLU_ERROR;
  993.     }
  994.     v1_new->edge_flag=GL_TRUE;
  995.     v1_new->data=v1->data;
  996.     v1_new->location[0]=v1->location[0];
  997.     v1_new->location[1]=v1->location[1];
  998.     v1_new->location[2]=v1->location[2];
  999.     v1_new->x=v1->x;
  1000.     v1_new->y=v1->y;
  1001.     v1_new->shadow_vertex=v1;
  1002.     v1->shadow_vertex=v1_new;
  1003.     v1_new->next=v1->next;
  1004.     v1_new->previous=v1;
  1005.     v1->next->previous=v1_new;
  1006.     v1->next=v1_new;
  1007.     v2_new->edge_flag=GL_TRUE;
  1008.     v2_new->data=v2->data;
  1009.     v2_new->location[0]=v2->location[0];
  1010.     v2_new->location[1]=v2->location[1];
  1011.     v2_new->location[2]=v2->location[2];
  1012.     v2_new->x=v2->x;
  1013.     v2_new->y=v2->y;
  1014.     v2_new->shadow_vertex=v2;
  1015.     v2->shadow_vertex=v2_new;
  1016.     v2_new->next=v2->next;
  1017.     v2_new->previous=v2;
  1018.     v2->next->previous=v2_new;
  1019.     v2->next=v2_new;
  1020.     /* link together the two lists */
  1021.     v1->next=v2_new;
  1022.     v2_new->previous=v1;
  1023.     v2->next=v1_new;
  1024.     v1_new->previous=v2;
  1025.     /* update the vertex count of the contour */
  1026.     contour->vertex_cnt += hole->vertex_cnt+2;
  1027.     /* remove the INTERIOR contour */
  1028.     contour->next=hole->next;
  1029.     if(hole->next!=NULL)
  1030.         hole->next->previous=contour;
  1031.     free(hole);
  1032.     /* update tobj structure */
  1033.     --(tobj->contour_cnt);
  1034.     if(contour->last_vertex==v1)
  1035.         contour->last_vertex=v1_new;
  1036.     /* mark two vertices with edge_flag */
  1037.     v2->edge_flag=GL_FALSE;
  1038.     v1->edge_flag=GL_FALSE;
  1039.     return GLU_NO_ERROR;
  1040. }
  1041.