View Issue Details

IDProjectCategoryView StatusLast Update
0024923CommunityOCCT:Meshpublic2015-05-14 16:25
Reporterdrazmyslovich Assigned Tobugmaster  
PrioritynormalSeverityminor 
Status closedResolutionfixed 
PlatformWindowsOSVC++ 2010 
Product Version6.6.0 
Target Version6.9.0Fixed in Version6.9.0 
Summary0024923: BRepMesh_CircleTool produces bad circles
DescriptionDue 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.
TagsNo tags attached.
Test case numberbugs mesh(017) bug24923

Attached Files

  • OCC660_fix.png (36,956 bytes)
  • circletool_unittest.cpp (7,776 bytes)
  • cylinder_top_old.png (8,297 bytes)
  • cylinder_top_new.png (10,474 bytes)

Relationships

related to 0023105 closedoan Community Exception during Meshing / Missing triangles 
related to 0025044 closedbugmaster Community BRepMesh tweaks 

Activities

drazmyslovich

2014-05-14 18:29

developer   ~0029336

Please, review the patch

pdn

2014-05-15 11:48

reporter   ~0029344

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.

drazmyslovich

2014-05-15 15:57

developer   ~0029349

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.

abv

2014-05-15 16:15

manager   ~0029351

File 3359.500_Klima_high.stp is attachment to 0023105

drazmyslovich

2014-05-15 16:19

developer   ~0029352

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

oan

2014-10-16 13:22

developer   ~0033202

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.

oan

2014-10-16 13:23

developer  

OCC660_fix.png (36,956 bytes)

drazmyslovich

2014-10-20 13:08

developer   ~0033324

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

drazmyslovich

2014-10-20 13:08

developer  

circletool_unittest.cpp (7,776 bytes)

git

2015-04-15 16:07

administrator   ~0039788

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.

oan

2015-04-15 16:48

developer   ~0039795

Dear Andrey,

could you please review changes in CR24923.

git

2015-04-15 18:43

administrator   ~0039808

Branch CR24923 has been deleted by oan.

SHA-1: 1c95c323f704ba8a5d395dc874cd57e30839858a

git

2015-04-15 18:50

administrator   ~0039809

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.

abv

2015-04-15 19:23

manager   ~0039813

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

abv

2015-04-15 19:31

manager   ~0039815

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

git

2015-04-17 16:18

administrator   ~0039971

Branch CR24923 has been updated forcibly by apv.

SHA-1: 2c129f1ea33f877fb8861fd9a770c192ea9d80ed

apv

2015-04-17 16:19

tester   ~0039972

Branch CR24923 has been rebased on the current master

oan

2015-04-22 11:41

developer   ~0040094

Dear APV,

are there any results of testing?

apv

2015-04-23 20:15

tester   ~0040189

Last edited: 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)

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

oan

2015-04-27 16:29

developer   ~0040287

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.

abv

2015-04-27 16:32

manager   ~0040289

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

oan

2015-04-28 09:56

developer  

cylinder_top_old.png (8,297 bytes)

oan

2015-04-28 09:57

developer  

cylinder_top_new.png (10,474 bytes)

oan

2015-04-28 10:03

developer   ~0040311

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

abv

2015-04-28 10:11

manager   ~0040313

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.

git

2015-04-30 15:00

administrator   ~0040480

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

apv

2015-04-30 15:04

tester   ~0040482

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

git

2015-04-30 15:30

administrator   ~0040486

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

git

2015-05-14 16:23

administrator   ~0040915

Branch CR0024923 has been deleted by inv.

SHA-1: 51ae1d3ab451b1902e5f6bc3ea112e616a18cae7

git

2015-05-14 16:25

administrator   ~0040949

Branch CR24923 has been deleted by inv.

SHA-1: 7e34f9f56f5a016dfaeec45cac94b1fa85ded191

Related Changesets

occt: master ec26bf88

2015-04-30 13:41:54

drazmyslovich


Committer: bugmaster Details Diff
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.

Update of test-cases according to the new behaviour

Update of test-cases in group mesh
Affected Issues
0024923
mod - src/BRepMesh/BRepMesh_CircleTool.cxx Diff File
mod - src/BRepMesh/BRepMesh_CircleTool.hxx Diff File
mod - src/QABugs/QABugs_19.cxx Diff File
add - tests/bugs/mesh/bug24923 Diff File
mod - tests/bugs/mesh/bug25364 Diff File
mod - tests/bugs/mesh/bug25519 Diff File
mod - tests/bugs/moddata_1/bug22759 Diff File
mod - tests/mesh/data/standard/B3 Diff File

