2
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$
    – Nathan Reed
    Commented Mar 19, 2016 at 2:22
  • $\begingroup$ @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. $\endgroup$
    – Sushovan Mandal
    Commented Mar 20, 2016 at 4:01
  • $\begingroup$ @nathanreed Below I have posted an answer that should work, can you improve upon it, or can you provide a better solution? $\endgroup$
    – Sushovan Mandal
    Commented Mar 20, 2016 at 4:02
  • $\begingroup$ 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. $\endgroup$
    – trichoplax is on Codidact now
    Commented Apr 2, 2016 at 7:51
  • $\begingroup$ 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? $\endgroup$
    – trichoplax is on Codidact now
    Commented Apr 2, 2016 at 7:59

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$
    – Dragonseel
    Commented Mar 20, 2016 at 13:13
  • $\begingroup$ @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. $\endgroup$
    – Sushovan Mandal
    Commented Mar 20, 2016 at 16:41
  • $\begingroup$ 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. $\endgroup$
    – Dragonseel
    Commented Mar 20, 2016 at 20:30
  • $\begingroup$ 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). $\endgroup$
    – trichoplax is on Codidact now
    Commented Apr 3, 2016 at 11:30
  • $\begingroup$ 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. $\endgroup$
    – trichoplax is on Codidact now
    Commented Apr 4, 2016 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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