OCCT

// Created on: 2009-10-22
// Created by: Mikhail SAZONOV
// Copyright (c) 2009-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#include <Poly_MakeLoops.hxx>
#include <NCollection_IncAllocator.hxx>
#include <NCollection_DataMap.hxx>
#include <gp_Dir.hxx>
#include <gp_Dir2d.hxx>

#ifdef OCCT_DEBUG
static int doDebug = 0;
#endif

//=================================================================================================

Poly_MakeLoops::Poly_MakeLoops(const Helper*                                 theHelper,
                               const occ::handle<NCollection_BaseAllocator>& theAlloc)
    : myHelper(theHelper),
      myAlloc(theAlloc),
      myMapLink(4000, myAlloc),
      myLoops(myAlloc),
      myStartIndices(4000)
{
}

//=================================================================================================

void Poly_MakeLoops::Reset(const Helper*                                 theHelper,
                           const occ::handle<NCollection_BaseAllocator>& theAlloc)
{
  myHelper = theHelper;
  myMapLink.Clear();
  myLoops.Clear(theAlloc);
  myStartIndices.Clear();
  myAlloc = theAlloc;
}

//=================================================================================================

void Poly_MakeLoops::AddLink(const Link& theLink)
{
  if (theLink.node1 == theLink.node2)
  {
    return;
  }
  int   aInd  = myMapLink.Add(theLink);
  Link& aLink = const_cast<Link&>(myMapLink(aInd));
  aLink.flags |= theLink.flags;
#ifdef OCCT_DEBUG
  myHelper->OnAddLink(aInd, aLink);
#endif
}

//=================================================================================================

void Poly_MakeLoops::ReplaceLink(const Link& theLink, const Link& theNewLink)
{
  if (theNewLink.node1 == theNewLink.node2)
  {
    return;
  }
  int aInd = myMapLink.Add(theLink);
  if (aInd > 0)
  {
    Link aLink;
    // replace with a null link first (workaround exception)
    myMapLink.Substitute(aInd, aLink);
    aLink = theNewLink;
    // and now put there the final value of link
    myMapLink.Substitute(aInd, aLink);
#ifdef OCCT_DEBUG
    myHelper->OnAddLink(aInd, aLink);
#endif
  }
}

//=================================================================================================

Poly_MakeLoops::LinkFlag Poly_MakeLoops::SetLinkOrientation(const Link&    theLink,
                                                            const LinkFlag theOrient)
{
  int      aInd = myMapLink.FindIndex(theLink);
  LinkFlag aOri = LF_None;
  if (aInd > 0)
  {
    Link& aLink = const_cast<Link&>(myMapLink(aInd));
    aOri        = (LinkFlag)(aLink.flags & LF_Both);
    aLink.flags = theOrient;
#ifdef OCCT_DEBUG
    myHelper->OnAddLink(aInd, aLink);
#endif
  }
  return aOri;
}

//=================================================================================================

Poly_MakeLoops::Link Poly_MakeLoops::FindLink(const Link& theLink) const
{
  int                  aInd = myMapLink.FindIndex(theLink);
  Poly_MakeLoops::Link aLink;
  if (aInd > 0)
  {
    aLink = myMapLink(aInd);
  }
  return aLink;
}

//=================================================================================================

