Generating vertices for a sphere

Question

In the DirectX mobile lighting sample, a cylinder is generated in the following manner:

for( DWORD i=0; i<50; i++ )
            {
                FLOAT theta = (2*D3DMX_PI*i)/(50-1);
                pVertices[2*i+0].position = D3DMXVECTOR3( (float)sin(theta),-1.0f, (float)cos(theta) );
                pVertices[2*i+0].normal   = D3DMXVECTOR3( (float)sin(theta), 0.0f, (float)cos(theta) );
                pVertices[2*i+1].position = D3DMXVECTOR3( (float)sin(theta), 1.0f, (float)cos(theta) );
                pVertices[2*i+1].normal   = D3DMXVECTOR3( (float)sin(theta), 0.0f, (float)cos(theta) );
            }

Is there a similar way to generate vertices for a sphere in DirectX Mobile(as a triangle strip or otherwise)? (AFAIK there's no D3DMXCreateSphere method)

---

The final solution .Thanks to quarternion for all his help.

void CreateSphere()
{
    const int iFactor = 20;
    int iPos = 0;

    arr_Vertices = new CUSTOMVERTEX[ui_VCount];
    ui_ShapeCount = iFactor *iFactor * 2; // use when rendering

    float arrV[iFactor* iFactor][3];

    for (DWORD j= 0; j < iFactor; j ++)
    {
        FLOAT theta = (D3DMX_PI*j)/(iFactor);

        for( DWORD i=0; i<iFactor; i++ )
        {
            iPos = j*iFactor+i;
            FLOAT phi = (2*D3DMX_PI*i)/(iFactor);
            arrV[iPos][0] = (float)(sin(theta)*cos(phi));
            arrV[iPos][1] = (float)(sin(theta)*sin(phi));
            arrV[iPos][2] = (float)(cos(theta));

            /*std::cout << "[" << j <<"][" << i << "] = " << arrV[iPos][0]  
                << "," << arrV[iPos][1] << "," << arrV[iPos][2] <<std::endl;*/
        }
    }

    int iNext = 0;

    for (DWORD j= 0; j < iFactor; j ++)
    { 

        for( DWORD i=0; i<iFactor; i++ )
        {
            if (i == iFactor - 1)
                iNext = 0;
            else iNext = i +1;

            iPos = (j*iFactor*6)+(i*6);
            arr_Vertices[iPos].position = D3DMXVECTOR3( arrV[j*iFactor+i][0], arrV[j*iFactor+i][1], arrV[j*iFactor+i][2]);
            arr_Vertices[iPos + 1].position = D3DMXVECTOR3( arrV[j*iFactor+iNext][0], arrV[j*iFactor+iNext][1], arrV[j*iFactor+iNext][2]);


            if (j != iFactor -1)
                arr_Vertices[iPos + 2].position = D3DMXVECTOR3( arrV[((j+1)*iFactor)+i][0], arrV[((j+1)*iFactor)+i][1], arrV[((j+1)*iFactor)+i][2]);
            else
                arr_Vertices[iPos + 2].position = D3DMXVECTOR3( 0, 0, -1); //Create a pseudo triangle fan for the last set of triangles

            arr_Vertices[iPos].normal = D3DMXVECTOR3( arr_Vertices[iPos].position.x, arr_Vertices[iPos].position.y, arr_Vertices[iPos].position.z);
            arr_Vertices[iPos + 1].normal = D3DMXVECTOR3( arr_Vertices[iPos+1].position.x, arr_Vertices[iPos+1].position.y, arr_Vertices[iPos+1].position.z);
            arr_Vertices[iPos + 2].normal = D3DMXVECTOR3( arr_Vertices[iPos+2].position.x, arr_Vertices[iPos+2].position.y, arr_Vertices[iPos+2].position.z);

            arr_Vertices[iPos + 3].position = D3DMXVECTOR3( arr_Vertices[iPos+2].position.x, arr_Vertices[iPos+2].position.y, arr_Vertices[iPos+2].position.z);
            arr_Vertices[iPos + 4].position = D3DMXVECTOR3( arr_Vertices[iPos+1].position.x, arr_Vertices[iPos+1].position.y, arr_Vertices[iPos+1].position.z);

            if (j != iFactor - 1)
                arr_Vertices[iPos + 5].position = D3DMXVECTOR3( arrV[((j+1)*iFactor)+iNext][0], arrV[((j+1)*iFactor)+iNext][1], arrV[((j+1)*iFactor)+iNext][2]);
            else
                arr_Vertices[iPos + 5].position = D3DMXVECTOR3( 0,0,-1);

            arr_Vertices[iPos + 3].normal = D3DMXVECTOR3( arr_Vertices[iPos+3].position.x, arr_Vertices[iPos+3].position.y, arr_Vertices[iPos+3].position.z);
            arr_Vertices[iPos + 4].normal = D3DMXVECTOR3( arr_Vertices[iPos+4].position.x, arr_Vertices[iPos+4].position.y, arr_Vertices[iPos+4].position.z);
            arr_Vertices[iPos + 5].normal = D3DMXVECTOR3( arr_Vertices[iPos+5].position.x, arr_Vertices[iPos+5].position.y, arr_Vertices[iPos+5].position.z);

            //std::cout << "[" << iPos <<"] = " << arr_Vertices[iPos].position.x << 
            //  "," << arr_Vertices[iPos].position.y <<
            //  "," << arr_Vertices[iPos].position.z <<std::endl;

            //std::cout << "[" << iPos + 1 <<"] = " << arr_Vertices[iPos + 1].position.x << 
            //  "," << arr_Vertices[iPos+ 1].position.y <<
            //  "," << arr_Vertices[iPos+ 1].position.z <<std::endl;

            //std::cout << "[" << iPos + 2 <<"] = " << arr_Vertices[iPos].position.x << 
            //  "," << arr_Vertices[iPos + 2].position.y <<
            //  "," << arr_Vertices[iPos + 2].position.z <<std::endl;
        }
    }
}

Should be usable with only a few adjustments. This creates a TRIANGLELIST but could be altered to output a set of triangle strips

Brucine

Do you have any requirements about, say, the minimum distance between two vertices? – Constant

No, there's not such requirement. I've been trying to come up with a formula for this for a while but failed. If I could get a hang of the basics I think I'd be able to tweak it for performance – Brucine

Is there anything wrong with using D3DXCreateSphere()? At the very least you could copy the vertices it creates somewhere else if you don't want the ID3DXMesh object. MSDN Documentation here: msdn.microsoft.com/en-us/library/bb172795(VS.85).aspx – Bedpost

Sorry tbridge. I should have mentioned that this was for the directx mobile api. There's no method simillar to D3DXCreateSphere(). – Brucine

There is a static Mesh.Sphere() method for the Mobile DirectX API too? Or am I still not understanding :)? msdn.microsoft.com/en-us/library/… – Bedpost

