🔒 Locked

Programatically create sphere

Started by brekehan May 19, 2009 at 7:22 AM 17 replies 11.4k views

Original Post

May 19, 2009 at 7:22 AM

Does anyone have an algorithm for creating the vertices for a sphere with a given a radius and another variable controlling how many triangles it is made of? How about texture coordinates to go along with those? My Google search is fairing well on this one. I can go in circles with sin and cos, but I'm not really sure how to actually make triangles with them, or how to get texture coords since I've never really understood spherical texture mapping.

Evil Steve

May 19, 2009 at 7:27 AM

Moving to Graphics Programming and Theory.

Have you tried Google? There seems to be a lot of reasonable results there - in particular, this and this (OpenGL, but the theory is the same as D3D).

KRIGSSVIN

May 19, 2009 at 1:53 PM

My code to generate sphere, everything is obvious nevertheless there are some my structs.

static void R_CreateSphere(lightShape_t *shape, float radius, int slices, int stacks) {	float		sinI[MAX_SHAPE_SEGMENTS], cosI[MAX_SHAPE_SEGMENTS];	float		sinJ[MAX_SHAPE_SEGMENTS], cosJ[MAX_SHAPE_SEGMENTS];	vec3_t		normal;	shadowVert_t	*vertex;	index_t		*index;	index_t		rowA, rowB;	int			i, j;	// validate parameters	radius = max(radius, 0.f);	slices = Q_clamp(slices, 2, MAX_SHAPE_SEGMENTS);	stacks = Q_clamp(stacks, 2, MAX_SHAPE_SEGMENTS);	// setup the shape	shape->numIndices = 6 * (stacks - 1) * slices;	shape->indices = R_StaticAlloc(shape->numIndices * sizeof(index_t));	shape->numVertices = (stacks - 1) * slices + 2;	shape->vertexBuffer = R_VB_Alloc(VBT_STATIC, shape->numVertices * sizeof(shadowVert_t));	// create sin/cos cache	for (i = 0; i < slices; i++)		Q_sincos(2.f * Q_PI * (float)i / (float)slices, &sinI, &cosI);	for (j = 0; j < stacks; j++)		Q_sincos(Q_PI * (float)j / (float)stacks, &sinJ[j], &cosJ[j]);	// generate vertices	vertex = R_VB_Map(shape->vertexBuffer, VBA_WRITE_ONLY);	// positive Z pole	vertex->xyz[0] = 0.f;	vertex->xyz[1] = 0.f;	vertex->xyz[2] = radius;	vertex++;	// stacks	for (j = 1; j < stacks; j++) {	        for (i = 0; i < slices; i++) {			normal[0] = sinI * sinJ[j];			normal[1] = cosI * sinJ[j];			normal[2] = cosJ[j];			vertex->xyz[0] = normal[0] * radius;			vertex->xyz[1] = normal[1] * radius;			vertex->xyz[2] = normal[2] * radius;			vertex++;		}	}	// negative Z pole	vertex->xyz[0] = 0.f;	vertex->xyz[1] = 0.f;	vertex->xyz[2] = -radius;	vertex++;	R_VB_Unmap(shape->vertexBuffer);	GL_BindVB(NULL);	// generate indices	index = shape->indices;	// positive Z pole	rowA = 0;	rowB = 1;	for(i = 0; i < slices - 1; i++) {		index[0] = rowA;		index[1] = rowB + i + 1;		index[2] = rowB + i;		index += 3;	}	index[0] = rowA;	index[1] = rowB;	index[2] = rowB + i;	index += 3;	// interior stacks	for (j = 1; j < stacks - 1; j++) {		rowA = 1 + (j - 1) * slices;		rowB = rowA + slices;		for (i = 0; i < slices - 1; i++) {			index[0] = rowA + i;			index[1] = rowA + i + 1;			index[2] = rowB + i;			index += 3;			index[0] = rowA + i + 1;			index[1] = rowB + i + 1;			index[2] = rowB + i;			index += 3;        	}		index[0] = rowA + i;		index[1] = rowA;		index[2] = rowB + i;		index += 3;		index[0] = rowA;		index[1] = rowB;		index[2] = rowB + i;		index += 3;	}	// negative Z pole	rowA = 1 + (stacks - 2) * slices;	rowB = rowA + slices;	for (i = 0; i < slices - 1; i++) {		index[0] = rowA + i;		index[1] = rowA + i + 1;		index[2] = rowB;		index += 3;	}	index[0] = rowA + i;	index[1] = rowA;	index[2] = rowB;}

mmakrzem

May 19, 2009 at 3:00 PM

I created four video tutorials that show how you can create a sphere programatically and also how to apply a texture over it. You can get the video's here: http://www.marek-knows.com/downloadSection.php?Topic=Physics&pg=1#Physics4

elenzil

May 20, 2009 at 4:35 PM

it's probably not what you're after,
but i have a simple demo showing non-realtime generation of a sphere with exactly N vertices here: http://elenzil.com/progs/separate
(essentially using a simple electrostatic repulsion method to relax an initial random distribution)
and a demo of efficiently uniformly distributing random points on a sphere here: http://elenzil.com/progs/randompoints

both include DirectX 9 source.

(sorry, new to the forum, not sure how to markup links yet)

brekehan

May 28, 2009 at 1:56 AM

Quote:
Original post by mmakrzem
I created four video tutorials that show how you can create a sphere programatically and also how to apply a texture over it. You can get the video's here: http://www.marek-knows.com/downloadSection.php?Topic=Physics&pg=1#Physics4

Site will not send an email to allow me to register in order to watch the video.

EDIT:
I finally got an email and logged in. Your website is so set up to make money.
The user is forced to watch videos in sequence and is only given a few free downloads. Before I am even able to get to the sphere video, which is the only one that interests me, I am told I need to purchase download slots.

Everyone has to make a buck, but I am not going to contribute to something that leaves such a sour taste in my mouth.

Maybe I'll try again in 4 days when I am allowed another free download from your site.

[Edited by - brekehan on May 28, 2009 2:56:38 AM]

brekehan

May 28, 2009 at 1:59 AM

Quote:
Original post by KRIGSSVIN
My code to generate sphere, everything is obvious nevertheless there are some my structs.

It isn't so obvious :(

I tired drawing on paper what is going on and I am failing to visualize it.
I tried stepping through the code and my first vertex ends up being (0, very close to 0, very close to 0)... like e-19 close.

I used a radius of 1, 4 stacks, 4 slices, in order to know what the trig valus should be.

I can't visualize the iteration of the vertices. Where is the first point supposed to be after you do a pole?

phresnel

May 28, 2009 at 2:13 AM

An easy algorithm with great results and without singularities at the poles is to create 6 planes, with normals to the left, right, top, bottom, front, back. You triangulate those planes, and then normalise all vertex positions, and finally multiply them by some radius. While still not a perfect mapping, it is also easy to texture that sphere with a cubemap.

brekehan

May 28, 2009 at 2:27 AM

Quote:
Original post by phresnel
An easy algorithm with better results and without singularities at the poles is to create 6 planes, with normals to the left, right, top, bottom, front, back. You triangulate those planes, and then normalise all vertex positions, and finally multiply them by some radius. While still not a perfect mapping, it is also easy to texture that sphere with a cubemap.

That sounds like a good idea.

I can probably use that for some spheres, but I have a special case where I need to generate my sphere to have particular triangles for proper texture mapping.

I want to end up with a sphere as I would if I created it in 3ds max.

This is built of rectangles, except for the stack next to the poles.
I imagine I can just split those rectangles into triangles if I can get an algorithm to get this far.

The reason I like this is that it makes texture mapping so easy. I can visualize the way the texture fits as if I took a knife and cut down the sphere from pole to pole on one side. It then unwraps to look like this:

So I can predict what my texture is going to look like as if I took a sheet of paper and wrapped it around a drinking glass. Of course there is some distortion near the poles because it is spherical, but I can still visualize it.

I am in fact trying to generate spheres in my engine in order to replace spheres that were exported from max as models for things like background, star field, planets, and moons. Each of those has multiple layers that are also spheres, so loading all these models from files seems silly, when I know my engine could do it instead.

EDIT:
I can easily see that sin and cos can be taken around the unit circle in the xz plane and the same for the yz plane. It is just a matter of using that to make the actual vertices. It's been a long time since trig class. I'll eventually get it if I draw enough pictures :P

KRIGSSVIN

May 28, 2009 at 2:46 AM

brekehan

This function gives you a sphere identical to 3DSMax one.
It consists of three parts: top cap, central part, and bottom cap.

Output is a triangle mesh, there are 3 indices per triangle.

Anyway, this is a sample from DXSDK adapted to my engine. They have normals there too.

brekehan

May 28, 2009 at 4:08 AM

Quote:
Original post by KRIGSSVIN
brekehan

This function gives you a sphere identical to 3DSMax one.
It consists of three parts: top cap, central part, and bottom cap.

Output is a triangle mesh, there are 3 indices per triangle.

Anyway, this is a sample from DXSDK adapted to my engine. They have normals there too.

I believe you, it probably works well and is exactly what I want. I am just trying to wrap my head around it. I never implement something I don't understand. I want to understand it.

Unfortuantly the March 2009 SDK doesn't seem to include the sample with sphere generation, that I can find. I do remember it being in an older SDK.

The part I am having trouble with is where you iterate through and make normals. I don't understand why you would multiply the sin you got from a circle in the xy plane by the sin you got from a circle in the xz plane. sin(a) * sin(b)... I am probably forgetting some trigonomic identity you are using.

I don't follow your process, or what you would have written in psuedocode before you implemented it. I see the code, I just don't know the algorithm.

KRIGSSVIN

May 28, 2009 at 8:37 AM

Quote:
I never implement something I don't understand. I want to understand it.

I personally don't see anything difficult about it, so nevermind if I tell you something is obvious to me, that's not obvious to you.

Look here:

	// Stacks counter represents range (0; 180) degrees of rotation around X axis.	// Start from 1 because we've already set positive Z pole.	for (j = 1; j < stacks; j++) {		// sin() range is (0; 1), this is the fraction of circle (see below) distance to use		stackDist = sinJ[j];		// cos() range is (1; -1), this is the height above XY plane		stackHeight = cosJ[j];		// Slices counter represents range (0; 360) degrees of rotation around Z axis, i.e. we draw circle lying on XY plane.	        for (i = 0; i < slices; i++) {			// Circle point position.			circleX = sinI;			circleY = cosI;			// Now smack them together.			// Unit position in sphere space and also the normal vector.			normal[0] = circleX * stackDist;			normal[1] = circleY * stackDist;			normal[2] = stackHeight;			vertex->xyz[0] = normal[0] * radius;			vertex->xyz[1] = normal[1] * radius;			vertex->xyz[2] = normal[2] * radius;			vertex++;		}	}

Take a look at the picture also:
http://img505.imageshack.us/img505/7188/69374605.jpg

brekehan

May 28, 2009 at 2:33 PM

Quote:
Original post by KRIGSSVIN
I personally don't see anything difficult about it, so nevermind if I tell you something is obvious to me, that's not obvious to you.

Look here:

	// Stacks counter represents range (0; 180) degrees of rotation around X axis.	// Start from 1 because we've already set positive Z pole.	for (j = 1; j < stacks; j++) {		// sin() range is (0; 1), this is the fraction of circle (see below) distance to use		stackDist = sinJ[j];		// cos() range is (1; -1), this is the height above XY plane		stackHeight = cosJ[j];		// Slices counter represents range (0; 360) degrees of rotation around Z axis, i.e. we draw circle lying on XY plane.	        for (i = 0; i < slices; i++) {			// Circle point position.			circleX = sinI;			circleY = cosI;			// Now smack them together.			// Unit position in sphere space and also the normal vector.			normal[0] = circleX * stackDist;			normal[1] = circleY * stackDist;			normal[2] = stackHeight;			vertex->xyz[0] = normal[0] * radius;			vertex->xyz[1] = normal[1] * radius;			vertex->xyz[2] = normal[2] * radius;			vertex++;		}	}

Take a look at the picture also:
http://img505.imageshack.us/img505/7188/69374605.jpg[/quote]

Ok, I tried to translate what you are doing in such a manner that it made sense to me. Here is the code I came up with.

void GenerateSphere(std::vector<Vertex> & vertices, float radius, unsigned stacks, unsigned slices){   vertices.clear();   // Get sin and cos around the unit circle in the xz plane   std::vector<double> xz_sin,                       xz_cos;	for(unsigned xz = 0; xz < slices; ++xz)   {      double angle = 2.0 * D3DX_PI * static_cast<double>(xz) / static_cast<double>(slices);      xz_sin.push_back(sin(angle));      xz_cos.push_back(cos(angle));   }   // Get sin and cos around half the unit circle in the yz plane   std::vector<double> yz_sin,                       yz_cos;   for(unsigned yz = 0; yz < stacks; ++yz)   {      double angle = D3DX_PI * static_cast<double>(yz) / static_cast<double>(stacks);      yz_sin.push_back(sin(angle));      yz_cos.push_back(cos(angle));   }   // Generate vertex data   Vertex poleBack;   poleBack.x = 0.0f;   poleBack.y = 0.0f;   poleBack.z = radius;   vertices.push_back(poleBack);   // Stacks counter represents range (0 to 180) degrees of rotation around X axis in the YZ plane	// Start from 1 because we've already created the positive Z pole   for(unsigned yz = 1; yz < stacks; ++yz)   {      double yz_y = yz_sin[yz]; // This is the distance along the Y axis of a point on the circle in the YZ plane 		double yz_z = yz_cos[yz]; // This is the distance along the Z axis of a point on the circle in the YZ plane      // Slices counter represents range (0 to 360) degrees of rotation around Z axis in the XY plane      for(unsigned xz = 0; xz < slices; ++xz)      {         double xz_z = xz_sin[xz]; // This is the distance along the Z axis of a point on the circle in the XZ plane 		   double xz_x = xz_cos[xz]; // This is the distance along the X axis of a point on the circle in the XZ plane         Vertex normal;         normal.x = xz_z * yz_y;  // Point on the circle in the XZ plane * distance         normal.y = xz_x * yz_y;         normal.z = yz_z;         Vertex vertex;         vertex.x = normal.x * radius;         vertex.y = normal.y * radius;         vertex.z = normal.z * radius;         vertices.push_back(vertex);      }   }   Vertex poleFront;   poleFront.x = 0.0f;   poleFront.y = 0.0f;   poleFront.z = -radius;   vertices.push_back(poleFront);}

Am I translating anything incorrectly?

Let's do an example with 4 slices and 4 stacks, radius of 1.0
When I step through with the debugger:
1) vertex 0 is a pole at the back of the sphere, sitting at z = 1
2) vertices 1 to 4 should be 4 points on a circle in the xy plane rotated around the z axis? It's depth is ~ 0.707 and it appears to start at the top of the circle and go around clockwise?

