View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0028639Open CASCADEOCCT:Modeling Algorithmspublic2017-04-07 07:342017-11-24 11:22
ReporteremvAssigned Tobugmaster  
PrioritynormalSeverityminor 
Status closedResolutionfixed 
Product Version7.1.0 
Target Version7.2.0Fixed in Version7.2.0 
Summary0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
DescriptionThe implementation of some methods of the IntPolyh_MaillageAffinage class is inefficient and sometimes most of the time is spent on the creation of the triangles instead of their intersection. It is necessary to revise these methods and make them more efficient. It will allow improving the performance of the algorithm.
Steps To ReproduceNot needed.
TagsNo tags attached.
Test case numberNot needed

Relationships

related to 0028599 closedapn Open CASCADE Replacement of old Boolean operations with new ones in BRepProj_Projection algorithm 

Activities

git

2017-04-12 10:05

administrator   ~0065164

Branch CR28639 has been created by emv.

SHA-1: 2440a6e876c7a9e6d18f1574ba50caf8bb354bb6


Detailed log of new commits:

Author: emv
Date: Fri Apr 7 07:43:44 2017 +0300

    0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
    
    The following improvements have been made:
    1. Linking edges to triangles while creating the edges.
    2. Replacing the array of couples of intersecting triangles with the list to avoid unnecessary allocations of memory.
    3. Using the algorithm of unbalanced binary tree when looking for pairs of interfering triangles.
    4. Building bounding boxes for the triangles only once and then reusing it.
    5. Making the simple methods of the IntPolyh_Point, IntPolyh_Edge, IntPolyh_Triangle, IntPolyh_Couple classes inline.

emv

2017-04-12 10:09

developer   ~0065165

Last edited: 2017-04-12 10:14

 Dear Mikhail, could you please review the branch CR28639?

