MantisBT - Community
View Issue Details
0026310Community[OCCT] OCCT:Modeling Algorithmspublic2015-06-04 09:572015-10-23 20:51
srlockley 
bugmaster 
normalmajor 
closedfixed 
WindowsVC++ 201364 bit
[OCCT] 7.1.0 
[OCCT] 6.9.1[OCCT] 6.9.1 
bugs modalg_6 bug26310_1, bug26310_2, bug26310_3, bug26310_4
0026310: Very slow boolean cut operations on cylinders
Very 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.
Branch 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.
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.
No tags attached.
related to 0025929closed bugmaster Open CASCADE Make Approx_ComputeLine algorithm adaptive 
related to 0026447closed bugmaster Community Performance degradation intersecting cylindrical surfaces 
zip cylinders.zip (1,421) 2015-06-04 09:57
https://tracker.dev.opencascade.org/
png b1b2cut.PNG (74,246) 2015-07-16 09:42
https://tracker.dev.opencascade.org/
png b2b1cut.PNG (72,629) 2015-07-16 09:42
https://tracker.dev.opencascade.org/
Issue History
2015-06-04 09:57srlockleyNew Issue
2015-06-04 09:57srlockleyAssigned To => msv
2015-06-04 09:57srlockleyFile Added: cylinders.zip
2015-06-04 11:07msvAssigned Tomsv => nbv
2015-06-04 11:07msvStatusnew => assigned
2015-06-04 11:07msvProduct Version6.9.0 => 7.1.0
2015-06-04 11:07msvSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=10663#r10663
2015-07-06 15:56gitNote Added: 0042757
2015-07-06 15:59nbvNote Added: 0042758
2015-07-06 15:59nbvAssigned Tonbv => msv
2015-07-06 15:59nbvStatusassigned => resolved
2015-07-06 15:59nbvSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=10882#r10882
2015-07-06 16:36abvNote Added: 0042759
2015-07-06 17:01nbvNote Added: 0042760
2015-07-06 17:24nbvNote Edited: 0042760bug_revision_view_page.php?bugnote_id=42760#r10884
2015-07-07 09:36gitNote Added: 0042772
2015-07-14 10:05srlockleyNote Added: 0042989
2015-07-14 10:43msvNote Added: 0042991
2015-07-14 20:09msvNote Added: 0043019
2015-07-14 20:09msvAssigned Tomsv => nbv
2015-07-14 20:09msvStatusresolved => assigned
2015-07-14 20:28abvNote Added: 0043020
2015-07-15 09:16msvNote Added: 0043022
2015-07-15 09:27nbvNote Added: 0043023
2015-07-15 09:35abvNote Added: 0043027
2015-07-15 10:22msvNote Added: 0043035
2015-07-15 10:59gitNote Added: 0043039
2015-07-15 11:02nbvNote Added: 0043040
2015-07-15 11:02nbvAssigned Tonbv => msv
2015-07-15 11:02nbvStatusassigned => resolved
2015-07-15 11:32nbvAssigned Tomsv => nbv
2015-07-15 11:32nbvStatusresolved => assigned
2015-07-15 13:59gitNote Added: 0043060
2015-07-15 14:00nbvNote Added: 0043061
2015-07-15 14:00nbvAssigned Tonbv => msv
2015-07-15 14:00nbvStatusassigned => resolved
2015-07-15 16:27msvNote Added: 0043074
2015-07-15 16:27msvAssigned Tomsv => bugmaster
2015-07-15 16:27msvStatusresolved => reviewed
2015-07-15 16:28msvNote Added: 0043075
2015-07-15 21:02srlockleyNote Added: 0043088
2015-07-16 09:01srlockleyNote Added: 0043092
2015-07-16 09:04srlockleyNote Edited: 0043092bug_revision_view_page.php?bugnote_id=43092#r10993
2015-07-16 09:04srlockleyNote Edited: 0043088bug_revision_view_page.php?bugnote_id=43088#r10995
2015-07-16 09:37msvRelationship addedrelated to 0026447
2015-07-16 09:41nbvNote Added: 0043096
2015-07-16 09:42nbvFile Added: b1b2cut.PNG
2015-07-16 09:42nbvFile Added: b2b1cut.PNG
2015-07-16 10:04nbvAssigned Tobugmaster => nbv
2015-07-16 10:04nbvStatusreviewed => assigned
2015-07-16 10:04gitNote Added: 0043098
2015-07-16 10:06nbvNote Added: 0043099
2015-07-16 10:06nbvAssigned Tonbv => msv
2015-07-16 10:06nbvStatusassigned => resolved
2015-07-16 10:39nbvRelationship addedrelated to 0025929
2015-07-16 10:53gitNote Added: 0043102
2015-07-16 11:03nbvNote Added: 0043104
2015-07-16 11:03nbvDescription Updatedbug_revision_view_page.php?rev_id=11004#r11004
2015-07-16 11:03nbvSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=11005#r11005
2015-07-16 11:03nbvAdditional Information Updatedbug_revision_view_page.php?rev_id=11007#r11007
2015-07-16 11:08msvNote Added: 0043105
2015-07-16 11:08msvAssigned Tomsv => bugmaster
2015-07-16 11:08msvStatusresolved => reviewed
2015-07-16 17:37apvAssigned Tobugmaster => apv
2015-07-18 00:46srlockleyNote Added: 0043171
2015-07-22 13:32gitNote Added: 0043286
2015-07-22 13:32apvTest case number => bugs modalg_6 bug26310_1, bug26310_2, bug26310_3, bug26310_4
2015-07-22 13:36apvNote Added: 0043287
2015-07-22 13:36apvAssigned Toapv => bugmaster
2015-07-22 13:36apvStatusreviewed => tested
2015-07-23 11:55bugmasterChangeset attached => occt master 7365fad6
2015-07-23 11:55bugmasterStatustested => verified
2015-07-23 11:55bugmasterResolutionopen => fixed
2015-07-23 13:25bugmasterTarget Version => 7.0.0
2015-08-14 10:54gitNote Added: 0044171
2015-08-14 10:56gitNote Added: 0044191
2015-09-01 11:36abvTarget Version7.0.0 => 6.9.1
2015-10-16 14:56aivStatusverified => closed
2015-10-23 20:51aivFixed in Version => 6.9.1

