Object Orientated Design to build a sphere in OpenGL

Introduction

The motivation for this project is to do some object oriented design with C++. The problem I have chosen is to draw a sphere in OpenGL without repeating vertices. Modern OpenGL does not provide any direct means to draw a sphere, rather the user needs to render a collection of triangles to achieve this. Each triangle is specified by three vertices which coincide with its corners. So it turns out that each vertex is shared by several triangles and we are left with the problem of not repeating the same vertex.

The approach I will use provides an efficient O(n log(n)) algorithm (n being the final number of vertices or number of triangles). However the algorithm or code will be special to this type of problem where we are dividing triangles. There are more general approaches such as searching for repeated vertices and removing them, or perhaps  making the vertices first and then finding the triangles second. But with these methods you will tend to get an O(n^2) algorithm, although this is probably not such a major drawback in practice and things can be sped up with the use of a hash table or some other search mechanism. Regardless; at the end of the day we will end up with a good little API to make a sphere in OpenGL.

The Problem

The basic approach to make a sphere by dividing triangles is easy to find on the web. We will start with an octahedron which consists of eight triangles. A topological graph of an octahedron is shown in Fig. 1. An octahedron is formed from eight triangles, which neighbour each other, and we wish to divide these triangles into more triangles to get something that is much closer to a sphere.

Fig. 1. Topological graph for an octahedron.

We can divide each of these triangles into four smaller triangles as shown in Fig. 2. We then normalise the lengths of all the vertices to unity to approximate a sphere of unit radius. Thus for each triangle we make three new vertices, but these vertices are shared with neighbouring vertices, and  we don't want to repeat ourself. We are left with the task of assigning the new vertices when needed and asking neighbouring triangles for them when they already exist. To do this we will use some object oriented design, by making a sphere object which is formed from a collection of triangle objects.

Fig. 2. Diagram showing how a triangle is divided into four smaller triangles.

The Objects

The sphere

Our sphere class has the following data:

    std::vector<GLfloat> verts;
    std::vector<GLuint> inds;
    std::vector<triangle> trigs;
    const GLuint order, nVerts, nTri;
    GLuint triCnt, triCntOld, vertCnt, vertCntOld;

There a three vectors, the first of which (vert) represents the set of vertices for our sphere which specify the corners of the triangles, the second (inds) is the set of indices which specify the vertices to form each triangle (as used by OpenGL), and the third (trigs) is the set of triangles. We also have (order) the number of iterations where each triangle is divided into four new triangles. If order = 0 we simply use the octahedron and if order = 1 we divide each of the octahedron's triangles into 4 new triangles only, then stop. If order is bigger we iterate the same procedure order times. The constants nVerts and nTri are the total number of vertices and triangles we end up with, and the last line of variables are just for counting these numbers as we iteratively build our sphere.

The triangles

Our triangle class encapsulates the following data:

    std::array<GLuint, 3> index; 
    std::array<GLuint, 3> neigh_tri; 
    std::stack<std::array<GLuint, 3> > lifo;

The first two arrays of length 3 hold the indices (index)  for the triangles three vertices and the indices (neigh_tri) for the three neighbouring triangles. These indices refer to the vectors in the sphere object, and only triangles which share an edge are considered neighbours. There is also a stack (called lifo) which these two arrays can be pushed onto.

Labelling conventions for triangles and Dividing triangles

We employ the following labelling convention. When we look at the face of a triangle from outside the sphere it either points up or down as shown in Fig. 3. The vertex indices (for the triangles' array: index) are ordered according to whether they are left, right, or top/bottom as per Fig. 3. In addition the neighbouring triangles (for the triangles' array: neigh_tri) are also ordered according to the orientations given in Fig. 3. These conventions are then used to subdivide our triangles while keeping tack of all the vertices and neighbours. Keeping these conventions in mind is crucial if you wish to delve into the full details of the source code.

Fig. 3. Diagram showing how the indices are ordered for both the vertices and the neighbouring triangles, when the triangles are pointing up or down.

When we subdivide a triangle the triangle object pushes its two array objects onto its stack. This triangle object will then become the smaller triangle in the centre of the subdivided triangle as shown in Fig. 2. But first we make all the new vertices and store the corresponding indices in the triangles array (index) that they belong to. 

To do this without repeating vertices we use the size of the triangles' index in the sphere class to establish a precedence. If the index of the neighbouring triangle is less than the one we are currently working on, then this vertex has already been made and we get the required index off the neighbour. Otherwise we make a new vertex.

After doing this we make three new triangles for each existing triangle, then re-establish which triangles neighbour each other while popping the stacks at appropriate times. This is all easier said than done, but you may read the code for full details.

The Code

The C++ code is available from my GitHub page: https://github.com/wilstep/OpenGL-sphere/releases/tag/v1.0. The code is arranged so that it can easily be reused as an API if you want to draw a sphere in some other application. As it stands it is set up for use on Linux. There is a single command line argument which sets the order variable. The resulting approximate sphere is rendered with lighting and shading, and the approximate sphere rotates on its y-axis. The figure below, Fig. 4, shows the order-0 sphere which is a octahedron. However this octahedron has the normal vectors for a sphere and so the lighting is all incorrect for an octahedron.

Fig. 4. An order-0 sphere, which is actually an octahedron. The edges are hard to see (in places) because the shading normals are for a sphere, not an octahedron.

The next figure, Fig. 5, shows an order-4 sphere that looks very convincing (2,048 triangles), however if you run this on your computer and focus on the spot where the light is reflected it will still be apparent that the sphere is rotating. If we go to order-6 (32,768 triangles) then this artefact disappears.

Fig. 5. An order-4 sphere which is composed of 2,048 triangles.

 That is all for this little project.