$darkmode
VCG Library
refine.h
1 /***********F*****************************************************************
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 #ifndef __VCGLIB_REFINE
25 #define __VCGLIB_REFINE
26 
27 #include <functional>
28 #include <map>
29 #include <vcg/space/sphere3.h>
30 #include <vcg/space/plane3.h>
31 #include <vcg/complex/algorithms/clean.h>
32 #include <vcg/space/texcoord2.h>
33 #include <vcg/space/triangle3.h>
34 
35 namespace vcg{
36 namespace tri{
37 
38 /* A very short intro about the generic refinement framework,
39  the main fuction is the
40 
41  template<class MESH_TYPE,class MIDPOINT, class EDGEPRED>
42  bool RefineE(MESH_TYPE &m, MIDPOINT mid, EDGEPRED ep,bool RefineSelected=false, CallBackPos *cb = 0)
43 
44  You have to provide two functor objects to this, one for deciding what edge has to be spltted and one to decide position and new values for the attributes of the new point.
45 
46  for example the minimal EDGEPRED is
47 
48  template <class MESH_TYPE, class FLT> class EdgeLen
49  {
50  public:
51  FLT thr2;
52  bool operator()(face::Pos<typename MESH_TYPE::FaceType> ep) const
53  {
54  return SquaredDistance(ep.f->V(ep.z)->P(), ep.f->V1(ep.z)->P())>thr2;
55  }
56  };
57 
58  With a bit of patience you can customize to make also slicing operation.
59 
60 */
61 
62 
63 /* The table which encodes how to subdivide a triangle depending
64  on the splitted edges is organized as such:
65 
66  TriNum (the first number): encodes the number of triangles
67  TV (the following 4 triples): encodes the resulting triangles where
68  0, 1, 2 are the original vertices of the triangles and 3, 4, 5
69  (mp01, mp12, mp20) are the midpoints of the three edges.
70 
71  In the case two edges are splitted the triangle has 2 possible splittings:
72 we need to choose a diagonal of the resulting trapezoid.
73 'swap' encodes the two diagonals to test: if diag1 < diag2 we swap the diagonal
74 like this (140, 504 -> 150, 514) (the second vertex of each triangles is replaced
75  by the first vertex of the other one).
76  2
77  / \
78  5---4
79  / \
80  0-------1
81 
82 */
83 
84 class Split {
85 public:
86  int TriNum; // number of triangles
87  int TV[4][3]; // The triangles coded as the following convention
88  // 0..2 vertici originali del triangolo
89  // 3..5 mp01, mp12, mp20 midpoints of the three edges
90  int swap[2][2]; // the two diagonals to test for swapping
91  int TE[4][3]; // the edge-edge correspondence between refined triangles and the old one
92  // (3) means the edge of the new triangle is internal;
93 };
94 
95 const Split SplitTab[8]={
96 /* m20 m12 m01 */
97 /* 0 0 0 */ {1, {{0,1,2},{0,0,0},{0,0,0},{0,0,0}}, {{0,0},{0,0}}, {{0,1,2},{0,0,0},{0,0,0},{0,0,0}} },
98 /* 0 0 1 */ {2, {{0,3,2},{3,1,2},{0,0,0},{0,0,0}}, {{0,0},{0,0}}, {{0,3,2},{0,1,3},{0,0,0},{0,0,0}} },
99 /* 0 1 0 */ {2, {{0,1,4},{0,4,2},{0,0,0},{0,0,0}}, {{0,0},{0,0}}, {{0,1,3},{3,1,2},{0,0,0},{0,0,0}} },
100 /* 0 1 1 */ {3, {{3,1,4},{0,3,2},{4,2,3},{0,0,0}}, {{0,4},{3,2}}, {{0,1,3},{0,3,2},{1,3,3},{0,0,0}} },
101 /* 1 0 0 */ {2, {{0,1,5},{5,1,2},{0,0,0},{0,0,0}}, {{0,0},{0,0}}, {{0,3,2},{3,1,2},{0,0,0},{0,0,0}} },
102 /* 1 0 1 */ {3, {{0,3,5},{3,1,5},{2,5,1},{0,0,0}}, {{3,2},{5,1}}, {{0,3,2},{0,3,3},{2,3,1},{0,0,0}} },
103 /* 1 1 0 */ {3, {{2,5,4},{0,1,5},{4,5,1},{0,0,0}}, {{0,4},{5,1}}, {{2,3,1},{0,3,2},{3,3,1},{0,0,0}} },
104 /* 1 1 1 */ //{4, {{0,3,5},{3,1,4},{5,4,2},{3,4,5}}, {{0,0},{0,0}}, {{0,3,2},{0,1,3},{3,1,2},{3,3,3}} },
105 /* 1 1 1 */ {4, {{3,4,5},{0,3,5},{3,1,4},{5,4,2}}, {{0,0},{0,0}}, {{3,3,3},{0,3,2},{0,1,3},{3,1,2}} },
106 };
107 
108 
109 template <class MeshType>
110 struct BaseInterpolator
111 {
112  typedef typename face::Pos<typename MeshType::FaceType> PosType;
113  typedef typename MeshType::VertexType VertexType;
114  void operator()(VertexType &, PosType ){}
115 };
116 
117 // Basic subdivision class
118 // This class must provide methods for finding the position of the newly created vertices
119 // In this implemenation we simply put the new vertex in the MidPoint position.
120 // Color and TexCoords are interpolated accordingly.
121 // This subdivision class allow also the correct interpolation of userdefined data by
122 // providing, in the constructor, an interpolator functor that will be called for each new vertex to be created.
123 
124 template<class MESH_TYPE, class InterpolatorFunctorType = BaseInterpolator< MESH_TYPE> >
125 struct MidPoint
126 {
127  typedef typename face::Pos<typename MESH_TYPE::FaceType> PosType;
128  typedef typename MESH_TYPE::VertexType VertexType;
129 
130  MidPoint(MESH_TYPE *_mp,
131  InterpolatorFunctorType *_intFunc=0) {
132  mp=_mp;
133  intFunc =_intFunc;
134  }
135 
136  MESH_TYPE *mp;
137  InterpolatorFunctorType *intFunc;
138 
139  void operator()(VertexType &nv, PosType ep){
140  assert(mp);
141  VertexType *V0 = ep.V() ;
142  VertexType *V1 = ep.VFlip() ;
143  if(V0 > V1) std::swap(V1,V0);
144 
145  nv.P()= (V0->P()+V1->P())/2.0;
146 
147  if( tri::HasPerVertexNormal(*mp))
148  nv.N()= (V0->N()+V1->N()).normalized();
149 
150  if( tri::HasPerVertexColor(*mp))
151  nv.C().lerp(V0->C(),V1->C(),.5f);
152 
153  if( tri::HasPerVertexQuality(*mp))
154  nv.Q() = (V0->Q()+V1->Q()) / 2.0;
155 
156  if( tri::HasPerVertexTexCoord(*mp))
157  nv.T().P() = (V0->T().P()+V1->T().P()) / 2.0;
158  if(intFunc)
159  (*intFunc)(nv,ep);
160  }
161 
162  Color4<typename MESH_TYPE::ScalarType> WedgeInterp(Color4<typename MESH_TYPE::ScalarType> &c0, Color4<typename MESH_TYPE::ScalarType> &c1)
163  {
164  Color4<typename MESH_TYPE::ScalarType> cc;
165  return cc.lerp(c0,c1,0.5f);
166  }
167 
168  template<class FL_TYPE>
169  TexCoord2<FL_TYPE,1> WedgeInterp(TexCoord2<FL_TYPE,1> &t0, TexCoord2<FL_TYPE,1> &t1)
170  {
171  TexCoord2<FL_TYPE,1> tmp;
172  assert(t0.n()== t1.n());
173  tmp.n()=t0.n();
174  tmp.t()=(t0.t()+t1.t())/2.0;
175  return tmp;
176  }
177 };
178 
179 
180 
181 template<class MESH_TYPE>
182 struct MidPointArc
183 {
184  void operator()(typename MESH_TYPE::VertexType &nv, face::Pos<typename MESH_TYPE::FaceType> ep)
185  {
186  const typename MESH_TYPE::ScalarType EPS =1e-10;
187  typename MESH_TYPE::CoordType vp = (ep.f->V(ep.z)->P()+ep.f->V1(ep.z)->P())/2.0;
188  typename MESH_TYPE::CoordType n = (ep.f->V(ep.z)->N()+ep.f->V1(ep.z)->N())/2.0;
189  typename MESH_TYPE::ScalarType w =n.Norm();
190  if(w<EPS) { nv.P()=(ep.f->V(ep.z)->P()+ep.f->V1(ep.z)->P())/2.0; return;}
191  n/=w;
192  typename MESH_TYPE::CoordType d0 = ep.f->V(ep.z)->P() - vp;
193  typename MESH_TYPE::CoordType d1 = ep.f->V1(ep.z)->P()- vp;
194  typename MESH_TYPE::ScalarType d=Distance(ep.f->V(ep.z)->P(),ep.f->V1(ep.z)->P())/2.0;
195 
196  typename MESH_TYPE::CoordType nn = ep.f->V1(ep.z)->N() ^ ep.f->V(ep.z)->N();
197  typename MESH_TYPE::CoordType np = n ^ d0; //vector perpendicular to the edge plane, normal is interpolated
198  np.Normalize();
199  double sign=1;
200  if(np*nn<0) sign=-1; // se le normali non divergono sposta il punto nella direzione opposta
201 
202  typename MESH_TYPE::CoordType n0=ep.f->V(ep.z)->N() -np*(ep.f->V(ep.z)->N()*np);
203  n0.Normalize();
204  typename MESH_TYPE::CoordType n1=ep.f->V1(ep.z)->N()-np*(ep.f->V1(ep.z)->N()*np);
205  assert(n1.Norm()>EPS);
206  n1.Normalize();
207  typename MESH_TYPE::ScalarType cosa0=n0*n;
208  typename MESH_TYPE::ScalarType cosa1=n1*n;
209  if(2-cosa0-cosa1<EPS) {nv.P()=(ep.f->V(ep.z)->P()+ep.f->V1(ep.z)->P())/2.0;return;}
210  typename MESH_TYPE::ScalarType cosb0=(d0*n)/d;
211  typename MESH_TYPE::ScalarType cosb1=(d1*n)/d;
212  assert(1+cosa0>EPS);
213  assert(1+cosa1>EPS);
214  typename MESH_TYPE::ScalarType delta0=d*(cosb0 +sqrt( ((1-cosb0*cosb0)*(1-cosa0))/(1+cosa0)) );
215  typename MESH_TYPE::ScalarType delta1=d*(cosb1 +sqrt( ((1-cosb1*cosb1)*(1-cosa1))/(1+cosa1)) );
216  assert(delta0+delta1<2*d);
217  nv.P()=vp+n*sign*(delta0+delta1)/2.0;
218  return ;
219  }
220 
221  // Aggiunte in modo grezzo le due wedgeinterp
222  Color4<typename MESH_TYPE::ScalarType> WedgeInterp(Color4<typename MESH_TYPE::ScalarType> &c0, Color4<typename MESH_TYPE::ScalarType> &c1)
223  {
224  Color4<typename MESH_TYPE::ScalarType> cc;
225  return cc.lerp(c0,c1,0.5f);
226  }
227 
228  template<class FL_TYPE>
229  TexCoord2<FL_TYPE,1> WedgeInterp(TexCoord2<FL_TYPE,1> &t0, TexCoord2<FL_TYPE,1> &t1)
230  {
231  TexCoord2<FL_TYPE,1> tmp;
232  assert(t0.n()== t1.n());
233  tmp.n()=t0.n();
234  tmp.t()=(t0.t()+t1.t())/2.0;
235  return tmp;
236  }
237 
238 };
239 
240 /*
241 Versione Della Midpoint basata sul paper:
242 S. Karbacher, S. Seeger, G. Hausler
243 A non linear subdivision scheme for triangle meshes
244 
245  Non funziona!
246  Almeno due problemi:
247  1) il verso delle normali influenza il risultato (e.g. si funziona solo se le normali divergono)
248  Risolvibile controllando se le normali divergono
249  2) gli archi vanno calcolati sul piano definito dalla normale interpolata e l'edge.
250  funziona molto meglio nelle zone di sella e non semplici.
251 
252 */
253 template<class MESH_TYPE>
254 struct MidPointArcNaive
255 {
256  typename MESH_TYPE::CoordType operator()(face::Pos<typename MESH_TYPE::FaceType> ep)
257  {
258 
259  typename MESH_TYPE::CoordType vp = (ep.f->V(ep.z)->P()+ep.f->V1(ep.z)->P())/2.0;
260  typename MESH_TYPE::CoordType n = (ep.f->V(ep.z)->N()+ep.f->V1(ep.z)->N())/2.0;
261  n.Normalize();
262  typename MESH_TYPE::CoordType d0 = ep.f->V(ep.z)->P() - vp;
263  typename MESH_TYPE::CoordType d1 = ep.f->V1(ep.z)->P()- vp;
264  typename MESH_TYPE::ScalarType d=Distance(ep.f->V(ep.z)->P(),ep.f->V1(ep.z)->P())/2.0;
265 
266  typename MESH_TYPE::ScalarType cosa0=ep.f->V(ep.z)->N()*n;
267  typename MESH_TYPE::ScalarType cosa1=ep.f->V1(ep.z)->N()*n;
268  typename MESH_TYPE::ScalarType cosb0=(d0*n)/d;
269  typename MESH_TYPE::ScalarType cosb1=(d1*n)/d;
270 
271  typename MESH_TYPE::ScalarType delta0=d*(cosb0 +sqrt( ((1-cosb0*cosb0)*(1-cosa0))/(1+cosa0)) );
272  typename MESH_TYPE::ScalarType delta1=d*(cosb1 +sqrt( ((1-cosb1*cosb1)*(1-cosa1))/(1+cosa1)) );
273 
274  return vp+n*(delta0+delta1)/2.0;
275  }
276 };
277 
278 
279 // Basic Predicate that tells if a given edge must be splitted.
280 // the constructure requires the threshold.
281 // VERY IMPORTANT REQUIREMENT: this function must be symmetric
282 // e.g. it must return the same value if the Pos is VFlipped.
283 // If this function is not symmetric the Refine can crash.
284 
285 template <class MESH_TYPE, class FLT>
286 class EdgeLen
287 {
288  FLT squaredThr;
289 public:
290  EdgeLen(){};
291  EdgeLen(FLT threshold) {setThr(threshold);}
292  void setThr(FLT threshold) {squaredThr = threshold*threshold; }
293  bool operator()(face::Pos<typename MESH_TYPE::FaceType> ep) const
294  {
295  return SquaredDistance(ep.V()->P(), ep.VFlip()->P())>squaredThr;
296  }
297 };
298 
299 /*********************************************************/
300 /*********************************************************
301 
302 Given a mesh the following function refines it according to two functor objects:
303 
304 - a predicate that tells if a given edge must be splitted
305 
306 - a functor that gives you the new position of the created vertices (starting from an edge)
307 
308 If RefineSelected is true only selected faces are taken into account for being splitted.
309 
310 Requirement: FF Adjacency and Manifoldness
311 
312 **********************************************************/
313 /*********************************************************/
314 template <class VertexPointer>
315 class RefinedFaceData
316  {
317  public:
318  RefinedFaceData(){
319  ep[0] = ep[1] = ep[2] = false;
320  vp[0] = vp[1] = vp[2] = NULL;
321  }
322  bool ep[3];
323  VertexPointer vp[3];
324  };
325 
326 template<class MESH_TYPE,class MIDPOINT, class EDGEPRED>
327 bool RefineE(MESH_TYPE &m, MIDPOINT &mid, EDGEPRED &ep,bool RefineSelected=false, CallBackPos *cb = 0)
328 {
329  // common typenames
330  typedef typename MESH_TYPE::VertexIterator VertexIterator;
331  typedef typename MESH_TYPE::FaceIterator FaceIterator;
332  typedef typename MESH_TYPE::VertexPointer VertexPointer;
333  typedef typename MESH_TYPE::FacePointer FacePointer;
334  typedef typename MESH_TYPE::FaceType FaceType;
335  typedef typename MESH_TYPE::FaceType::TexCoordType TexCoordType;
336  assert(tri::HasFFAdjacency(m));
337  tri::UpdateFlags<MESH_TYPE>::FaceBorderFromFF(m);
338  typedef face::Pos<FaceType> PosType;
339 
340  int j,NewVertNum=0,NewFaceNum=0;
341 
342  typedef RefinedFaceData<VertexPointer> RFD;
343  typedef typename MESH_TYPE :: template PerFaceAttributeHandle<RFD> HandleType;
344  HandleType RD = tri::Allocator<MESH_TYPE>:: template AddPerFaceAttribute<RFD> (m,std::string("RefineData"));
345 
346  // Callback stuff
347  int step=0;
348  int PercStep=std::max(1,m.fn/33);
349 
350  // First Loop: We analyze the mesh to compute the number of the new faces and new vertices
351  FaceIterator fi;
352  for(fi=m.face.begin(),j=0;fi!=m.face.end();++fi) if(!(*fi).IsD())
353  {
354  if(cb && (++step%PercStep)==0) (*cb)(step/PercStep,"Refining...");
355  // skip unselected faces if necessary
356  if(RefineSelected && !(*fi).IsS()) continue;
357 
358  for(j=0;j<3;j++)
359  {
360  if(RD[fi].ep[j]) continue;
361 
362  PosType edgeCur(&*fi,j);
363  if(RefineSelected && ! edgeCur.FFlip()->IsS()) continue;
364  if(!ep(edgeCur)) continue;
365 
366  RD[edgeCur.F()].ep[edgeCur.E()]=true;
367  ++NewFaceNum;
368  ++NewVertNum;
369  assert(edgeCur.IsManifold());
370  if(!edgeCur.IsBorder())
371  {
372  edgeCur.FlipF();
373  edgeCur.F()->SetV();
374  RD[edgeCur.F()].ep[edgeCur.E()]=true;
375  ++NewFaceNum;
376  }
377  }
378 
379  } // end face loop
380 
381  if(NewVertNum ==0 )
382  {
383  tri::Allocator<MESH_TYPE> :: template DeletePerFaceAttribute<RefinedFaceData<VertexPointer> > (m,RD);
384  return false;
385  }
386  VertexIterator lastv = tri::Allocator<MESH_TYPE>::AddVertices(m,NewVertNum);
387 
388  // Secondo loop: We initialize a edge->vertex map
389 
390  for(fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
391  {
392  if(cb && (++step%PercStep)==0)(*cb)(step/PercStep,"Refining...");
393  for(j=0;j<3;j++)
394  {
395  // skip unselected faces if necessary
396  if(RefineSelected && !(*fi).IsS()) continue;
397  for(j=0;j<3;j++)
398  {
399  PosType edgeCur(&*fi,j);
400  if(RefineSelected && ! edgeCur.FFlip()->IsS()) continue;
401 
402  if( RD[edgeCur.F()].ep[edgeCur.E()] && RD[edgeCur.F()].vp[edgeCur.E()] ==0 )
403  {
404  RD[edgeCur.F()].vp[edgeCur.E()] = &*lastv;
405  mid(*lastv,edgeCur);
406  if(!edgeCur.IsBorder())
407  {
408  edgeCur.FlipF();
409  assert(RD[edgeCur.F()].ep[edgeCur.E()]);
410  RD[edgeCur.F()].vp[edgeCur.E()] = &*lastv;
411  }
412  ++lastv;
413  }
414  }
415  }
416  }
417 
418  assert(lastv==m.vert.end()); // critical assert: we MUST have used all the vertex that we forecasted we need
419 
420  FaceIterator lastf = tri::Allocator<MESH_TYPE>::AddFaces(m,NewFaceNum);
421  FaceIterator oldendf = lastf;
422 
423 /*
424  * v0
425  *
426  *
427  * f0
428  *
429  * mp01 f3 mp02
430  *
431  *
432  * f1 f2
433  *
434  *v1 mp12 v2
435  *
436 */
437 
438  VertexPointer vv[6]; // The six vertices that arise in the single triangle splitting
439  // 0..2 Original triangle vertices
440  // 3..5 mp01, mp12, mp20 midpoints of the three edges
441  FacePointer nf[4]; // The (up to) four faces that are created.
442 
443  TexCoordType wtt[6]; // per ogni faccia sono al piu' tre i nuovi valori
444  // di texture per wedge (uno per ogni edge)
445 
446  for(fi=m.face.begin();fi!=oldendf;++fi) if(!(*fi).IsD())
447  {
448  if(cb && (++step%PercStep)==0)
449  (*cb)(step/PercStep,"Refining...");
450  vv[0]=(*fi).V(0);
451  vv[1]=(*fi).V(1);
452  vv[2]=(*fi).V(2);
453  vv[3] = RD[fi].vp[0];
454  vv[4] = RD[fi].vp[1];
455  vv[5] = RD[fi].vp[2];
456 
457  int ind = ((vv[3] != NULL) ? 1 : 0) + ((vv[4] != NULL) ? 2 : 0) + ((vv[5] != NULL) ? 4 : 0);
458 
459  nf[0]=&*fi;
460  int i;
461  for(i=1;i<SplitTab[ind].TriNum;++i){
462  nf[i]=&*lastf; ++lastf;
463  if(RefineSelected || (*fi).IsS()) (*nf[i]).SetS();
464  nf[i]->ImportData(*fi);
465 // if(tri::HasPerFaceColor(m))
466 // nf[i]->C()=(*fi).cC();
467  }
468 
469 
470  if(tri::HasPerWedgeTexCoord(m))
471  for(i=0;i<3;++i)
472  {
473  wtt[i]=(*fi).WT(i);
474  wtt[3+i]=mid.WedgeInterp((*fi).WT(i),(*fi).WT((i+1)%3));
475  }
476 
477  int orgflag = (*fi).Flags();
478  for (i=0; i<SplitTab[ind].TriNum; ++i)
479  for(j=0;j<3;++j)
480  {
481  (*nf[i]).V(j)=&*vv[SplitTab[ind].TV[i][j]];
482 
483  if(tri::HasPerWedgeTexCoord(m)) //analogo ai vertici...
484  (*nf[i]).WT(j) = wtt[SplitTab[ind].TV[i][j]];
485 
486  assert((*nf[i]).V(j)!=0);
487  if(SplitTab[ind].TE[i][j]!=3)
488  {
489  if(orgflag & (MESH_TYPE::FaceType::BORDER0<<(SplitTab[ind].TE[i][j])))
490  (*nf[i]).SetB(j);
491  else
492  (*nf[i]).ClearB(j);
493 
494  if(orgflag & (MESH_TYPE::FaceType::FACEEDGESEL0<<(SplitTab[ind].TE[i][j])))
495  (*nf[i]).SetFaceEdgeS(j);
496  else
497  (*nf[i]).ClearFaceEdgeS(j);
498  }
499  else
500  {
501  (*nf[i]).ClearB(j);
502  (*nf[i]).ClearFaceEdgeS(j);
503  }
504  }
505 
506  if(SplitTab[ind].TriNum==3 &&
507  SquaredDistance(vv[SplitTab[ind].swap[0][0]]->P(),vv[SplitTab[ind].swap[0][1]]->P()) <
508  SquaredDistance(vv[SplitTab[ind].swap[1][0]]->P(),vv[SplitTab[ind].swap[1][1]]->P()) )
509  { // swap the last two triangles
510  (*nf[2]).V(1)=(*nf[1]).V(0);
511  (*nf[1]).V(1)=(*nf[2]).V(0);
512  if(tri::HasPerWedgeTexCoord(m)){ //swap also textures coordinates
513  (*nf[2]).WT(1)=(*nf[1]).WT(0);
514  (*nf[1]).WT(1)=(*nf[2]).WT(0);
515  }
516 
517  if((*nf[1]).IsB(0)) (*nf[2]).SetB(1); else (*nf[2]).ClearB(1);
518  if((*nf[2]).IsB(0)) (*nf[1]).SetB(1); else (*nf[1]).ClearB(1);
519  (*nf[1]).ClearB(0);
520  (*nf[2]).ClearB(0);
521 
522  if((*nf[1]).IsFaceEdgeS(0)) (*nf[2]).SetFaceEdgeS(1); else (*nf[2]).ClearFaceEdgeS(1);
523  if((*nf[2]).IsFaceEdgeS(0)) (*nf[1]).SetFaceEdgeS(1); else (*nf[1]).ClearFaceEdgeS(1);
524  (*nf[1]).ClearFaceEdgeS(0);
525  (*nf[2]).ClearFaceEdgeS(0);
526  }
527  }
528 
529  assert(lastf==m.face.end()); // critical assert: we MUST have used all the faces that we forecasted we need and that we previously allocated.
530  assert(!m.vert.empty());
531  for(fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD()){
532  assert((*fi).V(0)>=&*m.vert.begin() && (*fi).V(0)<=&m.vert.back() );
533  assert((*fi).V(1)>=&*m.vert.begin() && (*fi).V(1)<=&m.vert.back() );
534  assert((*fi).V(2)>=&*m.vert.begin() && (*fi).V(2)<=&m.vert.back() );
535  }
536  tri::UpdateTopology<MESH_TYPE>::FaceFace(m);
537 
538  tri::Allocator<MESH_TYPE> :: template DeletePerFaceAttribute<RefinedFaceData<VertexPointer> > (m,RD);
539 
540  return true;
541 }
542 
543 /*************************************************************************/
544 // simple wrapper of the base refine for lazy coder that do not need a edge predicate
545 
546 template<class MESH_TYPE,class MIDPOINT>
547 bool Refine(MESH_TYPE &m, MIDPOINT mid, typename MESH_TYPE::ScalarType thr=0,bool RefineSelected=false, CallBackPos *cb = 0)
548 {
549  EdgeLen <MESH_TYPE, typename MESH_TYPE::ScalarType> ep(thr);
550  return RefineE(m,mid,ep,RefineSelected,cb);
551 }
552 /*************************************************************************/
553 
554 /*
555 Modified Butterfly interpolation scheme,
556 as presented in
557 Zorin, Schroeder
558 Subdivision for modeling and animation
559 Siggraph 2000 Course Notes
560 */
561 
562 /*
563 
564  vul-------vu--------vur
565  \ / \ /
566  \ / \ /
567  \ / fu \ /
568  vl--------vr
569  / \ fd / \
570  / \ / \
571  / \ / \
572  vdl-------vd--------vdr
573 
574 */
575 
576 template<class MESH_TYPE>
577 struct MidPointButterfly
578 {
579  MESH_TYPE &m;
580  MidPointButterfly(MESH_TYPE &_m):m(_m){}
581 
582  void operator()(typename MESH_TYPE::VertexType &nv, face::Pos<typename MESH_TYPE::FaceType> ep)
583  {
584  face::Pos<typename MESH_TYPE::FaceType> he(ep.f,ep.z,ep.f->V(ep.z));
585  typename MESH_TYPE::CoordType *vl,*vr;
586  typename MESH_TYPE::CoordType *vl0,*vr0;
587  typename MESH_TYPE::CoordType *vu,*vd,*vul,*vur,*vdl,*vdr;
588  vl=&he.v->P();
589  he.FlipV();
590  vr=&he.v->P();
591 
592  if( tri::HasPerVertexColor(m))
593  nv.C().lerp(ep.f->V(ep.z)->C(),ep.f->V1(ep.z)->C(),.5f);
594 
595  if(he.IsBorder())
596  {
597  he.NextB();
598  vr0=&he.v->P();
599  he.FlipV();
600  he.NextB();
601  assert(&he.v->P()==vl);
602  he.NextB();
603  vl0=&he.v->P();
604  nv.P()=((*vl)+(*vr))*(9.0/16.0)-((*vl0)+(*vr0))/16.0 ;
605  }
606  else
607  {
608  he.FlipE();he.FlipV();
609  vu=&he.v->P();
610  he.FlipF();he.FlipE();he.FlipV();
611  vur=&he.v->P();
612  he.FlipV();he.FlipE();he.FlipF(); assert(&he.v->P()==vu); // back to vu (on the right)
613  he.FlipE();
614  he.FlipF();he.FlipE();he.FlipV();
615  vul=&he.v->P();
616  he.FlipV();he.FlipE();he.FlipF(); assert(&he.v->P()==vu); // back to vu (on the left)
617  he.FlipV();he.FlipE();he.FlipF(); assert(&he.v->P()==vl);// again on vl (but under the edge)
618  he.FlipE();he.FlipV();
619  vd=&he.v->P();
620  he.FlipF();he.FlipE();he.FlipV();
621  vdl=&he.v->P();
622  he.FlipV();he.FlipE();he.FlipF(); assert(&he.v->P()==vd);// back to vd (on the right)
623  he.FlipE();
624  he.FlipF();he.FlipE();he.FlipV();
625  vdr=&he.v->P();
626 
627  nv.P()=((*vl)+(*vr))/2.0+((*vu)+(*vd))/8.0 - ((*vul)+(*vur)+(*vdl)+(*vdr))/16.0;
628  }
629  }
630 
632  Color4<typename MESH_TYPE::ScalarType> WedgeInterp(Color4<typename MESH_TYPE::ScalarType> &c0, Color4<typename MESH_TYPE::ScalarType> &c1)
633  {
634  Color4<typename MESH_TYPE::ScalarType> cc;
635  return cc.lerp(c0,c1,0.5f);
636  }
637 
638  template<class FL_TYPE>
639  TexCoord2<FL_TYPE,1> WedgeInterp(TexCoord2<FL_TYPE,1> &t0, TexCoord2<FL_TYPE,1> &t1)
640  {
641  TexCoord2<FL_TYPE,1> tmp;
642  assert(t0.n()== t1.n());
643  tmp.n()=t0.n();
644  tmp.t()=(t0.t()+t1.t())/2.0;
645  return tmp;
646  }
647 };
648 
649 
650 #if 0
651  int rule=0;
652  if(vr==vul) rule+=1;
653  if(vl==vur) rule+=2;
654  if(vl==vdr) rule+=4;
655  if(vr==vdl) rule+=8;
656  switch(rule){
657 /* */
658 /* */ case 0 : return ((*vl)+(*vr))/2.0+((*vu)+(*vd))/8.0 - ((*vul)+(*vur)+(*vdl)+(*vdr))/16.0;
659 /* ul */ case 1 : return (*vl*6 + *vr*10 + *vu + *vd*3 - *vur - *vdl -*vdr*2 )/16.0;
660 /* ur */ case 2 : return (*vr*6 + *vl*10 + *vu + *vd*3 - *vul - *vdr -*vdl*2 )/16.0;
661 /* dr */ case 4 : return (*vr*6 + *vl*10 + *vd + *vu*3 - *vdl - *vur -*vul*2 )/16.0;
662 /* dl */ case 8 : return (*vl*6 + *vr*10 + *vd + *vu*3 - *vdr - *vul -*vur*2 )/16.0;
663 /* ul,ur */ case 3 : return (*vl*4 + *vr*4 + *vd*2 + - *vdr - *vdl )/8.0;
664 /* dl,dr */ case 12 : return (*vl*4 + *vr*4 + *vu*2 + - *vur - *vul )/8.0;
665 
666 /* ul,dr */ case 5 :
667 /* ur,dl */ case 10 :
668  default:
669  return (*vl+ *vr)/2.0;
670  }
671 
672 
673 
674 #endif
675 /*
676  vul-------vu--------vur
677  \ / \ /
678  \ / \ /
679  \ / fu \ /
680  vl--------vr
681  / \ fd / \
682  / \ / \
683  / \ / \
684  vdl-------vd--------vdr
685 
686 */
687 
688 // Versione modificata per tenere di conto in meniara corretta dei vertici con valenza alta
689 
690 template<class MESH_TYPE>
691 struct MidPointButterfly2
692 {
693  typename MESH_TYPE::CoordType operator()(face::Pos<typename MESH_TYPE::FaceType> ep)
694  {
695 double Rules[11][10] =
696 {
697  {.0}, // valenza 0
698  {.0}, // valenza 1
699  {.0}, // valenza 2
700  { .4166666667, -.08333333333 , -.08333333333 }, // valenza 3
701  { .375 , .0 , -0.125 , .0 }, // valenza 4
702  { .35 , .03090169945 , -.08090169945 , -.08090169945, .03090169945 }, // valenza 5
703  { .5 , .125 , -0.0625 , .0 , -0.0625 , 0.125 }, // valenza 6
704  { .25 , .1088899050 , -.06042933822 , -.04846056675, -.04846056675, -.06042933822, .1088899050 }, // valenza 7
705  { .21875 , .1196383476 , -.03125 , -.05713834763, -.03125 , -.05713834763, -.03125 ,.1196383476 }, // valenza 8
706  { .1944444444, .1225409480 , -.00513312590 , -.05555555556, -.03407448880, -.03407448880, -.05555555556, -.00513312590, .1225409480 }, // valenza 9
707  { .175 , .1213525492 , .01545084973 , -.04635254918, -.04045084973, -.025 , -.04045084973, -.04635254918, .01545084973, .1213525492 } // valenza 10
708 };
709 
710 face::Pos<typename MESH_TYPE::FaceType> he(ep.f,ep.z,ep.f->V(ep.z));
711  typename MESH_TYPE::CoordType *vl,*vr;
712  vl=&he.v->P();
713  vr=&he.VFlip()->P();
714  if(he.IsBorder())
715  {he.FlipV();
716  typename MESH_TYPE::CoordType *vl0,*vr0;
717  he.NextB();
718  vr0=&he.v->P();
719  he.FlipV();
720  he.NextB();
721  assert(&he.v->P()==vl);
722  he.NextB();
723  vl0=&he.v->P();
724  return ((*vl)+(*vr))*(9.0/16.0)-((*vl0)+(*vr0))/16.0 ;
725  }
726 
727  int kl=0,kr=0; // valence of left and right vertices
728  bool bl=false,br=false; // if left and right vertices are of border
729  face::Pos<typename MESH_TYPE::FaceType> heStart=he;assert(he.v->P()==*vl);
730  do { // compute valence of left vertex
731  he.FlipE();he.FlipF();
732  if(he.IsBorder()) bl=true;
733  ++kl;
734  } while(he!=heStart);
735 
736  he.FlipV();heStart=he;assert(he.v->P()==*vr);
737  do { // compute valence of right vertex
738  he.FlipE();he.FlipF();
739  if(he.IsBorder()) br=true;
740  ++kr;
741  } while(he!=heStart);
742  if(br||bl) return MidPointButterfly<MESH_TYPE>()( ep );
743  if(kr==6 && kl==6) return MidPointButterfly<MESH_TYPE>()( ep );
744  // TRACE("odd vertex among valences of %i %i\n",kl,kr);
745  typename MESH_TYPE::CoordType newposl=*vl*.75, newposr=*vr*.75;
746  he.FlipV();heStart=he; assert(he.v->P()==*vl);
747  int i=0;
748  if(kl!=6)
749  do { // compute position of left vertex
750  newposl+= he.VFlip()->P() * Rules[kl][i];
751  he.FlipE();he.FlipF();
752  ++i;
753  } while(he!=heStart);
754  i=0;he.FlipV();heStart=he;assert(he.v->P()==*vr);
755  if(kr!=6)
756  do { // compute position of right vertex
757  newposr+=he.VFlip()->P()* Rules[kr][i];
758  he.FlipE();he.FlipF();
759  ++i;
760  } while(he!=heStart);
761  if(kr==6) return newposl;
762  if(kl==6) return newposr;
763  return newposl+newposr;
764  }
765 };
766 
767 /* The two following classes are the functor and the predicate that you need for using the refine framework to cut a mesh along a linear interpolation of the quality.
768  This can be used for example to slice a mesh with a plane. Just set the quality value as distance from plane and then functor and predicate
769  initialized 0 and invoke the refine
770 
771  MyMesh A;
772  tri::UpdateQuality:MyMesh>::VertexFromPlane(plane);
773  QualityMidPointFunctor<MyMesh> slicingfunc(0.0);
774  QualityEdgePredicate<MyMesh> slicingpred(0.0);
775  tri::UpdateTopology<MyMesh>::FaceFace(A);
776  RefineE<MyMesh, QualityMidPointFunctor<MyMesh>, QualityEdgePredicate<MyMesh> > (A, slicingfunc, slicingpred, false);
777 
778  Note that they store in the vertex quality the plane distance.
779  */
780 
781 template<class MESH_TYPE>
782 class QualityMidPointFunctor
783 {
784 public:
785  typedef Point3<typename MESH_TYPE::ScalarType> Point3x;
786  typedef typename MESH_TYPE::ScalarType ScalarType;
787 
788  ScalarType thr;
789 
790  QualityMidPointFunctor(ScalarType _thr):thr(_thr){}
791 
792 
793  void operator()(typename MESH_TYPE::VertexType &nv, const face::Pos<typename MESH_TYPE::FaceType> &ep){
794  Point3x p0=ep.f->V0(ep.z)->P();
795  Point3x p1=ep.f->V1(ep.z)->P();
796  ScalarType q0=ep.f->V0(ep.z)->Q()-thr;
797  ScalarType q1=ep.f->V1(ep.z)->Q()-thr;
798  double pp= q0/(q0-q1);
799  nv.P()=p1*pp + p0*(1.0-pp);
800  nv.Q()=thr;
801  }
802 
803  Color4<typename MESH_TYPE::ScalarType> WedgeInterp(Color4<typename MESH_TYPE::ScalarType> &c0, Color4<typename MESH_TYPE::ScalarType> &c1)
804  {
805  Color4<typename MESH_TYPE::ScalarType> cc;
806  return cc.lerp(c0,c1,0.5f);
807  }
808 
809  template<class FL_TYPE>
810  TexCoord2<FL_TYPE,1> WedgeInterp(TexCoord2<FL_TYPE,1> &t0, TexCoord2<FL_TYPE,1> &t1)
811  {
812  TexCoord2<FL_TYPE,1> tmp;
813  assert(t0.n()== t1.n());
814  tmp.n()=t0.n();
815  tmp.t()=(t0.t()+t1.t())/2.0;
816  return tmp;
817  }
818 };
819 
820 
821 template <class MESH_TYPE>
822 class QualityEdgePredicate
823 {
824  public:
825  typedef Point3<typename MESH_TYPE::ScalarType> Point3x;
826  typedef typename MESH_TYPE::ScalarType ScalarType;
827  ScalarType thr;
828  ScalarType tolerance;
829  QualityEdgePredicate(const ScalarType &thr,ScalarType _tolerance=0.02):thr(thr) {tolerance=_tolerance;}
830  bool operator()(face::Pos<typename MESH_TYPE::FaceType> ep)
831  {
832  ScalarType q0=ep.f->V0(ep.z)->Q()-thr;
833  ScalarType q1=ep.f->V1(ep.z)->Q()-thr;
834  if(q0>q1) std::swap(q0,q1);
835  if ( q0*q1 >= 0) return false;
836  // now a small check to be sure that we do not make too thin crossing.
837  double pp= q0/(q0-q1);
838  if ((fabs(pp)< tolerance)||(fabs(pp)> (1-tolerance))) return false;
839  return true;
840  }
841 };
842 
843 
844 template<class MESH_TYPE>
845 struct MidPointSphere
846 {
847  Sphere3<typename MESH_TYPE::ScalarType> sph;
848  typedef Point3<typename MESH_TYPE::ScalarType> Point3x;
849 
850  void operator()(typename MESH_TYPE::VertexType &nv, face::Pos<typename MESH_TYPE::FaceType> ep){
851  Point3x &p0=ep.f->V0(ep.z)->P();
852  Point3x &p1=ep.f->V1(ep.z)->P();
853  nv.P()= sph.c+((p0+p1)/2.0 - sph.c ).Normalize();
854  }
855 
856  Color4<typename MESH_TYPE::ScalarType> WedgeInterp(Color4<typename MESH_TYPE::ScalarType> &c0, Color4<typename MESH_TYPE::ScalarType> &c1)
857  {
858  Color4<typename MESH_TYPE::ScalarType> cc;
859  return cc.lerp(c0,c1,0.5f);
860  }
861 
862  template<class FL_TYPE>
863  TexCoord2<FL_TYPE,1> WedgeInterp(TexCoord2<FL_TYPE,1> &t0, TexCoord2<FL_TYPE,1> &t1)
864  {
865  TexCoord2<FL_TYPE,1> tmp;
866  assert(t0.n()== t1.n());
867  tmp.n()=t0.n();
868  tmp.t()=(t0.t()+t1.t())/2.0;
869  return tmp;
870  }
871 };
872 
873 
874 template <class FLT>
875 class EdgeSplSphere
876 {
877  public:
878  Sphere3<FLT> sph;
879  bool operator()(const Point3<FLT> &p0, const Point3<FLT> &p1) const
880  {
881  if(Distance(sph,p0)>0) {
882  if(Distance(sph,p1)>0) return false;
883  else return true;
884  }
885  else if(Distance(sph,p1)<=0) return false;
886  return true;
887  }
888 };
889 
890 template<class TRIMESH_TYPE>
891 struct CenterPointBarycenter
892 {
893  typename TRIMESH_TYPE::CoordType operator()(typename TRIMESH_TYPE::FacePointer f){
894  return vcg::Barycenter<typename TRIMESH_TYPE::FaceType>(*f);
895  }
896 };
897 
901 
902 template<class TRIMESH_TYPE, class CenterPoint=CenterPointBarycenter <TRIMESH_TYPE> >
903 class TriSplit
904 {
905 public:
906  typedef typename TRIMESH_TYPE::FaceType FaceType;
907  typedef typename TRIMESH_TYPE::VertexType VertexType;
908 
909  static void Apply(FaceType *f,
910  FaceType * f1,FaceType * f2,
911  VertexType * vB, CenterPoint Center)
912  {
913  vB->P() = Center(f);
914 
915  //three vertices of the face to be split
916  VertexType *V0,*V1,*V2;
917  V0 = f->V(0);
918  V1 = f->V(1);
919  V2 = f->V(2);
920 
921  //reupdate initial face
922  (*f).V(2) = &(*vB);
923  //new face #1
924  (*f1).V(0) = &(*vB);
925  (*f1).V(1) = V1;
926  (*f1).V(2) = V2;
927  //new face #2
928  (*f2).V(0) = V0;
929  (*f2).V(1) = &(*vB);
930  (*f2).V(2) = V2;
931 
932  if(f->HasFFAdjacency())
933  {
934  //update adjacency
935  f->FFp(1)->FFp(f->FFi(1)) = f1;
936  f->FFp(2)->FFp(f->FFi(2)) = f2;
937 
938  // ff adjacency
939  FaceType * FF0,*FF1,*FF2;
940  FF0 = f->FFp(0);
941  FF1 = f->FFp(1);
942  FF2 = f->FFp(2);
943 
944  //ff adjacency indexes
945  char FFi0,FFi1,FFi2;
946  FFi0 = f->FFi(0);
947  FFi1 = f->FFi(1);
948  FFi2 = f->FFi(2);
949  (void)FFi0;
950 
951  //initial face
952  (*f).FFp(1) = &(*f1);
953  (*f).FFi(1) = 0;
954  (*f).FFp(2) = &(*f2);
955  (*f).FFi(2) = 0;
956 
957  //face #1
958  (*f1).FFp(0) = f;
959  (*f1).FFi(0) = 1;
960 
961  (*f1).FFp(1) = FF1;
962  (*f1).FFi(1) = FFi1;
963 
964  (*f1).FFp(2) = &(*f2);
965  (*f1).FFi(2) = 1;
966 
967  //face #2
968  (*f2).FFp(0) = f;
969  (*f2).FFi(0) = 2;
970 
971  (*f2).FFp(1) = &(*f1);
972  (*f2).FFi(1) = 2;
973 
974  (*f2).FFp(2) = FF2;
975  (*f2).FFi(2) = FFi2;
976  }
977  //update faceEdge Sel if needed
978  if (f->HasFlags())
979  {
980  bool IsFaceEdgeS[3];
981  //collect and clear
982  for (size_t i=0;i<3;i++)
983  {
984  IsFaceEdgeS[i]=(*f).IsFaceEdgeS(i);
985  (*f).ClearFaceEdgeS(i);
986  (*f1).ClearFaceEdgeS(i);
987  (*f2).ClearFaceEdgeS(i);
988  }
989  //set back
990  if (IsFaceEdgeS[0])(*f).SetFaceEdgeS(0);
991  if (IsFaceEdgeS[1])(*f1).SetFaceEdgeS(1);
992  if (IsFaceEdgeS[2])(*f2).SetFaceEdgeS(2);
993  }
994  }
995 }; // end class TriSplit
996 
997 template <class MeshType>
998 void TrivialMidPointRefine(MeshType & m)
999 {
1000  typedef typename MeshType::VertexIterator VertexIterator;
1001  typedef typename MeshType::FaceIterator FaceIterator;
1002  typedef typename MeshType::VertexPointer VertexPointer;
1003  typedef typename MeshType::FacePointer FacePointer;
1004 
1005  Allocator<MeshType>::CompactEveryVector(m);
1006  int startFn = m.fn;
1007  FaceIterator lastf = tri::Allocator<MeshType>::AddFaces(m,m.fn*3);
1008  VertexIterator lastv = tri::Allocator<MeshType>::AddVertices(m,m.fn*3);
1009 
1010  /*
1011  * v0
1012  * / \
1013  * / f0 \
1014  * / \
1015  * mp01----------mp02
1016  * / \ f3 / \
1017  * / f1 \ / f2 \
1018  * / \ / \
1019  *v1 ---------- mp12------------v2
1020  *
1021  */
1022 
1023  for(int i=0;i<startFn;++i)
1024  {
1025  FacePointer f0= &m.face[i];
1026  FacePointer f1= &*lastf; ++lastf;
1027  f1->ImportData(*f0);
1028  FacePointer f2= &*lastf; ++lastf;
1029  f2->ImportData(*f0);
1030  FacePointer f3= &*lastf; ++lastf;
1031  f3->ImportData(*f0);
1032  VertexPointer v0 =m.face[i].V(0);
1033  VertexPointer v1 =m.face[i].V(1);
1034  VertexPointer v2 =m.face[i].V(2);
1035  VertexPointer mp01 = &*lastv; ++lastv;
1036  VertexPointer mp12 = &*lastv; ++lastv;
1037  VertexPointer mp02 = &*lastv; ++lastv;
1038 
1039  f0->V(0) = v0; f0->V(1) = mp01; f0->V(2) = mp02;
1040  f1->V(0) = v1; f1->V(1) = mp12; f1->V(2) = mp01;
1041  f2->V(0) = v2; f2->V(1) = mp02; f2->V(2) = mp12;
1042  f3->V(0) = mp12; f3->V(1) = mp02; f3->V(2) = mp01;
1043  mp01->P() = (v0>v1) ? (v0->P()+v1->P())/2.0 : (v1->P()+v0->P())/2.0;
1044  mp12->P() = (v1>v2) ? (v1->P()+v2->P())/2.0 : (v2->P()+v1->P())/2.0;
1045  mp02->P() = (v0>v2) ? (v0->P()+v2->P())/2.0 : (v2->P()+v0->P())/2.0;
1046  }
1047 
1048  int vd = tri::Clean<MeshType>::RemoveDuplicateVertex(m);
1049  printf("Vertex unification %i\n",vd);
1050  int vu = tri::Clean<MeshType>::RemoveUnreferencedVertex(m);
1051  printf("Vertex unref %i\n",vu);
1052  Allocator<MeshType>::CompactEveryVector(m);
1053 }
1054 
1055 
1056 template<class MESH_TYPE, class EDGEPRED>
1057 bool RefineMidpoint(MESH_TYPE &m, EDGEPRED &ep, bool RefineSelected=false, CallBackPos *cb = 0)
1058 {
1059  // common typenames
1060  typedef typename MESH_TYPE::VertexIterator VertexIterator;
1061  typedef typename MESH_TYPE::FaceIterator FaceIterator;
1062  typedef typename MESH_TYPE::VertexPointer VertexPointer;
1063  typedef typename MESH_TYPE::FacePointer FacePointer;
1064  typedef typename MESH_TYPE::FaceType FaceType;
1065  typedef typename MESH_TYPE::FaceType::TexCoordType TexCoordType;
1066 
1067  assert(tri::HasFFAdjacency(m));
1068  tri::UpdateFlags<MESH_TYPE>::FaceBorderFromFF(m);
1069  typedef face::Pos<FaceType> PosType;
1070 
1071  int j,NewVertNum=0,NewFaceNum=0;
1072 
1073  typedef RefinedFaceData<VertexPointer> RFD;
1074  typedef typename MESH_TYPE :: template PerFaceAttributeHandle<RFD> HandleType;
1075  HandleType RD = tri::Allocator<MESH_TYPE>:: template AddPerFaceAttribute<RFD> (m,std::string("RefineData"));
1076 
1077  MidPoint<MESH_TYPE> mid(&m);
1078  // Callback stuff
1079  int step=0;
1080  int PercStep=std::max(1,m.fn/33);
1081 
1082  // First Loop: We analyze the mesh to compute the number of the new faces and new vertices
1083  FaceIterator fi;
1084  for(fi=m.face.begin(),j=0;fi!=m.face.end();++fi) if(!(*fi).IsD())
1085  {
1086  if(cb && (++step%PercStep)==0) (*cb)(step/PercStep,"Refining...");
1087  // skip unselected faces if necessary
1088  if(RefineSelected && !(*fi).IsS()) continue;
1089 
1090  for(j=0;j<3;j++)
1091  {
1092  if(RD[fi].ep[j]) continue;
1093 
1094  PosType edgeCur(&*fi,j);
1095  if(RefineSelected && ! edgeCur.FFlip()->IsS()) continue;
1096  if(!ep(edgeCur)) continue;
1097 
1098  RD[edgeCur.F()].ep[edgeCur.E()]=true;
1099  ++NewFaceNum;
1100  ++NewVertNum;
1101  PosType start = edgeCur;
1102  if (!edgeCur.IsBorder())
1103  {
1104  do
1105  {
1106  edgeCur.NextF();
1107  edgeCur.F()->SetV();
1108  RD[edgeCur.F()].ep[edgeCur.E()] = true;
1109  ++NewFaceNum;
1110  } while (edgeCur != start);
1111  --NewFaceNum; //start is counted twice (could remove the first increment above)
1112  }
1113  }
1114 
1115  } // end face loop
1116 
1117  if(NewVertNum ==0 )
1118  {
1119  tri::Allocator<MESH_TYPE> :: template DeletePerFaceAttribute<RefinedFaceData<VertexPointer> > (m,RD);
1120  return false;
1121  }
1122  VertexIterator lastv = tri::Allocator<MESH_TYPE>::AddVertices(m,NewVertNum);
1123 
1124  // Secondo loop: We initialize a edge->vertex map
1125 
1126  for(fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
1127  {
1128  if(cb && (++step%PercStep)==0)(*cb)(step/PercStep,"Refining...");
1129  for(j=0;j<3;j++)
1130  {
1131  // skip unselected faces if necessary
1132  if(RefineSelected && !(*fi).IsS()) continue;
1133  for(j=0;j<3;j++)
1134  {
1135  PosType edgeCur(&*fi,j);
1136  if(RefineSelected && ! edgeCur.FFlip()->IsS()) continue;
1137 
1138  if( RD[edgeCur.F()].ep[edgeCur.E()] && RD[edgeCur.F()].vp[edgeCur.E()] ==0 )
1139  {
1140  RD[edgeCur.F()].vp[edgeCur.E()] = &*lastv;
1141  mid(*lastv,edgeCur);
1142  PosType start = edgeCur;
1143  if (!edgeCur.IsBorder())
1144  {
1145  do
1146  {
1147  edgeCur.NextF();
1148  assert(RD[edgeCur.F()].ep[edgeCur.E()]);
1149  RD[edgeCur.F()].vp[edgeCur.E()] = &*lastv;
1150  } while (edgeCur != start);
1151  }
1152  ++lastv;
1153  }
1154  }
1155  }
1156  }
1157 
1158  assert(lastv==m.vert.end()); // critical assert: we MUST have used all the vertex that we forecasted we need
1159 
1160  FaceIterator lastf = tri::Allocator<MESH_TYPE>::AddFaces(m,NewFaceNum);
1161  FaceIterator oldendf = lastf;
1162 
1163 /*
1164  * v0
1165  *
1166  *
1167  * f0
1168  *
1169  * mp01 f3 mp02
1170  *
1171  *
1172  * f1 f2
1173  *
1174  *v1 mp12 v2
1175  *
1176 */
1177 
1178  VertexPointer vv[6]; // The six vertices that arise in the single triangle splitting
1179  // 0..2 Original triangle vertices
1180  // 3..5 mp01, mp12, mp20 midpoints of the three edges
1181  FacePointer nf[4]; // The (up to) four faces that are created.
1182 
1183  TexCoordType wtt[6]; // per ogni faccia sono al piu' tre i nuovi valori
1184  // di texture per wedge (uno per ogni edge)
1185 
1186  for(fi=m.face.begin();fi!=oldendf;++fi) if(!(*fi).IsD())
1187  {
1188  if(cb && (++step%PercStep)==0)
1189  (*cb)(step/PercStep,"Refining...");
1190  vv[0]=(*fi).V(0);
1191  vv[1]=(*fi).V(1);
1192  vv[2]=(*fi).V(2);
1193  vv[3] = RD[fi].vp[0];
1194  vv[4] = RD[fi].vp[1];
1195  vv[5] = RD[fi].vp[2];
1196 
1197  int ind = ((vv[3] != NULL) ? 1 : 0) + ((vv[4] != NULL) ? 2 : 0) + ((vv[5] != NULL) ? 4 : 0);
1198 
1199  nf[0]=&*fi;
1200  int i;
1201  for(i=1;i<SplitTab[ind].TriNum;++i){
1202  nf[i]=&*lastf; ++lastf;
1203  if(RefineSelected || (*fi).IsS()) (*nf[i]).SetS();
1204  nf[i]->ImportData(*fi);
1205 
1206  }
1207 
1208 
1209  if(tri::HasPerWedgeTexCoord(m))
1210  for(i=0;i<3;++i)
1211  {
1212  wtt[i]=(*fi).WT(i);
1213  wtt[3+i]=mid.WedgeInterp((*fi).WT(i),(*fi).WT((i+1)%3));
1214  }
1215 
1216  int orgflag = (*fi).Flags();
1217  for (i=0; i<SplitTab[ind].TriNum; ++i)
1218  for(j=0;j<3;++j)
1219  {
1220  (*nf[i]).V(j)=&*vv[SplitTab[ind].TV[i][j]];
1221 
1222  if(tri::HasPerWedgeTexCoord(m)) //analogo ai vertici...
1223  (*nf[i]).WT(j) = wtt[SplitTab[ind].TV[i][j]];
1224 
1225  assert((*nf[i]).V(j)!=0);
1226  if(SplitTab[ind].TE[i][j]!=3)
1227  {
1228  if(orgflag & (MESH_TYPE::FaceType::BORDER0<<(SplitTab[ind].TE[i][j])))
1229  (*nf[i]).SetB(j);
1230  else
1231  (*nf[i]).ClearB(j);
1232 
1233  if(orgflag & (MESH_TYPE::FaceType::FACEEDGESEL0<<(SplitTab[ind].TE[i][j])))
1234  (*nf[i]).SetFaceEdgeS(j);
1235  else
1236  (*nf[i]).ClearFaceEdgeS(j);
1237  }
1238  else
1239  {
1240  (*nf[i]).ClearB(j);
1241  (*nf[i]).ClearFaceEdgeS(j);
1242  }
1243  }
1244 
1245  if(SplitTab[ind].TriNum==3 &&
1246  SquaredDistance(vv[SplitTab[ind].swap[0][0]]->P(),vv[SplitTab[ind].swap[0][1]]->P()) <
1247  SquaredDistance(vv[SplitTab[ind].swap[1][0]]->P(),vv[SplitTab[ind].swap[1][1]]->P()) )
1248  { // swap the last two triangles
1249  (*nf[2]).V(1)=(*nf[1]).V(0);
1250  (*nf[1]).V(1)=(*nf[2]).V(0);
1251  if(tri::HasPerWedgeTexCoord(m)){ //swap also textures coordinates
1252  (*nf[2]).WT(1)=(*nf[1]).WT(0);
1253  (*nf[1]).WT(1)=(*nf[2]).WT(0);
1254  }
1255 
1256  if((*nf[1]).IsB(0)) (*nf[2]).SetB(1); else (*nf[2]).ClearB(1);
1257  if((*nf[2]).IsB(0)) (*nf[1]).SetB(1); else (*nf[1]).ClearB(1);
1258  (*nf[1]).ClearB(0);
1259  (*nf[2]).ClearB(0);
1260 
1261  if((*nf[1]).IsFaceEdgeS(0)) (*nf[2]).SetFaceEdgeS(1); else (*nf[2]).ClearFaceEdgeS(1);
1262  if((*nf[2]).IsFaceEdgeS(0)) (*nf[1]).SetFaceEdgeS(1); else (*nf[1]).ClearFaceEdgeS(1);
1263  (*nf[1]).ClearFaceEdgeS(0);
1264  (*nf[2]).ClearFaceEdgeS(0);
1265  }
1266  }
1267 
1268  assert(lastf==m.face.end()); // critical assert: we MUST have used all the faces that we forecasted we need and that we previously allocated.
1269  assert(!m.vert.empty());
1270  for(fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD()){
1271  assert((*fi).V(0)>=&*m.vert.begin() && (*fi).V(0)<=&m.vert.back() );
1272  assert((*fi).V(1)>=&*m.vert.begin() && (*fi).V(1)<=&m.vert.back() );
1273  assert((*fi).V(2)>=&*m.vert.begin() && (*fi).V(2)<=&m.vert.back() );
1274  }
1275  tri::UpdateTopology<MESH_TYPE>::FaceFace(m);
1276 
1277  tri::Allocator<MESH_TYPE> :: template DeletePerFaceAttribute<RefinedFaceData<VertexPointer> > (m,RD);
1278 
1279  return true;
1280 }
1281 
1282 } // namespace tri
1283 } // namespace vcg
1284 
1285 #endif
vcg::Color4
Definition: color4.h:41
vcg::Point3
Definition: point3.h:43
vcg::tri::Allocator
Class to safely add and delete elements in a mesh.
Definition: allocate.h:97
vcg::tri::Allocator::AddVertices
static VertexIterator AddVertices(MeshType &m, size_t n, PointerUpdater< VertexPointer > &pu)
Add n vertices to the mesh. Function to add n vertices to the mesh. The elements are added always to ...
Definition: allocate.h:189
vcg::tri::Allocator::AddFaces
static FaceIterator AddFaces(MeshType &m, size_t n)
Function to add n faces to the mesh. First wrapper, with no parameters.
Definition: allocate.h:615
vcg::tri::Clean::RemoveDuplicateVertex
static int RemoveDuplicateVertex(MeshType &m, bool RemoveDegenerateFlag=true)
Definition: clean.h:206
vcg::tri::Clean::RemoveUnreferencedVertex
static int RemoveUnreferencedVertex(MeshType &m, bool DeleteVertexFlag=true)
Definition: clean.h:396
vcg::tri::EdgeLen
Definition: refine.h:287
vcg::tri::EdgeSplSphere
Definition: refine.h:876
vcg::tri::QualityEdgePredicate
Definition: refine.h:823
vcg::tri::QualityMidPointFunctor
Definition: refine.h:783
vcg::tri::RefinedFaceData
Definition: refine.h:316
vcg::tri::Split
Definition: refine.h:84
vcg::tri::TriSplit
Triangle split Simple templated function for splitting a triangle with a internal point....
Definition: refine.h:904
vcg::tri::UpdateFlags::FaceBorderFromFF
static void FaceBorderFromFF(MeshType &m)
Compute the border flags for the faces using the Face-Face Topology.
Definition: flag.h:170
vcg::tri::UpdateTopology::FaceFace
static void FaceFace(MeshType &m)
Update the Face-Face topological relation by allowing to retrieve for each face what other faces shar...
Definition: topology.h:395
vcg
Definition: namespaces.dox:6
vcg::tri::BaseInterpolator
Definition: refine.h:111
vcg::tri::CenterPointBarycenter
Definition: refine.h:892
vcg::tri::MidPointArcNaive
Definition: refine.h:255
vcg::tri::MidPointArc
Definition: refine.h:183
vcg::tri::MidPointButterfly2
Definition: refine.h:692
vcg::tri::MidPointButterfly
Definition: refine.h:578
vcg::tri::MidPointButterfly::WedgeInterp
Color4< typename MESH_TYPE::ScalarType > WedgeInterp(Color4< typename MESH_TYPE::ScalarType > &c0, Color4< typename MESH_TYPE::ScalarType > &c1)
Aggiunte in modo grezzo le due wedge interp.
Definition: refine.h:632
vcg::tri::MidPointSphere
Definition: refine.h:846
vcg::tri::MidPoint
Definition: refine.h:126
vcg::tri::MidPoint::operator()
void operator()(VertexType &nv, PosType ep)
This callback is called to fill up.
Definition: refine.h:139
Generated by doxygen 1.9.1 on Wed Mar 13 2024 13:53:31