3) vertices 5 to 8 should be 4 points on a circle in the xy plane roated around the z axis. It's depth is 0 and it appears to start at the top of the circle and go around clockwise.

4) vertices 9 to 12 should be 4 points on a circle in the xy plane rotated around the z axis. It's depth is ~ -0.707 and it appears to start at the top of the circle and go around clockwise.

5) Finish with vertex 13, which is the negative Z pole, sitting at z = -1

Is that all correct?

simotix

May 29, 2009 at 12:02 AM

Quote:
Original post by KRIGSSVIN
My code to generate sphere, everything is obvious nevertheless there are some my structs.

....

There is several things in this code that I do not understand.

What does all of this do?

	// create sin/cos cache	for (i = 0; i < slices; i++)		Q_sincos(2.f * Q_PI * (float)i / (float)slices, &sinI, &cosI);	for (j = 0; j < stacks; j++)		Q_sincos(Q_PI * (float)j / (float)stacks, &sinJ[j], &cosJ[j]);	// generate vertices	vertex = R_VB_Map(shape->vertexBuffer, VBA_WRITE_ONLY);

I think I have an idea, but I do not see sinI, sinJ or cosJ ever definited, and I have no clue was q_sincos means. Could you explain?

paul_nicholls

May 29, 2009 at 12:27 AM

