MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0029715Community[OCCT] OCCT:Meshpublic2018-04-23 16:002018-06-29 21:18
Reporterdrazmyslovich 
Assigned Toabv 
PrioritynormalSeverityminor 
StatusclosedResolutionfixed 
PlatformWindowsOSVC++ 2010OS Version64 bit
Product Version[OCCT] 7.1.0 
Target Version[OCCT] 7.3.0Fixed in Version[OCCT] 7.3.0 
Summary0029715: Mesh - Estimate the grid size of the acceleration structure by the complexity of the face
DescriptionBRepMesh_Delaun algorithm uses a grid as an acceleration structure for finding the circles and triangles, which can contain a point. The size of the grid is chosen according to the number of the input points of desired mesh: 2x2 (for <= 100 points), 5x5 (for <= 1000 points), 7x7 (for all other cases). Such heuristics works well for initial meshing. But, when the algorithm is used for the incremental meshing and much more points are added during the mesh refinement, the acceleration structure sizes become critical.
Steps To Reproducepload ALL
stepread slow.stp a *
time {incmesh a_1 0.0027}

for me it takes 244.9 seconds to mesh a single face
TagsNo tags attached.
Test case numberbugs mesh bug26889, bugs mesh bug29715
Attached Files? file icon slow.stp (58,179 bytes) 2018-04-23 16:00

- Relationships

-  Notes
(0075601)
git (administrator)
2018-04-23 16:05

Branch CR29715 has been created by drazmyslovich.

SHA-1: 0a9baccbb05cfbc98cf68898e6ae5f560f900329


Detailed log of new commits:

Author: drazmyslovich
Date: Mon Apr 23 15:04:29 2018 +0200

    0029715: Estimate the grid size of the acceleration structure by the complexity of the face
(0075602)
drazmyslovich (developer)
2018-04-23 16:09

The branch contains an estimation logic based on the complexity of the face and the desired face deflection.
This estimation reduces the meshing time for the provided face to 5.8 seconds. I was unable to find any model, which needs more time to mesh using the provided estimation.

Still, the best solution consists in implementing an adaptive grid acceleration structure, which splits itself, when necessary (adaptive quadtree)
(0075603)
drazmyslovich (developer)
2018-04-23 16:10

Dear Oleg, the branch is ready to be reviewed. Thank you.
(0075692)
oan (developer)
2018-04-26 12:39

Dear Dima,

I am glad to hear from you and thank you for the patch.

I would like to suggest the following modifications:
* eliminate copy-paste in BRepMesh_Delaun.cxx:

new constructor duplicates code of previously defined one.
Please move common part of both constructors to separate method.

I also suggest to move block

aBox.Enlarge (Precision);
superMesh (aBox);


back to perform( theVertexIndices ); method due to the same reason.
It will require addition cellsCountU and cellsCountV parameters to perform method.
Please also rename both parameters according to OCCT coding rules using "the" prefix.
Comments describing new functionality would also be useful.

* refactor code of BRepMesh_FastDiscretFace for the sake of better readability:

I suggest to move computation of errorneousFactorU and errorneousFactorV to separate method or function as well as part related to computation of cellsCountU, cellsCountV. This will make methods compact and simple to understand and debug.
Please also take into account OCCT coding rules and use proper prefix for local variables.

Please provide detail description for particular method and function, probably with formulas, so users can quickly understand notion of modifications without analysis of source code.

Computation of cellsCountV seems similar for the following cases:
+ else if (thetype == GeomAbs_SurfaceOfExtrusion)
+ {
+ // U is always a line
+ cellsCountU = (Standard_Integer)Ceiling (Pow (2, Log10 (nbVertices)));
+ Handle (Adaptor3d_HCurve) curve = gFace->BasisCurve ();
+ if (curve->GetType () == GeomAbs_Line || (curve->GetType () == GeomAbs_BSplineCurve && curve->Degree () < 2))
+ {
+ // planar case
+ cellsCountV = (Standard_Integer)Ceiling (Pow (2, Log10 (nbVertices)));
+ }
+ }
+ else if (thetype == GeomAbs_SurfaceOfRevolution)
+ {
+ Handle (Adaptor3d_HCurve) curve = gFace->BasisCurve ();
+ if (curve->GetType () == GeomAbs_Line || (curve->GetType () == GeomAbs_BSplineCurve && curve->Degree () < 2))
+ {
+ // planar, cylindrical, conical cases
+ cellsCountV = (Standard_Integer)Ceiling (Pow (2, Log10 (nbVertices)));
+ }
+ }