Local testing of that branch has shown the following improvements comparing to the master:
CPU boolean bcut_complex G2: 2.5 / 5.328125 [-53.08%]
CPU boolean bcut_complex N9: 0.671875 / 3.40625 [-80.28%]
CPU boolean bfuse_complex F1: 1.625 / 2.953125 [-44.97%]
CPU boolean bfuse_complex F2: 3.46875 / 6.09375 [-43.08%]
CPU boolean bfuse_complex F8: 1.9375 / 2.90625 [-33.33%]
CPU boolean bopcommon_complex D8: 8 / 16.703125 [-52.10%]
CPU boolean bopcommon_complex D9: 8.03125 / 16.6875 [-51.87%]
CPU boolean bopcommon_complex E5: 0.28125 / 1.546875 [-81.82%]
CPU boolean bopcommon_complex E6: 0.28125 / 1.5 [-81.25%]
CPU boolean bopcut_complex E1: 7.484375 / 16.328125 [-54.16%]
CPU boolean bopcut_complex E2: 7.625 / 16.125 [-52.71%]
CPU boolean bopcut_complex E7: 0.265625 / 1.5625 [-83.00%]
CPU boolean bopcut_complex E8: 0.28125 / 1.5 [-81.25%]
CPU boolean bopcut_complex P8: 5.46875 / 10.109375 [-45.90%]
CPU boolean bopfuse_complex C9: 7.546875 / 16.203125 [-53.42%]
CPU boolean bopfuse_complex D1: 7.71875 / 16.359375 [-52.82%]
CPU boolean bopfuse_complex D6: 0.265625 / 1.5 [-82.29%]
CPU boolean bopfuse_complex D7: 0.3125 / 1.5 [-79.17%]
CPU boolean bopfuse_complex J7: 1.46875 / 3.40625 [-56.88%]
CPU boolean bopfuse_simple ZP6: 2 / 5.015625 [-60.12%]
CPU boolean bsection R9: 1.84375 / 3.5625 [-48.25%]
CPU boolean gdml_private ZG4: 1.34375 / 36.921875 [-96.36%]
CPU boolean gdml_public A9: 4.078125 / 9.171875 [-55.54%]
CPU bugs modalg_1 buc60462_1: 1.875 / 3.59375 [-47.83%]
CPU bugs modalg_1 bug18186: 1.484375 / 2.28125 [-34.93%]
CPU bugs modalg_1 bug19071: 0.515625 / 1.109375 [-53.52%]
CPU bugs modalg_2 bug335: 0.453125 / 1.75 [-74.11%]
CPU bugs modalg_3 bug600: 4.59375 / 112.953125 [-95.93%]
CPU bugs modalg_4 bug697_2: 2.828125 / 4.15625 [-31.95%]
CPU bugs modalg_4 bug697_4: 2.96875 / 4.34375 [-31.65%]
CPU bugs modalg_4 bug697_7: 2.96875 / 4.296875 [-30.91%]
CPU bugs modalg_4 bug697_8: 2.96875 / 4.328125 [-31.41%]
CPU bugs modalg_5 bug25456: 2.6875 / 11.453125 [-76.53%]
CPU bugs modalg_6 bug22609: 1.1875 / 2.078125 [-42.86%]
CPU bugs modalg_6 bug26450: 3.765625 / 6.421875 [-41.36%]
CPU bugs modalg_6 bug26535: 2.1875 / 3 [-27.08%]
CPU bugs modalg_6 bug26621: 29.640625 / 42.59375 [-30.41%]
CPU bugs modalg_6 bug26848: 4.859375 / 113 [-95.70%]
CPU bugs modalg_6 bug26938_1: 4.03125 / 6.09375 [-33.85%]
CPU bugs modalg_6 bug26938_4: 3.3125 / 4.703125 [-29.57%]
CPU bugs modalg_6 bug27615: 29.859375 / 36.640625 [-18.51%]
CPU bugs modalg_6 bug27746_1: 5.890625 / 9.953125 [-40.82%]
CPU bugs moddata_1 bug152_1: 0.4375 / 10.40625 [-95.80%]
CPU bugs moddata_1 bug152_2: 0.453125 / 9.09375 [-95.02%]
CPU bugs moddata_2 bug228: 8.03125 / 16.640625 [-51.74%]
CPU bugs moddata_3 bug599: 4.765625 / 112.515625 [-95.76%]
CPU chamfer dist_angle_complex C1: 1.09375 / 3.03125 [-63.92%]
CPU chamfer dist_angle_sequence C1: 1.625 / 2.734375 [-40.57%]
CPU chamfer dist_dist_complex C1: 0.875 / 2.578125 [-66.06%]
CPU chamfer dist_dist_sequence C1: 1.609375 / 2.8125 [-42.78%]
CPU chamfer equal_dist_complex C1: 1.140625 / 3.0625 [-62.76%]
CPU chamfer equal_dist_sequence C1: 1.3125 / 2.71875 [-51.72%]
CPU perf modalg bug19793_2: 19.546875 / 55.59375 [-64.84%]
CPU prj base C7: 0.359375 / 2.5625 [-85.98%]
CPU prj base C8: 0.9375 / 6.03125 [-84.46%]
CPU prj base D1: 0.46875 / 3.1875 [-85.29%]
CPU prj base D2: 0.609375 / 4.09375 [-85.11%]
CPU prj base D4: 0.171875 / 0.828125 [-79.25%]
CPU prj base D5: 0.21875 / 1.09375 [-80.00%]
CPU prj base D8: 1.125 / 7.703125 [-85.40%]
CPU prj base D9: 0.3125 / 2.203125 [-85.82%]
CPU prj base E2: 0.125 / 0.78125 [-84.00%]
CPU prj base E3: 0.453125 / 2.4375 [-81.41%]
CPU prj base E4: 0.1875 / 1.4375 [-86.96%]
CPU prj base E5: 0.28125 / 1.4375 [-80.43%]
CPU prj base E6: 0.453125 / 2.5625 [-82.32%]
CPU prj base E7: 0.359375 / 2.171875 [-83.45%]
CPU prj base F5: 0.25 / 1.328125 [-81.18%]
CPU prj base F7: 0.25 / 1.25 [-80.00%]
CPU prj base G1: 0.1875 / 0.84375 [-77.78%]
CPU prj base G2: 0.09375 / 0.65625 [-85.71%]
CPU prj base G3: 0.28125 / 1.59375 [-82.35%]
CPU prj base G4: 0.34375 / 1.890625 [-81.82%]
CPU prj base G5: 0.515625 / 2.984375 [-82.72%]
CPU prj base G6: 0.484375 / 3.515625 [-86.22%]
CPU prj base G8: 0.1875 / 1.171875 [-84.00%]
CPU prj base G9: 0.140625 / 0.890625 [-84.21%]
CPU prj base H1: 0.25 / 1.21875 [-79.49%]
CPU prj base H2: 0.34375 / 2.046875 [-83.21%]
CPU prj base H4: 0.40625 / 2.40625 [-83.12%]
CPU prj base H5: 0.96875 / 7.078125 [-86.31%]
CPU prj base H6: 0.625 / 4.953125 [-87.38%]
CPU prj base H7: 0.625 / 4.703125 [-86.71%]
CPU prj base H8: 0.34375 / 2.203125 [-84.40%]
CPU prj base H9: 0.375 / 2.578125 [-85.45%]
CPU prj base I1: 0.359375 / 2.28125 [-84.25%]
CPU prj base I2: 0.3125 / 2.21875 [-85.92%]
CPU prj base I3: 1.421875 / 10.546875 [-86.52%]
CPU prj base I4: 0.46875 / 3.5 [-86.61%]