Unfortunately I can't use methods from the .net framework so Mesh.Sphere is not an option. I'm trying to see if there's an alternative to modeling a sphere and using the exported mesh so I could keep things simple. – Brucine

Full solution: #4558811 – Coven

Answer 1

Basic way of thinking about it:

First method not using a continuous triangle strip...

It's been a while so I might make a mistake...

A unit circle defined parametrically:

Where 0 =< theta < 2pi 
x = sin(theta);
y = cos(theta);

Now that we can define a single circle, imagine concentric rings on the x,y plane. Now imagine raising the inner most circle and as you raise it it pulls up the next ring, like a slinky... This visual only works for half a sphere.

So the form that produces the shape of a sphere from the concentric rings is of course another circle which is orthogonal to the rings, the (z,y) plane... Of course we are only interested in finding the offset of the ring (how high or low it needs to be offset from the (x,y) plane.

Because we just need the offset we only need half a circle... and further the poles will only be a single point. Use a triangle fan at the poles and strips between each ring.

After this mental exercise see http://en.wikipedia.org/wiki/Sphere and search for "The points on the sphere with radius r can be parametrized via" and you'll see the parametric form after that line.

The normals are very easy the sphere should always be built around (0,0,0) and the sphere should always be built with a radius of 1 (so you can simply scale it to the desired size) and then each vertex on the circle surface is equal to the normal.

---

The above method uses two triangle fans and a series of triangle strips... another method which produces a sphere with an even distribution of vertexes and can be drawn with a single triangle strip, although at the moment I'd go crazy trying to code it involves the following idea:

Imagine a tetrahedron centered about the origin (the points are 1 unit from 0,0,0). It is a pretty pathetic representation of a sphere but it is an approximation. Now imagine that we find the midpoint on each of the four faces and then push that point out until it is on the surface of the sphere. Then we find the midpoints of those faces and push them out to the surface of the sphere...

tetrahdralSphere(int recursions){}

Finding the mid point is very simple it is just the average of each of the x,y,z components. Then since the sphere is a unit sphere moving them to the surface is as simple as normalizing this new vector.

---

Method one produces a point distribution that looks lines of longitude and latitude and produces a non uniform distribution (it looks just like a globe if using quads and a wire frame), it is quite easy to implement. The second method requires recursion so it a little more difficult but will look more uniform. If you want to get really complicated and hurt your head... then try distributing n points and then simulate a repellent force between points which moves them apart and then normalize them across the surface. There are all kinds of headaches that need to addressed to make this work effectively but then you have rather uniformly distributed points and you can control the number of vertices's and you'll have have the very start of appreciation of what it takes for modeling tools to find the minimal geometry to represent a model.

---

Going with the first method. Draw a point at (0,0,1) then you need your first concentric ring (each ring will have the same number of points for simplicity).

Lets draw 10 points per ring... so phi will step in increments of 2pi/10 and lets draw 10 concentric rings

and we will draw 10 rings + 2 poles so theta will increase in increments of pi/12.

//this psudo code places the points
//NOT TESTED
deltaTheta = pi/12;
deltaPhi = 2pi/10;
drawVertex(0,0,1) //north pole end cap
for(int ring; ring < 10; ring++){ //move to a new z - offset 
  theta += deltaTheta;
  for(int point; point < 10; point++){ // draw a ring
    phi += deltaPhi;
    x = sin(theta) * cos(phi)
    y = sin(theta) * sin(phi)
    z = cos(theta)
    drawVertex(x,y,z)
  }
}
drawVertex(0, 0, -1) //south pole end cap

Composure

Thanks Quarternion. Regarding the first method, the Wikipedia page was one of the first I visited when trying to come up with an answer. The thing that stumped me was that we needed to have two 3 variables, r, theta and phi. I failed to come up with a way to derive phi from r and theta. Could we assume that theta = phi (assuming r = 1)? or is there another way to derive phi? I'm really confused at this point – Brucine

Oh well lets have you write out that equation on paper... first your going to center it about the origin because you can always translate it were you want... so get rid of the x0, y0 and z0 components(they are just translation components), next we've agreed that you can just scale your sphere as big as you need so get rid of the "r" on each line... there that should be cleaner. Next know that theta and phi are any value that is in the given ranges. I know there is a way to make this very easy... I'll get back. – Composure

Okay... Going back to that equation (on the wiki without the unneeded variables)... This parametric form is easiest to visualize as concentric rings seen as if looking into the (x,y) plane or the surface of the screen, and z going into the screen so it is like looking at the earth from the north pole. We can see that z = cos(theta) so there are two axis in a sphere and with the z axis already accounted for that means that the sin() component (the width or a ring) is determined be sin() that is why the x and y variables have an extra sin() mixing into what would be the eq of a circle (z aside). – Composure

Thanks. Followed your pseudo code and it generates a beautiful sphere consisting of uniformly distributed points. Could you give me some advice on how to properly make this point list in to a triangle strip or a triangle fan? I know I should add additional points to make up triangles but don't know exactly how – Brucine

and riemers.net/eng/Tutorials/DirectX/Csharp/Series3/… then fist allocate the vertices's into memory probably a couple variables for the poles and an array of arrays for the rings and then draw them in another step. – Composure

Answer 2

The usual way to triangulate a unit sphere is to build a tetrahedron or a icosahedron and

• If precision is enough, stop
• Else, for each existing face:
• Add a vertex at the midpoint of each edge and normalize it so that it is on the unit sphere
• Replace the face with four new faces. One of the faces has the three new midpoints as corners (draw it on paper, and the other three faces will become obvious)
• Loop.

To avoid duplicating vertexes at the edge midpoints, you need to track the existing vertices for reuse.

Kester