src/FeaturesPlugin/FeaturesPlugin_Boolean.cpp

   1 // Copyright (C) 2014-2019  CEA/DEN, EDF R&D
   2 //
   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, or (at your option) any later version.
   7 //
   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.
  12 //
  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
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19
  20 #include "FeaturesPlugin_Boolean.h"
  21
  22 #include <ModelAPI_Data.h>
  23 #include <ModelAPI_Document.h>
  24 #include <ModelAPI_AttributeReference.h>
  25 #include <ModelAPI_AttributeInteger.h>
  26 #include <ModelAPI_ResultBody.h>
  27 #include <ModelAPI_AttributeSelectionList.h>
  28 #include <ModelAPI_Session.h>
  29 #include <ModelAPI_Validator.h>
  30 #include <ModelAPI_Tools.h>
  31
  32 #include <GeomAlgoAPI_Boolean.h>
  33 #include <GeomAlgoAPI_CompoundBuilder.h>
  34 #include <GeomAlgoAPI_MakeShapeCustom.h>
  35 #include <GeomAlgoAPI_MakeShapeList.h>
  36 #include <GeomAlgoAPI_Partition.h>
  37 #include <GeomAlgoAPI_PaveFiller.h>
  38 #include <GeomAlgoAPI_ShapeBuilder.h>
  39 #include <GeomAlgoAPI_ShapeTools.h>
  40 #include <GeomAlgoAPI_Tools.h>
  41 #include <GeomAPI_Face.h>
  42 #include <GeomAPI_ShapeExplorer.h>
  43 #include <GeomAPI_ShapeIterator.h>
  44
  45 #include <algorithm>
  46 #include <map>
  47
  48 //=================================================================================================
  49 FeaturesPlugin_Boolean::FeaturesPlugin_Boolean(const OperationType theOperationType)
  50 : myOperationType(theOperationType)
  51 {
  52 }
  53
  54 //=================================================================================================
  55 void FeaturesPlugin_Boolean::initAttributes()
  56 {
  57   AttributeSelectionListPtr aSelection =
  58     std::dynamic_pointer_cast<ModelAPI_AttributeSelectionList>(data()->addAttribute(
  59     FeaturesPlugin_Boolean::OBJECT_LIST_ID(), ModelAPI_AttributeSelectionList::typeId()));
  60
  61   aSelection = std::dynamic_pointer_cast<ModelAPI_AttributeSelectionList>(data()->addAttribute(
  62     FeaturesPlugin_Boolean::TOOL_LIST_ID(), ModelAPI_AttributeSelectionList::typeId()));
  63
  64   ModelAPI_Session::get()->validators()->registerNotObligatory(getKind(), OBJECT_LIST_ID());
  65   ModelAPI_Session::get()->validators()->registerNotObligatory(getKind(), TOOL_LIST_ID());
  66 }
  67
  68 //=================================================================================================
  69 FeaturesPlugin_Boolean::OperationType FeaturesPlugin_Boolean::operationType()
  70 {
  71   return myOperationType;
  72 }
  73
  74 //=================================================================================================
  75 void FeaturesPlugin_Boolean::parentForShape(const GeomShapePtr& theShape,
  76                                             const ResultPtr& theContext,
  77                                             ObjectHierarchy& theShapesHierarchy)
  78 {
  79   ResultBodyPtr aResCompSolidPtr = ModelAPI_Tools::bodyOwner(theContext);
  80   if (aResCompSolidPtr.get()) {
  81     std::shared_ptr<GeomAPI_Shape> aContextShape = aResCompSolidPtr->shape();
  82     if (aContextShape->shapeType() <= GeomAPI_Shape::COMPSOLID) {
  83       theShapesHierarchy.AddParent(theShape, aContextShape);
  84       parentForShape(aContextShape, aResCompSolidPtr, theShapesHierarchy);
  85     }
  86   }
  87 }
  88
  89 bool FeaturesPlugin_Boolean::processAttribute(const std::string& theAttributeName,
  90                                               ObjectHierarchy& theObjects,
  91                                               ListOfShape& thePlanesList)
  92 {
  93   AttributeSelectionListPtr anObjectsSelList = selectionList(theAttributeName);
  94   for (int anObjectsIndex = 0; anObjectsIndex < anObjectsSelList->size(); anObjectsIndex++) {
  95     AttributeSelectionPtr anObjectAttr = anObjectsSelList->value(anObjectsIndex);
  96     GeomShapePtr anObject = anObjectAttr->value();
  97     if (!anObject.get()) {
  98       // It could be a construction plane.
  99       ResultPtr aContext = anObjectAttr->context();
 100       anObject = anObjectAttr->context()->shape();
 101       if (anObject.get()) {
 102         thePlanesList.push_back(anObject);
 103         continue;
 104       } else
 105         return false;
 106     }
 107
 108     theObjects.AddObject(anObject);
 109
 110     ResultPtr aContext = anObjectAttr->context();
 111     parentForShape(anObject, aContext, theObjects);
 112   }
 113   return true;
 114 }
 115
 116 //=================================================================================================
 117 void FeaturesPlugin_Boolean::loadNamingDS(std::shared_ptr<ModelAPI_ResultBody> theResultBody,
 118                                           const std::shared_ptr<GeomAPI_Shape> theBaseShape,
 119                                           const ListOfShape& theTools,
 120                                           const std::shared_ptr<GeomAPI_Shape> theResultShape,
 121                                           const GeomMakeShapePtr& theMakeShape)
 122 {
 123   //load result
 124   if(theBaseShape->isEqual(theResultShape)) {
 125     theResultBody->store(theResultShape, false);
 126     return;
 127   }
 128
 129   theResultBody->storeModified(theBaseShape, theResultShape);
 130
 131   theResultBody->loadModifiedShapes(theMakeShape, theBaseShape, GeomAPI_Shape::EDGE);
 132   theResultBody->loadModifiedShapes(theMakeShape, theBaseShape, GeomAPI_Shape::FACE);
 133
 134   theResultBody->loadDeletedShapes(theMakeShape, theBaseShape, GeomAPI_Shape::FACE);
 135
 136   for (ListOfShape::const_iterator anIter = theTools.begin();
 137        anIter != theTools.end();
 138        ++anIter)
 139   {
 140     GeomAPI_Shape::ShapeType aShapeType =
 141       (*anIter)->shapeType() <= GeomAPI_Shape::FACE ? GeomAPI_Shape::FACE
 142                                                     : GeomAPI_Shape::EDGE;
 143     theResultBody->loadModifiedShapes(theMakeShape, *anIter, aShapeType);
 144
 145     theResultBody->loadDeletedShapes(theMakeShape, *anIter, GeomAPI_Shape::FACE);
 146   }
 147 }
 148
 149 //=================================================================================================
 150 bool FeaturesPlugin_Boolean::processObject(
 151     const GeomAlgoAPI_Tools::BOPType theBooleanType,
 152     const GeomShapePtr& theObject,
 153     const ListOfShape& theTools,
 154     const ListOfShape& thePlanes,
 155     int& theResultIndex,
 156     std::vector<FeaturesPlugin_Tools::ResultBaseAlgo>& theResultBaseAlgoList,
 157     ListOfShape& theResultShapesList)
 158 {
 159   ListOfShape aListWithObject;
 160   aListWithObject.push_back(theObject);
 161   std::shared_ptr<GeomAlgoAPI_MakeShapeList> aMakeShapeList(new GeomAlgoAPI_MakeShapeList());
 162   std::shared_ptr<GeomAlgoAPI_MakeShape> aBoolAlgo;
 163   GeomShapePtr aResShape;
 164
 165   std::list<std::shared_ptr<GeomAPI_Pnt> > aBoundingPoints =
 166       GeomAlgoAPI_ShapeTools::getBoundingBox(aListWithObject, 1.0);
 167
 168   // Resize planes.
 169   ListOfShape aToolsWithPlanes = theTools;
 170   for (ListOfShape::const_iterator anIt = thePlanes.begin(); anIt != thePlanes.end(); ++anIt) {
 171     GeomShapePtr aPlane = *anIt;
 172     GeomShapePtr aTool = GeomAlgoAPI_ShapeTools::fitPlaneToBox(aPlane, aBoundingPoints);
 173     std::shared_ptr<GeomAlgoAPI_MakeShapeCustom> aMkShCustom(
 174         new GeomAlgoAPI_MakeShapeCustom);
 175     aMkShCustom->addModified(aPlane, aTool);
 176     aMakeShapeList->appendAlgo(aMkShCustom);
 177     aToolsWithPlanes.push_back(aTool);
 178   }
 179
 180   if (theBooleanType == GeomAlgoAPI_Tools::BOOL_PARTITION)
 181     aBoolAlgo.reset(new GeomAlgoAPI_Partition(aListWithObject, aToolsWithPlanes));
 182   else
 183     aBoolAlgo.reset(new GeomAlgoAPI_Boolean(aListWithObject,
 184                                             aToolsWithPlanes,
 185                                             theBooleanType));
 186
 187   // Checking that the algorithm worked properly.
 188   std::string anError;
 189   if (GeomAlgoAPI_Tools::AlgoError::isAlgorithmFailed(aBoolAlgo, getKind(), anError)) {
 190     setError(anError);
 191     return false;
 192   }
 193
 194   aResShape = aBoolAlgo->shape();
 195   if (aResShape.get() && aResShape->shapeType() == GeomAPI_Shape::COMPOUND) {
 196     int aSubResultsNb = 0;
 197     GeomAPI_ShapeIterator anIt(aResShape);
 198     for (; anIt.more(); anIt.next())
 199       ++aSubResultsNb;
 200
 201     if (aSubResultsNb == 1) {
 202       anIt.init(aResShape);
 203       if (anIt.more())
 204         aResShape = anIt.current();
 205     }
 206   }
 207
 208   aMakeShapeList->appendAlgo(aBoolAlgo);
 209
 210   GeomAPI_ShapeIterator aShapeIt(aResShape);
 211   if (aShapeIt.more() || aResShape->shapeType() == GeomAPI_Shape::VERTEX) {
 212     std::shared_ptr<ModelAPI_ResultBody> aResultBody =
 213         document()->createBody(data(), theResultIndex);
 214
 215     // tools should be added to the list to fulfill the correct history of modification
 216     aListWithObject.insert(aListWithObject.end(), theTools.begin(), theTools.end());
 217
 218     ListOfShape aUsedTools = theTools;
 219     aUsedTools.insert(aUsedTools.end(), thePlanes.begin(), thePlanes.end());
 220
 221     FeaturesPlugin_Tools::loadModifiedShapes(aResultBody,
 222                                              aListWithObject,
 223                                              aUsedTools,
 224                                              aMakeShapeList,
 225                                              aResShape);
 226     setResult(aResultBody, theResultIndex);
 227     ++theResultIndex;
 228
 229     FeaturesPlugin_Tools::ResultBaseAlgo aRBA;
 230     aRBA.resultBody = aResultBody;
 231     aRBA.baseShape = theObject;
 232     aRBA.makeShape = aMakeShapeList;
 233     theResultBaseAlgoList.push_back(aRBA);
 234     theResultShapesList.push_back(aResShape);
 235   }
 236   return true;
 237 }
 238
 239 //=================================================================================================
 240 bool FeaturesPlugin_Boolean::processCompsolid(
 241     const GeomAlgoAPI_Tools::BOPType theBooleanType,
 242     const ObjectHierarchy& theCompsolidHierarchy,
 243     const GeomShapePtr& theCompsolid,
 244     const ListOfShape& theTools,
 245     const ListOfShape& thePlanes,
 246     int& theResultIndex,
 247     std::vector<FeaturesPlugin_Tools::ResultBaseAlgo>& theResultBaseAlgoList,
 248     ListOfShape& theResultShapesList)
 249 {
 250   ListOfShape aUsedInOperationSolids;
 251   ListOfShape aNotUsedSolids;
 252   theCompsolidHierarchy.SplitCompound(theCompsolid, aUsedInOperationSolids, aNotUsedSolids);
 253
 254   std::shared_ptr<GeomAlgoAPI_MakeShapeList> aMakeShapeList(new GeomAlgoAPI_MakeShapeList());
 255
 256   std::list<std::shared_ptr<GeomAPI_Pnt> > aBoundingPoints =
 257       GeomAlgoAPI_ShapeTools::getBoundingBox(aUsedInOperationSolids, 1.0);
 258
 259   // Resize planes.
 260   ListOfShape aToolsWithPlanes = theTools;
 261   for (ListOfShape::const_iterator anIt = thePlanes.begin(); anIt != thePlanes.end(); ++anIt)
 262   {
 263     GeomShapePtr aPlane = *anIt;
 264     GeomShapePtr aTool = GeomAlgoAPI_ShapeTools::fitPlaneToBox(aPlane, aBoundingPoints);
 265     std::shared_ptr<GeomAlgoAPI_MakeShapeCustom> aMkShCustom(
 266       new GeomAlgoAPI_MakeShapeCustom);
 267     aMkShCustom->addModified(aPlane, aTool);
 268     aMakeShapeList->appendAlgo(aMkShCustom);
 269     aToolsWithPlanes.push_back(aTool);
 270   }
 271
 272   std::shared_ptr<GeomAlgoAPI_MakeShape> aBoolAlgo;
 273   if (theBooleanType == GeomAlgoAPI_Tools::BOOL_PARTITION)
 274     aBoolAlgo.reset(new GeomAlgoAPI_Partition(aUsedInOperationSolids, aToolsWithPlanes));
 275   else
 276     aBoolAlgo.reset(new GeomAlgoAPI_Boolean(aUsedInOperationSolids,
 277                                             aToolsWithPlanes,
 278                                             theBooleanType));
 279
 280   // Checking that the algorithm worked properly.
 281   std::string anError;
 282   if (GeomAlgoAPI_Tools::AlgoError::isAlgorithmFailed(aBoolAlgo, getKind(), anError)) {
 283     setError(anError);
 284     return false;
 285   }
 286
 287   aMakeShapeList->appendAlgo(aBoolAlgo);
 288   GeomShapePtr aResultShape = aBoolAlgo->shape();
 289
 290   // Add result to not used solids from compsolid.
 291   if (!aNotUsedSolids.empty()) {
 292     ListOfShape aShapesToAdd = aNotUsedSolids;
 293     aShapesToAdd.push_back(aBoolAlgo->shape());
 294     std::shared_ptr<GeomAlgoAPI_PaveFiller> aFillerAlgo(
 295         new GeomAlgoAPI_PaveFiller(aShapesToAdd, true));
 296     if (!aFillerAlgo->isDone()) {
 297       std::string aFeatureError = "Error: PaveFiller algorithm failed.";
 298       setError(aFeatureError);
 299       return false;
 300     }
 301
 302     aMakeShapeList->appendAlgo(aFillerAlgo);
 303     aResultShape = aFillerAlgo->shape();
 304   }
 305
 306   GeomAPI_ShapeIterator aShapeIt(aResultShape);
 307   if (aShapeIt.more() || aResultShape->shapeType() == GeomAPI_Shape::VERTEX)
 308   {
 309     std::shared_ptr<ModelAPI_ResultBody> aResultBody =
 310         document()->createBody(data(), theResultIndex);
 311
 312     ListOfShape aCompSolidList;
 313     aCompSolidList.push_back(theCompsolid);
 314     // tools should be added to the list to fulfill the correct history of modification
 315     aCompSolidList.insert(aCompSolidList.end(), theTools.begin(), theTools.end());
 316
 317     ListOfShape aUsedTools = theTools;
 318     aUsedTools.insert(aUsedTools.end(), thePlanes.begin(), thePlanes.end());
 319
 320     FeaturesPlugin_Tools::loadModifiedShapes(aResultBody,
 321                                              aCompSolidList,
 322                                              aUsedTools,
 323                                              aMakeShapeList,
 324                                              aResultShape);
 325     setResult(aResultBody, theResultIndex);
 326     ++theResultIndex;
 327
 328     FeaturesPlugin_Tools::ResultBaseAlgo aRBA;
 329     aRBA.resultBody = aResultBody;
 330     aRBA.baseShape = theCompsolid;
 331     aRBA.makeShape = aMakeShapeList;
 332     theResultBaseAlgoList.push_back(aRBA);
 333     theResultShapesList.push_back(aResultShape);
 334   }
 335   return true;
 336 }
 337
 338 //=================================================================================================
 339 bool FeaturesPlugin_Boolean::processCompound(
 340     const GeomAlgoAPI_Tools::BOPType theBooleanType,
 341     const ObjectHierarchy& theCompoundHierarchy,
 342     const GeomShapePtr& theCompound,
 343     const ListOfShape& theTools,
 344     int& theResultIndex,
 345     std::vector<FeaturesPlugin_Tools::ResultBaseAlgo>& theResultBaseAlgoList,
 346     ListOfShape& theResultShapesList)
 347 {
 348   ListOfShape aUsedInOperationShapes;
 349   ListOfShape aNotUsedShapes;
 350   theCompoundHierarchy.SplitCompound(theCompound, aUsedInOperationShapes, aNotUsedShapes);
 351
 352   std::shared_ptr<GeomAlgoAPI_MakeShapeList> aMakeShapeList(new GeomAlgoAPI_MakeShapeList());
 353   std::shared_ptr<GeomAlgoAPI_Boolean> aBoolAlgo(
 354       new GeomAlgoAPI_Boolean(aUsedInOperationShapes,
 355                               theTools,
 356                               theBooleanType));
 357
 358   // Checking that the algorithm worked properly.
 359   std::string anError;
 360   if (GeomAlgoAPI_Tools::AlgoError::isAlgorithmFailed(aBoolAlgo, getKind(), anError)) {
 361     setError(anError);
 362     return false;
 363   }
 364
 365   aMakeShapeList->appendAlgo(aBoolAlgo);
 366   GeomShapePtr aResultShape = aBoolAlgo->shape();
 367
 368   // Add result to not used shape from compound.
 369   if (!aNotUsedShapes.empty()) {
 370     ListOfShape aShapesForResult = aNotUsedShapes;
 371     if (aResultShape->shapeType() == GeomAPI_Shape::COMPOUND) {
 372       for (GeomAPI_ShapeIterator aResultIt(aResultShape); aResultIt.more(); aResultIt.next()) {
 373         aShapesForResult.push_back(aResultIt.current());
 374       }
 375     }
 376     else {
 377       aShapesForResult.push_back(aResultShape);
 378     }
 379
 380     if (aShapesForResult.size() == 1) {
 381       aResultShape = aShapesForResult.front();
 382     }
 383     else {
 384       aResultShape = GeomAlgoAPI_CompoundBuilder::compound(aShapesForResult);
 385     }
 386   }
 387
 388   GeomAPI_ShapeIterator aShapeIt(aResultShape);
 389   if (aShapeIt.more() || aResultShape->shapeType() == GeomAPI_Shape::VERTEX) {
 390     std::shared_ptr<ModelAPI_ResultBody> aResultBody =
 391         document()->createBody(data(), theResultIndex);
 392
 393     ListOfShape aCompoundList;
 394     aCompoundList.push_back(theCompound);
 395     FeaturesPlugin_Tools::loadModifiedShapes(aResultBody,
 396                                              aCompoundList,
 397                                              theTools,
 398                                              aMakeShapeList,
 399                                              aResultShape);
 400     setResult(aResultBody, theResultIndex);
 401     ++theResultIndex;
 402
 403     FeaturesPlugin_Tools::ResultBaseAlgo aRBA;
 404     aRBA.resultBody = aResultBody;
 405     aRBA.baseShape = theCompound;
 406     aRBA.makeShape = aMakeShapeList;
 407     theResultBaseAlgoList.push_back(aRBA);
 408     theResultShapesList.push_back(aResultShape);
 409   }
 410   return true;
 411 }
 412
 413 //=================================================================================================
 414
 415 void FeaturesPlugin_Boolean::ObjectHierarchy::AddObject(const GeomShapePtr& theObject)
 416 {
 417   myObjects.push_back(theObject);
 418 }
 419
 420 void FeaturesPlugin_Boolean::ObjectHierarchy::AddParent(const GeomShapePtr& theShape,
 421                                                         const GeomShapePtr& theParent)
 422 {
 423   myParent[theShape] = theParent;
 424
 425   MapShapeToIndex::iterator aFound = myParentIndices.find(theParent);
 426   size_t anIndex = myParentIndices.size();
 427   if (aFound == myParentIndices.end()) {
 428     myParentIndices[theParent] = anIndex;
 429     mySubshapes.push_back(ShapeAndSubshapes(theParent, ListOfShape()));
 430   } else
 431     anIndex = aFound->second;
 432
 433   mySubshapes[anIndex].second.push_back(theShape);
 434 }
 435
 436 GeomShapePtr FeaturesPlugin_Boolean::ObjectHierarchy::Parent(const GeomShapePtr& theShape,
 437                                                              bool theMarkProcessed)
 438 {
 439   MapShapeToParent::const_iterator aFound = myParent.find(theShape);
 440   GeomShapePtr aParent;
 441   if (aFound != myParent.end()) {
 442     aParent = aFound->second;
 443     if (theMarkProcessed) {
 444       // mark the parent and all its subs as processed by Boolean algorithm
 445       myProcessedObjects.insert(aParent);
 446       const ListOfShape& aSubs = mySubshapes[myParentIndices[aParent]].second;
 447       for (ListOfShape::const_iterator anIt = aSubs.begin(); anIt != aSubs.end(); ++anIt)
 448         myProcessedObjects.insert(*anIt);
 449     }
 450   }
 451   return aParent;
 452 }
 453
 454 void FeaturesPlugin_Boolean::ObjectHierarchy::ObjectsByType(
 455     ListOfShape& theShapesByType,
 456     ListOfShape& theOtherShapes,
 457     const GeomAPI_Shape::ShapeType theMinType,
 458     const GeomAPI_Shape::ShapeType theMaxType) const
 459 {
 460   if (theMinType > theMaxType)
 461     return ObjectsByType(theShapesByType, theOtherShapes, theMaxType, theMinType);
 462
 463   // no need to select objects if whole range is specified
 464   if (theMinType == GeomAPI_Shape::COMPOUND && theMaxType == GeomAPI_Shape::SHAPE) {
 465     theShapesByType.insert(theShapesByType.end(), myObjects.begin(), myObjects.end());
 466     return;
 467   }
 468
 469   for (ListOfShape::const_iterator anIt = myObjects.begin(); anIt != myObjects.end(); ++anIt) {
 470     GeomAPI_Shape::ShapeType aType = (*anIt)->shapeType();
 471     if (aType >= theMinType && aType <= theMaxType)
 472       theShapesByType.push_back(*anIt);
 473     else
 474       theOtherShapes.push_back(*anIt);
 475   }
 476 }
 477
 478
 479 void FeaturesPlugin_Boolean::ObjectHierarchy::SplitCompound(const GeomShapePtr& theCompShape,
 480                                                             ListOfShape& theUsed,
 481                                                             ListOfShape& theNotUsed) const
 482 {
 483   theUsed.clear();
 484   theNotUsed.clear();
 485
 486   MapShapeToIndex::const_iterator aFoundIndex = myParentIndices.find(theCompShape);
 487   if (aFoundIndex == myParentIndices.end())
 488     return; // no such shape
 489
 490   const ListOfShape& aSubs = mySubshapes[aFoundIndex->second].second;
 491   SetOfShape aSubsSet;
 492   aSubsSet.insert(aSubs.begin(), aSubs.end());
 493
 494   for (GeomAPI_ShapeIterator anExp(theCompShape); anExp.more(); anExp.next()) {
 495     GeomShapePtr aCurrent = anExp.current();
 496     if (aSubsSet.find(aCurrent) == aSubsSet.end())
 497       theNotUsed.push_back(aCurrent);
 498     else
 499       theUsed.push_back(aCurrent);
 500   }
 501 }
 502
 503 bool FeaturesPlugin_Boolean::ObjectHierarchy::IsEmpty() const
 504 {
 505   return myObjects.empty();
 506 }
 507
 508 void FeaturesPlugin_Boolean::ObjectHierarchy::CompoundsOfUnusedObjects(
 509     ListOfShape& theDestination) const
 510 {
 511   SetOfShape aUsedObjects;
 512   aUsedObjects.insert(myObjects.begin(), myObjects.end());
 513
 514   for (std::vector<ShapeAndSubshapes>::const_iterator anIt = mySubshapes.begin();
 515        anIt != mySubshapes.end(); ++anIt) {
 516     MapShapeToParent::const_iterator aParent = myParent.find(anIt->first);
 517     if ((aParent == myParent.end() || !aParent->second) &&
 518          anIt->first->shapeType() ==  GeomAPI_Shape::COMPOUND) {
 519       // this is a top-level compound
 520       GeomShapePtr aCompound = collectUnusedSubs(anIt->first, aUsedObjects);
 521       // add to destination non-empty compounds only
 522       if (aCompound)
 523         theDestination.push_back(aCompound);
 524     }
 525   }
 526 }
 527
 528 GeomShapePtr FeaturesPlugin_Boolean::ObjectHierarchy::collectUnusedSubs(
 529     GeomShapePtr theTopLevelCompound,
 530     const SetOfShape& theUsed) const
 531 {
 532   GeomShapePtr aResult = theTopLevelCompound->emptyCopied();
 533   bool isResultEmpty = true;
 534
 535   for (GeomAPI_ShapeIterator aSub(theTopLevelCompound); aSub.more(); aSub.next()) {
 536     GeomShapePtr aCurrent = aSub.current();
 537     if (theUsed.find(aCurrent) != theUsed.end())
 538       continue; // already used
 539
 540     MapShapeToIndex::const_iterator aFoundIndex = myParentIndices.find(aCurrent);
 541     if (aCurrent->shapeType() > GeomAPI_Shape::COMPOUND ||
 542         aFoundIndex == myParentIndices.end()) {
 543       bool isAddShape = true;
 544       // check compsolid is fully unused in the Boolean operation
 545       if (aCurrent->shapeType() == GeomAPI_Shape::COMPSOLID) {
 546         for (GeomAPI_ShapeIterator anIt(aCurrent); isAddShape && anIt.more(); anIt.next())
 547           isAddShape = theUsed.find(anIt.current()) == theUsed.end();
 548       }
 549
 550       if (isAddShape) { // low-level shape, add it
 551         GeomAlgoAPI_ShapeBuilder::add(aResult, aCurrent);
 552         isResultEmpty = false;
 553       }
 554     } else {
 555       GeomShapePtr aCompound = collectUnusedSubs(aCurrent, theUsed);
 556       if (aCompound) {
 557         GeomAlgoAPI_ShapeBuilder::add(theTopLevelCompound, aCompound);
 558         isResultEmpty = false;
 559       }
 560     }
 561   }
 562   return isResultEmpty ? GeomShapePtr() : aResult;
 563 }
 564
 565
 566 FeaturesPlugin_Boolean::ObjectHierarchy::Iterator FeaturesPlugin_Boolean::ObjectHierarchy::Begin()
 567 {
 568   return Iterator(this);
 569 }
 570
 571 FeaturesPlugin_Boolean::ObjectHierarchy::Iterator FeaturesPlugin_Boolean::ObjectHierarchy::End()
 572 {
 573   return Iterator(this, false);
 574 }
 575
 576 FeaturesPlugin_Boolean::ObjectHierarchy::Iterator::Iterator(
 577     FeaturesPlugin_Boolean::ObjectHierarchy* theHierarchy, bool isBegin)
 578   : myHierarchy(theHierarchy)
 579 {
 580   if (isBegin) {
 581     myObject = myHierarchy->myObjects.begin();
 582     SkipAlreadyProcessed();
 583   } else
 584     myObject = myHierarchy->myObjects.end();
 585 }
 586
 587 void FeaturesPlugin_Boolean::ObjectHierarchy::Iterator::SkipAlreadyProcessed()
 588 {
 589   while (myObject != myHierarchy->myObjects.end() &&
 590          myHierarchy->myProcessedObjects.find(*myObject) != myHierarchy->myProcessedObjects.end())
 591     ++myObject;
 592 }
 593
 594 bool FeaturesPlugin_Boolean::ObjectHierarchy::Iterator::operator==(const Iterator& theOther) const
 595 {
 596   return myObject == theOther.myObject;
 597 }
 598
 599 bool FeaturesPlugin_Boolean::ObjectHierarchy::Iterator::operator!=(const Iterator& theOther) const
 600 {
 601   return !operator==(theOther);
 602 }
 603
 604 FeaturesPlugin_Boolean::ObjectHierarchy::Iterator&
 605 FeaturesPlugin_Boolean::ObjectHierarchy::Iterator::operator++()
 606 {
 607   ++myObject;
 608   SkipAlreadyProcessed();
 609   return *this;
 610 }
 611
 612 FeaturesPlugin_Boolean::ObjectHierarchy::Iterator
 613 FeaturesPlugin_Boolean::ObjectHierarchy::Iterator::operator++(int)
 614 {
 615   Iterator aCurrent;
 616   aCurrent.myHierarchy = myHierarchy;
 617   aCurrent.myObject = myObject;
 618
 619   // increase iterator
 620   operator++();
 621
 622   return aCurrent;
 623 }
 624
 625 GeomShapePtr FeaturesPlugin_Boolean::ObjectHierarchy::Iterator::operator*() const
 626 {
 627   myHierarchy->myProcessedObjects.insert(*myObject);
 628   return *myObject;
 629 }