Hey guys. I’m looking for some guidance on how I should go about making a 3D Mesh procedurally that’ll look vaguely like a rock or an asteroid.

My first thoughts on this was to use Metaballs with some randomly placed… errr… balls then drop on a bump map made from my Simplex noise function.

The other idea seems a bit more ambitious and potentially ridiculous which’d be to take a shape of some sorts (say a sphere) then find the normal of every point on the sphere and move it in or out by a value determined by my noise function.

This first idea seems the most reasonable and more guaranteed to get a more natural look to things but any thoughts on the matter would be awesome. Thanks!

I’d keep it simple. Just a random idea for an algorithm:

Generate a sphere of points to start with. Number of points depending on desired size of asteroid.

“punch” a randomly selected point out on its normal by X amount. Near points get punched out by smaller amounts following out through the mesh reducing the step each time. Those points will need a new normal calculating as they are all punched in the direction of the original distortion but by a smaller amount - not on their own normal. (This is what allows elongated shapes etc to emerge rather than just a wibbly sphere).

Repeat X times with a smaller punch each time. 2/3rds of punches outwards, 1/3rd inwards. Inwards punches have a check to make sure it doesn’t go through the far side and if so either make a hole or reduce the strength of the punch.

Tweak number of punches, strength of punches, amount the punch spreads out, %in/out etc until you get results you like.

Oh, to avoid the sphere being left by randomness I’d ensure that every point is punched at least once at some strength. Several ways to do that but the simplest would be just to punch each point once, picking a random point that hasn’t been done yet each time.

Huh… Ok. That sounds much more reasonable that I had envisioned when you word it that way.

I was thinking Metaballs initially since it seemed to be able to make those familiar “potato” shapes you find with rocks and asteroids. Although I suppose once I have this it wouldn’t preclude me from generating different point clouds any ways.

Thanks!

Well you can get “potatoes” and other complex shapes with this algorithm so long as the first punch is sufficiently strong As I said tweak the settings to get the results you desire…

… But bare in mind it was all written off the top of my head and not something I’ve ever tried to do (or really researched) …

… so there may be a better way

Well once I get something working I’ll make sure to show off here to see how well the theory works

Just had a discussion with @pspeed and he suggested a different way which might work well as well. I’ve edited it down slightly but here is the conversation.

Paul A spherical style diamond-squares would be pretty straight forward to write.

Paul Use a sphere projected cube and run the algorithm on the six sides.

Tim my idea was to generate a sphere then “punch” in and out points from the sphere obvious moving one point drags its neighbours

Paul That last statement starts to make it complicated.

And diamond squares is a pretty trivial algorithm… and it has LOD built in.

If you wanted to generate multiple levels.

Tim well the dragging neighbours is easy enough really. Just follow the links out and apply the same translation but scaled down according to distance

Paul If I ever write my Asteroids clone ES example, it will have generated asteroids.

Tim probably distance squared but meh, stuff like that would need tweaking

Paul you have to know what the neighbors are then.

Tim yep

Paul So you have to create your own sphere mesh code.

Or decipher the existing sphere mesh.

Tim yeah, either is easy enough tho

links are there in the index tables

however I like your solution too

Paul mine is dirt simple. A sphere projected cube is the easiest kind of sphere mesh to create and easy to UV map also with none of the pole issues.

Take a cube, divide the faces, push the vertexes out from the center.

Tim yeah

i can visualize it. you are right that its simple

Paul The initial corner points stay where they are.

Tim might end up with quite uniform asteroids tho if not careful

Paul And if you are perturbing with diamond squares, you just build that into the algorithm.

no

diamond squares would make them random. You’d see the initial corners randomly in that case and let the algorithm interpolate roughness.

see = seed

Tim but they would all be spherical

Paul no

not necessarily.

Depends on the initial seed points.

Tim no potatoes, crescents, holes, etc

Paul you could have potatoes and crescents. No holes.

Tim I think you might want to have a few different base meshes to start from

to inject more variation into it

Paul Personally, I would do a secondary pass for craters and holes.

Tim nod, was just thinking that

you are back to following the mesh now though

Paul diamond squares is like a 3D (2.5D) midpoint displacement algorithm.

Wrapped around a sphere projected cube it would/could create very odd shapes.

concave, convex, all sorts of things.

Tim it displaces in 3 dimensions?

as opposed to just shifitng in/out on the normal?

Paul You are displacing the spherical coordinate radii

But you can create lots of shapes that way.

Crescents, bowls, etc.

Tim sounds like a good fit then

Paul With high initial roughness you’d even get ridiculous crystal-spiky asteroids.

Now I want to write this. Wish I had time.

Tim just need to be careful your points are close enough together for the roughness or they might distort past each other

Paul The projection does have some limitations which keep you from getting into trouble with inverted parts.

Tim yeah

For reference:

http://en.wikipedia.org/wiki/Diamond-square_algorithm

This is a pretty good introduction to midpoint displacement style fractals:

http://www.gameprogrammer.com/fractal.html

Or at least the pictures look nice.

But to see how it works if you’ve never done anything like this before, it might be worth doing a 2D midpoint displacement visualization first (in swing or something) and then convert it to polar coordinates to see how it would work on a 2D circle.

Playing with the roughness and how it decays can be lots of fun.

Note: ironically, I do not generally recommend midpoint displacement algorithms for terrain generation because there are much better ways that don’t have the “need to generate my neighbor too” requirements. But for a fixed system like a cube/spheroid, it should work well.

Oddly enough I sorta have come to the same idea as you guys mentioned there but I had no decent explanation as to how it worked. Which sounds strange but where I came across this was a pluggin for blender.

http://wiki.blender.org/index.php/Extensions:2.6/Py/Scripts/Add_Mesh/Rock_Generator