Thank you in advance,
Oleg.
(0075711)
git (administrator)
2018-04-27 12:00

Branch CR29715_1 has been created by drazmyslovich.

SHA-1: 84bd37a6d6bc6bb232c88d7fcd7ba6c32ee90388


Detailed log of new commits:

Author: drazmyslovich
Date: Mon Apr 23 15:04:29 2018 +0200

    0029715: Mesh - Estimate the grid size of the acceleration structure by the complexity of the face
    
    The circles acceleration structure sizes are estimated using the required deflection and the complexity of the face.
(0075712)
drazmyslovich (developer)
2018-04-27 12:02

Dear Oleg,

I applied the proposed modifications (and actually a bit more). Please, find the complete change set as a single commit in the new branch CR29715_1.

Thank you.
(0075719)
git (administrator)
2018-04-27 15:20

Branch CR29715_1 has been updated by oan.

SHA-1: e29d6eac84cdcb8b0eb62c0167049d62370bed45


Detailed log of new commits:

Author: oan
Date: Fri Apr 27 15:19:46 2018 +0300

    Minor code corrections

(0075729)
oan (developer)
2018-04-27 15:53

Dear Dima,

Thanks a lot!
I have made some minor corrections, could you please check it on your side.
Do you agree with that changes?


Mikhail,

For me patch is OK.
–°ould you please check it for possible remarks?
(0075730)
drazmyslovich (developer)
2018-04-27 16:13

Dear Oleg, yes, sure, I agree with your changes. Sorry, that I missed these pieces. Thank you!
(0075733)
oan (developer)
2018-04-27 16:55

Test report:

http://jenkins-test-11.nnov.opencascade.com/view/CR29715_1-master-oan/view/COMPARE/ [^]
(0075739)
msv (developer)
2018-04-28 12:18

According to the test report, the patch introduces the significant performance improvements:

CPU mesh advanced_shading B5: 12.1836781 / 58.2663735 [-79.09%]
CPU mesh advanced_incmesh_parallel B5: 8.2524529 / 18.6421195 [-55.73%]
CPU mesh advanced_mesh B5: 8.1588523 / 22.4329438 [-63.63%]
CPU mesh advanced_incmesh B5: 8.0964519 / 21.9337406 [-63.09%]
CPU bugs vis bug29412: 6.6144424 / 14.4924929 [-54.36%]
CPU bugs mesh bug25378_3_3: 2.5584164 / 23.9149533 [-89.30%]
CPU bugs mesh bug25378_1_3: 8.0808518 / 216.7009891 [-96.27%]
CPU bugs mesh bug26889: 16.7701075 / 80.2781146 [-79.11%]
CPU bugs moddata_3 bug25179: 24.180155 / 785.1998333 [-96.92%]

But it also adds several performance regressions:
CPU mesh advanced_incmesh_parallel A7: 3.7128238 / 2.2464144 [+65.28%]
CPU bugs mesh bug25378_2_3: 3.0420195 / 1.248008 [+143.75%]
CPU bugs mesh bug27453: 9.9372637 / 6.3492407 [+56.51%]
(0075897)
git (administrator)
2018-05-08 18:35

Branch CR29715_msv has been created by msv.

SHA-1: 4e6798d6b9a6dbba53de8ae52fb6ad8e2ecceeaf


Detailed log of new commits:

Author: msv
Date: Tue May 8 16:27:38 2018 +0300

    #Correct the method AdjustCellsCounts() taking into account different parametrization of surfaces of extrusion and revolution.
    
    #Use sqrt of the total number of vertices in the formula of calculation of cells count in one direction.
    
    #Correct calculation of cells count for torus and cylinder.

