Hi there, Imagine I have a polygon mesh (consisting of triangles) with holes (the surface is not closed). The holes can have arbitrary (convex, concave, 3D) shapes. The holes are stored as links to the edges connecting the vertices around the hole. Is there any fast way to close the hole while maintaining the direction of the mesh. The number of resulting triangles is not that important. The obvious way would be to triangulate the polygon that's surrounded by the vertices - but is there any other way - or what's the fastest way to do this? Do any of you know which algorithms Software like Cinema4D uses for it's hole closing algorithm? I don't want to reconstruct the surface. I just want to close my meshes. Flat and simple. Thanks and greetings, Roga

Since the polygon doesn't contain any holes (due to self represeting a hole)you can use e.g. the ear-clipping algorithm. It doesn't introduce new vertices and handle convex and concave polys well.

Well, IMHO the problem is definitely a triangulation problem, so I don't expect another class of problem solutions exists for polygonal hole filling.

Hi Haeggar and thanks for your replay. I was also thinking of the ear clip algorithm but as far as I remember the algorithm can have problems with concave shapes. If you imagine a circle shape with one vertex lying inside the circle a triangle in the wrong direction could be inserted - or am I wrong?

Greetings, Roga

Quote:Original post by Rogalon
I was also thinking of the ear clip algorithm but as far as I remember the algorithm can have problems with concave shapes.

AFAIK ear-clipping is intented for handling cancave polys as well. It can't handle holes but that isn't a restriction in your case.

If you want to look at another method then the (unmodified) Seidel algorithm may be of interest. However, I don't know about its computational costs, but I have in mind that it is more expensive than ear-clipping.


EDIT: Wikipedia hints in this page http://en.wikipedia.org/wiki/Ear_clipping to "monotone triangle decomposition" as a faster method than ear-clipping is.

Thanks for the link - I'll look that up.

Quote:Original post by haegarr
AFAIK ear-clipping is intented for handling cancave polys as well. It can't handle holes but that isn't a restriction in your case.

Ear-clipping can handly polygons with holes. The basic idea for an inner polygon nested in an outer polygon is to find a vertex A of the inner polygon and a vertex B of the outer polygon such that A and B are visible to each other. That is, you can connect them with a line segment that is not intersected by an other parts of the polygons. You then introduce two new edges, one from A to B and one from B to A to produce a simple polygon (that happens to have two coincident edges). The SampleFoundation/Triangulation sample at my website shows how this is done. It also handles the more general case of a tree of nested polygons.

Quote:
If you want to look at another method then the (unmodified) Seidel algorithm may be of interest. However, I don't know about its computational costs, but I have in mind that it is more expensive than ear-clipping.


EDIT: Wikipedia hints in this page http://en.wikipedia.org/wiki/Ear_clipping to "monotone triangle decomposition" as a faster method than ear-clipping is.

The discussion of "faster" is in the sense of "asymptotic order". For a polygon of n vertices, ear clipping may be implemented as an O(n^2) algorithm. Seidel's algorithm is O(n*logstar(n)), where for all practical purposes, logstar(n) is effectively small, making Seidel's practically an O(n) algorithm. Monotone triangle decomposition is part of this algorithm, a step performed after a decomposition into trapezoids with pairs of parallel horizontal edges. Without the randomization, you can get this to be O(n*log(n)). Chazelle has a paper that shows you can triangulate in O(n) time.

The engineering problems: How much time will it take to implement each of these algorithms and make them robust? Will your n be large enough that the asymptotic behavior makes a difference?