Skip to main content
GameDev.net gamedev.net
🔒 Locked

Procedural sphere creation

Started by Hurp Jun 6, 2009 at 11:44 PM 14 replies 23.4k views
Original Post
Hurp
Hurp
This is a topic that has proven much aggravation to me over the years. I have been able to make discs, cylinders and more but I could never create a sphere procedurally. Part of the problem is that I have no clue what the math in these websites mean ( http://mathworld.wolfram.com/Sphere.html , http://local.wasp.uwa.edu.au/~pbourke/geometry/sphere/ and http://math.rice.edu/~pcmi/sphere/gos4.html). I have tried reading multiple threads on this forum, including http://www.gamedev.net/community/forums/topic.asp?topic_id=340439 and http://www.gamedev.net/community/forums/topic.asp?topic_id=535449 . The problem is, it makes absolutely no sense to me. Could anyone, please explain from start to finish on the math behind creating the verticies and indicies. I would greatly appreciate it. [Edited by - Hurp on June 9, 2009 12:26:54 AM]
Zakwayda
Zakwayda
Could you edit your post and make the links click-able using HTML tags? That'll make it easier for us to check them out (and to understand what you're having trouble with).

The two most common methods for generating a sphere mesh (IMX at least) are:

1. Generate the vertices using spherical coordinate conversions.

2. Generate the vertices by recursively subdividing a Platonic solid and then normalizing the vertices of the resulting mesh.

The former is quite a bit easier to implement than the latter, but the distribution of triangles is noticeably uneven. However, in many cases this won't be a problem (in fact, I think the GLU library uses this method to generate sphere meshes). The second method produces a more even distribution of triangles, but is less straightforward to implement.

In addition to making those links click-able, perhaps you could clarify which methods you've tried, and what sort of troubles you've run into.
gltiich
gltiich
R = 1.0
For J = 0, PI
For I = 0, 2*PI
X = R * Cos(I) * Sin(J)
Y = R * Sin(I) * Sin(J)
Z = R * Cos(J)
PLOT(X, Y, Z)
ma_hty
ma_hty
"... over the years ..."

Arr... I don't think it can be a problem in a scale of years. Anyway, it is just an easy task. Let me show you a simple way of doing it.

void drawsphere(){  #define PI 3.14159265358979323846f  int width = 32;  int height = 16;  float theta, phi, *dat;  int i, j, t, ntri, nvec, *idx;  nvec = (height-2)* width+2;  ntri = (height-2)*(width-1)*2;  dat = (float*) malloc( nvec * 3*sizeof(float) );  idx =   (int*) malloc( ntri * 3*sizeof(int)   );  for( t=0, j=1; j<height-1; j++ )  for(      i=0; i<width; i++ )  {    theta = float(j)/(height-1) * PI;    phi   = float(i)/(width-1 ) * PI*2;    dat[t++] =  sinf(theta) * cosf(phi);    dat[t++] =  cosf(theta);    dat[t++] = -sinf(theta) * sinf(phi);  }  dat[t++]=0; dat[t++]= 1; dat[t++]=0;  dat[t++]=0; dat[t++]=-1; dat[t++]=0;  for( t=0, j=0; j<height-3; j++ )  for(      i=0; i<width-1; i++ )  {    idx[t++] = (j  )*width + i  ;    idx[t++] = (j+1)*width + i+1;    idx[t++] = (j  )*width + i+1;    idx[t++] = (j  )*width + i  ;    idx[t++] = (j+1)*width + i  ;    idx[t++] = (j+1)*width + i+1;  }  for( i=0; i<width-1; i++ )  {    idx[t++] = (height-2)*width;    idx[t++] = i;    idx[t++] = i+1;    idx[t++] = (height-2)*width+1;    idx[t++] = (height-3)*width + i+1;    idx[t++] = (height-3)*width + i;  }  glEnableClientState(GL_VERTEX_ARRAY);  glEnableClientState(GL_NORMAL_ARRAY);  glVertexPointer(3,GL_FLOAT,0,dat);  glNormalPointer(GL_FLOAT,0,dat);  glDrawElements(GL_TRIANGLES, ntri*3, GL_UNSIGNED_INT, idx );  glDisableClientState(GL_VERTEX_ARRAY);  glDisableClientState(GL_NORMAL_ARRAY);  free(idx);  free(dat);}

The source code above, drawsphere(), draws an unit sphere. It prepares the necessary vertices first. And then, it prepares the indexes of the triangles. Lastly, it draws them using some OpenGL commands.

[Edited by - ma_hty on June 8, 2009 4:54:02 AM]
phresnel
phresnel
Hurp:

I try to be simplicisstic.

Look at a sine wave.

Look at a cosine wave.

See how they differ.

Q: What if you take the sine wave as an x_0 coordinate, and the cosine wave as an x_1 coordinate? (think about it first before you proceed to the answer)

{

A: You get a circle. More specifically, with the function P(alpha)=P(sin(alpha),cos(alpha)) you describe a circle when you iterate for alpha=0..2*pi.

This yields a 2-dimensional line. Stomach that for now.

}

To see the answer, mark the text between {}.
Hurp
Hurp
Quote:
Original post by jyk
Could you edit your post and make the links click-able using HTML tags? That'll make it easier for us to check them out (and to understand what you're having trouble with).

