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 VCG_SYMMETRY_H
24 #define VCG_SYMMETRY_H
25 
26 #include <vcg/space/plane3.h>
27 #include <vcg/space/index/grid_static_ptr.h>
28 #include <vcg/complex/algorithms/closest.h>
29 #include <vcg/complex/algorithms/create/platonic.h>
30 #include <vcg/complex/algorithms/point_sampling.h>
31 
32 namespace vcg {
33 namespace tri {
34 
35 //class SphereEdge;
36 //class SphereFace;
37 //class SphereVertex;
38 
39 template <class TriMeshType>
40 class ExtrinsicPlaneSymmetry
41 {
42     typedef typename TriMeshType::VertexType VertexType;
43     typedef typename TriMeshType::FaceType FaceType;
44     typedef typename TriMeshType::CoordType CoordType;
45     typedef typename TriMeshType::ScalarType ScalarType;
46 
47 //    struct SphereUsedTypes : public vcg::UsedTypes<	vcg::Use<SphereVertex>::AsVertexType,
48 //                                                    vcg::Use<SphereFace>::AsFaceType>{};
49 
50 //    class SphereVertex  : public vcg::Vertex< SphereUsedTypes,
51 //                                             vcg::vertex::Coord<CoordType,ScalarType>,
52 //                                             vcg::vertex::Normal<CoordType,ScalarType>,
53 //                                            vcg::vertex::BitFlags>{};
54 
55 //    class SphereFace    : public vcg::Face< SphereUsedTypes, vcg::face::VertexRef,
56 //                                            vcg::vertex::Normal<vcg::Point3<ScalarType>,ScalarType>,
57 //                                            vcg::face::Mark,
58 //                                            vcg::face::BitFlags,vcg::face::FFAdj> {};
59 
60 //    class SphereMesh : public vcg::tri::TriMesh< std::vector<SphereVertex>, std::vector<SphereFace> > {};
61 
62 
63 
64     TriMeshType &tri_mesh;
65 
66     CoordType AlignZeroTr;
67 
68     std::vector<std::vector< ScalarType > > Weight;
69     //std::vector<std::vector<std::pair<VertexType*,VertexType*> > > VotingVertx;
70     std::vector<std::vector<std::pair<CoordType,CoordType>  > > VotingPos;
71 
72     std::vector<ScalarType> Votes;
73 
74 
75 
76     TriMeshType *sphere;
77 
78     typename vcg::GridStaticPtr<FaceType,ScalarType> GridSph;
79 
80     ScalarType RadiusInterval;
81     ScalarType MaxRadius;
82     int radiusSph;
83 
84     std::vector<std::pair<ScalarType,int> > SortedPlanes;
85     std::vector<vcg::Plane3<ScalarType> > SymmetricPlanes;
86 
Bucket(const vcg::Plane3<ScalarType> & Pl)87     int Bucket(const vcg::Plane3<ScalarType> &Pl)
88     {
89         ScalarType Offset=Pl.Offset();
90         CoordType Direction=Pl.Direction();
91         Direction.Normalize();
92         ///get the offset interval
93         int OffsetI=floor((Offset/RadiusInterval)+0.5);
94         assert(OffsetI<radiusSph);
95         ///then get the closest face
96         ScalarType MaxD=sphere->bbox.Diag();
97         ScalarType MinD;
98         CoordType ClosePt;
99         FaceType *choosen=NULL;
100         choosen=vcg::tri::GetClosestFaceBase(*sphere,GridSph,Direction,MaxD,MinD,ClosePt);
101         assert(choosen!=NULL);
102         int IndexF=choosen-&(sphere->face[0]);
103         ///compose the final index
104         int OffsetRadius=OffsetI * (sphere->face.size());
105         return(OffsetRadius+IndexF);
106     }
107 
Elect(CoordType p0,CoordType p1)108     void Elect(CoordType p0,CoordType p1)
109     {
110         CoordType AvP=(p0+p1)/2.0;
111         AvP-=AlignZeroTr;
112         CoordType Direction=p0-p1;
113         Direction.Normalize();
114         vcg::Plane3<ScalarType> Pl;
115         Pl.Init(AvP,Direction);
116         //invert if needed
117         if (Pl.Offset()<0)
118         {
119             ScalarType Off=Pl.Offset();
120             CoordType Dir=Pl.Direction();
121             Pl.Set(-Dir,-Off);
122         }
123         int index=Bucket(Pl);
124         assert(index>=0);
125         assert(index<(int)Votes.size());
126         ScalarType VoteValue=1;
127         Votes[index]+=VoteValue;
128         Weight[index].push_back(VoteValue);
129         VotingPos[index].push_back(std::pair<CoordType,CoordType> (p0,p1));
130     }
131 
GetInterpolatedPlane(int & Index)132     vcg::Plane3<ScalarType> GetInterpolatedPlane(int &Index)
133     {
134         ///then fit the plane
135         CoordType AvDir=CoordType(0,0,0);
136         ScalarType WSum=0;
137         ScalarType AvOffset=0;
138         for (size_t i=0;i<VotingPos[Index].size();i++)
139         {
140             CoordType p0=VotingPos[Index][i].first;
141             CoordType p1=VotingPos[Index][i].second;
142             ScalarType W=Weight[Index][i];
143             CoordType Dir=(p0-p1);
144             Dir.Normalize();
145 
146             CoordType AvP=(p0+p1)/2.0;
147             ScalarType Offset=AvP*Dir;
148 
149             //invert if needed
150             if (Offset<0)
151             {
152                 Offset=-Offset;
153                 Dir=-Dir;
154             }
155 
156             AvDir+=(Dir*W);
157             AvOffset+=(Offset*W);
158             WSum+=W;
159         }
160         AvDir.Normalize();
161         AvOffset/=WSum;
162         vcg::Plane3<ScalarType> Pl;
163         Pl.Set(AvDir,AvOffset);
164         return Pl;
165     }
166 
GetBasePlane(int & Index)167     vcg::Plane3<ScalarType> GetBasePlane(int &Index)
168     {
169         ///get offset value
170         int OffsetIndex=Index/sphere->face.size();
171         ScalarType OffsetVal=OffsetIndex*RadiusInterval;
172         int DirectionIndex=Index % sphere->face.size();
173         CoordType PlaneDirection=(sphere->face[DirectionIndex].P(0)+
174                                   sphere->face[DirectionIndex].P(1)+
175                                   sphere->face[DirectionIndex].P(2))/3.0;
176         PlaneDirection.Normalize();
177         CoordType CenterPl=PlaneDirection*OffsetVal;
178         CenterPl+=AlignZeroTr;
179         vcg::Plane3<ScalarType> RetPl;
180         RetPl.Init(CenterPl,PlaneDirection);
181         return RetPl;
182     }
183 
184     void InitSymmetricPlanes(const int SubN=4)
185     {
186         assert(SortedPlanes.size()>0);
187         SymmetricPlanes.clear();
188         int BestN=pow((ScalarType)2,(ScalarType)SubN);
189         if (BestN>=(int)SortedPlanes.size())BestN=SortedPlanes.size()-1;
190         for (size_t j=SortedPlanes.size()-1;j>SortedPlanes.size()-1-SubN;j--)
191         {
192             int Index=SortedPlanes[j].second;
193             SymmetricPlanes.push_back(GetInterpolatedPlane(Index));
194         }
195     }
196 
197 
198 public:
199 
GetPlanes(std::vector<vcg::Plane3<ScalarType>> & Planes,int Num)200     void GetPlanes(std::vector<vcg::Plane3<ScalarType> > &Planes,int Num)
201     {
202         if (SymmetricPlanes.size()==0)return;
203 
204         for (int i=0;i<Num;i++)
205             Planes.push_back(SymmetricPlanes[i]);
206     }
207 
208     void Init(bool OnlyBorder=false,
209               int SubDirections=4,
210               int NumberBestPlanes=16)
211     {
212         if (OnlyBorder)
213         {
214             vcg::tri::UpdateTopology<TriMeshType>::FaceFace(tri_mesh);
215             vcg::tri::UpdateFlags<TriMeshType>::FaceBorderFromFF(tri_mesh);
216             vcg::tri::UpdateFlags<TriMeshType>::VertexBorderFromFaceBorder(tri_mesh);
217         }
218         AlignZeroTr=tri_mesh.bbox.Center();
219 
220         ///initialize the mesh
221         if (sphere!=NULL)
222             sphere->Clear();
223         else
224             sphere=new TriMeshType();
225 
226         //create the sphere
227         vcg::tri::Sphere<TriMeshType>(*sphere,SubDirections);
228         vcg::tri::UpdateBounding<TriMeshType>::Box(*sphere);
229 		sphere->face.EnableMark();
230 
231         ///initialize grid
232         GridSph.Set(sphere->face.begin(),sphere->face.end());
233 
234         ///then get radius division steps
235         ScalarType MaxRadius=tri_mesh.bbox.Diag()/2;
236         int AreaSph=sphere->fn;
237         radiusSph=ceil(sqrt((ScalarType)AreaSph/4.0*M_PI));
238         RadiusInterval=MaxRadius/(ScalarType)radiusSph;
239 
240         ///and finally allocate space for votes
241         Votes.resize(radiusSph*sphere->fn,0);
242 
243         Weight.resize(radiusSph*sphere->fn);
244         VotingPos.resize(radiusSph*sphere->fn);
245 
246         ///then count votes
247         for (size_t i=0;i<tri_mesh.vert.size();i++)
248             for (size_t j=i+1;j<tri_mesh.vert.size();j++)
249             {
250                 VertexType *v0=&tri_mesh.vert[i];
251                 VertexType *v1=&tri_mesh.vert[j];
252                 if ((OnlyBorder)&&(!((v0->IsB())&&(v1->IsB()))))continue;
253                 Elect(v0->P(),v1->P());
254             }
255 
256         SortedPlanes.resize(Votes.size());
257         for (size_t i=0;i<Votes.size();i++)
258             SortedPlanes[i]=std::pair<ScalarType,int>(Votes[i],i);
259 
260         std::sort(SortedPlanes.begin(),SortedPlanes.end());
261 
262         InitSymmetricPlanes(NumberBestPlanes);
263 
264     }
265 
ExtrinsicPlaneSymmetry(TriMeshType & _tri_mesh)266     ExtrinsicPlaneSymmetry(TriMeshType &_tri_mesh):tri_mesh(_tri_mesh)
267     {
268         sphere=NULL;
269         RadiusInterval=-1;
270         radiusSph=-1;
271     }
272 
273 };
274 
275 }///end namespace vcg
276 }///end namespace tri
277 #endif
278