Issue History

Date Modified Username Field Change
2014-05-14 18:26 drazmyslovich New Issue
2014-05-14 18:26 drazmyslovich Assigned To => drazmyslovich
2014-05-14 18:29 drazmyslovich Note Added: 0029336
2014-05-14 18:29 drazmyslovich Status new => resolved
2014-05-14 18:50 abv Assigned To drazmyslovich => pdn
2014-05-14 18:50 abv Target Version Unscheduled => 6.8.0
2014-05-15 11:48 pdn Note Added: 0029344
2014-05-15 15:57 drazmyslovich Note Added: 0029349
2014-05-15 16:15 abv Note Added: 0029351
2014-05-15 16:15 abv Relationship added related to 0023105
2014-05-15 16:19 drazmyslovich Note Added: 0029352
2014-05-21 10:40 pdn Assigned To pdn => abk
2014-06-17 12:47 aiv Project Open CASCADE => Community
2014-06-20 14:19 oan Category OCCT:Modeling Algorithms => OCCT:Mesh
2014-07-01 14:27 drazmyslovich Relationship added related to 0025044
2014-07-07 12:45 abv Assigned To abk => oan
2014-10-16 13:22 oan Note Added: 0033202
2014-10-16 13:22 oan Assigned To oan => drazmyslovich
2014-10-16 13:22 oan Status resolved => feedback
2014-10-16 13:23 oan File Added: OCC660_fix.png
2014-10-20 12:46 drazmyslovich File Added: circletool_unittest.cpp
2014-10-20 13:08 drazmyslovich Note Added: 0033324
2014-10-20 13:08 drazmyslovich Assigned To drazmyslovich => oan
2014-10-20 13:08 drazmyslovich Status feedback => resolved
2014-10-20 13:08 drazmyslovich File Deleted: circletool_unittest.cpp
2014-10-20 13:08 drazmyslovich File Added: circletool_unittest.cpp
2014-11-11 01:04 abv Target Version 6.8.0 => 7.0.0
2015-04-15 16:07 git Note Added: 0039788
2015-04-15 16:48 oan Note Added: 0039795
2015-04-15 16:48 oan Assigned To oan => abv
2015-04-15 16:49 oan Target Version 7.0.0 => 6.9.0
2015-04-15 18:43 git Note Added: 0039808
2015-04-15 18:50 git Note Added: 0039809
2015-04-15 19:23 abv Note Added: 0039813
2015-04-15 19:23 abv Assigned To abv => bugmaster
2015-04-15 19:23 abv Status resolved => reviewed
2015-04-15 19:31 abv Note Added: 0039815
2015-04-16 12:59 apv Assigned To bugmaster => apv
2015-04-17 16:18 git Note Added: 0039971
2015-04-17 16:19 apv Note Added: 0039972
2015-04-22 11:41 oan Note Added: 0040094
2015-04-23 20:15 apv Note Added: 0040189
2015-04-23 20:15 apv Assigned To apv => oan
2015-04-23 20:15 apv Status reviewed => assigned
2015-04-23 20:16 apv Note Edited: 0040189
2015-04-27 16:29 oan Note Added: 0040287
2015-04-27 16:29 oan Assigned To oan => apv
2015-04-27 16:29 oan Status assigned => feedback
2015-04-27 16:32 abv Note Added: 0040289
2015-04-28 09:56 oan File Added: cylinder_top_old.png
2015-04-28 09:57 oan File Added: cylinder_top_new.png
2015-04-28 10:03 oan Note Added: 0040311
2015-04-28 10:11 abv Note Added: 0040313
2015-04-30 15:00 git Note Added: 0040480
2015-04-30 15:01 apv Test case number => bugs mesh(017) bug 24923
2015-04-30 15:02 apv Test case number bugs mesh(017) bug 24923 => bugs mesh(017) bug24923
2015-04-30 15:04 apv Note Added: 0040482
2015-04-30 15:04 apv Assigned To apv => bugmaster
2015-04-30 15:04 apv Status feedback => tested
2015-04-30 15:30 git Note Added: 0040486
2015-05-07 11:18 bugmaster Changeset attached => occt master ec26bf88
2015-05-07 11:18 bugmaster Status tested => verified
2015-05-07 11:18 bugmaster Resolution open => fixed
2015-05-14 15:28 aiv Status verified => closed
2015-05-14 15:30 aiv Fixed in Version => 6.9.0
2015-05-14 16:23 git Note Added: 0040915
2015-05-14 16:25 git Note Added: 0040949