The two most common methods for generating a sphere mesh (IMX at least) are:

1. Generate the vertices using spherical coordinate conversions.

2. Generate the vertices by recursively subdividing a Platonic solid and then normalizing the vertices of the resulting mesh.

The former is quite a bit easier to implement than the latter, but the distribution of triangles is noticeably uneven. However, in many cases this won't be a problem (in fact, I think the GLU library uses this method to generate sphere meshes). The second method produces a more even distribution of triangles, but is less straightforward to implement.

In addition to making those links click-able, perhaps you could clarify which methods you've tried, and what sort of troubles you've run into.


I would be interested in learnin the second way, I understand it would be harder but if it i a more even distribution then I feel it would be better to learn in the long run.

Quote:
Original post by gltiich
R = 1.0
For J = 0, PI
For I = 0, 2*PI
X = R * Cos(I) * Sin(J)
Y = R * Sin(I) * Sin(J)
Z = R * Cos(J)
PLOT(X, Y, Z)


Why would I plot the points like that? What is the math behind it? How do I use those points and form multiple triangles?

Quote:
Original post by ma_hty
"... over the years ..."

Arr... I don't think it can be a problem in a scale of years. Anyway, it is just an easy task. Let me show you a simple way of doing it.

*** Source Snippet Removed ***
The source code above, drawsphere(), draws an unit sphere. It prepares the necessary vertices first. And then, it prepares the indexes of the triangles. Lastly, it draws them using some OpenGL commands.


While I understand some of the reasons for the name of those variables, is nvec number of triangles and ntri numer of triangles? If so, how did you come up with the reasoning behind those variables?

nvec = (height-2)* width+2;
ntri = (height-2)*(width-1)*2;
Quote:
Original post by phresnel
Hurp:

I try to be simplicisstic.

Look at a sine wave.

Look at a cosine wave.

See how they differ.


While that sort of makes sense, I do not see how triangles could be formed from that.
phresnel
phresnel
Quote:
Original post by Hurp
While that sort of makes sense, I do not see how triangles could be formed from that.


Let's get back to the 2d-case, where you would form lines instead of triangles. We both agree that for this kind of rendering we have to approximate/tesselate the perfect 2-sphere/circle.

Having the function P(alpha)=P(cos(alpha),sin(alpha)), you would iterate from 0 to 2pi with a given step-size:

const float radius = ...;for (angle=0.0f; angle<=2pi-step_size; angle+=step_size) {    const float a[2] = { radius*cosf(alpha), radius*sinf(alpha) };    const float b[2] = { radius*cosf(alpha+step_size), radius*sinf(alpha+step_size) };    drawLine (a,b);}


Now, consider a 3-sphere ("sphere" in common parlance :D) being a collection of 2-spheres, stacked up into 3d, and the radius for each stack being based again on trigonometric functions. That's also related to tesselating a cylinder.

This is only to stomach that for now. You can actually create a sphere by creating a cylinder, and change the radius for each height, but this gives the worst approximation I know. It's better to add an outer loop for 0 to pi (not 2pi this time), and describe a half-sphere like above, just to get proper height-values for each stack, and of course proper radiuses. Basically, that is what GLUT and DirectX utilities do.

(note that more and imho better tesselations exist, like creating a cube with many polygons, and then normalizing each vertex of it)
ma_hty
ma_hty
Arr... the reasoning...

That's obvious (to me). You can count the number of vertices and the number of triangles precisely. There are only two cases. They are the triangles touching the poles and the triangles not touching the poles. The source code is there already. I guarantee you it is 100% functional. So, please spend some time to read.

The only less obvious issue about the triangles is their winding. You have to make sure the winding of the triangles consistence with each others. Such that, the 3D model can work with culling correctly.

[Edited by - ma_hty on June 12, 2009 7:27:24 AM]
Hurp
Hurp
Quote:
Original post by ma_hty
Arr... the reasoning...

That's obvious (to me). You can count the number of vertices and the number of triangles precisely. There are only two cases. They are the triangles touching the poles and the triangles not touching the poles. The source code is there already. I grantee you it is 100% functional. So, please spend some time to read.

The only less obvious issue about the triangles is their winding. You have to make sure the winding of the triangles consistence with each others. Such that, the 3D model can work with culling correctly.


