OCCT

// Copyright (c) 2013-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.

#ifndef _BRepMesh_Delaun_HeaderFile
#define _BRepMesh_Delaun_HeaderFile

#include <Standard.hxx>
#include <Standard_DefineAlloc.hxx>
#include <Standard_Macro.hxx>

#include <BRepMesh_CircleTool.hxx>
#include <BRepMesh_Triangle.hxx>
#include <BRepMesh_Edge.hxx>
#include <IMeshData_Types.hxx>
#include <BRepMesh_DataStructureOfDelaun.hxx>
#include <BRepMesh_GeomTool.hxx>
#include <Message_ProgressRange.hxx>

class Bnd_Box2d;
class BRepMesh_Vertex;

//! Compute the Delaunay's triangulation with the algorithm of Watson.
class BRepMesh_Delaun
{
public:
  DEFINE_STANDARD_ALLOC

  //! Creates instance of triangulator, but do not run the algorithm automatically.
  Standard_EXPORT BRepMesh_Delaun(const occ::handle<BRepMesh_DataStructureOfDelaun>& theOldMesh,
                                  const int                                          theCellsCountU,
                                  const int                                          theCellsCountV,
                                  const bool                                         isFillCircles);

  //! Creates the triangulation with an empty Mesh data structure.
  Standard_EXPORT BRepMesh_Delaun(IMeshData::Array1OfVertexOfDelaun& theVertices);

  //! Creates the triangulation with an existent Mesh data structure.
  Standard_EXPORT BRepMesh_Delaun(const occ::handle<BRepMesh_DataStructureOfDelaun>& theOldMesh,
                                  IMeshData::Array1OfVertexOfDelaun&                 theVertices);

  //! Creates the triangulation with an existant Mesh data structure.
  Standard_EXPORT BRepMesh_Delaun(const occ::handle<BRepMesh_DataStructureOfDelaun>& theOldMesh,
                                  IMeshData::VectorOfInteger& theVertexIndices);

  //! Creates the triangulation with an existant Mesh data structure.
  Standard_EXPORT BRepMesh_Delaun(const occ::handle<BRepMesh_DataStructureOfDelaun>& theOldMesh,
                                  IMeshData::VectorOfInteger& theVertexIndices,
                                  const int                   theCellsCountU,
                                  const int                   theCellsCountV);

  //! Initializes the triangulation with an array of vertices.
  Standard_EXPORT void Init(IMeshData::Array1OfVertexOfDelaun& theVertices);

  //! Forces initialization of circles cell filter using working structure.
  Standard_EXPORT void InitCirclesTool(const int theCellsCountU, const int theCellsCountV);

  //! Removes a vertex from the triangulation.
  Standard_EXPORT void RemoveVertex(const BRepMesh_Vertex& theVertex);

  //! Adds some vertices into the triangulation.
  Standard_EXPORT void AddVertices(IMeshData::VectorOfInteger&  theVerticesIndices,
                                   const Message_ProgressRange& theRange = Message_ProgressRange());

  //! Modify mesh to use the edge.
  //! @return True if done
  Standard_EXPORT bool UseEdge(const int theEdge);

  //! Gives the Mesh data structure.
  const occ::handle<BRepMesh_DataStructureOfDelaun>& Result() const { return myMeshData; }

  //! Forces insertion of constraint edges into the base triangulation.
  void ProcessConstraints()
  {
    insertInternalEdges();

    // Adjustment of meshes to boundary edges
    frontierAdjust();
  }

  //! Gives the list of frontier edges.
  Handle(IMeshData::MapOfInteger) Frontier() const { return getEdgesByType(BRepMesh_Frontier); }

  //! Gives the list of internal edges.
  Handle(IMeshData::MapOfInteger) InternalEdges() const { return getEdgesByType(BRepMesh_Fixed); }

  //! Gives the list of free edges used only one time
  Handle(IMeshData::MapOfInteger) FreeEdges() const { return getEdgesByType(BRepMesh_Free); }

