src/BOPTools/BOPTools_RoughShapeIntersector.cxx

   1 // Copyright (c) 1999-2012 OPEN CASCADE SAS
   2 //
   3 // The content of this file is subject to the Open CASCADE Technology Public
   4 // License Version 6.5 (the "License"). You may not use the content of this file
   5 // except in compliance with the License. Please obtain a copy of the License
   6 // at http://www.opencascade.org and read it completely before using this file.
   7 //
   8 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
   9 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  10 //
  11 // The Original Code and all software distributed under the License is
  12 // distributed on an "AS IS" basis, without warranty of any kind, and the
  13 // Initial Developer hereby disclaims all such warranties, including without
  14 // limitation, any warranties of merchantability, fitness for a particular
  15 // purpose or non-infringement. Please see the License for the specific terms
  16 // and conditions governing the rights and limitations under the License.
  17
  18 #include <BOPTools_RoughShapeIntersector.ixx>
  19
  20 #include <TopExp_Explorer.hxx>
  21 #include <TColStd_MapOfInteger.hxx>
  22 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  23 #include <TColStd_Array1OfListOfInteger.hxx>
  24 #include <BooleanOperations_ShapesDataStructure.hxx>
  25 #include <Bnd_Box.hxx>
  26
  27 static Standard_Integer TypeToIndex(const TopAbs_ShapeEnum& theType);
  28
  29 static Bnd_Box GetBoxEnlargedBySubShape(const Standard_Integer                        theIndex,
  30                                         const BooleanOperations_PShapesDataStructure& PDS);
  31
  32
  33 // =============================================================================================
  34 // function: Constructor
  35 // =============================================================================================
  36   BOPTools_RoughShapeIntersector::BOPTools_RoughShapeIntersector(const BooleanOperations_PShapesDataStructure& PDS)
  37 :
  38   myIsDone(Standard_False)
  39 {
  40   myPDS = PDS;
  41 }
  42
  43 // =============================================================================================
  44 // function: Perform
  45 // =============================================================================================
  46   void BOPTools_RoughShapeIntersector::Perform()
  47 {
  48   myIsDone = Standard_True;
  49
  50   Prepare();
  51
  52   // check flag myIsDone after Prepare() function
  53   if(!myIsDone)
  54     return;
  55   TColStd_ListOfInteger thelist;
  56   TColStd_Array1OfListOfInteger aSortedByTypeShapes1(TypeToIndex(TopAbs_COMPOUND), TypeToIndex(TopAbs_VERTEX));
  57   aSortedByTypeShapes1.Init(thelist);
  58
  59   TColStd_ListOfInteger thelist1;
  60   TColStd_Array1OfListOfInteger aSortedByTypeShapes2(TypeToIndex(TopAbs_COMPOUND), TypeToIndex(TopAbs_VERTEX));
  61   aSortedByTypeShapes2.Init(thelist1);
  62
  63   Standard_Integer k = 0;
  64
  65   for(k = myTableOfStatus->LowerRow(); k <= myTableOfStatus->UpperRow(); k++) {
  66     aSortedByTypeShapes1(TypeToIndex(myPDS->GetShapeType(k))).Append(k);
  67   }
  68
  69   for(k = myTableOfStatus->LowerCol(); k <= myTableOfStatus->UpperCol(); k++) {
  70     aSortedByTypeShapes2(TypeToIndex(myPDS->GetShapeType(k))).Append(k);
  71   }
  72
  73   //
  74   Standard_Integer aStartIndex = TypeToIndex(TopAbs_COMPOUND);
  75   Standard_Integer anEndIndex = TypeToIndex(TopAbs_VERTEX);
  76
  77   for(Standard_Integer index1 = aStartIndex; index1 <= anEndIndex; index1++) {
  78   //
  79     if(aSortedByTypeShapes1(index1).IsEmpty())
  80         continue;
  81
  82     for(Standard_Integer index2 = aStartIndex; index2 <= anEndIndex; index2++) {
  83       if(aSortedByTypeShapes2(index2).IsEmpty())
  84         continue;
  85
  86       TColStd_ListIteratorOfListOfInteger anIt1;
  87       TColStd_ListIteratorOfListOfInteger anIt2;
  88
  89       for(anIt1.Initialize(aSortedByTypeShapes1.Value(index1)); anIt1.More(); anIt1.Next()) {
  90         for(anIt2.Initialize(aSortedByTypeShapes2.Value(index2)); anIt2.More(); anIt2.Next()) {
  91
  92           //
  93           BOPTools_IntersectionStatus aStatus = myTableOfStatus->Value(anIt1.Value(), anIt2.Value());
  94
  95           if(aStatus != BOPTools_UNKNOWN && aStatus != BOPTools_BOUNDINGBOXOFSUBSHAPESINTERSECTED)
  96             continue;
  97
  98           const Bnd_Box& B1 = myBoundingBoxes->Value(anIt1.Value());
  99           const Bnd_Box& B2 = myBoundingBoxes->Value(anIt2.Value());
 100           //
 101           BOPTools_IntersectionStatus aNewValue = BOPTools_BOUNDINGBOXINTERSECTED;
 102
 103           if(B1.IsOut(B2)) {
 104             aNewValue = BOPTools_NONINTERSECTED;
 105             //
 106             PropagateForSuccessors1(anIt1.Value(), anIt2.Value(), aNewValue);
 107             //
 108           }
 109           else {
 110             aNewValue = BOPTools_BOUNDINGBOXINTERSECTED;
 111             const Bnd_Box& BB1 = myPDS->GetBoundingBox(anIt1.Value());
 112             const Bnd_Box& BB2 = myPDS->GetBoundingBox(anIt2.Value());
 113
 114             if(BB1.IsOut(BB2)) {
 115               aNewValue = BOPTools_BOUNDINGBOXOFSUBSHAPESINTERSECTED;
 116             }
 117           }
 118           // It is important to place this line after Propagation
 119           myTableOfStatus->ChangeValue(anIt1.Value(), anIt2.Value()) = aNewValue;
 120         }
 121       }
 122     }
 123   }
 124 }
 125
 126 // =============================================================================================
 127 // function: TableOfStatus
 128 // =============================================================================================
 129 const Handle(BOPTools_HArray2OfIntersectionStatus)& BOPTools_RoughShapeIntersector::TableOfStatus() const
 130 {
 131   return myTableOfStatus;
 132 }
 133
 134 // =============================================================================================
 135 // function: Prepare
 136 // =============================================================================================
 137 void BOPTools_RoughShapeIntersector::Prepare()
 138 {
 139   myIsDone = Standard_False;
 140
 141   if(!myTableOfStatus.IsNull() &&
 142      (myPDS != NULL) &&
 143      (myTableOfStatus->LowerRow() == 1) &&
 144      (myTableOfStatus->UpperRow() == myPDS->NumberOfShapesOfTheObject()) &&
 145      (myTableOfStatus->LowerCol() == myPDS->NumberOfShapesOfTheObject() + 1) &&
 146      (myTableOfStatus->UpperCol() == myPDS->NumberOfShapesOfTheObject() + myPDS->NumberOfShapesOfTheTool())) {
 147     myIsDone = Standard_True;
 148   }
 149   else {
 150     if(myPDS != NULL) {
 151       Standard_Integer firstlowerindex = 1;
 152       Standard_Integer firstupperindex = myPDS->NumberOfShapesOfTheObject();
 153       Standard_Integer secondlowerindex = myPDS->NumberOfShapesOfTheObject() + 1;
 154       Standard_Integer secondupperindex = myPDS->NumberOfShapesOfTheTool() + myPDS->NumberOfShapesOfTheObject();
 155       myTableOfStatus = new BOPTools_HArray2OfIntersectionStatus(firstlowerindex, firstupperindex,
 156                                                                  secondlowerindex, secondupperindex);
 157       myIsDone = Standard_True;
 158     }
 159   }
 160   if(!myIsDone)
 161     return;
 162
 163   myTableOfStatus->Init(BOPTools_UNKNOWN);
 164   //
 165   myBoundingBoxes = new Bnd_HArray1OfBox(1, myPDS->NumberOfSourceShapes());
 166
 167   for(Standard_Integer i = 1; i <= myPDS->NumberOfSourceShapes(); i++) {
 168     const Bnd_Box& aBox = GetBoxEnlargedBySubShape(i, myPDS);
 169     myBoundingBoxes->SetValue(i, aBox);
 170   }
 171 }
 172
 173 // =============================================================================================
 174 // function: IsDone
 175 // =============================================================================================
 176   Standard_Boolean BOPTools_RoughShapeIntersector::IsDone() const
 177 {
 178   return myIsDone;
 179 }
 180
 181 // =============================================================================================
 182 // function: PropagateForSuccessors1
 183 // =============================================================================================
 184 void BOPTools_RoughShapeIntersector::PropagateForSuccessors1(const Standard_Integer            AncestorsIndex1,
 185                                                              const Standard_Integer            AncestorsIndex2,
 186                                                              const BOPTools_IntersectionStatus theStatus)
 187 {
 188   if(myTableOfStatus->Value(AncestorsIndex1, AncestorsIndex2) != BOPTools_UNKNOWN)
 189     return;
 190
 191   myTableOfStatus->ChangeValue(AncestorsIndex1, AncestorsIndex2) = theStatus;
 192
 193   PropagateForSuccessors2(AncestorsIndex1, AncestorsIndex2, theStatus);
 194   Standard_Integer i = 1;
 195
 196   for(i = 1; i <= myPDS->NumberOfSuccessors(AncestorsIndex1); i++) {
 197     Standard_Integer asuccessor1 = myPDS->GetSuccessor(AncestorsIndex1, i);
 198     PropagateForSuccessors1(asuccessor1, AncestorsIndex2, theStatus);
 199   }
 200 }
 201
 202 // =============================================================================================
 203 // function: PropagateForSuccessors2
 204 // =============================================================================================
 205 void BOPTools_RoughShapeIntersector::PropagateForSuccessors2(const Standard_Integer            AncestorsIndex1,
 206                                                              const Standard_Integer            AncestorsIndex2,
 207                                                              const BOPTools_IntersectionStatus theStatus)
 208 {
 209   for(Standard_Integer j = 1; j <= myPDS->NumberOfSuccessors(AncestorsIndex2); j++) {
 210     Standard_Integer asuccessor2 = myPDS->GetSuccessor(AncestorsIndex2, j);
 211
 212     if(myTableOfStatus->Value(AncestorsIndex1, asuccessor2) == BOPTools_UNKNOWN) {
 213       myTableOfStatus->ChangeValue(AncestorsIndex1, asuccessor2) = theStatus;
 214
 215       PropagateForSuccessors2(AncestorsIndex1, asuccessor2, theStatus);
 216     }
 217   }
 218 }
 219
 220 // =============================================================================================
 221 // function: TypeToIndex
 222 // =============================================================================================
 223  Standard_Integer TypeToIndex(const TopAbs_ShapeEnum& theType) {
 224   return (Standard_Integer) theType;
 225 }
 226
 227 // =============================================================================================
 228 // function: GetBoxEnlargedBySubShape
 229 // =============================================================================================
 230 Bnd_Box GetBoxEnlargedBySubShape(const Standard_Integer                        theIndex,
 231                                  const BooleanOperations_PShapesDataStructure& PDS) {
 232   Bnd_Box aBox = PDS->GetBoundingBox(theIndex);
 233
 234   for(Standard_Integer i=1; i<= PDS->NumberOfSuccessors(theIndex); i++) {
 235     Standard_Integer asuccessorindex = PDS->GetSuccessor(theIndex, i);
 236     aBox.Add(GetBoxEnlargedBySubShape(asuccessorindex, PDS));
 237   }
 238   return aBox;
 239 }