1 // Created on: 1993-05-11
2 // Created by: Didier PIFFAULT
3 // Copyright (c) 1993-1999 Matra Datavision
4 // Copyright (c) 1999-2012 OPEN CASCADE SAS
6 // The content of this file is subject to the Open CASCADE Technology Public
7 // License Version 6.5 (the "License"). You may not use the content of this file
8 // except in compliance with the License. Please obtain a copy of the License
9 // at http://www.opencascade.org and read it completely before using this file.
11 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
12 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
14 // The Original Code and all software distributed under the License is
15 // distributed on an "AS IS" basis, without warranty of any kind, and the
16 // Initial Developer hereby disclaims all such warranties, including without
17 // limitation, any warranties of merchantability, fitness for a particular
18 // purpose or non-infringement. Please see the License for the specific terms
19 // and conditions governing the rights and limitations under the License.
22 #include <BRepMesh_DataStructureOfDelaun.ixx>
24 //=======================================================================
25 //function : BRepMesh_DataStructureOfDelaun
27 //=======================================================================
28 BRepMesh_DataStructureOfDelaun::BRepMesh_DataStructureOfDelaun(const BRepMesh_BaseAllocator& theAlloc,
29 const Standard_Integer NodeNumber)
30 : myNodes(NodeNumber, theAlloc),
31 myLinks(NodeNumber*3),
33 myElements(NodeNumber*2),
34 // Not_Debuged_Yet myDelElements(theAlloc),
35 myElemOfDomain(NodeNumber*2,theAlloc),
36 myLinkOfDomain(NodeNumber*2,theAlloc)
38 myAllocator = theAlloc;
41 //=======================================================================
44 //=======================================================================
45 Standard_Integer BRepMesh_DataStructureOfDelaun::AddNode(const BRepMesh_Vertex& theNode)
47 return myNodes.Add(theNode);
50 //=======================================================================
53 //=======================================================================
54 const BRepMesh_Vertex& BRepMesh_DataStructureOfDelaun::GetNode(const Standard_Integer Index)
56 return myNodes.FindKey(Index);
59 //=======================================================================
60 //function : GetNodeList
62 //=======================================================================
63 const BRepMesh_ListOfInteger& BRepMesh_DataStructureOfDelaun::GetNodeList(const Standard_Integer Index)
65 return myNodes.FindFromIndex(Index);
68 //=======================================================================
69 //function : ForceRemoveNode
71 //=======================================================================
72 void BRepMesh_DataStructureOfDelaun::ForceRemoveNode(const Standard_Integer Index)
74 if ( myNodes.FindFromIndex(Index).Extent()==0) {
75 myNodes.Delete(Index);
79 //=======================================================================
80 //function : ReplaceNodes
82 //=======================================================================
83 void BRepMesh_DataStructureOfDelaun::ReplaceNodes(const BRepMesh_VertexTool& NewNodes)
85 if ( NewNodes.IsEmpty() )
91 //=======================================================================
92 //function : ForceRemoveLink
94 //=======================================================================
95 void BRepMesh_DataStructureOfDelaun::ForceRemoveLink(const Standard_Integer Index)
97 //Warning, the static cast from const& to & is called for
98 //performance reasons. This is applicable only in case if later
99 //modification of element (field movability) does not influent on
101 BRepMesh_Edge& lref=(BRepMesh_Edge&)myLinks.FindKey(Index);
102 if (lref.Movability()!=BRepMesh_Deleted) {
103 if (myLinks.FindFromIndex(Index).Extent()==0) {
104 BRepMesh_ListOfInteger::Iterator tit;
105 BRepMesh_ListOfInteger& aList1 = myNodes(lref.FirstNode());
106 for(tit.Init(aList1); tit.More(); tit.Next()){
107 if (tit.Value()==Index) {
113 BRepMesh_ListOfInteger& aList2 = myNodes(lref.LastNode());
114 for(tit.Init(aList2); tit.More(); tit.Next()){
115 if (tit.Value()==Index) {
120 myLinkOfDomain.Remove(Index);
121 lref.SetMovability(BRepMesh_Deleted);
122 myDelLinks.Append(Index);
127 //=======================================================================
128 //function : RemoveNode
130 //=======================================================================
131 void BRepMesh_DataStructureOfDelaun::RemoveNode(const Standard_Integer Index)
133 if (myNodes.FindKey(Index).Movability() == BRepMesh_Free &&
134 myNodes.FindFromIndex(Index).Extent() == 0) {
135 myNodes.Delete(Index);
139 //=======================================================================
140 //function : MoveNode
142 //=======================================================================
143 Standard_Boolean BRepMesh_DataStructureOfDelaun::MoveNode(const Standard_Integer Index,
144 const BRepMesh_Vertex& newNode)
146 if (myNodes.FindIndex(newNode) == 0) {
147 const BRepMesh_ListOfInteger& refLink = myNodes(Index);
148 myNodes.Substitute(Index, newNode, refLink);
149 return Standard_True;
151 return Standard_False;
154 //=======================================================================
157 //=======================================================================
158 Standard_Integer BRepMesh_DataStructureOfDelaun::NbNodes()const
160 return myNodes.Extent();
163 //=======================================================================
166 //=======================================================================
167 Standard_Integer BRepMesh_DataStructureOfDelaun::AddLink(const BRepMesh_Edge& theLink)
169 Standard_Integer LinkIndex=myLinks.FindIndex(theLink);
171 BRepMesh_PairOfIndex aPair;
172 if (!myDelLinks.IsEmpty()) {
173 LinkIndex=myDelLinks.First();
174 myLinks.Substitute(LinkIndex, theLink, aPair);
175 myDelLinks.RemoveFirst();
178 LinkIndex=myLinks.Add(theLink, aPair);
180 myNodes(theLink.FirstNode()).Append(Abs(LinkIndex));
181 myNodes(theLink.LastNode()).Append(Abs(LinkIndex));
182 myLinkOfDomain.Add(LinkIndex);
184 else if (!theLink.SameOrientation(myLinks.FindKey(LinkIndex)))
185 LinkIndex=-LinkIndex;
190 //=======================================================================
193 //=======================================================================
194 const BRepMesh_Edge& BRepMesh_DataStructureOfDelaun::GetLink(const Standard_Integer Index)
196 return myLinks.FindKey(Index);
199 //=======================================================================
200 //function : RemoveLink
202 //=======================================================================
203 void BRepMesh_DataStructureOfDelaun::RemoveLink(const Standard_Integer Index)
205 //Warning, the static cast from const& to & is called for
206 //performance reasons. This is applicable only in case if later
207 //modification of element (field movability) does not influent on
209 BRepMesh_Edge& lref=(BRepMesh_Edge&)myLinks.FindKey(Index);
210 if (lref.Movability()!=BRepMesh_Deleted) {
211 if (lref.Movability()==BRepMesh_Free &&
212 myLinks.FindFromIndex(Index).Extent()==0) {
213 BRepMesh_ListOfInteger::Iterator tit;
214 BRepMesh_ListOfInteger& aList1 = myNodes(lref.FirstNode());
215 for(tit.Init(aList1); tit.More(); tit.Next()){
216 if (tit.Value()==Index) {
221 BRepMesh_ListOfInteger& aList2 = myNodes(lref.LastNode());
222 for(tit.Init(aList2); tit.More(); tit.Next()){
223 if (tit.Value()==Index) {
228 myLinkOfDomain.Remove(Index);
229 lref.SetMovability(BRepMesh_Deleted);
230 myDelLinks.Append(Index);
235 //=======================================================================
236 //function : SubstituteLink
238 //=======================================================================
239 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteLink(const Standard_Integer Index,
240 const BRepMesh_Edge& newLink)
242 //BRepMesh_ListOfInteger thelist(myAllocator);
243 BRepMesh_PairOfIndex aPair;
244 BRepMesh_Edge lref=myLinks.FindKey(Index);
245 if (lref.Movability()==BRepMesh_Deleted)
246 myLinks.Substitute(Index, newLink, aPair);
248 if (myLinks.FindIndex(newLink)!=0)
249 return Standard_False;
251 lref.SetMovability(BRepMesh_Deleted);
252 myLinks.Substitute(Index, lref, aPair);
254 BRepMesh_ListOfInteger::Iterator tit;
255 for(tit.Init(myNodes(lref.FirstNode())); tit.More(); tit.Next()){
256 if (tit.Value()==Index) {
257 myNodes(lref.FirstNode()).Remove(tit);
261 for(tit.Init(myNodes(lref.LastNode())); tit.More(); tit.Next()){
262 if (tit.Value()==Index) {
263 myNodes(lref.LastNode()).Remove(tit);
267 myLinks.Substitute(Index, newLink, aPair);
268 myNodes(newLink.FirstNode()).Append(Abs(Index));
269 myNodes(newLink.LastNode()).Append(Abs(Index));
271 return Standard_True;
274 //=======================================================================
277 //=======================================================================
278 Standard_Integer BRepMesh_DataStructureOfDelaun::NbLinks()const
280 return myLinks.Extent();
283 //=======================================================================
284 //function : AddElement
286 //=======================================================================
287 Standard_Integer BRepMesh_DataStructureOfDelaun::AddElement(const BRepMesh_Triangle& theElement)
289 Standard_Integer ElemIndex=myElements.FindIndex(theElement);
293 if (!myDelElements.IsEmpty()) {
294 ElemIndex=myDelElements.First();
295 myElements.Substitute(ElemIndex, theElement);
296 myDelElements.RemoveFirst();
299 ElemIndex=myElements.Add(theElement);
301 myElemOfDomain.Add(ElemIndex);
303 Standard_Integer ed1, ed2, ed3;
304 Standard_Boolean or1, or2, or3;
305 theElement.Edges(ed1, ed2, ed3, or1, or2, or3);
306 myLinks(ed1).Append(ElemIndex);
307 myLinks(ed2).Append(ElemIndex);
308 myLinks(ed3).Append(ElemIndex);
314 //=======================================================================
315 //function : GetElement
317 //=======================================================================
318 const BRepMesh_Triangle& BRepMesh_DataStructureOfDelaun::GetElement(const Standard_Integer Index)
320 return myElements.FindKey(Index);
323 //=======================================================================
324 //function : RemoveElement
326 //=======================================================================
327 void BRepMesh_DataStructureOfDelaun::RemoveElement(const Standard_Integer Index)
329 //Warning, the static cast from const& to & is called for
330 //performance reasons. This is applicable only in case if later
331 //modification of element (field movability) does not influent on
333 BRepMesh_Triangle& lelem=(BRepMesh_Triangle&)myElements.FindKey(Index);
334 if (lelem.Movability()!=BRepMesh_Deleted) {
335 ClearElement(Index, lelem);
336 lelem.SetMovability(BRepMesh_Deleted);
337 // Not_Debuged_Yet myDelElements.Append(Index);
338 myElemOfDomain.Remove(Index);
342 static void removeElementIndex(BRepMesh_PairOfIndex& thePair,
343 const Standard_Integer Index)
345 for(Standard_Integer i = 1, n = thePair.Extent(); i <= n; i++) {
346 if (thePair.Index(i)==Index) {
347 thePair.RemoveIndex(i);
353 void BRepMesh_DataStructureOfDelaun::ClearElement(const Standard_Integer Index,
354 const BRepMesh_Triangle& theElem)
356 if (theElem.Movability()==BRepMesh_Free) {
357 Standard_Integer ed1, ed2, ed3;
358 Standard_Boolean or1, or2, or3;
359 theElem.Edges(ed1, ed2, ed3, or1, or2, or3);
360 removeElementIndex(myLinks(ed1),Index);
361 removeElementIndex(myLinks(ed2),Index);
362 removeElementIndex(myLinks(ed3),Index);
366 //=======================================================================
367 //function : SubstituteElement
369 //=======================================================================
370 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteElement
371 (const Standard_Integer Index, const BRepMesh_Triangle& newElement)
373 const BRepMesh_Triangle& lelem=myElements.FindKey(Index);
374 if (lelem.Movability()==BRepMesh_Deleted)
375 myElements.Substitute(Index, newElement);
377 if (myElements.FindIndex(newElement)==0) {
378 ClearElement(Index, lelem);
379 // Warning: here new element and old element should have different Hash code
380 myElements.Substitute(Index, newElement);
382 Standard_Integer ed1, ed2, ed3;
383 Standard_Boolean or1, or2, or3;
384 newElement.Edges(ed1, ed2, ed3, or1, or2, or3);
385 myLinks(ed1).Append(Index);
386 myLinks(ed2).Append(Index);
387 myLinks(ed3).Append(Index);
389 else return Standard_False;
391 return Standard_True;
394 //=======================================================================
395 //function : ClearDomain
397 //=======================================================================
398 void BRepMesh_DataStructureOfDelaun::ClearDomain()
400 BRepMesh_MapOfInteger freeEdges;
401 Standard_Integer ed1, ed2, ed3;
402 Standard_Boolean or1, or2, or3;
403 BRepMesh_MapOfInteger::Iterator itDom(myElemOfDomain);
404 //Warning, the static cast from const& to & is called for
405 //performance reasons. This is applicable only in case if later
406 //modification of element (field movability) does not influent on
408 for (;itDom.More(); itDom.Next()) {
409 BRepMesh_Triangle& lelem=(BRepMesh_Triangle&)myElements.FindKey(itDom.Key());
410 lelem.Edges(ed1, ed2, ed3, or1, or2, or3);
414 ClearElement(itDom.Key(), lelem);
415 lelem.SetMovability(BRepMesh_Deleted);
416 // Not_Debuged_Yet myDelElements.Append(itDom.Key());
418 myElemOfDomain.Clear();
419 BRepMesh_MapOfInteger::Iterator edgeIt(freeEdges);
420 for (; edgeIt.More(); edgeIt.Next())
421 RemoveLink(edgeIt.Key());
424 //=======================================================================
425 //function : NbElements
427 //=======================================================================
428 Standard_Integer BRepMesh_DataStructureOfDelaun::NbElements()const
430 return myElements.Extent();
433 //=======================================================================
436 //=======================================================================
437 Standard_Integer BRepMesh_DataStructureOfDelaun::IndexOf(const BRepMesh_Vertex& aNode)
439 return myNodes.FindIndex(aNode);
442 //=======================================================================
445 //=======================================================================
446 Standard_Integer BRepMesh_DataStructureOfDelaun::IndexOf(const BRepMesh_Edge& aLink)const
448 return myLinks.FindIndex(aLink);
451 //=======================================================================
454 //=======================================================================
455 Standard_Integer BRepMesh_DataStructureOfDelaun::IndexOf(const BRepMesh_Triangle& anElement)const
457 return myElements.FindIndex(anElement);
460 //=======================================================================
461 //function : LinkNeighboursOf
463 //=======================================================================
464 const BRepMesh_ListOfInteger& BRepMesh_DataStructureOfDelaun::LinkNeighboursOf
465 (const Standard_Integer theNode)const
467 return myNodes.FindFromIndex(theNode);
470 //=======================================================================
471 //function : ElemConnectedTo
473 //=======================================================================
474 const BRepMesh_PairOfIndex& BRepMesh_DataStructureOfDelaun::ElemConnectedTo
475 (const Standard_Integer theLink)const
477 return myLinks.FindFromIndex(theLink);
480 //=======================================================================
481 //function : ElemOfDomain
483 //=======================================================================
484 const BRepMesh_MapOfInteger& BRepMesh_DataStructureOfDelaun::ElemOfDomain () const
486 return myElemOfDomain;
489 //=======================================================================
490 //function : LinkOfDomain
492 //=======================================================================
493 const BRepMesh_MapOfInteger& BRepMesh_DataStructureOfDelaun::LinkOfDomain () const
495 return myLinkOfDomain;
498 //=======================================================================
499 //function : ClearDeleted
501 //=======================================================================
502 void BRepMesh_DataStructureOfDelaun::ClearDeleted()
505 // Traitement des Elements
507 Standard_Integer IndexDelItem;
509 Standard_Integer lastNonDelItem=myElements.Extent();
510 /* // Not_Debuged_Yet
511 while (!myDelElements.IsEmpty()) {
512 while (lastNonDelItem>0) {
513 if (myElements.FindKey(lastNonDelItem).Movability()!=BRepMesh_Deleted)
515 myElements.RemoveLast();
519 IndexDelItem=myDelElements.First();
520 myDelElements.RemoveFirst();
522 if (IndexDelItem<lastNonDelItem) {
523 BRepMesh_Triangle eItem=myElements.FindKey(lastNonDelItem);
524 myElements.RemoveLast();
525 myElements.Substitute(IndexDelItem, eItem);
526 myElemOfDomain.Remove(lastNonDelItem);
527 myElemOfDomain.Add(IndexDelItem);
530 Standard_Integer ed[3], ied;
531 Standard_Boolean orient[3];
532 eItem.Edges(ed[0], ed[1], ed[2], orient[0], orient[1], orient[2]);
533 BRepMesh_ListOfInteger::Iterator itList;
534 for (ied=0; ied<3; ied++) {
535 BRepMesh_PairOfIndex& aPair = myLinks(ed[ied]);
536 for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; j++)
537 if (aPair.Index(j)==(lastNonDelItem+1)) {
538 aPair.SetIndex(j,IndexDelItem);
547 lastNonDelItem=myLinks.Extent();
549 while (!myDelLinks.IsEmpty()) {
550 while (lastNonDelItem>0) {
551 if (myLinks.FindKey(lastNonDelItem).Movability()!=BRepMesh_Deleted)
553 myLinks.RemoveLast();
557 IndexDelItem = myDelLinks.First();
558 myDelLinks.RemoveFirst();
560 if (IndexDelItem < lastNonDelItem) {
561 BRepMesh_Edge lItem=myLinks.FindKey(lastNonDelItem);
562 BRepMesh_PairOfIndex Data(myLinks(lastNonDelItem));
563 myLinks.RemoveLast();
564 myLinks.Substitute(IndexDelItem, lItem, Data);
565 myLinkOfDomain.Remove(lastNonDelItem);
566 myLinkOfDomain.Add(IndexDelItem);
569 Standard_Integer iv[2], ivx;
570 iv[0]=lItem.FirstNode();
571 iv[1]=lItem.LastNode();
573 BRepMesh_ListOfInteger::Iterator itLis;
574 for (ivx=0; ivx<2; ivx++) {
575 for (itLis.Init(myNodes(iv[ivx]));
576 itLis.More(); itLis.Next()) {
577 if (itLis.Value()==(lastNonDelItem+1)) {
578 itLis.ChangeValue()=IndexDelItem;
583 for(Standard_Integer j = 1, jn = Data.Extent(); j <= jn; j++) {
584 const BRepMesh_Triangle& Elem=myElements.FindKey(Data.Index(j));
586 Standard_Integer el[3], iel;
587 Standard_Boolean orl[3];
588 Elem.Edges(el[0], el[1], el[2], orl[0], orl[1], orl[2]);
589 for (iel=0; iel<3; iel++) {
590 if (el[iel]==lastNonDelItem+1) {
591 el[iel]=IndexDelItem;
595 myElements.Substitute(itLis.Value(),
596 BRepMesh_Triangle(el[0], el[1], el[2],
597 orl[0], orl[1], orl[2],
598 Elem.Movability() ));
605 lastNonDelItem = myNodes.Extent();
606 BRepMesh_ListOfInteger &aDelNodes = (BRepMesh_ListOfInteger &)myNodes.GetListOfDelNodes();
608 while (!aDelNodes.IsEmpty()) {
609 while (lastNonDelItem > 0) {
610 if (myNodes.FindKey(lastNonDelItem).Movability()!=BRepMesh_Deleted)
612 myNodes.RemoveLast();
615 IndexDelItem = aDelNodes.First();
616 aDelNodes.RemoveFirst();
618 if (IndexDelItem<lastNonDelItem) {
619 BRepMesh_Vertex nItem = myNodes.FindKey(lastNonDelItem);
620 BRepMesh_ListOfInteger Data;
621 Data.Append(myNodes(lastNonDelItem));
622 myNodes.RemoveLast();
624 myNodes.Substitute(IndexDelItem, nItem, Data);
626 BRepMesh_ListOfInteger::Iterator itLi;
627 for (itLi.Init(Data); itLi.More(); itLi.Next()) {
628 const BRepMesh_Edge& li=myLinks.FindKey(itLi.Value());
629 BRepMesh_PairOfIndex conx(myLinks(itLi.Value()));
630 Standard_Integer iv1=li.FirstNode();
631 Standard_Integer iv2=li.LastNode();
632 if (iv1==lastNonDelItem+1) iv1=IndexDelItem;
633 else if (iv2==lastNonDelItem+1) iv2=IndexDelItem;
635 myLinks.Substitute(itLi.Value(),
636 BRepMesh_Edge(iv1, iv2, li.Movability()), conx);
642 //=======================================================================
643 //function : Statistics
645 //=======================================================================
646 void BRepMesh_DataStructureOfDelaun::Statistics(Standard_OStream& S) const
648 S << " Map de nodes : \n";
649 myNodes.Statistics(S);
650 S << "\n Deleted nodes : " << myNodes.GetListOfDelNodes().Extent() << endl;
652 S << "\n\n Map de Links : \n";
653 myLinks.Statistics(S);
654 S << "\n Deleted links : " << myDelLinks.Extent() << endl;
656 S << "\n\n Map d elements : \n";
657 myElements.Statistics(S);
658 // Not_Debuged_Yet S << "\n Deleted elements : " << myDelElements.Extent() << endl;
661 //=======================================================================
662 //function : Allocator()
664 //=======================================================================
665 const BRepMesh_BaseAllocator& BRepMesh_DataStructureOfDelaun::Allocator() const
670 //=======================================================================
673 //=======================================================================
674 BRepMesh_VertexTool& BRepMesh_DataStructureOfDelaun::Data()