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

CC BY-SA 4.0
2019-08-16T20:42:21.830Z
It should not matter what the starting triangle is.
lightxbulb
CC BY-SA 4.0
2019-08-16T20:46:18.817Z
Maybe, but it does.
beyond
CC BY-SA 4.0
2019-08-16T21:44:00.660Z
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).
lightxbulb
CC BY-SA 4.0
2019-08-16T21:57:27.353Z
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....
beyond
CC BY-SA 4.0
2019-08-16T22:22:59.573Z
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.
lightxbulb
CC BY-SA 4.0
2019-08-16T19:32:40.680Z
2019-08-16T19:32:40.680Z
beyond
<p>I guess what you wanna achieve is mesh simplification. Then those materials can be useful for you.</p>

<p><a href="http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/08_Simplification.pdf" rel="nofollow noreferrer">http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/08_Simplification.pdf</a></p>

<p><a href="https://pages.mtu.edu/~shene/COURSES/cs3621/SLIDES/Simplification.pdf" rel="nofollow noreferrer">https://pages.mtu.edu/~shene/COURSES/cs3621/SLIDES/Simplification.pdf</a></p>

CC BY-SA 4.0
2019-08-16T09:36:10.287Z
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.
Looft
CC BY-SA 4.0
2019-08-16T10:59:35.247Z
I'm confused. Isn't triangle a kind of polygon?
Zhe Chen
CC BY-SA 4.0
2019-08-16T12:28:03.290Z
@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.
Christian Rau
CC BY-SA 4.0
2019-08-16T12:31:57.190Z
@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.
Christian Rau
CC BY-SA 4.0
2019-08-16T12:45:20.717Z
@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.
Looft
CC BY-SA 4.0
2019-08-16T09:19:14.953Z
2019-08-16T09:19:14.953Z
Zhe Chen
<p>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.</p>

<p>The 3D object should stay the same.</p>

<p>Polygons can be non-planar.</p>

CC BY-SA 4.0
2019-08-16T10:29:40.263Z
Please describe what you mean by polygon, for instance are they planar?
beyond
CC BY-SA 4.0
2019-08-16T19:02:54.550Z
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.
lightxbulb
CC BY-SA 4.0
2019-08-16T22:39:48.813Z
Is there any ambiguity when it comes to polygons not on a single plane?
Looft
CC BY-SA 4.0
2019-08-17T16:29:34.370Z
@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.
lightxbulb
<algorithm><polygon><triangulation>
Convert triangulated object to a polygonized object
Looft
# Convert triangulated object to a polygonized object

(Asked by: username_0 on 2019-08-16)

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.

**Tags:** algorithm, polygon, triangulation

> **Comments:**
> **username_1**: Please describe what you mean by polygon, for instance are they planar?  
> **username_2**: 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.  
> **username_0**: Is there any ambiguity when it comes to polygons not on a single plane?  
> **username_2**: @username_0 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.  

---

## 2 answers

### Answer by username_1 on 2019-08-16. Score: -1

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

> **Comments:**
> **username_2**: It should not matter what the starting triangle is.  
> **username_1**: Maybe, but it does.  
> **username_2**: 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).  
> **username_1**: 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....  
> **username_2**: 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.  

---

### Answer by username_3 on 2019-08-16. Score: -1

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>

> **Comments:**
> **username_0**: 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.  
> **username_3**: I'm confused. Isn't triangle a kind of polygon?  
> **username_4**: @username_0 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.  
> **username_4**: @username_0 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.  
> **username_0**: @username_4 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.  

---

