Re-divide surface to get similar-sized cell

I am looking for some suggestions of how to achieve this: Re-divide a surface (polydata with only triangles) to get similar-sized cells with minimal change from the original surface. May be I am overlooking something, but I was unable to find any filters that achieves this.

Animations in optimesh’s gihub page conceptually demonstrates what I am looking for. The main concern is that the original surface may have very different-sized cells, some of these may be elongated/streched in different ways. A toy example of such surface is shown below (simple sphere) with very small & stretched triangles near poles. In my experience, I am finding more of such surfaces (with very different-sized cells) after applying vtkQuadricDecimation. These surface tend to produce weird artifacts in further processing like curvature etc.

My question is inline with this question with no clear answers. optimesh package mentioned earlier does not really work 3D surfaces. It supports vtk file-format but does not support polydata [Error: Only VTK ‘UNSTRUCTURED_GRID’, ‘STRUCTURED_POINTS’, ‘STRUCTURED_GRID’, ‘RECTILINEAR_GRID’ supported (not POLYDATA)]

In my application it is highly desirable to have points uniformly spaced over the surface. Surfaces I generated were generated as following: Threshold volumetric data → marching cubes → smooth using vtkWindowedSincPolyDataFilter → vtkQuadricDecimation

Thank you in advance!

Toy surface with non-uniform cells:

I don’t think there is a VTK implementation of this kind of algorithm, but @will.schroeder might have better insight.

I have seen works doing the kind of diagram you’re looking for. If you’re willing to write down a filter, this looks very similar to what you’re talking about. The idea is to generate a 3D voronoi diagram such that your poly data is inside the domain of this voronoi diagram. The “almost uniformly sampled” output is the intersection between this 3D voronoi diagram and your input mesh.

It has been a long time since I looked at this work, so my explanation could be a bit off. If you end up developing a VTK filter, I would be more than happy to review it if you submit a merge request.

I’m not familiar with the latest work, but the idea has been around for a while including this '92 Siggraph paper: “Re-Tiling Polygonal Surfaces”. I do not believe this has been implemented in VTK but it would be nice to have (if anyone is feeling ambitious).

Hi, friend,

If you don’t find a pure VTK solution and if you don’t mind adding another dependency to your software, you can try CGAL: CGAL 5.2.1 - Polygon Mesh Processing: User Manual . The gmsh library may also have something similar.



I see a few suggestions have been made already, so forgive me for adding yet another suggestion to the list. Your goal of a tool which can take a non-uniform mesh and clean it up (make it much more uniform) is well served by distmesh:

I use it in my numerical analysis classes at Northeastern in Boston. The algorithm is easy to understand and there is a Matlab implementation which you might translate into C++.

Stuart Brorson
Boston, MA

Thank you all for suggestions. Sorry for delayed response.

I will try the suggestions and update sometime later how it worked out. I am working in python so will have to see which of the suggested packages have native python bindings.