int Poly_MakeLoops::Perform()
{
  // prepare the set of start indices
  myStartIndices.Clear();
  int i;
  for (i = 1; i <= myMapLink.Extent(); i++)
  {
    const Link& aLink = myMapLink(i);
    if (aLink.flags & LF_Fwd)
    {
      myStartIndices.Add(i);
    }
    if (aLink.flags & LF_Rev)
    {
      myStartIndices.Add(-i);
    }
  }

#ifdef OCCT_DEBUG
  if (doDebug)
    showBoundaryBreaks();
  int aNbLoopsOnPass2 = 0;
#endif

  int aResult = 0;

  occ::handle<NCollection_IncAllocator> aTempAlloc  = new NCollection_IncAllocator(4000);
  occ::handle<NCollection_IncAllocator> aTempAlloc1 = new NCollection_IncAllocator(4000);

  // two pass loop
  for (int aPassNum = 0; aPassNum < 2; aPassNum++)
  {
    myHangIndices.Clear();
    // main loop
    while (!myStartIndices.IsEmpty())
    {
      int aIndexS = myStartIndices.Top();

      aTempAlloc->Reset(false);
      NCollection_IndexedMap<int> aContour(100, aTempAlloc);
      int aStartNumber = findContour(aIndexS, aContour, aTempAlloc, aTempAlloc1);
#ifdef OCCT_DEBUG
      if (aStartNumber > 1)
        if (doDebug)
        {
          std::cout << "--- found contour with hanging links:" << std::endl;
          for (i = 1; i <= aContour.Extent(); i++)
            std::cout << " " << aContour(i);
          std::cout << std::endl;
        }
#endif
      if (aStartNumber == 0)
      { // error
        aResult |= RC_Failure;
        return aResult;
      }
      if (aStartNumber <= aContour.Extent())
      {
        // there is a closed loop in the contour
#ifdef OCCT_DEBUG
        if (aPassNum == 1)
          aNbLoopsOnPass2++;
#endif
        acceptContour(aContour, aStartNumber);
      }
      if (aStartNumber > 1)
      {
        // it is required to mark hanging edges
        int aNode;
        if (aStartNumber <= aContour.Extent())
        {
          // mark hanging edges starting from the first one till a bifurcation
          aNode = getFirstNode(aIndexS);
        }
        else
        {
          // open contour - mark from the end back till a bifurcation
          aIndexS = aContour(aStartNumber - 1);
          aNode   = getLastNode(aIndexS);
        }
        markHangChain(aNode, aIndexS);
      }
    }

    if (aPassNum == 0)
    {
      // move hanging links to start indices to make the second pass
      TColStd_PackedMapOfInteger::Iterator it(myHangIndices);
      for (; it.More(); it.Next())
      {
        myStartIndices.Add(it.Key());
      }
    }
  }
#ifdef OCCT_DEBUG
  if (doDebug && aNbLoopsOnPass2)
    std::cout << "MakeLoops: " << aNbLoopsOnPass2 << " contours accepted on the second pass"
              << std::endl;
#endif

  if (!myLoops.IsEmpty())
  {
    aResult |= RC_LoopsDone;
  }
  if (!myHangIndices.IsEmpty())
  {
    aResult |= RC_HangingLinks;
  }
  return aResult;
}

//=======================================================================
// function : findContour
// purpose  : Collects edges in chain until they form a closed contour.
// Returns the index in the map theContour where the loop starts.
// It may return the number greater than the extent of the map by 1,
// what means that the contour is open
//=======================================================================

int Poly_MakeLoops::findContour(int                                           theIndexS,
                                NCollection_IndexedMap<int>&                  theContour,
                                const occ::handle<NCollection_BaseAllocator>& theTempAlloc,
                                const occ::handle<NCollection_IncAllocator>&  theTempAlloc1) const
{
  theContour.Clear();
  int                           aStartIndex = 0;
  int                           aIndexS     = theIndexS;
  NCollection_DataMap<int, int> aNodeLink(100, theTempAlloc);
  int                           aLastNode = getLastNode(aIndexS);

  for (;;)
  {
    theContour.Add(aIndexS);
    aNodeLink.Bind(getFirstNode(aIndexS), aIndexS);

    int aIndex = std::abs(aIndexS);

    // collect the list of links from this node able to participate
    // in this contour
    theTempAlloc1->Reset(false);
    NCollection_List<int>                aLstIndS(theTempAlloc1);
    const ListOfLink&                    aLinks = myHelper->GetAdjacentLinks(aLastNode);
    Poly_MakeLoops::ListOfLink::Iterator itLinks(aLinks);
    for (; itLinks.More(); itLinks.Next())
    {
      int aInd = myMapLink.FindIndex(itLinks.Value());
      if (aInd == 0 || aInd == aIndex)
      {
        continue;
      }
      // determine the orientation in which the link is to be taken
      int aIndS  = aInd;
      int aNode1 = getFirstNode(aInd);
      if (aNode1 != aLastNode)
      {
        aIndS = -aIndS;
      }

      if (canLinkBeTaken(aIndS))
      {
        aLstIndS.Append(aIndS);
      }
    }

    if (aLstIndS.IsEmpty())
    {
      // no more ways: open contour
      aStartIndex = theContour.Extent() + 1;
      break;
    }

    int aIndexSNext = 0;
    if (aLstIndS.First() == aLstIndS.Last())
    {
      // only one possible way
      aIndexSNext = aLstIndS.First();
    }
    else
    {
      // find the most left way
      aIndexSNext = chooseLeftWay(aLastNode, aIndexS, aLstIndS);
    }

    aIndexS = aIndexSNext;

    if (aIndexS == 0)
    {
      // no more ways: open contour
      aStartIndex = theContour.Extent() + 1;
      break;
    }
    if (theContour.Contains(aIndexS))
    {
      // entering the loop second time, stop search
      aStartIndex = theContour.FindIndex(aIndexS);
      break;
    }
    if (theContour.Contains(-aIndexS))
    {
      // leaving the loop, stop search
      aStartIndex = theContour.FindIndex(-aIndexS) + 1;
      break;
    }

    aLastNode = getLastNode(aIndexS);

    if (aNodeLink.IsBound(aLastNode))
    {
      // closing the loop, stop search
      theContour.Add(aIndexS);
      aStartIndex = theContour.FindIndex(aNodeLink.Find(aLastNode));
      break;
    }
  }

  return aStartIndex;
}

