vcglib: tri_edge_collapse.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.19  2006/10/15 07:31:21  cignoni
00026   typenames and qualifiers for gcc compliance
00027 
00028   Revision 1.18  2006/10/09 20:09:40  cignoni
00029   Changed some access to VertexFaceIterator to reflect the shorter new operators.
00030 
00031   Revision 1.17  2005/10/12 10:44:01  cignoni
00032   Now creation of new edge use Ordered() constructor to comply the fact that the basic collapse is simmetric.
00033 
00034   Revision 1.16  2005/01/19 10:35:28  cignoni
00035   Better management of symmetric/asymmetric edge collapses
00036 
00037   Revision 1.15  2004/12/10 01:03:53  cignoni
00038   better comments and removed logging
00039 
00040   Revision 1.14  2004/11/23 10:34:23  cignoni
00041   passed parameters by reference in many funcs and gcc cleaning
00042 
00043   Revision 1.13  2004/10/25 16:28:32  ganovelli
00044   pos to edge
00045 
00046   Revision 1.12  2004/09/15 11:16:02  ganovelli
00047   changed P() to cP()
00048 
00049   Revision 1.11  2004/09/09 13:23:01  ponchio
00050   Header  guards typo
00051 
00052   Revision 1.10  2004/09/09 13:01:12  ponchio
00053   Linux compatible path in #include
00054 
00055   Revision 1.9  2004/09/08 15:13:29  ganovelli
00056   changes for gc
00057 
00058   Revision 1.8  2004/09/08 14:33:31  ganovelli
00059   *** empty log message ***
00060 
00061 
00062 ****************************************************************************/
00063 
00064 #ifndef __VCG_DECIMATION_TRICOLLAPSE
00065 #define __VCG_DECIMATION_TRICOLLAPSE
00066 
00067 #include<vcg/complex/trimesh/edge_collapse.h>
00068 #include<vcg/simplex/face/pos.h>
00069 #include<vcg/complex/local_optimization.h>
00070 
00071 
00072 namespace vcg{
00073 namespace tri{
00074 
00077 
00078 
00079 
00080 
00081 
00082 
00083 
00084 template<class TriMeshType, class MYTYPE>
00085 class TriEdgeCollapse: public LocalOptimization<TriMeshType>::LocModType , public EdgeCollapse<TriMeshType> 
00086 {
00087 public:
00089   class FailStat { 
00090   public:
00091         static int &Volume()           {static int vol=0; return vol;}
00092         static int &LinkConditionFace(){static int lkf=0; return lkf;}
00093         static int &LinkConditionEdge(){static int lke=0; return lke;}
00094         static int &LinkConditionVert(){static int lkv=0; return lkv;}
00095         static int &OutOfDate()        {static int ofd=0; return ofd;}
00096         static int &Border()           {static int bor=0; return bor;}
00097   static void Init() 
00098   {
00099    Volume()           =0;
00100    LinkConditionFace()=0;
00101    LinkConditionEdge()=0;
00102    LinkConditionVert()=0;
00103    OutOfDate()        =0;
00104    Border()           =0;
00105   }
00106 };
00107 protected:
00108   typedef       typename TriMeshType::FaceType FaceType;
00109   typedef       typename TriMeshType::FaceType::VertexType VertexType;
00110         typedef typename VertexType::EdgeType EdgeType;
00111   typedef       typename FaceType::VertexType::CoordType CoordType;
00112   typedef       typename TriMeshType::VertexType::ScalarType ScalarType;
00113   typedef typename LocalOptimization<TriMeshType>::HeapElem HeapElem;
00114         typedef typename LocalOptimization<TriMeshType>::HeapType HeapType;
00115 
00116   TriMeshType *mt;
00118         EdgeType pos;
00119 
00121         static int& GlobalMark(){ static int im=0; return im;}
00122 
00124         int localMark;
00125         
00127         ScalarType _priority;
00128 
00129         public:
00131         inline  TriEdgeCollapse()
00132                         {}
00134          inline TriEdgeCollapse(const EdgeType &p, int mark)
00135                         {    
00136                                 localMark = mark;
00137                                 pos=p;
00138                                 _priority = ComputePriority();
00139                         }
00140 
00141                 ~TriEdgeCollapse()
00142                         {}
00143 
00144 private:
00145 
00146 
00147 public:
00148 
00149 
00150   inline ScalarType ComputePriority()
00151   { 
00152                 _priority = Distance(pos.V(0)->cP(),pos.V(1)->cP()); 
00153     return _priority;
00154   }
00155 
00156   virtual const char *Info(TriMeshType &m) {
00157                 mt = &m;
00158     static char buf[60];
00159       sprintf(buf,"%i -> %i %g\n", pos.V(0)-&m.vert[0], pos.V(1)-&m.vert[0],-_priority);
00160    return buf;
00161   }
00162  
00163   inline void Execute(TriMeshType &m)
00164   {     
00165     CoordType MidPoint=(pos.V(0)->P()+pos.V(1)->P())/2.0;
00166     DoCollapse(m, pos, MidPoint);
00167   }
00168   
00169   static bool IsSymmetric() { return true;}
00170   
00171 
00172   // This function is called after an action to re-add in the heap elements whose priority could have been changed.
00173   // in the plain case we just put again in the heap all the edges around the vertex resulting from the previous collapse: v[1].
00174   // if the collapse is not symmetric you should add also backward edges (because v0->v1 collapse could be different from v1->v0)
00175 
00176   inline  void UpdateHeap(HeapType & h_ret)
00177   {
00178                 GlobalMark()++; int nn=0;
00179                 VertexType *v[2];
00180                 v[0]= pos.V(0);v[1]=pos.V(1);   
00181                 v[1]->IMark() = GlobalMark();
00182 
00183                 // First loop around the remaining vertex to unmark visited flags
00184     vcg::face::VFIterator<FaceType> vfi(v[1]);
00185                 while (!vfi.End()){
00186                         vfi.V1()->ClearV();
00187                         vfi.V2()->ClearV();
00188                         ++vfi;
00189                 }
00190 
00191     // Second Loop: add all the outgoing edges around v[1]
00192     // for each face add the two edges outgoing from v[1] and not visited.
00193     vfi = face::VFIterator<FaceType>(v[1]);
00194     while (!vfi.End())
00195     {
00196                         assert(!vfi.F()->IsD());
00197       for (int j=0;j<3;j++)
00198                         {
00199                                 if( !(vfi.V1()->IsV()) && (vfi.V1()->IsRW()))
00200                                 {
00201           vfi.V1()->SetV();
00202           h_ret.push_back(HeapElem(new MYTYPE(EdgeType( vfi.V(),vfi.V1() ),GlobalMark())));
00203           std::push_heap(h_ret.begin(),h_ret.end());
00204           if(! this->IsSymmetric()){
00205             h_ret.push_back(HeapElem(new MYTYPE(EdgeType( vfi.V1(),vfi.V()),GlobalMark())));
00206             std::push_heap(h_ret.begin(),h_ret.end());
00207           }
00208         }
00209                                 if(  !(vfi.V2()->IsV()) && (vfi.V2()->IsRW()))
00210                                 {
00211                                         vfi.V2()->SetV();
00212           h_ret.push_back(HeapElem(new MYTYPE(EdgeType(vfi.F()->V(vfi.I()),vfi.F()->V2(vfi.I())),GlobalMark())));
00213           std::push_heap(h_ret.begin(),h_ret.end());
00214           if(! this->IsSymmetric()){
00215             h_ret.push_back(HeapElem(new MYTYPE(EdgeType (vfi.F()->V1(vfi.I()),vfi.F()->V(vfi.I())),GlobalMark())));
00216             std::push_heap(h_ret.begin(),h_ret.end());
00217           }
00218         }
00219         //        if(vfi.V1()->IsRW() && vfi.V2()->IsRW() )
00220 //        {
00221 //          h_ret.push_back(HeapElem(new MYTYPE(EdgeType(vfi.V1(),vfi.V2()),this->GlobalMark())));
00222 //          std::push_heap(h_ret.begin(),h_ret.end());
00223 //          if(IsSymmetric()){
00224 //            h_ret.push_back(HeapElem(new MYTYPE(EdgeType(vfi.V2(),vfi.V1()), this->GlobalMark())));
00225 //            std::push_heap(h_ret.begin(),h_ret.end());
00226 //          }
00227 //        }
00228 
00229                         }
00230       ++vfi;nn++;
00231     }
00232 //              printf("ADDED %d\n",nn);
00233   }
00234 
00235   ModifierType IsOfType(){ return TriEdgeCollapseOp;}
00236 
00237   inline bool IsFeasible(){
00238                 return LinkConditions(pos);
00239         }
00240 
00241   inline bool IsUpToDate(){
00242    // if(pos.V(1)->IsD()) {
00243                         //      ++FailStat::OutOfDate();
00244                         //      return false;
00245                         //}
00246                         //
00247    // if(pos.V(1)->IsD()) {
00248                         //      ++FailStat::OutOfDate();
00249                         //      return false;
00250                         //}
00251 
00252                   VertexType *v0=pos.V(0);
00253                         VertexType *v1=pos.V(1);
00254                         
00255                         //if(! (( (!v0->IsD()) && (!v1->IsD())) &&
00256                         //                               localMark>=v0->IMark() &&
00257                         //                               localMark>=v1->IMark()))
00258                         if( v0->IsD() || v1->IsD() ||
00259                                  localMark < v0->IMark()  ||
00260                          localMark < v1->IMark()   )
00261                         {
00262                                 ++FailStat::OutOfDate();
00263                                 return false;
00264                         }
00265                                 return true;
00266         }
00267 
00268         virtual ScalarType Priority() const {
00269         return _priority;
00270   }
00271 
00272         static void Init(TriMeshType&m,HeapType&h_ret){
00273                 h_ret.clear();
00274                 typename TriMeshType::FaceIterator fi;
00275                 for(fi = m.face.begin(); fi != m.face.end();++fi)
00276                 if(!(*fi).IsD()){
00277                    for (int j=0;j<3;j++)
00278       {
00279         EdgeType p=EdgeType::OrderedEdge((*fi).V(j),(*fi).V((j+1)%3));
00280         h_ret.push_back(HeapElem(new MYTYPE(p, IMark(m))));
00281         //printf("Inserting in heap coll %3i ->%3i %f\n",p.V()-&m.vert[0],p.VFlip()-&m.vert[0],h_ret.back().locModPtr->Priority());
00282       }
00283                 }
00284         }
00285 
00286 };
00287 }//end namespace tri
00288 }//end namespace vcg
00289 
00290 #endif