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
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 #include <BRepMesh_DataStructureOfDelaun.hxx>
18 #include <BRepMesh_PairOfIndex.hxx>
19 #include <BRepBuilderAPI_MakeEdge.hxx>
20 #include <BRepBuilderAPI_MakeVertex.hxx>
22 #include <TopoDS_Compound.hxx>
23 #include <BRep_Builder.hxx>
24 #include <BRepTools.hxx>
25 #include <Standard_ErrorHandler.hxx>
28 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_DataStructureOfDelaun,Standard_Transient)
30 //=======================================================================
31 //function : BRepMesh_DataStructureOfDelaun
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)
48 //=======================================================================
49 //function : SubstituteNode
51 //=======================================================================
52 Standard_Integer BRepMesh_DataStructureOfDelaun::AddNode(
53 const BRepMesh_Vertex& theNode,
54 const Standard_Boolean isForceAdd)
56 const Standard_Integer aNodeId = myNodes->Add(theNode, isForceAdd);
57 if (!myNodeLinks.IsBound(aNodeId))
58 myNodeLinks.Bind(aNodeId, BRepMesh::ListOfInteger(myAllocator));
63 //=======================================================================
64 //function : SubstituteNode
66 //=======================================================================
67 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteNode(
68 const Standard_Integer theIndex,
69 const BRepMesh_Vertex& theNewNode)
71 if (myNodes->FindIndex(theNewNode) != 0)
72 return Standard_False;
74 myNodes->Substitute(theIndex, theNewNode);
78 //=======================================================================
81 //=======================================================================
82 Standard_Integer BRepMesh_DataStructureOfDelaun::AddLink(
83 const BRepMesh_Edge& theLink)
85 Standard_Integer aLinkIndex = IndexOf(theLink);
88 return theLink.IsSameOrientation(GetLink(aLinkIndex)) ?
89 aLinkIndex : -aLinkIndex;
92 BRepMesh_PairOfIndex aPair;
93 if (!myDelLinks.IsEmpty())
95 aLinkIndex = myDelLinks.First();
96 myLinks.Substitute(aLinkIndex, theLink, aPair);
97 myDelLinks.RemoveFirst();
100 aLinkIndex = myLinks.Add(theLink, aPair);
102 const Standard_Integer aLinkId = Abs(aLinkIndex);
103 linksConnectedTo(theLink.FirstNode()).Append(aLinkId);
104 linksConnectedTo(theLink.LastNode() ).Append(aLinkId);
105 myLinksOfDomain.Add(aLinkIndex);
110 //=======================================================================
111 //function : SubstituteLink
113 //=======================================================================
114 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteLink(
115 const Standard_Integer theIndex,
116 const BRepMesh_Edge& theNewLink)
118 BRepMesh_PairOfIndex aPair;
119 BRepMesh_Edge aLink = GetLink(theIndex);
120 if (aLink.Movability() == BRepMesh_Deleted)
122 myLinks.Substitute(theIndex, theNewLink, aPair);
123 return Standard_True;
126 if (IndexOf(theNewLink) != 0)
127 return Standard_False;
129 aLink.SetMovability(BRepMesh_Deleted);
130 myLinks.Substitute(theIndex, aLink, aPair);
131 cleanLink(theIndex, aLink);
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);
138 return Standard_True;
141 //=======================================================================
142 //function : ForceRemoveLink
144 //=======================================================================
145 void BRepMesh_DataStructureOfDelaun::RemoveLink(
146 const Standard_Integer theIndex,
147 const Standard_Boolean isForce)
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)
157 cleanLink(theIndex, aLink);
158 aLink.SetMovability(BRepMesh_Deleted);
160 myLinksOfDomain.Remove(theIndex);
161 myDelLinks.Append (theIndex);
164 //=======================================================================
165 //function : cleanLink
167 //=======================================================================
168 void BRepMesh_DataStructureOfDelaun::cleanLink(
169 const Standard_Integer theIndex,
170 const BRepMesh_Edge& theLink)
172 for (Standard_Integer i = 0; i < 2; ++i)
174 const Standard_Integer aNodeId = (i == 0) ?
175 theLink.FirstNode() : theLink.LastNode();
177 BRepMesh::ListOfInteger& aLinkList = linksConnectedTo(aNodeId);
178 BRepMesh::ListOfInteger::Iterator aLinkIt(aLinkList);
179 for(; aLinkIt.More(); aLinkIt.Next())
181 if (aLinkIt.Value() == theIndex)
183 aLinkList.Remove(aLinkIt);
190 //=======================================================================
191 //function : AddElement
193 //=======================================================================
194 Standard_Integer BRepMesh_DataStructureOfDelaun::AddElement(
195 const BRepMesh_Triangle& theElement)
197 Standard_Integer aElementIndex = IndexOf(theElement);
198 if (aElementIndex > 0)
199 return aElementIndex;
201 aElementIndex = myElements.Add(theElement);
202 myElementsOfDomain.Add(aElementIndex);
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);
210 return aElementIndex;
213 //=======================================================================
214 //function : RemoveElement
216 //=======================================================================
217 void BRepMesh_DataStructureOfDelaun::RemoveElement(
218 const Standard_Integer theIndex)
220 BRepMesh_Triangle& aElement = (BRepMesh_Triangle&)GetElement(theIndex);
221 if (aElement.Movability() == BRepMesh_Deleted)
224 cleanElement(theIndex, aElement);
225 aElement.SetMovability(BRepMesh_Deleted);
226 myElementsOfDomain.Remove(theIndex);
229 //=======================================================================
230 //function : cleanElement
232 //=======================================================================
233 void BRepMesh_DataStructureOfDelaun::cleanElement(
234 const Standard_Integer theIndex,
235 const BRepMesh_Triangle& theElement)
237 if (theElement.Movability() != BRepMesh_Free)
240 Standard_Integer e[3];
241 Standard_Boolean o[3];
242 theElement.Edges(e, o);
244 for (Standard_Integer i = 0; i < 3; ++i)
245 removeElementIndex(theIndex, myLinks(e[i]));
248 //=======================================================================
249 //function : removeElementIndex
251 //=======================================================================
252 void BRepMesh_DataStructureOfDelaun::removeElementIndex(
253 const Standard_Integer theIndex,
254 BRepMesh_PairOfIndex& thePair)
256 for (Standard_Integer i = 1, n = thePair.Extent(); i <= n; ++i)
258 if (thePair.Index(i) == theIndex)
260 thePair.RemoveIndex(i);
266 //=======================================================================
267 //function : SubstituteElement
269 //=======================================================================
270 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteElement(
271 const Standard_Integer theIndex,
272 const BRepMesh_Triangle& theNewElement)
274 const BRepMesh_Triangle& aElement = GetElement(theIndex);
275 if (aElement.Movability() == BRepMesh_Deleted)
277 myElements.Substitute(theIndex, theNewElement);
278 return Standard_True;
281 if (IndexOf(theNewElement) != 0)
282 return Standard_False;
284 cleanElement(theIndex, aElement);
285 // Warning: here new element and old element should have different Hash code
286 myElements.Substitute(theIndex, theNewElement);
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);
294 return Standard_True;
297 //=======================================================================
298 //function : ElementNodes
300 //=======================================================================
301 void BRepMesh_DataStructureOfDelaun::ElementNodes(
302 const BRepMesh_Triangle& theElement,
303 Standard_Integer (&theNodes)[3])
305 Standard_Integer e[3];
306 Standard_Boolean o[3];
307 theElement.Edges(e, o);
309 const BRepMesh_Edge& aLink1 = GetLink(e[0]);
312 theNodes[0] = aLink1.FirstNode();
313 theNodes[1] = aLink1.LastNode();
317 theNodes[1] = aLink1.FirstNode();
318 theNodes[0] = aLink1.LastNode();
321 const BRepMesh_Edge& aLink2 = GetLink(e[2]);
323 theNodes[2] = aLink2.FirstNode();
325 theNodes[2] = aLink2.LastNode();
328 //=======================================================================
329 //function : ClearDomain
331 //=======================================================================
332 void BRepMesh_DataStructureOfDelaun::ClearDomain()
334 BRepMesh::MapOfInteger aFreeEdges;
335 BRepMesh::MapOfInteger::Iterator aElementIt(myElementsOfDomain);
336 for (; aElementIt.More(); aElementIt.Next())
338 const Standard_Integer aElementId = aElementIt.Key();
339 BRepMesh_Triangle& aElement = (BRepMesh_Triangle&)GetElement(aElementId);
341 Standard_Integer e[3];
342 Standard_Boolean o[3];
343 aElement.Edges(e, o);
345 for (Standard_Integer i = 0; i < 3; ++i)
346 aFreeEdges.Add(e[i]);
348 cleanElement(aElementId, aElement);
349 aElement.SetMovability(BRepMesh_Deleted);
351 myElementsOfDomain.Clear();
353 BRepMesh::MapOfInteger::Iterator aEdgeIt(aFreeEdges);
354 for (; aEdgeIt.More(); aEdgeIt.Next())
355 RemoveLink(aEdgeIt.Key());
358 //=======================================================================
359 //function : clearDeletedLinks
361 //=======================================================================
362 void BRepMesh_DataStructureOfDelaun::clearDeletedLinks()
364 Standard_Integer aLastLiveItem = NbLinks();
365 while (!myDelLinks.IsEmpty())
367 while (aLastLiveItem > 0)
369 if (GetLink(aLastLiveItem).Movability() != BRepMesh_Deleted)
372 myLinks.RemoveLast();
376 Standard_Integer aDelItem = myDelLinks.First();
377 myDelLinks.RemoveFirst();
379 if (aDelItem > aLastLiveItem)
382 BRepMesh_Edge aLink = GetLink(aLastLiveItem);
383 BRepMesh_PairOfIndex& aPair = myLinks(aLastLiveItem);
385 myLinks.RemoveLast();
386 myLinks.Substitute(aDelItem, aLink, aPair);
388 myLinksOfDomain.Remove(aLastLiveItem);
389 myLinksOfDomain.Add(aDelItem);
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)
397 const Standard_Integer aCurNodeId = (i == 0) ?
398 aLink.FirstNode() : aLink.LastNode();
400 for (aLinkIt.Init(linksConnectedTo(aCurNodeId)); aLinkIt.More(); aLinkIt.Next())
402 Standard_Integer& aLinkId = aLinkIt.ChangeValue();
403 if (aLinkId == aLastLiveItemId)
411 // update elements references
412 for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j)
414 const BRepMesh_Triangle& aElement = GetElement(aPair.Index(j));
416 Standard_Integer e[3];
417 Standard_Boolean o[3];
418 aElement.Edges(e, o);
419 for (Standard_Integer i = 0; i < 3; ++i)
421 if (e[i] == aLastLiveItemId)
428 myElements.Substitute(aLinkIt.Value(),
429 BRepMesh_Triangle(e, o, aElement.Movability()));
434 //=======================================================================
435 //function : clearDeletedNodes
437 //=======================================================================
438 void BRepMesh_DataStructureOfDelaun::clearDeletedNodes()
440 BRepMesh::ListOfInteger& aDelNodes =
441 (BRepMesh::ListOfInteger&)myNodes->GetListOfDelNodes();
443 Standard_Integer aLastLiveItem = NbNodes();
444 while (!aDelNodes.IsEmpty())
446 while (aLastLiveItem > 0)
448 if (GetNode(aLastLiveItem).Movability() != BRepMesh_Deleted)
451 myNodes->RemoveLast();
455 Standard_Integer aDelItem = aDelNodes.First();
456 aDelNodes.RemoveFirst();
458 if (aDelItem > aLastLiveItem)
461 BRepMesh_Vertex aNode = GetNode(aLastLiveItem);
462 BRepMesh::ListOfInteger& aLinkList = linksConnectedTo(aLastLiveItem);
464 myNodes->RemoveLast();
467 myNodes->Substitute(aDelItem, aNode);
468 myNodeLinks.ChangeFind(aDelItem) = aLinkList;
470 const Standard_Integer aLastLiveItemId = aLastLiveItem + 1;
471 BRepMesh::ListOfInteger::Iterator aLinkIt(aLinkList);
472 for (; aLinkIt.More(); aLinkIt.Next())
474 const Standard_Integer aLinkId = aLinkIt.Value();
475 const BRepMesh_Edge& aLink = GetLink(aLinkId);
476 BRepMesh_PairOfIndex& aPair = myLinks(aLinkId);
478 Standard_Integer v[2] = { aLink.FirstNode(), aLink.LastNode() };
479 if (v[0] == aLastLiveItemId)
481 else if (v[1] == aLastLiveItemId)
484 myLinks.Substitute(aLinkId,
485 BRepMesh_Edge(v[0], v[1], aLink.Movability()), aPair);
490 //=======================================================================
491 //function : Statistics
493 //=======================================================================
494 void BRepMesh_DataStructureOfDelaun::Statistics(Standard_OStream& theStream) const
496 theStream << " Map of nodes : \n";
497 myNodes->Statistics(theStream);
498 theStream << "\n Deleted nodes : " << myNodes->GetListOfDelNodes().Extent() << endl;
500 theStream << "\n\n Map of Links : \n";
501 myLinks.Statistics(theStream);
502 theStream << "\n Deleted links : " << myDelLinks.Extent() << endl;
504 theStream << "\n\n Map of elements : \n";
505 myElements.Statistics(theStream);
508 //=======================================================================
509 //function : BRepMesh_Write
511 // Global function not declared in any public header, intended for use
512 // from debugger prompt (Command Window in Visual Studio).
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)
519 if (theMeshHandlePtr == 0 || theFileNameStr == 0)
521 return "Error: file name or mesh data is null";
524 Handle(BRepMesh_DataStructureOfDelaun) aMeshData =
525 *(Handle(BRepMesh_DataStructureOfDelaun)*)theMeshHandlePtr;
527 if (aMeshData.IsNull())
528 return "Error: mesh data is empty";
530 TopoDS_Compound aMesh;
531 BRep_Builder aBuilder;
532 aBuilder.MakeCompound(aMesh);
538 if (aMeshData->LinksOfDomain().IsEmpty())
540 const Standard_Integer aNodesNb = aMeshData->NbNodes();
541 for (Standard_Integer i = 1; i <= aNodesNb; ++i)
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));
550 BRepMesh::MapOfInteger::Iterator aLinksIt(aMeshData->LinksOfDomain());
551 for (; aLinksIt.More(); aLinksIt.Next())
553 const BRepMesh_Edge& aLink = aMeshData->GetLink(aLinksIt.Value());
555 for (Standard_Integer i = 0; i < 2; ++i)
557 const Standard_Integer aNodeId =
558 (i == 0) ? aLink.FirstNode() : aLink.LastNode();
560 const gp_XY& aNode = aMeshData->GetNode(aNodeId).Coord();
561 aPnt[i] = gp_Pnt(aNode.X(), aNode.Y(), 0.);
564 if (aPnt[0].SquareDistance(aPnt[1]) < Precision::SquareConfusion())
567 aBuilder.Add(aMesh, BRepBuilderAPI_MakeEdge(aPnt[0], aPnt[1]));
571 if (!BRepTools::Write(aMesh, theFileNameStr))
572 return "Error: write failed";
574 catch (Standard_Failure const& anException)
576 return anException.GetMessageString();
579 return theFileNameStr;