View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0026310CommunityOCCT:Modeling Algorithmspublic2015-06-04 09:572015-10-23 20:51
Reportersrlockley Assigned Tobugmaster  
PrioritynormalSeveritymajor 
Status closedResolutionfixed 
PlatformWindowsOSVC++ 2013 
Product Version7.1.0 
Target Version6.9.1Fixed in Version6.9.1 
Summary0026310: Very slow boolean cut operations on cylinders
DescriptionVery slow response on cutting operations between 2 cylinders and also any half space cutting operations with semi-infinite prisms that have curved edges on the swept face.The result of the boolean is also a fail, typically returning the original body shape

I have uploaded the two shape files b and c where b is the body shape and c is the tool to cut with.
Steps To ReproduceBranch CR26310_1 already contains four test cases.

Dear testers,

Please make following:
1. Add necessary heads in every test script
2. Show res1 and res2 (in bug26310_3 and bug26310_4) in SEPARATED picture (i.e. res1 in one picture, res2 in second).

And other necessary actions.
Additional information
and documentation updates		Attention!

Three test cases have been created and pushed to the branch.


It appears that they are incredibly slow in most circumstances. For cylinders it seems to be related to the resolution of the step size in IntCyCyTrim. Basically for my models the code which increments the variable 'anU1' only increments it by a very small amount each time (~0.003). This is because the variable 'aMinUexp' is always a small variation of the previous value due to the step variable.

In the code there is a while loop starting at line 2368 of file IntPatch_ImpImpIntersection_4.gxx

while(anU1 <= anUl){
.....
}

The issue is that 'anU1' takes thousands of iterations before it is less than 'anUl' for simple cylinders. This can take minutes up to hours to complete depending on the size of the shape, for example semi-infinite prisms can take up to an hour to complete. I have raised the query on the OCC main forum and been requested to re-raise it here.Attached are a pair of cylinders produced by BRepTools::Write that reproduce the problem. If the Cut operation of c from b is executed on 6.5.4 in draw.exe everything runs as expected and quickly. On 6.9.0 the performance is very slow and instead of returning the result shape, the original body is returned, no cut is performed.

I have found that with semi-infinite prisms that have non planar surfaces the same problem occurs but can be reduced significantly by making the prism finite and with a much smaller extrusion. It leads me to believe that the step that is calculated for iterating around the curve of the solid is small compared to the size of the extrusion and causes many executions. This is a wild guess though.

Hope this is enough information and someone can help, I have tried to debug the code and find the reason but it is a little beyond my understanding, I know from performance analysis the time is consumed by the single function CylCylComputeParameters however i think this is simply because it is being called many, many times.
TagsNo tags attached.
Test case numberbugs modalg_6 bug26310_1, bug26310_2, bug26310_3, bug26310_4

Attached Files

  • cylinders.zip (1,421 bytes)
  • b1b2cut.PNG (74,246 bytes)
  • b2b1cut.PNG (72,629 bytes)

Relationships

related to 0025929 closedbugmaster Open CASCADE Make Approx_ComputeLine algorithm adaptive 
related to 0026447 closedbugmaster Community Performance degradation intersecting cylindrical surfaces 

Activities

srlockley

2015-06-04 09:57

reporter  

cylinders.zip (1,421 bytes)

git

2015-07-06 15:56

administrator   ~0042757

Branch CR26310 has been created by nbv.

SHA-1: 20d299b38716bddbc6155007a047bfaa96522499


Detailed log of new commits:

Author: nbv
Date: Fri Jul 3 15:51:54 2015 +0300

    0026310: Very slow boolean cut operations on cylinders
    
    1. JoinWLines algorithm has been improved.
    2. Reference to the V-boundaries is deleted when computing step.
    3. Decreasing the tolerance when computing parameters of WLine.
    4. Adding boundary point is forbidden if it lies in prolongation of found ones.
    5. Possible reason of exception has been eliminated.
    6. Processing of critical point has been improved.
    
    Test cases for this issue have been created.
    Correction of some test case(s).

nbv

2015-07-06 15:59

developer   ~0042758

Dear Mikhail,

Please review CR26310 branch.

abv

2015-07-06 16:36

manager   ~0042759

