Random Asteroid Generation

I would do it by generating a spheroid sort-of-shape, then deforming the vertices randomly.

Chapter 2 of the OpenGL Redbook has a good description of generating an icosahedron and subdividing to make a better sphere approximation. There's all sorts of ways of randomising the vertices from a basic iterate-over-the-vertices-and-move-them-a-bit approach to a higher-quality solution like using Perlin noise.

Another idea is to define a function that is distance to a point P plus 3D Perlin noise, pick a threshold and use marching cubes to convert that into a mesh.

I've recently written an asteroid generator for my project. I started out by creating a tessellated cube. Then, each point is normalized in distance from the center: this creates a pretty smooth sphere. To generate a rough surface, I don't normalize to the exact radius, but by radius + some random value. The asteroids can also be squashed into ellpsoids.

In my asteroids, I want realistic craters and such, so I am going to move on to using heightmaps instead of random numbers. I already have the cube texture mapped, it would be easy when generating the 6 faces of the cube, to lookup the height from a map. If each face of the cube (before squashing into a sphere) is 64 by 64 quads, they you can get a reasonably high poly asteroid (64*64*6 faces = 24k faces) from a small map. I know this isn't random, but from there you can move on to generating the heightmap texture randomly: filtered noise for the rough shape, then render a few blended sprites on top of it (sprites of heightmap craters/scratches/etc ). and... we've got a random asteroid.

