trying to draw a sphere in a single triangle strip
I currently have code that draws a sphere as a series of quad strips for each latitude. There is a hole at the pole which could be filled with an end cap made of a triangle fan.
Instead, I would like to cover a sphere in a single strip of triangles. This would be efficient, as it is a single operation, but it is harder to visualize.
I created a paper model of an icosahedron and verified that I can start with one face, and number the faces sequentially hitting every one once until all are covered. My question is whether this would work for any arbitrary triangle covered shape with no holes.
Let's start with an icosahedron that is recursively split so that each face turns into 4 triangles. This is done by divide each edge in two. Can I number one face and go all through the faces? I have no idea and this one is not as easy to cut out and try.
Last, if it is possible, how could I determine the points and the order?
Are you using an immediate-mode drawing or buffers? If you are using buffers (VBO), then your previous algorithm with strips can be used, just add primitive restart index at each strip end. This also assumes using indices for juming through VBO.
The question whether this is possible for an arbitrary triangular geometry is actually quite complex! I have written a program to calculate this a while ago. The form was as simple as a cube, and there the program said it was possible (the solution is shown here http://ic.pics.livejournal.com/coded.../17957_320.png). However, for any more complex forms, there is most likely no solution, and if it is, the complexity to find it is O(n!), if you are familiar with this.
Moreover, why are you trying to draw it in one single strip? Triangle strips are widely considered the fastest type of drawing, but that was long ago. This performance win was due to the fact that the triangles did not have three coordinates, but only 1 in a strip (apart from the first triangle which has of course 3). In the times of VBOs, where you save all coordinates and simply draw index lists, the saving of memory is greatly reduced.
Not so long ago, I even did a performance test, drawing 512x512 quads (or 512x512x2 triangles). GL_TRIANGLES was only some 2% slower than GL_TRIANGLE_STRIP, and GL_QUADS and GL_QUAD_STRIP were again 2% slower than GL_TRIANGLES. This was one measurement, and the results varied, so it is not even certain that the strip is always fastest. You see, as the memory can be ignored (if you don't plan to draw billions of triangles), the performance is roughly the same for everything.
€dit: Very good code on how to draw an approximated sphere in openGL by use of an icosahedron can be found here, but how to add each coordinate only once to the VBO and create an index list out of it is a little more complex
Last edited by Brokenmind; 02-07-2014 at 07:35 AM.
I suspect for any platonic solid, it is possible. Hamilton asked whether there was a path visiting each vertex and returning to the start without visiting any edge twice, and that was doable with any platonic solid.
You said you wrote a program to do it. I can just visualize a cube and realize that I can do one face, then the four adjacent faces, then the opposite one. I couldn't visualize the icosahedron which is why I built one, but it works.
I want something quite a bit simpler. I suspect that any object that is topologically similar to a sphere will work, but I really don't know, it might require that the number of triangles going around to be odd or even.
Why do I want to do this? It will not only be faster, it will be more elegant. And right now, the implementation I have drawing a sphere doesn't do well at the poles. This way the poles will be a triangle like anything else. This won't have to distort pixels in a projection to map onto triangles, I could define the texture to map more simply directly to the triangles.
Last edited by hydrodog; 02-07-2014 at 10:25 AM.
Keep in mind: Visiting each vertex once without visiting any edge twice (but every edge once, I suppose?) and drawing an arbitrary solid in one triangle strip is not quite the same... I'd like to see your solution for the icosahedron, if possible!
Is the implementation you have by chance the gluSphere, on the right of this picture (with the quads replaced by two triangles):
The left one is, as you know, the icosahedron sphere which has a much more consistent triangle distribution, but if you plan to map textures to it, I guess the texture coordinates are harder to calculate than for a gluSphere.
The object I wrote the program for is in fact a truncated octahedron, and there are many ways to distribute triangles in it. As soon as a specific distribution and a starting point was chosen, the triangle strip (as far as I know) has only one possibility to cover the surface, and it's not easy to let it not cover faces twice. For the trunc. octahedron, I found no possibility to cover it with just one strip. You claim it's possible for every sphere-like object, but as soon as you replace one triangle by four smaller ones, any triangle strip will cover at most three of them, so I don't see how this can work.
I couldn't come up with an analytical solution, I literally built an icosahedron and labelled the sides, thus proving it works.
Tags for this Thread