  //! Gives vertex with the given index
  const BRepMesh_Vertex& GetVertex(const int theIndex) const
  {
    return myMeshData->GetNode(theIndex);
  }

  //! Gives edge with the given index
  const BRepMesh_Edge& GetEdge(const int theIndex) const { return myMeshData->GetLink(theIndex); }

  //! Gives triangle with the given index
  const BRepMesh_Triangle& GetTriangle(const int theIndex) const
  {
    return myMeshData->GetElement(theIndex);
  }

  //! Returns tool used to build mesh consistent to Delaunay criteria.
  const BRepMesh_CircleTool& Circles() const { return myCircles; }

  //! Test is the given triangle contains the given vertex.
  //! @param theSqTolerance square tolerance to check closeness to some edge
  //! @param theEdgeOn If it is != 0 the vertex lies onto the edge index
  //!        returned through this parameter.
  Standard_EXPORT bool Contains(const int              theTriangleId,
                                const BRepMesh_Vertex& theVertex,
                                const double           theSqTolerance,
                                int&                   theEdgeOn) const;

  //! Explicitly sets ids of auxiliary vertices used to build mesh and used by 3rd-party algorithms.
  inline void SetAuxVertices(const IMeshData::VectorOfInteger& theSupVert)
  {
    mySupVert = theSupVert;
  }

  //! Destruction of auxiliary triangles containing the given vertices.
  //! Removes auxiliary vertices also.
  //! @param theAuxVertices auxiliary vertices to be cleaned up.
  Standard_EXPORT void RemoveAuxElements();

private:
  enum ReplaceFlag
  {
    Replace,
    InsertAfter,
    InsertBefore
  };

  typedef NCollection_DataMap<int, IMeshData::MapOfInteger> DataMapOfMap;

  //! Performs initialization of circles cell filter tool.
  void initCirclesTool(const Bnd_Box2d& theBox, const int theCellsCountU, const int theCellsCountV);

  //! Add bounding box for edge defined by start & end point to
  //! the given vector of bounding boxes for triangulation edges.
  void fillBndBox(IMeshData::SequenceOfBndB2d& theBoxes,
                  const BRepMesh_Vertex&       theV1,
                  const BRepMesh_Vertex&       theV2);

  //! Gives the list of edges with type defined by the input parameter.
  //! If the given type is BRepMesh_Free returns list of edges
  //! that have number of connected elements less or equal 1.
  Handle(IMeshData::MapOfInteger) getEdgesByType(const BRepMesh_DegreeOfFreedom theEdgeType) const;

  //! Run triangulation procedure.
  void perform(IMeshData::VectorOfInteger& theVertexIndices,
               const int                   theCellsCountU = -1,
               const int                   theCellsCountV = -1);

  //! Build the super mesh.
  void superMesh(const Bnd_Box2d& theBox);

  //! Computes the triangulation and adds the vertices,
  //! edges and triangles to the Mesh data structure.
  void compute(IMeshData::VectorOfInteger& theVertexIndices);

  //! Adjust the mesh on the frontier.
  void frontierAdjust();

  //! Find left polygon of the given edge and call meshPolygon.
  bool meshLeftPolygonOf(const int                       theEdgeIndex,
                         const bool                      isForward,
                         Handle(IMeshData::MapOfInteger) theSkipped = nullptr);

  //! Find next link starting from the given node and has maximum
  //! angle respect the given reference link.
  //! Each time the next link is found other neighbor links at the pivot
  //! node are marked as leprous and will be excluded from consideration
  //! next time until a hanging end is occurred.
  int findNextPolygonLink(const int&                             theFirstNode,
                          const int&                             thePivotNode,
                          const BRepMesh_Vertex&                 thePivotVertex,
                          const gp_Vec2d&                        theRefLinkDir,
                          const IMeshData::SequenceOfBndB2d&     theBoxes,
                          const IMeshData::SequenceOfInteger&    thePolygon,
                          const Handle(IMeshData::MapOfInteger)& theSkipped,
                          const bool&                            isSkipLeprous,
                          IMeshData::MapOfInteger&               theLeprousLinks,
                          IMeshData::MapOfInteger&               theDeadLinks,
                          int&                                   theNextPivotNode,
                          gp_Vec2d&                              theNextLinkDir,
                          Bnd_B2d&                               theNextLinkBndBox);

