1
$\begingroup$

Is there an efficient algorithm to convert a 3D object described with a set of triangles to a 3D object described with a set of polygons. Polygons can have an arbitrary number of points, more is better. I'd like to minimize the number of polygons necessary to describe the 3D object but it does not have to be optimal.

The 3D object should stay the same.

Polygons can be non-planar.

$\endgroup$
  • 1
    $\begingroup$ Please describe what you mean by polygon, for instance are they planar? $\endgroup$ – beyond Aug 16 at 10:29
  • $\begingroup$ Look up 3d convex hull algorithms. Note that this will work only for convex objects though. Otherwise you may start at a tri and grow planar regions, marking tris as visited along the way. The algorithm has linear complexity if you have adjacency information. How does a "non-planar polygon" even work? Afaik the definition requires it to be planar. $\endgroup$ – lightxbulb Aug 16 at 19:02
  • $\begingroup$ Is there any ambiguity when it comes to polygons not on a single plane? $\endgroup$ – Looft Aug 16 at 22:39
  • $\begingroup$ @Looft There's no such definition afaik. Try defining those. Otherwise there are infinitely many surfaces that have the edge of such a polygon - for instance minimal surfaces, or a surface that matches the triangulated version, etc. In general in graphics APIs non planar polygons have "funny" behaviour. $\endgroup$ – lightxbulb Aug 17 at 16:29
-1
$\begingroup$

I guess what you wanna achieve is mesh simplification. Then those materials can be useful for you.

http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/08_Simplification.pdf

https://pages.mtu.edu/~shene/COURSES/cs3621/SLIDES/Simplification.pdf

$\endgroup$
  • $\begingroup$ I do not want to simplify the object. I just want to have a list of polygons that are not triangles to describe it. The more vertices these polygons have, the better. $\endgroup$ – Looft Aug 16 at 9:36
  • 1
    $\begingroup$ I'm confused. Isn't triangle a kind of polygon? $\endgroup$ – Zhe Chen Aug 16 at 10:59
  • $\begingroup$ @Looft But then you are simplifying your mesh since you're removing vertices from it (otherwise it's not clear how you want to create these "polygons"), under the requirement that you only want to simplify planar regions (which your question doesn't actually specify, but seems to be the most reasonable way to interpret it). But I agree that "classic" mesh simplification algorithms that work within the domain of triangular meshes might not work for your task out of the box. However, the principle of merging coplanar triangles stays the same, though. $\endgroup$ – Christian Rau Aug 16 at 12:28
  • $\begingroup$ @Looft But on the bottom line, elaborating a little more in the question what exactly you're looking for, what conditions those "polygons" ought to satisfy and how (if at all) the polygonal object should differ from the triangular one in its geometry, might be helpful in getting more accurate answers. $\endgroup$ – Christian Rau Aug 16 at 12:31
  • $\begingroup$ @ChristianRau Polygons can be triangles if necessary but as more vertices are used by a single polygon, fewer are needed to finish describing the 3D object. $\endgroup$ – Looft Aug 16 at 12:45
-1
$\begingroup$

I would try a rim-filling approach starting with a good guess for a central triangle. Rinse, repeat.

$\endgroup$
  • $\begingroup$ It should not matter what the starting triangle is. $\endgroup$ – lightxbulb Aug 16 at 20:42
  • $\begingroup$ Maybe, but it does. $\endgroup$ – beyond Aug 16 at 20:46
  • $\begingroup$ It doesn't since you grow a polygon until you can grow it no more - that procedure is finite and deterministic. You have a graph, where each node is a triangle and there's an edge in that graph between two nodes, only if the two corresponding triangles share an edge and are in the same plane. The algorithm to construct the largest polygon would make a polygon out of all connected components. Needless to say the solution is unique no matter from where you start. You iterate over all tris, and keep a list of the visited ones, the algo is O(N). $\endgroup$ – lightxbulb Aug 16 at 21:44
  • $\begingroup$ If you want to minimize the number of polygons the starting triangle is important, which the op prefers. The polygons do not have to be planar. Constructing the half-edge graph (or similar) is not O(n), so.... $\endgroup$ – beyond Aug 16 at 21:57
  • $\begingroup$ I am assuming you already have an adjacency structure, so the algo when having it is O(N) - constructing one is a well studied problem either way. Also the notion of non-planar polygons makes no sense to me, I am unaware of such a definition. So you need to define what a non-planar polygon is if you want to use such a term. If you consider the algorithm I described you will note that "the starting polygon" is irrelevant, since it iterates over all triangles once either way. The solution is unique. $\endgroup$ – lightxbulb Aug 16 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.