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