//=======================================================================
// function : acceptContour
// purpose  : Builds a wire from a given set of edge indices (starting with
// theStartNumber) and appends it to the result list.
// Also updates the start indices.
//=======================================================================

void Poly_MakeLoops::acceptContour(const NCollection_IndexedMap<int>& theContour,
                                   int                                theStartNumber)
{
  // append a new loop to the result
  Loop anEmptyLoop(myAlloc);
  myLoops.Append(anEmptyLoop);
  Loop& aLoop = myLoops.ChangeValue(myLoops.Length());

  // build a loop, mark links as taken,
  // remove them from the set of start indices
  int i;
  for (i = theStartNumber; i <= theContour.Extent(); i++)
  {
    int         aIndexS       = theContour(i); // index with sign
    int         aIndex        = std::abs(aIndexS);
    const Link& aLink         = myMapLink(aIndex);
    Link        aOrientedLink = aLink;
    if (aIndexS < 0)
    {
      aOrientedLink.Reverse();
    }
    aLoop.Append(aOrientedLink);
    // remove from start set
    myStartIndices.Remove(aIndexS);
  }
}

//=======================================================================
// function : getFirstNode
// purpose  : Returns the first node of the given link
// taking into account its orientation (the sign of index)
//=======================================================================

int Poly_MakeLoops::getFirstNode(int theIndexS) const
{
  int         aIndex = std::abs(theIndexS);
  const Link& aLink  = myMapLink(aIndex);
  if (theIndexS > 0)
  {
    return aLink.node1;
  }
  return aLink.node2;
}

//=======================================================================
// function : getLastNode
// purpose  : Returns the last node of the given link
// taking into account its orientation (the sign of index)
//=======================================================================

int Poly_MakeLoops::getLastNode(int theIndexS) const
{
  int         aIndex = std::abs(theIndexS);
  const Link& aLink  = myMapLink(aIndex);
  if (theIndexS > 0)
  {
    return aLink.node2;
  }
  return aLink.node1;
}

//=======================================================================
// function : markHangChain
// purpose  : Marks hanging links starting from the given node.
// Also removes such links from the start indices.
//=======================================================================

