vcglib: local_optimization.h Source File

00001 /****************************************************************************
00002 * VCGLib                                                            o o     *
00003 * Visual and Computer Graphics Library                            o     o   *
00004 *                                                                _   O  _   *
00005 * Copyright(C) 2004                                                \/)\/    *
00006 * Visual Computing Lab                                            /\/|      *
00007 * ISTI - Italian National Research Council                           |      *
00008 *                                                                    \      *
00009 * All rights reserved.                                                      *
00010 *                                                                           *
00011 * This program is free software; you can redistribute it and/or modify      *   
00012 * it under the terms of the GNU General Public License as published by      *
00013 * the Free Software Foundation; either version 2 of the License, or         *
00014 * (at your option) any later version.                                       *
00015 *                                                                           *
00016 * This program is distributed in the hope that it will be useful,           *
00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
00019 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
00020 * for more details.                                                         *
00021 *                                                                           *
00022 ****************************************************************************/
00023 /****************************************************************************
00024   $Log: not supported by cvs2svn $
00025   Revision 1.20  2007/01/19 09:13:09  cignoni
00026   Added Finalize() method to the interface
00027 
00028   Revision 1.19  2007/01/11 11:48:33  ganovelli
00029   currMetric inizialied to heap.front() (it was heap.back()- wrong)
00030 
00031   Revision 1.18  2006/12/11 14:09:44  ganovelli
00032   added missing initialization of currMetric
00033 
00034   Revision 1.17  2006/06/09 07:28:43  m_di_benedetto
00035   Corrected ClearHeap(): iterator "hi" not decrementable if it was the first of the container.
00036 
00037   Revision 1.16  2005/11/10 15:38:46  cignoni
00038   Added casts to remove warnings
00039 
00040   Revision 1.15  2005/10/02 23:23:52  cignoni
00041   Changed the sense of the < operator for heap: it is reversed according to the stl where highest score elements must float in the heap
00042   Completed TimeBudget Termination condition.
00043   Parametrized the ClearHeap procedure now there is a HeapSimplexRatio param. Removed dirty printf.
00044 
00045   Revision 1.14  2005/04/14 11:34:33  ponchio
00046   *** empty log message ***
00047 
00048   Revision 1.13  2005/01/19 10:33:50  cignoni
00049   Improved ClearHeap management
00050 
00051   Revision 1.12  2004/12/10 01:02:48  cignoni
00052   added an inline and removed loggng
00053 
00054   Revision 1.11  2004/12/03 21:14:39  ponchio
00055   Fixed memory leak...
00056 
00057   Revision 1.10  2004/11/23 10:37:17  cignoni
00058   Added a member with a cached copy of the floating Priority() value inside the HeapElem to optimize operator< in heap updating operator
00059 
00060   Revision 1.9  2004/11/05 10:03:47  fiorin
00061   Added ModifierType::TriEdgeFlipOp
00062 
00063   Revision 1.8  2004/10/25 07:02:56  ganovelli
00064   some inline function, logs on file (precompiler directive)
00065 
00066   Revision 1.7  2004/09/29 17:08:39  ganovelli
00067   changed > to < in heapelem comparison
00068 
00069   Revision 1.6  2004/09/28 09:57:08  cignoni
00070   Better Doxygen docs
00071 
00072   Revision 1.5  2004/09/15 10:40:20  ponchio
00073   typedef LocalOptimization HeapType -> public:
00074 
00075   Revision 1.4  2004/09/08 15:10:59  ganovelli
00076   *** empty log message ***
00077 
00078   Revision 1.3  2004/07/27 09:46:15  cignoni
00079   First working version of the LocalOptimization/Simplification Framework
00080 
00081   Revision 1.1  2004/07/15 12:04:14  ganovelli
00082   minor changes
00083 
00084   Revision 1.2  2004/07/09 10:22:56  ganovelli
00085   working draft
00086 
00087   Revision 1.1  2004/07/08 08:25:15  ganovelli
00088   first draft
00089 
00090 ****************************************************************************/
00091 
00092 #ifndef __VCGLIB_LOCALOPTIMIZATION
00093 #define __VCGLIB_LOCALOPTIMIZATION
00094 #include<vector>
00095 #include<algorithm>
00096 #include<time.h>
00097 #include<math.h>
00098 #include<vcg/complex/trimesh/base.h>
00099 
00100 namespace vcg{
00101 
00102 template<class MeshType> 
00103 class LocalOptimization;
00104 
00105 enum ModifierType{      TetraEdgeCollapseOp, TriEdgeSwapOp, TriVertexSplitOp,
00106                                 TriEdgeCollapseOp,TetraEdgeSpliOpt,TetraEdgeSwapOp, TriEdgeFlipOp};
00109 
00110 template <class MeshType>
00111 class LocalModification
00112 {
00113  public:
00114         typedef typename LocalOptimization<MeshType>::HeapType HeapType;
00115         typedef typename MeshType::ScalarType ScalarType;
00116 
00117 
00118         inline LocalModification(){};
00119         virtual ~LocalModification(){};
00120   
00122         virtual ModifierType IsOfType() = 0 ;
00123 
00125         virtual bool IsUpToDate() = 0 ;
00126 
00128         virtual bool IsFeasible() = 0;
00129 
00131         virtual ScalarType ComputePriority()=0;
00132 
00134         virtual ScalarType Priority() const =0;
00135 
00137         virtual void Execute(MeshType &m)=0;
00138 
00140         static void Init(MeshType &m, HeapType&);
00141 
00147         static float HeapSimplexRatio() {return 6.0f;} ;
00148 
00149   virtual const char *Info(MeshType &) {return 0;}
00151         virtual void UpdateHeap(HeapType&)=0;
00152 };      //end class local modification
00153 
00154 
00161 
00162 template<class MeshType>
00163 class LocalOptimization
00164 {
00165 public:
00166   LocalOptimization(MeshType &mm): m(mm){ ClearTermination();e=0.0;HeapSimplexRatio=5;}
00167 
00168         struct  HeapElem;
00169         // scalar type
00170         typedef typename MeshType::ScalarType ScalarType;
00171         // type of the heap
00172         typedef typename std::vector<HeapElem> HeapType;        
00173         // modification type    
00174         typedef  LocalModification <MeshType>  LocModType;
00175         // modification Pointer type    
00176         typedef  LocalModification <MeshType> * LocModPtrType;
00177         
00178 
00179 
00181          enum LOTermination {   
00182       LOnSimplices      = 0x01, // test number of simplicies    
00183                         LOnVertices             = 0x02, // test number of verticies
00184                         LOnOps                  = 0x04, // test number of operations
00185                         LOMetric                = 0x08, // test Metric (error, quality...instance dependent)
00186                         LOTime                  = 0x10  // test how much time is passed since the start
00187                 } ;
00188 
00189         int tf;
00190         
00191   int nPerfmormedOps,
00192                 nTargetOps,
00193                 nTargetSimplices,
00194                 nTargetVertices;
00195 
00196         float   timeBudget;
00197         int             start;
00198         ScalarType currMetric;
00199         ScalarType targetMetric;
00200 
00201   // The ratio between Heap size and the number of simplices in the current mesh
00202   // When this value is exceeded a ClearHeap Start;
00203 
00204   float HeapSimplexRatio; 
00205 
00206         void SetTerminationFlag         (int v){tf |= v;}
00207         void ClearTerminationFlag       (int v){tf &= ~v;}
00208         bool IsTerminationFlag          (int v){return ((tf & v)!=0);}
00209 
00210         void SetTargetSimplices (int ts                 ){nTargetSimplices      = ts;   SetTerminationFlag(LOnSimplices);       }               
00211         void SetTargetVertices  (int tv                 ){nTargetVertices       = tv;   SetTerminationFlag(LOnVertices);        } 
00212         void SetTargetOperations(int to                 ){nTargetOps            = to;   SetTerminationFlag(LOnOps);                     } 
00213 
00214         void SetTargetMetric    (ScalarType tm  ){targetMetric          = tm;   SetTerminationFlag(LOMetric);           } 
00215         void SetTimeBudget              (float tb               ){timeBudget            = tb;   SetTerminationFlag(LOTime);                     } 
00216 
00217   void ClearTermination()
00218   {
00219     tf=0;
00220     nTargetSimplices=0;
00221     nTargetOps=0;
00222     targetMetric=0;
00223     timeBudget=0;
00224     nTargetVertices=0;
00225   }
00227         MeshType & m;
00228 
00229 
00230 
00232         HeapType h;
00233 
00235   // it is just a wrapper of the pointer to the localMod. 
00236   // std heap does not work for
00237   // pointers and we want pointers to have heterogenous heaps. 
00238 
00239   struct HeapElem
00240   {
00241                 inline HeapElem(){locModPtr = NULL;}
00242           ~HeapElem(){}
00243 
00245     LocModPtrType locModPtr;
00246     float pri;
00247 
00248    
00249     inline HeapElem( LocModPtrType _locModPtr)
00250     {
00251                   locModPtr = _locModPtr;
00252       pri=float(locModPtr->Priority());
00253     };
00254 
00257     inline const bool operator <(const HeapElem & h) const 
00258     { 
00259                   return (pri > h.pri);
00260                   //return (locModPtr->Priority() < h.locModPtr->Priority());
00261           }
00262 
00263     bool IsUpToDate()
00264     {
00265                         return locModPtr->IsUpToDate();
00266                 }
00267   };
00268 
00269 
00270 
00272   ~LocalOptimization(){ 
00273     typename HeapType::iterator i;
00274     for(i = h.begin(); i != h.end(); i++)
00275       delete (*i).locModPtr;
00276   };
00277         
00278         double e;
00279 
00281   bool DoOptimization()
00282   {
00283     start=clock();
00284                 nPerfmormedOps =0;
00285                 while( !GoalReached() && !h.empty())
00286                         {
00287         if(h.size()> m.SimplexNumber()*HeapSimplexRatio )  ClearHeap();
00288                                 std::pop_heap(h.begin(),h.end());
00289         LocModPtrType  locMod   = h.back().locModPtr;
00290                                 currMetric=h.back().pri;
00291         h.pop_back();
00292                                         
00293                                 if( locMod->IsUpToDate() )      
00294                                 {       
00295           //printf("popped out: %s\n",locMod->Info(m));
00296                 // check if it is feasible
00297                                         if (locMod->IsFeasible())
00298                                         {
00299                                                 nPerfmormedOps++;
00300                                                 locMod->Execute(m);
00301                                                 locMod->UpdateHeap(h);
00302                                                 }
00303                                 }
00304         //else printf("popped out unfeasible\n");
00305                                 delete locMod;
00306                         }
00307                 return !(h.empty());
00308   }
00309  
00310 // It removes from the heap all the operations that are no more 'uptodate' 
00311 // (e.g. collapses that have some recently modified vertices)
00312 // This function  is called from time to time by the doOptimization (e.g. when the heap is larger than fn*3)
00313 void ClearHeap()
00314 {
00315         typename HeapType::iterator hi;
00316         //int sz=h.size();
00317         for(hi=h.begin();hi!=h.end();)
00318         {
00319                 if(!(*hi).locModPtr->IsUpToDate())
00320                 {
00321                         delete (*hi).locModPtr;
00322                         *hi=h.back();
00323                         if(&*hi==&h.back()) 
00324                         {
00325                                 hi=h.end();
00326                                 h.pop_back();
00327                                 break;
00328                         }
00329                     h.pop_back();
00330                         continue;
00331                 }
00332                 ++hi;
00333         }
00334         //qDebug("\nReduced heap from %7i to %7i (fn %7i) ",sz,h.size(),m.fn);
00335         make_heap(h.begin(),h.end());
00336 }
00337 
00341         template <class LocalModificationType> void Init()
00342         {
00343                 vcg::tri::InitVertexIMark(m);
00344                 
00345                 // The expected size of heap depends on the type of the local modification we are using..
00346                 HeapSimplexRatio = LocalModificationType::HeapSimplexRatio();
00347                 
00348                 LocalModificationType::Init(m,h);
00349                 std::make_heap(h.begin(),h.end());
00350                 if(!h.empty()) currMetric=h.front().pri;
00351         }
00352 
00353 
00354         template <class LocalModificationType> void Finalize()
00355         {
00356                 LocalModificationType::Finalize(m,h);
00357         }
00358 
00359 
00362         bool GoalReached(){
00363                 assert ( ( ( tf & LOnSimplices  )==0) ||  ( nTargetSimplices!= -1));
00364                 assert ( ( ( tf & LOnVertices   )==0) ||  ( nTargetVertices     != -1));
00365                 assert ( ( ( tf & LOnOps                )==0) ||  ( nTargetOps          != -1));
00366                 assert ( ( ( tf & LOMetric              )==0) ||  ( targetMetric        != -1));
00367                 assert ( ( ( tf & LOTime                )==0) ||  ( timeBudget          != -1));
00368 
00369                 if ( IsTerminationFlag(LOnSimplices) && ( m.SimplexNumber()<= nTargetSimplices)) return true;
00370                 if ( IsTerminationFlag(LOnVertices)  &&  ( m.VertexNumber() <= nTargetVertices)) return true;
00371                 if ( IsTerminationFlag(LOnOps)             && (nPerfmormedOps   == nTargetOps)) return true;
00372                 if ( IsTerminationFlag(LOMetric)                 &&  ( currMetric               > targetMetric)) return true;
00373                 if ( IsTerminationFlag(LOTime)                   &&     ( (clock()-start)/(float)CLOCKS_PER_SEC > timeBudget)) return true;
00374                 return false;
00375         }
00376 
00377 
00378 
00380   void ClearHeapOld()
00381   {
00382                 typename HeapType::iterator hi;
00383                 for(hi=h.begin();hi!=h.end();++hi)
00384                         if(!(*hi).locModPtr->IsUpToDate())
00385                         {
00386                                 *hi=h.back();
00387                                 h.pop_back();
00388                                 if(hi==h.end()) break;
00389                         }
00390                         //printf("\nReduced heap from %i to %i",sz,h.size());
00391                         make_heap(h.begin(),h.end());
00392   }
00393 
00394 };//end class decimation
00395 
00396 }//end namespace
00397 #endif