MantisBT - Open CASCADE
View Issue Details
0027915Open CASCADE[OCCT] OCCT:Foundation Classespublic2016-09-28 18:322016-12-09 16:38
msv 
apn 
normalintegration request 
closedfixed 
[OCCT] 7.0.0 
[OCCT] 7.1.0[OCCT] 7.1.0 
Not needed
0027915: Foundation Classes - remove the class NCollection_QuickSort
The class NCollection_QuickSort contains old non-optimal algorithm of sorting. The class std::sort makes the job better.

It is suggested to remove NCollection_QuickSort, and replace its usage with std::sort where it is needed. For now, I see the only usage of it in the file BRepExtrema_DistShapeShape.cxx
Not required
No tags attached.
Issue History
2016-09-28 18:32msvNew Issue
2016-09-28 18:32msvAssigned To => abv
2016-09-28 18:35abvAssigned Toabv => ski
2016-09-28 18:35abvStatusnew => assigned
2016-09-29 12:32kgvSeveritytweak => integration request
2016-09-29 12:32kgvSummaryRemove the class NCollection_QuickSort => Foundation Classes - remove the class NCollection_QuickSort
2016-09-29 19:08gitNote Added: 0058327
2016-09-29 19:10skiNote Added: 0058328
2016-09-29 19:10skiAssigned Toski => msv
2016-09-29 19:10skiStatusassigned => resolved
2016-09-29 19:10skiSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=14851#r14851
2016-09-30 11:57msvNote Added: 0058331
2016-09-30 11:57msvAssigned Tomsv => ski
2016-09-30 11:57msvStatusresolved => assigned
2016-09-30 12:06gitNote Added: 0058332
2016-09-30 12:07skiNote Added: 0058333
2016-09-30 12:07skiAssigned Toski => msv
2016-09-30 12:07skiStatusassigned => resolved
2016-09-30 12:12kgvNote Added: 0058334
2016-09-30 12:16msvNote Added: 0058338
2016-09-30 12:16msvAssigned Tomsv => bugmaster
2016-09-30 12:16msvStatusresolved => reviewed
2016-09-30 12:18msvNote Added: 0058339
2016-09-30 12:18msvAssigned Tobugmaster => ski
2016-09-30 12:18msvStatusreviewed => assigned
2016-09-30 12:54gitNote Added: 0058342
2016-09-30 12:55skiNote Added: 0058343
2016-09-30 12:55skiAssigned Toski => msv
2016-09-30 12:55skiStatusassigned => resolved
2016-09-30 14:49msvNote Added: 0058345
2016-09-30 14:49msvAssigned Tomsv => bugmaster
2016-09-30 14:49msvStatusresolved => reviewed
2016-10-03 12:35mkvAssigned Tobugmaster => mkv
2016-10-03 15:23gitNote Added: 0058365
2016-10-04 16:58mkvNote Added: 0058405
2016-10-04 16:59mkvNote Added: 0058406
2016-10-04 16:59mkvNote Added: 0058407
2016-10-04 16:59mkvAssigned Tomkv => ski
2016-10-04 16:59mkvStatusreviewed => assigned
2016-10-04 17:00mkvTest case number => Not needed
2016-10-05 13:43skiNote Added: 0058422
2016-10-05 13:43skiAssigned Toski => msv
2016-10-05 13:43skiStatusassigned => feedback
2016-10-05 14:22abvNote Added: 0058430
2016-10-05 15:09msvNote Added: 0058432
2016-10-05 15:09msvAssigned Tomsv => ski
2016-10-05 15:09msvStatusfeedback => assigned
2016-10-05 16:16gitNote Added: 0058438
2016-10-06 18:08gitNote Added: 0058468
2016-10-06 18:44skiNote Added: 0058470
2016-10-06 18:44skiAssigned Toski => abv
2016-10-06 18:44skiStatusassigned => resolved
2016-10-07 12:16gitNote Added: 0058475
2016-10-07 13:08skiNote Added: 0058477
2016-10-07 14:38gitNote Added: 0058479
2016-10-07 14:39abvNote Added: 0058480
2016-10-07 14:39abvAssigned Toabv => bugmaster
2016-10-07 14:39abvStatusresolved => reviewed
2016-10-07 16:00mkvAssigned Tobugmaster => mkv
2016-10-07 17:46kgvRelationship addedrelated to 0027941
2016-10-07 18:11gitNote Added: 0058492
2016-10-10 19:02mkvNote Added: 0058529
2016-10-10 19:04mkvNote Added: 0058530
2016-10-10 19:05mkvNote Added: 0058531
2016-10-10 19:05mkvAssigned Tomkv => abv
2016-10-10 19:05mkvStatusreviewed => feedback
2016-10-11 08:46abvAssigned Toabv => mkv
2016-10-11 08:47abvNote Added: 0058539
2016-10-11 13:12mkvNote Added: 0058569
2016-10-11 13:12mkvAssigned Tomkv => bugmaster
2016-10-11 13:12mkvStatusfeedback => tested
2016-10-20 15:13apnChangeset attached => occt master 3c162495
2016-10-20 15:13apnAssigned Tobugmaster => apn
2016-10-20 15:13apnStatustested => verified
2016-10-20 15:13apnResolutionopen => fixed
2016-10-28 21:42gitNote Added: 0059461
2016-12-09 16:30aivStatusverified => closed
2016-12-09 16:38aivFixed in Version => 7.1.0

