MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0024923Community[OCCT] OCCT:Meshpublic2014-05-14 18:262015-05-14 16:25
Reporterdrazmyslovich 
Assigned Tobugmaster 
PrioritynormalSeverityminor 
StatusclosedResolutionfixed 
PlatformWindowsOSVC++ 2010OS Version64 bit
Product Version[OCCT] 6.6.0 
Target Version[OCCT] 6.9.0Fixed in Version[OCCT] 6.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 Filespng file icon OCC660_fix.png (36,956 bytes) 2014-10-16 13:23
cpp file icon circletool_unittest.cpp (7,776 bytes) 2014-10-20 13:08
png file icon cylinder_top_old.png (8,297 bytes) 2015-04-28 09:56
png file icon cylinder_top_new.png (10,474 bytes) 2015-04-28 09:57

- Relationships
related to 0023105closedoan Community Exception during Meshing / Missing triangles 
related to 0025044feedbackdrazmyslovich Community BRepMesh tweaks 

-  Notes
(0029336)
drazmyslovich (developer)
2014-05-14 18:29

Please, review the patch
(0029344)
pdn (developer)
2014-05-15 11:48

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.
(0029349)
drazmyslovich (developer)
2014-05-15 15:57

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.
(0029351)
abv (manager)
2014-05-15 16:15

File 3359.500_Klima_high.stp is attachment to 0023105
(0029352)
drazmyslovich (developer)
2014-05-15 16:19

Exactly this one! After deep debugging I found, that exactly this exception was caused by the wrong circle.
(0033202)
oan (developer)
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.
(0033324)
drazmyslovich (developer)
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
(0039788)
git (administrator)
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.
(0039795)
oan (developer)
2015-04-15 16:48

Dear Andrey,

could you please review changes in CR24923.
(0039808)
git (administrator)
2015-04-15 18:43

Branch CR24923 has been deleted by oan.

SHA-1: 1c95c323f704ba8a5d395dc874cd57e30839858a
(0039809)
git (administrator)
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.
(0039813)
abv (manager)
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
(0039815)
abv (manager)
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...
(0039971)
git (administrator)
2015-04-17 16:18

Branch CR24923 has been updated forcibly by apv.

SHA-1: 2c129f1ea33f877fb8861fd9a770c192ea9d80ed
(0039972)
apv (tester)
2015-04-17 16:19

Branch CR24923 has been rebased on the current master
(0040094)
oan (developer)
2015-04-22 11:41

Dear APV,

are there any results of testing?
(0040189)
apv (tester)
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)

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 [^]

(0040287)
oan (developer)
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.
(0040289)
abv (manager)
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
(0040311)
oan (developer)
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).
(0040313)
abv (manager)
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.
(0040480)
git (administrator)
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

(0040482)
apv (tester)
2015-04-30 15:04

Dear Bugmaster, please pay attention, that fix for this issue has a branch in OCCTProducts git-repository.
(0040486)
git (administrator)
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

(0040915)
git (administrator)
2015-05-14 16:23

Branch CR0024923 has been deleted by inv.

SHA-1: 51ae1d3ab451b1902e5f6bc3ea112e616a18cae7
(0040949)
git (administrator)
2015-05-14 16:25

Branch CR24923 has been deleted by inv.

SHA-1: 7e34f9f56f5a016dfaeec45cac94b1fa85ded191

- Related Changesets
occt: master ec26bf88
Timestamp: 2015-04-30 13:41:54
Author: 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
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 user533 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 View Revisions
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-08 11:34 apv Relationship added parent of 0026200
2015-05-14 15:28 user533 Status verified => closed
2015-05-14 15:30 user533 Fixed in Version => 6.9.0
2015-05-14 16:23 git Note Added: 0040915
2015-05-14 16:25 git Note Added: 0040949


Copyright © 2000 - 2018 MantisBT Team
Powered by Mantis Bugtracker