View Full Version : trying to draw a sphere in a single triangle strip

hydrodog

02-07-2014, 06:58 AM

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?

Aleksandar

02-07-2014, 07:59 AM

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.

Brokenmind

02-07-2014, 08:23 AM

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/codedot/11832244/17957/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 (http://www.3dbuzz.com/forum/threads/118279-Quick-solution-for-making-a-sphere-in-OpenGL?p=961840#post961840), but how to add each coordinate only once to the VBO and create an index list out of it is a little more complex ;)

hydrodog

02-07-2014, 10:48 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.

Brokenmind

02-07-2014, 11:46 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):

http://www.junkship.net/Resources/News/VRNcvrUKnEGi3qy9QJi69w.png

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.

hydrodog

02-13-2014, 09:20 PM

I couldn't come up with an analytical solution, I literally built an icosahedron and labelled the sides, thus proving it works.

Brokenmind

02-18-2014, 04:12 AM

Constructing an icosahedron from paper (or whatever) from one cohesive "paper strip" is of course possible, but a triangle strip in openGL can't just arbitrarily change directions; in a fixed triangle mesh, as soon as you choose the starting triangle and direction, the strip is definite. If you could show a photograph of your built icosahedron, I could point out where your solution makes a turn impossible for triangle strips. Just a proposal...

Anyway, I think it is not possible in openGL to build such a thing.

wmelgaard

02-21-2014, 10:18 AM

See the attached program for (hemisphere) from a single line strip. If the limit in line 38 is changed from 180 - 360, you will get the entire sphere

Left click and drag rotates the model.1235

Powered by vBulletin® Version 4.2.3 Copyright © 2018 vBulletin Solutions, Inc. All rights reserved.