MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0026310Community[OCCT] OCCT:Modeling Algorithmspublic2015-06-04 09:572015-10-23 20:51
Reportersrlockley 
Assigned Tobugmaster 
PrioritynormalSeveritymajor 
StatusclosedResolutionfixed 
PlatformWindowsOSVC++ 2013OS Version64 bit
Product Version[OCCT] 7.1.0 
Target Version[OCCT] 6.9.1Fixed in Version[OCCT] 6.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 Fileszip file icon cylinders.zip (1,421 bytes) 2015-06-04 09:57
png file icon b1b2cut.PNG (74,246 bytes) 2015-07-16 09:42
png file icon b2b1cut.PNG (72,629 bytes) 2015-07-16 09:42

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

-  Notes
(0042757)
git (administrator)
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 (developer)
2015-07-06 15:59

Dear Mikhail,

Please review CR26310 branch.
(0042759)
abv (manager)
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 (developer)
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 (administrator)
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 (reporter)
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 (developer)
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 (developer)
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 (manager)
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 (developer)
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 (developer)
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 (manager)
2015-07-15 09:35

On, then why not " if (anUmaxAdded == RealFirst())"??
(0043035)
msv (developer)
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 (administrator)
2015-07-15 10:59

Branch CR26310 has been updated forcibly by nbv.

SHA-1: f6675b73ddce4fb37ee002aee39a5bb00ff5fa8a
(0043040)
nbv (developer)
2015-07-15 11:02

Dear Mikhail,

Please review the current state of CR26310 branch.
(0043060)
git (administrator)
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 (developer)
2015-07-15 14:00

Dear Mikhail,

Please review CR26310_1 branch.
(0043074)
msv (developer)
2015-07-15 16:27

Reviewed.
(0043075)
msv (developer)
2015-07-15 16:28

Andrey, concerning your remark, we followed your advise to use Boolean flag.
(0043088)
srlockley (reporter)
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 (reporter)
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 (developer)
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 (administrator)
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 (developer)
2015-07-16 10:06

Dear Mikhail,

Please review bugs/modalg_6/bug26310_4 test case in CR26310_1 branch.
(0043102)
git (administrator)
2015-07-16 10:53

Branch CR26310_1 has been updated forcibly by nbv.

SHA-1: 4496f22e22421e7f35ab617a2d5519ec3651c903
(0043104)
nbv (developer)
2015-07-16 11:03

"Steps To Reproduce" and "Additional information and documentation updates" have been corrected.
(0043105)
msv (developer)
2015-07-16 11:08

Reviewed.
(0043171)
srlockley (reporter)
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 (administrator)
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 (tester)
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 (administrator)
2015-08-14 10:54

Branch CR26310_1 has been deleted by inv.

SHA-1: 9943066a7a67299e762c28247fe5b3c341ed853f
(0044191)
git (administrator)
2015-08-14 10:56

Branch CR26310 has been deleted by inv.

SHA-1: f6675b73ddce4fb37ee002aee39a5bb00ff5fa8a

- Related Changesets
occt: master 7365fad6
Timestamp: 2015-07-22 13:10:27
Author: 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
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 View Revisions
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 View Revisions
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 View Revisions
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 View Revisions
2015-07-16 09:04 srlockley Note Edited: 0043088 View Revisions
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 View Revisions
2015-07-16 11:03 nbv Steps to Reproduce Updated View Revisions
2015-07-16 11:03 nbv Additional Information Updated View Revisions
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 user533 Status verified => closed
2015-10-23 20:51 user533 Fixed in Version => 6.9.1


Copyright © 2000 - 2018 MantisBT Team
Powered by Mantis Bugtracker