1 // Created on: 2009-10-22
2 // Created by: Mikhail SAZONOV
3 // Copyright (c) 2009-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 #include <Poly_MakeLoops.hxx>
17 #include <NCollection_IncAllocator.hxx>
18 #include <NCollection_DataMap.hxx>
20 #include <gp_Dir2d.hxx>
23 static Standard_Integer doDebug = 0;
26 //=======================================================================
27 //function : Poly_MakeLoops
29 //=======================================================================
31 Poly_MakeLoops::Poly_MakeLoops(const Helper* theHelper,
32 const Handle(NCollection_BaseAllocator)& theAlloc)
33 : myHelper (theHelper),
35 myMapLink (4000, myAlloc),
41 //=======================================================================
44 //=======================================================================
46 void Poly_MakeLoops::Reset
47 (const Helper* theHelper,
48 const Handle(NCollection_BaseAllocator)& theAlloc)
52 myLoops.Clear(theAlloc);
53 myStartIndices.Clear();
57 //=======================================================================
60 //=======================================================================
62 void Poly_MakeLoops::AddLink(const Link& theLink)
64 if (theLink.node1 == theLink.node2)
66 Standard_Integer aInd = myMapLink.Add(theLink);
67 Link& aLink = const_cast<Link&>(myMapLink(aInd));
68 aLink.flags |= theLink.flags;
70 myHelper->OnAddLink (aInd, aLink);
74 //=======================================================================
75 //function : ReplaceLink
77 //=======================================================================
79 void Poly_MakeLoops::ReplaceLink(const Link& theLink, const Link& theNewLink)
81 if (theNewLink.node1 == theNewLink.node2)
83 Standard_Integer aInd = myMapLink.Add(theLink);
87 // replace with a null link first (workaround exception)
88 myMapLink.Substitute(aInd, aLink);
90 // and now put there the final value of link
91 myMapLink.Substitute(aInd, aLink);
93 myHelper->OnAddLink (aInd, aLink);
98 //=======================================================================
99 //function : SetLinkOrientation
101 //=======================================================================
103 Poly_MakeLoops::LinkFlag Poly_MakeLoops::SetLinkOrientation
104 (const Link& theLink,
105 const LinkFlag theOrient)
107 Standard_Integer aInd = myMapLink.FindIndex(theLink);
108 LinkFlag aOri = LF_None;
111 Link& aLink = const_cast<Link&>(myMapLink(aInd));
112 aOri = (LinkFlag) (aLink.flags & LF_Both);
113 aLink.flags = theOrient;
115 myHelper->OnAddLink (aInd, aLink);
121 //=======================================================================
122 //function : FindLink
124 //=======================================================================
126 Poly_MakeLoops::Link Poly_MakeLoops::FindLink(const Link& theLink) const
128 Standard_Integer aInd = myMapLink.FindIndex(theLink);
129 Poly_MakeLoops::Link aLink;
131 aLink = myMapLink(aInd);
135 //=======================================================================
138 //=======================================================================
140 Standard_Integer Poly_MakeLoops::Perform()
142 // prepare the set of start indices
143 myStartIndices.Clear();
145 for (i = 1; i <= myMapLink.Extent(); i++)
147 const Link& aLink = myMapLink(i);
148 if (aLink.flags & LF_Fwd)
149 myStartIndices.Add(i);
150 if (aLink.flags & LF_Rev)
151 myStartIndices.Add(-i);
156 showBoundaryBreaks();
159 Standard_Integer aResult = 0;
161 Handle(NCollection_IncAllocator) aTempAlloc = new NCollection_IncAllocator(4000);
162 Handle(NCollection_IncAllocator) aTempAlloc1 = new NCollection_IncAllocator(4000);
165 Standard_Integer aPassNum, nbLoopsOnPass2 = 0;
166 for (aPassNum=0; aPassNum < 2; aPassNum++)
168 myHangIndices.Clear();
170 while (!myStartIndices.IsEmpty())
172 Standard_Integer aIndexS = myStartIndices.Top();
175 NCollection_IndexedMap<Standard_Integer> aContour (100, aTempAlloc);
176 Standard_Integer aStartNumber = findContour (aIndexS, aContour, aTempAlloc, aTempAlloc1);
178 if (aStartNumber > 1)
181 cout << "--- found contour with hanging links:" << endl;
182 for (i = 1; i <= aContour.Extent(); i++)
183 cout << " " << aContour(i);
187 if (aStartNumber == 0)
189 aResult |= RC_Failure;
192 if (aStartNumber <= aContour.Extent())
194 // there is a closed loop in the contour
197 acceptContour (aContour, aStartNumber);
199 if (aStartNumber > 1)
201 // it is required to mark hanging edges
202 Standard_Integer aNode;
203 if (aStartNumber <= aContour.Extent())
204 // mark hanging edges starting from the first one till a bifurcation
205 aNode = getFirstNode(aIndexS);
208 // open contour - mark from the end back till a bifurcation
209 aIndexS = aContour(aStartNumber - 1);
210 aNode = getLastNode(aIndexS);
212 markHangChain(aNode, aIndexS);
218 // move hanging links to start indices to make the second pass
219 TColStd_MapIteratorOfPackedMapOfInteger it(myHangIndices);
220 for (; it.More(); it.Next())
221 myStartIndices.Add(it.Key());
225 if (doDebug && nbLoopsOnPass2)
226 cout << "MakeLoops: " << nbLoopsOnPass2
227 << " contours accepted on the second pass" << endl;
230 if (!myLoops.IsEmpty())
231 aResult |= RC_LoopsDone;
232 if (!myHangIndices.IsEmpty())
233 aResult |= RC_HangingLinks;
237 //=======================================================================
238 //function : findContour
239 //purpose : Collects edges in chain until they form a closed contour.
240 // Returns the index in the map theContour where the loop starts.
241 // It may return the number greater than the extent of the map by 1,
242 // what means that the contour is open
243 //=======================================================================
245 Standard_Integer Poly_MakeLoops::findContour
246 (Standard_Integer theIndexS,
247 NCollection_IndexedMap<Standard_Integer> &theContour,
248 const Handle(NCollection_BaseAllocator)& theTempAlloc,
249 const Handle(NCollection_IncAllocator)& theTempAlloc1) const
252 Standard_Integer aStartIndex = 0;
253 Standard_Integer aIndexS = theIndexS;
254 NCollection_DataMap<Standard_Integer,Standard_Integer> aNodeLink(100, theTempAlloc);
255 Standard_Integer aLastNode = getLastNode (aIndexS);
258 theContour.Add(aIndexS);
259 aNodeLink.Bind(getFirstNode(aIndexS), aIndexS);
261 Standard_Integer aIndex = Abs (aIndexS);
263 // collect the list of links from this node able to participate
265 theTempAlloc1->Reset();
266 NCollection_List<Standard_Integer> aLstIndS (theTempAlloc1);
267 const ListOfLink& aLinks = myHelper->GetAdjacentLinks (aLastNode);
268 Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks);
269 for (; itLinks.More(); itLinks.Next()) {
270 Standard_Integer aInd = myMapLink.FindIndex(itLinks.Value());
271 if (aInd == 0 || aInd == aIndex)
273 // determine the orientation in which the link is to be taken
274 Standard_Integer aIndS = aInd;
275 Standard_Integer aNode1 = getFirstNode(aInd);
276 if (aNode1 != aLastNode)
279 if (canLinkBeTaken(aIndS))
280 aLstIndS.Append(aIndS);
283 if (aLstIndS.IsEmpty()) {
284 // no more ways: open contour
285 aStartIndex = theContour.Extent() + 1;
289 Standard_Integer aIndexSNext = 0;
290 if (aLstIndS.First() == aLstIndS.Last())
291 // only one possible way
292 aIndexSNext = aLstIndS.First();
294 // find the most left way
295 aIndexSNext = chooseLeftWay (aLastNode, aIndexS, aLstIndS);
297 aIndexS = aIndexSNext;
301 // no more ways: open contour
302 aStartIndex = theContour.Extent() + 1;
305 if (theContour.Contains(aIndexS))
307 // entering the loop second time, stop search
308 aStartIndex = theContour.FindIndex (aIndexS);
311 if (theContour.Contains (-aIndexS))
313 // leaving the loop, stop search
314 aStartIndex = theContour.FindIndex (-aIndexS) + 1;
318 aLastNode = getLastNode (aIndexS);
320 if (aNodeLink.IsBound(aLastNode))
322 // closing the loop, stop search
323 theContour.Add(aIndexS);
324 aStartIndex = theContour.FindIndex(aNodeLink.Find(aLastNode));
332 //=======================================================================
333 //function : acceptContour
334 //purpose : Builds a wire from a given set of edge indices (starting with
335 // theStartNumber) and appends it to the result list.
336 // Also updates the start indices.
337 //=======================================================================
339 void Poly_MakeLoops::acceptContour
340 (const NCollection_IndexedMap<Standard_Integer>& theContour,
341 Standard_Integer theStartNumber)
343 // append a new loop to the result
344 Loop anEmptyLoop(myAlloc);
345 myLoops.Append(anEmptyLoop);
346 Loop& aLoop = myLoops.ChangeValue(myLoops.Length());
348 // build a loop, mark links as taken,
349 // remove them from the set of start indices
351 for (i = theStartNumber; i <= theContour.Extent(); i++)
353 Standard_Integer aIndexS = theContour(i); // index with sign
354 Standard_Integer aIndex = Abs (aIndexS);
355 const Link& aLink = myMapLink(aIndex);
356 Link aOrientedLink = aLink;
358 aOrientedLink.Reverse();
359 aLoop.Append(aOrientedLink);
360 // remove from start set
361 myStartIndices.Remove(aIndexS);
365 //=======================================================================
366 //function : getFirstNode
367 //purpose : Returns the first node of the given link
368 // taking into account its orientation (the sign of index)
369 //=======================================================================
371 Standard_Integer Poly_MakeLoops::getFirstNode(Standard_Integer theIndexS) const
373 Standard_Integer aIndex = Abs(theIndexS);
374 const Link& aLink = myMapLink(aIndex);
380 //=======================================================================
381 //function : getLastNode
382 //purpose : Returns the last node of the given link
383 // taking into account its orientation (the sign of index)
384 //=======================================================================
386 Standard_Integer Poly_MakeLoops::getLastNode(int theIndexS) const
388 Standard_Integer aIndex = Abs(theIndexS);
389 const Link& aLink = myMapLink(aIndex);
395 //=======================================================================
396 //function : markHangChain
397 //purpose : Marks hanging links starting from the given node.
398 // Also removes such links from the start indices.
399 //=======================================================================
401 void Poly_MakeLoops::markHangChain(Standard_Integer theNode, Standard_Integer theIndexS)
403 Standard_Integer aNode1 = theNode;
404 Standard_Integer aIndexS = theIndexS;
405 Standard_Integer aIndex = Abs(aIndexS);
406 Standard_Boolean isOut = (aNode1 == getFirstNode(aIndexS));
409 // check if the current link is hanging:
410 // if it is outcoming from aNode1 then count the number of
411 // other incoming links and vise versa;
412 // if the number is zero than it is hanging
413 const ListOfLink& aLinks = myHelper->GetAdjacentLinks (aNode1);
414 Standard_Integer nEdges = 0;
415 Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks);
416 for (; itLinks.More() && nEdges == 0; itLinks.Next())
418 const Link &aL = itLinks.Value();
419 Standard_Integer aInd = myMapLink.FindIndex(aL);
420 if (aInd == 0 || aInd == aIndex)
422 if ((isOut && aNode1 == aL.node1) ||
423 (!isOut && aNode1 == aL.node2))
425 if (canLinkBeTaken(aInd))
432 // mark the current link as hanging
433 myStartIndices.Remove(aIndexS);
434 myHangIndices.Add(aIndexS);
436 // get other node of the link and the next link
438 aNode1 = getLastNode(aIndexS);
440 aNode1 = getFirstNode(aIndexS);
441 const ListOfLink& aNextLinks = myHelper->GetAdjacentLinks (aNode1);
442 Standard_Integer aNextIndexS = 0;
443 for (itLinks.Init(aNextLinks); itLinks.More(); itLinks.Next())
445 const Link &aL = itLinks.Value();
446 Standard_Integer aInd = myMapLink.FindIndex(aL);
447 if (aInd == 0 || aInd == aIndex)
449 if ((isOut && aNode1 == aL.node2) ||
450 (!isOut && aNode1 == aL.node1))
452 if (canLinkBeTaken(aInd))
454 if (aNextIndexS == 0)
458 // more than 1 ways, stop the chain
464 if (aNextIndexS == 0)
466 aIndexS = aNextIndexS;
467 aIndex = Abs(aIndexS);
471 //=======================================================================
472 //function : canLinkBeTaken
473 //purpose : Returns True if the link appointed by the index can participate
474 // in a loop in given orientation (it is the sign of index).
475 // Remark: A boundary edge can be taken only once
476 //=======================================================================
478 Standard_Boolean Poly_MakeLoops::canLinkBeTaken(Standard_Integer theIndexS) const
480 return myStartIndices.Contains(theIndexS);
483 //=======================================================================
484 //function : showBoundaryBreaks
486 //=======================================================================
489 void Poly_MakeLoops::showBoundaryBreaks() const
491 // collect nodes of boundary links
492 TColStd_PackedMapOfInteger aNodesMap;
494 for (i = 1; i <= myMapLink.Extent(); i++)
496 const Link& aLink = myMapLink(i);
497 Standard_Integer aFlags = aLink.flags & LF_Both;
498 if (aFlags && aFlags != LF_Both)
500 // take only oriented links
501 aNodesMap.Add(aLink.node1);
502 aNodesMap.Add(aLink.node2);
506 // check each node if the number of input and output links are equal
507 Standard_Boolean isFirst = Standard_True;
508 TColStd_MapIteratorOfPackedMapOfInteger it(aNodesMap);
509 for (; it.More(); it.Next())
511 Standard_Integer aNode = it.Key();
512 Standard_Integer nb = 0;
513 const ListOfLink& aLinks = myHelper->GetAdjacentLinks(aNode);
514 Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks);
515 for (; itLinks.More(); itLinks.Next())
517 const Poly_MakeLoops::Link& aLink = itLinks.Value();
518 if (myMapLink.FindIndex(aLink) == 0)
520 Standard_Integer aFlags = aLink.flags & LF_Both;
521 if (aFlags && aFlags != LF_Both)
523 if (aNode == aLink.node1) // output?
528 nb--; // reversed, so input
530 else if (aNode == aLink.node2) // input?
535 nb++; // reversed, so output
544 // indicate this node
547 isFirst = Standard_False;
548 cout << "boundary breaks are found in the following nodes:" << endl;
550 cout << aNode << " ";
558 //=======================================================================
559 //function : GetHangingLinks
561 //=======================================================================
563 void Poly_MakeLoops::GetHangingLinks(ListOfLink& theLinks) const
565 TColStd_MapIteratorOfPackedMapOfInteger it(myHangIndices);
566 for (; it.More(); it.Next())
568 Standard_Integer aIndexS = it.Key();
569 Link aLink = myMapLink(Abs(aIndexS));
572 theLinks.Append(aLink);
576 //=======================================================================
577 //function : Poly_MakeLoops3D
579 //=======================================================================
581 Poly_MakeLoops3D::Poly_MakeLoops3D(const Helper* theHelper,
582 const Handle(NCollection_BaseAllocator)& theAlloc)
583 : Poly_MakeLoops (theHelper, theAlloc)
587 //=======================================================================
588 //function : Poly_MakeLoops3D::chooseLeftWay
590 //=======================================================================
592 Standard_Integer Poly_MakeLoops3D::chooseLeftWay
593 (const Standard_Integer theNode,
594 const Standard_Integer theSegIndex,
595 const NCollection_List<Standard_Integer>& theLstIndS) const
597 Standard_Real aAngleMin = M_PI * 2;
599 const Helper* aHelper = getHelper();
600 if (!aHelper->GetNormal (theNode, aNormal))
601 return theLstIndS.First();
603 Link aLink = getLink(theSegIndex);
605 if (!aHelper->GetLastTangent (aLink, aTgtRef))
606 return theLstIndS.First();
608 // project tangent vector to the plane orthogonal to normal
609 // to get the reference direction
610 gp_XYZ aTgtRefXYZ = aNormal.XYZ().CrossCrossed (aTgtRef.XYZ(), aNormal.XYZ());
611 if (aTgtRefXYZ.SquareModulus() < 1e-14)
612 // a problem with defining reference direction, take first way
613 return theLstIndS.First();
614 aTgtRef = aTgtRefXYZ;
616 // find the way with minimal angle to the reference direction
617 // (the angle is in range ]-PI;PI])
618 Standard_Integer aResIndex = 0;
619 NCollection_List<Standard_Integer>::Iterator aItI (theLstIndS);
620 for (; aItI.More(); aItI.Next())
622 Standard_Integer aIndS = aItI.Value();
624 aLink = getLink(aIndS);
626 if (!aHelper->GetFirstTangent (aLink, aTgt))
629 gp_XYZ aTgtXYZ = aNormal.XYZ().CrossCrossed (aTgt.XYZ(), aNormal.XYZ());
630 if (aTgtXYZ.SquareModulus() < 1e-14)
631 // skip a problem way
635 Standard_Real aAngle = aTgt.AngleWithRef(aTgtRef, aNormal);
636 if (aAngle < 1e-4 - M_PI)
638 if (aAngle < aAngleMin)
644 return aResIndex == 0 ? theLstIndS.First() : aResIndex;
647 //=======================================================================
648 //function : Poly_MakeLoops2D
650 //=======================================================================
652 Poly_MakeLoops2D::Poly_MakeLoops2D(const Standard_Boolean theLeftWay,
653 const Helper* theHelper,
654 const Handle(NCollection_BaseAllocator)& theAlloc)
655 : Poly_MakeLoops (theHelper, theAlloc),
656 myRightWay(!theLeftWay)
660 //=======================================================================
661 //function : Poly_MakeLoops2D::chooseLeftWay
663 //=======================================================================
665 Standard_Integer Poly_MakeLoops2D::chooseLeftWay
666 (const Standard_Integer /*theNode*/,
667 const Standard_Integer theSegIndex,
668 const NCollection_List<Standard_Integer>& theLstIndS) const
670 Standard_Real aAngleMin = M_PI * 2;
671 const Helper* aHelper = getHelper();
672 Link aLink = getLink(theSegIndex);
674 if (!aHelper->GetLastTangent (aLink, aTgtRef))
675 // a problem with defining reference direction, take first way
676 return theLstIndS.First();
678 // find the way with minimal angle to the reference direction
679 // (the angle is in range ]-PI;PI])
680 Standard_Integer aResIndex = 0;
681 NCollection_List<Standard_Integer>::Iterator aItI (theLstIndS);
682 for (; aItI.More(); aItI.Next())
684 Standard_Integer aIndS = aItI.Value();
686 aLink = getLink(aIndS);
688 if (!aHelper->GetFirstTangent (aLink, aTgt))
689 // skip a problem way
692 Standard_Real aAngle = aTgt.Angle(aTgtRef);
695 if (aAngle < 1e-4 - M_PI)
697 if (aAngle < aAngleMin)
703 return aResIndex == 0 ? theLstIndS.First() : aResIndex;