View Issue Details

IDProjectCategoryView StatusLast Update
0028605Open CASCADEOCCT:Modeling Algorithmspublic2020-10-22 11:31
ReportermsvAssigned Tobugmaster  
PrioritynormalSeverityminor 
Status closedResolutionfixed 
Product Version7.1.0 
Target Version7.2.0Fixed in Version7.2.0 
Summary0028605: Improve the algorithm of calculation of valid intersection range of an edge
DescriptionThe 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).
Steps To ReproduceNot needed.
TagsNo tags attached.
Test case numberNot needed

Relationships

related to 0031871 assignedasuraven Open CASCADE Modeling Algorithms - Elaborate consistent shape validity criteria 

Activities

git

2017-03-29 16:53

administrator   ~0064786

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.

git

2017-03-29 16:56

administrator   ~0064787

Branch CR28605 has been updated forcibly by msv.

SHA-1: 4ad572db0a7e3c0368e19f420e88930fda16c58f

msv

2017-03-29 16:56

developer   ~0064788

Dear Eugeny, please review the branch.

emv

2017-03-30 08:40

developer   ~0064793

- 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?

git

2017-03-30 14:53

administrator   ~0064813

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.

git

2017-03-30 18:19

administrator   ~0064817

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

msv

2017-03-30 18:20

developer   ~0064819

Please review again.

git

2017-03-31 16:29

administrator   ~0064834

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

emv

2017-03-31 16:31

developer   ~0064835

Reviewed, please test.

mkv

2017-03-31 17:21

tester   ~0064837

Dear msv,
could you please rebase branch CR28605_1 on current master,
there are conflict files.

git

2017-03-31 17:34

administrator   ~0064840

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.

msv

2017-03-31 17:35

developer   ~0064841

Done in new branch CR28605_2.

mkv

2017-04-03 16:15

tester   ~0064865

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

mkv

2017-04-03 16:15

tester   ~0064867

Dear msv,
Branch CR28605_2 has been rejected due to:
- regressions/differences/improvements
- differences in images

git

2017-04-18 15:39

administrator   ~0065299

Branch CR28605_2 has been updated forcibly by msv.

SHA-1: 75c66034be9e3524faa786f990c8839eea522fd1

msv

2017-04-18 15:42

developer   ~0065300

I have corrected the code to remove regressions. The branch has been rebased.
Eugeny, please review it.

git

2017-04-18 15:53

administrator   ~0065302

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.

git

2017-04-18 16:41

administrator   ~0065306

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

emv

2017-04-18 16:45

developer   ~0065307

Reviewed, please test.

mkv

2017-04-19 19:16

tester   ~0065366

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

mkv

2017-04-19 19:17

tester   ~0065367

Dear msv,
Branch CR28605_2 has been rejected due to:
- differences in images

msv

2017-04-20 12:46

developer   ~0065387

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.

mkv

2017-04-20 12:52

tester   ~0065388

Dear BugMaster,
Branch CR28605_2 is TESTED.

git

2017-05-12 11:36

administrator   ~0065946

Branch CR28605 has been deleted by kgv.

SHA-1: 4ad572db0a7e3c0368e19f420e88930fda16c58f

git

2017-05-12 11:36

administrator   ~0065947

Branch CR28605_1 has been deleted by kgv.

SHA-1: b1af728cc3ccdb754984fc138cd184636969d2b1

git

2017-05-12 11:36

administrator   ~0065948

Branch CR28605_2 has been deleted by kgv.

SHA-1: da95091e9ce218495dacb6a68c611f04f7f4aada

Related Changesets

occt: master c0a1a35f

2017-03-24 13:04:05

msv


