Planet Rendering: Part 2 - Generating The Data

Time for an update. I'm making good progress with the demo; hopefully I'll finish it tomorrow..

In the mean time, let's get this discussion going.. I know many people here are working on terrain engines, and some are taking the procedural apporach. What functions are you using?
Also, what other issues would you like to be discussed conserning procedural height-data generation?

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

[edited by - technobot on July 25, 2003 5:46:22 PM]

Not much to add. I''m currently using multifractal with 12 octaves of ridged Perlin Noise.

Ridged Perlin noise is very easy to implement, you just basically use the absolute of the Perlin noise function, instead of using a "signed" noise. The main effect is to make your terrain sharper, like in mountaineous areas.

On the performance issue, i have to say i''m considering trading the real noise calculations for some pre-calculated noise tables that will be combined with a multi-fractal like function. I hope to increase my performance that way.

Y.

Have you checked out Texturing and Modeling? It''s got probably the best info on doing 3D planets, even if it''s not in realtime(it''s not to hard to adept it though). If you want to read about doing it in real-time, there are some articles in the upcoming books Graphics Programming methods and Shaderx2(although mainly focusing generating the data on GPU, rather then on the CPU). You could also check out baddoggames.com(or something like that, it''s Rob James''s site).
Jesse
www.laeuchli.com/jesse/

I''m not really working on planets, but a big terrain nevertheless. And you asked what methods terrain engines used, so here goes

The terrain supports virtually any terrain size, but I use 66x66km2 with per-meter-detail for our project, using one rough heightmap and procedural details inside every cell. All the raw vertex-data would occupy 48GBs of RAM, so I had to use procedural details to get things reasonable. The current terrain-data on the HDD takes 19MBs, uncompressed. The terrain-organization is a runtime, adaptive quadtree, that changes constantly when the viewpoint moves or rotates, which involves patch-recomputations and vertex-buffer re-organization.
Slow? I wouldn''t say that, the current alpha-stage of our overall engine renders the terrain at 500-800 FPS, no slow-down when moving

Some time ago, somebody said that it was just pure quake-nonsense aiming at several hundreds of FPS. Personally, I don''t understand my over-clocking friend, playing Q3 at 500 FPS, but our team''s terrain _is not the engine_. We''re gonna add more, and we need the performance to get other things going. So so that nobody will complain on this...

quote:

---

Original post by Ysaneya
Ridged Perlin noise is very easy to implement, you just basically use the absolute of the Perlin noise function, instead of using a "signed" noise. The main effect is to make your terrain sharper, like in mountaineous areas.

---

Glad you decided to join in. I beleive it''s one minus the absolute value, although I''m not sure whether this is done on the sum of all the octaves, or on each octave...

quote:

---

On the performance issue, i have to say i''m considering trading the real noise calculations for some pre-calculated noise tables that will be combined with a multi-fractal like function. I hope to increase my performance that way.

---

That may not be necessary... The trick is to minimise the calls to the multifractal function. I think we''ll get to that pretty soon.. Btw, have you had any success with the problems you mentioned in the previous thread?

quote:

---

Original post by laeuchli
Have you checked out Texturing and Modeling? [...]

---

No, I haven''t checked it, for some reasons I''d rather not list here... That''s ok though, I have at least some idea how to do these stuff anyway, from online sources as well as from my own thoughts.

quote:

---

Original post by coelurus
[...] I use 66x66km2 with per-meter-detail for our project, using one rough heightmap and procedural details inside every cell. All the raw vertex-data would occupy 48GBs of RAM, so I had to use procedural details to get things reasonable. The current terrain-data on the HDD takes 19MBs, uncompressed. The terrain-organization is a runtime, adaptive quadtree, that changes constantly when the viewpoint moves or rotates, which involves patch-recomputations and vertex-buffer re-organization.
Slow? I wouldn''t say that, the current alpha-stage of our overall engine renders the terrain at 500-800 FPS, no slow-down when moving

---

