1 // Copyright (C) 2007-2013 CEA/DEN, EDF R&D
3 // This library is free software; you can redistribute it and/or
4 // modify it under the terms of the GNU Lesser General Public
5 // License as published by the Free Software Foundation; either
6 // version 2.1 of the License.
8 // This library is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 // Lesser General Public License for more details.
13 // You should have received a copy of the GNU Lesser General Public
14 // License along with this library; if not, write to the Free Software
15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
19 // Author : Anthony Geay (CEA/DEN)
21 #include "InterpKernelCellSimplify.hxx"
22 #include "CellModel.hxx"
34 using namespace INTERP_KERNEL;
37 * This method takes as input a cell with type 'type' and whose connectivity is defined by (conn,lgth)
38 * It retrieves the same cell with a potentially different type (in return) whose connectivity is defined by (retConn,retLgth)
39 * \b WARNING for optimization reason the arrays 'retConn' and 'conn' can overlapped !
41 INTERP_KERNEL::NormalizedCellType CellSimplify::simplifyDegeneratedCell(INTERP_KERNEL::NormalizedCellType type, const int *conn, int lgth,
42 int *retConn, int& retLgth) throw(INTERP_KERNEL::Exception)
44 const INTERP_KERNEL::CellModel& cm=INTERP_KERNEL::CellModel::GetCellModel(type);
45 std::set<int> c(conn,conn+lgth);
47 bool isObviousNonDegeneratedCell=((int)c.size()==lgth);
48 if(cm.isQuadratic() || isObviousNonDegeneratedCell)
49 {//quadratic do nothing for the moment.
51 int *tmp=new int[lgth];//no direct std::copy ! overlapping of conn and retConn !
52 std::copy(conn,conn+lgth,tmp);
53 std::copy(tmp,tmp+lgth,retConn);
57 if(cm.getDimension()==2)
59 int *tmp=new int[lgth];
62 for(int i=1;i<lgth;i++)
63 if(std::find(tmp,tmp+newPos,conn[i])==tmp+newPos)
64 tmp[newPos++]=conn[i];
65 INTERP_KERNEL::NormalizedCellType ret=tryToUnPoly2D(cm.isQuadratic(),tmp,newPos,retConn,retLgth);
69 if(cm.getDimension()==3)
71 int nbOfFaces,lgthOfPolyhConn;
72 int *zipFullReprOfPolyh=getFullPolyh3DCell(type,conn,lgth,nbOfFaces,lgthOfPolyhConn);
73 INTERP_KERNEL::NormalizedCellType ret=tryToUnPoly3D(zipFullReprOfPolyh,nbOfFaces,lgthOfPolyhConn,retConn,retLgth);
74 delete [] zipFullReprOfPolyh;
77 throw INTERP_KERNEL::Exception("CellSimplify::simplifyDegeneratedCell : works only with 2D and 3D cell !");
82 * This static method tries to unpolygonize a cell whose connectivity is given by 'conn' and 'lgth'.
83 * Contrary to INTERP_KERNEL::CellSimplify::simplifyDegeneratedCell method 'conn' and 'retConn' do not overlap.
85 INTERP_KERNEL::NormalizedCellType CellSimplify::tryToUnPoly2D(bool isQuad, const int *conn, int lgth, int *retConn, int& retLgth)
88 std::copy(conn,conn+lgth,retConn);
94 return INTERP_KERNEL::NORM_TRI3;
96 return INTERP_KERNEL::NORM_QUAD4;
98 return INTERP_KERNEL::NORM_POLYGON;
106 return INTERP_KERNEL::NORM_TRI6;
108 return INTERP_KERNEL::NORM_QUAD8;
110 return INTERP_KERNEL::NORM_QPOLYG;
116 * This method takes as input a 3D linear cell and put its representation in returned array. Warning the returned array has to be deallocated.
117 * The length of the returned array is specified by out parameter
118 * The format of output array is the following :
119 * 1,2,3,-1,3,4,2,-1,3,4,1,-1,1,2,4,NORM_TRI3,NORM_TRI3,NORM_TRI3 (faces type at the end of classical polyhedron nodal description)
121 int *CellSimplify::getFullPolyh3DCell(INTERP_KERNEL::NormalizedCellType type, const int *conn, int lgth,
122 int& retNbOfFaces, int& retLgth)
124 const INTERP_KERNEL::CellModel& cm=INTERP_KERNEL::CellModel::GetCellModel(type);
125 unsigned nbOfFaces=cm.getNumberOfSons2(conn,lgth);
126 int *tmp=new int[nbOfFaces*(lgth+1)];
128 std::vector<int> faces;
129 for(unsigned j=0;j<nbOfFaces;j++)
131 INTERP_KERNEL::NormalizedCellType type2;
132 unsigned offset=cm.fillSonCellNodalConnectivity2(j,conn,lgth,work,type2);
134 int *tmp2=new int[offset];
137 for(unsigned k=1;k<offset;k++)
138 if(std::find(tmp2,tmp2+newPos,work[k])==tmp2+newPos)
139 tmp2[newPos++]=work[k];
146 faces.push_back(tryToUnPoly2D(CellModel::GetCellModel(type2).isQuadratic(),tmp2,newPos,work,tmp3));
152 std::copy(faces.begin(),faces.end(),--work);
153 retNbOfFaces=(int)faces.size();
154 retLgth=(int)std::distance(tmp,work);
159 * This static method tries to unpolygonize a cell whose connectivity is given by 'conn' (format is the same as specified in
160 * method INTERP_KERNEL::CellSimplify::getFullPolyh3DCell ) and 'lgth'+'nbOfFaces'.
161 * Contrary to INTERP_KERNEL::CellSimplify::simplifyDegeneratedCell method 'conn' and 'retConn' do not overlap.
163 INTERP_KERNEL::NormalizedCellType CellSimplify::tryToUnPoly3D(const int *conn, int nbOfFaces, int lgth, int *retConn, int& retLgth)
165 std::set<int> nodes(conn,conn+lgth);
167 int nbOfNodes=(int)nodes.size();
168 int magicNumber=100*nbOfNodes+nbOfFaces;
172 return tryToUnPolyHex8(conn,nbOfFaces,lgth,retConn,retLgth);
174 return tryToUnPolyHexp12(conn,nbOfFaces,lgth,retConn,retLgth);
176 return tryToUnPolyPenta6(conn,nbOfFaces,lgth,retConn,retLgth);
178 return tryToUnPolyPyra5(conn,nbOfFaces,lgth,retConn,retLgth);
180 return tryToUnPolyTetra4(conn,nbOfFaces,lgth,retConn,retLgth);
183 std::copy(conn,conn+lgth,retConn);
184 return INTERP_KERNEL::NORM_POLYHED;
188 bool CellSimplify::orientOppositeFace(const int *baseFace, int *retConn, const int *sideFace, int lgthBaseFace)
190 std::vector<int> tmp2;
191 std::set<int> bases(baseFace,baseFace+lgthBaseFace);
192 std::set<int> sides(sideFace,sideFace+4);
193 std::set_intersection(bases.begin(),bases.end(),sides.begin(),sides.end(),std::back_insert_iterator< std::vector<int> >(tmp2));
196 std::vector< std::pair<int,int> > baseEdges(lgthBaseFace);
197 std::vector< std::pair<int,int> > oppEdges(lgthBaseFace);
198 std::vector< std::pair<int,int> > sideEdges(4);
199 for(int i=0;i<lgthBaseFace;i++)
201 baseEdges[i]=std::pair<int,int>(baseFace[i],baseFace[(i+1)%lgthBaseFace]);
202 oppEdges[i]=std::pair<int,int>(retConn[i],retConn[(i+1)%lgthBaseFace]);
205 sideEdges[i]=std::pair<int,int>(sideFace[i],sideFace[(i+1)%4]);
206 std::vector< std::pair<int,int> > tmp;
207 std::set< std::pair<int,int> > baseEdgesS(baseEdges.begin(),baseEdges.end());
208 std::set< std::pair<int,int> > sideEdgesS(sideEdges.begin(),sideEdges.end());
209 std::set_intersection(baseEdgesS.begin(),baseEdgesS.end(),sideEdgesS.begin(),sideEdgesS.end(),std::back_insert_iterator< std::vector< std::pair<int,int> > >(tmp));
215 std::pair<int,int> p=sideEdges[i];
216 std::pair<int,int> r(p.second,p.first);
219 //end reverse sideFace
220 std::set< std::pair<int,int> > baseEdgesS2(baseEdges.begin(),baseEdges.end());
221 std::set< std::pair<int,int> > sideEdgesS2(sideEdges.begin(),sideEdges.end());
222 std::set_intersection(baseEdgesS2.begin(),baseEdgesS2.end(),sideEdgesS2.begin(),sideEdgesS2.end(),std::back_insert_iterator< std::vector< std::pair<int,int> > >(tmp));
229 std::pair<int,int> pInOpp;
230 for(int i=0;i<4 && !found;i++)
231 {//finding the pair(edge) in sideFace that do not include any node of tmp[0] edge
232 found=(tmp[0].first!=sideEdges[i].first && tmp[0].first!=sideEdges[i].second &&
233 tmp[0].second!=sideEdges[i].first && tmp[0].second!=sideEdges[i].second);
235 {//found ! reverse it
236 pInOpp.first=sideEdges[i].second;
237 pInOpp.second=sideEdges[i].first;
242 int pos=(int)std::distance(baseEdges.begin(),std::find(baseEdges.begin(),baseEdges.end(),tmp[0]));
243 std::vector< std::pair<int,int> >::iterator it=std::find(oppEdges.begin(),oppEdges.end(),pInOpp);
244 if(it==oppEdges.end())//the opposite edge of side face is not found opposite face ... maybe problem of orientation of polyhedron
246 int pos2=(int)std::distance(oppEdges.begin(),it);
249 offset+=lgthBaseFace;
250 //this is the end copy the result
251 int *tmp3=new int[lgthBaseFace];
252 for(int i=0;i<lgthBaseFace;i++)
253 tmp3[(offset+i)%lgthBaseFace]=oppEdges[i].first;
254 std::copy(tmp3,tmp3+lgthBaseFace,retConn);
259 bool CellSimplify::isWellOriented(const int *baseFace, int *retConn, const int *sideFace, int lgthBaseFace)
265 * This method is trying to permute the connectivity of 'oppFace' face so that the k_th node of 'baseFace' is associated to the
266 * k_th node in retConnOfOppFace. Excluded faces 'baseFace' and 'oppFace' all the other faces in 'conn' must be QUAD4 faces.
267 * If the arragement process succeeds true is returned and retConnOfOppFace is filled.
269 bool CellSimplify::tryToArrangeOppositeFace(const int *conn, int lgth, int lgthBaseFace, const int *baseFace, const int *oppFace, int nbOfFaces, int *retConnOfOppFace)
271 retConnOfOppFace[0]=oppFace[0];
272 for(int j=1;j<lgthBaseFace;j++)
273 retConnOfOppFace[j]=oppFace[lgthBaseFace-j];
274 const int *curFace=conn;
277 for(int i=0;i<nbOfFaces && ret;i++)
279 if(curFace!=baseFace && curFace!=oppFace)
282 ret=orientOppositeFace(baseFace,retConnOfOppFace,curFace,lgthBaseFace);
284 ret=isWellOriented(baseFace,retConnOfOppFace,curFace,lgthBaseFace);
287 curFace=std::find(curFace,conn+lgth,-1);
294 * Cell with 'conn' connectivity has been detected as a good candidate. Full check of this. If yes NORM_HEXA8 is returned.
295 * This method is only callable if in 'conn' there is 8 nodes and 6 faces.
296 * If fails a POLYHED is returned.
298 INTERP_KERNEL::NormalizedCellType CellSimplify::tryToUnPolyHex8(const int *conn, int nbOfFaces, int lgth, int *retConn, int& retLgth)
300 if(std::find_if(conn+lgth,conn+lgth+nbOfFaces,std::bind2nd(std::not_equal_to<int>(),(int)INTERP_KERNEL::NORM_QUAD4))==conn+lgth+nbOfFaces)
301 {//6 faces are QUAD4.
303 std::set<int> conn1(conn,conn+4);
304 for(int i=1;i<6 && oppositeFace<0;i++)
306 std::vector<int> tmp;
307 std::set<int> conn2(conn+5*i,conn+5*i+4);
308 std::set_intersection(conn1.begin(),conn1.end(),conn2.begin(),conn2.end(),std::back_insert_iterator< std::vector<int> >(tmp));
313 {//oppositeFace of face#0 found.
315 if(tryToArrangeOppositeFace(conn,lgth,4,conn,conn+5*oppositeFace,6,tmp2))
317 std::copy(conn,conn+4,retConn);
318 std::copy(tmp2,tmp2+4,retConn+4);
320 return INTERP_KERNEL::NORM_HEXA8;
325 std::copy(conn,conn+lgth,retConn);
326 return INTERP_KERNEL::NORM_POLYHED;
329 INTERP_KERNEL::NormalizedCellType CellSimplify::tryToUnPolyHexp12(const int *conn, int nbOfFaces, int lgth, int *retConn, int& retLgth)
331 std::size_t nbOfHexagon=std::count(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_POLYGON);
332 std::size_t nbOfQuad=std::count(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_QUAD4);
333 if(nbOfQuad==6 && nbOfHexagon==2)
335 const int *hexag0=std::find(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_POLYGON);
336 std::size_t hexg0Id=std::distance(conn+lgth,hexag0);
337 const int *hexag1=std::find(hexag0+1,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_POLYGON);
338 std::size_t hexg1Id=std::distance(conn+lgth,hexag1);
339 const int *connHexag0=conn+5*hexg0Id;
340 std::size_t lgthH0=std::distance(connHexag0,std::find(connHexag0,conn+lgth,-1));
343 const int *connHexag1=conn+5*hexg0Id+7+(hexg1Id-hexg0Id-1)*5;
344 std::size_t lgthH1=std::distance(connHexag1,std::find(connHexag1,conn+lgth,-1));
347 std::vector<int> tmp;
348 std::set<int> conn1(connHexag0,connHexag0+6);
349 std::set<int> conn2(connHexag1,connHexag1+6);
350 std::set_intersection(conn1.begin(),conn1.end(),conn2.begin(),conn2.end(),std::back_insert_iterator< std::vector<int> >(tmp));
354 if(tryToArrangeOppositeFace(conn,lgth,6,connHexag0,connHexag1,8,tmp2))
356 std::copy(connHexag0,connHexag0+6,retConn);
357 std::copy(tmp2,tmp2+6,retConn+6);
359 return INTERP_KERNEL::NORM_HEXGP12;
366 std::copy(conn,conn+lgth,retConn);
367 return INTERP_KERNEL::NORM_POLYHED;
371 * Cell with 'conn' connectivity has been detected as a good candidate. Full check of this. If yes NORM_PENTA6 is returned.
372 * If fails a POLYHED is returned.
374 INTERP_KERNEL::NormalizedCellType CellSimplify::tryToUnPolyPenta6(const int *conn, int nbOfFaces, int lgth, int *retConn, int& retLgth)
376 std::size_t nbOfTriFace=std::count(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_TRI3);
377 std::size_t nbOfQuadFace=std::count(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_QUAD4);
378 if(nbOfTriFace==2 && nbOfQuadFace==3)
380 std::size_t tri3_0=std::distance(conn+lgth,std::find(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_TRI3));
381 std::size_t tri3_1=std::distance(conn+lgth,std::find(conn+lgth+tri3_0+1,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_TRI3));
382 const int *tri_0=0,*tri_1=0;
384 for(std::size_t i=0;i<5;i++)
390 w=std::find(w,conn+lgth,-1);
393 std::vector<int> tmp;
394 std::set<int> conn1(tri_0,tri_0+3);
395 std::set<int> conn2(tri_1,tri_1+3);
396 std::set_intersection(conn1.begin(),conn1.end(),conn2.begin(),conn2.end(),std::back_insert_iterator< std::vector<int> >(tmp));
400 if(tryToArrangeOppositeFace(conn,lgth,3,tri_0,tri_1,5,tmp2))
402 std::copy(tri_0,tri_0+3,retConn);
403 std::copy(tmp2,tmp2+3,retConn+3);
405 return INTERP_KERNEL::NORM_PENTA6;
410 std::copy(conn,conn+lgth,retConn);
411 return INTERP_KERNEL::NORM_POLYHED;
415 * Cell with 'conn' connectivity has been detected as a good candidate. Full check of this. If yes NORM_PYRA5 is returned.
416 * If fails a POLYHED is returned.
418 INTERP_KERNEL::NormalizedCellType CellSimplify::tryToUnPolyPyra5(const int *conn, int nbOfFaces, int lgth, int *retConn, int& retLgth)
420 std::size_t nbOfTriFace=std::count(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_TRI3);
421 std::size_t nbOfQuadFace=std::count(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_QUAD4);
422 if(nbOfTriFace==4 && nbOfQuadFace==1)
424 std::size_t quad4_pos=std::distance(conn+lgth,std::find(conn+lgth,conn+lgth+nbOfFaces,(int)INTERP_KERNEL::NORM_QUAD4));
427 for(std::size_t i=0;i<5 && quad4==0;i++)
431 w=std::find(w,conn+lgth,-1);
434 std::set<int> quad4S(quad4,quad4+4);
438 for(std::size_t i=0;i<5 && ok;i++)
442 std::vector<int> tmp;
443 std::set<int> conn2(w,w+3);
444 std::set_intersection(conn2.begin(),conn2.end(),quad4S.begin(),quad4S.end(),std::back_insert_iterator< std::vector<int> >(tmp));
447 std::set_difference(conn2.begin(),conn2.end(),quad4S.begin(),quad4S.end(),std::back_insert_iterator< std::vector<int> >(tmp));
448 ok=ok && tmp.size()==1;
457 w=std::find(w,conn+lgth,-1);
462 std::copy(quad4,quad4+4,retConn);
465 return INTERP_KERNEL::NORM_PYRA5;
469 std::copy(conn,conn+lgth,retConn);
470 return INTERP_KERNEL::NORM_POLYHED;
474 * Cell with 'conn' connectivity has been detected as a good candidate. Full check of this. If yes NORM_TETRA4 is returned.
475 * If fails a POLYHED is returned.
477 INTERP_KERNEL::NormalizedCellType CellSimplify::tryToUnPolyTetra4(const int *conn, int nbOfFaces, int lgth, int *retConn, int& retLgth)
479 if(std::find_if(conn+lgth,conn+lgth+nbOfFaces,std::bind2nd(std::not_equal_to<int>(),(int)INTERP_KERNEL::NORM_TRI3))==conn+lgth+nbOfFaces)
481 std::set<int> tribase(conn,conn+3);
484 for(int i=1;i<4 && ok;i++)
486 std::vector<int> tmp;
487 std::set<int> conn2(conn+i*4,conn+4*i+3);
488 std::set_intersection(conn2.begin(),conn2.end(),tribase.begin(),tribase.end(),std::back_insert_iterator< std::vector<int> >(tmp));
491 std::set_difference(conn2.begin(),conn2.end(),tribase.begin(),tribase.end(),std::back_insert_iterator< std::vector<int> >(tmp));
492 ok=ok && tmp.size()==1;
503 std::copy(conn,conn+3,retConn);
506 return INTERP_KERNEL::NORM_TETRA4;
510 std::copy(conn,conn+lgth,retConn);
511 return INTERP_KERNEL::NORM_POLYHED;