MantisBT - Community
View Issue Details
0024923Community[OCCT] OCCT:Meshpublic2014-05-14 18:262015-05-14 16:25
WindowsVC++ 201064 bit
[OCCT] 6.6.0 
[OCCT] 6.9.0[OCCT] 6.9.0 
bugs mesh(017) bug24923
0024923: BRepMesh_CircleTool produces bad circles
Due to math precision error the central point of a triangle calculated by BRepMesh_CircleTool isn't always equidistant to all triangle vertices, what results in the bad circle generated for the triangle. As an effect: Select function doesn't return the index of the triangle for the triangle vertices.
This error affects the mesher result.
No tags attached.
related to 0023105closed oan Community Exception during Meshing / Missing triangles 
related to 0025044closed bugmaster Community BRepMesh tweaks 
png OCC660_fix.png (36,956) 2014-10-16 13:23
cpp circletool_unittest.cpp (7,776) 2014-10-20 13:08
png cylinder_top_old.png (8,297) 2015-04-28 09:56
png cylinder_top_new.png (10,474) 2015-04-28 09:57
Issue History
2014-05-14 18:26drazmyslovichNew Issue
2014-05-14 18:26drazmyslovichAssigned To => drazmyslovich
2014-05-14 18:29drazmyslovichNote Added: 0029336
2014-05-14 18:29drazmyslovichStatusnew => resolved
2014-05-14 18:50abvAssigned Todrazmyslovich => pdn
2014-05-14 18:50abvTarget VersionUnscheduled => 6.8.0
2014-05-15 11:48pdnNote Added: 0029344
2014-05-15 15:57drazmyslovichNote Added: 0029349
2014-05-15 16:15abvNote Added: 0029351
2014-05-15 16:15abvRelationship addedrelated to 0023105
2014-05-15 16:19drazmyslovichNote Added: 0029352
2014-05-21 10:40pdnAssigned Topdn => abk
2014-06-17 12:47aivProjectOpen CASCADE => Community
2014-06-20 14:19oanCategoryOCCT:Modeling Algorithms => OCCT:Mesh
2014-07-01 14:27drazmyslovichRelationship addedrelated to 0025044
2014-07-07 12:45abvAssigned Toabk => oan
2014-10-16 13:22oanNote Added: 0033202
2014-10-16 13:22oanAssigned Tooan => drazmyslovich
2014-10-16 13:22oanStatusresolved => feedback
2014-10-16 13:23oanFile Added: OCC660_fix.png
2014-10-20 12:46drazmyslovichFile Added: circletool_unittest.cpp
2014-10-20 13:08drazmyslovichNote Added: 0033324
2014-10-20 13:08drazmyslovichAssigned Todrazmyslovich => oan
2014-10-20 13:08drazmyslovichStatusfeedback => resolved
2014-10-20 13:08drazmyslovichFile Deleted: circletool_unittest.cpp
2014-10-20 13:08drazmyslovichFile Added: circletool_unittest.cpp
2014-11-11 01:04abvTarget Version6.8.0 => 7.0.0
2015-04-15 16:07gitNote Added: 0039788
2015-04-15 16:48oanNote Added: 0039795
2015-04-15 16:48oanAssigned Tooan => abv
2015-04-15 16:49oanTarget Version7.0.0 => 6.9.0
2015-04-15 18:43gitNote Added: 0039808
2015-04-15 18:50gitNote Added: 0039809
2015-04-15 19:23abvNote Added: 0039813
2015-04-15 19:23abvAssigned Toabv => bugmaster
2015-04-15 19:23abvStatusresolved => reviewed
2015-04-15 19:31abvNote Added: 0039815
2015-04-16 12:59apvAssigned Tobugmaster => apv
2015-04-17 16:18gitNote Added: 0039971
2015-04-17 16:19apvNote Added: 0039972
2015-04-22 11:41oanNote Added: 0040094
2015-04-23 20:15apvNote Added: 0040189
2015-04-23 20:15apvAssigned Toapv => oan
2015-04-23 20:15apvStatusreviewed => assigned
2015-04-23 20:16apvNote Edited: 0040189bug_revision_view_page.php?bugnote_id=40189#r10185
2015-04-27 16:29oanNote Added: 0040287
2015-04-27 16:29oanAssigned Tooan => apv
2015-04-27 16:29oanStatusassigned => feedback
2015-04-27 16:32abvNote Added: 0040289
2015-04-28 09:56oanFile Added: cylinder_top_old.png
2015-04-28 09:57oanFile Added: cylinder_top_new.png
2015-04-28 10:03oanNote Added: 0040311
2015-04-28 10:11abvNote Added: 0040313
2015-04-30 15:00gitNote Added: 0040480
2015-04-30 15:01apvTest case number => bugs mesh(017) bug 24923
2015-04-30 15:02apvTest case numberbugs mesh(017) bug 24923 => bugs mesh(017) bug24923
2015-04-30 15:04apvNote Added: 0040482
2015-04-30 15:04apvAssigned Toapv => bugmaster
2015-04-30 15:04apvStatusfeedback => tested
2015-04-30 15:30gitNote Added: 0040486
2015-05-07 11:18bugmasterChangeset attached => occt master ec26bf88
2015-05-07 11:18bugmasterStatustested => verified
2015-05-07 11:18bugmasterResolutionopen => fixed
2015-05-08 11:34apvRelationship addedparent of 0026200
2015-05-14 15:28aivStatusverified => closed
2015-05-14 15:30aivFixed in Version => 6.9.0
2015-05-14 16:23gitNote Added: 0040915
2015-05-14 16:25gitNote Added: 0040949