Another reason I advocate the 'deformed cube' approach to modeling objects, is level-of-detail becomes very easy. That 64x64 quad of an asteroid, if the geometry is derived from a heightmap, is easy to mipmap into a 32x32, 16x16 etc version all the way down to 2x2. Just keep an alternate version of the object in your index buffer (reusing the same vertices of course). Also, since the original geometry is a cube, texture mapping is very easy, 1 square texture per face. (Though for things like an asteroid, its much more efficient to put all 6 square faces inside of one texture atlas, so you don't have to bind the texture once per face.)

Does anyone have an example of code to share? Or at least the skeleton of the code?

I do plan on putting my code up on github. I thought I was far from doing that, but if there's interest I can put my 'dirty' code up early. I have a video of the asteroid here (it is a couple months old; I will try to make a new video tonight

Since then I've improved texture mapping, and far-away asteroids are rendered as sprites. I've also done a lot of work on the 'indoors' mode of the engine, and lighting, which isn't known in that video.)

My current 'engine' has 3 high-level graphics primitives:

-Sprites
-Meshes (Implemented as a VBO. A large mesh can be split across VBOs, and many small meshes can share one VBO.)
-Patches

Patches are the interesting one that I am working with, and I use these to build asteroids. A patch is a collection of vertices arranged in a rectangular array to form a 'sheet' of triangles. The patch itself isn't required to be on a plane. Each vertex can be placed independently, it just specifies the connectivity between vertices. And not every vertex needs to be defined; the patch can have holes in it. The patch itself can be rendered at different levels of detail; from a single quad to full quality. Each patch also contains Edges, which is just a list of vertices. Two patches can be 'sewn' together by connecting the edges. The asteroid is really just a cube; but instead of connecting the edges of 6 quads, I connect the edges of 6 patches.

Thanks for the suggestions guys, I decided to make the game 2 dimensional. My solution was to use trig to draw a circle then after each vertex is defined (the variable numberPoints can change the number of vertices, which right now is 32) I added a random number between 1 and 10 to get the effect. The asteroids look great now, other than the fact that I don't know how to texture it (Using GL_POLYGON).

A very simple way to do it would be to assign texture coordinates according to the asteroid vertices' x,y positions, transformed into u,v space:
[attachment=4800:asteroid_texcoords.JPG]
So if an asteroid's vertices are in the range [-5, 5], you can just calculate it's texture coordinates as:

u = x + 5 / 10
v = y + 5 / 10

A very simple way to do it would be to assign texture coordinates according to the asteroid vertices' x,y positions, transformed into u,v space:
[attachment=4800:asteroid_texcoords.JPG]
So if an asteroid's vertices are in the range [-5, 5], you can just calculate it's texture coordinates as:

u = x + 5 / 10
v = y + 5 / 10

I'm a little confused on what you mean by range, like the random coordinate assigned's range? It's a range from 0 to 10, so would it be u = x + 0 / 10, equaling 0?
I tried using just the vertex.x and vertex.y values (vertex is a sf::Vector2f), but I'm only getting an X over the asteroid of the texture and the rest is just different shades of brown from the texture... I'm confused xD.

[quote name='johnchapman' timestamp='1312742591' post='4845855']
A very simple way to do it would be to assign texture coordinates according to the asteroid vertices' x,y positions, transformed into u,v space:
[attachment=4800:asteroid_texcoords.JPG]
So if an asteroid's vertices are in the range [-5, 5], you can just calculate it's texture coordinates as:

u = x + 5 / 10
v = y + 5 / 10

I'm a little confused on what you mean by range, like the random coordinate assigned's range? It's a range from 0 to 10, so would it be u = x + 0 / 10, equaling 0?
[/quote]

Basically you want to map the minimum x,y coordinates to (0,0) the maximum x,y coordinates to (1,1) to generate texture coordinates for the asteroid vertices.

[quote name='KeyGames' timestamp='1312742972' post='4845856']
[quote name='johnchapman' timestamp='1312742591' post='4845855']
A very simple way to do it would be to assign texture coordinates according to the asteroid vertices' x,y positions, transformed into u,v space:
[attachment=4800:asteroid_texcoords.JPG]
So if an asteroid's vertices are in the range [-5, 5], you can just calculate it's texture coordinates as:

u = x + 5 / 10
v = y + 5 / 10

I'm a little confused on what you mean by range, like the random coordinate assigned's range? It's a range from 0 to 10, so would it be u = x + 0 / 10, equaling 0?
[/quote]

Basically you want to map the minimum x,y coordinates to (0,0) the maximum x,y coordinates to (1,1) to generate texture coordinates for the asteroid vertices.
[/quote]

For the U and V equations, what are the x and y? The random number generated by itself or the vertex with the random number generated added on? Sorry for all the questions I'm new to this. Also what would the rendering code look like? Just glTexCoord2d(texCoords.x texCoords.y);

For the U and V equations, what are the x and y? The random number generated by itself or the vertex with the random number generated added on? Sorry for all the questions I'm new to this. Also what would the rendering code look like? Just glTexCoord2d(texCoords.x texCoords.y);

Ahh, sorry - x and y are the positions of vertices, with the random number added. Although since you say 'added' I'm not entirely sure how you're generating the asteroids; I'd assumed you were doing something like this:

for each asteroid {
	for (i = 0; i < n_vertices; ++i) {
	//	generate vertex on circle:
		theta = 2pi * (i / n_vertices);
		asteroid.vertex.position.x = cos(theta);
		asteroid.vertex.position.y = sin(theta);
		
	//	randomly move vertex out from asteroid centre:
		asteroid.vertex.position.x *= random(min_size, max_size);
		asteroid.vertex.position.y *= random(min_size, max_size);
	}
}

Which would create a 'randomized' circle around (0, 0) in the range [-max_size, +max_size]. To generate the texture coordinates for each vertex you'd do:

asteroid.vertex.texcoord.x = asteroid.vertex.position.x + max_size / (max_size * 2);
asteroid.vertex.texcoord.y = asteroid.vertex.position.y + max_size / (max_size * 2);

Which just maps the vertex positions into the range [(0,0), (1,1)]. (0,0) is the bottom left of the texture, (1,1) is the top right.

As for rendering you'd just specify the texture coordinates along with your vertices, in immediate mode:

	
glBegin(GL_POLYGON);
		glVertex2f(asteroid vertex x,y);
		glTexCoord2f(asteroid texcoord u,v);
glEnd();

It's still not working right. I'll post my generation code and rendering code.

Generation:


int numberPoints = 32;
for(int i = 0; i < 360; i += 360 / numberPoints) {
float degreesRadians = float(i * (3.14159 / 180));
sf::Vector2f vertex;
vertex.x = cos(degreesRadians) * 50 + std::rand() % 10;
vertex.y = sin(degreesRadians) * 50 + std::rand() % 10;
mVertices.push_back(vertex);
sf::Vector2f texCoord;
texCoord.x = (vertex.x + 10) / 20;
texCoord.y = (vertex.y + 10) / 20;
mTexCoords.push_back(texCoord);
}





void Asteroid::Render() {
glTranslatef(mPosition.x, mPosition.y, 0.0f);
glRotatef(mRotation, 0.0f, 0.0f, 1.0f); // rotate on the Z axis for 2D view
glEnable(GL_TEXTURE_2D);
mAsteroidTexture.Bind();
glBegin(GL_POLYGON);
for(unsigned int i = 0; i < mVertices.size(); i++) {
glVertex2f(mVertices.x, mVertices.y);
glTexCoord2f(mTexCoords.x, mTexCoords.y);
}
glEnd();
glDisable(GL_TEXTURE_2D);
}



Could you help me fix it please? Also mAsteroidTexture is an sf::Image and SFML provides a texture binding function optimized for 2D.

Okay. I had a good look at your code, and I don't think it's doing what you think it's doing

First of all, you're not adding a random number in the range [1, 10], you're adding a number in the range [0, 9] using
std::rand() % 10

Generating your random number like this is dependant on the value of RAND_MAX which itself is library dependant, so relying on it is not portable (although it's probably 32767 in most cases). A better way would be to write a random function that is independant of RAND_MAX that will return floats in an arbitrary range:

float random(float min, float max) {
return (float(std::rand()) / float(RAND_MAX)) * (max - min) + min;
}

Second of all, adding random offsets to the vertices doesn't really work; it only seems to work in your function because you scale the positions by 50 first, so the random offset is comparatively small. If you wanted to make smaller asteroids (or use bigger offsets), your asteroid polygon would end up a mess like this:
[attachment=4809:bad_poly.JPG]
This is because by just adding offsets to the vertices you're allowing the vertices to 'cross over'. Worse still, if the offset is much bigger than the scale then the polgon gets completely displaced.

A much more reliable way to do it would be to generate a unit (radius = 1) circle, then scale the vertices to move them randomly out from (or in toward) the centre:
[attachment=4810:good_poly.JPG]

The code to do this is basically what I posted previously.

As for texture coordinates, you weren't generating them correctly; the range of your vertex positions is [-59, 59], not [-10, 10].

Note that you might get some interpolation artifacts showing up in your texture coordinates (see picture below); this is due to the way OpenGL splits up your polygon into triangles before rasterizing it. To eliminate this you could do something like use a triangle strip around a central vertex.
[attachment=4811:interpolation_artifacts.JPG]
Anyway, hope all this helps.

I got it working! As you can see it's still triangulated because I'm using glBegin(GL_TRIANGLE_FAN) around the center point. Is there a way to eliminate that or is it just something I'll have to deal with because of it being randomly generated? I'm happy for the most part with it! Thanks for all your help.

Since you are doing it in 2D, have you thought about generating your asteroids as texture images rather than as geometry? You can use Perlin noise to perturb a fuzzy disk, generate a bump map, and multiply it by a color map, then draw it as a single quad. Very quickly I did a couple to demonstrate:




By doing it this way, you can also encode a certain amount of shape information into the texture via the bump map, to give the asteroid more form than just a flat polygon mapped with a generic texture.

Since you are doing it in 2D, have you thought about generating your asteroids as texture images rather than as geometry? You can use Perlin noise to perturb a fuzzy disk, generate a bump map, and multiply it by a color map, then draw it as a single quad. Very quickly I did a couple to demonstrate:




By doing it this way, you can also encode a certain amount of shape information into the texture via the bump map, to give the asteroid more form than just a flat polygon mapped with a generic texture.

Well, I'm not that good at programming yet, so without any help I am lost completely on how to do this... any code samples I could see to get an idea how this is done?

To generate the above the procedure I used was as follows. (The code given here is in Lua, since that is my language of choice for this kind of stuff, but it should be fairly readable)

The basic shape of an asteroid is provided by a fuzzy disk function, that generates a circle of a specified radius where coordinate locations at the center of the circle evaluate to 1.0 and locations at the edge and beyond evaluate to 0.0.

[source]

function fuzzy_disk(x,y,radius)
local dist = math.sqrt( x*x + y*y)
local value = (radius - dist) / radius

if value<0 then value = 0 end
if value>1 then value = 1 end

return value
end
[/source]

This centers the circle at (0,0) so in order to map the circle to a buffer or texture you would map the region (-radius, -radius)->(radius, radius). So, imagining that the radius is equal to 1, then:

[source]
for x=0,ImageWidth-1,1 do
for y=0,ImageHeight-1,1 do
local nx = x / ImageWidth
local ny = y / ImageHeight

local value = fuzzy_disk(nx, ny)
Image:SetValue(x, y, value)
end
end
[/source]

This results in something like this:




To make it interesting, I used what is called Perlin noise. (Self-pimpage: See the link in my signature for my own personal noise library). Perlin noise is a type of function that generates a seemingly random number for a given input coordinate location. This value is continuously random and is frequently used for things such as landscape generation. One very handy use for Perlin noise is to effect a domain turbulence effect, where the actual input coordinates passed to a certain function (in this case the fuzzy_disk function) are modified first by the output of a set of Perlin noise functions. It looks like this:

[source]
F1 = 2D Perlin noise function or fractal
F2 = 2D Perline noise function or fractal (with different seed or offset, to generate different pattern than F1)

function perturbed_fuzzy_disk(x,y,radius)
local nx = x + F1:getValue(x,y)
local ny = y + F2:getValue(x,y)

return fuzzy_disk(nx,ny,radius)
end
[/source]

This function calls fuzzy_disk with the input coordinates, but before it does so it modifies them using the output of a pair of fractals. This has an effect on the fuzzy disk such that mapping it now will produce something that looks like this:




(Note, given that perturbing the image in this fashion can push the disk beyond the boundaries of its basic radius, I decreased the radius to 0.75, hence why it is smaller than the un-perturbed version).

Now, given a 2D array of values, as generated by the mapping function, you can generate a bump map of the function that makes it look as if it is being lit by a light. The function to do this is something like:

[source]

function bump_map(buf, light, spacing)
light=normalize(light)

local w,h = buf:width(), buf:height()
local bmp=CArray2Dd(w,h)

local x,y
for x=0,w-1,1 do
for y=0,h-1,1 do
-- Calculate x1,y1, x2,y2
local x1,y1,x2,y2 = x-1, y-1, x+1, y+1
if x1<0 then x1=0 end
if y1<0 then y1=0 end
if x2>w-1 then x2=w-1 end
if y2>h-1 then y2=h-1 end

local nx=(buf:get(x1,y) - buf:get(x2,y)) / (spacing/4)
local ny=1
local nz=(buf:get(x,y1) - buf:get(x,y2)) / (spacing/4)

local vec=normalize({nx,ny,nz})

local dot=vec[1]*light[1] + vec[2]*light[2] + vec[3]*light[3]
if dot<0 then dot=0 end
if dot>1 then dot=1 end
bmp:set(x,y,dot)
end
end
return bmp
end

[/source]

So now we can feed the mapped buffer from perturbed_fuzzy_disk to the bump-map function to generate a bump map, which ends up looking something like this:




That looks a little conical or pointy in shape, so we can apply Perlin's bias function to the output of he function, to push the values toward the high end of the range:

[source]

function bias(t, bias)
{
return math.pow(t, math.log(bias)/math.log(0.5));
}

[/source]

Using a bias value of 0.75, the result is this:




It's a bit rounder in appearance, so it should work.

From here, it is a simple matter of multiplying this bump map by a color map. Iterate the color map and bump map, and scale the RGB value of each pixel by the value from the bump map:




To finish it off, I applied a bias of 0.99 to the output of the perturbed_fuzzy_disk function and used that as the alpha channel:




And the result is an asteroid sprite that you can use, with alpha-blending.

(Can you tell that procedural generation of stuff is my favorite subject? )

Thank you so much for the answers! The LUA was easily readable. I'm having a problem implementing the Fuzzy Disk because it's only showing 1/4th of it and dividing it by the image height and width isn't working out well either... Below, the radius is set to 50 so that it's half of the image size (100).



mImage.Create(100, 100);
for(int x = 0; x < mImage.GetWidth(); x++) {
for(int y = 0; y < mImage.GetHeight(); y++) {
float nx = x;
float ny = y;
float value = FuzzyDisk(nx, ny, 50);
mImage.SetPixel(nx, ny, sf::Color(value * 255, value * 255, value * 255));
}
}




float Asteroid::FuzzyDisk(float x, float y, float radius) {
float distance = std::sqrt(x * x + y * y);
float value = (radius - distance) / radius;

if(value < 0)
value = 0;
else if(value > 1)
value = 1;

return value;
}


This code doesn't work but I'm just showing how I'm mapping it with SFML.


void Asteroid::Render(sf::RenderWindow* window) {
glEnable(GL_TEXTURE_2D);
mImage.Bind();
glBegin(GL_QUADS);
glTexCoord2f(0.0f, 1.0f);
glVertex2f(0.0f, 0.0f);

glTexCoord2f(1.0f, 1.0f);
glVertex2f(100.0f, 0.0f);

glTexCoord2f(1.0f, 0.0f);
glVertex2f(100.0f, 100.0f);

glTexCoord2f(0.0f, 0.0f);
glVertex2f(0.0f, 100.0f); glEnd();
glDisable(GL_TEXTURE_2D);
}


It only shows part of the disk because I made an error. The center of the circle is at (0,0) so you need to map a range from (-1,-1) to (1,1). Like so:


for x=0, ImageWidth-1, 1 do
for y=0, ImageHeight-1, 1 do
local nx = (x / ImageWidth) * 2.0 - 1.0 -- Remap nx to be in the range (-1,1) instead of (0,1)
local ny = (y / ImageHeight) *2.0 - 1.0 -- Same for ny

local value = fuzzy_disk(nx, ny)
Image:SetValue(x, y, value)
end
end


Sorry for the confusion on that.