Nikolai, does your fix solve the original problem? Please share the times to show whether performance has increased, and how much.

nbv

2015-07-06 17:01

developer   ~0042760

Last edited: 2015-07-06 17:24

 Andrei,

See test case bugs\modalg_6\bug26310_1 (performance meter).
On MASTER this computation takes >1.5s. On CR26310 branch it takes <0.1s.

I am sure that there is no point in counting, how many times CylCylComputeParameters() function is called.

Nevertheless, I have following statistic:
On MASTER this function is called > 500000 times;
On CR26310 this function is called 4412 times.

git

2015-07-07 09:36

administrator   ~0042772

Branch CR26310 has been updated by nbv.

SHA-1: a80950b4522f81a337122f97cb62346d93ec09b3


Detailed log of new commits:

Author: nbv
Date: Tue Jul 7 09:36:31 2015 +0300

    Small correction

srlockley

2015-07-14 10:05

reporter   ~0042989

This is fantastic news and thank you for your efforts. Is it possible to get these changes as a patch or is it necessary to wait for release 7.1?

msv

2015-07-14 10:43

developer   ~0042991

srlockley, it is up to you.
- You can get the patch from git branch CR26310. But be aware it is not yet certified.
- You cat wait for it is put in master branch.
- You can wait till release.
It depends on your way of working with OCCT.

msv

2015-07-14 20:09

developer   ~0043019

Remarks:

src\IntPatch\IntPatch_ImpImpIntersection_4.gxx
- lines 2156-2160 can be excluded if we initialize always with positive infinite.
- lines 2487-2490 are extra, since all points are inscribed in CriticalPointsComputing.
- line 2492 sorts the same constant array on each iteration. I propose to move this sorting inside CriticalPointsComputing.
- line 2906:
            if(IsEqual(anUmaxAdded, RealFirst()))
change to:
            if(! (anUmaxAdded > RealFirst()) )

src\IntPatch\IntPatch_Intersection.cxx
- In the method IsSeam, checking for IsEqual(aVal2, aPar1) is absent.

abv

2015-07-14 20:28

manager   ~0043020

Mikhail, can you comment on the reason to have strange comparisons like this:

 if(! (anUmaxAdded > RealFirst()) )

Current variant:

 if(IsEqual(anUmaxAdded, RealFirst()))


looks like anUmaxAdded has special value RealFirst() indicating that it is not initialized or somewhat of the kind... but your variant looks just weird.

Looking in the code, I see that my guess was correct. My advise is to use Boolan flag to clearly define the status: performance will not suffer that much, but you will save good time of the next developer who will stare at this code.

Please, please, PLEASE try to make your code clear, at least, insert comments describing non-trivial things!

msv

2015-07-15 09:16

developer   ~0043022

This thing is really trivial!
anUMaxAdded is initialized with RealFirst(), then a loop is done to find a maximal value. The discussed condition just checks if the value was modified or not. The initial expression IsEqual(anUmaxAdded, RealFirst()) involves calculation of difference, absolute value, and comparison with RealSmall(). This really seemed weird for me.

nbv

2015-07-15 09:27

developer   ~0043023