2014-05-14 18:29   
Please, review the patch
2014-05-15 11:48   
Thanks for reporting the problem and proposing solution. This part of BRepMesh algo is really critical from performance point of view. Could you please provide the test case (original OCC shape and if possible 2D triangle points) to reproduce problem and profile the solution you proposed.
2014-05-15 15:57   
today I´m unfortunately out of office, therefore I´ll be able to provide my test case only on Monday. By the way I´ve profiled my change and it doesn´t affect the performance.
Actually, for the first time I met this issue in the known ¨klima¨ file. The file has appeared already in some tickets on the tracker, I can´t find the ticket number, but this ticket lead to the big changes in BRepMesh_Delaun file in version 6.7.0, so some ticket between 6.6.0 and 6.7.0 releases. The file name is something like (500_Klima_High.step)
Moreover I have much more modifications for BRepMesh module, which lead to better meshing results without any performance loss. I just need time to analyze the latest version of BRepMesh_Delaun file and merge my changes (I´ve done mine on 6.6.0 base). For instance, I have completely rewrite FrontierAdjust function, since it doesn´t clean up all problems and time-to-time cleans the wrong edges. So far I merge it and test it, I´ll commit them.
2014-05-15 16:15   
File 3359.500_Klima_high.stp is attachment to 0023105
2014-05-15 16:19   
Exactly this one! After deep debugging I found, that exactly this exception was caused by the wrong circle.
2014-10-16 13:22   
Dear Dima,

I have checked the fix and I have few remarks. First of all, I have tried to apply the changes to OCCT 6.6.0 release and check problematic face from 0023105. Using it, BRepMesh generates mesh for that face, however it is far from the correct one (see attached screenshot OCC660_fix.png).

Concerning problematic face from 3359.500_Klima_high, as I remember correctly, the problem was that BRepMesh_PairOfIndex thrown exception due to addition of third triangle while mesh link can have only two neighbours. The source of such incorrectness was in algorithm of collection of polygons in the final part of BRepMesh_Delaun execution. There was possibility to collect polygons with self-intersections in case of thin ribs that you can see in reference face. And moreover, if I am still right exception was being thrown from frontierAdjust() method that does not use computed circles at all.

Currently BRepMesh_CircleTool implements calculation of circumcenter in a little bit different way. However, the difference between distances from circumcenter to nodes of triangle does not exceed the order of ~1e-13 whereas Precision::PConfusion() is 1e-9, so such difference can be considered as noise and should not influent the result. Like this, you can see at the screenshot that playing with such insignificant values can lead to unexpected results and in fact it can be an indicator that the core of the problem is more deeper. Moreover, circle selector also uses tolerance to check does the given point belong to some circle or not, hence, there is no neccessity to inflate radius of calculated circle artificially.

