Procedural Terrain Rendering How-To

Hey! Forgot to answer this bit. Vobj, in the example I gave, is anything defined in patch space. For example, the light or camera position.

Lights and cameras are typically stored in world or planet space, however, so you have to pre-transform these positions into patch-space for each patch prior to rendering that patch. The transformed positions are passed to the Shader as uniforms.

To go from world or planet space into patch space is also fairly trivial but wholly dependent upon how you define your patches. I define all of my patches as centered at the origin, laying along the xy plane, with z (Negative z in Unity, since it uses a left-hand coordinate system) as the radial outward direction This is what I call ‘patchSpace’. But patches need to rotated from this orientation, and translated to their ultimate location on the planet. To do this. I then calculate the one ‘yaw’ rotation and one ‘pitch’ rotation required to rotate the patch to its correct orientation in planet space (without that transformation, all patches would be centered on the zNeg face). Yaw implies rotation around the vertical (or ‘Polar’/‘North’) axis, and pitch around the horizontal (‘Equatorial’/‘East’) axis: these axes are defined differently per face (well, the xPos, xNeg, zPos, zNeg faces all share a common ‘north’ axis: yPos), but are common to each patch upon that face.

Knowing these two rotations, their respective axes, and the patch’s ultimate center coordinate once transformed and normalized to a sphere (patchCenterPlanet), I can create a single transformation matrix to convert the patch vertices defined in patchSpace into their proper location in planetSpace.

Ok, lots of words. Let’s math this shit:

Definitions:

World space:   right = x, up = y, forward = z, origin = 0,0,0)
Planet space:  right, up, and z, account for any tilt in planet's axis, as well as its current 
               rotation about that axis. Origin = the planet's origin in world space
Patch Space:   All of a patch's vertices are defined in this space, centered on its origin. 
               The space is different for each patch, but based upon two rotations and one translation. Equation for that is below.

For now we’re going to assume that PlanetSpace == WorldSpace, in other words, the planet’s axis has zero inclination, the planet is not rotating, and it is centered at the world space origin. I’m not going to detail how to build that transformation: If you understand the more difficult world-patch transformation, it will be easy to figure out how to do a world-planet transformation. And since transformations concatenate, world-patch is really: TworldToPatch = Tplanet * Tpatch (assuming column-major notation).

Note: I describe each face by its normal (radial outward) vector. So the ‘X Positive’ face lies within the Y-Z axis, and its radial outwards direction is +X.

So, for each face, define an “up” and a “right” vector. I’ll start with the simplest case, the Z Negative face (again, Unity, Left-Handed Coordinates. This would be Z Positive in a Right-Handed system).

//Z-Neg Face:
Vector3 faceUp = new Vector3(0,1,0);  //y-positive
Vector3 faceRight = new Vector3(1,0,0);  //x-positive

Next, we need to figure out where the patch’s center will be, once normalized to the planet-sized sphere. I call that position patchCenterPlanet . You need to know the patch’s center position in the quadtree, prior to ‘spherification’: i ca;; this the patchCenterCube The exact details will depend on your quadtree layout, but for me, the quadtree for each face is defined in planetSpace, the width of the LOD-0 node for that face is the planet’s diameter, and the face is displaced from the planet origin so that the center of the LOD-0 node just touches the surface of the planet-sized sphere at the very center of the node. In other words, the faces (and thus root nodes of each quadtree) form a box that tightly encloses the sphere. So:
(a == planet diameter)

//Z-Neg Face:
Vector3 patchCenterNormalized = patchCenterCube.normalize();
Vector3 patchCenterPlanet =  patchCenterNormalized * planetRadius;

That was easy. Ok, so ‘yaw’ will be a rotation around the ‘up’ axis, and ‘pitch’ will be around the ‘right’ axis. Calculate the patchCenterSphere's yaw and pitch values:

//Z-Neg Face:
float yaw = Asin(patchCenterNormalized.dot(faceRight)/planetRadius);  //Asin is arcsin
float pitch = Acos(patchCenter.Normalized.dot(faceUp)/planetRadius);  //Acos is arccos

Now we have all we need to build our transformation matrix. Recall:

(These are in row major notation, so be careful when converting them to OpenGL’s column-major format input)

These matrices concatenate easily. I apply my yaw rotation before my pitch rotation, so yaw rotation matrix must be post-multiplied with the pitch rotation matrix (again, row-major). In other words: T = P * Y, since row-major notation matricies are multiplied with vectors on their right. Also: alpha == pitch, beta == yaw

thanks wolfram alpha!

Finally, let’s add in the translational component to make it a 4x4 Homogenous transformation matrix:

Where s, t, and u are the x,y,z components of patchCenterSphere

Alright, so what does this thing do? It transforms your patchSpace vertices into planet space (which is also world space, in this example). It also defines the basis for your particular patch space… in other words, the 1st row defines the patch’s “right” direction, the 2nd row is “up”, the 3rd “forward”, and the 4th is its planet-space origin.