void Poly_MakeLoops::markHangChain(int theNode, int theIndexS)
{
  int  aNode1  = theNode;
  int  aIndexS = theIndexS;
  int  aIndex  = std::abs(aIndexS);
  bool isOut   = (aNode1 == getFirstNode(aIndexS));
  for (;;)
  {
    // check if the current link is hanging:
    // if it is outcoming from aNode1 then count the number of
    // other incoming links and vice-versa;
    // if the number is zero than it is hanging
    const ListOfLink&                    aLinks = myHelper->GetAdjacentLinks(aNode1);
    int                                  nEdges = 0;
    Poly_MakeLoops::ListOfLink::Iterator itLinks(aLinks);
    for (; itLinks.More() && nEdges == 0; itLinks.Next())
    {
      const Link& aL   = itLinks.Value();
      int         aInd = myMapLink.FindIndex(aL);
      if (aInd == 0 || aInd == aIndex)
      {
        continue;
      }
      if ((isOut && aNode1 == aL.node1) || (!isOut && aNode1 == aL.node2))
      {
        aInd = -aInd;
      }
      if (canLinkBeTaken(aInd))
      {
        nEdges++;
      }
    }
    if (nEdges > 0)
    {
      // leave this chain
      break;
    }

    // mark the current link as hanging
    myStartIndices.Remove(aIndexS);
    myHangIndices.Add(aIndexS);

    // get other node of the link and the next link
    if (isOut)
    {
      aNode1 = getLastNode(aIndexS);
    }
    else
    {
      aNode1 = getFirstNode(aIndexS);
    }
    const ListOfLink& aNextLinks  = myHelper->GetAdjacentLinks(aNode1);
    int               aNextIndexS = 0;
    for (itLinks.Init(aNextLinks); itLinks.More(); itLinks.Next())
    {
      const Link& aL   = itLinks.Value();
      int         aInd = myMapLink.FindIndex(aL);
      if (aInd == 0 || aInd == aIndex)
      {
        continue;
      }
      if ((isOut && aNode1 == aL.node2) || (!isOut && aNode1 == aL.node1))
      {
        aInd = -aInd;
      }
      if (canLinkBeTaken(aInd))
      {
        if (aNextIndexS == 0)
        {
          aNextIndexS = aInd;
        }
        else
        {
          // more than 1 ways, stop the chain
          aNextIndexS = 0;
          break;
        }
      }
    }
    if (aNextIndexS == 0)
    {
      break;
    }
    aIndexS = aNextIndexS;
    aIndex  = std::abs(aIndexS);
  }
}

//=======================================================================
// function : canLinkBeTaken
// purpose  : Returns True if the link appointed by the index can participate
// in a loop in given orientation (it is the sign of index).
// Remark: A boundary edge can be taken only once
//=======================================================================

bool Poly_MakeLoops::canLinkBeTaken(int theIndexS) const
{
  return myStartIndices.Contains(theIndexS);
}

//=================================================================================================

#ifdef OCCT_DEBUG
void Poly_MakeLoops::showBoundaryBreaks() const
{
  // collect nodes of boundary links
  TColStd_PackedMapOfInteger aNodesMap;
  int                        i;
  for (i = 1; i <= myMapLink.Extent(); i++)
  {
    const Link& aLink  = myMapLink(i);
    int         aFlags = aLink.flags & LF_Both;
    if (aFlags && aFlags != LF_Both)
    {
      // take only oriented links
      aNodesMap.Add(aLink.node1);
      aNodesMap.Add(aLink.node2);
    }
  }

  // check each node if the number of input and output links are equal
  bool                                 isFirst = true;
  TColStd_PackedMapOfInteger::Iterator it(aNodesMap);
  for (; it.More(); it.Next())
  {
    int                                  aNode  = it.Key();
    int                                  nb     = 0;
    const ListOfLink&                    aLinks = myHelper->GetAdjacentLinks(aNode);
    Poly_MakeLoops::ListOfLink::Iterator itLinks(aLinks);
    for (; itLinks.More(); itLinks.Next())
    {
      const Poly_MakeLoops::Link& aLink = itLinks.Value();
      if (myMapLink.FindIndex(aLink) == 0)
        continue;
      int aFlags = aLink.flags & LF_Both;
      if (aFlags && aFlags != LF_Both)
      {
        if (aNode == aLink.node1) // output?
        {
          if (aFlags & LF_Fwd)
            nb++; // yes, output
          else
            nb--; // reversed, so input
        }
        else if (aNode == aLink.node2) // input?
        {
          if (aFlags & LF_Fwd)
            nb--; // yes, input
          else
            nb++; // reversed, so output
        }
        else
          // inconsistent
          nb += 100;
      }
    }
    if (nb != 0)
    {
      // indicate this node
      if (isFirst)
      {
        isFirst = false;
        std::cout << "boundary breaks are found in the following nodes:" << std::endl;
      }
      std::cout << aNode << " ";
    }
  }
  if (!isFirst)
    std::cout << std::endl;
}
#endif

//=================================================================================================

void Poly_MakeLoops::GetHangingLinks(ListOfLink& theLinks) const
{
  TColStd_PackedMapOfInteger::Iterator it(myHangIndices);
  for (; it.More(); it.Next())
  {
    int  aIndexS = it.Key();
    Link aLink   = myMapLink(std::abs(aIndexS));
    if (aIndexS < 0)
    {
      aLink.Reverse();
    }
    theLinks.Append(aLink);
  }
}

//=================================================================================================

