b7d2adb1e0ce1f8167c5de88656a7783d4599328
[occt.git] / src / BRepMesh / BRepMesh_DataStructureOfDelaun.cxx
1 // Created on: 1993-05-11
2 // Created by: Didier PIFFAULT
3 // Copyright (c) 1993-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 #include <BRepMesh_DataStructureOfDelaun.hxx>
18 #include <BRepMesh_PairOfIndex.hxx>
19 #include <BRepBuilderAPI_MakeEdge.hxx>
20 #include <BRepBuilderAPI_MakeVertex.hxx>
21
22 #include <TopoDS_Compound.hxx>
23 #include <BRep_Builder.hxx>
24 #include <BRepTools.hxx>
25 #include <Standard_ErrorHandler.hxx>
26
27
28 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_DataStructureOfDelaun,Standard_Transient)
29
30 //=======================================================================
31 //function : BRepMesh_DataStructureOfDelaun
32 //purpose  : 
33 //=======================================================================
34 BRepMesh_DataStructureOfDelaun::BRepMesh_DataStructureOfDelaun(
35   const Handle(NCollection_IncAllocator)& theAllocator,
36   const Standard_Integer                  theReservedNodeSize)
37   : myAllocator       (theAllocator),
38     myNodes           (new BRepMesh_VertexTool(myAllocator)),
39     myNodeLinks       (theReservedNodeSize * 3, myAllocator),
40     myLinks           (theReservedNodeSize * 3, myAllocator),
41     myDelLinks        (myAllocator),
42     myElements        (theReservedNodeSize * 2, myAllocator),
43     myElementsOfDomain(theReservedNodeSize * 2, myAllocator),
44     myLinksOfDomain   (theReservedNodeSize * 2, myAllocator)
45 {
46 }
47
48 //=======================================================================
49 //function : SubstituteNode
50 //purpose  : 
51 //=======================================================================
52 Standard_Integer BRepMesh_DataStructureOfDelaun::AddNode(
53   const BRepMesh_Vertex& theNode,
54   const Standard_Boolean isForceAdd)
55 {
56   const Standard_Integer aNodeId = myNodes->Add(theNode, isForceAdd);
57   if (!myNodeLinks.IsBound(aNodeId))
58     myNodeLinks.Bind(aNodeId, BRepMesh::ListOfInteger(myAllocator));
59
60   return aNodeId;
61 }
62
63 //=======================================================================
64 //function : SubstituteNode
65 //purpose  : 
66 //=======================================================================
67 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteNode(
68   const Standard_Integer theIndex, 
69   const BRepMesh_Vertex& theNewNode)
70 {
71   if (myNodes->FindIndex(theNewNode) != 0)
72     return Standard_False;
73
74   myNodes->Substitute(theIndex, theNewNode);
75   return Standard_True;
76 }
77
78 //=======================================================================
79 //function : AddLink
80 //purpose  : 
81 //=======================================================================
82 Standard_Integer BRepMesh_DataStructureOfDelaun::AddLink(
83   const BRepMesh_Edge& theLink)
84 {
85   Standard_Integer aLinkIndex = IndexOf(theLink);
86   if (aLinkIndex > 0)
87   {
88     return theLink.IsSameOrientation(GetLink(aLinkIndex)) ?
89        aLinkIndex : -aLinkIndex;
90   }
91
92   BRepMesh_PairOfIndex aPair;
93   if (!myDelLinks.IsEmpty())
94   {
95     aLinkIndex = myDelLinks.First();
96     myLinks.Substitute(aLinkIndex, theLink, aPair);
97     myDelLinks.RemoveFirst();
98   }
99   else
100     aLinkIndex = myLinks.Add(theLink, aPair);
101
102   const Standard_Integer aLinkId = Abs(aLinkIndex);
103   linksConnectedTo(theLink.FirstNode()).Append(aLinkId);
104   linksConnectedTo(theLink.LastNode() ).Append(aLinkId);
105   myLinksOfDomain.Add(aLinkIndex);
106
107   return aLinkIndex;
108 }
109
110 //=======================================================================
111 //function : SubstituteLink
112 //purpose  : 
113 //=======================================================================
114 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteLink(
115   const Standard_Integer theIndex,
116   const BRepMesh_Edge&   theNewLink)
117 {
118   BRepMesh_PairOfIndex aPair;
119   BRepMesh_Edge aLink = GetLink(theIndex);
120   if (aLink.Movability() == BRepMesh_Deleted)
121   {
122     myLinks.Substitute(theIndex, theNewLink, aPair);
123     return Standard_True;
124   }
125
126   if (IndexOf(theNewLink) != 0) 
127     return Standard_False;
128
129   aLink.SetMovability(BRepMesh_Deleted);
130   myLinks.Substitute(theIndex, aLink, aPair);
131   cleanLink(theIndex, aLink);
132
133   const Standard_Integer aLinkId = Abs(theIndex);
134   linksConnectedTo(theNewLink.FirstNode()).Append(aLinkId);
135   linksConnectedTo(theNewLink.LastNode() ).Append(aLinkId);
136   myLinks.Substitute(theIndex, theNewLink, aPair);
137
138   return Standard_True;
139 }
140
141 //=======================================================================
142 //function : ForceRemoveLink
143 //purpose  : 
144 //=======================================================================
145 void BRepMesh_DataStructureOfDelaun::RemoveLink(
146   const Standard_Integer theIndex,
147   const Standard_Boolean isForce)
148 {
149   BRepMesh_Edge& aLink = (BRepMesh_Edge&)GetLink(theIndex);
150   if (aLink.Movability() == BRepMesh_Deleted            ||
151       (!isForce && aLink.Movability() != BRepMesh_Free) ||
152       ElementsConnectedTo(theIndex).Extent() != 0)
153   {
154     return;
155   }
156
157   cleanLink(theIndex, aLink);
158   aLink.SetMovability(BRepMesh_Deleted);
159
160   myLinksOfDomain.Remove(theIndex);
161   myDelLinks.Append     (theIndex);
162 }
163
164 //=======================================================================
165 //function : cleanLink
166 //purpose  : 
167 //=======================================================================
168 void BRepMesh_DataStructureOfDelaun::cleanLink(
169   const Standard_Integer theIndex,
170   const BRepMesh_Edge&   theLink)
171 {
172   for (Standard_Integer i = 0; i < 2; ++i)
173   {
174     const Standard_Integer aNodeId = (i == 0) ?
175       theLink.FirstNode() : theLink.LastNode();
176
177     BRepMesh::ListOfInteger& aLinkList = linksConnectedTo(aNodeId);
178     BRepMesh::ListOfInteger::Iterator aLinkIt(aLinkList);
179     for(; aLinkIt.More(); aLinkIt.Next())
180     {
181       if (aLinkIt.Value() == theIndex)
182       {
183         aLinkList.Remove(aLinkIt);
184         break;
185       }
186     }
187   }
188 }
189
190 //=======================================================================
191 //function : AddElement
192 //purpose  : 
193 //=======================================================================
194 Standard_Integer BRepMesh_DataStructureOfDelaun::AddElement(
195   const BRepMesh_Triangle& theElement)
196 {
197   Standard_Integer aElementIndex = IndexOf(theElement);
198   if (aElementIndex > 0)
199     return aElementIndex;
200
201   aElementIndex = myElements.Add(theElement);
202   myElementsOfDomain.Add(aElementIndex);
203
204   Standard_Integer e[3];
205   Standard_Boolean o[3];
206   theElement.Edges(e, o);
207   for (Standard_Integer i = 0; i < 3; ++i)
208     myLinks(e[i]).Append(aElementIndex);
209
210   return aElementIndex;
211 }
212
213 //=======================================================================
214 //function : RemoveElement
215 //purpose  : 
216 //=======================================================================
217 void BRepMesh_DataStructureOfDelaun::RemoveElement(
218   const Standard_Integer theIndex)
219 {
220   BRepMesh_Triangle& aElement = (BRepMesh_Triangle&)GetElement(theIndex);
221   if (aElement.Movability() == BRepMesh_Deleted)
222     return;
223
224   cleanElement(theIndex, aElement);
225   aElement.SetMovability(BRepMesh_Deleted);
226   myElementsOfDomain.Remove(theIndex);
227 }
228
229 //=======================================================================
230 //function : cleanElement
231 //purpose  : 
232 //=======================================================================
233 void BRepMesh_DataStructureOfDelaun::cleanElement(
234   const Standard_Integer   theIndex,
235   const BRepMesh_Triangle& theElement)
236 {
237   if (theElement.Movability() != BRepMesh_Free)
238     return;
239
240   Standard_Integer e[3];
241   Standard_Boolean o[3];
242   theElement.Edges(e, o);
243
244   for (Standard_Integer i = 0; i < 3; ++i)
245     removeElementIndex(theIndex, myLinks(e[i]));
246 }
247
248 //=======================================================================
249 //function : removeElementIndex
250 //purpose  : 
251 //=======================================================================
252 void BRepMesh_DataStructureOfDelaun::removeElementIndex(
253   const Standard_Integer theIndex,
254   BRepMesh_PairOfIndex&  thePair)
255 {
256   for (Standard_Integer i = 1, n = thePair.Extent(); i <= n; ++i)
257   {
258     if (thePair.Index(i) == theIndex)
259     {
260       thePair.RemoveIndex(i);
261       return;
262     }
263   }
264 }
265
266 //=======================================================================
267 //function : SubstituteElement
268 //purpose  : 
269 //=======================================================================
270 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteElement(
271   const Standard_Integer   theIndex,
272   const BRepMesh_Triangle& theNewElement)
273 {
274   const BRepMesh_Triangle& aElement = GetElement(theIndex);
275   if (aElement.Movability() == BRepMesh_Deleted) 
276   {
277     myElements.Substitute(theIndex, theNewElement);
278     return Standard_True;
279   }
280
281   if (IndexOf(theNewElement) != 0)
282     return Standard_False;
283
284   cleanElement(theIndex, aElement);
285   // Warning: here new element and old element should have different Hash code
286   myElements.Substitute(theIndex, theNewElement);
287
288   Standard_Integer e[3];
289   Standard_Boolean o[3];
290   theNewElement.Edges(e, o);
291   for (Standard_Integer i = 0; i < 3; ++i)
292     myLinks(e[i]).Append(theIndex);
293
294   return Standard_True;
295 }
296
297 //=======================================================================
298 //function : ElementNodes
299 //purpose  :
300 //=======================================================================
301 void BRepMesh_DataStructureOfDelaun::ElementNodes(
302     const BRepMesh_Triangle& theElement,
303     Standard_Integer         (&theNodes)[3])
304 {
305   Standard_Integer e[3];
306   Standard_Boolean o[3];
307   theElement.Edges(e, o);
308
309   const BRepMesh_Edge& aLink1 = GetLink(e[0]);
310   if (o[0])
311   {
312     theNodes[0] = aLink1.FirstNode();
313     theNodes[1] = aLink1.LastNode();
314   }
315   else
316   {
317     theNodes[1] = aLink1.FirstNode();
318     theNodes[0] = aLink1.LastNode();
319   }
320   
321   const BRepMesh_Edge& aLink2 = GetLink(e[2]);
322   if (o[2])
323     theNodes[2] = aLink2.FirstNode();
324   else
325     theNodes[2] = aLink2.LastNode();
326 }
327
328 //=======================================================================
329 //function : ClearDomain
330 //purpose  : 
331 //=======================================================================
332 void BRepMesh_DataStructureOfDelaun::ClearDomain()
333 {
334   BRepMesh::MapOfInteger aFreeEdges;
335   BRepMesh::MapOfInteger::Iterator aElementIt(myElementsOfDomain);
336   for (; aElementIt.More(); aElementIt.Next())
337   {
338     const Standard_Integer aElementId = aElementIt.Key();
339     BRepMesh_Triangle& aElement = (BRepMesh_Triangle&)GetElement(aElementId);
340
341     Standard_Integer e[3];
342     Standard_Boolean o[3];
343     aElement.Edges(e, o);
344
345     for (Standard_Integer i = 0; i < 3; ++i)
346       aFreeEdges.Add(e[i]);
347
348     cleanElement(aElementId, aElement);
349     aElement.SetMovability(BRepMesh_Deleted);
350   }
351   myElementsOfDomain.Clear();
352
353   BRepMesh::MapOfInteger::Iterator aEdgeIt(aFreeEdges);
354   for (; aEdgeIt.More(); aEdgeIt.Next())
355     RemoveLink(aEdgeIt.Key());
356 }
357
358 //=======================================================================
359 //function : clearDeletedLinks
360 //purpose  : 
361 //=======================================================================
362 void BRepMesh_DataStructureOfDelaun::clearDeletedLinks()
363 {
364   Standard_Integer aLastLiveItem = NbLinks();
365   while (!myDelLinks.IsEmpty())
366   {
367     while (aLastLiveItem > 0)
368     {
369       if (GetLink(aLastLiveItem).Movability() != BRepMesh_Deleted)
370         break;
371
372       myLinks.RemoveLast();
373       --aLastLiveItem;
374     }
375
376     Standard_Integer aDelItem = myDelLinks.First();
377     myDelLinks.RemoveFirst();
378
379     if (aDelItem > aLastLiveItem)
380       continue;
381
382     BRepMesh_Edge aLink = GetLink(aLastLiveItem);
383     BRepMesh_PairOfIndex& aPair = myLinks(aLastLiveItem);
384
385     myLinks.RemoveLast();
386     myLinks.Substitute(aDelItem, aLink, aPair);
387
388     myLinksOfDomain.Remove(aLastLiveItem);
389     myLinksOfDomain.Add(aDelItem);
390     --aLastLiveItem;
391
392     const Standard_Integer aLastLiveItemId = aLastLiveItem + 1;
393     BRepMesh::ListOfInteger::Iterator aLinkIt;
394     // update link references
395     for (Standard_Integer i = 0; i < 2; ++i)
396     {
397       const Standard_Integer aCurNodeId = (i == 0) ?
398         aLink.FirstNode() : aLink.LastNode();
399
400       for (aLinkIt.Init(linksConnectedTo(aCurNodeId)); aLinkIt.More(); aLinkIt.Next())
401       {
402         Standard_Integer& aLinkId = aLinkIt.ChangeValue();
403         if (aLinkId == aLastLiveItemId)
404         {
405           aLinkId = aDelItem;
406           break;
407         }
408       }
409     }
410
411     // update elements references
412     for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j)
413     {
414       const BRepMesh_Triangle& aElement = GetElement(aPair.Index(j));
415
416       Standard_Integer e[3];
417       Standard_Boolean o[3];
418       aElement.Edges(e, o);
419       for (Standard_Integer i = 0; i < 3; ++i)
420       {
421         if (e[i] == aLastLiveItemId)
422         {
423           e[i] = aDelItem;
424           break;
425         }
426       }
427
428       myElements.Substitute(aLinkIt.Value(), 
429         BRepMesh_Triangle(e, o, aElement.Movability()));
430     }
431   }
432 }
433
434 //=======================================================================
435 //function : clearDeletedNodes
436 //purpose  : 
437 //=======================================================================
438 void BRepMesh_DataStructureOfDelaun::clearDeletedNodes()
439 {
440   BRepMesh::ListOfInteger& aDelNodes = 
441     (BRepMesh::ListOfInteger&)myNodes->GetListOfDelNodes();
442
443   Standard_Integer aLastLiveItem = NbNodes();
444   while (!aDelNodes.IsEmpty())
445   {
446     while (aLastLiveItem > 0)
447     {
448       if (GetNode(aLastLiveItem).Movability() != BRepMesh_Deleted)
449         break;
450
451       myNodes->RemoveLast();
452       --aLastLiveItem;
453     }
454
455     Standard_Integer aDelItem = aDelNodes.First();
456     aDelNodes.RemoveFirst();
457
458     if (aDelItem > aLastLiveItem)
459       continue;
460
461     BRepMesh_Vertex aNode = GetNode(aLastLiveItem);
462     BRepMesh::ListOfInteger& aLinkList = linksConnectedTo(aLastLiveItem);
463
464     myNodes->RemoveLast();
465     --aLastLiveItem;
466
467     myNodes->Substitute(aDelItem, aNode);
468     myNodeLinks.ChangeFind(aDelItem) = aLinkList;
469
470     const Standard_Integer aLastLiveItemId = aLastLiveItem + 1;
471     BRepMesh::ListOfInteger::Iterator aLinkIt(aLinkList);
472     for (; aLinkIt.More(); aLinkIt.Next())
473     {
474       const Standard_Integer aLinkId = aLinkIt.Value();
475       const BRepMesh_Edge& aLink = GetLink(aLinkId);
476       BRepMesh_PairOfIndex& aPair = myLinks(aLinkId);
477
478       Standard_Integer v[2] = { aLink.FirstNode(), aLink.LastNode() };
479       if (v[0] == aLastLiveItemId)
480         v[0] = aDelItem;
481       else if (v[1] == aLastLiveItemId)
482         v[1] = aDelItem;
483
484       myLinks.Substitute(aLinkId,
485         BRepMesh_Edge(v[0], v[1], aLink.Movability()), aPair);
486     }
487   }
488 }
489
490 //=======================================================================
491 //function : Statistics
492 //purpose  : 
493 //=======================================================================
494 void BRepMesh_DataStructureOfDelaun::Statistics(Standard_OStream& theStream) const
495 {
496   theStream << " Map of nodes : \n";
497   myNodes->Statistics(theStream);
498   theStream << "\n Deleted nodes : " << myNodes->GetListOfDelNodes().Extent() << endl;
499
500   theStream << "\n\n Map of Links : \n";
501   myLinks.Statistics(theStream);
502   theStream << "\n Deleted links : " << myDelLinks.Extent() << endl;
503
504   theStream << "\n\n Map of elements : \n";
505   myElements.Statistics(theStream);
506 }
507
508 //=======================================================================
509 //function : BRepMesh_Write
510 //purpose  : 
511 //  Global function not declared in any public header, intended for use 
512 //  from debugger prompt (Command Window in Visual Studio).
513 //
514 //  Stores the mesh data structure to BRep file with the given name.
515 //=======================================================================
516 Standard_CString BRepMesh_Dump(void*            theMeshHandlePtr,
517                                Standard_CString theFileNameStr)
518 {
519   if (theMeshHandlePtr == 0 || theFileNameStr == 0)
520   {
521     return "Error: file name or mesh data is null";
522   }
523
524   Handle(BRepMesh_DataStructureOfDelaun) aMeshData = 
525     *(Handle(BRepMesh_DataStructureOfDelaun)*)theMeshHandlePtr;
526
527   if (aMeshData.IsNull())
528     return "Error: mesh data is empty";
529
530   TopoDS_Compound aMesh;
531   BRep_Builder aBuilder;
532   aBuilder.MakeCompound(aMesh);
533
534   try
535   {
536     OCC_CATCH_SIGNALS
537
538     if (aMeshData->LinksOfDomain().IsEmpty())
539     {
540       const Standard_Integer aNodesNb = aMeshData->NbNodes();
541       for (Standard_Integer i = 1; i <= aNodesNb; ++i)
542       {
543         const gp_XY& aNode = aMeshData->GetNode(i).Coord();
544         gp_Pnt aPnt(aNode.X(), aNode.Y(), 0.);
545         aBuilder.Add(aMesh, BRepBuilderAPI_MakeVertex(aPnt));
546       }
547     }
548     else
549     {
550       BRepMesh::MapOfInteger::Iterator aLinksIt(aMeshData->LinksOfDomain());
551       for (; aLinksIt.More(); aLinksIt.Next())
552       {
553         const BRepMesh_Edge& aLink = aMeshData->GetLink(aLinksIt.Value());
554         gp_Pnt aPnt[2];
555         for (Standard_Integer i = 0; i < 2; ++i)
556         {
557           const Standard_Integer aNodeId = 
558             (i == 0) ? aLink.FirstNode() : aLink.LastNode();
559
560           const gp_XY& aNode = aMeshData->GetNode(aNodeId).Coord();
561           aPnt[i] = gp_Pnt(aNode.X(), aNode.Y(), 0.);
562         }
563
564         if (aPnt[0].SquareDistance(aPnt[1]) < Precision::SquareConfusion())
565           continue;
566
567         aBuilder.Add(aMesh, BRepBuilderAPI_MakeEdge(aPnt[0], aPnt[1]));
568       }
569     }
570
571     if (!BRepTools::Write(aMesh, theFileNameStr))
572       return "Error: write failed";
573   }
574   catch (Standard_Failure const& anException)
575   {
576     return anException.GetMessageString();
577   }
578
579   return theFileNameStr;
580 }