Yes, it''s quite similar to our apporach - precalculated or outer-source low-detail plus procedural high details inside. I was actually asking what procedural (noise?) function people are using. Care to expand on yours a bit?
Also, regarding the speed - it pretty much depends how many vertices one updates per frame, and how.


Btw, regarding my demo - I have all the functions ready, but I need to fix some final bugs in my perlin noise implementation and adjust the interface before I upload it.

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

quote:

---

Original post by technobot

quote:

---

Original post by laeuchli
Have you checked out Texturing and Modeling? [...]

---

No, I haven''t checked it, for some reasons I''d rather not list here... That''s ok though, I have at least some idea how to do these stuff anyway, from online sources as well as from my own thoughts.

---

Heritic! :-). Really, unless you just enjoy figuring it out on your own, you should check out the latest addition of T&M. It''s pretty much got the state of the art in planet rendering. Those two other books are good too :-).

I simply used mid-point displacement on triangle-strips, since they are pretty quick to render (one call for one patch) and the method is really easy and quick during generation.
I don''t use the screen-space error-thingy, since that pretty much makes the patches'' LOD-levels unpredictable. My renderer relies on bunching up of patches, which means, when a bunch of patches of the highest LOD (the least detail) take up some area, I render them all with one call using the same index-lists as with single patches. That helps a lot with performance (is this what Chunked LOD does?). I might even reduce these bunches whenever I need to optimize, but I don''t feel like it atm...
LOD-levels are simply morphed with a vertex program and cracks are fixed with skirts. They don''t rely very much on the terrain and let the quadtree to be kept simple.
LOD is calculated with an exponential distance-formula, which fades in big features of patches very slowly and the small details quicker. The effect is invisible when walking and hardly noticeable when travelling at 90km/h. We''ll flatten out the terrain where the roads are, so even less morphing will be visible.

This terrain is not supposed to be a super-neat realistic terrain on its own, so I can afford skipping some usually preferred techniques. We''ll cover the terrain with a lot of other things anyway, which will obscure the terrain.

It seems most people are thinking along the same lines that a pre-generated elevation map is necessary for low level details, with simple fractals for high level (sub one kilometre) details, and I agree. The elevation map need not be derived from an actual planet, though. I think complex fractals and other algorithms could generate a realistic enough planet, although I haven’t done any work in this area myself.

I’m not sure I have anything more to contribute, as most of you seem to be using geo-mip-mapping techniques for rendering planets, while my own planetary terrain project uses ROAM. By the way, I’ve done hardly anything with the project since a demo I posted a couple of months ago so don’t expect any updates.

Justin.

Planet rendering! Woohoo!

I agree with Coelerus'' suggestion of using a midpoint-displacement (plasma) fractal. The big picture will have to be created by some smarter algorithm but midpoint-displacement is much faster than fractal brownian motion, so for the tiny detail-geometry that will be generated and discarded all the time as the player moves around i think it is a good idea to use midpoint-displacement. I haven''t really tried this but i think that in a triangle-subdivision it''s artifacts will be less ugly than in a square-subdivision.

Other than that, are we going to discuss the generating of normals in this thread? I have found that to be quite tricky too.

Marijn

One way to generate normals, is to make two vectors over the current point from the four closest points around. Take the cross-product and there''s your normal. One cheaper way is to simply take the difference in X and Z, set some value to Y and normalize.

I know, but as the terrain gets subdivided when players get closer the geometry changes and thus, the normals change. Changing normals is usually pretty ugly, so we can not generate normals on the fly. (Would probably be inefficient too.) If we keep our normals buffered, how do we generate them? From the ''top-level'' geometry we got from the file? This might create some weird artifacts i think, if the subdivision-generated points around a ''top-level'' point have normals based on different geometry the top level point will often appear as a light or dark spot on the terrain. It would be nice to have normals based on the form of the geometry after subdivision. If something like fractal brownian motion is used it is possible to find a rather accurate slope of the terrain based on the slope of the fractal at that point. Lots of extra calculations though.

