# 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

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.