In there is a link to a video that this script was based on that shows the process. I was going to try to convert the python script into java and see what happens.

suppose one did want to “punch in/out” the vertices…

what would be the best way to go about selecting the neighboring(within a radius) vertices to be manipulated?

is there a built-in way to select a vertex’s neighbors within radius on a mesh?

You should just implement a limited version of marching cubes. People who use this to create terrain mostly end up with grassy looking asteroids ;)>

@t0neg0d said: You should just implement a limited version of marching cubes. People who use this to create terrain mostly end up with grassy looking asteroids ;)>

Then they didn’t halve the displacement range at each level.

Edit: actually, I’m not even sure which algorithm this is referring to and I forgot this thread discussed a bunch… so probably nevermind.

<cite>@pspeed said:</cite> Then they didn't halve the displacement range at each level.Edit: actually, I’m not even sure which algorithm this is referring to and I forgot this thread discussed a bunch… so probably nevermind.

I was just kidding… the suggestion you gave looks to be simple and would produce great results. The original suggestion threw me a little, because no matter how *deformed* the sphere became, pushing a sphere’s verts along the normal… will just produce a distorted (but recognizable) sphere shape.

Not quite.

The first push along the normal will also distort the normals of the vertexes around it. When you then push along those new normals you end up moving away from the sphere shape some more.

At its most dramatic:

()

Goes to

(====)

Goes to

…_

(= ==)

…U

Hope that shows up in the forums!

You can see it doesn’t look very much like the original circle though even though each extrusion was along the normal.

Ah yeah… I see I see. Maybe this is the better approach then, considering fine detail could be (and probably should be) defined using normal/parallax mapping.

Honestly I think there are multiple valid algorithms in this thread. Which ones will give the better results is hard to say without trying some of them.

@zarch -what you last described is the way i am attempting to manipulate the verts of a geodesic icosasphere, but the biggest issue i am running into is something @pspeed had mentioned earlier… how to get your selected vertex’s neighbors (spatially speaking, not neighbors in an array or sorted list ).

i am currently making a custom mesh of a sphere with all points evenly (approximately) spaced apart on the surface (subdivided icosahedron).

i have duplicate verts at each intersection so that each face can have separate normals and texcoords.

i would like to change the vertex locations while they are still in my temporary array, before i send them to the meshbuffer.

i will most likely select the points of origin for the warping by random picking, but i have no idea how to select the duplicate verts that share the same vertex location… let alone all of the neighbor vertices within a given radius (+ their duplicates also).

i cant really use the order of my “position” array because my verts are added in their index order and in seperate iterations of my subdivision code.

anybody have any suggestions?

Is there any reason you used an icosahedron?

Anyway, the brute force approach is not hard… just loop through and find the vertexes equal to your target. Otherwise, you could create a brute force index like a Map of Lists… but then you need to maintain it.

If you were using a more spatially coherent source (like a projected cube) then it might be easier to come up with an approach that can also select the neighbors.

Is there any reason you are duplicating the vertexes? It’s seems like you would actually want them to share the normal for smooth shading and stuff. Otherwise, what is your intent with the normals as you move the vertexes around? Or do you actually want the triangles to all look flat?

It might be worth while to explain what the desired result is then maybe we even think of some different way to start that you haven’t considered.

@pspeed

i wanted to start with a geodesic sphere as a default lump of clay to mold “procedural” asteroids with.

i chose an icosahedron because it was the regular Platonic solid with the most faces to start with, then i subdivided each of the 20 faces (into 4 smaller triangles with normalized verts) ‘n’ times to create a “unit” sphere.

i want to use the points on this sphere as a base to create more realistic asteroids. i plan to have the user POV on the surface at times so i wanted a good resolution, or at least an easily scalable resolution.

i wanted all vertices of my base mesh to be spread out roughly evenly on the surface (as opposed to being more dense near the poles as with sliced spheres) so that i can manipulate them into asteroid shapes.

my plan was to manipulate the verts of the mesh by randomly picking a vertex and getting the surrounding verts (within a radius) to be “raised or sunk” relative to the direction of the normals of the center vertex. as these “radial” verts are moved, their normals are changed accordingly. upon the next iteration (maybe with different constraints, like an L-system, or fractally with different octaves) of randomly selecting a center vertex, the previously adjusted normal value is used as the direction the bumps/craters are relative to. after multiple iterations of manipulating the verts in this way, the mesh should have a more fluid/natural/organic shape. imagine a big hill with a little hill sticking out of it, with an even smaller hill sticking out of that one, with and even smaller hill… etc.

i would also like to come up with a way to manipulate those same mesh vertices dynamically at runtime according to user input… but seeing as all manipulation i am doing currently happens in a temp array that is eventually fed to the mesh’s position floatBuffer prior to building the mesh, i will wait and cross that bridge when i come to it.

the reason i duplicated all of the vertices for each polygon was to solve a texture coordinate ambiguity, but as a side effect, it also allowed me to have an option for “flat geometry shading” like you mentioned… which was actually helpful for troubleshooting and testing UV mapping templates.

funny side note… i was considering a 3d volume representation to accomplish this using marching cubes as comically suggested above, but it turns out to be a bit over my head at my current level.

In your current approach, you could build a graph of vertexes with the edges connecting them… and keep the vertexes shared until output. Then you can easily find neighbors.

Otherwise, if you use a projected subdivided cube (easy to build, easy to debug) then you can easily find neighbors because they are just part of the grid. Each cube face edge will connect to other cube faces but in a very straight forward way. Essentially you end up with 6 2D arrays of Vertexes (still shared).

It’s still a pretty uniform distribution of points:

I just personally think they are a lot easier to work with. Furthermore, they readily support fractal generation approaches like diamond-squares.

Also, you can debug it as a cube before projecting.