1 // Created on: 2007-11-24
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2007-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef Poly_CoherentTriangulation_HeaderFile
17 #define Poly_CoherentTriangulation_HeaderFile
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>
25 class Poly_CoherentTriangulation;
26 template <class A> class NCollection_List;
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;
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)
41 * Triangulation structure that allows to:
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>
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.
56 * @section Poly_CoherentTriangulation Architecture
57 * The data types used in this structure are:
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.
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).
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().
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.
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.
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.
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.
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.
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.
98 class Poly_CoherentTriangulation : public Standard_Transient
102 * Subclass Iterator - allows to iterate all triangles skipping those that
105 class IteratorOfTriangle : public Poly_BaseIteratorOfCoherentTriangle
109 Standard_EXPORT IteratorOfTriangle
110 (const Handle(Poly_CoherentTriangulation)& theTri);
112 Standard_EXPORT virtual void Next ();
116 * Subclass Iterator - allows to iterate all nodes skipping the free ones.
118 class IteratorOfNode : public Poly_BaseIteratorOfCoherentNode
122 Standard_EXPORT IteratorOfNode
123 (const Handle(Poly_CoherentTriangulation)& theTri);
125 Standard_EXPORT virtual void Next ();
129 * Subclass Iterator - allows to iterate all links skipping invalid ones.
131 class IteratorOfLink : public Poly_BaseIteratorOfCoherentLink
135 Standard_EXPORT IteratorOfLink
136 (const Handle(Poly_CoherentTriangulation)& theTri);
138 Standard_EXPORT virtual void Next ();
141 //! Couple of integer indices (used in RemoveDegenerated()).
144 Standard_Integer myValue[2];
146 TwoIntegers(Standard_Integer i0, Standard_Integer i1) {
147 myValue[0] = i0; myValue[1] = i1;
152 // ---------- PUBLIC METHODS ----------
158 Standard_EXPORT Poly_CoherentTriangulation
159 (const Handle(NCollection_BaseAllocator)& theAlloc = 0L);
162 * Constructor. It does not create Links, you should call ComputeLinks
163 * following this constructor if you need these links.
165 Standard_EXPORT Poly_CoherentTriangulation
166 (const Handle(Poly_Triangulation)& theTriangulation,
167 const Handle(NCollection_BaseAllocator)& theAlloc = 0L);
172 Standard_EXPORT virtual ~Poly_CoherentTriangulation ();
175 * Create an instance of Poly_Triangulation from this object.
177 Standard_EXPORT Handle(Poly_Triangulation)
178 GetTriangulation () const;
181 * Find and remove degenerated triangles in Triangulation.
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.
191 Standard_EXPORT Standard_Boolean RemoveDegenerated
192 (const Standard_Real theTol,
193 NCollection_List<TwoIntegers> * pLstRemovedNode = 0L);
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).
201 * <tt>[out]</tt> List that receives the indices of free nodes.
203 Standard_EXPORT Standard_Boolean GetFreeNodes
204 (NCollection_List<Standard_Integer>& lstNodes) const;
207 * Query the index of the last node in the triangulation
209 inline Standard_Integer MaxNode () const
210 { return myNodes.Length() - 1; }
213 * Query the index of the last triangle in the triangulation
215 inline Standard_Integer MaxTriangle () const
216 { return myTriangles.Length() - 1; }
219 * Set the Deflection value as the parameter of the given triangulation.
221 inline void SetDeflection(const Standard_Real theDefl)
222 { myDeflection = theDefl; }
225 * Query the Deflection parameter (default value 0. -- if never initialized)
227 inline Standard_Real Deflection () const
228 { return myDeflection; }
233 * 3D Coordinates of the node.
235 * Index of the node. If negative (default), the node is added to the
236 * end of the current array of nodes.
238 * Index of the added node.
240 Standard_EXPORT Standard_Integer SetNode (const gp_XYZ& thePnt,
241 const Standard_Integer iN= -1);
244 * Get the node at the given index 'i'.
246 inline const Poly_CoherentNode& Node (const Standard_Integer i) const
247 { return myNodes.Value(i); }
250 * Get the node at the given index 'i'.
252 inline Poly_CoherentNode& ChangeNode (const Standard_Integer i)
253 { return myNodes.ChangeValue(i); }
256 * Query the total number of active nodes (i.e. nodes used by 1 or more
259 Standard_EXPORT Standard_Integer NNodes () const;
262 * Get the triangle at the given index 'i'.
264 inline const Poly_CoherentTriangle& Triangle (const Standard_Integer i) const
265 { return myTriangles.Value(i); }
268 * Query the total number of active triangles (i.e. triangles that refer
269 * nodes, non-empty ones)
271 Standard_EXPORT Standard_Integer NTriangles () const;
274 * Query the total number of active Links.
276 Standard_EXPORT Standard_Integer NLinks () const;
279 * Removal of a single triangle from the triangulation.
281 Standard_EXPORT Standard_Boolean RemoveTriangle(Poly_CoherentTriangle& theTr);
284 * Removal of a single link from the triangulation.
286 Standard_EXPORT void RemoveLink (Poly_CoherentLink& theLink);
289 * Add a triangle to the triangulation.
291 * Pointer to the added triangle instance or NULL if an error occurred.
293 Standard_EXPORT Poly_CoherentTriangle *
294 AddTriangle (const Standard_Integer iNode0,
295 const Standard_Integer iNode1,
296 const Standard_Integer iNode2);
299 * Replace nodes in the given triangle.
301 * True if operation succeeded.
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);
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.
313 * Triangle that contains the link to be added.
315 * Index of the side (i.e., 0, 1 0r 2) defining the added link.
317 Standard_EXPORT Poly_CoherentLink *
318 AddLink (const Poly_CoherentTriangle& theTri,
319 const Standard_Integer theConn);
322 * Find one or two triangles that share the given couple of nodes.
324 * Link (in fact, just a couple of nodes) on which the triangle is
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
331 * True if at least one triangle is found and output as pTri.
333 Standard_EXPORT Standard_Boolean FindTriangle
334 (const Poly_CoherentLink& theLink,
335 const Poly_CoherentTriangle* pTri[2]) const;
338 * (Re)Calculate all links in this Triangulation.
340 Standard_EXPORT Standard_Integer ComputeLinks ();
343 * Clear all Links data from the Triangulation data.
345 Standard_EXPORT void ClearLinks ();
348 * Query the allocator of elements, this allocator can be used for other
351 inline const Handle(NCollection_BaseAllocator)&
357 * Create a copy of this Triangulation, using the given allocator.
359 Standard_EXPORT Handle(Poly_CoherentTriangulation) Clone
360 (const Handle(NCollection_BaseAllocator)& theAlloc) const;
365 Standard_EXPORT void Dump (Standard_OStream&) const;
368 // ---------- PROTECTED METHODS ----------
373 // ---------- PROTECTED FIELDS ----------
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;
382 // Declaration of CASCADE RTTI
383 DEFINE_STANDARD_RTTIEXT(Poly_CoherentTriangulation,Standard_Transient)
385 friend class IteratorOfTriangle;
386 friend class IteratorOfNode;
387 friend class IteratorOfLink;
390 #include <Poly_CoherentTriangulation.hxx>