I was recently given an assignment to generate a mesh from code, in Unity.

At runtime, the player will click at random positions on the screen. An array will store all these points. There must be at least 4 points for the calculation to take place. The users clicks will stop getting accepted once the player has clicked very close to the first clicked point (till here, I got it to work).

After all the points are added to the array/List, a mesh should be created from those points.

I thought of a few algorithms to work it out. First one - Delaunay triangulation

But what if there are 5 points on the same circle for the mesh? This negates the Delaunay's algorithm.

So I figured I'd first take the entire list of points, and parse through each point to find a convex hull. And then try to do each of the triangles within.

I'm not sure if I'm doing this the right way, or if there is any better way for what I want to do. If this is the best way, I don't know how to do the algorithm for the triangulation inside the convex hull

  • 1
    \$\begingroup\$ Have you searched for "polygon triangulation"? There's a good summary of methods on Wikipedia, including convex triangulation, ear clipping, and decomposition into monotone polygons, and a number of questions already on this site deal with this topic. \$\endgroup\$ – DMGregory Apr 19 '16 at 11:27
  • \$\begingroup\$ Don't worry about delaunay not working for the case you mention. Usually delaunay triangulators jitter the inputs to avoid pathological cases like that one. \$\endgroup\$ – Gato Apr 26 '16 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.