Notes
(0042757)
git   
2015-07-06 15:56   
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).
(0042758)
nbv   
2015-07-06 15:59   
Dear Mikhail,

Please review CR26310 branch.
(0042759)
abv   
2015-07-06 16:36   
Nikolai, does your fix solve the original problem? Please share the times to show whether performance has increased, and how much.
(0042760)
nbv   
2015-07-06 17:01   
(edited on: 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.

(0042772)
git   
2015-07-07 09:36   
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

(0042989)
srlockley   
2015-07-14 10:05   
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?
(0042991)
msv   
2015-07-14 10:43   
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.
(0043019)
msv   
2015-07-14 20:09   
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.
(0043020)
abv   
2015-07-14 20:28   
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!
(0043022)
msv   
2015-07-15 09:16   
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.
(0043023)
nbv   
2015-07-15 09:27   
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.
(0043027)
abv   
2015-07-15 09:35   
On, then why not " if (anUmaxAdded == RealFirst())"??
(0043035)
msv   
2015-07-15 10:22   
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.
(0043039)
git   
2015-07-15 10:59   
Branch CR26310 has been updated forcibly by nbv.

SHA-1: f6675b73ddce4fb37ee002aee39a5bb00ff5fa8a
(0043040)
nbv   
2015-07-15 11:02   
Dear Mikhail,

Please review the current state of CR26310 branch.
(0043060)
git   
2015-07-15 13:59   
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).
(0043061)
nbv   
2015-07-15 14:00   
Dear Mikhail,

Please review CR26310_1 branch.
(0043074)
msv   
2015-07-15 16:27   
Reviewed.
(0043075)
msv   
2015-07-15 16:28   
Andrey, concerning your remark, we followed your advise to use Boolean flag.
(0043088)
srlockley   
2015-07-15 21:02   
(edited on: 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?

(0043092)
srlockley   
2015-07-16 09:01   
(edited on: 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

(0043096)
nbv   
2015-07-16 09:41   
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.
(0043098)
git   
2015-07-16 10:04   
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

(0043099)
nbv   
2015-07-16 10:06   
Dear Mikhail,

Please review bugs/modalg_6/bug26310_4 test case in CR26310_1 branch.
(0043102)
git   
2015-07-16 10:53   
Branch CR26310_1 has been updated forcibly by nbv.

SHA-1: 4496f22e22421e7f35ab617a2d5519ec3651c903
(0043104)
nbv   
2015-07-16 11:03   
"Steps To Reproduce" and "Additional information and documentation updates" have been corrected.
(0043105)
msv   
2015-07-16 11:08   
Reviewed.
(0043171)
srlockley   
2015-07-18 00:46   
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
(0043286)
git   
2015-07-22 13:32   
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

(0043287)
apv   
2015-07-22 13:36   
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%]
(0044171)
git   
2015-08-14 10:54   
Branch CR26310_1 has been deleted by inv.

SHA-1: 9943066a7a67299e762c28247fe5b3c341ed853f
(0044191)
git   
2015-08-14 10:56   
Branch CR26310 has been deleted by inv.

SHA-1: f6675b73ddce4fb37ee002aee39a5bb00ff5fa8a