Spheres Through Triangle Tessellation

There are several methods of creating spheres.  The most common is to follow longitude and latitude lines and construct the sphere of latitude and longitude segments.  The sphere is then rendered in quadrilaterals.  The primary problem with this method is that it is inefficient and leaves noticeable artifacts at the poles, because of the packing of vertices.  One look at a globe with latitude and longitude lines will show you the vertex configuration, and it is NOT even.  The main failing of our navigation in fact, is that we do not use great circles in spherical geometry to plot our course, so we often do not choose the shortest possible path.  In fact, the only time we can choose the shortest path by drawing a straight line on a map if we travel straight north-south, or if we are going around the equator.  This is because these are great circles.  Obviously, not only is this an inefficient way to render a sphere, but an outdated and archaic not to mention debunked geographic coordinate system.

Fig. 1

There is another method I’m not going in to go in to now, and that is the method using great circles.  A great circle can be seen in red in Fig. 1.  The plane must go through the center of the sphere in order for the circle to be a great circle.  This way the circle is as big around as possible.  In the picture in Fig. 1 you may also note that the white lines defining the sphere are the exact latitude and longitude lines I spoke of earlier.  Notice how they bunch up inefficiently at the poles, and therefore skew navigational projection as well as rendering more inefficently, as far fewer polygons are needed to match the detail level of the areas of the sphere closer to the equator.  Now, the great circles method is something I have not yet figured out how to do, but rest assured, that is the only way you can actually hit every geodesic platonic solid.

The method I will show you is simple to do, as the only algorithm needed is this: tessellate each face and normalize the resulting extra vertices to the pseudo-radius (distance from centroid of every vertex on the hull.)  It is important to realize that this will not give you a geodesic surface, but it will be so damn close it is nearly impossible to tell when the detail level is high enough.  The more complex a geodesic hull you start with, the less this drift is apparent.  I recommend an icosahedron for smoothness, or an octahedron if you plan on projecting a texture on to it, as you have a vertex at each pole, assuming you want to do something like project a traditional coordinates earth map on to it.

Fig. 2

How to do such a thing?  Well, in Fig. 2 you can see how the subdivision in our tessellation works.  The blue vertices are the ones we produce.  Then what we do is normalize them to the same distance from the centroid as the black original vertices, the pseudo radius remains constant.  An infinite number of subdivisions would result in true sphere, but since we can’t do that for lack of an infinite amount of time, we settle for three or four times, plenty to convey that it’s a sphere as long as we have smooth light shading.  For exact specs on possible starting solids, you should visit this site.  A simple example of doing this rendering is available below.

Wait, one more thing before we’re on to the code; the process I use here is recursive, and this is where the drift itself comes from.  It is possible to make an even more close to geodesic hull if you use an iterative process in one pass to produce the tessellations before punching it out to the pseudo-radius.  I haven’t implemented this, as recursive looks good enough to me, but it just occurred to me that you would only drift by one increment when tessellating in one pass instead of however deep your recursive process is.  That’s your homework assignment I guess.  😛

Now, without further ado, the code sample.

sphere.c:
#include
#include
#include
#include

#define rat_octahedron_solid_base 1
#define rat_icosahedron_solid_base 2

#define _A 0.525731112119133606f
#define _B 0.850650808352039932f

#ifndef MATH_PI
# ifndef M_PI
# define MATH_PI 3.14159f
# else
# define MATH_PI M_PI
# endif
#endif

static unsigned int octa_indices[8][3]=
{
{0,1,2},{0,2,3},
{0,3,4},{0,4,1},
{5,2,1},{5,3,2},
{5,4,3},{5,1,4}
};

static float octa_verts[6][3]=
{
{0,0,-1},{1,0,0},
{0,-1,0},{-1,0,0},
{0,1,0},{0,0,1}
};

static unsigned int icosa_indices[20][3]=
{
{0,4,1},{0,9,4},{9,5,4},{4,5,8},{4,8,1},
{8,10,1},{8,3,10},{5,3,8},{5,2,3},{2,7,3},
{7,10,3},{7,6,10},{7,11,6},{11,0,6},{0,1,6},
{6,1,10},{9,0,11},{9,11,2},{9,2,5},{7,2,11}
};

static float icosa_verts[12][3]=
{
{_A,0.0,-_B},{-_A,0.0,-_B},{_A,0.0,_B},{-_A,0.0,_B},
{0.0,-_B,-_A},{0.0,-_B,_A},{0.0,_B,-_A},{0.0,_B,_A},
{-_B,-_A,0.0},{_B,-_A,0.0},{-_B,_A,0.0},{_B,_A,0.0}
};

inline static void normalize_vert(float *a)
{
float d=sqrtf(a[0]*a[0]+a[1]*a[1]+a[2]*a[2]);
a[0]/=d; a[1]/=d; a[2]/=d;
}

static void draw_recursive_tri(float *a,float *b,float *c,unsigned int div,float r)
{
if (div==0)
{
glNormal3fv(a);
glVertex3f(a[0]*r,a[1]*r,a[2]*r);

glNormal3fv(b);
glVertex3f(b[0]*r,b[1]*r,b[2]*r);

glNormal3fv(c);
glVertex3f(c[0]*r,c[1]*r,c[2]*r);
}
else
{
register unsigned int i;
float ab[3],ac[3],bc[3];
for (i=0; i<3; i++) { ab[i]=(a[i]+b[i])/2.0f; ac[i]=(a[i]+c[i])/2.0f; bc[i]=(b[i]+c[i])/2.0f; } normalize_vert(ab); normalize_vert(ac); normalize_vert(bc); draw_recursive_tri(a,ab,ac,div-1,r); draw_recursive_tri(b,bc,ab,div-1,r); draw_recursive_tri(c,ac,bc,div-1,r); draw_recursive_tri(ab,bc,ac,div-1,r); } } void rat_draw_sphere(unsigned int detail,float radius,int solid_base) { register unsigned int i; switch (solid_base) { case rat_octahedron_solid_base: glBegin(GL_TRIANGLES); for (i=0; i<8; i++) draw_recursive_tri ( octa_verts[octa_indices[i][0]], octa_verts[octa_indices[i][1]], octa_verts[octa_indices[i][2]], detail,radius ); glEnd(); break; case rat_icosahedron_solid_base: glBegin(GL_TRIANGLES); for (i=0; i<20; i++) draw_recursive_tri ( icosa_verts[icosa_indices[i][0]], icosa_verts[icosa_indices[i][1]], icosa_verts[icosa_indices[i][2]], detail,radius ); glEnd(); break; default: break; }; }[/source]

Advertisement