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 Handle_Poly_CoherentTriangulation;
26 class Poly_CoherentTriangulation;
27 template <class A> class NCollection_List;
29 typedef NCollection_Vector<Poly_CoherentTriangle>::Iterator
30 Poly_BaseIteratorOfCoherentTriangle;
31 typedef NCollection_Vector<Poly_CoherentNode>::Iterator
32 Poly_BaseIteratorOfCoherentNode;
33 typedef NCollection_Vector<Poly_CoherentLink>::Iterator
34 Poly_BaseIteratorOfCoherentLink;
36 //! Definition of HANDLE object using Standard_DefineHandle.hxx
37 #include <Standard_DefineHandle.hxx>
38 class Poly_CoherentTriangulation;
39 DEFINE_STANDARD_HANDLE (Poly_CoherentTriangulation, Standard_Transient)
42 * Triangulation structure that allows to:
44 * <li>Store the connectivity of each triangle with up to 3 neighbouring ones
45 * and with the corresponding 3rd nodes on them,</li>
46 * <li>Store the connectivity of each node with all triangles that share this
48 * <li>Add nodes and triangles to the structure,</li>
49 * <li>Find all triangles sharing a single or a couple of nodes</li>
50 * <li>Remove triangles from structure</li>
51 * <li>Optionally create Links between pairs of nodes according to the current
53 * <li>Convert from/to Poly_Triangulation structure.</li>
55 * This class is useful for algorithms that need to analyse and/or edit a
56 * triangulated mesh -- for example for mesh refining. The connectivity model
57 * follows the idea that all Triangles in a mesh should have coherent orientation
58 * like on a surface of a solid body. Connections between more than 2 triangles
60 * @section Poly_CoherentTriangulation Architecture
61 * The data types used in this structure are:
63 * <li><b>Poly_CoherentNode</b>: Inherits go_XYZ therefore provides the full
64 * public API of gp_XYZ. Contains references to all incident triangles. You
65 * can add new nodes but you cannot remove existing ones. However each node
66 * that has no referenced triangle is considered as "free" (use the method
67 * IsFreeNode() to check this). Free nodes are not available to further
68 * processing, particularly they are not exported in Poly_Triangulation.
70 * <li><b>Poly_CoherentTriangle</b>: Main data type. Refers three Nodes, three
71 * connected Triangles, three opposite (connected) Nodes and three Links.
72 * If there is boundary then 1, 2 or 3 references to Triangles/connected
73 * Nodes/Links are assigned to NULL (for pointers) or -1 (for integer
76 * You can find a triangle by one node using its triangle iterator or by
77 * two nodes - creating a temporary Poly_CoherentLink and calling the method
80 * Triangles can be removed but they are never deleted from
81 * the containing array. Removed triangles have all nodes equal to -1. You
82 * can use the method IsEmpty() to check that.
84 * <li><b>Poly_CoherentLink</b>: Auxiliary data type. Normally the array of
85 * Links is empty, because for many algorithms it is sufficient to define
86 * only Triangles. You can explicitly create the Links at least once,
87 * calling the method ComputeLinks(). Each Link is oriented couple of
88 * Poly_CoherentNode (directed to the ascending Node index). It refers
89 * two connected triangulated Nodes - on the left and on the right,
90 * therefore a Poly_CoherentLink instance refers the full set of nodes
91 * that constitute a couple of connected Triangles. A boundary Link has
92 * either the first (left) or the second (right) connected node index
95 * When the array of Links is created, all subsequent calls to AddTriangle
96 * and RemoveTriangle try to preserve the connectivity Triangle-Link in
97 * addition to the connectivity Triangle-Triangle. Particularly, new Links
98 * are created by method AddTriangle() and existing ones are removed by
99 * method RemoveTriangle(), in each case whenever necessary.
101 * Similarly to Poly_CoherentTriangle, a Link can be removed but not
102 * destroyed separately from others. Removed Link can be recogniosed using
103 * the method IsEmpty(). To destroy all Links, call the method ClearLinks(),
104 * this method also nullifies Link references in all Triangles.
106 * All objects (except for free Nodes and empty Triangles and Links) can be
107 * visited by the corresponding Iterator. Direct access is provided only for
108 * Nodes (needed to resolve Node indexed commonly used as reference). Triangles
109 * and Links can be retrieved by their index only internally, the public API
110 * provides only references or pointers to C++ objects. If you need a direct
111 * access to Triangles and Links, you can subclass Poly_CoherentTriangulation
112 * and use the protected API for your needs.
114 * Memory management: All data objects are stored in NCollection_Vector
115 * containers that prove to be efficient for the performance. In addition
116 * references to triangles are stored in ring lists, with an instance of such
117 * list per Poly_CoherentNode. These lists are allocated in a memory allocator
118 * that is provided in the constructor of Poly_CoherentTriangulation. By default
119 * the standard OCCT allocator (aka NCollection_BaseAllocator) is used. But if
120 * you need to increase the performance you can use NCollection_IncAllocator
125 class Poly_CoherentTriangulation : public Standard_Transient
129 * Subclass Iterator - allows to iterate all triangles skipping those that
132 class IteratorOfTriangle : public Poly_BaseIteratorOfCoherentTriangle
136 Standard_EXPORT IteratorOfTriangle
137 (const Handle_Poly_CoherentTriangulation& theTri);
139 Standard_EXPORT virtual void Next ();
143 * Subclass Iterator - allows to iterate all nodes skipping the free ones.
145 class IteratorOfNode : public Poly_BaseIteratorOfCoherentNode
149 Standard_EXPORT IteratorOfNode
150 (const Handle_Poly_CoherentTriangulation& theTri);
152 Standard_EXPORT virtual void Next ();
156 * Subclass Iterator - allows to iterate all links skipping invalid ones.
158 class IteratorOfLink : public Poly_BaseIteratorOfCoherentLink
162 Standard_EXPORT IteratorOfLink
163 (const Handle_Poly_CoherentTriangulation& theTri);
165 Standard_EXPORT virtual void Next ();
168 //! Couple of integer indices (used in RemoveDegenerated()).
171 Standard_Integer myValue[2];
173 TwoIntegers(Standard_Integer i0, Standard_Integer i1) {
174 myValue[0] = i0; myValue[1] = i1;
179 // ---------- PUBLIC METHODS ----------
185 Standard_EXPORT Poly_CoherentTriangulation
186 (const Handle_NCollection_BaseAllocator& theAlloc = 0L);
189 * Constructor. It does not create Links, you should call ComputeLinks
190 * following this constructor if you need these links.
192 Standard_EXPORT Poly_CoherentTriangulation
193 (const Handle_Poly_Triangulation& theTriangulation,
194 const Handle_NCollection_BaseAllocator& theAlloc = 0L);
199 Standard_EXPORT virtual ~Poly_CoherentTriangulation ();
202 * Create an instance of Poly_Triangulation from this object.
204 Standard_EXPORT Handle_Poly_Triangulation
205 GetTriangulation () const;
208 * Find and remove degenerated triangles in Triangulation.
210 * Tolerance for the degeneration case. If any two nodes of a triangle have
211 * the distance less than this tolerance, this triangle is considered
212 * degenerated and therefore removed by this method.
213 * @param pLstRemovedNode
214 * Optional parameter. If defined, then it will receive the list of arrays
215 * where the first number is the index of removed node and the seond -
216 * the index of remaining node to which the mesh was reconnected.
218 Standard_EXPORT Standard_Boolean RemoveDegenerated
219 (const Standard_Real theTol,
220 NCollection_List<TwoIntegers> * pLstRemovedNode = 0L);
223 * Create a list of free nodes. These nodes may appear as a result of any
224 * custom mesh decimation or RemoveDegenerated() call. This analysis is
225 * necessary if you support additional data structures based on the
226 * triangulation (e.g., edges on the surface boundary).
228 * <tt>[out]</tt> List that receives the indices of free nodes.
230 Standard_EXPORT Standard_Boolean GetFreeNodes
231 (NCollection_List<Standard_Integer>& lstNodes) const;
234 * Query the index of the last node in the triangulation
236 inline Standard_Integer MaxNode () const
237 { return myNodes.Length() - 1; }
240 * Query the index of the last triangle in the triangulation
242 inline Standard_Integer MaxTriangle () const
243 { return myTriangles.Length() - 1; }
246 * Set the Deflection value as the parameter of the given triangulation.
248 inline void SetDeflection(const Standard_Real theDefl)
249 { myDeflection = theDefl; }
252 * Query the Deflection parameter (default value 0. -- if never initialized)
254 inline Standard_Real Deflection () const
255 { return myDeflection; }
260 * 3D Coordinates of the node.
262 * Index of the node. If negative (default), the node is added to the
263 * end of the current array of nodes.
265 * Index of the added node.
267 Standard_EXPORT Standard_Integer SetNode (const gp_XYZ& thePnt,
268 const Standard_Integer iN= -1);
271 * Get the node at the given index 'i'.
273 inline const Poly_CoherentNode& Node (const Standard_Integer i) const
274 { return myNodes.Value(i); }
277 * Get the node at the given index 'i'.
279 inline Poly_CoherentNode& ChangeNode (const Standard_Integer i)
280 { return myNodes.ChangeValue(i); }
283 * Query the total number of active nodes (i.e. nodes used by 1 or more
286 Standard_EXPORT Standard_Integer NNodes () const;
289 * Get the triangle at the given index 'i'.
291 inline const Poly_CoherentTriangle& Triangle (const Standard_Integer i) const
292 { return myTriangles.Value(i); }
295 * Query the total number of active triangles (i.e. triangles that refer
296 * nodes, non-empty ones)
298 Standard_EXPORT Standard_Integer NTriangles () const;
301 * Query the total number of active Links.
303 Standard_EXPORT Standard_Integer NLinks () const;
306 * Removal of a single triangle from the triangulation.
308 Standard_EXPORT Standard_Boolean RemoveTriangle(Poly_CoherentTriangle& theTr);
311 * Removal of a single link from the triangulation.
313 Standard_EXPORT void RemoveLink (Poly_CoherentLink& theLink);
316 * Add a triangle to the triangulation.
318 * Pointer to the added triangle instance or NULL if an error occurred.
320 Standard_EXPORT Poly_CoherentTriangle *
321 AddTriangle (const Standard_Integer iNode0,
322 const Standard_Integer iNode1,
323 const Standard_Integer iNode2);
326 * Replace nodes in the given triangle.
328 * True if operation succeeded.
330 Standard_EXPORT Standard_Boolean ReplaceNodes
331 (Poly_CoherentTriangle& theTriangle,
332 const Standard_Integer iNode0,
333 const Standard_Integer iNode1,
334 const Standard_Integer iNode2);
337 * Add a single link to triangulation, based on a triangle and its side index.
338 * This method does not check for coincidence with already present links.
340 * Triangle that contains the link to be added.
342 * Index of the side (i.e., 0, 1 0r 2) defining the added link.
344 Standard_EXPORT Poly_CoherentLink *
345 AddLink (const Poly_CoherentTriangle& theTri,
346 const Standard_Integer theConn);
349 * Find one or two triangles that share the given couple of nodes.
351 * Link (in fact, just a couple of nodes) on which the triangle is
354 * <tt>[out]</tt> Array of two pointers to triangle. pTri[0] stores the
355 * triangle to the left of the link, while pTri[1] stores the one to the
358 * True if at least one triangle is found and output as pTri.
360 Standard_EXPORT Standard_Boolean FindTriangle
361 (const Poly_CoherentLink& theLink,
362 const Poly_CoherentTriangle* pTri[2]) const;
365 * (Re)Calculate all links in this Triangulation.
367 Standard_EXPORT Standard_Integer ComputeLinks ();
370 * Clear all Links data from the Triangulation data.
372 Standard_EXPORT void ClearLinks ();
375 * Query the allocator of elements, this allocator can be used for other
378 inline const Handle_NCollection_BaseAllocator&
384 * Create a copy of this Triangulation, using the given allocator.
386 Standard_EXPORT Handle_Poly_CoherentTriangulation Clone
387 (const Handle_NCollection_BaseAllocator& theAlloc) const;
392 Standard_EXPORT void Dump (Standard_OStream&) const;
395 // ---------- PROTECTED METHODS ----------
400 // ---------- PROTECTED FIELDS ----------
402 NCollection_Vector<Poly_CoherentTriangle> myTriangles;
403 NCollection_Vector<Poly_CoherentNode> myNodes;
404 NCollection_Vector<Poly_CoherentLink> myLinks;
405 Handle_NCollection_BaseAllocator myAlloc;
406 Standard_Real myDeflection;
409 // Declaration of CASCADE RTTI
410 DEFINE_STANDARD_RTTI (Poly_CoherentTriangulation)
412 friend class IteratorOfTriangle;
413 friend class IteratorOfNode;
414 friend class IteratorOfLink;
417 #include <Poly_CoherentTriangulation.hxx>