Quote:
Original post by simotix
Quote:
Original post by KRIGSSVIN
My code to generate sphere, everything is obvious nevertheless there are some my structs.

....

There is several things in this code that I do not understand.

What does all of this do?
	// create sin/cos cache	for (i = 0; i < slices; i++)		Q_sincos(2.f * Q_PI * (float)i / (float)slices, &sinI, &cosI);	for (j = 0; j < stacks; j++)		Q_sincos(Q_PI * (float)j / (float)stacks, &sinJ[j], &cosJ[j]);	// generate vertices	vertex = R_VB_Map(shape->vertexBuffer, VBA_WRITE_ONLY);
I think I have an idea, but I do not see sinI, sinJ or cosJ ever definited, and I have no clue was q_sincos means. Could you explain?

Hi simotix,
If you look at the code further up, the definitions for sinI, SinJ, etc. are at the top of the code that was posted.

static void R_CreateSphere(lightShape_t *shape, float radius, int slices, int stacks) {	float		sinI[MAX_SHAPE_SEGMENTS], cosI[MAX_SHAPE_SEGMENTS];	float		sinJ[MAX_SHAPE_SEGMENTS], cosJ[MAX_SHAPE_SEGMENTS];	vec3_t		normal;	shadowVert_t	*vertex;	index_t		*index;	index_t		rowA, rowB;	int			i, j;

I can guess that the routine q_sincos takes the input angle (radians) and returns the sin and cose of that angle into the last two params...

I hope this helps :)
cheers,
Paul