Marijn

Keep a pile of potential LOD levels for your geometry and generate normals over a set of frames. For example, if things change only by one LOD level, you simply store normals for 1 level above and under if things move slowly. If things move quickly or LOD levels vary a lot, 2 might be needed. That way, you will always have the correct normals at your disposal, without any delays when switching. Determining when to generate the normals should be a bit more sophisticated, but the general idea is pretty robust.

coelurus, marijnh:
Midpoint displacement produces somewhat boring and unrealistic results, IMO. If you''re not really after realism that may be enough, but I prefer a more flexible (and unforetunately more expensive) approach, in particular some sort of multifractal function.

Justin Nixon:
Pre-generated elevation data for low level details is not really necessary as such, but it can indeed improve realism if it is generated by realistic methods or even taken from actual real-world data. Also, ROAM/GMM may have less to do with this thread than you think...



Before I get to the subject of normals, I''d like to discuss my demo and the generation of our height data. I finally finished the demo today, and have uploaded it here. The noise functions and related code are included in the archive. I had to slightly adjust some of the functions I described in the original post to get reasonable results. They probably could use some more tweaking, but I decided to leave them at their current state, as that is not very important. The demo is based on a program I wrote 2.5 years ago, during my early days in 3D graphics.

The elevation map of the demo is generated as follows: when the image is created or resized, for each pixel of the image I translate the pixel coordinates (x,y) into a set of polar coordinates (longtitude, latitude), then translate those into a set of 3D coordinates (x,y,z) and store those in a two-dimensional lookup table (a simple array). The 3D coordinates are calculated as the 3D unit vector from the center of a planet to a point on its surface with the polar coordinates mentioned above. At a later stage, I feed the precalculated coordinates into a 3D fractal function, along with other parameters, to get the height value at each pixel of the map. This results in a map that can be seamlessly mapped onto a sphere with a cylindrical uv mapping. As a side-effect, the map is stretched near the top and bottom edges. This stretching should be canceled if the map is mapped onto a sphere.

After playing with the demo a little, I think that the Multifractal2 function gives the most interesting results, but you should probably take the time to find your own favorite. I didn''t like the results of the ridged and cracked filters, but they do have interesting characteristics... Perhaps it is possible to get better results out of them by integrating them into some clever composite function. I tried making a function like that, but the results were quite crappy. I think it deserves another try though... maybe I''ll do that later. Although a function such as that will be quite expensive, I suppose.



Anyway, regardless of the exact function, the height data generation is the same, so let''s talk about that for a moment. As we discussed in the 1st thread, our data is organized in a geo-quadtree, whereas each node points to three vertices that represent its geometric data. The vertices are shared among neighboring nodes, and contain a unit vector (pointing away from the center of the planet, towards its surface) and an altitude value. In addition, the leaf nodes contain geomipmap patches (one patch per node), which is what we render. Hence, we have several cases:

• Initialy subdividing a node upto the desired level. This is only done once in the beginning, when we are building our tree, and at this stage only the nodes'' vertices are being updated, and no GMM patches are generated. The level of subdivision is determined based on a preliminary per-node error metric that is evaluated according to easily available factors such as a node''s distance from the camera and the altitudes of its vertices.


• Generating a GMM patch for the first time. This is done towards the end of the tree construction stage, when we create our leaf nodes. As the patch is generated, we keep track of the heights of the patches'' vertices, and their effect on the node''s error metric. If at the end of mipmap generation the error metric is found to be too high, we must split the node further, until the error metric is low enough.


• Splitting a leaf node. This is done on a regular basis, whenever a node''s error metric grows above an upper limit.


• Merging leaf nodes. This is also done on a regular basis, based on the error metrics.

The first case is fairly easy. Since we don''t need to generate a GMM patch, we just need to find the coordinates and heights of three new vertices, one at the middle of each edge of the (triangular) node. The other vertices are already available (and are being used by the node we are splitting). For each edge, take the two vertices that define it, sum up their vertex vectors, and normalize the result. This gives the vertex vector of the new vertex. All that is left to do is to pass that vector to the fractal function to get the height of the vertex. Note that since the vertices are shared, some verices may not need to be generated at all.

