Cutting a cylinder with polygonal solid very slow

A bit of digging reveals the hotspot to be

void IntPolyh_Triangle::SetEdgeandOrientation(const Standard_Integer EdgeIndex, const IntPolyh_ArrayOfEdges &TEdges)
{
  const Standard_Integer FinTE = TEdges.NbItems();

  Standard_Integer PE1 =0,PE2 =0;

  Standard_Integer Test=1;

  if (EdgeIndex==1) { PE1=p1; PE2=p2; }
  else if (EdgeIndex==2) { PE1=p2; PE2=p3; }
  else if (EdgeIndex==3) { PE1=p3; PE2=p1; }
  else {
    Test=0;
  }
  if (Test!=0) {
    for(Standard_Integer iioo=0; iioo<FinTE; iioo++) {
      Standard_Integer EFP=TEdges[iioo].FirstPoint();
      if (EFP==PE1) {
    Standard_Integer ESP=TEdges[iioo].SecondPoint();
    if (ESP!=EFP) {
      if (ESP==PE2) {

-----------------------------------
The majority of the time is spent in
Standard_Integer EFP=TEdges[iioo].FirstPoint();
It seems that the loop is going around thousands of times checking edges in an exponential way

The main problem is the number of triangles in the two surface, there is almost 5000 in one and over 7000 in the other, this is caused by the triangulation of the cylinder. the code of SetEdgeandOrientation compares each of the 5000 with each of the 7000, leading to a considerable performance degradation. It appears that cylinders are being translated into a set of very fine resolution triangles and all are passing the bounding box filters so they are considered as candidates for edge reversal. Whats best, reduce the number of triangles or optimize this edge orientation code, maybe using maps?

Proposed Solution

Use a map of the edges to remove the large iterations

I have written the following new method for IntPolyh_Triangle, this uses a map to look up the pint indices. It is assuming we have less than 64K of points but we are in real trouble if we have anywhere near that anyway. Perhaps a map with longs would be easier but cannot see this in OCC.


The following method in IntPolyh_MaillageAffinage is also changed


void IntPolyh_Triangle::SetEdgeandOrientation(const Standard_Integer EdgeIndex, const TColStd_DataMapOfIntegerInteger& maps) {

    Standard_Integer PE1 = 0, PE2 = 0;
    Standard_Integer Test = 1;
    if (EdgeIndex == 1) { PE1 = p1; PE2 = p2; }
    else if (EdgeIndex == 2) { PE1 = p2; PE2 = p3; }
    else if (EdgeIndex == 3) { PE1 = p3; PE2 = p1; }
    else
    {
        Test = 0;
    }


    if (Test != 0)
    {
        Standard_Integer hashPoint = (PE1 << sizeof(unsigned short)) | (short)PE2;
        if (maps.IsBound(hashPoint))
        {
            Standard_Integer item = maps(hashPoint);
            //take the first one
            SetEdgeOrientation(EdgeIndex, 1);
            SetEdge(EdgeIndex, item);
        }
        else
        {
            hashPoint = (PE2 << sizeof(unsigned short)) | (short)PE1;
            if (maps.IsBound(hashPoint))
            {
                Standard_Integer item = maps(hashPoint);
                //take the first one
                SetEdgeOrientation(EdgeIndex, 1);
                SetEdge(EdgeIndex, item);
            }
        }
    }
}




The performance is significantly improved, from 2-3 minutes for the test case uploaded this site down to about 20 seconds

There was an error in the proposed function the SetEdgeOrientation reverse condition was incorrectly set to 1 instead of -1

void IntPolyh_Triangle::SetEdgeandOrientation(const Standard_Integer EdgeIndex, const TColStd_DataMapOfIntegerInteger& maps) {

    Standard_Integer PE1 = 0, PE2 = 0;
    Standard_Integer Test = 1;
    if (EdgeIndex == 1) { PE1 = p1; PE2 = p2; }
    else if (EdgeIndex == 2) { PE1 = p2; PE2 = p3; }
    else if (EdgeIndex == 3) { PE1 = p3; PE2 = p1; }
    else
    {
        Test = 0;
    }


    if (Test != 0)
    {
        Standard_Integer hashPoint = (PE1 << sizeof(unsigned short)) | (short)PE2;
        if (maps.IsBound(hashPoint))
        {
            Standard_Integer item = maps(hashPoint);
            //take the first one
            SetEdgeOrientation(EdgeIndex, 1);
            SetEdge(EdgeIndex, item);
        }
        else
        {
            hashPoint = (PE2 << sizeof(unsigned short)) | (short)PE1;
            if (maps.IsBound(hashPoint))
            {
                Standard_Integer item = maps(hashPoint);
                //take the first one
                SetEdgeOrientation(EdgeIndex, -1);
                SetEdge(EdgeIndex, item);
            }
        }
    }
}