  //! Check is the given link intersects the polygon boundaries.
  //! Returns bounding box for the given link through the theLinkBndBox parameter.
  bool checkIntersection(const BRepMesh_Edge&                theLink,
                         const IMeshData::SequenceOfInteger& thePolygon,
                         const IMeshData::SequenceOfBndB2d&  thePolyBoxes,
                         const bool                          isConsiderEndPointTouch,
                         const bool                          isConsiderPointOnEdge,
                         const bool                          isSkipLastEdge,
                         Bnd_B2d&                            theLinkBndBox) const;

  //! Triangulatiion of a closed polygon described by the list
  //! of indexes of its edges in the structure.
  //! (negative index means reversed edge)
  void meshPolygon(IMeshData::SequenceOfInteger&   thePolygon,
                   IMeshData::SequenceOfBndB2d&    thePolyBoxes,
                   Handle(IMeshData::MapOfInteger) theSkipped = nullptr);

  //! Decomposes the given closed simple polygon (polygon without glued edges
  //! and loops) on two simpler ones by adding new link at the most thin part
  //! in respect to end point of the first link.
  //! In case if source polygon consists of three links, creates new triangle
  //! and clears source container.
  //! @param thePolygon source polygon to be decomposed (first part of decomposition).
  //! @param thePolyBoxes bounding boxes corresponded to source polygon's links.
  //! @param thePolygonCut product of decomposition of source polygon (second part of
  //! decomposition).
  //! @param thePolyBoxesCut bounding boxes corresponded to resulting polygon's links.
  void decomposeSimplePolygon(IMeshData::SequenceOfInteger& thePolygon,
                              IMeshData::SequenceOfBndB2d&  thePolyBoxes,
                              IMeshData::SequenceOfInteger& thePolygonCut,
                              IMeshData::SequenceOfBndB2d&  thePolyBoxesCut);

  //! Triangulation of closed polygon containing only three edges.
  bool meshElementaryPolygon(const IMeshData::SequenceOfInteger& thePolygon);

  //! Creates the triangles between the given node and the given polyline.
  void createTriangles(const int theVertexIndex, IMeshData::MapOfIntegerInteger& thePoly);

  //! Add a triangle based on the given oriented edges into mesh
  void addTriangle(const int (&theEdgesId)[3],
                   const bool (&theEdgesOri)[3],
                   const int (&theNodesId)[3]);

  //! Deletes the triangle with the given index and adds the free edges into the map.
  //! When an edge is suppressed more than one time it is destroyed.
  void deleteTriangle(const int theIndex, IMeshData::MapOfIntegerInteger& theLoopEdges);

  //! Returns start and end nodes of the given edge in respect to its orientation.
  void getOrientedNodes(const BRepMesh_Edge& theEdge, const bool isForward, int* theNodes) const;

  //! Processes loop within the given polygon formed by range of its
  //! links specified by start and end link indices.
  void processLoop(const int                           theLinkFrom,
                   const int                           theLinkTo,
                   const IMeshData::SequenceOfInteger& thePolygon,
                   const IMeshData::SequenceOfBndB2d&  thePolyBoxes);

  //! Creates new link based on the given nodes and updates the given polygon.
  int createAndReplacePolygonLink(const int                     theNodes[],
                                  const gp_Pnt2d                thePnts[],
                                  const int                     theRootIndex,
                                  const ReplaceFlag             theReplaceFlag,
                                  IMeshData::SequenceOfInteger& thePolygon,
                                  IMeshData::SequenceOfBndB2d&  thePolyBoxes);

  //! Creates the triangles on new nodes.
  void createTrianglesOnNewVertices(IMeshData::VectorOfInteger&  theVertexIndices,
                                    const Message_ProgressRange& theRange);

