I have a space game, where action(colonization, fighting about colonization, misuse of mining craft, etc.) may need to take place on a large asteroid or planetoid. I'm still putting it together in my head, and I'd like to be able to dig a tunnel or something through the asteroid, blow the thing up, or whatever. Simulation of internal gravity is unnecessary, but I would be able to calculate vilume, and from that, mass, and from that gravity to affect every other independant object, but inside the object, I'll just assume that structural integrity is infinite. make life easier. I suppose I'll represent the object with a mesh, but if there's a better way to do it, I'll do that. What I need is a bit of knowledge on how meshes are put together, so I can align the edges of the hole(probably a sphere or rounded-end cylinder) with the edges of the asteroid, and add the changes to the asteroid's mesh. Is a mesh just a list of vertices and triangles, or is there a some sort of inter-triangle connectivity? How would I detect the intersection of two triangles? What problems or issues have I not foreseen?

I thought of that, and I don't want to do that because I want to be able to drill tunnels and stuff.

Quote:Original post by NIm
I thought of that, and I don't want to do that because I want to be able to drill tunnels and stuff.

Google "Constructive Solid Geometry", and understand that you're getting into a highly nontrivial area of geometry handling.

marching cubes algorithm?

I would suggest voxel maps. An asteroid can be represented as a 3d array. Tunnelling is trivial, becase all it needs is the ability to remove voxels one by one. Surface rendering can be implemented by connecting the edges of the voxel cubes with polygons. Computing the total mass is a trivial voxel count. These are the algorithms used by medical imaging systems (mri and ct).

The way "metaballs" (3D volumetric objects rendered using marching cubes algo) usually work is you have a 3D grid of points that store a "field strength" value, analogous to how far from the asteroid surface the point is. So rather than just on/off voxels you have a range of values. It's a bit more complicated when you're modifying it on the fly but it gives the surface a more smooth and natural appearance. You could possibly generate the field grid from a voxel map just by "blurring" it and have the best of both worlds.

Let's say you use bytes (0-255) to store the field grid, and 128 is the threshold value where you render the surface. When you have a grid cell with all of its corner values below the threshold it's empty space.. All corners above the threshold means the cell is solid rock. When one side of the cell is above the threshold and the other side is below, you render polygons that cross the cell.

The polygons are placed by interpolating between the corner field strengths. E.g. If the field is 64 on the left side of the cell and 255 on the right, the surface would be placed one third of the cell width from the left. Since you're dealing with eight corners per cube it gets a bit more complex, but fortunately it has been solved for you already as you can find any number of marching cubes implementations on the net :)

Wiki reading (with illustrations of both "smooth" metaballs and voxel data):
http://en.wikipedia.org/wiki/Metaballs
http://en.wikipedia.org/wiki/Marching_cubes

Thank you very much! this has been extremely helpful! I will probably use marching cubes or metaballs. How processor intensive are these methods?

Marching cubes is very fast. When used to display the metaballs effect in real time you'd need to run marching cubes to recreate the polygon mesh every frame, yet this was done on 100MHz computers back in the day. In the case of an asteroid tunneling game, you only need to recreate the mesh when the terrain is modified (e.g. the user clicks to excavate some rock). If your mesh is really huge it could take a noticable fraction of a second per click. The rest of the time it's a big happy static object rendering at a ridiculous rate. Alternatively you could split the mesh into several smaller cubes so you only need to recreate the mesh for the part of the asteroid that was modified.