The second case is similar to the first one, except that we''re generating a GMM patch, rather than just a few vertices. Each GMM patch consists of a vertex buffer and a set of index buffers, one index buffer per LOD level. All patches have the same amount of vertices and faces, which are aranged in the same way regardless of the node''s subdivision level (the higher the subdivision level, the smaller the patch and its faces, but the topography remains the same). Therefore, we can precalculate the index buffers and share them among all mipmap patches. This leaves us with the vertex buffer. There are two catches: one - the patches'' vertices are stored in simple hardware-friendly xyz format, and not in unit-vector-plus-height format like the nodes'' vertices; and two - to allow for single-percision floats, the vertices'' coordinates are stored relatively to a predefined reference point inside the node (e.g. the node''s first vertex).

The corner vertices of the patch can almost be taken directly from the node - they just need to be converted to the proper format and biased by the reference point. The other vertices are generated as follows:

• Find the unit vector corresponding to the vertex.


• Pass that vector to the fractal function to obtain a height value.


• Convert to xyz format by scaling the unit vector by the height value.


• Bias the resulting vector by subtracting the reference point''s vector from it, and store the result.

There are two ways that I''m aware of to find the unit vector of each vertex. The first way is to interpolate the unit vectors of the node''s three vertices and renormalize. The other way is to recursively fill-in the mid-way vertices, as if we were simply subdividing the node to a much higher subdivision level. I think the 2nd way is simpler, and may actually be faster (since one needs only to do one vector sum of two vectors per GMM vertex, instead of a bilinear interpolation of three verctors). In addition, it might hold the key to an significant optimization that I''m currently considerring.

This brings us to the third case, splitting a leaf node. This is basically a combination of the first and second cases - first, new node vertices are generated as necessary, and the original node is split; then, mipmap patches are generated for the new nodes; and finally, the old mipmap patch is destroyed. An important observation is that about a third of the new GMM vertices can be easily obtained from the old GMM patch, and so can the new node vertices.

Finally, in the fourth case we merge four neighboring leaf nodes, such that their parent node becomes a leaf node. This is somewhat of a mix between the second and third cases. The parent node already has its three vertices, but it is missing a GMM patch, so we must generate one. However, similarly to the third case, all vertices of the new GMM patch can be easily obtained from the four GMM patches of the nodes that are being merged.

As you may notice, all but the fourth case require vector normilizations to generate the new vertices. I think this can be sped up by using a 3D lookup table of scaling factors. Of course, if anyone has a better way to generate the vertices (other than midpoint-displacement), do post.



And now, at last, to the issue of normals. This is an important issue. Ideally, the normal of a vertex at a low LOD should be exactly the same as the normal of that vertex at the highest supported LOD. This is because the lighting of the terrain should not change in accordance with the subdivision level - it should be independant of the LOD. The problem with this is that to generate normals like that, we need knowledge about the geometry of the highest LOD. I do not yet know how to generate the normals like that, especially if that is to be done efficiently. Any ideas?
I do know that the normals should probably be generated together with the rest of the vertices'' data.

coelurus:
The terms of x, y, and z as you used them are not relevant to us, since we are dealing with a sphere. For example, at the north pole y would be up, but at the equator it will be paralel to the planet''s surface.


Michael K.,
Co-designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

quote:

---

Glad you decided to join in. I beleive it's one minus the absolute value, although I'm not sure whether this is done on the sum of all the octaves, or on each octave...

---