Author: msv
Date: Sat Apr 28 12:32:43 2018 +0300

    Update the test case bugs/mesh/bug26889 to accept improvement.
(0075898)
msv (developer)
2018-05-08 18:40

My remarks:

src/BRepMesh/BRepMesh_FastDiscretFace.cxx
- Line 189: parameterization of SurfaceOfExtrusion and SurfaceOfRevolution differ, since with the first U parameter goes along the basis curve, and with the second U parameter goes along the rotation angle. So, for SurfaceOfExtrusion theErrFactorU must be updated instead of theErrFactorV.
- Wrap too long lines 502, 503.
- The formulas on lines 502, 503 do not conform to calculation of DeltaX, DeltaY for Cylinder and Torus (see BRepMesh_FastDiscret.cxx:544,561)
- In the formula cells_count = 2 ^ log10 ( estimated_points_count ), estimated_points_count is the number of divisions in the given parametric dimension. But in the formula cells_count = 2 ^ log10 ( initial_vertex_count ) really the total number of vertices is passed. It is needed to get sqrt(initial_vertex_count) (or initial_vertex_count divided by the number of estimated points along the parametric dimension with curvature) to pass to that formula.
(0075899)
msv (developer)
2018-05-08 18:41

The branch CR29715_msv contains the work over remarks. I have started testing it in the Jenkins job CR29715-master-msv.
(0075914)
git (administrator)
2018-05-10 09:36

Branch CR29715_msv has been updated forcibly by msv.

SHA-1: 4ebc243a7879835d09733ff0adeda9169a254f11
(0075915)
git (administrator)
2018-05-10 09:48

Branch CR29715 has been updated forcibly by msv.

SHA-1: 6772fcfa687cbb413e10beba4cdd47fc2a29231f
(0075916)
msv (developer)
2018-05-10 09:54

The branch CR29715_msv has been tested OK. It has been combined to one commit and written as CR29715.
Dear bugmaster, please integrate it.
(0075917)
git (administrator)
2018-05-10 09:59

Branch CR29715_1 has been deleted by msv.

SHA-1: e29d6eac84cdcb8b0eb62c0167049d62370bed45
(0076141)
bugmaster (administrator)
2018-05-23 11:12

Combination -
OCCT branch : CR29715_msv SHA - 4e6798d6b9a6dbba53de8ae52fb6ad8e2ecceeaf
Products branch : master SHA - 300cf879a836fb8a5c4636713070ca9cf544749f
was compiled on Linux, MacOS and Windows platforms and tested in optimize mode.

Number of compiler warnings:
No new/fixed warnings

Regressions/Differences/Improvements:
No regressions/differences

CPU differences:
Debian70-64:
OCCT
Total CPU difference: 17248.210000000025 / 18243.73999999987 [-5.46%]
Products
Total CPU difference: 7422.500000000026 / 7499.630000000054 [-1.03%]
Windows-64-VC10:
OCCT
Total CPU difference: 16928.51091539861 / 18049.78370299853 [-6.21%]
Products
Total CPU difference: 7620.383648299952 / 7697.713343999945 [-1.00%]


Image differences :
No differences that require special attention

Memory differences :
No differences that require special attention
(0076931)
git (administrator)
2018-06-23 13:56

Branch CR29715 has been deleted by kgv.

SHA-1: 6772fcfa687cbb413e10beba4cdd47fc2a29231f
(0076932)
git (administrator)
2018-06-23 13:56

Branch CR29715_msv has been deleted by kgv.

SHA-1: 4ebc243a7879835d09733ff0adeda9169a254f11

- Related Changesets
occt: master c424cad6
Timestamp: 2018-04-23 13:04:29
Author: abv
Committer: abv
Details ] Diff ]
0029715: Mesh - Estimate the grid size of the acceleration structure by the complexity of the face

The circles acceleration structure sizes are estimated using the required deflection and the complexity of the face.
mod - src/BRepMesh/BRepMesh_Delaun.cxx Diff ] File ]
mod - src/BRepMesh/BRepMesh_Delaun.hxx Diff ] File ]
mod - src/BRepMesh/BRepMesh_FastDiscretFace.cxx Diff ] File ]
mod - tests/bugs/mesh/bug26889 Diff ] File ]
add - tests/bugs/mesh/bug29715 Diff ] File ]
occt: master 3e782664
Timestamp: 2018-04-23 13:04:29
Author: abv
Committer: abv
Details ] Diff ]
0029715: Mesh - Estimate the grid size of the acceleration structure by the complexity of the face