Evil Steve

May 29, 2009 at 3:02 AM

Quote:
Original post by mmakrzem
I created four video tutorials that show how you can create a sphere programatically and also how to apply a texture over it. You can get the video's here: http://www.marek-knows.com/downloadSection.php?Topic=Physics&pg=1#Physics4

It'd be nice if you could mention that you still have to pay to view the videos after signing up. Or at least mention that on the site...

brekehan

May 29, 2009 at 3:06 AM

Here is my translated function from the one Krigssvin posted:
So now, what to do about texture coords?

//------------------------------------------------------------------------------void GenerateSphere(std::vector<Vertex> & vertices, float radius, unsigned stacks, unsigned slices){   // Start with an empty vector   vertices.clear();   // Get sin and cos around the unit circle in the xz plane   std::vector<double> xz_sin,                       xz_cos;   for(unsigned xz = 0; xz < slices; ++xz)   {      double angle = 2.0 * D3DX_PI * static_cast<double>(xz) / static_cast<double>(slices);      xz_sin.push_back(sin(angle));      xz_cos.push_back(cos(angle));   }   // Get sin and cos around half the unit circle in the yz plane   std::vector<double> yz_sin,                       yz_cos;   for(unsigned yz = 0; yz < stacks; ++yz)   {      double angle = D3DX_PI * static_cast<double>(yz) / static_cast<double>(stacks);      yz_sin.push_back(sin(angle));      yz_cos.push_back(cos(angle));   }   // Generate vertex data   std::vector<Vertex> unorderedVertices;   Vertex poleBack;   poleBack.x = 0.0f;   poleBack.y = 0.0f;   poleBack.z = radius;   unorderedVertices.push_back(poleBack);   // Stacks counter represents range (0 to 180) degrees of rotation around X axis in the YZ plane   // Start from 1 because we've already created the positive Z pole   for(unsigned yz = 1; yz < stacks; ++yz)   {      double yz_y = yz_sin[yz]; // This is the distance along the Y axis of a point on the circle in the YZ plane       double yz_z = yz_cos[yz]; // This is the distance along the Z axis of a point on the circle in the YZ plane      // Slices counter represents range (0 to 360) degrees of rotation around Z axis in the XY plane      // So, these vertices form circles in the XY plane going from pos Z to neg Z      // Each circle starts at the top and goes around clockwise      for(unsigned xz = 0; xz < slices; ++xz)      {         double xz_z = xz_sin[xz]; // This is the distance along the Z axis of a point on the circle in the XZ plane          double xz_x = xz_cos[xz]; // This is the distance along the X axis of a point on the circle in the XZ plane         Vertex normal;         normal.x = static_cast<float>(xz_z * yz_y);  // Point on the circle in the XZ plane * distance         normal.y = static_cast<float>(xz_x * yz_y);         normal.z = static_cast<float>(yz_z);         Vertex vertex;         vertex.x = normal.x * radius;         vertex.y = normal.y * radius;         vertex.z = normal.z * radius;         unorderedVertices.push_back(vertex);      }   }   Vertex poleFront;   poleFront.x = 0.0f;   poleFront.y = 0.0f;   poleFront.z = -radius;   vertices.push_back(poleFront);   // At this point we have:   //   // The positive Z pole at the first vertex   // The negative Z pole at the last vertex   // Starting at vertex 1, points along a circle in the XY plane. The circle contains a number of points equal to slices   // A number of those circles, coming from pos Z to neg Z, equal to the number of stacks.   // Generate indices   std::vector<unsigned> indices;	// Positive Z Cap   unsigned rowA = 0;   unsigned rowB = 1;   unsigned i;   for(i = 0; i < slices - 1; ++i)   {      indices.push_back(rowA);      indices.push_back(rowB + i + 1);      indices.push_back(rowB + i);	}   indices.push_back(rowA);   indices.push_back(rowB);   indices.push_back(rowB + i);   // Between caps   unsigned j;   for(j = 1; j < stacks - 1; j++)   {      rowA = 1 + (j - 1) * slices;      rowB = rowA + slices;      for(i = 0; i < slices - 1; i++)      {         indices.push_back(rowA + i);         indices.push_back(rowA + i + 1);         indices.push_back(rowB + i);         indices.push_back(rowA + i + 1);         indices.push_back(rowB + i + 1);         indices.push_back(rowB + i);      }      indices.push_back(rowA + i);      indices.push_back(rowA);      indices.push_back(rowB + i);      indices.push_back(rowA);      indices.push_back(rowB);      indices.push_back(rowB + i);   }   // Order the vertices according to the indices   for(std::vector<unsigned>::iterator it = indices.begin(); it != indices.end(); it++)   {      vertices.push_back(unorderedVertices[*it]);   }}