Committer: bugmaster Details Diff
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.
Affected Issues
0028605
mod - dox/user_guides/draw_test_harness/draw_test_harness.md Diff File
mod - dox/user_guides/modeling_algos/modeling_algos.md Diff File
mod - src/BOPTools/BOPTools_AlgoTools_2.cxx Diff File
mod - src/BRepLib/BRepLib.hxx Diff File
add - src/BRepLib/BRepLib_1.cxx Diff File
mod - src/BRepLib/FILES Diff File
mod - src/BRepTest/BRepTest_CheckCommands.cxx Diff File
mod - src/IntTools/IntTools_ShrunkRange.cxx Diff File
mod - tests/offset/shape_type_i_c/YE1 Diff File
mod - tests/offset/shape_type_i_c/YE2 Diff File

Issue History

Date Modified Username Field Change
2017-03-29 11:24 msv New Issue
2017-03-29 11:24 msv Assigned To => msv
2017-03-29 11:25 msv Status new => assigned
2017-03-29 16:53 git Note Added: 0064786
2017-03-29 16:56 git Note Added: 0064787
2017-03-29 16:56 msv Note Added: 0064788
2017-03-29 16:56 msv Assigned To msv => emv
2017-03-29 16:56 msv Status assigned => resolved
2017-03-30 08:40 emv Note Added: 0064793
2017-03-30 08:40 emv Assigned To emv => msv
2017-03-30 08:40 emv Status resolved => assigned
2017-03-30 14:53 git Note Added: 0064813
2017-03-30 18:19 git Note Added: 0064817
2017-03-30 18:20 msv Note Added: 0064819
2017-03-30 18:20 msv Assigned To msv => emv
2017-03-30 18:20 msv Status assigned => resolved
2017-03-31 16:29 git Note Added: 0064834
2017-03-31 16:31 emv Note Added: 0064835
2017-03-31 16:31 emv Assigned To emv => bugmaster
2017-03-31 16:31 emv Status resolved => reviewed
2017-03-31 17:21 mkv Note Added: 0064837
2017-03-31 17:21 mkv Status reviewed => feedback
2017-03-31 17:34 git Note Added: 0064840
2017-03-31 17:35 msv Note Added: 0064841
2017-03-31 17:35 msv Assigned To bugmaster => mkv
2017-03-31 17:35 msv Status feedback => reviewed
2017-04-03 16:15 mkv Note Added: 0064865
2017-04-03 16:15 mkv Note Added: 0064867
2017-04-03 16:15 mkv Status reviewed => assigned
2017-04-03 16:15 mkv Test case number => Not needed
2017-04-03 16:15 mkv Assigned To mkv => msv
2017-04-18 15:39 git Note Added: 0065299
2017-04-18 15:42 msv Note Added: 0065300
2017-04-18 15:42 msv Assigned To msv => emv
2017-04-18 15:42 msv Status assigned => resolved
2017-04-18 15:53 git Note Added: 0065302
2017-04-18 16:41 git Note Added: 0065306
2017-04-18 16:45 emv Note Added: 0065307
2017-04-18 16:45 emv Assigned To emv => bugmaster
2017-04-18 16:45 emv Status resolved => reviewed
2017-04-18 17:22 mkv Assigned To bugmaster => mkv
2017-04-19 19:16 mkv Note Added: 0065366
2017-04-19 19:17 mkv Note Added: 0065367
2017-04-19 19:17 mkv Assigned To mkv => msv
2017-04-19 19:17 mkv Status reviewed => feedback
2017-04-20 12:46 msv Note Added: 0065387
2017-04-20 12:47 msv Assigned To msv => mkv
2017-04-20 12:52 mkv Note Added: 0065388
2017-04-20 12:52 mkv Assigned To mkv => bugmaster
2017-04-20 12:52 mkv Status feedback => tested
2017-04-21 14:59 bugmaster Changeset attached => occt master c0a1a35f
2017-04-21 14:59 bugmaster Status tested => verified
2017-04-21 14:59 bugmaster Resolution open => fixed
2017-05-12 11:36 git Note Added: 0065946
2017-05-12 11:36 git Note Added: 0065947
2017-05-12 11:36 git Note Added: 0065948
2017-09-29 16:19 aiv Fixed in Version => 7.2.0
2017-09-29 16:25 aiv Status verified => closed
2020-10-22 11:31 msv Relationship added related to 0031871