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