MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0027915Open CASCADE[OCCT] OCCT:Foundation Classespublic2016-09-28 18:322016-12-09 16:38
Reportermsv 
Assigned Toapn 
PrioritynormalSeverityintegration request 
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version[OCCT] 7.0.0 
Target Version[OCCT] 7.1.0Fixed in Version[OCCT] 7.1.0 
Summary0027915: Foundation Classes - remove the class NCollection_QuickSort
DescriptionThe 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
Steps To ReproduceNot required
TagsNo tags attached.
Test case numberNot needed
Attached Files

- Relationships

-  Notes
(0058327)
git (administrator)
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 (developer)
2016-09-29 19:10

Dear msv,

please review.
(0058331)
msv (developer)
2016-09-30 11:57

Please wrap long line 96.
(0058332)
git (administrator)
2016-09-30 12:06

Branch CR27915 has been updated forcibly by ski.

SHA-1: 62267893919681755aec8de8d8841591016525b2
(0058333)
ski (developer)
2016-09-30 12:07

Done.
(0058334)
kgv (developer)
2016-09-30 12:12

Removal of public API should be mentioned in porting notes.
(0058338)
msv (developer)
2016-09-30 12:16

Reviewed.
(0058339)
msv (developer)
2016-09-30 12:18

Please update porting notes.
(0058342)
git (administrator)
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 (developer)
2016-09-30 12:55

Porting notes were updated,

please review.
(0058345)
msv (developer)
2016-09-30 14:49

Reviewed.
(0058365)
git (administrator)
2016-10-03 15:23

Branch CR27915 has been updated forcibly by mkv.

SHA-1: 47ed13fa8aed429bd633947e31b32d261c691c52
(0058405)
mkv (tester)
2016-10-04 16:58

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

Dear ski,
Branch CR27915 has been rejected due to:
- regressions/differences/improvements
- differences in images
(0058422)
ski (developer)
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 (manager)
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 (developer)
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 (administrator)
2016-10-05 16:16

Branch CR27915 has been updated forcibly by ski.

SHA-1: 830c185ad9bf75334cfe95c93feba99ada2e7e17
(0058468)
git (administrator)
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 (developer)
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 (administrator)
2016-10-07 12:16

Branch CR27915 has been updated forcibly by ski.

SHA-1: 960e1f44f3441108f9b486d14a414f3ec2c52ac2
(0058477)
ski (developer)
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 (administrator)
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 (manager)
2016-10-07 14:39

Reviewed with some corrections, please test
(0058492)
git (administrator)
2016-10-07 18:11

Branch CR27915 has been updated forcibly by mkv.

SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633
(0058529)
mkv (tester)
2016-10-10 19:02

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

Dear abv,
Branch CR27915 has been rejected due to:
- differences in images
(0058539)
abv (manager)
2016-10-11 08:47

This difference is intentional, please proceed
(0058569)
mkv (tester)
2016-10-11 13:12

Dear BugMaster,
Branch CR27915 is TESTED.
(0059461)
git (administrator)
2016-10-28 21:42

Branch CR27915 has been deleted by kgv.

SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633

- Related Changesets
occt: master 3c162495
Timestamp: 2016-10-13 10:40:12
Author: ski
Committer: apn
Details ] Diff ]
0027915: Foundation Classes - remove the class NCollection_QuickSort

Class NCollection_QuickSort was removed.
Direction of dimension lines was corrected.
Updated porting notes.
minor corrections in AIS
mod - dox/dev_guides/upgrade/upgrade.md Diff ] File ]
mod - src/AIS/AIS_LengthDimension.cxx Diff ] File ]
mod - src/BRepExtrema/BRepExtrema_DistShapeShape.cxx Diff ] File ]
mod - src/NCollection/FILES Diff ] File ]
rm - src/NCollection/NCollection_QuickSort.hxx Diff ] File ]
mod - tests/bugs/moddata_3/bug24896 Diff ] File ]
mod - tests/bugs/vis/bug26056 Diff ] File ]