  //! Cleanup mesh from the free triangles.
  void cleanupMesh();

  //! Goes through the neighbour triangles around the given node started
  //! from the given link, returns TRUE if some triangle has a bounding
  //! frontier edge or FALSE elsewhere.
  bool isBoundToFrontier(const int theRefNodeId, const int theRefLinkId);

  //! Remove internal triangles from the given polygon.
  void cleanupPolygon(const IMeshData::SequenceOfInteger& thePolygon,
                      const IMeshData::SequenceOfBndB2d&  thePolyBoxes);

  //! Checks is the given vertex lies inside the polygon.
  bool isVertexInsidePolygon(const int&                        theVertexId,
                             const IMeshData::VectorOfInteger& thePolygonVertices) const;

  //! Remove all triangles and edges that are placed inside the polygon or crossed it.
  void killTrianglesAroundVertex(const int                           theZombieNodeId,
                                 const IMeshData::VectorOfInteger&   thePolyVertices,
                                 const IMeshData::MapOfInteger&      thePolyVerticesFindMap,
                                 const IMeshData::SequenceOfInteger& thePolygon,
                                 const IMeshData::SequenceOfBndB2d&  thePolyBoxes,
                                 IMeshData::MapOfInteger&            theSurvivedLinks,
                                 IMeshData::MapOfIntegerInteger&     theLoopEdges,
                                 IMeshData::VectorOfInteger&         theVictimNodes);

  //! Checks is the given link crosses the polygon boundary.
  //! If yes, kills its triangles and checks neighbor links on boundary intersection. Does nothing
  //! elsewhere.
  void killTrianglesOnIntersectingLinks(const int&                          theLinkToCheckId,
                                        const BRepMesh_Edge&                theLinkToCheck,
                                        const int&                          theEndPoint,
                                        const IMeshData::SequenceOfInteger& thePolygon,
                                        const IMeshData::SequenceOfBndB2d&  thePolyBoxes,
                                        IMeshData::MapOfInteger&            theSurvivedLinks,
                                        IMeshData::MapOfIntegerInteger&     theLoopEdges);

  //! Kill triangles bound to the given link.
  void killLinkTriangles(const int& theLinkId, IMeshData::MapOfIntegerInteger& theLoopEdges);

  //! Calculates distances between the given point and edges of triangle.
  double calculateDist(const gp_XY            theVEdges[3],
                       const gp_XY            thePoints[3],
                       const BRepMesh_Vertex& theVertex,
                       double                 theDistance[3],
                       double                 theSqModulus[3],
                       int&                   theEdgeOn) const;

  //! Checks intersection between the two segments.
  BRepMesh_GeomTool::IntFlag intSegSeg(const BRepMesh_Edge& theEdge1,
                                       const BRepMesh_Edge& theEdge2,
                                       const bool           isConsiderEndPointTouch,
                                       const bool           isConsiderPointOnEdge,
                                       gp_Pnt2d&            theIntPnt) const;

  //! Returns area of the loop of the given polygon defined by indices of its start and end links.
  double polyArea(const IMeshData::SequenceOfInteger& thePolygon,
                  const int                           theStartIndex,
                  const int                           theEndIndex) const;

  //! Performs insertion of internal edges into mesh.
  void insertInternalEdges();

  //! Checks whether the given vertex id relates to super contour.
  bool isSupVertex(const int theVertexIdx) const
  {
    for (IMeshData::VectorOfInteger::Iterator aIt(mySupVert); aIt.More(); aIt.Next())
    {
      if (theVertexIdx == aIt.Value())
      {
        return true;
      }
    }

    return false;
  }

private:
  occ::handle<BRepMesh_DataStructureOfDelaun> myMeshData;
  BRepMesh_CircleTool                         myCircles;
  IMeshData::VectorOfInteger                  mySupVert;
  bool                                        myInitCircles;
  BRepMesh_Triangle                           mySupTrian;
};

#endif