New terrain engine

Hello all. I've been doing some research and trial and error and am in the process of developing a new terrain engine based on adaptive quadtrees and triangle fans.

I read about it at www.gamasutra.com but didn't think much of it. Well just recently I dumped my old system because it had cracks and crevices between terrain resolution patches and moved to using triangle fans. Each fan is composed of 10, vertices and 9 triangles. The matrix idea from gamasutra actually popped into my head and then I remembered the article. Amazing how trying to achieve the same result leads you to the same conclusions, without you even realizing it.

My goals for the terrain system are:

• View-dependent CLOD. This is not based on height or detail of the land.
• Render from camera to horizon in all directions, regardless of altitude.
• 60 FPS or better, hopefully more like 80 to 100.
• Quad tree-based culling system using p and n vertices, plane coherency, and other similar tests.
• Multiple terrain texture types seamlessly blending from one type to another. Fairly simple texture blending.
• Per pixel diffuse and specular lighting using shaders.
• Ground foliage using textured quads - not billboards.
• Water with reflection properties using cubic environment mapping. Would love to have real-time environment mapping, however, even high end computers with uber cards would have problems in a terrain setting. Will probably update environment map once every 15 frames. Many games use this technique to aid rendering. Check out Need For Speed Underground 2. Environment mapping on cars lags behind actual position of car due to delayed update of environment map. Midnight Madness also uses this technique only it updates once every 6 frames and maintains a cache of the environment map.
  Cannot use vertex displacement shaders as my card does not support this. Requires PS 3.0+. Would look good for water, but just cannot do it.
• Shadowing of terrain objects using shaders. No shadows for distant objects. Just not enough FPS for it.

The most important factor in the engine is rendering to the horizon. Many, many games just simply cannot do this which is annoying. This means that CLOD must concentrate on distance from camera rather than density of triangles based on elevation changes. With Rottgers even a resolute terrain patch will render slowly off in the distance because the same number of tri's are used. Might use Rottgers to reduce the tri's on the map and then use adaptive quadtree LOD triangle fans to further reduce the detail levels.

Will have screenshots soon.
If I can render to the horizon with acceptable levels of detail and render <=80000 triangles, I think I can maintain 80 FPS.

I'm going to use geometry clipmaps. Came across an article by Hugues Hoppes who used to be with Microsoft. I'm fairly certain FS9 uses this technique to render to the horizon. I've not been able to create a terrain in world space from data points and get it working right. In order to do a complete coast-to-coast fly over for the U.S. I will need to figure out how to implement this.
I can't really explain what a geo clipmap is except to say that it is much like a texture clipmap and/or a texture mipmap.

To prevent T junctions I have to interpolate the height of the T junction on y to account for the upsampled height value.

For instance if a T junction is occurring on the top side of a quad, then I must take the lower left Y and lower right Y and interpolate using an interpolant of .5f to place the vertex at the correct position to seamlessly connect with it's neighbor.

Once I get this done, it should be able to render to the horizon. It will probably need 11 to 14 resolutions of the terrain to get it done right.

Hopefully pictures soon.

I did get the quad-tree triangle fan-based terrain done, but I'm not happy with it's performance.

This is a screenshot from the engine so far. There are 3 levels of detail here although you cannot clearly see them. The first level uses 8 triangles per 4 quads, second is 4 triangles per 4 quads and third is 2 triangles per 4 quads. There is no terrain popping or morphing with this method. Level 1 and 2 do have seams but I can fix that.

This screenie has the following parameters:

Near/Far clip: 1.0 to 35000.0f
HFOV: 45 degrees
Height map size: 2048x2048
Detail map: 128.0f
Light map 1.0f - one map across terrain, no tiling
Texture map 1.0f - same as light map

Not sure about the number of tri's since each level needs its own data member for number of tri's. I'd say it's close to 100000 triangles in this screenie.

Might I suggest, that when you're done with that, to take it a step further. :D

After that you've already got your quad trees and uber terrain..

Add portal culling and BSP for seamless indoor/outdoor transitions, give it a try!

Quote:

---

Add portal culling and BSP for seamless indoor/outdoor transitions, give it a try!

---

Why don't you give it a try yourself?



Good luck with your project Bubba. Looks interesting.

Quote:

---

Originally Posted by BobMcGee123

Why don't you give it a try yourself?



Good luck with your project Bubba. Looks interesting.

---

I'm getting there :D.

Hey Bubba, always nice to see more interest in the wonderful world of terrain rendering :)

Quote:

---

Originally Posted by Bubba

This means that CLOD must concentrate on distance from camera rather than density of triangles based on elevation changes. With Rottgers even a resolute terrain patch will render slowly off in the distance because the same number of tri's are used.

---

