search

BrunoLevy / geogram

a programming library with geometric algorithms
Other
1.85k stars 125 forks source link

Classification error in MeshSurfaceIntersection #81

Closed BrunoLevy closed 1 year ago

BrunoLevy commented 1 year ago

MeshSurfaceIntersection sometimes fails to classify internal shells. Examples: in the "Monsters" category of Thingi10K

BrunoLevy commented 1 year ago
BrunoLevy commented 1 year ago

Move debug log from mesh_surface_intersection.cpp here: -1 is it FPE ? activate FPE -> OK -2 deactivate Delaunay: result is OK on 1st run on some tests but not all of them -3 is it incoherent h's ? Implemented unique h's, does not fix the problem -4 can it be a memory error ? -> Nope, valgrind OK -5 what does it do after floatigy ? -> just the same -6 can it be exactly coplanar faces tessellated in different ways ? -7 it may be possible that two overlapping facets return different Tweaking triangle_normal_axis_exact() makes it work sometimes, but I think the problem is somewhere else -9 there seems to be a question of connected components, see tmp_wing.geogram vs tmp_wing_2.geogram that has an additional isolated triangle -10 test whether there are ambiguities (coplanar facets in same radial set) in radial_sort there is none in tmp_wing.geogram -11 is it when a surface intersects several coplanar surfaces ? two_cylinders_with_sphere: no problem new minimalistic test case with three boxes has the problem and has no coplanar faces -12 tmp_wing has a small spurious facet, is it the one selected as the "leftmost" one ? Saved leftmost, it is not this one, OK -13 tmp_wing_4 with big spurious facet: has the bug kill big spurious facet: no bug -14) check all CDTxxx without and with spurious facet they seem to be the same -15 sort facets before on tmp_wing_4 -> there is not the bug anymore but sort facets before on calabi_yau_part2 -> there is still the bug -16 OK: 32 regions (33 with spurious facet) !OK: 26 regions

BrunoLevy commented 1 year ago

Got it ! In Constrained 2D Delaunay triangulation, some constrained edges were not marked as constrained, and were flipped by subsequent Delaunayize or constraint insertions (fixed).