Poly_MakeLoops3D::Poly_MakeLoops3D(const Helper*                                 theHelper,
                                   const occ::handle<NCollection_BaseAllocator>& theAlloc)
    : Poly_MakeLoops(theHelper, theAlloc)
{
}

//=================================================================================================

int Poly_MakeLoops3D::chooseLeftWay(const int                    theNode,
                                    const int                    theSegIndex,
                                    const NCollection_List<int>& theLstIndS) const
{
  double        aAngleMin = M_PI * 2;
  gp_Dir        aNormal;
  const Helper* aHelper = getHelper();
  if (!aHelper->GetNormal(theNode, aNormal))
  {
    return theLstIndS.First();
  }

  Link   aLink = getLink(theSegIndex);
  gp_Dir aTgtRef;
  if (!aHelper->GetLastTangent(aLink, aTgtRef))
  {
    return theLstIndS.First();
  }

  // project tangent vector to the plane orthogonal to normal
  // to get the reference direction
  gp_XYZ aTgtRefXYZ = aNormal.XYZ().CrossCrossed(aTgtRef.XYZ(), aNormal.XYZ());
  if (aTgtRefXYZ.SquareModulus() < 1e-14)
  {
    // a problem with defining reference direction, take first way
    return theLstIndS.First();
  }
  aTgtRef = aTgtRefXYZ;

  // find the way with minimal angle to the reference direction
  // (the angle is in range ]-PI;PI])
  int                             aResIndex = 0;
  NCollection_List<int>::Iterator aItI(theLstIndS);
  for (; aItI.More(); aItI.Next())
  {
    int aIndS = aItI.Value();

    aLink = getLink(aIndS);
    gp_Dir aTgt;
    if (!aHelper->GetFirstTangent(aLink, aTgt))
    {
      continue;
    }

    gp_XYZ aTgtXYZ = aNormal.XYZ().CrossCrossed(aTgt.XYZ(), aNormal.XYZ());
    if (aTgtXYZ.SquareModulus() < 1e-14)
    {
      // skip a problem way
      continue;
    }
    aTgt = aTgtXYZ;

    double aAngle = aTgt.AngleWithRef(aTgtRef, aNormal);
    if (aAngle < 1e-4 - M_PI)
    {
      aAngle = M_PI;
    }
    if (aAngle < aAngleMin)
    {
      aAngleMin = aAngle;
      aResIndex = aIndS;
    }
  }
  return aResIndex == 0 ? theLstIndS.First() : aResIndex;
}

//=================================================================================================

Poly_MakeLoops2D::Poly_MakeLoops2D(const bool                                    theLeftWay,
                                   const Helper*                                 theHelper,
                                   const occ::handle<NCollection_BaseAllocator>& theAlloc)
    : Poly_MakeLoops(theHelper, theAlloc),
      myRightWay(!theLeftWay)
{
}

//=================================================================================================

int Poly_MakeLoops2D::chooseLeftWay(const int /*theNode*/,
                                    const int                    theSegIndex,
                                    const NCollection_List<int>& theLstIndS) const
{
  double        aAngleMin = M_PI * 2;
  const Helper* aHelper   = getHelper();
  Link          aLink     = getLink(theSegIndex);
  gp_Dir2d      aTgtRef;
  if (!aHelper->GetLastTangent(aLink, aTgtRef))
  {
    // a problem with defining reference direction, take first way
    return theLstIndS.First();
  }

  // find the way with minimal angle to the reference direction
  // (the angle is in range ]-PI;PI])
  int                             aResIndex = 0;
  NCollection_List<int>::Iterator aItI(theLstIndS);
  for (; aItI.More(); aItI.Next())
  {
    int aIndS = aItI.Value();

    aLink = getLink(aIndS);
    gp_Dir2d aTgt;
    if (!aHelper->GetFirstTangent(aLink, aTgt))
    {
      // skip a problem way
      continue;
    }

    double aAngle = aTgt.Angle(aTgtRef);
    if (myRightWay)
    {
      aAngle = -aAngle;
    }
    if (aAngle < 1e-4 - M_PI)
    {
      aAngle = M_PI;
    }
    if (aAngle < aAngleMin)
    {
      aAngleMin = aAngle;
      aResIndex = aIndS;
    }
  }
  return aResIndex == 0 ? theLstIndS.First() : aResIndex;
}