Actually, Roettgers algorithm uses both the roughness of the terrain and the distance to the camera for its LOD calculation. So a resolute patch will use less and less triangles as it moves off into the distance. It will however, use more triangles than a flat section of terrain that is equally distant from the camera. A desirable propery :)


Your initial analysis seems pretty thorough, here's some other things to consider:

• How will you handle transitions between levels of detail (Geomorphing, allow popping?)
• re: rendering to the horizon. Do you mean always rendering to the edge of your terrain? how will you line up your sky with the edges? if your terrain is square, you'll see triangular regions in the corners. If you use a skydome, your sky will intersect the terrain, and without fog, you'll see terrain features appear/dissapear from behind the sky.
• Algorithms like Roettgers and ROAM incorporate things like culling and T-junction elimination. Performing these things as a post-process can eat valuable CPU time. Will your adaptive quad-tree algorithm allow you to do these types of things as you calculate the levels of detail?

Looks great man keep up the good work

Quote:

---

How will you handle transitions between levels of detail (Geomorphing, allow popping?)

---

Geomorphing can be minimized by using linear interpolation between two resolutions of terrain. Basically instead of presenting the actual vertex height, you pick an in-between value based on the neighboring vertices.

Quote:

---

re: rendering to the horizon. Do you mean always rendering to the edge of your terrain?

---

I mean render to the horizon just as it says. Think Microsoft Flight Simulator or Combat Flight Simulator.

Quote:

---

how will you line up your sky with the edges? if your terrain is square, you'll see triangular regions in the corners.

---

I'm not quite sure how to correct this, except that I hope to render far enough from the camera so that fogging artifacts are not easily noticed.

Quote:

---

If you use a skydome, your sky will intersect the terrain, and without fog, you'll see terrain features appear/dissapear from behind the sky.

---

No skydome here. I'm either going to just use flat grids to represent the skies, mixed in with the same algo used in FS9 to generate clouds (Found a link leading to the guy's site who designed the MS FS9 cloud system) or I will use a sky cylinder - sort of like going to an IMAX movie where the screen surrounds you. The cylinder will also not cause the same fogging artifacts as a skybox or dome.

Quote:

---

Algorithms like Roettgers and ROAM incorporate things like culling and T-junction elimination. Performing these things as a post-process can eat valuable CPU time. Will your adaptive quad-tree algorithm allow you to do these types of things as you calculate the levels of detail?

---

Yes this does eat CPU time however it can be minimized. It is a simple lookup between two resolutions and then doing an interpolation between the two. Note that these geo clipmaps are all regular grids, not TINs so they are easy to use.
Each clipmap is a power of 2 difference from the previous one. In this way it creates a terrain mip map pyramid in memory.

I will dump DX vertex buffers and index buffers since I must dynamically alter the contents of both given the current view. I'm not sure what kind of hardware penalty this will incur, but it will open up video memory for more textures.

Ok first things first. I must get a raw data to terrain system working. Pre-creating the vertex grid will not do. I must create the grid on the fly in order to support paging. I could create a large grid and then load when the camera moves off the grid, but that is for later.

So I think I've figured out how to do this, but it's not using geo clipmaps.

The big problem with the transition from raw data to vertices is that the world position of the vertices is NOT encoded in the height file. It is extremely simple to determine where in the world the camera is, because we already know this. Now we load into memory all the terrain surrounding the player. Once we have the data we now have to figure out the world x and z coords of the data points. Here is what I've come up with.

Since world coordinates have nothing to do with camera position, it is quite simple to figure out where in the world a given data point is. World position of a data point in a grid is determined by subtracting it's row and column from the row,column of the center point in a heightfield or height map.

So if we want a 5000 x 5000 viewing frustum and a most resolute cell size of 16 we can determine where in the world these data points are by subtracting the row,column of the data point from the center row,column and multiplying by the cellsize. In order for this to work correctly, we must subtract from the center point of the entire map system. Let's say we are in China and we need to figure out our world coords after we have extracted the row and column, we subtract from the center row and column - not for the China area, but for the entire world. If the center of the world is Africa then we subtract our row,column from that point in the Africa zone which represents the center of our world. Otherwise we will get local coords as it relates to the China zone.
Now you could store the mid x and z's for the zones which would be ideal so you could subtract from those x and z's to get your world coords correct. It's quite complex actually.

There is the problem of dealing with negative row and columns but by using a modulus operation on the world coords, you can find out how many maps (given a known same size map width and height for all sections) you are left/right above/below the center map zone. Then you can determine where the leftmost portion of the map you are in is by using the above value and multiplying by the WorldMapWidth and WorldMapHeight value. Then you subtract the world point we computed from the leftmost and topmost value and divide by cellsize to determine the correct row and column for the current map.