I agree with Mikhail (http://tracker.dev.opencascade.org/view.php?id=26310#c43022). Comparing with RealFirst() in this context is used only for indication if anUmaxAdded were changed during cycle execution.

abv

2015-07-15 09:35

manager   ~0043027

On, then why not " if (anUmaxAdded == RealFirst())"??

msv

2015-07-15 10:22

developer   ~0043035

OK, we can compare using "==", I agree that such expression will look more clear, but I always try to avoid using operator == with float numbers.

git

2015-07-15 10:59

administrator   ~0043039

Branch CR26310 has been updated forcibly by nbv.

SHA-1: f6675b73ddce4fb37ee002aee39a5bb00ff5fa8a

nbv

2015-07-15 11:02

developer   ~0043040

Dear Mikhail,

Please review the current state of CR26310 branch.

git

2015-07-15 13:59

administrator   ~0043060

Branch CR26310_1 has been created by nbv.

SHA-1: 43010d47ee7ed81696bb070a34b8e7baba61e5dd


Detailed log of new commits:

Author: nbv
Date: Wed Jul 15 13:47:53 2015 +0300

    0026310: Very slow boolean cut operations on cylinders
    
    1. JoinWLines algorithm has been improved.
    2. Reference to the V-boundaries is deleted when computing step.
    3. Decreasing the tolerance when computing parameters of WLine.
    4. Adding boundary point is forbidden if it lies in prolongation of found ones.
    5. Possible reason of exception has been eliminated.
    6. Processing of critical point has been improved.
    
    Test cases for this issue have been created.
    Correction of some test case(s).

nbv

2015-07-15 14:00

developer   ~0043061

Dear Mikhail,

Please review CR26310_1 branch.

msv

2015-07-15 16:27

developer   ~0043074

Reviewed.

msv

2015-07-15 16:28

developer   ~0043075

Andrey, concerning your remark, we followed your advise to use Boolean flag.

srlockley

2015-07-15 21:02

reporter   ~0043088

Last edited: 2015-07-16 09:04

 Dear all, I have downloaded the fix you have kindly done so far and applied it in my application. Performance seems much better, unfortunately the actual boolean cut operation is not happening. When the small cylinder, in my previously uploaded test case is subtracted from the large one, it simply returns the large cylinder unchanged. Is this definitely not happening in your test case? does my test case now work for you. If it is I wonder if I have to add some other previous patches to get the boolean cut to work?

srlockley

2015-07-16 09:01

reporter   ~0043092

Last edited: 2015-07-16 09:04

 Having reviewed other reports I wonder if the failure to cut problem I am experiencing is the same as 0025542. The axis of the small cylinder lies in the plane of the large cylinders circular face

nbv

2015-07-16 09:41

developer   ~0043096

Dear srlockley,

I cannot reproduce your problem on CR26310_1 branch. My result seems to be OK.

Try the following DRAW-scripts:

SCRIPT # 1:
See tests/bugs/modalg_6/bug26310_3 in CR26310_1 branch.
You can see the result in the b1b2cut.png attached picture.

SCRIPT # 2:

Draw[]> restore [locate_data_file bug26310_b1.brep] b1
Draw[]> restore [locate_data_file bug26310_b2.brep] b2
Draw[]> bop b2 b1
Draw[]> bopcut res1
Draw[]> boptuc res2

You can see the result in the b2b1cut.png attached picture.

nbv

2015-07-16 09:42

developer  

b1b2cut.PNG (74,246 bytes)

nbv

2015-07-16 09:42

developer  

b2b1cut.PNG (72,629 bytes)

git

2015-07-16 10:04

administrator   ~0043098

Branch CR26310_1 has been updated by nbv.

SHA-1: cebb62d71efe5f495f7b6e3ef4a4dbf1921b628e


Detailed log of new commits:

Author: nbv
Date: Thu Jul 16 10:03:12 2015 +0300

    Test case bugs/modalg_6/bug26310_4 is added

nbv

2015-07-16 10:06

developer   ~0043099

Dear Mikhail,

Please review bugs/modalg_6/bug26310_4 test case in CR26310_1 branch.

git

2015-07-16 10:53

administrator   ~0043102

Branch CR26310_1 has been updated forcibly by nbv.

SHA-1: 4496f22e22421e7f35ab617a2d5519ec3651c903

nbv

2015-07-16 11:03

developer   ~0043104

"Steps To Reproduce" and "Additional information and documentation updates" have been corrected.

msv

2015-07-16 11:08

developer   ~0043105

Reviewed.

srlockley

2015-07-18 00:46

reporter   ~0043171

I have now built the whole branch and checked against my application, everything works correctly, the failure to cut was fixed by a separate prior bug fix which I have now included. Thanks again for your help with this.

Steve

git

2015-07-22 13:32

administrator   ~0043286

Branch CR26310_1 has been updated by apv.

SHA-1: 9943066a7a67299e762c28247fe5b3c341ed853f


Detailed log of new commits:

Author: apv
Date: Wed Jul 22 13:31:45 2015 +0300

    Update of test-cases for issue 0026310

apv

2015-07-22 13:36

tester   ~0043287

Dear BugMaster,

Branch CR26310_1 from occt git-repository (and IR-2015-07-09 from products git-repository) was compiled on Linux and Windows platforms and tested.
SHA-1: 4496f22e22421e7f35ab617a2d5519ec3651c903

Number of compiler warnings:
occt component:
   Linux: 24 (24 on master)
   Windows: 0 (0 on master)
products component:
   Linux: 37 (37 on master)
   Windows: 0 (0 on master)

Regressions/Differences:
Not detected

Testing cases:
bugs modalg_6 bug26310_1 - OK
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Debian70-64/bugs/modalg_6/bug26310_1.html
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Windows-64-VC10/bugs/modalg_6/bug26310_1.html
bugs modalg_6 bug26310_2 - OK
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Debian70-64/bugs/modalg_6/bug26310_2.html
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Windows-64-VC10/bugs/modalg_6/bug26310_2.html
bugs modalg_6 bug26310_3 - OK
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Debian70-64/bugs/modalg_6/bug26310_3.html
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Windows-64-VC10/bugs/modalg_6/bug26310_3.html
bugs modalg_6 bug26310_4 - KO (known problem)
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Debian70-64/bugs/modalg_6/bug26310_4.html
http://occt-tests/CR26310-1-IR-2015-07-09-occt-64/Windows-64-VC10/bugs/modalg_6/bug26310_4.html

Testing on Linux:
Total MEMORY difference: 97157245 / 96641405 [+0.53%]
Total CPU difference: 17589.679999999877 / 17395.919999999725 [+1.11%]

Testing on Windows:
Total MEMORY difference: 57182398 / 56551221 [+1.12%]
Total CPU difference: 16361.21327889888 / 15999.244158598929 [+2.26%]

git

2015-08-14 10:54

administrator   ~0044171

Branch CR26310_1 has been deleted by inv.

SHA-1: 9943066a7a67299e762c28247fe5b3c341ed853f

git

2015-08-14 10:56

administrator   ~0044191

Branch CR26310 has been deleted by inv.

SHA-1: f6675b73ddce4fb37ee002aee39a5bb00ff5fa8a

Related Changesets

occt: master 7365fad6

2015-07-22 13:10:27

nbv


Committer: bugmaster Details Diff		 0026310: Very slow boolean cut operations on cylinders

1. JoinWLines algorithm has been improved.
2. Reference to the V-boundaries is deleted when computing step.
3. Decreasing the tolerance when computing parameters of WLine.
4. Adding boundary point is forbidden if it lies in prolongation of found ones.
5. Possible reason of exception has been eliminated.
6. Processing of critical point has been improved.

Test cases for this issue have been created.
Correction of some test case(s).

Test case bugs/modalg_6/bug26310_4 is added

Update of test-cases for issue 0026310		 Affected Issues
0026310
mod - src/IntPatch/IntPatch_ImpImpIntersection_4.gxx Diff File
mod - src/IntPatch/IntPatch_Intersection.cxx Diff File
mod - src/IntTools/IntTools_FaceFace.cxx Diff File
mod - tests/bugs/modalg_5/bug24915 Diff File
mod - tests/bugs/modalg_5/bug25292_11 Diff File
mod - tests/bugs/modalg_5/bug25292_12 Diff File
add - tests/bugs/modalg_6/bug26310_1 Diff File
add - tests/bugs/modalg_6/bug26310_2 Diff File
add - tests/bugs/modalg_6/bug26310_3 Diff File
add - tests/bugs/modalg_6/bug26310_4 Diff File

Issue History

Date Modified Username Field Change
2015-06-04 09:57 srlockley New Issue
2015-06-04 09:57 srlockley Assigned To => msv
2015-06-04 09:57 srlockley File Added: cylinders.zip
2015-06-04 11:07 msv Assigned To msv => nbv
2015-06-04 11:07 msv Status new => assigned
2015-06-04 11:07 msv Product Version 6.9.0 => 7.1.0
2015-06-04 11:07 msv Steps to Reproduce Updated
2015-07-06 15:56 git Note Added: 0042757
2015-07-06 15:59 nbv Note Added: 0042758
2015-07-06 15:59 nbv Assigned To nbv => msv
2015-07-06 15:59 nbv Status assigned => resolved
2015-07-06 15:59 nbv Steps to Reproduce Updated
2015-07-06 16:36 abv Note Added: 0042759
2015-07-06 17:01 nbv Note Added: 0042760
2015-07-06 17:24 nbv Note Edited: 0042760
2015-07-07 09:36 git Note Added: 0042772
2015-07-14 10:05 srlockley Note Added: 0042989
2015-07-14 10:43 msv Note Added: 0042991
2015-07-14 20:09 msv Note Added: 0043019
2015-07-14 20:09 msv Assigned To msv => nbv
2015-07-14 20:09 msv Status resolved => assigned
2015-07-14 20:28 abv Note Added: 0043020
2015-07-15 09:16 msv Note Added: 0043022
2015-07-15 09:27 nbv Note Added: 0043023
2015-07-15 09:35 abv Note Added: 0043027
2015-07-15 10:22 msv Note Added: 0043035
2015-07-15 10:59 git Note Added: 0043039
2015-07-15 11:02 nbv Note Added: 0043040
2015-07-15 11:02 nbv Assigned To nbv => msv
2015-07-15 11:02 nbv Status assigned => resolved
2015-07-15 11:32 nbv Assigned To msv => nbv
2015-07-15 11:32 nbv Status resolved => assigned
2015-07-15 13:59 git Note Added: 0043060
2015-07-15 14:00 nbv Note Added: 0043061
2015-07-15 14:00 nbv Assigned To nbv => msv
2015-07-15 14:00 nbv Status assigned => resolved
2015-07-15 16:27 msv Note Added: 0043074
2015-07-15 16:27 msv Assigned To msv => bugmaster
2015-07-15 16:27 msv Status resolved => reviewed
2015-07-15 16:28 msv Note Added: 0043075
2015-07-15 21:02 srlockley Note Added: 0043088
2015-07-16 09:01 srlockley Note Added: 0043092
2015-07-16 09:04 srlockley Note Edited: 0043092
2015-07-16 09:04 srlockley Note Edited: 0043088
2015-07-16 09:37 msv Relationship added related to 0026447
2015-07-16 09:41 nbv Note Added: 0043096
2015-07-16 09:42 nbv File Added: b1b2cut.PNG
2015-07-16 09:42 nbv File Added: b2b1cut.PNG
2015-07-16 10:04 nbv Assigned To bugmaster => nbv
2015-07-16 10:04 nbv Status reviewed => assigned
2015-07-16 10:04 git Note Added: 0043098
2015-07-16 10:06 nbv Note Added: 0043099
2015-07-16 10:06 nbv Assigned To nbv => msv
2015-07-16 10:06 nbv Status assigned => resolved
2015-07-16 10:39 nbv Relationship added related to 0025929
2015-07-16 10:53 git Note Added: 0043102
2015-07-16 11:03 nbv Note Added: 0043104
2015-07-16 11:03 nbv Description Updated
2015-07-16 11:03 nbv Steps to Reproduce Updated
2015-07-16 11:03 nbv Additional Information Updated
2015-07-16 11:08 msv Note Added: 0043105
2015-07-16 11:08 msv Assigned To msv => bugmaster
2015-07-16 11:08 msv Status resolved => reviewed
2015-07-16 17:37 apv Assigned To bugmaster => apv
2015-07-18 00:46 srlockley Note Added: 0043171
2015-07-22 13:32 git Note Added: 0043286
2015-07-22 13:32 apv Test case number => bugs modalg_6 bug26310_1, bug26310_2, bug26310_3, bug26310_4
2015-07-22 13:36 apv Note Added: 0043287
2015-07-22 13:36 apv Assigned To apv => bugmaster
2015-07-22 13:36 apv Status reviewed => tested
2015-07-23 11:55 bugmaster Changeset attached => occt master 7365fad6
2015-07-23 11:55 bugmaster Status tested => verified
2015-07-23 11:55 bugmaster Resolution open => fixed
2015-07-23 13:25 bugmaster Target Version => 7.0.0
2015-08-14 10:54 git Note Added: 0044171
2015-08-14 10:56 git Note Added: 0044191
2015-09-01 11:36 abv Target Version 7.0.0 => 6.9.1
2015-10-16 14:56 aiv Status verified => closed
2015-10-23 20:51 aiv Fixed in Version => 6.9.1