tetra_edge_collapse.h

Go to the documentation of this file.

/****************************************************************************
* VCGLib                                                            o o     *
* Visual and Computer Graphics Library                            o     o   *
*                                                                _   O  _   *
* Copyright(C) 2004                                                \/)\/    *
* Visual Computing Lab                                            /\/|      *
* ISTI - Italian National Research Council                           |      *
*                                                                    \      *
* All rights reserved.                                                      *
*                                                                           *
* This program is free software; you can redistribute it and/or modify      *   
* it under the terms of the GNU General Public License as published by      *
* the Free Software Foundation; either version 2 of the License, or         *
* (at your option) any later version.                                       *
*                                                                           *
* This program is distributed in the hope that it will be useful,           *
* but WITHOUT ANY WARRANTY; without even the implied warranty of            *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
* GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
* for more details.                                                         *
*                                                                           *
****************************************************************************/
/****************************************************************************
  History
****************************************************************************/

#ifndef __VCG_DECIMATION_COLLAPSE
#define __VCG_DECIMATION_COLLAPSE

#include<vcg/complex/algorithms/local_optimization.h>
#include<vcg/simplex/tetrahedron/pos.h>
#include<vcg/complex/tetramesh/edge_collapse.h>
#include<vcg/space/point3.h>


struct FAIL{
        static int VOL(){static int vol=0; return vol++;}
        static int LKF(){static int lkf=0; return lkf++;}
        static int LKE(){static int lke=0; return lke++;}
        static int LKV(){static int lkv=0; return lkv++;}
        static int OFD(){static int ofd=0; return ofd++;}
        static int BOR(){static int bor=0; return bor++;}

};

namespace vcg{
namespace tetra{






template<class TETRA_MESH_TYPE>
class TetraEdgeCollapse: public LocalOptimization<TETRA_MESH_TYPE>::LocModType
{
 
  //typedef     typename TETRA_MESH_TYPE TETRA_MESH_TYPE;
  typedef       typename TETRA_MESH_TYPE::TetraType TetraType;
  typedef       typename TetraType::VertexType VertexType;
  typedef       typename TetraType::VertexType::CoordType CoordType;
  typedef       typename TETRA_MESH_TYPE::VertexType::ScalarType ScalarType;
  //typedef typename vcg::tri::LocalModification LocalMod;
  typedef Pos<TetraType> PosType;
  typedef PosLoop<TetraType> PosLType;
        typedef typename LocalOptimization<TETRA_MESH_TYPE>::HeapElem HeapElem;
private:

Point3<ScalarType> _NewPoint;
vcg::tetra::EdgeCollapse<TETRA_MESH_TYPE> _EC;
static int& _Imark(){ static int im=0; return im;}
PosType pos;
VertexType *vrem;
ScalarType _priority;

public:
        TetraEdgeCollapse()
                {}

        TetraEdgeCollapse(PosType p,int mark)
                {    
                        _Imark() = mark;
                        pos=p;
                        _priority = _AspectRatioMedia(p);
                }

  ~TetraEdgeCollapse()
                {}

private:

ScalarType _AspectRatioMedia(PosType p)
{
  PosLType posl=PosLType(p.T(),p.F(),p.E(),p.V());
  posl.Reset();
  int num=0;
  ScalarType ratio_media=0.f;
  while(!posl.LoopEnd())
  {
    ratio_media+=posl.T()->AspectRatio();
    posl.NextT();
    num++;
  }
  ratio_media=ratio_media/num;
  return (ratio_media);
}


ScalarType _VolumePreservingError(PosType &pos,CoordType &new_point,int nsteps)
{
  VertexType *ve0=(pos.T()->V(Tetra::VofE(pos.E(),0)));
  VertexType *ve1=(pos.T()->V(Tetra::VofE(pos.E(),1)));
  bool ext_v0=ve0->IsB();
  bool ext_v1=ve1->IsB();

  ScalarType best_error=0.f;
   if ((ext_v0)&&(!ext_v1))
      new_point=ve0->P();
   else
   if ((!ext_v0)&&(ext_v1))
      new_point=ve1->P();
   else
   if ((!ext_v0)&&(!ext_v1))
         {/*CoordType g;
         g.SetZero();
         g+=ve0->cP();
         g+=ve1->cP();
         g/=2;*/
     new_point=(ve0->cP()+ve1->cP())/2.f;
         }
   else
   if ((ext_v0)&&(ext_v1))//both are external vertex
   {
    ScalarType step=1.f/(nsteps-1);
    ScalarType Vol_Original=_EC.VolumeOriginal();
    for (int i=0;i<nsteps;i++)
    {
      best_error=1000000.f;
      ScalarType alfatemp=step*((ScalarType)i);
                        //CoordType g;
                        // g.SetZero();
                 //g+=ve0->cP()*alfatemp;
                 //g+=ve1->cP()*(1-alfatemp);
          //CoordType newPTemp=g;
      CoordType newPTemp=(ve0->cP()*alfatemp) +(ve1->cP()*(1.f-alfatemp));
      //the error is the absolute value of difference of volumes
      ScalarType error=fabs(Vol_Original-_EC.VolumeSimulateCollapse(pos,newPTemp));
      if(error<best_error)
      {
       new_point=newPTemp;
       best_error=error;
      }
    }
   }
   return (best_error);
}



public:
  
