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