-// File: Poly_Connect.cxx
-// Created: Mon Mar 6 16:30:09 1995
-// Author: Laurent PAINNOT
-// <lpa@metrox>
-
-
-#include <Poly_Connect.ixx>
+// Created on: 1995-03-06
+// Created by: Laurent PAINNOT
+// Copyright (c) 1995-1999 Matra Datavision
+// Copyright (c) 1999-2014 OPEN CASCADE SAS
+//
+// This file is part of Open CASCADE Technology software library.
+//
+// This library is free software; you can redistribute it and/or modify it under
+// the terms of the GNU Lesser General Public License version 2.1 as published
+// by the Free Software Foundation, with special exception defined in the file
+// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
+// distribution for complete text of the license and disclaimer of any warranty.
+//
+// Alternatively, this file may be used under the terms of Open CASCADE
+// commercial license or contractual agreement.
+
+#include <Poly_Connect.hxx>
+
+#include <NCollection_IncAllocator.hxx>
#include <Poly_Triangle.hxx>
+#include <Poly_Triangulation.hxx>
-#include <Standard.hxx>
+// this structure records one of the edges starting from a node
+struct polyedge
+{
+ polyedge* next; // the next edge in the list
+ Standard_Integer nt[2]; // the two adjacent triangles
+ Standard_Integer nn[2]; // the two adjacent nodes
+ Standard_Integer nd; // the second node of the edge
+ DEFINE_STANDARD_ALLOC
+};
+//=======================================================================
+//function : Poly_Connect
+//purpose :
+//=======================================================================
+Poly_Connect::Poly_Connect()
+: mytr (0),
+ myfirst (0),
+ mynode (0),
+ myothernode (0),
+ mysense (false),
+ mymore (false)
+{
+ //
+}
//=======================================================================
//function : Poly_Connect
-//purpose :
+//purpose :
//=======================================================================
-// this structure records one of the edges starting from a node
+Poly_Connect::Poly_Connect(const Handle(Poly_Triangulation)& theTriangulation)
+: myTriangulation (theTriangulation),
+ myTriangles (1, theTriangulation->NbNodes()),
+ myAdjacents (1, 6 * theTriangulation->NbTriangles()),
+ mytr (0),
+ myfirst (0),
+ mynode (0),
+ myothernode (0),
+ mysense (false),
+ mymore (false)
+{
+ Load (theTriangulation);
+}
-//typedef struct polyedge {
-struct polyedge {
- polyedge* next; // the next edge in the list
- Standard_Integer nd; // the second node of the edge
- Standard_Integer nt[2]; // the two adjacent triangles
- Standard_Integer nn[2]; // the two adjacent nodes
- void* operator new(size_t aSize)
- {return (void*)(Standard::Allocate(aSize));}
-// void operator delete(void* aNode, size_t aSize) {
- void operator delete(void* aNode) {
- Standard_Address anAdress = (Standard_Address)aNode;
- Standard::Free(anAdress);
+//=======================================================================
+//function : Load
+//purpose :
+//=======================================================================
+void Poly_Connect::Load (const Handle(Poly_Triangulation)& theTriangulation)
+{
+ myTriangulation = theTriangulation;
+ mytr = 0;
+ myfirst = 0;
+ mynode = 0;
+ myothernode = 0;
+ mysense = false;
+ mymore = false;
+
+ const Standard_Integer aNbNodes = myTriangulation->NbNodes();
+ const Standard_Integer aNbTris = myTriangulation->NbTriangles();
+ {
+ const Standard_Integer aNbAdjs = 6 * aNbTris;
+ if (myTriangles.Size() != aNbNodes)
+ {
+ myTriangles.Resize (1, aNbNodes, Standard_False);
}
- };
+ if (myAdjacents.Size() != aNbAdjs)
+ {
+ myAdjacents.Resize (1, aNbAdjs, Standard_False);
+ }
+ }
-Poly_Connect::Poly_Connect(const Handle(Poly_Triangulation)& T) :
- myTriangulation(T),
- myTriangles(1,T->NbNodes()),
- myAdjacents(1,6*T->NbTriangles())
-{
myTriangles.Init(0);
myAdjacents.Init(0);
- Standard_Integer nbNodes = myTriangulation->NbNodes();
- Standard_Integer nbTriangles = myTriangulation->NbTriangles();
// We first build an array of the list of edges connected to the nodes
-
-
-
// create an array to store the edges starting from the vertices
-
- Standard_Integer i;
- // the last node is not used because edges are stored at the lower node index
- polyedge** edges = new polyedge*[nbNodes];
- for (i = 0; i < nbNodes; i++) edges[i] = 0;
-
+ NCollection_Array1<polyedge*> anEdges (1, aNbNodes);
+ anEdges.Init (NULL);
+ // use incremental allocator for small allocations
+ Handle(NCollection_IncAllocator) anIncAlloc = new NCollection_IncAllocator();
// loop on the triangles
- Standard_Integer j,k,n[3],n1,n2;
- const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
-
- for (i = 1; i <= nbTriangles; i++) {
-
+ NCollection_Vec3<Standard_Integer> aTriNodes;
+ NCollection_Vec2<Standard_Integer> anEdgeNodes;
+ for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
+ {
// get the nodes
- triangles(i).Get(n[0],n[1],n[2]);
+ myTriangulation->Triangle (aTriIter).Get (aTriNodes[0], aTriNodes[1], aTriNodes[2]);
// Update the myTriangles array
- myTriangles(n[0]) = i;
- myTriangles(n[1]) = i;
- myTriangles(n[2]) = i;
+ myTriangles.SetValue (aTriNodes[0], aTriIter);
+ myTriangles.SetValue (aTriNodes[1], aTriIter);
+ myTriangles.SetValue (aTriNodes[2], aTriIter);
// update the edge lists
- for (j = 0; j < 3; j++) {
- k = (j+1) % 3; // the following node of the edge
- if (n[j] <= n[k]) {
- n1 = n[j];
- n2 = n[k];
+ for (Standard_Integer aNodeInTri = 0; aNodeInTri < 3; ++aNodeInTri)
+ {
+ const Standard_Integer aNodeNext = (aNodeInTri + 1) % 3; // the following node of the edge
+ if (aTriNodes[aNodeInTri] < aTriNodes[aNodeNext])
+ {
+ anEdgeNodes[0] = aTriNodes[aNodeInTri];
+ anEdgeNodes[1] = aTriNodes[aNodeNext];
}
- else {
- n1 = n[k];
- n2 = n[j];
+ else
+ {
+ anEdgeNodes[0] = aTriNodes[aNodeNext];
+ anEdgeNodes[1] = aTriNodes[aNodeInTri];
}
- // edge from n1 to n2 with n1 < n2
- // insert in the list of n1
-
- polyedge* ced = edges[n1];
- while (ced != 0) {
- // the edge already exists
- if (ced->nd == n2)
- break;
- else
- ced = ced->next;
+ // edge from node 0 to node 1 with node 0 < node 1
+ // insert in the list of node 0
+ polyedge* ced = anEdges[anEdgeNodes[0]];
+ for (; ced != NULL; ced = ced->next)
+ {
+ // the edge already exists
+ if (ced->nd == anEdgeNodes[1])
+ {
+ // just mark the adjacency if found
+ ced->nt[1] = aTriIter;
+ ced->nn[1] = aTriNodes[3 - aNodeInTri - aNodeNext]; // the third node
+ break;
+ }
}
- if (ced == 0) {
- // create the edge if not found
- ced = new polyedge;
- ced->next = edges[n1];
- edges[n1] = ced;
- ced->nd = n2;
- ced->nt[0] = i;
- ced->nn[0] = n[3-j-k]; // the third node
- ced->nt[1] = 0;
- ced->nn[1] = 0;
- }
- else {
- // just mark the adjacency if found
- ced->nt[1] = i;
- ced->nn[1] = n[3-j-k]; // the third node
+ if (ced == NULL)
+ {
+ // create the edge if not found
+ ced = (polyedge* )anIncAlloc->Allocate (sizeof(polyedge));
+ ced->next = anEdges[anEdgeNodes[0]];
+ anEdges[anEdgeNodes[0]] = ced;
+ ced->nd = anEdgeNodes[1];
+ ced->nt[0] = aTriIter;
+ ced->nn[0] = aTriNodes[3 - aNodeInTri - aNodeNext]; // the third node
+ ced->nt[1] = 0;
+ ced->nn[1] = 0;
}
}
}
-
// now complete the myAdjacents array
-
- Standard_Integer index = 1;
- for (i = 1; i <= nbTriangles; i++) {
-
+ Standard_Integer anAdjIndex = 1;
+ for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
+ {
// get the nodes
- triangles(i).Get(n[0],n[1],n[2]);
-
- // fore each edge
- for (j = 0; j < 3; j++) {
- k = (j+1) % 3; // the following node of the edge
- if (n[j] <= n[k]) {
- n1 = n[j];
- n2 = n[k];
+ myTriangulation->Triangle (aTriIter).Get (aTriNodes[0], aTriNodes[1], aTriNodes[2]);
+
+ // for each edge in triangle
+ for (Standard_Integer aNodeInTri = 0; aNodeInTri < 3; ++aNodeInTri)
+ {
+ const Standard_Integer aNodeNext = (aNodeInTri + 1) % 3; // the following node of the edge
+ if (aTriNodes[aNodeInTri] < aTriNodes[aNodeNext])
+ {
+ anEdgeNodes[0] = aTriNodes[aNodeInTri];
+ anEdgeNodes[1] = aTriNodes[aNodeNext];
}
- else {
- n1 = n[k];
- n2 = n[j];
+ else
+ {
+ anEdgeNodes[0] = aTriNodes[aNodeNext];
+ anEdgeNodes[1] = aTriNodes[aNodeInTri];
}
- // edge from n1 to n2 with n1 < n2
- // find in the list of n1
-
- polyedge* ced = edges[n1];
- while (ced->nd != n2)
- ced = ced->next;
+ // edge from node 0 to node 1 with node 0 < node 1
+ // find in the list of node 0
+ const polyedge* ced = anEdges[anEdgeNodes[0]];
+ while (ced->nd != anEdgeNodes[1])
+ {
+ ced = ced->next;
+ }
// Find the adjacent triangle
- Standard_Integer l = 0;
- if (ced->nt[0] == i) l = 1;
-
- myAdjacents(index) = ced->nt[l];
- myAdjacents(index+3) = ced->nn[l];
- index++;
- }
- index += 3;
- }
+ const Standard_Integer l = ced->nt[0] == aTriIter ? 1 : 0;
- // destroy the edges array
- for (i = 0; i < nbNodes; i++) {
- polyedge* ced = edges[i];
- while (ced != 0) {
- polyedge* tmp = ced->next;
- delete ced;
- ced = tmp;
+ myAdjacents.SetValue (anAdjIndex, ced->nt[l]);
+ myAdjacents.SetValue (anAdjIndex + 3, ced->nn[l]);
+ ++anAdjIndex;
}
+ anAdjIndex += 3;
}
- delete [] edges;
-}
-
-//=======================================================================
-//function : Triangles
-//purpose :
-//=======================================================================
-
-void Poly_Connect::Triangles(const Standard_Integer T,
- Standard_Integer& t1,
- Standard_Integer& t2,
- Standard_Integer& t3) const
-{
- Standard_Integer index = 6*(T-1);
- t1 = myAdjacents(index+1);
- t2 = myAdjacents(index+2);
- t3 = myAdjacents(index+3);
-}
-
-//=======================================================================
-//function : Nodes
-//purpose :
-//=======================================================================
-void Poly_Connect::Nodes(const Standard_Integer T,
- Standard_Integer& n1,
- Standard_Integer& n2,
- Standard_Integer& n3) const
-{
- Standard_Integer index = 6*(T-1);
- n1 = myAdjacents(index+4);
- n2 = myAdjacents(index+5);
- n3 = myAdjacents(index+6);
+ // destroy the edges array - can be skipped when using NCollection_IncAllocator
+ /*for (Standard_Integer aNodeIter = anEdges.Lower(); aNodeIter <= anEdges.Upper(); ++aNodeIter)
+ {
+ for (polyedge* anEdgeIter = anEdges[aNodeIter]; anEdgeIter != NULL;)
+ {
+ polyedge* aTmp = anEdgeIter->next;
+ anIncAlloc->Free (anEdgeIter);
+ anEdgeIter = aTmp;
+ }
+ }*/
}
-
//=======================================================================
//function : Initialize
//purpose :
void Poly_Connect::Next()
{
Standard_Integer i, j;
- static Standard_Integer n[3];
- static Standard_Integer t[3];
+ Standard_Integer n[3];
+ Standard_Integer t[3];
const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
Triangles(mytr, t[0], t[1], t[2]);
if (mysense) {
}
mymore = Standard_False;
}
-
-
-//=======================================================================
-//function : Value
-//purpose :
-//=======================================================================
-
-Standard_Integer Poly_Connect::Value() const
-{
- return mytr;
-}