1 /****************************************************************************
2 * VCGLib o o *
3 * Visual and Computer Graphics Library o o *
4 * _ O _ *
5 * Copyright(C) 2004-2016 \/)\/ *
6 * Visual Computing Lab /\/| *
7 * ISTI - Italian National Research Council | *
8 * \ *
9 * All rights reserved. *
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 * This program is distributed in the hope that it will be useful, *
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
20 * for more details. *
21 * *
22 ****************************************************************************/
23 /****************************************************************************
24 History
25 ****************************************************************************/
26
27 #ifndef __VCG_DECIMATION_COLLAPSE
28 #define __VCG_DECIMATION_COLLAPSE
29
30 #include<vcg/complex/algorithms/local_optimization.h>
31 #include<vcg/simplex/tetrahedron/pos.h>
32 #include<vcg/complex/tetramesh/edge_collapse.h>
33 #include<vcg/space/point3.h>
34
35
36 struct FAIL{
VOLFAIL37 static int VOL(){static int vol=0; return vol++;}
LKFFAIL38 static int LKF(){static int lkf=0; return lkf++;}
LKEFAIL39 static int LKE(){static int lke=0; return lke++;}
LKVFAIL40 static int LKV(){static int lkv=0; return lkv++;}
OFDFAIL41 static int OFD(){static int ofd=0; return ofd++;}
BORFAIL42 static int BOR(){static int bor=0; return bor++;}
43
44 };
45
46 namespace vcg{
47 namespace tetra{
48
49 /** \addtogroup tetramesh */
50 /*@{*/
51 /// This Class is specialization of LocalModification for the edge collapse
52 /// It wraps the atomic operation EdgeCollapse to be used in a optimizatin routine.
53 /// Note that it has knowledge of the heap of the class LocalOptimization because
54 /// it is responsible of updating it after a collapse has been performed
55
56 template<class TETRA_MESH_TYPE>
57 class TetraEdgeCollapse: public LocalOptimization<TETRA_MESH_TYPE>::LocModType
58 {
59
60 /// The tetrahedral mesh type
61 //typedef typename TETRA_MESH_TYPE TETRA_MESH_TYPE;
62 /// The tetrahedron type
63 typedef typename TETRA_MESH_TYPE::TetraType TetraType;
64 /// The vertex type
65 typedef typename TetraType::VertexType VertexType;
66 /// The coordinate type
67 typedef typename TetraType::VertexType::CoordType CoordType;
68 /// The scalar type
69 typedef typename TETRA_MESH_TYPE::VertexType::ScalarType ScalarType;
70 /////the base type class
71 //typedef typename vcg::tri::LocalModification LocalMod;
72 /// The HEdgePos type
73 typedef Pos<TetraType> PosType;
74 /// The HEdgePos Loop type
75 typedef PosLoop<TetraType> PosLType;
76 /// definition of the heap element
77 typedef typename LocalOptimization<TETRA_MESH_TYPE>::HeapElem HeapElem;
78 private:
79
80 ///the new point that substitute the edge
81 Point3<ScalarType> _NewPoint;
82 ///the pointer to edge collapser method
83 vcg::tetra::EdgeCollapse<TETRA_MESH_TYPE> _EC;
84 ///mark for up_dating
_Imark()85 static int& _Imark(){ static int im=0; return im;}
86 ///the pos of collapse
87 PosType pos;
88 ///pointer to vertex that remain
89 VertexType *vrem;
90 /// priority in the heap
91 ScalarType _priority;
92
93 public:
94 /// Default Constructor
TetraEdgeCollapse()95 TetraEdgeCollapse()
96 {}
97
98 ///Constructor with postype
TetraEdgeCollapse(PosType p,int mark)99 TetraEdgeCollapse(PosType p,int mark)
100 {
101 _Imark() = mark;
102 pos=p;
103 _priority = _AspectRatioMedia(p);
104 }
105
~TetraEdgeCollapse()106 ~TetraEdgeCollapse()
107 {}
108
109 private:
110
111 ///Return the aspect Ratio media of the tetrahedrons
112 ///that share the adge to collapse
_AspectRatioMedia(PosType p)113 ScalarType _AspectRatioMedia(PosType p)
114 {
115 PosLType posl=PosLType(p.T(),p.F(),p.E(),p.V());
116 posl.Reset();
117 int num=0;
118 ScalarType ratio_media=0.f;
119 while(!posl.LoopEnd())
120 {
121 ratio_media+=posl.T()->AspectRatio();
122 posl.NextT();
123 num++;
124 }
125 ratio_media=ratio_media/num;
126 return (ratio_media);
127 }
128
129
130 ///Modify pos and alfa to obtain the collapse that minimize the error
_VolumePreservingError(PosType & pos,CoordType & new_point,int nsteps)131 ScalarType _VolumePreservingError(PosType &pos,CoordType &new_point,int nsteps)
132 {
133 VertexType *ve0=(pos.T()->V(Tetra::VofE(pos.E(),0)));
134 VertexType *ve1=(pos.T()->V(Tetra::VofE(pos.E(),1)));
135 bool ext_v0=ve0->IsB();
136 bool ext_v1=ve1->IsB();
137
138 ScalarType best_error=0.f;
139 if ((ext_v0)&&(!ext_v1))
140 new_point=ve0->P();
141 else
142 if ((!ext_v0)&&(ext_v1))
143 new_point=ve1->P();
144 else
145 if ((!ext_v0)&&(!ext_v1))
146 {/*CoordType g;
147 g.SetZero();
148 g+=ve0->cP();
149 g+=ve1->cP();
150 g/=2;*/
151 new_point=(ve0->cP()+ve1->cP())/2.f;
152 }
153 else
154 if ((ext_v0)&&(ext_v1))//both are external vertex
155 {
156 ScalarType step=1.f/(nsteps-1);
157 ScalarType Vol_Original=_EC.VolumeOriginal();
158 for (int i=0;i<nsteps;i++)
159 {
160 best_error=1000000.f;
161 ScalarType alfatemp=step*((ScalarType)i);
162 //CoordType g;
163 // g.SetZero();
164 //g+=ve0->cP()*alfatemp;
165 //g+=ve1->cP()*(1-alfatemp);
166 //CoordType newPTemp=g;
167 CoordType newPTemp=(ve0->cP()*alfatemp) +(ve1->cP()*(1.f-alfatemp));
168 //the error is the absolute value of difference of volumes
169 ScalarType error=fabs(Vol_Original-_EC.VolumeSimulateCollapse(pos,newPTemp));
170 if(error<best_error)
171 {
172 new_point=newPTemp;
173 best_error=error;
174 }
175 }
176 }
177 return (best_error);
178 }
179
180
181
182 public:
183
Info(TETRA_MESH_TYPE & m)184 virtual const char *Info(TETRA_MESH_TYPE &m) {
185 static char buf[60];
186 //sprintf(buf,"collapse %i -> %i %f\n", pos.()-&m.vert[0], pos.VFlip()-&m.vert[0],_priority);
187 return buf;
188 }
189
ComputePriority()190 ScalarType ComputePriority()
191 {
192 return (_priority = _AspectRatioMedia(this->pos));
193 }
194
ComputeError()195 ScalarType ComputeError()
196 {
197 vrem=(pos.T()->V(Tetra::VofE(pos.E(),0)));
198 return (_VolumePreservingError(pos,_NewPoint,5));// magic number....parametrize!
199 }
200
Execute(TETRA_MESH_TYPE & tm)201 void Execute(TETRA_MESH_TYPE &tm)
202 {
203 // _EC.FindSets(pos);
204 assert(!vrem->IsD());
205 int del=_EC.DoCollapse(pos,_NewPoint);
206 tm.tn-=del;
207 tm.vn-=1;
208 }
209
UpdateHeap(typename LocalOptimization<TETRA_MESH_TYPE>::HeapType & h_ret)210 void UpdateHeap(typename LocalOptimization<TETRA_MESH_TYPE>::HeapType & h_ret)
211 {
212 assert(!vrem->IsD());
213 _Imark()++;
214 VTIterator<TetraType> VTi(vrem->VTb(),vrem->VTi());
215 while (!VTi.End())
216 {
217 VTi.Vt()->ComputeVolume();
218 for (int j=0;j<6;j++)
219 {
220 vcg::tetra::Pos<TetraType> p=Pos<TetraType>(VTi.Vt(),Tetra::FofE(j,0),j,Tetra::VofE(j,0));
221 assert(!p.T()->V(p.V())->IsD());
222 assert(!p.T()->IsD());
223 h_ret.push_back(HeapElem(new TetraEdgeCollapse<TETRA_MESH_TYPE>(p,_Imark())));
224 std::push_heap(h_ret.begin(),h_ret.end());
225 // update the mark of the vertices
226 VTi.Vt()->V(Tetra::VofE(j,0))->IMark() = _Imark();
227 }
228 ++VTi;
229 }
230 }
231
232 /// return the type of operation
233
IsOfType()234 ModifierType IsOfType(){ return TetraEdgeCollapseOp;}
235
IsFeasible()236 bool IsFeasible(){
237 vcg::tetra::EdgeCollapse<TETRA_MESH_TYPE>::Reset();
238 _EC.FindSets(pos);
239 ComputeError();
240 return(_EC.CheckPreconditions(pos,_NewPoint));
241 }
242
IsUpToDate()243 bool IsUpToDate(){
244 if (!pos.T()->IsD())
245 {
246 VertexType *v0=pos.T()->V(Tetra::VofE(pos.E(),0));
247 VertexType *v1=pos.T()->V(Tetra::VofE(pos.E(),1));
248 assert(!v0->IsD());
249 assert(!v1->IsD());
250 if(! (( (!v0->IsD()) && (!v1->IsD())) &&
251 _Imark()>=v0->IMark() &&
252 _Imark()>=v1->IMark()))
253 {
254 FAIL::OFD();
255 return false;
256 }
257 else
258 return true;
259 }
260 else
261 return false;
262 }
263
Priority()264 virtual ScalarType Priority() const {
265 return _priority;
266 }
267
268 /// perform initialization
Init(TETRA_MESH_TYPE & m,typename LocalOptimization<TETRA_MESH_TYPE>::HeapType & h_ret)269 static void Init(TETRA_MESH_TYPE &m,typename LocalOptimization<TETRA_MESH_TYPE>::HeapType& h_ret){
270 h_ret.clear();
271 typename TETRA_MESH_TYPE::TetraIterator ti;
272 for(ti = m.tetra.begin(); ti != m.tetra.end();++ti)
273 if(!(*ti).IsD()){
274 (*ti).ComputeVolume();
275 for (int j=0;j<6;j++)
276 {
277 PosType p=PosType(&*ti,Tetra::FofE(j,0),j,Tetra::VofE(j,0));
278 assert(!p.T()->V(p.V())->IsD());
279 assert(!p.T()->IsD());
280 h_ret.push_back(HeapElem(new TetraEdgeCollapse<TETRA_MESH_TYPE>(p,m.IMark)));
281 }
282 }
283 }
284
285 };
286 }//end namespace tetra
287 }//end namespace vcg
288 #endif
289