The list shows only the most noticeable improvements.

git

2017-04-14 13:06

administrator   ~0065214

Branch CR28639 has been updated forcibly by emv.

SHA-1: 34e5d782d6c90ab6d875d3efbf5f0a8dff676461

emv

2017-04-14 13:06

developer   ~0065215

The branch CR28474 has been rebased on current master.

git

2017-04-14 13:16

administrator   ~0065217

Branch CR28639 has been updated forcibly by emv.

SHA-1: 109fb801f0c23e8aa4da85884a42d68acac73316

msv

2017-04-19 10:27

developer   ~0065330

Remarks:

src\IntPolyh\FILES
- keep alphabit sorting of list of files.

src\IntPolyh\IntPolyh_Edge.hxx
src\IntPolyh\IntPolyh_Point.hxx
src\IntPolyh\IntPolyh_Couple.hxx
src\IntPolyh\IntPolyh_Triangle.hxx
- As you are changing 90% of the source code rename fields according to coding rules.

src\IntPolyh\IntPolyh_Couple.hxx
- 53: it returns integer, so it is not TRUE.
- 58: "the angle of between", "of" is extra.

src\IntPolyh\IntPolyh_CoupleMapHasher.hxx
- DEFINE_STANDARD_ALLOC is not needed.

src\IntPolyh\IntPolyh_Triangle.hxx
- get rid of "if" statements in GetEdgeNumber, SetEdge, GetEdgeOrientation, SetEdgeOrientation, GetNextTriangle2, LinkEdges2Triangle, SetEdgeAndOrientation by replacing fields p1,p2,p3,e1,e2,e3,oe1,oe2,oe3 with C arrays p[3], e[3], oe[3].
- compact boolean flags using bit fields.

src\IntPolyh\IntPolyh_Triangle.cxx
- The method IntPolyh_Triangle::BoundingBox is to be optimized:
  - use cached isDegenerated flag;
  - avoid enlarge and setting gap on repeated calls.

src\IntPolyh\IntPolyh_MaillageAffinage.cxx
- 178: make it private.
- In the method TriangleCompare now it became useless to check the number of contacts by NbTTC. So, the lines 3200-3202, 3231-3232 are to be removed.

