src/ShapeAnalysis/ShapeAnalysis_FreeBounds.cxx

   1 // Created on: 1998-04-27
   2 // Created by: Roman LYGIN
   3 // Copyright (c) 1998-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 // Modified:    Thu Sep 17 12:27:58 1998
  18 // 25.12.98 pdn transmission from BRepTools_Sewing to BRepBuilderAPI_Sewing
  19 //szv#4 S4163
  20 // 11.01.00 svv #1: porting on DEC
  21
  22 #include <ShapeAnalysis_FreeBounds.ixx>
  23
  24 #include <BRep_Builder.hxx>
  25 #include <BRep_Tool.hxx>
  26 #include <BRepBuilderAPI_Sewing.hxx>
  27
  28 #include <Precision.hxx>
  29
  30 #include <TopoDS.hxx>
  31 #include <TopoDS_Vertex.hxx>
  32 #include <TopoDS_Wire.hxx>
  33 #include <TopoDS_Edge.hxx>
  34 #include <TopoDS_Iterator.hxx>
  35
  36 #include <TColStd_Array1OfBoolean.hxx>
  37 #include <TColStd_Array1OfInteger.hxx>
  38 #include <TColStd_SequenceOfInteger.hxx>
  39
  40 #include <ShapeExtend_WireData.hxx>
  41 #include <ShapeExtend_Explorer.hxx>
  42 #include <ShapeBuild_Vertex.hxx>
  43 #include <ShapeBuild_Edge.hxx>
  44 #include <ShapeAnalysis.hxx>
  45 #include <ShapeAnalysis_Edge.hxx>
  46 #include <ShapeAnalysis_Wire.hxx>
  47 #include <ShapeAnalysis_Shell.hxx>
  48
  49 #include <gp_Pnt.hxx> //ied_modif_for_compil_Nov-19-1998
  50 #include <TopExp_Explorer.hxx>
  51 #include <TopTools_MapOfShape.hxx>
  52 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  53 #include <TopoDS_Shell.hxx>
  54 #include <ShapeAnalysis_BoxBndTree.hxx>
  55 #include <NCollection_UBTreeFiller.hxx>
  56 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  57 #include <TopTools_HArray1OfShape.hxx>
  58 #include <TopExp.hxx>
  59
  60 //=======================================================================
  61 //function : ShapeAnalysis_FreeBounds
  62 //purpose  : Empty constructor
  63 //=======================================================================
  64
  65 ShapeAnalysis_FreeBounds::ShapeAnalysis_FreeBounds() {}
  66
  67 //=======================================================================
  68 //function : ShapeAnalysis_FreeBounds
  69 //purpose  :
  70 //=======================================================================
  71
  72 ShapeAnalysis_FreeBounds::ShapeAnalysis_FreeBounds(const TopoDS_Shape& shape,
  73                                                    const Standard_Real toler,
  74                                                    const Standard_Boolean splitclosed,
  75                                                    const Standard_Boolean splitopen) :
  76        myTolerance (toler), myShared (Standard_False),
  77        mySplitClosed (splitclosed), mySplitOpen (splitopen)
  78 {
  79   BRepBuilderAPI_Sewing Sew(toler, Standard_False, Standard_False);
  80   for (TopoDS_Iterator S (shape); S.More(); S.Next()) Sew.Add(S.Value());
  81   Sew.Perform();
  82   //
  83   // Extract free edges.
  84   //
  85   Standard_Integer nbedge = Sew.NbFreeEdges();
  86   Handle(TopTools_HSequenceOfShape) edges = new TopTools_HSequenceOfShape;
  87   Handle(TopTools_HSequenceOfShape) wires;
  88   TopoDS_Edge anEdge;
  89   for (Standard_Integer iedge = 1 ; iedge <= nbedge ; iedge++) {
  90     anEdge = TopoDS::Edge (Sew.FreeEdge(iedge));
  91     if ( !BRep_Tool::Degenerated(anEdge) ) edges->Append (anEdge);
  92   }
  93   //
  94   // Chainage.
  95   //
  96   ConnectEdgesToWires (edges, toler, Standard_False, wires);
  97   DispatchWires (wires, myWires, myEdges);
  98   SplitWires ();
  99
 100   return ;
 101 }
 102
 103 //=======================================================================
 104 //function : ShapeAnalysis_FreeBounds
 105 //purpose  :
 106 //=======================================================================
 107
 108 ShapeAnalysis_FreeBounds::ShapeAnalysis_FreeBounds(const TopoDS_Shape& shape,
 109                                                    const Standard_Boolean splitclosed,
 110                                                    const Standard_Boolean splitopen,
 111                                                    const Standard_Boolean checkinternaledges) :
 112        myTolerance (0.), myShared (Standard_True),
 113        mySplitClosed (splitclosed), mySplitOpen (splitopen)
 114 {
 115   TopoDS_Shell aTmpShell;
 116   BRep_Builder aB;
 117   aB.MakeShell(aTmpShell);
 118   for(TopExp_Explorer aExpFace(shape,TopAbs_FACE);aExpFace.More(); aExpFace.Next())
 119     aB.Add(aTmpShell,aExpFace.Current());
 120
 121   ShapeAnalysis_Shell sas;
 122   sas.CheckOrientedShells (aTmpShell, Standard_True, checkinternaledges);
 123
 124   if (sas.HasFreeEdges()) {
 125     ShapeExtend_Explorer see;
 126     Handle(TopTools_HSequenceOfShape) edges = see.SeqFromCompound (sas.FreeEdges(), Standard_False);
 127
 128     Handle(TopTools_HSequenceOfShape) wires;
 129     ConnectEdgesToWires (edges, Precision::Confusion(), Standard_True, wires);
 130     DispatchWires (wires, myWires, myEdges);
 131     SplitWires ();
 132   }
 133
 134
 135 }
 136
 137 //=======================================================================
 138 //function : ConnectEdgesToWires
 139 //purpose  :
 140 //=======================================================================
 141
 142  void ShapeAnalysis_FreeBounds::ConnectEdgesToWires(Handle(TopTools_HSequenceOfShape)& edges,
 143                                                     const Standard_Real toler,
 144                                                     const Standard_Boolean shared,
 145                                                     Handle(TopTools_HSequenceOfShape)& wires)
 146 {
 147   Handle(TopTools_HSequenceOfShape) iwires = new TopTools_HSequenceOfShape;
 148   BRep_Builder B;
 149
 150   Standard_Integer i; // svv #1
 151   for (i = 1; i <= edges->Length(); i++) {
 152     TopoDS_Wire wire;
 153     B.MakeWire (wire);
 154     B.Add (wire, edges->Value (i));
 155     iwires->Append (wire);
 156   }
 157
 158   ConnectWiresToWires (iwires, toler, shared, wires);
 159
 160   for (i = 1; i <= edges->Length(); i++)
 161     if (iwires->Value(i).Orientation() == TopAbs_REVERSED)
 162       edges->ChangeValue(i).Reverse();
 163 }
 164
 165 //=======================================================================
 166 //function : ConnectWiresToWires
 167 //purpose  :
 168 //=======================================================================
 169
 170  void ShapeAnalysis_FreeBounds::ConnectWiresToWires(Handle(TopTools_HSequenceOfShape)& iwires,
 171                                                     const Standard_Real toler,
 172                                                     const Standard_Boolean shared,
 173                                                     Handle(TopTools_HSequenceOfShape)& owires)
 174 {
 175   TopTools_DataMapOfShapeShape map;
 176   ConnectWiresToWires (iwires, toler, shared, owires, map);
 177 }
 178
 179 //=======================================================================
 180 //function : ConnectWiresToWires
 181 //purpose  :
 182 //=======================================================================
 183
 184  void ShapeAnalysis_FreeBounds::ConnectWiresToWires(Handle(TopTools_HSequenceOfShape)& iwires,
 185                                                     const Standard_Real toler,
 186                                                     const Standard_Boolean shared,
 187                                                     Handle(TopTools_HSequenceOfShape)& owires,
 188                                                     TopTools_DataMapOfShapeShape& vertices)
 189 {
 190   if (iwires.IsNull() || !iwires->Length()) return;
 191   Handle(TopTools_HArray1OfShape) arrwires = new TopTools_HArray1OfShape(1, iwires->Length());
 192   //amv
 193   Standard_Integer i;
 194   for (i = 1; i <= arrwires->Length(); i++)
 195     arrwires->SetValue(i, iwires->Value(i));
 196   owires = new TopTools_HSequenceOfShape;
 197   Standard_Real tolerance = Max (toler, Precision::Confusion());
 198
 199   Handle(ShapeExtend_WireData)
 200     sewd = new ShapeExtend_WireData (TopoDS::Wire (arrwires->Value (1)));
 201
 202   Handle(ShapeAnalysis_Wire) saw = new ShapeAnalysis_Wire;
 203   saw->Load (sewd);
 204   saw->SetPrecision (tolerance);
 205
 206   ShapeAnalysis_BoxBndTree aBBTree;
 207   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
 208   ShapeAnalysis_BoxBndTreeSelector aSel(arrwires, shared);
 209   aSel.LoadList(1);
 210
 211   for (Standard_Integer inbW = 2; inbW <= arrwires->Length(); inbW++){
 212     TopoDS_Wire trW = TopoDS::Wire (arrwires->Value (inbW));
 213     Bnd_Box aBox;
 214     TopoDS_Vertex trV1, trV2;
 215     ShapeAnalysis::FindBounds (trW, trV1, trV2);
 216     gp_Pnt trP1 = BRep_Tool::Pnt(trV1);
 217     gp_Pnt trP2 = BRep_Tool::Pnt(trV2);
 218     aBox.Set(trP1);
 219     aBox.Add(trP2);
 220     aBox.SetGap(tolerance);
 221     aTreeFiller.Add(inbW, aBox);
 222   }
 223
 224   aTreeFiller.Fill();
 225   Standard_Integer nsel;
 226
 227   ShapeAnalysis_Edge sae; //szv#4:S4163:12Mar99 moved
 228   Standard_Boolean done = Standard_False;
 229
 230   Standard_Boolean isUsedManifoldMode = Standard_True;
 231
 232   if((sewd->NbEdges() < 1) && (sewd->NbNonManifoldEdges() > 0))
 233   {
 234     isUsedManifoldMode = Standard_False;
 235   }
 236
 237   while (!done)
 238   {
 239     Standard_Boolean found = Standard_False, tail = Standard_False, direct = Standard_False;
 240     Standard_Integer lwire=0;
 241     aSel.SetStop();
 242     Bnd_Box FVBox, LVBox;
 243     TopoDS_Vertex Vf, Vl;
 244     Vf = isUsedManifoldMode ? sae.FirstVertex(sewd->Edge(1)) :
 245       sae.FirstVertex(sewd->NonmanifoldEdge(1));
 246     Vl = isUsedManifoldMode ? sae.LastVertex(sewd->Edge(sewd->NbEdges())) :
 247       sae.LastVertex(sewd->NonmanifoldEdge(sewd->NbNonManifoldEdges()));
 248
 249     gp_Pnt pf, pl;
 250     pf = BRep_Tool::Pnt(Vf);
 251     pl = BRep_Tool::Pnt(Vl);
 252     FVBox.Set(pf);
 253     FVBox.SetGap(tolerance);
 254     LVBox.Set(pl);
 255     LVBox.SetGap(tolerance);
 256
 257     aSel.DefineBoxes(FVBox, LVBox);
 258
 259     if (shared)
 260       aSel.DefineVertexes(Vf,Vl);
 261     else
 262     {
 263       aSel.DefinePnt(pf,pl);
 264       aSel.SetTolerance(tolerance);
 265     }
 266
 267     nsel = aBBTree.Select(aSel);
 268
 269     if (nsel != 0 && !aSel.LastCheckStatus(ShapeExtend_FAIL))
 270     {
 271       found = Standard_True;
 272       lwire = aSel.GetNb();
 273       tail    = aSel.LastCheckStatus (ShapeExtend_DONE1) ||
 274                 aSel.LastCheckStatus (ShapeExtend_DONE2);
 275       direct  = aSel.LastCheckStatus (ShapeExtend_DONE1) ||
 276                 aSel.LastCheckStatus (ShapeExtend_DONE3);
 277       aSel.LoadList(lwire);
 278     }
 279
 280     if (found)
 281     {
 282       if (!direct)
 283         arrwires->ChangeValue(lwire).Reverse();
 284
 285       TopoDS_Wire aCurW = TopoDS::Wire (arrwires->Value (lwire));
 286       Handle(ShapeExtend_WireData) acurwd = new
 287         ShapeExtend_WireData ( TopoDS::Wire (arrwires->Value (lwire)));
 288       sewd->Add (acurwd, (tail ? 0 : 1));
 289     }
 290     else
 291     {
 292       //making wire
 293       //1.providing connection (see ShapeFix_Wire::FixConnected())
 294       //Standard_Integer i; // svv #1
 295       for (/*Standard_Integer*/ i = 1; i <= saw->NbEdges(); i++)
 296       {
 297         if (saw->CheckConnected (i))
 298         {
 299           Standard_Integer n2 = i;
 300           Standard_Integer n1 = (n2 > 1 ? n2 - 1 : saw->NbEdges());
 301           TopoDS_Edge E1 = sewd->Edge(n1);
 302           TopoDS_Edge E2 = sewd->Edge(n2);
 303
 304           TopoDS_Vertex Vprev, Vfol, V; //connection vertex
 305           Vprev = sae.LastVertex (E1);
 306           Vfol = sae.FirstVertex (E2);
 307
 308           if (saw->LastCheckStatus (ShapeExtend_DONE1)) //absolutely confused
 309             V = Vprev;
 310           else {
 311             ShapeBuild_Vertex sbv;
 312             V = sbv.CombineVertex (Vprev, Vfol);
 313           }
 314           vertices.Bind (Vprev, V);
 315           vertices.Bind (Vfol, V);
 316
 317           //replace vertices to a new one
 318           ShapeBuild_Edge sbe;
 319           if (saw->NbEdges() < 2)
 320             sewd->Set (sbe.CopyReplaceVertices (E2, V, V), n2);
 321           else {
 322             sewd->Set (sbe.CopyReplaceVertices (E2, V, TopoDS_Vertex()), n2);
 323             if (!saw->LastCheckStatus (ShapeExtend_DONE1))
 324               sewd->Set (sbe.CopyReplaceVertices (E1, TopoDS_Vertex(), V), n1);
 325           }
 326         }
 327       }
 328
 329       //2.making wire
 330       TopoDS_Wire wire = sewd->Wire();
 331       if (!saw->CheckConnected (1) && saw->LastCheckStatus (ShapeExtend_OK))
 332         wire.Closed (Standard_True);
 333
 334       owires->Append (wire);
 335       sewd->Clear();
 336
 337       // Recherche de la premier edge non traitee pour un autre wire.
 338       //Searching for first edge for next wire
 339       lwire = -1;
 340       for (/*Standard_Integer*/ i = 1 ; i <= arrwires->Length() && lwire == -1; i++)
 341       {
 342         if (!aSel.ContWire(i))
 343         {
 344           lwire = i; //szv#4:S4163:12Mar99 optimized
 345         }
 346       }
 347
 348       if (lwire == -1)
 349         done = 1;
 350       else
 351       {
 352         sewd->Add (TopoDS::Wire (arrwires->Value (lwire)));
 353         aSel.LoadList(lwire);
 354       }
 355     }
 356   }
 357
 358   for ( /*Standard_Integer*/ i = 1; i <= iwires->Length(); i++)
 359   {
 360     iwires->SetValue (i, arrwires->Value(i));
 361   }
 362 }
 363
 364 static void SplitWire(const TopoDS_Wire& wire,
 365                       const Standard_Real toler,
 366                       const Standard_Boolean shared,
 367                       Handle(TopTools_HSequenceOfShape)& closed,
 368                       Handle(TopTools_HSequenceOfShape)& open)
 369 {
 370   closed = new TopTools_HSequenceOfShape;
 371   open   = new TopTools_HSequenceOfShape;
 372   Standard_Real tolerance = Max (toler, Precision::Confusion());
 373
 374   BRep_Builder B;
 375   ShapeAnalysis_Edge sae;
 376
 377   Handle(ShapeExtend_WireData) sewd = new ShapeExtend_WireData (wire);
 378   Standard_Integer nbedges = sewd->NbEdges();
 379
 380   //ConnectedEdgeSequence - list of indices of connected edges to build a wire
 381   TColStd_SequenceOfInteger ces;
 382   //statuses - array of flags describing the edge:
 383   //0-free, 1-in CES, 2-already in wire,
 384   //3-no closed wire can be produced starting at this edge
 385   TColStd_Array1OfInteger statuses (1, nbedges);
 386   statuses.Init (0);
 387
 388   //building closed wires
 389   Standard_Integer i; // svv #1
 390   for (i = 1; i <= nbedges; i++)
 391     if (statuses.Value (i) == 0) {
 392       ces.Append (i); statuses.SetValue (i, 1); //putting into CES
 393       Standard_Boolean SearchBackward = Standard_True;
 394
 395       for(;;) {
 396         Standard_Boolean found;
 397         TopoDS_Edge edge;
 398         TopoDS_Vertex lvertex;
 399         gp_Pnt lpoint;
 400
 401         //searching for connection in ces
 402         if (SearchBackward) {
 403           SearchBackward = Standard_False;
 404           found = Standard_False;
 405           edge = sewd->Edge (ces.Last());
 406           lvertex = sae.LastVertex (edge);
 407           lpoint = BRep_Tool::Pnt (lvertex);
 408           Standard_Integer j; // svv #1
 409           for (j = ces.Length(); (j >= 1) && !found; j--) {
 410             TopoDS_Vertex fv = sae.FirstVertex (sewd->Edge (ces.Value (j)) );
 411             gp_Pnt fp = BRep_Tool::Pnt (fv);
 412             if ((shared && lvertex.IsSame (fv)) ||
 413                 (!shared && lpoint.IsEqual (fp, tolerance)))
 414               found = Standard_True;
 415           }
 416
 417           if (found) {
 418             j++;//because of decreasing last iteration
 419             //making closed wire
 420             TopoDS_Wire wire1;
 421             B.MakeWire (wire1);
 422             for (Standard_Integer cesindex = j; cesindex <= ces.Length(); cesindex++) {
 423               B.Add (wire1, sewd->Edge (ces.Value (cesindex)));
 424               statuses.SetValue (ces.Value (cesindex), 2);
 425             }
 426             wire1.Closed (Standard_True);
 427             closed->Append (wire1);
 428             ces.Remove (j, ces.Length());
 429             if (ces.IsEmpty()) break;
 430           }
 431         }
 432
 433         //searching for connection among free edges
 434         found = Standard_False;
 435         edge = sewd->Edge (ces.Last());
 436         lvertex = sae.LastVertex (edge);
 437         lpoint = BRep_Tool::Pnt (lvertex);
 438         Standard_Integer j; // svv #1
 439         for (j = 1; (j <= nbedges) && !found; j++)
 440           if (statuses.Value (j) == 0) {
 441             TopoDS_Vertex fv = sae.FirstVertex (sewd->Edge (j));
 442             gp_Pnt fp = BRep_Tool::Pnt (fv);
 443             if ((shared && lvertex.IsSame (fv)) ||
 444                 (!shared && lpoint.IsEqual (fp, tolerance)))
 445               found = Standard_True;
 446           }
 447
 448         if (found) {
 449           j--;//because of last iteration
 450           ces.Append (j); statuses.SetValue (j, 1);//putting into CES
 451           SearchBackward = Standard_True;
 452           continue;
 453         }
 454
 455         //no edges found - mark the branch as open (use status 3)
 456         statuses.SetValue (ces.Last(), 3);
 457         ces.Remove (ces.Length());
 458         if (ces.IsEmpty()) break;
 459       }
 460     }
 461
 462   //building open wires
 463   Handle(TopTools_HSequenceOfShape) edges = new TopTools_HSequenceOfShape;
 464   for (i = 1; i <= nbedges; i++)
 465     if (statuses.Value (i) != 2) edges->Append (sewd->Edge(i));
 466
 467   ShapeAnalysis_FreeBounds::ConnectEdgesToWires (edges, toler, shared, open);
 468 }
 469
 470  void ShapeAnalysis_FreeBounds::SplitWires(const Handle(TopTools_HSequenceOfShape)& wires,
 471                                            const Standard_Real toler,
 472                                            const Standard_Boolean shared,
 473                                            Handle(TopTools_HSequenceOfShape)& closed,
 474                                            Handle(TopTools_HSequenceOfShape)& open)
 475 {
 476   closed = new TopTools_HSequenceOfShape;
 477   open   = new TopTools_HSequenceOfShape;
 478
 479   for (Standard_Integer i = 1; i <= wires->Length(); i++) {
 480     Handle(TopTools_HSequenceOfShape) tmpclosed, tmpopen;
 481     SplitWire (TopoDS::Wire (wires->Value (i)), toler, shared, tmpclosed, tmpopen);
 482     closed->Append (tmpclosed);
 483     open->Append (tmpopen);
 484   }
 485 }
 486
 487 //=======================================================================
 488 //function : DispatchWires
 489 //purpose  :
 490 //=======================================================================
 491
 492  void ShapeAnalysis_FreeBounds::DispatchWires(const Handle(TopTools_HSequenceOfShape)& wires,
 493                                               TopoDS_Compound& closed,
 494                                               TopoDS_Compound& open)
 495 {
 496   BRep_Builder B;
 497   if (closed.IsNull()) B.MakeCompound (closed);
 498   if (open.IsNull())  B.MakeCompound (open);
 499   if (wires.IsNull()) return;
 500
 501   for (Standard_Integer iw = 1 ; iw <= wires->Length(); iw++)
 502     if ( wires->Value (iw).Closed() )
 503       B.Add (closed, wires->Value (iw));
 504     else
 505       B.Add (open, wires->Value (iw));
 506 }
 507
 508 //=======================================================================
 509 //function : SplitWires
 510 //purpose  : Splits compounds of closed (myWires) and open (myEdges) wires
 511 //           into small closed wires according to fields mySplitClosed and
 512 //           mySplitOpen and rebuilds compounds
 513 //=======================================================================
 514
 515  void ShapeAnalysis_FreeBounds::SplitWires()
 516 {
 517   if (!mySplitClosed && !mySplitOpen) return; //nothing to do
 518
 519   ShapeExtend_Explorer see;
 520   Handle(TopTools_HSequenceOfShape) closedwires, cw1, cw2,
 521                                     openwires,   ow1, ow2;
 522   closedwires = see.SeqFromCompound (myWires, Standard_False);
 523   openwires   = see.SeqFromCompound (myEdges, Standard_False);
 524
 525   if (mySplitClosed) SplitWires (closedwires, myTolerance, myShared, cw1, ow1);
 526   else {cw1 = closedwires; ow1 = new TopTools_HSequenceOfShape;}
 527
 528   if (mySplitOpen) SplitWires (openwires, myTolerance, myShared, cw2, ow2);
 529   else {cw2 = new TopTools_HSequenceOfShape; ow2 = openwires;}
 530
 531   closedwires = cw1; closedwires->Append (cw2);
 532   openwires = ow1;   openwires->Append (ow2);
 533
 534   //szv#4:S4163:12Mar99 SGI warns
 535   TopoDS_Shape compWires = see.CompoundFromSeq (closedwires);
 536   TopoDS_Shape compEdges = see.CompoundFromSeq (openwires);
 537   myWires = TopoDS::Compound (compWires);
 538   myEdges = TopoDS::Compound (compEdges);
 539 }