<p>Start from any triangle. Traverse it's edge's and check that the angle between the two triangles is less than 180deg. If it is add it to the current selection and continue expanding.</p>

<p>The check is actually really simple if you use vector geometry. Say A - B is the common edge with C on the selected side and D on the other. Then just check if <code>dot((D-B), cross((A-B), (C-B)) &lt; 0</code>.</p>

<p>Single triangle patches should be ruled out, as for us to determine convexity, it has to span across several triangles.
We have to keep sampling until we've tested everything.  When a convex patch continues further, it's size keeps on increasing by including the neighbouring triangles that satisfy convexity, until the patch reaches the maximum size it can attain.</p>

CC BY-SA 3.0
2016-03-20T13:13:42.493Z
If a patch ends, and not all triangles have been visited/tested, you have to start anew with another random triangle that is not part of a patch yet. So you find all convex patches and not just the one you happen to begin with. Then chose the biggest one. (Note: Patches can be just a single triangle)
Dragonseel
CC BY-SA 3.0
2016-03-20T16:41:13.333Z
@dragonseel well for practical purposes I think single triangle patches should be ruled out, as for us to determine convexity, it has to span across several triangles.
well we do get all patches, but when a convex patch continues further, it's size keeps on increasing by including the neighbouring triangles that satisfy convexity, until the patch reaches the maximum size it can attain.
Sushovan Mandal
CC BY-SA 3.0
2016-03-20T20:30:55.647Z
Yea. I just wanted to emphazise that in order to find the biggest convex patch, you have to keep sampling until you tested everything, since after the first one there might be a even bigger one disconnected that you haven't found jet.
Dragonseel
CC BY-SA 3.0
2016-04-03T11:30:31.910Z
A possible problem with this approach is that for some surfaces there will exist a path between two adjacent triangles that is made up only of convex steps, even though the two adjacent triangles touch along a concave edge. In sufficiently smooth examples this may not be a problem as the inaccuracy will only tend to be one triangle wide, but it is possible to construct examples with arbitrarily large concavities that are accessible by purely convex paths. For example, imagine the shape made by pushing a pin into a balloon so that the surface dips inwards (assuming it doesn't burst).
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-04T12:40:59.857Z
I understand that your answer is just an example to get things started. I was just giving some feedback in the hope that it will trigger an idea for improvement from someone.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-03-20T03:54:01.847Z
2016-04-01T09:31:26.370Z
2016-04-01T09:31:26.370Z
Sushovan Mandal
<p>Given a 3D object in Computer graphics, whose surface is represented as a 3D triangular mesh (mesh of 3D triangle objects), I need to find the maximum continual Convex patches on the surface of the given 3D object.</p>

<p>I am using OpenGl to render the graphics within a C++ program. What kind of methods or algorithms should I use to find the convex patches.</p>

<p>I have to apply different colors to the different convex patches on the object to signify the selection. </p>

<p>Say I have a sphere then the whole sphere is one maximal convex patch. Any portion of the sphere surface will be a convex patch, by maximal I mean the maximum continuous convex patches that can be found. Well in the rendering, depending on the viewing angles, the maximal convex patches visible to the viewer will have to colored. I have to report all the convex patches, each patch being the maximal in that area.</p>

<p>I am using "maximal" to mean a convex surface which is not a subset of a larger convex surface, rather than to mean the largest convex surface that exists in the triangle mesh. The patches need to be strictly convex (never flat).</p>

CC BY-SA 3.0
2016-03-19T02:22:18.800Z
OpenGL doesn't seem like it would help here; it's a computational geometry problem, not rendering. Can you edit the question and define your terms better? What do you mean by a "maximum continual convex patch" exactly?
Nathan Reed
CC BY-SA 3.0
2016-03-20T04:01:00.113Z
@nathanreed opengl will be used to render the objects, processing algorithms are to be done in C++. I have to apply different colors to the different convex patches on the object to signify the selection. Say I have a sphere then the whole sphere is one maximal convex patch. Any portion of the sphere surface will be a convex patch, by maximal I mean the maximum continuous convex patch that can be found. Well in the rendering, depending on the viewing angles, the maximal convex patches visible to the viewer will have to colored.
Sushovan Mandal
CC BY-SA 3.0
2016-03-20T04:02:01.553Z
@nathanreed Below I have posted an answer that should work, can you improve upon it, or can you provide a better solution?
Sushovan Mandal
CC BY-SA 3.0
2016-04-02T07:51:33.137Z
The comments on your answer suggest some confusion over what is meant by "maximal". I believe you are using "maximal" to mean a convex surface which is not a subset of a larger convex surface, rather than to mean the largest convex surface that exists in the triangle mesh. This is covered in your question but due to the confusion it might be worth editing to clarify.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-02T07:59:20.887Z
It would be helpful to know what the purpose is, to give a better idea of exactly what is required. For example, does a convex patch need to be strictly convex (never flat), or does it count as convex provided it is nowhere concave? A cylinder is nowhere concave. It is convex everywhere, but it is not strictly convex in every direction (it is flat in the axial direction). Do you want the surface of a cylinder to count as one convex patch?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-03T08:43:49.370Z
@trichoplax thanks for the suggestion! yes, a convex surface which is not a subset of a larger convex surface, is what is meant. And yes, it needs to be strictly convex. For a cylinder, there would be one convex patch in the whole figure which is maximal, and this patch would not include the axial flat surfaces.
Sushovan Mandal
CC BY-SA 3.0
2016-04-03T11:15:01.443Z
I meant that the curved surface of the cylinder is itself flat in the direction parallel to its central axis. Depending on whether you move to the next triangle around the cylinder or along the cylinder, it will appear to be either strictly convex (moving around), or flat (moving along). Do you require the surface to be strictly convex in every direction, or only one direction?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-03T11:38:01.053Z
It may help to consider a torus. Do you require an algorithm that makes the outer half of the torus a single convex patch, with the triangles on the inner half (around the hole) not counted as being in any convex patch? Or do you require an algorithm that makes the whole surface of the torus a single convex patch, since even on those parts of the surface that are concave in one direction, they are still convex in the perpendicular direction?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-04T07:57:35.103Z
@trichoplax strictly convex is what I am looking for. In the example of the Torus, I require an algorithm that makes the outer half of the torus a single convex patch, with the visible (the inner surface of the other side of the torus will be visible to the viewer) triangles on the inner half (around the hole) , that forms a concave lateral arc to the viewer, it should show convex strips perpendicular to the concave arc. I hope I was able to communicate the idea effectively.
Sushovan Mandal
CC BY-SA 3.0
2016-04-04T12:39:02.793Z
Your description of how the torus should be divided is perfectly clear, but I can't see a way of translating that into a rigorous requirement that would apply to other types of surface. The strips are distinct from each other due to concave edges, but they all seem to be connected to the large outer convex patch, and therefore part of it. I think the main question here is how to unambiguously define what a maximal convex patch is.
trichoplax is on Codidact now
<3d><mesh><computational-geometry><triangulation>
maximal convex patching in Computer graphics
Sushovan Mandal
# maximal convex patching in Computer graphics

(Asked by: username_0 on 2016-03-18)

Given a 3D object in Computer graphics, whose surface is represented as a 3D triangular mesh (mesh of 3D triangle objects), I need to find the maximum continual Convex patches on the surface of the given 3D object.

I am using OpenGl to render the graphics within a C++ program. What kind of methods or algorithms should I use to find the convex patches.

I have to apply different colors to the different convex patches on the object to signify the selection.

Say I have a sphere then the whole sphere is one maximal convex patch. Any portion of the sphere surface will be a convex patch, by maximal I mean the maximum continuous convex patches that can be found. Well in the rendering, depending on the viewing angles, the maximal convex patches visible to the viewer will have to colored. I have to report all the convex patches, each patch being the maximal in that area.

I am using "maximal" to mean a convex surface which is not a subset of a larger convex surface, rather than to mean the largest convex surface that exists in the triangle mesh. The patches need to be strictly convex (never flat).

**Tags:** 3d, mesh, computational-geometry, triangulation

> **Comments:**
> **username_1**: OpenGL doesn't seem like it would help here; it's a computational geometry problem, not rendering. Can you edit the question and define your terms better? What do you mean by a "maximum continual convex patch" exactly?  
> **username_0**: @username_1 opengl will be used to render the objects, processing algorithms are to be done in C++. I have to apply different colors to the different convex patches on the object to signify the selection. Say I have a sphere then the whole sphere is one maximal convex patch. Any portion of the sphere surface will be a convex patch, by maximal I mean the maximum continuous convex patch that can be found. Well in the rendering, depending on the viewing angles, the maximal convex patches visible to the viewer will have to colored.  
> **username_0**: @username_1 Below I have posted an answer that should work, can you improve upon it, or can you provide a better solution?  
> **username_2**: The comments on your answer suggest some confusion over what is meant by "maximal". I believe you are using "maximal" to mean a convex surface which is not a subset of a larger convex surface, rather than to mean the largest convex surface that exists in the triangle mesh. This is covered in your question but due to the confusion it might be worth editing to clarify.  
> **username_2**: It would be helpful to know what the purpose is, to give a better idea of exactly what is required. For example, does a convex patch need to be strictly convex (never flat), or does it count as convex provided it is nowhere concave? A cylinder is nowhere concave. It is convex everywhere, but it is not strictly convex in every direction (it is flat in the axial direction). Do you want the surface of a cylinder to count as one convex patch?  
> **username_0**: @username_2 thanks for the suggestion! yes, a convex surface which is not a subset of a larger convex surface, is what is meant. And yes, it needs to be strictly convex. For a cylinder, there would be one convex patch in the whole figure which is maximal, and this patch would not include the axial flat surfaces.  
> **username_2**: I meant that the curved surface of the cylinder is itself flat in the direction parallel to its central axis. Depending on whether you move to the next triangle around the cylinder or along the cylinder, it will appear to be either strictly convex (moving around), or flat (moving along). Do you require the surface to be strictly convex in every direction, or only one direction?  
> **username_2**: It may help to consider a torus. Do you require an algorithm that makes the outer half of the torus a single convex patch, with the triangles on the inner half (around the hole) not counted as being in any convex patch? Or do you require an algorithm that makes the whole surface of the torus a single convex patch, since even on those parts of the surface that are concave in one direction, they are still convex in the perpendicular direction?  
> **username_0**: @username_2 strictly convex is what I am looking for. In the example of the Torus, I require an algorithm that makes the outer half of the torus a single convex patch, with the visible (the inner surface of the other side of the torus will be visible to the viewer) triangles on the inner half (around the hole) , that forms a concave lateral arc to the viewer, it should show convex strips perpendicular to the concave arc. I hope I was able to communicate the idea effectively.  
> **username_2**: Your description of how the torus should be divided is perfectly clear, but I can't see a way of translating that into a rigorous requirement that would apply to other types of surface. The strips are distinct from each other due to concave edges, but they all seem to be connected to the large outer convex patch, and therefore part of it. I think the main question here is how to unambiguously define what a maximal convex patch is.  

---

## 1 answers

### Answer by username_0 on 2016-03-20. Score: 1 | Accepted answer

Start from any triangle. Traverse it's edge's and check that the angle between the two triangles is less than 180deg. If it is add it to the current selection and continue expanding.

The check is actually really simple if you use vector geometry. Say A - B is the common edge with C on the selected side and D on the other. Then just check if `dot((D-B), cross((A-B), (C-B)) < 0`.

Single triangle patches should be ruled out, as for us to determine convexity, it has to span across several triangles.
We have to keep sampling until we've tested everything. When a convex patch continues further, it's size keeps on increasing by including the neighbouring triangles that satisfy convexity, until the patch reaches the maximum size it can attain.

> **Comments:**
> **username_3**: If a patch ends, and not all triangles have been visited/tested, you have to start anew with another random triangle that is not part of a patch yet. So you find all convex patches and not just the one you happen to begin with. Then chose the biggest one. (Note: Patches can be just a single triangle)  
> **username_0**: @username_3 well for practical purposes I think single triangle patches should be ruled out, as for us to determine convexity, it has to span across several triangles. well we do get all patches, but when a convex patch continues further, it's size keeps on increasing by including the neighbouring triangles that satisfy convexity, until the patch reaches the maximum size it can attain.  
> **username_3**: Yea. I just wanted to emphazise that in order to find the biggest convex patch, you have to keep sampling until you tested everything, since after the first one there might be a even bigger one disconnected that you haven't found jet.  
> **username_2**: A possible problem with this approach is that for some surfaces there will exist a path between two adjacent triangles that is made up only of convex steps, even though the two adjacent triangles touch along a concave edge. In sufficiently smooth examples this may not be a problem as the inaccuracy will only tend to be one triangle wide, but it is possible to construct examples with arbitrarily large concavities that are accessible by purely convex paths. For example, imagine the shape made by pushing a pin into a balloon so that the surface dips inwards (assuming it doesn't burst).  
> **username_2**: I understand that your answer is just an example to get things started. I was just giving some feedback in the hope that it will trigger an idea for improvement from someone.  

---

