Stephen's Blog

Knowing that sqrt() is an expensive function, I attempted to cache the calculated magnitude value inside my getMagnitude() function of my Vector class. Whenever getMagnitude() is called, a check is made to determine whether or not the magnitude value has been computed for the given vector, and the magnitude value is returned after being computed if necessary. If you ever needed to know the magnitude of a vector more than once, calls after the first were cheap.

In practice, this optimization is very disappointing. After some profiling, I have determined that out of 847,767 calls, only 15,482 were able to take advantage of my caching scheme — roughly 1.9%. The cost of the check alone probably outweighs the benefits, and the storage of the cached magnitude adds another floating point value to the storage requirements for my Vector structure.

It’s worth noting that others may find this particular optimization to be very effective. In most cases, getMagnitude() was being called on Vectors that immediately fell out of scope, so the caching scheme was usually guaranteed to be fail.

Moral of the story: premature optimization is best avoided, and optimizations of this nature should be driven by profiling statistics.

You’d think it would be trivial to convert an image to RGB 565 format (16 bits per pixel, using 5 bits for red, 6 for green (since our eyes are more sensitive to it) and 5 for blue). This format was popular years ago, and is making a come back in the mobile arena where most video hardware supports only 16 bpp. In fact, the OpenGL ES standard only allows 16 bpp.

Yet none of the popular image editing software presents you a way to do this.

The ffmpeg utility will do this, fortunately. It can be invoked as such:

ffmpeg -vcodec png -i source.png -vcodec png -pix_fmt rgb565 destination_565.png

Season to taste.

To see a list of “pix_fmt’s” that are supported:

ffmpeg -pix_fmts

This how to will explain how to derive a list of vertices that will be useful in rendering a sphere in 3 dimensions. If you’re only interested in a code example, you’ll find a functional class toward the bottom; however, I will first attempt to explain the concepts.

Sampling Points

Lets start with a definition of a sphere (I assume you know what a sphere is, but a precise definition will provide some insight on where we might find our vertices.) Wolfram defines a sphere as:

…the set of all points in three-dimensional Euclidean space that are located at a distance R (the “radius“) from a given point (the “center“).

Our clue lies in the beginning of the definition, “…the set of all points…” What this means is that any equation we may use for a sphere will be useful to find points in this set. In other words, any one solution to this equation will yield precisely one point on the sphere. Essentially, we want to sample points along our sphere. The usual equation for a sphere, again borrowed from Wolfram:
x^2 + y^2 + z^2 = R^2
This equation, however, is not entirely useful to us yet. In order to find a single point, we need to know several variables. For example, we know that a unit sphere (a sphere with R=1) will touch the point at  (0, 0, 1), so if we were to use our known values for x and y and R here, we could solve for z:
0^2 + 0^2 + z^2 = 1^2
z^2 = 1
z = sqrt( 1 )
z = +/- 1
Again, this isn’t entirely useful to us because we can only find a useful triplet (x, y, z) by knowing two of its values, which we only knew beforehand because it was convenient. We could find some useful points by looking at the range for x: [-R, R], y: [-R,R], etc. By taking various pairs in these ranges, we could find our vertices by solving for z, but once we define x, our range for y changes, and vice-versa. This is the right concept, but lets look at at another way to define a sphere, which might be more conducive to sampling points in the manner we need.

Spherical Coordinate System

You’ve probably studied an alternative system for describing locations on a sphere in geography related to our Earth. To describe points on our globe, we talk about two variables: latitude and longitude. Distinct values for both of these describes exactly one point on the planet. Latitude describes a horizontal ring around our globe, while Longitude describes a vertical ring around the globe (actually, a semicircle). Where these two intersect, we have our unique location. We often call this coordinate system a geographic coordinate system.

This is actually a special case of a spherical coordinate system. In a spherical coordinate system, we can describe any point as we did above, with one additional value: radius. In our geographic coordinate system, we have a fixed and known radius (6,378.1 kilometers, says Google), so we take it for granted. In a spherical coordinate system, this additional value allows us to describe any point in 3 dimensions. The longitude is usually called θ (theta), and the latitude φ (phi).

The spherical coordinate system essentially uses two angles and a radius to describe points. You can read more about spherical coordinate systems on Wikipedia and Wolfram. As earlier, we can define any point with a triplet (θ, φ, r), now a couple bonuses: we know one of our values (r), and we don’t have the range dependency problems for the other two as we encountered earlier.