But we wanted to go from world space to patch space, not the other way around. This is also easy… we just need the inverse of this matrix. The inverse is a bit annoying to compute, but there’s one shortcut: if each basis vector is orthogonal and of unit length, the inverse is equal to the transpose. That’s much easier. Just normalize each row of the above resulting matrix. (Note: you only have to calculate this matrix once, when the patch is first defined, so in my mind computational expense is less important than clarity. It may actually be cheaper to compute the inverse than to do what I’m suggesting).

After normalizing each row, take the transpose. The transpose is simply Mij = Mji, in other words, flip each value along the diagonal axis (top let to bottom right). values on the axis (i.e. M11 M22 etc) remain unchanged.

You now have the inverse transformation matrix: in other words, the transform that will take you from planet(world) space into patch space!! Once you transform your lights & camera into patch space, you can now transform them into the TBN (tangent) space, and in doing so, perform advanced eye-position dependent lighting, such as specular and reflection. Congratulations, mission accomplished.

I could go on, and probably should go into more detail on some of these points, but I’m tired and this is already a huge post.

That would be very much appreciated :smile:

That’s awesome, I’m seriously impressed by the performance. Makes me want to go back to OpenGL, too… I do prefer it over DX.

Project’s going well, although I’ve taken a slight detour recently. Working on making the Simplex Noise function (textureless version) accept seeds, and also produce the gradient. Getting very close to it.

Also been working on some more stylistic elements, mostly for fun. You all have inspired me to ‘take a break’ from the technical aspects every once in a while and just play around with the actual results :smile:. Here’s a quick shot:

Alos… I love this book.

Picked it up several years ago and still find myself referring to it at least twice a month. Same with this one.

I highly recommend both!

Are you sure that is right @NavyFish, I needed to reverse this in order to get the texture coordinates given a XYZ sphere position and come up with this.

    float h1 = modPos.x;
    float h2 = modPos.y;

    float h = Mathf.Atan(h1) / (QUARTER_PI);
    float v = Mathf.Atan(h2) / (QUARTER_PI);

However this does not work properly, the texture coordinates returned are from ~-0.76-0.76, it turns out that using the Golden Ratio yields the right result.

    float h1 = modPos.x;
    float h2 = modPos.y;

    float h = Mathf.Atan(h1) * 1.618033989f;//golden ratio??
    float v = Mathf.Atan(h2) * 1.618033989f;

Yeah It’s quite amazing how well WebGL performs. I have yet to compute the noise on the CPU for collision and other calculations, but luckily Javascript has support for worker threads.

Are you using Ashima’s Simplex GPU noise? Would be interesting to see how you implement the seed functionality. I’ve been working on porting Ashima’s Simplex noise to Javascript - https://github.com/raRaRa/javascript-noise

Yes, I agree, it’s major fun to play around with the results! Here’s a video I took yesterday, it’s running on an old Acer laptop with GeForce 750m.

(Took me a while to find some interesting spot on the planet, and yes, I’m using terraced function to get those nice terrain features!)

I have to check out these books!

I’m pretty sure, yes. Did you put your x and y values into the range [-1,+1] first? Think about it: tan(PI/4) == 1 and tan(-PI/4) == -1. Not sure where .76 is coming from.

How are you storing your data, as textures? You can load a frame buffer with the texture and then readPixels on it to get that data onto the CPU. This stalls the pipeline, however, so you’ll want to look into asynchronous transfers to hide that stall. In essence you need to queue up the data for reading and then wait a couple of frames before actually reading it… This gives the driver enough time to pipeline the read and not cause a visible stall, at the cost of having your data a few frames late… But that data will typically persist for many hundreds of frames, so having it a few frames late is a negligible cost.

I’m still trying to figure this out in Unity, its going to require writing a cuatom native plugin… The pitfalls of working with someone else’s engine…

That’s what I wanted to do originally, but the problem with WebGL is that it doesn’t have asynchronous readPixels method. However, the team behind WebGL is working on supporting WebGL operations in worker threads, which should (hopefully) fix that issue. I’m unsure if it may still cause rendering pipeline hiccups or other issues :frowning:

For the reasons above I’ve decided to implement the noise functions on the CPU side, because I can do them in worker threads without affecting the rendering pipeline.

Life would be so much easier if I could just read the pixels asynchronously, no need to maintain the noise in two places.

Yep, I’m using Ashima’s WebGL noise for now, although will eventually move to a texture based lookup approach for speed. I’ve gotten seeds to work, and Stefan Gustavson himself agrees that it’s a valid approach. Will publish that code shortly: https://github.com/ashima/webgl-noise/issues/9#issuecomment-170826758