- Issue History
Date Modified Username Field Change
2016-09-28 18:32 msv New Issue
2016-09-28 18:32 msv Assigned To => abv
2016-09-28 18:35 abv Assigned To abv => ski
2016-09-28 18:35 abv Status new => assigned
2016-09-29 12:32 kgv Severity tweak => integration request
2016-09-29 12:32 kgv Summary Remove the class NCollection_QuickSort => Foundation Classes - remove the class NCollection_QuickSort
2016-09-29 19:08 git Note Added: 0058327
2016-09-29 19:10 ski Note Added: 0058328
2016-09-29 19:10 ski Assigned To ski => msv
2016-09-29 19:10 ski Status assigned => resolved
2016-09-29 19:10 ski Steps to Reproduce Updated View Revisions
2016-09-30 11:57 msv Note Added: 0058331
2016-09-30 11:57 msv Assigned To msv => ski
2016-09-30 11:57 msv Status resolved => assigned
2016-09-30 12:06 git Note Added: 0058332
2016-09-30 12:07 ski Note Added: 0058333
2016-09-30 12:07 ski Assigned To ski => msv
2016-09-30 12:07 ski Status assigned => resolved
2016-09-30 12:12 kgv Note Added: 0058334
2016-09-30 12:16 msv Note Added: 0058338
2016-09-30 12:16 msv Assigned To msv => bugmaster
2016-09-30 12:16 msv Status resolved => reviewed
2016-09-30 12:18 msv Note Added: 0058339
2016-09-30 12:18 msv Assigned To bugmaster => ski
2016-09-30 12:18 msv Status reviewed => assigned
2016-09-30 12:54 git Note Added: 0058342
2016-09-30 12:55 ski Note Added: 0058343
2016-09-30 12:55 ski Assigned To ski => msv
2016-09-30 12:55 ski Status assigned => resolved
2016-09-30 14:49 msv Note Added: 0058345
2016-09-30 14:49 msv Assigned To msv => bugmaster
2016-09-30 14:49 msv Status resolved => reviewed
2016-10-03 12:35 mkv Assigned To bugmaster => mkv
2016-10-03 15:23 git Note Added: 0058365
2016-10-04 16:58 mkv Note Added: 0058405
2016-10-04 16:59 mkv Note Added: 0058406
2016-10-04 16:59 mkv Note Added: 0058407
2016-10-04 16:59 mkv Assigned To mkv => ski
2016-10-04 16:59 mkv Status reviewed => assigned
2016-10-04 17:00 mkv Test case number => Not needed
2016-10-05 13:43 ski Note Added: 0058422
2016-10-05 13:43 ski Assigned To ski => msv
2016-10-05 13:43 ski Status assigned => feedback
2016-10-05 14:22 abv Note Added: 0058430
2016-10-05 15:09 msv Note Added: 0058432
2016-10-05 15:09 msv Assigned To msv => ski
2016-10-05 15:09 msv Status feedback => assigned
2016-10-05 16:16 git Note Added: 0058438
2016-10-06 18:08 git Note Added: 0058468
2016-10-06 18:44 ski Note Added: 0058470
2016-10-06 18:44 ski Assigned To ski => abv
2016-10-06 18:44 ski Status assigned => resolved
2016-10-07 12:16 git Note Added: 0058475
2016-10-07 13:08 ski Note Added: 0058477
2016-10-07 14:38 git Note Added: 0058479
2016-10-07 14:39 abv Note Added: 0058480
2016-10-07 14:39 abv Assigned To abv => bugmaster
2016-10-07 14:39 abv Status resolved => reviewed
2016-10-07 16:00 mkv Assigned To bugmaster => mkv
2016-10-07 17:46 kgv Relationship added related to 0027941
2016-10-07 18:11 git Note Added: 0058492
2016-10-10 19:02 mkv Note Added: 0058529
2016-10-10 19:04 mkv Note Added: 0058530
2016-10-10 19:05 mkv Note Added: 0058531
2016-10-10 19:05 mkv Assigned To mkv => abv
2016-10-10 19:05 mkv Status reviewed => feedback
2016-10-11 08:46 abv Assigned To abv => mkv
2016-10-11 08:47 abv Note Added: 0058539
2016-10-11 13:12 mkv Note Added: 0058569
2016-10-11 13:12 mkv Assigned To mkv => bugmaster
2016-10-11 13:12 mkv Status feedback => tested
2016-10-20 15:13 apn Changeset attached => occt master 3c162495
2016-10-20 15:13 apn Assigned To bugmaster => apn
2016-10-20 15:13 apn Status tested => verified
2016-10-20 15:13 apn Resolution open => fixed
2016-10-28 21:42 git Note Added: 0059461
2016-12-09 16:30 user533 Status verified => closed
2016-12-09 16:38 user533 Fixed in Version => 7.1.0


Copyright © 2000 - 2018 MantisBT Team
Powered by Mantis Bugtracker