Taking above considerations into account, unfortunately, I suppose to reject this fix.
2014-10-20 13:08   
Dear Oleg, I've just written and submitted as an attachment a small unit test for the circle tool. I've run it several times and it fails in 60% of cases (with no matter 6.6.0 or 6.8.0 algorithms). I think, it should be reasonable enough to accept my fix. Moreover evaluating the radius over all 3 vertices without adding epsilon reduces the fail rate to 25%. And only adding some epsilon to the radius makes circle tool fails free (I've stopped the test after 10000000 fail-free circles).
Yes, I agree, that the problem in klima test was caused by bad polygon generating (frontierAdjust was "top of stack" function, the actual function - MeshLeftPolygonOf). But the exception of adding the third triangle to the edge was caused exactly by the circle tool, since the inspector hasn't found, that a vertex is a part of some triangle.
I hope my unit test will help to identify the problem.
Regards, Dima
2015-04-15 16:07   
Branch CR24923 has been created by oan.

SHA-1: 1c95c323f704ba8a5d395dc874cd57e30839858a

Detailed log of new commits:

Author: razmyslovich
Date: Wed Apr 15 16:06:57 2015 +0300

    0024923: BRepMesh_CircleTool produces bad circles
    Calculate radius of circumcircle as maximum difference between its center and vertices or reference triangle.
    Draw test command OCC25547 has been implemented.
2015-04-15 16:48   
Dear Andrey,

could you please review changes in CR24923.
2015-04-15 18:43   
Branch CR24923 has been deleted by oan.

SHA-1: 1c95c323f704ba8a5d395dc874cd57e30839858a
2015-04-15 18:50   
Branch CR24923 has been created by oan.

SHA-1: 82ec77e7114849eb4b255c07cfedb62f21740f48

Detailed log of new commits:

Author: razmyslovich
Date: Wed Apr 15 18:45:21 2015 +0300

    0024923: BRepMesh_CircleTool produces bad circles
    Calculate radius of circumcircle as maximum difference between its center and vertices or reference triangle.
    Draw test command OCC25547 has been implemented.
    Small optimizations for speed.
2015-04-15 19:23   
Reviewed, please test.

Besides, it would be nice to have comment in the code explaining that taking maximum among distances to three points, and addition of 1e-7, are needed to cover possible numerical error
2015-04-15 19:31   
Another (general) remark is that it is bad practice of duplicating basic tools like construction of circle by 3 points, available in basic packages of OCCT, in BRepMesh (e.g. BRepMesh_CircleTool::MakeCircle() is functionally equivalent to gce_MakeCircle2d). If existing tools are bad, fixing them should be preferred to writing your own ones...
2015-04-17 16:18   
Branch CR24923 has been updated forcibly by apv.

SHA-1: 2c129f1ea33f877fb8861fd9a770c192ea9d80ed
2015-04-17 16:19   
Branch CR24923 has been rebased on the current master
2015-04-22 11:41   
Dear APV,

are there any results of testing?
2015-04-23 20:15   
(edited on: 2015-04-23 20:16)
Dear BugMaster,

Branch CR24923 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested.
SHA-1: 2c129f1ea33f877fb8861fd9a770c192ea9d80ed

Number of compiler warnings:
occt component:
   Linux: 18 (18 on master)
   Windows: 0 (0 on master)
products component:
   Linux: 4 (4 on master)
   Windows: 0 (0 on master)

http://occt-tests/CR24923-master-occt-64/Debian60-64/summary.html [^]
http://occt-tests/CR24923-master-occt-64/Windows-64-VC10/summary.html [^]
bugs moddata_1(012) bug22759
bugs mesh(017) bug25364, bug25519
mesh standard_shading(001) B3 (possible improvements)
mesh standard_incmesh(002) B3 (possible improvements)
mesh standard_mesh(003) B3 (possible improvements)
mesh standard_incmesh_parallel(007) B3 (possible improvements)
http://occt-tests/CR24923-master-products-64/Debian60-64/summary.html [^]
http://occt-tests/CR24923-master-products-64/Windows-64-VC10/summary.html [^]
omf standard_meshtuc(012) ZH6
omf standard_meshtuc(012) ZH4

Testing on Linux:
Total MEMORY difference: 94285295 / 94355756 [-0.07%]
Total CPU difference: 53868.24999999921 / 51851.56999999946 [+3.89%]

Testing on Windows:
Total MEMORY difference: 57028146 / 57038409 [-0.02%]
Total CPU difference: 16145.136293799107 / 16164.574018399078 [-0.12%]

There are differences in images found by testdiff:
http://occt-tests/CR24923-master-occt-64/Debian60-64/diff-Debian60-64.html [^]
http://occt-tests/CR24923-master-occt-64/Windows-64-VC10/diff-Windows-64-VC10.html [^]
http://occt-tests/CR24923-master-products-64/Debian60-64/diff-Debian60-64.html [^]
http://occt-tests/CR24923-master-products-64/Windows-64-VC10/diff-Windows-64-VC10.html [^]

2015-04-27 16:29   
Dear Bugmaster,

all differences from "mesh" and "bugs" grids are improvements: bug25519 - deflection is less than reference one by 10%; bug22759 - number of triangles has decreased.

Results of test cases from OMF are highly dependent of mesh produced by BRepMesh so can be treated as unstable.

I suggest integration.
2015-04-27 16:32   
It seems that algorithm now produces in some cases more narrow triangles than before, see image of bugs vis bug23225
2015-04-28 10:03   
Otherwise, IMHO result of this test case seems better than the old one, number of narrow triangles near boundaries has reduced (please see attached screenshots).
2015-04-28 10:11   
Well, I cannot say for sure it is better (this might depend on context of possible use of this mesh), but at least it is more regular; also the same between Linux and Windows at the case when they were different. The purpose of my remark was not to say it is regression, just to not have this change unaddressed.
2015-04-30 15:00   
Branch CR24923 has been updated by apv.

SHA-1: 3f38609782dc06ebdba6b1d4eda470cd243d18fc

Detailed log of new commits:

Author: apv
Date: Thu Apr 30 15:00:03 2015 +0300

    Update of test-cases according to the new behaviour

2015-04-30 15:04   
Dear Bugmaster, please pay attention, that fix for this issue has a branch in OCCTProducts git-repository.
2015-04-30 15:30   
Branch CR24923 has been updated by apv.

SHA-1: 7e34f9f56f5a016dfaeec45cac94b1fa85ded191

Detailed log of new commits:

Author: apv
Date: Thu Apr 30 15:30:25 2015 +0300

    Update of test-cases in group mesh

2015-05-14 16:23   
Branch CR0024923 has been deleted by inv.

SHA-1: 51ae1d3ab451b1902e5f6bc3ea112e616a18cae7
2015-05-14 16:25   
Branch CR24923 has been deleted by inv.

SHA-1: 7e34f9f56f5a016dfaeec45cac94b1fa85ded191