BRepMesh_CircleTool produces bad circles

Please, review the patch

Hello,
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.

Hello,
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.

File 3359.500_Klima_high.stp is attachment to #0023105

Exactly this one! After deep debugging I found, that exactly this exception was caused by the wrong circle.

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 Attachment 4 (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.

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.
[signature removed]Dima

Branch [archived branch] has been created by Commenter 2.

[revision removed]


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.

Dear Andrey,

could you please review changes in CR24923.

Branch [archived branch] has been deleted by Commenter 2.

[revision removed]

Branch [archived branch] has been created by Commenter 2.

[revision removed]


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.

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

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...

Branch [archived branch] has been updated forcibly by Participant.

[revision removed]

Branch [archived branch] has been rebased on the current master

Dear APV,

are there any results of testing?

Dear Commenter 1,

Branch CR24923 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested.
[revision removed]

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)

Regressions/Differences:
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

Dear Commenter 1,

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.

It seems that algorithm now produces in some cases more narrow triangles than before, see image of bugs vis bug23225

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).

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.

Branch [archived branch] has been updated by Participant.

[revision removed]


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

Dear Commenter 1, please pay attention, that fix for this issue has a branch in OCCTProducts git-repository.

Branch [archived branch] has been updated by Participant.

[revision removed]


Detailed log of new commits:

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

    Update of test-cases in group mesh

Branch [archived branch] has been deleted by Participant.

[revision removed]

Branch [archived branch] has been deleted by Participant.

[revision removed]