src/VTKViewer/VTKViewer_ConvexTool.cxx

   1 //  This library is distributed in the hope that it will be useful,
   2 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
   3 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   4 //  Lesser General Public License for more details.
   5 //
   6 //  You should have received a copy of the GNU Lesser General Public
   7 //  License along with this library; if not, write to the Free Software
   8 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
   9 //
  10 //  See http://www.opencascade.org/SALOME/ or email : webmaster.salome@opencascade.org
  11 //
  12 //
  13 //
  14 //  File   : VTKViewer_ConvexTool.cxx
  15 //  Author : Eugeny Nikolaev
  16 //  Module : SALOME
  17 //  $Header$
  18
  19 #include "VTKViewer_ConvexTool.h"
  20
  21 #include <vtkUnstructuredGrid.h>
  22 #include <vtkTriangle.h>
  23 #include <vtkConvexPointSet.h>
  24
  25 #include <vtkMath.h>
  26 #include <set>
  27 #include <algorithm>
  28 #include <algo.h>
  29
  30 static float FACE_TOLERANCE=0;
  31
  32 typedef std::set<vtkIdType> TUIDS; // unique ids
  33 typedef std::map<vtkIdType,TUIDS> TPTOIDS; // id points -> unique ids
  34
  35
  36 namespace CONVEX_TOOL{
  37 #ifdef _DEBUG_
  38 static int MYDEBUG = 0;
  39 #else
  40 static int MYDEBUG = 0;
  41 #endif
  42
  43 static void GetCenter(vtkUnstructuredGrid* theGrid,TCell theptIds,float *center)
  44 {
  45   float *p;
  46   center[0] = center[1] = center[2] = 0.0;
  47
  48   int numIds=theptIds.size();
  49
  50   // get the center of the cell
  51   for (int i=0; i < numIds; i++)
  52     {
  53       p = theGrid->GetPoint(theptIds[i]);
  54       for (int j=0; j < 3; j++)
  55         {
  56           center[j] += p[j];
  57         }
  58     }
  59   for (int j=0; j<3; j++)
  60     {
  61       center[j] /= numIds;
  62     }
  63 }
  64
  65 static void ReverseIds(TCell &theIds){
  66   int i;
  67   vtkIdType tmp;
  68   vtkIdType npts=theIds.size();
  69
  70   for(i=0;i<(npts/2);i++){
  71     tmp = theIds[i];
  72     theIds[i] = theIds[npts-i-1];
  73     theIds[npts-i-1] = tmp;
  74   }
  75 }
  76
  77 // caclulation of connected faces (faceId -> (faceId1,faceId2, ...))
  78 void GetFriends(const TPTOIDS p2faces,const TCellArray f2points,TPTOIDS& face2face_output)
  79 {
  80   TCellArray::const_iterator f2pIter = f2points.begin();
  81
  82   for( ; f2pIter!=f2points.end() ; f2pIter++ ){
  83     vtkIdType faceId = f2pIter->first;
  84     TCell face_points = f2pIter->second;
  85     int nb_face_points = face_points.size();
  86
  87     vtkIdType id1;
  88     vtkIdType id2;
  89     TPTOIDS::const_iterator faces1;
  90     TPTOIDS::const_iterator faces2;
  91
  92     id1 = face_points[0];
  93     faces1 = p2faces.find(id1);
  94
  95     TUIDS output_faces;
  96
  97     for(int i=1 ; i<nb_face_points ; i++ ){
  98
  99       id2 = face_points[i];
 100
 101       faces2 = p2faces.find(id2);
 102
 103       std::set_intersection(faces1->second.begin(), faces1->second.end(), faces2->second.begin(), faces2->second.end(),
 104                             inserter(output_faces,output_faces.begin()));
 105
 106       id1 = id2;
 107       faces1 = faces2;
 108     }
 109     id1 = face_points[0];
 110     faces1 = p2faces.find(id1);
 111     std::set_intersection(faces1->second.begin(), faces1->second.end(), faces2->second.begin(), faces2->second.end(),
 112                           inserter(output_faces,output_faces.begin()));
 113
 114     output_faces.erase(faceId); // erase the face id for which we found friends
 115
 116     if(MYDEBUG){
 117       cout << "fId[" << faceId <<"]: ";
 118       copy(output_faces.begin(), output_faces.end(), ostream_iterator<vtkIdType>(cout, " "));
 119       cout << endl;
 120     }
 121
 122     face2face_output[faceId] = output_faces;
 123   }
 124 }
 125
 126 bool IsConnectedFacesOnOnePlane(vtkUnstructuredGrid* theGrid,
 127                                 vtkIdType theFId1,vtkIdType theFId2,
 128                                 TUIDS FpIds1,TUIDS FpIds2)
 129 {
 130   bool status = false;
 131   TUIDS common_ids;
 132   std::set_intersection(FpIds1.begin(), FpIds1.end(), FpIds2.begin(), FpIds2.end(),
 133                         inserter(common_ids,common_ids.begin()));
 134
 135   /*           Number of common ids = 2 (A1,A2)
 136
 137
 138                 _ _ _ _ _      _ _ _ _    vectors:
 139                |         \   /         |   v1 {A2,A1}
 140                           \ /              v2 {A1,B1}
 141                |           | A2        |   v3 {A1,C1}
 142                            |
 143                |           |           |
 144                            |
 145                |           | A1        |
 146                           / \
 147                |_ _ _ _ _/   \_ _ _ _ _|
 148                B2        B1   C1        C2
 149
 150    */
 151   TUIDS::iterator common_iter = common_ids.begin();
 152   if(common_ids.size() == 2){
 153     TUIDS::iterator loc_id1_0 = FpIds1.find(*(common_iter));
 154     common_iter++;
 155     TUIDS::iterator loc_id1_1 = FpIds1.find(*(common_iter));
 156
 157     TUIDS::iterator loc_id2_0 = FpIds1.begin();
 158     TUIDS::iterator loc_id2_1 = FpIds2.begin();
 159
 160     vtkIdType A1 = *loc_id1_0;
 161     vtkIdType A2 = *loc_id1_1;
 162     vtkIdType B1,B2;
 163     vtkIdType C1,C2;
 164
 165     for(;loc_id2_0!=FpIds1.end();loc_id2_0++)
 166       if(*loc_id2_0 != A1 && *loc_id2_0!= A2){
 167         B1 = *loc_id2_0;
 168         break;
 169       }
 170     for(;loc_id2_1!=FpIds2.end();loc_id2_1++)
 171       if(*loc_id2_1 != A1 && *loc_id2_1!= A2){
 172         C1 = *loc_id2_1;
 173         break;
 174       }
 175     if(MYDEBUG) cout <<endl;
 176     if(MYDEBUG) cout << "FId_1="<<theFId1<<" FId_2="<<theFId2<<endl;
 177     if(MYDEBUG) cout << "   A1="<<A1<<" A2="<<A2<<" B1="<<B1<<" C1="<<C1<<" ->";
 178     float *p[4];
 179     float v1[3],v2[3],v3[3];
 180     p[0] = theGrid->GetPoint(A1);
 181     p[1] = theGrid->GetPoint(A2);
 182     p[2] = theGrid->GetPoint(B1);
 183     p[3] = theGrid->GetPoint(C1);
 184
 185     for(int i=0;i<3;i++){
 186       v1[i] = p[1][i] - p[0][i];
 187       v2[i] = p[2][i] - p[0][i];
 188       v3[i] = p[3][i] - p[0][i];
 189     }
 190
 191
 192     float det = vtkMath::Determinant3x3(v1,v2,v3);
 193 //     float det = v1[0]*(v2[1]*v3[2]-v2[2]*v3[1]) -
 194 //                 v1[1]*(v2[0]*v3[2]-v2[2]*v3[0]) +
 195 //                 v1[2]*(v2[0]*v3[1]-v2[1]*v3[0]);
 196     if(det < 0)
 197       det = -det;
 198
 199     if( det <= FACE_TOLERANCE )
 200       status = true;
 201     if (MYDEBUG){
 202       for(int k=0;k<4;k++){
 203         cout << " (";
 204         for(int j=0;j<2;j++){
 205           cout << p[k][j] << ",";
 206         }
 207         cout << p[k][2] << ")   ";
 208       }
 209       cout << endl;
 210     }
 211
 212   } else if (common_ids.size() >2){
 213     // not implemented yet
 214     if(MYDEBUG) cout << "Warning! VTKViewer_ConvexTool::IsConnectedFacesOnOnePlane()";
 215   } else {
 216     // one or no connection ... continue
 217   }
 218
 219   return status;
 220 }
 221
 222 void GetAllFacesOnOnePlane(TPTOIDS theFaces, vtkIdType faceId,
 223                            TUIDS &new_faces,TCell &new_faces_v2){
 224
 225   if (new_faces.find(faceId) != new_faces.end()) return;
 226
 227   new_faces.insert(new_faces.begin(),faceId);
 228   new_faces_v2.push_back(faceId);
 229
 230   TPTOIDS::const_iterator aIter1 = theFaces.find(faceId);
 231   if(aIter1!=theFaces.end()){
 232     TUIDS::const_iterator aIter2 = (aIter1->second).begin();
 233     for(;aIter2!=(aIter1->second).end();aIter2++){
 234       if (new_faces.find(*aIter2) != new_faces.end()) continue;
 235       GetAllFacesOnOnePlane(theFaces,*aIter2,
 236                             new_faces,new_faces_v2); // recurvise
 237     }
 238   }
 239   return;
 240 }
 241
 242 void GetSumm(TCell v1,TCell v2,TCell &output){
 243
 244   output.clear();
 245
 246   if(MYDEBUG) cout << "========================================="<<endl;
 247   if(MYDEBUG) cout << "v1:";
 248   if(MYDEBUG) copy(v1.begin(), v1.end(), ostream_iterator<vtkIdType>(cout, " "));
 249   if(MYDEBUG) cout << "\tv2:";
 250   if(MYDEBUG) copy(v2.begin(), v2.end(), ostream_iterator<vtkIdType>(cout, " "));
 251   if(MYDEBUG) cout << endl;
 252
 253   TUIDS v1_set;
 254   copy(v1.begin(), v1.end(), inserter(v1_set,v1_set.begin()));
 255   TUIDS v2_set;
 256   copy(v2.begin(), v2.end(), inserter(v2_set,v2_set.begin()));
 257   TUIDS tmpIntersection;
 258   set_intersection(v1_set.begin(),v1_set.end(),v2_set.begin(),v2_set.end(),inserter(tmpIntersection,tmpIntersection.begin()));
 259   if(MYDEBUG) copy(tmpIntersection.begin(),tmpIntersection.end(),ostream_iterator<vtkIdType>(cout, " "));
 260   if(MYDEBUG) cout << endl;
 261
 262   if(tmpIntersection.size() < 2)
 263     if(MYDEBUG) cout << __FILE__ << "[" << __LINE__ << "]: Warning ! Wrong ids" << endl;
 264
 265   TCell::iterator v1_iter = v1.begin();
 266
 267   for(;v1_iter!=v1.end();v1_iter++){
 268
 269     vtkIdType curr_id = *v1_iter;
 270
 271     output.push_back(curr_id);
 272
 273     if(tmpIntersection.find(curr_id) != tmpIntersection.end()){
 274       TCell::iterator v1_iter_tmp;
 275       v1_iter_tmp = v1_iter;
 276       v1_iter++;
 277
 278       if(v1_iter==v1.end()) v1_iter=v1.begin();
 279
 280       curr_id = *v1_iter;
 281
 282       if(tmpIntersection.find(curr_id) != tmpIntersection.end()){
 283         TCell::iterator v2_iter = v2.begin();
 284         for(;v2_iter!=v2.end();v2_iter++){
 285           vtkIdType v2_id = *v2_iter;
 286           if(tmpIntersection.find(v2_id) == tmpIntersection.end())
 287             output.push_back(v2_id);
 288         }
 289       }
 290
 291       v1_iter = v1_iter_tmp;
 292       curr_id = *v1_iter;
 293
 294     }
 295   }
 296
 297   if(MYDEBUG) cout << "Result: " ;
 298   if(MYDEBUG) copy(output.begin(),output.end(),ostream_iterator<vtkIdType>(cout, " "));
 299   if(MYDEBUG) cout << endl;
 300 }
 301
 302 void GetPolygonalFaces(vtkUnstructuredGrid* theGrid,int cellId,TCellArray &outputCellArray)
 303 {
 304   if (theGrid->GetCellType(cellId) == VTK_CONVEX_POINT_SET){
 305     // get vtkCell type = VTK_CONVEX_POINT_SET
 306     if(vtkConvexPointSet* convex = static_cast<vtkConvexPointSet*>(theGrid->GetCell(cellId))){
 307       TCellArray f2points;
 308       float convex_center[3]; // convex center point coorinat
 309       int aNbFaces = convex->GetNumberOfFaces();
 310       int numPts = convex->GetNumberOfPoints();
 311       TCell convex_ids;
 312       TPTOIDS p2faces; // key=pointId , value facesIds set
 313
 314       for(int i=0;i<numPts;i++)
 315           convex_ids.push_back(convex->GetPointId(i));
 316
 317       GetCenter(theGrid,convex_ids,convex_center);
 318
 319       for (vtkIdType faceId=0; faceId < aNbFaces; faceId++){
 320         vtkCell *aFace = convex->GetFace(faceId);
 321         int numFacePts = aFace->GetNumberOfPoints();
 322         TCell aIds;
 323
 324         for(int i=0;i<numFacePts;i++)
 325           aIds.push_back(aFace->GetPointId(i));
 326
 327         float v_a[3],v_b[3],v_convex2face[3]; // vectors
 328         float *id_0,*id_1,*id_n;
 329         /*=============================================
 330                         ,+- - - -  _
 331                    _   / id_n   |  v_b {id_0,id_n}
 332                   v_b /            _
 333                      /          |  v_a {id_0,id_1}
 334                     /
 335                    /            |
 336                   + id_0
 337                    \
 338                   _ \           |
 339                  v_a \
 340                       \ id_1    |
 341                        "+- - - -
 342
 343          ============================================*/
 344         id_0 = theGrid->GetPoint(aIds[0]);
 345         id_1 = theGrid->GetPoint(aIds[1]);
 346         id_n = theGrid->GetPoint(aIds[numFacePts-1]);
 347
 348         for(int i=0;i<3;i++){
 349           v_a[i] = id_1[i] - id_0[i];
 350           v_b[i] = id_n[i] - id_0[i];
 351           v_convex2face[i] = id_0[i] - convex_center[i];
 352         }
 353
 354         if (vtkMath::Determinant3x3(v_a,v_b,v_convex2face) < 0){
 355           ReverseIds(aIds);
 356         }
 357
 358         for(int i=0;i<aIds.size();i++){
 359           TUIDS &acell = p2faces[aIds[i]];
 360           acell.insert(faceId);
 361         }
 362
 363         f2points[faceId] = aIds;
 364
 365       }
 366
 367       TPTOIDS face2face;
 368       GetFriends(p2faces,f2points,face2face);
 369
 370       TPTOIDS face2points;
 371
 372       // copy TCellArray::f2points to TPTOIDS::face2points
 373       for(TCellArray::iterator f2points_iter=f2points.begin();
 374           f2points_iter!=f2points.end();
 375           f2points_iter++){
 376
 377         TUIDS tmp;
 378         for(TCell::iterator points_iter=(f2points_iter->second).begin();
 379             points_iter!=(f2points_iter->second).end();
 380             points_iter++)
 381           tmp.insert(*points_iter);
 382
 383         face2points[f2points_iter->first] = tmp;
 384       } // end copy
 385
 386
 387       TPTOIDS new_face2faces; // which connected and in one plane
 388       int count=0;
 389
 390       TPTOIDS::const_iterator aF2FIter = face2face.begin();
 391       for(;aF2FIter!=face2face.end();aF2FIter++){
 392         vtkIdType f_key = aF2FIter->first;
 393         TUIDS &faces = new_face2faces[f_key];
 394         //faces.insert(f_key);
 395         TUIDS f_friends = aF2FIter->second;
 396         TUIDS::const_iterator a_friends_iter = f_friends.begin();
 397         for(;a_friends_iter!=f_friends.end();a_friends_iter++){
 398           vtkIdType friend_id = *a_friends_iter;
 399           if( IsConnectedFacesOnOnePlane(theGrid,f_key,friend_id,
 400                                         (face2points.find(f_key))->second,
 401                                         (face2points.find(friend_id))->second)){
 402             faces.insert(friend_id);
 403           } // end if
 404
 405         } // end a_friends_iter
 406       } // end aF2FIter
 407
 408       if(MYDEBUG)
 409       {
 410         TPTOIDS::const_iterator new_face2face_iter = new_face2faces.begin();
 411         cout << "Connected faces and on plane:" << endl;
 412         for(;new_face2face_iter!=new_face2faces.end();new_face2face_iter++){
 413           cout << "Group ["<<new_face2face_iter->first<<"] :";
 414           TUIDS::const_iterator new_faces_iter = (new_face2face_iter->second).begin();
 415           for(;new_faces_iter!=(new_face2face_iter->second).end();new_faces_iter++)
 416             cout << " " << *new_faces_iter ;
 417           cout << endl;
 418         }
 419       }
 420
 421       TPTOIDS output_newid2face;
 422       TCellArray output_newid2face_v2;
 423       {
 424         TUIDS already_in;
 425         TUIDS already_in_tmp;
 426         int k=0;
 427         TPTOIDS::const_iterator new_face2face_iter = new_face2faces.begin();
 428         for(;new_face2face_iter!=new_face2faces.end();new_face2face_iter++){
 429           if(already_in.find(new_face2face_iter->first) != already_in.end())
 430             continue;
 431           if(new_face2face_iter->second.size() > 1)
 432             continue;
 433
 434           TCell &tmp_v2 = output_newid2face_v2[k];
 435           tmp_v2.push_back(new_face2face_iter->first);
 436           already_in.insert(new_face2face_iter->first);
 437
 438           TUIDS::const_iterator new_faces_iter = (new_face2face_iter->second).begin();
 439           for(;new_faces_iter!=(new_face2face_iter->second).end();new_faces_iter++){
 440             if(already_in.find(*new_faces_iter) != already_in.end()) continue;
 441             already_in.insert(*new_faces_iter);
 442
 443             already_in_tmp.clear();
 444             already_in_tmp.insert(new_face2face_iter->first);
 445
 446             TUIDS &tmp = output_newid2face[k];
 447             GetAllFacesOnOnePlane(new_face2faces,*new_faces_iter,
 448                                   already_in_tmp,tmp_v2);
 449
 450             for(TUIDS::const_iterator aIter=already_in_tmp.begin();
 451                 aIter!=already_in_tmp.end();
 452                 aIter++)
 453               {
 454                 already_in.insert(*aIter);
 455                 tmp.insert(*aIter);
 456               }
 457           }
 458           k++;
 459         }
 460       }
 461
 462       if(MYDEBUG) {
 463         cout << "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
 464         {
 465           TPTOIDS::const_iterator new_face2face_iter = output_newid2face.begin();
 466           for(;new_face2face_iter!=output_newid2face.end();new_face2face_iter++){
 467             cout << "Group ["<<new_face2face_iter->first<<"] :";
 468             TUIDS::const_iterator new_faces_iter = (new_face2face_iter->second).begin();
 469             for(;new_faces_iter!=(new_face2face_iter->second).end();new_faces_iter++)
 470               cout << " " << *new_faces_iter ;
 471             cout << endl;
 472           }
 473         }
 474         cout << "++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++"<<endl;
 475         cout << "++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++"<<endl;
 476         cout << "+++++++++++++++++++++++ ++ ++ ++++++++++++++++++++++++++++"<<endl;
 477         cout << "+++++++++++++++++++++++++   ++++++++++++++++++++++++++++++"<<endl;
 478         cout << "++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++"<<endl;
 479         {
 480           TCellArray::const_iterator new_face2face_iter = output_newid2face_v2.begin();
 481           for(;new_face2face_iter!=output_newid2face_v2.end();new_face2face_iter++){
 482             cout << "Group ["<<new_face2face_iter->first<<"] :";
 483             TCell::const_iterator new_faces_iter = (new_face2face_iter->second).begin();
 484             for(;new_faces_iter!=(new_face2face_iter->second).end();new_faces_iter++)
 485               cout << " " << *new_faces_iter ;
 486             cout << endl;
 487           }
 488         }
 489       }
 490       TCellArray output_new_face2ids;
 491 //       {
 492 //      TPTOIDS::const_iterator new_face2face_iter = output_newid2face.begin();
 493 //      for(;new_face2face_iter!=output_newid2face.end();new_face2face_iter++){
 494
 495 //        vtkIdType new_faceId = new_face2face_iter->first;
 496 //        TUIDS::const_iterator new_faces_iter = (new_face2face_iter->second).begin();
 497 //        vtkIdType fId0 = *new_faces_iter;
 498 //        TCellArray::const_iterator pIds0_iter = f2points.find(fId0);
 499 //        TCell pIds0 = pIds0_iter->second;
 500 //        TCell &output = output_new_face2ids[new_faceId];
 501 //        new_faces_iter++;
 502 //        if(new_face2face_iter->second.size() > 2 ){}
 503 //        for(;new_faces_iter!=(new_face2face_iter->second).end();new_faces_iter++){
 504
 505 //          vtkIdType faceId = *new_faces_iter;
 506 //          // find how much nodes in face (f2points)
 507 //          TCellArray::const_iterator pIds_iter = f2points.find(faceId);
 508 //          TCell pIds = pIds_iter->second;
 509
 510 //          GetSumm(pIds0,pIds,output);
 511 //          pIds0 = output;
 512
 513 //        } // end new_faces_iter
 514
 515 //      } // new_face2face_iter
 516 //       }
 517
 518       {
 519         TCellArray::const_iterator new_face2face_iter = output_newid2face_v2.begin();
 520         for(;new_face2face_iter!=output_newid2face_v2.end();new_face2face_iter++){
 521
 522           vtkIdType new_faceId = new_face2face_iter->first;
 523           TCell::const_iterator new_faces_iter = (new_face2face_iter->second).begin();
 524           vtkIdType fId0 = *new_faces_iter;
 525           TCellArray::const_iterator pIds0_iter = f2points.find(fId0);
 526           TCell pIds0 = pIds0_iter->second;
 527           TCell &output = output_new_face2ids[new_faceId];
 528           new_faces_iter++;
 529           if(new_face2face_iter->second.size() == 1 ){
 530             TCellArray::const_iterator pIds_iter = f2points.find(fId0);
 531             TCell pIds = pIds_iter->second;
 532             output = pIds;
 533             continue;
 534           }
 535           for(;new_faces_iter!=(new_face2face_iter->second).end();new_faces_iter++){
 536
 537             vtkIdType faceId = *new_faces_iter;
 538             // find how much nodes in face (f2points)
 539             TCellArray::const_iterator pIds_iter = f2points.find(faceId);
 540             TCell pIds = pIds_iter->second;
 541
 542             GetSumm(pIds0,pIds,output);
 543             pIds0 = output;
 544
 545           } // end new_faces_iter
 546
 547         } // new_face2face_iter
 548       }
 549
 550       if(MYDEBUG) {
 551         cout << "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
 552         cout << "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
 553         cout << "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
 554       }
 555       outputCellArray = output_new_face2ids;//f2points;
 556     }
 557   } else {
 558     // not implemented
 559   }
 560 }
 561 }