The main problem is bridging the gap between map sections. Worst case scenario would be the camera looking across 4 map sections at a time which would require a significant amount of CPU time to determine the mesh for this viewpoint. A solution to this method would be to cache all eight neighbors into memory and keep them there for reference. When the user moves into another map section, then cache it's 8 neighbors as well. This would have to be done in a thread that could track the camera's movements and keep track of the relative movement amounts. When these amounts exceeded the known mapsize, it would then begin reading from disk into the eight map caches. This might stall rendering for a bit, but it wouldn't be too bad. We can cache as much or as little data as we would need since the likelihood of the camera flying through the current map before we cache all of the neighbors is minimal or next to impossible, given we use a realistic map size.

Now creating the vertices for these maps will have to be extremely fast. I will probably use a quad-tree approach and for larger resolutions, I will simply skip values in the height map since this is esssentially what is going on. Since I'm not using a grid in memory I can render this map front to back and take advantage of the zbuffer to increase the framerates.
For frustum culling I will probably cull the quadtree nodes based on their min and max. Then when a section passes the cull, I will create the vertices for that section dynamically while at the same time using the camera to point CLOD mechanism to determine the step size in the world and in the corresponding data.

If this works as planned I should be able to allow fly throughs on huge terrain sets that will only be limited by hard disk storage. It will only send vertices down the pipeline that are known to be visible since it only creates them if it's bounding volume passes the cull test.
The CLOD mechanism should work using step sizes and cell sizes. T intersections can be solved by storing the last resolution type and then adjusting 'in-between' vertices to match interpolated heights.

For instance if you have a map patch cellsize of 16 next to a cellsize of 32 you will have a T intersection. This can be eliminated by finding the two vertices connection the top line of the T intersection. Since the vertical line of the T is directly halfway between the 2 vertices, you simply set the height to be the interpolated halfway value between the Y of vertex 1 and the Y of vertex 2 and completely ignore the height value in the map for the vertex forming the T since that is the problem in the first place.

Hopefully I will have a rudimentary implementation of this in the next few weeks. This is not an easy problem to solve eh?

Why not subdivide *half* of the adjacent patch to line up with TVertex (ie. add a vertex at the centre of the flat quad connecting to TVertex). This would avoid T-Junctions in the first place, rather than correcting them afterwards.

Bubba, I am no where near where you are in GFX programming, but everytime I read one of your posts I am learning a lot more about the theory. You are one of the few on this board who explain everything you are going to do in a reasonable way. Granted I have to goto wikipedia now and again to find out wtf you are talking about but over all, I have to thank you for posts. I have a real perspective of doing 3d because of them.

Because in my system the subdivision is recursive which means I cannot choose which patch to subdivide or even which quad. It must be done after the subdivision step. Another approach is to reorder the tri's of the more resolute patch to directly match the borders of the less resolute patch.

Several papers on it here: www.vterrain.org

So far I've downloaded almost all of these PDFs and some from Hugues Hoppe homepage.

Will be doing a lot more reading before I start coding this
behemoth.

:)

As for data I'm going to create a proprietary file editor using MFC that will allow me to add heightfields to the larger data set. These will have headers indicating the world coordinates of the center of the map as well as the mapwidth/depth in world coords and actual height map coords.

Quote:

---

Originally Posted by Bubba

For instance if you have a map patch cellsize of 16 next to a cellsize of 32 you will have a T intersection. This can be eliminated by finding the two vertices connection the top line of the T intersection. Since the vertical line of the T is directly halfway between the 2 vertices, you simply set the height to be the interpolated halfway value between the Y of vertex 1 and the Y of vertex 2 and completely ignore the height value in the map for the vertex forming the T since that is the problem in the first place.

---

You're assuming that neighboring blocks are never more than one level of detail from each other. Rottger's algo solves this, but in my research on the subject I found a good method that sends suboptimal meshes for the edges of lower resolution blocks neighboring lower resolution blocks. Choosing which one to use is really a question of CPU time vs GPU time. The idea there is that you have one big quad sitting next to a bunch of little neighboring quads, so you render the big quad with a triangle fan and step through the neighboring side at the resolution of the smaller quads.
Boer explains this better than I do.

In my system they won't be. This is purely CLOD based on range from the camera so all patches will differ from each other in resolution by a power of 2, but what you described is what I'm currently doing and I don't like the outcome.

check mine XD http://i35.photobucket.com/albums/d1...me/Area/Mt.jpg

That's either real, from Crysis (the Far Cry 2 engine), RenderMonkey or it's Bryce.

Quote:

---

Originally Posted by Bubba

That's either real, from Crysis (the Far Cry 2 engine), RenderMonkey or it's Bryce.

---

Im pretty sure its terragen (looking at his index of images)

It looks familiar.