src\IntPolyh\IntPolyh_MaillageAffinage.hxx
- Remove declaration of not implemented method GetArrayOfSP.
- Remove unused field TStartPoints.
- Remove unused class IntPolyh_ArrayOfStartPoints.hxx
- Remove unused methods:
 TriangleComparePSP
 StartPointsCalcul.
 NextStartingPointsResearch
 StartingPointsResearch

git

2017-04-20 15:24

administrator   ~0065398

Branch CR28639 has been updated by emv.

SHA-1: d629fd18d4a161e98cce65f620c35955864f2068


Detailed log of new commits:

Author: emv
Date: Thu Apr 20 11:41:41 2017 +0300

    Correction of the *IntPolyh_Triangle* class.
    
    Upgrade guide has been updated with the removed methods.

Author: emv
Date: Wed Apr 19 16:36:01 2017 +0300

    Correction of the *IntPolyh_Point* class.

Author: emv
Date: Wed Apr 19 16:21:45 2017 +0300

    Correction of the *IntPolyh_Edge* class.

Author: emv
Date: Wed Apr 19 16:00:20 2017 +0300

    Correction of the clas *IntPolyh_Couple*.

Author: emv
Date: Wed Apr 19 14:58:28 2017 +0300

    // Corrections according to remarks;
    
    * The method *IntPolyh_Triangle::SetEdgeandOrientation* has been removed as unused;
    * The following methods of the *IntPolyh_MaillageAffinage* have been removed as unused:
     - *LinkEdges2Triangles*;
     - *TriangleEdgeContact2*;
     - *StartingPointsResearch2*;
     - *NextStartingPointsResearch2*;
     - *TriangleComparePSP*;
     - *StartPointsCalcul*.

emv

2017-04-20 15:29

developer   ~0065399

Dear Mikhail, please review the updated branch. Do not pay too much attention to commit messages, they will be updated in the final branch with single commit.

git

2017-04-20 15:30

administrator   ~0065400

Branch CR28639_1 has been created by emv.

SHA-1: beb827d193b281b494b648717985d20db0c38c21


Detailed log of new commits:

Author: emv
Date: Fri Apr 7 07:43:44 2017 +0300

    0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
    
    The following improvements have been made:
    1. Linking edges to triangles while creating the edges.
    2. Replacing the array of couples of intersecting triangles with the list to avoid unnecessary allocations of memory.
    3. Using the algorithm of unbalanced binary tree when looking for pairs of interfering triangles.
    4. Building bounding boxes for the triangles only once and then reusing it.
    5. Making the simple methods of the IntPolyh_Point, IntPolyh_Edge, IntPolyh_Triangle, IntPolyh_Couple classes inline.
    6. The following methods of the *IntPolyh_Triangle* class have been removed as unused:
      - *CheckCommonEdge*
      - *SetEdgeandOrientation*
      - *MultipleMiddleRefinement2*.
    7. The method *IntPolyh_Triangle::TriangleDeflection* has been replaced with the *IntPolyh_Triangle::ComputeDeflection*.
    8. The following methods of the *IntPolyh_MaillageAffinage* class have been removed as unused:
      - *LinkEdges2Triangles*;
      - *TriangleEdgeContact2*;
      - *StartingPointsResearch2*;
      - *NextStartingPointsResearch2*;
      - *TriangleComparePSP*;
      - *StartPointsCalcul*.

msv

2017-04-21 11:57

developer   ~0065416

Remarks:

src\IntPolyh\IntPolyh_Couple.hxx
src\IntPolyh\IntPolyh_Point.hxx
- Using of bit field is unjustified for only one variable.

src\IntPolyh\IntPolyh_Triangle.cxx
- in the method IntPolyh_Triangle::Dump, pass int argument to printf instead of bool.

git

2017-04-21 12:08

administrator   ~0065418

Branch CR28639_1 has been updated by emv.

SHA-1: d8dd328be4993a1edcb81c62c3349ed9d719fcf9