The circles acceleration structure sizes are estimated using the required deflection and the complexity of the face.
mod - src/BRepMesh/BRepMesh_Delaun.cxx Diff ] File ]
mod - src/BRepMesh/BRepMesh_Delaun.hxx Diff ] File ]
mod - src/BRepMesh/BRepMesh_FastDiscretFace.cxx Diff ] File ]
mod - tests/bugs/mesh/bug26889 Diff ] File ]
add - tests/bugs/mesh/bug29715 Diff ] File ]

- Issue History
Date Modified Username Field Change
2018-04-23 16:00 drazmyslovich New Issue
2018-04-23 16:00 drazmyslovich Assigned To => oan
2018-04-23 16:00 drazmyslovich File Added: slow.stp
2018-04-23 16:05 git Note Added: 0075601
2018-04-23 16:09 drazmyslovich Note Added: 0075602
2018-04-23 16:10 kgv Summary Meshing of BSpline faces takes a lot of time due to the inefficient acceleration structure => Mesh - Estimate the grid size of the acceleration structure by the complexity of the face
2018-04-23 16:10 kgv Steps to Reproduce Updated View Revisions
2018-04-23 16:10 drazmyslovich Note Added: 0075603
2018-04-23 16:10 drazmyslovich Status new => resolved
2018-04-23 16:10 drazmyslovich Steps to Reproduce Updated View Revisions
2018-04-26 12:39 oan Note Added: 0075692
2018-04-26 12:39 oan Assigned To oan => drazmyslovich
2018-04-26 12:39 oan Status resolved => feedback
2018-04-27 12:00 git Note Added: 0075711
2018-04-27 12:02 drazmyslovich Note Added: 0075712
2018-04-27 12:02 drazmyslovich Assigned To drazmyslovich => oan
2018-04-27 12:02 drazmyslovich Status feedback => resolved
2018-04-27 15:20 git Note Added: 0075719
2018-04-27 15:44 oan Assigned To oan => drazmyslovich
2018-04-27 15:45 oan Assigned To drazmyslovich => msv
2018-04-27 15:53 oan Note Added: 0075729
2018-04-27 16:13 drazmyslovich Note Added: 0075730
2018-04-27 16:55 oan Note Added: 0075733
2018-04-28 12:18 msv Note Added: 0075739
2018-05-08 18:35 git Note Added: 0075897
2018-05-08 18:40 msv Note Added: 0075898
2018-05-08 18:41 msv Note Added: 0075899
2018-05-10 09:36 git Note Added: 0075914
2018-05-10 09:48 git Note Added: 0075915
2018-05-10 09:54 msv Note Added: 0075916
2018-05-10 09:54 msv Assigned To msv => bugmaster
2018-05-10 09:54 msv Status resolved => reviewed
2018-05-10 09:59 git Note Added: 0075917
2018-05-23 11:07 bugmaster Test case number => bugs mesh bug26889, bugs mesh bug29715
2018-05-23 11:12 bugmaster Note Added: 0076141
2018-05-23 11:12 bugmaster Status reviewed => tested
2018-05-25 17:15 abv Target Version 7.4.0* => 7.3.0
2018-05-29 12:33 abv Changeset attached => occt master c424cad6
2018-05-29 12:33 abv Assigned To bugmaster => abv
2018-05-29 12:33 abv Status tested => verified
2018-05-29 12:33 abv Resolution open => fixed
2018-05-29 15:54 abv Changeset attached => occt master 3e782664
2018-06-23 13:56 git Note Added: 0076931
2018-06-23 13:56 git Note Added: 0076932
2018-06-29 21:13 user533 Fixed in Version => 7.3.0
2018-06-29 21:18 user533 Status verified => closed


Copyright © 2000 - 2018 MantisBT Team
Powered by Mantis Bugtracker