1

I am currently experimenting with openGL, and I'm drawing a lot of circles that I have to break down to triangles (triangulate a circle).

I've been calculating the vertices of the triangles by having an angle that is incremented, and using cos() and sin() to get the x and y values for one vertex.

I searched a bit on the internet about the best and most efficient way of doing this, and even though there's not much information avaliable realized that thin and long triangles (my approach) are not very good. A better approach would be to start with an equilateral triangle and then repeatedly add triangles that cover the larges possible area that's not yet covered.

left - my method; right - new method

left - my method; right - new method

I am wondering if this is the most efficient way of doing this, and if yes, how would that be implemented in actual code.

The website where I found the method: link

SamFF
  • 203
  • 1
  • 7
  • I expect that using outscribbed square (or some polygon with less vertexes for example 6-10) and [shader that discards pixels outside circle](https://stackoverflow.com/a/41442375/2521214) will be faster but you have to measure on targeted HW to be sure... along with geometry shader you could pass just center point and radius instead of full geometry – Spektre Feb 19 '23 at 08:05
  • Meshing a circle or a sphere is a fascinating topic overall. In your case what kind of efficiency are you interested in? Do you want the least area difference per iteration? – John Alexiou Feb 19 '23 at 13:59
  • @Spektre I don't want to do that on the fragment shader, I just want to calculate the vertices for the triangles and store them in an array. – SamFF Feb 19 '23 at 20:38
  • @JohnAlexiou As described on the website I mentioned, I want that any triangle added covers the maximum possible area that is not covered. – SamFF Feb 19 '23 at 20:39
  • FYI - Thin skinny triangles are to be avoided as they are numerically unstable. – John Alexiou Feb 19 '23 at 22:56

1 Answers1

1

both triangulations has their pros and cons

The Triangle FAN has equal sized triangles which sometimes looks better with textures (and other interpolated stuff) and the code to generate is simple for loop with parametric circle equation.

The increasing detail mesh has less triangles and can easily support LOD which might be faster. However number of points is not arbitrary (3,6,12,24,48,...). The code is slightly more complicated you could:

  1. start with equilateral triangle remembering circumference edges

    so add triangle (p0,p1,p2) to mesh and edges (p0,p1),(p1,p2),(p2,p0) to circumference.

  2. for each edge (p0,p1) of circumference

    compute:

    p2 = 0.5*(p0+p1); // mid point
p2 = r*p2/|p2|;   // normalize it to circle circumference assuming (0,0) is center

    add triangle (p0,p1,p2) to mesh and replace p0,p1 edge with (p0,p2),(p2,p1) edges

    note that r/|p2| will be the same for all edges in current detail level so no need to compute expensive |p2| over and over again.

  3. goto #2 until you have enough dense triangulation

so 2 for loops and few dynamic lists (points,triangles,circumference_edges,and some temps if not doing this inplace). Also this method does not need goniometrics at all (can be modified to generate the triangle fan too).

Here similar stuff:

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Hello Spektre, hope you are doing fine, can you join this chat room https://chat.stackoverflow.com/rooms/252092/3d-graphics – andre_lamothe Feb 23 '23 at 21:52