Detailed log of new commits:

Author: emv
Date: Fri Apr 21 12:08:17 2017 +0300

    // Corrections according to remarks.

emv

2017-04-21 12:09

developer   ~0065419

Done. Please review the git branch CR28639_1.

msv

2017-04-21 12:12

developer   ~0065420

Reviewed.

git

2017-04-21 16:00

administrator   ~0065428

Branch CR28639_1 has been updated forcibly by mkv.

SHA-1: 0ac0ed9c7fdbaae169278ccc4e016e8e83b3b6ce

mkv

2017-04-24 14:23

tester   ~0065476

Dear BugMaster,
Branch CR28639_1 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: 0ac0ed9c7fdbaae169278ccc4e016e8e83b3b6ce

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: 91790382 / 91810384 [-0.02%]
Total CPU difference: 18996.680000000324 / 19561.10000000033 [-2.89%]
products component :
Total MEMORY difference: 31249691 / 31264414 [-0.05%]
Total CPU difference: 5414.379999999983 / 5400.509999999974 [+0.26%]
Testing on Windows:
occt component :
Total MEMORY difference: 58037467 / 58034445 [+0.01%]
Total CPU difference: 17316.891004998637 / 18122.277367698553 [-4.44%]
products component :
Total MEMORY difference: 22650125 / 22611847 [+0.17%]
Total CPU difference: 5318.339291699976 / 5410.192680499973 [-1.70%]

There are no differences in images found by testdiff.

mkv

2017-04-24 14:24

tester   ~0065477

Dear BugMaster,
Branch CR28639_1 is TESTED.

git

2017-04-28 12:24

administrator   ~0065634

Branch CR28639_1 has been updated by emv.

SHA-1: 416145208d7ab4534e0de6b4544e355703e17616


Detailed log of new commits:

Author: emv
Date: Fri Apr 28 12:23:04 2017 +0300

    // Elimination of the warning.

git

2017-05-12 11:36

administrator   ~0065959

Branch CR28639 has been deleted by kgv.

SHA-1: d629fd18d4a161e98cce65f620c35955864f2068

git

2017-05-12 11:36

administrator   ~0065960

Branch CR28639_1 has been deleted by kgv.

SHA-1: 416145208d7ab4534e0de6b4544e355703e17616

Related Changesets

occt: master 68b07699

2017-04-07 04:43:44

emv


Committer: bugmaster Details Diff		 0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm

The following improvements have been made:
1. Linking edges to triangles while creating the edges.
2. Replacing the array of couples of intersecting triangles with the list to avoid unnecessary allocations of memory.
3. Using the algorithm of unbalanced binary tree when looking for pairs of interfering triangles.
4. Building bounding boxes for the triangles only once and then reusing it.
5. Making the simple methods of the IntPolyh_Point, IntPolyh_Edge, IntPolyh_Triangle, IntPolyh_Couple classes inline.
6. The following methods of the *IntPolyh_Triangle* class have been removed as unused:
- *CheckCommonEdge*
- *SetEdgeandOrientation*
- *MultipleMiddleRefinement2*.
7. The method *IntPolyh_Triangle::TriangleDeflection* has been replaced with the *IntPolyh_Triangle::ComputeDeflection*.
8. The following methods of the *IntPolyh_MaillageAffinage* class have been removed as unused:
- *LinkEdges2Triangles*;
- *TriangleEdgeContact2*;
- *StartingPointsResearch2*;
- *NextStartingPointsResearch2*;
- *TriangleComparePSP*;
- *StartPointsCalcul*.		 Affected Issues
0028639
mod - dox/dev_guides/upgrade/upgrade.md Diff File
mod - src/IntPolyh/FILES Diff File
rm - src/IntPolyh/IntPolyh_ArrayOfStartPoints.hxx Diff File
mod - src/IntPolyh/IntPolyh_Couple.cxx Diff File
mod - src/IntPolyh/IntPolyh_Couple.hxx Diff File
add - src/IntPolyh/IntPolyh_CoupleMapHasher.hxx Diff File
mod - src/IntPolyh/IntPolyh_Edge.cxx Diff File
mod - src/IntPolyh/IntPolyh_Edge.hxx Diff File
mod - src/IntPolyh/IntPolyh_Intersection.cxx Diff File
mod - src/IntPolyh/IntPolyh_Intersection.hxx Diff File
mod - src/IntPolyh/IntPolyh_Intersection_1.cxx Diff File
mod - src/IntPolyh/IntPolyh_MaillageAffinage.cxx Diff File
mod - src/IntPolyh/IntPolyh_MaillageAffinage.hxx Diff File
mod - src/IntPolyh/IntPolyh_Point.cxx Diff File
mod - src/IntPolyh/IntPolyh_Point.hxx Diff File
mod - src/IntPolyh/IntPolyh_Triangle.cxx Diff File
mod - src/IntPolyh/IntPolyh_Triangle.hxx Diff File