Notes
(0058327)
git   
2016-09-29 19:08   
Branch CR27915 has been created by ski.

SHA-1: d870d0a07c0b864a64070e5de40f2da46dc16ffc


Detailed log of new commits:

Author: ski
Date: Thu Sep 29 19:08:20 2016 +0300

    0027915: Foundation Classes - remove the class NCollection_QuickSort
    
    Class NCollection_QuickSort was removed.
(0058328)
ski   
2016-09-29 19:10   
Dear msv,

please review.
(0058331)
msv   
2016-09-30 11:57   
Please wrap long line 96.
(0058332)
git   
2016-09-30 12:06   
Branch CR27915 has been updated forcibly by ski.

SHA-1: 62267893919681755aec8de8d8841591016525b2
(0058333)
ski   
2016-09-30 12:07   
Done.
(0058334)
kgv   
2016-09-30 12:12   
Removal of public API should be mentioned in porting notes.
(0058338)
msv   
2016-09-30 12:16   
Reviewed.
(0058339)
msv   
2016-09-30 12:18   
Please update porting notes.
(0058342)
git   
2016-09-30 12:54   
Branch CR27915 has been updated by ski.

SHA-1: 84180eecec7b73b61c21005d7bfb7b447dcf7e52


Detailed log of new commits:

Author: ski
Date: Thu Sep 29 19:08:20 2016 +0300

    Updated porting notes.

(0058343)
ski   
2016-09-30 12:55   
Porting notes were updated,

please review.
(0058345)
msv   
2016-09-30 14:49   
Reviewed.
(0058365)
git   
2016-10-03 15:23   
Branch CR27915 has been updated forcibly by mkv.

SHA-1: 47ed13fa8aed429bd633947e31b32d261c691c52
(0058405)
mkv   
2016-10-04 16:58   
Dear BugMaster,
Branch CR27915 was rebased on current master of occt git-repository.
SHA-1: 47ed13fa8aed429bd633947e31b32d261c691c52
(0058406)
mkv   
2016-10-04 16:59   
Dear BugMaster,
Branch CR27915 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: 47ed13fa8aed429bd633947e31b32d261c691c52

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 : 1145

Regressions/Differences/Improvements:
http://occt-tests/CR27915-master-OCCT/Debian70-64/bugs/moddata_3/bug24896.html [^]
http://occt-tests/CR27915-master-OCCT/Windows-64-VC10/bugs/moddata_3/bug24896.html [^]
bugs moddata_3 bug24896: FAILED

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 90771821 / 90543009 [+0.25%]
Total CPU difference: 19380.519999999833 / 19276.75999999978 [+0.54%]
products component :
Total MEMORY difference: 30032513 / 30036359 [-0.01%]
Total CPU difference: 5178.37999999997 / 5173.459999999983 [+0.10%]