Ah, so it’s actually faster to use texture lookup? I wonder why it was implemented without one, if I recall correctly it was for performance reasons, but I may be wrong! At least it’s very simple to use. Very cool that Stefan Gustavson himself has replied and validated your work! :smile:

Yes, x and y are in [-1,1] range.

Anyway, happy to get to use the Golden Ratio, so pretty…

That’s one of the reasons he developed the textureless variant - so it was easy to ‘plug n play’, the other primary motivation was to make it compatible with GLES2.0, hence it uses floats not ints, etc.

They had hoped that since it didn’t rely on texture lookups it would play well with modern texture-access-heavy games, using untapped ALU resources… But modern GPUs have really upped the texture bandwidth and access speed, so that isn’t much of a bottleneck.

The textured variants still perform about twice as fast as the textureless.

If it works, great! Is the vertex distribution working for you? I’m excited to see someone else try the technique.

Just using it for reverse texture lookup, experimenting a little with something, this thread is evil.

/edit
Think I found the explanation.

lol, yes, too many interesting subjects :slight_smile: just confirming… That algorithm I developed is for distributing quadsphere vertices more evenly. I suppose the vertices could remain undistributed, with the texture coordinates distributed to make for a more even coverage… But haven’t tested that myself. If you end up getting it to work, please share!

My version with the golden ratio is working just fine, below is the reverse height lookup from xyz positions to texture then back to the planet for visualization.

1 Like

That’s awesome. So your modified version of Ashima’s Simplex noise is going to support seeds and texture lookup? Are you going to make it open-source on Github? :smiley:

That or create a pull request on the Ashima git.

I haven’t done seeds (or gradient) for 4d noise, not sure if i’m up to the task.

@NavyFish Hello again!
So. I have a mess on output with your examples.
First problem is numthreads. In first kernel if nVertsPerSide = 128 i get error that say “too much. only x * y * z <= 1024 threads” or smth.
So.
When i try to nVertsPerSideWithBorder = 32 and nVertsPerSide 30, and mesh with side 30 v - mess output.
Idk.
I can post shader here…

Try [numthreads(32,32,1)] and Dispatch(kernel, 7, 7, 1) … See post #113 in this thread.

This executes 49 (7x7) ‘groups’ of threads, where each group contains 1024 threads, for a total of 50,176 thread executions. There’s a limit to the number of vertices in a mesh in Unity (Something like 64k), so those numbers are designed to keep below that limit while still giving multiples of 32 threads per group (this number seems to work well on most modern GPUs).

numthreads(x,y,z): z must always equal 1, and xy must be less than 1024.
Dispatch(gx,gy,gz) calls gx
gygz number of thread groups. Each of those groups contains xy*z number of threads.


Figured I’d post a few pics to accompany good news… I’ve finally gotten analytic normals working at all octaves. This approach is about 5 times faster than numerically calculating the normals (as I’ve been doing up until now). The downside is that you have to be careful with your noise functions - any modifications to them, such as discontinuities like absolute value, etc, will break the analytic derivatives. I think I’ll keep using both, reverting to numericals only when needed.

Additionally, I’ve gotten 3D seeds working with the textureless variant of SimplexNoise… woohoo!

I’ve been working on a sub-project in Unity, so this isn’t my full planet. It’s a single patch, no LOD, etc… just messing around.

Contour Lines!

Spotlight, demonstrating the Per-Pixel normals, using the analytic derivative in a fragment shader. In the future I’ll use a normal map, but this is being generated in real-time

Just a neat shot :smile: makes me want to play a survival game, lol. This and the above shot all have low resolution meshes, but with about 14 octaves of noise comprising the pixel normals. There are no textures here, just solid colors being applied by a color ramp

This is actually the full color ramp. It’s a 1x96 pixel ‘texture’ I created in MS Paint, lol. The ‘rocky mountain’ images are using this ramp as well, but with the ranges skewed

showing normals, tangents, and biTangents

closer shot of the normals. Notice the black lines: those are numerical normals, turned on to compare against the analytic normals (the red lines). They match everywhere almost perfectly, any differences being due to the analytic normals using the gradient of a continuous surface, where the numerical normals are discrete height samples on a discrete grid. Green and Blue are tangent and bitangent lines.

another shot, showing the analytic normals equivalency with numericals, even in a tight place. This is about 8 octaves of noise. As long as you decrease the vertex spacing as you go, I don’t think there’s a limit to the approach. I’ve tested it at 20 octaves and had the same good results.

2 Likes

Looks really good! I really like the spotlight and normals pictures. It’s too bad I can’t use the analytic normals since I’m messing up the noise afterwards (using terraced function plus blending other various noise functions).

The darkness around that huge mountain sure gives that survival feeling! Do you actually have any plans to make games out of this? I’m thinking about making a few mini games out of my engine, got some rough ideas in my head.

Really glad to see your engine coming along very nicely. Can’t wait to see more :smiley: