MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0026557Community[OCCT] OCCT:Modeling Algorithmspublic2015-08-12 19:222016-02-10 01:52
Reportersrlockley 
Assigned Topkv 
PrioritynormalSeveritymajor 
StatusassignedResolutionopen 
PlatformWindowsOSVC++ 2013OS Version32 bit
Product Version[OCCT] 6.9.0 
Target VersionFixed in Version 
Summary0026557: Cutting a cylinder with polygonal solid very slow
DescriptionWhen a polygonal shape is used to cut a cylinder performance significantly degrades. Performance for a simple cut can be several minutes.
Steps To ReproduceThree files are uploaded. The Cylinder file contains a brep of pipe with an inner wall. The Cut1 file contains a polygonal or faceted solid with no curved surfaces or edges
Using
Bop Cylinder Cut1
BopCut result

will show the performance degradation

Also uploaded is a brep Rectangular, replace Cylinder with this to see normal performance.

Bop Rectangular Cut1
BopCut result
TagsNo tags attached.
Test case number
Attached Fileszip file icon SlowCut.zip (102,288 bytes) 2015-08-12 19:22

- Relationships

-  Notes
(0044108)
srlockley (reporter)
2015-08-13 20:02

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
(0044323)
srlockley (reporter)
2015-08-14 17:54

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?
(0044326)
srlockley (reporter)
2015-08-14 20:08

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
(0044330)
srlockley (reporter)
2015-08-15 09:29

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);
            }
        }
    }
}

- Issue History
Date Modified Username Field Change
2015-08-12 19:22 srlockley New Issue
2015-08-12 19:22 srlockley Assigned To => msv
2015-08-12 19:22 srlockley File Added: SlowCut.zip
2015-08-13 15:46 srlockley Assigned To msv => jgv
2015-08-13 15:50 jgv Assigned To jgv => pkv
2015-08-13 20:02 srlockley Note Added: 0044108
2015-08-14 06:02 pkv Status new => assigned
2015-08-14 17:54 srlockley Note Added: 0044323
2015-08-14 20:08 srlockley Note Added: 0044326
2015-08-15 09:29 srlockley Note Added: 0044330


Copyright © 2000 - 2021 MantisBT Team
Powered by Mantis Bugtracker