Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

CGAL Surface_mesh_simplification produces self-intersecting elements after decimation #6

Open
fangq opened this issue Jun 12, 2015 · 11 comments

Comments

@fangq
Copy link
Owner

fangq commented Jun 12, 2015

The mesh simplification algorithm used in CGAL does not ensure the output mesh is self-intersection free. An alternative or update to Surface_mesh_simplification that ensures self-intersection-free would be very useful.

@harmening
Copy link
Contributor

Any updates here?
Tried remeshing with mmgs_O3, too, but run into the same error of self-intersections such that tetgen wasn't able to produce volume meshes. I'm afraid it's rather a problem of our data (very close surface meshes) than of the actual remeshing algorithms, since we feed them with a combination of surface meshes, that are very close to each other, and the algorithms try to remesh every surface mesh on its own but are not checking for intersections with the other nearby surface meshes.

@fangq
Copy link
Owner Author

fangq commented Feb 24, 2024

@harmening, if your surface mesh is a single closed surface, you can just call meshcheckrepair(no, fc, 'meshfix') to fix the self-intersection.

for a general purpose repairing tool, this is extremely hard and I don't anticipate this ticket can be closed easily.

@fangq
Copy link
Owner Author

fangq commented Feb 24, 2024

also checkout our brain2mesh paper and code

https://github.com/fangq/brain2mesh
http://dx.doi.org/10.1117/1.NPh.7.1.015008

it is based on iso2mesh, and we specifically handle multi-layered meshes with close distances (CSF/gray-matter/white-matter surfaces) and used a combination of boolean, repairing, and remeshing to create usable meshes.

@harmening
Copy link
Contributor

@fangq, no, it's not a single closed surface - it's a combination of 4 nested closed surfaces (scalp, skull, csf, cortex), meshcheckrepair wasn't helping.
Thanks for pointing me to brain2mesh, I will definetely have a look!

@harmening
Copy link
Contributor

Ok, requiring a minimum distance between the nested surface meshes helped for me to prevent self-intersections during CGAL-remeshing. It's not a perfect solution, but might be sufficient until a remeshing-tool is found (which e.g. can promise self-intersection-free outputs).

@fangq
Copy link
Owner Author

fangq commented Mar 6, 2024

@harmening, I am not sure what you meant by "CGAL-remeshing".

in our brain2mesh script, we did the intersecting surface handling mostly by using surfboolean with the resolve option

https://github.com/fangq/brain2mesh/blob/cdb24f2839de45bba52cc5754f13b4dd3393fe67/brain2mesh.m#L308-L319

only when resolve is not sufficient, we used the decouple option to insert a gap between the adjacent shells

https://github.com/fangq/brain2mesh/blob/cdb24f2839de45bba52cc5754f13b4dd3393fe67/brain2mesh.m#L294-L307

the decouple option calls meshfix.

@harmening
Copy link
Contributor

Sorry @fangq, with "CGAL-remeshing" I meant the CGAL surface mesh decimation called before tetrahedralization.
I checked your brain2mesh script, but surfboolean with resolve is not solving the problem (the script already fails during the coarse tetrahedralization of the combined tissues). I also directly tried surfboolean with decouple (loop=2), but meshfix wasn't able to return something useful. I agree with you that this is an extremely hard problem to solve.
This is because my meshes in this case super close to each other in more than one area. But to make clear: This is nothing what happens if I run your full brain2mesh pipeline with segmented MRIs. Your pipeline is really awesome (tried it on many heads) and works just perfectly fine! My unusual case of really close surface meshes is not stemming from your brain2mesh surface triangulation. It stems from an algorithm I am working on to approximate the surface meshes for individual subjects if no MRI is available (using e.g. exact optode or electrode positions as for example measured by photogrammetry scans). If I add a regulariser to ensure, that there is a minimum distance of a few millimeters between the meshes, a subsequent tetrahedralization with s2m always seems to work smoothly. :-)

@fangq
Copy link
Owner Author

fangq commented Mar 8, 2024

try this sequence:

  1. meshresample for each shell individually
  2. call meshcheckrepair('meshfix') on each shell individually
  3. run surfboolean('resolve') progressively like we did in brain2mesh

you can not by bass meshcheckrepair because surfboolean does not fix self-intersection.

it sounds like what you are doing is exactly what brain2mesh is meant to do - why not using it directly?

@harmening
Copy link
Contributor

Oh yes, good idea! But since meshresample only downsamples (decimate), I used mmgs_03 (as in my first post) to upsample (refine) (cause I need to upsample), but this time first on the shells individually (compared to my first post). Then meshcheckrepair('meshfix') on each shell and then the progressive combination with surfboolean('resolve') as in brain2mesh. Nice!!
Results: sometimes this volume mesh generation works, sometimes it fails. It seems to be depending on the mmgs_03 remeshing parameters (mainly -hmax, i.e. maximum edge size). For large edge size values (i.e. less refining) it works, for smaller edge sizes (more refining) it fails at the coarse tetrahedralization of the combined tissues as before.

@harmening
Copy link
Contributor

harmening commented Mar 13, 2024

So, @fangq, I propose to close this here for now. I think we found the very improbable boarder of this whole nested_surf2mesh pipeline. This case is so unlikely because my input data do not stem from MRI segmentations but a warping algorithm. I learned to constrain my algorithm to ensure a minimum distance between the nested surface meshes, which is anyway physiologically plausible. Then the whole tetrahedralization works fine and I am satisfied.
Anyhow, super interesting, that (although there is no intersection in the raw meshes), during refining some (self-)intersections occur, that make the tetrahedralization fail.
I very much appreciate all your effort in helping me, thanks a lot! And let me, at this point, also thank you, for your really thorough and tireless open source contribution with the whole segmentation and meshing stuff. It often saved me a lot of time during my research and always worked as expected. Thank you so much!

@fangq
Copy link
Owner Author

fangq commented Mar 13, 2024

@harmening, the above discussion has deviated from the purpose of this ticket, so I agree that we should not use this thread to continue the discussion. For any additional questions related to meshing multi-shell surfaces, I suggest you start a new ticket in either iso2mesh or brain2mesh repo.

However, I will leave this ticket open because the described issue still has not been resolved.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants