b311480e |
1 | // Created on: 2009-10-22 |
2 | // Created by: Mikhail SAZONOV |
973c2be1 |
3 | // Copyright (c) 2009-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
7fd59977 |
15 | |
16 | #ifndef Poly_MakeLoops_HeaderFile |
17 | #define Poly_MakeLoops_HeaderFile |
18 | |
19 | #include <NCollection_Sequence.hxx> |
20 | #include <NCollection_IndexedMap.hxx> |
21 | #include <TColStd_PackedMapOfInteger.hxx> |
22 | #include <TColStd_MapIteratorOfPackedMapOfInteger.hxx> |
c04c30b3 |
23 | #include <NCollection_IncAllocator.hxx> |
7fd59977 |
24 | #include <NCollection_List.hxx> |
25 | |
7fd59977 |
26 | |
27 | /** |
28 | * Make loops from a set of connected links. A link is represented by |
29 | * a pair of integer indices of nodes. |
30 | */ |
31 | class Poly_MakeLoops |
32 | { |
33 | public: |
34 | //! Orientation flags that can be attached to a link |
35 | enum LinkFlag { |
36 | LF_None = 0, |
37 | LF_Fwd = 1, // forward orientation |
38 | LF_Rev = 2, // reversed orientation |
39 | LF_Both = 3, // both ways oriented |
40 | LF_Reversed = 4 // means the link is reversed |
41 | }; |
42 | |
43 | //! The Link structure |
44 | struct Link |
45 | { |
46 | Standard_Integer node1, node2; |
47 | Standard_Integer flags; |
48 | |
49 | Link() |
50 | : node1(0), node2(0), flags(0) {} |
51 | |
52 | Link(Standard_Integer theNode1, Standard_Integer theNode2) |
600519c9 |
53 | : node1(theNode1), node2(theNode2), flags(1) {} |
7fd59977 |
54 | |
55 | void Reverse() |
56 | { |
57 | flags ^= Poly_MakeLoops::LF_Reversed; |
58 | } |
59 | |
60 | Standard_Boolean IsReversed() const |
61 | { |
dde68833 |
62 | return (flags & Poly_MakeLoops::LF_Reversed) != 0; |
7fd59977 |
63 | } |
64 | |
65 | void Nullify() |
66 | { |
67 | node1 = node2 = 0; |
68 | } |
69 | |
70 | Standard_Boolean IsNull() const |
71 | { |
72 | return node1 == 0 || node2 == 0; |
73 | } |
74 | }; |
75 | |
76 | // Define the Loop as a list of links |
77 | typedef NCollection_List<Link> ListOfLink; |
78 | typedef ListOfLink Loop; |
79 | |
80 | //! The abstract helper class |
81 | class Helper |
82 | { |
83 | public: |
84 | //! returns the links adjacent to the given node |
85 | virtual const ListOfLink& GetAdjacentLinks (Standard_Integer theNode) const = 0; |
86 | //! hook function called from AddLink in _DEBUG mode |
87 | virtual void OnAddLink (Standard_Integer /*theNum*/, const Link& /*theLink*/) const {} |
88 | }; |
89 | |
90 | //! This class implements a heap of integers. The most effective usage |
91 | //! of it is first to add there all items, and then get top item and remove |
92 | //! any items till it becomes empty. |
93 | class HeapOfInteger |
94 | { |
95 | public: |
96 | HeapOfInteger (const Standard_Integer theNbPreAllocated = 1) |
97 | : myMap (theNbPreAllocated), |
98 | myIterReady (Standard_False) {} |
99 | |
100 | void Clear() |
101 | { |
102 | myMap.Clear(); |
103 | myIterReady = Standard_False; |
104 | } |
105 | |
106 | void Add (const Standard_Integer theValue) |
107 | { |
108 | myMap.Add (theValue); |
109 | myIterReady = Standard_False; |
110 | } |
111 | |
112 | Standard_Integer Top() |
113 | { |
114 | if (!myIterReady) |
115 | { |
116 | myIter.Initialize (myMap); |
117 | myIterReady = Standard_True; |
118 | } |
119 | return myIter.Key(); |
120 | } |
121 | |
122 | Standard_Boolean Contains (const Standard_Integer theValue) const |
123 | { |
124 | return myMap.Contains (theValue); |
125 | } |
126 | |
127 | void Remove (const Standard_Integer theValue) |
128 | { |
129 | if (myIterReady && myIter.More() && myIter.Key() == theValue) |
130 | myIter.Next(); |
131 | myMap.Remove (theValue); |
132 | } |
133 | |
134 | Standard_Boolean IsEmpty() |
135 | { |
136 | if (!myIterReady) |
137 | { |
138 | myIter.Initialize (myMap); |
139 | myIterReady = Standard_True; |
140 | } |
141 | return !myIter.More(); |
142 | } |
143 | |
144 | private: |
145 | TColStd_PackedMapOfInteger myMap; |
146 | TColStd_MapIteratorOfPackedMapOfInteger myIter; |
147 | Standard_Boolean myIterReady; |
148 | }; |
149 | |
150 | public: |
151 | // PUBLIC METHODS |
152 | |
153 | //! Constructor. If helper is NULL then the algorithm will |
154 | //! probably return a wrong result |
155 | Standard_EXPORT Poly_MakeLoops(const Helper* theHelper, |
857ffd5e |
156 | const Handle(NCollection_BaseAllocator)& theAlloc = 0L); |
7fd59977 |
157 | |
158 | //! It is to reset the algorithm to the initial state. |
159 | Standard_EXPORT void Reset |
160 | (const Helper* theHelper, |
857ffd5e |
161 | const Handle(NCollection_BaseAllocator)& theAlloc = 0L); |
7fd59977 |
162 | |
163 | //! Adds a link to the set. theOrient defines which orientations of the link |
164 | //! are allowed. |
165 | Standard_EXPORT void AddLink(const Link& theLink); |
166 | |
167 | //! Replace one link with another (e.g. to change order of nodes) |
168 | Standard_EXPORT void ReplaceLink(const Link& theLink, const Link& theNewLink); |
169 | |
170 | //! Set a new value of orientation of a link already added earlier. |
171 | //! It can be used with LF_None to exclude the link from consideration. |
172 | //! Returns the old value of orienation. |
173 | Standard_EXPORT LinkFlag SetLinkOrientation |
174 | (const Link& theLink, |
175 | const LinkFlag theOrient); |
176 | |
177 | //! Find the link stored in algo by value |
178 | Standard_EXPORT Link FindLink(const Link& theLink) const; |
179 | |
180 | enum ResultCode |
181 | { |
182 | RC_LoopsDone = 1, |
183 | RC_HangingLinks = 2, |
184 | RC_Failure = 4 |
185 | }; |
186 | |
187 | //! Does the work. Returns the collection of result codes |
188 | Standard_EXPORT Standard_Integer Perform(); |
189 | |
190 | //! Returns the number of loops in the result |
191 | Standard_Integer GetNbLoops() const |
192 | { |
193 | return myLoops.Length(); |
194 | } |
195 | |
196 | //! Returns the loop of the given index |
197 | const Loop& GetLoop(Standard_Integer theIndex) const |
198 | { |
199 | return myLoops.Value(theIndex); |
200 | } |
201 | |
202 | //! Returns the number of detected hanging chains |
203 | Standard_Integer GetNbHanging() const |
204 | { |
205 | return myHangIndices.Extent(); |
206 | } |
207 | |
208 | //! Fills in the list of hanging links |
5fec2f77 |
209 | Standard_EXPORT void GetHangingLinks(ListOfLink& theLinks) const; |
7fd59977 |
210 | |
211 | protected: |
212 | virtual Standard_Integer chooseLeftWay |
213 | (const Standard_Integer theNode, |
214 | const Standard_Integer theSegIndex, |
215 | const NCollection_List<Standard_Integer>& theLstIndS) const = 0; |
216 | |
217 | const Helper* getHelper () const |
218 | { |
219 | return myHelper; |
220 | } |
221 | |
222 | Link getLink (const Standard_Integer theSegIndex) const |
223 | { |
224 | Link aLink = myMapLink(Abs(theSegIndex)); |
225 | if (theSegIndex < 0) |
226 | aLink.Reverse(); |
227 | return aLink; |
228 | } |
0797d9d3 |
229 | #ifdef OCCT_DEBUG |
7fd59977 |
230 | void showBoundaryBreaks() const; |
231 | #endif |
232 | |
233 | private: |
234 | int findContour(Standard_Integer theIndexS, NCollection_IndexedMap<Standard_Integer>& theContour, |
857ffd5e |
235 | const Handle(NCollection_BaseAllocator)& theTempAlloc, |
236 | const Handle(NCollection_IncAllocator)& theTempAlloc1) const; |
7fd59977 |
237 | void acceptContour(const NCollection_IndexedMap<Standard_Integer>& theContour, |
238 | Standard_Integer theStartNumber); |
239 | Standard_Integer getFirstNode(Standard_Integer theIndexS) const; |
240 | Standard_Integer getLastNode(Standard_Integer theIndexS) const; |
241 | void markHangChain(Standard_Integer theNode, Standard_Integer theIndexS); |
242 | Standard_Boolean canLinkBeTaken(Standard_Integer theIndexS) const; |
243 | |
244 | // FIELDS |
245 | const Helper* myHelper; |
857ffd5e |
246 | Handle(NCollection_BaseAllocator) myAlloc; |
7fd59977 |
247 | NCollection_IndexedMap<Link> myMapLink; |
248 | NCollection_Sequence<Loop> myLoops; |
249 | HeapOfInteger myStartIndices; |
250 | TColStd_PackedMapOfInteger myHangIndices; |
251 | }; |
252 | |
2b2be3fb |
253 | //! Computes a hash code for the given link, in the range [1, theUpperBound] |
254 | //! @param theLink the link which hash code is to be computed |
255 | //! @param theUpperBound the upper bound of the range a computing hash code must be within |
256 | //! @return a computed hash code, in the range [1, theUpperBound] |
257 | inline Standard_Integer HashCode (const Poly_MakeLoops::Link& theLink, const Standard_Integer theUpperBound) |
7fd59977 |
258 | { |
2b2be3fb |
259 | return HashCode (theLink.node1 + theLink.node2, theUpperBound); |
7fd59977 |
260 | } |
261 | |
262 | /** |
263 | * IsEqual method is needed for maps |
264 | */ |
265 | inline Standard_Boolean IsEqual(const Poly_MakeLoops::Link& theKey1, |
266 | const Poly_MakeLoops::Link& theKey2) |
267 | { |
0ebaa4db |
268 | return ((theKey1.node1 == theKey2.node1 && theKey1.node2 == theKey2.node2) || |
269 | (theKey1.node1 == theKey2.node2 && theKey1.node2 == theKey2.node1)); |
7fd59977 |
270 | } |
271 | |
272 | /** |
273 | * Implementation for 3D space |
274 | */ |
275 | class gp_Dir; |
276 | class Poly_MakeLoops3D: public Poly_MakeLoops |
277 | { |
278 | public: |
279 | //! The abstract helper class |
280 | class Helper: public Poly_MakeLoops::Helper |
281 | { |
282 | public: |
283 | // all the following methods should return False if |
284 | // it is impossible to return a valid direction |
285 | |
286 | //! returns the tangent vector at the first node of a link |
287 | virtual Standard_Boolean GetFirstTangent(const Link& theLink, |
288 | gp_Dir& theDir) const = 0; |
289 | |
290 | //! returns the tangent vector at the last node of a link |
291 | virtual Standard_Boolean GetLastTangent(const Link& theLink, |
292 | gp_Dir& theDir) const = 0; |
293 | |
294 | //! returns the normal to the surface at a given node |
295 | virtual Standard_Boolean GetNormal(Standard_Integer theNode, |
296 | gp_Dir& theDir) const = 0; |
297 | }; |
298 | |
299 | //! Constructor. If helper is NULL then the algorithm will |
300 | //! probably return a wrong result |
301 | Standard_EXPORT Poly_MakeLoops3D(const Helper* theHelper, |
857ffd5e |
302 | const Handle(NCollection_BaseAllocator)& theAlloc); |
7fd59977 |
303 | |
304 | protected: |
305 | Standard_EXPORT virtual Standard_Integer chooseLeftWay |
306 | (const Standard_Integer theNode, |
307 | const Standard_Integer theSegIndex, |
308 | const NCollection_List<Standard_Integer>& theLstIndS) const; |
309 | const Helper* getHelper () const |
310 | { |
311 | return static_cast<const Poly_MakeLoops3D::Helper*> |
312 | (Poly_MakeLoops::getHelper()); |
313 | } |
314 | }; |
315 | |
316 | /** |
317 | * Implementation for 2D space |
318 | */ |
319 | class gp_Dir2d; |
320 | class Poly_MakeLoops2D: public Poly_MakeLoops |
321 | { |
322 | public: |
323 | //! The abstract helper class |
324 | class Helper: public Poly_MakeLoops::Helper |
325 | { |
326 | public: |
327 | // all the following methods should return False if |
328 | // it is impossible to return a valid direction |
329 | |
330 | //! returns the tangent vector at the first node of a link |
331 | virtual Standard_Boolean GetFirstTangent(const Link& theLink, |
332 | gp_Dir2d& theDir) const = 0; |
333 | |
334 | //! returns the tangent vector at the last node of a link |
335 | virtual Standard_Boolean GetLastTangent(const Link& theLink, |
336 | gp_Dir2d& theDir) const = 0; |
337 | }; |
338 | |
339 | //! Constructor. If helper is NULL then the algorithm will |
340 | //! probably return a wrong result |
341 | Standard_EXPORT Poly_MakeLoops2D(const Standard_Boolean theLeftWay, |
342 | const Helper* theHelper, |
857ffd5e |
343 | const Handle(NCollection_BaseAllocator)& theAlloc); |
7fd59977 |
344 | |
345 | protected: |
346 | Standard_EXPORT virtual Standard_Integer chooseLeftWay |
347 | (const Standard_Integer theNode, |
348 | const Standard_Integer theSegIndex, |
349 | const NCollection_List<Standard_Integer>& theLstIndS) const; |
350 | const Helper* getHelper () const |
351 | { |
352 | return static_cast<const Poly_MakeLoops2D::Helper*> |
353 | (Poly_MakeLoops::getHelper()); |
354 | } |
355 | |
356 | private: |
357 | //! this flag says that chooseLeftWay must choose the right way instead |
358 | Standard_Boolean myRightWay; |
359 | }; |
360 | |
361 | #endif |