src/Poly/Poly_CoherentTriangulation.hxx

   1 // Created on: 2007-11-24
   2 // Created by: Alexander GRIGORIEV
   3 // Copyright (c) 2007-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef Poly_CoherentTriangulation_HeaderFile
  17 #define Poly_CoherentTriangulation_HeaderFile
  18
  19 #include <Poly_Triangulation.hxx>
  20 #include <Poly_CoherentNode.hxx>
  21 #include <Poly_CoherentTriangle.hxx>
  22 #include <Poly_CoherentLink.hxx>
  23 #include <NCollection_Vector.hxx>
  24
  25 class Poly_CoherentTriangulation;
  26 template <class A> class NCollection_List;
  27
  28 typedef NCollection_Vector<Poly_CoherentTriangle>::Iterator
  29                                 Poly_BaseIteratorOfCoherentTriangle;
  30 typedef NCollection_Vector<Poly_CoherentNode>::Iterator
  31                                 Poly_BaseIteratorOfCoherentNode;
  32 typedef NCollection_Vector<Poly_CoherentLink>::Iterator
  33                                 Poly_BaseIteratorOfCoherentLink;
  34
  35 //! Definition of HANDLE object using Standard_DefineHandle.hxx
  36 #include <Standard_Type.hxx>
  37 class Poly_CoherentTriangulation;
  38 DEFINE_STANDARD_HANDLE (Poly_CoherentTriangulation, Standard_Transient)
  39
  40 /**
  41  * Triangulation structure that allows to:
  42  * <ul>
  43  * <li>Store the connectivity of each triangle with up to 3 neighbouring ones and with the corresponding 3rd nodes on them,</li>
  44  * <li>Store the connectivity of each node with all triangles that share this node</li>
  45  * <li>Add nodes and triangles to the structure,</li>
  46  * <li>Find all triangles sharing a single or a couple of nodes</li>
  47  * <li>Remove triangles from structure</li>
  48  * <li>Optionally create Links between pairs of nodes according to the current triangulation.</li>
  49  * <li>Convert from/to Poly_Triangulation structure.</li>
  50  * </ul>
  51  *
  52  * This class is useful for algorithms that need to analyse and/or edit a triangulated mesh -- for example for mesh refining.
  53  * The connectivity model follows the idea that all Triangles in a mesh should have coherent orientation like on a surface of a solid body.
  54  * Connections between more than 2 triangles are not suppoorted.
  55  *
  56  * @section Poly_CoherentTriangulation Architecture
  57  * The data types used in this structure are:
  58  * <ul>
  59  * <li><b>Poly_CoherentNode</b>: Inherits go_XYZ therefore provides the full public API of gp_XYZ.
  60  * Contains references to all incident triangles. You can add new nodes but you cannot remove existing ones.
  61  * However each node that has no referenced triangle is considered as "free" (use the method IsFreeNode() to check this).
  62  * Free nodes are not available to further processing, particularly they are not exported in Poly_Triangulation.
  63  * </li>
  64  * <li><b>Poly_CoherentTriangle</b>: Main data type. Refers three Nodes, three connected Triangles, three opposite (connected) Nodes and three Links.
  65  * 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).
  66  *
  67  * You can find a triangle by one node using its triangle iterator or by
  68  * two nodes - creating a temporary Poly_CoherentLink and calling the method FindTriangle().
  69  *
  70  * Triangles can be removed but they are never deleted from the containing array. Removed triangles have all nodes equal to -1.
  71  * You can use the method IsEmpty() to check that.
  72  * </li>
  73  * <li><b>Poly_CoherentLink</b>: Auxiliary data type. Normally the array of Links is empty, because for many algorithms it is sufficient to define only Triangles.
  74  * 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).
  75  * It refers two connected triangulated Nodes - on the left and on the right,
  76  * therefore a Poly_CoherentLink instance refers the full set of nodes that constitute a couple of connected Triangles.
  77  * A boundary Link has either the first (left) or the second (right) connected node index equal to -1.
  78  *
  79  * 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.
  80  * Particularly, new Links are created by method AddTriangle() and existing ones are removed by method RemoveTriangle(), in each case whenever necessary.
  81  *
  82  * Similarly to Poly_CoherentTriangle, a Link can be removed but not destroyed separately from others.
  83  * Removed Link can be recogniosed using the method IsEmpty(). To destroy all Links, call the method ClearLinks(),
  84  * this method also nullifies Link references in all Triangles.
  85  * </li>
  86  * All objects (except for free Nodes and empty Triangles and Links) can be visited by the corresponding Iterator.
  87  * Direct access is provided only for Nodes (needed to resolve Node indexed commonly used as reference).
  88  * Triangles and Links can be retrieved by their index only internally, the public API provides only references or pointers to C++ objects.
  89  * If you need a direct access to Triangles and Links, you can subclass Poly_CoherentTriangulation and use the protected API for your needs.
  90  *
  91  * Memory management: All data objects are stored in NCollection_Vector containers that prove to be efficient for the performance.
  92  * In addition references to triangles are stored in ring lists, with an instance of such list per Poly_CoherentNode.
  93  * These lists are allocated in a memory allocator that is provided in the constructor of Poly_CoherentTriangulation.
  94  * By default the standard OCCT allocator (aka NCollection_BaseAllocator) is used.
  95  * But if you need to increase the performance you can use NCollection_IncAllocator instead.
  96  * </ul>
  97  */
  98 class Poly_CoherentTriangulation : public Standard_Transient
  99 {
 100  public:
 101   /**
 102    * Subclass Iterator - allows to iterate all triangles skipping those that
 103    * have been removed.
 104    */
 105   class IteratorOfTriangle : public Poly_BaseIteratorOfCoherentTriangle
 106   {
 107   public:
 108     //! Constructor
 109     Standard_EXPORT IteratorOfTriangle
 110                           (const Handle(Poly_CoherentTriangulation)& theTri);
 111     //! Make step
 112     Standard_EXPORT virtual void Next ();
 113   };
 114
 115   /**
 116    * Subclass Iterator - allows to iterate all nodes skipping the free ones.
 117    */
 118   class IteratorOfNode : public Poly_BaseIteratorOfCoherentNode
 119   {
 120   public:
 121     //! Constructor
 122     Standard_EXPORT IteratorOfNode
 123                         (const Handle(Poly_CoherentTriangulation)& theTri);
 124     //! Make step
 125     Standard_EXPORT virtual void Next ();
 126   };
 127
 128   /**
 129    * Subclass Iterator - allows to iterate all links skipping invalid ones.
 130    */
 131   class IteratorOfLink : public Poly_BaseIteratorOfCoherentLink
 132   {
 133   public:
 134     //! Constructor
 135     Standard_EXPORT IteratorOfLink
 136                         (const Handle(Poly_CoherentTriangulation)& theTri);
 137     //! Make step
 138     Standard_EXPORT virtual void Next ();
 139   };
 140
 141   //! Couple of integer indices (used in RemoveDegenerated()).
 142   struct TwoIntegers
 143   {
 144     Standard_Integer myValue[2];
 145     TwoIntegers() {}
 146     TwoIntegers(Standard_Integer i0, Standard_Integer i1) {
 147       myValue[0] = i0; myValue[1] = i1;
 148     }
 149   };
 150
 151  public:
 152   // ---------- PUBLIC METHODS ----------
 153
 154
 155   /**
 156    * Empty constructor.
 157    */
 158   Standard_EXPORT Poly_CoherentTriangulation
 159                 (const Handle(NCollection_BaseAllocator)& theAlloc = 0L);
 160
 161   /**
 162    * Constructor. It does not create Links, you should call ComputeLinks
 163    * following this constructor if you need these links.
 164    */
 165   Standard_EXPORT Poly_CoherentTriangulation
 166                 (const Handle(Poly_Triangulation)&        theTriangulation,
 167                  const Handle(NCollection_BaseAllocator)& theAlloc = 0L);
 168
 169   /**
 170    * Destructor.
 171    */
 172   Standard_EXPORT virtual ~Poly_CoherentTriangulation ();
 173
 174   /**
 175    * Create an instance of Poly_Triangulation from this object.
 176    */
 177   Standard_EXPORT Handle(Poly_Triangulation)
 178                                    GetTriangulation () const;
 179
 180   /**
 181    * Find and remove degenerated triangles in Triangulation.
 182    * @param theTol
 183    *   Tolerance for the degeneration case. If any two nodes of a triangle have
 184    *   the distance less than this tolerance, this triangle is considered
 185    *   degenerated and therefore removed by this method.
 186    * @param pLstRemovedNode
 187    *   Optional parameter. If defined, then it will receive the list of arrays
 188    *   where the first number is the index of removed node and the seond -
 189    *   the index of remaining node to which the mesh was reconnected.
 190    */
 191   Standard_EXPORT Standard_Boolean RemoveDegenerated
 192                         (const Standard_Real             theTol,
 193                          NCollection_List<TwoIntegers> * pLstRemovedNode = 0L);
 194
 195   /**
 196    * Create a list of free nodes. These nodes may appear as a result of any
 197    * custom mesh decimation or RemoveDegenerated() call. This analysis is
 198    * necessary if you support additional data structures based on the
 199    * triangulation (e.g., edges on the surface boundary).
 200    * @param lstNodes
 201    *   <tt>[out]</tt> List that receives the indices of free nodes.
 202    */
 203   Standard_EXPORT Standard_Boolean GetFreeNodes
 204                         (NCollection_List<Standard_Integer>& lstNodes) const;
 205
 206   /**
 207    * Query the index of the last node in the triangulation
 208    */
 209   inline Standard_Integer          MaxNode      () const
 210   { return myNodes.Length() - 1; }
 211
 212   /**
 213    * Query the index of the last triangle in the triangulation
 214    */
 215   inline Standard_Integer          MaxTriangle  () const
 216   { return myTriangles.Length() - 1; }
 217
 218   /**
 219    * Set the Deflection value as the parameter of the given triangulation.
 220    */
 221   inline void                      SetDeflection(const Standard_Real theDefl)
 222   { myDeflection = theDefl; }
 223
 224   /**
 225    * Query the Deflection parameter (default value 0. -- if never initialized)
 226    */
 227   inline Standard_Real             Deflection   () const
 228   { return myDeflection; }
 229
 230   /**
 231    * Initialize a node
 232    * @param thePoint
 233    *   3D Coordinates of the node.
 234    * @param iN
 235    *   Index of the node. If negative (default), the node is added to the
 236    *   end of the current array of nodes.
 237    * @return
 238    *   Index of the added node.
 239    */
 240   Standard_EXPORT Standard_Integer SetNode      (const gp_XYZ&          thePnt,
 241                                                  const Standard_Integer iN= -1);
 242
 243   /**
 244    * Get the node at the given index 'i'.
 245    */
 246   inline const Poly_CoherentNode&  Node         (const Standard_Integer i) const
 247   { return myNodes.Value(i); }
 248
 249   /**
 250    * Get the node at the given index 'i'.
 251    */
 252   inline Poly_CoherentNode&        ChangeNode   (const Standard_Integer i)
 253   { return myNodes.ChangeValue(i); }
 254
 255   /**
 256    * Query the total number of active nodes (i.e. nodes used by 1 or more
 257    * triangles)
 258    */
 259   Standard_EXPORT Standard_Integer NNodes       () const;
 260
 261   /**
 262    * Get the triangle at the given index 'i'.
 263    */
 264   inline const Poly_CoherentTriangle&  Triangle (const Standard_Integer i) const
 265   { return myTriangles.Value(i); }
 266
 267   /**
 268    * Query the total number of active triangles (i.e. triangles that refer
 269    * nodes, non-empty ones)
 270    */
 271   Standard_EXPORT Standard_Integer NTriangles   () const;
 272
 273   /**
 274    * Query the total number of active Links.
 275    */
 276   Standard_EXPORT Standard_Integer NLinks       () const;
 277
 278   /**
 279    * Removal of a single triangle from the triangulation.
 280    */
 281   Standard_EXPORT Standard_Boolean RemoveTriangle(Poly_CoherentTriangle& theTr);
 282
 283   /**
 284    * Removal of a single link from the triangulation.
 285    */
 286   Standard_EXPORT void             RemoveLink   (Poly_CoherentLink& theLink);
 287
 288   /**
 289    * Add a triangle to the triangulation.
 290    * @return
 291    *   Pointer to the added triangle instance or NULL if an error occurred.
 292    */
 293   Standard_EXPORT Poly_CoherentTriangle *
 294                                    AddTriangle  (const Standard_Integer iNode0,
 295                                                  const Standard_Integer iNode1,
 296                                                  const Standard_Integer iNode2);
 297
 298   /**
 299    * Replace nodes in the given triangle.
 300    * @return
 301    *   True if operation succeeded.
 302    */
 303   Standard_EXPORT Standard_Boolean ReplaceNodes
 304                     (Poly_CoherentTriangle& theTriangle,
 305                      const Standard_Integer iNode0,
 306                      const Standard_Integer iNode1,
 307                      const Standard_Integer iNode2);
 308
 309   /**
 310    * Add a single link to triangulation, based on a triangle and its side index.
 311    * This method does not check for coincidence with already present links.
 312    * @param theTri
 313    *   Triangle that contains the link to be added.
 314    * @param theConn
 315    *   Index of the side (i.e., 0, 1 0r 2) defining the added link.
 316    */
 317   Standard_EXPORT Poly_CoherentLink *
 318                                    AddLink (const Poly_CoherentTriangle& theTri,
 319                                             const Standard_Integer    theConn);
 320
 321   /**
 322    * Find one or two triangles that share the given couple of nodes.
 323    * @param theLink
 324    *   Link (in fact, just a couple of nodes) on which the triangle is
 325    *   searched.
 326    * @param pTri
 327    *   <tt>[out]</tt> Array of two pointers to triangle. pTri[0] stores the
 328    *   triangle to the left of the link, while pTri[1] stores the one to the
 329    *   right of the link.
 330    * @return
 331    *   True if at least one triangle is found and output as pTri.
 332    */
 333   Standard_EXPORT Standard_Boolean FindTriangle
 334                                 (const Poly_CoherentLink&       theLink,
 335                                  const Poly_CoherentTriangle*   pTri[2]) const;
 336
 337   /**
 338    * (Re)Calculate all links in this Triangulation.
 339    */
 340   Standard_EXPORT Standard_Integer ComputeLinks ();
 341
 342   /**
 343    * Clear all Links data from the Triangulation data.
 344    */
 345   Standard_EXPORT void             ClearLinks   ();
 346
 347   /**
 348    * Query the allocator of elements, this allocator can be used for other
 349    * objects
 350    */
 351   inline const Handle(NCollection_BaseAllocator)&
 352                                 Allocator       () const
 353   {
 354     return myAlloc;
 355   }
 356   /**
 357    * Create a copy of this Triangulation, using the given allocator.
 358    */
 359   Standard_EXPORT Handle(Poly_CoherentTriangulation)  Clone
 360                 (const Handle(NCollection_BaseAllocator)& theAlloc) const;
 361
 362   /**
 363    * Debugging output.
 364    */
 365   Standard_EXPORT void             Dump         (Standard_OStream&) const;
 366
 367  protected:
 368   // ---------- PROTECTED METHODS ----------
 369
 370
 371
 372  protected:
 373   // ---------- PROTECTED FIELDS ----------
 374
 375   NCollection_Vector<Poly_CoherentTriangle> myTriangles;
 376   NCollection_Vector<Poly_CoherentNode>     myNodes;
 377   NCollection_Vector<Poly_CoherentLink>     myLinks;
 378   Handle(NCollection_BaseAllocator)          myAlloc;
 379   Standard_Real                             myDeflection;
 380
 381  public:
 382 // Declaration of CASCADE RTTI
 383 DEFINE_STANDARD_RTTIEXT(Poly_CoherentTriangulation,Standard_Transient)
 384
 385   friend class IteratorOfTriangle;
 386   friend class IteratorOfNode;
 387   friend class IteratorOfLink;
 388 };
 389
 390 #include <Poly_CoherentTriangulation.hxx>
 391
 392 #endif