  virtual const char *Info(TETRA_MESH_TYPE &m) {
    static char buf[60];
    //sprintf(buf,"collapse %i -> %i %f\n", pos.()-&m.vert[0], pos.VFlip()-&m.vert[0],_priority);
    return buf;
  }

  ScalarType ComputePriority()
  { 
                return (_priority = _AspectRatioMedia(this->pos));
  }

  ScalarType ComputeError()
  {
          vrem=(pos.T()->V(Tetra::VofE(pos.E(),0)));
      return (_VolumePreservingError(pos,_NewPoint,5));// magic number....parametrize!
  }

  void Execute(TETRA_MESH_TYPE &tm)
  {
   // _EC.FindSets(pos);
        assert(!vrem->IsD());
    int del=_EC.DoCollapse(pos,_NewPoint);
        tm.tn-=del;
        tm.vn-=1;
  }
  
  void UpdateHeap(typename LocalOptimization<TETRA_MESH_TYPE>::HeapType & h_ret)
  {
    assert(!vrem->IsD());
                _Imark()++;
    VTIterator<TetraType> VTi(vrem->VTb(),vrem->VTi());
    while (!VTi.End())
    {
          VTi.Vt()->ComputeVolume();
      for (int j=0;j<6;j++)
      {
                vcg::tetra::Pos<TetraType> p=Pos<TetraType>(VTi.Vt(),Tetra::FofE(j,0),j,Tetra::VofE(j,0));
                assert(!p.T()->V(p.V())->IsD());
                assert(!p.T()->IsD());
        h_ret.push_back(HeapElem(new TetraEdgeCollapse<TETRA_MESH_TYPE>(p,_Imark())));
                std::push_heap(h_ret.begin(),h_ret.end());
                // update the mark of the vertices
                VTi.Vt()->V(Tetra::VofE(j,0))->IMark() = _Imark();
      }
      ++VTi;
    }
  }


  ModifierType IsOfType(){ return TetraEdgeCollapseOp;}

  bool IsFeasible(){
                                vcg::tetra::EdgeCollapse<TETRA_MESH_TYPE>::Reset();     
                                _EC.FindSets(pos);
                                ComputeError();
                                return(_EC.CheckPreconditions(pos,_NewPoint));
                                }

  bool IsUpToDate(){
                if (!pos.T()->IsD())
                                {
        VertexType *v0=pos.T()->V(Tetra::VofE(pos.E(),0));
                VertexType *v1=pos.T()->V(Tetra::VofE(pos.E(),1));
                assert(!v0->IsD());
                assert(!v1->IsD());
                        if(! (( (!v0->IsD()) && (!v1->IsD())) &&
                                                         _Imark()>=v0->IMark() &&
                                                         _Imark()>=v1->IMark()))
                        {
                                FAIL::OFD(); 
                                return false;
                        }
                        else 
                                return true;
                  }
                        else 
                        return false;
        }

        virtual ScalarType Priority() const {
                return _priority;
        }

        static void Init(TETRA_MESH_TYPE &m,typename LocalOptimization<TETRA_MESH_TYPE>::HeapType& h_ret){
                h_ret.clear();
                typename TETRA_MESH_TYPE::TetraIterator ti;
                for(ti = m.tetra.begin(); ti != m.tetra.end();++ti)
                if(!(*ti).IsD()){
                        (*ti).ComputeVolume();
           for (int j=0;j<6;j++)
                {
                        PosType p=PosType(&*ti,Tetra::FofE(j,0),j,Tetra::VofE(j,0));
                        assert(!p.T()->V(p.V())->IsD());
                        assert(!p.T()->IsD());
                        h_ret.push_back(HeapElem(new TetraEdgeCollapse<TETRA_MESH_TYPE>(p,m.IMark)));
                }
                }
        }

};
}//end namespace tetra
}//end namespace vcg
#endif