MantisBT - Open CASCADE
View Issue Details
0028605Open CASCADE[OCCT] OCCT:Modeling Algorithmspublic2017-03-29 11:242017-09-29 16:25
msv 
bugmaster 
normalminor 
closedfixed 
[OCCT] 7.1.0 
[OCCT] 7.2.0[OCCT] 7.2.0 
Not needed
0028605: Improve the algorithm of calculation of valid intersection range of an edge
The algorithm IntTools_ShrunkRange used in Boolean operations needs to be improved. Now it finds a point on curve distant along the curve from the point with first/last parameter using AbscissaPoint algorithm. It is incorrect, because the vertex point may not be placed on the end of the curve. It is needed to find intersection of a sphere of vertex with the curve and use the intersection point nearest to the analyzed end.

In order to not decrease performance with using the heavy algorithm of intersection curve-surface we will use simplified algorithm of binary search. It is proved to be not worse by performance than AbscissaPoint approach.

The same algorithm will be used in checkshape in the new check for coverage of an edge by vertices (see #23731).
Not needed.
No tags attached.
Issue History
2017-03-29 11:24msvNew Issue
2017-03-29 11:24msvAssigned To => msv
2017-03-29 11:25msvRelationship addedrelated to 0023731
2017-03-29 11:25msvStatusnew => assigned
2017-03-29 16:53gitNote Added: 0064786
2017-03-29 16:56gitNote Added: 0064787
2017-03-29 16:56msvNote Added: 0064788
2017-03-29 16:56msvAssigned Tomsv => emv
2017-03-29 16:56msvStatusassigned => resolved
2017-03-30 08:40emvNote Added: 0064793
2017-03-30 08:40emvAssigned Toemv => msv
2017-03-30 08:40emvStatusresolved => assigned
2017-03-30 14:53gitNote Added: 0064813
2017-03-30 18:19gitNote Added: 0064817
2017-03-30 18:20msvNote Added: 0064819
2017-03-30 18:20msvAssigned Tomsv => emv
2017-03-30 18:20msvStatusassigned => resolved
2017-03-31 16:29gitNote Added: 0064834
2017-03-31 16:31emvNote Added: 0064835
2017-03-31 16:31emvAssigned Toemv => bugmaster
2017-03-31 16:31emvStatusresolved => reviewed
2017-03-31 17:21mkvNote Added: 0064837
2017-03-31 17:21mkvStatusreviewed => feedback
2017-03-31 17:34gitNote Added: 0064840
2017-03-31 17:35msvNote Added: 0064841
2017-03-31 17:35msvAssigned Tobugmaster => mkv
2017-03-31 17:35msvStatusfeedback => reviewed
2017-04-03 16:15mkvNote Added: 0064865
2017-04-03 16:15mkvNote Added: 0064867
2017-04-03 16:15mkvStatusreviewed => assigned
2017-04-03 16:15mkvTest case number => Not needed
2017-04-03 16:15mkvAssigned Tomkv => msv
2017-04-18 15:39gitNote Added: 0065299
2017-04-18 15:42msvNote Added: 0065300
2017-04-18 15:42msvAssigned Tomsv => emv
2017-04-18 15:42msvStatusassigned => resolved
2017-04-18 15:53gitNote Added: 0065302
2017-04-18 16:41gitNote Added: 0065306
2017-04-18 16:45emvNote Added: 0065307
2017-04-18 16:45emvAssigned Toemv => bugmaster
2017-04-18 16:45emvStatusresolved => reviewed
2017-04-18 17:22mkvAssigned Tobugmaster => mkv
2017-04-19 19:16mkvNote Added: 0065366
2017-04-19 19:17mkvNote Added: 0065367
2017-04-19 19:17mkvAssigned Tomkv => msv
2017-04-19 19:17mkvStatusreviewed => feedback
2017-04-20 12:46msvNote Added: 0065387
2017-04-20 12:47msvAssigned Tomsv => mkv
2017-04-20 12:52mkvNote Added: 0065388
2017-04-20 12:52mkvAssigned Tomkv => bugmaster
2017-04-20 12:52mkvStatusfeedback => tested
2017-04-21 14:59bugmasterChangeset attached => occt master c0a1a35f
2017-04-21 14:59bugmasterStatustested => verified
2017-04-21 14:59bugmasterResolutionopen => fixed
2017-05-12 11:36gitNote Added: 0065946
2017-05-12 11:36gitNote Added: 0065947
2017-05-12 11:36gitNote Added: 0065948
2017-09-29 16:19aivFixed in Version => 7.2.0
2017-09-29 16:25aivStatusverified => closed

Notes
(0064786)
git   
2017-03-29 16:53   
Branch CR28605 has been created by msv.

SHA-1: 9420a6eed3ab7b6b7fff0b20f8487a251afea120


Detailed log of new commits:

Author: msv
Date: Fri Mar 24 16:04:05 2017 +0300

    0028605: Improve the algorithm of calculation of valid intersection range of an edge
    
    - New method BRepLib::FindValidRange() has been added. It computes the range of the edge not covered by boundary vertices.
    - The algorithm of calculation of valid intersection range in the class IntTools_ShrunkRange has been corrected to use the new method.
    - The method BOPTools_AlgoTools::MakeSplitEdge() has been improved to protect against errors in the case of reversed orientation of the input edge.
    - Two new Draw commands have been added:
      validrange - it calls the new method BRepLib::FindValidRange().
      tolsphere - it shows tolerances of vertices by drawing a sphere around each vertex of the shape.
(0064787)
git   
2017-03-29 16:56   
Branch CR28605 has been updated forcibly by msv.

SHA-1: 4ad572db0a7e3c0368e19f420e88930fda16c58f
(0064788)
msv   
2017-03-29 16:56   
Dear Eugeny, please review the branch.
(0064793)
emv   
2017-03-30 08:40   
- Misprint in the commit message - should be "offset shape_type_i_c YE1, YE2"

BRepLib_1.cxx:
- After line 69 put: else {anU2 = anEndU; break}. Otherwise the OUT parameter will be outside the given range
- Lines 75-89: For calculation of the precise solution calculation it is better to use the parameter previous to the OUT parameter:
  anUIn - parameter inside sphere (start value is aStartU)
  anUOut - parameter outside the sphere
  Both parameters should be updated with each step of the while loop at lines 58-73
- Lines 116, 127: Why not to use anEps for comparision?
- Lines 162-182: What if the vertices of the edge are null? Should not we use the boundary points of the edge in this case?

BRepTest_CheckCommands:
- Move lines 1637-1642 to 1647. No need to create pOutU1 and pOutU2 if the valid range has not been found

IntTools_ShrunkRange:
- Line 167: restore the comment - compute the shrunk range - part of the edge not covered by the tolerance spheres of its vertices
- move the call to BRepLib::FindValidRange to line 158

Could you please update documentation with the new functionality and new commands?
(0064813)
git   
2017-03-30 14:53   
Branch CR28605_1 has been created by msv.

SHA-1: 5a174cbd3cde434d17ed27d83560d258a536687e


Detailed log of new commits:

Author: msv
Date: Thu Mar 30 12:09:18 2017 +0300

    // update according to remarks

Author: msv
Date: Fri Mar 24 16:04:05 2017 +0300

    0028605: Improve the algorithm of calculation of valid intersection range of an edge
    
    - New method BRepLib::FindValidRange() has been added. It computes the range of the edge not covered by boundary vertices.
    - The algorithm of calculation of valid intersection range in the class IntTools_ShrunkRange has been corrected to use the new method.
    - The method BOPTools_AlgoTools::MakeSplitEdge() has been improved to protect against errors in the case of reversed orientation of the input edge.
    - Two new Draw commands have been added:
      validrange - it calls the new method BRepLib::FindValidRange().
      tolsphere - it shows tolerances of vertices by drawing a sphere around each vertex of the shape.
    - The test cases "offset shape_type_i_c YE1,YE2" became better. The scripts have been corrected to reflect the new state.
(0064817)
git   
2017-03-30 18:19   
Branch CR28605_1 has been updated by msv.

SHA-1: a403403da1bd397f302840d7e39b0b5c507a0963


Detailed log of new commits:

Author: msv
Date: Thu Mar 30 17:36:39 2017 +0300

    //Update according to remarks 2.
    //Implement protection against hanging inside singularities

(0064819)
msv   
2017-03-30 18:20   
Please review again.
(0064834)
git   
2017-03-31 16:29   
Branch CR28605_1 has been updated by msv.

SHA-1: b1af728cc3ccdb754984fc138cd184636969d2b1


Detailed log of new commits:

Author: msv
Date: Fri Mar 31 16:27:58 2017 +0300

    // comment is added

(0064835)
emv   
2017-03-31 16:31   
Reviewed, please test.
(0064837)
mkv   
2017-03-31 17:21   
Dear msv,
could you please rebase branch CR28605_1 on current master,
there are conflict files.

(0064840)
git   
2017-03-31 17:34   
Branch CR28605_2 has been created by msv.

SHA-1: 95112d09684146e9cc9d00e8778cca04350668ec


Detailed log of new commits:

Author: msv
Date: Fri Mar 24 16:04:05 2017 +0300

    0028605: Improve the algorithm of calculation of valid intersection range of an edge
    
    - New method BRepLib::FindValidRange() has been added. It computes the range of the edge not covered by boundary vertices.
    - The algorithm of calculation of valid intersection range in the class IntTools_ShrunkRange has been corrected to use the new method.
    - The method BOPTools_AlgoTools::MakeSplitEdge() has been improved to protect against errors in the case of reversed orientation of the input edge.
    - Two new Draw commands have been added:
      validrange - it calls the new method BRepLib::FindValidRange().
      tolsphere - it shows tolerances of vertices by drawing a sphere around each vertex of the shape.
    - The test cases "offset shape_type_i_c YE1,YE2" became better. The scripts have been corrected to reflect the new state.
(0064841)
msv   
2017-03-31 17:35   
Done in new branch CR28605_2.
(0064865)
mkv   
2017-04-03 16:15   
Dear BugMaster,
Branch CR28605_2 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
SHA-1: 95112d09684146e9cc9d00e8778cca04350668ec

Number of compiler warnings:

occt component :
Linux: 0 (0 on master)
Windows: 0 (0 on master)
MacOS : 0 (0 on master)

products component :
Linux: 64 (64 on master)
Windows: 0 (0 on master)
MacOS : 1212

Regressions/Differences/Improvements:
http://occt-tests/CR28605_2-master-OCCT/Debian70-64/summary.html [^]
http://occt-tests/CR28605_2-master-OCCT/Debian70-64/summary.html [^]
Failed:
  boolean bcommon_complex C1
  boolean bcut_complex Q4
  boolean bfuse_complex E6, P7, R6, R9
  boolean bopcommon_complex J1
  boolean bopfuse_complex K3
  boolean bopsection B2, D5, D6
  boolean bsection E4, G7, M8, M9, N4, N5, N6
  bugs modalg_1 bug10232, bug12918
  bugs modalg_2 bug21754, bug22557, bug23429
  bugs modalg_4 bug81, bug23548, pro19653
  bugs modalg_5 bug22831, bug23782, bug23958, bug24266, bug24290_1, bug24656, bug24851, bug24914, bug25002, bug25292_13, bug25292_14, bug25470, bug25772
  bugs modalg_6 bug21875, bug24094, bug25890, bug26310_2, bug26310_3, bug26444, bug27128, bug27179, bug27182, bug27267, bug27283, bug27677, bug27746_1, bug27761, bug28373
  bugs moddata_1 bug152_1, bug152_2
  offset shape_type_a A1

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 91873959 / 91026254 [+0.93%]
Total CPU difference: 19124.8600000003 / 19145.890000000287 [-0.11%]
products component :
Total MEMORY difference: 30767824 / 30770563 [-0.01%]
Total CPU difference: 5396.489999999984 / 5358.419999999984 [+0.71%]
Testing on Windows:
occt component :
Total MEMORY difference: 57475458 / 57471137 [+0.01%]
Total CPU difference: 17962.828745598657 / 17607.583268398554 [+2.02%]
products component :
Total MEMORY difference: 22295607 / 22257195 [+0.17%]
Total CPU difference: 5425.371577799978 / 5313.206858799958 [+2.11%]

There are following differences in images found by testdiff.
http://occt-tests/CR28605_2-master-OCCT/Debian70-64/diff-Debian70-64.html [^]
http://occt-tests/CR28605_2-master-OCCT/Windows-64-VC10/diff-Windows-64-VC10-image.html [^]
IMAGE boolean bopcommon_complex J1: J1.png differs
IMAGE bugs modalg_2 bug472_3: bug472_3.png differs
IMAGE bugs modalg_2 bug497_3: bug497_3.png differs
IMAGE bugs modalg_6 bug26619: bug26619.png differs
IMAGE bugs modalg_6 bug27615: bug27615.png differs
IMAGE bugs modalg_6 bug27761: bug27761.png differs
(0064867)
mkv   
2017-04-03 16:15   
Dear msv,
Branch CR28605_2 has been rejected due to:
- regressions/differences/improvements
- differences in images
(0065299)
git   
2017-04-18 15:39   
Branch CR28605_2 has been updated forcibly by msv.

SHA-1: 75c66034be9e3524faa786f990c8839eea522fd1
(0065300)
msv   
2017-04-18 15:42   
I have corrected the code to remove regressions. The branch has been rebased.
Eugeny, please review it.
(0065302)
git   
2017-04-18 15:53   
Branch CR28605_2 has been updated by msv.

SHA-1: a4bbcc6d53cb7d91d292298a45a09ac1ee95496b


Detailed log of new commits:

Author: msv
Date: Tue Apr 18 15:53:24 2017 +0300

    // Correct according to remarks.

(0065306)
git   
2017-04-18 16:41   
Branch CR28605_2 has been updated by msv.

SHA-1: da95091e9ce218495dacb6a68c611f04f7f4aada


Detailed log of new commits:

Author: msv
Date: Tue Apr 18 16:41:51 2017 +0300

    // more correction

(0065307)
emv   
2017-04-18 16:45   
Reviewed, please test.
(0065366)
mkv   
2017-04-19 19:16   
Dear BugMaster,
Branch CR28605_2 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
SHA-1: da95091e9ce218495dacb6a68c611f04f7f4aada

Number of compiler warnings:

occt component :
Linux: 0 (0 on master)
Windows: 0 (0 on master)
MacOS : 0 (0 on master)

products component :
Linux: 64 (64 on master)
Windows: 0 (0 on master)
MacOS : 1195

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 92072573 / 90695027 [+1.52%]
Total CPU difference: 19846.49000000039 / 19728.57000000033 [+0.60%]
products component :
Total MEMORY difference: 30393389 / 30341918 [+0.17%]
Total CPU difference: 5381.669999999979 / 5356.299999999965 [+0.47%]
Testing on Windows:
occt component :
Total MEMORY difference: 57807308 / 57804189 [+0.01%]
Total CPU difference: 18255.829823798547 / 18136.473458698543 [+0.66%]
products component :
Total MEMORY difference: 22303862 / 22265369 [+0.17%]
Total CPU difference: 5324.704132499974 / 5359.788757399982 [-0.65%]

There are following differences in images found by testdiff.
http://occt-tests/CR28605__2-master-OCCT/Debian70-64/diff-Debian70-64.html [^]
http://occt-tests/CR28605__2-master-OCCT/Windows-64-VC10/diff-Windows-64-VC10-image.html [^]
IMAGE bugs modalg_1 bug10232: bug10232.png differs
IMAGE bugs modalg_2 bug472_3: bug472_3.png differs
IMAGE bugs modalg_2 bug497_3: bug497_3.png differs
IMAGE bugs modalg_6 bug26619: bug26619.png differs
IMAGE bugs modalg_6 bug27615: bug27615.png differs
(0065367)
mkv   
2017-04-19 19:17   
Dear msv,
Branch CR28605_2 has been rejected due to:
- differences in images
(0065387)
msv   
2017-04-20 12:46   
The differences in images do not show any regression.

IMAGE bugs modalg_1 bug10232: bug10232.png differs
This test is unstable, and this change is not regression.

IMAGE bugs modalg_2 bug472_3: bug472_3.png differs
The result is invalid in both master and fix, no regression.

IMAGE bugs modalg_2 bug497_3: bug497_3.png differs
The result is invalid in both master and fix, no regression.

IMAGE bugs modalg_6 bug26619: bug26619.png differs
The result is still bad in fix, but it became better than in master.

IMAGE bugs modalg_6 bug27615: bug27615.png differs
The result became better than in master.
(0065388)
mkv   
2017-04-20 12:52   
Dear BugMaster,
Branch CR28605_2 is TESTED.
(0065946)
git   
2017-05-12 11:36   
Branch CR28605 has been deleted by kgv.

SHA-1: 4ad572db0a7e3c0368e19f420e88930fda16c58f
(0065947)
git   
2017-05-12 11:36   
Branch CR28605_1 has been deleted by kgv.

SHA-1: b1af728cc3ccdb754984fc138cd184636969d2b1
(0065948)
git   
2017-05-12 11:36   
Branch CR28605_2 has been deleted by kgv.

SHA-1: da95091e9ce218495dacb6a68c611f04f7f4aada