1 /**************************************************************************** 2 * VCGLib o o * 3 * Visual and Computer Graphics Library o o * 4 * _ O _ * 5 * Copyright(C) 2004-2016 \/)\/ * 6 * Visual Computing Lab /\/| * 7 * ISTI - Italian National Research Council | * 8 * \ * 9 * All rights reserved. * 10 * * 11 * This program is free software; you can redistribute it and/or modify * 12 * it under the terms of the GNU General Public License as published by * 13 * the Free Software Foundation; either version 2 of the License, or * 14 * (at your option) any later version. * 15 * * 16 * This program is distributed in the hope that it will be useful, * 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) * 20 * for more details. * 21 * * 22 ****************************************************************************/ 23 #ifndef NORMAL_EXTRAPOLATION_H 24 #define NORMAL_EXTRAPOLATION_H 25 26 #include <vcg/space/index/kdtree/kdtree.h> 27 #include <vcg/space/fitting3.h> 28 #include <vcg/complex/algorithms/smooth.h> 29 30 namespace vcg { 31 namespace tri { 32 /// 33 /** \addtogroup trimesh */ 34 /*@{*/ 35 /// Class of static functions to smooth and fair meshes and their attributes. 36 37 38 39 template <typename MeshType> 40 class PointCloudNormal { 41 public: 42 43 typedef typename MeshType::VertexType VertexType; 44 typedef typename MeshType::VertexType::CoordType CoordType; 45 typedef typename MeshType::VertexPointer VertexPointer; 46 typedef typename MeshType::VertexIterator VertexIterator; 47 typedef typename MeshType::ScalarType ScalarType; 48 49 class WArc 50 { 51 public: WArc(VertexPointer _s,VertexPointer _t)52 WArc(VertexPointer _s,VertexPointer _t):src(_s),trg(_t),w(fabs(_s->cN()*_t->cN())){} 53 54 VertexPointer src; 55 VertexPointer trg; 56 float w; 57 bool operator< (const WArc &a) const {return w<a.w;} 58 }; 59 60 static void ComputeUndirectedNormal(MeshType &m, int nn, ScalarType maxDist, KdTree<ScalarType> &tree,vcg::CallBackPos * cb=0) 61 { 62 // tree.setMaxNofNeighbors(nn); 63 const ScalarType maxDistSquared = maxDist*maxDist; 64 int cnt=0; 65 int step = max(m.vn, int(m.vn / 100)); 66 typename KdTree<ScalarType>::PriorityQueue nq; 67 for (VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi) 68 { 69 tree.doQueryK(vi->cP(),nn,nq); 70 if(cb && (++cnt%step)==0) cb(cnt/step,"Fitting planes"); 71 72 // int neighbours = tree.getNofFoundNeighbors(); 73 int neighbours = nq.getNofElements(); 74 std::vector<CoordType> ptVec; 75 for (int i = 0; i < neighbours; i++) 76 { 77 // int neightId = tree.getNeighborId(i); 78 int neightId = nq.getIndex(i); 79 if(nq.getWeight(i) <maxDistSquared) 80 ptVec.push_back(m.vert[neightId].cP()); 81 } 82 Plane3<ScalarType> plane; 83 FitPlaneToPointSet(ptVec,plane); 84 vi->N()=plane.Direction(); 85 } 86 } 87 AddNeighboursToHeap(MeshType & m,VertexPointer vp,int nn,KdTree<ScalarType> & tree,std::vector<WArc> & heap)88 static void AddNeighboursToHeap( MeshType &m, VertexPointer vp, int nn, KdTree<ScalarType> &tree, std::vector<WArc> &heap) 89 { 90 typename KdTree<ScalarType>::PriorityQueue nq; 91 tree.doQueryK(vp->cP(),nn,nq); 92 93 int neighbours = nq.getNofElements(); 94 for (int i = 0; i < neighbours; i++) 95 { 96 // int neightId = tree.getNeighborId(i); 97 int neightId = nq.getIndex(i); 98 if (neightId < m.vn && (&m.vert[neightId] != vp)) 99 { 100 if(!m.vert[neightId].IsV()) 101 { 102 heap.push_back(WArc(vp,&(m.vert[neightId]))); 103 //std::push_heap(heap.begin(),heap.end()); 104 if(heap.back().w < 0.3f) 105 heap.pop_back(); 106 else 107 std::push_heap(heap.begin(),heap.end()); 108 } 109 } 110 } 111 //std::push_heap(heap.begin(),heap.end()); 112 } 113 /*! \brief parameters for the normal generation 114 */ 115 struct Param 116 { ParamParam117 Param(): 118 fittingAdjNum(10), 119 smoothingIterNum(0), 120 coherentAdjNum(8), 121 viewPoint(0,0,0), 122 useViewPoint(false) 123 {} 124 125 int fittingAdjNum; /// number of adjacent nodes used for computing the fitting plane 126 int smoothingIterNum; /// number of itaration of a simple normal smoothing (use the same number of ajdacent of fittingAdjNjm) 127 int coherentAdjNum; /// number of nodes used in the coherency pass 128 CoordType viewPoint; /// position of a viewpoint used to disambiguate direction 129 bool useViewPoint; /// if the position of the viewpoint has to be used. 130 }; 131 132 static void Compute(MeshType &m, Param p, vcg::CallBackPos * cb=0) 133 { 134 tri::Allocator<MeshType>::CompactVertexVector(m); 135 if(cb) cb(1,"Building KdTree..."); 136 VertexConstDataWrapper<MeshType> DW(m); 137 KdTree<ScalarType> tree(DW); 138 139 ComputeUndirectedNormal(m, p.fittingAdjNum, std::numeric_limits<ScalarType>::max(), tree,cb); 140 141 tri::Smooth<MeshType>::VertexNormalPointCloud(m,p.fittingAdjNum,p.smoothingIterNum,&tree); 142 143 if(p.coherentAdjNum==0) return; 144 // tree.setMaxNofNeighbors(p.coherentAdjNum+1); 145 146 if(p.useViewPoint) // Simple case use the viewpoint position to determine the right orientation of each point 147 { 148 for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi) 149 { 150 if ( vi->N().dot(p.viewPoint- vi->P())<0.0f) 151 vi->N()=-(*vi).N(); 152 } 153 return; 154 } 155 156 tri::UpdateFlags<MeshType>::VertexClearV(m); 157 std::vector<WArc> heap; 158 VertexIterator vi=m.vert.begin(); 159 while(true) 160 { 161 // search an unvisited vertex 162 while(vi!=m.vert.end() && vi->IsV()) 163 ++vi; 164 165 if(vi==m.vert.end()) return; 166 167 vi->SetV(); 168 AddNeighboursToHeap(m,&*vi,p.coherentAdjNum,tree,heap); 169 170 while(!heap.empty()) 171 { 172 std::pop_heap(heap.begin(),heap.end()); 173 WArc a = heap.back(); 174 heap.pop_back(); 175 if(!a.trg->IsV()) 176 { 177 a.trg->SetV(); 178 if(a.src->cN()*a.trg->cN()<0.0f) 179 a.trg->N()=-a.trg->N(); 180 AddNeighboursToHeap(m,a.trg,p.coherentAdjNum,tree,heap); 181 } 182 } 183 } 184 185 return; 186 } 187 188 }; 189 }//end namespace vcg 190 }//end namespace vcg 191 #endif // NORMAL_EXTRAPOLATION_H 192