Source/System/NodeCores/Drawables/Nurbs/Internal/OSGSimplePolygon.h

   1 /*---------------------------------------------------------------------------*\
   2  *                           OpenSG NURBS Library                            *
   3  *                                                                           *
   4  *                                                                           *
   5  * Copyright (C) 2001-2006 by the University of Bonn, Computer Graphics Group*
   6  *                                                                           *
   7  *                         http://cg.cs.uni-bonn.de/                         *
   8  *                                                                           *
   9  * contact: edhellon@cs.uni-bonn.de, guthe@cs.uni-bonn.de, rk@cs.uni-bonn.de *
  10  *                                                                           *
  11 \*---------------------------------------------------------------------------*/
  12 /*---------------------------------------------------------------------------*\
  13  *                                License                                    *
  14  *                                                                           *
  15  * This library is free software; you can redistribute it and/or modify it   *
  16  * under the terms of the GNU Library General Public License as published    *
  17  * by the Free Software Foundation, version 2.                               *
  18  *                                                                           *
  19  * This library is distributed in the hope that it will be useful, but       *
  20  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  22  * Library General Public License for more details.                          *
  23  *                                                                           *
  24  * You should have received a copy of the GNU Library General Public         *
  25  * License along with this library; if not, write to the Free Software       *
  26  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
  27  *                                                                           *
  28 \*---------------------------------------------------------------------------*/
  29 /*---------------------------------------------------------------------------*\
  30  *                                Changes                                    *
  31  *                                                                           *
  32  *                                                                           *
  33  *                                                                           *
  34  *                                                                           *
  35  *                                                                           *
  36  *                                                                           *
  37 \*---------------------------------------------------------------------------*/
  38 #ifndef _OSG_SIMPLEPOLYGON_H_
  39 #define _OSG_SIMPLEPOLYGON_H_
  40
  41 #include <iostream>
  42 #include "OSGDrawableDef.h"
  43 #include "OSGdctptypes.h"
  44
  45 OSG_BEGIN_NAMESPACE
  46
  47 #define OSG_TRIANGULATE_CONVEX
  48
  49 class SimplePolygon;
  50
  51 typedef std::vector <SimplePolygon> simplepolygonvector;
  52
  53 class OSG_DRAWABLE_DLLMAPPING SimplePolygon
  54 {
  55   public:
  56     SimplePolygon();
  57     // copy constructor
  58     SimplePolygon(const SimplePolygon &p) :
  59         vertices        (p.vertices ),
  60         is_marked       (p.is_marked),
  61         validThirdPoints(           ),
  62         numThirdPoints  (          0),
  63         maxCalculated   (          0),
  64         v1tp            (         -1),
  65         v2tp            (         -1),
  66         m_bConvex       (p.m_bConvex)
  67
  68     {
  69     }
  70     ~SimplePolygon() {};
  71
  72     DCTPivector vertices; // vertices. edges are from [n - 1, n] plus [vertices.size() - 1, 0], always ordered clockwise.
  73     // these are pointers into a global vertices table
  74     int          is_marked; // 0 if delauney != 0 else
  75     DCTPivector  validThirdPoints; // valid third points for actual edge
  76     unsigned int numThirdPoints; // actual number of valid third points
  77     int          maxCalculated; // max. third point tested
  78     int          v1tp, v2tp;   // actual first edge
  79     bool         m_bConvex;
  80
  81     int triangulate(DCTPVec2dvector &globalverts, simplepolygonvector &polylist); //triangulates the polygon, using RK's method.
  82     // inserts the new polygons (triangles) at the end of the polygon list.
  83     // also sets up marking information for the new polygons.
  84   protected:
  85 //  bool checkOrient( const DCTPVec3dvector &crclSpaceVerts, const DCTPVec3dvector &crclNormals ) const; // check if triangle has correct orientation
  86 //  bool checkOrient( const DCTPVec3dvector &crclSpaceVerts, const DCTPVec3dvector &crclNormals, int i1, int i2, int i3 ) const; // check if triangle has correct orientation
  87     int findThirdPoint(DCTPVec2dvector &globalverts, int i1, int i2, int &i3); // try to find a suitable third point for (v1, v2)
  88     int isInsidePolygon(DCTPVec2dvector &globalverts, int i1, int i2, int i3) const; // is the triangle formed by the vertices (v1, v2, v3) inside the polygon ?
  89     int doIntersect(DCTPVec2dvector &globalverts, int v1, int v2, int p1, int p2) const; // do the two polylines (v1, v2) and (p1, p2) intersect ?
  90     int isInsideCircumCircle(DCTPVec2dvector &globalverts, int v1, int v2, int v3, int p) const; // is the point `p' inside the circumcircle of the triangle (v1, v2, v3) ?
  91     int isDelaunay(DCTPVec2dvector &globalverts, int v1, int v2, int v3); // is the triangle formed by the vertices (v1, v2, v3) a Delaunay triangle (with regard to this polygon ?
  92
  93     // next three routines return 0 if done, !=0 if need to run again
  94     int removeLinearPoints(DCTPVec2dvector &globalverts, const Vec2d min, const Vec2d max); // remove linear points on polygon O(n)
  95     int splitPolygon(DCTPVec2dvector &globalverts, simplepolygonvector &polylist, const Vec2d min, const Vec2d max); // check for double vertices and split polygon in two O(nlogn)
  96     int intersectPolygon(DCTPVec2dvector &globalverts, simplepolygonvector &polylist); // check if polygon intersects itself and split in two O(n^2)
  97   public:
  98     bool isReversed(DCTPVec2dvector &globalverts); // check if polygon is reversed => ignore it O(n)
  99     bool isConvex(DCTPVec2dvector &globalverts);
 100     // stuff to fix invalid polygons
 101     int fixAndTriangulate(DCTPVec2dvector &globalverts, simplepolygonvector &polylist); // fix the polygon and triangulate the resulting valid polygons
 102   protected:
 103     double getAngle(Vec2d dir); // calculate angle between dir and (1,0) FIXME: should go to Vec2d
 104     int    getMinMax(DCTPVec2dvector &globalverts, Vec2d &min, Vec2d &max);
 105
 106     inline int getThirdPoint(DCTPVec2dvector &globalverts, int v1, int v2, unsigned int index)
 107     {
 108         const unsigned int vsize  = UInt32(vertices.size());
 109         const unsigned int hsize1 = ( (vsize - 1) >> 1);
 110         const unsigned int h2size = (hsize1 << 1);
 111
 112 //    std::cerr << v1 << "," << v2 << " " << index << std::endl;
 113
 114         if( (v1 != v1tp) || (v2 != v2tp) )
 115         {
 116             maxCalculated  = int(hsize1);
 117             numThirdPoints = 0;
 118             v1tp           = v1;
 119             v2tp           = v2;
 120         }
 121         while(index >= numThirdPoints)
 122         {
 123             if( (maxCalculated >= int(vsize) ) || (maxCalculated < 0) )
 124             {
 125 //        std::cerr << "No valid third point " << v1 << "," << v2 << " " << index << std::endl;
 126                 return -1;
 127             }
 128 //      std::cerr << "Testing " << v1 << "," << v2 << "," << maxCalculated << std::endl;
 129             // FIXME: should also check if any point is on the edge
 130             // FIXME: of the triangle [v1, v2, maxCalculated]
 131             // FIXME: that is on the edges [v1, maxCalculated]
 132             // FIXME: or [v2, maxCalculated]
 133             if( (maxCalculated != v1) && (maxCalculated != v2) &&
 134                 (isInsidePolygon(globalverts, v1, v2, maxCalculated) == 0) )
 135             {
 136                 validThirdPoints[numThirdPoints] = maxCalculated;
 137                 ++numThirdPoints;
 138             }
 139             maxCalculated = h2size - maxCalculated;
 140             if(maxCalculated >= int(hsize1) )
 141             {
 142                 ++maxCalculated;
 143             }
 144         }
 145 //    std::cerr << "valid third point " << v1 << "," << v2 << " " << index << " = " << validThirdPoints[ index ] << std::endl;
 146         return validThirdPoints[index];
 147     }
 148
 149 };
 150
 151 OSG_END_NAMESPACE
 152
 153
 154
 155
 156 #endif // SimplePolygon.h