// File: Poly_CoherentTriangulation.hxx // Created: 24.11.07 14:24 // Author: Alexander GRIGORIEV // Copyright: Open Cascade 2007 #ifndef Poly_CoherentTriangulation_HeaderFile #define Poly_CoherentTriangulation_HeaderFile #include #include #include #include #include class Handle_Poly_CoherentTriangulation; class Poly_CoherentTriangulation; template class NCollection_List; typedef NCollection_Vector::Iterator Poly_BaseIteratorOfCoherentTriangle; typedef NCollection_Vector::Iterator Poly_BaseIteratorOfCoherentNode; typedef NCollection_Vector::Iterator Poly_BaseIteratorOfCoherentLink; /** * Triangulation structure that allows to: *
    *
  • Store the connectivity of each triangle with up to 3 neighbouring ones * and with the corresponding 3rd nodes on them,
    • *
  • Store the connectivity of each node with all triangles that share this * node
    • *
  • Add nodes and triangles to the structure,
    • *
  • Find all triangles sharing a single or a couple of nodes
    • *
  • Remove triangles from structure
    • *
  • Optionally create Links between pairs of nodes according to the current * triangulation. *
  • Convert from/to Poly_Triangulation structure.
    • *
* This class is useful for algorithms that need to analyse and/or edit a * triangulated mesh -- for example for mesh refining. The connectivity model * follows the idea that all Triangles in a mesh should have coherent orientation * like on a surface of a solid body. Connections between more than 2 triangles * are not suppoorted. * @section Poly_CoherentTriangulation Architecture * The data types used in this structure are: *
    *
  • Poly_CoherentNode: Inherits go_XYZ therefore provides the full * public API of gp_XYZ. Contains references to all incident triangles. You * can add new nodes but you cannot remove existing ones. However each node * that has no referenced triangle is considered as "free" (use the method * IsFreeNode() to check this). Free nodes are not available to further * processing, particularly they are not exported in Poly_Triangulation. *
    • *
  • Poly_CoherentTriangle: Main data type. Refers three Nodes, three * connected Triangles, three opposite (connected) Nodes and three Links. * If there is boundary then 1, 2 or 3 references to Triangles/connected * Nodes/Links are assigned to NULL (for pointers) or -1 (for integer * node index). *
    * You can find a triangle by one node using its triangle iterator or by * two nodes - creating a temporary Poly_CoherentLink and calling the method * FindTriangle(). *
    * Triangles can be removed but they are never deleted from * the containing array. Removed triangles have all nodes equal to -1. You * can use the method IsEmpty() to check that. *
    • *
  • Poly_CoherentLink: Auxiliary data type. Normally the array of * Links is empty, because for many algorithms it is sufficient to define * only Triangles. You can explicitly create the Links at least once, * calling the method ComputeLinks(). Each Link is oriented couple of * Poly_CoherentNode (directed to the ascending Node index). It refers * two connected triangulated Nodes - on the left and on the right, * therefore a Poly_CoherentLink instance refers the full set of nodes * that constitute a couple of connected Triangles. A boundary Link has * either the first (left) or the second (right) connected node index * equal to -1. *
    * When the array of Links is created, all subsequent calls to AddTriangle * and RemoveTriangle try to preserve the connectivity Triangle-Link in * addition to the connectivity Triangle-Triangle. Particularly, new Links * are created by method AddTriangle() and existing ones are removed by * method RemoveTriangle(), in each case whenever necessary. *
    * Similarly to Poly_CoherentTriangle, a Link can be removed but not * destroyed separately from others. Removed Link can be recogniosed using * the method IsEmpty(). To destroy all Links, call the method ClearLinks(), * this method also nullifies Link references in all Triangles. *
    • * All objects (except for free Nodes and empty Triangles and Links) can be * visited by the corresponding Iterator. Direct access is provided only for * Nodes (needed to resolve Node indexed commonly used as reference). Triangles * and Links can be retrieved by their index only internally, the public API * provides only references or pointers to C++ objects. If you need a direct * access to Triangles and Links, you can subclass Poly_CoherentTriangulation * and use the protected API for your needs. *
    * Memory management: All data objects are stored in NCollection_Vector * containers that prove to be efficient for the performance. In addition * references to triangles are stored in ring lists, with an instance of such * list per Poly_CoherentNode. These lists are allocated in a memory allocator * that is provided in the constructor of Poly_CoherentTriangulation. By default * the standard OCCT allocator (aka NCollection_BaseAllocator) is used. But if * you need to increase the performance you can use NCollection_IncAllocator * instead. *