Our range for θ is [0, 2Π] and our range for φ is [0, Π], and these ranges do not depend on each other. So we can take any value in one, and any value in the other, and given our radius, we have a point on our sphere. If we sample these values at even intervals, we will have vertices that will make a consistent looking sphere. The smaller the interval we use, the more vertices we will come up with, and the more detailed our sphere will be. Obviously, this will be more work for our rendering engine, so there is an important trade-off there.

We have one last challenge: our rendering engine probably doesn’t like spherical coordinates, so we need to convert back to cartesian coordinates. Fortunately, this is a trivial matter of trigonometry, and we can use sine and cosine for our conversions as follows:
x = r cos θ sin φ
y = r sin θ sin φ
z = r cos φ

Algorithm

Now we have a convenient way to sample points on our sphere and convert them to the coordinate system we need. All we need to do this is a few variables to describe (1) our radius, (2) how many values in the range for θ we want to sample, and (3) how many values in the range for φ we want to sample.  In the code below, we call these numStacks and numSlices. Given these, a couple for-loops is all we need.

Before I get to the example code, let me briefly explain one more thing. In OpenGL, it is possible (and preferred) to reuse vertices. If a vertex is shared between two or more polygons, you can define the vertex once and refer to it by its index as often as needed. For example, if you have triangles ABC and BCD, you can first define an array of your vertices (ABCD), then define your triangles by the indices of your vertices. So our triangles above would be 0,1,2 and 2,3,4. This should explain part of the code below related to indices, except they are designed to use triangle strips. I won’t bother explaining those, as Google will be able to tell you all about them.

So here’s the code, this first one I’ve defined in sphere.h:

class Sphere {
    public:
        Sphere( const float radius, const unsigned int numStacks, const unsigned int numSlices );
        ~Sphere();
 
        float const getRadius() const { return _radius; };
        unsigned int const getNumStacks() const { return _numStacks; }
        unsigned int const getNumSlices() const { return _numSlices; };
 
        const float* const getVertices() const { return _vertices; };
        unsigned int const getNumVertices() const { return _numVertices; };
 
        const unsigned short* const getIndices() const { return _indices; };
        unsigned int const getNumIndices() const { return _numIndices; };
    private:
        // given
        const float _radius;
        const unsigned int _numStacks;
        const unsigned int _numSlices;
 
        // computed
        unsigned int _numVertices;
        unsigned int _numIndices;
        float* _vertices;
        unsigned short* _indices;
};

And sphere.cpp:

Sphere::Sphere( const float radius, const unsigned int numStacks, const unsigned int numSlices ) :
        _radius(radius), _numStacks(numStacks), _numSlices(numSlices) {
 
    _numVertices = (numStacks + 1) * numSlices;
    _vertices = new float[ _numVertices * 3 ];
 
    _numIndices = numStacks * (numSlices + 1) * 2;
    _indices = new unsigned short[ _numIndices ];
 
    // build vertices. loop around each stack to get all the vertices on it.
    int vertexIndex = 0;
    for ( unsigned int stackNum=0; stackNum<=_numStacks; ++stackNum ) {
        for ( unsigned int sliceNum=0; sliceNum<_numSlices; ++sliceNum ) {
 
            float theta = stackNum * (PI / numStacks);
            float phi = sliceNum * 2 * (PI / numSlices);
            float sinTheta = sin(theta);
            float sinPhi = sin(phi);
            float cosTheta = cos(theta);
            float cosPhi = cos(phi);
 
            _vertices[ vertexIndex ] =      _radius * cosPhi * sinTheta;
            _vertices[ vertexIndex+1 ] =    _radius * sinPhi * sinTheta;
            _vertices[ vertexIndex+2 ] =    _radius * cosTheta;
            vertexIndex+=3;
 
        }
    }
 
    // build indcies. for each stack, loop around and build a triangle strip.
    int indexIndex = 0;
    for ( unsigned int stackNum=0; stackNum<_numStacks; ++stackNum ) {
        for ( unsigned int sliceNum=0; sliceNum<=_numSlices; ++sliceNum ) { // less than or equal, as opposed to above
 
            _indices[ indexIndex ] = (stackNum * numSlices) + (sliceNum % _numSlices);
            _indices[ indexIndex+1 ] = ( (stackNum + 1) * numSlices ) + (sliceNum % numSlices);
 
            indexIndex+=2;
        }
    }
}
 
Sphere::~Sphere() {
    delete [] _vertices;
    delete [] _indices;
}

I hope this has been helpful. Don’t hesitate to ask questions.