1 /**************************************************************************** 2 * MeshLab o o * 3 * A versatile mesh processing toolbox o o * 4 * _ O _ * 5 * Copyright(C) 2008 \/)\/ * 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 25 #ifndef edit_topomeshbuilder_H 26 #define edit_topomeshbuilder_H 27 28 #include <common/interfaces.h> 29 30 #include <vcg/complex/intersection.h> 31 #include <vcg/complex/algorithms/clean.h> 32 #include <vcg/space/index/grid_static_ptr.h> 33 #include <vcg/complex/algorithms/closest.h> 34 35 #include <vcg/space/index/grid_static_ptr.h> 36 #include <vcg/space/index/aabb_binary_tree/aabb_binary_tree.h> 37 #include <vcg/space/index/octree.h> 38 #include <vcg/space/index/spatial_hashing.h> 39 40 #include <vcg/complex/algorithms/refine.h> 41 #include <vcg/complex/append.h> 42 #include <vcg/complex/algorithms/smooth.h> 43 44 #include "edit_topodialog.h" 45 46 47 48 49 //************************************************************** 50 // template class NearestMidPoint 51 // This class is used by the retopology algorithm 52 // to obtain the closest point to each "ideal" new 53 // mesh vertex 54 // 55 // The operator () is called by the standard vcg "Refine<,>" 56 // method to obtain the new vertices coordinates 57 // 58 // Because of the great reuse of that operator, this class 59 // needs to be initialized with the original "source" model. 60 // This can be done by calling the "init" method 61 // 62 template<class MESH_TYPE> 63 class NearestMidPoint : public std::unary_function<face::Pos<typename MESH_TYPE::FaceType>, typename MESH_TYPE::CoordType> 64 { 65 typedef GridStaticPtr<CMeshO::FaceType, CMeshO::ScalarType > MetroMeshGrid; 66 67 public: 68 // if DEBUG value is true, the class will fill 69 // the LoutMid QList with ALL the "failed" vertices. 70 // So, LoutMid will contain all vertices that have not 71 // been found by the UnifGrid.GetClosest() function 72 bool DEBUG; 73 QList<Point3f> * LoutMid; 74 75 // Uniform grid, init by the "init()" method 76 MetroMeshGrid unifGrid; 77 78 // Marker 79 typedef tri::FaceTmark<MESH_TYPE> MarkerFace; 80 MarkerFace markerFunctor; 81 82 // All of the data structures used by the retopology algo have 83 // to be initialized *before* the function call. 84 // 85 // This is necessary in order to reduce comput time init(MESH_TYPE * _m,float dist)86 void init(MESH_TYPE *_m, float dist) 87 { 88 m=_m; 89 if(m) 90 { 91 // Set up uniform grid 92 unifGrid.Set(m->face.begin(),m->face.end()); 93 markerFunctor.SetMesh(m); 94 dist_upper_bound = dist; 95 } 96 } 97 98 // Standard operator called by Refine<> 99 // 100 // If you want to change the way new vertices are generated 101 // you have to modify the "VertexTypr nv" output coords operator()102 void operator()(typename MESH_TYPE::VertexType &nv, face::Pos<typename MESH_TYPE::FaceType> ep) 103 { 104 Point3f closestPt, normf, bestq, ip; 105 106 float dist = dist_upper_bound; 107 vcg::face::PointDistanceBaseFunctor<float> PDistFunct; 108 109 // startPt is the point from where the "GetClosest" query will start 110 const typename MESH_TYPE::CoordType &startPt= (ep.f->V(ep.z)->P()+ep.f->V1(ep.z)->P())/2.0; 111 CMeshO::FaceType *nearestF=0; 112 113 // in "dist" will be returned the closest point distance from startPt 114 dist=dist_upper_bound; 115 116 Point3f p1 = ep.f->V(ep.z)->P(); 117 Point3f p2 = ep.f->V1(ep.z)->P(); 118 float incDist = sqrt(math::Sqr(p1.X()-p2.X())+math::Sqr(p1.Y()-p2.Y())+math::Sqr(p1.Z()-p2.Z())); 119 120 // distPerc is the % distance used to evaluate the maximum query distance 121 incDist = incDist * distPerc; 122 123 // dist_ upper_bound is the maximum query distance, evaluated 124 // with a % factor given by the user 125 dist_upper_bound = incDist; 126 127 // Query the uniform grid and get the original mesh's point nearest to startPt 128 nearestF = unifGrid.GetClosest(PDistFunct, 129 markerFunctor, 130 startPt, 131 dist_upper_bound, 132 dist, 133 closestPt); 134 135 // Output distance has not changed: no closest point found. 136 // The original "ideal" point will be used, and then will be 137 // smoothed with laplacian smooth algorithm 138 if(dist == dist_upper_bound) 139 { 140 nv.P()= startPt; 141 nv.N()= ((ep.f->V(ep.z)->N() + ep.f->V(ep.z)->N())/2).normalized(); 142 nv.C().lerp(ep.f->V(ep.z)->C(),ep.f->V1(ep.z)->C(),.5f); 143 nv.Q() = ((ep.f->V(ep.z)->Q()+ep.f->V1(ep.z)->Q())) / 2.0; 144 145 // Mark it as selected to smooth it 146 nv.SetS(); 147 148 qDebug("Unable to find closest point. Marked for smoothing"); 149 150 // If debug mode is on, the point will be drawn in meshlab 151 if(DEBUG) LoutMid->push_back(startPt); 152 } 153 // distance has changed: got the closest point 154 else 155 { 156 nv.P()= closestPt; 157 158 Point3f interp; 159 // Try to interpolate vertex colors and normals 160 if(InterpolationParameters<typename MESH_TYPE::FaceType,typename MESH_TYPE::ScalarType>(*nearestF,(*nearestF).cN(), closestPt, interp[0], interp[1], interp[2])) 161 { 162 interp[2]=1.0-interp[1]-interp[0]; 163 164 nv.P()= closestPt; 165 nv.N()= ((nearestF->V(0)->N() + nearestF->V(1)->N() + nearestF->V(2)->N())/3).normalized(); 166 nv.C().lerp(nearestF->V(0)->C(),nearestF->V(1)->C(),nearestF->V(2)->C(),interp); 167 nv.Q() = nearestF->V(0)->Q()*interp[0] + nearestF->V(1)->Q()*interp[1] + nearestF->V(2)->Q()*interp[2]; 168 169 nv.ClearS(); 170 } 171 } 172 } 173 174 // Color interpolation called by Refine<,> WedgeInterp(Color4<typename MESH_TYPE::ScalarType> & c0,Color4<typename MESH_TYPE::ScalarType> & c1)175 Color4<typename MESH_TYPE::ScalarType> WedgeInterp(Color4<typename MESH_TYPE::ScalarType> &c0, Color4<typename MESH_TYPE::ScalarType> &c1) 176 { 177 Color4<typename MESH_TYPE::ScalarType> cc; 178 return cc.lerp(c0,c1,0.5f); 179 } 180 181 // Color interpolation called by Refine<,> 182 template<class FL_TYPE> WedgeInterp(TexCoord2<FL_TYPE,1> & t0,TexCoord2<FL_TYPE,1> & t1)183 TexCoord2<FL_TYPE,1> WedgeInterp(TexCoord2<FL_TYPE,1> &t0, TexCoord2<FL_TYPE,1> &t1) 184 { 185 TexCoord2<FL_TYPE,1> tmp; 186 assert(t0.n()== t1.n()); 187 tmp.n()=t0.n(); 188 tmp.t()=(t0.t()+t1.t())/2.0; 189 return tmp; 190 } 191 192 float dist_upper_bound; // maximum upper distance (See below "distPerc") 193 float distPerc; // distance for getClosest() is evalutated as a % of the edge's length (float from 0.01 to 0.99) 194 195 private: 196 // Internal mesh model 197 CMeshO *m; 198 }; 199 200 201 202 203 204 205 206 207 208 209 210 //************************************************************** 211 // class RetopMeshBuilder 212 // This class contains the retopology algorithm, 213 // and is used for "edit" and "filter" plugin modes 214 // 215 class RetopMeshBuilder 216 { 217 public: 218 // Mid point sampler object, used by "Refine" in the retopo process 219 NearestMidPoint<CMeshO> * midSampler; 220 221 // This list will be filled (in debug mode) with all the "not found" closest vertices 222 QList<Point3f> Lout; 223 RetopMeshBuilder()224 RetopMeshBuilder() {}; 225 226 // init mid point sampler object init(MeshModel * _mm,double dist)227 void init(MeshModel *_mm, double dist) 228 { 229 _mm->updateDataMask(MeshModel::MM_FACEMARK); 230 midSampler = new NearestMidPoint<CMeshO>(); 231 midSampler->init(&_mm->cm, dist); 232 } 233 234 // 235 // Creates the retopology mesh in edit mode (edit_topo plugin) 236 // createRefinedMesh(MeshModel & outMesh,float dist,int iterations,QList<Fce> Fstack,QList<Vtx> stack,edit_topodialog * dialog,bool DEBUG)237 void createRefinedMesh(MeshModel &outMesh, /*MeshModel &in,*/ float dist, int iterations, QList<Fce> Fstack, QList<Vtx> stack, edit_topodialog *dialog, bool DEBUG) 238 { 239 dialog->setBarMax(iterations); 240 dialog->setStatusLabel("Init topo"); 241 242 midSampler->DEBUG = DEBUG; 243 midSampler->distPerc = dist; 244 midSampler->LoutMid = &Lout; 245 246 // Create a "flat" mesh from the user defined topology defined 247 // in faces stack "Fstack" and vertices stack "stack" 248 createBasicMesh(outMesh, Fstack, stack); 249 250 dialog->setStatusLabel("Done"); 251 252 CMeshO::FaceIterator fi; 253 for(fi=outMesh.cm.face.begin(); fi!=outMesh.cm.face.end(); fi++) 254 {(*fi).ClearS(); for(int i=0; i<3; i++) (*fi).V(i)->ClearS(); } 255 256 outMesh.updateDataMask(MeshModel::MM_FACEFACETOPO | MeshModel::MM_FACEFLAGBORDER); 257 if(tri::Clean<CMeshO>::CountNonManifoldEdgeFF(outMesh.cm)==0) 258 for(int i=0; i<iterations; i++) 259 { 260 dialog->setStatusLabel("Iter: "+QString("%1").arg(i+1)); 261 262 // This is che core point of the retopology plugin: 263 // here "Refine" is called with "NearestMidPoint" and "midSampler" 264 // - midSampler uses an uniform grid to get the closest point 265 // for each given vertex, and "builds" the new mesh by adapting 266 // it over the existing "in" meshmodel 267 // If the midSampler fails (for example if a hole is found), each 268 // vertex is marked with SetS() and will be smoothed later 269 // 270 outMesh.updateDataMask(MeshModel::MM_FACEFACETOPO | MeshModel::MM_FACEFLAGBORDER); 271 Refine<CMeshO, NearestMidPoint<CMeshO> >(outMesh.cm, *midSampler, 0, false, 0); 272 outMesh.clearDataMask( MeshModel::MM_VERTFACETOPO); 273 dialog->setBarVal(i+1); 274 } 275 276 outMesh.setFileName("Retopology.ply"); 277 tri::UpdateBounding<CMeshO>::Box(outMesh.cm); 278 279 dialog->setStatusLabel("Normals"); 280 281 // Recalculate new model's face normals and select faces with selected vertices 282 for(fi=outMesh.cm.face.begin(); fi!=outMesh.cm.face.end(); fi++) 283 { 284 (*fi).N()=((fi->V(0)->N() + fi->V(1)->N() + fi->V(2)->N())/3); 285 (*fi).ClearS(); 286 287 for(int i=0; i<3; i++) 288 if((*fi).V(i)->IsS()) 289 (*fi).SetS(); 290 } 291 292 // Expand selected faces to obtain a more refined smooth 293 for(int i=0; i<(1+(int)(iterations/4)); i++) 294 for(fi=outMesh.cm.face.begin(); fi!=outMesh.cm.face.end(); fi++) 295 if((*fi).IsS()) 296 for(int i=0; i<3; i++) 297 (*fi).FFp(i)->SetS(); 298 299 dialog->setStatusLabel("Lapl smooth"); 300 301 // Laplacian smooth for selected faces 302 tri::UpdateSelection<CMeshO>::VertexFromFaceStrict(outMesh.cm); 303 tri::Smooth<CMeshO>::VertexCoordLaplacian(outMesh.cm,3,true,0); 304 dialog->setStatusLabel("Done"); 305 } 306 307 308 309 310 311 //********************************************************************************************// 312 // 313 // Creates a retop mesh for the "filter" mode (not used in edit_topo) 314 // - userMesh = The low level mesh selected by the user as new basic topology 315 // - inMesh = The original mesh from where the userMesh has been created 316 // - it = Number of iterations (from 0 to 10) 317 // - dist = % for incremental distance (from 0.01 to 0.99) 318 // - outMesh = The output retopology mesh 319 // 320 // 321 //********************************************************************************************// applyTopoMesh(MeshModel & userTopoMesh,MeshModel & inModel,int it,float dist,MeshModel & outMesh)322 bool applyTopoMesh(MeshModel &userTopoMesh, MeshModel &inModel, int it, float dist, MeshModel &outMesh) 323 { 324 // turn off debug mode 325 midSampler->DEBUG = false; 326 327 midSampler->distPerc = dist; 328 outMesh.updateDataMask(MeshModel::MM_FACEFACETOPO); 329 330 // Update topology for in mesh, to be sure that the model can be refined 331 bool oriented,orientable; 332 tri::Clean<CMeshO>::IsOrientedMesh(outMesh.cm, oriented,orientable); 333 vcg::tri::UpdateTopology<CMeshO>::FaceFace(outMesh.cm); 334 vcg::tri::UpdateTopology<CMeshO>::TestFaceFace(outMesh.cm); 335 vcg::tri::UpdateNormals<CMeshO>::PerVertexNormalizedPerFace(outMesh.cm); 336 outMesh.clearDataMask(MeshModel::MM_FACEFACETOPO); 337 338 // Clear faces and vertices selection 339 CMeshO::FaceIterator fi; 340 for(fi=outMesh.cm.face.begin(); fi!=outMesh.cm.face.end(); fi++) 341 {(*fi).ClearS(); for(int i=0; i<3; i++) (*fi).V(i)->ClearS(); } 342 343 outMesh.updateDataMask(MeshModel::MM_FACEFACETOPO | MeshModel::MM_FACEFLAGBORDER); 344 if(tri::Clean<CMeshO>::CountNonManifoldEdgeFF(outMesh.cm)==0) 345 { 346 for(int i=0; i<it; i++) 347 { 348 outMesh.updateDataMask(MeshModel::MM_FACEFACETOPO | MeshModel::MM_FACEFLAGBORDER); 349 350 // Call refine to build the retopologized mesh. Important note: "midSampler" needs to be initialized before 351 Refine<CMeshO,NearestMidPoint<CMeshO> >(outMesh.cm, *midSampler, 0, false, 0); 352 outMesh.clearDataMask( MeshModel::MM_VERTFACETOPO); 353 } 354 } 355 else return false; 356 357 outMesh.setFileName("Retopology.ply"); 358 tri::UpdateBounding<CMeshO>::Box(outMesh.cm); 359 360 // compute face normals, and select faces for not found vertices (to smooth them) 361 for(fi=outMesh.cm.face.begin(); fi!=outMesh.cm.face.end(); fi++) 362 { 363 (*fi).N()=((fi->V(0)->N() + fi->V(1)->N() + fi->V(2)->N())/3); 364 (*fi).ClearS(); 365 366 for(int i=0; i<3; i++) 367 if((*fi).V(i)->IsS()) 368 (*fi).SetS(); 369 } 370 371 for(int i=0; i<(1+(int)(it/4)); i++) 372 for(fi=outMesh.cm.face.begin(); fi!=outMesh.cm.face.end(); fi++) 373 if((*fi).IsS()) 374 for(int i=0; i<3; i++) 375 (*fi).FFp(i)->SetS(); 376 377 // Laplacian smooth for not-found vertices 378 tri::UpdateSelection<CMeshO>::VertexFromFaceStrict(outMesh.cm); 379 tri::Smooth<CMeshO>::VertexCoordLaplacian(outMesh.cm,3,true,0); 380 381 return true; 382 } 383 384 385 386 private: 387 // Creates the flat initial mesh from the user defined topology createBasicMesh(MeshModel & outMesh,QList<Fce> Fstack,QList<Vtx> Vstack)388 void createBasicMesh(MeshModel &outMesh, QList<Fce> Fstack, QList<Vtx> Vstack) 389 { 390 // Elaborate topology relations 391 QVector<Vtx> nStack(Vstack.count()); 392 QVector<Fce> nFstack(Fstack.count()); nFstack = Fstack.toVector(); 393 for(int i=0; i<Vstack.count(); i++) 394 { 395 Vtx v = Vstack.at(i); 396 397 for(int j=0; j<Fstack.count(); j++) 398 { 399 Fce f = nFstack[j]; 400 for(int n=0; n<3; n++) 401 for(int m=0; m<2; m++) 402 if(f.e[n].v[m].vName == v.vName) 403 f.e[n].v[m].vName = QString("%1").arg(i); 404 405 nFstack[j]=f; 406 } 407 v.vName = QString("%1").arg(i); 408 nStack[i]=v; 409 } 410 411 int allFce = 0; 412 for(int i=0; i<nFstack.count(); i++) 413 if(nFstack.at(i).selected) 414 allFce++; 415 416 // Allocate the new mesh 417 outMesh.cm.Clear(); 418 vcg::tri::Allocator<CMeshO>::AddVertices(outMesh.cm, nStack.count()); 419 vcg::tri::Allocator<CMeshO>::AddFaces(outMesh.cm, allFce); 420 421 QVector<CMeshO::VertexPointer> ivp(Vstack.count()); 422 423 int v =0; 424 CMeshO::VertexIterator vi; 425 for(vi=outMesh.cm.vert.begin(); vi!=outMesh.cm.vert.end(); vi++) 426 { 427 ivp[v] = &*vi; 428 (*vi).P() = Point3f(nStack[v].V.X(), nStack[v].V.Y(), nStack[v].V.Z()); 429 430 Point3f closestPt; 431 vcg::face::PointDistanceBaseFunctor<float> PDistFunct; 432 433 const CMeshO::CoordType &startPt = (*vi).P(); 434 CMeshO::FaceType *nearestF=0; 435 436 float d1,d2; d1 = d2 = 1000; 437 438 // Use the sampler to get original vertices normals 439 nearestF = midSampler->unifGrid.GetClosest(PDistFunct, 440 midSampler->markerFunctor, 441 startPt, 442 d1, 443 d2, 444 closestPt); 445 446 (*vi).C().lerp(nearestF->V(0)->C(),nearestF->V(1)->C(),.5f); 447 (*vi).N() = ((nearestF->V(0)->N() + nearestF->V(1)->N() + nearestF->V(2)->N())/3).normalized(); 448 449 ++v; 450 } 451 452 int f = 0; 453 CMeshO::FaceIterator fi; 454 for(fi=outMesh.cm.face.begin(); fi!=outMesh.cm.face.end(); fi++) 455 { 456 Fce fce = nFstack[f]; 457 458 if(fce.selected) 459 { 460 QList<Vtx> allV; 461 for(int i=0; i<3; i++) 462 for(int j=0; j<2; j++) 463 if(!allV.contains(fce.e[i].v[j])) 464 allV.push_back(fce.e[i].v[j]); 465 466 int ivpId0 = allV.at(0).vName.toInt(); 467 int ivpId1 = allV.at(1).vName.toInt(); 468 int ivpId2 = allV.at(2).vName.toInt(); 469 470 (*fi).V(0) = ivp.at(ivpId0); 471 (*fi).V(1) = ivp.at(ivpId1); 472 (*fi).V(2) = ivp.at(ivpId2); 473 f++; 474 } 475 } 476 outMesh.updateDataMask(MeshModel::MM_FACEFACETOPO); 477 478 // Re-orient new mesh 479 bool oriented,orientable; 480 tri::Clean<CMeshO>::IsOrientedMesh(outMesh.cm, oriented,orientable); 481 vcg::tri::UpdateTopology<CMeshO>::FaceFace(outMesh.cm); 482 vcg::tri::UpdateTopology<CMeshO>::TestFaceFace(outMesh.cm); 483 484 outMesh.clearDataMask(MeshModel::MM_FACEFACETOPO); 485 } 486 }; 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 #endif 514 515 516