Issue History

Date Modified Username Field Change
2017-04-07 07:34 emv New Issue
2017-04-07 07:34 emv Assigned To => msv
2017-04-07 07:34 emv Assigned To msv => emv
2017-04-07 07:34 emv Status new => assigned
2017-04-07 09:28 emv Relationship added related to 0028599
2017-04-12 10:05 git Note Added: 0065164
2017-04-12 10:09 emv Note Added: 0065165
2017-04-12 10:09 emv Assigned To emv => msv
2017-04-12 10:09 emv Status assigned => resolved
2017-04-12 10:09 emv Steps to Reproduce Updated
2017-04-12 10:13 emv Note Edited: 0065165
2017-04-12 10:14 emv Note Edited: 0065165
2017-04-14 13:06 git Note Added: 0065214
2017-04-14 13:06 emv Note Added: 0065215
2017-04-14 13:16 git Note Added: 0065217
2017-04-19 10:27 msv Note Added: 0065330
2017-04-19 10:27 msv Assigned To msv => emv
2017-04-19 10:27 msv Status resolved => assigned
2017-04-20 15:24 git Note Added: 0065398
2017-04-20 15:29 emv Note Added: 0065399
2017-04-20 15:29 emv Assigned To emv => msv
2017-04-20 15:29 emv Status assigned => resolved
2017-04-20 15:30 git Note Added: 0065400
2017-04-21 11:57 msv Note Added: 0065416
2017-04-21 11:57 msv Assigned To msv => emv
2017-04-21 11:57 msv Status resolved => assigned
2017-04-21 12:08 git Note Added: 0065418
2017-04-21 12:09 emv Note Added: 0065419
2017-04-21 12:09 emv Assigned To emv => msv
2017-04-21 12:09 emv Status assigned => resolved
2017-04-21 12:12 msv Note Added: 0065420
2017-04-21 12:12 msv Assigned To msv => bugmaster
2017-04-21 12:12 msv Status resolved => reviewed
2017-04-21 12:34 mkv Assigned To bugmaster => mkv
2017-04-21 16:00 git Note Added: 0065428
2017-04-24 14:23 mkv Note Added: 0065476
2017-04-24 14:24 mkv Note Added: 0065477
2017-04-24 14:24 mkv Assigned To mkv => bugmaster
2017-04-24 14:24 mkv Status reviewed => tested
2017-04-24 14:24 mkv Test case number => Not needed
2017-04-28 12:24 git Note Added: 0065634
2017-04-28 13:08 bugmaster Changeset attached => occt master 68b07699
2017-04-28 13:08 bugmaster Status tested => verified
2017-04-28 13:08 bugmaster Resolution open => fixed
2017-05-12 11:36 git Note Added: 0065959
2017-05-12 11:36 git Note Added: 0065960
2017-09-29 16:19 aiv Fixed in Version => 7.2.0
2017-09-29 16:25 aiv Status verified => closed