gunu_tesselate1.cpp Source File

00001 /* LIBGUL - Geometry Utility Library
00002  * Copyright (C) 1998-1999 Norbert Irmer
00003  *
00004  * This library is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU Library General Public
00006  * License as published by the Free Software Foundation; either
00007  * version 2 of the License, or (at your option) any later version.
00008  *
00009  * This library is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * Library General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU Library General Public
00015  * License along with this library; if not, write to the
00016  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00017  * Boston, MA 02111-1307, USA.
00018  */
00019  
00020 
00021 #include "stdafx.h"
00022 
00023 #include <iostream>
00024 
00025 #include "gul_types.h"
00026 #include "gust_new.h"
00027 #include "gul_vector.h"
00028 #include "guge_linear.h"
00029 #include "guge_normalize.h"
00030 #include "gunu_basics.h"
00031 #include "gunu_derivatives.h"
00032 #include "gunu_divide.h"
00033 #include "gunu_intersect.h"
00034 #include "gunu_linearize.h"
00035 #include "guar_exact.h"
00036 #include "gugr_basics.h"
00037 #include "gugr_split.h"
00038 #include "gul_io.h"
00039 #include "gugr_regularize.h"
00040 #include "gugr_triangulate.h"
00041 #include "gugr_planesweep.h"
00042 #include "gugr_contour.h"
00043 #include "gul_std.h"
00044 #include "gugr_io.h"
00045 
00046 #include "gunu_tesselate.h"
00047 
00048 // #include <crtdbg.h>
00049 
00050 using gul::List;
00051 using gul::List2;
00052 using gul::ListNode;
00053 using gul::point;
00054 using gul::hpoint;
00055 using gul::point2;
00056 using gul::hpoint2;
00057 using gul::curve;
00058 using gul::Min;
00059 using gul::set;
00060 // using gul::is_zero;
00061 using gul::normalize;
00062 using gul::euclid;
00063 using guar::rational;
00064 using gugr::graph_vertex;
00065 using gugr::graph_edge;
00066 using gugr::cut_info;
00067 using gugr::IntersectWithVerticals;
00068 using gugr::DivideVerticalStrips;
00069 using gugr::IntersectWithHorizontals;
00070 using gugr::DivideHorizontalStrips;
00071 using gugr::EdgeCycle;
00072 using gugr::graph_vertex_list;
00073 using gugr::graph_edge_list;
00074 using gugr::vertex_rep;
00075 using gugr::coord2int;
00076 using gugr::polyline;
00077 using gugr::OddEvenRule;
00078 using gugr::segment;
00079 
00080 /*-------------------------------------------------------------------
00081   approximate trimmed NURBS surface with triangles
00082 --------------------------------------------------------------------*/
00083 namespace gunu {
00084 
00085 template< class T, class HP >
00086 GULAPI void DoLinearizeTrimmedSurface( 
00087             int max_iter,
00088             const int nu, const int pu, Ptr< T >& KnotsU,
00089             const int nv, const int pv, Ptr< T >& KnotsV,
00090             Ptr< Ptr< HP > >& Pw,
00091             const T tol,
00092             Ptr< Ptr< point2<T> > >& contour,
00093             void (*outfunc1)( TessInfo<T,HP> *, void * ),                                  
00094             void (*outfunc2)( TessInfo<T,HP> *, gugr::GraphInfo *,
00095                               gugr::GraphConvInfo<T> *, void * ),
00096             void *usrdata )
00097 {
00098   TessInfo<T,HP>       A;
00099   gugr::GraphConvInfo<T>  Gconv;
00100   graph_edge_list   E;
00101   graph_vertex_list V;
00102   gugr::GraphInfo         G;
00103   rational MinX,MaxX,FarMinX,FarMaxX,MinY,MaxY,FarMinY,FarMaxY,X1,X2,Y1,Y2;
00104   T x1,x2,y1,y2,minx,maxx,miny,maxy,dx,dy,scale,scalei;
00105   int i,nContour,n;
00106   unsigned long *cbuf = (unsigned long *)alloca(gul::rtr<T>::mantissa_length());
00107   rational Big(guar::ULong(0x100000));
00108   List< ListNode<segment> > S;
00109   List< ListNode<polyline> > Pl;
00110   polyline *pl;
00111   ListNode<polyline> *pn;
00112  
00113   if( (nContour = contour.nElems()) < 1 ) return;
00114   
00115   minx = x1 = miny = y1 = (T)0.0;   /* --- initialise graph info --- */
00116   maxx = x2 = maxy = y2 = (T)1.0; 
00117   
00118   for( i = 0; i < nContour; i++ )
00119   {
00120     if( (n = contour[i].nElems()) < 2 ) return;
00121     // if( contour[i][0] != contour[i][n-1] ) return;  // not closed
00122     guge::UpdateBoundingBoxE<T>( n, contour[i], minx, maxx, miny, maxy );
00123   }  
00124   dx = maxx - minx;
00125   dy = maxy - miny;
00126   scale = dx > dy ? dx : dy;
00127   minx -= scale;         // after this the normalized points will lie between
00128   miny -= scale;         // 1 and 2
00129   scalei = (T)1/scale;
00130 
00131   /*  
00132   gugr::DumpPS<T>::set_transformation( minx, miny, scale, scale );
00133   gugr::Dump<T>::set_transformation( minx, miny, scale, scale );
00134   */
00135 
00136   Gconv.minx = minx; Gconv.miny = miny; Gconv.scale = scale;
00137 
00138   x1 = (x1 - minx)/scale;   x2 = (x2 - minx)/scale;
00139   y1 = (y1 - miny)/scale;   y2 = (y2 - miny)/scale;
00140 
00141   for( i = 0; i < nContour; i++ ) 
00142   {
00143     pn = new ListNode<polyline>();
00144     Pl.Append( pn );
00145     pl = &pn->el;
00146     pl->init( contour[i].nElems(), contour[i], minx, miny, scalei ); 
00147   }
00148 
00149   X1 = rational( coord2int(x1,cbuf),cbuf );
00150   X2 = rational( coord2int(x2,cbuf),cbuf );
00151   Gconv.MinY = rational( guar::ULong(0x100000), -1 );
00152   Gconv.MaxY = rational(coord2int((T)2,cbuf),cbuf)+Big;
00153   Gconv.FarMinY = rational(guar::ULong(0x200000),-1);
00154   Gconv.FarMaxY = Gconv.MaxY + Big;
00155   
00156   Y1 = rational(coord2int(y1,cbuf),cbuf);
00157   Y2 = rational(coord2int(y2,cbuf),cbuf);
00158   Gconv.MinX = Gconv.MinY;
00159   Gconv.MaxX = Gconv.MaxY;
00160   Gconv.FarMinX = Gconv.FarMinY;
00161   Gconv.FarMaxX = Gconv.FarMaxY;
00162 
00163   OddEvenRule( Pl, Gconv.FarMaxX, Gconv.FarMaxY, 1, 0, E, V, S );
00164 
00165   S.DeleteElems();
00166 
00167   // gugr::OrientEdges( E.head );
00168   
00169   gugr::InitGraph<T>( X1, X2, Y1, Y2, &Gconv, &E, &V, &G );  // initialise graph info
00170   E.DeleteElems();
00171   V.DeleteElems();
00172 
00173   /*
00174   cout << "after construction of graph\n";
00175   cout << "***************************\n";
00176   gugr::Dump<T>::dump_vertices( G.V.head );
00177   gugr::Dump<T>::dump_edges( G.E.head );
00178   */
00179 
00180                     /* --- initialise nurbs surface info --- */
00181   A.org->nu = nu;
00182   A.org->pu = pu;  
00183   A.org->U =  KnotsU;
00184   A.org->nv = nv;
00185   A.org->pv = pv;  
00186   A.org->V =  KnotsV;
00187   A.org->Pw = Pw;
00188   /*
00189   guge::CalcBoundingBox( (A.org->nu+1)*(A.org->nv+1), 
00190                A.org->Pw[0], A.x1, A.x2, A.y1, A.y2, A.z1, A.z2 ); 
00191   */
00192 
00193   A.org->P00 = gul::euclid( A.org->Pw[0][0] );
00194   A.org->P01 = gul::euclid( A.org->Pw[0][A.org->nu] );
00195   A.org->P10 = gul::euclid( A.org->Pw[A.org->nv][0] );
00196   A.org->P11 = gul::euclid( A.org->Pw[A.org->nv][A.org->nu] );
00197 
00198   A.u1 = 0.0;
00199   A.u2 = 1.0; 
00200   A.v1 = 0.0;
00201   A.v2 = 1.0; 
00202 
00203   /*
00204   _CrtSetReportMode( _CRT_WARN, _CRTDBG_MODE_DEBUG );
00205   _RPT1( _CRT_WARN, "number of pool items = %d\n", 
00206          gust::pooldbg::count );
00207   _RPT2( _CRT_WARN, "rationals = %d, reps = %d\n", 
00208          rational::count, rational::rational_rep::count );
00209   _RPT3( _CRT_WARN, "graph_vertex's = %d, vertex's = %d, vertex_rep's = %d\n", 
00210          gugr::graph_vertex::count, gugr::vertex::count, 
00211          gugr::vertex_rep::count );
00212   */
00213 
00214   _DoLinearizeTrimmedSurface( 1, max_iter, &A, &G, &Gconv, tol,
00215                               outfunc1, outfunc2, usrdata );
00216 }
00217 
00218 /*-------------------------------------------------------------------
00219   approximate trimmed NURBS surface with triangles
00220 --------------------------------------------------------------------*/
00221 template GULAPI void DoLinearizeTrimmedSurface( 
00222        int max_iter,
00223        const int nu, const int pu, Ptr< float >& KnotsU,
00224        const int nv, const int pv, Ptr< float >& KnotsV,
00225        Ptr< Ptr< hpoint<float> > >& Pw,
00226        const float tol,
00227        Ptr< Ptr< point2<float> > >& contour,
00228        void outfunc1( gunu::TessInfo<float,hpoint<float> > *, void * ),                                   
00229        void outfunc2( gunu::TessInfo<float,hpoint<float> > *, gugr::GraphInfo *,
00230                       gugr::GraphConvInfo<float> *, void * ),
00231        void *usrdata );
00232 template GULAPI void DoLinearizeTrimmedSurface( 
00233        int max_iter,
00234        const int nu, const int pu, Ptr< double >& KnotsU,
00235        const int nv, const int pv, Ptr< double >& KnotsV,
00236        Ptr< Ptr < hpoint<double> > >& Pw,
00237        const double tol,
00238        Ptr< Ptr< point2<double> > >& contour,
00239        void outfunc1( TessInfo<double,hpoint<double> > *, void * ),                                   
00240        void outfunc2( TessInfo<double,hpoint<double> > *, gugr::GraphInfo *,
00241                       gugr::GraphConvInfo<double> *, void * ),
00242        void *usrdata );
00243 
00244 template GULAPI void DoLinearizeTrimmedSurface( 
00245        int max_iter,
00246        const int nu, const int pu, Ptr< float >& KnotsU,
00247        const int nv, const int pv, Ptr< float >& KnotsV,
00248        Ptr< Ptr< point<float> > >& Pw,
00249        const float tol,
00250        Ptr< Ptr< point2<float> > >& contour,
00251        void outfunc1( gunu::TessInfo<float,point<float> > *, void * ),                                   
00252        void outfunc2( gunu::TessInfo<float,point<float> > *, gugr::GraphInfo *,
00253                       gugr::GraphConvInfo<float> *, void * ),
00254        void *usrdata );
00255 template GULAPI void DoLinearizeTrimmedSurface( 
00256        int max_iter,
00257        const int nu, const int pu, Ptr< double >& KnotsU,
00258        const int nv, const int pv, Ptr< double >& KnotsV,
00259        Ptr< Ptr < point<double> > >& Pw,
00260        const double tol,
00261        Ptr< Ptr< point2<double> > >& contour,
00262        void outfunc1( TessInfo<double,point<double> > *, void * ),                                   
00263        void outfunc2( TessInfo<double,point<double> > *, gugr::GraphInfo *,
00264                       gugr::GraphConvInfo<double> *, void * ),
00265        void *usrdata );
00266 
00267 }
00268