Source/System/NodeCores/Drawables/Nurbs/Internal/OSGParSpaceTrimmer.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_PARSPACETRIMMER_H_
  39 #define _OSG_PARSPACETRIMMER_H_
  40 #ifdef __sgi
  41 #pragma once
  42 #endif
  43
  44 #include "OSGDrawableDef.h"
  45 #include "OSGConfig.h"
  46
  47 #include <stdlib.h>
  48 #include <iostream>
  49 #include "OSGBezierCurve2D.h"
  50 #include "OSGDCTPMesh.h"
  51 #include "OSGDirectedGraph.h"
  52 #include "OSGBSplineTensorSurface.h"
  53
  54 OSG_BEGIN_NAMESPACE
  55
  56 #ifdef OSG_WIN32_ICL
  57 #pragma warning( disable : 171 )
  58 #endif
  59
  60 #define OSG_ADAPTIVE_QUAD_TREE
  61 //#define OSG_FORCE_NO_T_VERTICES
  62 //#define OSG_KEEP_2D_POINTS
  63 #define OSG_USE_SIMPLIFIER
  64
  65 //#include "NurbsPatchSurface.h"
  66
  67 #ifdef OSG_ADAPTIVE_QUAD_TREE
  68 class QuadTreeCreator;
  69 #endif
  70
  71 static const int ERR_NO_STARTING_FACE = -1;
  72 static const int ERR_SET_MININTERSECTION = -2;
  73 static const int ERR_DIRECTEDGE          = -3;
  74 static const int ERR_STATETRANSITION_I   = -4;
  75 static const int ERR_STATETRANSITION_II  = -5;
  76 static const int ERR_NULL_END_NODE       = -6;
  77 static const int ERR_NO_MERGECURVE_START = -7;
  78 static const int ERR_NO_MERGECURVE_END   = -8;
  79 static const int ERR_DEGENERATE_BEZIER   = -9;
  80
  81 #ifdef OSG_FORCE_NO_T_VERTICES
  82 struct SPosNorm
  83 {
  84     Vec3d clPos;
  85 /* #ifndef OSG_CREATE_NORMAL_MAPS
  86         Vec3d                   clNorm;
  87  #endif*/
  88  #ifdef OSG_KEEP_2D_POINTS
  89     unsigned int uiNum;
  90  #endif
  91 };
  92 #endif
  93
  94 class ParSpaceTrimmer;
  95
  96 class OSG_DRAWABLE_DLLMAPPING ParSpaceTrimmerError
  97 {
  98   public:
  99     int errtype;
 100
 101     inline ParSpaceTrimmerError(void);
 102     inline ParSpaceTrimmerError(int t);
 103
 104     inline ~ParSpaceTrimmerError(void);
 105 };
 106
 107
 108 class OSG_DRAWABLE_DLLMAPPING TrimState
 109 {
 110     friend class ParSpaceTrimmer;
 111
 112     enum state_type
 113     {
 114         IN_VERTEX,
 115         OVER_FACE
 116     };
 117
 118     state_type  state;
 119     DCTPFace   *f;
 120     DCTPVertex *v;
 121 };
 122
 123 struct SScanLineEntry;
 124
 125 struct SScanLineEdge
 126 {
 127     DCTPVertex *pclFromVertex;
 128     DCTPVertex *pclToVertex;
 129     SScanLineEdge *ptPrev;
 130     SScanLineEdge *ptNext;
 131     SScanLineEntry *ptEntry;
 132 //      unsigned int    uiOrigNum;
 133     bool bInvalid;
 134 };
 135
 136 struct SScanLineEntry
 137 {
 138     SScanLineEdge *ptEdge;
 139     SScanLineEntry *ptPrev;
 140     SScanLineEntry *ptNext;
 141 };
 142
 143 struct SScanLineEvent
 144 {
 145     SScanLineEdge *ptEdge;
 146     bool bStart;
 147     Vec2d clPos;
 148     Vec2d clOther;
 149
 150     SScanLineEvent(void) : ptEdge(NULL), bStart(false), clPos(), clOther() {}
 151
 152   private:
 153
 154     SScanLineEvent(const SScanLineEvent &other);
 155     void operator =(const SScanLineEvent &rhs);
 156 };
 157
 158 struct OSG_DRAWABLE_DLLMAPPING SScanLineEventLess
 159 {
 160     inline bool operator() (const SScanLineEvent *ptEvent1,
 161                             const SScanLineEvent *ptEvent2) const;
 162 };
 163
 164 typedef std::set<SScanLineEvent*, SScanLineEventLess> ScanLineEventSet;
 165
 166 #ifdef OSG_USE_SIMPLIFIER
 167 struct SPolySimVertex
 168 {
 169     unsigned int uiIndex;
 170     unsigned int uiPrev;
 171     unsigned int uiNext;
 172     Vec3d clPos;
 173     double dSimplifyError;
 174
 175     SPolySimVertex(void):
 176         uiIndex(0), uiPrev(0), uiNext(0), clPos(), dSimplifyError(0.0) {}
 177 };
 178
 179 struct OSG_DRAWABLE_DLLMAPPING SPolySimVertexLess
 180 {
 181     inline bool operator() (const SPolySimVertex *ptVertex1,
 182                             const SPolySimVertex *ptVertex2) const;
 183 };
 184
 185 typedef std::set<SPolySimVertex*, SPolySimVertexLess> SPolySimVertexSet;
 186 #endif
 187
 188 class OSG_DRAWABLE_DLLMAPPING ParSpaceTrimmer
 189 {
 190   private:
 191     DCTPMesh                              *mesh;
 192     bezier2ddequevector                   *tcs;         //trimming curves
 193     bezier3ddequevector                   *tcs3d;       // 3d trimming curves
 194     double                                 terr;        // trimming error (used for 3d loops only!)
 195     TrimState                              state;
 196     DCTPFace                              *start_face;  //the face in which the curve starts (if it starts OVER_FACE)
 197     DCTPEdge                              *ie;          //last intersected edge
 198     double                                 ip;          //intersection parameter on bezier curve
 199     std::vector<std::vector<DCTPVertex*> > vcel;
 200     std::vector<std::vector<Vec2d> >      *pvccrd;
 201     std::vector<std::vector<Vec3d> >      *m_pvvclSewed;
 202 #ifdef OSG_FORCE_NO_T_VERTICES
 203 /* #ifndef OSG_CREATE_NORMAL_MAPS
 204         std::vector< std::vector< Vec3d > >             *m_pvvclNormals;
 205  #endif*/
 206  #ifdef OSG_KEEP_2D_POINTS
 207     unsigned int m_uiPosCnt;
 208  #endif
 209 #endif
 210     bool  m_bDeleteVertexInfo;
 211     Vec2d m_clMin, m_clMax;
 212 #ifdef OSG_ADAPTIVE_QUAD_TREE
 213     QuadTreeCreator *m_pclQuadTree;
 214 #endif
 215     std::vector<bool> *m_pvbReversed;
 216     std::vector<bool> *m_pvbUsed;
 217
 218 #ifdef OSG_USE_SIMPLIFIER
 219     BSplineTensorSurface *m_pclNurbs;
 220 #endif
 221
 222     bool isOverQuad(DCTPFace *f, Vec2d &p);
 223     bool isNearQuad(DCTPFace *f, Vec2d &p);
 224     bool isOverFace(DCTPFace *f, Vec2d &p);
 225
 226     void getStartingFace(Vec2d p);
 227     void initializeStartState(bezier2ddeque& tc);
 228     void initializeStartState2(unsigned int uiLoop, std::vector<DCTPVertex*> &el);
 229
 230     void *isOnFaceBoundary(DCTPFace *f, Vec2d &p, bool &isedge);
 231     bool  isOnEdge(DCTPEdge *e, Vec2d &p, DCTPVertex* &v);
 232     bool  isOnSection(Vec2d &p1, Vec2d &p2, Vec2d &p);
 233
 234     void processCurve(bezier2ddeque &tc, std::vector<DCTPVertex*> &el);
 235     void processCurve2(unsigned int uiLoop, std::vector<DCTPVertex*> &el);
 236     bool StateTransition(BezierCurve2D &b, std::vector<DCTPVertex*> &el);
 237 #ifdef OSG_FORCE_NO_T_VERTICES
 238 // #ifdef OSG_CREATE_NORMAL_MAPS
 239     bool StateTransition2(Vec2d &rclAct, Vec2d clNext, std::vector<DCTPVertex*> &el, Vec3d &rclActS, Vec3d clNextS);
 240 /* #else
 241         bool StateTransition2( Vec2d &rclAct, Vec2d clNext, std::vector< DCTPVertex* > &el, Vec3d &rclActS, Vec3d clNextS, Vec3d &rclActN, Vec3d clNextN );
 242  #endif*/
 243 #else
 244     bool StateTransition2(Vec2d &rclAct, Vec2d clNext, std::vector<DCTPVertex*> &el, Vec3d &rclActS, Vec3d clNextS);
 245 #endif
 246     bool setMinIntersectionWithFace(BezierCurve2D &b);
 247     bool setMinIntersectionWithFace2(Vec2d clAct, Vec2d clNext);
 248     bool goingOutOnEdge(BezierCurve2D& bc, DCTPVertex *&v, bool &feu, std::vector<DCTPVertex*> &el);
 249     bool goingOutOnEdge2(Vec2d clAct, Vec2d clNext, DCTPVertex *&v, bool &feu, std::vector<DCTPVertex*> &el);
 250 //        bool StoreCurveToFace( BezierCurve2D &bc, double t, DCTPVertex *v );
 251     bool            StoreCurveApproximation(BezierCurve2D &bc, double t, std::vector<DCTPVertex*> &el);
 252     DCTPFace*       getContinuingFace(BezierCurve2D &bc);
 253     DCTPFace*       getContinuingFace2(Vec2d clAct, Vec2d clNext);
 254     Vec2d           calcNormal(Vec2d &a, Vec2d &b);
 255     bool            checkEdgeNormals(DirectedGraph<Vec2d, unsigned char> &sg, int from, int to);
 256     void            checkEdgeloops(); //check for intersections/overlappings in edgeloops and remove them
 257     bool            insertScanLineEvents(SScanLineEdge *ptEdge, ScanLineEventSet &rsptEvents, char cWhich = -1); // ucWhich = -1 for both
 258     SScanLineEntry *insertInScanLine(SScanLineEntry *ptActEntry, SScanLineEntry *ptScanLine);
 259     void            saveLoop(SScanLineEdge *ptEdge);
 260     void            checkSLIntersection(SScanLineEntry *ptActEntry, ScanLineEventSet &rsptEvents);
 261     void            ScanLineIntersect(SScanLineEntry *ptEntry1, SScanLineEntry *ptEntry2, ScanLineEventSet &rsptEvents);
 262     bool            isSLEntryLess(SScanLineEdge *ptEdge1, SScanLineEdge *ptEdge2);
 263     void            removeSLEntry(SScanLineEntry *ptEntry, ScanLineEventSet &rsptEvents);
 264     DCTPVertex *    intersectsLoop(DCTPVertex *pclVertex1, DCTPVertex *pclVertex2, unsigned int uiLoop);
 265     bool            doIntersect(Vec2d clV1, Vec2d clV2, Vec2d clV3, Vec2d clV4, double &rdParam);
 266     void            deleteVertexInfo();
 267     bool            isLoopValid(const unsigned int cuiLoop);
 268     bool            intersectsRay(const Vec2d cclV1, const Vec2d cclV2, const Vec2d cclStart, const Vec2d cclEnd);
 269
 270   public:
 271     inline ParSpaceTrimmer(void);
 272     inline ~ParSpaceTrimmer(void);
 273
 274     void Initialize(DCTPMesh &m, bezier2ddequevector &c2d, bezier3ddequevector &c3d, std::vector<std::vector<Vec2d> > &vccrd, double err
 275 #ifdef OSG_USE_SIMPLIFIER
 276                     , BSplineTensorSurface *pclNurbs
 277 #endif
 278                     )
 279     {
 280 //                      std::cerr << "trim with err = " << err << std::endl;
 281         mesh   = &m;
 282         tcs    = &c2d;
 283         pvccrd = &vccrd;
 284         tcs3d  = &c3d;
 285         terr   = err;
 286         mesh->reinit();
 287 #ifdef OSG_USE_SIMPLIFIER
 288         m_pclNurbs = pclNurbs;
 289 #endif
 290     }
 291     void Initialize(DCTPMesh &m, bezier2ddequevector &tc, std::vector<std::vector<Vec2d> > &vccrd
 292 #ifdef OSG_ADAPTIVE_QUAD_TREE
 293                     , QuadTreeCreator *pclQuadTree
 294 #endif
 295 #ifdef OSG_USE_SIMPLIFIER
 296                     , BSplineTensorSurface *pclNurbs
 297 #endif
 298                     )
 299     {
 300         mesh       = &m;
 301         tcs        = &tc;
 302         pvccrd     = &vccrd;
 303         m_clMin[0] = m_clMax[0] = (*mesh->vertices.begin() )->coords[0];
 304         m_clMin[1] = m_clMax[1] = (*mesh->vertices.begin() )->coords[1];
 305
 306         for(dctpvertexset::iterator it_vertex = mesh->vertices.begin(); it_vertex != mesh->vertices.end(); ++it_vertex)
 307         {
 308             (*it_vertex)->vertexinfo = reinterpret_cast<void*>(1);
 309             if( (*it_vertex)->coords[0] < m_clMin[0])
 310                 m_clMin[0] = (*it_vertex)->coords[0];
 311             else if( (*it_vertex)->coords[0] > m_clMax[0])
 312                 m_clMax[0] = (*it_vertex)->coords[0];
 313             if( (*it_vertex)->coords[1] < m_clMin[1])
 314                 m_clMin[1] = (*it_vertex)->coords[1];
 315             else if( (*it_vertex)->coords[1] > m_clMax[1])
 316                 m_clMax[1] = (*it_vertex)->coords[1];
 317         }
 318
 319         m_clMin[0] += DCTP_EPS * 0.5;
 320         m_clMin[1] += DCTP_EPS * 0.5;
 321         m_clMax[0] -= DCTP_EPS * 0.5;
 322         m_clMax[1] -= DCTP_EPS * 0.5;
 323 #ifdef OSG_ADAPTIVE_QUAD_TREE
 324         m_pclQuadTree = pclQuadTree;
 325 #endif
 326 #ifdef OSG_USE_SIMPLIFIER
 327         m_pclNurbs = pclNurbs;
 328 #endif
 329 //                              m_bMaxLength = false;
 330         tcs3d = NULL;
 331     }
 332
 333 #ifdef OSG_FORCE_NO_T_VERTICES
 334 // #ifdef OSG_CREATE_NORMAL_MAPS
 335     void Initialize2(DCTPMesh &m, std::vector<std::vector<Vec2d> > &vccrd, std::vector<std::vector<Vec3d> > &vvclSewed, std::vector<bool> &rvbRev, std::vector<bool> &rvbUsed)
 336 /* #else
 337         void Initialize2( DCTPMesh &m, std::vector< std::vector< Vec2d > > &vccrd, std::vector< std::vector< Vec3d > > &vvclSewed, std::vector< std::vector< Vec3d > > &vvclNormals, std::vector< bool > &rvbRev, std::vector< bool > &rvbUsed )
 338  #endif*/
 339 #else
 340     void Initialize2(DCTPMesh &m, std::vector<std::vector<Vec2d> > &vccrd, std::vector<std::vector<Vec3d> > &vvclSewed, std::vector<bool> &rvbRev, std::vector<bool> &rvbUsed)
 341 #endif
 342     {
 343         mesh         = &m;
 344         tcs          = NULL;
 345         pvccrd       = &vccrd;
 346         m_pvvclSewed = &vvclSewed;
 347 #ifdef OSG_FORCE_NO_T_VERTICES
 348 /* #ifndef OSG_CREATE_NORMAL_MAPS
 349                 m_pvvclNormals = &vvclNormals;
 350  #endif*/
 351 #endif
 352         m_pvbReversed = &rvbRev;
 353         m_pvbUsed     = &rvbUsed;
 354         if(mesh->vertices.size() )
 355         {
 356             m_clMin[0] = m_clMax[0] = (*mesh->vertices.begin() )->coords[0];
 357             m_clMin[1] = m_clMax[1] = (*mesh->vertices.begin() )->coords[1];
 358         }
 359
 360         for(dctpvertexset::iterator it_vertex = mesh->vertices.begin(); it_vertex != mesh->vertices.end(); ++it_vertex)
 361         {
 362             (*it_vertex)->vertexinfo = NULL;
 363             if( (*it_vertex)->coords[0] < m_clMin[0])
 364                 m_clMin[0] = (*it_vertex)->coords[0];
 365             else if( (*it_vertex)->coords[0] > m_clMax[0])
 366                 m_clMax[0] = (*it_vertex)->coords[0];
 367             if( (*it_vertex)->coords[1] < m_clMin[1])
 368                 m_clMin[1] = (*it_vertex)->coords[1];
 369             else if( (*it_vertex)->coords[1] > m_clMax[1])
 370                 m_clMax[1] = (*it_vertex)->coords[1];
 371         }
 372
 373         m_clMin[0] += DCTP_EPS * 0.5;
 374         m_clMin[1] += DCTP_EPS * 0.5;
 375         m_clMax[0] -= DCTP_EPS * 0.5;
 376         m_clMax[1] -= DCTP_EPS * 0.5;
 377     }
 378
 379     int PerformTrimming(void);
 380     int PerformTrimming2(void);
 381 #ifdef OSG_FORCE_NO_T_VERTICES
 382  #ifdef OSG_KEEP_2D_POINTS
 383     int buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *pGraph, std::vector<Vec3d> *pvclSewed = NULL, std::vector<Vec3d> *pvclNormals = NULL, std::vector<unsigned int> *pvclIdx = NULL);
 384  #else
 385     int buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *pGraph, std::vector<Vec3d> *pvclSewed = NULL, std::vector<Vec3d> *pvclNormals = NULL);
 386  #endif
 387 #else
 388     int  buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *pGraph, std::vector<Vec3d> *pvclSewed = NULL);
 389     void getTrimmingLoops(std::vector<std::vector<Vec2d> > &rvvclTrimmingLoops);
 390 #endif
 391
 392
 393 #ifdef OSG_USE_SIMPLIFIER
 394     double DistToEdge(const Vec3d cclPoint, const Vec3d cclLine1, const Vec3d cclLine2) const;
 395 #endif
 396
 397   private:
 398
 399     ParSpaceTrimmer(const ParSpaceTrimmer &other);
 400     void operator=(const ParSpaceTrimmer &rhs);
 401 };
 402
 403 #ifdef OSG_WIN32_ICL
 404 #pragma warning( default : 171 )
 405 #endif
 406
 407 OSG_END_NAMESPACE
 408
 409 #include "OSGParSpaceTrimmer.inl"
 410
 411 #endif