# maximal convex patching in Computer graphics

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).

• 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 Mar 19 '16 at 2:22
• @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 Mar 20 '16 at 4:01
• @nathanreed Below I have posted an answer that should work, can you improve upon it, or can you provide a better solution? – Sushovan Mandal Mar 20 '16 at 4:02
• 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 Apr 2 '16 at 7:51
• 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 Apr 2 '16 at 7:59

## 1 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.

• 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 Mar 20 '16 at 13:13
• @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 Mar 20 '16 at 16:41
• 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 Mar 20 '16 at 20:30
• 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 Apr 3 '16 at 11:30
• @trichoplax I am myself not sure that the algorithm I have posted is optimal or the best one. If you have a better algorithm, please do share. I would love receive it! If another answer turns out to be better, I will unaccept my answer the accept the better one. And for your example, as I said above in coment to the question, if there are local convex strips, they should be shown as local convex strips. – Sushovan Mandal Apr 4 '16 at 8:00