phresnel

May 29, 2009 at 3:34 AM

Quote:
Original post by Evil Steve
Quote:
Original post by mmakrzem
I created four video tutorials that show how you can create a sphere programatically and also how to apply a texture over it. You can get the video's here: http://www.marek-knows.com/downloadSection.php?Topic=Physics&pg=1#Physics4
It'd be nice if you could mention that you still have to pay to view the videos after signing up. Or at least mention that on the site...

I guess this is how he keeps a living. But I doubt my own guess :S

KRIGSSVIN

May 29, 2009 at 5:59 AM

brekehan,

Quote:

When I step through with the debugger:
1) vertex 0 is a pole at the back of the sphere, sitting at z = 1
2) vertices 1 to 4 should be 4 points on a circle in the xy plane rotated around the z axis? It's depth is ~ 0.707 and it appears to start at the top of the circle and go around clockwise?

3) vertices 5 to 8 should be 4 points on a circle in the xy plane roated around the z axis. It's depth is 0 and it appears to start at the top of the circle and go around clockwise.

4) vertices 9 to 12 should be 4 points on a circle in the xy plane rotated around the z axis. It's depth is ~ -0.707 and it appears to start at the top of the circle and go around clockwise.

5) Finish with vertex 13, which is the negative Z pole, sitting at z = -1

Everything is brilliant!

Q_sincos() takes radian angle input and outputs its sine and cosine.

In sin[IJ]/cos[IJ] we cache function values of angles mapped in a manner (0; 180)=(0; stacks) and (0; 360)=(0; slices).

About texture coordinates... there are many ways. Look at 3DSMax techniques, for example, and google them. I didn't go deep into it because I need spheres only for light shapes in my deferred renderer.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.