Testing on Windows:
occt component :
Total MEMORY difference: 57228492 / 57236340 [-0.01%]
Total CPU difference: 19240.710937098607 / 18116.099728098634 [+6.21%]
products component :
Total MEMORY difference: 21274098 / 21238613 [+0.17%]
Total CPU difference: 5405.69985169998 / 4976.229098699953 [+8.63%]

There are following differences in images found by testdiff.
http://occt-tests/CR27915-master-OCCT/Debian70-64/diff-Debian70-64.html [^]
http://occt-tests/CR27915-master-OCCT/Windows-64-VC10/diff-Windows-64-VC10-image.html [^]
IMAGE bugs vis bug26056: bug26056.png differs
(0058407)
mkv   
2016-10-04 16:59   
Dear ski,
Branch CR27915 has been rejected due to:
- regressions/differences/improvements
- differences in images
(0058422)
ski   
2016-10-05 13:43   
Test case bugs moddata_3 bug24896:

This test case checks intersection between curve and planar face.
There are two solutions:
vertexes (66.6, 11.8556887323157, 0.3) and (66.6, -11.8556887483839, 0.3).
In these points distance between curve and face is equal to 0.
Function BRepExtrema_DistShapeShape founds these two solutions and sorts them by distance (distance is equal to 0 in each solution as i have already said).
In case of std::sort algorithm before last sorting of possible solutions:

0 1 2
0.2999899 1 3
0 1 4

First value in a row is a distance.
Second value is an index of the 1st sub-shape.
Third value is an index of the 2st sub-shape.

After sorting by std::sort we have:

0 1 2
0 1 4
0.2999899 1 3

In case of NCollection_QuickSort algorithm:
Before sorting:
0 1 2
0.2999899 1 3
0 1 4
After sorting:
0 1 4
0 1 2
0.2999899 1 3

So, it seems that solutions are right and just swapped. Test case should be corrected.



Differences in image bugs vis bug26056: bug26056.png
Images are different because of the same reason as above.

In case of std::sort algorithm
Before sorting
49.1999997992 1 1
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4
After soring
49.1999997992 1 1
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4

In case of NCollection_QuickSort algorithm
Before sorting
49.1999997992 1 1
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4
After soring
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4
49.1999997992 1 1

All solutions are right and can be used. Reference image should be updated.

Dear msv,

please comment.

(0058430)
abv   
2016-10-05 14:22   
Sergey, can you try to use std::stable_sort on these cases? As it seems from your results, std::sort already produces more stable results that NCollection_QuickSort, and thus is better, but stable_sort should give us guarantee of stability in all cases.
(0058432)
msv   
2016-10-05 15:09   
Sergey, I agree that algorithm DistShapeShape works right. However I have concern about the result image of the test case "bugs vis bug26056". Before the fix, the dimensions were drawn outside of the face and it was clear. Now the dimension lines (light green) overlap with the shapes, and the picture became unclear. Could you go deep in this test case and try to return the picture clear look?
(0058438)
git   
2016-10-05 16:16   
Branch CR27915 has been updated forcibly by ski.

SHA-1: 830c185ad9bf75334cfe95c93feba99ada2e7e17
(0058468)
git   
2016-10-06 18:08   
Branch CR27915 has been updated by ski.

SHA-1: 0313f9cf162d49ab62a03bf9dd2b153159d39e7b


Detailed log of new commits:

Author: ski
Date: Thu Oct 6 18:08:04 2016 +0300

    Direction of dimension lines was corrected.

(0058470)
ski   
2016-10-06 18:44   
Test case bugs moddata_3 bug24896:

Without patch (NCollection_QuickSort is used)
Method AIS_LengthDimension::InitEdgeFaceLength computes direction of the edge "anEdge", this direction will be used for direction of the dimension lines.
In case of edge "anEdge" direction is equal to gp_Dir(1,0,0), (First vertex of the edge = (-100, -100, 0), last = (100, -100, 0))
After that InitEdgeFaceLength computes minimum distance between the edge and the face.
In case of NCollection_QuickSort DistShapeShape returns two solutions:
1) (100, -100, 0) Last vertex of the edge "anEdge"
1) (100, -100, 50) Corresponding vertex on the "aFace"
2) (-100, -100, 0) First vertex of the edge "anEdge"
2) (-100, -100, 50) Corresponding vertex on the "aFace"
InitEdgeFaceLength takes the first solution (last vertex of the edge) and builds dimension lines from these vertexes using previusly calculated direction gp_Dir(1,0,0).
After that dimension lines are drawn outside of the face and the edge.