Hem, you're obviously right, it's 1-abs(noise) (i'm using it for each octave, not all octaves).

In case you didn't see it yet (already posted the links a few times on this very same boards), here's the link to my planet engine (plus videos):

Clicky

Regarding my problems, haven't advanced much yet. However, concerning the normals generation... i've hit this problem directly in the face, since i'm generating all the data on-the-fly. I'm keeping a huge cache of vertices. In my terrain algorithm, when i split a node in 4, i reuse the vertices from the parent. This has dramatically cut down the number of vertices to generate procedurally; but also improved the rendering speed, since the same vertices are referenced with indices, it improved the Transform cache usage.

Now, about the normals, i simply get the vertex positions of 2 neighbooring vertices in the same node, and do a cross-product. Note that i'm really doing it on the vertex positions in world space, and not differencing the heights, because my earth is real 3D (deformed sphere).

Ok, so what if a vertex is on a node boundary, you say? If do you get a neighboor if this neighboor is in another node ? Well, when updating my quadtree, i also keep, for each node, links to the neighbooring nodes. The algorithm is definately not very easy to implement, lots of cases and exceptions, but... it works. As a result, the cost of calculating the normal at a vertex is just the cost of accessing the neighbooring vertices positions, and doing a cross-product.

Y.


[edited by - Ysaneya on August 1, 2003 4:42:00 AM]

Your videos are stunning, Ysaneya. Good work. I think my lack of motivation, and probably talent, with my own project has just taken another hit.

Justin.

[edited by - Justin Nixon on August 1, 2003 1:46:09 PM]

quote:

---

Original post by technobot
And now, at last, to the issue of normals. This is an important issue. Ideally, the normal of a vertex at a low LOD should be exactly the same as the normal of that vertex at the highest supported LOD. This is because the lighting of the terrain should not change in accordance with the subdivision level - it should be independant of the LOD. The problem with this is that to generate normals like that, we need knowledge about the geometry of the highest LOD. I do not yet know how to generate the normals like that, especially if that is to be done efficiently. Any ideas?
I do know that the normals should probably be generated together with the rest of the vertices'' data.

---

The height in your world is generated by noise, correct? You can get the normals from the actual source data, instead of the surronding verticies. If you''re using (for example) Perlin noise, then you actually get the height from a series of interpolation functions of the form xi = x0 + f(a)*(x1-x0) where f(a) is usually the ease curve
f(a) = 3a^2 - 2a^3. Fully expanded the usual perlin noise height function given the 4 noise corner vectors v1, v2, v3, and v4 is:

h(x,y) = v1 + f(x)(v2-v1) + f(y)( (v3 + f(x)(v4-v3)) - (v1 +
f(x)(v2-v1)) )

It''s easy to find dh/dx and dh/dy. Looking through my notes I think df/dx (x,y) = (6x - 6x^2)*(c1 + (c2 - c1)(3y^2 - 2y^3)) where c1 = v2-v1 and c2 = v4 - v3. dh/dy is something similar, but I can''t seem to find it now...But either way, you should be able to plug v1, v2, v3, v4 in a general function and very quickly get back dh/dx and dh/dy. These can be used to find the tangent plane at (x,y), where that plane''s normal is the normal of the vertex at that point. I''ve been working with it all today, trying to find some nice mathematical tricks that make this as fast as possible to calculate. I should be done by the end of today, and then I can test it. Unforutunately I''ve had to dig out the calculus 3 book because I don''t remember a lot of it.

If your world is defined by noise, you should be able to get the normal at *any* point with infinite precision (i.e., precision of the float), without taking cross products with nearby verticies. I think it''d be pretty fast too, I''ll post my results when I get it working in good order.

LuxMentis-
You have my attention. My math brain kept telling me there was a faster way to generate normals - after all, they''re just curves, right? But did I listen to it? Hell, no. Programmer brain buried it under cross-product hell.

It''s a wee bit past my bedtime, but I''ll definitely be checking back for those results. Actually I''ll probably try to derive the thing myself and double-check. Right now everything''s amazingly fast though. normals = (0.0f, 1.0f, 0.0f)


As long as it''s permanently noon everywhere on the planet at once...

quote:

---

Original post by Ysaneya
In case you didn''t see it yet (already posted the links a few times on this very same boards), here''s the link to my planet engine (plus videos):

Clicky

---

Your screenshots look really beautiful. I haven''t checked out the videos, since my connection is quite slow, but I''ll take Justin''s word that they look even better.

quote:

---

In my terrain algorithm, when i split a node in 4, i reuse the vertices from the parent. This has dramatically cut down the number of vertices to generate procedurally; but also improved the rendering speed, since the same vertices are referenced with indices, it improved the Transform cache usage.

---

Yes, I was also considerring reusing the vertices entirely (not just adjusting and copying them, like I suggested earlier). I''m glad to hear you are getting significant performance improvements from that approach. Just so I could see the issues with this more clearly - how are you storing your vertices (singles/doubles; global/relative coordinates; etc.)?

quote:

---

Now, about the normals, [...]

---

If you recall, we briefly discussed a neighbor-nodes connectivity scheme in the first thread. As for calculating the normals, a cross product is generally fine, but it depends on your exact geometry (i.e. on the local Level of Detail), which I think is incorrect behavior. It would be interesting to find a quick way of generating normals that are independant of LOD. If you wish to stick to cross products, I think there are some ways of optimizing the calculation, possibly by rearanging the mathematical terms a little...


LuxMentis:
Yes, it is possible to find a formula for the normal based on the noise function, but at least at first sight it seems to be much more expensive than a cross product... Hopefully I am wrong on this one. Also, it gets more difficult to find the formula if the function is more complex than just a bunch of perlin noise octaves... Nevertheless, I look forward to seeing your results.

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

I just finished a long search for normals calculations. Unforetunately I didn't find much (other than the usual cross product). I did find a faster-than-cross-product method for calculating normals in a LOD-dependant way, curtesy of Yann L's water lecture. Here is a code snippet from the lecture:

void ComputeHeightfieldNormals(int xsize, int ysize, float *Heightmap, fvector *Normalmap)
{
        int x, y;
        float l;
        fvector *N;
        int xsm = xsize - 1;
        int ysm = ysize - 1;        

        for( y = 0; y < ysize; y++ )
	   for( x = 0; x < xsize; x++ ) {

	      // Access current normalmap grid point

              N = &NormalMap[y*xsize+x];

	      // Compute normal by using the height differential

              N->x = HeightMap[y*xsize + ( !x ? 0 : x-1)] - HeightMap[y*xsize + ( x == xsm ? xsm : x+1 )];
              N->y = HeightMap[( !y ? 0 : y-1)*xsize + x] - HeightMap[( y == ysm ? ysm : y+1 )*xsize + x];
              N->z = (2.0f / (float)xsize) + (2.0f / (float)ysize);

	      // Normalize it

              l = sqrt(N->x*N->x + N->y*N->y + N->z*N->z); 
	      if( l != 0 ) { 
	         N->x /= l; 
	         N->y /= l;
	         N->z /= l; 
	      } else N->x = N->y = N->z = 0.0f;

           }  
}

It's called height differencing (or something like that). The above code is meant for a heightmap, so we cannot use it in that form - we need to adjust it. Getting the altitudes of adjacent vertices is not a problem, but there are two other problems. The first problem is that the above code assumes a rectangular grid where each vertex has four non-diagonal neighbours, whereas in our case, each vertex has six immediate neighbors arranged in a triangular grid:

assumed:        ours:
+----c----+      c-----d
|    |    |     | |   | |
|    |    |    |   | |   |
b----a----d   b-----a-----e
|    |    |    |   | |   |
|    |    |     | |   | |
+----e----+      g-----f

 

The second problem is that the above code assumes that the coordinate system is arranged the same everywhere, i.e. "up" is the same vector everywhere. This is not so in our case, since we are dealing with a sphere, rather than a flat surface. I'm not sure how these two problems can be resolved...

In any case, it would still be interesting to find a LOD-independant method.

EDIT: D*** editor screws up my ascii art!

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!


[edited by - technobot on August 3, 2003 8:21:30 PM]