*/ class Poly_CoherentTriangulation : public Standard_Transient { public: /** * Subclass Iterator - allows to iterate all triangles skipping those that * have been removed. */ class IteratorOfTriangle : public Poly_BaseIteratorOfCoherentTriangle { public: //! Constructor Standard_EXPORT IteratorOfTriangle (const Handle_Poly_CoherentTriangulation& theTri); //! Make step Standard_EXPORT virtual void Next (); }; /** * Subclass Iterator - allows to iterate all nodes skipping the free ones. */ class IteratorOfNode : public Poly_BaseIteratorOfCoherentNode { public: //! Constructor Standard_EXPORT IteratorOfNode (const Handle_Poly_CoherentTriangulation& theTri); //! Make step Standard_EXPORT virtual void Next (); }; /** * Subclass Iterator - allows to iterate all links skipping invalid ones. */ class IteratorOfLink : public Poly_BaseIteratorOfCoherentLink { public: //! Constructor Standard_EXPORT IteratorOfLink (const Handle_Poly_CoherentTriangulation& theTri); //! Make step Standard_EXPORT virtual void Next (); }; //! Couple of integer indices (used in RemoveDegenerated()). struct TwoIntegers { Standard_Integer myValue[2]; TwoIntegers() {} TwoIntegers(Standard_Integer i0, Standard_Integer i1) { myValue[0] = i0; myValue[1] = i1; } }; public: // ---------- PUBLIC METHODS ---------- /** * Empty constructor. */ Standard_EXPORT Poly_CoherentTriangulation (const Handle_NCollection_BaseAllocator& theAlloc = 0L); /** * Constructor. It does not create Links, you should call ComputeLinks * following this constructor if you need these links. */ Standard_EXPORT Poly_CoherentTriangulation (const Handle_Poly_Triangulation& theTriangulation, const Handle_NCollection_BaseAllocator& theAlloc = 0L); /** * Destructor. */ Standard_EXPORT virtual ~Poly_CoherentTriangulation (); /** * Create an instance of Poly_Triangulation from this object. */ Standard_EXPORT Handle_Poly_Triangulation GetTriangulation () const; /** * Find and remove degenerated triangles in Triangulation. * @param theTol * Tolerance for the degeneration case. If any two nodes of a triangle have * the distance less than this tolerance, this triangle is considered * degenerated and therefore removed by this method. * @param pLstRemovedNode * Optional parameter. If defined, then it will receive the list of arrays * where the first number is the index of removed node and the seond - * the index of remaining node to which the mesh was reconnected. */ Standard_EXPORT Standard_Boolean RemoveDegenerated (const Standard_Real theTol, NCollection_List * pLstRemovedNode = 0L); /** * Create a list of free nodes. These nodes may appear as a result of any * custom mesh decimation or RemoveDegenerated() call. This analysis is * necessary if you support additional data structures based on the * triangulation (e.g., edges on the surface boundary). * @param lstNodes * [out] List that receives the indices of free nodes. */ Standard_EXPORT Standard_Boolean GetFreeNodes (NCollection_List& lstNodes) const; /** * Query the index of the last node in the triangulation */ inline Standard_Integer MaxNode () const { return myNodes.Length() - 1; } /** * Query the index of the last triangle in the triangulation */ inline Standard_Integer MaxTriangle () const { return myTriangles.Length() - 1; } /** * Set the Deflection value as the parameter of the given triangulation. */ inline void SetDeflection(const Standard_Real theDefl) { myDeflection = theDefl; } /** * Query the Deflection parameter (default value 0. -- if never initialized) */ inline Standard_Real Deflection () const { return myDeflection; } /** * Initialize a node * @param thePoint * 3D Coordinates of the node. * @param iN * Index of the node. If negative (default), the node is added to the * end of the current array of nodes. * @return * Index of the added node. */ Standard_EXPORT Standard_Integer SetNode (const gp_XYZ& thePnt, const Standard_Integer iN= -1); /** * Get the node at the given index 'i'. */ inline const Poly_CoherentNode& Node (const Standard_Integer i) const { return myNodes.Value(i); } /** * Get the node at the given index 'i'. */ inline Poly_CoherentNode& ChangeNode (const Standard_Integer i) { return myNodes.ChangeValue(i); } /** * Query the total number of active nodes (i.e. nodes used by 1 or more * triangles) */ Standard_EXPORT Standard_Integer NNodes () const; /** * Get the triangle at the given index 'i'. */ inline const Poly_CoherentTriangle& Triangle (const Standard_Integer i) const { return myTriangles.Value(i); } /** * Query the total number of active triangles (i.e. triangles that refer * nodes, non-empty ones) */ Standard_EXPORT Standard_Integer NTriangles () const; /** * Query the total number of active Links. */ Standard_EXPORT Standard_Integer NLinks () const; /** * Removal of a single triangle from the triangulation. */ Standard_EXPORT Standard_Boolean RemoveTriangle(Poly_CoherentTriangle& theTr); /** * Removal of a single link from the triangulation. */ Standard_EXPORT void RemoveLink (Poly_CoherentLink& theLink); /** * Add a triangle to the triangulation. * @return * Pointer to the added triangle instance or NULL if an error occurred. */ Standard_EXPORT Poly_CoherentTriangle * AddTriangle (const Standard_Integer iNode0, const Standard_Integer iNode1, const Standard_Integer iNode2); /** * Replace nodes in the given triangle. * @return * True if operation succeeded. */ Standard_EXPORT Standard_Boolean ReplaceNodes (Poly_CoherentTriangle& theTriangle, const Standard_Integer iNode0, const Standard_Integer iNode1, const Standard_Integer iNode2); /** * Add a single link to triangulation, based on a triangle and its side index. * This method does not check for coincidence with already present links. * @param theTri * Triangle that contains the link to be added. * @param theConn * Index of the side (i.e., 0, 1 0r 2) defining the added link. */ Standard_EXPORT Poly_CoherentLink * AddLink (const Poly_CoherentTriangle& theTri, const Standard_Integer theConn); /** * Find one or two triangles that share the given couple of nodes. * @param theLink * Link (in fact, just a couple of nodes) on which the triangle is * searched. * @param pTri * [out] Array of two pointers to triangle. pTri[0] stores the * triangle to the left of the link, while pTri[1] stores the one to the * right of the link. * @return * True if at least one triangle is found and output as pTri. */ Standard_EXPORT Standard_Boolean FindTriangle (const Poly_CoherentLink& theLink, const Poly_CoherentTriangle* pTri[2]) const; /** * (Re)Calculate all links in this Triangulation. */ Standard_EXPORT Standard_Integer ComputeLinks (); /** * Clear all Links data from the Triangulation data. */ Standard_EXPORT void ClearLinks (); /** * Query the allocator of elements, this allocator can be used for other * objects */ inline const Handle_NCollection_BaseAllocator& Allocator () const { return myAlloc; } /** * Create a copy of this Triangulation, using the given allocator. */ Standard_EXPORT Handle_Poly_CoherentTriangulation Clone (const Handle_NCollection_BaseAllocator& theAlloc) const; /** * Debugging output. */ Standard_EXPORT void Dump (Standard_OStream&) const; protected: // ---------- PROTECTED METHODS ---------- protected: // ---------- PROTECTED FIELDS ---------- NCollection_Vector myTriangles; NCollection_Vector myNodes; NCollection_Vector myLinks; Handle_NCollection_BaseAllocator myAlloc; Standard_Real myDeflection; public: // Declaration of CASCADE RTTI DEFINE_STANDARD_RTTI (Poly_CoherentTriangulation) friend class IteratorOfTriangle; friend class IteratorOfNode; friend class IteratorOfLink; }; #include #endif