With patch (std::stable_sort is used)
Method AIS_LengthDimension::InitEdgeFaceLength computes direction as it was discribed above.
After that InitEdgeFaceLength computes minimum distance between the edge and the face.
In case of std::stable_sort DistShapeShape returns two solutions:
1) (-100, -100, 0) First vertex of the edge "anEdge"
1) (-100, -100, 50) Corresponding vertex on the "aFace"
2) (100, -100, 0) Last vertex of the edge "anEdge"
2) (100, -100, 50) Corresponding vertex on the "aFace"
InitEdgeFaceLength takes the first one (first vertex of the edge) and builds dimension lines from these vertexes using previusly calculated direction gp_Dir(1,0,0).
After that dimension lines are drawn inside the face and the edge.

So, it is nessecery to reverse the direction of dimension lines in case when first vertex of edge is used.
Changes are located in last commit of branch CR27915.

Dear abv,

please review.
(0058475)
git   
2016-10-07 12:16   
Branch CR27915 has been updated forcibly by ski.

SHA-1: 960e1f44f3441108f9b486d14a414f3ec2c52ac2
(0058477)
ski   
2016-10-07 13:08   
Dear abv,

I have corrected test case bugs moddata_3 bug24896.
Porting notes were modified as it was discussed.
Checking for vertexes was added to have correct direction of dimension lines.
(0058479)
git   
2016-10-07 14:38   
Branch CR27915 has been updated by abv.

SHA-1: 9ce1a1503e3f392575d9abf3d5439d971e587bdb


Detailed log of new commits:

Author: abv
Date: Fri Oct 7 14:38:17 2016 +0300

    // minor corrections in AIS

(0058480)
abv   
2016-10-07 14:39   
Reviewed with some corrections, please test
(0058492)
git   
2016-10-07 18:11   
Branch CR27915 has been updated forcibly by mkv.

SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633
(0058529)
mkv   
2016-10-10 19:02   
Dear BugMaster,
Branch CR27915 was rebased on current master of occt git-repository.
SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633
(0058530)
mkv   
2016-10-10 19:04   
Dear BugMaster,
Branch CR27915 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: 45f0ab8fc775e42dcfe586dece5806ff82ebf633

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 : 1129

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 90833860 / 91106900 [-0.30%]
Total CPU difference: 19412.109999999855 / 19439.88000000002 [-0.14%]
products component :
Total MEMORY difference: 30039694 / 30012726 [+0.09%]
Total CPU difference: 5240.689999999986 / 5239.289999999958 [+0.03%]

Testing on Windows:
occt component :
Total MEMORY difference: 57231122 / 57241724 [-0.02%]
Total CPU difference: 17941.65940989871 / 18173.586096598698 [-1.28%]
products component :
Total MEMORY difference: 21277667 / 21240754 [+0.17%]
Total CPU difference: 4995.323621099945 / 5008.287304199943 [-0.26%]

There are following differences in images found by testdiff.
http://occt-tests/CR27915-master-OCCT/Debian70-64/diff-Debian70-64.html [^]
http://occt-tests/CR27915-master-OCCT/Windows-64-VC10/diff-Windows-64-VC10-image.html [^]
IMAGE bugs vis bug26056: bug26056.png differs
(0058531)
mkv   
2016-10-10 19:05   
Dear abv,
Branch CR27915 has been rejected due to:
- differences in images
(0058539)
abv   
2016-10-11 08:47   
This difference is intentional, please proceed
(0058569)
mkv   
2016-10-11 13:12   
Dear BugMaster,
Branch CR27915 is TESTED.
(0059461)
git   
2016-10-28 21:42   
Branch CR27915 has been deleted by kgv.

SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633