View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0029715CommunityOCCT:Meshpublic2018-04-23 16:002018-06-29 21:18
Reporterdrazmyslovich Assigned Toabv 
PrioritynormalSeverityminor 
Status closedResolutionfixed 
PlatformWindowsOSVC++ 2010 
Product Version7.1.0 
Target Version7.3.0Fixed in Version7.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

  • slow.stp (58,179 bytes)

Activities

drazmyslovich

2018-04-23 16:00

developer  

slow.stp (58,179 bytes)

git

2018-04-23 16:05

administrator   ~0075601

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

drazmyslovich

2018-04-23 16:09

developer   ~0075602

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)

drazmyslovich

2018-04-23 16:10

developer   ~0075603

Dear Oleg, the branch is ready to be reviewed. Thank you.

oan

2018-04-26 12:39

developer   ~0075692

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.

git

2018-04-27 12:00

administrator   ~0075711

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.

drazmyslovich

2018-04-27 12:02

developer   ~0075712

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.

git

2018-04-27 15:20

administrator   ~0075719

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

oan

2018-04-27 15:53

developer   ~0075729

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?

drazmyslovich

2018-04-27 16:13

developer   ~0075730

Dear Oleg, yes, sure, I agree with your changes. Sorry, that I missed these pieces. Thank you!

oan

2018-04-27 16:55

developer   ~0075733

Test report:

http://jenkins-test-11.nnov.opencascade.com/view/CR29715_1-master-oan/view/COMPARE/

msv

2018-04-28 12:18

developer   ~0075739

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%]

git

2018-05-08 18:35

administrator   ~0075897

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.

msv

2018-05-08 18:40

developer   ~0075898

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.

msv

2018-05-08 18:41

developer   ~0075899

The branch CR29715_msv contains the work over remarks. I have started testing it in the Jenkins job CR29715-master-msv.

git

2018-05-10 09:36

administrator   ~0075914

Branch CR29715_msv has been updated forcibly by msv.

SHA-1: 4ebc243a7879835d09733ff0adeda9169a254f11

git

2018-05-10 09:48

administrator   ~0075915

Branch CR29715 has been updated forcibly by msv.

SHA-1: 6772fcfa687cbb413e10beba4cdd47fc2a29231f

msv

2018-05-10 09:54

developer   ~0075916

The branch CR29715_msv has been tested OK. It has been combined to one commit and written as CR29715.
Dear bugmaster, please integrate it.

git

2018-05-10 09:59

administrator   ~0075917

Branch CR29715_1 has been deleted by msv.

SHA-1: e29d6eac84cdcb8b0eb62c0167049d62370bed45

bugmaster

2018-05-23 11:12

administrator   ~0076141

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

git

2018-06-23 13:56

administrator   ~0076931

Branch CR29715 has been deleted by kgv.

SHA-1: 6772fcfa687cbb413e10beba4cdd47fc2a29231f

git

2018-06-23 13:56

administrator   ~0076932

Branch CR29715_msv has been deleted by kgv.

SHA-1: 4ebc243a7879835d09733ff0adeda9169a254f11

Related Changesets

occt: master c424cad6

2018-04-23 13:04:29

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.		 Affected Issues
0029715
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

2018-04-23 13:04:29

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.		 Affected Issues
0029715
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
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
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 aiv Fixed in Version => 7.3.0
2018-06-29 21:18 aiv Status verified => closed