Alright, so I tried to read your code as much as I could and get it to work in DirectX. In my class I have the following variables to help with reading/building the buffers.

	unsigned int m_unNumberOfVerticies;	unsigned int m_unNumberOfTriangles;	unsigned int m_unNumberOfIndicies;


My actual sphere building code is this
	D3DVERTEXELEMENT9 dvVertexElements[] =	{		{0,  0, D3DDECLTYPE_FLOAT3, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_POSITION, 0},		D3DDECL_END()	};	lpD3Device->CreateVertexDeclaration(dvVertexElements, &m_VD);#define PI 3.14159265358979323846f	int width = 32;	int height = 16;	float theta, phi, *dat;	int i, j, t, ntri, nvec, *idx;	nvec = (height-2)* width+2;	ntri = (height-2)*(width-1)*2;	dat = (float*) malloc( nvec * 3*sizeof(float) );	idx =   (int*) malloc( ntri * 3*sizeof(int)   );	m_unNumberOfVerticies = nvec;	m_unNumberOfIndicies = ntri * 3;	m_unNumberOfTriangles = ntri;	for( t=0, j=1; j<height-1; j++ )		for(      i=0; i<width; i++ )		{			theta = float(j)/(height-1) * PI;			phi   = float(i)/(width-1 ) * PI*2;			dat[t++] =  sinf(theta) * cosf(phi);			dat[t++] =  cosf(theta);			dat[t++] = -sinf(theta) * sinf(phi);		}		dat[t++]=0; dat[t++]= 1; dat[t++]=0;		dat[t++]=0; dat[t++]=-1; dat[t++]=0;		for( t=0, j=0; j<height-3; j++ )			for(      i=0; i<width-1; i++ )			{				idx[t++] = (j  )*width + i  ;				idx[t++] = (j+1)*width + i+1;				idx[t++] = (j  )*width + i+1;				idx[t++] = (j  )*width + i  ;				idx[t++] = (j+1)*width + i  ;				idx[t++] = (j+1)*width + i+1;			}			for( i=0; i<width-1; i++ )			{				idx[t++] = (height-2)*width;				idx[t++] = i;				idx[t++] = i+1;				idx[t++] = (height-2)*width+1;				idx[t++] = (height-3)*width + i+1;				idx[t++] = (height-3)*width + i;			}			lpD3Device->CreateVertexBuffer(nvec*sizeof(float), 0, 0, D3DPOOL_DEFAULT, &m_VB, 0);			lpD3Device->CreateIndexBuffer(m_unNumberOfIndicies*sizeof(int),0, D3DFMT_INDEX16,  D3DPOOL_DEFAULT, &m_IB, 0);			void *buffer;			m_VB->Lock(0,0, &buffer, 0);			memcpy(buffer, dat, nvec* (sizeof(float) * 3));			m_VB->Unlock();			m_IB->Lock(0,0, &buffer, 0);			memcpy(buffer, idx, m_unNumberOfIndicies*sizeof(int));			m_IB->Unlock();


My rendering code ...
	lpD3DDevice->SetStreamSource(0, m_VB, 0, m_sizeof(float)*3);	lpD3DDevice->SetIndices(m_IB);									lpD3DDevice->SetVertexDeclaration(m_VD);	lpD3DDevice->DrawIndexedPrimitive(D3DPT_TRIANGLELIST, 0, 0, m_unNumberOfVerticies, 0, m_unNumberOfTriangles);


The problem is I get what seems to be only the top half of the sphere, with reverse culling. Do you have any idea why this is happening and how to fix it?
trunks14
trunks14
For what it's worth, I came across this problem a while ago. I made an OpenGL project to display a lit sphere which was first created in memory and then displayed. You may want to look there.

Disclaimers:
* Weird combination of C++ and C features.
* Includes lighting code for OpenGL, initialization and SDL stuff, for this reason a lot of code you may not be interested in is present, the good thing I guess is that there is an executable that demonstrates the created sphere. You may want to look at the CreateSphere function in main.cpp. (exe is in the Bin/Debug directory)
* Pointer math craziness!!!! BEWARE, sorry I could not think of a better way to create a sphere in memory (vertices + triangles structure) in my C mindset.
* The most complex code is the one that connects the vertices to actually form triangles..., the code to parametically generate the vertices is actually very trivial.


I could go on like this forever, I guess...I tried to comment it to a certain level of correctness and ease so that I could go back to it at a later time and either laugh at me or re-understand it and use for something else :)

Also, in main.cpp, there are defines:

#define STACKS 32
#define SLICES 32

So you can change those numbers :) If you know OpenGL you can do a little tweaking to display the vertices and the wireframe to better understand how the algorithm works. The minimum is 2 stacks and 3 slices if im not wrong... Actually if you change line 183 in main.cpp to:
glPolygonMode(GL_FRONT, GL_LINE);
You'll get the wireframe representation which makes a better job at telling you how the sphere was constructed:

From left to right, and down:
2 stacks 3 slices
8 stacks 8 slices
16 stacks 16 slices
32 stacks 32 slices



Link: Here! ~476 KB

To run the .exe you'll need SDL.dll, opengl32.dll and glu32.dll

[Edited by - trunks14 on June 12, 2009 12:09:09 AM]
ma_hty
ma_hty
Oh... Direct3D...

I had given it up for a few years already (since DirectX 8). I'm not quite sure whether I can help or not.


Anyway, at least, I should be able to provide some basic information.

Firstly,

lpD3Device->CreateIndexBuffer(m_unNumberOfIndicies*sizeof(int),0, D3DFMT_INDEX16, D3DPOOL_DEFAULT, &m_IB, 0);

This line is probably incorrect. D3DFMT_INDEX16 is probably two bytes integer. However, you copy to the buffer a block of 4 bytes integer later. You must be very unlucky. Otherwise, you should have noticed it because the program crashed during execution.


Secondly, the orientations of Direct3D and OpenGL are different. OpenGL is right-handed and Direct3D is left-handed. Also, the direction of the axis of Direct3D and OpenGL point towards different directions too. Therefore, when you converting a 3D mesh from OpenGL to Direct3D (vice versa), you need to explicitly reverse the winding in order to make culling to work correctly. Also, please pay some attention about the direction of the axis.

(Anyway, if the windings of a 3D model are consistent in the first place, there will be two cases only. You can try them both to see which one is correct simply.)

To reverse the winding, you can
  for( t=0, j=0; j<height-3; j++ )  for(      i=0; i<width-1; i++ )  {    idx[t++] = (j  )*width + i  ;    idx[t++] = (j+1)*width + i+1;  // switch this line with the following line    idx[t++] = (j  )*width + i+1;  // <<    idx[t++] = (j  )*width + i  ;    idx[t++] = (j+1)*width + i  ;  // switch this line with the following line    idx[t++] = (j+1)*width + i+1;  // <<  }  for( i=0; i<width-1; i++ )  {    idx[t++] = (height-2)*width;    idx[t++] = i;  // switch this line with the following line    idx[t++] = i+1;  // <<    idx[t++] = (height-2)*width+1;    idx[t++] = (height-3)*width + i+1;  // switch this line with the following line    idx[t++] = (height-3)*width + i;  // <<  }


[Edited by - ma_hty on June 12, 2009 8:47:52 AM]
ma_hty
ma_hty
By the way, please be careful about the memory management.

The memory you requested from the system using malloc() should be returned to the system by explicitly calling free(). If you didn't, the system will keep reserving that memory block for you. In the worst case, it can exhaust all memory available.

[Edited by - ma_hty on June 12, 2009 7:12:11 AM]
Hurp
Hurp
Quote:
Original post by ma_hty
lpD3Device->CreateIndexBuffer(m_unNumberOfIndicies*sizeof(int),0, D3DFMT_INDEX16, D3DPOOL_DEFAULT, &m_IB, 0);

This line is probably incorrect. D3DFMT_INDEX16 is probably two bytes integer. However, you copy to the buffer a block of 4 bytes integer later. You must be very unlucky. Otherwise, you should have noticed it because the program crashed during execution.



If not D3DFMT_INDEX16, then what else could it be?

Also, I tried your window order change and I still have the same issue. In fact, it looks the same.

http://img34.imageshack.us/img34/1073/brokenf.jpg
ma_hty
ma_hty
It is a problem that you cannot ignore. (@@... funny Hurp...)

By the way, it is easy to fix too. Just use D3DFMT_INDEX32.
ma_hty
ma_hty
lpD3Device->CreateVertexBuffer(nvec*sizeof(float), 0, 0, D3DPOOL_DEFAULT, &m_VB, 0); //<< wrong


lpD3Device->CreateVertexBuffer(nvec*3*sizeof(float), 0, 0, D3DPOOL_DEFAULT, &m_VB, 0);
Hurp
Hurp
Quote:
Original post by ma_hty
lpD3Device->CreateVertexBuffer(nvec*sizeof(float), 0, 0, D3DPOOL_DEFAULT, &m_VB, 0); //<< wrong


lpD3Device->CreateVertexBuffer(nvec*3*sizeof(float), 0, 0, D3DPOOL_DEFAULT, &m_VB, 0);


Ah, that did fix it. Thanks a lot. I have two last questions about the code.

1) If I wanted to have the size based off a radius, what would be the best approach? Would it be ..

theta = float(j)/(height-1) * (RADIUS * PI);
phi = float(i)/(width-1 ) * (RADIUS * PI*2);

2) What is "weight" and "height"? Is that stacks and slices?

Topic Locked

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

Sign in to reply to this topic.