src/lineconn2d/LineConn2d_Model.cxx

   1 // File:      LineConn2d_Model.cpp
   2 // Created:   03.08.05 21:05:54
   3 // Author:    Alexander GRIGORIEV
   4 // Copyright: Open Cascade 2005
   5
   6 #include <LineConn2dAfx.h>
   7
   8 #include <LineConn2d_Model.h>
   9 #include <LineConn2d_PathIterator.h>
  10 #include <LineConn2d_IntervalBuffer.h>
  11 #include <NCollection_UBTreeFiller.hxx>
  12 #include <Standard_ProgramError.hxx>
  13
  14 #ifdef DEB
  15 #include <stdio.h>
  16 #endif
  17
  18 //=======================================================================
  19 //function : LineConn2d_Model
  20 //purpose  : Empty constructor
  21 //=======================================================================
  22
  23 LineConn2d_Model::LineConn2d_Model ()
  24   : myAlloc       (new NCollection_IncAllocator()),
  25     myTree        (new NCollection_IncAllocator()),
  26     myTolerance   (10 * Precision::Confusion()),
  27     myPortLength  (0.),
  28     mySearchDepth (2.)
  29 {
  30   myObjects.Append (LineConn2d_Object());
  31   myConnections.Append (LineConn2d_Connection());
  32   myPorts.Append (LineConn2d_Port());
  33 }
  34
  35 //=======================================================================
  36 //function : AddObject
  37 //purpose  :
  38 //=======================================================================
  39
  40 Standard_Integer LineConn2d_Model::AddObject ()
  41 {
  42   const Standard_Integer anInd = myObjects.Length();
  43   myObjects.Append (LineConn2d_Object (myAlloc));
  44   return anInd;
  45 }
  46
  47 //=======================================================================
  48 //function : AddPort
  49 //purpose  :
  50 //=======================================================================
  51
  52 Standard_Integer LineConn2d_Model::AddPoort (const Standard_Integer iObj,
  53                                              const gp_XY&           thePnt,
  54                                              const gp_Dir2d&        theDir)
  55 {
  56   Standard_Integer aResult (0);
  57   if (iObj > 0 && iObj < myObjects.Length()) {
  58     aResult = myPorts.Length();
  59     myPorts.Append (LineConn2d_Port (myObjects(iObj), thePnt, theDir));
  60   }
  61   return aResult;
  62 }
  63
  64 //=======================================================================
  65 //function : AddConnection
  66 //purpose  :
  67 //=======================================================================
  68
  69 Standard_Integer LineConn2d_Model::AddConnection (const Standard_Integer iPort1,
  70                                                   const Standard_Integer iPort2)
  71 {
  72   Standard_Integer aResult (0);
  73   const Standard_Integer nPorts = myPorts.Length();
  74   if (iPort1 > 0 && iPort1 < nPorts &&
  75       iPort2 > 0 && iPort2 < nPorts) {
  76     aResult = myConnections.Length();
  77     myConnections.Append (LineConn2d_Connection (myAlloc,
  78                                                  iPort1,
  79                                                  iPort2));
  80   }
  81   return aResult;
  82 }
  83
  84 //=======================================================================
  85 //function : Update
  86 //purpose  :
  87 //=======================================================================
  88
  89 void LineConn2d_Model::Update ()
  90 {
  91   myTree.Clear();
  92   NCollection_UBTreeFiller <const LineConn2d_Object *, LineConn2d_Box>
  93     aTreeFiller(myTree);
  94
  95   // skipping the 0th member; update the objects and fill the tree.
  96   NCollection_Vector <LineConn2d_Object>::Iterator anIter (myObjects);
  97   for (anIter.Next(); anIter.More(); anIter.Next()) {
  98     LineConn2d_Object& anObj = anIter.ChangeValue();
  99     anObj.Update();
 100     aTreeFiller.Add (&anObj, anObj.Box());
 101   }
 102   aTreeFiller.Fill();
 103
 104   _PortLen = LineConn2d::IsSmall (myPortLength)? 2 * myTolerance : myPortLength;
 105   myTreeBox = myTree.Root().Bnd();
 106   // Update the box with all ports in the model
 107   NCollection_Vector <LineConn2d_Port>::Iterator anIterP (myPorts);
 108   for (anIterP.Next(); anIterP.More(); anIterP.Next())
 109     myTreeBox.Add (anIterP.Value().Location().XY() +
 110                    anIterP.Value().Direction().XY() * _PortLen);
 111   myTreeBox.Enlarge (myTolerance + 10 * Precision::Confusion());
 112 }
 113
 114 //=======================================================================
 115 //function : HalfPerimeter
 116 //purpose  :
 117 //=======================================================================
 118
 119 Standard_Real LineConn2d_Model::HalfPerimeter () const
 120 {
 121   const LineConn2d_Box& aBox = myTree.Root().Bnd();
 122   return 2 * (aBox.HSize().X() + aBox.HSize().Y());
 123 }
 124
 125 //=======================================================================
 126 //function : TempAlloc
 127 //purpose  :
 128 //=======================================================================
 129
 130 const Handle(NCollection_BaseAllocator)& LineConn2d_Model::TempAlloc () const
 131 {
 132   if (myTempAlloc.IsNull())
 133     ((Handle(NCollection_IncAllocator)&) myTempAlloc) =
 134       new NCollection_IncAllocator();
 135   return myTempAlloc;
 136 }
 137
 138 //=======================================================================
 139 //function : Compute
 140 //purpose  :
 141 //=======================================================================
 142
 143 Standard_Boolean LineConn2d_Model::Compute ()
 144 {
 145   Update();
 146
 147   const Standard_Integer nConn = myConnections.Length();
 148   for (Standard_Integer iConn = 1; iConn < nConn; iConn++) {
 149     LineConn2d_Connection& aConn = myConnections(iConn);
 150     const LineConn2d_Port& aPortSrc = myPorts (aConn.Port(0));
 151     const LineConn2d_Port& aPortTgt = myPorts (aConn.Port(1));
 152     // Check the ports if any of them is included into other objects
 153     if (checkPort (aPortSrc) == Standard_False ||
 154         checkPort (aPortTgt) == Standard_False)
 155       continue;
 156
 157     _PntTgt     = gp_XY (aPortTgt.Location().XY() +
 158                          _PortLen * aPortTgt.Direction().XY());
 159     _SegTgtPort = LineConn2d_Segment (aPortTgt.Location().XY(), _PntTgt);
 160
 161     // Create the root path (a short segment from the first port)
 162     LineConn2d_Path aPathRoot;
 163     LineConn2d::Orient anOrient =
 164       LineConn2d::Orientation (aPortSrc.Direction().XY());
 165     if (!LineConn2d_Path::createPath (aPathRoot, * this,
 166                                       aPortSrc.Location().XY(), anOrient,
 167                                       Standard_True))
 168       continue;
 169     if (aPathRoot.Delta().Modulus() < _PortLen)
 170       continue;
 171     aPathRoot.SetDelta (aPathRoot.Direction() * _PortLen);
 172     aPathRoot.Evaluate (_PntTgt);
 173
 174     const Standard_Integer aMaxDepthIncr =
 175       Standard_Integer (mySearchDepth * LineConn2d_Path::PriceOfBreak());
 176     const Standard_Integer anUltimateDepth = aMaxDepthIncr * 3;
 177     Standard_Integer aMaxDepth = aMaxDepthIncr;
 178
 179     // Create three branches near the beginning of the first Path.
 180     const gp_XY aPntExt = aPathRoot.Extremity();
 181     createPath (aPathRoot, aPntExt, -1);
 182     createPath (aPathRoot, aPntExt,  0);
 183     createPath (aPathRoot, aPntExt,  1);
 184
 185     // Calculation loop.
 186     Standard_Boolean isNewPath (Standard_True);
 187     Standard_Integer aMinPrice (::IntegerLast());
 188     Standard_Integer aCurPrice (::IntegerLast());
 189     const LineConn2d_Path * aMinPricedPath = 0L;
 190
 191     while (isNewPath) {
 192       isNewPath = Standard_False;
 193       // Evaluate the minimal price over all the leaves
 194       LineConn2d_PathIterator aPathIter (aPathRoot, TempAlloc());
 195       while (aPathIter.More()) {
 196         const LineConn2d_Path& aPath = aPathIter.Value();
 197         Standard_Integer aPathPrice = aPath.Price();
 198         // Correct the price for the terminating path if it makes an angle
 199         // with the port direction.
 200         if (aPath.IsComplete()) {
 201           if (LineConn2d::IsSmall (aPath.Direction() ^
 202                                    aPortTgt.Direction().XY()) == Standard_False)
 203             aPathPrice += LineConn2d_Path::PriceOfBreak();
 204         }
 205         if (aPathPrice < aCurPrice)
 206           aCurPrice = aPathPrice;
 207         if (aPath.IsComplete() && aPathPrice < aMinPrice) {
 208           aMinPrice = aPathPrice;
 209           aMinPricedPath = &aPath;
 210         }
 211         aPathIter.Next();
 212       }
 213
 214       // Create new path elements
 215       aPathIter = LineConn2d_PathIterator (aPathRoot, TempAlloc());
 216       aPathIter.SetDepthLimit (20);
 217       while (aPathIter.More()) {
 218         LineConn2d_Path& aPath = aPathIter.Value();
 219         aPathIter.Next();
 220         const Standard_Integer aPrice = aPath.Price();
 221         if (aPrice < aMinPrice && aPrice < aCurPrice + aMaxDepth &&
 222             !aPath.IsComplete ())
 223         {
 224           // Create new paths
 225           gp_XY aProjPnt;
 226           if (aPath.ProjectPoint (aProjPnt, _PntTgt)) {
 227             // The target is projected on this path. Create a NEW SUB-PATH
 228             // IN THE PROJECTION point. If this path does not reach the PntTgt,
 229             // it is abandoned (not included).
 230             if ((aProjPnt - aPath.Origin()).Modulus() > myTolerance)
 231               if (createPath (aPath, aProjPnt, 100))
 232                 isNewPath = Standard_True;
 233           }
 234           if (aPath.Limitation() >= 0) {
 235             // limitation front or right => create the NEW PATH TO THE LEFT
 236             if (createPath (aPath, aPath.Extremity(), -1))
 237               isNewPath = Standard_True;
 238           }
 239           if (aPath.Limitation() <= 0) {
 240             // limitation front or left => create the NEW PATH TO THE RIGHT
 241             if (createPath (aPath, aPath.Extremity(), 1))
 242               isNewPath = Standard_True;
 243           }
 244           // Create the outline on both sides, find the extrema
 245           gp_XY  aPathDir = aPath.Direction();
 246           NCollection_List<Standard_Real> lstOut (myTempAlloc);
 247           for (Standard_Integer iSide = -1; iSide < 2; iSide += 2) {
 248             pathOutline (lstOut, aPath, iSide);
 249             NCollection_List<Standard_Real>::Iterator anIterOut (lstOut);
 250             for (; anIterOut.More(); anIterOut.Next()) {
 251               const gp_XY aPnt = aPath.Point (anIterOut.Value());
 252               // Check against the point proximity to the path start or end
 253               if ((aPnt - aPath.Origin())    * aPathDir > myTolerance * 1.2 &&
 254                   (aPath.Extremity() - aPnt) * aPathDir > myTolerance * 1.2)
 255               {
 256                 if (createPath (aPath, aPnt, iSide))
 257                   isNewPath = Standard_True;
 258               }
 259             }
 260           } // end for(.. iSide ..)
 261         }
 262       } // end while (aPathIter)
 263       if (isNewPath == Standard_False && aMinPricedPath == 0L) {
 264         if (aMaxDepth < anUltimateDepth) {
 265           aMaxDepth += aMaxDepthIncr;
 266           isNewPath = Standard_True;
 267         }
 268       }
 269     }
 270     // Copy the result to the current Connection
 271     const LineConn2d_Path * aPath = aMinPricedPath;
 272     if (aPath) {
 273       aConn.ClearSegments();
 274       gp_XY aPathPoint = aPath->Extremity();
 275       aConn.AddSegment (LineConn2d_Segment (aPathPoint,
 276                                             aPortTgt.Location().XY()));
 277       for (; aPath; aPath = &aPath -> Parent()) {
 278         aConn.PrependSegment (LineConn2d_Segment (aPath->Origin(), aPathPoint));
 279         aPathPoint = aPath->Origin();
 280       }
 281     }
 282     myTempAlloc.Nullify();      // clear the temporary data storage
 283   }
 284   return Standard_True;     // OK
 285 }
 286
 287 //=======================================================================
 288 //function : pathOutline
 289 //purpose  : Find the maximal points on the model outline on the given
 290 //           side of the current path
 291 //=======================================================================
 292
 293 void LineConn2d_Model::pathOutline (NCollection_List<Standard_Real>& outList,
 294                                     const LineConn2d_Path            thePath,
 295                                     const Standard_Integer           theSide)
 296 {
 297   const gp_XY aModelSize = 2 * Box().HSize();
 298   const Standard_Real aConf (Precision::Confusion());
 299   gp_XY aPntExtr = thePath.Extremity();
 300   Standard_Real aRelTol (0.);
 301
 302   // Create the box for the transversal band covering the whole length
 303   // of the path
 304   LineConn2d_Box anOutBox;
 305   const gp_XY aCenterPath = (thePath.Origin() + aPntExtr) * 0.5;
 306   switch (thePath.Orientation()) {
 307     case LineConn2d::E:
 308       anOutBox = LineConn2d_Box (aCenterPath
 309                                  + gp_XY (0., -theSide * aModelSize.Y()),
 310                                  gp_XY (thePath.Delta().X() * 0.5 + aConf,
 311                                         aModelSize.Y()));
 312       aRelTol = myTolerance / thePath.Delta().X();
 313       break;
 314     case LineConn2d::W:
 315       anOutBox = LineConn2d_Box (aCenterPath
 316                                  + gp_XY (0., theSide * aModelSize.Y()),
 317                                  gp_XY (-thePath.Delta().X() * 0.5 + aConf,
 318                                         aModelSize.Y()));
 319       aRelTol = -myTolerance / thePath.Delta().X();
 320       break;
 321     case LineConn2d::N:
 322       anOutBox = LineConn2d_Box (aCenterPath
 323                                  + gp_XY (theSide * aModelSize.X(), 0.),
 324                                  gp_XY (aModelSize.X(),
 325                                         thePath.Delta().Y() * 0.5 + aConf));
 326       aRelTol = myTolerance / thePath.Delta().Y();
 327       break;
 328     case LineConn2d::S:
 329       anOutBox = LineConn2d_Box (aCenterPath
 330                                  + gp_XY (-theSide * aModelSize.X(), 0.),
 331                                  gp_XY (aModelSize.X(),
 332                                         -thePath.Delta().Y() * 0.5 + aConf));
 333       aRelTol = -myTolerance / thePath.Delta().Y();
 334       break;
 335   }
 336
 337   // Create the interval buffer and add there the baseline
 338   LineConn2d_IntervalBuffer aZBuffer (myTempAlloc);
 339   aZBuffer.Add (LineConn2d_ZInterval (-::RealLast(), 0., 1.));
 340
 341   // Select and iterate the boxes for model objects
 342   LineConn2d_BoxTreeSelector aSelBox (anOutBox);
 343   myTree.Select (aSelBox);
 344   NCollection_List<const LineConn2d_Object *>::Iterator
 345     aSelBoxIter (aSelBox.GetObjects());
 346   for (; aSelBoxIter.More(); aSelBoxIter.Next()) {
 347     const LineConn2d_Box& aBox = aSelBoxIter.Value() -> Box();
 348     // X[0] - coordinate of box start (normalized and relative to the path)
 349     // X[1] - coordinate of box start (normalized and relative to the path)
 350     // X[2] - Z-coordinate to be stored in Z-buffer
 351     //        (nearest to the path is the greatest)
 352     Standard_Real anX[3];
 353     switch (thePath.Orientation()) {
 354     case LineConn2d::E:
 355       anX[0] = (aBox.Center().X() - aBox.HSize().X()
 356                 - thePath.Origin().X()) / thePath.Delta().X();
 357       anX[1] = (aBox.Center().X() + aBox.HSize().X()
 358                 - thePath.Origin().X()) / thePath.Delta().X();
 359       anX[2] = theSide * aBox.Center().Y() + aBox.HSize().Y();
 360       break;
 361     case LineConn2d::N:
 362       anX[0] = (aBox.Center().Y() - aBox.HSize().Y()
 363                 - thePath.Origin().Y()) / thePath.Delta().Y();
 364       anX[1] = (aBox.Center().Y() + aBox.HSize().Y()
 365                 - thePath.Origin().Y()) / thePath.Delta().Y();
 366       anX[2] = -theSide * aBox.Center().X() + aBox.HSize().X();
 367       break;
 368     case LineConn2d::W:
 369       anX[0] = (aBox.Center().X() + aBox.HSize().X()
 370                  - thePath.Origin().X()) / thePath.Delta().X();
 371       anX[1] = (aBox.Center().X() - aBox.HSize().X()
 372                  - thePath.Origin().X()) / thePath.Delta().X();
 373       anX[2] = -theSide * aBox.Center().Y() + aBox.HSize().Y();
 374       break;
 375     case LineConn2d::S:
 376       anX[0] = (aBox.Center().Y() + aBox.HSize().Y()
 377                  - thePath.Origin().Y()) / thePath.Delta().Y();
 378       anX[1] = (aBox.Center().Y() - aBox.HSize().Y()
 379                   - thePath.Origin().Y()) / thePath.Delta().Y();
 380       anX[2] = theSide * aBox.Center().X() + aBox.HSize().X();
 381       break;
 382     default:
 383       continue;
 384     }
 385     // Assertion check
 386     if (aRelTol < Precision::Confusion() || anX[1] < anX[0])
 387       Standard_ProgramError::Raise (__FILE__);
 388     if (anX[0] < 0.) anX[0] = 0.;
 389     if (anX[1] > 1.) anX[1] = 1.;
 390     if (anX[1] - anX[0] < aRelTol)
 391       continue;
 392
 393     aZBuffer.Add (LineConn2d_ZInterval (anX[2], anX[0], anX[1]));
 394   } // end iteration on the model selected boxes
 395   aZBuffer.CheckBuffer();
 396   aZBuffer.GetMinima (outList, aRelTol);
 397
 398 //      filebuf aFileBuf;
 399 //      if (aFileBuf.open("LineConn2d_Path.trace", ios::out|ios::app))
 400 //        aZBuffer.Dump (ostream(&aFileBuf), aRelTol);
 401 //      aFileBuf.close();
 402 }
 403
 404 //=======================================================================
 405 //function : createPath
 406 //purpose  :
 407 //=======================================================================
 408
 409 Standard_Boolean LineConn2d_Model::createPath
 410                                 (LineConn2d_Path&         thePath,
 411                                  const gp_XY&             theStart,
 412                                  const Standard_Integer   iSide) const
 413 {
 414   // Compute the orientation for the new path, taking into account the Side
 415   LineConn2d::Orient anOrient;
 416   Standard_Boolean isSearchTerm (Standard_False);
 417   if (iSide > -2 && iSide < 2)
 418     anOrient = thePath.Orientation (iSide);
 419   else {
 420     // the orientation is not on the side, it is directed to the target
 421     isSearchTerm = Standard_True;
 422     anOrient = LineConn2d::Orientation (_PntTgt - theStart);
 423   }
 424
 425   LineConn2d_Path aNewPath;
 426   const Standard_Boolean aResult =
 427     LineConn2d_Path::createPath (aNewPath, * this, theStart, anOrient,
 428                                  Standard_False);
 429   if (aResult) {
 430     gp_XY aProjPnt;
 431     if (aNewPath.ProjectPoint (aProjPnt, _PntTgt))
 432       if ((aProjPnt - _PntTgt).SquareModulus() < Precision::Confusion())
 433         aNewPath.SetExtremity (aProjPnt);
 434       else {
 435         if (isSearchTerm)
 436           return Standard_False;
 437         // Check that the created path does not intersect the target port
 438         // segment; if so, abandon the path.
 439         Standard_Real bidAlpha[2];
 440         if (_SegTgtPort.IsIntersect (aNewPath, bidAlpha))
 441           return Standard_False;
 442       }
 443     thePath.AddBranch (aNewPath, _PntTgt);
 444
 445 #ifdef DEBB
 446     static FILE * ff = NULL;
 447     static int ccc = 0;
 448     ff = fopen ("LineConn2d_Path.trace",ff ? "at" : "wt");
 449
 450     const gp_XY anExtr = aNewPath.Extremity();
 451     const LineConn2d_Path * aPath = &thePath;
 452     Standard_Integer aDepth (0);
 453     for (; aPath; aPath = &aPath->Parent())
 454       aDepth++;
 455     const gp_XY anExP = thePath.Extremity();
 456
 457     fprintf (ff, "2dprofile pp%d F %.7g %.7g TT %.7g %.7g W # %c%5d\n",
 458              ++ccc ,aNewPath.Origin().X(),aNewPath.Origin().Y(),
 459              anExtr.X(),anExtr.Y(), aNewPath.IsComplete() ? 'C' : '.',
 460              aNewPath.Price());
 461 //  fprintf (ff,
 462 //           "=> (%6.1f %6.1f) - (%6.1f %6.1f), Lim %3d, Depth %3d, Price%4d\n",
 463 //           aNewPath.Origin().X(),aNewPath.Origin().Y(),anExtr.X(),anExtr.Y(),
 464 //           aNewPath.Limitation(), aDepth, aNewPath.Price());
 465
 466 //  fprintf (ff,
 467 //           "   [%6.1f %6.1f] - [%6.1f %6.1f], Lim %3d, Price%4d\n",
 468 //           thePath.Origin().X(), thePath.Origin().Y(), anExP.X(),anExP.Y(),
 469 //           thePath.Limitation(), thePath.Price());
 470
 471     fclose (ff);
 472 #endif
 473   }
 474   return aResult;
 475 }
 476
 477 //=======================================================================
 478 //function : checkPort
 479 //purpose  :
 480 //=======================================================================
 481
 482 Standard_Boolean LineConn2d_Model::checkPort
 483                         (const LineConn2d_Port& thePort) const
 484 {
 485   Standard_Boolean aResult (Standard_True);
 486   const gp_XY aPnt [2] = {
 487     thePort.Location().XY(),
 488     thePort.Location().XY() + _PortLen * thePort.Direction().XY()
 489   };
 490
 491   for (Standard_Integer i = 1; i < myObjects.Length(); i++) {
 492     const LineConn2d_Object& anObj = myObjects(i);
 493     if (&anObj == &thePort.Object())    // skip checking the self
 494       continue;
 495     if (anObj.IsOut (aPnt[1], myTolerance) == Standard_False) {
 496       aResult = Standard_False;
 497       break;
 498     }
 499   }
 500   return aResult;
 501 }